betaFeedback

WorksMathematics

The exponent 1/41/4 in three complexity bounds: integer bases, continued fractions, and the (3/2)n(3/2)^n steering word

Abstract

Let ξξ be a real algebraic irrational number and p(n,ξ,b)p(n,ξ,b) the number of distinct blocks of length nn in its base-bb expansion. Bugeaud and Evertse proved in 2008 that p(n,ξ,b)/(n(log⁡n)η)p(n,ξ,b)/(n(\log n)^η) is unbounded for every η<1/11η<1/11. We prove this for every η<1/4η<1/4. We also prove the analogous bound for the continued fraction expansion of an algebraic number of degree at least three, with every exponent δ<1/4δ<1/4. Bugeaud announced this statement in 2013 with an unspecified δ>0δ>0. Finally, the subword complexity of the steering word of (3/2)n(3/2)^n exceeds C k(log⁡k)ηC\,k(\log k)^η infinitely often for every η<1/4η<1/4 and every CC. The three proofs share one count: ε−1\varepsilon^{-1} classes times ε−3\varepsilon^{-3} subspaces from the quantitative Subspace Theorem of Evertse and Ferretti. The subspaces are then disposed of at the cost of a logarithm, with no further power of ε−1\varepsilon^{-1}. All three results, and the quantitative Subspace Theorem they rest on, are machine-verified in Lean~4.

Introduction

Borel's problem

Borel introduced normal numbers in 1909 and proved that almost every real number is normal to every integer base [5]. In 1950, at the end of a note on the decimal digits of 2\sqrt{2}, he wrote [Bor50]:

En définitive, le problème de savoir si les chiffres d’un nombre tel que 2\sqrt{2} satisfont ou non à toutes les lois que l’on peut énoncer pour des chiffres choisis au hasard me paraît toujours être un des problèmes les plus importants qui se posent aux mathématiciens.

It is now commonly expected that every real algebraic irrational number is normal to every integer base. This is far out of reach. A much weaker measure of randomness is the block complexity [4]: for an integer b≥2b \ge2 and a real number ξ\xi with bb-ary expansion ξ=⌊ξ⌋+∑j≥1ajb−j\xi= \lfloor\xi\rfloor+ \sum_{j\ge1} a_j b^{-j},

p(n,ξ,b)=Card⁡{ak+1ak+2⋯ak+n:k≥0}.p(n,\xi,b) = \operatorname{Card}\{a_{k+1}a_{k+2}\cdots a_{k+n}: k \ge0\}.

A number normal to base bb has p(n,ξ,b)=bnp(n,\xi,b) = b^n for every nn. The known lower bounds for algebraic ξ\xi are barely above linear.

  • By Morse and Hedlund [17], p(n,ξ,b)≥n+1p(n,\xi,b) \ge n+1 for every irrational ξ\xi.

  • Ferenczi and Mauduit [15] used Ridout’s theorem [18] to show p(n,ξ,b)−n→∞p(n,\xi,b)-n \to\infty for algebraic irrational ξ\xi.

  • Adamczewski, Bugeaud and Luca [3] gave a combinatorial transcendence criterion based on the Schmidt Subspace Theorem. With it, Adamczewski and Bugeaud [2] proved p(n,ξ,b)/n→∞p(n,\xi,b)/n \to\infty. Since automatic sequences have complexity O(n)O(n) [12], this answers Cobham’s question [11]: irrational automatic numbers are transcendental.

  • Bugeaud and Evertse [4 Thm. 2.1] brought in the quantitative Subspace Theorem of Evertse and Schlickewei [14]. They proved that

lim sup⁡n→∞p(n,ξ,b)n(log⁡n)η=+∞for every η<1/11.(1)\limsup_{n\to\infty}\frac{p(n,\xi,b)}{n(\log n)^\eta}=+\infty\qquad\text{for every }\eta<1/11. \tag*{(1)}

so in particular p(n,ξ,b)≥n(log⁡n)0.09p(n,\xi,b) \ge n(\log n)^{0.09} for infinitely many nn.

Continued fractions

By Lagrange’s theorem, the continued fraction expansion α=[0;a1,a2,…]\alpha= [0; a_1, a_2, \ldots] is ultimately periodic exactly when α\alpha is quadratic. Let

p(n,a)=Card⁡{aℓ+1⋯aℓ+n:ℓ≥0}p(n,a)=\operatorname{Card}\{a_{\ell+1}\cdots a_{\ell+n}:\ell\ge0\}

be the complexity function of the sequence of partial quotients of an algebraic α\alpha of degree at least three. Its lower bounds came in the same order as for integer bases.

  • Adamczewski and Bugeaud [1] proved p(n,a)−n→∞p(n,a)-n\to\infty.

  • Bugeaud [9 Thm. 1.1] proved p(n,a)/n→∞p(n,a)/n\to\infty. It follows that the continued fraction of an algebraic number of degree at least three is not automatic [9 Thm. 1.2].

The steering word

Little is known about the distribution of the fractional parts of (3/2)n(3/2)^n [16]. Write (3/2)n=mn+εn(3/2)^n=m_n+\varepsilon_n, where mnm_n is the nearest integer, and put tn=2mn+1−3mnt_n=2m_{n+1}-3m_n. The resulting word T=(tn)n≥0T=(t_n)_{n\ge0} over {−2,…,2}\{-2,\ldots,2\} is the steering word of (3/2)n(3/2)^n [19]. Its subword complexity pT(k)p_T(k) satisfies pT(k)/k→∞p_T(k)/k\to\infty [19 Thm. 1.1]. The proof transfers the Adamczewski–Bugeaud method to this word. Problem 5.2 of [19] asks for a bound pT(k)≥k(log⁡k)δp_T(k)\ge k(\log k)^\delta for infinitely many kk, with some δ>0\delta>0.

What was announced

Bugeaud remarked twice that the exponents could be improved or carried over, and neither remark was followed up.

  • Integer bases. After restating (1) as Theorem 12.2 of his survey [10], Bugeaud writes: “Using the recent results of [Evertse–Ferretti] allows us to show that Theorem 12.2 holds for η\eta in a slightly larger interval than [0,1/11)[0,1/11).” No value and no proof are given.

  • Continued fractions. At the end of [9], §6, Bugeaud writes that “it seems to be possible to prove” that

lim sup⁡n→∞p(n,a)n(log⁡n)δ=+∞(2)\limsup_{n\to\infty}\frac{p(n,a)}{n(\log n)^\delta}=+\infty \tag*{(2)}

for some δ>0\delta>0, and that “more details will be given in a subsequent note”. Two years later [10 §12] he says that the continued fraction analogues of Theorem 12.2 and of an effective bound “have not been written yet, but there is little doubt that they hold”.

Bugeaud’s 2011 survey [7] and his monograph [8 Ch. 8] restate (1) as it is. Bugeaud and Evertse also note [4 (2.4)] that their method gives an extra factor (log⁡log⁡n)δ(\log\log n)^\delta at η=1/11\eta=1/11, without proof. We are not aware of any later work that gives an exponent beyond 1/111/11 in (1), or that proves (2) with an explicit value of δ\delta. We checked the papers that cite [4].

Results

