AFTD Auto-Formalizing Theoretical Domains

halving_partition_kernel_even_reduction

theoremverified

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.

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

    line 4

      rw [show 2 ^ (e + 1) * n + 2 * r = 2 * (2 ^ e * n + r) by ring]
  2. 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.

    line 5

    uses halving_partition_count_two_mul

      exact 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

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