Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus,
Saarbrücken<EMAIL_ADDRESS>Kaiserslautern-Landau,
<EMAIL_ADDRESS>Egor Gorbachev and Marvin Künnemann [500]Theory
of computation Design and analysis of algorithms

###### Acknowledgements.

The second author thanks Karl Bringmann, Nick Fischer and Karol Węgrzycki for
helpful discussions. 0 2022 A

# Combinatorial Designs Meet Hypercliques:
Higher Lower Bounds for Klee’s Measure Problem and Related Problems in
Dimensions $d\geq 4$

Egor Gorbachev  Marvin Künnemann

###### Abstract

Klee’s measure problem (computing the volume of the union of $n$ axis-parallel
boxes in $\mathbb{R}^{d}$) is well known to have $n^{\frac{d}{2}\pm
o(1)}$-time algorithms (Overmars, Yap, SICOMP’91; Chan FOCS’13). Only
recently, a conditional lower bound (without any restriction to
“combinatorial” algorithms) could be shown for $d=3$ (Künnemann, FOCS’22). Can
this result be extended to a tight lower bound for dimensions $d\geq 4$?

In this paper, we formalize the technique of the tight lower bound for $d=3$
using a combinatorial object we call _prefix covering design_. We show that
these designs, which are related in spirit to combinatorial designs, directly
translate to conditional lower bounds for Klee’s measure problem and various
related problems. By devising good prefix covering designs, we give the
following lower bounds for Klee’s measure problem in $\mathbb{R}^{d}$, the
depth problem for axis-parallel boxes in $\mathbb{R}^{d}$, the largest-
volume/max-perimeter empty (anchored) box problem in $\mathbb{R}^{2d}$, and
related problems:

  * •

$\Omega(n^{1.90476})$ for $d=4$,

  * •

$\Omega(n^{2.22222})$ for $d=5$,

  * •

$\Omega(n^{d/3+2\sqrt{d}/9-o(\sqrt{d})})$ for general $d$,

assuming the 3-uniform hyperclique hypothesis. For Klee’s measure problem and
the depth problem, these bounds improve previous lower bounds of
$\Omega(n^{1.777...}),\Omega(n^{2.0833...})$ and
$\Omega(n^{d/3+1/3+\Theta(1/d)})$ respectively.

Our improved prefix covering designs were obtained by (1) exploiting a
computer-aided search using problem-specific insights as well as SAT solvers,
and (2) showing how to transform combinatorial _covering designs_ known in the
literature to strong prefix covering designs. In contrast, we show that our
lower bounds are close to best possible using this proof technique.

###### keywords:

Fine-grained complexity theory, non-combinatorial lower bounds, computational
geometry, clique detection

###### category:

##  1 Introduction

For various problems in computational geometry, the best known algorithms
display a running time of the form $n^{\Theta(d)}$ where $d$ denotes the
number of dimensions: Klee’s measure problem and the depth problem for axis-
parallel boxes in $\mathbb{R}^{d}$ can be solved in time $n^{d/2\pm o(1)}$
[40, 18, 19], a recent algorithm [21] computes the largest-volume empty axis-
parallel box among a given set of points in time
$\widetilde{\mathcal{O}}(n^{(5d+2)/6})$, the star discrepancy can be computed
in time $O(n^{d/2+1})$ [25], the maximum-weight rectangle problem can be
solved in time $O(n^{d})$ [9], to name few examples. Indeed, for all listed
problems, it can be shown [18, 28, 9] that an $n^{o(d)}$-time algorithm would
refute the Exponential Time Hypothesis (ETH). Thus, the subsequent challenge
is to determine running times $n^{f(d)}$ with $f(d)=\Theta(d)$ that are
optimal under fine-grained complexity assumptions. By the nature of these
running times (which quickly increase with $d$), it is particularly
interesting to determine optimal time bounds for small dimensions such as
$d\in\\{2,3,4,5\\}$.

For some of these problems, strong conditional lower bounds are known: For
Klee’s measure problem and the depth problem, Chan [18] gives a tight
conditional lower bound of $n^{d/2-o(1)}$ for _combinatorial_ algorithms –
roughly speaking, algorithms that avoid the algebraic techniques underlying
fast matrix multiplication algorithms. When considering general algorithms
(not only combinatorial ones), tight lower bounds are only known for
_weighted_ problems or small dimensions: For the weighted depth problem and
the maximum-weight rectangle problem, tight lower bounds of $n^{d/2-o(1)}$ and
$n^{d-o(1)}$, respectively, can be shown under the Weighted $k$-Clique
Hypothesis [8]. Showing strong lower bounds for the simpler, _unweighted_
problems appears to be more difficult, however. For Klee’s measure problem and
the unweighted depth problem, a recent result shows an $n^{d/(3-3/d)-o(1)}$
conditional lower bound under the 3-uniform hyperclique hypothesis [34], which
yields a tight bound for $d=3$, but not for $d\geq 4$.

Thus, the motivating question of this paper is the following:

_Can we prove conditional optimality of known algorithms for Klee’s measure
problem, the depth problem and related problems for small dimensions $d\geq
4$, such as $d\in\\{4,5,6\\}$?_

###  1.1 Our Results

As a starting point of this work, we formalize the approach used in [34] to
obtain tight hardness for $d=3$. To this end, we define the following
combinatorial object, which we term _prefix covering designs_ (due to its
conceptual similarity to certain combinatorial designs111In fact, we will
later establish a formal connection between these concepts.).

In the following definition, let $\binom{S}{t}$ denote the set of $t$-element
subsets of $S$.

######  Definition 1.1.

Let $d,K,\alpha\in\mathbb{N}$ with $d\geq 3$ and $K\geq 4$. A _$(d,K,\alpha)$
-prefix covering design_ consists of $d$ sequences $s_{1},\dots,s_{d}$ over
$[K]$ with the following properties.

  * •

Triplet condition: For every $\\{a,b,c\\}\in\binom{[K]}{3}$, there are
$i,i^{\prime},i^{\prime\prime}\in[d]$ and
$\ell,\ell^{\prime},\ell^{\prime\prime}\in\mathbb{N}_{0}$ such that

    * –

each element of $\\{a,b,c\\}$ is contained in $s_{i}[..\ell]$,
$s_{i^{\prime}}[..\ell^{\prime}]$, or
$s_{i^{\prime\prime}}[..\ell^{\prime\prime}]$. (Here, $s[..\ell]$ denotes the
prefix of the first $\ell$ elements of $s$.)

    * –

$\ell+\ell^{\prime}+\ell^{\prime\prime}\leq\alpha$.

  * •

Singleton condition: For every $x\in[K]$ occurring more than once in
$s_{1},\dots,s_{d}$, define $\ell_{\min}(x)$ ($\ell_{\max}(x)$) as the minimal
(maximal) $\ell$ such that there is some $i$ with $s_{i}[\ell]=x$. Then we
have

    * –

$\ell_{\min}(x)+\ell_{\max}(x)\leq\alpha+1$.

As an example, it is straightforward to see that for any $d$, the sequences
$s_{1}=(1,d+1),s_{2}=(2,d+1),\dots,s_{d}=(d,d+1)$ constitute a $(d,d+1,3)$
prefix covering design.222For the triplet condition, note that the triplet
$\\{a,b,c\\}\in\binom{[d]}{3}$ is contained in the prefixes
$s_{a}[..1],s_{b}[..1],s_{c}[..1]$ of total length $\alpha=3$ and that any
triplet $\\{a,b,d+1\\}$ with $\\{a,b\\}\in\binom{[d]}{2}$ is contained in the
prefixes $s_{a}[..2],s_{b}[..1]$ of total length $\alpha=3$. The singleton
condition only needs to be checked for $x=d+1$, for which we note that
$\ell_{\min}(d+1)=\ell_{\max}(d+1)=2$ and thus
$\ell_{\min}(d+1)+\ell_{\max}(d+1)=4\leq\alpha+1$ for $\alpha=3$.

Prefix covering designs constitute the core of the proof technique used in
[34]. Specifically, we show that the existence of good prefix covering designs
directly leads to strong lower bounds for several problems (these reductions
are implicit in [34] or adapted to prefix covering designs from [28]).

######  Proposition 1.2.

Let $d,K,\alpha\in\mathbb{N}$ such that there exists a $(d,K,\alpha)$ prefix
covering design. Unless the 3-uniform Hyperclique Hypothesis fails, there is
no $\varepsilon>0$ such that there exists an
$O(n^{\frac{K}{\alpha}-\varepsilon})$-time algorithm for any of the following
problems:

  * •

Klee’s Measure problem in $\mathbb{R}^{d}$,

  * •

Depth problem in $\mathbb{R}^{d}$,

  * •

Largest-Volume Empty Anchored Box problem in $\mathbb{R}^{2d}$,

  * •

Maximum-Perimeter Empty Anchored Box problem in $\mathbb{R}^{2d}$.

Beyond these problems, similar reductions are also possible for related
problems such as the Bichromatic Box problem in $\mathbb{R}^{2d}$ (given sets
of red and blue points, find the axis-parallel box containing the maximum
number of blue points while avoiding any red point) and various related
discrepancy problems such as the Star Discrepancy, see [28]. Note that there
is a blow-up in the dimension for the Empty Anchored Box problems, which turns
out to be unavoidable assuming the 3-uniform hyperclique hypothesis, as there
are $O(n^{(1/2-\varepsilon)d})$-algorithms for these problems (see below). At
this point, we only give a rough sketch of the reduction, with the full proof
deferred to Section A, where we also formally define all listed problems and
discuss the 3-uniform hyperclique hypothesis.

######  Proof 1.3 (Proof sketch for Proposition 1.2).

For each problem, we give a reduction from the 3-uniform hyperclique problem:
Given a 3-uniform hypergraph $G=(V,E)$ with $V=V^{(1)}\cup\cdots\cup V^{(K)}$
and $|V^{(1)}|=\cdots=|V^{(K)}|=n$, determine whether there are $v^{(1)}\in
V^{(1)},\dots,v^{(K)}\in V^{(K)}$ that form a clique in $G$. The 3-uniform
hyperclique hypothesis states that this problem requires running time
$n^{K-o(1)}$.

Intuitively, a special case of each of the problems listed above is to find an
axis-parallel box $Q$ satisfying certain properties. More specifically, any
candidate box $Q$ is given by choosing some value $v_{i}\in\\{0,\dots,U-1\\}$
for each dimension $i\in[d]$. We use a $(d,K,\alpha)$ prefix covering design
$s_{1},\dots,s_{d}$ to interpret the values $v_{1},\dots,v_{d}$ as choices of
vertices in $V^{(1)},\dots,V^{(K)}$: Namely, with
$s_{i}=(s_{i}[1],\dots,s_{i}[L])$, we think of any number
$v_{i}\in\\{0,\dots,U-1\\}$ with $U=n^{L}$ as a base-$n$ number
$v_{i}=(v_{i}[1],\dots,v_{i}[L])$. We interpret
$(v_{i}[1],\dots,v_{i}[L])\in\\{0,\dots,n-1\\}^{L}$ as choosing the
$(v_{i}[\ell]+1)$-st vertex in $V^{(s_{i}[\ell])}$ for all $1\leq\ell\leq L$.

With this encoding fixed, it remains to ensure that the only true solutions
$Q$ encode a _clique_ in $G$. This consists of two tasks: (1) ensuring that
the candidate box $Q$ chooses vertices consistently, i.e., for each $V^{(x)}$
such that $x$ occurs in more than one $s_{i}$, we need to make sure that the
same vertex is chosen in each occurrence, and (2) ensuring that the chosen
vertices form a clique. Crucially, for both tasks, our geometric problems
allow us to exclude candidate boxes $Q$ where the $v_{i}$ have certain
prefixes. Specifically, due to the singleton condition, we only need to
construct $O(n^{\alpha})$ boxes to ensure consistency of the remaining
candidate solutions $Q$. Likewise, the triplet condition is used to ensure
that all candidate boxes $Q$ that encode a non-clique (for which one of the
triplets $\\{v^{(a)},v^{(b)},v^{(c)}\\}$ is not an edge in $G$) are excluded,
using only $O(n^{\alpha})$ additional boxes. In total, this creates an
instance of size $O(n^{\alpha})$ for the target problem, which yields an
$n^{\frac{K}{\alpha}-o(1)}$ lower bound under the 3-uniform hyperclique
hypothesis.

From Proposition 1.2, we obtain the following direct corollary.

######  Corollary 1.4.

For any $d\geq 3$, let
$\gamma_{d}\coloneqq\sup\\{\frac{K}{\alpha}\mid\text{there is a
}(d,K,\alpha)\text{ prefix covering design}\\}$. Then for no $\varepsilon>0$
there exists an $O(n^{\gamma_{d}-\varepsilon})$-algorithm for any of the
problems listed in Proposition 1.2, unless the 3-uniform hyperclique
hypothesis fails.

The tight conditional lower bound [34] for Klee’s Measure problem and the
depth problem in $\mathbb{R}^{3}$ follows from the following construction: For
any $g\in\mathbb{N}$, we set $K=3g$, write
$[K]=\\{a_{1},\dots,a_{g},b_{1},\dots,b_{g},c_{1},\dots,c_{g}\\}$ and observe
that

$s_{1}=(a_{1},\dots,a_{g},b_{g},\dots,b_{1}),s_{2}=(b_{1},\dots,b_{g},c_{g},\dots,c_{1}),s_{3}=(c_{1},\dots,c_{g},a_{g},\dots,a_{1})$

provide a $(3,3g,2g+1)$ prefix covering design. Thus, we obtain
$\gamma_{3}\geq\lim_{g\to\infty}\frac{3g}{2g+1}=\frac{3}{2}$, establishing an
$n^{\frac{3}{2}-o(1)}$ conditional lower bound for KMP in $\mathbb{R}^{3}$ and
related problems.333It is not hard to prove that $\gamma_{3}\leq\frac{3}{2}$,
resulting in $\gamma_{3}=\frac{3}{2}$. This raises the question whether we can
find exact values of $\gamma_{d}$ for $d\geq 4$.

Given the direct applicability of prefix covering designs to Klee’s measure
problem, the depth problem and many related problems, it is only natural to
ask what the highest obtainable lower bounds are using this technique. For
one, designing better prefix covering designs gives stronger lower bounds. On
the other hand, establishing limits for prefix covering designs may indicate
potential for improved algorithms for KMP and related problems (such a
phenomenon has been observed in other contexts, e.g., [16]).

Our first result is that prefix covering designs cannot establish a higher
lower bound than $n^{\frac{d}{3}+O(\sqrt{d})}$. The following bound will be
proved in Section 3.

######  Proposition 1.5.

We have that
$\gamma_{d}\leq\frac{d}{3(1-\sqrt{\frac{2}{d}})}=\frac{d}{3}+\sqrt{\frac{2}{9}}\cdot\sqrt{d}+o(\sqrt{d})$.

However, as $\frac{d}{3(1-\sqrt{2/d})}\geq\frac{d}{2}$ for $d\leq 18$, this
result does not rule out tight lower bounds for small dimensions. In fact,
combining a computer-aided search with problem-specific insights, we give
improved constructions for $d\in\\{4,5\\}$, which give lower bounds that are
surprisingly close to $\frac{d}{2}$.

######  Theorem 1.6.

There is a $(4,40,21)$ prefix covering design, which yields
$\gamma_{4}\geq\frac{40}{21}>1.90476$.

There is a $(5,40,18)$ prefix covering design, which yields
$\gamma_{5}\geq\frac{40}{18}>2.22222$.

######  Proof 1.7.

The following sequences give a $(4,40,21)$ prefix covering design:

$\displaystyle s_{1}$ $\displaystyle=(1,2,3,4,5,6,7,8,9,10,40,19,28,37,26),$
$\displaystyle s_{2}$
$\displaystyle=(11,12,13,14,15,16,17,18,19,20,30,9,38,27,36),$ $\displaystyle
s_{3}$ $\displaystyle=(21,22,23,24,25,26,27,28,29,30,20,39,8,7,37),$
$\displaystyle s_{4}$
$\displaystyle=(31,32,33,34,35,36,37,38,39,40,10,29,18,17,27).$

The following sequences give a $(5,40,18)$ prefix covering design:

$\displaystyle s_{1}$ $\displaystyle=(1,2,3,4,5,6,7,8,24,31,38,30,14),$
$\displaystyle s_{2}$ $\displaystyle=(9,10,11,12,13,14,15,16,32,40,6,31,22),$
$\displaystyle s_{3}$ $\displaystyle=(17,18,19,20,21,22,23,24,8,7,39,15,30),$
$\displaystyle s_{4}$ $\displaystyle=(25,26,27,28,29,30,31,32,40,16,23,39,6),$
$\displaystyle s_{5}$ $\displaystyle=(33,34,35,36,37,38,39,40,16,32,15,23).$

