## Measure-distanced subsets of an interval

Suppose ${(X, d)}$ is a bounded metric space in which we want to find ${n}$ points at safe distance ${\delta}$ from one other: ${d(x_j, x_k)\ge \delta}$ for all ${j\ne k}$. Let ${\delta_n}$ be the greatest value of ${\delta}$ for which this is possible (technically, the supremum which might not be attained). We have ${\mathrm{diam}\,(X) = \delta_2 \ge \delta_3\ge \cdots}$.

The sequence ${\delta_n}$ tends to zero if and only if ${X}$ is totally bounded. From now on, consider a specific metric space which is bounded but not totally bounded: the space ${X}$ of all measurable subsets of ${[0, 1]}$ with the metric ${d(A, B)=|A\triangle B|}$, the measure of the symmetric difference. More specifically, the elements of ${X}$ are equivalence classes of sets that differ by a null subset. Another way to think of it is the subset of ${L^1([0, 1])}$ which consists of functions that attain only the values ${0}$ and ${1}$. In this form we identify a set ${A}$ with its characteristic function ${\chi_A}$. The measure space ${[0, 1]}$ could be replaced by any isomorphic probability space, of which there are many.

The space ${X}$ contains an infinite subset ${\{E_1, E_2, \dots \}}$ with ${\delta=1/2}$ separation: namely, let ${E_k}$ be the set of all numbers ${x\in [0, 1]}$ such that the fractional part of ${2^k x}$ is less than ${1/2}$; or equivalently, the ${k}$th binary digit of ${x}$ is zero. Each symmetric difference ${E_j\triangle E_k}$ has measure exactly ${1/2}$. Therefore, ${\delta_n\ge 1/2}$ for every ${n}$.

## Upper bound for distances

To get an upper bound for ${\delta_n}$, suppose ${\{E_1, \dots, E_n\}}$ are ${\delta}$-separated. Let ${\chi_k}$ be the characteristic function of ${E_k}$. By assumption, ${\int_0^1 |\chi_k-\chi_j|\ge \delta}$ whenever ${1\le k < j \le n}$. Summing over all such pairs ${(k, j)}$ shows that ${\int_0^1 \sum_{k. Fix a point ${x\in [0, 1]}$ and let ${p}$ be the number of sets among ${E_1, \dots, E_n}$ that contain ${x}$. An easy counting argument shows ${\sum_{k. The latter quantity is bounded by ${r(n-r)}$ where ${r = \lceil n/2\rceil}$. Since this bound holds for every ${x}$, it follows that ${\delta n(n-1)/2 \le r(n-r)}$, which simplifies to

${\displaystyle \delta \le \frac{r}{2r-1}}$, where ${r = \lceil n/2\rceil}$.

For example, ${\delta_4\le \delta_3\le 2/3}$, ${\delta_6\le \delta_5\le 3/5}$, ${\delta_8\le \delta_7\le 4/7}$, and so on. Are these estimates sharp? For an affirmative answer it would be enough to demonstrate that ${\delta_{2r}\ge r/(2r-1)}$ by finding a suitable collection of ${2r}$ subsets. Note that sharpness requires that almost every point of ${[0, 1]}$ be covered by exactly ${r}$ of these subsets, and that all pairwise distances between sets must be equal to ${r/(2r-1)}$.

## Sharpness of the upper bound

Four subsets with ${2/3}$ separation are easy to find: ${[0,1/3]}$, ${[1/3, 2/3]}$, ${[2/3, 1]}$, and ${[0, 1]}$. Thus, ${\delta_4=2/3}$.

To find six subsets with ${3/5}$ separation, some preparation is helpful.

For any set ${A}$, the map ${E\mapsto E\triangle A}$ is an isometry of ${X}$ onto ${X}$. So, there is no loss of generality in assuming that one of our ${2r}$ sets is ${[0, 1]}$. Then we are to find ${E_1,\dots, E_{2r-1}}$ of measure ${1-r/(2r-1) = (r-1)/(2r-1)}$. In order to have the specified distances, the measure of intersection of any two sets must be ${(r-2)/(4r-2)}$.

For example, if ${r=2}$, the above says we need three disjoint sets of measure ${1/3}$, which is a trivial thing to find. For ${r>2}$ the sets will no longer be disjoint.

## Discretization of the problem

A natural way to proceed is to partition ${[0, 1]}$ into ${4r-2}$ equal subintervals (or other sets of equal measure). Then we look for ${2r-1}$ sets, each of which consists of ${(4r-2)(r-1)/(2r-1) = 2r-2}$ subintervals. Their pairwise intersections must consist of ${(4r-2)(r-2)/(4r-2) = r-2}$ subintervals.

The case ${r=2}$ was done above. If ${r=3}$, we want to use ${10}$ subintervals to form ${5}$ sets with ${4}$ subintervals in each. Pairwise intersections must consist of precisely ${1}$ 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 ${\delta_6=3/5}$.

Next up, ${r=4}$. Following the above method, we partition ${[0, 1]}$ into ${4r-2 = 14}$ equal subintervals and look for ${7}$ sets, each of which consists of ${6}$ subintervals. Pairwise intersections must consist of ${2}$ subintervals each. Can this be done?

Think of a cube. It has ${8}$ vertices and ${6}$ faces, and ${8+6=14}$. In the set {faces and vertices}, we choose ${7}$ subsets of cardinality ${6}$ 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, ${\delta_8 = 4/7}$. But it is concerning that ${\delta_6}$ and ${\delta_8}$ required different combinatorial constructions. What happens next?

For ${r=5}$, we partition ${[0, 1]}$ into ${18}$ equal subintervals and look for ${9}$ sets, with ${8}$ subintervals in each. Pairwise intersections must consist of ${3}$ subintervals. I don’t see any neat construction here.

## Summary so far

The results obtained so far for ${r=2, 3, 4}$ can be summarized as follows: there exists a 0-1 matrix ${B_r}$ of size ${(2r-1)\times (4r-2)}$ in which the dot product of two rows is ${r-2}$ when the rows are distinct and ${2r-2}$ otherwise. Specifically,

${\displaystyle B_2 = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} }$

${\displaystyle B_3 = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}}$

The matrix ${B_4}$ is best written in block form ${[F | V]}$ according to the faces-vertices interpretation. Here

${\displaystyle F = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}}$ and ${\displaystyle V = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}}$

