exp INDEX LENGTHGEQ A REACH

# The Geometry of Rounding ††thanks: Research supported in part by NSF grant
1934884, 2130536, 2130608

Jason Vander Woude  School of Computing and Department of Mathematics,
University of Nebraska-Lincoln  Peter Dixon Part of the work done while the
author was at Iowa State University Ben-Gurion University of the Negev  A.
Pavan  Department of Computer Science, Iowa State University  Jamie Radcliffe
Department of Mathematics, University of Nebraska-Lincoln  N. V. Vinodchandran
School of Computing, University of Nebraska-Lincoln

###### Abstract

Rounding has proven to be a fundamental tool in theoretical computer science.
By observing that rounding and partitioning of $\mathbb{R}^{d}$ are
equivalent, we introduce the following natural partition problem which we call
the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally
small) and $\epsilon>0$ (ideally large), is there a partition of
$\mathbb{R}^{d}$ with unit hypercubes such that for every point
$\vec{p}\in\mathbb{R}^{d}$, its closed $\epsilon$-neighborhood (in the
$\ell_{\infty}$ norm) intersects at most $k$ hypercubes?

We undertake a comprehensive study of this partition problem. We prove that
for every $d\in\mathbb{N}$, there is an explicit (and efficiently computable)
hypercube partition of $\mathbb{R}^{d}$ with $k=d+1$ and
$\epsilon=\frac{1}{2d}$. We complement this construction by proving that the
value of $k=d+1$ is the best possible (for any $\epsilon$) for a broad class
of “reasonable” partitions including hypercube partitions. We also investigate
the optimality of the parameter $\epsilon$ and prove that any partition in
this broad class that has $k=d+1$, must have
$\epsilon\leq\frac{1}{2\sqrt{d}}$. These bounds imply limitations of certain
deterministic rounding schemes existing in the literature. Furthermore, this
general bound is based on the currently known lower bounds for the dissection
number of the cube, and improvements to this bound will yield improvements to
our bounds.

While our work is motivated by the desire to understand rounding algorithms,
one of our main conceptual contributions is the introduction of the secluded
hypercube partition problem, which fits well with a long history of
investigations by mathematicians on various hypercube partitions/tilings of
Euclidean space.

Keywords. Rounding, Partition, Tiling, Packing, Tesselation, Cube, Hypercube,
Reclusive, Sperner, Dissection, Triangulation

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
  2. 2 Main Results and Proof Outlines
    1. 2.1 Lower Bound on Degree ($k$)
    2. 2.2 Upper Bound on Tolerance ($\epsilon$)
  3. 3 Related Work in Mathematics
  4. 4 Organization
  5. 5 Notation
  6. 6 Definitions and Basic Partition Results
  7. 7 Reclusive Partitions
    1. 7.1 An Example Reclusive Partition
    2. 7.2 Motivating Properties
    3. 7.3 Construction
  8. 8 Fundamental Property of the Reclusive Definition
  9. 9 Optimality of the Degree Parameter ($k$)
    1. 9.1 The Optimality Theorems
    2. 9.2 Tools for Proving the Optimality Theorems
    3. 9.3 Proofs of the Optimality Theorems
    4. 9.4 Optimality Theorem Gaps
  10. 10 Upper Bounds on the Tolerance Parameter ($\epsilon$)
  11. 11 Application of Reclusive Partitions to Deterministic Rounding
  12. 12 Conclusions and Future Work
  13. A Rounding Schemes in Prior Work
    1. A.1 A Very Simple Rounding Scheme
    2. A.2 The Randomized Rounding Scheme of Saks and Zhou
    3. A.3 The Randomized Rounding Scheme of Goldreich
    4. A.4 The Deterministic Rounding Scheme of Hoza and Klivans
  14. B Measure Theory
  15. C Binary Relations

##  1 Introduction

Rounding has proven to be a fundamental tool in theoretical computer science.
Generically, if $\mathcal{X}\subseteq\mathcal{Y}$ are metric spaces with the
same metric, then a rounding algorithm $\mathcal{R}$ maps points in
$\mathcal{X}$ to points in $\mathcal{Y}$ (typically so that $x$ is close to
$\mathcal{R}(x)$). Intuitively, the purpose of rounding is to limit the number
of possible outcomes of the algorithm, which in turn can help reduce the
complexity (e.g. space complexity, time complexity, or the number of random
bits needed). Often $\mathcal{X}=\mathbb{R}^{d}$ with the metric induced by
the $l^{\infty}$ norm (we call this metric $d_{max}$).

In complexity theory, one of the earliest applications of rounding is in the
seminal work of Saks and Zhou [1] in the context of space-bounded
derandomization. They devised a randomized algorithm $\mathcal{R}$ rounding
from $[0,1]^{d}$ to $[0,1]^{d}$ with the following property: for every
$\vec{x}\in[0,1]^{d}$,

$\Pr_{r\in\Sigma^{\ell}}\big{[}\forall\vec{y}\in
B_{\epsilon}(\vec{x}):\mathcal{R}(r,\vec{x})=\mathcal{R}(r,\vec{y})\big{]}\geq
1-1/\poly(d)$

and for any $r\in\Sigma^{\ell}$,
$d_{max}\left(\vec{x},\mathcal{R}(r,\vec{x})\right)<\epsilon$.

Here, $B_{\epsilon}(\vec{x})$ is the open $\epsilon$-ball around $\vec{x}$
with respect to the $l^{\infty}$ norm and
$\Sigma^{\ell}=\left\\{0,1\right\\}^{\ell}$ is the sample space of random
bits. The property above expresses that for any $\epsilon$-ball, with high
probability over the choice of randomness, all points in the ball round to the
same value. The Saks and Zhou rounding scheme is a randomized rounding scheme
with $\epsilon=1/\poly(d)$ using $\ell=O(\log d)$ bits of randomness. This
randomized rounding is a critical step in the well known derandomization of
probabilistic space-bounded algorithms, namely
$\BPSPACE(S)\subseteq\DSPACE(S^{3/2})$.

A more recent example in which randomized rounding is employed is in the
context of pseudodeterminism and multi-pseudodeterminism [2, 3, 4]. A
pseudodetermistic algorithm is a randomized algorithm that on any particular
input, returns a canonical solution with probability at least $2/3$ (which can
be boosted to $1-\delta$). A $k$-pseudodeterministic algorithm, a
generalization of a pseudodeterministic algorithm, is a probabilistic
algorithm such that for each input $x$, there is a set $S_{x}$ of cardinality
at most $k$, and on input $x$, the algorithm returns a value in $S_{x}$ with
probability at least $\frac{k+1}{k+2}$ (which again can be boosted to
$1-\delta$). In the context of designing multi-pseudodeterministic algorithms,
Goldreich [3] designed a randomized algorithm $\mathcal{R}$ with the following
property: for every $\vec{x}\in\mathbb{R}^{d}$, there exists $S_{\vec{x}}$ of
cardinality at most $k=d+1$ such that

$\Pr_{r\in\Sigma^{\ell}}\left[\forall\vec{y}\in
B_{\epsilon}(\vec{x}):\mathcal{R}(r,\vec{y})\in
S_{\vec{x}}\right]\geq\frac{k+1}{k+2}$

and for any $r\in\Sigma^{\ell}$,
$d_{max}\left(\vec{x},\mathcal{R}(r,\vec{x})\right)<\epsilon$.

Goldreich’s rounding has a different requirement than Saks and Zhou’s: for any
$\epsilon$-ball, Goldreich does not require that with high probability all
points in the ball round to the same value, but he does require that there is
a small set such that with high probability all points in the ball round to
points in that set. Also, in Saks and Zhou’s scheme, the single value that the
ball is rounded to can depend on random bits $r$, but Goldreich’s scheme
requires the set $S_{\vec{x}}$ to be independent of the randomness. Using this
rounding scheme, Goldreich showed the existence of $(d+1)$-pseudodeterministic
approximation algorithms for a class of functions whose range is
$\mathbb{R}^{d}$. Grossman and Liu used a similar rounding scheme to design
low influential-bit algorithms, a notion that generalizes pseudodeterministic
algorithms [4]. Similar rounding schemes have found applications in a very
recent work of Impagliazzo, Lei, Pitassi, and Sorrell [5] in the context of
making statistical learning algorithms reproducible.

In [6], Hoza and Klivans designed a certain deterministic rounding scheme.
Their work is motivated by the problem of reducing randomness for adaptive
algorithms. Consider the problem of simulating $m$ adaptive (adversarially
chosen) invocations of a randomized estimation algorithm that returns a vector
in $\mathbb{R}^{d}$. If the algorithm requires $n$ bits of randomness, then
the trivial way of simulating $m$ invocations requires $nm$ random bits. To
reduce the randomness, they designed a deterministic rounding algorithm
$\mathcal{R}$ that has the same properties as that of Goldreich. In other
words, for every $\vec{x}\in\mathbb{R}^{d}$, the size of the set
$\left\\{\mathcal{R}(\vec{y}):\vec{y}\in B_{\epsilon}(\vec{x})\right\\}$ has
cardinality at most $d+1$. Combining this rounding algorithm with the INW
pseudorandom generator [7], Hoza and Klivans reduced the amount of randomness
required for the above adaptive invocation problem to $n+O(m\log(d+1))$. We
give more elaborate details on all these rounding schemes and how they fit
into our work in sec:rounding-schemes-in-prior-work.

The present work investigates the geometry of rounding. We equate the notion
of deterministic rounding schemes to partitions of Euclidean space
$\mathbb{R}^{d}$. This connection led us to the introduction of a very natural
partition problem that we call the secluded hypercube partition problem. Using
this geometric approach, we establish upper and lower bounds on the parameters
of certain deterministic rounding schemes. Perhaps more importantly, the
partition problem we investigate is very natural and should be of independent
interest to a broader community. The introduction of the secluded hypercube
partition problem is one of our main conceptual contributions.

######  Definition 1.1 ($(k(d),\epsilon(d))$-Deterministic Rounding).

A deterministic rounding scheme is a family of functions
${\mathcal{F}}=\\{f_{d}\\}_{d\in\mathbb{N}}$ where
$f_{d}:\mathbb{R}^{d}\to\mathbb{R}^{d}$. We call $\mathcal{F}$ a
$(k(d),\varepsilon(d))$-deterministic rounding scheme if (1)
$\forall\vec{x}\in\mathbb{R}^{d}$, $d_{max}(\vec{x},f_{d}(\vec{x}))\leq 1$111
The bound of 1 is not critical. We can use any constant and scale the
parameters appropriately.  (2) $\forall\vec{x}\in\mathbb{R}^{d}$,
$\lvert\\{f_{d}(\vec{z})\colon\vec{z}\in
B_{\varepsilon(d)}(\vec{x})\\}\rvert\leq k(d)$.

######  Definition 1.2 ($(k,\epsilon)$-Secluded Partition).

A partition $\mathcal{P}$ of $\mathbb{R}^{d}$ is called a
$(k,\epsilon)$-secluded partition if for every $\vec{p}\in\mathbb{R}^{d}$,
$\lvert\left\\{X\in\mathcal{P}\colon
X\cap\overline{B}_{\epsilon}(\vec{p})\not=\emptyset\right\\}\rvert\leq k$.

######  Remark 1.3.

The use of the word “secluded” is meant as a synonym for “remote” or
“isolated” and is meant to indicate that every point in space is only nearby
(within $\epsilon$) a few (at most $k$) members of the partition.

We refer to $k$ as the degree of the partition and $\epsilon$ as its
tolerance. The values of $k$ and $\epsilon$ will often be functions of the
dimension $d$.

There is a natural equivalence between rounding schemes and partitions of
Euclidean space in a very general sense. A rounding function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ induces a partition
$\mathcal{P}_{f}$ as follows:
$\mathcal{P}_{f}=\left\\{f^{-1}(y):y\in\operatorname{range}(f)\right\\}$.
Conversely, a partition $\mathcal{P}$ induces a deterministic rounding
function $f_{\mathcal{P}}$ as follows: for each member $X\in\mathcal{P}$ let
$\vec{p}_{X}\in X$ some fixed representative. Then the rounding function
$f_{\mathcal{P}}$ maps any point $\vec{p}\in X$ to $\vec{p}_{X}$. This
connection leads to the following observation.

######  Observation 1.4 (Equivalence of Rounding Schemes and Partitions).

A $(k(d),\epsilon(d))$-deterministic rounding scheme induces, for each
$d\in\mathbb{N}$, a $(k(d),\epsilon(d))$-secluded partition of
$\mathbb{R}^{d}$ in which each member has diameter222The diameter is at most
$2$, not at most $1$. For example, the rounding scheme which rounds a point by
sending each coordinate to the nearest even integer (breaking ties by rounding
up) is a $(2^{d},1)$-deterministic rounding scheme, and the partition it
induces in each dimension consists of hypercubes of side length $2$. at most
$2$. Conversely, a sequence $\langle\mathcal{P}_{d}\rangle_{d=1}^{\infty}$ of
partitions where $\mathcal{P}_{d}$ is $(k(d),\epsilon(d))$-secluded and
contains only members of diameter at most $1$ induces many333For each member,
any representative of that member can be chosen.
$(k(d),\epsilon(d))$-deterministic rounding schemes.

The connection between rounding schemes and partitions of Euclidean space has
been observed in earlier works. In particular, the works of Fiege et. al.,
Kindler et. al., and Braverman and Minzer investigated the foams problem in
the context of parallel repetition [8, 9, 10, 11]. The foams problem asks to
find a body that tiles $\mathbb{R}^{d}$ with $\mathbb{Z}^{d}$ with the
smallest surface area. These works established connections between the foams
problem and the parallel repetition theorem and gave a new foams construction.
This new construction led to an optimal noise-resistant randomized rounding
scheme (more precisely a distribution $\mathcal{D}$ over deterministic
rounding schemes) with the following property for all $d\in\mathbb{N}$:
$\forall\vec{x},\vec{y}\in\mathbb{R}^{d}$ such that
$d_{max}(\vec{x},\vec{y})\leq\epsilon$, it holds that
$\Pr_{f\sim\mathcal{D}}\left[f(\vec{x})=f(\vec{y})\right]\geq
1-O(\varepsilon)$. In [9, Definition 1.2], a randomized rounding scheme is
defined as a distribution of functions for each dimension rather than a single
function in each dimension. Not all rounding algorithms necessarily abide by
this definition of a randomized rounding scheme, but all of those discussed in
this paper do including [1, 3, 9, 10, 6, 5]. Thus, while our results will be
about deterministic rounding schemes, there is a connection between
deterministic and randomized rounding schemes in this sense.

###  1.1 Our Contributions

In this work we conduct an extensive investigation of secluded partitions.
Contributions of this work are two-fold. The first contribution is the
formulation of a very natural partition problem known as the secluded
hypercube partition problem and an explicit construction of such partition
with degree $d+1$ and tolerance $1/2d$. The second contribution is
establishing impossibility results on the degree and the tolerance parameters.
In particular, we establish that any “reasonable” secluded partition must have
degree at least $d+1$ and every reasonable partition with degree $d+1$ must
have tolerance at most $1/2\sqrt{d}$.

We start our investigation by considering unit hypercube partitions of
$\mathbb{R}^{d}$, which are very natural and extensively studied partitions of
Euclidean space. A partition $\mathcal{P}$ of $\mathbb{R}^{d}$ is a unit
hypercube partition if every $X\in\mathcal{P}$ is a $d$-dimensional unit
hypercube. Note that the diameter of a unit hypercube is $1$ in the $d_{max}$
metric.

######  Question (Secluded Hypercube Partition Problem).

Let $d\in\mathbb{N}$. For what values of $k\in\mathbb{N}$ and
$\epsilon\in(0,\infty)$ does there exist a $(k,\epsilon)$-secluded unit
hypercube partition $\mathcal{P}$ of $\mathbb{R}^{d}$?

One of our main conceptual contributions is the formulation of the above
question which is a very natural geometric question and should be of broad
interest. The question asks: given $d\in\mathbb{N}$, $\epsilon\in(0,\infty)$,
and $k\in\mathbb{N}$, is there a partition of $\mathbb{R}^{d}$ with unit
hypercubes so that for any point $\vec{p}\in\mathbb{R}^{d}$, its
$\epsilon$-neighborhood, in the $d_{max}$ metric, intersects with at most $k$
hypercubes? It is easy to see that the natural grid partition of
$\mathbb{R}^{d}$ with unit hypercubes is a $(2^{d},1/2)$-secluded partition.
Our first technical contribution is the design of a parameterized class of
explicit $(d+1,\frac{1}{2d})$-secluded unit hypercube partitions for each
$d\in\mathbb{N}$. (See :hypercube-partition-thm for a more elaborate statement
of the following result and its proof.)

######  Theorem (Hypercube Partition Theorem).

For all $d\in\mathbb{N}$, there exists $(d+1,\frac{1}{2d})$-secluded unit
hypercube partitions of $\mathbb{R}^{d}$.

Our next result shows that the above construction is optimal with respect to
the degree parameter. In particular, we show that for any unit hypercube
partition of $\mathbb{R}^{d}$ and any $\epsilon\in(0,\infty)$, the degree has
to be at least $d+1$. (See :unit-hypercube-optimality for a slightly stronger
version of the following result and its proof.)

######  Theorem (Degree Optimality for Unit Hypercube Partitions).

For every $(k,\epsilon)$-secluded unit hypercube partition $\mathcal{P}$ of
$\mathbb{R}^{d}$, it must be that $k\geq d+1$.

