AFTD Auto-Formalizing Theoretical Domains

halving_partition_count_two_mul

theoremverifiedformalization

For every natural number n, the number of halving partitions of 2n equals the number of halving partitions of n, that is, halving_partition_count (2 * n) = halving_partition_count n.

Statement

theorem halving_partition_count_two_mul (n : ℕ) :
    halving_partition_count (2 * n) = halving_partition_count n
Formalizes
arXiv:2611.01243 Lemma 2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
Used by 2

Read back from the Lean

For every natural number $n$, the halving partition count of $2n$ equals the halving partition count of $n$.

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 constructing a bijection between the halving partitions of n and the halving partitions of 2n via the map p ↦ n :: p for n > 0 (the case n = 0 is trivial by definition). For any halving partition of 2n, its first element must equal ⌊2n / 2⌋ = n, and its remaining elements form a halving partition of 2n - n = n. Conversely, prepending n to any halving partition of n produces a valid halving partition of 2n because n = 2n / 2 and the chain relation holds between n and the leading element of the partition.

  1. For n > 0, every element of n :: p is strictly positive whenever p is a halving partition of n.

    Unfolding the definition of is_halving_partition for n :: p requires three conditions: positivity of all elements, the sum equalling 2n, and the halving chain condition. For positivity, any element x ∈ n :: p is either n (which is positive by the assumption hn) or belongs to p (which is positive because p is a halving partition of n).

    lines 1–9

    uses List.mem_cons.mp

    private theorem halving_partition_count_two_mul_cons_mem (n : ℕ) (p : List ℕ)
        (hn : 0 < n) (hp : is_halving_partition n p) :
        is_halving_partition (2*n) (n :: p) := by
      unfold is_halving_partition at hp ⊢
      refine ⟨?_, ?_, ?_⟩
      · intro x hx
        rcases List.mem_cons.mp hx with rfl | hx
        · exact hn
        · exact hp.1 x hx
  2. The sum of the list n :: p equals 2n. automation

    The sum of n :: p is n + p.sum. Since p is a halving partition of n, its sum is n, so the sum is n + n = 2n, which is verified by linear arithmetic.

    lines 10–11

    uses List.sum_cons

      · simp only [List.sum_cons, hp.2.1]
        omega
  3. The list n :: p satisfies the halving condition and chain property for 2n.

    The leading element n satisfies n = (2n) / 2 by integer division. For the chain condition on n :: p, if p is empty, [n] is a singleton chain. If p = q :: tail, the hypothesis on p ensures that q is either n / 2 or (n + 1) / 2 and that p is chained, so prepending n maintains the chain property.

    lines 12–20

    uses List.IsChain.singleton, List.IsChain.cons_cons

      · change (n = 2*n/2 ∨ n = (2*n+1)/2) ∧
          List.IsChain (fun x y => y = x/2 ∨ y = (x+1)/2) (n :: p)
        refine ⟨by omega, ?_⟩
        cases p with
        | nil => exact List.IsChain.singleton n
        | cons q tail =>
          obtain ⟨hq, hchain⟩ := hp.2.2
          exact List.IsChain.cons_cons hq hchain
    
  4. Any halving partition q of 2n (with n > 0) is non-empty.

    Unpacking the definition of a halving partition on q, an empty partition would require 2n = 0, which contradicts n > 0.

    lines 21–27

    private theorem halving_partition_count_two_mul_exists (n : ℕ) (q : List ℕ) (hn : 0 < n)
        (hq : is_halving_partition (2*n) q) :
        ∃ p, is_halving_partition n p ∧ q = n :: p := by
      unfold is_halving_partition at hq
      rcases hq with ⟨hpos, hsum, hmatch⟩
      cases q with
      | nil => simp at hmatch; omega
  5. The first element q₁ of q must equal n.

    Writing q = q₁ :: tail, the halving condition requires q₁ = (2n) / 2 or q₁ = (2n + 1) / 2. By integer division, both expressions evaluate to n, so q₁ = n.

    lines 28–31

      | cons q1 tail =>
        obtain ⟨hq1, hchain⟩ := hmatch
        have hq1n : q1 = n := by
          rcases hq1 with h | h <;> omega
  6. The tail of q has sum n and is non-empty, so it can be written as q₂ :: tail₂.

    Since q₁ = n and q₁.sum + tail.sum = 2n, the tail has sum n. Because n > 0, the tail cannot be empty (as [].sum = 0), so it has a head q₂ and a remainder tail₂.

    lines 32–38

    uses List.sum_cons

        simp only [List.sum_cons] at hsum
        have htailsum : tail.sum = n := by omega
        have htailne : tail ≠ [] := by
          intro h; subst h; simp at htailsum; omega
        cases tail with
        | nil => exact absurd rfl htailne
        | cons q2 tail2 =>
  7. The element q₂ satisfies q₂ ∈ {n / 2, (n + 1) / 2}, and q₂ :: tail₂ is chained under the halving relation.

    Substituting q₁ = n into the chain condition for n :: q₂ :: tail₂, the first relation asserts that q₂ is n / 2 or (n + 1) / 2. Extracting the remainder of the chain gives that q₂ :: tail₂ is also chained.

    lines 39–43

    uses List.IsChain.rel, List.isChain_cons_cons.mp

          rw [hq1n] at hchain
          have hR : (fun x y => y = x/2 ∨ y = (x+1)/2) n q2 :=
            List.IsChain.rel (R := fun x y => y = x/2 ∨ y = (x+1)/2) hchain
          have hchain' : List.IsChain (fun x y => y = x/2 ∨ y = (x+1)/2) (q2 :: tail2) :=
            (List.isChain_cons_cons.mp hchain).2
  8. The tail q₂ :: tail₂ is a halving partition of n, and q = n :: (q₂ :: tail₂).

    The tail satisfies all four requirements of a halving partition of n: its elements are positive (inherited from q), it sums to n, its head q₂ satisfies the halving condition for n, and it is a halving chain. Since q₁ = n, q decomposes as n :: (q₂ :: tail₂).

    lines 44–48

    uses List.mem_cons_of_mem

          refine ⟨q2 :: tail2, ?_, ?_⟩
          · unfold is_halving_partition
            exact ⟨by intro x hx; exact hpos x (List.mem_cons_of_mem _ hx), htailsum, hR, hchain'⟩
          · simp [hq1n]
    
  9. For n = 0, halving_partition_count (2 * 0) = halving_partition_count 0 holds by definition.

    We split on whether n = 0 or n > 0. When n = 0, 2 * 0 = 0, so both sides are identical definitionally.

    lines 49–54

    uses Nat.eq_zero_or_pos

    /-- For every natural number n, the number of halving partitions of 2n equals the number of halving partitions of n. -/
    theorem halving_partition_count_two_mul (n : ℕ) :
        halving_partition_count (2 * n) = halving_partition_count n := by
      rcases Nat.eq_zero_or_pos n with hn | hn
      · subst hn
        rfl
  10. For n > 0, it suffices to show that p ↦ n :: p is a bijection between halving partitions of n and halving partitions of 2n.

    Unfolding halving_partition_count, we need to show that the sets of partitions of n and 2n have the same cardinality. By Set.ncard_congr, it suffices to exhibit a well-defined, injective, and surjective mapping, chosen here to be p ↦ n :: p.

    lines 55–57

    uses Set.ncard_congr

      · unfold halving_partition_count
        symm
        refine Set.ncard_congr (fun p _ => n :: p) ?_ ?_ ?_
  11. The mapping p ↦ n :: p maps halving partitions of n into halving partitions of 2n.

    This is the content of the helper lemma halving_partition_count_two_mul_cons_mem.

    lines 58–59

    uses halving_partition_count_two_mul_cons_mem

        · intro p hp
          exact halving_partition_count_two_mul_cons_mem n p hn hp
  12. The mapping p ↦ n :: p is injective.

    If n :: p = n :: q, the injectivity of list construction (List.cons.inj) implies that p = q.

    lines 60–61

    uses List.cons.inj

        · intro p q hp hq h
          exact (List.cons.inj h).2
  13. The mapping p ↦ n :: p is surjective.

    Given any halving partition q of 2n, the helper lemma halving_partition_count_two_mul_exists yields a halving partition p of n with q = n :: p, completing the bijection.

    lines 62–64

    uses halving_partition_count_two_mul_exists

        · intro q hq
          obtain ⟨p, hp, hpq⟩ := halving_partition_count_two_mul_exists n q hn hq
          exact ⟨p, hp, hpq.symm⟩