For the readers’ convenience, we provide checker programs to verify the
singleton and triplet conditions in [1] (see Section B for details).

For Klee’s measure problem and the depth problem in $\mathbb{R}^{4}$ and
$\mathbb{R}^{5}$, the gap between the resulting conditional lower bound and
the known upper bound is thus at most $O(n^{0.09524})$ and $O(n^{0.27778})$,
respectively. This improves over previous hyperclique-based lower bounds of
$\Omega(n^{1.777})$ and $\Omega(n^{2.0833})$, respectively.

These results may (re-)ignite hope that it might be possible to find prefix
covering designs that establish tight lower bounds for $d=4$ and $d=5$. Alas,
by a careful investigation of the limits of prefix covering designs, we refute
this hope.

######  Theorem 1.8.

We have $\gamma_{4}<2$.

This result is proven via a careful analysis of the structure of prefix
covering designs with quality $\frac{K}{\alpha}$ approaching 2: We show that
certain _levels_ (i.e., $s_{1}[\ell],\dots,s_{4}[\ell]$ for certain values of
$\ell$) must have a very rigid structure. Essentially, every element on such a
level must have exactly a single copy on a corresponding other level. A
detailed analysis of all possibilities displays a contradiction; we cannot get
a quality $\frac{K}{\alpha}$ that is arbitrarily close to $2$. We give the
full proof in Section C. It remains an interesting question to determine the
precise value of $\gamma_{4}$; our results yield $1.90476\leq\gamma_{4}<2$.

#### Connection to covering designs

Our previous results give evidence of the intricacy of designing good prefix
covering designs. Unfortunately, designing optimized designs for small
dimensions like $d=4$ and $d=5$ offers little insights into the asymptotics in
$d$ as well as the general structure of good prefix designs for larger
dimensions.

We address this by providing general constructions that are applicable for all
$d$ and make use of the extensive literature on _combinatorial designs_.
Specifically, we observe an interesting connection between so-called _covering
designs_ (see, e.g., the surveys [38, 30, 31, 29] and [20] for an algorithmic
application in computational geometry) and prefix covering designs. A
$(v,k,t)$ covering design is a collection of $k$-sized subsets
$B_{1},\dots,B_{b}$ – called _blocks_ – of $[v]$ such that every $t$-element
subset of $[v]$ is fully contained in some block $B_{i}$. These covering
designs constitute a relaxation of balanced incomplete block designs.

Note that a $(d,K,\alpha)$ prefix covering design $s_{1},\dots,s_{d}$ where
each $s_{i}$ has length at most $L$ is superficially similar to a
$(v,k,t)$-covering design with $v=K$ elements, block size $k=L$, parameter
$t=3$ and $d$ blocks: in both designs, we cover triplets among $v=K$ elements
using $d$ sequences/blocks. However, there are two key differences. (1) In
covering designs, we cover each triplet in a single block, while in prefix
covering designs, we may use prefixes from up to three sequences. (2) The
sequences of prefix covering designs are inherently ordered (due to the
_prefix_ nature of the singleton and triplet conditions), while covering
designs have unordered blocks. A priori, it is unclear whether there is a
general way to use good covering designs to obtain good prefix covering
designs or vice versa. Maybe surprisingly, we show how to use good $(v,k,t)$
covering designs with $t=2$ (rather than $t=3$, which might appear as the more
natural correspondence) to obtain strong prefix covering designs.

Specifically, for any such covering design satisfying a mild matching-like
condition (which is satisfied by many constructions known in the literature),
we obtain high-quality prefix covering designs. We will see below that by
plugging in known constructions, we get prefix covering designs that are close
to optimal when $d\to\infty$.

######  Theorem 1.9.

Let $d\geq 3,k\in\mathbb{N}$ and $v$ be a multiple of $d$ such that there is a
$(v,k,2)$ covering design with $d$ blocks with the following property: For
every block $B_{i}$, there exists $U_{i}\subseteq B_{i}$ of size $\frac{v}{d}$
such that $U_{1},\dots,U_{d}$ partition $[v]$. Then
$\gamma_{d}\geq\frac{d}{3-2\frac{v}{kd}}$.

Let us give an example application of this theorem (see Sections 1.2 and B for
stronger consequences). It is well known that the projective plane of order
$q$ (where $q$ is a prime power) yields a set of $v=q^{2}+q+1$ points,
$d=q^{2}+q+1$ lines, with $k=q+1$ points on each line, such that every pair of
points is connected by a line. This yields a $(v,k,2)$-design with
$d=v=q^{2}+q+1$ and $k=q+1$. One can show that this design satisfies the
matching-like condition (see Section C). Thus, for infinitely many $d$, we
obtain a lower bound of $\gamma_{d}\geq\frac{d}{3-\frac{2}{q+1}}$. Since
$q=O(\sqrt{d})$, we obtain
$\gamma_{d}\geq\frac{d}{3-\Omega(1/\sqrt{d})}=\frac{d}{3}+\Omega(\sqrt{d})$
for infinitely many $d$, improving over the lower bound of
$\gamma_{d}\geq\frac{d}{3}+\frac{1}{3}+\frac{1}{3(d-1)}$ that is implicit in
[34].

###  1.2 Consequences: Improved conditional lower bounds

Using Theorem 1.9, we may take any $(v,k,2)$ covering design with $d$ blocks
that is known in the literature, check whether it satisfies the matching-like
condition, and obtain the corresponding lower bound on $\gamma_{d}$. In Table
1, we list lower bounds on $\gamma_{d},d\leq 10$ obtained this way,
specifically, by using covering designs listed in the La Jolla Covering
Repository [29] (see Section 2 for details). Notably, the resulting lower
bounds improve over the constructions in [34] for $d\geq 4$.

We also provide a lower bound for _all_ $\gamma_{d}$ that is close to optimal
when $d\to\infty$.

######  Theorem 1.10.

There is some function $f(d)=d/3+2\sqrt{d}/9-o(\sqrt{d})$ such that
$\gamma_{d}\geq f(d)$ for all $d\geq 3$.

This lower bound is obtained by showing how to extend the projective planes
covering designs (in a suitable way) to obtain strong prefix covering designs
for all values of $d$.

By the above theorem, we obtain a $n^{d/3+2/9\sqrt{d}-o(\sqrt{d})}$
conditional lower bound for Klee’s measure problem and related problems. Note
that Chan’s reduction from $K$-clique [18] can be interpreted as a lower bound
of $n^{(\omega/6)d-o(1)}$ assuming that current $K$-clique algorithms are
optimal. If $\omega=2$, this cannot give any higher lower bound than
$n^{d/3-o(1)}$.

Table 1 also lists the corresponding upper bound of $O(n^{d/2})$ for Klee’s
measure problem and the depth problem for comparison. The gaps for the
Largest-Volume/Maximum-Perimeter Empty (Anchored) Box problem in
$\mathbb{R}^{d}$ are a bit larger: Chan [21] obtains an upper bound444While
Chan focuses on the Largest-Volume Empty Box problem, he states that his
algorithms for $d\geq 4$ also work for the Maximum-Perimeter version, see [21,
Section 5]. for the anchored version of
$\widetilde{\mathcal{O}}(n^{d/3+\lfloor
d/2\rfloor/6})\leq\widetilde{\mathcal{O}}(n^{5d/12})$ for $d\geq 4$. In
particular, this yields upper bounds of $\widetilde{\mathcal{O}}(n^{2.5})$,
$\widetilde{\mathcal{O}}(n^{3.3334})$, and
$\widetilde{\mathcal{O}}(n^{4.1667})$ for $d=6$, $d=8$ and $d=10$,
respectively, while we supply a conditional lower bound of
$n^{\gamma_{d/2}-o(1)}$ for even $d\geq 6$, which yields lower bounds of
$n^{1.5-o(1)}$, $n^{1.9047-o(1)}$ and $n^{2.2222-o(1)}$ for $d=6$, $d=8$ and
$d=10$, respectively. It is an interesting question whether we can prove a
higher lower bound than $n^{d/4-o(1)}$ for any $d$ or whether Chan’s
algorithms can be improved further.

$d$ |  Upper bound |  Previously known lower bound |  SAT-solver lower bound |  Covering designs lower bound
---|---|---|---|---
$3$ |  $1.5$ |  $1.5$ |  |  $1.5$
$4$ |  $2$ |  $1.7777$ |  $1.9047$ |  $1.8461$
$5$ |  $2.5$ |  $2.0833$ |  $2.2222$ |  $2.1929$
$6$ |  $3$ |  $2.4$ |  |  $2.5714$
$7$ |  $3.5$ |  $2.7222$ |  |  $3$
$8$ |  $4$ |  $3.0476$ |  |  $3.3333$
$9$ |  $4.5$ |  $3.375$ |  |  $3.6818$
$10$ |  $5$ |  $3.7037$ |  |  $4.0540$
Table 1: The exponents of the upper and conditional lower bounds for Klee’s
measure problem and the depth problem in $\mathbb{R}^{d}$ for $d\leq 10$. The
upper bound column is due to the $n^{d/2\pm o(1)}$-time algorithms [40, 18,
19], the conditional lower bounds are based on the 3-uniform hyperclique
hypothesis and result from [34] (3rd column), Theorem 1.6 (4th column) and
from combining Theorem 1.9 with covering designs found in the La Jolla
Covering Repository maintained by D. Gordon [29] (5th column).

##### Related Work

Klee’s measure problem has been well-studied since the 1970s [33, 10, 27, 41,
40, 18, 19, 34], including algorithms beating $n^{d/2\pm o(1)}$ for various
special cases, e.g., [4, 11, 3, 12, 43, 13].

The depth problem for axis-parallel boxes is closely related to Klee’s measure
problem and often admits similar algorithmic ideas, see particularly [19].

Finding a largest-volume empty axis-parallel box has initially been mostly
studied in two dimensions (see, e.g., [39, 22, 5]). In higher dimensions,
Backer and Keil [7] give a $\widetilde{\mathcal{O}}(n^{d})$ algorithm, which
was recently improved to $\widetilde{\mathcal{O}}(n^{(5d+2)/6})$ by Chan [21].
Note that our lower bounds are most interesting for the anchored version of
the problem, which is solvable in faster running time
$\widetilde{\mathcal{O}}(n^{5d/12})$ [21]. Approximation algorithms have been
given in [26]. Giannopoulos et al. [28] give a reduction from $d$-clique,
which can be understood as an $n^{(\omega/12)d-o(1)}$ lower bound assuming
that current clique algorithms are optimal.

##  2 Constructions

In this section, we prove our general result transforming covering designs to
prefix covering designs (Theorem 1.9). All remaining proofs and details on
constructing prefix covering designs are deferred to Section B in the
appendix.

For a $(d,K,\alpha)$ prefix covering design (PCD) with sequences $s_{1}$,
$s_{2}$, $\ldots$, $s_{d}$ we call elements $s_{1}[i]$, $s_{2}[i]$, $\ldots$,
$s_{d}[i]$ the $i$-th level of the PCD.

When analyzing such prefix covering designs, it is helpful to distinguish
between the “first” occurrence of some element, which we call the _primary_
element, and all other occurrences, which we call _copies_. We call a pair
$(i,\ell)$ a position if $1\leq i\leq d$, $1\leq\ell$, and there exists
$\ell$-th element in $s_{i}$.

######  Definition 2.1.

For any prefix covering design $s_{1},\dots,s_{d}$, we call a position
$(i,\ell)$ the _primary position_ of value $x$ ($1\leq x\leq K$) if and only
if $s_{i}[\ell]=x$ and $s_{i^{\prime}}[\ell^{\prime}]\neq x$ for every other
position $(i^{\prime},\ell^{\prime})$ such that $(\ell^{\prime},i^{\prime})$
precedes $(\ell,i)$ in the lexicographic ordering.

Every other occurrence $(i^{\prime},\ell^{\prime})$ with
$s_{i^{\prime}}[\ell^{\prime}]=x$ is called a _copy_ of $x$.

Note that if $(i,\ell)$ is a primary position of value $x$, then
$\ell=\ell_{\min}(x)$.

######  Definition 2.2.

A $(v,k,t)$ covering design where $v\geq 2$, $k\geq t\geq 1$ is a collection
of $k$-element subsets (called blocks) of $[v]$ such that any $t$-element
subset is contained in at least one block.

In the following proof, we will be extensively using $(v,k,t)$ covering
designs for $t=2$. So, every pair of elements is contained in at least one
block.

######  Proof 2.3 (Proof of Theorem 1.9).

Consider some $(v,k,2)$ covering design consisting of $d$ blocks where $v$ is
divisible by $d$ and set $v^{\prime}\coloneqq\frac{v}{d}\in\mathbb{N}$. Define
$B_{1}$, $B_{2}$, $\ldots$, $B_{d}$ as the blocks of this covering design.
Assume there exist sets $U_{1}\subseteq B_{1}$, $U_{2}\subseteq B_{2}$,
$\ldots$, $U_{d}\subseteq B_{d}$ such that
$|U_{1}|=|U_{2}|=\ldots=|U_{d}|=v^{\prime}$ and $U_{1},U_{2},\ldots,U_{d}$
partition $[v]$. Then we will prove that for every $\varepsilon>0$, there
exist $K$ and $\alpha$ such that
$\frac{K}{\alpha}\geq\frac{d}{3-2\frac{v}{kd}}-\varepsilon$ and $(d,K,\alpha)$
PCD exists. From this we automatically get that
$\gamma_{d}\geq\frac{d}{3-2\frac{v}{kd}}$ by going to the limit.

$s_{1}$ | 8 | 9 | 10 | 1 | 2 | 3
---|---|---|---|---|---|---
$s_{2}$ | 11 | 12 | 13 | 4 | 1 | 5
$s_{3}$ | 14 | 15 | 16 | 7 | 1 | 6
$s_{4}$ | 17 | 18 | 19 | 6 | 2 | 4
$s_{5}$ | 20 | 21 | 22 | 2 | 5 | 7
$s_{6}$ | 23 | 24 | 25 | 3 | 4 | 7
$s_{7}$ | 26 | 27 | 28 | 5 | 3 | 6
Figure 1: Example of a ($7$, $28$, $10$) PCD construction from a $(7,3,2)$
covering design with $7$ blocks.

First, we present a slightly worse construction.

Order elements inside blocks of a given covering design in such a way that
elements of $U_{i}$ are located in the first $v^{\prime}$ positions of
$B_{i}$, i.e., $\\{B_{i}[j]\mid 1\leq j\leq v^{\prime}\\}=U_{i}$. To construct
sequences of our PCD, we take these blocks of the covering design and put $kd$
new different elements in front of them by prepending $k$ elements in each
sequence. In other words, the resulting PCD has sequences $s_{1}$, $s_{2}$,
$\ldots$, $s_{d}$ each of length $2k$ such that $s_{i}[j]=v+(i-1)\cdot k+j$
for $j\leq k$ and $s_{i}[j]=b_{i}[j-k]$ for $j>k$. An example for $d=7$ is
given in Figure 1. We will prove that this gives a $(d,K,\alpha)$ PCD with
$K=(v^{\prime}+k)d$ and $\alpha\leq 3k+v^{\prime}$.

There are $v^{\prime}d$ elements from a covering design and $kd$ more unique
elements that we added, so $K=(v^{\prime}+k)d$. It remains to check that
$\alpha\leq 3k+v^{\prime}$.

First, we check the singleton condition. Due to our ordering of the covering
design blocks, all primary positions of all elements are located in the first
$k+v^{\prime}$ levels, so $\ell_{\min}(x)\leq k+v^{\prime}$ for every element
$x$. At the same time, there are $2k$ elements in each sequence in total, so
$\ell_{\max}(x)\leq 2k$. Thus,
$\ell_{\min}(x)+\ell_{\max}(x)\leq(k+v^{\prime})+2k=3k+v^{\prime}$ for each
$x\in[K]$.

Second, we check the triplet condition. Assume we chose three elements $a$,
$b$ and $c$. Define their primary positions as $(i_{a},\ell_{a})$,
$(i_{b},\ell_{b})$ and $(i_{c},\ell_{c})$ respectively. Without loss of
generality, assume that $\ell_{a}\leq\ell_{b}\leq\ell_{c}$. Consider two
cases.

  1. 1.

If there is at most one element from the covering design among these three,
then $\ell_{a}\leq k$, $\ell_{b}\leq k$ and $\ell_{c}\leq k+v^{\prime}$, so we
can cover them with prefixes $s_{i_{a}}[..\ell_{a}]$, $s_{i_{b}}[..\ell_{b}]$
and $s_{i_{c}}[..\ell_{c}]$ of total size $\ell_{a}+\ell_{b}+\ell_{c}\leq
k+k+(k+v^{\prime})=3k+v^{\prime}$.

  2. 2.

