AFTD Auto-Formalizing Theoretical Domains

mondrian_pell_side_mod

theoremverified

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.

  1. 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.

    lines 2–5

      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
  2. 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.

    line 6

        | zero => simp [mondrian_pell_side]
  3. 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.

    lines 7–10

        | 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
  4. For 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.

    line 11

      exact (key j).1.1

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_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
See it in the graphDiscuss this resultChallenge it