Does ${B_5}$ exist? Perhaps not.

## Combinatorics of finite sets

In combinatorial terms, we are looking for a ${k}$-uniform ${\ell}$-intersecting family of ${m}$ subsets of ${[n]}$, with specific values

${k = 2r-2}$, ${\ell=r-2}$, ${m=2r-1}$, ${n=4r-2}$.

Explanation of terms: ${[n]=\{1, 2, \dots, n\}}$, being ${k}$-uniform means every set has ${k}$ elements, and being ${\ell}$-intersecting means all pairwise intersections have ${\ell}$ 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 ${X=[0,n]}$ be the real interval and let ${\lambda}$ be the Lebesgue measure on ${X}$. If ${\mathcal{F}=\{F_1,\ldots,F_m\}}$ is a family of subsets of ${X}$ such that

1. ${\lambda(F_i)=k}$ for all ${i\in [m]}$, and
2. ${\lambda(F_i\cap F_j)=\ell}$ for all distinct ${i,j\in[m]}$,

then we call ${\mathcal{F}}$ a fractional ${\ell}$-intersecting ${k}$-uniform ${m}$-family of ${X}$. For given real numbers ${n,\ell}$ and integer ${m}$, let ${\kappa_{\ell}^{\text{frac}}(n,m)}$ be the largest real number ${k}$ such that there exists a fractional ${\ell}$-intersecting ${k}$-uniform ${m}$-family of ${[0,n]}$.

Theorem 2.5 Let ${n>\ell\ge 0}$ be two real numbers and let ${m\ge 1}$ be an integer. Then

${\displaystyle \kappa_{\ell}^{\text{frac}}(n,m)={m-1\choose s-1}\alpha+{m-1\choose t-1}\beta, }$

where ${\displaystyle s=\left\lfloor\frac{1+\sqrt{1+4m(m-1)\ell/n}}{2}\right\rfloor}$, ${\displaystyle t=\left\lceil\frac{1+\sqrt{1+4m(m-1)\ell/n}}{2}\right\rceil}$

and ${(\alpha,\beta)}$ is the solution of the system

${\displaystyle \binom{m}{s}\alpha+\binom{m}{t}\beta=n}$

${\displaystyle \binom{m-2}{s-2}\alpha+\binom{m-2}{t-2}\beta=\ell}$.