If there are at least two elements from the covering design among these three,
then $b$ and $c$ are in the covering design. By the definition of a covering
design, there should be a sequence $s_{i}$ that contains both $b$ and $c$.
Thus we can cover all three elements with two prefixes: $s_{i}[..2k]$ (whole
sequence) and $s_{i_{a}}[..\ell_{a}]$ of total size $2k+\ell_{a}\leq
2k+(k+v^{\prime})=3k+v^{\prime}$.

This concludes the proof that $\alpha\leq 3k+v^{\prime}$ and already gives a
bound
$\gamma_{d}\geq\frac{K}{\alpha}\geq\frac{(k+v^{\prime})d}{3k+v^{\prime}}=\frac{d}{3}\cdot\frac{3k+3v^{\prime}}{3k+v^{\prime}}=\frac{d}{3}\cdot\left(1+\frac{2v^{\prime}}{3k+v^{\prime}}\right)=\frac{d}{3}\cdot\left(1+\frac{2v}{3dk+v}\right)$.

To improve this construction we will replicate the covering design $n$ times
for some positive integer $n$. Define $B_{i}^{j}$ for $1\leq i\leq d$ and
$1\leq j\leq n$ as the $i$-th block of the $j$-th copy of the covering design.
We want different copies of the covering design to be over different elements,
so the $v$ elements of $B^{j}$ are $\\{(j-1)v+1,\dots,jv\\}$. Define
$U_{i}^{j}$ as $v^{\prime}$-element subsets of $B_{i}^{j}$ such that
$U_{1}^{j}$, $U_{2}^{j}$, $\ldots$, $U_{d}^{j}$ partition
$\\{(j-1)v+1,\dots,jv\\}$. Define $R_{i}^{j}\coloneqq B_{i}^{j}\setminus
U_{i}^{j}$ as the remaining $k-v^{\prime}$ elements of each block. Also, for
every sequence of our PCD, we define $m\coloneqq nk-(n-1)v^{\prime}$ unique
elements that are put at the beginning of this sequence. Let these unique
elements for sequence $i$ be called $A_{i}$
($A_{i}=\\{nv+(i-1)m+1,\dots,nv+im\\}$). Now we are ready to construct the
sequences $s_{1},\dots,s_{d}$ of our prefix covering design by

$s_{i}=(A_{i},U_{i}^{1},U_{i}^{2},\ldots,U_{i}^{n},R_{i}^{n},R_{i}^{n-1},\ldots,R_{i}^{1}).$

An example of such a construction is given in Figure 2.

$s_{1}$ | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 1 | 8 | 15 | 19 | 20 | 12 | 13 | 5 | 6
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$s_{2}$ | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 2 | 9 | 16 | 15 | 21 | 8 | 14 | 1 | 7
$s_{3}$ | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 3 | 10 | 17 | 15 | 18 | 8 | 11 | 1 | 4
$s_{4}$ | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 4 | 11 | 18 | 19 | 16 | 12 | 9 | 5 | 2
$s_{5}$ | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 5 | 12 | 19 | 21 | 17 | 14 | 10 | 7 | 3
$s_{6}$ | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 6 | 13 | 20 | 16 | 17 | 9 | 10 | 2 | 3
$s_{7}$ | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 7 | 14 | 21 | 20 | 18 | 13 | 11 | 6 | 4
Figure 2: Example of a $(7,70,24)$ prefix covering design obtained by a scaled
construction with $v=7$ ($v^{\prime}=1$), $k=3$, $d=7$ and $n=3$.

We will prove that such a PCD has $K=(nk+v^{\prime})d$ and $\alpha\leq
3nk-(2n-3)v^{\prime}$, similarly to the proof for the simpler construction.
First, there are $v^{\prime}d$ elements from every covering design, and there
are $n$ designs, so overall, there are $nv^{\prime}d$ elements from covering
designs. Additionally, there are $md=nkd-(n-1)v^{\prime}d$ more unique
elements that we added, so $K=(nk+v^{\prime})d$ indeed. It remains to check
that $\alpha\leq T$ where $T\coloneqq 3nk-(2n-3)v^{\prime}$. We will use that
$T=2m+nk+v^{\prime}=3m+nv^{\prime}$.

First, we check the singleton condition. Due to our ordering of the covering
design blocks, all primary positions of all elements are located in the first
$m+nv^{\prime}$ levels, so $\ell_{\min}(x)\leq m+nv^{\prime}$ for every
element $x$. If $\ell_{\min}(x)\leq m$, this element has only one occurrence,
and we do not need to check the singleton condition for it. If
$\ell_{\min}(x)=m+(n-i)v^{\prime}+j$ for some $1\leq i\leq n$ and $1\leq j\leq
v^{\prime}$, then it means that element $x$ belongs to the $(n-i+1)$-st
covering design, and its other occurrences are located in the levels from
$m+nv^{\prime}+(i-1)(k-v^{\prime})+1$ to $m+nv^{\prime}+i(k-v^{\prime})$. So
$\ell_{\max}(x)\leq m+nv^{\prime}+i(k-v^{\prime})$. Consequently,
$\ell_{\min}(x)+\ell_{\max}(x)\leq(m+(n-i)v^{\prime}+j)+(m+nv^{\prime}+i(k-v^{\prime}))=2m+2nv^{\prime}+i(k-2v^{\prime})+j\leq
2m+2nv^{\prime}+n(k-2v^{\prime})+v^{\prime}=2m+nk+v^{\prime}=T<T+1$ where we
used the fact that $k-2v^{\prime}=k-2\frac{v}{d}\geq 0$ due to the lemma
below. We have even proved a slightly stronger inequality:

$\ell_{\min}(x)+\ell_{\max}(x)\leq T.$ (1)

######  Lemma 2.4.

For every $(v,k,2)$ covering design with $d\geq 2$ blocks, $k\geq 2v/d$ holds.

[Proof of Lemma] If $k<v$, then every element $x\in[v]$ should be located in
at least two sets: otherwise, we would cover only $k-1<v-1$ pairs involving
$x$, which contradicts the fact that it is a covering design. But if every
element is located in at least two sets, then the sum of all set sizes $kd$ is
at least $2v$. Dividing both numbers by $d$, we get the desired inequality.

If $k\geq v$, then $k\geq v\geq 2\frac{v}{d}$ because $d\geq 2$.

Second, we check the triplet condition. Consider any three elements $a$, $b$
and $c$. Define their primary positions as $(i_{a},\ell_{a})$,
$(i_{b},\ell_{b})$ and $(i_{c},\ell_{c})$ respectively. Without loss of
generality, assume that $\ell_{a}\leq\ell_{b}\leq\ell_{c}$. Consider two
cases.

  1. 1.

If at most one element out of these three is from covering designs, we know
that $\ell_{a}\leq m$, $\ell_{b}\leq m$ and $\ell_{c}\leq m+nv^{\prime}$, so
we can cover them with prefixes $s_{i_{a}}[..\ell_{a}]$,
$s_{i_{b}}[..\ell_{b}]$ and $s_{i_{c}}[..\ell_{c}]$ with total size
$\ell_{a}+\ell_{b}+\ell_{c}\leq m+m+(m+nv^{\prime})=3m+nv^{\prime}=T$.

  2. 2.

If at least two elements out of these three are from covering designs, then
$b$ and $c$ are in the covering designs. By the definition of a covering
design there should be a sequence $s_{i}$ that contains both $b$ and
$c$.555$b$ and $c$ may belong to different copies of our covering design, but
all copies are identical, so equivalent elements from all covering designs
occur in the same sequences, so there indeed should exist such $s_{i}$. Then
we can cover all three elements with two prefixes:
$s_{i}[..\max(\ell_{b}^{i},\ell_{c}^{i})]$ and $s_{i_{a}}[..\ell_{a}]$ where
$\ell_{b}^{i}$ and $\ell_{c}^{i}$ are positions of elements $b$ and $c$,
respectively, in the sequence $i$. We already know that elements $b$ and $c$
satisfy (1). It follows that
$\ell_{a}+\ell_{b}^{i}\leq\ell_{b}+\ell_{b}^{i}\leq T$ and
$\ell_{a}+\ell_{c}^{i}\leq\ell_{c}+\ell_{c}^{i}\leq T$. From this we can
conclude that $\ell_{a}+\max(\ell_{b}^{i},\ell_{c}^{i})\leq T$, as desired.

This concludes the proof that $\alpha\leq T=3nk-(2n-3)v^{\prime}$. This
construction gives us a bound
$\gamma_{d}\geq\frac{K}{\alpha}\geq\frac{(nk+v^{\prime})d}{3nk-(2n-3)v^{\prime}}=\frac{(k+\frac{v^{\prime}}{n})d}{3k-(2-\frac{3}{n})v^{\prime}}$
where $n\in\mathbb{N}$ can be chosen arbitrarily. When $n$ approaches
infinity, this value approaches
$\frac{kd}{3k-2v^{\prime}}=\frac{d}{3-\frac{2v^{\prime}}{k}}=\frac{d}{3-2\frac{v}{kd}}$.
Thus, for every $\varepsilon>0$ there exists $n$ such that such a construction
gives $\frac{K}{\alpha}\geq\frac{d}{3-2\frac{v}{kd}}-\varepsilon$, as desired.

We say that a $(v,k,2)$ covering design with $d$ blocks _admits a multi-
matching_ if for every block $B_{i}$ we can choose a subset $U_{i}$ of size
$v/d$ such that $U_{1},U_{2},\ldots,U_{d}$ partition $[v]$. The following
observation shows that in Theorem 1.9 it is not a restriction to assume that
$v$ is divisible by $d$, since we can always suitably scale covering designs:

Every $(v,k,2)$ covering design with $d$ blocks can be transformed into a
$(vd,kd,2)$ covering design with $d$ blocks by replacing each of $v$ elements
with $d$ distinct elements. If this scaled covering design admits a multi-
matching, we get a lower bound for $\gamma_{d}$ of
$\frac{d}{3-2\frac{(vd)}{(kd)d}}=\frac{d}{3-2\frac{v}{kd}}$.

The bound we give depends on the existence of specific covering designs
admitting multi-matchings. In Section B, we transform this lower bound into a
general lower bound depending only on $d$; in Table 3, we list the bounds we
obtain for specific values of $d$. These values were obtained as follows: for
a fixed value of $d$, the best lower bound can be obtained by finding a
covering design that minimizes the value $\mathrm{freq}\coloneqq\frac{kd}{v}$
which we call _frequency_ (for a fixed covering design, the frequency is the
average number of occurrences of elements). We searched for covering designs
in the La Jolla Covering Repository [29], fixing the number of blocks to $d$
and choosing the ones with the smallest frequencies. Then we multiplied the
number of elements and set sizes in these covering designs by $d$ using
Observation 2 (because Theorem 1.9 works only for covering designs with $v$
divisible by $d$) and checked whether they admit multi-matching. Perhaps
surprisingly, for all specific values of $d$ that we checked, the obtained
covering designs indeed admit a multi-matching. The covering designs used and
their multi-matchings can be found in [1] along with a computer program that
checks that provided constructions are indeed covering designs, and they
indeed admit multi-matchings.

The question remains whether the frequency in some dimension $d$ could be
minimized by a covering design that does _not_ admit a multi-matching. Indeed,
one can construct covering designs that do not admit a multi-matching.
However, since we aim to minimize the frequencies, we are considering covering
designs that should have a relatively small degree of redundancy — otherwise,
they probably could be improved. In Section B, we formulate the corresponding
conjecture that “sufficiently good” covering designs always admit a multi-
matching and discuss some evidence. We also provide weaker bounds obtained
from covering designs not admitting multi-matchings.

##  3 Limits

In this section, we prove limits of prefix covering designs, i.e., upper
bounds on $\gamma_{d}=\sup\\{\frac{K}{\alpha}\mid\text{there exists a
}(d,K,\alpha)\text{ prefix covering design}\\}$. The proof that $\gamma_{4}<2$
is deferred to Section C in the appendix.

The following lemma formalizes the intuition that increasing the value of $K$
can only lead to better (more precisely, not worse) prefix covering designs.

######  Lemma 3.1 (Scaling Lemma).

For every $(d,K,\alpha)$ PCD and positive integer $\lambda\in\mathbb{N}$,
there also exists a $(d,\lambda\cdot K,\lambda\cdot\alpha)$ PCD.

The proof of this fact is deferred to Section C in the appendix.

######  Proof 3.2 (Proof of Proposition 1.5).

For a fixed $(d,K,\alpha)$ PCD define
$g\coloneqq\left\lceil\frac{K}{d}\right\rceil$. If $\alpha\geq 3g$ then
$\frac{K}{\alpha}\leq\frac{K}{3g}\leq\frac{K}{3K/d}=\frac{d}{3}$ and the
proposition statement holds. Otherwise define $a\coloneqq\left\lceil
g-\frac{\alpha}{3}\right\rceil\geq 1$, i.e., $3(g-a)\leq\alpha<3(g-a+1)$. We
will prove that $a<\sqrt{\frac{2}{d}}+2$. If $a=1$, it is correct, so from now
on we assume that $a\geq 2$.

Define $B$ as the set of all elements $x$ that have $\ell_{\min}(x)>g-a$. We
claim that $|B|\geq d(a-1)$: The number of (not necessarily distinct) elements
in the first $(g-a)$ positions (over all $s_{i}$) is $d\cdot(g-a)=dg-
da<d\cdot(\frac{K}{d}+1)-da=K-d(a-1)$. Since there are $K$ distinct numbers in
total, the claim follows.

To prove the proposition, we will define a graph $G_{B}$ with vertex set $B$.
We connect two elements $x,y\in B$ by an edge if and only if there is some
sequence $s_{i}$ containing both $x$ and $y$. We obtain our result by proving
both an upper and a lower bound on the number of edges.

For a lower bound on the number of edges, consider how triplets
$\\{a,b,c\\}\in\binom{B}{3}$ are covered by prefixes: For any such triplet
$\\{a,b,c\\}$, there are prefixes $s_{i}[..\ell]$,
$s_{i^{\prime}}[..\ell^{\prime}]$ and
$s_{i^{\prime\prime}}[..\ell^{\prime\prime}]$ which contain $a$, $b$ and $c$
and satisfy $\ell+\ell^{\prime}+\ell^{\prime\prime}\leq\alpha$.

######  Claim 1.

Without loss of generality, we may assume that at least one of $\ell$,
$\ell^{\prime}$ and $\ell^{\prime\prime}$ is zero.

######  Proof 3.3.

If all of them are at least $g-a+1$, then
$\ell+\ell^{\prime}+\ell^{\prime\prime}\geq 3(g-a+1)>\alpha$, which yields a
contradiction. Otherwise, if at least one of them is at most $g-a$, then this
prefix cannot contain any of $a$, $b$ and $c$ as
$\ell_{\mathrm{min}}(a),\ell_{\mathrm{min}}(b),\ell_{\mathrm{min}}(c)>g-a$. We
can set this prefix to the empty prefix without loss of generality.

So indeed, we can imagine that triplets of elements in $B$ must be covered by
using only two prefixes, not three. In particular, for every triplet of
elements from $B$, at least two of them must occur in the same sequence, i.e.,
they must have an edge in $G_{B}$. Put differently, the complement graph of
$G_{B}$ is triangle-free and thus contains at most $|B|^{2}/4$ edges by
Mantel’s Theorem [37] (a special case of Turan’s Theorem). We conclude that
$G_{B}$ has at least
$\binom{|B|}{2}-\frac{|B|^{2}}{4}=\frac{|B|^{2}-2|B|}{4}\geq\frac{(|B|-2)^{2}}{4}$
edges because $|B|\geq 2$.

We now show that either the number of edges is at most $dg^{2}/2$ or $|B|\leq
2g$. We ask on which positions elements from $B$ can be located in the
sequences. We know that $\ell_{\min}(x)\geq g-a+1$ for any $x\in B$. At the
same time, if some element from $B$ is located in position $\geq 2(g-a)+3$ (in
some sequence $i$), then this must be its only occurrence since otherwise, it
would violate the singleton condition. Furthermore, any covering of a triplet
with such an element cannot contain elements from $B$ in other sequences
because it would take a prefix of length at least $2(g-a)+3$ in sequence $i$
and a prefix of length at least $g-a+1$ in some other sequence, which would
violate the triplet condition. From this, we can conclude that if every
triplet with this element and other elements in $B$ is covered, all elements
from $B$ have to occur in sequence $i$. We can assume that all elements have
indices at most $\alpha$ (otherwise, they are useless for coverings), so there
are at most $\alpha-(g-a)\leq 2g$ elements from $B$ in this sequence. This
yields $|B|\leq 2g$. In the remaining case all $x\in B$ satisfy
$\ell_{\max}(x)\leq 2(g-a)+2$ and $\ell_{\min}(x)>(g-a)$, so there are at most
$g-a+2\leq g$ elements from $B$ in each sequence. Thus, there are at most
$d\cdot\binom{g}{2}$ pairs of elements from $B$ that occur in the same
sequence.

