1

So, I've wondered if there are irrationals where I can calculate some digit $n\in\mathbb{N}$ when given only the $k_n\in \mathbb{N}_0$ ($k_n<n-1$) digits before them. Preferrably $k_n\in o(n)$.

I think this is one of the problems which is easy to state but hard to answer.

So of course, if $k_n$ would be positive and fixed, this is just asking when digits of an irrational can be expressed as a recurrence relation $(d_n)$ with recursion depth $k$ (as pointed out in the comments, with fixed $k$ such a number would always be rational). And of course there are infinite examples where the digit sequence can be easily described, e.g. the Louville number $\sum 10^{-\ell!}$ ($d_n=1$ if and only if $n=\ell!$ for some $\ell\in\mathbb{N}_0$, else $d_n=0$, so $k_n=0$), the 123...-Sequence (slightly more complicated closed form) and any multiple of them.

So I'm asking: Do you know any irrational that wasn't (more or less) defined by a digit sequence but turned out to have (a relatively easy) one?

By "more or less" I mean that I count the 123...-Sequence to the obvious ones. By "relatively easy" I mean any formula that isn't cheating the question. E.g. "$\pi$ has the digit sequence that describes the digits of $\pi$" is not helping, writing $$d_n (\pi) = \left\lfloor 10^n \pi\right\rfloor - 10\left\lfloor 10^{n-1} \pi\right\rfloor$$ or substituting $\pi$ by a formula evaluating to it in one of the two is not helping either and not in the spirit of the question. The irrational number should not be used in the formula.

EDIT: Through a related question I found the promising article On the rapid computation of various polylogarithmic constants from David Bailey, Peter Borwein and Simon Plouffe in which they describe an algorithm for finding any digit of a number of the form $$\sum_{\ell=0}^\infty \frac{p(\ell)}{b^{c\ell}q(\ell)}$$ where $p$ and $q$ are polynomials and $c$ is a positive integer. They also show that $\pi$, $\pi^2$, $\log(2)$ and $\log^2(2)$ happen to be of this form. If their $\frac{p(\ell)}{q(\ell)}$vwould always be nonnegative integers, they would form the desired examples, but from what I understand from the paper it is not so easy. I want something more substantial than simple computability.

SK19
  • 3,121
  • 1
    Suppose you have a real number $\sum_{n=1}^{\infty} a_n10^{-n}$ with digits $a_n \in {0, 1, ..., 9}$ and described by $a_n = f(a_{n-1}, ..., a_{n-k})$ (for $n>k$) for some fixed integer $k>0$ and some function $f$ that takes values in ${0, 1, ..., 9}$. Regardless of the initial seed $a_1, .., a_k$, this always produces a sequence ${a_n}{n=1}^{\infty}$ that is eventually periodic, and so the number $\sum{n=1}^{\infty} a_n 10^{-n}$ is rational. And the irrational number $\sum_{n=1}^{\infty} 10^{-n!}$ cannot be described this way. – Michael Dec 29 '17 at 12:38
  • 1
    @Michael Good thought, reference for proof? However, in my question, $k$ doesn't need to be fixed. – SK19 Dec 29 '17 at 12:47
  • @Michael But I realized that my question was misleading. I hope to have fixed that. – SK19 Dec 29 '17 at 12:51
  • 1
    So, you want an irrational number with a predictable sequence of digits but one that can be derived in some more natural way as well? – badjohn Dec 29 '17 at 13:27
  • Those are exactly the computable real numbers. Look at Liouville numbers if you want example of algorithms generating digits of irrational numbers. The Chaitin constant is the best known example of definable but non-computable real number. $o(k_n)$ doesn't make any sense. If you meant the algorithm enumerating the digits has a polynomial complexity, then we can give examples but I don't think we can say much in general, as it can be unprovable that the algorithm is polynomial even if it is. – reuns Dec 29 '17 at 13:31
  • @badjohn Basically, yes. – SK19 Dec 29 '17 at 13:51
  • @reuns It is $o(n)$. I mean that preferably the number of digits preceding $n$ should be sublinear in terms of $n$. For example, digit $10$ needs digit $9$, digit $100$ needs digits $98$, $99$ etc. (logarithmic example). However, saying that there is an algorithm is too broad. I would be fine with expressing the digits in terms of functions that need numerical evaluation, as long as you don't define functions specificly to answer this question. – SK19 Dec 29 '17 at 14:10

1 Answers1

1

Here are more details on my comment: We want to construct a sequence $\{a_n\}_{n=1}^{\infty}$, where $a_n \in \{0, 1, ..., 9\}$ for all $n$, and understand whether or not $\sum_{n=1}^{\infty}a_n 10^{-n}$ is rational.

Recall that $\sum_{n=1}^{\infty} a_n 10^{-n}$ is rational if and only if $\{a_n\}$ is eventually periodic (so that periodic behavior starts after some transient). An eventually periodic sequence has the general form: $$ \{a_n\}_{n=1}^{\infty} = \{\underbrace{b_1, b_2, …, b_r}_{\mbox{transient}}, c_1, c_2, …, c_m, c_1, c_2, …., c_m, c_1,c_2, …, c_m, …\} $$ where $m$ is the size of the period.

Homogeneous constructions with depth $k$

Fix $k$ as a positive integer. Initialize $a_1, ..., a_k$ as any values in $\{0, 1, ..., 9\}$ and define $$ a_n = f(a_{n-1} ,a_{n-2} , ..., a_{n-k}) \quad, \forall n \in \{k+1, k+2, ...\} $$ where $f$ is any function that takes values in $\{0, 1, ..., n\}$, formally, $$ f:\{0, 1, ..., 9\}^k \rightarrow \{0, 1, ..., 9\} $$