This looks complicated, but with our values ${\ell=r-2}$, ${m=2r-1}$, ${n=4r-2}$ both ${s}$ and ${t}$ turn out to be equal to ${r-1}$. This is an exceptional case when the linear system is degenerate: it amounts to ${\alpha+\beta = (4r-2)/\binom{2r-1}{r-1}}$. The final result is ${\kappa_{\ell}^{\text{frac}}(n,m)=2r-2}$ as we wanted. Yay.

So, the upper bounds for distances are indeed sharp, meaning that ${n}$ subsets of the unit interval can be separated by measure-distance of ${r/(2r-1)}$, where ${r = \lceil n/2\rceil}$. But dividing the intervals into ${4r-2}$ 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 ${4r-2}$.

The authors remark that if ${\alpha, \beta}$ are integers, then a partition with ${k=\kappa^{\text{frac}}}$ exists in the combinatorial realm of ${\{1, \dots, n\}}$. However, this is not “if and only if”. Indeed, ${\alpha+\beta = (4r-2)/\binom{2r-1}{r-1}}$ which takes integer values when ${r=1, 2, 3}$, and is fractional (less than 1) when ${r\ge 4}$. But we do have a combinatorial solution when ${r=4}$. So it is not quite clear for what values of ${r}$ there exists a ${(2r-2)}$-uniform ${(r-2)}$-intersecting family of ${2r-1}$ subsets of ${[4r-2]}$. Perhaps an answer could be found by following the construction for this specific case, when the formulas magically simplify.

## Two subspaces, part II

Good news first. Given a 2-dimensional subspace $M$ of $\mathbb R^4$ (or $\mathbb C^4$) such that $e_j\notin M\cup M^\perp$ ($j=1,2,3,4$), we can always find a coordinate subspace $N$ such that $M$ and $N$ are in generic position. (Recall that generic position means $(M\cup M^\perp)\cap (N\cup N^\perp)=\{0\}$, which is feasible only when the dimension of $M$ and $N$ is half the dimension of the ambient space.)

Indeed, suppose that none of the subspaces $\langle e_1,e_2\rangle$, $\langle e_1,e_3\rangle$, $\langle e_1,e_4\rangle$ are in generic position with $M$. By the pigeonhole principle, either $M$ or $M^\perp$ meets at least two of these subspaces. We may assume $M$ meets $\langle e_1,e_2\rangle$ and $\langle e_1,e_3\rangle$. Since $M$ is two-dimensional, it follows that $M\subset \langle e_1,e_2,e_3\rangle$. Hence $e_4\in M^\perp$, a contradiction.

The story is different in $n=6$ and higher dimensions. Consider the space

$M=\langle e_1-e_2,e_1-e_3,e_4+e_5+e_6\rangle$, with $M^\perp=\langle e_1+e_2+e_3,e_4-e_5,e_4-e_6\rangle$

The condition $\forall j\ e_j\notin M\cup M^\perp$ holds. Yet, for any 3-dimensional coordinate space $N$, either $N$ or its complement contains at least two of vectors $e_1,e_2,e_3$, and therefore intersect $M$. Damn perfidious pigeons.

So it’s not enough to demand that $M\cup M^\perp$ does not contain any basis vectors. Let’s ask it to stay away from the basis vectors, as far as possible. By the Pythagorean theorem, the maximal possible distance of $e_j$ to $M\cup M^\perp$ is $1/\sqrt{2}$, attained when $e_j$ is equidistant from $M$ and $M^\perp$. Let’s call $M$ an equidistant subspace if this holds for all $e_j$. There are at least two other natural ways to express this property:

• In the basis $\{e_1,\dots,e_{2n}\}$, the projection onto $M$ is a matrix with 1/2 on the diagonal
• Reflection across $M$ sends $e_j$ into a vector orthogonal to $e_j$. As a matrix, this reflection has 0s on the diagonal.

In two dimensions, the only equidistant subspaces are $y=x$ and $y=-x$. In higher dimensions they form a connected subset of the Grassmannian $\mathrm{Gr} (n/2, n)$ (self-promotion).

Is every equidistant subspace in generic position with some coordinate subspace?

We already saw that the answer is yes when $n=2,4$. It is also affirmative when $n=6$ (G. Weiss and V. Zarikian, “Paving small matrices and the Kadison-Singer extension problem”, 2010). I am 75% sure that the answer is yes in general.