designated_partition_six_tuple_twelve_mod_three
For every natural number n, 3 divides the number of designated partition 6-tuples of size 12n + 10, designated_partition_k_tuple 6 (12 * n + 10).
Statement
theorem designated_partition_six_tuple_twelve_mod_three (n : ℕ) :
3 ∣ designated_partition_k_tuple 6 (12 * n + 10)- Formalizes
- arXiv:2611.05623 Theorem 3.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- designated_partition_k_tupleThe number A_k(n) of ordered k-tuples of partitions with designated summands of total size n, defined as the n-th coefficient of F^k.
- monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
- designated_partition_gen_funThe generating function F in PowerSeries ℕ for partitions with designated summands, defined via Nat.Partition.genFun.
Read back from the Lean
For every natural number $n$, $3$ divides designated_partition_k_tuple 6 (12 * n + 10).
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 establishes that the number of designated partition 6-tuples of size 12n + 10 is divisible by 3 using generating functions modulo 3. Since the generating function is raised to the 6th power, it can be expressed as the cube of a power series, (F^2)^3. In characteristic 3, the Frobenius endomorphism implies that (f(X))^3 = f(X^3), so the cube of any power series has only powers divisible by 3; since 12n + 10 is congruent to 1 modulo 3, its coefficient is zero modulo 3, meaning the integer coefficient is divisible by 3.
In (ZMod 3)[X], every polynomial P satisfies P^3 = P(X^3)
By polynomial induction on P. For the sum p + q, (p + q)^3 = p^3 + q^3 by the Freshman's Dream in characteristic 3 (add_pow_char), and the expansion map is additive (map_add). For a monomial a * X^k, its cube is a^3 * X^(3k), which equals a * X^(3k) because a^3 = a in ZMod 3 by Fermat's little theorem (ZMod.pow_card); this matches the expansion Polynomial.expand (ZMod 3) 3 of the monomial.
uses
add_pow_char,map_add,Polynomial.expand_monomial,Polynomial.C_mul_X_pow_eq_monomial,mul_pow,Polynomial.C_pow,pow_mul,ZMod.pow_cardhave hpoly : ∀ P : Polynomial (ZMod 3), P ^ 3 = Polynomial.expand (ZMod 3) 3 P := by intro P induction P using Polynomial.induction_on' with | add p q hp hq => rw [add_pow_char, hp, hq, map_add] | monomial k a => rw [Polynomial.expand_monomial] rw [show Polynomial.monomial k a = Polynomial.C a * Polynomial.X ^ k from (Polynomial.C_mul_X_pow_eq_monomial).symm] rw [mul_pow, ← Polynomial.C_pow, ← pow_mul, ZMod.pow_card, Polynomial.C_mul_X_pow_eq_monomial]
For any power series f over ZMod 3 and any index m not divisible by 3, the m-th coefficient of f^3 is 0
Because m < m + 1, the m-th coefficient of f^3 depends only on the polynomial truncation of f modulo X^(m+1) (PowerSeries.coeff_coe_trunc_of_lt, PowerSeries.trunc_trunc_pow). Applying the polynomial identity P^3 = P(X^3) to this truncation, the m-th coefficient of the expansion P(X^3) is 0 because 3 does not divide m (Polynomial.coeff_expand, if_neg).
uses
PowerSeries.coeff_coe_trunc_of_lt,PowerSeries.trunc_trunc_pow,Polynomial.coe_pow,Polynomial.coeff_coe,Polynomial.coeff_expand,if_neghave hcoeff : ∀ (f : PowerSeries (ZMod 3)) (m : ℕ), ¬ 3 ∣ m → (f ^ 3).coeff m = 0 := by intro f m hm rw [(PowerSeries.coeff_coe_trunc_of_lt (n := m) (m := m+1) (f := f^3) (show m < m+1 by omega)).symm] rw [← PowerSeries.trunc_trunc_pow f (m+1) 3] rw [PowerSeries.coeff_coe_trunc_of_lt (n := m) (m := m+1) (f := ((PowerSeries.trunc (m+1) f : PowerSeries (ZMod 3)) ^ 3)) (show m < m+1 by omega)] rw [← Polynomial.coe_pow, Polynomial.coeff_coe, hpoly] rw [Polynomial.coeff_expand (by norm_num), if_neg hm]
Setting m = 12n + 10, 3 does not divide m automation
Linear arithmetic shows 12n + 10 = 3(4n + 3) + 1 is congruent to 1 modulo 3, hence not divisible by 3.
set m := 12 * n + 10 have hm : ¬ 3 ∣ m := by omega
The number of designated partition 6-tuples of size m, viewed in ZMod 3, equals the m-th coefficient of the generating function to the 6th power mapped into ZMod 3
By definition, designated_partition_k_tuple 6 m is the m-th coefficient of designated_partition_gen_fun^6. Mapping coefficients via Nat.castRingHom commutes with extracting the coefficient (PowerSeries.coeff_map).
uses
PowerSeries.coeff_maphave key : ((designated_partition_k_tuple 6 m : ℕ) : ZMod 3) = (PowerSeries.coeff m) (PowerSeries.map (Nat.castRingHom (ZMod 3)) (designated_partition_gen_fun ^ 6)) := by rw [PowerSeries.coeff_map] rfl
The m-th coefficient of the generating function to the 6th power in ZMod 3 is 0
We rewrite the 6th power as a cube: (gen_fun^2)^3. Since the ring homomorphism preserves powers (map_pow), this is the cube of an element in (PowerSeries (ZMod 3)). Because 3 does not divide m, its m-th coefficient vanishes by the power series cube lemma.
uses
map_powhave hN : ((designated_partition_k_tuple 6 m : ℕ) : ZMod 3) = 0 := by rw [key] rw [show designated_partition_gen_fun ^ 6 = (designated_partition_gen_fun ^ 2) ^ 3 by ring] rw [map_pow] rw [hcoeff _ m hm]
3 divides designated_partition_k_tuple 6 (12 * n + 10)
An integer maps to 0 in ZMod 3 if and only if 3 divides it (ZMod.natCast_eq_zero_iff). Since its image in ZMod 3 is 0, 3 divides the coefficient.
uses
ZMod.natCast_eq_zero_iffexact (ZMod.natCast_eq_zero_iff (designated_partition_k_tuple 6 m) 3).1 hN
add_pow_char- in a commutative semiring of prime characteristic p, (x + y)^p = x^p + y^p
map_add- an additive map preserves addition: f(x + y) = f(x) + f(y)
Polynomial.expand_monomial- expanding a monomial by p multiplies its exponent by p: expand p (monomial q r) = monomial (q * p) r
Polynomial.C_mul_X_pow_eq_monomial- a monomial a * X^n equals monomial n a
mul_pow- in a commutative monoid, (a * b)^n = a^n * b^n
Polynomial.C_pow- the constant polynomial C(a^n) equals (C a)^n
pow_mul- a^(m * n) = (a^m)^n
ZMod.pow_card- in ZMod p for prime p, x^p = x (Fermat's little theorem)
PowerSeries.coeff_coe_trunc_of_lt- if n < m, the n-th coefficient of the degree-m truncation of a power series equals the n-th coefficient of the power series
PowerSeries.trunc_trunc_pow- the degree-n truncation of the a-th power of a power series equals the degree-n truncation of the a-th power of its truncation
Polynomial.coe_pow- the coercion of a polynomial power to a power series equals the power of the coerced polynomial
Polynomial.coeff_coe- the n-th power series coefficient of a coerced polynomial equals its polynomial coefficient
Polynomial.coeff_expand- the n-th coefficient of expand p f is f.coeff (n / p) if p divides n, and 0 otherwise
if_neg- if a condition c is false, then if c then t else e evaluates to e
PowerSeries.coeff_map- the n-th coefficient of the entrywise map of a power series by f is f applied to the n-th coefficient
map_pow- a monoid homomorphism preserves powers: f(a^n) = (f a)^n
ZMod.natCast_eq_zero_iff- an integer a maps to 0 in ZMod b if and only if b divides a
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 lemma designated_partition_six_tuple_twelve_mod_three_aux (n : ℕ) : 3 ∣ designated_partition_k_tuple 6 (12 * n + 10) := by have hpoly : ∀ P : Polynomial (ZMod 3), P ^ 3 = Polynomial.expand (ZMod 3) 3 P := by intro P induction P using Polynomial.induction_on' with | add p q hp hq => rw [add_pow_char, hp, hq, map_add] | monomial k a => rw [Polynomial.expand_monomial] rw [show Polynomial.monomial k a = Polynomial.C a * Polynomial.X ^ k from (Polynomial.C_mul_X_pow_eq_monomial).symm] rw [mul_pow, ← Polynomial.C_pow, ← pow_mul, ZMod.pow_card, Polynomial.C_mul_X_pow_eq_monomial] have hcoeff : ∀ (f : PowerSeries (ZMod 3)) (m : ℕ), ¬ 3 ∣ m → (f ^ 3).coeff m = 0 := by intro f m hm rw [(PowerSeries.coeff_coe_trunc_of_lt (n := m) (m := m+1) (f := f^3) (show m < m+1 by omega)).symm] rw [← PowerSeries.trunc_trunc_pow f (m+1) 3] rw [PowerSeries.coeff_coe_trunc_of_lt (n := m) (m := m+1) (f := ((PowerSeries.trunc (m+1) f : PowerSeries (ZMod 3)) ^ 3)) (show m < m+1 by omega)] rw [← Polynomial.coe_pow, Polynomial.coeff_coe, hpoly] rw [Polynomial.coeff_expand (by norm_num), if_neg hm] set m := 12 * n + 10 have hm : ¬ 3 ∣ m := by omega have key : ((designated_partition_k_tuple 6 m : ℕ) : ZMod 3) = (PowerSeries.coeff m) (PowerSeries.map (Nat.castRingHom (ZMod 3)) (designated_partition_gen_fun ^ 6)) := by rw [PowerSeries.coeff_map] rfl have hN : ((designated_partition_k_tuple 6 m : ℕ) : ZMod 3) = 0 := by rw [key] rw [show designated_partition_gen_fun ^ 6 = (designated_partition_gen_fun ^ 2) ^ 3 by ring] rw [map_pow] rw [hcoeff _ m hm] exact (ZMod.natCast_eq_zero_iff (designated_partition_k_tuple 6 m) 3).1 hN/-- For all natural numbers n, 3 divides the number of designated partition 6-tuples of size 12n + 10. -/theorem designated_partition_six_tuple_twelve_mod_three (n : ℕ) : 3 ∣ designated_partition_k_tuple 6 (12 * n + 10) := designated_partition_six_tuple_twelve_mod_three_aux n