12
$\begingroup$

Particular questions such as Why is $\pi$ so close to $3$? or Why is $\pi^2$ so close to $10$? may be regarded as the first two cases of the question sequence Why is $\pi^k$ so close to its nearest integer?

For instance, we may stare in awe in front of the almost-unit $$\frac{\pi}{31^\frac{1}{3}}=1.000067...$$

or, in binary system, $$\frac{\pi}{11111_{2}^\frac{1}{11_2}} \approx 1$$

so proving that $\pi^3>31$ becomes interesting, but it would not be striking that sometimes $\pi^k$ lied close to its nearest integer if that was balanced by other unlucky times when it would be at almost half a unit, by the straightforward effect of the rounding function.

Under a uniform distribution assumption, the expected distance between $\pi^k$ and its nearest integer is $\frac{1}{4}$, and the title has at least the following two interpretations, as a random variable (given this made sense) and as particular outcomes of a random variable:

  1. In average, is $\pi^k$ any closer to its nearest integer than expected? The first three powers have differences less than $\frac{1}{4}$ in absolute value, namely $$\begin{align} \pi-3 &\approx .1416 \\ \pi^2-10 &\approx -0.1304 \\ \pi^3-31 &\approx0.0063 \end{align}$$ This event has probability $\left(\frac{1}{2}\right)^3=\frac{1}{8}$ assuming independence. What happens as the number of powers considered grows? Another approach, with median instead of average: Does the median of the absolute value of that difference tend to $\frac{1}{4}$?

  2. Let $\lfloor x \rceil$ denote the rounding function. Although the answer to the first question may be false, for what values of $k$ does $\lfloor x^k \rceil ^\frac{1}{k}$ yield more bits of $\pi$ than it uses? For instance, $\lfloor x^{157} \rceil ^\frac{1}{157}$ seems to be an interesting approximation to $\pi$. (See this question)

In either case:

Q: Is the difference between $\pi^k$ and its nearest integer uniformly distributed in $(-\frac{1}{2},\frac{1}{2})$?

$\endgroup$
  • 1
    $\begingroup$ This feels like it is true because $\pi$ is transcendental $\endgroup$ – vrugtehagel Feb 11 '16 at 11:24
  • 1
    $\begingroup$ @vrugtehagel: on the contrary, we expect this to be true with any algebraic number in place of $\pi$ (except for actual integers), while there are uncountably many transcendental numbers for which the analogous statement is false. $\endgroup$ – Greg Martin Feb 12 '16 at 2:31
  • 1
    $\begingroup$ @Greg, PV-numbers also form algebraic counterexamples. $\endgroup$ – Gerry Myerson Feb 12 '16 at 6:08
  • $\begingroup$ @Gerry Myerson Yes, true. Would $\lfloor x \rceil$ as proposed by Hastad be a proper choice? functions.wolfram.com/IntegerFunctions/Round/introductions/… $\endgroup$ – Jaume Oliver Lafont Feb 14 '16 at 9:03
  • 2
    $\begingroup$ Uniform distribution properties of particular numbers are extremely difficult to handle with current machinery. I know in the case of normality (where we look at sequences $b^{k} x$), we're pretty good at constructing sets of $x$ with certain properties (and determining their size), but we have pretty much no understanding of the normality of, say, $\pi, e, \sqrt{7}$, etc. You should check out this book (amazon.com/Uniform-Distribution-Sequences-Dover-Mathematics/dp/…), which is pretty much the standard starting place for questions about uniform distribution. $\endgroup$ – AJY Feb 15 '16 at 15:33
4
$\begingroup$

There are two ways of looking into this problem. For this we need to define what uniform distribution means. I will alter and observe the interval $[0,1]$ and adopt $x = [x]+\{x\}$ for clarity.

  1. If we take that uniform distribution is corresponding to uniform distribution of random numbers then $\{\pi^k\}$ is of much lower quality than the best uniform random distribution we can produce using other algorithms. This is to say that it would not be a good generator of random numbers.

  2. If we take that uniform distribution is actually equidistribution, meaning on average and looking at infinity, the frequency of terms falling into any segment $[a,b]$ tends to $b-a$, then we believe that $[\pi^k]$ is equidistributed although there is no proof.

First thing first.

  1. We are fairly convinced that $\pi$ is a normal number, digits from $0$ to $9$ are appearing each with frequency $\frac{1}{10}$ for couple of million digits and beyond.

