A coin in front of every power

A coin in front of every term puts a random sign on each of $1, \tfrac12, \tfrac13, \dots$ and finds that the sum converges, lands somewhere different every time, and lands according to a smooth, flat-topped density that can be computed to any accuracy. It ends by naming the series one change away: put the coins on the powers of a fixed number instead,

$$X = \pm 1 \pm \lambda \pm \lambda^2 \pm \lambda^3 \pm \cdots, \qquad 0 < \lambda < 1,$$

and the answer is no longer understood.

Nothing about this series is subtle. It converges absolutely for every choice of signs, faster than the harmonic one ever could, since its terms are those of the sum that fits in one square. Its values all lie in the interval from $-1/(1-\lambda)$ to $1/(1-\lambda)$, reached only by the all-minus and all-plus patterns. The question is how the chance of landing is spread over that interval — and the answer depends on $\lambda$ in a way that is simple below one half, simple at one half, and above one half is one of the oldest open questions about a random series anybody has written down.

Four values of λ, four kinds of answer #

Nothing in the figures below is sampled. The first $n$ terms take $2^n$ values, each with chance $2^{-n}$, and all of them are listed and sorted into bars; $n$ is chosen large enough that the terms left out could move a value by less than a small fraction of a bar.

At $\lambda = \tfrac13$ the sum lands on a dust: nearly three quarters of the 128 bars are empty, and the occupied ones cluster in pairs of pairs of pairs. At $\lambda = \tfrac12$ it lands anywhere in $[-2, 2]$ with equal chance, and every bar is exactly a quarter high. At $\lambda = 1/\sqrt2$ the bars climb in a straight line, run level, and fall in a straight line: a trapezoid. And at $\lambda = 1/\varphi \approx 0.618$, the reciprocal of the golden ratio, they make a hill that looks exactly as smooth as the trapezoid’s neighbours would, and it is the one distribution in the row that has no density at all.

The last claim is what the next essay, two sign patterns that land together, is about. This one is about the other three, and about why the region above one half is where the difficulty lives.

Every such distribution is two copies of itself #

The series has one structural fact that decides almost everything. Split off the first sign:

$$X = \pm 1 + \lambda\,(\pm 1 \pm \lambda \pm \lambda^2 \pm \cdots) = \pm 1 + \lambda X',$$

where $X'$ has exactly the same distribution as $X$. So the distribution of $X$ is an equal mixture of two copies of itself, each shrunk by the factor $\lambda$, one centred at $+1$ and one at $-1$.

Each shrunken copy occupies an interval of half-width $\lambda/(1-\lambda)$ around $\pm 1$, so the gap between them is

$$2 - \frac{2\lambda}{1-\lambda},$$

which is positive below one half, nought at one half, and negative — an overlap — above it. The figure’s three panels are the three cases: a gap of $0.67$ at $\lambda = 0.4$, contact at $\tfrac12$, an overlap of a whole unit at $0.6$.

Below one half the copies are disjoint, and so are the copies of copies inside each of them, and so on down: every stage of the splitting opens new gaps inside the old pieces. What is left after infinitely many stages is a Cantor set, and the distribution lives on it. At one half the copies tile the interval exactly, and the only distribution that is two half-size copies of itself placed edge to edge is the flat one. Above one half the copies pile on top of each other, and the equation says the distribution is its own two overlapping copies without saying what shape that forces.

One coin sequence, three kinds of number #

The two cases below and at one half are the same coin tosses read in two different bases, and seeing it that way explains the flat distribution without any computation.

Write each sign as a digit: a plus as $1$ and a minus as $0$, so that the $k$-th sign is $2b_k - 1$ for a fair random digit $b_k$. At $\lambda = \tfrac12$ the sum becomes

$$X = \sum_{k \ge 0} (2b_k - 1)\,2^{-k} = 4 \sum_{k \ge 0} b_k\, 2^{-(k+1)} - 2 = 4U - 2,$$

where $U = 0.b_0 b_1 b_2\ldots$ in binary. A number whose binary digits are independent fair coins is a uniformly random number in $[0, 1]$ — that is what a uniform random number is, digit by digit, and it is how fair bits are turned into random numbers in practice. So $X$ is uniform on $[-2, 2]$, and the flatness in the first figure is the flatness of the binary digits.

At $\lambda = \tfrac13$ the same digits land in base three instead, as the ternary digits $0$ and $2$ of a number — the digit $1$ never occurs, which is exactly the description of the Cantor set. And at $\lambda = 1/\varphi$ they land in base φ, a numeral system in which the digits are not unique: $0.011$ and $0.100$ are the same number there, because $\varphi^{-2} + \varphi^{-3} = \varphi^{-1}$. The same stream of coin tosses produces a uniform number, a point of a Cantor set, or a point of a distribution with no density, and the only thing that changed is the base the tosses were written in. Base two has room for every pattern exactly once; base three has more room than the patterns can fill; base φ has less room than there are patterns, and some of them have to share.

