Skip to main content
MathOverflow

Return to Question

see last paragraph added at the bottom, featuring a theorem closely related to my discussion
Source Link
Vincent Granville
Vincent Granville
  • 3.1k
  • 8
  • 21

Edit: A related result for convergents $p_n/q_n$ of continued fractions is the following (it is the last theorem in this article, and pictured below):

enter image description here

In short, it seems to imply that if $\lambda=1+\epsilon$ with $\epsilon = 0$, then only some proportion of all numbers $\alpha$ will satisfy $q^\lambda |q\alpha-p|\geq 1$, where $p/q$ is any rational approximation to $\alpha$ with $p,q$ coprime positive integers. With $\epsilon > 0$, almost all $\alpha$ will. Note that in the above theorem, my number $\alpha$ is denoted as $x$.

Edit: A related result for convergents $p_n/q_n$ of continued fractions is the following (it is the last theorem in this article, and pictured below):

enter image description here

In short, it seems to imply that if $\lambda=1+\epsilon$ with $\epsilon = 0$, then only some proportion of all numbers $\alpha$ will satisfy $q^\lambda |q\alpha-p|\geq 1$, where $p/q$ is any rational approximation to $\alpha$ with $p,q$ coprime positive integers. With $\epsilon > 0$, almost all $\alpha$ will. Note that in the above theorem, my number $\alpha$ is denoted as $x$.

Source Link
Vincent Granville
Vincent Granville
  • 3.1k
  • 8
  • 21

Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)

If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are looking for successive runs of increasing lengths, or in other words, successive run records of the digit $0$, their respective (increasing) lengths, and the position where they occur in the base $b$ expansion of the numbers in question.

It is a probability question where a theoretical distribution is sought, not just for numbers like $\pi$ but for numbers with random digits or even strings of random characters (the digits or characters being uniformly and independently distributed). So it can be of interest for mathematicians interested in combinatorics. In my case, my interest is in the asymptotics related to approximating irrational numbers by rational ones, and in particular, by dyadic fractions.

I did some simulations, and my empirical results are consistent with what has been observed for the digits of (say) $\pi$. My simulations are summarized in the illustration below. I created 200 artificial numbers with same properties as $\pi$ (as far as the digit distribution in base $b=3$ is concerned), looking at the first million digits, with $b=3$. For one of them (a typical case), I've found this:

  • One isolated zero (the first occurrence of zero) starts at position 3
  • The first run of 2 zeros starts at position 13 in the digits expansion
  • The next longer run consists of 3 zeros, starting at position 69
  • The next longer one (4 zeros) starts at position 132
  • Then we have 5 zeros starting at position 670, then six starting at position 743, 8 starting at position 13411, 10 starting at position 58454, and 12 starting at position 384100.

The observations can be summarized by the following bivariate sequence: $$(3, 1), (13,2), (69, 3), (132, 4), (670,5), (743,6), (13411, 8), (58454, 10), (384100, 12), \dots $$

Now repeat the process for a very large set of numbers and blend all the sequences of vectors $(X,Y)$ together. We have, as I expected, the following very good approximation: $$Y=\log_b \bar{X}$$ where $\bar{X}$ is the average $X$ corresponding to a specific, fixed $Y$, computed on all the numbers in your sample.

Question: I am looking at the distribution of $\log X$, conditionally to $Y$. Is it Gaussian? If not what are the asymptotics?

Connection to approximations of irrationals by rational numbers

Here, the rational numbers in question are of the form $\frac{p_n}{q_n}$ with (for now), $q_n=3^n$. But there are strong analogies with best approximations or approximations with convergents of continued fractions. A best approximation for an irrational $\alpha \in [0, 1]$, in my case, occurs when the first $n$ digits end with non-zero, followed by a record run of zeros, thus the purpose of my above question. If that record run is of length $r_n$, we have $$\alpha-\frac{p_n}{q_n} \geq \frac{1}{q_{n+r_n}}$$ My simulations suggest that $r_n = b^{\lambda n} \sim q_n^\lambda$ makes sense. When you put things together, it ends up with something like this: $$S(\alpha)\equiv q^\lambda (q\alpha - p)\geq 1$$ for a large proportion of $\alpha\in[0,1]$. That proportion can be computed with as much accuracy as desired. The larger $\lambda$, the more irrationals can be approximated that way. It sounds that $\lambda>1+\epsilon$ is good enough, and maybe $S(\alpha)\equiv q \cdot (\log q) \cdot (q\alpha - p)$ can be used to define the rational part of an irrational number in the above context: find $p,q$ that minimizes $S(\alpha)$ and then the "best" (in some way) approximation of $\alpha$ by a rational is that $p/q$ achieving the minimum. For more details about my earlier investigations about this, see my previous MO question, here.