mondrian_prime_square_area_shape_bound
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
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_prime_square_area_free_shape_boundFor distinct primes p and q and t+r=2e, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square have a side…
- mondrian_prime_square_area_middle_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square…
- Used by 1
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
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.
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).
uses
mondrian_prime_square_area_free_shape_bound,mondrian_prime_square_area_middle_shape_boundhave 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
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₂.
uses
Finset.card_filter_add_card_filter_not,not_or,not_nothave 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
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.
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
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_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