WorksMathematics
The exponent in three complexity bounds: integer bases, continued fractions, and the steering word
Abstract
Let be a real algebraic irrational number and the number of distinct blocks of length in its base- expansion. Bugeaud and Evertse proved in 2008 that is unbounded for every . We prove this for every . We also prove the analogous bound for the continued fraction expansion of an algebraic number of degree at least three, with every exponent . Bugeaud announced this statement in 2013 with an unspecified . Finally, the subword complexity of the steering word of exceeds infinitely often for every and every . The three proofs share one count: classes times 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 . 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 , he wrote [Bor50]:
En définitive, le problème de savoir si les chiffres d’un nombre tel que 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 and a real number with -ary expansion ,
A number normal to base has for every . The known lower bounds for algebraic are barely above linear.
By Morse and Hedlund [17], for every irrational .
Ferenczi and Mauduit [15] used Ridout’s theorem [18] to show for algebraic irrational .
Adamczewski, Bugeaud and Luca [3] gave a combinatorial transcendence criterion based on the Schmidt Subspace Theorem. With it, Adamczewski and Bugeaud [2] proved . Since automatic sequences have complexity [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
so in particular for infinitely many .
Continued fractions
By Lagrange’s theorem, the continued fraction expansion is ultimately periodic exactly when is quadratic. Let
be the complexity function of the sequence of partial quotients of an algebraic of degree at least three. Its lower bounds came in the same order as for integer bases.
Adamczewski and Bugeaud [1] proved .
Bugeaud [9 Thm. 1.1] proved . 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 [16]. Write , where is the nearest integer, and put . The resulting word over is the steering word of [19]. Its subword complexity satisfies [19 Thm. 1.1]. The proof transfers the Adamczewski–Bugeaud method to this word. Problem 5.2 of [19] asks for a bound for infinitely many , with some .
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 in a slightly larger interval than .” 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
for some , 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 at , without proof. We are not aware of any later work that gives an exponent beyond in (1), or that proves (2) with an explicit value of . We checked the papers that cite [4].
Results
We prove the following three theorems.
Theorem 1.1. Let be an integer and a real algebraic irrational number. For every real and every real ,
Theorem 1.2. Let be a sequence of positive integers such that is algebraic of degree at least three. For every with and every real ,
Theorem 1.3. For every real and every real , the subword complexity of the steering word of satisfies for infinitely many . In particular, for infinitely many , which solves Problem 5.2 of [19].
Each statement is equivalent to . Theorem 1.1 improves (1) from to . Theorem 1.2 is (2) with every . In Theorem 1.2, may be infinite; this happens exactly when is unbounded, and then there is nothing to prove.
The common count
The common count. All three proofs follow [4 §§6–7]. Suppose for all large , and fix with . A pigeonhole argument gives repetitions in the word, and these give integer points . The heights of the points grow at least doubly exponentially, and each point satisfies a system of Diophantine inequalities with exponent . Sort the points into about classes according to the relative size of two of their coordinates. Theorem 2.1 below then puts each class into proper subspaces, so there are subspaces in all. The point of this paper is that each of these subspaces contains only of the points, up to a remainder that lies on lines or planes holding points each. Hence
which is impossible for large since .
In [4] the count is , from three factors:
the classes;
subspaces per class, from [14];
points per subspace, from a two-variable quantitative Ridout theorem [4 Cor. 5.2].
Using Evertse and Ferretti’s count [13] gives , which is the “slightly larger interval” of [10] (Remark 6.1). The remaining factor 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 . This costs . 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 write , and for the -adic absolute value normalized by . 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 , to linear forms with coefficients in , and to the coordinates at finitely many primes.
Theorem 2.1 (Evertse–Ferretti [13]). Let be a real algebraic number, a finite set of primes, and . There is with the following property. Suppose we are given:
linear forms in , with coefficients where and for some , and with for some ;
reals and ;
exponents with some and some ;
exponents for , with for some , for each ;
and .
Then the points with
lie in at most proper linear subspaces of .
The exponent of is what makes possible. Theorem 1.2 needs only , and Theorem 1.3 only rational.
Lemma 2.2. Let be integers with for all , and let . The indices with number at most .
Proof. .
We call the set in Lemma 2.2 a window of ratio at .
Integer bases: proof of Theorem 1.1
Let and let be real, algebraic, irrational, of degree . We may assume . Suppose for all large , with , and put . Liouville’s inequality gives with
The points
3.1. The points. The following is Lemma 6.1 of [4].
Lemma 3.1 (Bugeaud–Evertse). There are , integers and such that, for every ,
Remark 3.2. [4 Lemma 6.1] is printed with the hypothesis . It holds, and is used, for . This does not affect [4 §7].
Put and , the gap of . Let . Then . For large , , every with satisfies the inequality of Lemma 3.1 with exponent , and is below any fixed multiple of . We count the points , . Point has a large gap if , and a small gap if .
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 such that for the points with , , and lie in at most proper subspaces of .
Sketch. Let and sort the points by . For put , so that and . On the class apply Theorem 2.1 with , the primes dividing , and :
at , the forms , , with exponents , , ;
at , the coordinates with exponents , , .
The exponents sum to . Summing over the classes gives the bound.
Lemma 3.4. There is with the following property. Suppose with , , , and . Then .
Proof. Put . Multiply the approximation by and use :
So , and in particular . Apply (3) to , which is nonzero: this gives . Next write . Here and both coefficients are at most . Applying (3) again gives . Multiply the two bounds and take logarithms. This gives the claim with .
Lemma 3.5. There is such that, for , every proper subspace of contains at most of the points with a large gap.
Proof. Let be the first two indices with . The cross product satisfies , and every satisfies . Moreover . Otherwise and would be proportional, which forces with .
If , Lemma 3.4 gives with . By Lemma 2.2, at most points lie in .
If , then and . So every point of has the same gap . On such a plane the problem is a genuine Ridout problem, for . A large gap gives , a window of ratio at . There are at most such points.
Small gaps
Lemma 3.6. There is such that, for , the points with , , , and lie on at most lines of .
Proof. Apply Theorem 2.1 with and .
At , take the forms and , with determinant and exponents and . Since , we have .
At , take the exponents and . Write . Since a small gap means , we get .
The exponents sum to .
Lemma 3.7. Let be an integer. If with and , then .
Proof. Cancel : , and the right-hand side is divisible by . Since , is prime to .
No line contains two points () with a small gap. A small gap gives , so . Lemma 3.7 then gives with , contrary to Lemma 3.1.
The count
By Proposition 3.3, Lemma 3.5, Lemma 3.6 and the remark above,
This contradicts for large , and proves Theorem 1.1.
Continued fractions: proof of Theorem 1.2
Let be algebraic of degree at least three, with convergents (, ). Suppose for all large , with . Then is finite, so for some integer .
The points
We use Bugeaud’s quadratic approximations of [9 §3]. Let , and be integers with
The continued fraction completed by periodicity after represents a quadratic number. Its minimal polynomial has the coefficients
Put and , and consider the forms
Their values at are and the left-hand sides of (3.2) and (3.3) of [9].
Lemma 4.1. If , then satisfies:
(1) and ;
(2) and ;
(3) ;
(4) ;
(5) ;
(6) (Bugeaud’s Claim) for every with ,
Sketch. The upper bounds in (3)–(5) are (3.2)–(3.4) of [9], together with the length of the repetition. Inequality (1) uses : the recurrence leaves in a term of size at least . The lower bound in (4) uses that the errors alternate in sign and satisfy .
Lemma 4.2. Suppose has at most factors of length . Then there is a configuration as above with and .
Proof. Two of the positions carry the same factor of length . This gives a repetition of length at least at distance . Slide it to the left as far as it goes.
The count
Let .
Proposition 4.3. There is with the following property. Let and let () be points as in Lemma 4.1, with heights such that , and . Then .
Sketch. The proof has four steps.
(i) First application. Let , and cover by at most cells of length . On one cell, are bounded at by , with
The four forms have determinant . Theorem 2.1 with , and puts the points of a cell into proper subspaces of . Altogether there are subspaces.
(ii) Planes. A subspace of dimension at most two contains of the points. Two of its points determine the others. Liouville’s inequality for the quadratic expression in bounds the height of any further point by . This is a window of ratio in , and Lemma 2.2 applies.
(iii) A proper subspace off . A proper subspace contains points outside . Let be the first three independent ones. Their cross product is orthogonal to and has . Since , . By the Claim and the quadratic Liouville inequality, . So every later point with has .
Now eliminate a coordinate with . The forms in the remaining three coordinates have determinant and exponents . So Theorem 2.1 with and the fixed value puts these points into planes, each covered by (ii). The earlier points have , and there are of them by Lemma 2.2.
(iv) The hyperplane . On , the forms in have determinant and exponents . Theorem 2.1 with and puts the points of into planes, each covered by (ii).
Adding up gives .
Proof of Theorem 1.2. Take the lengths with large, so that . Lemma 4.2 with gives configurations, and so points with heights satisfying
For large these heights grow doubly exponentially. Choose with . Then for , so Lemma 4.1 applies with . By Proposition 4.3,
which fails for large since .
Remark 4.4. The argument uses Theorem 2.1 only through its exponent , at . With a count of subspaces it gives every with . The count of Evertse–Schlickewei [14] at gives .
The steering word: proof of Theorem 1.3
Write with the nearest integer, and . A repetition of length at means for . By [19 Lemma 2.7], a repetition forces . Put . The numerical facts used are , , and . Suppose for all large , with , and put .
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 and integers with
such that there is a repetition of length at .
Since , a repetition of length at gives . The gap of is .
Large gaps
For , and put
Then is odd, , and .
Proposition 5.2. There is such that for the points of the pairs with and lie in at most planes.
Proof. Let and sort the points by . On one class apply Theorem 2.1 with , , and the exponents
Table 8a.
At and the forms are the coordinates. The entries sum to with . Each inequality is an identity between powers of . Summing over the classes gives the bound.
Fix a plane .
Lemma 5.3. If , any two points , on the plane with the same gap satisfy .
Proof. Eliminating gives with fixed by the plane. So and . If , then , because is odd. If moreover , then , which is false.
Lemma 5.4. If , and , then .
Proof. If then . Otherwise , and cubing gives .
Lemma 5.5. Let . If two points , on the plane have different gaps, then every point on it has .
Proof. Eliminate . This gives , where , and are minors built from the two given points. Comparing -adic valuations gives and . Lemma 5.4 gives , which fails for .
Lemma 5.6. Each plane carries at most indices of Lemma 5.1 with a large gap, .
Proof. If , then , so the gap is a constant . A large gap gives , where is the first index on the plane. This is a window of ratio .
If , Lemma 5.3 confines the indices with the gap of to a window of ratio . Let be the first index with another gap. Lemma 5.5 confines the remaining indices to a window of ratio at . Lemma 2.2 finishes the proof.
Small gaps
Lemma 5.7. The points of the pairs with small gap lie on at most lines, and each line carries at most three indices of Lemma 5.1.
Proof. The coordinate is odd and divisible by . Also and . Apply Theorem 2.1 with , , , and the exponents
Table 8b.
The small gap enters at : . Two points on one line satisfy . Since is odd, , and gives , hence .
The count
Let and . For , the pair satisfies , and for large the threshold of Proposition 5.2 holds. Splitting the indices by the size of the gap, Proposition 5.2 and Lemmas 5.6 and 5.7 give
This contradicts 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 , since . 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 confines the points to a window of ratio . 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 and (or the oddness of ) separates the points. In Theorem 1.2 the exceptional hyperplane plays the role of the small gaps.
Remark 6.3. The exponent is : one power of 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 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 subdirectoryAdditions/for Section 3;Bugeaud2013/Additions/for Section 4;Stephan2026a/for Section 5;QuantitativeSubspace/andDiophantineApproximation/for the shared tools.
In the Lean statements:
Theorem 1.1 is stated for with digits , irrational and algebraic. This is the case , which suffices.
Theorem 1.2 counts the factors of as a cardinal, possibly infinite.
Theorem 1.3 is stated for the word with the rounded value of .
| Statement | Lean declaration | File |
| Section 3: BugeaudEvertse2008/ | ||
| Thm. 1.1 | Real.frequently_lt_complexity_of_lt_quarter | Additions/Theorem21Quarter |
| Lemma 3.1 | Real.exists_approx_of_complexity_le | Repetitions |
| Prop. 3.3 | Real.exists_planes_of_approx | ThreeVariable |
| Lemma 3.4 | Real.exists_mul_log_le_of_plane | Additions/PlaneLiouville |
| Lemma 3.5 | Real.card_mem_plane_le_log | Additions/PlaneLiouville |
| Lemma 3.6 | Real.exists_lines_of_small_gap | Additions/SmallGap |
| Lemma 3.7 | Int.dvd_of_pow_sub_pow_mul_eq | Additions/SmallGap |
| Remark 6.1 | Real.frequently_lt_complexity | Theorem21 |
| Section 4: Bugeaud2013/Additions/ | ||
| Thm. 1.2 | Nat.frequently_lt_encard_factors_of_lt_quarter | Delta |
| Lemma 4.1 | Nat.cfPoint_spadeVec | CFPoints |
| Lemma 4.2 | Nat.exists_config | Complexity |
| Prop. 4.3 | Real.card_le_of_cfPoints | Count |
| step (i) | Real.exists_cover_four | Count |
| step (ii) | Real.card_mem_le_of_finrank_le_two | Points |
| step (iii) | Real.card_mem_le_of_ne_top | Subspaces |
| step (iv) | Real.exists_planes_t0 | Hyperplanes |
| Remark 4.4 | Nat.frequently_lt_encard_factors_of_lt_ninth | Delta |
| Section 5: Stephan2026a/ | ||
| Thm. 1.3 | SteeringWord.frequently_lt_complexity | QuantitativeTheorem |
| (1/8) | SteeringWord.quantitativeSuperlinear | QuantitativeTheorem |
| Lemma 5.1 | SteeringWord.exists_violators_of_complexity_le | QuantitativeViolators |
| Prop. 5.2 | SteeringWord.exists_planes_of_violators | QuantitativePlanes |
| Lemma 5.3 | SteeringWord.seven_mul_lt_of_same_gap | QuantitativePlaneStep |
| Lemma 5.4 | SteeringWord.three_pow_le_of_ne_zero | QuantitativePlaneStep |
| Lemma 5.5 | SteeringWord.lt_of_ne_gap | QuantitativePlaneStep |
| Lemma 5.6 | SteeringWord.card_mem_plane_le | QuantitativePlaneStep |
| Lemma 5.7 | SteeringWord.exists_lines_of_violators | QuantitativeLines |
SteeringWord.card_mem_line_le | QuantitativeLines | |
| Shared tools: QuantitativeSubspace/, DiophantineApproximation/ | ||
| Thm. 2.1 | Real.subspaceBoundAt_three | RealFormCount |
| Lemma 2.2 | Nat.card_le_of_doubling_window | DoublingSequences |
Table 1.
References
References
- [1]B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers II. Continued fractions, Acta Math. 195 (2005), 1–20.
- [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]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]Y. Bugeaud and J.-H. Evertse, On two notions of complexity of algebraic numbers, Acta Arith. 133 (2008), 221–250.DOI
- [5]É. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rend. Circ. Mat. Palermo 27 (1909), 247–271.DOI
- [7]Y. Bugeaud, Quantitative versions of the Subspace Theorem and applications, J. Théor. Nombres Bordeaux 23 (2011), 35–57.DOI
- [8]Y. Bugeaud, Distribution modulo one and Diophantine approximation, Cambridge Tracts in Math. 193, Cambridge University Press, 2012.DOI
- [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
- [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.
- [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
- [12]A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.DOI
- [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
- [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
- [15]S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion, J. Number Theory 67 (1997), 146–161.DOI
- [16]K. Mahler, An unsolved problem on the powers of 3/2, J. Austral. Math. Soc. 8 (1968), 313–321.DOI
- [17]M. Morse and G. A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), 815–866.DOI
- [18]D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125–131.
- [19]R. Stephan, Superlinear complexity of the (3/2)^n steering word, arXiv:2607.11648 (2026).arxiv.org/abs/2607.11648