mondrian_prime_square_area_free_shape_bound
For 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 indivisible by q.
Statement
theorem mondrian_prime_square_area_free_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) : ((mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).filter (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)).card ≤ 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 6
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
- mondrian_prime_free_factor_pair_encodingIn a positive factor pair of q^s times p^t whose first side is indivisible by q, that side is a pure p-power and the other side contains…
- mondrian_prime_power_side_log_boundA pure p-power side fitting in a q times p^e square has exponent at most e plus floor(log_p(q)).
- mondrian_prime_square_cofactor_side_boundA side q^2 times p^a fitting in a q times p^e square satisfies a plus floor(log_p(q)) plus one at most e, for distinct primes.
- mondrian_shape_exponent_interval_boundA family of distinct sorted factor pairs that can be encoded by a chosen side C times p to an exponent in [lo,hi] has at most hi plus one…
- Used by 2
- mondrian_prime_square_area_shape_boundFor 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.
- 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
Any shape of area q^2 * p^t fitting in a q * p^e square with at least one side indivisible by q must have that side entirely free of q (a pure power of p), while the other side carries the full factor q^2. The bounding box restricts both side lengths, confining the p-exponent of the q-free side to an explicit integer interval of length at most r, using the relation t + r = 2e. Since shapes are uniquely determined by this exponent, the interval bound lemma shows that at most r such shapes can exist.
Define the set of relevant shapes S and helper functions for each shape's sides and p-exponent.
Note that the primes p and q are positive. Define S as the set of shapes of area q^2 * p^t fitting into a q * p^e square where at least one side is not divisible by q. For any shape d, define g(d) to select the side not divisible by q (d₂ if q ∣ d₁, and d₁ otherwise), o(d) to select the other side, and f(d) as the exponent of p in the prime factorization of g(d).
have hp0 := hp.pos have hq0 := hq.pos let S := (mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).filter (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2) let g := fun d : ℕ × ℕ => if q ∣ d.1 then d.2 else d.1 let o := fun d : ℕ × ℕ => if q ∣ d.1 then d.1 else d.2 let f := fun d => (g d).factorization p
For each shape d ∈ S, g(d) is a pure power p^(f(d)), o(d) is q^2 * p^(v_p(o(d))), their p-exponents sum to t, and both sides are at most q * p^e.
Unpack membership in S: the side lengths satisfy d₁ * d₂ = q^2 * p^t, d₁ ≤ d₂ ≤ q * p^e, and both sides are strictly positive. Since at least one side is not divisible by q, split into cases on whether q ∣ d₁. If q ∣ d₁, then q ∤ d₂, and `mondrian_prime_free_factor_pair_encoding` gives d₂ = p^(v_p(d₂)) and d₁ = q^2 * p^(v_p(d₁)) with exponents summing to t; here g(d) = d₂ and o(d) = d₁. If q ∤ d₁, the same lemma applies directly to (d₁, d₂), giving g(d) = d₁ = p^(v_p(d₁)) and o(d) = d₂ = q^2 * p^(v_p(d₂)). In both cases, both side lengths are bounded above by d₂ ≤ q * p^e.
uses
Finset.mem_filter.mp,mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,Nat.mul_comm,mondrian_prime_free_factor_pair_encodinghave hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = p ^ f d ∧ o d = q ^ 2 * p ^ ((o d).factorization p) ∧ f d + (o d).factorization p = t ∧ g d ≤ q * p ^ e ∧ o d ≤ q * p ^ e := by intro d hd obtain ⟨hdS, hfree⟩ := Finset.mem_filter.mp hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hdS have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; positivity) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; positivity) by_cases hh : q ∣ d.1 · have hfree' : ¬ q ∣ d.2 := hfree.resolve_left (by simpa using hh) have h := mondrian_prime_free_factor_pair_encoding p q t 2 d.2 d.1 hp hq hpq hy hx (by simpa [Nat.mul_comm] using hprod) hfree' simpa [g, o, f, hh] using And.intro (Or.inr rfl : d.2 = d.1 ∨ d.2 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro hn (hord.trans hn))))) · have h := mondrian_prime_free_factor_pair_encoding p q t 2 d.1 d.2 hp hq hpq hx hy hprod hh simpa [g, o, f, hh] using And.intro (Or.inl rfl : d.1 = d.1 ∨ d.1 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro (hord.trans hn) hn))))
The number of shapes in S is bounded by the width of the interval for the exponent f(d), namely (e + ⌊log_p q⌋ + 1) - (e + ⌊log_p q⌋ + 1 - r).
Apply `mondrian_shape_exponent_interval_bound` with C = 1, lower bound lo = e + ⌊log_p q⌋ + 1 - r, and upper bound hi = e + ⌊log_p q⌋. For any d ∈ S, g(d) = p^(f(d)) ≤ q * p^e implies f(d) ≤ e + ⌊log_p q⌋ by `mondrian_prime_power_side_log_bound`. The cofactor side o(d) = q^2 * p^(v_p(o(d))) ≤ q * p^e implies v_p(o(d)) + ⌊log_p q⌋ + 1 ≤ e by `mondrian_prime_square_cofactor_side_bound`. Since f(d) + v_p(o(d)) = t and t + r = 2e, linear arithmetic (`omega`) deduces that f(d) ≥ e + ⌊log_p q⌋ + 1 - r.
uses
mondrian_shape_exponent_interval_bound,Nat.mul_pos,pow_pos,Finset.mem_filter.mp,mondrian_prime_power_side_log_bound,mondrian_prime_square_cofactor_side_boundhave hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q ^ 2 * p ^ t) 1 (e + Nat.log p q + 1 - r) (e + Nat.log p q) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t)) (fun _ h => (Finset.mem_filter.mp h).1) g f (by intro d hd; exact ⟨(hg d hd).1, by simpa using (hg d hd).2.1⟩) (by intro d hd obtain ⟨_, hgp, hop, hv, hgn, hon⟩ := hg d hd have ha := mondrian_prime_power_side_log_bound p q e (f d) hp (by rwa [← hgp]) have hb := mondrian_prime_square_cofactor_side_bound p q e ((o d).factorization p) hp hq hpq (by rwa [← hop]) constructor <;> omega)
The number of shapes in S is at most r. automation
Unfolding the definition of S in the interval bound, linear integer arithmetic (`omega`) simplifies (e + ⌊log_p q⌋ + 1) - (e + ⌊log_p q⌋ + 1 - r) to at most r.
dsimp [S] at hh omega
Finset.mem_filter.mp- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Nat.mul_comm- Multiplication on natural numbers is commutative: n * m = m * n.
Nat.pos_of_mul_pos_left- If a product of natural numbers is strictly positive, its second factor is strictly positive.
Nat.pos_of_mul_pos_right- If a product of natural numbers is strictly positive, its first factor is strictly positive.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
mondrian_mem_factor_shapes- A pair (d₁, d₂) is a factor shape of area A fitting in an n × n square if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
mondrian_prime_free_factor_pair_encoding- If two positive integers x and y have product q^s * p^t for distinct primes p and q, and q does not divide x, then x is a pure power of p, y is q^s times a power of p, and their p-adic exponents sum to t.
mondrian_prime_power_side_log_bound- If p is prime and p^a ≤ q * p^e, then the exponent a is at most e + ⌊log_p q⌋.
mondrian_prime_square_cofactor_side_bound- For distinct primes p and q, if q^2 * p^a ≤ q * p^e, then a + ⌊log_p q⌋ + 1 ≤ e.
mondrian_shape_exponent_interval_bound- If every shape in a set S has a side equal to C * p^(f(d)) with f(d) restricted to [lo, hi], then the number of shapes in S is at most hi + 1 - lo.
pow_pos- A positive base raised to any natural power is strictly positive.
- Natural number subtraction in the interval bounds is truncated at zero, but `omega` automatically accounts for this arithmetic detail in deducing the upper bound on the interval width.
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_free_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) : ((mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).filter (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)).card ≤ r := by have hp0 := hp.pos have hq0 := hq.pos let S := (mondrian_factor_shapes (q * p ^ e) (q ^ 2 * p ^ t)).filter (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2) let g := fun d : ℕ × ℕ => if q ∣ d.1 then d.2 else d.1 let o := fun d : ℕ × ℕ => if q ∣ d.1 then d.1 else d.2 let f := fun d => (g d).factorization p have hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = p ^ f d ∧ o d = q ^ 2 * p ^ ((o d).factorization p) ∧ f d + (o d).factorization p = t ∧ g d ≤ q * p ^ e ∧ o d ≤ q * p ^ e := by intro d hd obtain ⟨hdS, hfree⟩ := Finset.mem_filter.mp hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hdS have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; positivity) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; positivity) by_cases hh : q ∣ d.1 · have hfree' : ¬ q ∣ d.2 := hfree.resolve_left (by simpa using hh) have h := mondrian_prime_free_factor_pair_encoding p q t 2 d.2 d.1 hp hq hpq hy hx (by simpa [Nat.mul_comm] using hprod) hfree' simpa [g, o, f, hh] using And.intro (Or.inr rfl : d.2 = d.1 ∨ d.2 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro hn (hord.trans hn))))) · have h := mondrian_prime_free_factor_pair_encoding p q t 2 d.1 d.2 hp hq hpq hx hy hprod hh simpa [g, o, f, hh] using And.intro (Or.inl rfl : d.1 = d.1 ∨ d.1 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro (hord.trans hn) hn)))) have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q ^ 2 * p ^ t) 1 (e + Nat.log p q + 1 - r) (e + Nat.log p q) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t)) (fun _ h => (Finset.mem_filter.mp h).1) g f (by intro d hd; exact ⟨(hg d hd).1, by simpa using (hg d hd).2.1⟩) (by intro d hd obtain ⟨_, hgp, hop, hv, hgn, hon⟩ := hg d hd have ha := mondrian_prime_power_side_log_bound p q e (f d) hp (by rwa [← hgp]) have hb := mondrian_prime_square_cofactor_side_bound p q e ((o d).factorization p) hp hq hpq (by rwa [← hop]) constructor <;> omega) dsimp [S] at hh omega