We prove the following three theorems.

Theorem 1.1. Let b≥2b\ge2 be an integer and ξ\xi a real algebraic irrational number. For every real η<1/4\eta<1/4 and every real CC,

p(n,ξ,b)>Cn(log⁡n)ηfor infinitely many n.p(n,\xi,b)>Cn(\log n)^\eta\qquad\text{for infinitely many }n.

Theorem 1.2. Let a=(aℓ)ℓ≥1a=(a_\ell)_{\ell\ge1} be a sequence of positive integers such that α=[0;a1,a2,…]\alpha=[0;a_1,a_2,\ldots] is algebraic of degree at least three. For every δ\delta with 0≤δ<1/40\le\delta<1/4 and every real CC,

p(n,a)>Cn(log⁡n)δfor infinitely many n.p(n,a)>Cn(\log n)^\delta\qquad\text{for infinitely many }n.

Theorem 1.3. For every real η<1/4\eta<1/4 and every real CC, the subword complexity of the steering word of (3/2)n(3/2)^n satisfies pT(k)>Ck(log⁡k)ηp_T(k)>Ck(\log k)^\eta for infinitely many kk. In particular, pT(k)≥k(log⁡k)1/8p_T(k)\ge k(\log k)^{1/8} for infinitely many kk, which solves Problem 5.2 of [19].

Each statement is equivalent to lim sup⁡p(n)/(n(log⁡n)η)=+∞\limsup p(n)/(n(\log n)^\eta)=+\infty. Theorem 1.1 improves (1) from 1/111/11 to 1/41/4. Theorem 1.2 is (2) with every δ<1/4\delta<1/4. In Theorem 1.2, p(n,a)p(n,a) may be infinite; this happens exactly when aa is unbounded, and then there is nothing to prove.

The common count

The common count. All three proofs follow [4 §§6–7]. Suppose p(n)≤cn(log⁡n)up(n) \le cn(\log n)^u for all large nn, and fix vv with u<v<1/4u < v < 1/4. A pigeonhole argument gives repetitions in the word, and these give integer points xN,…,x2N−1x_N,\ldots,x_{2N-1}. The heights of the points grow at least doubly exponentially, and each point satisfies a system of Diophantine inequalities with exponent ε=N−v+o(1)\varepsilon= N^{-v+o(1)}. Sort the points into about ε−1\varepsilon^{-1} classes according to the relative size of two of their coordinates. Theorem 2.1 below then puts each class into ε−3+o(1)\varepsilon^{-3+o(1)} proper subspaces, so there are ε−4+o(1)\varepsilon^{-4+o(1)} subspaces in all. The point of this paper is that each of these subspaces contains only O(log⁡ε−1)O(\log\varepsilon^{-1}) of the points, up to a remainder that lies on ε−3+o(1)\varepsilon^{-3+o(1)} lines or planes holding O(log⁡ε−1)O(\log\varepsilon^{-1}) points each. Hence

N≤ε−4+o(1)=N4v+o(1),N \le\varepsilon^{-4+o(1)} = N^{4v+o(1)},

which is impossible for large NN since 4v<14v < 1.

In [4] the count is ε−11\varepsilon^{-11}, from three factors:

  • the ε−1\varepsilon^{-1} classes;

  • ε−7\varepsilon^{-7} subspaces per class, from [14];

  • ε−3\varepsilon^{-3} points per subspace, from a two-variable quantitative Ridout theorem [4 Cor. 5.2].

Using Evertse and Ferretti’s count [13] gives 1+3+3=71 + 3 + 3 = 7, which is the “slightly larger interval” of [10] (Remark 6.1). The remaining factor ε−3\varepsilon^{-3} goes away as follows.

  • In the integer-base and steering-word problems, a plane through the points either has a constant gap (the difference of the two exponents) or it does not. If it does not, eliminating one variable leaves an inequality that Liouville’s inequality or integer arithmetic bounds, with no Subspace Theorem at all. If the gap is constant, the plane carries a genuine Ridout problem. We count such planes only for points with a large gap. The points with a small gap are handled once, globally, by one more two-variable application. In that application each line holds at most one point (or three) because of a coprimality.

  • For continued fractions, a subspace that avoids one exceptional hyperplane is handled by a three-variable application at a fixed exponent δ=3/4\delta= 3/4. This costs O(1)O(1). The exceptional hyperplane is handled once, globally.

Formalization

Formalization. Theorems 1.1–1.3 are proved in Lean 4 with Mathlib, using only the three standard axioms of Lean. So are all the results they use, including the quantitative Subspace Theorem in the form of Theorem 2.1 and Lemma 6.1 of [4]. The code is in the repository https://github.com/rwst/Subspace-Theorems. Appendix A lists, for every numbered statement below, the Lean declaration that proves it.

Tools

For x∈Znx \in\mathbb{Z}^n write ∣x∣=max⁡i∣xi∣|x| = \max_i |x_i|, and ∣⋅∣l|\cdot|_l for the ll-adic absolute value normalized by ∣l∣l=l−1|l|_l = l^{-1}. The following is the form of the quantitative Subspace Theorem we use. It follows from Evertse and Ferretti’s theorem for systems of inequalities [13 §3], specialized to the ground field Q\mathbb{Q}, to linear forms with coefficients in Z+Zα+Zα2\mathbb{Z} + \mathbb{Z}\alpha+ \mathbb{Z}\alpha^2, and to the coordinates at finitely many primes.

Theorem 2.1 (Evertse–Ferretti [13]). Let α\alpha be a real algebraic number, SS a finite set of primes, and 2≤n≤42 \le n \le4. There is K=K(α,S,n)>0K = K(\alpha,S,n) > 0 with the following property. Suppose we are given:

  • linear forms L1,…,LnL_1,\ldots,L_n in X1,…,XnX_1,\ldots,X_n, with coefficients c0+c1α+c2α2c_0 + c_1\alpha+ c_2\alpha^2 where cj∈Zc_j \in\mathbb{Z} and ∣cj∣≤B|c_j| \le B for some B≥1B \ge1, and with ∣det⁡(L1,…,Ln)∣≥γ|\det(L_1,\ldots,L_n)| \ge\gamma for some 0<γ≤10 < \gamma\le1;

  • reals C≥1C \ge1 and 0<δ≤10 < \delta\le1;

  • exponents ei≤1e_i \le1 with some ei=1e_i = 1 and some ei≤1−δ/(2n)e_i \le1 - \delta/(2n);

  • exponents fl,i≤0f_{l,i} \le0 for l∈Sl \in S, with fl,i=0f_{l,i} = 0 for some ii, for each ll;

  • and ∑iei+∑l∈S∑ifl,i≤−δ\sum_i e_i + \sum_{l\in S}\sum_i f_{l,i} \le-\delta.

Then the points x∈Zn∖{0}x \in\mathbb{Z}^{n} \setminus\{0\} with

∣Li(x)∣≤C∣x∣ei,∣xi∣l≤∣x∣fl,i(1≤i≤n, l∈S),|L_i(x)| \le C|x|^{e_i}, \qquad|x_i|_l \le|x|^{f_{l,i}} \qquad(1 \le i \le n,\ l \in S),
log⁡∣x∣≥Kδ−1(1+log⁡B+log⁡C+log⁡γ−1)\log|x| \ge K\delta^{-1}(1+\log B+\log C+\log\gamma^{-1})