Dust below one half, and how much of it there is #

The Cantor dust at $\lambda = \tfrac13$ is the familiar one, the middle-thirds set scaled to the interval $[-\tfrac32, \tfrac32]$: writing $\pm 1 \pm \tfrac13 \pm \tfrac19 \dots$ is writing a number in base three with every digit $0$ or $2$, after a shift. Its size is measured by a dimension. A set made of two copies of itself, each shrunk by $\lambda$, with no overlap, has dimension $d$ satisfying $2\lambda^d = 1$ — two pieces, each contributing its share of the whole’s size at scale $\lambda$ — so

$$d = \frac{\log 2}{\log(1/\lambda)},$$

which is $0.6309$ at $\lambda = \tfrac13$ and rises to exactly one at $\lambda = \tfrac12$.

Above one half the same formula gives a number larger than one, and that is the whole difficulty in one line. Two copies shrunk by $0.6$ would have total “size” $2 \times 0.6^d$, and for that to equal one the dimension would have to be $1.36$ — more than a line has room for. The copies cannot sit side by side; they must overlap, and how much they overlap, and whether the overlaps pile up into spikes or spread evenly, is exactly what decides whether the distribution has a density. The figure marks the values where the answer is known: on the line at dimension one, three where a density exists in closed form; just below the line, two where it does not.

The values where the density can be written down #

A handful of values above one half give up their answer at once, and the reason is the flat case one level down. Take $\lambda = 1/\sqrt2$. Then $\lambda^2 = \tfrac12$, and the terms split into the even powers $\pm 1 \pm \tfrac12 \pm \tfrac14 \cdots$ and the odd ones $\lambda(\pm 1 \pm \tfrac12 \pm \tfrac14 \cdots)$. Each group is the one-half series, which is flat on $[-2, 2]$ because a coin for every binary digit gives a uniformly random number. The two groups use different coins. So $X$ is a flat random number plus an independent flat random number shrunk by $1/\sqrt2$.

The density of a sum of two independent flat pieces is a trapezoid — the overlap of one sliding interval with another — with corners at $\pm(2 - \sqrt2)$ and $\pm(2 + \sqrt2)$. At $\lambda = 2^{-1/3}$ the terms split three ways, the density is the convolution of three flat pieces, and it is made of pieces of parabolas joined smoothly. At $2^{-1/m}$ it is $m$ flat pieces, with a density made of polynomials of degree $m - 1$, smoother with every step towards one. The figure checks the enumerated bars against the closed forms and they agree to about one part in ten thousand, which is the size of the terms the enumeration left out.

These are the easy cases, and they are special: they work because some power of $\lambda$ is exactly one half, so the overlapping copies can be regrouped into non-overlapping ones. For $\lambda = 0.6$, or $0.65$, or the golden value, no power of $\lambda$ is a half and no regrouping exists.

Overlapping evenly and overlapping exactly #

Without a regrouping, the only information is the equation: the distribution is its two shrunken copies, overlapping. There are two quite different ways for copies to overlap, and they pull in opposite directions.

The copies can overlap evenly. At a typical $\lambda$, the two shrunken copies are offset by an amount unrelated to their own internal structure, so the dense parts of one land on ordinary parts of the other, the copies of copies do the same one level down, and the piling-up averages out. That is the mechanism behind a density, and it is why Solomyak’s theorem below is true for almost every $\lambda$: when nothing lines up, overlap smooths.

Or the copies can overlap exactly. If $\lambda$ satisfies an equation with small whole-number coefficients, some of the $2^n$ sign patterns land on precisely the same point, and when they do, the weight of both lands there together. At the golden value $\lambda^2 + \lambda = 1$, so $+1 - \lambda - \lambda^2$ and $-1 + \lambda + \lambda^2$ are both exactly nought, and any two patterns that differ only by swapping those three signs land together. Exact coincidences concentrate weight where even overlaps would spread it, and if they happen often enough the concentration survives the limit and the distribution is left with no density. How often “often enough” is — and why the golden value’s coincidences win while those of many other algebraic numbers lose — is the next essay.

A distribution function that looks the same either way #

The difference between having a density and not having one is invisible at the level of the distribution function, the chance $F(x)$ of landing at or below $x$.

All four curves are continuous, because no single value is ever landed on with positive chance: to land on a particular point, infinitely many coins must all come out one particular way. At $\lambda = \tfrac13$ the function is a staircase with no steps, flat across every gap of the dust and climbing only on the dust itself. At $\tfrac12$ it is a straight line. At $1/\sqrt2$ it is a smooth S-curve whose slope is the trapezoid.