This theorem raises the question of whether there exist non-hypercube
partitions with degree smaller than $d+1$. There are trivial examples of such
partitions since any partition with fewer than $d+1$ members trivially has
degree smaller than $d+1$ no matter what value of tolerance is used. Another
trivial example is concentric “shells” in the $d_{max}$ metric:
$\mathcal{P}=\left\\{\overline{B}_{1},\;\overline{B}_{2}\setminus\overline{B}_{1},\;\overline{B}_{3}\setminus\overline{B}_{2},\;\overline{B}_{4}\setminus\overline{B}_{3},\;\ldots\right\\}$
(where $\overline{B}_{i}$ denotes the ball of radius $i$ centered at
$\vec{0}$). For tolerance $\epsilon\leq\frac{1}{2}$, this is a
$(2,\epsilon)$-secluded partition.

In the first of these examples, since there are a finite number of members,
some member has infinite diameter and infinite measure. In the second example,
though every member has finite measure and finite diameter, there is no bound
on either of these quantities (i.e. for any $D$ and any $\mu$, the partition
contains a member with diameter greater than $D$ and measure greater than
$\mu$). If we consider partitions with either a bound on the diameter of the
members or a bound on the measure of the members, then we can rule out the
possibility of degree less than $d+1$. We say a partition has bounded diameter
(resp. bounded measure) if there exists some bound $b\in(0,\infty)$ such that
every member of the partition has diameter (resp. measure) at most $b$. Such
$b$ will be called a diameter bound (resp. measure bound) for the partition.
Our next contribution is a degree optimality theorem for bounded measure
partitions. (See :first-optimality-thm for an equivalent statement of the
following result and a proof.)

######  Theorem (Degree Optimality for Bounded Measure Partitions).

For every $(k,\epsilon)$-secluded partition $\mathcal{P}$ of $\mathbb{R}^{d}$
with bounded measure, it must be that $k\geq d+1$.

Since a partition with bounded diameter must also be a partition of bounded
measure444Suppose $\mathcal{P}$ is a partition of $\mathbb{R}^{d}$ of bounded
diameter. Then there is some $D$ such every member $X\in\mathcal{P}$ has
$\operatorname{diam}(X)\leq D$. Let $\mu=(2D)^{d}$. For any $X\in\mathcal{P}$,
fix some $\vec{x}\in X$ so $\overline{B}_{D}(\vec{x})\supset X$ and note that
$\overline{B}_{D}(\vec{x})$ (in the $d_{max}$ metric) has measure
$(2D)^{d}=\mu$ which shows that each member of $\mathcal{P}$ has measure at
most $\mu$, so $\mathcal{P}$ has bounded measure., we get the following
corollary. (See :second-optimality-thm for a stronger version of this result
and its proof.)

######  Corollary (Degree Optimality for Bounded Diameter Partitions).

For every $(k,\epsilon)$-secluded partition $\mathcal{P}$ of $\mathbb{R}^{d}$
with bounded diameter, it must be that $k\geq d+1$.

Now we turn from the degree parameter to the tolerance parameter. The
(Hypercube Partition Theorem). above states that there is a
$(k,\epsilon)$-secluded partition with degree $k=d+1$ (the minimum possible
for bounded partitions) and tolerance $\epsilon=\frac{1}{2d}$. Is it possible
to design $(k,\epsilon)$-secluded partitions maintaining optimal $k=d+1$, but
with larger $\epsilon$? We could just scale up the sizes of the hypercubes in
the  (Hypercube Partition Theorem). to obtain any $\epsilon$ we want, so this
question only makes sense if we compare $\epsilon$ to the size of the largest
member of the partition. (See :sperner-upper-bound for a more detailed version
of the following result and its proof.)

######  Theorem (Tolerance Upper Bound).

For every $(d+1,\epsilon)$-secluded partition $\mathcal{P}$ of
$\mathbb{R}^{d}$ with diameter bound $D$, it must be that
$\epsilon\leq\frac{D}{2\sqrt{d}}$.

Our goal was to show an upper bound of $1/\Omega(d)$ on the tolerance
parameter as that would establish that our construction is optimal in both
degree and tolerance. However, we could only establish this for $d=1$ and
$d=2$. Closing the gap between our upper and lower bounds on the tolerance
parameter is the main open question that emerged from our investigation.

The above results and :rounding-schemes-and-partitions establish a limitation
of deterministic rounding schemes as follows.

######  Corollary 1.5 (Limitations of Deterministic Rounding Schemes).

For any $(k(d),\epsilon(d))$-deterministic rounding scheme, $k(d)$ must be at
least $d+1$, and for $(d+1,\epsilon(d))$-deterministic rounding schemes,
$\epsilon(d)$ must be at most555:rounding-schemes-and-partitions gives a
diameter bound of $D=2$, so $\frac{D}{2\sqrt{d}}=\frac{1}{\sqrt{d}}$
$\frac{1}{\sqrt{d}}$.

Finally, we show an application of the hypercube partition theorem in the
context of sample complexity of pseudodeterministic algorithms. Let
$f_{1},\ldots,f_{d}$ be functions from $\\{0,1\\}^{n}$ to $[0,1]$. Given
blackbox access to the functions, the goal is to output a vector
$\vec{\alpha}=\langle\alpha_{1},\ldots,\alpha_{d}\rangle$ that is an
$(\epsilon,\delta)$-approximation to the vector
$\langle\mathbb{E}(f_{i})\rangle_{i=1}^{d}$ with respect to $d_{max}$ metric.
This means that with probability at least $1-\delta$, the vector
$\vec{\alpha}\in\mathbb{R}^{d}$ returned by the algorithm is such that
$d_{max}(\vec{\alpha},\langle\mathbb{E}(f_{i})\rangle_{i=1}^{d})\leq\epsilon$
which is equivalent to saying that with probability at least $1-\delta$, it
holds for all $i$ that $\lvert\alpha_{i}-\mathbb{E}(f_{i})\rvert\leq\epsilon$.
Goldreich proved that there is $(d+1)$-pseudodeterministic algorithm for this
task, and this algorithm has a sample complexity of $\widetilde{O}(d^{4})$
[3]. Using our hypercube partitions, we show that the sample complexity can be
improved to $\widetilde{O}(d^{2})$ samples.

[Application to Pseudodeterministic
Algorithms]propositionRestatableApplicationToPseudodeterministicAlgorithms Let
$f_{1},\ldots,f_{d}:\\{0,1\\}^{n}\to[0,1]$ be functions and
$\epsilon\in(0,\infty)$ and $\delta\in(0,\frac{1}{2})$. There is an algorithm
that given sample access to each $f_{i}$ can $(d+1)$-pseudodeterministically
$(\epsilon,\delta)$-approximate $\langle\mathbb{E}(f_{i})\rangle_{i=1}^{d}$
relative to the $d_{max}$ metric using
$O\left(\frac{(d+1)^{2}}{\epsilon^{2}}\cdot\log\left(\frac{d}{\delta}\right)\right)$
samples.

##  2 Main Results and Proof Outlines

In this section, we give formal statements and proof outlines for all our
results. We start with some required notation. A complete set of notations
that we use in this paper is given in sec:notation.

For a point $\vec{p}\in\mathbb{R}^{d}$ and $\varepsilon\in(0,\infty)$,
$\overline{B}_{\epsilon}(\vec{p})$ denotes the closed ball of radius
$\epsilon$ around $\vec{p}$, with respect to the $d_{max}$ metric (we will use
this metric throughout this paper). In other words,
$\overline{B}_{\epsilon}(\vec{p})\operatorname{\overset{def}{=}}\left\\{\vec{x}\in\mathbb{R}^{d}:\lVert\vec{x}-{\vec{p}}\rVert_{\infty}\leq\epsilon\right\\}=\left\\{\vec{x}\in\mathbb{R}^{d}:\forall
i\;\lvert x_{i}-y_{i}\rvert\leq\epsilon\right\\}.$

When it is understood that we are considering a particular partition
$\mathcal{P}$, then for any point $\vec{p}\in\mathbb{R}^{d}$, and any
$\epsilon\in(0,\infty)$, we let $\mathcal{N}_{\epsilon}(\vec{p})$ denote the
members of $\mathcal{P}$ intersecting the closed $\epsilon$-neighborhood of
$\vec{p}$:

$\mathcal{N}_{\epsilon}(\vec{p})\operatorname{\overset{def}{=}}\left\\{X\in\mathcal{P}:X\cap\overline{B}_{\epsilon}(\vec{p})\not=\emptyset\right\\}.$

In addition, we let $\mathcal{N}_{\overline{0}}(\vec{p})$ denote the members
of $\mathcal{P}$ whose closure contains $\vec{p}$.

$\mathcal{N}_{\overline{0}}(\vec{p})\operatorname{\overset{def}{=}}\left\\{X\in\mathcal{P}:\overline{X}\ni\vec{p}\right\\}.$

These two sets will be ubiquitous throughout the paper. We will restate the
(Secluded Hypercube Partition Problem). using this notation as follows:

######  Question 2.1 (Secluded Hypercube Partition Problem).

Let $d\in\mathbb{N}$. Given $k\in\mathbb{N}$ (degree) and
$\epsilon\in(0,\infty)$ (tolerance) does there exists a partition
$\mathcal{P}$ of $\mathbb{R}^{d}$ consisting of unit hypercubes such that for
every point $\vec{p}\in\mathbb{R}^{d}$,
$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\leq k$ ?

This work is a comprehensive study of ques:motivating. It is easy to verify
that for $k=2^{d}$ and any $\epsilon\leq\frac{1}{2}$ such a partition exists.
In particular, the standard grid partition demonstrated in fig:simple-
partition has the desired property.

Can we do better? For $d=2$ by shifting layers of the standard grid partition,
as demonstrated in fig:reclusive-partition, we can reduce the degree to $3$
and have tolerance of $\frac{1}{4}$. While it is not obvious, for $d=3$, this
shifting method yields a partition with degree $4$ and tolerance $\frac{1}{6}$
(again, see fig:reclusive-partition .

Figure 1: Simple unit hypercube partitions of $\mathbb{R}^{d}$ for $d=1,2,3$.
The shaded red regions are $\epsilon=\frac{1}{2}$ radius balls (in the
$d_{max}$ metric/$\lVert\cdot\rVert_{\infty}$ norm) showing that these
neighborhoods don’t intersect more than $k=2^{d}$ members of the partition (it
might look from the picture that centering the ball in one of the hypercubes
would intersect more, but it does not because the hypercubes are half open).
Furthermore, there are hypercubes that do intersect $2^{d}$ members as shown.
(This figure was produced using Manim [12].) Figure 2: This is a particular
reclusive partition of $\mathbb{R}^{d}$ for $d=1,2,3$. The shaded red regions
are $\epsilon=\frac{1}{2d}$ radius balls (in the $d_{max}$
metric/$\lVert\cdot\rVert_{\infty}$ norm) showing that these neighborhoods
don’t intersect more than $k=d+1$ members of the partition. Observe that in
the $d=2$ case, the $x$-direction shift (horizontal) is $\frac{1}{2}$ unit; in
the $d=3$ case, there are shifts of $\frac{2}{3}$ as well as $\frac{1}{3}$ in
various directions. (This figure was produced using Manim [12].)

Our first result shows that this intuition generalizes to all dimensions. We
construct hypercube partitions with degree $d+1$ and tolerance $\frac{1}{2d}$.
We note that, while the intuition about the degree bound generalizes from
lower dimensions, we do not believe it was obvious that
$\epsilon=\frac{1}{2d}$ was achievable. We show at the end of sec:reclusive-
lattice-partitions that a slight change to our partitions, while seemingly
innocuous, results in significantly worse degree.

[Hypercube Partition Theorem]theoremRestatableHypercubePartitionThm Let
$d\in\mathbb{N}$. Then there exists a $(d+1,\frac{1}{2d})$-secluded unit
hypercube partition $\mathcal{P}$ of $\mathbb{R}^{d}$. I.e., for any point
$\vec{p}\in\mathbb{R}^{d}$, we have

$\lvert\mathcal{N}_{\frac{1}{2d}}(\vec{p})\rvert\leq d+1.$

###### Proof Outline.

The proof of this theorem is constructive. We specify a particular basis for
the vector space $\mathbb{R}^{d}$ and consider all linear combinations of
these vectors in which all coefficients are integers (sometimes called integer
linear combinations). These integer linear combinations are such that a unit
hypercube can be placed at each position and it will form a partition of
$\mathbb{R}^{d}$. We view the basis as the columns of a matrix in an
appropriate order. We define a class of matrices which we call reclusive
matrices—these are upper triangular matrices with $1$’s on the diagonal, and
in each row the values that appear after the diagonal entry (inclusive) are
decreasing. Given such a reclusive matrix $A$, we associate a lattice group
$L_{A}$ which is the set of vectors of the form $A\vec{v}$ where
$\vec{v}\in\mathbb{Z}^{d}$. Now the members of the partition are the hypercube
shifted by elements of the lattice group $L_{A}$. We prove that every
reclusive matrix induces a $(d+1,\epsilon)$-secluded unit hypercube partition
where the value of $\epsilon$ depends on a property of the matrix called the
reclusive distance $\Delta$.

For two hypercubes $X,Y$ in this partition, we consider the vectors $\vec{n}$
and $\vec{m}$ (viewed as integer sequences) which define the positions of $X$
and $Y$ relative to the chosen basis. We show that $X$ and $Y$ are adjacent if
and only if the vector/sequence $\vec{n}-\vec{m}$ is an alternating sequence
of $-1$’s and $1$’s padded by $0$’s (what we call weak-alt-1 sequences). We
use this characterization to prove that for $\Delta$, two members of the
partition are either adjacent or their positions are at least $\Delta$ far
apart. This means that for any ball of radius $\frac{\Delta}{2}$, all
partition members that it intersects must be pairwise adjacent. I.e., they
constitute a clique in the graph theory sense when the partition is viewed as
an infinite graph with members being vertices and edges representing
adjacency666Members are adjacent if their closures intersect. of members.
Because of this, it suffices to show that there are no cliques of size greater
than $d+1$ in this partition graph. We do this by giving an explicit graph
coloring of the partition using $d+1$ colors. This will show that the
partition defined is a $(d+1,\Delta/2)$-secluded partition. Finally, it is
easy to construct (we give examples) reclusive matrices with $\Delta=1/d$.

∎

Recall from the introduction that a deterministic rounding scheme yields a
partition of $\mathbb{R}^{d}$. Thus using the rounding scheme of Hoza and
Klivans [6], we can obtain a $(d+1,\frac{1}{6(d+1)})$-secluded partition of
$\mathbb{R}^{d}$ whose diameter is bounded above by 1. However, the members of
this partition are not unit hypercubes (See fig:preserving_randomness_hoza-
klivans_partition in sec:hoza-klivans for $d=2$). For the sake of
completeness, we provide a proof of the theorem in sec:hoza-klivans.

######  Theorem 2.2 (Hoza-Klivans Partition).

Let $d\in\mathbb{N}$. Then there exists a $(d+1,\frac{1}{6(d+1)})$-secluded
partition $\mathcal{P}$ of $\mathbb{R}^{d}$ with diameter at most $1$.

###  2.1 Lower Bound on Degree ($k$)

Our next set of results investigate the optimality of the degree parameter
($k$) of partitions. We first prove that the value of $d+1$ in :hypercube-
partition-thm is indeed optimal for hypercube partitions.

[Optimality for Unit Hypercube
Partitions]theoremRestatableOptimalityForUnitHypercubePartitionsThm Let
$d\in\mathbb{N}$ and $\mathcal{P}$ a unit hypercube partition of
$\mathbb{R}^{d}$. Then there exists $\vec{p}\in\mathbb{R}^{d}$ such that

$\lvert\mathcal{N}_{\overline{0}}(\vec{p})\rvert\geq d+1$

Furthermore, $\mathcal{P}$ contains a $(d+1)$-clique.

The above theorem states that there is a particular $\vec{p}\in\mathbb{R}^{d}$
so that for every choice of $\epsilon$, $B_{\epsilon}(\vec{p})$ intersects at
least $d+1$ members of the partition, and thus the value $d+1$ from
:hypercube-partition-thm cannot be made any smaller. A $(d+1)$-clique in
$\mathcal{P}$ means that there is a set of $d+1$ members of $\mathcal{P}$ that
have pairwise intersecting closures (see :defn-adj), and its existence follows
trivially from the first claim of the theorem. This result is stronger than
just claiming that such a partition $\mathcal{P}$ must have degree parameter
at least $d+1$ (see the upcoming discussion of the three Optimality Theorems
(or subsec:optimality-theorems and subsec:gaps) for details.)

As discussed in the prior section, in generalizing from hypercubes to more
general partitions, we have to impose some condition to avoid trivialities,
and we previously mentioned partitions with bounded measure or bounded
diameter. We also consider one other condition which imposes a type of local
finiteness. Thus, we prove three different degree optimality theorems. Each
has a slightly different requirement on the types of partitions under
consideration (each bounding the size of the partition members in some way)
and each has a slightly different sense in which the partitions are considered
optimal.

In the statements below, $m$ denotes the Lebesgue measure (intuitively the
volume of a set). We present all three theorems before discussing the proof
outlines. The First Optimality Theorem states that for partitions of
$\mathbb{R}^{d}$ in which all members are bounded in measure, then there is no
secluded partition with degree less than $d+1$, because no matter the value of
$\epsilon$, some point $\vec{p}$ can be found such that
$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\geq d+1$.

[First Optimality Theorem]theoremRestatableFirstOptimalityThm If
$d\in\mathbb{N}$, and $\mathcal{P}$ is a partition of $\mathbb{R}^{d}$, and
there exists $M\in(0,\infty)$ such that for all $X\in\mathcal{P}$, $X$ is
Lebesgue measurable, and $m(X)<M$, then for any $\epsilon\in(0,\infty)$, there
exists $\vec{p}\in\mathbb{R}^{d}$ such that

$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\geq d+1.$

The Second Optimality Theorem states that under the stronger hypothesis that
the members of the partition are bounded in diameter, then not only there is
no secluded partition with degree less than $d+1$, but it is even false if we
allow $\epsilon$ to be different for each point in the space. The $\epsilon$
function in the statement below should be viewed as some fixed $\epsilon$ for
each point of $\mathbb{R}^{d}$.

[Second Optimality Theorem]theoremRestatableSecondOptimalityThm If
$d\in\mathbb{N}$, and $\mathcal{P}$ is a partition of $\mathbb{R}^{d}$, and
there exists $D\in(0,\infty)$ such that for all $X\in\mathcal{P}$, it holds
that $\operatorname{diam}(X)<D$, then for any
$\epsilon:\mathbb{R}^{d}\to(0,\infty)$, there exists
$\vec{p}\in\mathbb{R}^{d}$ such that

$\lvert\mathcal{N}_{\epsilon(\vec{p})}(\vec{p})\rvert\geq d+1.$

The conclusion of the Second Optimality Theorem is stronger than the
conclusion of the First Optimality Theorem, but the hypothesis is also
stronger (assuming all members are measurable); could it be, though, that the
hypothesis of the First Optimality Theorem implies the conclusions of the
Second Optimality Theorem and we just didn’t find a proof of this? We show in
sec:clique-optimality that this is not the case. There really is a “gap”
between these two theorems.

The Third Optimality Theorem uses a still stronger hypothesis and requires
finiteness somewhere in the space. With this strengthened hypothesis, the
conclusion can again be strengthened to say that we don’t even really care
about the $\epsilon$ neighborhoods at all because there is some point at the
closure of $d+1$ members. The theorem hypothesis uses the notion of a strict
pairwise bound $D$ (:strict-pairwise-bound) which just means that for each
member $X\in\mathcal{P}$, all points in $X$ are distance strictly less than
$D$ apart777This is stronger than saying that the diameter of each member is
$\leq D$, but weaker than saying that the diameter of each member is $<D$.
Members can have diameter $D$, but can’t have points that attain that
diameter. (with respect to $d_{max}$).

[Third Optimality Theorem]theoremRestatableThirdOptimalityThm If
$d\in\mathbb{N}$, and $\mathcal{P}$ is a partition of $\mathbb{R}^{d}$, and
there exists $D\in(0,\infty)$ such that for all $X\in\mathcal{P}$, $D$ is a
strict pairwise bound for $X$ (it is sufficient but not necessary that
$\operatorname{diam}(X)<D$), and if there exists some
$\vec{\alpha}\in\mathbb{R}^{d}$ such that $\vec{\alpha}+[0,D]^{d}$ intersects
finitely many members of $\mathcal{P}$, then there exists
$\vec{p}\in\mathbb{R}^{d}$ such that

$\lvert\mathcal{N}_{\overline{0}}(\vec{p})\rvert\geq d+1.$

Furthermore, $\mathcal{P}$ contains a $(d+1)$-clique.

Just as with the first two Optimality Theorems, we will show in sec:clique-
optimality that the hypothesis of the Second Optimality Theorem does not imply
the conclusion of the Third Optimality Theorem, so again there is a “gap”. Now
we turn to the proof outlines for the four theorems above.

###### Proof Outline for Lower Bound on Degree ($k$) (*:unit-hypercube-
optimality).

