AFTD Auto-Formalizing Theoretical Domains

mondrian_cells_union_sum

theoremverified

Summing any integer-valued cell weight over a union of pairwise disjoint rectangle cell sets equals the sum of its sums over the rectangles.

Statement

theorem mondrian_cells_union_sum (P : List (ℕ × ℕ × ℕ × ℕ))
    (h : P.Pairwise (fun r s =>
      Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s)))
    (f : ℕ × ℕ → ℤ) :
    ∑ c ∈ P.toFinset.biUnion mondrian_rect_cells, f c =
      (P.map (fun r => ∑ c ∈ mondrian_rect_cells r, f c)).sum
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
Classical.choiceQuot.soundpropext
Built on 1
  • mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
Used by 1

The proof, explained

The theorem is proved by induction on the list of rectangles P. The base case of an empty list holds because both the union and list sums are zero. In the inductive step for `r :: P`, the pairwise disjointness hypothesis ensures that the cell set of `r` is disjoint from the union of cell sets of `P`, allowing the sum over the union to split into the sum over `r` plus the sum over `P`. The proof is completed by applying the induction hypothesis to the tail sum and unfolding the list summation.

  1. The sum equality holds when the list of rectangles is empty. automation

    We induct on the list P. When P is empty, the union of cells is empty and the mapped list of sums is empty, so both sides evaluate to 0 by simplification.

    lines 9–10

      induction P with
      | nil => simp
  2. In the inductive step for r :: P, the head rectangle r is disjoint from every rectangle in P, and P is pairwise disjoint.

    Applying `List.pairwise_cons.mp` to the assumption that `r :: P` is pairwise disjoint separates it into two hypotheses: `r` has cell sets disjoint from every rectangle in `P` (hr), and `P` itself is pairwise disjoint (hP).

    lines 11–12

    uses List.pairwise_cons.mp

      | cons r P ih =>
        obtain ⟨hr, hP⟩ := List.pairwise_cons.mp h
  3. The cells of rectangle r are disjoint from the union of cells of all rectangles in P.

    By `Finset.disjoint_biUnion_right`, a set is disjoint from a union over a finite set if and only if it is disjoint from each constituent set. Rewriting the membership condition with `List.mem_toFinset` makes this match the hypothesis that `r` is disjoint from every rectangle in `P`.

    lines 13–16

    uses Finset.disjoint_biUnion_right, List.mem_toFinset

        have hd : Disjoint (mondrian_rect_cells r)
            (P.toFinset.biUnion mondrian_rect_cells) := by
          rw [Finset.disjoint_biUnion_right]
          simpa only [List.mem_toFinset] using hr
  4. The sum over the union of cells of r :: P equals the sum of the rectangle sums over r :: P.

    The cell set of `r :: P` is rewritten as the union of the cells of `r` and the cell union of `P` using `List.toFinset_cons` and `Finset.biUnion_insert`. Since these two sets are disjoint, `Finset.sum_union` splits the summation into the sum over `r`'s cells plus the sum over `P`'s cells. Applying the induction hypothesis (`ih hP`) and expanding the list map and list sum with `List.map_cons` and `List.sum_cons` equates both sides.

    lines 17–18

    uses List.toFinset_cons, Finset.biUnion_insert, Finset.sum_union, List.map_cons, List.sum_cons

        rw [List.toFinset_cons, Finset.biUnion_insert, Finset.sum_union hd,
          ih hP, List.map_cons, List.sum_cons]
List.pairwise_cons.mp
If a list `a :: l` is pairwise related under a relation R, then `a` is related to every element in `l` and `l` is itself pairwise related under R.
Finset.disjoint_biUnion_right
A finite set s is disjoint from a indexed union of finite sets over t if and only if s is disjoint from each member set.
List.mem_toFinset
An element belongs to the finite set of a list if and only if it belongs to the list.
List.toFinset_cons
The finite set associated with `a :: l` is obtained by inserting `a` into the finite set of `l`.
Finset.biUnion_insert
The union of a family of finite sets over `{a} ∪ s` equals `t a ∪ ⋃_{x ∈ s} t x`.
Finset.sum_union
The sum of a function over the union of two disjoint finite sets is the sum over the first set plus the sum over the second.
List.map_cons
Mapping a function over `a :: l` yields `f a` followed by the map over `l`.
List.sum_cons
The sum of a list `a :: l` is `a` plus the sum of `l`.

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_cells_union_sum (P : List (ℕ × ℕ × ℕ × ℕ))    (h : P.Pairwise (fun r s =>      Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s)))    (f : ℕ × ℕ → ℤ) :    ∑ c ∈ P.toFinset.biUnion mondrian_rect_cells, f c =      (P.map (fun r => ∑ c ∈ mondrian_rect_cells r, f c)).sum := by  induction P with  | nil => simp  | cons r P ih =>    obtain ⟨hr, hP⟩ := List.pairwise_cons.mp h    have hd : Disjoint (mondrian_rect_cells r)        (P.toFinset.biUnion mondrian_rect_cells) := by      rw [Finset.disjoint_biUnion_right]      simpa only [List.mem_toFinset] using hr    rw [List.toFinset_cons, Finset.biUnion_insert, Finset.sum_union hd,      ih hP, List.map_cons, List.sum_cons]
See it in the graphDiscuss this resultChallenge it