Multiples and powers mod 1

For a positive real numberx, the expressionx mod 1 means the fractional part ofx:

x mod 1 =x - x .

This post will look at the distributions ofnx mod 1 and xⁿ mod 1 for n = 1, 2, 3, ....

The distribution of nx mod 1 is easy to classify. Ifx is rational thennx will cycle through a finite number of values in the interval [0, 1]. Ifx is irrational thennx will be uniformly distributed in the interval.

The distribution of xⁿ mod 1 is more subtle. We have three basic facts.

1. If 0 x < 1, then xⁿ 0 as n .
2. If x = 1 then xⁿ = 1 for alln.
3. For almost all x > 1 the sequence xⁿ mod 1 is uniformly distributed. But for some values ofx it is not, and there's no known classification for these exceptional values ofx.

The rest of the post will focus on the third fact.

Suppose x = 2. Then for all even n, xⁿ mod 1 = 0. The sequence isn't uniformly distributed in [0, 1] because half the sequence is piled up at 0.

For another example, let's look at powers of the golden ratio = (1 + 5)/2. For even values of n the sequence ⁿ converges to 1, and for odd values of n it converges to 0. You can find a proof here.

At one time it was not known whether xⁿ mod 1 is uniformly distributed forx = 3 + 2. (SeeHAKMEM, item 32.) I don't know whether this is still unknown. Let's see what we can tell from a plot.

Apparently sometime around n = 25 the sequence suddenly converges to 0. That looks awfully suspicious. Let's calculate x²⁵ using bc.

 $ echo '(3 + sqrt(2))^25' | bc -l 13223107213151867.43024035874391918714

This says x²⁵ mod 1 should be around 0.43, not near 0. The reason we're seeing all zeros is that all the bits in the significand are being used to store the integer part and none are left over for the fractional part. A standard floating point number has 53 bits of significand and

(3 + 2)²⁵ > 2⁵³.

For more details, see Anatomy of a floating point number.

Now let's see what happens when we calculate xⁿ mod 1 correctly using bc. Here's the revised plot.

Is this uniformly distributed? Well, it's not obviously not uniformly distributed. But we can't tell by looking at a plot because uniform distribution is an asymptotic property.

We didn't give the definition of a uniformly distributed sequence until now because an intuitive understanding of the term was sufficient. Now we should be more precise.

Given a setE, a sequence , and an integer N, define A(E, , N) to be the number of elements in the first N elements of the sequence that fall inside E. We say is uniformly distributed mod 1 if for every 0 a b 1,

lim_N A([a, b), , N) / N = b - a.

That is, the relative port of points that fall in an interval is equal to the length of the interval.

Now let's go back to the example x = 2. We know that the powers of this value of x are not uniformly distributed mod 1. But we also said that for almost all x > 1 the powers ofx are uniformly distributed. That means every tiny little interval around 2 contains a numbery such that the powers ofy are uniformly distributed mod 1. Now ify is very close to 2 and we plot the first few values ofyⁿ mod 1 then half of the values will be near 0. The sequence will not look uniformly distributed, though it is uniformly distributed in the limit.

The post Multiples and powers mod 1 first appeared on John D. Cook.