As a corollary to the Third Optimality Theorem, we get the same conclusion for
partitions whose members have a uniform upper bound on diameter and a uniform
lower bound on the measure (see :diam-measure-cor), and since unit hypercube
partitions have this property, the conclusion follows. ∎

###### Alternate Proof Sketch.

It is also possible to directly prove this result without using the heavy
machinery of the three Optimality Theorems by showing that if $\vec{p}$ is one
of the corners of some hypercube $X$, then it is at the closure of at least
$d+1$ members. The argument goes by induction on $d$ and considers the
$2^{d}$-many orthants locally around $\vec{p}$ showing that because $X$ takes
up exactly one orthant, the only ways to fill up the other $2^{d}-1$ orthants
requires at least $d$ other hypercubes. ∎

We give the outlines of the three Optimality Theorems in order of increasing
complexity (which happens to be reverse order).

###### Proof Outline for the Third Optimality Theorem.

To prove this, let $H$ denote the closed hypercube $\vec{\alpha}+[0,D]^{d}$
which intersects only finitely many elements of $\mathcal{P}$. We use the
partition $\mathcal{P}$ to induce a (finite) partition $\mathcal{S}$ on $H$:

$\mathcal{S}=\left\\{X\cap H:X\in\mathcal{P},\;X\cap
H\not=\emptyset\right\\}.$

$D$ remains a strict pairwise bound for all $X$ in the induced partition
$\mathcal{S}$. This means that no member of $\mathcal{S}$ intersects opposing
facets of the hypercube $H$, and thus no two corners of $H$ belong to the same
member of $\mathcal{S}$. We show that this allows us to color all points of
$H$ using $2^{d}$ colors (one associated with each corner) in such a way to
satisfy the coloring properties of a generalized Sperner’s lemma/KMM lemma,
and such that all points within any member of $\mathcal{S}$ are assigned the
same color. This will let us conclude that there is some point $\vec{p}$ of
the space belonging to the closure of $d+1$ colors, and because there are only
finitely many members of $\mathcal{S}$, we use the fact that the closure of a
finite union of members is equal to the finite union of the closures, and so
$\vec{p}$ belongs not just to the closure of $d+1$ colors, but to the closure
of $d+1$ members of $\mathcal{S}$. The existence of a $(d+1)$-clique is a
trivial consequence because all of these $d+1$ members have closures that
contain $\vec{p}$ and so each pair of these members is adjacent (see :defn-
adj). ∎

The proof of the Second Optimality Theorem is quite similar to the previous
proof.

###### Proof Outline for the Second Optimality Theorem.

Let $H=[0,D]^{d}$ and let $\mathcal{S}$ denote the partition of $H$ induced by
$\mathcal{P}$, observing that as before, the fact that each $X\in\mathcal{P}$
has $\operatorname{diam}(X)<D$ implies no member of $\mathcal{P}$ (and thus
$\mathcal{S}$) intersects opposing facets of $H$. Using the same Sperner/KMM
technique as before we can find some point $\vec{p}$ in the closure of $d+1$
colors. However, because the closure of an infinite collection of members may
be larger than the infinite union of the closures of those members, it is
possible that $\vec{p}$ does not belong to the closure of $d+1$ members of
$\mathcal{S}$. However, no matter what the value of $\epsilon(\vec{p})$ is,
this neighborhood of $\vec{p}$ contains an open set around $\vec{p}$, and that
open set must intersect some member of $\mathcal{S}$ corresponding to each of
the $d+1$ colors. This gives the result. ∎

The proof of the First Optimality Theorem is more involved.

###### Proof Outline for the First Optimality Theorem.

Having only a bound on the measure of the members of $\mathcal{P}$, it is
possible that they extend arbitrarily far (even infinitely far) within
$\mathbb{R}^{d}$, so the goal will be to approximate $\mathcal{P}$ by a nicer
partition that has bounded diameter elements and then utilize the same
Sperner/KMM techniques as used for the Second and Third Optimality Theorems.
In fact, the approximating partition $\mathcal{A}$ that we construct will
satisfy the hypothesis of the Third Optimality Theorem, so there is a point
$\vec{p}$ belonging to the closure of $d+1$ members of $\mathcal{A}$. We then
argue that the partition $\mathcal{A}$ is similar enough to $\mathcal{P}$ that
the set $B_{\epsilon}(\vec{p})$ intersects at least $d+1$ members of
$\mathcal{P}$.

In more detail, the steps are as follows:

  1. 1.

Partition $\mathbb{R}^{d}$ into a grid of $\epsilon$-diameter hypercubes

  2. 2.

Label each of these hypercubes with a member of $\mathcal{P}$ that it
intersects a lot (i.e. the measure of the intersection is sufficiently large)

  3. 3.

Define a graph (equivalently a symmetric binary relation) on the hypercubes so
that they are adjacent in the graph if they are close together and also share
the same label

  4. 4.

Consider the transitive closure of the relation (i.e. connected components of
the graph); show that each connected component has cardinality less than a
fixed size, and so has bounded diameter

  5. 5.

Consider the partition $\mathcal{A}$ where members correspond to equivalence
classes and apply the Third Optimality Theorem to get a point $\vec{p}$ at the
closure of $d+1$ members of $\mathcal{A}$

  6. 6.

Show that each such element of $\mathcal{A}$ is a superset of a hypercube in
the grid and that different elements of $\mathcal{A}$ which have $\vec{p}$ in
their closure contain hypercubes with distinct labels

  7. 7.

Show that each of the $d+1$ distinctly labeled hypercubes above are contained
in $B_{\epsilon}(\vec{p})$

∎

###  2.2 Upper Bound on Tolerance ($\epsilon$)

With the optimality of the parameter $k$ firmly established, we wish to
consider whether our value of $\epsilon=\frac{1}{2d}$ in :hypercube-partition-
thm is maximal when we have $k$ minimized at $k=d+1$. Ideally, we want to
consider optimality of the $\epsilon$ parameter not just for unit hypercube
partitions but for a broader class of partitions. A natural class is
partitions with the property that each member has a strict pairwise
bound888While it might seem that considering partitions with members of
diameter at most $D=1$ would be more natural than considering a strict
pairwise bound of $1$, working through the proofs of the results below one can
begin to see that actually, the strict pairwise bound is the “right” thing to
do as that is the condition that works best in the proofs. In fact, trying to
use the diameter leads to slightly weaker results. (see :strict-pairwise-
bound) of $D=1$; all unit hypercube partitions belong to this class999This is
at least true as we define unit hypercube partitions using half-open
hypercubes (see :defn-unit-hypercube-partition)., and $D=1$ is the smallest
value of $D$ we can use so that they do. For the sake of comparisons between
some results in the paper we didn’t want to fix $D$ to be $1$ in the statement
of the results below, but taking any of the results below as a standalone
result, the value of $D$ is nothing more than a trivial scaling factor, so the
reader can consider it to be fixed at $D=1$. The next result gives a trivial
bound on the tolerance parameter, but gives a tight bound for $d=1$.

[Trivial Tolerance ($\epsilon$)
Bound]propositionRestatableTrivialToleranceBound If $d\in\mathbb{N}$, and
$\mathcal{P}$ is a partition of $\mathbb{R}^{d}$, and there exists
$D\in(0,\infty)$ such that for all $X\in\mathcal{P}$,
$\operatorname{diam}(X)\leq D$, and if $\epsilon\in(0,\infty)$ such that for
all $\vec{p}\in\mathbb{R}^{d}$,

$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\leq 2^{d}$

then $\epsilon\leq\frac{D}{2}$.

###### Proof Sketch.

If $\epsilon>\frac{D}{2}$, we fix an arbitrary member $X$ of $\mathcal{P}$,
and shift the hypercube $[-\epsilon,\epsilon]^{d}$ so that $X$ is completely
contained in the interior. Then we observe that the $2^{d}$-many corners of
the shifted $[-\epsilon,\epsilon]^{d}$ are distance greater than $D$ apart (in
$d_{max}$), so they each belong to a distinct member of $\mathcal{P}$, and
none of them belong to $X$. Taking $\vec{p}$ to be the center of the shifted
$[-\epsilon,\epsilon]^{d}$, we have for contradiction that
$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\geq 2^{d}+1>2^{d}+1$. ∎

By considering the specific value $d=1$, we get the following corollary which
states that $\epsilon=\frac{D}{2d}=\frac{1}{2d}$ is indeed the optimal value
for the class of partitions with strict pairwise bound of $D=1$ for dimension
$d=1$.

[Optimal Tolerance ($\epsilon$) in
$\mathbb{R}^{1}$]corollaryRestatableOptimalToleranceROne If $d=1$ and
$\mathcal{P}$ is a partition of $\mathbb{R}^{d}=\mathbb{R}^{1}$, and there
exists $D\in(0,\infty)$ such that for all $X\in\mathcal{P}$, $D$ is a strict
pairwise bound for $X$, and if $\epsilon\in(0,\infty)$ is such that for all
$\vec{p}\in\mathbb{R}^{d}$,

$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\leq d+1=2$

then $\epsilon\leq\frac{D}{2}=\frac{D}{2d}$.

###### Proof.

Since $D$ is a strict pairwise bound for each member of $\mathcal{P}$, then
every member of $\mathcal{P}$ has diameter at most $D$. Apply :optimal-diam-d1
with $d=1$. ∎

We can also show that the value of $\epsilon=\frac{D}{2d}$ is optimal for
$d=2$, but :optimal-diam-d1 evaluated with $d=2$ does not give the correct
value, so it requires a separate proof.

[Optimal Tolerance ($\epsilon$) in
$\mathbb{R}^{2}$]propositionRestatableOptimalToleranceInRTwo If $d=2$ and
$\mathcal{P}$ is a partition of $\mathbb{R}^{d}=\mathbb{R}^{2}$, and there
exists $D\in(0,\infty)$ such that for all $X\in\mathcal{P}$, $D$ is a strict
pairwise bound for $X$, and if $\epsilon\in(0,\infty)$ is such that for all
$\vec{p}\in\mathbb{R}^{d}$,

$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\leq d+1=3$

then $\epsilon\leq\frac{D}{4}=\frac{D}{2d}$.

For other dimensions, we do not know if $\epsilon=\frac{D}{2d}$ is optimal
(though we conjecture that it is up to a constant factor; see :linear-
conjecture). The next result at least gives an upper bound that for any
$d\in\mathbb{N}$, $\epsilon\leq\frac{D}{2\sqrt{d}}$101010There are two useful
ways to interpret this upper bound. First, the value of
$\epsilon=\frac{1}{2d}$ that we achieve is within a factor of
$\frac{1}{\sqrt{d}}$ of the optimal value
$\epsilon^{\prime}\leq\frac{1}{2\sqrt{d}}$ which gives a bound on the quality
in terms of the dimension. Second, the value of $\epsilon=\frac{1}{2d}$ that
we achieve is correct to within a square:
$\epsilon=\frac{1}{2d}>\left(\frac{1}{2\sqrt{d}}\right)^{2}\geq(\epsilon^{\prime})^{2}$
which gives a dimension invariant way to view it..

[Universal Tolerance ($\epsilon$)
Bound]theoremRestatableUniversalToleranceBound If $d\in\mathbb{N}$, and
$\mathcal{P}$ is a partition of $\mathbb{R}^{d}$, and there exists
$D\in(0,\infty)$ such that for all $X\in\mathcal{P}$, it holds that $D$ is a
strict pairwise bound for $X$, and if there exists $\epsilon\in(0,\infty)$
such that for all $\vec{p}\in\mathbb{R}^{d}$,

$\lvert\mathcal{N}_{\epsilon}(\vec{p})\rvert\leq d+1,$

then $\epsilon\leq\frac{D}{2(\sqrt[d]{\operatorname{Sperner}(d)}-1)}$ (if
$d>1$). In particular, $\epsilon\leq\frac{D}{2\sqrt{d}}$ (for any $d$).

The $\operatorname{Sperner}(d)$ quantity in the theorem statement is something
that will be discussed in depth prior to proving the theorem. It will be
sufficient for now to note that $\operatorname{Sperner}(d)$ is bounded below
by the minimum number of simplices needed in any dissection of the $d$-cube,
and the “in particular” claim in the theorem uses a lower bound of
$(d+1)^{\frac{d-1}{2}}$ for the dissection number. Any improvements that are
made to the dissection number lower bound will translate directly to
improvements of our $\epsilon$ upper bound.

###### Proof Methods of *:sperner-upper-bound.

We apply a stronger version of Sperner’s lemma (or, equivalently, a stronger
version of the KKM lemma) to find multiple points within a fixed volume that
are near $d+1$ different members of the partition. It is then argued that the
$\epsilon$-balls around these points must be disjoint, and the value of
$\epsilon$ is bounded from above using a volume/measure argument. ∎

##  3 Related Work in Mathematics

We showed in sec:introduction how our work is related to rounding schemes used
in computational complexity theory, and in this section we connect our work to
the rich history of and continued interest in partitions of $\mathbb{R}^{d}$,
and in particular, partitions by unit hypercubes. Note that in essence, a
partition by unit hypercubes is the same as a tiling or a packing of unit
hypercubes. The only distinction is that in tilings and packings, the
boundaries are ignored and in a partition they are not. Further, it is common
in the literature to refer to $[0,1)^{d}$ and $[0,1]^{d}$ as a “cube”,
“$d$-cube”, or “hypercube”. Below, we discuss a number of questions that have
been investigated in the literature regarding tilings and unit hypercubes.
Most of these results deal with translated unit cubes (i.e. no rotation or the
higher dimensional analogs of rotation).

The purpose of these examples is fourfold: (1) to demonstrate broad interest
in hypercubes and hypercube partitions, (2) to show that even though questions
about hypercubes may seem very simple, there remains active research in this
area, (3) to preview a few questions related to some of our results, and (4)
to demonstrate that there are many results which hold in $\mathbb{R}^{1}$,
$\mathbb{R}^{2}$, and $\mathbb{R}^{3}$ but which may not hold in higher
dimensions.

#### Minkowski lattice cube-tiling conjecture (1907)

Minkowski’s conjecture [13] states that in any lattice tiling of
$\mathbb{R}^{d}$ by translated unit cubes there exists a pair of cubes whose
intersection is an entire $(d-1)$-dimensional face (e.g. in $\mathbb{R}^{2}$
there would be a pair of squares with a common edge, and in $\mathbb{R}^{3}$
there would be a pair of cubes sharing a common square side). A lattice tiling
is one in which the centers of all of the cubes form a critical lattice (see
Related Problems in [14] and [15] for definitions). It was proven true in 1941
by Hajós [16].

#### Keller’s conjecture (1930)