From the above lower and upper bounds on the number of edges, we derive that

$\frac{(|B|-2)^{2}}{4}\leq d\cdot\binom{g}{2}<\frac{dg^{2}}{2}.$

Combining this with the fact that $d(a-1)\leq|B|$, we deduce that
$d(a-1)-2\leq|B|-2<\sqrt{2d}g$. (Note that in the case $|B|\leq 2g$, the upper
bound is trivially satsified since $d\geq 2$.) Consequently,

$a<\frac{\sqrt{2d}g+2}{d}+1\leq\sqrt{\frac{2}{d}}g+2$

for $d\geq 2$. We plug this inequality into our initial inequality on
$\alpha$:

$\alpha\geq
3(g-a)>3g\left(1-\sqrt{\frac{2}{d}}-\frac{2}{g}\right)\geq\frac{3K}{d}\left(1-\sqrt{\frac{2}{d}}-\frac{2}{g}\right).$

It follows that

$\frac{K}{\alpha}\leq\frac{K}{\frac{3K}{d}\left(1-\sqrt{\frac{2}{d}}-\frac{2}{g}\right)}=\frac{d}{3\cdot\left(1-\sqrt{\frac{2}{d}}-\frac{2}{g}\right)}.$

Due to Scaling Lemma 3.1 we know that if there exists a $(d,K,\alpha)$ PCD
then there also exists a $(d,K\cdot\lambda,\alpha\cdot\lambda)$ PCD for every
positive integer $\lambda$. If we plug this covering design into the
inequality above, we will get that

$\frac{K}{\alpha}=\frac{\lambda\cdot
K}{\lambda\cdot\alpha}\leq\frac{d}{3\cdot\left(1-\sqrt{\frac{2}{d}}-\frac{2}{g^{\prime}}\right)}$

where $g^{\prime}\coloneqq\left\lceil\frac{K\cdot\lambda}{d}\right\rceil$. If
we take $\lambda\to+\infty$ then $\frac{2}{g^{\prime}}\to 0$ and in the limit,
we get the desired upper bound on $\frac{K}{\alpha}$:

$\frac{K}{\alpha}\leq\frac{d}{3\cdot\left(1-\sqrt{\frac{2}{d}}\right)}=\frac{d}{3}\cdot\left(1+\frac{\sqrt{\frac{2}{d}}}{1-\sqrt{\frac{2}{d}}}\right)=\frac{d}{3}+\frac{\sqrt{2d}}{3\left(1-\sqrt{\frac{2}{d}}\right)}=\frac{d}{3}+\sqrt{\frac{2}{9}}\cdot\sqrt{d}+o(\sqrt{d}).$

##  4 Conclusion and Outlook

In this work, we make progress on obtaining tight conditional lower bounds for
Klee’s measure problem and related problems for $d\geq 4$. We give improved
lower bounds that leave gaps of only $O(n^{0.09524})$, $O(n^{0.27778})$ and
$O(n^{0.4286})$ for $d=4$, $d=5$ and $d=6$, respectively. On the negative
side, we prove that the proof technique via prefix covering designs and
Proposition 1.2 — despite yielding a tight lower bound for $d=3$ — cannot give
tight lower bounds for $d\geq 4$, so that a novel reduction approach is needed
for this task. Of course, it remains a tantalizing possibility that the
$n^{d/2\pm o(1)}$ running time for Klee’s measure problem for large dimensions
$d\geq 4$ can be broken.

We feel that the prefix covering designs formalized in this work are
interesting in their own right. We establish a connection to the well-studied
covering designs, by giving a framework that turns 2-covering designs into
prefix covering designs. This connection leads to the asymptotic bound
$\gamma_{d}=\frac{d}{3}+\Theta(\sqrt{d})$, leading to an
$n^{d/3+\Theta(\sqrt{d})}$ conditional lower bound for Klee’s measure problem
and related problems, improving over a previous bound of
$n^{d/3+1/3+\Omega(1/d)}$.

## References

  * [1] Codes and constructions for _Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions $d\geq 4$_.  https://github.com/Peltorator/klees-measure-lower-bounds-repo.
  * [2] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof.  More consequences of falsifying SETH and the orthogonal vectors conjecture.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 253–266. ACM, 2018.  doi:10.1145/3188745.3188938.
  * [3] Pankaj K. Agarwal.  An improved algorithm for computing the volume of the union of cubes.  In David G. Kirkpatrick and Joseph S. B. Mitchell, editors, Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pages 230–239. ACM, 2010.  doi:10.1145/1810959.1811000.
  * [4] Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir.  Computing the volume of the union of cubes.  In Jeff Erickson, editor, Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 294–301. ACM, 2007.  doi:10.1145/1247069.1247121.
  * [5] Alok Aggarwal and Subhash Suri.  Fast algorithms for computing the largest empty rectangle.  In D. Soule, editor, Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, pages 278–290. ACM, 1987.  doi:10.1145/41958.41988.
  * [6] Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, and Maria Paula Parga Nina.  The fine-grained complexity of multi-dimensional ordering properties.  Algorithmica, 84(11):3156–3191, 2022.  doi:10.1007/s00453-022-01014-x.
  * [7] Jonathan Backer and J. Mark Keil.  The mono- and bichromatic empty rectangle and square problems in all dimensions.  In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, volume 6034 of Lecture Notes in Computer Science, pages 14–25. Springer, 2010.  doi:10.1007/978-3-642-12200-2\\_3.
  * [8] Arturs Backurs, Nishanth Dikkala, and Christos Tzamos.  Tight hardness results for maximum weight rectangles.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 81:1–81:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.ICALP.2016.81.
  * [9] Jérémy Barbay, Timothy M. Chan, Gonzalo Navarro, and Pablo Pérez-Lantero.  Maximum-weight planar boxes in $o(n^{2})$ time (and better).  Inf. Process. Lett., 114(8):437–445, 2014.  doi:10.1016/j.ipl.2014.03.007.
  * [10] J. L. Bentley.  Algorithms for Klee’s rectangle problems.  Department of Computer Science, Carnegie Mellon University, Unpublished notes, 1977.
  * [11] Nicola Beume, Carlos M. Fonseca, Manuel López-Ibáñez, Luís Paquete, and Jan Vahrenhold.  On the complexity of computing the hypervolume indicator.  IEEE Trans. Evol. Comput., 13(5):1075–1082, 2009.  doi:10.1109/TEVC.2009.2015575.
  * [12] Karl Bringmann.  An improved algorithm for Klee’s measure problem on fat boxes.  Comput. Geom., 45(5-6):225–233, 2012.  doi:10.1016/j.comgeo.2011.12.001.
  * [13] Karl Bringmann.  Bringing order to special cases of Klee’s measure problem.  In Krishnendu Chatterjee and Jirí Sgall, editors, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087 of Lecture Notes in Computer Science, pages 207–218. Springer, 2013.  doi:10.1007/978-3-642-40313-2\\_20.
  * [14] Karl Bringmann, Nick Fischer, and Marvin Künnemann.  A fine-grained analogue of schaefer’s theorem in P: dichotomy of $\exists^{k}\forall$-quantified first-order graph properties.  In Amir Shpilka, editor, Proc. 34th Computational Complexity Conference (CCC 2019), volume 137 of LIPIcs, pages 31:1–31:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.CCC.2019.31.
  * [15] Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, and Zahra Parsaeian.  Towards sub-quadratic diameter computation in geometric intersection graphs.  In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 21:1–21:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.SoCG.2022.21.
  * [16] Karl Bringmann and Marvin Künnemann.  Improved approximation for fréchet distance on c-packed curves matching conditional lower bounds.  Int. J. Comput. Geom. Appl., 27(1-2):85–120, 2017.  doi:10.1142/S0218195917600056.
  * [17] Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt.  Answering (unions of) conjunctive queries using random access and random-order enumeration.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 393–409. ACM, 2020.  doi:10.1145/3375395.3387662.
  * [18] Timothy M. Chan.  A (slightly) faster algorithm for Klee’s measure problem.  Comput. Geom., 43(3):243–250, 2010.  doi:10.1016/j.comgeo.2009.01.007.
  * [19] Timothy M. Chan.  Klee’s measure problem made easy.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 410–419. IEEE Computer Society, 2013.  doi:10.1109/FOCS.2013.51.
  * [20] Timothy M. Chan.  Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back.  Discret. Comput. Geom., 61(4):899–922, 2019.  doi:10.1007/s00454-019-00062-5.
  * [21] Timothy M. Chan.  Faster algorithms for largest empty rectangles and boxes.  In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 24:1–24:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021\.  doi:10.4230/LIPIcs.SoCG.2021.24.
  * [22] Bernard Chazelle, Robert L. (Scot) Drysdale III, and D. T. Lee.  Computing the largest empty rectangle.  SIAM J. Comput., 15(1):300–315, 1986.  doi:10.1137/0215022.
  * [23] Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, and Nicole Wein.  Approximation algorithms and hardness for $n$-pairs shortest paths and all-nodes shortest cycles.  In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 290–300. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00034.
  * [24] Mina Dalirrooyfard and Virginia Vassilevska Williams.  Induced cycles and paths are harder than you think.  In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 531–542. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00057.
  * [25] David P. Dobkin, David Eppstein, and Don P. Mitchell.  Computing the discrepancy with applications to supersampling patterns.  ACM Trans. Graph., 15(4):354–376, 1996.  doi:10.1145/234535.234536.
  * [26] Adrian Dumitrescu and Minghui Jiang.  On the largest empty axis-parallel box amidst _n_ points.  Algorithmica, 66(2):225–248, 2013.  doi:10.1007/s00453-012-9635-5.
  * [27] Michael L. Fredman and Bruce W. Weide.  On the complexity of computing the measure of u[ai, bi].  Commun. ACM, 21(7):540–544, 1978.  doi:10.1145/359545.359553.
  * [28] Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner.  Hardness of discrepancy computation and $\varepsilon$-net verification in high dimension.  J. Complex., 28(2):162–176, 2012.  doi:10.1016/j.jco.2011.09.001.
  * [29] Daniel M. Gordon.  La jolla covering repository.  https://www.dmgordon.org/cover/.  Accessed: 2022-11-27.
  * [30] Daniel M. Gordon, Greg Kuperberg, and Oren Patashnik.  New constructions for covering designs.  Journal of Combinatorial Designs, 3:269–284, 1995.
  * [31] Daniel M. Gordon and Douglas R. Stinson.  Coverings.  In Charles J. Colbourn and Jeffrey H. Dinitz, editors, Handbook of Combinatorial Designs. 2006.
  * [32] Albert E. Ingham.  On the difference between consecutive primes.  Quarterly Journal of Mathematics, 1:255–266, 1937.
  * [33] Victor Klee.  Can the measure of $\bigcup_{1}^{n}[a_{i},b_{i}]$ be computed in less than $O(n\log n)$ steps?  The American Mathematical Monthly, 84(4):284–285, 1977.
  * [34] Marvin Künnemann.  A tight (non-combinatorial) conditional lower bound for Klee’s measure problem in 3d.  In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 555–566. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00059.
  * [35] Marvin Künnemann and Dániel Marx.  Finding small satisfying assignments faster than brute force: A fine-grained perspective into boolean constraint satisfaction.  In Shubhangi Saraf, editor, Proc. 35th Computational Complexity Conference (CCC 2020), volume 169 of LIPIcs, pages 27:1–27:28. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.CCC.2020.27.
  * [36] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In Artur Czumaj, editor, Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2018.  doi:10.1137/1.9781611975031.80.
  * [37] W. Mantel.  Problem 28: Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff.  In Wiskundige Opgaven 10, pages 60–61. 1907.
  * [38] W. H. Mills and R. C. Mullin.  Coverings and packings.  In J. H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory: A Collection of Surveys, pages 371–399. Wiley, 1992.
  * [39] Amnon Naamad, D. T. Lee, and Wen-Lian Hsu.  On the maximum empty rectangle problem.  Discret. Appl. Math., 8(3):267–277, 1984.  doi:10.1016/0166-218X(84)90124-0.
  * [40] Mark H. Overmars and Chee-Keng Yap.  New upper bounds in Klee’s measure problem.  SIAM J. Comput., 20(6):1034–1045, 1991.  doi:10.1137/0220065.
  * [41] Jan van Leeuwen and Derick Wood.  The measure problem for rectangular ranges in d-space.  J. Algorithms, 2(3):282–300, 1981.  doi:10.1016/0196-6774(81)90027-4.
  * [42] Virginia Vassilevska Williams and Yinzhan Xu.  Truly subcubic min-plus product for less structured matrices, with applications.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 12–29. SIAM, 2020.  doi:10.1137/1.9781611975994.2.
  * [43] Hakan Yildiz and Subhash Suri.  On klee’s measure problem for grounded boxes.  In Tamal K. Dey and Sue Whitesides, editors, Proceedings of the 28th ACM Symposium on Computational Geometry, Chapel Hill, NC, USA, June 17-20, 2012, pages 111–120. ACM, 2012.  doi:10.1145/2261250.2261267.

##  Appendix A Reductions

In this section, we give the reductions from the 3-uniform hyperclique problem
to all considered problems.

We first state the 3-uniform $K$-hyperclique problem, using a $K$-partite
formulation that is well-known to be equivalent to the general case:

######  Problem A.1 (3-uniform $K$-hyperclique).

Let $K\geq 4$. We are given a $K$-partite 3-uniform hypergraph $G=(V,E)$,
i.e., $V$ is the disjoint union of vertex parts $V^{(1)},\dots,V^{(K)}$,
containing $n$ nodes each, and $E\subseteq\binom{V}{3}$ such that every edge
connects 3 vertices from different vertex parts. The task is to determine
whether there are $v_{1}\in V^{(1)},\dots,v_{K}\in V^{(K)}$ forming a
$K$-clique, i.e., $\\{v_{i},v_{j},v_{k}\\}\in E$ for all
$\\{i,j,k\\}\in\binom{[K]}{3}$.

While the $K$-clique problem in _graphs_ is well known to be solvable in time
$O(n^{(\omega/3)K})$ (whenever $K$ is divisible by 3), no algorithm is known
that beats brute-force running time $n^{K\pm o(1)}$ for the 3-uniform
$K$-hyperclique problem by a polynomial factor. In fact, it is known that the
algebraic approach for the fast $K$-clique algorithms cannot work for
$K$-hyperclique, see [36] for a thorough discussion. Correspondingly, the
following hypothesis has been formulated:

######  Hypothesis 2 (3-uniform $K$-hyperclique hypothesis).

For no $K\geq 4$ and $\varepsilon>0$, there is an $O(n^{K-\varepsilon})$-time
algorithm for the 3-uniform $K$-hyperclique problem.

A refutation of the 3-uniform $K$-hyperclique hypothesis would give a novel
$O(2^{(1-\varepsilon)n})$-algorithm for Max3SAT [2, 36], as well as improved
algorithms for Boolean CSPs parameterized by solution size [35] and model-
checking certain first-order properties [14]. It has been used to give strong
conditional lower bounds for various problems, e.g. [2, 36, 14, 42, 17, 6, 15,
24, 23].

We turn to the first set of problems: In the _coverage problem_ , we receive
$n$ axis-parallel boxes $A_{1},\dots,A_{n}$ and a bounding box $B$ as input,
and ask whether the union of $A_{1},\dots,A_{n}$ is equal to $B$. Trivially,
this problem is a special case of _Klee’s measure problem_ , which receives
$A_{1},\dots,A_{n}$ as input and asks to compute the volume of the union of
$A_{1},\dots,A_{n}$. Finally, the _depth problem_ for unweighted axis-parallel
box, receives $A_{1},\dots,A_{n}$ as input and asks to find a point that is
contained in the _maximum number of boxes_ , which we call the _depth_ of
$A_{1},\dots,A_{n}$. It is not difficult to see (cf., e.g. [18]) that the
coverage problem reduces to the depth problem with $n2^{d}$ boxes: For each
$A_{i}$, compute a set of $2^{d}$ boxes that cover the complement of $A_{i}$
in $B$. The depth of these boxes is (at least) $n$ if and only if the original
coverage problem is a NO instance.

Thus, by giving an efficient reduction to the coverage problem, we obtain the
same lower bounds for Klee’s measure problem and the depth problem. The
following proposition is implicit in the tight conditional lower bound for
Klee’s measure problem and the depth problem in 3D [34]:

######  Proposition A.2 (Implicit in [34]).

