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<j} |\chi_k-\chi_j|\ge \delta n(n-1)/2}. 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<j} |\chi_k(x)-\chi_j(x)| = p(n-p)}. 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.

I admit it could be neater

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.

Measurability of Banach space valued functions

There is only an indirect proof of the existence of a function {f\colon [0, 1]\to \mathbb R} that is not Lebesgue measurable. But it’s easy to give an explicit example when the codomain of {f} is a Banach space: just let {b(t)} be the sequence of the binary digits of {t}, considered as an element of the sequence space {\ell_\infty}.

Why is {b} not measurable? Recall that a Banach space-valued function {f} is (Bochner) measurable iff there is a sequence of simple functions {\sum v_k \chi_{A_k}} (finite sum, measurable {A_k}, arbitrary vectors {v_k}) that converges to {f} almost everywhere. This property implies that, with an exception of a null set, the range of {f} lies in the separable subspace spanned by all the vectors {v_k} used in the sequence of simple functions. But {b} has the property {\|b(t)-b(s)\|=1} whenever {t\ne s}, so the image of any uncountable set under {b} is nonseparable.

Another way to look at this: on the interval [0, 1) the function {b} is injective and its range has discrete topology, which implies that every subset of [0, 1) is the preimage of some open subset of {\ell_\infty} under {b}.

The binary-digits functions can also be used to illustrate an issue with the duality of Lebesgue-Bochner spaces {L_p(0, 1; X)} where {X} is a Banach space and {1\le p<\infty}. (So, {f} belongs to this space iff it is Bochner measurable and the {L^p} norm of {\|f\|\colon [0, 1]\to [0, \infty)} is finite.) In general we do not have the expected relation {L_p(0, 1; X)^* = L_q(0, 1; X^*)} with {1/p+1/q=1}. The natural isometric embedding of {L_q(0, 1; X^*)} into {L_p(0, 1; X)^*} is still there: any {g\in L_q(0, 1; X^*)} acts on {L_p(0, 1; X)} by {f\mapsto \int \langle f(t), g(t) \rangle\, dt}. But unless {X^*} has the Radon–Nikodym property, these are more bounded linear functionals on {L_p(0, 1; X)}.

To construct such a functional, let {b_n(t)} be the {n}-th binary digit of {t}. Given {f\in L_1(0, 1; \ell_1)}, write it in coordinates as {(f_1, f_2, \dots)} and define {\varphi(f) = \sum_n \int_0^1 f_n b_n}. This is a bounded linear functional, since {|\varphi(f)|\le \sum_n \int_0^1 |f_n| = \|f\|}. But there is no function {g\in L_\infty(0, 1; \ell_\infty)} that represents it, i.e., {\varphi(f) = \int_0^1 \langle f(t), g(t)\rangle \,dt = \sum_n \int_0^1 f_n g_n }. Indeed, if such {g} existed then by considering {f} with only one nonzero coordinate, we find that {g_n} must be {b_n}, using the duality {L_1^* =  L_\infty} in the scalar case. But the function {[0, 1]\to \ell_\infty} with the components {(b_1, b_2, \dots)} is not measurable, as shown above.

This example, which applies to all {1\le p<\infty}, also serves as a reminder that the duality relation {L_p(0, 1; X)^* = L_q(0, 1; X^*)} depends on the dual space {X^*} having the Radon-Nikodym property (RNP), not {X} itself. Indeed, {X=\ell_1} has the RNP; its dual does not.

The importance of {X^*} having the RNP becomes clear once one tries to follow the usual proof of {L_p^*=L_q}. Given {\varphi\in L_p(0,1;X)^*}, we can define an {X^*}-valued measure {\tau} on {[0, 1]} by {\tau(A)(v) = \varphi( v\chi_A)} where {A\subset [0, 1]} is Lebesgue measurable and {v\in X}. This measure has reasonable finiteness and continuity properties coming from {\varphi} being a bounded functional. Still, the existence of a density {g\colon [0, 1]\to X^*} of the measure {\tau} depends on the structure of the Banach space {X^*}.

Diagonal

The diagonal {D=\{(x,x):0\le x\le 1\}} of the unit square {Q=[0,1]\times [0,1]} is a mysterious thing. For one thing, its length is an irrational number. But this is not what I’m writing about.

Behold the mystery
Behold the mystery

The diagonal has zero area. Lebesgue integrable functions on {Q} form the normed space {L^1(Q)} which, upon closer inspection, consists not of functions but of their equivalence classes. Two functions {f,g} are equivalent if the set {\{f\ne g\}} has zero area. In particular, changing all the value of {f} on the diagonal {D} does not change {f} as an element of {L^1(Q)}. The logical conclusion is that given an element {f\in L^1(Q)}, we have no way to give a meaning to the integral of {f} over {D}.

But wait a moment. If I take two square integrable function {u,v\in L^2[0,1]}, then the expression {\int_0^1 u(x)v(x)\,dx} makes perfect sense. On the other hand, it represents the integral of the function {f(x,y)=u(x)v(y)} over the diagonal {D}.

Pushing this further, if an element {f\in L^1(Q)} can be represented as {f(x,y)=\sum_{k=1}^n u_k(x)v_k(y)} for some {u_k,v_k\in L^2[0,1]}, then {\int_D f} is naturally defined as {\sum_{k=1}^n \int_0^1 u_kv_k}. I can even take infinite sums, assuming that everything converges.

This is confusing. If I pick up an element of {L^1(Q)} off the sidewalk, how will I know if it’s safe to integrate it over the diagonal? The existence or nonexistence of the decomposition into sum of products is not obvious.

I guess a satisfactory answer is given by the notion of a Lebesgue point. Given {f\in L^1(Q)} and a point {p} of {Q}, consider the following statement:

\displaystyle    \exists y_0\in \mathbb R \text{ such that } \lim_{r\rightarrow 0} \frac{1}{r^2} \int_{|x-p|<r} |f - y_0| =0   \ \ \ \ \ (1)

The validity of (1) and the value of {y_0} are not affected by the choice of a representative of {f}. If (1) holds, {p} is called a Lebesgue point of {f}, and we can think of {y_0} as the “true” value of {f(p)} (whether or not our representative agrees with that value). It’s a theorem that almost every point of the domain of {f} is a Lebesgue point. The meaning of “almost every” corresponds to the measure under consideration: on the plane it’s the area, on a line it’s the length.

The product {f(x,y)=u(x)v(y)} has a special feature. Since almost every {x\in [0,1]} is a Lebesgue point of {u}, and a.e. {y\in[0,1]} is a Lebesgue point of {v}, it follows that almost every point of the diagonal (in the sense of linear measure) is a Lebesgue point of the product {f}. (It helps to integrate over small squares instead of disks in (1), which does not change anything.) This makes it possible to define {\int_D f} unambigiously.

The sums of products also have the property that almost every point of {D} is a Lebesgue point. And other elements of {L^1(Q)} may also have this property: they are safe to integrate diagonally, too.