halving_partition_count_two_mul
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…
- halving_partition_countThe number of halving partitions of $n$, denoted $a(n)$, is the cardinality (using
- Used by 2
- halving_partition_kernel_even_reductionFor all natural numbers e, r, and n, the halving partition count satisfies halving_partition_count (2 ^ (e + 1) * n + 2 * r) =…
- halving_partition_count_two_powFor every natural number e, the number of halving partitions of 2^e is equal to 1, that is, halving_partition_count (2 ^ e) = 1.
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.
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).
uses
List.mem_cons.mpprivate 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
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.
uses
List.sum_cons· simp only [List.sum_cons, hp.2.1] omega
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.
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
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.
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
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.
| cons q1 tail => obtain ⟨hq1, hchain⟩ := hmatch have hq1n : q1 = n := by rcases hq1 with h | h <;> omegaThe 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₂.
uses
List.sum_conssimp 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 =>
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.
uses
List.IsChain.rel,List.isChain_cons_cons.mprw [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
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₂).
uses
List.mem_cons_of_memrefine ⟨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 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.
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
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.
uses
Set.ncard_congr· unfold halving_partition_count symm refine Set.ncard_congr (fun p _ => n :: p) ?_ ?_ ?_
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.
uses
halving_partition_count_two_mul_cons_mem· intro p hp exact halving_partition_count_two_mul_cons_mem n p hn hp
The mapping p ↦ n :: p is injective.
If n :: p = n :: q, the injectivity of list construction (List.cons.inj) implies that p = q.
uses
List.cons.inj· intro p q hp hq h exact (List.cons.inj h).2
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.
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.
- Integer division equalities on natural numbers, such as 2n / 2 = n and (2n + 1) / 2 = n, are discharged automatically by the omega tactic.
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.
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⟩