HEXAGONbeta

Superlinear complexity of the (3/2)n(3/2)^n steering word

A mix of human-written and AI-generated textHuman understanding: all partsmath.NT — Number Theorymath.CO — Combinatorics

Contributed by Ralf Stephan ↗

Version 1 / Oct 20, 2026/ arXiv: 2607.11648 / CC0 1.0

Abstract

Write (3/2)n=mn+εn(3/2)^n = m_n + \varepsilon_n with mnm_n the nearest integer and εn∈[−12,12)\varepsilon_n\in[-\tfrac12,\tfrac12), and let T=(tn)T=(t_n), tn=2mn+1−3mnt_n=2m_{n+1}-3m_n, be the resulting \emph{steering word}: the step-by-step record of the map x↦32xx\mapsto\tfrac32 x on the orbit of 1, coded by nearest-integer rounding. We prove that the subword complexity pT(k)p_T(k) of TT is superlinear, pT(k)/k→∞p_T(k)/k\to\infty. A pigeonhole argument reduces this to exponential pair repulsion of the orbit modulo one, which we establish by two applications of the pp-adic Subspace Theorem: once in three variables, which handles all gaps between the two orbit points at once, and once in two variables (Ridout's theorem) for the single degenerate family of constant gap. The argument is completely formalized in Lean~4, together with the Subspace Theorem it uses.

Provenance statement

Author directed the LLM (Fable 5) at finding new results in the uniform distribution mod one of (3/2)^n problem space. Author directed Opus 4.8 and 5 to formalize Fable's plan, and Fable to write the draft paper, which underwent several versions. Yann Bugeaud read and commented on the paper; he also suggested the existence of a simplified proof, which Fable 5.1 subsequently found. Author directed LLM to adapt the paper accordingly.

Formalizations

References

  1. B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers I. Expansions in integer bases , Ann. of Math. (2) 165 (2007), no. 2, 547--565.
  2. J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations , Cambridge University Press, Cambridge, 2003.
  3. Y. Bugeaud and J.-H. Evertse, On two notions of complexity of algebraic numbers , Acta Arith. 133 (2008), no. 3, 221--250.
  4. E. Bombieri and W. Gubler, Heights in Diophantine geometry , New Mathematical Monographs 4 , Cambridge University Press, Cambridge, 2006.
  5. J. Cassaigne, Constructing infinite words of intermediate complexity , Developments in Language Theory (DLT 2002), Lecture Notes in Comput. Sci. 2450 , Springer, Berlin, 2003, 173--184.
  6. J. Cassaigne and F. Nicolas, Factor complexity , in: V. Berthé and M. Rigo (eds.), Combinatorics, automata and number theory, Encyclopedia Math. Appl. 135 , Cambridge University Press, Cambridge, 2010, 163--247.
  7. A. Cobham, Uniform tag sequences , Math. Systems Theory 6 (1972), 164--192.
  8. P. Corvaja and U. Zannier, On the rational approximations to the powers of an algebraic number: solution of two problems of Mahler and Mendès France , Acta Math. 193 (2004), no. 2, 175--191. arXiv:math/0403522.arXiv
  9. A. Dubickas, On integer sequences generated by linear maps , Glasg. Math. J. 51 (2009), no. 2, 243--252.
  10. A. Dubickas and A. Novikas, Integer parts of powers of rational numbers , Math. Z. 251 (2005), no. 3, 635--648.
Show all 25 referencesShow fewer references
  1. S. Akiyama, C. Frougny, and J. Sakarovitch, Powers of rationals modulo 11 and rational base number systems , Israel J. Math. 168 (2008), 53--91.
  2. F. Durand, B. Host, and C. Skau, Substitution dynamical systems, Bratteli diagrams and dimension groups , Ergodic Theory Dynam. Systems 19 (1999), no. 4, 953--993.
  3. H. Erazo and C. G. Moreira, The Heinis spectrum has non-empty interior , Combinatorics on Words (WORDS 2025), Lecture Notes in Comput. Sci., vol 15729. Springer, Cham, 2025.
  4. S. Ferenczi, Complexity of sequences and dynamical systems , Discrete Math. 206 (1999), no. 1--3, 145--154.
  5. L. Flatto, J. C. Lagarias, and A. D. Pollington, On the range of fractional parts {ξ(p/q)n}\{\xi(p/q)^n\} , Acta Arith. 70 (1995), no. 2, 125--147.
  6. A. Hilion and G. Levitt, A Pansiot-type subword complexity theorem for automorphisms of free groups , Israel J. Math. 270, 59–93 (2025). arXiv:2208.00676.arXiv
  7. J. Kopra, On the trace subshifts of fractional multiplication automata , Theoret. Comput. Sci. 851 (2021), 92--110.
  8. K. Mahler, On the fractional parts of the powers of a rational number II , Mathematika 4 (1957), 122--124.
  9. M. Morse and G. A. Hedlund, Symbolic dynamics , Amer. J. Math. 60 (1938), no. 4, 815--866.
  10. J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés , Automata, Languages and Programming (ICALP 1984), Lecture Notes in Comput. Sci. 172 , Springer, Berlin, 1984, 380--389.
  11. S. Puzynina, Complexity of infinite words , Machines, Computations, and Universality (MCU 2024), Lecture Notes in Comput. Sci. 15270 , Springer, Cham, 2025, 1--16.
  12. P. S. Nair, V. Kumar, and S. S. Rout, Algebraic approximations to linear combinations of SS-units , arXiv:2506.02898 (v3, 18 Nov 2025).arXiv
  13. D. Ridout, Rational approximations to algebraic numbers , Mathematika 4 (1957), 125--131.
  14. H. P. Schlickewei, The p\mathfrak{p}-adic Thue--Siegel--Roth--Schmidt theorem , Arch. Math. (Basel) 29 (1977), no. 3, 267--270.
  15. W. Zudilin, A new lower bound for ∥(3/2)k∥\lVert(3/2)^k\rVert , J. Théor. Nombres Bordeaux 19 (2007), no. 1, 311--323.

Version history

  1. v1Submitted by Ralf StephanInitial depositCurrentOct 20, 2026