mondrian_pell_side_eq
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$.
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`).
induction j with | zero => decide
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.
| 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]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`.
induction j with | zero => decide
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`.
| 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]; omegaThe 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`).
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
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}$.
uses
mondrian_pell_side_eq_q_stephave 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
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$.
exact (key j).1There 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`.
uses
mondrian_pell_side_eq_bounds,mondrian_pell_side_eq_pell,mondrian_pell_side_eq_sideuse 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
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.
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⟩