Claim: The resulting sequence $\{a_n\}_{n=1}^{\infty}$ is eventually periodic and so $\sum_{n=1}^{\infty} a_n 10^{-n}$ is rational.

Proof: There are only $10^k$ possible sequences of length $k$ with elements in $\{0, 1, ..., 9\}$. So eventually the infinite sequence $\{a_n\}$ must repeat some particular length-$k$ sequence, say, $c_1, c_2, ..., c_k$. This sets up the same initial conditions for the recursion, and so the $\{a_n\}$ sequence repeats its behavior periodically forever thereafter with occurrences of $c_1, ..., c_k$ acting as "renewals" that start a new period: $$ \{a_n\} = \{\underbrace{b_1, b_2, ..., b_r}_{\mbox{transient}}, \underbrace{c_1, ..., c_k}_{\mbox{renewal}}, ..., \underbrace{c_1, ..., c_k}_{\mbox{renewal}}, ..., \underbrace{c_1, ..., c_k}_{\mbox{renewal}}, ...\} \quad \Box $$

Inhomogeneous constructions with depth $k$

Again initialize $a_1, ..., a_k$ as any values in $\{0, 1, ..., 9\}$. Consider the modified construction $$ a_n = f_n(a_{n-1}, a_{n-2}, ..., a_{n-k}) \quad, \forall n \in \{k+1, k+2, ...\} $$ The difference here is that the function $f_n$ can change with $n$. Here it is easy to construct an irrational number. We can even do it with a "depth $0$" function that depends only on $n$: $$ a_n=f_n = \left\{ \begin{array}{ll} 1 &\mbox{ if $n$ is a perfect square} \\ 0 & \mbox{ otherwise} \end{array} \right.$$ The resulting $\{a_n\}$ sequence consists of only 0s and 1s and the duration between 1s increases (linearly), so the sequence is not eventually periodic and $\sum_{n=1}^{\infty} a_n 10^{-n} = \sum_{i=1}^{\infty} 10^{-i^2}$ is irrational. In fact you have already done something similar by a function that defines $a_n=f_n=1$ if and only if $n=m!$ for some integer $m$ (and $a_n=0$ else), which constructs $\sum_{i=1}^{\infty} 10^{-i!}$.

Michael
  • 23,905
  • Note: There are $10^{(10^k)}$ such functions $f:{0, 1, ..., 9}^k \rightarrow {0, 1, ..., 9}$. – Michael Dec 29 '17 at 19:53
  • Isn't the argument "there are only $K$ such functions, so the sequence must be eventually periodic" the same as "there are only 10 digits, so any number must be eventually periodic", leading to the infamous wrong argument that there are no irrational numbers? – SK19 Dec 29 '17 at 23:53
  • I do not know what infamous argument you are talking about. But, my above comment on $10^{(10^k)}$ such functions $f$ was only a side note that has nothing to do with the above claim about eventually periodic behavior. That claim uses only one given function $f$, and uses the pigeonhole principle that, since there are only a finite number of sequences of length $k$, any infinite length sequence must have repetitions of the same length-$k$ sequence. Indeed, just chop the infinite sequence into blocks of size $k$: Eventually one of the blocks must have exactly the same values as a predecessor. – Michael Dec 30 '17 at 01:02
  • 1
    As an experiment, consider an infinite binary-valued (0/1) sequence and look at strings of length $k=2$. It is impossible to write down a string of 10 bits without repeating a length-2 sequence somewhere, example $$ 01\underbrace{10}00\underbrace{10}11 $$ (I consider 10-bit sequences since we can chop them into 5 blocks of size 2, at least one of the blocks must be the same as another.) Likewise, for any finite alphabet and any positive integer $k$, for any infinite sequence of alphabet symbols, there must exist a $k$-length string that appears multiple times. – Michael Dec 30 '17 at 01:15
  • Okok, I see I overread the "..." between the blocks in the answer above. Then it makes sense. Btw, the infamous argument was this one: https://math.stackexchange.com/questions/2300067/irrational-numbers-impossible?rq=1 – SK19 Dec 30 '17 at 09:14
  • I do not understand that link. It talks of "reducing the chances" (the chances of what?) and "the right number" (what does this mean?). I was hoping that link would give an argument that is interesting but has a subtle flaw, instead it just does not make sense at all. – Michael Dec 30 '17 at 13:07
  • A better link that gives a followable (but of course incorrect) "proof" that irrationals do not exist is here: https://math.stackexchange.com/questions/365200/non-existence-of-irrational-numbers – Michael Dec 30 '17 at 14:15
  • Infamous argument in the sense of "when they repeat forever, at some point a pattern just has to emerge". Something I've heard quite a few times from non mathematicians. That question was just one like that and the first I encountered when writing this question. – SK19 Dec 31 '17 at 21:56
  • Ah, I just now noticed your edit on the inhomogenous part. I like it very much and wish I could upvote it more than once, but my question still stands: Is there an irrational number that turned up before someone figured out its "easy" digit sequence? From my perspective you first constructed the number via sequence and then showed it is irrational, I want it the other way around. Do you know how I can clarify my post in regard to this? It seems I'm misunderstood. – SK19 Feb 20 '18 at 05:51
  • I don't know. The famous irrationals are $\sqrt{2}, e$, and $\pi$ (though I only know how to prove $\sqrt{2}$ and $e$ are irrational, I take that $\pi$ is irrational on faith). They all have "difficult" decimal expansions. – Michael Feb 20 '18 at 06:40