Two sign patterns that land together

A coin in front of every power puts a random sign on each term of $1 + \lambda + \lambda^2 + \cdots$ and finds that for $\lambda$ above one half the result lands on a smooth-looking hill that fills its interval. For almost every $\lambda$ the hill has a density. At $\lambda = 1/\varphi = 0.618\ldots$, the reciprocal of the golden ratio, it does not: all of its weight sits on a set of length nought, spread so evenly through the interval that no picture can find the gaps.

Paul Erdős proved that in 1939, and his proof and the one that measures how thin the set is both start from the same place — not from the shape of the hill, which gives nothing away, but from a single identity. Because $\varphi^2 = \varphi + 1$, dividing by $\varphi^3$ gives

$$\lambda^2 + \lambda = 1 \qquad (\lambda = 1/\varphi),$$

and that one line means two different sign patterns can land on exactly the same point.

The same point by two routes #

Take the three signs $+\,-\,-$ in front of $1$, $\lambda$ and $\lambda^2$. They contribute $1 - \lambda - \lambda^2$, which is nought. The opposite three, $-\,+\,+$, contribute $-1 + \lambda + \lambda^2$, which is also nought. So any two sign patterns that are identical except that one has $+\,-\,-$ where the other has $-\,+\,+$ — in any three consecutive places, since multiplying the identity by $\lambda^k$ moves it along — land on precisely the same number.

The two walks in the figure set off in opposite directions — one a whole unit to the right, the other a whole unit to the left — and meet again after the third step, having travelled $\pm(1 - \lambda - \lambda^2) = 0$ net. From there they take the same steps and arrive together. Nothing like this can happen at $\lambda = 0.65$: two different sign patterns can only land together if $\lambda$ is a root of a polynomial with coefficients $-1$, $0$ and $1$, and $0.65$ is not.

The identity is a statement about writing numbers in base φ, where the digit string $0.100$ and the string $0.011$ name the same number. Base two has exactly one way to write most numbers; base φ has many, and the random sign pattern is a random base-φ expansion that frequently lands on a number some other expansion also names.

Far fewer landing points than patterns #

Collisions compound. Every window of three places where one pattern reads $+\,-\,-$ gives a partner, and the partners have partners. Counting the distinct landing points exactly, by writing every partial sum as $a + b\lambda$ with whole $a$ and $b$ and using $\lambda^2 = 1 - \lambda$ to keep it in that form, gives the numbers in the figure.

Two patterns of one term land on two points; four of two terms on four; eight of three terms on seven. From there the count falls steadily behind: 12 points for 16 patterns, 88 for 256, 609 for 4,096, and at twenty terms 28,656 points for 1,048,576 patterns — every count one less than a Fibonacci number, $F(n + 3) - 1$, at every $n$ checked. The number of landing points grows like $\varphi^n$, and the number of patterns like $2^n$.

There is a reason the count cannot grow faster, and it is where the golden ratio’s special nature enters. The number $a + b\lambda$ has a partner, its conjugate $a - b\varphi$, got by replacing $\lambda = 1/\varphi$ with the equation’s other root $-\varphi$. The conjugate of a partial sum $\sum \pm \lambda^k$ is $\sum \pm (-\varphi)^k$, which is at most about $\varphi^{n+1}$ in size. So every landing point is a pair of whole numbers $(a, b)$ whose value lies in a fixed interval and whose conjugate lies in an interval of width about $\varphi^n$ — a strip of the plane of area proportional to $\varphi^n$, which can hold only about $\varphi^n$ lattice points. The patterns are forced to share, not by any special coincidence but because there is not enough room: $2^n$ patterns, $\varphi^n$ places.

Base φ, and where the Fibonacci numbers come from #

Writing numbers in base φ is an old idea with a young inventor: George Bergman published it in 1957, at the age of twelve. Every whole number has a finite base-φ expansion, and it becomes unique once one rule is imposed — no two ones side by side, since $011$ can always be rewritten as $100$. Strings of noughts and ones with no two ones adjacent are counted by the Fibonacci numbers: a string of length $m$ either ends in a nought, after any allowed string of length $m - 1$, or ends in $01$, after any allowed string of length $m - 2$, so the counts add like Fibonacci numbers, and there are $F(m + 2)$ of them.

That is the natural home for the count in the figure. A landing point of $n$ signs is a base-φ number with $n$ digits, and rewriting $011$ as $100$ carries leftward — at the front, one place beyond the first digit, since $1 + \lambda = \varphi$ — so the rewritten strings have $n + 1$ places and there are $F(n + 3)$ strings with no adjacent ones among them. One of those is too large for any $n$ signs to reach. The figure finds the count $F(n + 3) - 1$ exactly at every $n$ from one to twenty; the sketch explains where the Fibonacci numbers come from and stops short of a proof, since a rewriting can also carry to the right, and following every carry is the part it does not do.

