mondrian_list_sum_count_mod
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
- mondrian_partition_normalized_prime_free_width_modIn an admissible n-square partition with every width divisible by positive d and with constant normalized area C, the number of normalized…
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- mondrian_partition_isolated_row_functionLet d divide the square side. If an integer row-level function has increment one on a selected tile and has zero increment on every other…
- mondrian_partition_isolated_height_residueLet d divide the square side. If every tile except r either has width divisible by d or height divisible by m, and r has height…
- mondrian_common_width_divides_sideEvery common divisor of the tile widths in an admissible n-square partition divides n.
- mondrian_partition_prime_free_width_countFor an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of…
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.
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.
induction L with | nil => simp
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).
| cons r L ih => have hr := h r (by simp) have ht := ih (fun s hs => h s (by simp [hs]))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.
uses
List.map_cons,List.sum_cons,List.countP_conshave 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
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.
uses
dvd_addrw [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
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.
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