No set fills half of every interval

No interval in it, and length to spare built a set that seems to defy the picture of length as a property of pieces. Remove from $[0, 1]$ a middle interval of length $\tfrac14$, then from each of the two pieces left a middle interval of length $\tfrac1{16}$, then from each of the four pieces a middle of length $\tfrac1{64}$, and so on. The removed intervals add up to exactly one half, so half the length remains — and yet every interval, however short, has had something removed from it, so the set contains no interval at all. It is the Smith–Volterra–Cantor set, a fat Cantor set, with length and no room.

That makes it the natural test for a question that sounds as though it ought to have an easy yes. Every interval contains points of the set and points of its gaps. Could a set be arranged so finely that it takes exactly half of every interval — the same proportion everywhere, at every scale, like a perfectly even grey? This essay shows that the answer is no, for this set and for every set that has a length, and that the reason is a theorem about what a set looks like through a microscope.

The share of a shrinking window #

Call the set $E$, and for a point $x$ and a radius $r$ let the density at that radius be the share of the window around $x$ that lies in $E$:

$$d_r(x) = \frac{|E \cap (x - r,\, x + r)|}{2r}.$$

The figures compute it from the eighteenth stage of the construction, kept as 262,144 sorted intervals with their running total of length, so that the length of $E$ inside any window is two binary searches; the stages after the eighteenth remove less than $2^{-19}$ in all, far below anything the windows here can see.

The hero follows the density at three points as the window closes. At a point of the set chosen by random choices of left or right at every stage, the window at radius $\tfrac12$ is about half full — the window is most of $[0,1]$ — and as it shrinks the share climbs, unevenly, because at each scale the window keeps meeting a new gap of the next stage. It reaches $0.997$ at radius $10^{-5}$ and is still climbing. At the middle of one of the three-stage gaps, of width $\tfrac1{64}$, the share falls to nought the moment the window fits inside the gap, and stays there. At the left end of that same gap the share settles on exactly one half: to the right of the point is gap, to the left is set with fewer and fewer holes in it, and the window always straddles both.

The third behaviour is the only way to get an answer other than 0 or 1, and it needs a point on the edge of a gap. There are countably many such points. Every other point of the set behaves like the first, and every other point outside it like the second.

Twenty thousand points at four radii #

Three points prove nothing about all of them, so the next figure asks the question of twenty thousand points scattered evenly over $[0, 1]$. At radius $\tfrac1{10}$ the densities are spread across the whole range — a window of that size usually contains several gaps and several pieces — and 90.72% of the points have a density strictly between $0.1$ and $0.9$. At radius $\tfrac1{100}$ the histogram has grown spikes at both ends and the in-between share is 44.62%. At $\tfrac1{1000}$ it is 14.89%, and at $\tfrac1{10\,000}$ it is 3.22%. The densities are being driven apart, towards nought and one, and the points left in the middle are the ones that happen to sit near the edge of a gap whose size matches the window — fewer at every smaller radius, because a smaller window has to be closer to an edge to straddle it.

This is Lebesgue’s density theorem, which Henri Lebesgue proved in 1910 for every set that has a length in his sense: as the window shrinks, $d_r(x)$ tends to 1 at almost every point of the set and to 0 at almost every point outside it. “Almost every” is the measure theorist’s phrase for “except on a set of length nought”, and in this example the exceptions are the gap endpoints and a few other points whose windows keep catching gaps in an unlucky rhythm. They exist, and there are uncountably many of them on some sets; but together they have no length, and a randomly chosen point lands on one with probability nought.

The theorem is the reason length is a sensible notion for sets as ragged as this one. Covering a set from outside defined the length of a set by covering it with intervals as economically as possible, and the density theorem says that, measured at a point, a set with a length looks like an interval or like empty space. It has no third texture, no uniform grey, at almost any point at all.

A derivative in disguise #

The density theorem is a statement about derivatives, and seeing it that way explains why it should be true. Let $F(x)$ be the length of the part of $E$ that lies to the left of $x$, $F(x) = |E \cap [0, x]|$. Then the density at radius $r$ is exactly a difference quotient,

$$d_r(x) = \frac{F(x + r) - F(x - r)}{2r},$$

and the theorem says that $F$ has a derivative almost everywhere, equal to 1 on the set and 0 off it. For the fat Cantor set, $F$ is a staircase that rises with slope one across the set and stays flat across every gap; because the gaps are dense, it has no interval of steady slope anywhere, and still its slope exists and is 0 or 1 at almost every point.

