AFTD Auto-Formalizing Theoretical Domains

mondrian_pell_side_eq

theoremverified

Each n_j equals 105 q_j for odd p_j, q_j with q_j < p_j < 7q_j and p_j² − 19 q_j² = −2, where (p₀, q₀) = (13, 3) and (p_{j+1}, q_{j+1}) = (170p_j + 741q_j, 39p_j + 170q_j).

Statement

theorem mondrian_pell_side_eq (j : ℕ) :
    ∃ p q : ℕ, p % 2 = 1 ∧ q % 2 = 1 ∧ q < p ∧ p < 7 * q ∧
      (p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 = -2 ∧ mondrian_pell_side j = 105 * q
Source
arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), proof of Theorem 1.1 (the norm −2 Pell family); serves mondrian_pell_family_defect_280.
Verified
15 Oct 2026
Axioms
Quot.soundpropext
Built on 1
  • mondrian_pell_sideThe side lengths n₀ = 315, n₁ = 106785, n_{j+2} = 340 n_{j+1} − n_j.
Used by 1
  • 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…

The proof, explained

To express each Mondrian side length as $105 q_j$ with the required constraints, the proof defines a sequence of pairs $(p_j, q_j)$ starting from $(13, 3)$ using the recurrence $(p_{j+1}, q_{j+1}) = (170 p_j + 741 q_j, 39 p_j + 170 q_j)$. By induction, the algebraic identity $(170p + 741q)^2 - 19(39p + 170q)^2 = p^2 - 19q^2$ ensures that $p_j^2 - 19 q_j^2 = -2$ for all $j$, while odd parity and the bounds $q_j < p_j < 7q_j$ are preserved at each step. Finally, unrolling the recurrence shows that $q_j$ satisfies $q_{j+2} = 340 q_{j+1} - q_j$, matching the defining recurrence of $\\mathrm{mondrian\\_pell\\_side}$ and establishing $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q_j$.

  1. For the base case $j = 0$, $p_0^2 - 19 q_0^2 = -2$.

    At $j = 0$, the initial pair is $(p_0, q_0) = (13, 3)$. Evaluating the quadratic form gives $13^2 - 19 \\times 3^2 = 169 - 171 = -2$, which Lean verifies by direct computation (`decide`).

    lines 12–13

      induction j with
      | zero => decide
  2. For every $n \\in \\mathbb{N}$, if $p_n^2 - 19 q_n^2 = -2$, then $p_{n+1}^2 - 19 q_{n+1}^2 = -2$.

    By the recurrence definition, $p_{n+1} = 170 p_n + 741 q_n$ and $q_{n+1} = 39 p_n + 170 q_n$. The algebraic identity $(170p + 741q)^2 - 19(39p + 170q)^2 = p^2 - 19q^2$ holds for all integers (verified by `ring`). Substituting $p_{n+1}$ and $q_{n+1}$ into the Pell form and rewriting with this identity shows that $p_{n+1}^2 - 19 q_{n+1}^2 = p_n^2 - 19 q_n^2$, which equals $-2$ by the induction hypothesis.

    lines 14–23

      | succ n ih =>
        have hP : (mondrian_pell_side_eq_p (n + 1) : ℤ) =
            170 * (mondrian_pell_side_eq_p n : ℤ) + 741 * (mondrian_pell_side_eq_q n : ℤ) := by
          push_cast [mondrian_pell_side_eq_p]; rfl
        have hQ : (mondrian_pell_side_eq_q (n + 1) : ℤ) =
            39 * (mondrian_pell_side_eq_p n : ℤ) + 170 * (mondrian_pell_side_eq_q n : ℤ) := by
          push_cast [mondrian_pell_side_eq_q]; rfl
        have id : ∀ p q : ℤ, (170 * p + 741 * q) ^ 2 - 19 * (39 * p + 170 * q) ^ 2 = p ^ 2 - 19 * q ^ 2 := by
          intro p q; ring
        rw [hP, hQ, id, ih]
  3. The initial values $p_0 = 13$ and $q_0 = 3$ are odd, and satisfy $q_0 < p_0 < 7 q_0$.

    For $j = 0$, both $13$ and $3$ leave remainder $1$ modulo $2$, and $3 < 13 < 7 \\times 3 = 21$. This conjunction of finite arithmetic checks is discharged by `decide`.

    lines 30–31

      induction j with
      | zero => decide
  4. The inductive step preserves odd parity of $p$ and $q$ and the bounds $q < p < 7q$.

    Assuming the bounds and odd parity hold for $n$, the recurrence gives $p_{n+1} = 170 p_n + 741 q_n$ and $q_{n+1} = 39 p_n + 170 q_n$. Because $170$ is even while $741$ and $39$ are odd, $p_{n+1} \\equiv q_n \\equiv 1 \\pmod 2$ and $q_{n+1} \\equiv p_n \\equiv 1 \\pmod 2$. The inequalities $q_{n+1} < p_{n+1}$ and $p_{n+1} < 7 q_{n+1}$ follow from $q_n < p_n < 7 q_n$ by linear arithmetic, closed by `omega`.

    lines 32–40

      | succ n ih =>
        obtain ⟨h1, h2, h3, h4⟩ := ih
        have hP : mondrian_pell_side_eq_p (n + 1) = 170 * mondrian_pell_side_eq_p n + 741 * mondrian_pell_side_eq_q n := rfl
        have hQ : mondrian_pell_side_eq_q (n + 1) = 39 * mondrian_pell_side_eq_p n + 170 * mondrian_pell_side_eq_q n := rfl
        refine ⟨?_, ?_, ?_, ?_⟩
        · rw [hP]; omega
        · rw [hQ]; omega
        · rw [hP, hQ]; omega
        · rw [hP, hQ]; omega
  5. The sequence $q_j$ satisfies the three-term recurrence $q_{j+2} + q_j = 340 q_{j+1}$.

    Expanding $q_{j+2} = 39 p_{j+1} + 170 q_{j+1}$ and substituting $p_{j+1} = 170 p_j + 741 q_j$ and $q_{j+1} = 39 p_j + 170 q_j$, both $q_{j+2} + q_j$ and $340 q_{j+1}$ reduce to $13260 p_j + 57800 q_j$, which is verified by linear integer arithmetic (`omega`).

    lines 44–51

      have h1 : mondrian_pell_side_eq_q (j + 2) =
          39 * mondrian_pell_side_eq_p (j + 1) + 170 * mondrian_pell_side_eq_q (j + 1) := rfl
      have h2 : mondrian_pell_side_eq_p (j + 1) =
          170 * mondrian_pell_side_eq_p j + 741 * mondrian_pell_side_eq_q j := rfl
      have h3 : mondrian_pell_side_eq_q (j + 1) =
          39 * mondrian_pell_side_eq_p j + 170 * mondrian_pell_side_eq_q j := rfl
      rw [h1, h2, h3]
      omega
  6. For all $k \\in \\mathbb{N}$, $\\mathrm{mondrian\\_pell\\_side}(k) = 105 q_k$ and $\\mathrm{mondrian\\_pell\\_side}(k+1) = 105 q_{k+1}$.

    We prove this simultaneous statement by induction on $k$. The base case $k = 0$ asserts $\\mathrm{mondrian\\_pell\\_side}(0) = 105 q_0$ and $\\mathrm{mondrian\\_pell\\_side}(1) = 105 q_1$, which holds because $315 = 105 \\times 3$ and $106785 = 105 \\times 1017$ (`decide`). For the inductive step, the first equality is the induction hypothesis for $k+1$. For the second, $\\mathrm{mondrian\\_pell\\_side}(n+2) = 340 \\, \\mathrm{mondrian\\_pell\\_side}(n+1) - \\mathrm{mondrian\\_pell\\_side}(n)$ by definition; substituting the induction hypotheses and using the recurrence $q_{n+2} + q_n = 340 q_{n+1}$ from `mondrian_pell_side_eq_q_step`, `omega` verifies that $\\mathrm{mondrian\\_pell\\_side}(n+2) = 105 q_{n+2}$.

    lines 55–68

    uses mondrian_pell_side_eq_q_step

      have key : ∀ k, mondrian_pell_side k = 105 * mondrian_pell_side_eq_q k ∧
          mondrian_pell_side (k + 1) = 105 * mondrian_pell_side_eq_q (k + 1) := by
        intro k
        induction k with
        | zero =>
          decide
        | succ n ih =>
          obtain ⟨h1, h2⟩ := ih
          refine ⟨h2, ?_⟩
          have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl
          have hstep := mondrian_pell_side_eq_q_step n
          change mondrian_pell_side (n + 2) = 105 * mondrian_pell_side_eq_q (n + 2)
          rw [e, h1, h2]
          omega
  7. For all $j \\in \\mathbb{N}$, $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q_j$.

    Specializing the inductive result to $k = j$ and extracting the first conjunct gives $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q_j$.

    line 69

      exact (key j).1
  8. There exist odd natural numbers $p, q$ with $q < p < 7q$, $p^2 - 19q^2 = -2$, and $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q$.

    We instantiate the existential witnesses with $p_j$ and $q_j$. Their odd parity and the bounds $q_j < p_j < 7 q_j$ are provided by `mondrian_pell_side_eq_bounds`. The Pell equation $p_j^2 - 19 q_j^2 = -2$ holds by `mondrian_pell_side_eq_pell`, and the side length equality $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q_j$ holds by `mondrian_pell_side_eq_side`.

    lines 74–76

    uses mondrian_pell_side_eq_bounds, mondrian_pell_side_eq_pell, mondrian_pell_side_eq_side

      use mondrian_pell_side_eq_p j, mondrian_pell_side_eq_q j
      obtain ⟨h1, h2, h3, h4⟩ := mondrian_pell_side_eq_bounds j
      exact ⟨h1, h2, h3, h4, mondrian_pell_side_eq_pell j, mondrian_pell_side_eq_side j⟩
