AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_square_area_shape_bound

theoremverified

For distinct primes p and q and t+r=2e with positive r, at most 2r unordered shapes of area q^2 times p^t fit in the q times p^e square.

Statement

theorem mondrian_prime_square_area_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p)
    (hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) (hr : 0 < r) :
    (mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).card ≤ 2 * r
Source
Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof partitions the valid shapes of area q² pᵗ fitting in the (q pᵉ) × (q pᵉ) square into two complementary subsets: shapes where at least one dimension is not divisible by q, and shapes where both dimensions are divisible by q. Each subset is bounded above by r using previously established lemmas (`mondrian_prime_square_area_free_shape_bound` and `mondrian_prime_square_area_middle_shape_bound`). Summing these two bounds shows that the total number of shapes cannot exceed 2r.

  1. At most r shapes have at least one dimension not divisible by q, and at most r shapes have both dimensions divisible by q.

    We apply two prior lemmas to bound each subset: `mondrian_prime_square_area_free_shape_bound` establishes that the number of shapes (d₁, d₂) satisfying ¬(q ∣ d₁) ∨ ¬(q ∣ d₂) is at most r (hypothesis h1), while `mondrian_prime_square_area_middle_shape_bound` establishes that the number of shapes satisfying q ∣ d₁ ∧ q ∣ d₂ is also at most r (hypothesis h2).

    lines 4–5

    uses mondrian_prime_square_area_free_shape_bound, mondrian_prime_square_area_middle_shape_bound

      have h1 := mondrian_prime_square_area_free_shape_bound p q e t r hp hq hpq htr
      have h2 := mondrian_prime_square_area_middle_shape_bound p q e t r hp hq hpq htr hr
  2. The total number of shapes is the sum of the counts of these two complementary subsets.

    Using `Finset.card_filter_add_card_filter_not`, the set of valid shapes is partitioned into elements satisfying ¬(q ∣ d₁) ∨ ¬(q ∣ d₂) and elements satisfying its negation. Rewriting the negation ¬(¬(q ∣ d₁) ∨ ¬(q ∣ d₂)) using De Morgan's law (`not_or`) and double negation elimination (`not_not`) transforms it into q ∣ d₁ ∧ q ∣ d₂.

    lines 6–9

    uses Finset.card_filter_add_card_filter_not, not_or, not_not

      have hh := Finset.card_filter_add_card_filter_not
        (s := mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t))
        (fun d : ℕ × ℕ => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)
      simp only [not_or, not_not] at hh
  3. The total number of valid shapes is at most 2r.

    Since the total count is the sum of the two subset sizes (hypothesis hh) and each subset size is at most r (hypotheses h1 and h2), linear integer arithmetic (`omega`) completes the proof that the total is at most r + r = 2r.

    line 10

      omega
Finset.card_filter_add_card_filter_not
For any finite set s and decidable property p, the number of elements in s satisfying p plus the number of elements satisfying ¬p equals the total cardinality of s.
mondrian_prime_square_area_free_shape_bound
For distinct primes p and q and t + r = 2e, the number of shapes of area q² pᵗ fitting in a (q pᵉ) × (q pᵉ) square with at least one side not divisible by q is at most r.
mondrian_prime_square_area_middle_shape_bound
For distinct primes p and q, t + r = 2e, and r > 0, the number of shapes of area q² pᵗ fitting in a (q pᵉ) × (q pᵉ) square with both sides divisible by q is at most r.
not_not
Double negation elimination: ¬¬P ↔ P.
not_or
De Morgan's law: the negation of a disjunction is the conjunction of the negations, ¬(P ∨ Q) ↔ ¬P ∧ ¬Q.

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_prime_square_area_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p)    (hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) (hr : 0 < r) :    (mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).card ≤ 2 * r := by  have h1 := mondrian_prime_square_area_free_shape_bound p q e t r hp hq hpq htr  have h2 := mondrian_prime_square_area_middle_shape_bound p q e t r hp hq hpq htr hr  have hh := Finset.card_filter_add_card_filter_not    (s := mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t))    (fun d : ℕ × ℕ => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)  simp only [not_or, not_not] at hh  omega
See it in the graphDiscuss this resultChallenge it