Let $d,K,\alpha\in\mathbb{N}$ such that there exists a $(d,K,\alpha)$ prefix
covering design. Unless the 3-uniform Hyperclique Hypothesis fails, there is
no $\varepsilon>0$ such that there exists an
$O(n^{\frac{K}{\alpha}-\varepsilon})$-time algorithm for:

  * •

the coverage problem for axis-parallel boxes in $\mathbb{R}^{d}$.

  * •

the depth problem for unweighted axis-parallel boxes in $\mathbb{R}^{d}$.

  * •

Klee’s measure problem for axis-parallel boxes in $\mathbb{R}^{d}$.

Before we give the proof, for technical reasons, we start with a simple
observation about prefix covering designs.

Let $s_{1},\dots,s_{d}$ be a $(d,K,\alpha)$ prefix covering design. Without
loss of generality, we may assume that all $s_{i}$ have equal length $\alpha$.
Let $s^{\prime}_{1},\dots,s^{\prime}_{d}$ denote the prefix covering design
obtained as follows: (1) we delete all elements $s_{i}[\ell]$ with
$\ell>\alpha$ and (2) for any sequence $s^{\prime}_{i}$ with $|s_{i}|<\alpha$,
we set $s^{\prime}_{i}[\ell]=s_{1}[1]$ for $|s_{i}|<\ell\leq\alpha$. Note that
$s^{\prime}_{1},\dots,s^{\prime}_{d}$ are of equal length $\alpha$. It is
straightforward to check that it remains a $(d,K,\alpha)$ prefix covering
design.

######  Proof A.3 (Proof of Proposition A.2).

Let $s_{1},\dots,s_{d}$ be a $(d,K,\alpha)$ prefix covering design. We reduce
the 3-uniform $K$-hyperclique problem to the coverage problem as follows: Let
$G=(V,E)$ denote a $K$-partite 3-uniform hypergraph with vertex parts
$V^{(1)},\dots,V^{(K)}$.

Let $L_{1},\dots,L_{d}$ denote the lengths of the sequences
$s_{1},\dots,s_{d}$ and let $L\coloneqq\max_{i}L_{i}$. We will specify an
instance of the coverage problem with bounding box $[0,U)^{d}$ where
$U\coloneqq n^{L}$. For any tuple
$v=(v[1],\dots,v[\ell])\in\\{0,\dots,n\\}^{\ell}$ with $\ell\leq L$, we define

$\mathrm{ind}(v)=v[1]n^{L-1}+v[2]n^{L-2}+\cdots+v[\ell]n^{L-\ell}.$

Thus, the hypercubes
$\prod_{i=1}^{d}[\mathrm{ind}(v_{i}),\mathrm{ind}(v_{i})+1)$ for
$v_{1},\dots,v_{d}\in\\{0,\dots,n-1\\}^{L}$ partition the bounding box. For
any subset $X\subseteq[K]$, we interpret $f:X\to\\{0,\dots,n-1\\}$ as choosing
the $(f(x)+1)$-st vertex in $V^{(x)}$, written $v_{f(x)}^{(x)}$, for each
$x\in X$. For any $v=(v[1],\dots,v[\ell])\in\\{0,\dots,n-1\\}^{\ell}$ with
$\ell\leq L$, we define

$\displaystyle I_{<}(v)$
$\displaystyle=[\mathrm{ind}(v[1],\dots,v[\ell-1],0),$
$\displaystyle\mathrm{ind}(v[1],\dots,v[\ell-1],v[\ell])),$ $\displaystyle
I(v)$ $\displaystyle=[\mathrm{ind}(v[1],\dots,v[\ell-1],v[\ell]),$
$\displaystyle\mathrm{ind}(v[1],\dots,v[\ell-1],v[\ell]+1)),$ $\displaystyle
I_{>}(v)$ $\displaystyle=[\mathrm{ind}(v[1],\dots,v[\ell-1],v[\ell]+1),$
$\displaystyle\mathrm{ind}(v[1],\dots,v[\ell-1],n)).$

Note that for any $v^{\prime}\in\\{0,\dots,n-1\\}^{L}$, the interval
$[\mathrm{ind}(v^{\prime}),\mathrm{ind}(v^{\prime})+1)$ is contained in $I(v)$
if and only if $v[1],\dots,v[\ell]$ agrees with
$v^{\prime}[1],\dots,v^{\prime}[\ell]$ (otherwise, they are disjoint).
Similarly, $[\mathrm{ind}(v^{\prime}),\mathrm{ind}(v^{\prime})+1)$ is
contained in $I_{<}(v)$ if and only if $v^{\prime}$ and $v$ agree on the first
$\ell-1$ positions _and_ $v^{\prime}[\ell]<v[\ell]$. An analogous statement
holds for $I_{>}(v)$. For the empty prefix $v=()$, we define $I(v)=[0,n^{L})$.

We will construct boxes of the following form: For any distinct dimensions
$i_{1},\dots,i_{k}\in[d]$ and intervals $I_{1},\dots,I_{k}$ in $[0,U)$, we
define the _checking box_
$B(i_{1}:I_{1},\dots,i_{k}:I_{k})=J_{1}\times\cdots\times J_{d}$ where
$J_{i_{1}}=I_{1},\dots,J_{i_{k}}=I_{k}$ and $J_{i}=[0,U)$ for all
$i\in[d]\setminus\\{i_{1},\dots,i_{k}\\}$.

We define two types of boxes. The first type are _edge-checking boxes_.
Specifically, for any $\\{a,b,c\\}\in\binom{[K]}{3}$, we will construct a box
as follows: According to the triplet condition of the prefix covering design
$s_{1},\dots,s_{d}$, there are $i,i^{\prime},i^{\prime\prime}\in[d]$ and
$\ell,\ell^{\prime},\ell^{\prime\prime}\in\mathbb{N}_{0}$ such that the set
$X$ of elements occurring in
$s_{i}[..\ell],s_{i^{\prime}}[..\ell^{\prime}],s_{i^{\prime\prime}}[..\ell^{\prime\prime}]$
satisfies $a,b,c\in X$ and $|X|\leq\alpha$. For any function
$f:X\to\\{0,\dots,n-1\\}$ with
$\\{v_{f(a)}^{(a)},v_{f(b)}^{(b)},v_{f(c)}^{(c)}\\}\notin E$, we define the
edge-checking box

$\displaystyle C_{a,b,c,f}=B($ $\displaystyle
i:I(f(s_{i}[1]),\dots,f(s_{i}[\ell])),$ $\displaystyle
i^{\prime}:I(f(s_{i^{\prime}}[1]),\dots,f(s_{i^{\prime}}[\ell^{\prime}])),$
$\displaystyle
i^{\prime\prime}:I(f(s_{i^{\prime\prime}}[1]),\dots,f(s_{i^{\prime\prime}}[\ell^{\prime\prime}]))).$

The second type of boxes are _consistency-checking boxes_. Specifically, for
any $x\in[K]$ that occurs more than once in $s_{1},\dots,s_{d}$ we do the
following. Let $(i,\ell_{\mathrm{min}})$ be such that $\ell_{\mathrm{min}}$ is
minimal with $s_{i}[\ell_{\mathrm{min}}]=x$. For every
$(i^{\prime},\ell^{\prime})\neq(i,\ell_{\mathrm{min}})$ with
$s_{i^{\prime}}[\ell^{\prime}]=x$, we let $X_{i^{\prime},\ell^{\prime}}$
denote the elements occurring in
$s_{i}[..\ell_{\mathrm{min}}],s_{i^{\prime}}[..\ell^{\prime}]$. By singleton
condition, we have $|X_{i^{\prime},\ell^{\prime}}|\leq\alpha$, since these
prefix have total length
$\ell_{\mathrm{min}}+\ell^{\prime}\leq\ell_{\mathrm{min}}(x)+\ell_{\mathrm{max}}(x)\leq\alpha+1$
and $x$ occurs in both of them. For each $f:X\to\\{0,\dots,n-1\\}$, we
construct the consistency-checking boxes

$\displaystyle C^{<}_{x,i^{\prime},\ell^{\prime},f}=B($ $\displaystyle
i:I(f(s_{i}[1]),\dots,f(s_{i}[\ell_{\mathrm{min}}-1]),f(x))$ $\displaystyle
i^{\prime}:I_{<}(f(s_{i^{\prime}}[1]),\dots,f(s_{i^{\prime}}[\ell^{\prime}-1]),f(x))),$
$\displaystyle C^{>}_{x,i^{\prime},\ell^{\prime},f}=B($ $\displaystyle
i:I(f(s_{i}[1]),\dots,f(s_{i}[\ell_{\mathrm{min}}-1]),f(x))$ $\displaystyle
i^{\prime}:I_{>}(f(s_{i^{\prime}}[1]),\dots,f(s_{i^{\prime}}[\ell^{\prime}-1]),f(x))).$

This finishes the construction of the reduction.

Recall that hypercubes
$\prod_{i=1}^{d}[\mathrm{ind}(v_{i}),\mathrm{ind}(v_{i})+1)$ for
$v_{1},\dots,v_{d}\in\\{0,\dots,n-1\\}^{L}$ partition the bounding box. We say
that $v_{1},\dots,v_{d}$ is a _consistent encoding_ , if for each
$(i,\ell),(i^{\prime},\ell^{\prime})$ with
$s_{i}[\ell]=s_{i^{\prime}}[\ell^{\prime}]$, we have
$v_{i}[\ell]=v_{i^{\prime}}[\ell^{\prime}]$. Note that there is a bijection
between consistent encodings $v_{1},\dots,v_{d}$ and $v^{(1)}\in
V^{(1)},\dots,v^{(K)}\in V^{(K)}$ given by setting
$v^{(x)}=v^{(x)}_{v_{i}[\ell]}$ for each $(i,\ell)$ with $s_{i}[\ell]=x$.

We claim that any hypercube
$\prod_{i=1}^{d}[\mathrm{ind}(v_{i}),\mathrm{ind}(v_{i})+1)$ for
$v_{1},\dots,v_{d}\in\\{0,\dots,n-1\\}^{L}$ remains uncovered by the
constructed boxes if and only if $v_{1},\dots,v_{d}$ gives a consistent
encoding of $K$-hyperclique in $G$:

  1. 1.

Any inconsistent encoding is covered by a corresponding consistency-checking
box: Specifically, let $x\in[K],i^{\prime},i^{\prime\prime}\in[d]$ and
$\ell^{\prime}\geq\ell^{\prime\prime}$ be such that
$s_{i^{\prime}}[\ell^{\prime}]=s_{i^{\prime\prime}}[\ell^{\prime\prime}]=x$,
$v_{i^{\prime}}[\ell^{\prime}]\neq v_{i^{\prime\prime}}[\ell^{\prime\prime}]$
and $\ell^{\prime}$ is minimal with this property, i.e., all positions
$(i,\ell)$ with $\ell<\ell^{\prime}$ are consistent. Then, let
$(i,\ell_{\mathrm{min}})$ be as chosen in the definition of the consistency-
checking boxes for $x$. Note that either $v_{i^{\prime}}[\ell^{\prime}]\neq
v_{i}[\ell_{\mathrm{min}}]$ or $v_{i^{\prime\prime}}[\ell^{\prime\prime}]\neq
v_{i}[\ell_{\mathrm{min}}]$; without loss of generality, assume that
$v_{i^{\prime}}[\ell^{\prime}]\neq v_{i}[\ell_{\mathrm{min}}]$. Recall that
$X_{i^{\prime},\ell^{\prime}}$ denotes the set of elements occurring in
$s_{i}[..\ell_{\mathrm{min}}],s_{i^{\prime}}[..\ell^{\prime}]$ and note that
$v_{i}[..\ell_{\mathrm{min}}],v_{i^{\prime}}[..\ell^{\prime}-1]$ is a
consistent encoding of some
$f:X_{i^{\prime},\ell^{\prime}}\to\\{0,\dots,n-1\\}$.

Conversely, it is straightforward to see that the hypercubes of all consistent
encodings are left uncovered by the consistency-checking boxes.

  2. 2.

The consistent encoding of any $v^{(1)}\in V^{(1)},\dots,v^{(K)}\in V^{(K)}$
that does _not_ form a hyperclique is covered by a corresponding edge-checking
box: Let $\\{a,b,c\\}\in\binom{[K]}{3}$ such that
$\\{v^{(a)},v^{(b)},v^{(c)}\\}\notin E$, witnessing that
$v^{(1)},\dots,v^{(K)}$ do not form a hyperclique. We claim that the
corresponding consistent encoding $v_{1},\dots,v_{d}$ is covered by the edge-
checking box $C_{a,b,c,f}$ for an appropriately chosen $f$. Specifically, let
$s_{i}[..\ell],s_{i^{\prime}}[..\ell^{\prime}],s_{i^{\prime\prime}}[..\ell^{\prime\prime}]$
denote the prefixes chosen according to the triplet condition, let $X$ denote
the set of elements occurring in these prefixes and let
$f:X\to\\{0,\dots,n-1\\}$ be defined by $f(s_{j}[t])=v_{j}[t]$ for all
$(j,t)\in\\{(i,1),\dots,(i,\ell),(i^{\prime},1),\dots,(i^{\prime},\ell^{\prime}),(i^{\prime\prime},1),\dots,(i^{\prime\prime},\ell^{\prime\prime})\\}$
(this is well-defined for the consistent encoding $v_{1},\dots,v_{d}$). Then
the hypercube $\prod_{i=1}^{d}[\mathrm{ind}(v_{i}),\mathrm{ind}(v_{i})+1)$ is
covered by this edge-checking box $C_{a,b,c,f}$, which exists since
$\\{v^{(a)},v^{(b)},v^{(c)}\\}\notin E$.

Conversely, it is straightforward to see that the only consistent encodings
covered by some edge-checking boxes $C_{a,b,c,f}$ correspond to vertex choices
$v^{(1)},\dots,v^{(K)}$ such that $\\{v^{(a)},v^{(b)},v^{(c)}\\}\notin E$.

Finally, we obtain our conditional lower bound: The number of constructed
edge-checking boxes $C_{a,b,c,f}$ is at most
$\binom{K}{3}n^{\alpha}=O(n^{\alpha})$ as there are at most $n^{\alpha}$
functions of the form $f:X\to\\{0,\dots,n-1\\}$ for $|X|\leq\alpha$.
Similarly, there are at most $O(n^{\alpha})$ consistency-checking boxes
$C^{<}_{x,i^{\prime},\ell^{\prime},f}$ and
$C^{<}_{x,i^{\prime},\ell^{\prime},f}$, as there are $O(1)$ choices for
$x,i^{\prime},\ell^{\prime}$ and at most $n^{\alpha}$ functions of the form
$f:X\to\\{0,\dots,n-1\\}$ for $|X|\leq\alpha$. These boxes can be constructed
in time $O(n^{\alpha})$. Thus, any $O(N^{\frac{K}{\alpha}-\varepsilon})$-time
algorithm for the coverage problem on $N=O(n^{\alpha})$ boxes would decide the
given 3-uniform $K$-hyperclique instance in time $O(n^{K-\alpha\varepsilon})$,
which would refute the 3-uniform hyperclique conjecture.

By the known reductions from the coverage problem to Klee’s measure problem
and the depth problem, the proposition follows.

Note that for Klee’s Measure Problem, the above reduction in fact shows a
$n^{K/\alpha-o(1)}$ lower bound already under the weaker assumption that
_counting_ $K$-hypercliques in 3-uniform hypergraphs requires time
$n^{K-o(1)}$.

#### Empty Box problems

We turn to problems of finding “large” axis-parallel boxes containing no
points. Specifically, in the Largest-Volume Empty Box problem, we are given a
set $P$ of $n$ points in $\mathbb{R}^{d}$ and a bounding box
$B_{0}=[0,U]^{d}$. The task is to find the largest-volume box $B$ in $B_{0}$
that contains no point of $P$ in its interior. We study the simpler _anchored_
variant, in which the box must have the form
$(0,b_{1})\times(0,b_{2})\times\cdots(0,b_{d})$, i.e., it has the origin as
one of its vertices.

Likewise, in the Maximum-Perimeter Empty Anchored Box problem, on the same
input, the task is to find the box $B$ of the form
$(0,b_{1})\times(0,b_{2})\times\cdots(0,b_{d})\subseteq B_{0}$ containing no
points of $P$ in its interior and maximizing $b_{1}+\cdots+b_{d}$.

We generalize the ideas from [28] for similar problems to exploit prefix
covering designs:

######  Proposition A.4.

Let $d,K,\alpha\in\mathbb{N}$ such that there exists a $(d,K,\alpha)$ prefix
covering design. Unless the 3-uniform Hyperclique Hypothesis fails, there is
no $\varepsilon>0$ such that there exists an
$O(n^{\frac{K}{\alpha}-\varepsilon})$-time algorithm for:

  * •

