AdditionChain.lean`

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL: Lean4 Domain Explanation Language

Annotation provenance. This overlay contains 10 curated AI-written annotations and 7190 mechanical source-derived annotations. They have not been human-reviewed as explanations; treat them as unverified and not mathematical authority. Retained generation history: The 71 original curated annotations were produced in a Claude Sonnet 5.5 session at medium effort; Claude Opus 5.5 is recorded in that session as the advisor model, not the direct author. The bulk source-derived expansion was generated mechanically from pinned source comments by tooling developed in a GPT-5.6 Sol session at ultra reasoning; GPT-5.6 Sol did not originate the quoted source prose. On 2026-10-17 the mechanically generated source-comment annotations of the Formal Conjectures, Carleson, FLT, PFR, CompFiles, Mathematics in Lean and Theorem Proving in Lean overlays were regenerated by the same generator after three corrections made in a Claude Sonnet 5.5 session: titles no longer cut a sentence inside mathematics or end on a dangling word, workflow markers are removed from the quoted prose, and declaration names follow the scanner's namespace resolution. The boilerplate step line was dropped, and comments that were only a row of dashes no longer yield annotations. No new prose was written and no human review is claimed.

Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.

Project sources: Pinned project documentation, Formal Conjectures paper, arXiv v1

12 declarations, 0 contain sorry, 0 declared as axioms

Addition chains

An addition chain for $n$ is a strictly increasing sequence $1 = a_0 < a_1 < \cdots < a_r = n$ in which every entry after the first is the sum of two earlier entries. Its length is $r$, the number of additions, and $\ell(n)$ is the least length over all chains ending at $n$.

additionChainLength is an infimum over List ℕ, so an explicit chain bounds it above (additionChainLength_le) but nothing bounds it below until the search is confined. The confinement here is that an addition step at most doubles, so r steps cannot reach past 2 ^ r (getLast_le_two_pow), giving lt_additionChainLength_of_two_pow_lt.

Imports (2)

Imported by 1 file

FormalConjecturesForMathlib.lean

def IsAdditionChain An addition chain is a strictly increasing sequence line 43 source
Source documentation
An addition chain is a strictly increasing sequence $1 = a_0 < a_1 < \cdots < a_r$ in which every entry after the first is the sum of two (not necessarily distinct) earlier entries.
IsAdditionChain c asserts that the list $c$ is such a chain: it starts at $1$, is strictly increasing, and every entry other than $1$ is a sum of two entries of $c$.

no axioms what this means
Statement uses: List, Nat
Proof uses: And, Eq, Option, List.head?, Option.some, OfNat.ofNat, List.Pairwise, LT.lt, Membership.mem, Ne, Exists, HAdd.hAdd
5 instances, coercions and auxiliary constants left out.

Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
```
def IsAdditionChain (c : List ℕ) : Prop :=
…
```
Mentions: c
instance (instance at line 50) line 50 source
Source documentation
Every quantifier in IsAdditionChain is bounded by the list, so membership is decidable and a concrete chain can be checked by decide.
```
instance (c : List ℕ) : Decidable (IsAdditionChain c) := by
…
```
Mentions: c, IsAdditionChain
def additionChainLength The length $\ell(n)$ of $n$: the minimal number of addition steps (the number of entries minus one) over all addition chains ending at $n$ line 55 source
Source documentation
The length $\ell(n)$ of $n$: the minimal number of addition steps (the number of entries minus one) over all addition chains ending at $n$.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat
Proof uses: InfSet.sInf, Set.ofPred, Exists, List, And, IsAdditionChain, Eq, Option, List.getLast?, Option.some, List.length, HAdd.hAdd, OfNat.ofNat
4 instances, coercions and auxiliary constants left out.
```
noncomputable def additionChainLength (n : ℕ) : ℕ :=
…
```
def additionChainSteps The set of step counts realised by chains ending at n line 59 source
Source documentation
The set of step counts realised by chains ending at n.

no axioms what this means
Statement uses: Nat, Set
Proof uses: Set.ofPred, Exists, List, And, IsAdditionChain, Eq, Option, List.getLast?, Option.some, List.length, HAdd.hAdd, OfNat.ofNat
3 instances, coercions and auxiliary constants left out.
```
def additionChainSteps (n : ℕ) : Set ℕ :=
…
```
theorem additionChainLength_eq_sInf line 62 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Eq, additionChainLength, InfSet.sInf, additionChainSteps
Proof uses: rfl
1 instances, coercions and auxiliary constants left out.
theorem additionChainLength_le Exhibiting a chain bounds ℓ above line 66 source
Source documentation
Exhibiting a chain bounds ℓ above.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, List, IsAdditionChain, Eq, Option, List.getLast?, Option.some, List.length, HAdd.hAdd, OfNat.ofNat, LE.le, additionChainLength
Proof uses: Nat.sInf_le, Set.ofPred, Exists, And, Exists.intro, And.intro
7 instances, coercions and auxiliary constants left out.
```
theorem additionChainLength_le {n r : ℕ} (c : List ℕ) (hc : IsAdditionChain c)
    (hlast : c.getLast? = some n) (hlen : c.length = r + 1) : additionChainLength n ≤ r :=
