The cosines of the powers of two

A solvable chaos of every degree showed that the map $T_2(x) = 2x^2 - 1$ is chaotic and completely solvable at once. Write a point of $[-1, 1]$ as $\cos\theta$, and the map doubles the angle: $T_2(\cos\theta) = \cos 2\theta$. Every orbit is therefore a sequence of cosines of doubling angles, every one of them written down by a formula, and the same essay found that almost every orbit spends its time according to the arcsine density, crowding towards the ends of the interval. It ended on the orbit it had drawn first. Started at $\cos 1$, the orbit is

$$\cos 1,\ \cos 2,\ \cos 4,\ \cos 8,\ \ldots,\ \cos(2^k),\ \ldots$$

the cosines of the powers of two, in radians. Almost every orbit is fair. Is this one?

This essay follows that one orbit as far as it can be followed, which turns out to be a question about computing a single constant, and tests it every way a finite computation allows. The answer is that it behaves exactly as a fair orbit should for a quarter of a million steps, and that its fairness for ever is equivalent to a statement about the binary digits of $1/(2\pi)$ that nobody knows how to prove.

Each step reads one more digit #

The formula $x_k = \cos(2^k)$ looks as if it settles everything, and it does not, because a cosine needs its angle reduced modulo $2\pi$ before it can be evaluated to any accuracy. The angle $2^{50}$ radians is about $1.1 \times 10^{15}$ radians, and its cosine depends on where that lands within a single turn — on the fractional part of $2^{50}/(2\pi)$, which needs $1/(2\pi)$ to fifty binary places before the first useful one.

That is the whole structure of the problem. Write $1/(2\pi)$ in binary:

$$\frac{1}{2\pi} = 0.00101000101111100110000011011011\ldots_2$$

Multiplying by $2^k$ moves the binary point $k$ places to the right, and the fractional part is what is left after it. So the angle $2^k$, as a fraction of a full turn, is the binary number formed by the digits of $1/(2\pi)$ from the $(k+1)$-th onwards.

The map $T_2$ doubles the angle, and doubling shifts the window one digit along. This is the doubling map again — the map that shifts a number’s binary digits — dressed in a cosine, and the orbit of $\cos 1$ is the orbit of $1/(2\pi)$ under doubling, viewed through the change of coordinates that the same map in different coordinates used to identify the tent map with the logistic map. The whole future of this orbit is written out in advance, one digit per step, in a constant that nobody chose and that has nothing to do with the map.

Fifty-one steps of arithmetic #

The obvious way to compute the orbit is to iterate: start at $\cos 1$, square, double, subtract one, repeat. In double-precision arithmetic that works for a while.

The two curves lie on top of each other until step 51, and then the iterated one goes its own way. That is exactly what the digit picture predicts. A double-precision number carries 53 binary digits, so $\cos 1$ stored in one is the cosine of an angle correct to about 53 bits. Each step of the map consumes one bit of that angle, and by the fiftieth step the stored value has used up everything it knew about where it started. From then on the iterated orbit is the true orbit of some other point, one whose binary expansion agrees with $1/(2\pi)$ for fifty-odd places and continues with the arithmetic’s rounding errors.

The orbit a computer draws examined that situation in general: a computed chaotic orbit is often the true orbit of a nearby starting point, which is enough for statistics and useless for following one particular point. Here the particular point is the whole question. Iterating will never reveal where the orbit of $\cos 1$ goes after fifty steps, however good the arithmetic, unless the arithmetic carries as many bits as the number of steps.

Reading the digits sidesteps the problem completely. The digits of $1/(2\pi)$ were computed for this essay to $2^{18} = 262{,}144$ binary places, by computing $\pi$ in exact integer arithmetic with Machin’s formula $\pi = 16\arctan\frac15 - 4\arctan\frac{1}{239}$, checking it against Størmer’s four-term formula to all but the last few guard digits, and dividing. Each orbit point is then the cosine of a 53-bit window of those digits, so every one of the 262,080 points used here is correct to the precision of the arithmetic — not after a few dozen steps, but at every step.

Step $k$ costs $k$ digits #

The reading has a price that grows with the step. To know where the orbit is at step $k$ to any useful accuracy, the digits of $1/(2\pi)$ from position $k$ to about $k + 50$ are needed, and the usual ways of computing a constant produce its digits in order, from the first. So the cost of locating the millionth point of this orbit is the cost of computing $1/(2\pi)$ to a million binary places — a few seconds with modern methods, and growing a little faster than linearly with the number of places. There is no shortcut in sight that would place the orbit at step $10^{100}$.

