mondrian_perfect_width_free_count_ne_two
In a perfect admissible square partition, for any divisor d of the square side, exactly two tiles cannot have widths indivisible by d.
Statement
theorem mondrian_perfect_width_free_count_ne_two (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hdn : d ∣ n) : P.countP (fun r => decide (¬ d ∣ mondrian_rect_width r)) ≠ 2
- Source
- Helper for the remaining three-prime cases of OP-280, arXiv:2610.19193, Section 1; follows from periodic row isolation.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_perfect_height_injectiveThe heights of the tiles in a perfect admissible square partition are pairwise distinct.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- 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_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_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).
The proof, explained
The theorem states that in a perfect square partition, exactly two tiles cannot have widths indivisible by a side divisor d. Assuming for contradiction that exactly two such tiles r and s exist, the perfectness condition forces them to have distinct heights. Taking the shorter tile u and the taller tile v, the height of v cannot divide that of u, while every other tile in the partition either has width divisible by d or equals v; the isolated height residue theorem then forces d to divide the width of u, which is a contradiction.
Assume for contradiction that exactly two tiles have width not divisible by d, and denote these two tiles by r and s.
We suppose the count of tiles whose widths are not divisible by d is 2. The count equals the length of the filtered sublist (by List.countP_eq_length_filter), so this sublist has length 2 and can therefore be unpacked into a two-element list [r, s] (using List.length_eq_two.mp).
uses
List.countP_eq_length_filter,List.length_eq_two.mpintro hc let cond := fun r => decide (¬ d ∣ mondrian_rect_width r) have hc_filt : (P.filter cond).length = 2 := by rw [← List.countP_eq_length_filter] exact hc obtain ⟨r, s, hfilt⟩ := List.length_eq_two.mp hc_filt
A tile in P has width not divisible by d if and only if it is r or s; in particular, r and s belong to P and their widths are not divisible by d.
Membership in the filtered list is equivalent to belonging to [r, s] (by List.mem_filter), which means a tile satisfies the condition if and only if it equals r or s. Evaluating this at r and s confirms that both belong to P and neither width is divisible by d.
uses
List.mem_filterhave hmem_iff : ∀ t, (t ∈ P ∧ cond t = true) ↔ t = r ∨ t = s := by intro t rw [← List.mem_filter, hfilt] simp have hr_in : r ∈ P := (hmem_iff r).mpr (Or.inl rfl) |>.1 have hs_in : s ∈ P := (hmem_iff s).mpr (Or.inr rfl) |>.1 have hr_ndvd : ¬ d ∣ mondrian_rect_width r := by have := (hmem_iff r).mpr (Or.inl rfl) |>.2 simpa [cond] using this have hs_ndvd : ¬ d ∣ mondrian_rect_width s := by have := (hmem_iff s).mpr (Or.inr rfl) |>.2 simpa [cond] using this
The list of tiles P has no duplicates, which implies r ≠ s.
By the definition of a partition, distinct tiles are pairwise non-congruent and disjoint. Since equal tiles would be congruent, no tile can equal another, meaning the list P has no duplicates (List.nodup_iff_pairwise_ne). Filtering preserves this property, so the list [r, s] has no duplicates, which implies r ≠ s.
uses
List.nodup_iff_pairwise_nehave hnodup : P.Nodup := by rw [List.nodup_iff_pairwise_ne] apply hP.2.2.1.imp intro a b hab he subst b exact hab.2 (Or.inl ⟨rfl, rfl⟩) have hfilt_nodup : [r, s].Nodup := by rw [← hfilt] exact hnodup.filter cond have hne : r ≠ s := by simpa using hfilt_nodup
The tiles r and s have distinct heights.
Because the partition is perfect (its defect is 0), tiles with the same height are identical (mondrian_perfect_height_injective). If r and s had the same height, they would be identical, contradicting r ≠ s.
uses
mondrian_perfect_height_injectivehave hne_h : mondrian_rect_height r ≠ mondrian_rect_height s := by intro heq exact hne (mondrian_perfect_height_injective n P hP hz r hr_in s hs_in heq)
If two tiles u and v are the only tiles whose widths are not divisible by d, and the height of u is strictly smaller than the height of v, then a contradiction is reached.
Because the height of u is positive (from mondrian_partition_bounds) and strictly less than that of v, the height of v cannot divide that of u (by Nat.le_of_dvd and lt_irrefl). Moreover, any other tile t ≠ u must have width divisible by d or equal v (in which case the height of v divides the height of t by dvd_rfl). Under these conditions, the isolated height residue lemma (mondrian_partition_isolated_height_residue) forces d to divide the width of u, directly contradicting that the width of u is not divisible by d.
uses
mondrian_partition_bounds,Nat.le_of_dvd,lt_irrefl,dvd_rfl,mondrian_partition_isolated_height_residuehave h_contra : ∀ u v, u ∈ P → v ∈ P → ¬ d ∣ mondrian_rect_width u → (∀ t, (t ∈ P ∧ cond t = true) → t = u ∨ t = v) → mondrian_rect_height u < mondrian_rect_height v → False := by intro u v hu hv hu_ndvd hall hlt have hpos_u := (mondrian_partition_bounds n P hP u hu).2.2.2.1 have hnot_dvd_v_u : ¬ mondrian_rect_height v ∣ mondrian_rect_height u := by intro hdvd have := Nat.le_of_dvd hpos_u hdvd exact lt_irrefl _ (hlt.trans_le this) have hothers : ∀ t ∈ P, t ≠ u → d ∣ mondrian_rect_width t ∨ mondrian_rect_height v ∣ mondrian_rect_height t := by intro t ht htu by_cases hdt : d ∣ mondrian_rect_width t · exact Or.inl hdt · have hcond : cond t = true := by simpa [cond] using hdt have ht_or := hall t ⟨ht, hcond⟩ rcases ht_or with rfl | rfl · exact (htu rfl).elim · exact Or.inr dvd_rfl have hdvd_u := mondrian_partition_isolated_height_residue n d (mondrian_rect_height v) P hP hdn u hu hnot_dvd_v_u hothers exact hu_ndvd hdvd_u
Either the height of r is less than that of s or vice versa, and both cases lead to contradiction.
Since the heights of r and s are unequal, trichotomy gives either height(r) < height(s) or height(s) < height(r) (via lt_or_gt_of_ne). Applying the contradiction lemma from the previous step to (r, s) in the first case, and symmetrically to (s, r) in the second case, yields False in both branches.
uses
lt_or_gt_of_nercases lt_or_gt_of_ne hne_h with hlt | hgt · exact h_contra r s hr_in hs_in hr_ndvd (fun t ht => (hmem_iff t).mp ht) hlt · have hall_symm : ∀ t, (t ∈ P ∧ cond t = true) → t = s ∨ t = r := by intro t ht rcases (hmem_iff t).mp ht with h | h · exact Or.inr h · exact Or.inl h exact h_contra s r hs_in hr_in hs_ndvd hall_symm hgt
List.countP_eq_length_filter- The number of elements in a list satisfying a boolean predicate equals the length of the sublist of elements that satisfy it.
List.length_eq_two.mp- A list has length 2 if and only if it consists of exactly two elements [a, b].
List.mem_filter- An element belongs to a filtered list if and only if it belongs to the original list and satisfies the filtering condition.
List.nodup_iff_pairwise_ne- A list contains no duplicate elements if and only if every pair of elements at distinct positions is unequal.
mondrian_perfect_height_injective- In a perfect square partition (defect 0), tiles with identical heights must be the same tile.
mondrian_partition_bounds- Every tile in a valid partition of an n × n square has strictly positive width and height bounded by n.
Nat.le_of_dvd- If a positive integer divides another, it is less than or equal to it.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
dvd_rfl- Any element divides itself.
mondrian_partition_isolated_height_residue- In a square partition where d divides the side length, if an isolated tile has height not divisible by m while every other tile either has width divisible by d or height divisible by m, then d must divide the width of the isolated tile.
lt_or_gt_of_ne- Two unequal elements in a linear order satisfy either a < b or b < a.
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_width_free_count_ne_two (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hdn : d ∣ n) : P.countP (fun r => decide (¬ d ∣ mondrian_rect_width r)) ≠ 2 := by intro hc let cond := fun r => decide (¬ d ∣ mondrian_rect_width r) have hc_filt : (P.filter cond).length = 2 := by rw [← List.countP_eq_length_filter] exact hc obtain ⟨r, s, hfilt⟩ := List.length_eq_two.mp hc_filt have hmem_iff : ∀ t, (t ∈ P ∧ cond t = true) ↔ t = r ∨ t = s := by intro t rw [← List.mem_filter, hfilt] simp have hr_in : r ∈ P := (hmem_iff r).mpr (Or.inl rfl) |>.1 have hs_in : s ∈ P := (hmem_iff s).mpr (Or.inr rfl) |>.1 have hr_ndvd : ¬ d ∣ mondrian_rect_width r := by have := (hmem_iff r).mpr (Or.inl rfl) |>.2 simpa [cond] using this have hs_ndvd : ¬ d ∣ mondrian_rect_width s := by have := (hmem_iff s).mpr (Or.inr rfl) |>.2 simpa [cond] using this have hnodup : P.Nodup := by rw [List.nodup_iff_pairwise_ne] apply hP.2.2.1.imp intro a b hab he subst b exact hab.2 (Or.inl ⟨rfl, rfl⟩) have hfilt_nodup : [r, s].Nodup := by rw [← hfilt] exact hnodup.filter cond have hne : r ≠ s := by simpa using hfilt_nodup have hne_h : mondrian_rect_height r ≠ mondrian_rect_height s := by intro heq exact hne (mondrian_perfect_height_injective n P hP hz r hr_in s hs_in heq) have h_contra : ∀ u v, u ∈ P → v ∈ P → ¬ d ∣ mondrian_rect_width u → (∀ t, (t ∈ P ∧ cond t = true) → t = u ∨ t = v) → mondrian_rect_height u < mondrian_rect_height v → False := by intro u v hu hv hu_ndvd hall hlt have hpos_u := (mondrian_partition_bounds n P hP u hu).2.2.2.1 have hnot_dvd_v_u : ¬ mondrian_rect_height v ∣ mondrian_rect_height u := by intro hdvd have := Nat.le_of_dvd hpos_u hdvd exact lt_irrefl _ (hlt.trans_le this) have hothers : ∀ t ∈ P, t ≠ u → d ∣ mondrian_rect_width t ∨ mondrian_rect_height v ∣ mondrian_rect_height t := by intro t ht htu by_cases hdt : d ∣ mondrian_rect_width t · exact Or.inl hdt · have hcond : cond t = true := by simpa [cond] using hdt have ht_or := hall t ⟨ht, hcond⟩ rcases ht_or with rfl | rfl · exact (htu rfl).elim · exact Or.inr dvd_rfl have hdvd_u := mondrian_partition_isolated_height_residue n d (mondrian_rect_height v) P hP hdn u hu hnot_dvd_v_u hothers exact hu_ndvd hdvd_u rcases lt_or_gt_of_ne hne_h with hlt | hgt · exact h_contra r s hr_in hs_in hr_ndvd (fun t ht => (hmem_iff t).mp ht) hlt · have hall_symm : ∀ t, (t ∈ P ∧ cond t = true) → t = s ∨ t = r := by intro t ht rcases (hmem_iff t).mp ht with h | h · exact Or.inr h · exact Or.inl h exact h_contra s r hs_in hr_in hs_ndvd hall_symm hgt