halving_partition_count_two_pow
For every natural number e, the number of halving partitions of 2^e is equal to 1, that is, halving_partition_count (2 ^ e) = 1.
Statement
theorem halving_partition_count_two_pow (e : ℕ) :
halving_partition_count (2 ^ e) = 1- Formalizes
- arXiv:2611.01243 Lemma 2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- halving_partition_count_two_mulFor every natural number n, the number of halving partitions of 2n equals the number of halving partitions of n, that is,…
- halving_partition_countThe number of halving partitions of $n$, denoted $a(n)$, is the cardinality (using
Set.ncard) of the set of lists $p$ of positive… - is_halving_partitionA sequence of positive integers $(p_1, \dots, p_k)$ is a halving partition of $n \ge 1$ if…
Read back from the Lean
For every natural number $e$, the number of halving partitions of $2^e$ (given by halving_partition_count (2 ^ e)) is equal to 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by induction on the exponent e. The base case e = 0 reduces to showing that 1 has a unique halving partition, namely [1], which is established by showing that any list of positive integers summing to 1 must have length 1. For the inductive step, 2^(e+1) is factored as 2 * 2^e, and halving_partition_count_two_mul shows that halving partitions of 2 * 2^e are equinumerous with those of 2^e, which equals 1 by the induction hypothesis.
The set of halving partitions of 1 is equal to {[1]}, provided each set is contained in the other.
We state as an intermediate goal that the set of halving partitions of 1 is the singleton set {[1]}. By set extensionality (`ext`), two sets are equal if they contain the same elements, and `constructor` reduces this equality to two subset inclusions: showing that every halving partition of 1 is in {[1]}, and that [1] is in the set of halving partitions of 1.
have hset : {p : List ℕ | is_halving_partition 1 p} = {[1]} := by ext p constructor
Any halving partition of 1 must be the singleton list [1].
Let p be a halving partition of 1. Unfolding the definition (`Set.mem_ofPred_eq`), its elements are positive integers and their sum is 1. If p were empty, its sum would be 0 rather than 1, so p is nonempty. Since every element of p is positive, each is at least 1, which implies that the length of p is at most its sum (`List.length_le_sum_of_one_le`), so p has length at most 1. Because p is nonempty, its length is strictly positive (`List.length_pos_iff.mpr`), forcing its length to be exactly 1. By `List.length_eq_one_iff.mp`, p has the form [a], and since its sum is a = 1 (`List.sum_singleton`), we conclude p = [1], so p ∈ {[1]}.
uses
Set.mem_ofPred_eq,List.length_le_sum_of_one_le,List.length_pos_iff.mpr,List.length_eq_one_iff.mp,List.sum_singleton· intro hp simp only [Set.mem_ofPred_eq, is_halving_partition] at hp obtain ⟨hpos, hsum, hcase⟩ := hp have hne : p ≠ [] := by intro h rw [h] at hsum simp at hsum have hlen : p.length ≤ 1 := by have h1 : ∀ i ∈ p, 1 ≤ i := fun i hi => hpos i hi have := List.length_le_sum_of_one_le p h1 omega have hlen1 : p.length = 1 := by have : 0 < p.length := List.length_pos_iff.mpr hne omega obtain ⟨a, rfl⟩ := List.length_eq_one_iff.mp hlen1 simp only [List.sum_singleton] at hsum rw [hsum] rfl
The list [1] is a valid halving partition of 1.
For the reverse inclusion, if p ∈ {[1]}, then p = [1] (`Set.mem_singleton_iff`). Substituting [1] into the definition of a halving partition, all conditions hold: its single element 1 is positive, its sum is 1, its first element satisfies (1 + 1) / 2 = 1, and the pairwise halving chaining condition holds vacuously for a list of length 1. Simplification verifies all these conditions.
uses
Set.mem_singleton_iff· intro hp simp only [Set.mem_singleton_iff] at hp rw [hp] simp [is_halving_partition]
The number of halving partitions of 1 is 1.
The count of halving partitions of 1 is by definition the cardinality (`ncard`) of the set of halving partitions of 1. Rewriting this set to {[1]} using the equality proved above, its cardinality is 1 by `Set.ncard_singleton`.
uses
Set.ncard_singletonchange ({p : List ℕ | is_halving_partition 1 p}).ncard = 1 rw [hset, Set.ncard_singleton]
For e = 0, halving_partition_count (2^0) = 1.
We prove the main theorem by induction on e. In the base case e = 0, 2^0 = 1, so the goal halving_partition_count 1 = 1 is closed directly by the auxiliary lemma `halving_partition_count_two_pow_aux_one`.
uses
halving_partition_count_two_pow_aux_oneinduction e with | zero => exact halving_partition_count_two_pow_aux_one
For the successor step, halving_partition_count (2^(e+1)) = 1 assuming halving_partition_count (2^e) = 1.
In the inductive step, 2^(e+1) rewrites to 2^e * 2 by `pow_succ`, and multiplication commutes (`mul_comm`) to give 2 * 2^e. By `halving_partition_count_two_mul`, the count of halving partitions of 2 * 2^e equals that of 2^e. Applying the induction hypothesis ih completes the proof.
uses
pow_succ,mul_comm,halving_partition_count_two_mul| succ e ih => rw [pow_succ] rw [mul_comm] rw [halving_partition_count_two_mul] exact ih
Set.mem_ofPred_eq- An element x belongs to the set defined by a predicate p if and only if p(x) holds.
List.length_le_sum_of_one_le- If every element in a list of natural numbers is at least 1, then the length of the list is at most the sum of its elements.
List.length_pos_iff.mpr- A list has strictly positive length if and only if it is nonempty (specifically, nonemptiness implies positive length).
List.length_eq_one_iff.mp- A list has length 1 if and only if it is a singleton list [a] for some element a.
List.sum_singleton- The sum of a singleton list [x] is x.
Set.mem_singleton_iff- An element a belongs to the singleton set {b} if and only if a = b.
Set.ncard_singleton- The cardinality of a singleton set {a} is 1.
halving_partition_count_two_pow_aux_one- The number of halving partitions of 1 is 1.
pow_succ- For any base a in a monoid and natural number n, a^(n + 1) = a^n * a.
mul_comm- Multiplication is commutative, that is, a * b = b * a.
halving_partition_count_two_mul- For every natural number n, the number of halving partitions of 2 * n equals the number of halving partitions of n.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem halving_partition_count_two_pow_aux_one : halving_partition_count 1 = 1 := by have hset : {p : List ℕ | is_halving_partition 1 p} = {[1]} := by ext p constructor · intro hp simp only [Set.mem_ofPred_eq, is_halving_partition] at hp obtain ⟨hpos, hsum, hcase⟩ := hp have hne : p ≠ [] := by intro h rw [h] at hsum simp at hsum have hlen : p.length ≤ 1 := by have h1 : ∀ i ∈ p, 1 ≤ i := fun i hi => hpos i hi have := List.length_le_sum_of_one_le p h1 omega have hlen1 : p.length = 1 := by have : 0 < p.length := List.length_pos_iff.mpr hne omega obtain ⟨a, rfl⟩ := List.length_eq_one_iff.mp hlen1 simp only [List.sum_singleton] at hsum rw [hsum] rfl · intro hp simp only [Set.mem_singleton_iff] at hp rw [hp] simp [is_halving_partition] change ({p : List ℕ | is_halving_partition 1 p}).ncard = 1 rw [hset, Set.ncard_singleton]/-- For every natural number e, the number of halving partitions of 2^e is equal to 1. -/theorem halving_partition_count_two_pow (e : ℕ) : halving_partition_count (2 ^ e) = 1 := by induction e with | zero => exact halving_partition_count_two_pow_aux_one | succ e ih => rw [pow_succ] rw [mul_comm] rw [halving_partition_count_two_mul] exact ih