Keller’s conjecture [17] is a generalization of Minkowski’s conjecture, which
relaxes the assumption that the cubes form a lattice. Thus, it states that in
any tiling of $\mathbb{R}^{d}$ by translated unit cubes, there exists a pair
of cubes whose intersection is an entire $(d-1)$-dimensional face. The
complete resolution of this conjecture took substantial effort only being
completely resolved in 2020. In 1940 Perron [18, 19] showed it was true for
$d\leq 6$. Szabó [20] recast the question in terms of periodic tilings in 1986
and then introduced the so-called Keller graphs along with Corrádi in 1990
[21]. In 1992, Lagarias and Shor [22] used the Keller graphs to show that the
conjecture is false for all $d\geq 10$. This bound was refined by Mackey in
2002 [23] showing that the conjecture is false for $d\geq 8$. Progress on the
only remaining case of $d=7$ was made by Debroni, Eblen, Langston, Myrvold,
Shor, and Weerapurage in 2011 [24], and by Kisielewicz and Łysakowska in 2014
[25], and by Kisielewicz in 2017 [26] and by Łysakowska in 2018 [27]. Finally,
in 2020, Brakensiek, Heule, Mackey, and Narváez [28] determined that the
conjecture was true for $d=7$ using automated satisfiability approaches which
fully resolved the conjecture.

#### Furtwängler’s conjecture (1936)

Furtwängler’s conjecture [29] is another generalization of Minkowski’s
conjecture where instead of tilings, $k$-fold tilings are considered (a
$k$-fold tiling is a collection of positions so that if a hypercube is placed
at each position, then every point of $\mathbb{R}^{d}$ either belongs to the
boundary of some hypercube, or belongs to exactly $k$ hypercubes).
Furtwängler’s conjecture states that in any $k$-fold lattice tiling of
$\mathbb{R}^{d}$, there exists a pair of cubes whose intersection is an entire
$(d-1)$-dimensional face, and he proved it for $d\leq 3$. However, Hajós
proved in 1942 [16] that the conjecture was false for $d\geq 4$. In 1979,
Robinson [30] completely characterized the conjecture by proving for exactly
which pairs $(k,d)$ the conjecture held and which it did not.

#### Fuglede’s set conjecture (1974) and functional analysis

A set $\Omega\subset\mathbb{R}^{d}$ is called a spectral set if it has
positive measure and if there is a basis of certain exponential functions for
the space $L^{2}(\Omega)$ of square integrable functions (the set generating
the basis is denoted $\Lambda$). Fuglede [31] conjectured that a set was
spectral if and only if it could be used to tile $\mathbb{R}^{d}$. Though this
was proved false by Tao in 2004 [32], earlier work by Lagarias, Reeds, and
Wang in 2000 [33] showed something similar for the special case of unit cubes.
In particular, they showed that a set $\Lambda$ will generate a basis for
$L^{2}([0,1]^{d})$ if and only if $\Lambda$ is the set of center positions of
hypercubes in some partition of translated hypercubes. They used this result
to show that extending an orthogonal set of functions to a basis is equivalent
to extending a packing of hypercubes to a tiling. The ability to extend
packings to tilings was also studied by Dutour, Itoh, and Poyarkov in 2018
[34], though in a different context.

#### Countable partitions of $[0,1]$ by closed sets

A problem solved by Sierpiński [35, 36] was that there is no (non-trivial)
partition of the unit interval into countably many closed sets. This extends
trivially to show that there is no (non-trivial) partition the unit hypercube
$[0,1]^{d}$ into countably many closed sets. This has some connection to our
work. In particular, we state a conjecture which is equivalent to this problem
when $d=1$, and thus provides a natural interesting generalization of this
problem to higher dimensions.

#### Coverings, dissections, and triangulations of the cube

A covering of the cube is a set of simplices (using the vertices of the cube)
so that the union of the simplices is the entire cube. A dissection is a
covering with the additional requirement that the only overlap occurs at the
boundary of the simplices. A triangulation is a dissection with the additional
requirement that the intersection of any two simplices is either empty or a
face of each. It has long been known that there is a triangulation of the
$d$-cube $[0,1]^{d}$ using $d!$ simplices. In 1982, Sallee [37, 38] gave lower
bounds for how many simplices are needed in a triangulation, and many others
have tried to bound the minimal number of simplices needed for a covering, a
dissection, and a triangulation since then. In this paper, we will utilize the
dissection number for one of our upper bounds and will utilize the dissection
number lower bound of Glazyrin from 2012 [39].

#### Unit cubes more broadly

Many of the above results are discussed in the 2005 survey paper “What Is
Known About Unit Cubes” by Zong [40] and in his 2006 book [41]. In addition,
many other properties of unit cubes are presented. Zong makes the case that
despite the apparent simplicity of the $d$-cube, there is much that remains
unknown about it.

##  4 Organization

The remainder of the paper provides a complete description and proofs of the
established results in detail. In sec:notation, we summarize notation that we
will use. In sec:defn-basics we present some basic definitions and results
pertaining to partitions. In sec:reclusive-lattice-partitions we construct the
a class of partitions which we call reclusive partitions and prove the
Hypercube Partition Theorem. In sec:clique-optimality we prove three degree
Optimality Theorems to establish that $k=d+1$ is the minimum value of $k$ for
a broad range of reasonable partitions. In sec:epsilon we first prove the
optimality of the tolerance parameter for dimensions 1 and 2 (:optimal-diam-d1
and :optimal-diam-d2). In this section, we further show the $1/2\sqrt{d}$
upper bound the tolerance for higher dimensions. In sec:algorithm we offer an
application of secluded partitions to deterministic rounding and
multipseudodeterminism. sec:future contains concluding remarks and a
discussion about future research directions.

##  5 Notation

We will use the following notation and conventions throughout this paper.

  * •

We use $\mathbb{N}$ throughout to indicate the strictly positive integers.

  * •

For any $d\in\mathbb{N}$, we let $[d]$ denote the set of the first $d$
positive integers ($[d]=\left\\{1,2,\ldots,d\right\\}$).

  * •

If $d\in\mathbb{N}$ and $S\subseteq\mathbb{R}^{d}$ and
$\vec{v}\in\mathbb{R}^{d}$, then we use the following notation to indicate
shifting/translating the set $S$:

$\vec{v}+S=S+\vec{v}\operatorname{\overset{def}{=}}\left\\{\vec{s}+\vec{v}\colon\vec{s}\in
S\right\\}.$

  * •

For $d\in\mathbb{N}$ we define the metric $d_{max}$ on $\mathbb{R}^{d}$ which
is the metric induced by the $l^{\infty}$ norm111111Technically this is a
different metric for each dimension $d$, but it is not necessary to include
this in the notation as the dimension will be clear from context.:

$d_{max}(\vec{x},\vec{y})\operatorname{\overset{def}{=}}\max_{i\in[d]}\lvert
x_{i}-y_{i}\rvert=\lVert\vec{x}-\vec{y}\rVert_{\infty}.$

While we could use the $\lVert\cdot\rVert_{\infty}$ norm notation throughout
the paper, we choose to use the $d_{max}$ metric notation when possible.

  * •

For any $X\subseteq\mathbb{R}^{d}$ we denote the closure of $X$ with respect
to the $d_{max}$ metric by $\overline{X}$. Since the topology induced by the
$l^{\infty}$ norm on $\mathbb{R}^{d}$ is the same as the Euclidean topology
(induced by the $l^{2}$ norm), and the Euclidean topology on $\mathbb{R}^{d}$
is the same as the product topology on $\mathbb{R}^{d}$, the closure is the
same when taken with respect to any of these. In particular, if
$X_{1},\ldots,X_{d}\subseteq\mathbb{R}$ and $X=\prod_{i=1}^{d}X_{i}$, then
$\overline{X}=\prod_{i=1}^{d}\overline{X_{i}}$ (because the product of
closures is the same as the closure of the product).

  * •

For any $\vec{x}\in\mathbb{R}^{d}$ and $\epsilon\in(0,\infty)$ we use
$B^{\circ}_{\epsilon}(\vec{x})\operatorname{\overset{def}{=}}\left\\{\vec{y}\in\mathbb{R}^{d}:d_{max}(\vec{x},\vec{y})<\epsilon\right\\}$
to denote the open ball of radius $\epsilon$ around $\vec{x}$, and we use
$\overline{B}_{\epsilon}(\vec{x})\operatorname{\overset{def}{=}}\left\\{\vec{y}\in\mathbb{R}^{d}:d_{max}(\vec{x},\vec{y})\leq\epsilon\right\\}$
to denote the closed ball of radius $\epsilon$ around $\vec{x}$, noting that
$\overline{B}_{\epsilon}(\vec{x})=\overline{B^{\circ}_{\epsilon}(\vec{x})}$.
The standard notation for the open ball is $B_{\epsilon}(\vec{x})$, but we
will not use the open ball very often in this paper and prefer to use the
circle superscript to emphasize when we do. (Any occurrence in the paper of a
ball without the overline or the circle superscript is a typo.)

  * •

Though mentioned in the introduction, for ease of reference, we again define
the $\epsilon$-neighborhoods. When it is understood that we are considering a
particular partition $\mathcal{P}$, then for any point
$\vec{p}\in\mathbb{R}^{d}$, and any $\epsilon\in(0,\infty)$, we let

$\mathcal{N}_{\epsilon}(\vec{p})\operatorname{\overset{def}{=}}\left\\{X\in\mathcal{P}:X\cap\overline{B}_{\epsilon}(\vec{p})\not=\emptyset\right\\}.$
$\mathcal{N}_{\overline{0}}(\vec{p})\operatorname{\overset{def}{=}}\left\\{X\in\mathcal{P}:\overline{X}\ni\vec{p}\right\\}.$

An alternative expression of the former is as follows. This is justified in
:alternate-neighborhood-defn at the end of this section.

$\mathcal{N}_{\epsilon}(\vec{p})=\left\\{\operatorname{member}(\vec{x}):\vec{x}\in\overline{B}_{\epsilon}(\vec{p})\right\\}.$

  * •

If the partition $\mathcal{P}$ of $\mathbb{R}^{d}$ is understood, we define a
function $\operatorname{member}:\mathbb{R}^{d}\to\mathcal{P}$ mapping each
point $\vec{x}\in\mathbb{R}^{d}$ to the unique member containing it. Often
this is denoted using the equivalence class notation of $[\vec{x}]$, but in
this paper we shall prefer to use the $\operatorname{member}$ function
notation for clarity since we will in general not be thinking of the partition
as being defined by an equivalence relation.

  * •

When we say “countable” we mean finite or countably infinite.

######  Lemma 5.1.

$\mathcal{N}_{\epsilon}(\vec{p})=\left\\{\operatorname{member}(\vec{x}):\vec{x}\in\overline{B}_{\epsilon}(\vec{p})\right\\}.$

###### Proof.

If $X\in\mathcal{N}_{\epsilon}(\vec{p})$, then
$X\cap\overline{B}_{\epsilon}(\vec{p})\not=\emptyset$, so let $\vec{x}_{0}\in
X\cap\overline{B}_{\epsilon}(\vec{p})$ which means
$\operatorname{member}(\vec{x}_{0})=X$, so
$X\in\left\\{\operatorname{member}(\vec{x}):\vec{x}\in\overline{B}_{\epsilon}(\vec{p})\right\\}$.
Conversely, if
$X\in\left\\{\operatorname{member}(\vec{x}):\vec{x}\in\overline{B}_{\epsilon}(\vec{p})\right\\}$
then there exists $\vec{x}_{0}\in\overline{B}_{\epsilon}(\vec{p})$ such that
$X=\operatorname{member}(\vec{x}_{0})$, so in particular $\vec{x}_{0}\in X$
and thus $X\cap\overline{B}_{\epsilon}(\vec{p})\not=\emptyset$ so
$X\in\mathcal{N}_{\epsilon}(\vec{p})$. ∎

##  6 Definitions and Basic Partition Results

In this section, we will provide a variety of fairly basic claims about
hypercube partitions that we will need later. We also introduce an example of
a reclusive partition in order to present some geometric intuition before
moving into the linear algebra perspective in the next section.

We first define a natural notion of adjacency for any partition of
$\mathbb{R}^{d}$. By definition, no two members of a partition contain the
same element, but if we consider the closures of the members, then this need
not hold.

######  Definition 6.1 (Adjacent).

Let $d\in\mathbb{N}$, and $\mathcal{P}$ be a partition of $\mathbb{R}^{d}$,
and $X,Y\in\mathcal{P}$. We say that $X$ and $Y$ are adjacent if the
intersection of their closures is non-empty. That is, we say $X$ and $Y$ are
adjacent if $\overline{X}\cap\overline{Y}\not=\emptyset$. We denote this
relation as $X\operatorname{\overset{adj}{\sim}}Y$.

As defined, adjacency is a reflexive relation—for any partition $\mathcal{P}$,
for all $X\in\mathcal{P}$, we have $X\operatorname{\overset{adj}{\sim}}X$.
Also note that despite the notation, adjacency is not an equivalence relation
as it is not transitive in general.

Every partition of $\mathbb{R}^{d}$ naturally induces a graph in which
adjacency in the graph aligns with adjacency in the partition.

######  Definition 6.2 (Partition Graph).

Let $d\in\mathbb{N}$ and $\mathcal{P}$ be a partition of $\mathbb{R}^{d}$. The
partition graph of $\mathcal{P}$ is the graph $G$ whose vertex set is the set
$\mathcal{P}$, and whose edge set contains the edge $\left\\{X,Y\right\\}$ if
and only if $X\operatorname{\overset{adj}{\sim}}Y$ in the partition.

Because adjacency is reflexive, every vertex in $G$ has a self-loop. However,
this will not be important for us. We will usually not talk explicitly of this
graph and will instead identify the partition and its graph structure. We will
frequently need to prove that two members of a partition are not adjacent, and
we will use the following simple corollary.

######  Corollary 6.3 (Non-Adjacency Corollary).

Let $d\in\mathbb{N}$, and $\mathcal{P}$ be a partition of $\mathbb{R}^{d}$,
and $X,Y\in\mathcal{P}$. If for all $\vec{x}\in\overline{X}$ and
$\vec{y}\in\overline{Y}$ it holds that $d_{max}(\vec{x},\vec{y})>0$ then $X$
and $Y$ are not adjacent.

###### Proof.

For proof by contrapositive, if $X$ and $Y$ are adjacent, then there exists
$\vec{z}\in\overline{X}\cap\overline{Y}$, so let $\vec{x}=\vec{y}=\vec{z}$ and
we have $d_{max}(\vec{x},\vec{y})=0$. ∎

We will be particularly interested in partitions of translated unit hypercubes
as defined below.

######  Definition 6.4 (Unit Hypercubes and Unit Hypercube Partitions).

Let $d\in\mathbb{N}$. A set $X\subseteq\mathbb{R}^{d}$ is called a unit
hypercube if there exists $\vec{a}\in\mathbb{R}^{d}$ such that $X$ can be
expressed as

$X=\vec{a}+[0,1)^{d}.$

If so, this expression is unique, and we call $\vec{a}$ the representative
corner of $X$ and denote it by $\operatorname{rep}(X)$. A partition
$\mathcal{P}$ of $\mathbb{R}^{d}$ is called a unit hypercube partition if each
member of $\mathcal{P}$ is a unit hypercube.

It is worth noting that $\operatorname{rep}(X)\in X$.

The terminology of our definition may be somewhat deceptive because what we
call a unit hypercube partition requires these hypercubes to be translations
of $[0,1)^{d}$. For example, if $\mathbb{R}^{2}$ is partitioned by a unit grid
and the partition is rotated, then it would not be considered a unit hypercube
partition by our definition. As mentioned before, some other sources consider
the closed unit hypercube $\vec{a}+[0,1]^{d}$ or rotations of this set. If we
need a closed unit hypercube, we mention so explicitly.

The following simple lemma shows that shifting a unit hypercube changes the
representative corner in the natural way.

######  Lemma 6.5 (Representative Corner Shift Lemma).

Let $d\in\mathbb{N}$, and $X\subset\mathbb{R}^{d}$ be a unit hypercube. Then
for any vector $\vec{v}\in\mathbb{R}^{d}$,

$\operatorname{rep}(X+\vec{v})=\operatorname{rep}(X)+\vec{v}.$

###### Proof.

This holds because if $X=\vec{a}+[0,1)^{d}$, then
$X+\vec{v}=(\vec{a}+\vec{v})+[0,1)^{d}$. ∎

While the defined notion of adjacency may be the most natural, it will not be
the easiest to work with, so the next two lemmas together give an equivalent
characterization of adjacency of members of a unit hypercube partition. The
first lemma states that in a unit hypercube partition it is impossible to have
two distinct unit hypercubes $X$ and $Y$ with representative corners closer
than a distance of $1$ of each other, because otherwise the hypercubes would
overlap.

######  Lemma 6.6 (Non-Overlapping Lemma).

Let $d\in\mathbb{N}$, and $\mathcal{P}$ be a unit hypercube partition of
$\mathbb{R}^{d}$, and $X,Y\in\mathcal{P}$. Then either $X=Y$ or
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\geq 1$.

###### Proof.

If $d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))<1$ then for all
$i\in[d]$,
$\lvert\operatorname{rep}(X)_{i}-\operatorname{rep}(Y)_{i}\rvert<1$. Thus, for
all $i\in[d]$, either

$\operatorname{rep}(X)_{i}\in[\operatorname{rep}(Y)_{i},\operatorname{rep}(Y)_{i}+1)$

or

$\operatorname{rep}(Y)_{i}\in[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1).$

In either case, this implies

$[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1)\cap[\operatorname{rep}(Y)_{i},\operatorname{rep}(Y)_{i}+1)\not=\emptyset.$

Note that by definition of $\operatorname{rep}(X)$ and
$\operatorname{rep}(Y)$, we can express $X$ and $Y$ as

$\displaystyle X$
$\displaystyle=\prod_{i=1}^{d}[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1)$
$\displaystyle Y$
$\displaystyle=\prod_{i=1}^{d}[\operatorname{rep}(Y)_{i},\operatorname{rep}(Y)_{i}+1).$

This implies that $X\cap Y\not=\emptyset$, and because $\mathcal{P}$ is a
partition, this implies $X=Y$. ∎

