AFTD Auto-Formalizing Theoretical Domains

mondrian_seven_rects_defect_ge

theoremverifiedformalization

Within the seven-rectangle family, the defect is always at least 280 (in particular never 0): if p, q are odd then p² − 19q² ≡ 2 (mod 4), and if both are even then 4 ∣ E with E ≠ 0, so |E| ≥ 2.

Statement

theorem mondrian_seven_rects_defect_ge (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p)
    (hp : p < 7 * q) :
    280 ≤ mondrian_defect (mondrian_seven_rects p q)
Formalizes
arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), Proposition 2.
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • mondrian_seven_rects_defectWith E = p² − 19q², the defect of the seven-rectangle dissection is 140|E|.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • mondrian_seven_rectsThe seven rectangles R₁, …, R₇ of the generic dissection of the n×n square, n = 105q, with a = 7(7q−p), b = 42q, c = 7(7q+p), d = 5(8q−p),…

The proof, explained

The proof uses the known formula expressing the defect of the seven-rectangle configuration as 140 · |p² − 19q²|. It first proves that p² − 19q² ≠ 0 using 19-adic valuations: since 19 is prime, p² = 19q² would require 2 · v₁₉(p) = 1 + 2 · v₁₉(q), which is impossible by parity. Next, since p and q share parity with q < p, writing p = q + 2s reveals that p² − 19q² = 2 · (2s² + 2qs − 9q²). Because this nonzero integer has an explicit factor of 2, its absolute value is at least 2, ensuring that the defect is at least 140 · 2 = 280.

  1. The defect of the seven-rectangle dissection is 140 · |p² − 19q²| as an integer

    We instantiate the known defect formula `mondrian_seven_rects_defect` using the assumed parity condition p % 2 = q % 2 and the inequalities q < p < 7q.

    line 4

    uses mondrian_seven_rects_defect

      have h := mondrian_seven_rects_defect p q hpar hqp hp
  2. p² − 19q² ≠ 0

    Suppose for contradiction that p² − 19q² = 0, so p² = 19q² with p, q > 0 (via `sub_eq_zero.mp`). Since 19 is prime, applying the 19-adic valuation v₁₉ to both sides (via `congrArg`) and expanding using valuation rules for products and powers (`padicValNat.pow`, `padicValNat.mul`, `pow_ne_zero`, `padicValNat_self`) produces the identity 2 · v₁₉(p) = 1 + 2 · v₁₉(q). This equates an even integer with an odd integer, which is impossible.

    lines 5–14

    uses sub_eq_zero.mp, congrArg, padicValNat.pow, padicValNat.mul, pow_ne_zero, padicValNat_self

      have hne : (p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 ≠ 0 := by
        intro hE
        have hEq : p ^ 2 = 19 * q ^ 2 := by exact_mod_cast (sub_eq_zero.mp hE)
        have hq0 : q ≠ 0 := by omega
        have hp0 : p ≠ 0 := by omega
        haveI : Fact (Nat.Prime 19) := ⟨by norm_num⟩
        have hv := congrArg (padicValNat 19) hEq
        rw [padicValNat.pow, padicValNat.mul (by norm_num) (pow_ne_zero 2 hq0),
          padicValNat.pow, padicValNat_self] at hv
        omega
  3. There exists a natural number s such that p = q + 2s

    Because p and q share the same parity (p % 2 = q % 2) and q < p, their difference p − q is a positive even integer, so setting s = (p − q) / 2 provides the required witness.

    line 15

      obtain ⟨s, rfl⟩ : ∃ s, p = q + 2 * s := ⟨(p - q) / 2, by omega⟩
  4. p² − 19q² factors as 2 · (2s² + 2qs − 9q²), and this product is nonzero

    Substituting p = q + 2s into p² − 19q² and expanding algebraically yields 2 · (2s² + 2qs − 9q²). Rewriting this expression into both the defect equation and the nonvanishing hypothesis shows that the defect is 140 · |2 · (2s² + 2qs − 9q²)| and that this product does not vanish.

    lines 16–18

      have hF : ((q + 2 * s : ℕ) : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 =
          2 * (2 * (s : ℤ) ^ 2 + 2 * q * s - 9 * q ^ 2) := by push_cast; ring
      rw [hF] at h hne
  5. The integer factor |2s² + 2qs − 9q²| is at least 1

    Any nonzero integer has absolute value at least 1 (`Int.one_le_abs`). If 2s² + 2qs − 9q² were zero, multiplying it by 2 would give 0 (`mul_zero`), contradicting our previous finding that 2 · (2s² + 2qs − 9q²) ≠ 0.

    lines 19–23

    uses Int.one_le_abs, mul_zero

      have h1 : (1 : ℤ) ≤ |2 * (s : ℤ) ^ 2 + 2 * q * s - 9 * q ^ 2| := by
        apply Int.one_le_abs
        intro h0
        apply hne
        rw [h0, mul_zero]
  6. The defect of the seven-rectangle dissection is at least 280

    Factoring out |2| = 2 from the absolute value (`abs_mul`, `abs_of_pos`) turns 140 · |2 · (2s² + 2qs − 9q²)| into 280 · |2s² + 2qs − 9q²|. Since |2s² + 2qs − 9q²| ≥ 1, linear arithmetic gives 280 ≤ defect in the integers, which `exact_mod_cast` transfers to the natural numbers to conclude the theorem.

    lines 24–27

    uses abs_mul, abs_of_pos

      rw [abs_mul, abs_of_pos (by norm_num : (0 : ℤ) < 2)] at h
      have h2 : (280 : ℤ) ≤ (mondrian_defect (mondrian_seven_rects (q + 2 * s) q) : ℤ) := by
        rw [h]; linarith
      exact_mod_cast h2
mondrian_seven_rects_defect
For natural numbers satisfying the bounds and parity conditions, the defect of the seven-rectangle dissection is 140 · |p² − 19q²|
sub_eq_zero.mp
If a − b = 0, then a = b
congrArg
If two inputs are equal, applying any function to them yields equal outputs: a = b implies f(a) = f(b)
padicValNat.pow
The p-adic valuation of a power is vₚ(aⁿ) = n · vₚ(a)
padicValNat.mul
For nonzero natural numbers a and b, the p-adic valuation of their product is vₚ(ab) = vₚ(a) + vₚ(b)
pow_ne_zero
In a domain with no zero divisors, powers of a nonzero element are nonzero: a ≠ 0 implies aⁿ ≠ 0
padicValNat_self
For any prime p, the p-adic valuation of p is 1, i.e., vₚ(p) = 1
Int.one_le_abs
Any nonzero integer has absolute value at least 1
mul_zero
Multiplying any element by zero gives zero: a · 0 = 0
abs_mul
The absolute value of a product is the product of the absolute values: |ab| = |a| · |b|
abs_of_pos
If an element is strictly positive, its absolute value equals itself: a > 0 implies |a| = 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_seven_rects_defect_ge (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p)    (hp : p < 7 * q) :    280 ≤ mondrian_defect (mondrian_seven_rects p q) := by  have h := mondrian_seven_rects_defect p q hpar hqp hp  have hne : (p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 ≠ 0 := by    intro hE    have hEq : p ^ 2 = 19 * q ^ 2 := by exact_mod_cast (sub_eq_zero.mp hE)    have hq0 : q ≠ 0 := by omega    have hp0 : p ≠ 0 := by omega    haveI : Fact (Nat.Prime 19) := ⟨by norm_num⟩    have hv := congrArg (padicValNat 19) hEq    rw [padicValNat.pow, padicValNat.mul (by norm_num) (pow_ne_zero 2 hq0),      padicValNat.pow, padicValNat_self] at hv    omega  obtain ⟨s, rfl⟩ : ∃ s, p = q + 2 * s := ⟨(p - q) / 2, by omega⟩  have hF : ((q + 2 * s : ℕ) : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 =      2 * (2 * (s : ℤ) ^ 2 + 2 * q * s - 9 * q ^ 2) := by push_cast; ring  rw [hF] at h hne  have h1 : (1 : ℤ) ≤ |2 * (s : ℤ) ^ 2 + 2 * q * s - 9 * q ^ 2| := by    apply Int.one_le_abs    intro h0    apply hne    rw [h0, mul_zero]  rw [abs_mul, abs_of_pos (by norm_num : (0 : ℤ) < 2)] at h  have h2 : (280 : ℤ) ≤ (mondrian_defect (mondrian_seven_rects (q + 2 * s) q) : ℤ) := by    rw [h]; linarith  exact_mod_cast h2
See it in the graphDiscuss this resultChallenge it