At the golden value it is also a smooth-looking S-curve, and it is a curve of the staircase’s kind. A monotone function has a slope at almost every point, and a distribution with no density has a distribution function whose slope is nought at almost every point — so the golden curve climbs from nought to one while having zero slope almost everywhere, doing all of its climbing on a set of no length, exactly like the Cantor staircase. The difference is that its climbing set is spread through the whole interval instead of leaving visible gaps, and so it looks, at every resolution a drawing can reach, like an ordinary smooth function. The figure’s golden curve and its $1/\sqrt2$ curve are indistinguishable in kind to the eye, and one of them has a slope everywhere and the other almost nowhere.

What is known, and how it was found #

The subject has a clean dichotomy, found by Børge Jessen and Aurel Wintner in 1935: for every $\lambda$, the distribution of $X$ either has a density or is purely singular — concentrated on a set of no length — with no mixture of the two. Every value above one half is one or the other, and the question is which.

The first answer was a surprise in each direction. In 1939 Paul Erdős showed that at $\lambda = 1/\varphi$, and at the reciprocal of every Pisot number — a whole-number root whose other roots all lie inside the unit circle — the distribution is singular, although it fills the interval. In 1940 he showed the opposite for almost every $\lambda$ close enough to one. Half a century later, in 1995, Boris Solomyak proved that almost every $\lambda$ between one half and one gives a density, by a transversality argument that controls how the overlapping copies move past each other as $\lambda$ changes. Since then the exceptional set has been shrunk further: Michael Hochman showed in 2014 that the dimension of the distribution is one outside a set of $\lambda$ of dimension zero, Pablo Shmerkin upgraded that to a density outside a set of dimension zero, and Péter Varjú proved in 2019 that the dimension is one at every transcendental $\lambda$.

Solomyak’s idea is worth stating because it is the precise form of “overlap smooths”. Two sign patterns that differ first at the $k$-th term land at points whose difference is $\lambda^k$ times a power series in $\lambda$ with coefficients $0$ and $\pm 2$. For the two to land close together, that power series has to be nearly nought at the chosen $\lambda$. Solomyak showed that on the interval from one half to about $0.649$, any such power series that comes near nought is also steep there — it crosses nought rather than touching it — so for most $\lambda$ it is not small, and the set of $\lambda$ where many patterns crowd together has measure nought. Beyond $0.649$ the same property fails for some series, and Yuval Peres and Solomyak finished the interval in 1996 with the regrouping that gave the trapezoid: the even and odd powers of $\lambda$ use different coins, so the distribution at $\lambda$ is the one at $\lambda^2$ added to a shrunken independent copy of itself, and a density at $\lambda^2$ passes up to $\lambda$. The method measures crowding across all $\lambda$ at once, and so it can never name the $\lambda$ it misses.

“Almost every” is the phrase to notice. It says that a $\lambda$ chosen at random gives a density, and says nothing about $0.6$, or $0.65$, or $2/3$, each of which is a single value in a set of measure zero. For most specific values of $\lambda$ that anybody would write down, nobody knows.

What the pictures cannot show #

Whether a density exists. Every figure here is a finite enumeration, and a finite enumeration gives a histogram, and every histogram is a density. The golden hill in the first figure is made of eighteen terms’ worth of landing points sorted into 128 bars; the true distribution at $1/\varphi$ puts all its weight on a set of length nought, and no finite number of bars can show a set of length nought, because every bar has length. The two kinds of distribution differ only in the limit, and the pictures are all before the limit.

Which way the golden hill fails. The deficit in dimension is small — the golden distribution’s dimension is $0.9957$, less than half a per cent below one — so its failure to have a density shows up only at scales far finer than any histogram, where a bar of width $\varepsilon$ holds about $\varepsilon^{0.9957}$ of the weight instead of $\varepsilon$. At $\varepsilon = 10^{-6}$ that is a factor of $1.06$. To show a factor of two the bars would have to be about $10^{-70}$ wide.

The theorems. Solomyak’s almost-every result and Erdős’s singularity are quoted, not drawn. The next essay draws the mechanism behind Erdős’s side of the answer; the other side’s transversality argument has no single picture.

Still open: whether the golden value has company #

The reciprocals of Pisot numbers are the only values between one half and one known to give a singular distribution. They are countably many, and they are all algebraic numbers of a very particular kind. Whether any other $\lambda$ gives a singular distribution — whether the exceptional set Solomyak’s theorem leaves room for is exactly the Pisot reciprocals, or contains something else — has been asked since Erdős and is open. For algebraic $\lambda$ that are not Pisot reciprocals, Varjú’s work since 2019 settles many cases through a condition on the size of the polynomial $\lambda$ satisfies, and the conditions do not reach every algebraic number. And a value as plain as $\lambda = \tfrac23$, a rational number with no special structure, is not settled either. Nobody has proved that the sum has a density there, though every computation says it should. What is proved is weaker and still not obvious: its dimension is exactly one, by Hochman’s theorem, because no polynomial with coefficients $-1$, $0$ and $1$ has $\tfrac23$ as a root — so no two sign patterns ever land together, and the only question left is whether evenly spread overlaps are spread evenly enough.