List.mem_cons.mp
An element belongs to a list a :: l if and only if it equals a or belongs to l.
List.sum_cons
The sum of a list with head a and tail l equals a + sum(l).
List.IsChain.singleton
A singleton list [a] satisfies the chain condition for any binary relation.
List.IsChain.cons_cons
If R a b holds and the list b :: l is chained under R, then a :: b :: l is chained under R.
List.IsChain.rel
If a list a :: b :: l is chained under R, then the relation R a b holds between its first two elements.
List.isChain_cons_cons.mp
If a list a :: b :: l is chained under R, then R a b holds and the tail b :: l is also chained under R.
List.mem_cons_of_mem
If an element belongs to l, then it belongs to y :: l.
Nat.eq_zero_or_pos
Every natural number n is either equal to 0 or strictly positive.
Set.ncard_congr
If a function between two sets is well-defined, injective, and surjective, then the two sets have equal cardinality.
halving_partition_count_two_mul_cons_mem
For n > 0, prepending n to any halving partition of n yields a halving partition of 2n.
List.cons.inj
If two prepended lists a :: l and a' :: l' are equal, then their heads are equal (a = a') and their tails are equal (l = l').
halving_partition_count_two_mul_exists
For n > 0, every halving partition of 2n can be written as n :: p for some halving partition p 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

