AFTD Auto-Formalizing Theoretical Domains

mondrian_list_sum_count_mod

theoremverified

If each integer list contribution is congruent modulo p to u when its predicate holds and to zero otherwise, their sum is congruent to u times the number satisfying the predicate.

Statement

theorem mondrian_list_sum_count_mod (L : List (ℕ × ℕ × ℕ × ℕ))
    (p u : ℤ) (f : (ℕ × ℕ × ℕ × ℕ) → ℤ)
    (pred : (ℕ × ℕ × ℕ × ℕ) → Bool)
    (h : ∀ r ∈ L, p ∣ f r - if pred r then u else 0) :
    p ∣ (L.map f).sum - (L.countP pred : ℤ) * u
Source
Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
Verified
26 Oct 2026
Axioms
propext
Used by 6

The proof, explained

The theorem is proved by induction on the list L. In the base case where L is empty, the sum and count are both zero, so the difference is zero and trivially divisible by p. In the inductive step, the expression for r :: L decomposes algebraically into the contribution of the head element r plus the corresponding expression for the tail L. Since p divides the head contribution by assumption and divides the tail expression by the induction hypothesis, it divides their sum.

  1. The divisibility holds in the base case where L is the empty list.

    We proceed by induction on L. When L is empty, the mapped list is empty, its sum is 0, and the count of elements satisfying pred is 0. The expression reduces to 0 - 0 * u = 0, which is divisible by p; simp closes this base case.

    lines 8–9

      induction L with
      | nil => simp
  2. In the inductive step for r :: L, p divides the head difference, and by the induction hypothesis, p divides the tail difference.

    For the list r :: L, we instantiate the hypothesis h at the head element r ∈ r :: L to obtain divisibility for the head (hr). Applying the induction hypothesis ih to the tail L requires that every element s ∈ L satisfies the divisibility condition; this holds because any s ∈ L is in r :: L, yielding divisibility for the tail (ht).

    lines 10–12

      | cons r L ih =>
        have hr := h r (by simp)
        have ht := ih (fun s hs => h s (by simp [hs]))
  3. The difference for r :: L decomposes into the head difference plus the tail difference.

    We establish the algebraic identity splitting the expression into head and tail components. Rewriting with List.map_cons, List.sum_cons, and List.countP_cons expresses the sum and count on r :: L in terms of r and L. A case split on whether pred r is true or false, followed by ring arithmetic, confirms the identity in both cases.

    lines 13–17

    uses List.map_cons, List.sum_cons, List.countP_cons

        have heq : ((r :: L).map f).sum - ((r :: L).countP pred : ℤ) * u =
            (f r - if pred r then u else 0) +
              ((L.map f).sum - (L.countP pred : ℤ) * u) := by
          simp only [List.map_cons, List.sum_cons, List.countP_cons]
          cases pred r <;> simp <;> ring
  4. p divides the difference for r :: L, completing the induction.

    Rewriting the goal with the algebraic identity heq expresses the quantity as the sum of the head difference and the tail difference. Since p divides each of these terms by hr and ht, dvd_add establishes that p divides their sum.

    lines 18–19

    uses dvd_add

        rw [heq]
        exact dvd_add hr ht
List.map_cons
Mapping a function over a non-empty list applies the function to the head and prepends it to the mapped tail.
List.sum_cons
The sum of a non-empty list is the head element plus the sum of the tail.
List.countP_cons
Counting elements satisfying a predicate in a non-empty list equals the count in the tail plus 1 if the head satisfies the predicate and 0 otherwise.
dvd_add
If a divides b and a divides c, then a divides b + c.

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

open scoped BigOperatorstheorem mondrian_list_sum_count_mod (L : List (ℕ × ℕ × ℕ × ℕ))    (p u : ℤ) (f : (ℕ × ℕ × ℕ × ℕ) → ℤ)    (pred : (ℕ × ℕ × ℕ × ℕ) → Bool)    (h : ∀ r ∈ L, p ∣ f r - if pred r then u else 0) :    p ∣ (L.map f).sum - (L.countP pred : ℤ) * u := by  induction L with  | nil => simp  | cons r L ih =>    have hr := h r (by simp)    have ht := ih (fun s hs => h s (by simp [hs]))    have heq : ((r :: L).map f).sum - ((r :: L).countP pred : ℤ) * u =        (f r - if pred r then u else 0) +          ((L.map f).sum - (L.countP pred : ℤ) * u) := by      simp only [List.map_cons, List.sum_cons, List.countP_cons]      cases pred r <;> simp <;> ring    rw [heq]    exact dvd_add hr ht
See it in the graphDiscuss this resultChallenge it