That is the special case, for indicator functions, of Lebesgue’s differentiation theorem: the running integral of any integrable function has the function itself as its derivative, except on a set of length nought. Which functions can be added up met the integral as the thing a function’s upper and lower sums agree on; the differentiation theorem is its converse, the fundamental theorem of calculus extended to every function with an integral, and the price of the extension is the phrase “almost everywhere”. The price is real. The staircase with no steps rises from 0 to 1 with derivative nought at almost every point, so it is not the running integral of its derivative; it climbs entirely on the middle-thirds Cantor set, which has no length, where the differentiation theorem says nothing. The fat Cantor set’s staircase is the opposite case — it climbs on a set of positive length and is the integral of its derivative — and the difference between the two staircases is exactly the difference between a set of length nought and a set of length one half.

Seen this way the theorem is also a statement of the kind almost every orbit is fair made about binary digits: a property that holds at every point is too much to ask, a property that holds at almost every point is what measure can deliver, and the exceptions, though they may be dense and uncountable, weigh nothing.

Sets built to fill half, and where they fail #

Now the question of the opening. Suppose a set $A$ filled exactly half of every interval. Then its density would be exactly $\tfrac12$ at every point and every radius — and the density theorem says it must be 0 or 1 almost everywhere. Both cannot hold unless the set has no points worth mentioning, and a set that fills half of every interval has half the length of each. So no set with a length fills half of every interval. The proof is two lines once the theorem is in hand, and it reaches every possible construction at once.

The figure shows why every attempt fails, by trying the most natural one. Cut $[0, 1]$ into cells of width $2^{-m}$ and keep every other one: the set of $x$ with $\lfloor 2^m x \rfloor$ even. A long window holds many cells, half of them kept, and its share is within $2^{-m}/\ell$ of a half — the leftover piece of one cell at the window’s end is the only unfairness. A window shorter than one cell can sit entirely inside a kept cell, and then its share is 1. The curves plot the worst excess over one half, maximised over every placement of the window, against the window’s length, for $m = 4, 8, 12, 16$. Each is flat at the maximum, $\tfrac12$, until the window outgrows a cell, then falls in a sawtooth towards nought. Finer cells move the cliff to a smaller scale, and that is all they can do.

The natural escape is to use infinitely many scales at once — keep the cells of every width in some balanced combination — and the theorem says that escape is closed too. The density at a point is a limit as the window shrinks, and whatever happens at each finite scale, the limit must come out 0 or 1 at almost every point. A set that is fair at more and more scales is a set whose fairness is postponed, and at each point the microscope eventually sees past it.

Every small shift is a difference #

The theorem’s first famous use was Hugo Steinhaus’s of 1920, which two dusts that add up to a line stated: for any set $E$ of positive length, the differences $x - y$ of its points fill a whole interval around nought. The density theorem proves it. Pick a point where the density of $E$ is above $\tfrac34$ at some radius $r$, so that more than three quarters of the window of width $2r$ around it is set. Shift the window’s contents by any $t$ smaller than $r/2$: the shifted set still covers more than half of the original window’s width, and two sets each covering more than half of one interval must overlap. A point in the overlap is in $E$ and in $E + t$, so it is $y + t$ for some $y$ in $E$, and $t$ is a difference.

The figure draws the overlap itself, $|E \cap (E + t)|$, as the shift grows from 0 to 1. At $t = 0$ it is the whole length, $0.5001$ at the twelfth stage, and as the copy slides it falls away in a ragged decline — the overlap rises again whenever a shift lines up the copy’s pieces with the set’s own — but it changes continuously, because sliding by a little changes the overlap by a little, and it is positive from 0 right up to a shift of 1. So for this set the differences fill the whole interval from $-1$ to $1$. The continuity is the general mechanism and the density theorem is what makes the start positive near every density point, not only at $t = 0$.

The density theorem as a fair game #

There is a second way to read the theorem that has nothing to do with windows centred on a point. Write a point of $[0, 1]$ in binary and reveal its digits one at a time. After $n$ digits the point is known to lie in a dyadic interval of length $2^{-n}$, and the share of $E$ in that interval is the best available guess at the chance that the point is in $E$. The figure follows that guess for forty random points. It starts at $\tfrac12$, the set’s length, and then moves at each digit, sometimes far — a digit that puts the point in a big gap sends the guess to nought at once — and every path ends at 0 or 1: 18 in the set, 22 outside it, each correctly classified by the 22nd digit.

