AFTD Auto-Formalizing Theoretical Domains

halving_partition_count_two_pow

theoremverifiedformalization

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.

  1. 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.

    lines 2–4

      have hset : {p : List ℕ | is_halving_partition 1 p} = {[1]} := by
        ext p
        constructor
  2. 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]}.

    lines 5–22

    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
  3. 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.

    lines 23–26

    uses Set.mem_singleton_iff

        · intro hp
          simp only [Set.mem_singleton_iff] at hp
          rw [hp]
          simp [is_halving_partition]
  4. 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`.

    lines 27–28

    uses Set.ncard_singleton

      change ({p : List ℕ | is_halving_partition 1 p}).ncard = 1
      rw [hset, Set.ncard_singleton]
  5. 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`.

    lines 33–34

    uses halving_partition_count_two_pow_aux_one

      induction e with
      | zero => exact halving_partition_count_two_pow_aux_one
  6. 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.

    lines 35–39

    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

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
See it in the graphDiscuss this resultChallenge it