lie in at most Kδ−3(1+log⁡δ−1)2K\delta^{-3}(1+\log\delta^{-1})^2 proper linear subspaces of Qn\mathbb{Q}^n.

The exponent 33 of δ−1\delta^{-1} is what makes 1/41/4 possible. Theorem 1.2 needs only S=∅S=\emptyset, and Theorem 1.3 only α\alpha rational.

Lemma 2.2. Let (tn)(t_n) be integers with 2tn<tn+12t_n<t_{n+1} for all nn, and let R≥1R\ge1. The indices n≥n0n\ge n_0 with tn≤Rtn0t_n\le Rt_{n_0} number at most log⁡R/log⁡2+1\log R/\log2+1.

Proof. 2ktn0≤tn0+k2^k t_{n_0}\le t_{n_0+k}.

We call the set in Lemma 2.2 a window of ratio RR at n0n_0.

Integer bases: proof of Theorem 1.1

Let b≥2b\ge2 and let ξ\xi be real, algebraic, irrational, of degree dd. We may assume 0<ξ<10<\xi<1. Suppose p(n,ξ,b)≤cn(log⁡n)up(n,\xi,b)\le cn(\log n)^u for all large nn, with 0≤u<1/40\le u<1/4, and put v=(u+1/4)/2v=(u+1/4)/2. Liouville’s inequality gives A≥1A\ge1 with

∣c0+c1ξ∣≥(AZd)−1for (c0,c1)∈Z2∖{0}, ∣c0∣,∣c1∣≤Z, Z≥1.(3)|c_0+c_1\xi|\ge(AZ^d)^{-1}\qquad\text{for }(c_0,c_1)\in\mathbb{Z}^2\setminus\{0\},\ |c_0|,|c_1|\le Z,\ Z\ge1. \tag*{(3)}

The points

3.1. The points. The following is Lemma 6.1 of [4].

Lemma 3.1 (Bugeaud–Evertse). There are C∈NC\in\mathbb{N}, integers 0≤rn<tn0\le r_n<t_n and pn∈Zp_n\in\mathbb{Z} such that, for every nn,

2tn<tn+1,tn≤(2n+2)C(n+1),∣pn∣≤btn,b∤pn if rn≥1,2t_n<t_{n+1},\qquad t_n\le(2n+2)^{C(n+1)},\qquad|p_n|\le b^{t_n},\qquad b\nmid p_n\text{ if }r_n\ge1,
∣btnξ−brnξ−pn∣≤(btn)−(log⁡tn)−v.|b^{t_n}\xi-b^{r_n}\xi-p_n|\le(b^{t_n})^{-(\log t_n)^{-v}}.

Remark 3.2. [4 Lemma 6.1] is printed with the hypothesis v<uv<u. It holds, and is used, for v>uv>u. This does not affect [4 §7].

Put xn=(btn,brn,pn)∈Z3x_n=(b^{t_n},b^{r_n},p_n)\in\mathbb{Z}^3 and sn=tn−rns_n=t_n-r_n, the gap of xnx_n. Let ε=(log⁡t2N)−v\varepsilon=(\log t_{2N})^{-v}. Then ε−1=Nv+o(1)\varepsilon^{-1}=N^{v+o(1)}. For large NN, 0<ε≤10<\varepsilon\le1, every xnx_n with N≤n<2NN\le n<2N satisfies the inequality of Lemma 3.1 with exponent −ε-\varepsilon, and ε−1\varepsilon^{-1} is below any fixed multiple of tnlog⁡bt_n\log b. We count the NN points xnx_n, N≤n<2NN\le n<2N. Point xnx_n has a large gap if εtn<4sn\varepsilon t_n<4s_n, and a small gap if 4sn≤εtn4s_n\le\varepsilon t_n.

Large gaps

3.2. Large gaps. The first step is the three-variable step of [4 §7], with Theorem 2.1 in place of [14].

Proposition 3.3. There is K>0K>0 such that for 0<ε≤10<\varepsilon\le1 the points (bt,br,p)(b^t,b^r,p) with r<tr<t, ∣p∣≤bt|p|\le b^t, ∣btξ−brξ−p∣≤(bt)−ε|b^t\xi-b^r\xi-p|\le(b^t)^{-\varepsilon} and Kε−1≤tlog⁡bK\varepsilon^{-1}\le t\log b lie in at most Kε−4(1+log⁡ε−1)2K\varepsilon^{-4}(1+\log\varepsilon^{-1})^2 proper subspaces of Q3\mathbb{Q}^3.

Sketch. Let k=⌊2/ε⌋+1k=\lfloor2/\varepsilon\rfloor+1 and sort the points by ℓ=⌊kr/t⌋\ell=\lfloor kr/t\rfloor. For l∣bl\mid b put gl=−vl(b)log⁡l/log⁡bg_l=-v_l(b)\log l/\log b, so that ∣bt∣l=(br)gl|b^t|_l=(b^r)^{g_l} and ∑l∣bgl=−1\sum_{l\mid b}g_l=-1. On the class ℓ\ell apply Theorem 2.1 with n=3n=3, SS the primes dividing bb, and δ=ε−1/k≥ε/2\delta=\varepsilon-1/k\ge\varepsilon/2:

  • at ∞\infty, the forms X1X_1, X2X_2, ξX1−ξX2−X3\xi X_1-\xi X_2-X_3 with exponents 11, (ℓ+1)/k(\ell+1)/k, −ε-\varepsilon;

  • at l∣bl\mid b, the coordinates with exponents glg_l, glℓ/kg_l\ell/k, 00.

The exponents sum to 1/k−ε1/k-\varepsilon. Summing over the k≤3/εk\le3/\varepsilon classes gives the bound.

Lemma 3.4. There is D≥1D\ge1 with the following property. Suppose z1bt+z2br+z3p=0z_1b^t+z_2b^r+z_3p=0 with ∣zi∣≤Z|z_i|\le Z, Z≥1Z\ge1, z3≠0z_3\ne0, r<tr<t and ∣btξ−brξ−p∣≤1|b^t\xi-b^r\xi-p|\le1. Then tlog⁡b≤D(1+log⁡Z)t\log b\le D(1+\log Z).

Proof. Put s=t−rs=t-r. Multiply the approximation by z3z_3 and use z3p=−z1bt−z2brz_3p=-z_1b^t-z_2b^r:

brΓ=z3(btξ−brξ−p),Γ=(z3ξ+z1)bs+(z2−z3ξ).b^r\Gamma=z_3(b^t\xi-b^r\xi-p),\qquad\Gamma=(z_3\xi+z_1)b^s+(z_2-z_3\xi).

