AFTD Auto-Formalizing Theoretical Domains

mondrian_liminf_min_defect_seven_le

theoremverifiedformalization

liminf_{n→∞} M₇(n) ≤ 280: infinitely many squares have a seven-rectangle Mondrian partition with defect at most 280.

Statement

theorem mondrian_liminf_min_defect_seven_le :
    Filter.liminf (fun n => mondrian_min_defect_seven n) Filter.atTop ≤ 280
Formalizes
arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), Theorem 1.1 ('Consequently liminf M(n) ≤ 280'; the partitions used have seven rectangles, so the bound holds for M₇).
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • mondrian_min_defect_sevenM₇(n): the minimum defect over admissible Mondrian partitions of the n×n square into exactly seven rectangles (⊤ when there is none).
  • mondrian_pell_family_defect_280For n₀ = 315, n₁ = 106785, n_{j+2} = 340n_{j+1} − n_j: for every j the n_j×n_j square has a Mondrian partition into seven pairwise…
  • 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_pell_sideThe side lengths n₀ = 315, n₁ = 106785, n_{j+2} = 340 n_{j+1} − n_j.

The proof, explained

To show that liminf_{n→∞} M₇(n) ≤ 280, it suffices to find an unbounded sequence of square side lengths admitting a 7-rectangle Mondrian partition of defect at most 280. We consider the sequence s_j = mondrian_pell_side j generated by a Pell-type recurrence, which is shown by induction to satisfy s_j ≥ j and thus grow to infinity. For each j, the lemma mondrian_pell_family_defect_280 provides an explicit 7-rectangle partition of the s_j × s_j square with defect 280, showing M₇(s_j) ≤ 280 holds frequently and yielding the liminf bound.

  1. The sequence of square side lengths satisfies j ≤ mondrian_pell_side j for all j, and in particular grows without bound.

    We prove a stronger invariant by induction on j: j + 315 ≤ mondrian_pell_side j and mondrian_pell_side j + 1 ≤ mondrian_pell_side (j + 1). For j = 0, the side lengths are mondrian_pell_side 0 = 315 and mondrian_pell_side 1 = 106785, which satisfy both inequalities. In the inductive step from n to n + 1, the first inequality (n + 1) + 315 ≤ mondrian_pell_side (n + 1) follows from the induction hypotheses n + 315 ≤ mondrian_pell_side n and mondrian_pell_side n < mondrian_pell_side (n + 1). The second inequality uses the recurrence mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n; since mondrian_pell_side n < mondrian_pell_side (n + 1), linear arithmetic confirms it exceeds mondrian_pell_side (n + 1) + 1. Finally, j ≤ j + 315 ≤ mondrian_pell_side j yields j ≤ mondrian_pell_side j.

    lines 3–13

      have hgrow : ∀ j, j ≤ mondrian_pell_side j := by
        have key : ∀ j, j + 315 ≤ mondrian_pell_side j ∧ mondrian_pell_side j + 1 ≤ mondrian_pell_side (j + 1) := by
          intro j
          induction j with
          | zero => simp [mondrian_pell_side]
          | succ n ih =>
            obtain ⟨h1, h2⟩ := ih
            have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl
            refine ⟨by omega, ?_⟩
            rw [e]; omega
        exact fun j => by have := (key j).1; omega
  2. To show liminf_{n→∞} M₇(n) ≤ 280, it suffices to show that for every threshold N, M₇(mondrian_pell_side N) ≤ 280.

    By Filter.liminf_le_of_frequently_le', the limit inferior along Filter.atTop is at most 280 if M₇(n) ≤ 280 holds frequently. Rewriting this condition with Filter.frequently_atTop means that for any threshold N, there must exist some b ≥ N with M₇(b) ≤ 280. Choosing b = mondrian_pell_side N, the growth lemma guarantees N ≤ mondrian_pell_side N, so it suffices to show M₇(mondrian_pell_side N) ≤ 280.

    lines 14–17

    uses Filter.liminf_le_of_frequently_le', Filter.frequently_atTop

      apply Filter.liminf_le_of_frequently_le'
      rw [Filter.frequently_atTop]
      intro N
      refine ⟨mondrian_pell_side N, hgrow N, ?_⟩
  3. M₇(mondrian_pell_side N) ≤ 280, completing the proof.

    The lemma mondrian_pell_family_defect_280 provides a partition P of the square of side mondrian_pell_side N into 7 rectangles with defect exactly 280. Because M₇(n) is defined as the infimum of defects over all valid 7-rectangle partitions of an n × n square, iInf₂_le bounds this infimum by the defect of P, which is 280.

    lines 18–21

    uses mondrian_pell_family_defect_280, iInf₂_le

      obtain ⟨⟨P, hP, hlen, hdef⟩, -⟩ := mondrian_pell_family_defect_280 N
      calc mondrian_min_defect_seven (mondrian_pell_side N) ≤ (mondrian_defect P : ℕ∞) :=
            iInf₂_le P ⟨hP, hlen⟩
        _ = 280 := by rw [hdef]; rfl
Filter.liminf_le_of_frequently_le'
If a property holds frequently along a filter, then the limit inferior along that filter is bounded above by any value that bounds the property.
Filter.frequently_atTop
A predicate holds frequently along the atTop filter if and only if for every threshold a, there exists some b ≥ a satisfying the predicate.
mondrian_pell_family_defect_280
For every index j, there exists a 7-rectangle Mondrian partition of the square of side mondrian_pell_side j with defect 280, and the side length is congruent to 315 modulo 630.
iInf₂_le
The infimum of a doubly indexed family ⨅ i, ⨅ j, f i j is bounded above by any particular entry f i j.

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_liminf_min_defect_seven_le :    Filter.liminf (fun n => mondrian_min_defect_seven n) Filter.atTop ≤ 280 := by  have hgrow : ∀ j, j ≤ mondrian_pell_side j := by    have key : ∀ j, j + 315 ≤ mondrian_pell_side j ∧ mondrian_pell_side j + 1 ≤ mondrian_pell_side (j + 1) := by      intro j      induction j with      | zero => simp [mondrian_pell_side]      | succ n ih =>        obtain ⟨h1, h2⟩ := ih        have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl        refine ⟨by omega, ?_⟩        rw [e]; omega    exact fun j => by have := (key j).1; omega  apply Filter.liminf_le_of_frequently_le'  rw [Filter.frequently_atTop]  intro N  refine ⟨mondrian_pell_side N, hgrow N, ?_⟩  obtain ⟨⟨P, hP, hlen, hdef⟩, -⟩ := mondrian_pell_family_defect_280 N  calc mondrian_min_defect_seven (mondrian_pell_side N) ≤ (mondrian_defect P : ℕ∞) :=        iInf₂_le P ⟨hP, hlen⟩    _ = 280 := by rw [hdef]; rfl
See it in the graphDiscuss this resultChallenge it