The same strings count something else as well. The word a straight line spells at golden slope is a string with no two ones side by side, and a tiling that never repeats grows its two kinds of piece in Fibonacci numbers for the same reason. The random sum, the golden cutting sequence and the Penrose tiling all inherit their counting from one equation, $\varphi^2 = \varphi + 1$.

Why 0.65 escapes the argument #

At $\lambda = 0.65$ the same enumeration finds no collisions at all: two different sign patterns never land on the same point, because $\tfrac{13}{20}$ is not a root of any polynomial with coefficients $-1$, $0$ and $1$ — a rational root of such a polynomial would need a denominator dividing its leading coefficient, which is $\pm 1$. So all $2^n$ patterns give $2^n$ different points, the entropy grows by the full $\log 2$ per sign, and the dimension is one.

That removes the obstruction and proves nothing further. A dimension of one is compatible with a density and also with a distribution that has none; the entropy argument can only ever show that a distribution is thin, never that it is thick. The argument for a density has to show that the $2^n$ distinct points spread their weight evenly at every scale, which is a statement about how close together different patterns land rather than whether they land exactly together, and for $0.65$ nobody has managed it. The essay before this one describes the transversality argument that does it for almost every $\lambda$ and cannot say which.

A shortfall of 0.002 per sign #

Having fewer landing points than patterns is not, on its own, enough to rule out a density. At twenty terms the points are $2 \times 10^{-4}$ apart on average, finer than any histogram, and a set of points that fine could be approximating a smooth density perfectly well. What matters is how unevenly the weight is shared among them, and the measure of that is the entropy of the distribution of landing points: the average of $-\log p$ over the points, weighted by their chances $p$.

With no collisions each new sign doubles the number of equally likely points and adds exactly $\log 2 = 0.6931$ to the entropy. With collisions it adds less. The increase per sign settles, at the golden value, on $h = 0.47915$, and it settles within a dozen terms.

Compare that with what a density would need. To spread smoothly across an interval at resolution $\lambda^n$ — the size of the last term — the weight has to be shared out over about $\varphi^n$ boxes nearly evenly, which takes entropy $n \log\varphi = 0.48121\,n$. The golden sum supplies $0.47915$ per sign, about $0.002$ short of that every time. The shortfall compounds: after $n$ signs the weight is concentrated on about $e^{0.47915 n}$ effective boxes out of $e^{0.48121 n}$ available, a vanishing fraction. The ratio

$$\frac{h}{\log \varphi} = \frac{0.47915}{0.48121} = 0.99571$$

is the dimension of the distribution — Adriano Garsia defined the entropy in 1963, and Jeff Alexander and Don Zagier computed this value in 1991 — and a dimension below one means the weight lives on a set of length nought. The tribonacci number, the root of $x^3 = x^2 + x + 1$, gives $0.9804$ by the same exact count, and the tetranacci and pentanacci numbers give $0.9869$ and $0.9926$. Each is a fraction of a per cent below the line, and each is a distribution with no density.

Powers that close in on whole numbers #

Erdős’s proof, older than the entropy by a quarter of a century, used a different consequence of the same equation. It turns on what happens to the powers of $\varphi$.

The sum $\varphi^n + (-1/\varphi)^n$ is a whole number for every $n$ — it is the $n$-th Lucas number, $1, 3, 4, 7, 11, 18, \dots$, built by the same rule as the Fibonacci numbers — and $(-1/\varphi)^n$ shrinks to nothing. So $\varphi^n$ is within $\varphi^{-n}$ of a whole number, and gets closer at every step: $\varphi^{16} = 2206.9995\ldots$ This is exactly the property that defines a Pisot number: an algebraic integer greater than one whose other conjugates all lie inside the unit circle, which makes their powers vanish and leaves the number’s own powers nearly whole. The rectangle that eats itself meets the same fact as a curiosity of the golden ratio, and numbers whose powers must come home meets its relatives on the unit circle. The tribonacci number is Pisot too, its two other roots a complex pair of size $0.74$, and its powers close in more slowly. The powers of $1/0.65$ follow no such law.

The transform that will not die down #

The characteristic function of the random sum — the average of $\cos(tX)$ — is the product of the averages for each term, and each term contributes a single cosine:

$$\hat\mu(t) = \prod_{k \ge 0} \cos(\lambda^k t).$$

A distribution with a density has a characteristic function that dies away as $t$ grows: that is the Riemann–Lebesgue lemma, the continuous cousin of the Fourier coefficients of a function falling away, the fact that averaging a faster and faster oscillation against any fixed density gives something closer and closer to nought. Erdős showed that at the golden value it does not die away.