So br∣Γ∣≤Zb^r|\Gamma|\le Z, and in particular ∣Γ∣≤Z|\Gamma|\le Z. Apply (3) to z1+z3ξz_1+z_3\xi, which is nonzero: this gives bs≤AZd+1(2+∣ξ∣)b^s\le AZ^{d+1}(2+|\xi|). Next write Γ=(z1bs+z2)+z3(bs−1)ξ\Gamma=(z_1b^s+z_2)+z_3(b^s-1)\xi. Here z3(bs−1)≠0z_3(b^s-1)\ne0 and both coefficients are at most W=2ZbsW=2Zb^s. Applying (3) again gives br≤AWdZb^r\le AW^dZ. Multiply the two bounds and take logarithms. This gives the claim with D=(d+2)2(1+log⁡A+log⁡(2+∣ξ∣))D=(d+2)^2(1+\log A+\log(2+|\xi|)).

Lemma 3.5. There is KK such that, for 0<ε≤10<\varepsilon\le1, every proper subspace UU of Q3\mathbb{Q}^3 contains at most K(1+log⁡ε−1)K(1+\log\varepsilon^{-1}) of the points xnx_n with a large gap.

Proof. Let i1<i2i_1<i_2 be the first two indices with xn∈Ux_n\in U. The cross product z=xi1×xi2z=x_{i_1}\times x_{i_2} satisfies ∣zi∣≤Z=2b2ti2|z_i|\le Z=2b^{2t_{i_2}}, and every xn∈Ux_n\in U satisfies z1btn+z2brn+z3pn=0z_1b^{t_n}+z_2b^{r_n}+z_3p_n=0. Moreover (z2,z3)≠(0,0)(z_2,z_3)\ne(0,0). Otherwise xi1x_{i_1} and xi2x_{i_2} would be proportional, which forces b∣pi2b\mid p_{i_2} with ri2≥1r_{i_2}\ge1.

If z3≠0z_3\ne0, Lemma 3.4 gives tn≤Rti2t_n\le Rt_{i_2} with R=D(2+2log⁡b)/log⁡bR=D(2+2\log b)/\log b. By Lemma 2.2, at most log⁡R/log⁡2+2\log R/\log2+2 points lie in UU.

If z3=0z_3=0, then z2≠0z_2\ne0 and bsn=−z2/z1b^{s_n}=-z_2/z_1. So every point of UU has the same gap s0≤ti1s_0\le t_{i_1}. On such a plane the problem is a genuine Ridout problem, for (bs0−1)ξ(b^{s_0}-1)\xi. A large gap gives εtn<4s0≤4ti1\varepsilon t_n<4s_0\le4t_{i_1}, a window of ratio 4/ε4/\varepsilon at i1i_1. There are at most 3+2log⁡ε−13+2\log\varepsilon^{-1} such points.

Small gaps

Lemma 3.6. There is KK such that, for 0<ε≤10<\varepsilon\le1, the points y=(bt−br,p)y=(b^t-b^r,p) with r<tr<t, ∣p∣≤bt|p|\le b^t, ∣btξ−brξ−p∣≤(bt)−ε|b^t\xi-b^r\xi-p|\le(b^t)^{-\varepsilon}, 4(t−r)≤εt4(t-r)\le\varepsilon t and Kε−1≤tlog⁡bK\varepsilon^{-1}\le t\log b lie on at most Kε−3(1+log⁡ε−1)2K\varepsilon^{-3}(1+\log\varepsilon^{-1})^2 lines of Q2\mathbb{Q}^2.

Proof. Apply Theorem 2.1 with n=2n=2 and δ=ε/2\delta=\varepsilon/2.

  • At ∞\infty, take the forms ξX1−X2\xi X_1-X_2 and X1X_1, with determinant 11 and exponents −ε-\varepsilon and 11. Since bt/2≤∣y∣≤btb^t/2\le|y|\le b^t, we have ∣ξy1−y2∣≤∣y∣−ε|\xi y_1-y_2|\le|y|^{-\varepsilon}.

  • At l∣bl\mid b, take the exponents (1−ε/4)gl(1-\varepsilon/4)g_l and 00. Write y1=br(bs−1)y_1=b^r(b^s-1). Since a small gap means r≥(1−ε/4)tr\ge(1-\varepsilon/4)t, we get ∣y1∣l≤(bt)gl≤∣y∣(1−ε/4)gl|y_1|_l\le(b^t)^{g_l}\le|y|^{(1-\varepsilon/4)g_l}.

The exponents sum to −ε+1−(1−ε/4)=−3ε/4≤−δ-\varepsilon+1-(1-\varepsilon/4)=-3\varepsilon/4\le-\delta.

Lemma 3.7. Let b≠0b\ne0 be an integer. If (bt1−br1)p2=(bt2−br2)p1(b^{t_1}-b^{r_1})p_2=(b^{t_2}-b^{r_2})p_1 with r1<t1r_1<t_1 and r1<r2≤t2r_1<r_2\le t_2, then b∣p2b\mid p_2.

Proof. Cancel br1b^{r_1}: (bt1−r1−1)p2=br2−r1(bt2−r2−1)p1(b^{t_1-r_1}-1)p_2=b^{r_2-r_1}(b^{t_2-r_2}-1)p_1, and the right-hand side is divisible by bb. Since b⋅bt1−r1−1−(bt1−r1−1)=1b\cdot b^{t_1-r_1-1}-(b^{t_1-r_1}-1)=1, bb is prime to bt1−r1−1b^{t_1-r_1}-1.

No line contains two points yn,ymy_n,y_m (n<mn<m) with a small gap. A small gap gives 3t≤4r3t\le4r, so 4rm≥3tm>6tn>4rn4r_m\ge3t_m>6t_n>4r_n. Lemma 3.7 then gives b∣pmb\mid p_m with rm≥1r_m\ge1, contrary to Lemma 3.1.

The count

By Proposition 3.3, Lemma 3.5, Lemma 3.6 and the remark above,

N≤Kε−4(1+log⁡ε−1)2⋅K(1+log⁡ε−1)+Kε−3(1+log⁡ε−1)2≤K′ε−4(1+log⁡ε−1)3=N4ν+o(1).N\le K\varepsilon^{-4}(1+\log\varepsilon^{-1})^2\cdot K(1+\log\varepsilon^{-1})+K\varepsilon^{-3}(1+\log\varepsilon^{-1})^2\le K'\varepsilon^{-4}(1+\log\varepsilon^{-1})^3=N^{4\nu+o(1)}.

This contradicts 4ν<14\nu<1 for large NN, and proves Theorem 1.1.

Continued fractions: proof of Theorem 1.2

Let α=[0;a1,a2,…]\alpha=[0;a_1,a_2,\ldots] be algebraic of degree at least three, with convergents pℓ/qℓp_\ell/q_\ell (p−1=q0=1p_{-1}=q_0=1, q−1=p0=0q_{-1}=p_0=0). Suppose p(ℓ,a)≤Cℓ(log⁡ℓ)δp(\ell,a)\le C\ell(\log\ell)^\delta for all large ℓ\ell, with 0≤δ<1/40\le\delta<1/4. Then p(1,a)p(1,a) is finite, so aℓ≤Ma_\ell\le M for some integer M≥1M\ge1.

The points

We use Bugeaud’s quadratic approximations of [9 §3]. Let w≥1w \ge1, r≥2r \ge2 and 1≤u≤r1 \le u \le r be integers with

am+r=am(w<m≤w+u),aw≠aw+r if w≥2.a_{m+r}=a_m \quad(w<m\le w+u),\qquad a_w\ne a_{w+r}\text{ if }w\ge2.

