mondrian_pell_side_mod
Every side length n_j of the family is ≡ 315 (mod 630).
Statement
theorem mondrian_pell_side_mod (j : ℕ) : mondrian_pell_side j % 630 = 315- Source
- arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), Theorem 1.1 (the congruence n_j ≡ 315 mod 630); 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
The theorem is proved by mathematical induction on j. Because the recurrence for mondrian_pell_side is of second order, the statement is strengthened into an auxiliary lemma asserting that any two consecutive terms are congruent to 315 modulo 630 and that the sequence is non-decreasing. The base case j = 0 follows by directly evaluating the initial values 315 and 106785 modulo 630. In the inductive step, the recurrence mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n combined with the induction hypotheses preserves both the modulo 630 residue and monotonicity, from which the main theorem is immediately deduced.
To prove the theorem, it suffices to show by induction that for all j, both mondrian_pell_side j and mondrian_pell_side (j + 1) are congruent to 315 modulo 630, and mondrian_pell_side j ≤ mondrian_pell_side (j + 1).
Because the recurrence relation for mondrian_pell_side is of second order, a simple induction on a single term cannot propagate. We introduce a local lemma (key) with a strengthened induction hypothesis asserting that any two consecutive terms are congruent to 315 modulo 630 and that the sequence is non-decreasing. We introduce j and set up induction on j.
have key : ∀ j, (mondrian_pell_side j % 630 = 315 ∧ mondrian_pell_side (j + 1) % 630 = 315) ∧ mondrian_pell_side j ≤ mondrian_pell_side (j + 1) := by intro j induction j with
The base case j = 0 holds: mondrian_pell_side 0 ≡ 315 (mod 630), mondrian_pell_side 1 ≡ 315 (mod 630), and mondrian_pell_side 0 ≤ mondrian_pell_side 1. automation
For j = 0, the definition yields mondrian_pell_side 0 = 315 and mondrian_pell_side 1 = 106785. Since 315 % 630 = 315, 106785 = 169 * 630 + 315 ≡ 315 (mod 630), and 315 ≤ 106785, all three conditions hold. The simp tactic evaluates the definition of mondrian_pell_side and closes the goal.
| zero => simp [mondrian_pell_side]The inductive step holds: from the hypothesis for n, the conditions follow for n + 1, establishing the key lemma for all j. automation
Assuming the induction hypothesis for n, we have mondrian_pell_side n % 630 = 315, mondrian_pell_side (n + 1) % 630 = 315, and mondrian_pell_side n ≤ mondrian_pell_side (n + 1). The definition gives mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n. The first conjunct for n + 1 is immediate from the hypothesis. After rewriting mondrian_pell_side (n + 2) using this recurrence, the remaining goals require showing (340 * mondrian_pell_side (n + 1) - mondrian_pell_side n) % 630 = 315 and mondrian_pell_side (n + 1) ≤ 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n. Because 340 * 315 - 315 = 339 * 315 = 169 * 630 + 315 ≡ 315 (mod 630) and 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n ≥ 339 * mondrian_pell_side (n + 1) ≥ mondrian_pell_side (n + 1), the omega tactic verifies both arithmetic goals.
| succ n ih => obtain ⟨⟨h1, h2⟩, h3⟩ := ih have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl refine ⟨⟨h2, ?_⟩, ?_⟩ <;> rw [e] <;> omegaFor every j, mondrian_pell_side j % 630 = 315.
Specializing the proven lemma key to j and extracting the first conjunct yields mondrian_pell_side j % 630 = 315 directly.
exact (key j).1.1
- The sequence is defined using natural number subtraction, which truncates to 0 if the subtrahend exceeds the minuend. Strengthening the induction hypothesis to include the monotonicity condition mondrian_pell_side j ≤ mondrian_pell_side (j + 1) ensures that 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n behaves like integer subtraction without underflow.
- In the inductive step (line 10), the omega tactic automatically closes both subgoals—the congruence modulo 630 and the inequality preserving monotonicity—using Presburger linear arithmetic.
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.
theorem mondrian_pell_side_mod (j : ℕ) : mondrian_pell_side j % 630 = 315 := by have key : ∀ j, (mondrian_pell_side j % 630 = 315 ∧ mondrian_pell_side (j + 1) % 630 = 315) ∧ mondrian_pell_side j ≤ mondrian_pell_side (j + 1) := by intro j induction j with | zero => simp [mondrian_pell_side] | succ n ih => obtain ⟨⟨h1, h2⟩, h3⟩ := ih have e : mondrian_pell_side (n + 2) = 340 * mondrian_pell_side (n + 1) - mondrian_pell_side n := rfl refine ⟨⟨h2, ?_⟩, ?_⟩ <;> rw [e] <;> omega exact (key j).1.1