Look at the frequencies $t = 2\pi\varphi^n$. The first $n + 1$ factors of the product are $\cos(2\pi\varphi^n), \cos(2\pi\varphi^{n-1}), \dots, \cos(2\pi)$, and each $\varphi^m$ is within $\varphi^{-m}$ of a whole number, so each factor is the cosine of a small angle, very nearly one. Their product converges as $n$ grows, because the angles shrink geometrically. The remaining factors are $\cos(2\pi\varphi^{-1}), \cos(2\pi\varphi^{-2}), \dots$ — the same fixed list whatever $n$ is. So $\hat\mu(2\pi\varphi^n)$ approaches a fixed non-zero number, $4.87 \times 10^{-4}$, and holds it for ever. The figure shows it doing so from $n = 5$ onward. At $0.6$ and $0.65$, whose reciprocals are not Pisot numbers, the same kind of frequencies give a product that falls through ten orders of magnitude.

A transform that does not die away rules out a density. By the dichotomy Jessen and Wintner proved in 1935 — every such distribution has a density or is purely singular — the golden distribution is purely singular, and the argument works word for word for the reciprocal of every Pisot number.

A quasicrystal’s sharp spots, from the same property #

The property that ruins the random sum is the one that makes a quasicrystal look like a crystal. Penrose’s rhombus tiling is built by a substitution whose scaling factor is $\varphi$, and it has no period; yet shining X-rays through a material arranged that way gives a pattern of perfectly sharp spots, which is what a periodic crystal gives and what an irregular arrangement should not. Enrico Bombieri and Jean Taylor explained why in 1986: for a substitution whose scaling factor is a Pisot number, the powers of the factor close in on whole numbers, the waves scattered by the tiles at the matching frequencies stay in step instead of cancelling, and the transform of the arrangement keeps sharp peaks at those frequencies for ever.

The material was real before the explanation was. Dan Shechtman saw ten-fold symmetric spots from a rapidly cooled aluminium–manganese alloy in 1982, a symmetry no periodic crystal can have, and spent years being told the pattern must come from twinned ordinary crystals; the Nobel Prize for chemistry in 2011 recorded who was right. The sharpness of those spots, in an arrangement with no period, is the Pisot property at work.

It is the same calculation read with the opposite sign of approval. In a quasicrystal the transform refusing to die down is the sharp diffraction spot that made the discovery possible; in the random sum it is the proof that no density exists. Both are the product of cosines of nearly whole multiples of $2\pi$.

What the pictures cannot show #

The limit. The count figure stops at twenty terms and the entropy at eighteen; the transform is drawn to $n = 24$. The claims are about every $n$. The Fibonacci pattern in the counts is checked at every $n$ drawn and not proved here, and the entropy per sign is seen to settle to five places, which is evidence for the limit rather than a computation of it — Alexander and Zagier’s value comes from an exact formula, and agrees.

The set the weight lives on. A dimension of $0.9957$ says the distribution sits on a set of length nought, and nothing drawn here shows that set. Its distribution function is a curve of the staircase’s kind, with slope nought almost everywhere, and a drawing of it looks like any smooth S-curve. It is dense in the interval, it has no gaps anybody could draw, and its deficit from full length appears only at scales around $10^{-70}$.

Why only these numbers. Every argument on this page uses the Pisot property — powers closing in on whole numbers, or conjugates that stay small — and the figures show it for four Pisot numbers. They cannot show that nothing else behaves the same way, which is the open question.

Still open: what else can land together #

The argument needs two things: exact collisions between sign patterns, which happen whenever $\lambda$ is a root of a polynomial with coefficients $-1$, $0$ and $1$, and enough of them to push the entropy below $\log(1/\lambda)$. Pisot reciprocals have both. Many other algebraic numbers have collisions without enough of them, and their dimension is one; Michael Hochman proved in 2014 that for every algebraic $\lambda$ the dimension is exactly the entropy divided by $\log(1/\lambda)$, or one if that is larger, so for algebraic numbers the question is purely one of counting collisions.

What is not known is how small that count can make the dimension away from the Pisot numbers, and here the question meets a problem from a different part of number theory. Emmanuel Breuillard and Péter Varjú showed in 2019 that the entropy of a collision-prone $\lambda$ is controlled by its Mahler measure — the product of the sizes of its conjugates outside the unit circle — and that a positive answer to Lehmer’s question about how small a Mahler measure can be, open since 1933, would imply that every $\lambda$ close enough to one gives dimension one. Whether the golden value’s company among the singular distributions extends beyond the Pisot numbers is thus tied to whether a polynomial with Mahler measure below Lehmer’s $1.17628$ exists — two questions separated by forty years and a field, asking in the end how close an algebraic number can come to landing its powers on whole numbers.