For $\pi$ itself there is one, of a limited kind. David Bailey, Peter Borwein and Simon Plouffe found in 1995 a series for $\pi$ whose terms let the hexadecimal digits at any position be computed without computing the ones before, in time roughly proportional to the position and with almost no memory. It is the reason specific far-out digits of $\pi$ can be checked independently of the full expansion. No such formula is known for $1/\pi$ or $1/(2\pi)$. If one were found, the orbit of $\cos 1$ under the doubling-angle map could be sampled at any step without visiting the steps before — though it would still say nothing about whether the orbit is fair, since a digit-extraction formula produces digits and not their statistics.

The asymmetry with the map is worth noticing. The map $T_2$ is a polynomial of degree two, cheap to apply, and the orbit is given by a closed formula. All the expense lies in knowing the starting point to enough precision, because each step multiplies the uncertainty by two. That is sensitive dependence in its purest form: the dynamics are perfectly known, the starting point is perfectly specified, and the only obstacle to the far future is the length of the description of where it began.

Two hundred and sixty thousand points #

With the true orbit in hand, the first test is the one that defines fairness for this map: does it spend its time according to the arcsine density?

The fit is close enough to be uninformative in the best sense. The arcsine law predicts how many of the 262,080 points should fall in each of the forty bins, and the chi-square statistic, which adds up the squared discrepancies weighted by the expected counts, comes out at 24.4. For 39 degrees of freedom a genuinely random sample would give a larger value more than nine times in ten. The orbit is not merely compatible with the arcsine law; it fits it somewhat better than a random sample usually does, which at this length is unremarkable.

The density itself has a reason, which the histogram an orbit leaves derived for the logistic map. If the angles are spread uniformly round the circle, their cosines are not uniform on $[-1, 1]$: a uniform angle spends more of its time near $0$ and $\pi$, where the cosine changes slowly, than near $\pi/2$, where it sweeps through the middle of the interval fast. The density of $\cos\theta$ for uniform $\theta$ is $1/(\pi\sqrt{1 - x^2})$, the curve in the figure, and the histogram of the orbit fits it because the angles $2^k$ look uniform round the circle. Fairness of the orbit and uniformity of the angles are the same statement.

A running share that does what chance does #

A histogram summarises the end of the computation. The running share shows how it got there.

If the angles are uniform, a quarter of them should fall in the first quarter of the turn, and for independent random angles the share after $n$ draws would wander around 0.25 with a typical deviation of $\sqrt{3/16n}$. The orbit’s share starts erratically — after ten steps it is 0.3 — and settles inside the band the random draws would occupy, ending at 0.2510. At no length does it leave the band, and at no length does it hug 0.25 suspiciously closely either. It looks like chance at every scale.

That is the most that a finite computation can say, and the limitation is not a technicality. Almost every orbit is fair pointed out that the ergodic theorem is a statement about limits, and that a number could behave normally for a billion digits and then stop: append a billion zeros to the first billion digits of any number and the running share collapses. Nothing in the first quarter of a million digits rules that out for $1/(2\pi)$, and nothing ever could.

Blocks of digits #

The quarter-turn test looks at single pairs of digits — the first two after the window’s start decide which quarter an angle is in. A fair orbit needs more: every block of digits must occur with the right frequency, which is what it means for the binary expansion to be normal, and what makes the orbit visit every small interval of angle in proportion to its length.

The statistic in the figure is the serial test. For each block length it compares how often each possible block occurs with how often it would occur if the digits were independent and fair, after allowing for what the counts of blocks one shorter already imply, and expresses the excess in standard deviations. A bias in blocks of length up to fourteen — some pattern of fourteen digits turning up even slightly more often than one in 16,384 — would show as a point well outside the shaded band. None does.

There is one feature worth reporting because it looks like a discovery and is not. All fourteen of the warm points sit a little below zero. If the fourteen were independent and each as likely to fall below zero as above, that would happen to random digits about once in sixteen thousand times; in fact they share most of their counts — the blocks of length nine are made of the blocks of length eight — and they move together. The figure measures the effect directly: of two hundred strings of random digits put through the same test, nine put all fourteen points on one side of zero. The second half of the digits of $1/(2\pi)$, tested on its own, puts only ten of the fourteen below. It is a mild coincidence of the first half of these particular digits, and it says nothing about the constant.