The continued fraction completed by periodicity after awa_w represents a quadratic number. Its minimal polynomial v0X2−(v1+v2)X+v3v_0X^2-(v_1+v_2)X+v_3 has the coefficients

v0=qw−1qw+r−qwqw+r−1,v1=qw−1pw+r−qwpw+r−1,v_0=q_{w-1}q_{w+r}-q_wq_{w+r-1},\qquad v_1=q_{w-1}p_{w+r}-q_wp_{w+r-1},
v2=pw−1qw+r−pwqw+r−1,v3=pw−1pw+r−pwpw+r−1.v_2=p_{w-1}q_{w+r}-p_wq_{w+r-1},\qquad v_3=p_{w-1}p_{w+r}-p_wp_{w+r-1}.

Put H=qwqw+rH=q_wq_{w+r} and Q=qwQ=q_w, and consider the forms

L1=α2X0−α(X1+X2)+X3,L2=αX0−X1,L3=αX0−X2.L_1=\alpha^2X_0-\alpha(X_1+X_2)+X_3,\qquad L_2=\alpha X_0-X_1,\qquad L_3=\alpha X_0-X_2.

Their values at vv are Pn(α)P_n(\alpha) and the left-hand sides of (3.2) and (3.3) of [9].

Lemma 4.1. If Hε≤2uH^\varepsilon\le2^u, then v=(v0,…,v3)v=(v_0,\ldots,v_3) satisfies:

(1) ∣vi∣≤H|v_i|\le H and H≤(M+1)4∣v0∣H\le(M+1)^4|v_0|;

(2) 1≤Q1\le Q and Q2≤HQ^2\le H;

(3) ∣L1(v)∣≤24H−1−ε|L_1(v)|\le24H^{-1-\varepsilon};

(4) Q2/(2H)≤∣L2(v)∣≤min⁡(2Q2/H,3H−ε/2)Q^2/(2H)\le|L_2(v)|\le\min(2Q^2/H,3H^{-\varepsilon/2});

(5) ∣L3(v)∣≤2H/Q2|L_3(v)|\le2H/Q^2;

(6) (Bugeaud’s Claim) for every z∈R4z\in\mathbb{R}^4 with z⋅v=0z\cdot v=0,

Q∣z0+(z1+z2)α+z3α2∣≤12(M+1)2∑i∣zi∣.Q\left|z_0+(z_1+z_2)\alpha+z_3\alpha^2\right|\le12(M+1)^2\sum_i|z_i|.

Sketch. The upper bounds in (3)–(5) are (3.2)–(3.4) of [9], together with the length uu of the repetition. Inequality (1) uses aw≠aw+ra_w\ne a_{w+r}: the recurrence qℓ=aℓqℓ−1+qℓ−2q_\ell=a_\ell q_{\ell-1}+q_{\ell-2} leaves in v0v_0 a term of size at least H/(M+1)3H/(M+1)^3. The lower bound in (4) uses that the errors qℓα−pℓq_\ell\alpha-p_\ell alternate in sign and satisfy qℓ+1∣qℓα−pℓ∣≥1/2q_{\ell+1}|q_\ell\alpha-p_\ell|\ge1/2.

Lemma 4.2. Suppose aa has at most pp factors of length ℓ≥12\ell\ge12. Then there is a configuration as above with ℓ≤4u\ell\le4u and w+r≤2p+ℓ+1w+r\le2p+\ell+1.

Proof. Two of the positions 0,…,p0,\ldots,p carry the same factor of length ℓ\ell. This gives a repetition of length at least ℓ/3\ell/3 at distance r≥ur\ge u. Slide it to the left as far as it goes.

The count

Let T0={X1=X2}⊂Q4T_0=\{X_1=X_2\}\subset\mathbb{Q}^4.

Proposition 4.3. There is KK with the following property. Let 0<ε≤10<\varepsilon\le1 and let vkv_k (k∈Ik\in I) be points as in Lemma 4.1, with heights HkH_k such that log⁡Hk≥1\log H_k\ge1, log⁡Hk+1≥2log⁡Hk\log H_{k+1}\ge2\log H_k and log⁡Hk≥Kε−K\log H_k\ge K\varepsilon^{-K}. Then #I≤Kε−4(1+log⁡ε−1)3\#I\le K\varepsilon^{-4}(1+\log\varepsilon^{-1})^3.

Sketch. The proof has four steps.

(i) First application. Let ρ=log⁡Q/log⁡H∈[0,1/2]\rho=\log Q/\log H\in[0,1/2], and cover [0,1/2][0,1/2] by at most 10ε−110\varepsilon^{-1} cells [ρ−,ρ+][\rho^-,\rho^+] of length ε/4\varepsilon/4. On one cell, L1,L2,L3,X0L_1,L_2,L_3,X_0 are bounded at vv by 24(M+1)4∣v∣ei24(M+1)^4|v|^{e_i}, with

e=(−1−ε, 2ρ+−1, 1−2ρ−, 1),∑iei≤−ε/2.e=(-1-\varepsilon,\ 2\rho^+-1,\ 1-2\rho^-,\ 1),\qquad\sum_i e_i\le-\varepsilon/2.

The four forms have determinant −1-1. Theorem 2.1 with n=4n=4, S=∅S=\varnothing and δ=ε/2\delta=\varepsilon/2 puts the points of a cell into O(ε−3(1+log⁡ε−1)2)O(\varepsilon^{-3}(1+\log\varepsilon^{-1})^2) proper subspaces of Q4\mathbb{Q}^4. Altogether there are O(ε−4(1+log⁡ε−1)2)O(\varepsilon^{-4}(1+\log\varepsilon^{-1})^2) subspaces.

(ii) Planes. A subspace of dimension at most two contains O(log⁡ε−1)O(\log\varepsilon^{-1}) of the points. Two of its points va,vbv_a,v_b determine the others. Liouville’s inequality for the quadratic expression L1(x)L2(y)−L1(y)L2(x)L_1(x)L_2(y)-L_1(y)L_2(x) in α\alpha bounds the height of any further point by (cHb4D+4)1/ε(cH_b^{4D+4})^{1/\varepsilon}. This is a window of ratio O(ε−1)O(\varepsilon^{-1}) in log⁡H\log H, and Lemma 2.2 applies.

(iii) A proper subspace off T0T_0. A proper subspace UU contains O(log⁡ε−1)O(\log\varepsilon^{-1}) points outside T0T_0. Let va,vb,vcv_a,v_b,v_c be the first three independent ones. Their cross product zz is orthogonal to UU and has ∣z∣≤6Hc3|z| \le6H_c^3. Since va∉T0v_a \notin T_0, Λ=z0+(z1+z2)α+z3α2≠0\Lambda= z_0 + (z_1 + z_2)\alpha+ z_3\alpha^2 \ne0. By the Claim and the quadratic Liouville inequality, Q≤∣z∣O(1)Q \le|z|^{O(1)}. So every later point with log⁡H≥K(1+log⁡∣z∣)\log H \ge K(1 + \log|z|) has Q2≤H1/4Q^2 \le H^{1/4}.

