Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Adamczewski–Bugeaud Theorem 1: complexity of algebraic expansions

Open
BorelNormality.adamczewski_bugeaud_complexity

by LG · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorics-on-wordsnumber-theorytranscendence

Adamczewski–Bugeaud (2007), Theorem 1. Let b≥2b \ge 2b≥2 be an integer and let xxx be an irrational algebraic real number. The complexity function p(n)p(n)p(n) of the base-bbb expansion of xxx — the number of distinct blocks of nnn digits occurring in it — satisfies

lim inf⁡n→∞p(n)n=+∞.\liminf_{n \to \infty} \frac{p(n)}{n} = +\infty.n→∞liminf​np(n)​=+∞.

This is the strongest known general result about the digit expansions of irrational algebraic numbers, and the closest approach to Borel's conjecture to date: a number normal in base bbb has p(n)=bnp(n) = b^np(n)=bn, so the theorem is a very weak shadow of the conjectured behaviour. Its proof is a combinatorial transcendence criterion derived from the Schmidt Subspace Theorem. In particular every irrational real number with sub-linear complexity (p(n)=O(n)p(n) = O(n)p(n)=O(n)) is transcendental.

Formalization Note. The limit inferior is taken in ENNReal (R≥0∪{∞}\mathbb{R}_{\ge 0}\cup\{\infty\}R≥0​∪{∞}) along Filter.atTop, with value ⊤ (+∞+\infty+∞); this is equivalent to p(n)/n→+∞p(n)/n \to +\inftyp(n)/n→+∞. The complexity function is BorelNormality.complexity from the mission's definition file.

Preamble
import Mathlib
import Definitions.Def_Normal_Core
import Definitions.Def_BorelNormality_Complexity

set_option autoImplicit false
Formal statement
namespace BorelNormality

theorem adamczewski_bugeaud_complexity (x : ℝ) (hx : IsAlgebraic ℚ x) (hi : Irrational x)
    (b : ℕ) (hb : 2 ≤ b) :
    Filter.liminf (fun n : ℕ => (complexity b x n : ENNReal) / (n : ENNReal)) Filter.atTop = ⊤ := by sorry

end BorelNormality
Source
B. Adamczewski, Y. Bugeaud, On the complexity of algebraic numbers I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565, Theorem 1 (Section 2), https://doi.org/10.4007/annals.2007.165.547. Verbatim: 'Let b ≥ 2 be an integer. The complexity function of the b-ary expansion of every irrational algebraic number satisfies liminf_{n→∞} p(n)/n = +∞.'
Read-back

What the Lean code literally says, in plain math · GLM (Z.ai), same-agent blind pass — not an independent sub-agent

For every real number xxx, every proof that xxx is algebraic over Q\mathbb{Q}Q (a nonzero polynomial over Q\mathbb{Q}Q vanishes at xxx), every proof that xxx is irrational (xxx is not in the range of the coercion Q→R\mathbb{Q} \to \mathbb{R}Q→R), every natural number bbb and every proof of 2≤b2 \le b2≤b: the limit inferior, along the cofinite filter on N\mathbb{N}N, of the sequence n↦p(n)/nn \mapsto p(n)/nn↦p(n)/n computed in R≥0∪{∞}\mathbb{R}_{\ge 0}\cup\{\infty\}R≥0​∪{∞} equals +∞+\infty+∞. Here p(n)p(n)p(n) is BorelNormality.complexity b x n, the number of distinct length-nnn words over {0,…,b−1}\{0, \dots, b-1\}{0,…,b−1} occurring in the digit sequence n↦⌊xbn+1⌋ mod bn \mapsto \lfloor x b^{n+1}\rfloor \bmod bn↦⌊xbn+1⌋modb. At n=0n = 0n=0 the denominator is 000 and the quotient is +∞+\infty+∞ (since p(0)=1≠0p(0) = 1 \ne 0p(0)=1=0); the limit inferior along atTop is unaffected by this and any finite set of initial terms. The conclusion lim inf⁡=+∞\liminf = +\inftyliminf=+∞ is equivalent to the whole sequence tending to +∞+\infty+∞; the statement uses lim inf⁡\liminfliminf, matching the source.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me