The sequence of guesses is a martingale, a fair game: averaging the shares of the two halves of an interval gives back the share of the whole, so the next guess is, on average, the present one. Paul Lévy proved in 1937 that a fair game of this kind, guessing at an event that the full information settles, converges to the event’s own indicator — 1 if it happens, 0 if not — with probability one. That is Lévy’s zero–one law, and for this particular game it is the density theorem with dyadic intervals in place of centred windows. The same martingale reasoning drives evidence that can be multiplied, where a running likelihood ratio is a fair game under the null and is forced towards nought. A theorem of real analysis and a theorem about betting turn out to be one statement about how information about a point accumulates.

Some of every interval, all of none #

The fat Cantor set falls short of filling half of every interval in an obvious way: its gaps are intervals that contain none of it. A weaker demand can be met. Fill each gap with a copy of the set shrunk to fit, then fill the gaps of the copies with copies of their own, and so on forever. The figure carries this out to two levels in the fifteen largest gaps, and already every window of width $0.02$ placed at a thousandth of the way along holds some of the set and some of its complement, between 19.4% and 96.9% of it. Carried on to every level, the construction gives a set that meets every interval in positive length and contains no interval — a set with $0 < |A \cap I| < |I|$ for every interval $I$, of the kind Walter Rudin described in 1983 as well-distributed.

It is as close to an even grey as a set can come, and the density theorem still applies to it. At almost every point the share of a shrinking window goes to 0 or 1. What the filling changes is where the exceptional points are: the points at which the density does something else are now dense in the line, appearing in every interval, though they still have length nought. A set can be spread through every interval, but it cannot be spread evenly through any of them in the limit.

Eighteen stages of the set, and no rate for every set #

The densities are exact for the eighteenth stage of the construction, whose intervals differ from the limit set by less than $2^{-19}$ in total length, and the radii stop at $10^{-5}$, where that difference is still invisible. The overlap curve uses the twelfth stage. The sample points and the forty paths are seeded and reproducible. So the figures compute exactly what they claim for a set indistinguishable at their resolution from the fat Cantor set, and they show the theorem’s conclusion arriving on that set; they cannot show a limit, since every curve stops at a finite radius.

No figure here exhibits a set whose density fails to exist on a set of positive length, because there is none; that is the theorem, and it is proved, not observed. The figures also do not show how slowly the density can approach 0 or 1. On the fat Cantor set the approach is fast because the gaps shrink like $4^{-n}$; for sets with gaps shrinking more slowly the density at typical points can take arbitrarily long to settle, and no rate holds for every set.

And the theorem is about sets that have a length. A set with no length in Lebesgue’s sense — the set with no size at all built by choosing one point from each class of the rationals’ translates — has no density either, because its share of a window is not defined; with the outer length of covering a set from outside in its place, such a set can look like “full” in every window and still have a complement that looks just as full.

Still open: windows of other shapes #

On the line every window is an interval, and the theorem holds. In the plane there is a choice of window, and the choice matters. Discs work, and so do squares, and so — a theorem of Børge Jessen, Józef Marcinkiewicz and Antoni Zygmund in 1935 — do rectangles with sides parallel to the axes, however elongated. Rectangles that may point in any direction do not: Besicovitch’s sets, which contain a segment in every direction while having no area — the planar original of the sets no set with a line in every direction is small counted over a finite field — give sets whose density measured with thin rectangles of the right orientation is 1 at points where it should be 0.

The open problem sits between those. Choose at each point of the plane one direction, varying smoothly — a Lipschitz vector field — and measure density using thin segments along the chosen direction at each point. Does the density theorem hold for such averages? Zygmund asked this in the 1930s, and it is still unsolved; Elias Stein’s version for averages of functions over the same segments is open too. The difficulty is that the segments at nearby points point in slightly different directions, which is just enough freedom to try to build a Besicovitch-type counterexample and not, so far, enough to succeed. Whether a smoothly varying choice of direction is tame enough is one of the central open questions of harmonic analysis.

Grey is not a texture a set can have #

Every set with a length looks, at almost every point, like the whole line or like nothing: the share of a shrinking window around the point tends to 1 or to 0. On the fat Cantor set the in-between shares fall from nine tenths of all points at radius $\tfrac1{10}$ to three per cent at $\tfrac1{10\,000}$, and only the edges of gaps hold out at one half. So no set fills half of every interval; every construction that tries, like alternating cells, is fair at large scales and fails inside its finest cell. The same theorem makes every small shift a difference of two of the set’s points, and read as a fair game of guessing digits it is Lévy’s zero–one law. A set can meet every interval without filling any — but even then, under the microscope, it is black or white.