the Maximum-Perimeter Empty Anchored Box problem in $\mathbb{R}^{2d}$.

  * •

the Largest-Volume Empty Anchored Box problem in $\mathbb{R}^{2d}$.

######  Proof A.5.

We give a proof analogous to Proposition A.2, using ideas of the reduction
from $d$-clique to bichromatic rectangle given in [28]. We give the arguments
for the Max-Perimeter Empty Anchored Problem first, and describe the changes
for the Largest-Volume Empty Anchored Box Problem later.

As in [28], we view $\mathbb{R}^{2d}$ as the product of the two-dimensional
subspaces

$\mathbb{R}_{i}^{2}=\\{(x_{1},y_{1},\dots,x_{d},y_{d})\mid x_{j}=y_{j}=0,j\neq
i)\\}\subseteq\mathbb{R}^{2d}.$

For a point $p\in\mathbb{R}^{2d}$ and $i\in[d]$, we let $p_{i}$ denote its
projection to $\mathbb{R}_{i}^{2}$.

Let $s_{1},\dots,s_{d}$ be a $(d,K,\alpha)$ prefix covering design. We reduce
the 3-uniform $K$-hyperclique problem to the Maximum-Perimeter Empty Anchored
Box problem as follows: Let $G=(V,E)$ denote a $K$-partite 3-uniform
hypergraph with vertex parts $V^{(1)},\dots,V^{(K)}$.

By Observation A, we may assume that the sequences $s_{1},\dots,s_{d}$ have
equal length $L\coloneqq\alpha$. As in Proposition A.2, for any tuple
$v=(v[1],\dots,v[\ell])\in\\{0,\dots,n\\}^{\ell}$ with $\ell\leq L$, we define

$\mathrm{ind}(v)=v[1]n^{L-1}+v[2]n^{L-2}+\cdots+v[\ell]n^{L-\ell}.$

Let $U\coloneqq n^{L}$. To represent admissible choices of $\\{0,\dots,U-1\\}$
in $\mathbb{R}_{i}^{2}$, we use the scaffold construction of [28], i.e., we
define for every $x\in\\{0,\dots,U\\}$ the point $p(x;i)\in\mathbb{R}_{i}^{2}$
by

$p_{i}(x;i)=(x,U-x).$

For an anchored box $X$, let $b$ denote the vertex of $X$ opposite the origin.
Note that if $X$ contains no point $p(x;i)$, then the contribution of
$\mathbb{R}^{2}_{i}$ to the perimeter is at most $U+1$, which is attained, by
choosing $b$ such that $b_{i}=(x+1,U-x)$ for some $x\in\\{0,\dots,U-1\\}$.
Furthermore, the contribution of $\mathbb{R}^{2}_{i}$ to the perimeter is
$U+1$ only if $(x,U-x-1)<b_{i}$ for some $x\in\\{0,\dots,U-1\\}$.

Thus, any empty anchored box of perimeter $\geq d(2U+2)$ chooses, for each
$i\in[d]$, some $x_{i}\in\\{0,\dots,U-1\\}$ with $(x_{i},U-x_{i}-1)<b_{i}$. We
now view $x_{i}$ as $x_{i}\in\\{0,\dots,n-1\\}^{L}$ and introduce additional
points such that the corresponding choice gives an empty box if and only if
$x_{1},\dots,x_{d}$ encode a $K$-hyperclique in $G$ (according to the prefix
covering design $s_{1},\dots,s_{d}$).

As a gadget, we show how to introduce points that exclude certain intervals
$I\subseteq\\{0,\dots,U-1\\}$. Specifically, for any
$I\subseteq\\{0,\dots,U-1\\}$ and $i\in[d]$, we define
$q(I;i)\in\mathbb{R}^{2}_{i}$ by

$q_{i}(I;i)=(\min(I),U-\max(I)-1).$

For any distinct dimensions $i_{1},\dots,i_{k}\in[d]$ and intervals
$I_{1},\dots,I_{k}$ in $\\{0,\dots,U-1\\}$, we can define
$q(i_{1}:I_{1},\dots,i_{k}:I_{k})$ as _checking point_ analogous to the
_checking box_ $B(i_{1}:I_{1},\dots,i_{d}:I_{d})$ as

$q(i_{1}:I_{1},\dots,i_{d}:I_{d})=q(I_{1};i_{1})+\cdots+q(I_{d};i_{d}).$

Note that an empty box of perimeter $\geq d(U+1)$ that does not contain
$q(i_{1}:I_{1},\dots,i_{d}:I_{d})$ must choose, for each $i\in[d]$, some
$x_{i}\in\\{0,\dots,U-1\\}$, such that for all $j\in[k]$, $x_{k}\notin I_{k}$.
This gives precisely the same semantics as the edge-checking boxes in
Proposition A.2. Thus, we can define the checking objects $C_{a,b,c,f}$,
$C_{x,i^{\prime},\ell^{\prime},f}^{<}$, and
$C_{x,i^{\prime},\ell^{\prime},f}^{>}$ as in Proposition A.2 (by replacing
$B(\cdot)$ by $q(\cdot)$).

Note that we obtain $O(n^{\alpha})$ checking points $q(\cdot)$ (as analyzed in
Propostion A.2), as well as an additional $O(n^{\alpha})$ points $p(x;i)$ for
$x\in\\{0,\dots,U-1\\},i\in[d]$, since $U=n^{L}=n^{\alpha}$. We thus obtain
that a $O(N^{\frac{K}{\alpha}-\varepsilon})$-time algorithm for the Maximum-
Perimeter Empty Anchored Box problem on $N=n^{\alpha}$ points would give a
$O(n^{K-\alpha\varepsilon})$-time algorithm for the 3-uniform $K$-hyperclique
problem, refuting the 3-uniform hyperclique conjecture.

The above reduction can be adapted to the Largest-Volume Empty Anchored Box
problem in a straightforward way, analogously to the reduction to the Maximum
Empty Star problem in [28]. Namely, we define $C=\mu^{U}$ for some $\mu$ to be
determined later and replace the definition of each point
$p(x;i)\in\mathbb{R}_{i}^{2}$ by

$p_{i}(x;i)=(\mu^{i},\frac{C}{\mu^{i}}).$

This way, the largest-volume anchored box in $[0,C]^{2d}$ not containing any
point $p(x;i)$ chooses a vertex $b_{i}\in\mathbb{R}_{i}^{2}$ with
$b_{i}=(\mu^{x_{i}+1},C/\mu^{x_{i}})$, and has volume $(C\mu)^{d}$.
Furthermore, we replace the points $q(I;i)\in\mathbb{R}^{2}_{i}$ by

$q_{i}(I;i)=(\mu^{\min(I)},\frac{C}{\mu^{\max(I)-1}}).$

These point definitions lead to the same semantics as for the Maximum-
Perimeter Problem, where instead of an empty anchored box of perimeter
$d(U+1)$, we now search for an empty anchored box of volume $(C\mu)^{d}$. We
thus obtain a $n^{\frac{K}{\alpha}-o(1)}$ lower bound under the 3-uniform
hyperclique conjecture analogously to before.

##  Appendix B Constructions: Omitted Proofs and Details

$d$ |  Best known upper bound from [19] |  Previously known lower bound from [34] |  SAT-solver lower bound from Theorem 1.6 |  Covering designs lower bound from Theorem 1.9 |  ($v$, $k$) of the covering design
---|---|---|---|---|---
$3$ |  $1.5$ |  $1.5$ |  |  $1.5$ |  ($3$, $2$)
$4$ |  $2$ |  $1.777$ |  $1.9047$ |  $1.8461$ |  ($20$, $12$)
$5$ |  $2.5$ |  $2.0833$ |  $2.2222$ |  $2.1929$ |  ($45$, $25$)
$6$ |  $3$ |  $2.4$ |  |  $2.5714$ |  ($6$, $3$)
$7$ |  $3.5$ |  $2.7222$ |  |  $3$ |  ($7$, $3$)
$8$ |  $4$ |  $3.0476$ |  |  $3.3333$ |  ($24$, $10$)
$9$ |  $4.5$ |  $3.375$ |  |  $3.6818$ |  ($90$, $36$)
$10$ |  $5$ |  $3.7037$ |  |  $4.0540$ |  ($80$, $30$)
$11$ |  $5.5$ |  $4.0333$ |  |  $4.4160$ |  ($308$, $110$)
$12$ |  $6$ |  $4.3636$ |  |  $4.8$ |  ($36$, $12$)
$13$ |  $6.5$ |  $4.6944$ |  |  $5.2$ |  ($13$, $4$)
$14$ |  $7$ |  $5.0256$ |  |  $5.5322$ |  ($966$, $294$)
$15$ |  $7.5$ |  $5.3571$ |  |  $5.8823$ |  ($405$, $120$)
$16$ |  $8$ |  $5.6888$ |  |  $6.2249$ |  ($880$, $256$)
$17$ |  $8.5$ |  $6.0208$ |  |  $6.5796$ |  ($782$, $221$)
$18$ |  $9$ |  $6.3529$ |  |  $6.9428$ |  ($198$, $54$)
$19$ |  $9.5$ |  $6.6851$ |  |  $7.3076$ |  ($19$, $5$)
$20$ |  $10$ |  $7.0175$ |  |  $7.6923$ |  ($80$, $20$)
$21$ |  $10.5$ |  $7.35$ |  |  $8.0769$ |  ($21$, $5$)
Figure 3: Table of the exponents of lower bounds for Klee’s measure problem
and the depth problem in $\mathbb{R}^{d}$ for $d\leq 21$ acquired via covering
designs and its comparison to other lower and upper bounds. All the covering
designs used and a verifier program can be found in [1].

The constructions for $d=4$ and $d=5$ discussed below were obtained by
assuming that $K=gd$ for some positive integer $g$, fitting primary
occurrences of all elements in the first $g$ levels of sequences, i.e.,
$s_{i}[j]=(i-1)g+j$ for all $1\leq i\leq d$, $1\leq j\leq g$, and then running
a SAT-solver for fixed values of $d$, $g$ and $\alpha$ that tries to fill
levels from $g+1$-st to determine whether such PCDs exists. There is no
guarantee though that these constructions are optimal. For $d\geq 6$ the
constructions obtained by this SAT-solver were not better than the results
obtained by Theorem 1.9 for a general case, so we only discuss cases of $d=4$
and $d=5$ here.

######  Proof B.1 (Proof of Theorem 1.6).

We prove these two facts by presenting constructions of prefix covering
designs with desired values of $\frac{K}{\alpha}$.

For $d=4$ we present the following ($4$, $40$, $21$) PCD which gives us
$\frac{K}{\alpha}=\frac{40}{21}>1.90476$.

$s_{1}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 40 | 19 | 28 | 37 | 26
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$s_{2}$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 30 | 9 | 38 | 27 | 36
$s_{3}$ | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 20 | 39 | 8 | 7 | 37
$s_{4}$ | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 10 | 29 | 18 | 17 | 27

It is easy to see that this PCD has $d=4$ and $K=40$. Now we prove that
$\alpha=21$.

First, we check the singleton condition for all elements. Imagine we want to
check the singleton condition for element $x=10y+z$ where $0\leq y\leq 3$ and
$1\leq z\leq 10$. Then $\ell_{\min}(x)=z$. There are $15$ elements in every
sequence in total, so $\ell_{\max}(x)\leq 15$. It means that for $z\leq 7$ it
is true that $\ell_{\min}(x)+\ell_{\max}(x)\leq 7+15=22\leq 21+1$ and the
singleton condition holds. For $z\geq 8$ it is easy to see that every element
occurs exactly twice and $\ell_{\max}(x)=21-z$, so
$\ell_{\min}(x)+\ell_{\max}(x)=21\leq 21+1$. So the singleton condition also
holds.

The hard part is to prove the triplet condition. It is not hard to see that
most triplets can be covered by covering their primary positions. For the
remaining triplets, some observations may be done that reduce the search
space, but in the end, we still would need to go through many cases. Instead
of that, we provide a computer program that manually checks the singleton
condition for all elements and the triplet condition for all triplets
according to the definition. It can be found in [1].

For $d=5$ we present the following ($5$, $40$, $18$) PCD which gives us
$\frac{K}{\alpha}=\frac{40}{18}>2.22222$.

$s_{1}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 24 | 31 | 38 | 30 | 14
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$s_{2}$ | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 32 | 40 | 6 | 31 | 22
$s_{3}$ | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 8 | 7 | 39 | 15 | 30
$s_{4}$ | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 40 | 16 | 23 | 39 | 6
$s_{5}$ | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 16 | 32 | 15 | 23 |

It is again easy to see that this PCD has $d=5$ and $K=40$. Now we prove that
$\alpha=18$.

First, we check the singleton condition for all elements. Imagine we want to
check the singleton condition for element $x=8y+z$ where $0\leq y\leq 4$ and
$1\leq z\leq 8$. Then $\ell_{\min}(x)=z$. There are at most $13$ elements in
every sequence in total, so $\ell_{\max}(x)\leq 13$. It means that for $z\leq
6$ it is true that $\ell_{\min}(x)+\ell_{\max}(x)\leq 6+13=19\leq 18+1$ and
the singleton condition holds. Elements with $z=7$ are not located in the
level $13$, so for them $\ell_{\max}(x)\leq 12$ and
$\ell_{\min}(x)+\ell_{\max}(x)\leq 7+12=19\leq 18+1$. Elements with $z=8$ are
not located in the levels $12$ and $13$, so for them $\ell_{\max}(x)\leq 11$
and $\ell_{\min}(x)+\ell_{\max}(x)\leq 8+11=19\leq 18+1$.

The hard part again is to prove the triplet condition. We again skip this part
and refer to the computer program that does it provided in [1].

We try to answer a question raised in Section 2:

#### Do good covering designs always admit a multi-matching?

Phrasing it more formally, we get the following conjecture:

######  Conjecture B.2.

For every integer $d\geq 3$, there exists a bound $\beta_{d}>0$ such that
there exists at least one covering design with $d$ blocks with
$\mathrm{freq}\leq\beta_{d}$ and for all $(v,k,2)$ covering designs with $d$
blocks and $\mathrm{freq}\leq\beta_{d}$ their scaled version $(vd,kd,2)$
admits multi-matching.

In other words, if this conjecture would be true, it would mean that
$\gamma_{d}\geq\frac{d}{3-2/\mathrm{freq}_{d}}$ where $\mathrm{freq}_{d}$ is
the infimum of frequencies of all covering designs with $d$ blocks. We do not
know whether this conjecture is true or false, but there are some signs
indicating that it may be correct.

But what if this conjecture is false? Do we get any reasonable bounds? It
turns out the answer is “yes”. We can simply create covering designs that are
more redundant. Imagine there is a $(vd,kd,2)$ covering design with $d$ blocks
that does not admit multi-matching. Then we can create a $(vd,kd+v,2)$
covering design (where blocks are multisets instead of sets but it does not
bother us because we can leave only the first occurrence of every element in
every sequence of our prefix covering design) that admits multi-matching. This
can be done by adding unique $v$ values to every block (adding all $vd$ values
in total). For example, add $(i-1)v+1$, $(i-1)v+2$, $\ldots$, $iv$ to the
$i$-th block. In this way, these new elements may be chosen as unique elements
in each block for multi-matching. If we plug this covering design into our
formula, we get a $\frac{d}{3-2\frac{v}{kd+v}}$ lower bound. In Theorem 1.10
will see that for “good enough” covering designs $v=o(kd)$, so it does not
change the asymptotic lower bound in terms of $d$ but worsens lower bounds for
specific values of $d$.

######  Proof B.3 (Proof of Theorem 1.10).

Right now, we have some specific lower bounds for exact values of $d$ and some
generic construction for arbitrary $d$, which depends on covering design’s
“quality”. We would like to get lower bounds that depend only on $d$. To do
this, we look at specific covering designs admitting multi-matching.
Specifically, finite projective planes. They are $(m^{2}+m+1,m+1,2)$ covering
designs with $d=m^{2}+m+1$ blocks. They are known to exist for $m=p^{n}$ where
$p$ is a prime number and $n$ is a positive integer. Actually, projective
planes are even more powerful than covering designs, they are so-called
balanced incomplete block designs, which means that every element is located
in the same number of blocks, and every pair of elements is located in the
same number of blocks (in our case, exactly once). In this situation, every
block has size $m+1$, and every element is located in $m+1$ blocks. It means
that if we look at blocks and elements as a bipartite graph, every vertex in
both parts has degree $m+1$, so this is an $(m+1)$-regular bipartite graph.
Due to Hall’s theorem, it admits matching, so in every block, there exists a
unique element (in this case the number of blocks is equal to the number of
elements, so multi-matching is actually just a matching). So finite projective
planes satisfy the conditions of Theorem 1.9 and can be used to construct a
$\frac{d}{3-2\frac{v}{kd}}=\frac{d}{3-\frac{2}{k}}=\frac{d}{3}+\frac{d}{3}\cdot\frac{2}{3k-2}$
lower bounds for $d=m^{2}+m+1$ and $m$ being a prime power. This construction
gives us a
$\frac{d}{3}+\frac{d}{3}\cdot\frac{2}{3k-2}=\frac{d}{3}+\frac{d}{3}\cdot\frac{2}{3m+1}=\frac{d}{3}+\frac{2}{9}\cdot\frac{d}{m+\frac{1}{3}}=\frac{d}{3}+\frac{2}{9}\sqrt{d}+o\left(\sqrt{d}\right)$
lower bound for these specific values of $d$ (because
$\sqrt{d}-1<m+\frac{1}{3}<\sqrt{d}$).