Now eliminate a coordinate xjx_j with zj≠0z_j \ne0. The forms zjL1,zjL2,zjL3z_jL_1,z_jL_2,z_jL_3 in the remaining three coordinates have determinant ±zjΛ\pm z_j\Lambda and exponents (−1,−3/4,1)(-1,-3/4,1). So Theorem 2.1 with n=3n=3 and the fixed value δ=3/4\delta= 3/4 puts these points into O(1)O(1) planes, each covered by (ii). The earlier points have log⁡H≤9Klog⁡Hc\log H \le9K\log H_c, and there are O(1)O(1) of them by Lemma 2.2.

(iv) The hyperplane T0T_0. On T0T_0, the forms L1,L2,X0L_1,L_2,X_0 in (X0,X1,X3)(X_0,X_1,X_3) have determinant 11 and exponents (−1−ε,0,1)(-1-\varepsilon,0,1). Theorem 2.1 with n=3n=3 and δ=ε\delta=\varepsilon puts the points of T0T_0 into O(ε−3(1+log⁡ε−1)2)O(\varepsilon^{-3}(1+\log\varepsilon^{-1})^2) planes, each covered by (ii).

Adding up gives O(ε−4(1+log⁡ε−1)3)O(\varepsilon^{-4}(1+\log\varepsilon^{-1})^3).

Proof of Theorem 1.2. Take the lengths ℓk=Ek+1(k+1)2(k+1)\ell_k=E^{k+1}(k+1)^{2(k+1)} with EE large, so that log⁡ℓk≍klog⁡k\log\ell_k\asymp k\log k. Lemma 4.2 with p=⌊Cℓk(log⁡ℓk)δ⌋p=\lfloor C\ell_k(\log\ell_k)^\delta\rfloor gives configurations, and so points vkv_k with heights Hk=qwqw+rH_k=q_wq_{w+r} satisfying

2ℓk/8≤Hk≤(M+1)2(w+r).2^{\ell_k/8}\le H_k\le(M+1)2^{(w+r)}.

For EE large these heights grow doubly exponentially. Choose εN\varepsilon_N with εN−1≍(log⁡ℓ2N)δ≍(Nlog⁡N)δ\varepsilon_N^{-1}\asymp(\log\ell_{2N})^\delta\asymp(N\log N)^\delta. Then HkεN≤2uH_k^{\varepsilon_N}\le2^u for N≤k<2NN\le k<2N, so Lemma 4.1 applies with ε=εN\varepsilon=\varepsilon_N. By Proposition 4.3,

N≤KεN−4(1+log⁡εN−1)3=(Nlog⁡N)4δ+o(1),N\le K\varepsilon_N^{-4}(1+\log\varepsilon_N^{-1})^3=(N\log N)^{4\delta+o(1)},

which fails for large NN since 4δ<14\delta<1.

Remark 4.4. The argument uses Theorem 2.1 only through its exponent 33, at n=3,4n=3,4. With a count of δ−a\delta^{-a} subspaces it gives every δ\delta with (a+1)δ<1(a+1)\delta<1. The count δ−(n+4)\delta^{-(n+4)} of Evertse–Schlickewei [14] at n=4n=4 gives δ<1/9\delta<1/9.

The steering word: proof of Theorem 1.3

Write (3/2)n=mn+εn(3/2)^n=m_n+\varepsilon_n with mnm_n the nearest integer, and tn=2mn+1−3mnt_n=2m_{n+1}-3m_n. A repetition of length LL at a<ca<c means ta+i=tc+it_{a+i}=t_{c+i} for 0≤i<L0\le i<L. By [19 Lemma 2.7], a repetition forces ∣εc−εa∣≤(2/3)L|\varepsilon_c-\varepsilon_a|\le(2/3)^L. Put λ=log⁡2/log⁡3\lambda=\log2/\log3. The numerical facts used are λ≤2/3\lambda\le2/3, 219<3122^{19}<3^{12}, 35<283^5<2^8 and 318≥648⋅2183^{18}\ge648\cdot2^{18}. Suppose pT(k)≤ck(log⁡k)up_T(k)\le ck(\log k)^u for all large kk, with 0≤u<1/40\le u<1/4, and put v=(u+1/4)/2v=(u+1/4)/2.

The points

The combinatorial half of [4 Lemma 6.1] applies to any word with finitely many factors of each length.

Lemma 5.1. There are C∈NC\in\mathbb{N} and integers rn<τnr_n<\tau_n with

2τn<τn+1,τn≤(2n+2)C(n+1),2\tau_n<\tau_{n+1},\qquad\tau_n\le(2n+2)^{C(n+1)},

such that there is a repetition of length ⌈τn(log⁡τn)−v⌉\lceil\tau_n(\log\tau_n)^{-v}\rceil at (an,cn)=(rn+2,τn+2)(a_n,c_n)=(r_n+2,\tau_n+2).

Since (2/3)L<3−L/3(2/3)^L<3^{-L/3}, a repetition of length L≥3cεL\ge3c\varepsilon at a<ca<c gives ∣εc−εa∣≤(3c)−ε|\varepsilon_c-\varepsilon_a|\le(3^c)^{-\varepsilon}. The gap of (a,c)(a,c) is s=c−as=c-a.

Large gaps

For 2≤a<c2\le a<c, s=c−as=c-a and M=mc−ma≥1M=m_c-m_a\ge1 put

x=(3c,2s3a,2cM)∈Z3,N=x0−x1−x2=2c(εc−εa).x=(3^c,2^{s}3^a,2^cM)\in\mathbb{Z}^3,\qquad\mathcal{N}=x_0-x_1-x_2=2^c(\varepsilon_c-\varepsilon_a).

Then N\mathcal{N} is odd, ∣N∣<2c|\mathcal{N}|<2^c, and ∣x∣=3c|x|=3^c.

Proposition 5.2. There is KK such that for 0<ε≤10<\varepsilon\le1 the points xx of the pairs with ∣εc−εa∣≤(3c)−ε|\varepsilon_c-\varepsilon_a|\le(3^c)^{-\varepsilon} and Kε−1≤clog⁡3K\varepsilon^{-1}\le c\log3 lie in at most Kε−4(1+log⁡ε−1)2K\varepsilon^{-4}(1+\log\varepsilon^{-1})^2 planes.

Proof. Let k=⌊2/ε⌋+1k=\lfloor2/\varepsilon\rfloor+1 and sort the points by ℓ=⌊ks/c⌋\ell=\lfloor ks/c\rfloor. On one class apply Theorem 2.1 with n=3n=3, S={2,3}S=\{2,3\}, C=1C=1 and the exponents

X0−X1−X2X_0-X_1-X_2X1X_1X2X_2
∞\inftyλ−ε\lambda-\varepsilon1−(1−λ)ℓ/k1-(1-\lambda)\ell/k11
2200−λℓ/k-\lambda\ell/k−λ-\lambda
33−1-1−(1−(ℓ+1)/k)-(1-(\ell+1)/k)00

Table 8a.

At 22 and 33 the forms are the coordinates. The entries sum to 1/k−ε=−δ1/k-\varepsilon=-\delta with δ≥ε/2\delta\geq\varepsilon/2. Each inequality is an identity between powers of 3c3^c. Summing over the k≤3/εk\leq3/\varepsilon classes gives the bound. □\square

