AFTD Auto-Formalizing Theoretical Domains

designated_partition_six_tuple_twelve_mod_three

theoremverifiedformalization

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.

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

    lines 3–12

    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_card

      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]
  2. 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).

    lines 13–22

    uses PowerSeries.coeff_coe_trunc_of_lt, PowerSeries.trunc_trunc_pow, Polynomial.coe_pow, Polynomial.coeff_coe, Polynomial.coeff_expand, if_neg

      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]
  3. 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.

    lines 23–24

      set m := 12 * n + 10
      have hm : ¬ 3 ∣ m := by omega
  4. 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).

    lines 25–29

    uses PowerSeries.coeff_map

      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
  5. 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.

    lines 30–34

    uses map_pow

      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]
  6. 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.

    line 35

    uses ZMod.natCast_eq_zero_iff

      exact (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

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