Now we generalize this construction for all values of $d$. Remember how we
created scaled constructions for covering designs. We had $K=(nk+v^{\prime})d$
and $\alpha\leq 3nk-(2n-3)v^{\prime}$ where $v^{\prime}=\frac{v}{d}$ and all
elements had primary positions in the first $nk+v^{\prime}$ levels. To
generalize this construction for $d^{\prime}>d$, we will add $d^{\prime}-d$
new dimensions, and every one of them will contain $nk-(2n-1)v^{\prime}$
unique elements. We claim that the value of $\alpha$ is still $\leq
3nk-(2n-3)v^{\prime}$ because if a triplet contains at least one element from
these new dimensions, it can be covered by covering primary positions of all
three elements:
$(nk-(2n-1)v^{\prime})+(nk+v^{\prime})+(nk+v^{\prime})=3nk-(2n-3)v^{\prime}$.
And $K=(nk+v^{\prime})\cdot d+(nk-(2n-1)v^{\prime})\cdot(d^{\prime}-d)$. For
our specific case it means that $\alpha\leq 3nk-2n+3$ and
$K=(nk+1)d+(nk-2n+1)(d^{\prime}-d)=(nk+1)d^{\prime}-2n(d^{\prime}-d)$ because
$v^{\prime}=1$. Then
$\frac{K}{\alpha}\geq\frac{(nk+1)d^{\prime}-2n(d^{\prime}-d)}{3nk-2n+3}=\frac{(k+\frac{1}{n})d^{\prime}-2(d^{\prime}-d)}{3k-2+\frac{3}{n}}$.
It approaches $\frac{kd^{\prime}-2(d^{\prime}-d)}{3k-2}$ when $n$ approaches
infinity. It is equal to
$\frac{d^{\prime}}{3}\cdot\frac{3k-6\frac{d^{\prime}-d}{d}}{3k-2}=\frac{d^{\prime}}{3}(1+\frac{2-6\frac{d^{\prime}-d}{d^{\prime}}}{3k-2})=\frac{d^{\prime}}{3}+\frac{d^{\prime}}{3}\cdot\frac{2-6\frac{d^{\prime}-d}{d^{\prime}}}{3k-2}$.
For the fixed value of $d^{\prime}$ we will take $d\coloneqq
p_{i}^{2}+p_{i}+1$ where $p_{i}$ is the largest prime such that
$p_{i}^{2}+p_{i}+1\leq d^{\prime}$. The closer $d$, the better bound we will
get. On average, the distance between neighboring primes is logarithmic, so
$d^{\prime}-d\leq(p_{i+1}^{2}+p_{i+1}+1)-(p_{i}^{2}+p_{i}+1)=O(p_{i+1}^{2}-p_{i}^{2})=O(p_{i}\cdot(p_{i+1}-p_{i}))=O(\sqrt{d^{\prime}}\cdot\log
d^{\prime})$ on average but it may not hold in the worst case. Legendre’s
conjecture states that there is a prime between every two consecutive squares,
so that would mean that $p_{i+1}-p_{i}=O(\sqrt{p_{i}})$ which means that
$d^{\prime}-d=O\left(d^{\prime\frac{3}{4}}\right)$. But Legendre’s conjecture,
as its name hints, is a conjecture, so we will use a weaker result by Ingham
[32] that states that $p_{i+1}-p_{i}=O\left(p_{i}^{\frac{2}{3}}\right)$. For
us it means that $d^{\prime}-d=O\left(d^{\prime\frac{5}{6}}\right)$. At the
same time we know that
$k=m+1=\sqrt{d}+o\left(\sqrt{d}\right)=\sqrt{d^{\prime}}\pm
o\left(\sqrt{d^{\prime}}\right)$, so we can rewrite the lower bound in terms
of $d^{\prime}$:

$\frac{d^{\prime}}{3}+\frac{d^{\prime}}{3}\cdot\frac{2-6\frac{d^{\prime}-d}{d^{\prime}}}{3k-2}=\frac{d^{\prime}}{3}+\frac{d^{\prime}}{3}\cdot\frac{2-6\frac{O\left(d^{\prime\frac{5}{6}}\right)}{d^{\prime}}}{3\sqrt{d^{\prime}}\pm
o(\sqrt{d^{\prime}})}=$
$=\frac{d^{\prime}}{3}+\frac{d^{\prime}}{3}\cdot\frac{2-o(1)}{(3\pm
o(1))\sqrt{d^{\prime}}}=\frac{d^{\prime}}{3}+\frac{2}{9}\sqrt{d^{\prime}}-o\left(\sqrt{d^{\prime}}\right).$

Which matches the bound we would get if $d^{\prime}$ admitted finite
projective planes in the first two summands.

##  Appendix C Limits — Omitted Proofs

######  Proof C.1 (Proof of Scaling Lemma 3.1).

Let $s_{1},\dots,s_{d}$ be a $(d,K,\alpha)$ PCD and call $\lambda$ the
_scaling factor_. We construct a PCD $s^{\prime}_{1},\dots,s^{\prime}_{d}$
with $K^{\prime}\coloneqq\lambda\cdot K$ elements and
$\alpha^{\prime}\coloneqq\lambda\cdot\alpha$ by replacing every element of
$s_{1},\dots,s_{d}$ with $\lambda$ elements. Specifically, for every primary
position $(i,\ell)$ with value $x$, we replace $x$ by the elements $\lambda
x-\lambda+1,\lambda x-\lambda+2,\ldots,\lambda x-1,\lambda x$. If $(i,\ell)$
is a copy of $x$, we replace $x$ by the elements $\lambda x,\lambda
x-1,\ldots,\lambda x-\lambda+2,\lambda x-\lambda+1$.

We need to check that the triplet and singleton conditions for
$\alpha^{\prime}=\lambda\cdot\alpha$ are satisfied. For every triplet
$\\{a,b,c\\}\in\binom{[K^{\prime}]}{3}$ of elements, consider the triplet
$\left\\{\left\lceil\frac{a}{\lambda}\right\rceil,\left\lceil\frac{b}{\lambda}\right\rceil,\left\lceil\frac{c}{\lambda}\right\rceil\right\\}\subseteq[K]$.
666In the definition of prefix covering designs, the triplet condition should
be satisfied for all $\\{a,b,c\\}\in\binom{[K]}{3}$. We may assume that the
triplet condition should be satisfied for all $\\{a,b,c\\}\subseteq K$ because
if some of these three values are equal, we may add arbitrary values to make
it a triplet (it is possible because $K\geq 3$) and a coverage for such three
distinct elements will cover $\\{a,b,c\\}$. Since $s_{1},\dots,s_{d}$ is a
prefix covering design, there must exist prefixes $s_{i}[..\ell]$,
$s_{i^{\prime}}[..\ell^{\prime}]$ and
$s_{i^{\prime\prime}}[..\ell^{\prime\prime}]$ that cover this triplet and
satisfy $\ell+\ell^{\prime}+\ell^{\prime\prime}\leq\alpha$. It is easy to see
that prefixes $s^{\prime}_{i}[..\lambda\ell]$,
$s^{\prime}_{i^{\prime}}[..\lambda\ell^{\prime}]$ and
$s^{\prime}_{i^{\prime\prime}}[..\lambda\ell^{\prime\prime}]$ cover the
elements $\\{a,b,c\\}$ and have a total length of
$\lambda\ell+\lambda\ell^{\prime}+\lambda\ell^{\prime\prime}\leq\lambda\alpha=\alpha^{\prime}$.

The singleton condition follows similarly: Let $a\in[K^{\prime}]$ be an
element occurring at least twice in $s^{\prime}_{1},\dots,s^{\prime}_{d}$.
Define $x\coloneqq\left\lceil\frac{a}{\lambda}\right\rceil$ and
$y\coloneqq\lambda x-a$. Consider the primary position
$(i,\ell_{\mathrm{min}}(x))$ of the element $x$ in $s_{1},\dots,s_{d}$. Then
$s^{\prime}_{i}[\lambda\ell_{\mathrm{min}}(x)-y]=a$ by construction of
$s^{\prime}_{i}$. Thus,
$\ell^{\prime}_{\min}(a)\leq\lambda\ell_{\mathrm{min}}(x)-y$. On the other
hand, for any other position $(i,\ell)$ of $a$ in
$s^{\prime}_{1},\dots,s^{\prime}_{d}$, we have with
$z\coloneqq\left\lceil\frac{\ell}{\lambda}\right\rceil$ that $s_{i}[z]=x$ and
thus $\ell=\lambda(z-1)+y+1$ by construction of
$s^{\prime}_{1},\dots,s^{\prime}_{d}$. Since $z\leq\ell_{\max}(x)$, we
conclude that

$\displaystyle\ell_{\mathrm{min}}^{\prime}(a)+\ell_{\mathrm{max}}^{\prime}(a)$
$\displaystyle\leq(\lambda\ell_{\mathrm{min}}(x)-y)+(\lambda(\ell_{\mathrm{max}}(x)-1)+y+1)$
$\displaystyle=\lambda(\ell_{\mathrm{min}}(x)+\ell_{\mathrm{max}}(x)-1)+1\leq\lambda\alpha+1=\alpha^{\prime}+1,$

where in the last line we used that
$\ell_{\min}(x)+\ell_{\max}(x)\leq\alpha+1$ (since $s_{1},\dots,s_{d}$ is a
$(d,K,\alpha)$ PCD). Thus, $s^{\prime}_{1},\dots,s^{\prime}_{d}$ is a
$(d,\lambda K,\lambda\alpha)$ PCD, as desired.

######  Proof C.2 (Proof of Theorem 1.8).

Assume for contradiction that $\gamma_{4}\geq 2$. Then there exists a sequence
of $(4,K_{i},\alpha_{i})$ prefix covering designs such that
$\liminf_{i\to\infty}\frac{K_{i}}{\alpha_{i}}\geq 2$. By the Scaling Lemma 3.1
we may scale every prefix covering design in the sequence to have larger value
of $K_{i}$ than the previous one, so we may assume that $K_{i}<K_{i+1}$ for
all $i\geq 1$. We prove a series of properties that hold for all PCDs in this
sequence for sufficiently large $i$. For clarity of presentation (by a slight
abuse of notation), we will use asymptotic statements (over $i$) and write
$\alpha$ instead of $\alpha_{i}$ and $K$ instead of $K_{i}$. For example, we
can already write that $K\geq 2\alpha-o(\alpha)$ and
$\alpha\leq\frac{K}{2}+o(K)$. For any considered PCD
$s_{1},s_{2},\ldots,s_{d}$ we may also assume that no elements are located in
the same sequence $s_{i}$ twice because otherwise we could simply delete the
second occurance, and it could only improve the construction.

######  Lemma C.3.

If $\alpha\leq\frac{K}{2}+o(K)$, the largest level of a primary position is at
most $\frac{\alpha}{2}+o(\alpha)$.

######  Proof C.4 (Proof of Lemma C.3).

Call $(i_{m},m)$ the largest primary position (with largest $m$) of this PCD.
We will prove that $m\leq\frac{\alpha}{2}+o(\alpha)$. Assume for contradiction
that $m=\frac{\alpha}{2}+\varepsilon\alpha$ for some
$\varepsilon>\varepsilon_{0}>0$ where $\varepsilon_{0}$ is a constant
independent of $K$ and $\alpha$. It is easy to see that $s_{i_{m}}[m]$ cannot
have copies because otherwise, we would have $m+m^{\prime}\geq
m+m\geq\alpha+2\varepsilon\alpha>\alpha$ where $m^{\prime}$ is the level of
any copy, contradicting the singleton condition for $s_{i_{m}}[m]$. We prove
that prefix $s_{i_{m}}[..m]$ and prefixes
$s_{i}[..\frac{\alpha}{2}-\varepsilon\alpha]$ for all $i\neq i_{m}$ cover all
$K$ elements. Assume for contradiction that it is not true. Distinguish two
cases of where else elements can be located.

  1. 1.

If some element is located at a position $(i_{m},y)$ for $y\geq
m+1\geq\frac{\alpha}{2}+\varepsilon\alpha+1$ then it cannot be its primary
position because $m$ was the largest primary position, so this element should
have a primary position in some other sequence $i\neq i_{m}$ at level at most
$\frac{\alpha}{2}-\varepsilon\alpha$ for the singleton condition to hold. But
all such elements are covered by prefixes
$s_{i}[..\frac{\alpha}{2}-\varepsilon\alpha]$.

  2. 2.

If an element is not located in sequence $i_{m}$, define its primary position
as $(i_{y},y)$. But then we need prefixes of total size at least $m+y$ to
cover any triplet of form $\\{s_{i_{m}}[m],s_{i_{y}}[y],c\\}$ with $c\in[K]$.
So $m+y\leq\alpha$ which yields $y\leq\frac{\alpha}{2}-\varepsilon\alpha$, and
this element is covered by prefix
$s_{i_{y}}[..\frac{\alpha}{2}-\varepsilon\alpha]$.

So indeed these prefixes cover all elements. Thus, they must contain at least
$K$ elements. But their total size is
$m+3\cdot\left(\frac{\alpha}{2}-\varepsilon\alpha\right)=\frac{\alpha}{2}+\varepsilon\alpha+3\cdot\left(\frac{\alpha}{2}-\varepsilon\alpha\right)=(2-2\varepsilon)\alpha<(2-2\varepsilon_{0})\alpha<K$
for big enough $K$. So we get a contradiction.

Consequently, all primary positions are located on the first
$m=\frac{\alpha}{2}\pm o(\alpha)$ levels (it is obvious that
$m\geq\frac{\alpha}{2}-o(\alpha)$ as there are $K\geq 2\alpha-o(\alpha)$
elements that should have primary positions in $4$ sequences). But these
levels contain $K+o(K)$ elements in total, so almost all777Here and later,
_almost all_ is understood as all but $o(K)$. elements at these levels are
primary.

######  Lemma C.5.

Let $m$ denote the largest level of a primary position. There exists
$\varepsilon>0$ independent of $K$ such that every element with primary
position level $p$ with $(1-\varepsilon)m\leq p\leq m$ has at least one copy.

######  Proof C.6 (Proof of Lemma C.5).

Assume for contradiction that there exists an element with a primary position
level between $m-\varepsilon m$ and $m$ that does not have any copies. Define
its primary position, without loss of generality, as $(1,m-x)$ where $0\leq
x\leq\varepsilon m$. We distinguish two cases whether there exist any element
with a primary position in the levels $[m-2\varepsilon m,m]$ from sequences
$2$, $3$ or $4$ that does not have a copy or not.

  1. 1.

If it does exist, define its primary position without loss of generality as
$(2,m-y)$ where $0\leq y\leq 2\varepsilon m$. Consider how to cover triplets
of the form $\\{s_{1}[m-x],s_{2}[m-y],s_{i}[z]\\}$ for $i\in\\{3,4\\}$ and
$z\in[m-2\varepsilon m,m]$ such that $(i,z)$ is the primary position of
$s_{i}[z]$ (it exists as there are $4m=K+o(K)$ positions on the first $m$
levels, so almost all of them are primary). We cannot cover them with three
sequences because it would take
$\geq(3-5\varepsilon)m\geq\left(\frac{3-5\varepsilon}{2}-o(1)\right)\alpha>\alpha$
for small enough $\varepsilon$. Thus, we must cover such triplets with at most
two sequences. But $s_{1}[m-x]$ and $s_{2}[m-y]$ do not have copies, so
$s_{i}[z]$ must have some copy in sequence $1$ or $2$. If we copy it to
sequence $1$, its position must be $\leq m+2\varepsilon m+o(m)$ to comply with
the triplet condition, and if we copy it to sequence $2$, its position must be
$\leq m+\varepsilon m+o(m)$ to comply with the triplet condition. As we have
$o(m)$ copy positions in the first $m$ levels, it means that there are
$3\varepsilon m+o(m)$ suitable copy positions in the first two sequences in
total. But there are $4\varepsilon m-o(m)$ primary elements from layers
$[m-2\varepsilon m,m]$ in sequences $3$ and $4$ that should be copied. This
yields a contradiction.

  2. 2.

