Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Any number less than 1 can be expressed in base g as $\sum _{k=1}^\infty {\frac {D_k}{g^k}}$, where $D_k$ is the value of the $k^{th}$ digit. If we were interested in only the non-zero digits of this number, we could equivilantly express it as $\sum _{k=1}^\infty {\frac {C_k}{g^{Z(k)}}}$, where $Z(k)$ is the position of the $k^{th}$ non-zero digit base $g$ and $C_k$ is the value of that digit (i.e. $C_k = D_{Z(k)}$).

Now, consider all the numbers of this form $(\sum _{k=1}^\infty {\frac {C_k}{g^{Z(k)}}})$ where the function $Z(k)$ eventually dominates any polynomial. Is there a proof that any number of this form is transcendental?

So far, I have found a paper demostrating this result for the case $g=2$; it can be found here: http://www.escholarship.org/uc/item/44t5s388?display=all

share|improve this question
4  
This was also posted on MSE: math.stackexchange.com/questions/6321/… . –  Joseph O'Rourke Oct 9 '10 at 16:37
2  
Roth's theorem. –  Felipe Voloch Oct 9 '10 at 17:05
7  
Roth's theorem implies that it is transcendental if $Z(k+1)>(2+\epsilon)Z(k)$ infinitely often. Unfortunately, Z(k) eventually dominating any polynomial is not sufficient to guarantee this. Even $Z(k)=2^k$ doesn't grow fast enough for Roth's theorem to apply. –  George Lowther Oct 9 '10 at 17:23
8  
But the $p$-adic version of Roth's theorem (due to Ridout in the version one needs here) does the trick if $Z(k+1) > (1+ \epsilon) Z(k)$ infinitely often and, in particular for $Z(k)=2^k$. –  Mike Bennett Oct 9 '10 at 22:24
2  
I see the correct theorem now. The paper is Rational approximations to algebraic numbers (dx.doi.org/10.1112/S0025579300001182). Not free access, but it is quoted in An explicit version of the theorem of Roth-Ridout (seminariomatematico.dm.unito.it/rendiconti/cartaceo/53-3.html) Theorem 2 (Ridout's theorem). This does indeed do the job! Many thanks for that. In fact you only need the denominators to have factors from some finite set of primes, which covers Z(k) growing exponentially and any base. Still, the case for Z(k) merely dominating any polynomial seems to be open. –  George Lowther Oct 11 '10 at 1:25

2 Answers 2

up vote 15 down vote accepted

I don't know of a paper proving the result, but I can prove it for you now. In fact, the methods in the paper you link generalize to an arbitrary base $g\gt2$. The authors of the paper don't seem to think that it generalizes quite so easily, as in the Open Problems section they state that "For bases $b\gt2$ there is the problem of having more than two possible digits. What kinds of bounds might be placed on counts of 1's and 2's for ternary expansions of algebraic numbers?". Hopefully I have not made any major mistakes...

[Edit: A paper by Bugeaud, On the b-ary expansion of an algebraic number, available from his homepage gives lower bounds on the number of nonzero digits in an irrational algebraic number. There, he references the paper linked in the question, saying "Apparently, their approach does not extend to a base $b$ with $b\ge3$". However, he has just responded to this question, agreeing that the method does indeed generalize. So I'm more confident about my proof now.]

Use $\#(x,N)$ to denote the number of nonzero base-$g$ digits in the expansion of $x$, up to and including the $N$'th digit after the 'decimal' point, then what you are asking for is implied by the following.

If $x$ is irrational and satisfies a rational polynomial of degree $D$ then $\#(x,N)\ge cN^{1/D}$ for a positive constant $c$ and all $N$.

First, I'll introduce some notation similar to that used in the linked paper. Use $r_1(n)$ to denote the $n$'th base-$g$ digit of $x$, so that $0\le r_1(n)\le g-1$ and $$ x=\sum_nr_1(n)g^{-n}. $$

It's enough to consider $1\le x\lt2$, so I'll do that throughout. Then $r_1(n)=0$ for $n\lt0$ and $r_1(0)=1$. Also use $r_d(n)$ to denote $$ r_d(n)=\sum_{p_1+p_2+\cdots+p_d=n}r_1(p_1)r_1(p_2)\cdots r_1(p_d)=\sum_{j+k=n}r_1(j)r_{d-1}(k) $$ This satisfies the inequalities $r_d(n)\ge r_1(0)r_{d-1}(n)=r_{d-1}(n)$ and $$ \sum_{n\le N}r_d(n)\le(g-1)^d\#(x,N)^d\le(g-1)^d(N+1)^d.\qquad\qquad{\rm(1)} $$ Also, raising $x$ to the $d$'th power gives $$ x^d=\sum_nr_d(n)g^{-n}, $$ which differs from the base $g$ expansion of $x^d$ only because $r_d(n)$ can exceed $g$. We also introduce notation for the expansion of $x^d$ with the digits shifted to the left $R$ places and truncated to leave the fractional part, $$ T_d(R)=\sum_{n\ge1}r_d(R+n)g^{-n}, $$ so that $g^Rx^d-T_d(R)$ is an integer. This can also be bounded, using (1), $$ \begin{array}{rl} \displaystyle T_d(R)&\displaystyle\le\sum_{n\ge1}(g-1)^d(R+n+1)^dg^{-n}\\ &\displaystyle\le\sum_{n\ge1}(g-1)^d(R+1)^d(n+1)^dg^{-n}\\ &\displaystyle\le C_d(R+1)^d \end{array} $$ where $C_d=\sum_{n\ge1}(g-1)^d(n+1)^dg^{-d}$ is a constant independent of $R$.

Now suppose that $x$ satisfies an integer polynomial of degree $D\gt1$, $$ A_Dx^D+A_{D-1}x^{D-1}+\cdots+A_1x+A_0=0 $$ with $A_D\gt0$. It follows that $$ T(R)\equiv\sum_{d=1}^D A_dT_d(R) $$ is an integer for each $R$. The following is similar to Theorem 3.1 in the linked paper.

Lemma 1: For all sufficiently large $N$, there exists $n\in(N/(D+1),N)$ with $r_1(n)\gt0$.

Proof: This is a consequence of Liouville's theorem for rational approximation. If the statement was false then setting $m=\lfloor N/(D+1)\rfloor$, $p=\sum_{n=0}^mr_1(n)g^{-n}$, $q=g^{m}$ gives infinitely many approximations $\vert x-p/q\vert=q^{-D}o(1)$ as $N$ increases, contradicting Liouville's theorem.

In Lemma 1, Roth's theorem could have been used to reduce the $D+1$ term to $2+\epsilon$. In fact, Ridout's theorem as discussed in the comments can be used to reduce it even further to $1+\epsilon$. This isn't needed here, so I just used the more elementary Liouville's theorem.

Lemma 6.1 from the linked paper generalizes to base $b$, and puts upper bounds on the number of times at which $T(n)$ can be nonzero.

Lemma 2: For large enough $N$, setting $K=\lceil 2D\log_g N\rceil$ gives $$ \sum_{1\le R\le N-K}T_d(R) < (g-1)^{d-1}\#(x,N)^d+1 $$ for $1\le d\le D$ and so, $$ \sum_{1\le R\le N-K}\vert T(R)\vert\le\sum_{d=1}^D\vert A_d\vert ((g-1)^{d-1}\#(x,N)^D+1) $$

Proof: Using similar inequalities to the proof used in the linked paper, $$ \begin{array}{rl} \displaystyle\sum_{1\le R\le N-K}T_d(R) &\displaystyle=\sum_{m\ge1}g^{-m}\sum_{R\le N-K}r_d(R+m)\\ &\displaystyle\le\sum_{m=1}^Kg^{-m}\sum_{R\le N}r_d(R)+g^{-K}\sum_{m > K}g^{K-m}\sum_{R\le N-K}r_d(R+m)\\ &\displaystyle \le \frac{1}{g-1}\sum_{R\le N}r_d(R)+g^{-K}\sum_{K\le R\le N}T_d(R)\\ &\displaystyle\le(g-1)^{d-1}\#(x,N)^d+g^{-K}NC_d(N+1)^d. \end{array} $$ The final term is bounded by $C_d(N+1)^{d+1}/N^{2D}$ which will be less than 1 for $N$ large.

Lemma 6.2 also generalizes, which gives blocks where $T(R)$ is nonzero.

Lemma 3: Let $R_1\lt R_2$ be positive integers with $r_{D-1}(R)=0$ for all $R\in(R_0,R_1]$ and $T(R_1)\gt0$. Then $T(R)\gt0$ for all $R\in[R_0,R_1]$.

Proof: We have the following relation for $T$, $$ T(R-1)=\frac{1}{g}T(R)+\frac{1}{g}\sum_{d=1}^D A_dr_d(R). $$ As $r_d(n)\ge r_{d-1}(n)$, the hypothesis implies that $r_d(R)=0$ for all $1\le d\le D-1$ and $R\in(R_0,R_1]$. Therefore, $$ T(R-1)=\frac{1}{g}T(R)+\frac{1}{g}A_Dr_D(R)\ge \frac{1}{g}T(R). $$ Assuming inductively that $T(R)\gt0$ gives $T(R-1)\gt0$.

Putting this together gives the result (Theorem 7.2 in the linked paper).

Theorem 4: There is a constant $c$ such that, for all sufficiently large $N$ $$ \#(x,N)>cN^{1/D} $$

Proof: Suppose not, then for any $\delta\gt0$, there are infinitely many $N$ with $\#(x,N)\lt\delta N^{1/D}$ and, using (1), $$ \sum_{n\le N}r_{D-1}(n)\le \delta N^{1-1/D}\qquad\qquad{\rm(2)} $$ In particular, the proportion of integers $R$ with $r_{D-1}(R)\gt0$ goes to $0$. Let $0=R_1\lt R_2\lt\cdots\lt R_M\le N$ be those integers in the range $[0,N]$ with $r_{D-1}(R_k)\gt0$ and set $R_{M+1}=N$. Then (2) gives $M+1\le\delta N^{1-1/D}$, and $r_d(R)=0$ for $d\le D-1$ and $R$ in any of the ranges $(R_i,R_{i+1})$. So, $T_d(R-1)=g^{R-R_{i+1}}T_d(R_{i+1}-1)$.

Fixing $\epsilon\gt0$ and letting $I$ denote the numbers $i$ with $R_{i+1}-R_i\gt\epsilon N^{1/D}$ gives $$ \sum_{i\in I}(R_{i+1}-R_i)\ge N - (M+1)\epsilon N^{1/D}\ge N(1-\epsilon \delta). $$ So, the intervals $(R_i,R_{i+1})$ larger than $\epsilon N^{1/D}$ cover most of the interval $[0,N]$, as long as $\epsilon\delta$ is small enough.

If $R$ is in the range $(R_i,R_{i+1}-D\log_gN)$ and $r_D(R)\gt0$ then $T(R-1)\gt0$: $$ T(R-1)\ge \frac{1}{g}A_D-g^{R-R_{i+1}}\sum_{d=1}^{D-1}\vert A_d\vert T_d(R_{i+1}-1) \ge\frac1g-N^{-D}\sum_{d=1}^{D-1}\vert A_d\vert C_d R_{i+1}^d $$ which is positive, so long as $N$ is chosen large enough.

Assuming that $N$ is large enough, by Lemma 1, for each $i$ in $I$, there is $$ j\in\left(\frac{1}{D+1}(R_{i+1}-R_i-D\log_gN),R_{i+1}-R_i-D\log_gN\right) $$ with $r_1(j)\gt0$. Then, $r_D(R_i+j)\ge r_{D-1}(R_i)r_1(j)$ is positive, so $T(R_i+j-1)\gt0$. Lemma 3 implies that $T(R_i+j)$ is positive for all $0\le j\lt(R_{i+1}-R_i-D\log_gN)/(D+1)$. $$ \sum_{1\le n< N-2D\log_g N}\vert T(n)\vert\ge\frac{1}{D+1}\sum_{i\in I}(R_{i+1}-R_i-2D\log_gN) \ge\frac{N(1-\epsilon\delta)}{D+1}-2\delta N^{1-1/D}\log_gN $$ This contradicts Lemma 2, which gives, for $N$ large, $$ \sum_{1\le n< N-2D\log_g N}\vert T(n)\vert =O(\delta^D N). $$

share|improve this answer

I must apologize and correct what I wrote in an earlier paper: the method does extend to base > 2. Using Liouville's inequality, you lose a bit in the constant c, but the great advantage is that everything can be made fully explicit.

share|improve this answer
    
+1. Many thanks for your response! Unfortunately, with less than 50 rep you can't add a comment to my answer, but I'll edit it to refer to this response. –  George Lowther Oct 11 '10 at 15:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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