…
```
Mentions: c, IsAdditionChain, additionChainLength
theorem additionChainSteps_nonempty line 70 source
no axioms what this means
Statement uses: Nat, List, IsAdditionChain, Eq, Option, List.getLast?, Option.some, List.length, HAdd.hAdd, OfNat.ofNat, Set.Nonempty, additionChainSteps
Proof uses: Exists.intro, Membership.mem, Set, And, And.intro
7 instances, coercions and auxiliary constants left out.
theorem IsAdditionChain.one_le_of_mem line 74 source
standard axioms: propext what this means
Statement uses: List, Nat, IsAdditionChain, Membership.mem, LE.le, OfNat.ofNat
Proof uses: Eq, Option, List.head?, Option.some, And, List.Pairwise, LT.lt, Ne, Exists, HAdd.hAdd, List.nil, False.elim, Eq.mp, False, Eq.symm, List.cons, Or, Iff.mp, List.mem_cons, le_rfl and 5 more
15 instances, coercions and auxiliary constants left out.

Tactic trace: 10 steps
Open to load the checked before-and-after goal states.
theorem IsAdditionChain.dropLast Dropping the last entry of a chain leaves a chain line 88 source
Source documentation
Dropping the last entry of a chain leaves a chain. The entries are positive, so a summand of the last entry is never the last entry itself and so survives the drop.

standard axioms: Quot.sound, propext what this means
Statement uses: List, Nat, IsAdditionChain, HAppend.hAppend, List.cons, List.nil, Ne
Proof uses: Eq, Option, List.head?, Option.some, OfNat.ofNat, And, List.Pairwise, LT.lt, Membership.mem, Exists, HAdd.hAdd, And.intro, False.elim, Eq.mp, False, Eq.trans, Not, True, congrArg, eq_self and 20 more
17 instances, coercions and auxiliary constants left out.

Tactic trace: 31 steps
Open to load the checked before-and-after goal states.
```
theorem IsAdditionChain.dropLast {ys : List ℕ} {y : ℕ} (h : IsAdditionChain (ys ++ [y]))
    (hys : ys ≠ []) : IsAdditionChain ys := by
…
```
Mentions: IsAdditionChain
theorem IsAdditionChain.getLast_le_two_pow Every step at most doubles, so a chain of r steps cannot reach past 2 ^ r line 111 source
Source documentation
Every step at most doubles, so a chain of r steps cannot reach past 2 ^ r.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: List, Nat, IsAdditionChain, Ne, List.nil, LE.le, List.getLast, HPow.hPow, OfNat.ofNat, HSub.hSub, List.length
Proof uses: List.reverseRecOn, False.elim, Eq.mp, False, Eq.trans, Not, Eq, True, congrArg, eq_self, not_true_eq_false, HAppend.hAppend, List.cons, Eq.mpr, id, List.append_ne_nil_of_right_ne_nil, List.cons_ne_nil, List.getLast_append_singleton, Or, eq_or_ne and 41 more
49 instances, coercions and auxiliary constants left out.

Tactic trace: 50 steps
Open to load the checked before-and-after goal states.
```
theorem IsAdditionChain.getLast_le_two_pow {c : List ℕ} (h : IsAdditionChain c) (hne : c ≠ []) :
    c.getLast hne ≤ 2 ^ (c.length - 1) := by
…
```
Mentions: c, IsAdditionChain
theorem le_two_pow_additionChainLength The doubling bound, transported to ℓ: reaching n takes at least log₂ n steps line 154 source
Source documentation
The doubling bound, transported to ℓ: reaching n takes at least log₂ n steps.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Set.Nonempty, additionChainSteps, LE.le, HPow.hPow, OfNat.ofNat, additionChainLength
Proof uses: List, And, IsAdditionChain, Eq, Option, List.getLast?, Option.some, List.length, HAdd.hAdd, InfSet.sInf, Membership.mem, Set, Nat.sInf_mem, Ne, List.nil, False, False.elim, Eq.mp, eq_false', Option.none and 11 more
22 instances, coercions and auxiliary constants left out.

Tactic trace: 10 steps
Open to load the checked before-and-after goal states.
```
theorem le_two_pow_additionChainLength {n : ℕ} (hne : (additionChainSteps n).Nonempty) :
    n ≤ 2 ^ additionChainLength n := by
…
```
Mentions: additionChainSteps, additionChainLength
theorem lt_additionChainLength_of_two_pow_lt The lower-bound tool: r steps cannot reach past 2 ^ r line 166 source
Source documentation
The lower-bound tool: r steps cannot reach past 2 ^ r.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Set.Nonempty, additionChainSteps, LT.lt, HPow.hPow, OfNat.ofNat, additionChainLength
Proof uses: Decidable.byContradiction, Not, LE.le, le_two_pow_additionChainLength, Nat.pow_le_pow_right, GT.gt, Eq.mp
21 instances, coercions and auxiliary constants left out.

Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
```
theorem lt_additionChainLength_of_two_pow_lt {n r : ℕ} (hne : (additionChainSteps n).Nonempty)
    (h : 2 ^ r < n) : r < additionChainLength n := by
…
```
Mentions: additionChainSteps, additionChainLength