Although we have no proof, for our story, this will be good for now. If we take $\pi$ as a normal number and if digits appear as if they are random(, but pay attention that normal does not mean random, it only has some property of a random sequence) then we can take that $\{\pi\}$ in $\pi=3+\{\pi\}$ has some random properties: it starts non-randomly, but then as we are adding more digits, additional segments are all more "random".

When we say that $\pi$ does not start randomly, we have a specific randomness in mind. There is a type of randomness (Martin-Löf) related to Kolmogorov complexity that says that a number is random if we cannot compress it, we cannot write a program much shorter than its number of digits. So $\pi$ is not random in this sense, since we can write a pretty short programs for it. Even more, if we look into first few digits expressed for example as a spigot algorithm

$$\pi=2+\frac{1}{3}(2+\frac{2}{5}(2+\frac{3}{7}(...(2+\frac{k}{2k+1}(...)))))$$

we can notice that first few digits can be encoded within a shorter sequence, and only as we go deeper more data is needed and more operations will be performed. Many random generators have this feature and for this reason many algorithms have a worm-up phase. It is difficult to state precisely if it is two, three, six or ten first digits in $\pi$ that are interconnected through a first few terms in an expression like the one we have shown using the spigot algorithm, (we would need to define a precise measure for this,) but a few first digits have a simpler connection, they are easier to express, and for this reason they are less random in the sense we have explained. The reason, again, is that you can extract their 10-base values from a shorter sequence in the spigot (or many similar) algorithms.

There are other bases that have this feature as well but less obvious, like 16-base. We have this equation that allows extracting 16-base digit without extracting any other previous digit. This does not say that we are completely ignoring all of them since we still need to calculate modulo operation for all more larger and larger number.

$$\pi=\sum\limits_{k=0}^{\infty}\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})$$

Of course, it is not purely about a formula, it is about the complexity of operations involved too.

All more and more we are becoming aware that the digits of $\pi$ are part of a complicated chaotic system. In that sense we can talk about "being random" regarding $\pi$ in the sense of "being feasible to evaluate".

Now, we will write the equations taking all $\mod 1$ and sometimes thinking in base $3$

$$\{(3+\{\pi\})^k\}\stackrel{\mod 1}{=}\sum\limits_{k=0}^{n-1} \{\binom{n}{k} 3^{k} \{\pi\}^{n-k} \}$$

Look what we have. For small $k$, we will have large $n-k$ and this will push $\{\pi\}^{n-k}$ farther from decimal point, so it will have less effect on the distribution. $3^k$ is not going to help much, it will shift the value (if we are looking at base $3$, just for the sake of making it all more obvious) few places towards the decimal point. So if we assume that $\{\pi\}^{k}$ is becoming all more and more random, its influence is not going to be felt immediately.

On the other hand, if we have large $k$, we have most dominant $3^k$ part that is going to shift the value and include deeper digits from $\{\pi\}^{n-k}$, those that we expect to be more "random" based on the normality of $\pi$. But even that is not going to happen immediately.

So, if we have any chance for good randomness, we have to wait a little bit all initial conditions and values to mangle first. If we would have only first 20 digits of $\pi$, we would not be able to say anything about the quality of their randomness, because a sample would be too small. As we are running deeper, they start to exhibit properties of a normal number. Knowing that first few digits are related to the simple series is the reason to treat them as kind of less random.

Another problem is that there is a deeper connection that does not vanish between terms. These discovered connections are reducing the total randomness. More expressions we have, shorter they are, and the randomness is all more and more gone.

$$1+\pi+\pi^2+...+\pi^n=\frac{\pi^{n+1}-1}{\pi-1}=\frac{1}{\frac{1}{\pi^{n}}-\frac{1}{\pi^{n+1}}}-\frac{1}{\pi-1}=H_{d}(\pi^{n},\pi^{n+1})-\frac{1}{\pi-1}$$

where $H_{d}$ is harmonic difference. Put two of these together and you have:

$$H_{d}(\pi^{n-1},\pi^{n})-\frac{1}{\pi-1}+\pi^n=H_{d}(\pi^{n},\pi^{n+1})-\frac{1}{\pi-1}$$

which is

$$ \{\pi^n \}= \{ \{H_{d}(\pi^{n},\pi^{n+1})\}-\{H_{d}(\pi^{n-1},\pi^{n})\} +1 \}$$

From here it turns out that our distribution is equal to the differences between two terms of another harmonic like distribution that involves the same constant $\pi$. This harmonic game is the actual mixer or at least it gives the idea what mixing process involves. And it reveals that the mixing process is not that strong. It takes two close values which contain similar amount of "randomness" and mix them. That way, it cannot improve much above them. This is saying as much about $\{\pi^n \}$ as much $\{\pi^{n+1} \}$. The random mixture might get in, but slowly although our tests are not able to detect a specific effect on some elements of this slower than desired mixture.