Powers settle nothing that multiples settle #

The difficulty is specific to powers, and the comparison with multiples shows how specific. The sequence $\cos k$ — the cosines of the whole numbers rather than of the powers of two — is provably fair. The angles $k$ modulo $2\pi$ are the multiples of a fixed rotation, and Hermann Weyl showed in 1916 that the multiples of any irrational fraction of a turn are spread uniformly round the circle; $1/(2\pi)$ is irrational, so the angles are uniform and the cosines follow the arcsine law. A series that waits on π used the same angles $n$ modulo $\pi$ and found that their rate of approach to the multiples is the hard question; their uniformity is not in doubt. The leading digits of the powers of two are settled by the same theorem, because they are governed by the multiples $k \log_{10} 2$ modulo 1, and multiplying makes the digit one common drew exactly that.

Multiples are rotations, and a rotation is the tamest of maps: it moves every point by the same amount, so knowing that the step is irrational is enough to know everything. Powers of two are orbits of the doubling map, which is chaotic, and for chaotic maps knowing the starting point is irrational, or transcendental, or the reciprocal of $2\pi$, tells nothing about where its orbit goes. Weyl’s theorem has a doubling counterpart, Émile Borel’s, that almost every starting point is normal; but “almost every” is a statement about a randomly chosen point, and $1/(2\pi)$ was not chosen at random.

The same question one degree up #

A solvable chaos of every degree showed that $T_2$ is the first of a family: for every $n$ there is a polynomial $T_n$ with $T_n(\cos\theta) = \cos n\theta$. The orbit of $\cos 1$ under the cubic $T_3(x) = 4x^3 - 3x$ is $\cos(3^k)$, and its fairness is the same question about the same constant, asked in base three.

Tripling a binary fraction is not a shift of its digits, so the computation is different: the fractional part of $3^k/(2\pi)$ is obtained by multiplying the stored value of $1/(2\pi)$ by three and discarding the integer part, again and again, and each tripling costs $\log_2 3 \approx 1.585$ of the stored bits. Sixty thousand steps use about 95,000 of the 262,144, well inside what is known. The histogram fits the arcsine law again, with a chi-square of 34.1 on 29 degrees of freedom, a value random samples exceed about a quarter of the time.

Normality in base three is a separate property from normality in base two. Wolfgang Schmidt showed that a number can be normal to one base and not to the other whenever the two bases are not powers of a common number, as two and three are not. So the orbit of $\cos 1$ under $T_3$ could in principle be fair while its orbit under $T_2$ is not, or the reverse; the two computations are independent evidence about two independent unknowns, and both come out the same way.

Still open: one digit at a time #

It is not known whether the binary digits of $1/(2\pi)$ are normal, and so it is not known whether the orbit of $\cos 1$ under $x \mapsto 2x^2 - 1$ follows the arcsine law. It is not even known whether the digit 1 occurs in that expansion with frequency one half, which would be the statement that the angle $2^k$ lies in each half of the turn half the time — a much weaker property than fairness. The same is true of $\pi$, $\sqrt 2$, $e$ and every other constant arising from anything other than a construction designed to be normal.

What is known is the general theorem: Borel’s, that almost every number is normal in every base, so almost every starting point of every Chebyshev map gives a fair orbit. Between that theorem and any particular orbit there is no known bridge. The methods that settle Weyl’s theorem for multiples rest on the rotation being an isometry and break the moment the map stretches. There are partial results for sequences like $2^k \alpha$ with $\alpha$ satisfying special conditions, and results saying the set of exceptions, though of zero length, is large in other senses. None of them reaches a number defined by geometry. The digits can be computed as far as anyone likes — $\pi$ is known to trillions of places, all of which look normal — and the computation can only ever say what the first trillion digits do.

A constant read one digit at a time #

The orbit of $\cos 1$ under a solvable map is, in the end, a slow reading of $1/(2\pi)$: each step uncovers one more binary digit and turns it into a position on the interval. Iteration loses the reading after fifty-one steps because the arithmetic has only fifty-three digits to give; computing the constant carries it as far as the computation goes, here to a quarter of a million steps, and every test of fairness that a finite reading allows comes out as fair as chance. The formula for the orbit is exact and the behaviour of the orbit is unknown, and the gap between the two is the same gap that separates a theorem about almost every number from a statement about one.