private theorem halving_partition_count_two_mul_cons_mem (n : ℕ) (p : List ℕ)    (hn : 0 < n) (hp : is_halving_partition n p) :    is_halving_partition (2*n) (n :: p) := by  unfold is_halving_partition at hp ⊢  refine ⟨?_, ?_, ?_⟩  · intro x hx    rcases List.mem_cons.mp hx with rfl | hx    · exact hn    · exact hp.1 x hx  · simp only [List.sum_cons, hp.2.1]    omega  · change (n = 2*n/2 ∨ n = (2*n+1)/2) ∧      List.IsChain (fun x y => y = x/2 ∨ y = (x+1)/2) (n :: p)    refine ⟨by omega, ?_⟩    cases p with    | nil => exact List.IsChain.singleton n    | cons q tail =>      obtain ⟨hq, hchain⟩ := hp.2.2      exact List.IsChain.cons_cons hq hchainprivate theorem halving_partition_count_two_mul_exists (n : ℕ) (q : List ℕ) (hn : 0 < n)    (hq : is_halving_partition (2*n) q) :    ∃ p, is_halving_partition n p ∧ q = n :: p := by  unfold is_halving_partition at hq  rcases hq with ⟨hpos, hsum, hmatch⟩  cases q with  | nil => simp at hmatch; omega  | cons q1 tail =>    obtain ⟨hq1, hchain⟩ := hmatch    have hq1n : q1 = n := by      rcases hq1 with h | h <;> omega    simp only [List.sum_cons] at hsum    have htailsum : tail.sum = n := by omega    have htailne : tail ≠ [] := by      intro h; subst h; simp at htailsum; omega    cases tail with    | nil => exact absurd rfl htailne    | cons q2 tail2 =>      rw [hq1n] at hchain      have hR : (fun x y => y = x/2 ∨ y = (x+1)/2) n q2 :=        List.IsChain.rel (R := fun x y => y = x/2 ∨ y = (x+1)/2) hchain      have hchain' : List.IsChain (fun x y => y = x/2 ∨ y = (x+1)/2) (q2 :: tail2) :=        (List.isChain_cons_cons.mp hchain).2      refine ⟨q2 :: tail2, ?_, ?_⟩      · unfold is_halving_partition        exact ⟨by intro x hx; exact hpos x (List.mem_cons_of_mem _ hx), htailsum, hR, hchain'⟩      · simp [hq1n]/-- For every natural number n, the number of halving partitions of 2n equals the number of halving partitions of n. -/theorem halving_partition_count_two_mul (n : ℕ) :    halving_partition_count (2 * n) = halving_partition_count n := by  rcases Nat.eq_zero_or_pos n with hn | hn  · subst hn    rfl  · unfold halving_partition_count    symm    refine Set.ncard_congr (fun p _ => n :: p) ?_ ?_ ?_    · intro p hp      exact halving_partition_count_two_mul_cons_mem n p hn hp    · intro p q hp hq h      exact (List.cons.inj h).2    · intro q hq      obtain ⟨p, hp, hpq⟩ := halving_partition_count_two_mul_exists n q hn hq      exact ⟨p, hp, hpq.symm⟩
See it in the graphDiscuss this resultChallenge it