Mixers are part of many mathematical random generators we have devised, and with that many encryption algorithms. In that sense, if we take $\{\pi^k\}$ as a generator of random numbers, it is not a good one. This is what we have before taking fractional part for example:

$$ k(n+1) = \frac{k(n)^2}{k(n-1)}$$

The randomness of this sequence depends on its ability to mix values as much as on the two initial values needed, which are in our case $1$ and $\pi$. Although Knuth is suggesting using sufficient number of initial digits of $\pi$ for random seed in a couple of his polynomial type of random generators, because they exhibit nice random properties, the expression for random mixture is not as trivial as $x^k$.

To illustrate this I will show a distribution of constants (real part) for FFT, Fast Fourier transformation, for $\{\pi^k\}$ first 1000 terms and for 1000 random values.

Random values have a nice bell curve

1000 random values

$\{\pi^k\}$ are not there yet

Distribution for power of $\pi$

  1. There are two theorems that will help deciding about this power series. One is Weyl's saying about the condition that any series is equidistributed, and another Hardy and Littlewood saying that power series (like ours) with almost all real numbers (almost all means with some exceptions like integers, golden ratio and so on) is equidistributed.

So, we are either within almost all or we are an exception.

Weyl is saying to calculate for all positive integers $p$ this and to check if the limit tends to $0$.

$$\lim\limits_{m \to \infty} \frac{1}{m} \sum\limits_{n=1}^{m} e^{2\pi i p \pi^n}$$

We will satisfy ourselves with calculating real part of it, for $p=1$ and without reciprocal.

$$\sum\limits_{n=1}^{m} \cos(2\pi^{n+1})$$

Without further ado here is the plot for $n<1000$. The sum stays well beyond $n$ so if we divide it as the limit requires it will probably start reaching $0$. We do know that most of the numbers are normal in this sense, but we have a strong headache when we try to resolve any single one of them like $\pi^n$ or $e^n$.

Even if we ignore this and take that it is equidistributed, do not use $\{\pi^n\}$ as a random generator in interval $(0,1)$. It will not pass various random tests.

Weyl's criterion for $\pi$ power sequence

$\endgroup$
  • 2
    $\begingroup$ "First few digits of $\pi$ are by no means random or normal. They are very precise..." I don't quite get that remark. It seems to suggest that the first (say) ten digits of $\pi$ are "less random" that (say) the first ten digits after the millionth. $\endgroup$ – leonbloy Feb 13 '16 at 13:57
  • 2
    $\begingroup$ Sorry, I cannot make sense of that. Could you elaborate (or pass some reference) on why the digits 1001-1005 have "better random features" than the digits 1-5 ? $\endgroup$ – leonbloy Feb 13 '16 at 14:14
  • 1
    $\begingroup$ Please undelete your answer, it was very interesting. $\endgroup$ – YoTengoUnLCD Feb 13 '16 at 21:05
  • 1
    $\begingroup$ If you look into a spigot algorithm you can see that you get first few digits from 2+1/3(2+2/5(... and then the next 2+1/3(2+2/5(2+3/7.... These two expressions are defining digits. In that sense among them there is a simpler connection in precise sense that you need shorter sequence and less numbers to find them. $\endgroup$ – user195934 Feb 15 '16 at 14:55
  • 1
    $\begingroup$ @JaumeOliverLafont: That would be one of the possible measures. It is all about the complexity of an algorithm that would effectively compute first few digits comparing to the effective computation of any other later digit. We can find 314 again somewhere in the expansion later, but to effectively compute that another appearance of 314 we need more time and computing power. So together with what you have mentioned, you need to add the complexity of whatever operation is used with some mathematically proven or suspected maximum efficiency of it. Spigot is witnessing all that by its shape. $\endgroup$ – user195934 Feb 15 '16 at 20:26
8
$\begingroup$

It's mentioned here that the sequence $x^n$ ($n=1,2 \cdots$) in modulo $1$ is known to be uniformly distributed for almost every $x>1$. At the same time, and perhaps surprisingly, not even a single example has been discovered - only some exceptions (and all algebraic). Furthermore, it has been proved (see same reference) that the "exceptions", in spite of having Lebesgue measure zero, are uncountable (hence they must include trascendental numbers).

I didn't find anything about the particular case $x=\pi$, neither about what happens with the distribution of the fractional parts (do they concentrate around $0$?) in the non-uniform exceptional cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.