Fix a plane w0X0+w1X1+w2X2=0w_0X_0+w_1X_1+w_2X_2=0.

Lemma 5.3. If w2≠0w_2\ne0, any two points (a1,c1)(a_1,c_1), (a2,c2)(a_2,c_2) on the plane with the same gap satisfy 7c2<19c17c_2<19c_1.

Proof. Eliminating X2X_2 gives N=β13c+β22s3a\mathcal{N}=\beta_1 3^c+\beta_2 2^s3^a with β1,β2∈Q\beta_1,\beta_2\in\mathbb{Q} fixed by the plane. So Ni=3ai(β13si+β22si)\mathcal{N}_i=3^{a_i}(\beta_1 3^{s_i}+\beta_2 2^{s_i}) and N23a1=N13a2\mathcal{N}_2^{3^{a_1}}=\mathcal{N}_1^{3^{a_2}}. If a2>a1a_2>a_1, then 3c2−c1≤∣N2∣<2c23^{c_2-c_1}\leq|\mathcal{N}_2|<2^{c_2}, because N1\mathcal{N}_1 is odd. If moreover 7c2≥19c17c_2\geq19c_1, then 312c2≤319(c2−c1)<219c23^{12c_2}\leq3^{19(c_2-c_1)}<2^{19c_2}, which is false. □\square

Lemma 5.4. If n1≠0n_1\ne0, ∣n2∣≤m|n_2|\leq m and z=3sn1−2sn2≠0z=3^s n_1-2^s n_2\ne0, then 3s≤2(2m+1)3∣z∣3^s\leq2(2m+1)^3|z|.

Proof. If 2s+1m≤3s2^{s+1}m\leq3^s then ∣z∣≥3s/2|z|\geq3^s/2. Otherwise 3s<(2m+1)2s3^s<(2m+1)2^s, and cubing gives 3s<(2m+1)33^s<(2m+1)^3. □\square

Lemma 5.5. Let w2≠0w_2\ne0. If two points (a1,c1)(a_1,c_1), (a2,c2)(a_2,c_2) on the plane have different gaps, then every point (a,c)(a,c) on it has c<18(c1+c2)+18c<18(c_1+c_2)+18.

Proof. Eliminate β1,β2\beta_1,\beta_2. This gives ND=3a(3sn1−2sn2)\mathcal{N}D=3^a(3^s n_1-2^s n_2), where DD, n1n_1 and n2n_2 are minors built from the two given points. Comparing 22-adic valuations gives D≠0D\ne0 and n1≠0n_1\ne0. Lemma 5.4 gives 3c<250⋅648c1+c22c3^c<250\cdot648^{c_1+c_2}2^c, which fails for c≥18(c1+c2)+18c\geq18(c_1+c_2)+18. □\square

Lemma 5.6. Each plane carries at most 12(1+log⁡ε−1)12(1+\log\varepsilon^{-1}) indices nn of Lemma 5.1 with a large gap, εcn<4sn\varepsilon c_n<4s_n.

Proof. If w2=0w_2=0, then w03s+w12s=0w_0 3^s+w_1 2^s=0, so the gap is a constant s0s_0. A large gap gives τn<4s0/ε≤(4/ε)τn1\tau_n<4s_0/\varepsilon\leq(4/\varepsilon)\tau_{n_1}, where n1n_1 is the first index on the plane. This is a window of ratio 4/ε4/\varepsilon.

If w2≠0w_2\ne0, Lemma 5.3 confines the indices with the gap of n1n_1 to a window of ratio 88. Let n′n' be the first index with another gap. Lemma 5.5 confines the remaining indices to a window of ratio 128128 at n′n'. Lemma 2.2 finishes the proof. □\square

Small gaps

Lemma 5.7. The points y=(3c−2s3a,2cM)y=(3^c-2^s3^a,2^cM) of the pairs with small gap s≤εc/4s\leq\varepsilon c/4 lie on at most Kε−3(1+log⁡ε−1)K\varepsilon^{-3}(1+\log\varepsilon^{-1}) lines, and each line carries at most three indices nn of Lemma 5.1.

Proof. The coordinate y0=3a(3s−2s)y_0=3^a(3^s-2^s) is odd and divisible by 3a3^a. Also 3c−1≤∣y∣≤3c3^{c-1}\leq|y|\leq3^c and y0−y1=Ny_0-y_1=\mathcal{N}. Apply Theorem 2.1 with n=2n=2, C=3C=3, δ=3ε/4\delta=3\varepsilon/4, and the exponents

Y0−Y1Y_0-Y_1Y1Y_1
∞\inftyλ−ε\lambda-\varepsilon11
2200−λ-\lambda
33−(1−ε/4)-(1-\varepsilon/4)00

Table 8b.

The small gap enters at 33: ∣y0∣3≤3−a≤(3c)−(1−ε/4)|y_0|_3\leq3^{-a}\leq(3^c)^{-(1-\varepsilon/4)}. Two points on one line satisfy y0y1′=y0′y1y_0y'_1=y'_0y_1. Since y0′y'_0 is odd, 2c′∣y1<3c2^{c'}\mid y_1<3^c, and 35<283^5<2^8 gives 5c′<8c5c'<8c, hence τ′<4τ\tau'<4\tau. □\square

The count

Let ε0=(log⁡τ2N)−ν\varepsilon_0=(\log\tau_2N)^{-\nu} and ε=ε0/6\varepsilon=\varepsilon_0/6. For N≤n<2NN\le n<2N, the pair (an,cn)(a_n,c_n) satisfies ∣εcn−εan∣≤(3cn)−ε|\varepsilon c_n-\varepsilon a_n|\le(3^{c_n})^{-\varepsilon}, and for large NN the threshold of Proposition 5.2 holds. Splitting the NN indices by the size of the gap, Proposition 5.2 and Lemmas 5.6 and 5.7 give

N≤Kε−4(1+log⁡ε−1)2⋅12(1+log⁡ε−1)+3Kε−3(1+log⁡ε−1)2=N4ν+o(1).N \le K\varepsilon^{-4}(1+\log\varepsilon^{-1})^2\cdot12(1+\log\varepsilon^{-1})+3K\varepsilon^{-3}(1+\log\varepsilon^{-1})^2=N^{4\nu+o(1)}.

This contradicts 4ν<14\nu<1 and proves Theorem 1.3. □

Remarks on the exponents

Remark 6.1. If the original argument of [4 §§6–7] is run with Theorem 2.1 in place of [14], both the three-variable step and the per-plane step improve. This gives (1) for every η<1/7\eta<1/7, since 7=1+3+37=1+3+3. It is the most direct reading of Bugeaud’s “slightly larger interval than [0, 1/11)” [10]. This intermediate statement is also machine-verified (Appendix A).

Remark 6.2. In each proof, Ridout’s theorem is still needed on the planes of constant gap. There we lose only a logarithm, because the large-gap condition εt<4s\varepsilon t<4s confines the points to a window of ratio 4/ε4/\varepsilon. Points with a small gap behave like approximations to a single number, and they are counted once on lines. Within that count, the coprimality of bb and bs−1b^s-1 (or the oddness of 3s−2s3^s-2^s) separates the points. In Theorem 1.2 the exceptional hyperplane T0T_0 plays the role of the small gaps.

