Consider irrational numbers between 1 and 9.

Lets call a specific one $a$. Let $n>0$ be an integer.

In decimal consider the first $n$ digits of $a$. Call that string $A(a,n)$. Now consider the next $n$ digits of $a$ after the first $n$. Call that string $B(a,n)$.

Define $a$ has the repeat digits property (rdp) iff :

$$A(a,n) = B(a,n) $$

For some $n$. Also $rdp(a) = $ true.

Now it is tempting to think statistically about this. What is the probability that $rdp(a) =$ true ? And probably that probability is equal to

$$ 10^{-1} + 10^{-2} + 10^{-3} + ... = 1/9 $$

Or close to it. Is that correct ??

However i wonder about actual proofs rather than statistical reasoning.

So I make a conjecture

There exists NO $n$ such that

$$ A(\pi,n) = B(\pi,n)$$

Now i picked the number $\pi$ because we know alot about its digits. ( unlike say zeta(5) , euler gamma etc , in fact we are not even sure they are irrational ! ) For instance we can compute the 100000 th digit in base 16 without needing to store or compute all the previous ones.

. See https://en.m.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula

So how to handle this ??

Or is this one of the simplest undecidable problems ?

Or the simplest example of computational irreducibility ? ( see wolfram's book a new kind of science ).

Is there any hope of solving they things besides brute force Search and luck ?

Is this THE example of the ultimate halting problem ?

  • 1
    $\begingroup$ It is widely beliefed that $\pi$ is normal, in particular contains every finite string of digits. But we do not even know of any digit, whether it occurs infinite many often in $\pi$. There is a possibility that eventually $\pi$ ends with $001110011010\cdots $ and only zeros and ones are following. $\endgroup$ – Peter Mar 1 '17 at 18:43
  • 1
    $\begingroup$ I do not think that we can find out in near future whether the problem of occuring digits in irrational numbers is decideable or not. We simply do not know enough about this stuff, so we can only guess and point out the evidence we have with the digits already calculated. $\endgroup$ – Peter Mar 1 '17 at 18:46
  • 1
    $\begingroup$ If I remember right, every string of digits of length $11$ or less is known to occur in $\pi$. Apparantly because of this, many mathematicians believe that $\pi$ is normal. $\endgroup$ – Peter Mar 1 '17 at 18:47
  • $\begingroup$ @Peter: That does not really help resolve this problem (except as an example of we don't really know anything about the behavior of the digits of $\pi$). $\endgroup$ – Henning Makholm Mar 1 '17 at 18:47
  • $\begingroup$ I did not claim that we can resolve the problem. $\endgroup$ – Peter Mar 1 '17 at 18:48

I believe your conjecture is open, but here are some partial results:

Let $a$ be defined to have the infinitely-often-repeating-digits property (IORDP) if there are infinitely many values of $n$ such that $A(a,n) = B(a,n)$.

If $a$ has IORDP, it has irrationality measure at least $2$. That's because in the repeat-digits cases we can match the first $2 \cdot n$ digits of $a$ with a fraction whose denominator only has $n$ digits (all $9$'s). This isn't very helpful since every irrational number has irrationality measure at least $2$. (However, irrationality measure is defined as an infimum so maybe it is possible to strengthen this to a strict inequality?)

But, we can define the infinitely-often-twice-repeating-digits property (IOTRDP) to mean that there are infinitely many $n$ with $A(a,n) = B(a,n) = C(a,n)$ where $C$ is the third sequence of $n$ digits. If $a$ has IOTRDP, then it has irrationality measure at least $3$. So one thing we can say is that algebraic numbers like $\sqrt{2}$ do not have IOTRDP.

And since $\pi$ is known to have an irrationality measure less than $8$, we can be sure that only finitely often is it the case that the first $n$ digits of $\pi$ repeat $8$ times. But this is not enough to establish that any particular number of repetitions of the initial digit sequence of $\pi$ never occurs.

Also, there is a relationship between irrationality measure and the runtime analysis of digit-extraction algorithms like BBP. Although the expected number of summands for BBP to extract the $n^{th}$ nybble is $n+O(1)$, we can't rule out the existence of cases where it requires more than $7 \cdot n$ terms, i.e. the first $n$ nybbles of $\pi$ are followed by more than $6 \cdot n$ $0$'s or $f$'s. This doesn't affect the asymptotic runtime of BBP since it's a constant factor but it means maybe there are digits that take more than seven times as long as typical ones to extract.


Not an answer but here are a couple thoughts that are too long for a comment:

Your calculation of the probability rdp(a) is true is not quite right. You are over counting numbers that satisfy the condition for multiple values of $n$. For example $.1111$ satisfies the condition for both $n=1$ and $n=2$. In any case what you computed is an upper bound, and $1/10$ is trivially a lower bound.

You can rewrite rdp(a)being true as $10^na-a - \lfloor10^na-a\rfloor < 10^{-n}$ for some $n$ so $a - K/(10^n-1) < \frac{1}{10^n(10^n-1)}$ which is reminds me of diophantine approximation, perhaps something can be said in that direction.


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.