Suppose is a bounded metric space in which we want to find
points at safe distance
from one other:
for all
. Let
be the greatest value of
for which this is possible (technically, the supremum which might not be attained). We have
.
The sequence tends to zero if and only if
is totally bounded. From now on, consider a specific metric space which is bounded but not totally bounded: the space
of all measurable subsets of
with the metric
, the measure of the symmetric difference. More specifically, the elements of
are equivalence classes of sets that differ by a null subset. Another way to think of it is the subset of
which consists of functions that attain only the values
and
. In this form we identify a set
with its characteristic function
. The measure space
could be replaced by any isomorphic probability space, of which there are many.
The space contains an infinite subset
with
separation: namely, let
be the set of all numbers
such that the fractional part of
is less than
; or equivalently, the
th binary digit of
is zero. Each symmetric difference
has measure exactly
. Therefore,
for every
.
Upper bound for distances
To get an upper bound for , suppose
are
-separated. Let
be the characteristic function of
. By assumption,
whenever
. Summing over all such pairs
shows that
. Fix a point
and let
be the number of sets among
that contain
. An easy counting argument shows
. The latter quantity is bounded by
where
. Since this bound holds for every
, it follows that
, which simplifies to
, where
.
For example, ,
,
, and so on. Are these estimates sharp? For an affirmative answer it would be enough to demonstrate that
by finding a suitable collection of
subsets. Note that sharpness requires that almost every point of
be covered by exactly
of these subsets, and that all pairwise distances between sets must be equal to
.
Sharpness of the upper bound
Four subsets with separation are easy to find:
,
,
, and
. Thus,
.
To find six subsets with separation, some preparation is helpful.
For any set , the map
is an isometry of
onto
. So, there is no loss of generality in assuming that one of our
sets is
. Then we are to find
of measure
. In order to have the specified distances, the measure of intersection of any two sets must be
.
For example, if , the above says we need three disjoint sets of measure
, which is a trivial thing to find. For
the sets will no longer be disjoint.
Discretization of the problem
A natural way to proceed is to partition into
equal subintervals (or other sets of equal measure). Then we look for
sets, each of which consists of
subintervals. Their pairwise intersections must consist of
subintervals.
The case was done above. If
, we want to use
subintervals to form
sets with
subintervals in each. Pairwise intersections must consist of precisely
subinterval. Encoding subintervals by their indices 0-9, we can describe such sets as 0123, 3456, 6780, 1479, 2589. And since 10 is a triangular number, there is a neat illustration of these five sets: three sides of the triangle, and two “stars” connecting its center to the sides.

There is no need to translate this back into sets formed by subintervals: as long as the combinatorial problem has a solution, we have the desired conclusion. In this case, the conclusion is .
Next up, . Following the above method, we partition
into
equal subintervals and look for
sets, each of which consists of
subintervals. Pairwise intersections must consist of
subintervals each. Can this be done?
Think of a cube. It has vertices and
faces, and
. In the set {faces and vertices}, we choose
subsets of cardinality
as follows:
- {face, all its vertices, and the opposite face}. There are 6 such sets. Any two of them have exactly 2 elements in common.
- {all faces} is our 7th set, it has 2 elements in common with each of the above.
Thus, . But it is concerning that
and
required different combinatorial constructions. What happens next?
For , we partition
into
equal subintervals and look for
sets, with
subintervals in each. Pairwise intersections must consist of
subintervals. I don’t see any neat construction here.
Summary so far
The results obtained so far for can be summarized as follows: there exists a 0-1 matrix
of size
in which the dot product of two rows is
when the rows are distinct and
otherwise. Specifically,
The matrix is best written in block form
according to the faces-vertices interpretation. Here
and
Does exist? Perhaps not.
Combinatorics of finite sets
In combinatorial terms, we are looking for a -uniform
-intersecting family of
subsets of
, with specific values
,
,
,
.
Explanation of terms: , being
-uniform means every set has
elements, and being
-intersecting means all pairwise intersections have
elements.
Thus began my fishing expedition into the literature on combinatorics of finite sets. Surprisingly, it ended with a pivot back to where it started: measurable subsets of an interval.
Fractional intersecting uniform families
A recent (2018) preprint Uniform sets in a family with restricted intersections (Yandong Bai, Binlong Li, Jiuqiang Liu, Shenggui Zhang) relates the combinatorial problem back to subsets of an interval. I quote the relevant result (Theorem 2.5) with slight changes of notation.
Let be the real interval and let
be the Lebesgue measure on
. If
is a family of subsets of
such that
for all
, and
for all distinct
,
then we call a fractional
-intersecting
-uniform
-family of
. For given real numbers
and integer
, let
be the largest real number
such that there exists a fractional
-intersecting
-uniform
-family of
.
Theorem 2.5 Let be two real numbers and let
be an integer. Then
where ,
and is the solution of the system
.
This looks complicated, but with our values ,
,
both
and
turn out to be equal to
. This is an exceptional case when the linear system is degenerate: it amounts to
. The final result is
as we wanted. Yay.
So, the upper bounds for distances are indeed sharp, meaning that subsets of the unit interval can be separated by measure-distance of
, where
. But dividing the intervals into
equal parts may not be enough to construct such subsets: in general one has to use a larger number of parts, some integer multiple of
.
The authors remark that if are integers, then a partition with
exists in the combinatorial realm of
. However, this is not “if and only if”. Indeed,
which takes integer values when
, and is fractional (less than 1) when
. But we do have a combinatorial solution when
. So it is not quite clear for what values of
there exists a
-uniform
-intersecting family of
subsets of
. Perhaps an answer could be found by following the construction for this specific case, when the formulas magically simplify.