The next lemma shows that in the case of of adjacent hypercubes, the above
lower bound on the distance between the representative corners is tight. The
intuition is that if $X$ and $Y$ are unit hypercubes, then because the side
lengths of the hypercubes are all 1, it is the case that adjacency of $X$ and
$Y$ is equivalent to the representatives of $X$ and $Y$ being within a
distance of 1 (in the $d_{max}$ metric, which measures the furthest
coordinate).

######  Lemma 6.7 (Adjacency by Representatives Lemma).

Let $d\in\mathbb{N}$, and $\mathcal{P}$ be a unit hypercube partition of
$\mathbb{R}^{d}$, and $X,Y\in\mathcal{P}$. Then
$X\operatorname{\overset{adj}{\sim}}Y$ if and only if
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\leq 1$.

###### Proof.

We begin with the reverse direction. If
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\leq 1$ then for all
$i\in[d]$,
$\lvert\operatorname{rep}(X)_{j}-\operatorname{rep}(Y)_{j}\rvert\leq 1$. By
similar reasoning as the previous lemma (but using the closed intervals
instead of the half open intervals), we have for all $i\in[d]$,

$[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1]\cap[\operatorname{rep}(Y)_{i},\operatorname{rep}(Y)_{i}+1]\not=\emptyset.$

Since
$X=\prod_{i=1}^{d}[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1)$
(and similarly for $Y$), we can express the closures as

$\displaystyle\overline{X}$
$\displaystyle=\prod_{i=1}^{d}[\operatorname{rep}(X)_{i},\operatorname{rep}(X)_{i}+1]$
$\displaystyle\overline{Y}$
$\displaystyle=\prod_{i=1}^{d}[\operatorname{rep}(Y)_{i},\operatorname{rep}(Y)_{i}+1].$

Thus $\overline{X}$ and $\overline{Y}$ intersect in each coordinate, so
$\overline{X}\cap\overline{Y}\not=\emptyset$. Thus, by definition,
$X\operatorname{\overset{adj}{\sim}}Y$.

Now we prove the forward direction by contrapositive. Suppose
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))>1$. This implies the
existence of some $j\in[d]$ such that
$\lvert\operatorname{rep}(X)_{j}-\operatorname{rep}(Y)_{j}\rvert>1$. This
means

$[\operatorname{rep}(X)_{j},\operatorname{rep}(X)_{j}+1]\cap[\operatorname{rep}(Y)_{j},\operatorname{rep}(Y)_{j}+1]=\emptyset$

thus $\overline{X}\cap\overline{Y}=\emptyset$, so $X$ and $Y$ are not
adjacent. ∎

The previous two lemmas give rise to a number of equivalent notions of
adjacency in a unit hypercube partition which we now formalize.

######  Corollary 6.8 (Equivalent Definitions of Adjacency).

Let $d\in\mathbb{N}$, and $\mathcal{P}$ be a unit hypercube partition of
$\mathbb{R}^{d}$, and $X,Y\in\mathcal{P}$. The following statements are all
equivalent:

  1. 1.

$X\operatorname{\overset{adj}{\sim}}Y$

  2. 2.

$X=Y$ or $d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=1$

  3. 3.

$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=0$ or
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=1$

  4. 4.

$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\leq 1$

###### Proof.

That (1) and (4) are equivalent is the statement of the previous lemma.
Statements (2) and (3) are equivalent because $X=Y$ if and only if
$\operatorname{rep}(X)=\operatorname{rep}(Y)$ if and only if
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=0$. Thus, it suffices to
show that (3) and (4) are equivalent.

Trivially, (3) implies (4). To show that (4) implies (3), assume
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\leq 1$; so by :non-
overlapping, either $X=Y$ implying
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=0$ implying (3), or
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\geq 1$ implying
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))=1$ (because
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))\leq 1$ by hypothesis)
implying (3).

∎

The following proposition shows that in a hypercube partition, if a collection
of hypercubes is a clique in the partition graph (i.e. they are all pairwise
adjacent), then that actually implies that there is a point $\vec{p}$ which is
at the closure of all of them, and so for any choice of
$\epsilon\in(0,\infty)$, $\overline{B}_{\epsilon}(\vec{p})$ will intersect
every one of these hypercubes. This does not hold for more general partitions.
The usefulness of this result is that it is possible to show that a unit
hypercube partition is not $(k,\epsilon$-secluded by finding a clique of size
$k+1$.

######  Proposition 6.9 (Hypercube Cliques).

Let $d,n\in\mathbb{N}$, and $\mathcal{P}$ be a unit hypercube partition of
$\mathbb{R}^{d}$, and $X_{1},\ldots,X_{n}\in\mathcal{P}$ such that for all
$i,j\in[n]$ $X_{i}\operatorname{\overset{adj}{\sim}}X_{j}$. Then there is a
point $\vec{p}\in\mathbb{R}^{d}$ such that for all $i\in[n]$,
$\vec{p}\in\overline{X_{i}}$.

###### Proof.

Let $X_{1},\ldots,X_{n}$ as stated. Each $\overline{X_{i}}$ can be expresses
as $\overline{X_{i}}=\overline{B}_{\frac{1}{2}}(\vec{x}^{(i)})$ for some
$\vec{x}^{(i)}\in\mathbb{R}^{d}$. Because each $X_{i}$ and $X_{j}$ are
adjacent, by definition $\overline{X_{i}}\cap\overline{X_{j}}\not=\emptyset$,
and because of each these sets is a metric ball of radius $\frac{1}{2}$, it
follows that $d_{max}(\vec{x}^{(i)},\vec{x}^{(j)})\leq 1$. It is a property of
the $d_{max}$ metric that if a set of vectors are all pairwise within distance
$1$ of each other, then there is a point $\vec{p}$ which is within distance
$\frac{1}{2}$ of all of them121212If the set of vectors is $S$, then the point
$\vec{p}$ can defined coordinate-wise as $p_{i}=\frac{1}{2}(\sup_{\vec{x}\in
S}x_{i}-\inf_{\vec{x}\in S}x_{i})$., so we can find such a $\vec{p}$ for the
set $\vec{x}^{(i)},\ldots,\vec{x}^{(n)}$. Since $\vec{p}$ is distance at most
$\frac{1}{2}$ from each $\vec{x}^{(n)}$, that means
$\vec{p}\in\overline{B}_{\frac{1}{2}}(\vec{x}^{(n)})=\overline{X_{i}}$. ∎

##  7 Reclusive Partitions

In this section we define what we call reclusive partitions. The word
reclusive is a synonym of secluded, but we will have a different technical
definition. We have used, and will continue to use the term secluded to
discuss generic partitions. We will use the term reclusive partition to talk
about unit hypercube partitions which have the very specific linear algebra
structure that we develop in this section.

###  7.1 An Example Reclusive Partition

We will shortly be working with partitions of $\mathbb{R}^{d}$ from a linear
algebraic perspective because that allows us to state the results very
generally. However, this makes the intuition of the geometry more difficult.
As a partial remedy for this, we first introduce a very specific reclusive
partition of $\mathbb{R}^{d}$ for each $d\in\mathbb{N}$—these are the
partitions that we first studied, and they are mathematically very convenient
to work with. We will not be interested in them as anything more than an
example because the parameter value of $\epsilon$ that they achieve is only
$\frac{1}{2^{d-1}}$ and as we have mentioned, some of the reclusive partitions
will achieve as large as $\frac{1}{2d}$. Nonetheless, these partitions capture
the essential geometric idea of the construction of the more general reclusive
partitions.

The following defines for all $d\in\mathbb{N}$ a partition of $\mathbb{R}^{d}$
which consists solely of half-open/half-closed unit hypercubes. After
presenting the definition, we elaborate on how to interpret it geometrically.

######  Definition 7.1 ($\mathcal{P}_{d}$).

For each $d\in\mathbb{N}$, define131313By this definition, in the case that
$d=1$, $v_{d}=\langle 1\rangle$.
$\vec{v_{d}}\operatorname{\overset{def}{=}}\langle\frac{1}{2^{d-1}},\ldots,\frac{1}{2^{d-1}},1\rangle$,
the vector whose last entry is $1$ and all other $d-1$ entries are
$\frac{1}{2^{d-1}}$.

Define $\mathcal{P}_{1}$, which is a partition of $\mathbb{R}^{1}$, as
follows:

$\mathcal{P}_{1}\operatorname{\overset{def}{=}}\left\\{[0,1)+n\colon
n\in\mathbb{Z}\right\\}=\left\\{[0,1)+n\cdot\vec{v_{1}}\colon
n\in\mathbb{Z}\right\\}.$

Then define $\mathcal{P}_{d}$, which is a partition of $\mathbb{R}^{d}$,
inductively for all $d\in\mathbb{N}$ with $d>1$ as follows:

$\mathcal{P}_{d}\operatorname{\overset{def}{=}}\left\\{B\times[0,1)+n\cdot\vec{v_{d}}\colon
n\in\mathbb{Z},\;B\in\mathcal{P}_{d-1}\right\\}$

The following discussion motivates why we are interested in this partition and
how to understand it geometrically. The first partition ($d=1$) breaks up
$\mathbb{R}^{d}=\mathbb{R}^{1}$ into unit intervals which are half open. This
partition has the property that for any fixed point $x\in\mathbb{R}^{1}$, if
you consider all points with (Euclidean) distance less than or equal to
$1/2^{d}=1/2$ from $x$, all such points belong to at most $d+1=2$ members of
the partition $\mathcal{P}_{1}$ (see fig:simple-partition).

Then consider how the second partition $\mathcal{P}_{2}$ is constructed by
first examining only the members constructed when $n=0$. In this case, each
member is $B\times[0,1)$ for some $B\in\mathcal{P}_{1}$. We think of this as
extruding each member of the previous partition one unit into the newest
dimension. Restricted to $n=0$, this would partition
$\mathbb{R}^{1}\times[0,1)$, so to capture all elements of $\mathbb{R}^{2}$,
we need to make shifts not just for $n=0$ but for every integer. The last
index of $\vec{v_{d}}$ is $1$ to get integer shifts in the newest dimension so
that for an arbitrary value of $n$ we get a partition of
$\mathbb{R}^{1}\times[n,n+1)$.

Why is it that $\vec{v_{d}}$ is defined as it is? If we had taken
$\vec{v_{d}}=\langle 0,\ldots,0,1\rangle$ for example (so that
$\vec{v_{2}}=\langle 0,1\rangle$), the definition above would still produce a
partition. However, it would not have the desired property that for any point
$\vec{x}\in\mathbb{R}^{2}$ the points within a distance $1/2^{d}=1/4$ belong
to at most $d+1=3$ members of $\mathcal{P}_{2}$. For example (see fig:simple-
partition), the point $(1,1)$ would be arbitrarily close to points of the
following four members: $[0,1)\times[0,1)$, $[0,1)\times[1,2)$,
$[1,2)\times[0,1)$, $[1,2)\times[1,2)$.

To get this property, we shift the extrusions by a “little bit” in all of the
other dimensions too in order to offset the “seams” or boundaries between
members of the partition. With each new partition we build from an old one,
the amount of shift in each dimension is reduced (the entries in the vector
$\vec{v_{d}}$ decrease as $d$ increases) so that shifts aren’t “undone” by
shifting too much and cycling back. The construction of $\mathcal{P}_{3}$ has
a similar intuition, and beyond that, we find it difficult to visualize. For
completeness, we next prove that the $\mathcal{P}_{d}$ are indeed partitions.
The proof will probably not lend insight to the rest of the paper and should
be freely skipped.

######  Claim 7.2.

For each $d\in\mathbb{N}$, $\mathcal{P}_{d}$ is a partition of
$\mathbb{R}^{d}$.

###### Proof.

If $d=1$ (for an inductive base case), let $x\in\mathbb{R}^{1}$ be arbitrary
and let $n=\lfloor x\rfloor$ so $x\in[n,n+1)$ and $x\not\in[m,m+1)$ for any
$m\not=n$, so $\mathcal{P}_{1}$ partitions $\mathbb{R}^{1}$.

The inductive case follows similarly. Let $\vec{x}=\langle
x_{i}\rangle_{i=1}^{d}\in\mathbb{R}^{d}$ be arbitrary. We want to prove the
existence of unique $n\in\mathbb{Z}$ and $B\in\mathcal{P}_{d-1}$ such that
$\vec{x}\in B\times[0,1)+n\cdot\vec{v_{d}}$. Note that by necessity $n=\lfloor
x_{d}\rfloor$ so that $x_{d}\in[0,1)+n\cdot 1=[n,n+1)$ (recall that the last
coordinate of $\vec{v_{d}}$ is $v_{d_{d}}=1$). Then we see that $\vec{x}\in
B\times[0,1)+n\cdot\vec{v_{d}}$ if and only if $\vec{x}-n\cdot\vec{v_{d}}\in
B\times[0,1)$, and since we have already established the value of $n$, this
holds if and only if $\langle x_{i}-n\cdot v_{d_{i}}\rangle_{i=1}^{d-1}\in B$.
By the inductive hypothesis, there exists a unique $B\in\mathcal{P}_{d-1}$
such that this holds. Thus $\mathcal{P}_{d}$ partitions $\mathbb{R}^{d}$. ∎

Based on our discussion above, we hope we have provided the intuition that
each member of any $\mathcal{P}_{d}$ is a unit hypercube with some amount of
shift. The $\mathcal{P}_{d}$ example partitions will be useful to keep in mind
as we work with more general unit hypercube partitions.

###  7.2 Motivating Properties

While the inductive definition of the running example partitions
$\mathcal{P}_{d}$ is useful, it is also useful to consider unit hypercube
partitions from another perspective. One can note that in the partition
$\mathcal{P}_{d}$, the representative corner of each unit hypercube is an
integer linear combination of the vectors $\vec{v_{1}},\ldots,\vec{v_{d}}$ as
defined in :example-partition (padded with zeros in the trailing entries as
necessary which correspond to the higher dimensions). The set of all integer
linear combinations of a set of basis vectors for the vector space
$\mathbb{R}^{d}$ is known as a lattice group (it is a group under vector
addition). Viewing the hypercube representatives as points within the lattice
group will be useful. In particular, this gives motivation to look at certain
regularly structured unit hypercube partitions by examining a matrix
associated with a set of basis vectors of $\mathbb{R}^{d}$. For example,
consider the example partition $\mathcal{P}_{d}$ for $d=5$. If we embed the
vectors $\vec{v_{1}},\ldots,\vec{v_{5}}$ from :example-partition into
$\mathbb{R}^{5}$ (by padding), and use those vectors as the columns of a
matrix, then the matrix would be as follows (e.g. the first column is
$\vec{v_{1}}$, the second column is $\vec{v_{2}}$, and so on with zeros padded
at the end as necessary).

$A=\left[\begin{array}[]{ccccc}1&\frac{1}{2}&\frac{1}{4}&\frac{1}{8}&\frac{1}{16}\\\
0&1&\frac{1}{4}&\frac{1}{8}&\frac{1}{16}\\\ 0&0&1&\frac{1}{8}&\frac{1}{16}\\\
0&0&0&1&\frac{1}{16}\\\ 0&0&0&0&1\end{array}\right]$

In fact, we could equivalently have defined $\mathcal{P}_{5}$ (and similarly
for all $\mathcal{P}_{d}$ from the running example) to be the set of unit
hypercubes whose representatives were integer linear combinations of the
columns of this matrix; in other words, $\mathcal{P}_{5}$ could have been
defined as the set of unit hypercubes whose representatives are given by
$A\vec{n}$ for some $\vec{n}\in\mathbb{Z}^{d}$.

In light of this, we shall define a more structured version of unit hypercube
partitions by defining them in terms of a matrix. Observe the following four
structural properties of the example matrix $A$ above:

  1. 1.

The matrix $A$ for $\mathcal{P}_{5}$ above explicitly contains the structure
of the partitions $\mathcal{P}_{d}$ for $d\leq 5$ in the sense that the
submatrix consisting of the first 4 rows and first 4 columns is the matrix
associated with the partition $\mathcal{P}_{4}$. Similarly the submatrix
consisting of the first 3 rows and first 3 columns is the matrix associated
with the partition $\mathcal{P}_{3}$, and so on.

  2. 2.

The matrix is upper triangular. The reason is that in the inductive definition
of $\mathcal{P}_{d}$, the vector $\vec{v_{d}}$ is in $\mathbb{R}^{d}$, so the
lengths of these vectors grows by one with each iteration of the construction,
and each iteration of the construction adds a row and column.

  3. 3.

The diagonal of the matrix is all 1’s. This is because in the inductive
definition of $\mathcal{P}_{d}$, there has to be a unit shift in the current
dimension to accommodate that the members of the partition are unit
hypercubes. For example, in the definition of $\mathcal{P}_{1}$, the members
are $[0,1)+n\langle 1\rangle$ for all $n\in\mathbb{Z}$. If the vector $\langle
1\rangle$ was anything else, this would not be a partition. In the case of
$\mathcal{P}_{2}$, each element is of the form
$B\times[0,1)+n\langle\frac{1}{2},1\rangle$. Again, the last index of this
vector must be 1 because we are extruding the elements of the previous
partition by $[0,1)$. This holds in each dimension of the construction.

  4. 4.

The entries in each row are strictly decreasing. This is because in the
inductive definition of $\mathcal{P}_{d}$, we wanted to offset the “seams” of
the hypercubes to prevent points in $\mathbb{R}^{n}$ from being “close” to too
many hypercubes. For example, if we had defined $\mathcal{P}_{d}$ by taking
each $\vec{v_{d}}$ to be the vector of all 0’s aside from the last entry being
1, then the associated matrix would be the identity matrix. This would indeed
generate a unit hypercube partition, but it would not have the property we
ultimately desire of limiting the adjacencies (in fact, this is the partition
in fig:simple-partition).

As mentioned earlier, while the $\mathcal{P}_{d}$ serve as nice examples, the
exponentially decreasing nature of the shifts
($\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\ldots$) leads to a need
for exponentially decreasing $\epsilon$ parameter. Instead, we would like the
shifts to change linearly and work with partitions that have matrices more
like one of the ones below:

$\left[\begin{array}[]{ccccc}1&\frac{4}{5}&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\
0&1&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\ 0&0&1&\frac{2}{5}&\frac{1}{5}\\\
0&0&0&1&\frac{1}{5}\\\
0&0&0&0&1\end{array}\right]\qquad\text{or}\qquad\left[\begin{array}[]{ccccc}1&\frac{4}{5}&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\
0&1&\frac{4}{5}&\frac{3}{5}&\frac{2}{5}\\\ 0&0&1&\frac{4}{5}&\frac{3}{5}\\\
0&0&0&1&\frac{4}{5}\\\ 0&0&0&0&1\end{array}\right]$

In fact, we will define the matrices of interest in a general enough way to
include all of the matrices shown so far. Notice that both of these two
matrices have the same structural properties mentioned above.

We now define the type of matrices that we will be interested in based on the
ideas just discussed. These matrices will be used to define partitions which
have the property that hypercubes will be adjacent to a small number of other
hypercubes; in the language of graph theory, the members will have few
neighbors, so we call them reclusive matrices and reclusive partitions. Stated
again for emphasis, we will have a connection between minimizing the parameter
$k$ in the motivating question in the introduction, and minimizing the sizes
of cliques in the partition graph.

###  7.3 Construction

######  Definition 7.3 (Reclusive Matrix).

Informally, a square matrix $A$ will be called a reclusive matrix if it is
upper triangular, has only $1$’s on the main diagonal, and is strictly
decreasing with positive entries in each row starting at the main diagonal.

More formally, a square $n\times n$ matrix $A=(a_{ij})$ will be called a
reclusive matrix if all of the following hold:

  1. 1.

For all $i>j\in[n]$, $a_{ij}=0$. (Upper Triangular)

  2. 2.

For all $i\in[n]$, $a_{ii}=1$. ($1$’s on Diagonal)

  3. 3.

For all $i\leq j<k\in[n]$, $a_{ij}>a_{ik}>0$. (Decreasing and Non-zero after
Diagonal)

######  Remark 7.4.

Reclusive matrices are invertible because they are upper triangular so the
determinant is equal to the product of the diagonal entries which are all 1.

We view $d\times d$ reclusive matrices as a natural way to build partitions of
$\mathbb{R}^{d}$ as just discussed. Before defining these partitions, we
formalize the lattice group structure mentioned in the motivating discussion.

######  Definition 7.5 (Lattice Group).

For any invertible $d\times d$ matrix $A$, define the set
$L_{A}\operatorname{\overset{def}{=}}\left\\{A\vec{v}\colon\vec{v}\in\mathbb{Z}^{d}\right\\}$.

The set $L_{A}$ is a group under vector addition. Since $A$ is an invertible
linear map, it is actually an isomorphism between $L_{A}$ and
$\mathbb{Z}^{d}$.

######  Definition 7.6 (Reclusive Partition).

If $A$ is a $d\times d$ reclusive matrix, then we associate to it a partition
$\mathcal{P}_{A}$, called the reclusive partition for $A$, where

$\mathcal{P}_{A}\operatorname{\overset{def}{=}}\left\\{\vec{a}+[0,1)^{d}\colon\vec{a}\in
L_{A}\right\\}.$

######  Remark 7.7.

Some sources use the notation $L_{A}+[0,1)^{d}$ to indicate the set
$\mathcal{P}_{A}$, but we will elect to not do so here.

Notice that every member of $\mathcal{P}_{A}$ is a unit hypercube shifted by
an element of the lattice group so that for all $X\in\mathcal{P}_{A}$,
$\operatorname{rep}(X)\in L_{A}$ and conversely, for every $\vec{a}\in L_{A}$
there is a unit hypercube $X$ whose representative is $\vec{a}$. The proof
that this is a partition will not be presented as it is a direct consequence
of :efficent-computation-of-representatives which shows that for any element
$\vec{x}\in\mathbb{R}^{d}$ there is a unique $X\in\mathcal{P}$ such that
$\vec{x}\in X$ by explicitly computing the representative
$\operatorname{rep}(X)$.

We will have use for yet another equivalent notion of adjacency, but to do so
we must introduce two definitions for types of finite sequences (which we will
apply to vectors). These defined sequences will play the essential role in
proving that the reclusive partitions have the properties that we are looking
for.

######  Definition 7.8 (Alt-1 and Weak-Alt-1 Sequences).

A finite sequence $\langle c_{i}\rangle_{i=1}^{n}$ is called alt-1
(alternating sequence of magnitude 1) if $\langle
c_{i}\rangle_{i=1}^{n}=\langle(-1)^{i}\rangle_{i=1}^{n}$ or $\langle
c_{i}\rangle_{i=1}^{n}=\langle(-1)^{i+1}\rangle_{i=1}^{n}$.

A finite sequence $\langle c_{i}\rangle_{i=1}^{n}$ is called weak-alt-1
(weakly alternating sequence of magnitude 1) if all terms are $-1$, $0$, or
$1$, and the subsequence $\langle c_{i_{j}}\rangle_{j=1}^{k}$ of non-zero
terms is an alt-1 sequence.

######  Remark 7.9.

We consider the empty sequence to vacuously satisfy these definitions, so in
particular, a finite sequence of all zeros is considered weak-alt-1.

The next lemma is more or less an adaption of the alternating sequence
convergence theorem from calculus (c.f. [42]). If we take a dot product of an
alt-1 sequence and a strictly monotonic positive sequence, then we know what
the sign of that dot product will be and can bound the magnitude.

######  Lemma 7.10.

Let $\langle c_{i}\rangle_{i=1}^{n}$ be an alt-1 sequence. Let $\langle
a_{i}\rangle_{i=1}^{n}$ be a strictly decreasing (resp. strictly increasing)
positive sequence. Letting $s=\sum_{i=1}^{n}c_{i}a_{i}$, the following hold:

  1. 1.

If $n=1$ then $\lvert s\rvert=a_{1}$ (resp. $\lvert s\rvert=a_{n}$)

  2. 2.

If $n\geq 2$ then $a_{1}-a_{2}\leq\lvert s\rvert\leq a_{1}$ (resp.
$a_{n}-a_{n-1}\leq\lvert s\rvert\leq a_{n}$)

  3. 3.

$\lvert s\rvert>0$

  4. 4.

$\operatorname{sign}(s)=\operatorname{sign}(c_{1})$ (resp.
$\operatorname{sign}(s)=\operatorname{sign}(c_{n})$)

###### Proof.

Note that (3) is implied by (1) and implied by (2) since $\langle
a_{i}\rangle$ is strictly decreasing (resp. strictly increasing), so (3) need
not be proven.

We prove the “increasing” version of the statement because the inductive
indexing is cleaner. This immediately implies the stated “decreasing” version
by reversing $\langle a_{i}\rangle$ and reversing $\langle c_{i}\rangle$.

We prove the “increasing” version by induction on $n$. If $n=1$, the claim
holds trivially. Otherwise $n>1$ and assume for inductive hypothesis that the
lemma holds for $n-1$. Then let

$s\operatorname{\overset{def}{=}}\sum_{i=1}^{n}c_{i}a_{i}\qquad\text{and}\qquad
s^{\prime}\operatorname{\overset{def}{=}}\sum_{i=1}^{n-1}c_{i}a_{i}\qquad\text{noting
that}\qquad s=s^{\prime}+c_{n}a_{n}.$

Thus, we have

$\displaystyle s$ $\displaystyle=s^{\prime}+c_{n}a_{n}$
$\displaystyle=\operatorname{sign}(s^{\prime})\lvert
s^{\prime}\rvert+c_{n}a_{n}$ (Decomposition of $s^{\prime}$)
$\displaystyle=\operatorname{sign}(c_{n-1})\lvert s^{\prime}\rvert+c_{n}a_{n}$
(Inductive hypothesis) $\displaystyle=-c_{n}\lvert
s^{\prime}\rvert+c_{n}a_{n}$ ($\operatorname{sign}(c_{n-1})=c_{n-1}=-c_{n}$ by
alt-1 def’n) $\displaystyle=c_{n}(a_{n}-\lvert s^{\prime}\rvert).$

Taking the magnitude we have

$\displaystyle\lvert s\rvert$ $\displaystyle=\lvert c_{n}\rvert\lvert
a_{n}-\lvert s^{\prime}\rvert\rvert$ $\displaystyle=\lvert a_{n}-\lvert
s^{\prime}\rvert\rvert$ $\displaystyle=a_{n}-\lvert s^{\prime}\rvert.$
($a_{n}$ and $\lvert s^{\prime}\rvert$ both non-negative)

Since $\lvert s^{\prime}\rvert$ is non-negative, it follows that $\lvert
s\rvert\leq a_{n}$. Further, by inductive hypothesis, $\lvert
s^{\prime}\rvert\leq a_{n-1}$ so again by the last line above, $\lvert
s\rvert=a_{n}-\lvert s^{\prime}\rvert\geq a_{n}-a_{n-1}$ which proves (2).

Lastly, noting again that $a_{n}>a_{n-1}\geq\lvert s^{\prime}\rvert$ we have

$\displaystyle\operatorname{sign}(s)$
$\displaystyle=\operatorname{sign}(c_{n}(a_{n}-\lvert s^{\prime}\rvert))$
$\displaystyle=\operatorname{sign}(c_{n})\operatorname{sign}(a_{n}-\lvert
s^{\prime}\rvert)$ $\displaystyle=c_{n}\cdot 1$
($c_{n}=\operatorname{sign}(c_{n})$ and $a_{n}-\lvert s^{\prime}\rvert>0$)

which proves (4). ∎

The reason we required $\langle a_{i}\rangle$ to be strictly monotonic was
because otherwise $\operatorname{sign}(c_{n})$ could be $0$. The above lemma
extends very naturally to weak-alt-1 sequences which have at least one non-
zero term by applying the lemma to the subsequence of non-zero terms and the
corresponding entries of $\langle a_{i}\rangle$ and we shall sometimes use it
as such.

The following proposition will be the key to establishing the (final)
equivalent definition of adjacency. The $A\vec{c}$ in the statement will end
up being $\operatorname{rep}(X)-\operatorname{rep}(Y)$ for unit hypercubes $X$
and $Y$, so this proposition will give an equivalent condition for
$\lVert\operatorname{rep}(X)-\operatorname{rep}(Y)\rVert_{\infty}\leq 1$
(which by :equiv-defn-adjacency is equivalent to $X$ and $Y$ being adjacent).

######  Proposition 7.11.

Let $A$ be a $d\times d$ reclusive matrix and $\vec{c}\in\mathbb{Z}^{d}$
(emphasis: $\vec{c}$ has integer coordinates). Then $\lVert
A\vec{c}\rVert_{\infty}\leq 1$ if and only if $\vec{c}=\langle
c_{j}\rangle_{j=1}^{d}$ is a weak-alt-1 sequence.

###### Proof.

Before proving either direction, let $\vec{x}=A\vec{c}$. Note that for any
$i\in[d]$

$\displaystyle x_{i}$ $\displaystyle=\sum_{j=1}^{d}a_{ij}c_{j}$ (Def’n of
matrix multiplication) $\displaystyle=\sum_{j=i}^{d}a_{ij}c_{j}.$ (If $j<i$
then $a_{ij}=0$)

Note that $\langle a_{ij}\rangle_{j=i}^{d}$ is a strictly decreasing positive
sequence.

We begin by proving the reverse direction. If $\langle c_{j}\rangle_{j=1}^{d}$
is a weak-alt-1 sequence, then for any $i\in[d]$, the subsequence $\langle
c_{j}\rangle_{j=i}^{d}$ is also a weak-alt-1 sequence. Then by :alt-1-sums
(applied to the subsequence of non-zero terms) and the expression of $\vec{x}$
above, $\lvert x_{i}\rvert\leq a_{ii}=1$. Since this holds for all $i\in[d]$,
$\lVert\vec{x}\rVert\leq 1$.

For the reverse direction, assume that $\langle c_{j}\rangle_{j=1}^{d}$ is not
a weak-alt-1 sequence, in which case we let $k\in[d]$ be the largest integer
such that the subsequence $\langle c_{j}\rangle_{j=k}^{d}$ is not weak-alt-1.
By the above expression of $\vec{x}$ we have

$\displaystyle\lVert\vec{x}\rVert_{\infty}$
$\displaystyle=\max_{i\in[d]}\lvert x_{i}\rvert$ (Def’n)
$\displaystyle\geq\lvert x_{k}\rvert$
$\displaystyle=\lvert\sum_{j=k}^{d}a_{kj}c_{j}\rvert$ (By expression of
$x_{k}$) $\displaystyle=\lvert c_{k}+\sum_{j=k+1}^{d}a_{kj}c_{j}\rvert$ ($A$
is reclusive, so $a_{kk}=1$)

If $\lvert c_{d}\rvert>1$ then $\langle c_{j}\rangle_{j=d}^{d}$ is not weak-
alt-1, so $k=d$. Then the the above summation is empty, so this shows
$\lVert\vec{x}\rVert_{\infty}\geq\lvert c_{d}\rvert>1$ and we are done in this
case. Otherwise we may assume $\lvert c_{d}\rvert\leq 1$; further, since
$\vec{c}\in\mathbb{Z}^{d}$ this means $c_{d}$ is $-1$, $0$, or $1$ and thus
$\langle c_{j}\rangle_{j=d}^{d}$ is trivially weak-alt-1 which implies
$k\not=d$. Then the sequence $\langle c_{j}\rangle_{j=k+1}^{d}$ is non-empty
(because $k\not=d$) and is weak-alt-1 (by design of $k$) and contains at least
one non-zero term (because otherwise it would be trivially weak-alt-1)—let $n$
denote the number of non-zero terms. Let $\langle j_{i}\rangle_{i=1}^{n}$ be
the sequence of non-zero terms of $\langle c_{j}\rangle_{j=k+1}^{d}$. Then
$\langle c_{j_{i}}\rangle_{i=1}^{n}$ is an alt-1 sequence, and $\langle
a_{kj_{i}}\rangle_{i=1}^{n}$ is a strictly decreasing sequence (since it is a
subsequence of $\langle a_{kj}\rangle_{j=k+1}^{d}$ which is strictly
decreasing because $A$ is reclusive). Thus, :alt-1-sums applies to
$s=\sum_{j=k+1}^{d}a_{kj}c_{j}=\sum_{i=1}^{n}a_{kj_{i}}c_{j_{i}}$ (with
different cases if $n=1$ or $n\geq 2$). We complete the proof with cases on
the magnitude of $c_{k}$ (and handle the subcases of the value of $n$ as
needed).

Recall that $c_{k}\in\mathbb{Z}$ and note that $\lvert c_{k}\rvert\not=0$
because $\langle c_{j}\rangle_{j=k+1}^{d}$ is weak-alt-1, so if $c_{k}=0$,
then $\langle c_{j}\rangle_{j=k}^{d}$ would be weak-alt-1, but it is not by
choice of $k$. So we consider two cases: $\lvert c_{k}\rvert=1$ and $\lvert
c_{k}\rvert\geq 2$.

Case 1: If $\lvert c_{k}\rvert\geq 2$, then by :alt-1-sums $\lvert s\rvert\leq
a_{kj_{1}}$ (regardless of the value of $n$). This gives the following
inequalities:

$\displaystyle\lVert\vec{x}\rVert_{\infty}$ $\displaystyle\geq\lvert
c_{k}+s\rvert$ (Work above) $\displaystyle\geq\lvert c_{k}\rvert-\lvert
s\rvert$ (Triangle inequality) $\displaystyle\geq 2-\lvert s\rvert$
(Assumption on $\lvert c_{k}\rvert$) $\displaystyle\geq 2-a_{kj_{1}}$
(:alt-1-sums) $\displaystyle=1+(1-a_{kj_{1}})$ $\displaystyle>1$ ($j_{1}\geq
k+1$ so $a_{kj_{1}}<1$)

Case 2: If $\lvert c_{k}\rvert=1$, then because $\langle
c_{j}\rangle_{j=k}^{d}$ is not weak-alt-1, it implies that
$\operatorname{sign}(c_{k})=\operatorname{sign}(c_{j_{1}})$. We then get the
following inequalities:

$\displaystyle\lVert\vec{x}\rVert_{\infty}$ $\displaystyle\geq\lvert
c_{k}+s\rvert$ (Work above) $\displaystyle=\lvert c_{k}\rvert+\lvert s\rvert$
(Same sign) $\displaystyle=1+\lvert s\rvert$ (Assumption on $\lvert
c_{k}\rvert$)

From here we have two cases depending on if $n=1$ or $n\geq 2$. If $n=1$, then
by :alt-1-sums $\lvert s\rvert=a_{kj_{1}}$, so from the above we have

$\displaystyle\lVert\vec{x}\rVert_{\infty}$ $\displaystyle\geq 1+a_{kj_{1}}$
$\displaystyle>1$ ($j_{1}\geq k+1$ so $a_{kj_{1}}>0$)

If instead $n\geq 2$, then by :alt-1-sums $\lvert s\rvert\geq
a_{kj_{1}}-a_{kj_{2}}$, so from the above we have

$\displaystyle\lVert\vec{x}\rVert_{\infty}$ $\displaystyle\geq
1+(a_{kj_{1}}-a_{kj_{2}})$ $\displaystyle>1$ ($j_{2}>j_{1}\geq k+1$ so
$a_{kj_{1}}-a_{kj_{2}}>0$)

∎

Upon inspection, one may note that we can improve upon the statement of the
prior proposition. In the proof above, if $\vec{c}$ was not a weak-alt-1
sequence, then not only was $\lVert A\vec{c}\rVert_{\infty}>1$, but it could
be bounded away from $1$. This should not be surprising since
$\left\\{A\vec{v}\colon\vec{v}\in\mathbb{Z}^{d}\right\\}$ is isomorphic to
$\mathbb{Z}^{d}$ (as stated in the discussion of :lattice-group).
Specifically, if $\vec{c}$ was not weak-alt-1, the above proof showed that one
of the following four equations held:

$\displaystyle\lVert A\vec{c}\rVert_{\infty}$ $\displaystyle\geq 1+1$ ($\lvert
c_{d}\rvert>1$) $\displaystyle\lVert A\vec{c}\rVert_{\infty}$
$\displaystyle\geq 1+(1-a_{kj_{1}})$ ($\lvert c_{d}\rvert\leq 1$ and $\lvert
c_{k}\rvert\geq 2$) $\displaystyle\lVert A\vec{c}\rVert_{\infty}$
$\displaystyle\geq 1+(a_{kj_{1}})$ ($\lvert c_{d}\rvert\leq 1$ and $\lvert
c_{k}\rvert=1$ and $n=1$) $\displaystyle\lVert A\vec{c}\rVert_{\infty}$
$\displaystyle\geq 1+(a_{kj_{1}}-a_{kj_{2}})$ ($\lvert c_{d}\rvert\leq 1$ and
$\lvert c_{k}\rvert=1$ and $n\geq 2$)

If we ignore the specifics of how $k$, $j_{1}$, and $j_{2}$ were found, and
minimize over all possibilities, it leads to the following definition and
corollary.

######  Definition 7.12 (Reclusive Distance).

If $A$ is a $d\times d$ reclusive matrix, define $\Delta_{A}$, the reclusive
distance of $A$, as follows (taking $\min\emptyset=\infty$)

$\displaystyle\delta_{1}$ $\displaystyle\operatorname{\overset{def}{=}}1$
$\displaystyle\delta_{2}$
$\displaystyle\operatorname{\overset{def}{=}}\min_{k\in[d]}\min_{k<j\leq
d}(1-a_{kj})$ $\displaystyle\delta_{3}$
$\displaystyle\operatorname{\overset{def}{=}}\min_{k\in[d]}\min_{k<j\leq
d}(a_{kj})$ $\displaystyle\delta_{4}$
$\displaystyle\operatorname{\overset{def}{=}}\min_{k\in[d]}\min_{k<j<j^{\prime}\leq
d}(a_{kj}-a_{kj^{\prime}})$ $\displaystyle\Delta_{A}$
$\displaystyle\operatorname{\overset{def}{=}}\min\left\\{\delta_{1},\delta_{2},\delta_{3},\delta_{4}\right\\}$

Observe that because $A$ is reclusive, $\Delta_{A}>0$.

######  Corollary 7.13.

Let $A$ be a $d\times d$ reclusive matrix and $\vec{c}\in\mathbb{Z}^{d}$
(emphasis: $\vec{c}$ has integer coordinates). Then $\lVert
A\vec{c}\rVert_{\infty}\leq 1$ if and only if $\vec{c}=\langle
c_{j}\rangle_{j=1}^{d}$ is a weak-alt-1 sequence. Further, if $\lVert
A\vec{c}\rVert_{\infty}>1$, then $\lVert A\vec{c}\rVert_{\infty}\geq
1+\Delta_{A}$.

###### Proof.

The proof is implicit in the proof of :adj-norm-equiv. ∎

A simple application of this corollary shows that if $X$ and $Y$ are non-
adjacent hypercubes in a reclusive partition, then the distance between the
representatives of the two hypercubes are separated by one plus the reclusive
distance of the partition.

######  Lemma 7.14 (Adjacent or Far Lemma (Representatives)).

Let $d\in\mathbb{N}$, and $A$ be a $d\times d$ reclusive matrix, and
$\mathcal{P}_{A}$ its reclusive partition, and $\Delta_{A}$ its reclusive
distance. Let $X,Y\in\mathcal{P}_{A}$ such that $X$ and $Y$ are not adjacent.
Then $d_{max}(\operatorname{rep}(X),\operatorname{rep}{Y})\geq 1+\Delta_{A}$.

###### Proof.

By definition of $\mathcal{P}_{A}$, there exists
$\vec{m},\vec{n}\in\mathbb{Z}^{d}$ such that $A\vec{m}=\operatorname{rep}(X)$
and $A\vec{n}=\operatorname{rep}(Y)$ (in particular
$\vec{m}=A^{-1}\operatorname{rep}(X)$ and
$\vec{n}=A^{-1}\operatorname{rep}(Y)$). By :equiv-defn-adjacency, because $X$
and $Y$ are not adjacent,
$d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))>1$, so

$\displaystyle 1$
$\displaystyle<d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))$
$\displaystyle=\lVert\operatorname{rep}(X)-\operatorname{rep}(Y)\rVert_{\infty}$
$\displaystyle=\lVert A\vec{m}-A\vec{n}\rVert_{\infty}$ $\displaystyle=\lVert
A(\vec{m}-\vec{n})\rVert_{\infty}.$

By :reclusive-dist-cor, since $\lVert A(\vec{m}-\vec{n})\rVert>1$ it must be
that $\lVert A(\vec{m}-\vec{n})\rVert\geq 1+\Delta_{A}$. ∎

A similar result holds when considering general elements $\vec{x},\vec{y}$ of
non-adjacent hypercubes $X$ and $Y$. We can get this result because the
location of $\vec{x}$ relative to $\operatorname{rep}(X)$ is similar to the
location of $\vec{y}$ relative to $\operatorname{rep}(Y)$.

######  Lemma 7.15 (Adjacent or Far Lemma (Points)).

Let $d\in\mathbb{N}$, and $A$ be a $d\times d$ reclusive matrix, and
$\mathcal{P}_{A}$ its reclusive partition, and $\Delta_{A}$ its reclusive
distance. Let $X,Y\in\mathcal{P}_{A}$ such that $X$ and $Y$ are not adjacent.
For all $\vec{x}\in X$ and $\vec{y}\in Y$, it holds that
$d_{max}(\vec{x},\vec{y})>\Delta_{A}$.

###### Proof.

By the definition of unit hypercubes,
$\vec{x}\in\operatorname{rep}(X)+[0,1)^{d}$, so let $\vec{\alpha}\in[0,1)^{d}$
such that $\vec{x}=\operatorname{rep}(X)+\vec{\alpha}$. Similarly, let
$\vec{\beta}\in[0,1)^{d}$ such that
$\vec{y}=\operatorname{rep}(Y)+\vec{\beta}$. As in the proof of the prior
lemma, let $\vec{m}=A^{-1}\operatorname{rep}(X)$ and
$\vec{n}=A^{-1}\operatorname{rep}(Y)$.

Since $\vec{\alpha},\vec{\beta}\in[0,1)^{d}$, it follows that
$\vec{\beta}-\vec{\alpha}\in(-1,1)^{d}$ so
$\lVert\vec{\beta}-\vec{\alpha}\rVert_{\infty}<1$. Then we have the following:

$\displaystyle d_{max}(\vec{x},\vec{y})$
$\displaystyle=\lVert\vec{x}-\vec{y}\rVert_{\infty}$
$\displaystyle=\lVert(A\vec{m}+\vec{\alpha})-(A\vec{n}+\vec{\beta})\rVert_{\infty}$
$\displaystyle=\lVert(A(\vec{m}+\vec{n}))-(\vec{\beta}-\vec{\alpha})\rVert_{\infty}$
$\displaystyle\geq\lVert(A(\vec{m}+\vec{n}))\rVert_{\infty}-\lVert\vec{\beta}-\vec{\alpha}\rVert_{\infty}$
(Triangle inequality)
$\displaystyle\geq(1+\Delta_{A})-\lVert(\vec{\beta}-\vec{\alpha})\rVert_{\infty}$
(By previous lemma) $\displaystyle>(1+\Delta_{A})-1$
($\lVert\vec{\beta}-\vec{\alpha}\rVert_{\infty}<1$) $\displaystyle=\Delta_{A}$

Noting the strict inequality in the second to last line completes the proof. ∎

This lemma will be important later when we need a fixed bound on the distances
between non-adjacent partition members.

Now that we have given a bound on how close non-adjacent hypercubes can be, we
want to turn our attention to how many hypercubes can be pairwise adjacent. In
other words, we want to show a bound on the size of the largest clique in the
partition graph of a reclusive partition. We actually do something stronger
and give an explicit coloring of the graph (an explicit coloring of the
hypercubes). If a graph can be properly colored with $n$ colors, then the size
of the largest clique in the graph is at most $n$.

######  Theorem 7.16 (Coloring Reclusive Partitions).

Let $d\in\mathbb{N}$ and let $A$ be a $d\times d$ reclusive matrix. The graph
of the reclusive partition $\mathcal{P}_{A}$ can be properly $(d+1)$-colored.

###### Proof.

Let $\chi=\left[1,2,\ldots,d\right]$ be a $1\times d$ matrix. Define the
coloring function on the hypercubes as follows:

$\displaystyle\operatorname{color}:\mathcal{P}_{A}\to\mathbb{Z}_{d+1}$
$\displaystyle\operatorname{color}(X)=\chi\;A^{-1}\;\operatorname{rep}(X)\mod(d+1).$

Recall that if $X\in\mathcal{P}_{A}$, then $\operatorname{rep}(X)=A\vec{m}$
for some $\vec{m}\in\mathbb{Z}^{d}$ (by definition of the reclusive partition
$\mathcal{P}_{A}$), and $\vec{m}$ is unique because $A$ is invertible, so the
definition of $\operatorname{color}$ has an appropriate codomain because
$(A^{-1}(A\vec{m}))=\vec{m}\in\mathbb{Z}^{d}$, and taken as a column vector it
can be multiplied with $\chi$ to obtain an integer.

Let $X$ and $Y$ be distinct hypercubes in $\mathcal{P}_{A}$ such that
$X\operatorname{\overset{adj}{\sim}}Y$. We must show that
$\operatorname{color}(X)\not=\operatorname{color}(Y)$. We do so by looking at
the differences of the colors (and explicitly emphasize that it is being done
$\mod(d+1)$). Let $\vec{m}=A^{-1}\operatorname{rep}(X)$ and
$\vec{n}=A^{-1}\operatorname{rep}(Y)$.

$\displaystyle\operatorname{color}(X)-\operatorname{color}(Y)\mod(d+1)$
$\displaystyle=\big{[}(\chi\vec{m}\mod(d+1))-(\chi\vec{n}\mod(d+1))\big{]}\mod(d+1)$
(definition) $\displaystyle=\big{[}\chi\vec{m}-\chi\vec{n}\big{]}\mod(d+1)$
(property of modular arithmetic)
$\displaystyle=\big{[}\chi(\vec{m}-\vec{n})\big{]}\mod(d+1)$ (linearity of
$\chi$)

Observe that by :adj-norm-equiv, because
$X\operatorname{\overset{adj}{\sim}}Y$ it follows that $(\vec{m}-\vec{n})$ is
a weak-alt-1 sequence/vector. Further, $(\vec{m}-\vec{n})$ has at least one
non-zero term (if it did not, then $\vec{m}=\vec{n}$ so
$\operatorname{rep}(X)=\operatorname{rep}(Y)$ but we assumed $X$ and $Y$ were
distinct). Note also that the matrix product of $\chi$ with
$(\vec{m}-\vec{n})$ is really a dot product of the increasing positive
sequence $\langle 1,2,\ldots,d\rangle$ with a weak-alt-1 sequence with a non-
zero term. Thus, by :alt-1-sums (applied to the (non-empty) subsequence of
non-zero terms), we have

$0<\lvert\chi(\vec{m}-\vec{n})\rvert\leq d.$

Thus, $\chi(\vec{m}-\vec{n})\mod(d+1)\not=0$ which proves that
$\operatorname{color}(X)\not=\operatorname{color}(Y)$, so this is a proper
coloring. ∎

In fact, the coloring above is tight—the chromatic number (the smallest number
of colors that can be used to color the graph) is $d+1$. To prove this, it
suffices to show that $\mathcal{P}_{A}$ has a $(d+1)$-clique.

The following result actually follows as a corollary to the Optimality Theorem
for Unit Hypercube Partitions (:hypercube-partition-thm), so the following
proof is not strictly necessary; however, :hypercube-partition-thm uses far
more machinery, and it is fairly simple to find an explicit clique in the
partition.

######  Proposition 7.17 (Chromatic Number).

Let $d\in\mathbb{N}$, and $A$ be a $d\times d$ reclusive matrix, and
$\mathcal{P}_{A}$ its reclusive partition. There exists a clique in
$\mathcal{P}_{A}$ of size $d+1$.

###### Proof.

For each $i\in[d]$, let $\vec{e_{i}}\in\mathbb{Z}^{d}$ denote the $i$th
standard basis vector (i.e. all zeros except for the $i$th term which is $1$).
Let $V=\left\\{\vec{0}\right\\}\cup\left\\{\vec{e_{i}}\colon
i\in[d]\right\\}$. Note that for any two vectors $\vec{v},\vec{w}\in V$, that
$\vec{v}-\vec{w}$ is a weak-alt-1 vector. This is obvious if one of the
vectors is $\vec{0}$ because then the difference is a standard basis vector
which is all zeros except for a single term which is $1$, so it is weak-alt-1.
Otherwise, $\vec{v}=\vec{e_{i}}$ and $\vec{w}=\vec{e_{j}}$ for some
$i,j\in[d]$. If $i=j$, then the difference is $\vec{0}$ which is trivially
weak-alt-1, and if $i\not=j$, then the difference is all zeros except for a
term which is $+1$ and a term which is $-1$; such a vector must be a weak-
alt-1 sequence.

Let $R=\left\\{A\vec{v}\colon\vec{v}\in V\right\\}$ denote a set of
representatives, and let
$C=\left\\{X\in\mathcal{P}_{A}\colon\operatorname{rep}(X)\in R\right\\}$ be
the set of unit hypercubes in $\mathcal{P}_{A}$ whose representatives are in
$R$. Then $C$ (and $V$) have cardinality $d+1$, and we claim that $C$ is a
clique.

Consider hypercubes $X,Y\in C$, so
$\operatorname{rep}(X),\operatorname{rep}(Y)\in R$, so
$A^{-1}\operatorname{rep}(X),A^{-1}\operatorname{rep}(Y)\in V$. Let
$\vec{m}=A^{-1}\operatorname{rep}(X)$ and
$\vec{n}=A^{-1}\operatorname{rep}(Y)$. As described, since $\vec{m},\vec{n}\in
V$, we have that $\vec{m}-\vec{n}$ is a weak-alt-1 sequence. By :adj-norm-
equiv this implies that $\lVert A(\vec{m}-\vec{n})\rVert_{\infty}\leq 1$.
Thus,

$\displaystyle d_{max}(\operatorname{rep}(X),\operatorname{rep}(Y))$
$\displaystyle=\lVert\operatorname{rep}(X)-\operatorname{rep}(Y)\rVert_{\infty}$
$\displaystyle=\lVert A(\vec{m}-\vec{n})\rVert_{\infty}$ $\displaystyle\leq 1$

and by :equiv-defn-adjacency, $X$ and $Y$ are adjacent. Since this holds for
any two hypercubes in $C$, it must be that $C$ is a $(d+1)$-clique. ∎

The following theorem is the main result of this section showing that we have
constructed partitions satisfying the motivating question with $k=d+1$ and
$\epsilon=\frac{\Delta_{A}}{2}$. Then the Hypercube Parition Theorem
(:hypercube-partition-thm) mentioned in sec:results will be a simple corollary
of this by demonstrating the existence of a reclusive partition with
$\Delta_{A}=\frac{1}{d}$.

######  Theorem 7.18 (Partition Theorem).

Let $d\in\mathbb{N}$, and $A$ be a $d\times d$ reclusive matrix, and
$\mathcal{P}_{A}$ its reclusive partition, and $\Delta_{A}$ its reclusive
distance. Then for any $\vec{p}\in\mathbb{R}^{d}$,

$\lvert\mathcal{N}_{\Delta_{A}/2}(\vec{p})\rvert\leq d+1.$

###### Proof.

It suffices to prove that $\mathcal{N}_{\Delta_{A}/2}(\vec{p})$ is a clique
since by :coloring, any clique contains at most $d+1$ hypercubes. Let
$X,Y\in\mathcal{N}_{\Delta_{A}/2}(\vec{p})$ be arbitrary. By definition of
$\mathcal{N}_{\Delta_{A}/2}(\vec{p})$, there exists $\vec{x}\in X$ such that
$d_{max}(\vec{p},\vec{x})\leq\frac{\Delta_{A}}{2}$ and similarly there exists
$\vec{y}\in Y$ such that $d_{max}(\vec{p},\vec{y})\leq\frac{\Delta_{A}}{2}$.
By the triangle inequality of metrics,

$d_{max}(\vec{x},\vec{y})\leq
d_{max}(\vec{p},\vec{x})+d_{max}(\vec{p},\vec{y})\leq\frac{\Delta_{A}}{2}+\frac{\Delta_{A}}{2}=\Delta_{A}$

By the contrapositive of the Adjacent or Far Lemma (:adjacent-or-far), since
there exists $\vec{x}\in X$ and $\vec{y}\in Y$ such that
$d_{max}(\vec{x},\vec{y})\leq\Delta_{A}$, it must be that $X$ and $Y$ are
adjacent. ∎

In order to state the Hypercube Parition Theorem (:hypercube-partition-thm) as
promised, we first need a simple lemma. To motivate the following choice,
consider again the definition of reclusive distance (:reclusive-dist-def) and
the discussion leading up to it. To make the most of the Partition Theorem, we
want to have a large reclusive distance, and that is accomplished by keeping
three key quantities in a reclusive matrix large—for each row $k$ and
arbitrary entries $j<j^{\prime}$ within that row, we want the following to be
large: $(1-a_{kj})$, $(a_{kj})$, and $(a_{kj}-a_{kj^{\prime}})$. The first
discourages using matrix entries greater than $1$ (which is partially why
reclusive matrices were defined to not allow that) and encourages using small
entries; the second encourages using large entries; the third seems to
encourage “even spacing” of the terms in a given row.