Remark 6.3. The exponent 1/41/4 is 1/(1+3)1/(1+3): one power of ε−1\varepsilon^{-1} for the classes, three for the count of Theorem 2.1. Improving it by this method would need either fewer classes or a count better than δ−3\delta^{-3} in the quantitative Subspace Theorem.

Acknowledgements

We thank Yann Bugeaud for drawing our attention to this question. This work relies on a complete formalization of the Subspace Theorem and its quantitative versions, which is publicly available and is being incorporated into the TauCeti library.

Appendix A. The Lean formalization

Everything is in the repository

https://github.com/rwst/Subspace-Theorems,

a Lean 4 project on Mathlib. Every declaration below is proved without sorry. Its axioms, as reported by #print axioms, are the three standard axioms propext, Classical.choice and Quot.sound. The repository declares no axioms of its own. The steering-word theorems are additionally certified by the comparator tool against an independent statement file. The directories are:

  • BugeaudEvertse2008/ for [4], and its subdirectory Additions/ for Section 3;

  • Bugeaud2013/Additions/ for Section 4;

  • Stephan2026a/ for Section 5;

  • QuantitativeSubspace/ and DiophantineApproximation/ for the shared tools.

In the Lean statements:

  • Theorem 1.1 is stated for ξ=∑j≥0ajb−j−1\xi=\sum_{j\ge0}a_jb^{-j-1} with digits aj∈{0,…,b−1}a_j\in\{0,\ldots,b-1\}, irrational and algebraic. This is the case 0<ξ<10<\xi<1, which suffices.

  • Theorem 1.2 counts the factors of a1a2⋯a_1a_2\cdots as a cardinal, possibly infinite.

  • Theorem 1.3 is stated for the word tn=2mn+1−3mnt_n=2m_{n+1}-3m_n with mnm_n the rounded value of (3/2)n(3/2)^n.

StatementLean declarationFile
Section 3: BugeaudEvertse2008/
Thm. 1.1Real.frequently_lt_complexity_of_lt_quarterAdditions/Theorem21Quarter
Lemma 3.1Real.exists_approx_of_complexity_leRepetitions
Prop. 3.3Real.exists_planes_of_approxThreeVariable
Lemma 3.4Real.exists_mul_log_le_of_planeAdditions/PlaneLiouville
Lemma 3.5Real.card_mem_plane_le_logAdditions/PlaneLiouville
Lemma 3.6Real.exists_lines_of_small_gapAdditions/SmallGap
Lemma 3.7Int.dvd_of_pow_sub_pow_mul_eqAdditions/SmallGap
Remark 6.1Real.frequently_lt_complexityTheorem21
Section 4: Bugeaud2013/Additions/
Thm. 1.2Nat.frequently_lt_encard_factors_of_lt_quarterDelta
Lemma 4.1Nat.cfPoint_spadeVecCFPoints
Lemma 4.2Nat.exists_configComplexity
Prop. 4.3Real.card_le_of_cfPointsCount
step (i)Real.exists_cover_fourCount
step (ii)Real.card_mem_le_of_finrank_le_twoPoints
step (iii)Real.card_mem_le_of_ne_topSubspaces
step (iv)Real.exists_planes_t0Hyperplanes
Remark 4.4Nat.frequently_lt_encard_factors_of_lt_ninthDelta
Section 5: Stephan2026a/
Thm. 1.3SteeringWord.frequently_lt_complexityQuantitativeTheorem
(1/8)SteeringWord.quantitativeSuperlinearQuantitativeTheorem
Lemma 5.1SteeringWord.exists_violators_of_complexity_leQuantitativeViolators
Prop. 5.2SteeringWord.exists_planes_of_violatorsQuantitativePlanes
Lemma 5.3SteeringWord.seven_mul_lt_of_same_gapQuantitativePlaneStep
Lemma 5.4SteeringWord.three_pow_le_of_ne_zeroQuantitativePlaneStep
Lemma 5.5SteeringWord.lt_of_ne_gapQuantitativePlaneStep
Lemma 5.6SteeringWord.card_mem_plane_leQuantitativePlaneStep
Lemma 5.7SteeringWord.exists_lines_of_violatorsQuantitativeLines
SteeringWord.card_mem_line_leQuantitativeLines
Shared tools: QuantitativeSubspace/, DiophantineApproximation/
Thm. 2.1Real.subspaceBoundAt_threeRealFormCount
Lemma 2.2Nat.card_le_of_doubling_windowDoublingSequences

Table 1.

References

References

  1. [1]B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers II. Continued fractions, Acta Math. 195 (2005), 1–20.
  2. [2]B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), 547–565.DOI
  3. [3]B. Adamczewski, Y. Bugeaud and F. Luca, Sur la complexité des nombres algébriques, C. R. Acad. Sci. Paris 339 (2004), 11–14.DOI
  4. [4]Y. Bugeaud and J.-H. Evertse, On two notions of complexity of algebraic numbers, Acta Arith. 133 (2008), 221–250.DOI
  5. [5]É. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rend. Circ. Mat. Palermo 27 (1909), 247–271.DOI
  6. [7]Y. Bugeaud, Quantitative versions of the Subspace Theorem and applications, J. Théor. Nombres Bordeaux 23 (2011), 35–57.DOI
  7. [8]Y. Bugeaud, Distribution modulo one and Diophantine approximation, Cambridge Tracts in Math. 193, Cambridge University Press, 2012.DOI
  8. [9]Y. Bugeaud, Automatic continued fractions are transcendental or quadratic, Ann. Sci. Éc. Norm. Supér. (4) 46 (2013), 1005–1022.arxiv.org/abs/1012.1709
  9. [10]Y. Bugeaud, Expansions of algebraic numbers, in: Four Faces of Number Theory, EMS Ser. Lect. Math., Eur. Math. Soc., Zürich, 2015, 31–75.
  10. [11]A. Cobham, On the Hartmanis–Stearns problem for a class of tag machines, in: Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, IEEE, 1968, 51–60.DOI
  11. [12]A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.DOI
  12. [13]J.-H. Evertse and R. G. Ferretti, A further improvement of the Quantitative Subspace Theorem, Ann. of Math. (2) 177 (2013), 513–590.arxiv.org/abs/1008.2340
  13. [14]J.-H. Evertse and H. P. Schlickewei, A quantitative version of the Absolute Subspace Theorem, J. reine angew. Math. 548 (2002), 21–127.DOI
  14. [15]S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion, J. Number Theory 67 (1997), 146–161.DOI
  15. [16]K. Mahler, An unsolved problem on the powers of 3/2, J. Austral. Math. Soc. 8 (1968), 313–321.DOI
  16. [17]M. Morse and G. A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), 815–866.DOI
  17. [18]D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125–131.
  18. [19]R. Stephan, Superlinear complexity of the (3/2)^n steering word, arXiv:2607.11648 (2026).arxiv.org/abs/2607.11648

Paper details

vlnc:W_ddthbcz4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents