AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_height_component_count

theoremverified

For a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of width-indivisible tiles divisible by p. The decidability parameter merely supplies a classical component-membership test.

Statement

theorem mondrian_perfect_height_component_count (n p a : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ))
    [DecidablePred ((mondrian_height_graph p P).Reachable a)]
    (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P)
    (hz : mondrian_defect P = 0) :
    p ∣ P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r ∧
      (mondrian_height_graph p P).Reachable a r.2.2.1))
Source
Helper for OP-280 and the width-indivisible height graph; componentwise refinement of the prime-free side-count congruence.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 15
  • mondrian_height_graphThe undirected graph on integer row levels whose edges are the bottom and top levels of tiles with width indivisible by d; loops are…
  • mondrian_height_graph_adj_of_memEvery positive-height member of the rectangle list whose width is indivisible by d gives a height-graph edge between its bottom and top…
  • mondrian_partition_horizontal_momentFor every integer-valued function f on row levels, the sum over an admissible n-square partition of width times the increment of f across…
  • mondrian_rect_floor_contributionWhen positive q divides a rectangle height, its width times the integer difference of quotient y coordinates is its area divided by q.
  • mondrian_list_sum_count_modIf each integer list contribution is congruent modulo p to u when its predicate holds and to zero otherwise, their sum is congruent to u…
  • mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
  • mondrian_partition_boundsEvery rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • 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…
  • mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
  • Arena.Reachable.transReachability is transitive.

The proof, explained