Based on these considerations, we make all entries in the matrix multiples of
a common denominator.

######  Lemma 7.19.

Let $d\in\mathbb{N}$, and $A$ be a $d\times d$ reclusive matrix, and
$\Delta_{A}$ its reclusive distance. If for all $i,j\in[d]$ it holds that
$a_{ij}$ is a multiple of $\frac{1}{k}$ (including $0$), then
$\Delta_{A}\geq\frac{1}{k}$. Further, such reclusive matrices exist for $k\geq
d$.

###### Proof.

The first claim follows from the definitions of reclusive matrix and reclusive
distance. For the second claim, let $k\geq d$ and consider the $d\times d$
reclusive matrix $A$ which has $1$’s on the main diagonal and $0$’s in the
lower triangle (as required for all reclusive matrices) and for any other
entry, $a_{ij}=\frac{d-i+1}{k}$.

$A=\left[\begin{array}[]{ccccccc}1&\frac{d-1}{k}&\frac{d-2}{k}&\frac{d-3}{k}&\cdots&\frac{2}{k}&\frac{1}{k}\\\
0&1&\frac{d-2}{k}&\frac{d-3}{k}&\cdots&\frac{2}{k}&\frac{1}{k}\\\
0&0&1&\frac{d-3}{k}&\cdots&\frac{2}{k}&\frac{1}{k}\\\
0&0&0&1&\cdots&\frac{2}{k}&\frac{1}{k}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&1&\frac{1}{k}\\\ 0&0&0&0&\cdots&0&1\end{array}\right]$

It is easily verified that this is in fact a reclusive matrix. ∎

We shall be particularly interested in reclusive $d\times d$ matrices $A$ as
in the lemma with $k=d$ in which case the lemma says that
$\Delta_{A}\geq\frac{1}{d}$, and by examination of the first row
$\Delta_{A}\leq\frac{1}{d}$ giving equality.

###### Proof.

As just discussed, there exists a reclusive partition $\mathcal{P}_{A}$ with
with reclusive distance $\Delta_{A}=\frac{1}{d}$, so the conclusion follows
from :partition-thm. ∎

##  8 Fundamental Property of the Reclusive Definition

It would be a fair question for one to ask, “Why bother developing this
general notion of reclusive partitions if you end up only using one specific
example?” The initial reason for why we defined reclusive partitions is that
we found ourselves looking to generalize the example of exponentially decaying
shifts that we presented at the beginning of the section in order to move from
$\epsilon$ with the denominator growing exponentially to $\epsilon$ with the
denominator growing linearly. The generalization followed by noting the
properties in Subsection 7.2.

Initially, we expected this to be a much stronger generalization than we
needed and expected that the order in which the shifts were applied would not
really matter. However, as we will demonstrate in this subsection, we were
incorrect, and the definition of a reclusive matrix really seems to capture
something that seems fundamental to the properties we are interested
in—particularly the property of considering partitions with minimal possible
clique sizes.

Consider, for example, the following two reclusive matrices $A^{\prime}$ and
$A^{\prime\prime}$ (the shorthand notation denotes the value only of entries
in the strict upper diagonal since the diagonal must be $1$’s and the
subdiagonal must be $0$’s).

$A^{\prime}=\left(\frac{d-j+1}{d}\right)=\left[\begin{array}[]{ccccccc}1&\frac{d-1}{d}&\frac{d-2}{d}&\frac{d-3}{d}&\cdots&\frac{2}{d}&\frac{1}{d}\\\
0&1&\frac{d-2}{d}&\frac{d-3}{d}&\cdots&\frac{2}{d}&\frac{1}{d}\\\
0&0&1&\frac{d-3}{d}&\cdots&\frac{2}{d}&\frac{1}{d}\\\
0&0&0&1&\cdots&\frac{2}{d}&\frac{1}{d}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&1&\frac{1}{d}\\\
0&0&0&0&\cdots&0&1\end{array}\right]\qquad\text{Example,
$d=5$:}\left[\begin{array}[]{ccccccc}1&\frac{4}{5}&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\
0&1&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\ 0&0&1&\frac{2}{5}&\frac{1}{5}\\\
0&0&0&1&\frac{1}{5}\\\ 0&0&0&0&1\end{array}\right]$
$A^{\prime\prime}=\left(\frac{d-j+1}{d-i+1}\right)=\left[\begin{array}[]{ccccccc}1&\frac{d-1}{d}&\frac{d-2}{d}&\frac{d-3}{d}&\cdots&\frac{2}{d}&\frac{1}{d}\\\
0&1&\frac{d-2}{d-1}&\frac{d-3}{d-1}&\cdots&\frac{2}{d-1}&\frac{1}{d-1}\\\
0&0&1&\frac{d-3}{d-2}&\cdots&\frac{2}{d-2}&\frac{1}{d-2}\\\
0&0&0&1&\cdots&\frac{2}{d-3}&\frac{1}{d-3}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&1&\frac{1}{2}\\\
0&0&0&0&\cdots&0&1\end{array}\right]\qquad\text{Example,
$d=5$:}\left[\begin{array}[]{ccccccc}1&\frac{4}{5}&\frac{3}{5}&\frac{2}{5}&\frac{1}{5}\\\
0&1&\frac{3}{4}&\frac{2}{4}&\frac{1}{4}\\\ 0&0&1&\frac{2}{3}&\frac{1}{3}\\\
0&0&0&1&\frac{1}{2}\\\ 0&0&0&0&1\end{array}\right]$

Then consider the matrices $B^{\prime}$ and $B^{\prime\prime}$.

$B^{\prime}=\left(\frac{j-1}{d}\right)=\left[\begin{array}[]{ccccccc}1&\frac{1}{d}&\frac{2}{d}&\frac{3}{d}&\cdots&\frac{d-2}{d}&\frac{d-1}{d}\\\
0&1&\frac{2}{d}&\frac{3}{d}&\cdots&\frac{d-2}{d}&\frac{d-1}{d}\\\
0&0&1&\frac{3}{d}&\cdots&\frac{d-2}{d}&\frac{d-1}{d}\\\
0&0&0&1&\cdots&\frac{d-2}{d}&\frac{d-1}{d}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&1&\frac{d-1}{d}\\\
0&0&0&0&\cdots&0&1\end{array}\right]\qquad\text{Example,
$d=5$:}\left[\begin{array}[]{ccccccc}1&\frac{1}{5}&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}\\\
0&1&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}\\\ 0&0&1&\frac{3}{5}&\frac{4}{5}\\\
0&0&0&1&\frac{4}{5}\\\ 0&0&0&0&1\end{array}\right]$

$B^{\prime\prime}=\left(\frac{i-j}{d-i+1}\right)=\left[\begin{array}[]{ccccccc}1&\frac{1}{d}&\frac{2}{d}&\frac{3}{d}&\cdots&\frac{d-2}{d}&\frac{d-1}{d}\\\
0&1&\frac{1}{d-1}&\frac{2}{d-1}&\cdots&\frac{d-3}{d-1}&\frac{d-2}{d-1}\\\
0&0&1&\frac{1}{d-2}&\cdots&\frac{d-4}{d-2}&\frac{d-3}{d-2}\\\
0&0&0&1&\cdots&\frac{d-5}{d-3}&\frac{d-4}{d-3}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&1&\frac{1}{2}\\\
0&0&0&0&\cdots&0&1\end{array}\right]\qquad\text{Example,
$d=5$:}\left[\begin{array}[]{ccccccc}1&\frac{1}{5}&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}\\\
0&1&\frac{1}{4}&\frac{2}{4}&\frac{3}{4}\\\ 0&0&1&\frac{1}{3}&\frac{2}{3}\\\
0&0&0&1&\frac{1}{2}\\\ 0&0&0&0&1\end{array}\right]$

Clearly $B^{\prime}$ and $B^{\prime\prime}$ are not reclusive
matrices141414Well, they are for $d=1$ and $d=2$, but not for any $d\geq 3$.
since the entries in the rows are not decreasing. Nonetheless, $B^{\prime}$
and $B^{\prime\prime}$ define partitions of $\mathbb{R}^{d}$ in the same
fashion as a reclusive matrix151515The partition is the set of all unit
hypercubes with representatives in the set
$\left\\{B^{\prime}\vec{v}\colon\vec{v}\in\mathbb{Z}^{d}\right\\}$ (resp.
$\left\\{B^{\prime\prime}\vec{v}\colon\vec{v}\in\mathbb{Z}^{d}\right\\}$)..
For example, the partition associated with $B^{\prime}$ in dimension $5$ is
the one constructed by partitioning $\mathbb{R}^{1}$ into unit intervals, then
extruding those intervals into unit squares in $\mathbb{R}^{2}$, copying the
extrusion to multiple layers, and shifting each layer by $1/5$ of a unit more
to the right than the previous layer; then extruding this partition of
$\mathbb{R}^{2}$ into $\mathbb{R}^{3}$ and shifting each layer by $2/5$ of a
unit more than the previous layer. In this sense, this partition is
constructed in a very similar way to the partition for $A^{\prime}$: layers
are still offset by multiples of $1/5$, and the only difference is that
smaller shifts happen first.

By Theorem 7.16, the partitions $\mathcal{P}_{A^{\prime}}$ and
$\mathcal{P}_{A^{\prime\prime}}$ do not contain any cliques of size $d+2$, so
a natural question is whether the partitions associated with $B^{\prime}$ and
$B^{\prime\prime}$ also have this property since their constructions are so
similar. Our intuition was that the answer to this question would “yes”, but
this is not the case. For $d\leq 4$, the partitions for both $B^{\prime}$ and
$B^{\prime\prime}$ do not have cliques of size $d+2$, but for $d=5$ they do.

We found this by exhaustive computer search161616Because of the repetitive
structure of the partition (since the underlying structure is a lattice), it
suffices to check a sufficiently large but finite subset of the partition for
cliques to determine the size of the largest clique in the whole partition.,
but our claim that for $d=5$, $B^{\prime}$ and $B^{\prime\prime}$ each have a
$d+2=7$ clique can easily be verified. Consider the following set of $7$
vectors in $\mathbb{Z}^{5}$:

$\left[\begin{array}[]{c}0\\\ 1\\\ -1\\\ 0\\\
1\end{array}\right],\left[\begin{array}[]{c}0\\\ 0\\\ -1\\\ 0\\\
1\end{array}\right],\left[\begin{array}[]{c}0\\\ 1\\\ 0\\\ 0\\\
0\end{array}\right],\left[\begin{array}[]{c}-1\\\ 1\\\ -1\\\ 0\\\
1\end{array}\right],\left[\begin{array}[]{c}-1\\\ 0\\\ 0\\\ 0\\\
1\end{array}\right],\left[\begin{array}[]{c}-1\\\ 0\\\ 0\\\ 1\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 0\\\ 0\\\ 1\\\
0\end{array}\right]$

Multiplying $B^{\prime}$ with each vector results in the representative corner
of the hypercubes associated with each vector (one can similarly compute them
for $B^{\prime\prime}$):

$\left[\begin{array}[]{c}3/5\\\ 7/5\\\ -1/5\\\ 4/5\\\
1\end{array}\right],\left[\begin{array}[]{c}2/5\\\ 2/5\\\ -1/5\\\ 4/5\\\
1\end{array}\right],\left[\begin{array}[]{c}1/5\\\ 1\\\ 0\\\ 0\\\
0\end{array}\right],\left[\begin{array}[]{c}-2/5\\\ 7/5\\\ -1/5\\\ 4/5\\\
1\end{array}\right],\left[\begin{array}[]{c}-1/5\\\ 4/5\\\ 4/5\\\ 4/5\\\
1\end{array}\right],\left[\begin{array}[]{c}-2/5\\\ 3/5\\\ 3/5\\\ 1\\\
0\end{array}\right],\left[\begin{array}[]{c}3/5\\\ 3/5\\\ 3/5\\\ 1\\\
0\end{array}\right]$

To see that the hypercubes with representative corners at these $7$ locations
form a clique, check that the $d_{max}$ distance between any pair is exactly
$1$ (and apply Corollary 6.8). By Proposition 6.9, and the discussion
preceeding it, this shows that this partition has points where any ball of any
radius centered at that point intersect all $7$ of these hypercubes.

It could be that there is some sufficiently large dimension $d$ such that
$B^{\prime}$ and $B^{\prime\prime}$ have cliques of size at most $d+1$, but we
conjecture that this is not the case.

######  Conjecture 8.1 (Maximum Clique Sizes in Non-Reclusive Partitions
$B^{\prime}$ and $B^{\prime\prime}$).

Based on our computations, we conjecture that the maximum clique size in the
partitions associated with $B^{\prime}$ and $B^{\prime\prime}$ is greater than
$d+1$ for all $d\geq 5$, and we know the maximum clique sizes for dimensions
given in Table 1.

d | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---
B’ | 2 | 3 | 4 | 5 | 7 | 9 | 12 | 16 | 22 | 30 | 39 | 51
B” | 2 | 3 | 4 | 5 | 7 | 9 | 11 | 16 | 21 | 28 | 36 | 47
Table 1: Maximum clique sizes in non-reclusive partitions $B^{\prime}$ and
$B^{\prime\prime}$ for various dimensions.

The above example demonstrates that our definition of reclusive partitions is
not an arbitrary one and captures a certain structure of lattice based
partitions that is sufficient to ensure that no large cliques exist. The key
is that because our definition of reclusive partitions demands that the terms
be decreasing in each row, we get an equivalent definition of adjacency in
terms of weak-alt-1 sequences. The above example shows that this equivalence
does not hold if we relax the decreasing requirement.

##  9 Optimality of the Degree Parameter ($k$)

Given our results that we can find a uniformly-sized neighborhood around every
point that intersects at most $d+1$ members of the partition, it is natural to
ask if this is optimal—can this value be improved from $d+1$ to $d$ or even
smaller? In other words, is there a partition of $\mathbb{R}^{d}$ and a
neighborhood around each point in $\mathbb{R}^{d}$ such that each of these
neighborhoods intersects at most $d$ members of the partition? The answer is
basically no; our partitions are optimal, and in this section we will discuss
the technicalities of what we mean by “basically” and then prove the
optimality formally.

It is obvious that this question above is only worth asking if some
restrictions are added, because otherwise the partition of $\mathbb{R}^{d}$
which contains just one member ($\mathcal{P}=\left\\{\mathbb{R}^{d}\right\\}$)
along with any neighborhoods trivially has the property that each neighborhood
intersects only one member of the partition (because there is only one). The
context above suggests that we are interested in partitions similar to tilings
and packings, and so we will restrict to the context in which the size of the
partition members is uniformly bounded in some way.

Two natural ways to bound the size of the members are by bounding the diameter
and by bounding the measure. Note that bounding the diameter is a strictly
stronger condition (assuming all members are measurable), because if we insist
that each member of the partition has diameter at most $D$ in the $d_{max}$
metric, then the measure of each member is at most $(2D)^{d}$ (fix some point
in the member, and all other points are within $D$ of it, so the member is
contained in a ball of radius $D$ in the $d_{max}$ metric, and this ball has
measure $(2D)^{d}$ because this ball is a $d$-dimensional hypercube with side
length $2D$).

Thus, if we can answer this question by just restricting the measure, that
would be ideal since it is a weaker hypothesis. Unfortunately, we will see
that we cannot get the strongest version of the conclusion that we want just
by bounding the measure, and so we will also consider diameter bounds. It will
occur frequently in our theorems, though, that to get nicely generalized
statements, diameter is not quite what we want. For example, consider the sets
$[0,1)$ and $[0,1]$. Both sets have diameter $1$, but the the former has the
stronger property that all pairs of points have distance strictly less than
the diameter. In other words, diameter171717In general
$\operatorname{diam}(X)\operatorname{\overset{def}{=}}\sup\left\\{\textrm{distance}(x,y):x,y\in
X\right\\}$ is defined as a supremum of distances, and the former set does not
attain the supremum while the latter does. We want to distinguish between
these cases, so we give the following definition.

######  Definition 9.1 (Strict Pairwise Bound).

If $X$ is a subset of a metric space and $D\in(0,\infty)$ is a constant such
that for all $x,y\in X$ it holds that $\mathrm{distance}(x,y)<D$, then we call
$D$ a strict pairwise bound of $X$.

######  Remark 9.2.

Unbounded sets do not have any strict pairwise bounds, and bounded sets have
infinitely many strict pairwise bounds (if $D$ is a strict pairwise bound,
then so is $D+\epsilon$ for any $\epsilon\in[0,\infty)$). Also, we have the
following implications:

$\operatorname{diam}(X)<D\quad\Longrightarrow\quad D\text{ is a strict
pairwise bound of }X\quad\Longrightarrow\quad\operatorname{diam}(X)\leq D$

In general, the reverse implications do not hold which is exemplified by the
sets $[0,D)$ and $[0,D]$.

Because of the distinction just mentioned between a strict bound on diameter,
a strict pairwise bound, and a nonstrict bound on diameter, we don’t want to
restrict to unit diameter partition members in this section as we did in the
last section, and instead will state many results for a general diameter (or
strict pairwise bound) $D\in(0,\infty)$. It is worth noting that all of the
results of the previous section used unit hypercubes, but if we allow for $D$
diameter hypercubes (i.e., translations of $[0,D)^{d}$) then the results also
scale so that we can still attain the parameter $k=d+1$ and
$\epsilon=\frac{D}{2d}$.

In this section, we will prove the three different Optimality Theorems
presented in sec:results. We begin with a more in depth discussion (and
restatement) of these theorems and some of the corollaries that will follow.