mondrian_pell_side_eq_q_step
For every $j \\in \\mathbb{N}$, the sequence $q_j$ satisfies the linear recurrence $q_{j+2} + q_j = 340 q_{j+1}$.
mondrian_pell_side_eq_bounds
For every $j \\in \\mathbb{N}$, $p_j$ and $q_j$ are odd natural numbers satisfying $q_j < p_j < 7 q_j$.
mondrian_pell_side_eq_pell
For every $j \\in \\mathbb{N}$, the pair $(p_j, q_j)$ satisfies the Pell-type equation $p_j^2 - 19 q_j^2 = -2$ in integers.
mondrian_pell_side_eq_side
For every $j \\in \\mathbb{N}$, the Mondrian side length sequence satisfies $\\mathrm{mondrian\\_pell\\_side}(j) = 105 q_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

def mondrian_pell_side_eq_pair : ℕ → ℕ × ℕ  | 0 => (13, 3)  | j + 1 =>    let pq := mondrian_pell_side_eq_pair j    (170 * pq.1 + 741 * pq.2, 39 * pq.1 + 170 * pq.2)def mondrian_pell_side_eq_p (j : ℕ) : ℕ := (mondrian_pell_side_eq_pair j).1def mondrian_pell_side_eq_q (j : ℕ) : ℕ := (mondrian_pell_side_eq_pair j).2lemma mondrian_pell_side_eq_pell (j : ℕ) :    (mondrian_pell_side_eq_p j : ℤ) ^ 2 - 19 * (mondrian_pell_side_eq_q j : ℤ) ^ 2 = -2 := by  induction j with  | zero => decide  | succ n ih =>    have hP : (mondrian_pell_side_eq_p (n + 1) : ℤ) =        170 * (mondrian_pell_side_eq_p n : ℤ) + 741 * (mondrian_pell_side_eq_q n : ℤ) := by      push_cast [mondrian_pell_side_eq_p]; rfl    have hQ : (mondrian_pell_side_eq_q (n + 1) : ℤ) =        39 * (mondrian_pell_side_eq_p n : ℤ) + 170 * (mondrian_pell_side_eq_q n : ℤ) := by      push_cast [mondrian_pell_side_eq_q]; rfl    have id : ∀ p q : ℤ, (170 * p + 741 * q) ^ 2 - 19 * (39 * p + 170 * q) ^ 2 = p ^ 2 - 19 * q ^ 2 := by      intro p q; ring    rw [hP, hQ, id, ih]lemma mondrian_pell_side_eq_bounds (j : ℕ) :    mondrian_pell_side_eq_p j % 2 = 1 ∧    mondrian_pell_side_eq_q j % 2 = 1 ∧    mondrian_pell_side_eq_q j < mondrian_pell_side_eq_p j ∧    mondrian_pell_side_eq_p j < 7 * mondrian_pell_side_eq_q j := by  induction j with  | zero => decide  | succ n ih =>    obtain ⟨h1, h2, h3, h4⟩ := ih    have hP : mondrian_pell_side_eq_p (n + 1) = 170 * mondrian_pell_side_eq_p n + 741 * mondrian_pell_side_eq_q n := rfl    have hQ : mondrian_pell_side_eq_q (n + 1) = 39 * mondrian_pell_side_eq_p n + 170 * mondrian_pell_side_eq_q n := rfl    refine ⟨?_, ?_, ?_, ?_⟩    · rw [hP]; omega    · rw [hQ]; omega    · rw [hP, hQ]; omega    · rw [hP, hQ]; omegalemma mondrian_pell_side_eq_q_step (j : ℕ) :    mondrian_pell_side_eq_q (j + 2) + mondrian_pell_side_eq_q j = 340 * mondrian_pell_side_eq_q (j + 1) := by  have h1 : mondrian_pell_side_eq_q (j + 2) =      39 * mondrian_pell_side_eq_p (j + 1) + 170 * mondrian_pell_side_eq_q (j + 1) := rfl  have h2 : mondrian_pell_side_eq_p (j + 1) =      170 * mondrian_pell_side_eq_p j + 741 * mondrian_pell_side_eq_q j := rfl  have h3 : mondrian_pell_side_eq_q (j + 1) =      39 * mondrian_pell_side_eq_p j + 170 * mondrian_pell_side_eq_q j := rfl  rw [h1, h2, h3]  omegalemma mondrian_pell_side_eq_side (j : ℕ) :    mondrian_pell_side j = 105 * mondrian_pell_side_eq_q j := by  have key : ∀ k, mondrian_pell_side k = 105 * mondrian_pell_side_eq_q k ∧      mondrian_pell_side (k + 1) = 105 * mondrian_pell_side_eq_q (k + 1) := by    intro k    induction k with    | zero =>      decide    | succ n ih =>      obtain ⟨h1, h2⟩ := ih      refine ⟨h2, ?_⟩      have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl      have hstep := mondrian_pell_side_eq_q_step n      change mondrian_pell_side (n + 2) = 105 * mondrian_pell_side_eq_q (n + 2)      rw [e, h1, h2]      omega  exact (key j).1theorem mondrian_pell_side_eq (j : ℕ) :    ∃ p q : ℕ, p % 2 = 1 ∧ q % 2 = 1 ∧ q < p ∧ p < 7 * q ∧      (p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 = -2 ∧ mondrian_pell_side j = 105 * q := by  use mondrian_pell_side_eq_p j, mondrian_pell_side_eq_q j  obtain ⟨h1, h2, h3, h4⟩ := mondrian_pell_side_eq_bounds j  exact ⟨h1, h2, h3, h4, mondrian_pell_side_eq_pell j, mondrian_pell_side_eq_side j⟩
See it in the graphDiscuss this resultChallenge it