If there does not exist such an element $s_{2}[m-y]$, then all elements with
primary positions on levels $[m-2\varepsilon m,m]$ in sequences $2$, $3$ and
$4$ have copies. If some of them have copies in sequences $2$, $3$ or $4$ on
positions $\geq m+\varepsilon m+\delta m$ for some constant $\delta>0$
independent of $K$, these positions cannot be used to cover triplets
containing $s_{1}[m-x]$ due to the triplet condition, so this situation is
equivalent to the situation where such an element does not have a copy at all,
and we understood that it is impossible. So only levels $\leq m+\varepsilon
m+o(m)$ are available in the sequences $2$, $3$ and $4$ for copies. At the
same time, these elements have primary positions $\geq m-2\varepsilon m$, so
due to the singleton condition their copies in sequence $1$ cannot be higher
than level $m+2\varepsilon m+o(m)$. As we know that there are $o(m)$ copy
positions on the first $m$ levels of all sequences, there are $2\varepsilon
m+\varepsilon m+\varepsilon m+\varepsilon m+o(m)=5\varepsilon m+o(m)$ copy
positions for these elements. But there are $6\varepsilon m-o(m)$ such primary
elements from sequences $2$, $3$ and $4$ in total. Consequently, some of them
cannot have copies, yielding a contradiction.

######  Lemma C.7.

Let $m$ denote the largest level of a primary position. There exists
$\varepsilon>0$ independent of $K$ such that _almost_ every element with
primary position level $p$ with $(1-\varepsilon)m\leq p\leq m$ has _exactly_
one copy and this copy is located on level $2m-p\pm o(m)$.

######  Proof C.8 (Proof of Lemma C.7).

From Lemma C.5, we know that all of these elements with primary positions from
levels $[m-\varepsilon m,m]$ have at least one copy. At the same time, due to
the singleton condition, their copies should be on levels $\leq m+\varepsilon
m+o(m)$, and as we know, there are $o(m)$ copy positions in the first $m$
levels, so there are $4\varepsilon m+o(m)$ copy positions for them in total.
But there are $4\varepsilon m-o(m)$ such elements. Thus, almost all elements
with primary positions from levels $[m-\varepsilon m,m]$ have _exactly_ one
copy. For an element with primary position $(k,m-x)$, such a copy should be on
the level $\leq m+x+o(m)$ due to the singleton condition. At the same time,
its level can not be much smaller. Assume for contradiction that there are
$\geq\delta m$ elements with primary positions $(k_{i},m-x_{i})$ for some
constant $\delta>0$ independent of $K$, and their copies are located at
positions $y_{i}\leq m+x_{i}-\gamma m$ for some constant $\gamma>0$
independent of $K$. Define $S$ as the sum of all copy positions of all
elements with primary positions from levels $[m-\varepsilon m,m]$ that have
exactly one copy. Every such position is at most $m+x+o(m)$ for an element
with a primary position on level $m-x$, but there are $\geq\delta m$ elements
that have copy positions $\leq m+x-\gamma m$. It means that $S\leq
4\left(\sum_{i=0}^{\varepsilon m}m+i\right)-(\gamma m)\cdot(\delta
m)=(4\varepsilon+2\varepsilon^{2}+o(1)-\gamma\cdot\delta)m^{2}$. On the other
hand, we can find a lower bound on $S$. Only $o(m)$ elements have copy
positions smaller than $m$, so there are $4\varepsilon m-o(m)$ elements that
should have copies on levels starting from the $m$-th. If we order these copy
positions in the increasing order, the first four positions are $\geq m$, the
second four positions are $\geq m+1$, and so on: positions with indices
$4i+1$, $4i+2$, $4i+3$ and $4i+4$ are $\geq m+i$ (because otherwise, we would
need to pack at least $4i+1$ elements on $i$ levels of four sequences). It
means that their sum $S$ is at least $4\varepsilon
m^{2}+2\varepsilon^{2}m^{2}-o(m^{2})=(4\varepsilon+2\varepsilon^{2}-o(1))m^{2}$.
Which contradicts the upper bound we acquired.

So almost all of these elements with primary positions from levels
$[m-\varepsilon m,m]$ have exactly one copy, and if the primary position of
such an element is $m-x$, then its copy is located on level $m+x\pm o(m)$ for
almost all elements. It also means that for constants
$0\leq\varepsilon_{2}<\varepsilon_{1}\leq\varepsilon$ independent of $K$
almost all elements from $[m-\varepsilon_{1}m,m-\varepsilon_{2}m)$ are
primary, and almost all of them have exactly one copy each, and for almost all
of them, these copies are located on levels
$[m+\varepsilon_{2}m-o(m),m+\varepsilon_{1}m+o(m))$. But there are $o(m)$
positions on levels
$[m+\varepsilon_{2}m-o(m),m+\varepsilon_{1}m+o(m))\setminus[m+\varepsilon_{2}m,m+\varepsilon_{1}m)$,
so we can say that almost all of these elements have their copies on levels
$[m+\varepsilon_{2}m,m+\varepsilon_{1}m)$.

Now all the preparatory work is done, and we are ready to prove that such
constructions are not possible. We say that an element with primary position
$(i,m-x)$ “is uniquely copied” to sequence $j$ if it has exactly one copy and
it is located on level $m+x\pm o(m)$ in the sequence $j$. We fix some
sufficiently small constant $\gamma>0$ independent of $K$. We say that
elements from levels $[m-\varepsilon_{1}m,m-\varepsilon_{2}m)$
($0\leq\varepsilon_{2}<\varepsilon_{1}\leq\varepsilon$) from sequence $i$ “are
uniquely copied” to sequence $j$ if there exist $\geq\gamma m$ elements with
primary positions on these levels in sequence $i$ that have their one and only
copy in sequence $j$ on levels $[m+\varepsilon_{2}m,m+\varepsilon_{1}m)$.

Call $P_{[\ell,r)}$ the set of all pairs $(i,j)$ such that there are
$\geq\gamma m$ elements from levels $[\ell,r)$ from sequence $i$ that are
uniquely copied to levels $[2m-r,2m-\ell)$ in sequence $j$.

######  Lemma C.9.

There exists $\delta>0$ independent of $K$ such that there exist
$0<\varepsilon_{2}<\varepsilon_{1}\leq\varepsilon$ such that
$B\coloneqq\frac{\varepsilon_{1}m-\varepsilon_{2}m}{5}\geq\delta m$ and
$P_{[m-\varepsilon_{1}m,m-\varepsilon_{2}m)}=P_{[m-\varepsilon_{1}m+iB,m-\varepsilon_{1}m+(i+1)B)}$
for all $0\leq i\leq 4$.

######  Proof C.10.

We prove this statement by a construction. $\delta$ will be equal to
$\frac{\varepsilon}{5^{12}}$ (and we should take $\gamma$ much smaller than
$\delta$). We provide an iterative process with at most $12$ steps that will
lead us to desired values of $\varepsilon_{1}$ and $\varepsilon_{2}$.

We start with a segment $[m-\varepsilon m,m)$. On every iteration we divide
our current segment $[\ell,r)$ into five almost equal parts and consider
$P$-sets for these six segments. Define them as $P$, $P_{1}$, $P_{2}$,
$P_{3}$, $P_{4}$ and $P_{5}$. If all of them are equal to each other, the
lemma holds and we use the current segment $[\ell,r)$ as the answer. Otherwise
there exists $1\leq i\leq 5$ such that $P\neq P_{i}$. As all five subsegments
of $[\ell,r)$ lie strictly inside $[\ell,r)$, this implies that
$P_{i}\subsetneq P$ and thus $|P_{i}|\leq|P|-1$. We replace our current
segment $[\ell,r)$ with $[\ell+(i-1)(r-\ell)/5,\ell+i(r-\ell)/5)$ and continue
to the next stage. Note that $|P_{[m-\varepsilon m,m)}|\leq 4\cdot 3=12$ and
on every next iteration the size of the segment decreases by a factor of $5$
and the size of $P$-set decreases by at least one. Consequently, after at most
$12$ iterations, we will get a suitable segment of size at least
$\frac{\varepsilon}{5^{12}}$.

Due to Lemma C.9 we kow that there exists a segment $[A,A+5B)$ such that
$A\geq m-\varepsilon m$, $A+5B\leq m$, $B=\Theta(m)$, and this segment
satisfies the lemma statement. Now we answer a question: which pairs $(i,j)$
can be in the $P$-set of the segment $[A,A+5B)$?

######  Lemma C.11.

If $1\leq i,j,k,\ell\leq 4$ are four distinct integers, at least one of pairs
$(i,j)$, $(j,i)$ and $(k,\ell)$ is not present in the $P$-set of $[A,A+5B)$.

######  Proof C.12.

Assume for contradiction that all these pairs are present in the $P$-set of
$[A,A+5B)$. Then all these pairs are contained in $P$-sets of all $5$
subsegments due to Lemma C.9. In particular, it means that there is an element
with primary position $(i,A+x)$ where $0\leq x<B$ that has its only copy in
sequence $j$ on level $2m-A-x\pm o(m)$. Also, there exists an element with
primary position $(j,A+y)$ where $0\leq y<B$ that has its only copy in
sequence $i$ on level $2m-A-y\pm o(m)$, and an element with primary position
$(k,A+4B+z)$ where $0\leq z<B$ that has its only copy in sequence $\ell$ on
level $2m-A-4B-z\pm o(m)$. We claim that it is impossible to cover these three
elements with prefixes of total size at most $\alpha=2m+o(m)$. If we use three
different prefixes, the sum of their lengths is at least
$3\cdot(1-\varepsilon)m>\alpha$ because $A\geq m-\varepsilon m$. Element
$s_{k}[A+4B+z]$ does not lie in the same sequences as two other elements, so
it must be covered alone. It has $\ell_{\min}(s_{k}[A+4B+z])=A+4B+z$, so such
prefix must have size at least $A+4B+z$. The two other elements are both
located in sequences $i$ and $j$, so we should take a prefix in one of them.
Without loss of generality, say we take sequence $j$. The coverage will be of
size $(A+4B+z)+(2m-A-x\pm o(m))=2m+4B+z-x\pm o(m)\geq 2m+4B-x\pm o(m)\geq
2m+3B\pm o(m)=(2+\Theta(1))m>\alpha$. So we cannot have all three pairs
$(i,j)$, $(j,i)$ and $(k,\ell)$ in our $P$-set at the same time.

We prove the same statement about other three pairs.

######  Lemma C.13.

If $1\leq i,j,k,\ell\leq 4$ are four distinct integers, at least one of pairs
$(i,j)$, $(j,k)$ and $(k,\ell)$ is not present in the $P$-set of $[A,A+5B)$.

######  Proof C.14.

Assume for a contradiction that all these pairs are present in the $P$-set of
$[A,A+5B)$. Then all these pairs are contained in $P$-sets of all $5$
subsegments due to Lemma C.9. In particular, there is an element with primary
position $(i,A+2B+x)$ where $0\leq x<B$ that has its only copy in sequence $j$
on level $2m-A-2B-x\pm o(m)$. Also there exists an element with primary
position $(j,A+y)$ where $0\leq y<B$ that has its only copy in sequence $k$ on
level $2m-A-y\pm o(m)$ and an element with primary position $(k,A+4B+z)$ where
$0\leq z<B$ that has its only copy in sequence $l$ on level $2m-A-4B-z\pm
o(m)$. We claim that it is impossible to cover these three elements with
prefixes of total size at most $\alpha=2m+o(m)$. If we use three different
prefixes, the sum of their lengths is at least
$3\cdot(1-\varepsilon)m>2m+o(m)$ because $A\geq m-\varepsilon m$. Now imagine
that we use two sequences (obviously one sequence is impossible because there
is no one sequence where all three elements are located). It is easy to see
that we should take a prefix in sequence $k$ because otherwise, element
$s_{k}[A+4B+z]$ can be covered only using sequence $\ell$, and no other
elements from these three are located in that sequence and level on which
$s_{k}[A+4B+z]$ is located in that sequence is not smaller than in sequence
$k$ for this element (because in sequence $k$ it has its primary position), so
it would be not worse to take prefix in sequence $k$ instead. So we should
take sequence $k$ and either sequence $i$ or $j$. If we take sequence $i$, the
coverage will be of size $(A+2B+x)+(2m-A-y\pm o(m))=2m+2B+x-y\pm o(m)\geq
2m+2B-y\pm o(m)\geq 2m+B\pm o(m)=(2+\Theta(1))m>\alpha$ because $B=\Theta(m)$.
If we take sequence $j$, the coverage will be of size $(A+4B+z)+(2m-A-2B-x\pm
o(m))=2m+2B+z-x\pm o(m)\geq 2m+2B-x\pm o(m)\geq 2m+B\pm
o(m)=(2+\Theta(1))m>\alpha$. So we cannot have all three pairs $(i,j)$,
$(j,k)$ and $(k,\ell)$ in our $P$-set at the same time.

These two limitations are sufficient for us to prove that such construction
cannot exist. Consider a directed graph $G=(V,E)$ where $V=[4]$ and $E=P$. The
weight of an edge $i\to j$ is equal to the number of elements going from
sequence $i$ to sequence $j$ (notice that due to the definition of $P$-set all
weights are $\geq\gamma m$). In every sequence there are $5B\pm o(m)$ elements
that should be uniquely copied somewhere, and there are $5B$ places (on levels
$[2m-A-5B,2m-A)$) where elements from other sequences can be uniquely copied
to in this sequence. It means that for every vertex the sum of all outgoing
edges is $5B\pm o(m)$ and the sum of all ingoing edges is $5B\pm o(m)$.

Distinguish two cases whether there exist pairs $(i,j)$ and $(j,i)$ for some
$i\neq j$ in the $P$-set or not.

  1. 1.

First, consider the case where such two pairs do not exist. So if there exists
a pair $(i,j)$, the reversed pair $(j,i)$ cannot be present. Without loss of
generality, say that there exists an edge $1\to 2$. It means that there cannot
exist an edge $2\to 1$. Without loss of generality, say that there exists an
edge $2\to 3$. It means that there cannot exist edge $3\to 2$. Elements from
sequence $3$ cannot be uniquely copied to sequence $4$, because otherwise we
get a construction where we have pairs $(i,j)$, $(j,k)$ and $(k,\ell)$ where
$i=1$, $j=2$, $k=3$ and $\ell=4$ which would violate Lemma C.13. So the only
place where elements from sequence $3$ can be uniquely copied to is sequence
$1$. Now we have a triangle $1\to 2\to 3\to 1$. In the same, way we can see
that there cannot exist edges $1\to 4$ and $2\to 4$ because otherwise, we
would also violate Lemma C.13. So it means that there are no edges into vertex
$4$. It means that there can exist only $o(m)$ elements that are uniquely
copied there. But it should have at least $5B\pm o(m)=\Theta(m)$ ingoing
elements. It is a contradiction. See Figure 4 for more understanding.

$3$$1$$2$$4$ Figure 4: Solid edges are present, dashed edges cannot be
present. We get a contradiction because no ingoing edges to vertex $4$ are
allowed.

  2. 2.

Second, consider the case where there exist both pairs $(i,j)$ and $(j,i)$ for
some $i\neq j$. Define $k,\ell$ such that
$\\{k,\ell\\}=\\{1,2,3,4\\}\setminus\\{i,j\\}$. There cannot exist edges
$(k,\ell)$ or $(\ell,k)$ because it would violate Lemma C.11. So then it means
that almost all elements from sequences $k$ and $\ell$ are uniquely copied to
sequences $i$ and $j$. There are $10B\pm o(m)$ such elements, so they take
$10B\pm o(m)$ places. But there are $10B\pm o(m)$ places for copy in sequences
$i$ and $j$ in total. Then edges $(i,j)$ and $(j,i)$ should have weights
$o(m)$. But we cannot have edges with such small values because otherwise, we
would not even add such pairs to $P$. This is a contradiction. See Figure 5
for more understanding.

$i$$j$$k$$\ell$ Figure 5: Solid edges are present, snake edges may be present,
dashed edges cannot be present. We get a contradiction because too many
elements are uniquely copied to sequences $i$ and $j$.

It concludes the proof of the theorem. It means that for any $(4,K,\alpha)$
PCD, it is true that $\frac{K}{\alpha}\leq 2-\varepsilon^{\prime}$ for some
fixed $\varepsilon^{\prime}>0$ independent of $K$ and, for example, no
matching lower bound for $4$-dimensional Klee’s measure problem is possible
using this approach.