AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_width_free_count_ne_two

theoremverified

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.

  1. 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).

    lines 5–10

    uses List.countP_eq_length_filter, List.length_eq_two.mp

      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
  2. 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.

    lines 11–22

    uses List.mem_filter

      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
  3. 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.

    lines 23–32

    uses List.nodup_iff_pairwise_ne

      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
  4. 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.

    lines 33–35

    uses mondrian_perfect_height_injective

      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)
  5. 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.

    lines 36–56

    uses mondrian_partition_bounds, Nat.le_of_dvd, lt_irrefl, dvd_rfl, mondrian_partition_isolated_height_residue

      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
  6. 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.

    lines 57–64

    uses lt_or_gt_of_ne

      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
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

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
See it in the graphDiscuss this resultChallenge it