halving_partition_kernel_even_reduction
For all natural numbers e, r, and n, the halving partition count satisfies halving_partition_count (2 ^ (e + 1) * n + 2 * r) = halving_partition_count (2 ^ e * n + r).
Statement
theorem halving_partition_kernel_even_reduction (e r n : ℕ) :
halving_partition_count (2 ^ (e + 1) * n + 2 * r) = halving_partition_count (2 ^ e * n + r)- Source
- arXiv:2611.01243 Sec. 6, paragraph 2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
Read back from the Lean
For all natural numbers $e$, $r$, and $n$, the number of halving partitions (halving_partition_count) of $2^{e+1} n + 2r$ is equal to the number of halving partitions of $2^e n + r$.
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 proof factors out a common factor of 2 from the input 2 ^ (e + 1) * n + 2 * r, rewriting it as 2 * (2 ^ e * n + r). The theorem then follows immediately by applying halving_partition_count_two_mul, which states that doubling an integer leaves its halving partition count invariant.
The argument 2 ^ (e + 1) * n + 2 * r can be factored as 2 * (2 ^ e * n + r).
Since 2 ^ (e + 1) = 2 * 2 ^ e, we can factor out 2 by standard ring arithmetic to obtain 2 ^ (e + 1) * n + 2 * r = 2 * (2 ^ e * n + r). Rewriting the left-hand side using this identity transforms the goal into halving_partition_count (2 * (2 ^ e * n + r)) = halving_partition_count (2 ^ e * n + r).
rw [show 2 ^ (e + 1) * n + 2 * r = 2 * (2 ^ e * n + r) by ring]
halving_partition_count (2 * (2 ^ e * n + r)) = halving_partition_count (2 ^ e * n + r)
By halving_partition_count_two_mul, doubling an argument leaves its halving partition count unchanged. Applying this lemma with 2 ^ e * n + r completes the proof.
uses
halving_partition_count_two_mulexact halving_partition_count_two_mul _
halving_partition_count_two_mul- For any 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.
/-- Even-remainder elements of the 2-kernel reduce to elements at the preceding scale. -/theorem halving_partition_kernel_even_reduction (e r n : ℕ) : halving_partition_count (2 ^ (e + 1) * n + 2 * r) = halving_partition_count (2 ^ e * n + r) := by rw [show 2 ^ (e + 1) * n + 2 * r = 2 * (2 ^ e * n + r) by ring] exact halving_partition_count_two_mul _