mondrian_perfect_height_component_count
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.
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).
uses
Nat.lt_of_lt_of_le,List.ne_nil_of_length_pos,List.exists_mem_of_ne_nil,mondrian_partition_bounds,Nat.mul_posclassical 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
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).
uses
pow_poslet 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 _
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.
uses
mondrian_defect_zero_equal,decide_eq_false,Bool.false_eq_true,if_false,sub_zero,dvd_mul_of_dvd_lefthave 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 _
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.
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⟩
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.
uses
if_true,decide_eq_false,Bool.false_eq_true,if_falsehave 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
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.
uses
mondrian_list_sum_count_modhave hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) F pred htermThe 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.
uses
mondrian_partition_horizontal_moment,dvd_mul_of_dvd_lefthave 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 _
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.
uses
dvd_subhave 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
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.
uses
Nat.not_dvd_ordCompl,Nat.ne_of_gthave 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
- The decidability hypothesis for graph reachability is superseded by activating classical logic, enabling noncomputable reasoning about paths in the height graph.
- The proof embeds natural quantities into the integers ℤ to enable ring operations and telescoping cancellation before casting the final divisibility relation back to ℕ.
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.
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