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.