The theorem is proved by a discrete horizontal moment argument (a discrete Stokes' formula). Because the partition has defect zero, all tiles share the same area A = q * u, where q = p^(v_p(A)) and p ∤ u. We define a height potential f(y) = ⌊y/q⌋ on the component of a in the height graph and 0 outside it; the sum of the tile moments width(r) * (f(y_top) - f(y_bot)) telescopes to n * (f(n) - f(0)), which is divisible by p because p ∣ n. Term by term, width-divisible tiles contribute 0 mod p, while width-indivisible tiles in the component contribute exactly u; since p does not divide u, the number of such tiles in the component must be divisible by p.

  1. The partition P is non-empty and contains a rectangle r0 with strictly positive area.

    By definition of a partition, P contains at least 2 tiles, so its length is strictly positive (Nat.lt_of_lt_of_le). Thus P is non-empty (List.ne_nil_of_length_pos) and contains an element r0 (List.exists_mem_of_ne_nil). The partition bounds lemma (mondrian_partition_bounds) ensures that r0 has strictly positive width and height, and hence strictly positive area (Nat.mul_pos).

    lines 8–14

    uses Nat.lt_of_lt_of_le, List.ne_nil_of_length_pos, List.exists_mem_of_ne_nil, mondrian_partition_bounds, Nat.mul_pos

      classical
      have hlen : 0 < P.length := Nat.lt_of_lt_of_le (by decide) hP.1
      have hne : P ≠ [] := List.ne_nil_of_length_pos hlen
      obtain ⟨r0, hr0⟩ := List.exists_mem_of_ne_nil P hne
      have hApos : 0 < mondrian_rect_area r0 := by
        obtain ⟨-, -, hw, hh, -⟩ := mondrian_partition_bounds n P hP r0 hr0
        exact Nat.mul_pos hw hh
  2. Define the p-power part q and p-free part u of the tile area, the height graph H, the height weight function f, the component predicate pred, and the horizontal moment term F.

    Let q = p^(v_p(area(r0))) and u = area(r0) / q be the p-power and p-free components of the area of r0. Let H be the height graph with edges defined by width-indivisible tiles. Define f(y) on heights to be ⌊y / q⌋ if y is reachable from a in H and 0 otherwise. Define pred(r) to test whether p ∤ width(r) and the bottom height r.2.2.1 is reachable from a in H. Define F(r) = width(r) * (f(r.2.2.2) - f(r.2.2.1)). Since p is prime, q > 0 (pow_pos).

    lines 15–23

    uses pow_pos

      let q := p ^ (mondrian_rect_area r0).factorization p
      let u := mondrian_rect_area r0 / q
      let H := mondrian_height_graph p P
      let f : ℕ → ℤ := fun y => if H.Reachable a y then ((y / q : ℕ) : ℤ) else 0
      let pred : (ℕ × ℕ × ℕ × ℕ) → Bool := fun r =>
        decide (¬ p ∣ mondrian_rect_width r ∧ H.Reachable a r.2.2.1)
      let F : (ℕ × ℕ × ℕ × ℕ) → ℤ := fun r =>
        (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)
      have hq : 0 < q := pow_pos hp.pos _
  3. For any tile r ∈ P whose width is divisible by p, p divides F(r) - (if pred(r) then u else 0).

    Because the partition has defect zero, all tiles have area equal to area(r0) (mondrian_defect_zero_equal). If p divides width(r), then p ∤ width(r) is false, making pred(r) false (decide_eq_false). Thus the conditional expression evaluates to 0 (Bool.false_eq_true, if_false, sub_zero). Since p divides width(r), it divides F(r) = width(r) * (f(y_top) - f(y_bot)) (dvd_mul_of_dvd_left), so p divides F(r) - 0.

    lines 24–36

    uses mondrian_defect_zero_equal, decide_eq_false, Bool.false_eq_true, if_false, sub_zero, dvd_mul_of_dvd_left

      have hterm : ∀ r ∈ P, (p : ℤ) ∣ F r - if pred r then (u : ℤ) else 0 := by
        intro r hr
        have hAr : mondrian_rect_area r = mondrian_rect_area r0 :=
          mondrian_defect_zero_equal P hz r r0 hr hr0
        by_cases hw : p ∣ mondrian_rect_width r
        · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw
          have hpred : pred r = false := by
            simp only [pred]
            apply decide_eq_false
            intro h
            exact h.1 hw
          simp only [F, hpred, Bool.false_eq_true, if_false, sub_zero]
          exact dvd_mul_of_dvd_left hwZ _
  4. For any tile r ∈ P with p ∤ width(r), q divides height(r), the floor contribution evaluates to u, and reachability from a is equivalent for its bottom and top heights.

    Since p does not divide width(r), q (a power of p) is coprime to width(r). As q divides area(r0) (Nat.ordProj_dvd), which equals area(r) = width(r) * height(r), coprimality implies q divides height(r). The floor contribution formula (mondrian_rect_floor_contribution) then gives width(r) * (⌊y_top/q⌋ - ⌊y_bot/q⌋) = area(r)/q = u. Furthermore, because p ∤ width(r), r forms an edge in H between its bottom and top heights (mondrian_height_graph_adj_of_mem), so y_top is reachable from a if and only if y_bot is.

    lines 37–50

    uses Nat.ordProj_dvd, mondrian_rect_floor_contribution, Nat.le_of_lt, mondrian_height_graph_adj_of_mem

        · have hcop : q.Coprime (mondrian_rect_width r) :=
            (hp.coprime_iff_not_dvd.mpr hw).pow_left _
          have hqh : q ∣ mondrian_rect_height r := by
            apply hcop.dvd_mul_left.mp
            change q ∣ mondrian_rect_area r
            rw [hAr]
            exact Nat.ordProj_dvd _ p
          have he := mondrian_rect_floor_contribution r
            (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh
          rw [hAr] at he
          have hadj : H.Adj r.2.2.1 r.2.2.2 :=
            mondrian_height_graph_adj_of_mem p P r hr hw (hP.2.1 r hr).2
          have hreach_iff : H.Reachable a r.2.2.2 ↔ H.Reachable a r.2.2.1 :=
            ⟨fun h => h.trans hadj.reachable.symm, fun h => h.trans hadj.reachable⟩
  5. For any tile r ∈ P with p ∤ width(r), F(r) equals u (if its bottom height is reachable) or 0 (if not), completing the proof that p divides F(r) - (if pred(r) then u else 0) for all r ∈ P.

    Case split on whether the bottom height is reachable from a in H. If reachable, the top height is also reachable, pred(r) is true, and F(r) = width(r) * (⌊y_top/q⌋ - ⌊y_bot/q⌋) = u (if_true). If not reachable, neither height is reachable, pred(r) is false (decide_eq_false), and F(r) = width(r) * (0 - 0) = 0. In both cases F(r) equals (if pred(r) then u else 0), so the difference is 0 and hence divisible by p.

    lines 51–65

    uses if_true, decide_eq_false, Bool.false_eq_true, if_false

          have hFeq : F r = if pred r then (u : ℤ) else 0 := by
            by_cases hrb : H.Reachable a r.2.2.1
            · have hrt : H.Reachable a r.2.2.2 := hreach_iff.mpr hrb
              have hpred : pred r = true := by simp [pred, hw, hrb]
              simp only [F, f, hrb, hrt, hpred, if_true]
              rw [he]
            · have hrt : ¬ H.Reachable a r.2.2.2 := fun h => hrb (hreach_iff.mp h)
              have hpred : pred r = false := by
                simp only [pred]
                apply decide_eq_false
                intro h; exact hrb h.2
              simp only [F, f, hrb, hrt, hpred, Bool.false_eq_true, if_false]
              ring
          rw [hFeq]
          simp
  6. The sum of F(r) over all tiles in P is congruent modulo p to the count of satisfying tiles times u: p divides ∑ F(r) - (countP pred) * u.

    Summing the local divisibility relations over all tiles in P using the list summation lemma mondrian_list_sum_count_mod establishes that the total sum of F minus (countP pred) * u is divisible by p.

    line 66

    uses mondrian_list_sum_count_mod

      have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) F pred hterm
  7. The total horizontal moment ∑ F(r) is divisible by p.

    By the horizontal moment identity for partitions (mondrian_partition_horizontal_moment), the sum ∑ F(r) telescopes to n * (f(n) - f(0)). Since p divides n by hypothesis, p divides this product (dvd_mul_of_dvd_left) and hence divides the total sum.

    lines 67–71

    uses mondrian_partition_horizontal_moment, dvd_mul_of_dvd_left

      have hmoment := mondrian_partition_horizontal_moment n P hP f
      have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn
      have hsumdiv : (p : ℤ) ∣ (P.map F).sum := by
        rw [show (P.map F).sum = (n : ℤ) * (f n - f 0) from hmoment]
        exact dvd_mul_of_dvd_left hnZ _
  8. In ℤ, p divides (countP pred) * u.

    Because p divides both ∑ F(r) and ∑ F(r) - (countP pred) * u, it divides their difference (dvd_sub). Ring simplification shows this difference is exactly (countP pred) * u.

    lines 72–76

    uses dvd_sub

      have hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by
        have hh := dvd_sub hsumdiv hsum
        have heq : (P.map F).sum - ((P.map F).sum - (P.countP pred : ℤ) * (u : ℤ)) =
            (P.countP pred : ℤ) * (u : ℤ) := by ring
        rwa [heq] at hh
  9. The prime p divides the count of tiles in P satisfying pred.

    Casting the divisibility from ℤ to ℕ gives p ∣ (countP pred) * u. By Euclid's lemma for the prime p, p divides countP pred or p divides u. But u = area(r0) / p^(v_p(area(r0))) is the p-free cofactor of the non-zero area of r0, so p cannot divide u (Nat.not_dvd_ordCompl, using Nat.ne_of_gt). Thus p must divide countP pred.

    lines 77–80

    uses Nat.not_dvd_ordCompl, Nat.ne_of_gt

      have hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod
      rcases hp.dvd_mul.mp hprodN with hc | hu
      · exact hc
      · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim
Nat.lt_of_lt_of_le
if a < b and b ≤ c, then a < c
List.ne_nil_of_length_pos
a list with strictly positive length is non-empty
List.exists_mem_of_ne_nil
every non-empty list contains at least one element
mondrian_partition_bounds
for any tile in an n-square partition, its coordinates are bounded by n and its width and height are strictly positive
Nat.mul_pos
the product of two strictly positive natural numbers is strictly positive
pow_pos
a strictly positive base raised to any natural power is strictly positive
mondrian_defect_zero_equal
in a partition with defect zero, all rectangles have identical area
decide_eq_false
if a proposition P is false, then decide P = false
Bool.false_eq_true
the proposition (false = true) is False
if_false
an if-then-else whose condition is False reduces to the else branch
sub_zero
subtracting zero from an element of an additive group leaves it unchanged (a - 0 = a)
dvd_mul_of_dvd_left
if a divides b, then a divides b * c
Nat.ordProj_dvd
the p-part p^(factorization p n) divides n
mondrian_rect_floor_contribution
if q divides the height of rectangle r, then width(r) * (⌊y_top/q⌋ - ⌊y_bot/q⌋) equals area(r)/q
Nat.le_of_lt
if a < b for natural numbers, then a ≤ b
mondrian_height_graph_adj_of_mem
a tile whose width is not divisible by d connects its bottom and top heights by an edge in the height graph
if_true
an if-then-else whose condition is True reduces to the then branch
mondrian_list_sum_count_mod
if each term f(r) is congruent mod p to u when pred(r) holds and 0 otherwise, then the list sum of f is congruent mod p to (countP pred) * u
mondrian_partition_horizontal_moment
the sum over all tiles in an n-partition of width(r) * (f(y_top) - f(y_bot)) telescopes to n * (f(n) - f(0))
dvd_sub
if a divides b and a divides c, then a divides b - c
Nat.not_dvd_ordCompl
a prime p does not divide the p-free part n / p^(factorization p n) of any non-zero n
Nat.ne_of_gt
if b < a, then a ≠ b

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

theorem mondrian_perfect_height_component_count (n p a : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ))    [DecidablePred ((mondrian_height_graph p P).Reachable a)]    (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P)    (hz : mondrian_defect P = 0) :    p ∣ P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r ∧      (mondrian_height_graph p P).Reachable a r.2.2.1)) := by  classical  have hlen : 0 < P.length := Nat.lt_of_lt_of_le (by decide) hP.1  have hne : P ≠ [] := List.ne_nil_of_length_pos hlen  obtain ⟨r0, hr0⟩ := List.exists_mem_of_ne_nil P hne  have hApos : 0 < mondrian_rect_area r0 := by    obtain ⟨-, -, hw, hh, -⟩ := mondrian_partition_bounds n P hP r0 hr0    exact Nat.mul_pos hw hh  let q := p ^ (mondrian_rect_area r0).factorization p  let u := mondrian_rect_area r0 / q  let H := mondrian_height_graph p P  let f : ℕ → ℤ := fun y => if H.Reachable a y then ((y / q : ℕ) : ℤ) else 0  let pred : (ℕ × ℕ × ℕ × ℕ) → Bool := fun r =>    decide (¬ p ∣ mondrian_rect_width r ∧ H.Reachable a r.2.2.1)  let F : (ℕ × ℕ × ℕ × ℕ) → ℤ := fun r =>    (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)  have hq : 0 < q := pow_pos hp.pos _  have hterm : ∀ r ∈ P, (p : ℤ) ∣ F r - if pred r then (u : ℤ) else 0 := by    intro r hr    have hAr : mondrian_rect_area r = mondrian_rect_area r0 :=      mondrian_defect_zero_equal P hz r r0 hr hr0    by_cases hw : p ∣ mondrian_rect_width r    · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw      have hpred : pred r = false := by        simp only [pred]        apply decide_eq_false        intro h        exact h.1 hw      simp only [F, hpred, Bool.false_eq_true, if_false, sub_zero]      exact dvd_mul_of_dvd_left hwZ _    · have hcop : q.Coprime (mondrian_rect_width r) :=        (hp.coprime_iff_not_dvd.mpr hw).pow_left _      have hqh : q ∣ mondrian_rect_height r := by        apply hcop.dvd_mul_left.mp        change q ∣ mondrian_rect_area r        rw [hAr]        exact Nat.ordProj_dvd _ p      have he := mondrian_rect_floor_contribution r        (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh      rw [hAr] at he      have hadj : H.Adj r.2.2.1 r.2.2.2 :=        mondrian_height_graph_adj_of_mem p P r hr hw (hP.2.1 r hr).2      have hreach_iff : H.Reachable a r.2.2.2 ↔ H.Reachable a r.2.2.1 :=        ⟨fun h => h.trans hadj.reachable.symm, fun h => h.trans hadj.reachable⟩      have hFeq : F r = if pred r then (u : ℤ) else 0 := by        by_cases hrb : H.Reachable a r.2.2.1        · have hrt : H.Reachable a r.2.2.2 := hreach_iff.mpr hrb          have hpred : pred r = true := by simp [pred, hw, hrb]          simp only [F, f, hrb, hrt, hpred, if_true]          rw [he]        · have hrt : ¬ H.Reachable a r.2.2.2 := fun h => hrb (hreach_iff.mp h)          have hpred : pred r = false := by            simp only [pred]            apply decide_eq_false            intro h; exact hrb h.2          simp only [F, f, hrb, hrt, hpred, Bool.false_eq_true, if_false]          ring      rw [hFeq]      simp  have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) F pred hterm  have hmoment := mondrian_partition_horizontal_moment n P hP f  have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn  have hsumdiv : (p : ℤ) ∣ (P.map F).sum := by    rw [show (P.map F).sum = (n : ℤ) * (f n - f 0) from hmoment]    exact dvd_mul_of_dvd_left hnZ _  have hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by    have hh := dvd_sub hsumdiv hsum    have heq : (P.map F).sum - ((P.map F).sum - (P.countP pred : ℤ) * (u : ℤ)) =        (P.countP pred : ℤ) * (u : ℤ) := by ring    rwa [heq] at hh  have hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod  rcases hp.dvd_mul.mp hprodN with hc | hu  · exact hc  · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim
See it in the graphDiscuss this resultChallenge it