mondrian_prime_square_area_middle_shape_bound
For 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 have both sides divisible by q.
Statement
theorem mondrian_prime_square_area_middle_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)).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 7
- mondrian_distinct_prime_not_dvd_powA prime q distinct from p does not divide any power of p.
- 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_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…
- mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- 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.
The proof, explained
The proof bounds the number of shapes (ordered factor pairs) of area q^2 * p^t fitting in a q * p^e square such that both dimensions are multiples of q. First, it shows that the divisibility by q forces both dimensions to have q-adic valuation exactly 1, so the shapes are of the form (q * p^a, q * p^b) with a + b = t, a ≤ b, and b ≤ e. Consequently, the smaller exponent a is constrained to the integer interval [e - r, e - 1]. Applying `mondrian_shape_exponent_interval_bound` then bounds the cardinality of such shapes by (e - 1) + 1 - (e - r) = r.
The set S of shapes with both dimensions divisible by q is defined, and the exponent e is positive.
We note the positivity of the primes p and q, and define S as the filter of shapes in `mondrian_factor_shapes (q * p^e) (q^2 * p^t)` whose components are both divisible by q. Since t + r = 2e and r > 0, linear arithmetic (`omega`) ensures e > 0.
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) have he : 0 < e := by omega
Every shape d = (d.1, d.2) in S factors as d.1 = q * p^(v_p(d.1)) and d.2 = q * p^(v_p(d.2)), with v_p(d.1) + v_p(d.2) = t.
Since d is in S, d.1 * d.2 = q^2 * p^t with d.1, d.2 > 0. By `mondrian_two_prime_factor_pair_encoding`, d.1 = q^b * p^(v_p(d.1)) and d.2 = q^c * p^(v_p(d.2)) with b + c = 2 and v_p(d.1) + v_p(d.2) = t. If b = 0, then d.1 = p^(v_p(d.1)), implying q ∣ p^(v_p(d.1)), which contradicts `mondrian_distinct_prime_not_dvd_pow`. Thus b ≠ 0. Symmetrically, c ≠ 0. Because b + c = 2 in ℕ and both are non-zero, b = 1 and c = 1.
uses
Finset.mem_filter.mp,mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,mondrian_two_prime_factor_pair_encoding,mondrian_distinct_prime_not_dvd_pow,pow_zero,one_mul,pow_onehave hdata : ∀ d ∈ S, d.1 = q * p ^ d.1.factorization p ∧ d.2 = q * p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t ∧ d.1.factorization p ≤ d.2.factorization p ∧ d.2.factorization p ≤ e := by intro d hd obtain ⟨hdS, hdivx, hdivy⟩ := 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) obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 2 d.1 d.2 hp hq hpq hx hy hprod have hb : b ≠ 0 := by intro hh have hnod := mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq apply hnod rw [hxb, hh, pow_zero, one_mul] at hdivx exact hdivx have hc : c ≠ 0 := by intro hh have hnod := mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq apply hnod rw [hyc, hh, pow_zero, one_mul] at hdivy exact hdivy have hb1 : b = 1 := by omega have hc1 : c = 1 := by omega simp only [hb1, hc1, pow_one] at hxb hyc
The p-adic valuations satisfy v_p(d.1) ≤ v_p(d.2) ≤ e.
From the shape ordering d.1 ≤ d.2 and the bounding box constraint d.2 ≤ q * p^e, we substitute the factorizations to get q * p^(v_p(d.1)) ≤ q * p^(v_p(d.2)) and q * p^(v_p(d.2)) ≤ q * p^e. Dividing by q > 0 leaves p^(v_p(d.1)) ≤ p^(v_p(d.2)) and p^(v_p(d.2)) ≤ p^e. Since p > 1, `Nat.pow_le_pow_iff_right` converts these to the exponent inequalities v_p(d.1) ≤ v_p(d.2) and v_p(d.2) ≤ e.
uses
Nat.pow_le_pow_iff_righthave hab : d.1.factorization p ≤ d.2.factorization p := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp rw [hxb, hyc] at hord nlinarith [hq.pos] have hbe : d.2.factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp rw [hyc] at hn nlinarith [hq.pos] exact ⟨hxb, hyc, hv, hab, hbe⟩
The cardinality of S is bounded by (e - 1) + 1 - (e - r).
For every d in S, the first coordinate is d.1 = q * p^(v_p(d.1)). From v_p(d.1) + v_p(d.2) = t, v_p(d.1) ≤ v_p(d.2) ≤ e, and t + r = 2e with r > 0, linear arithmetic establishes that v_p(d.1) lies in the interval [e - r, e - 1]. Applying `mondrian_shape_exponent_interval_bound` with C = q, lo = e - r, and hi = e - 1 yields |S| ≤ (e - 1) + 1 - (e - r).
uses
mondrian_shape_exponent_interval_bound,Nat.mul_pos,pow_pos,Finset.mem_filter.mp,Prod.fst,Or.inlhave hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q ^ 2 * p ^ t) q (e - r) (e - 1) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t)) (fun _ h => (Finset.mem_filter.mp h).1) Prod.fst (fun d => d.1.factorization p) (by intro d hd; exact ⟨Or.inl rfl, (hdata d hd).1⟩) (by intro d hd obtain ⟨_, _, hv, hab, hbe⟩ := hdata d hd constructor <;> omega)
The number of shapes in S is at most r. automation
Unfolding the definition of S in the bound and evaluating (e - 1) + 1 - (e - r) = r via linear arithmetic (`omega`) closes the goal.
dsimp [S] at hh omega
Finset.mem_filter.mp- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
mondrian_mem_factor_shapes- A pair d belongs to mondrian_factor_shapes n A if and only if d.1 * d.2 = A, A ≠ 0, d.1 ≤ d.2, and d.2 ≤ n.
Nat.pos_of_mul_pos_right- If the product of natural numbers a * b is positive, then a is positive.
Nat.pos_of_mul_pos_left- If the product of natural numbers a * b is positive, then b is positive.
mondrian_two_prime_factor_pair_encoding- For distinct primes p and q and positive integers x, y with x * y = q^s * p^t, there exist natural numbers b, c summing to s such that x = q^b * p^(v_p(x)), y = q^c * p^(v_p(y)), and v_p(x) + v_p(y) = t.
mondrian_distinct_prime_not_dvd_pow- For distinct primes p and q, q does not divide any power p^a.
pow_zero- Any element raised to the zeroth power equals 1.
one_mul- Multiplying an element on the left by 1 leaves it unchanged.
pow_one- Any element raised to the first power equals itself.
Nat.pow_le_pow_iff_right- For a natural base a > 1, a^n ≤ a^m holds if and only if n ≤ m.
mondrian_shape_exponent_interval_bound- If each shape in a subset S of factor shapes has one dimension equal to C * p^(f(d)) where the integer exponent f(d) lies in [lo, hi], then the cardinality of S is at most hi + 1 - lo.
Nat.mul_pos- The product of two positive natural numbers is positive.
pow_pos- Any natural power of a positive number is positive.
Prod.fst- The projection mapping an ordered pair (x, y) to its first component x.
Or.inl- Infers the disjunction a ∨ b from a proof of the left disjunct a.
- The proof relies on `omega` to handle linear integer arithmetic, including establishing that e > 0, verifying that the p-exponent falls in the interval [e - r, e - 1], and simplifying the final cardinality bound (e - 1) + 1 - (e - r) to r.
- The tactic `nlinarith` automatically cancels the positive factor q from inequalities such as q * p^a ≤ q * p^b without manual division steps.
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_middle_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)).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) have he : 0 < e := by omega have hdata : ∀ d ∈ S, d.1 = q * p ^ d.1.factorization p ∧ d.2 = q * p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t ∧ d.1.factorization p ≤ d.2.factorization p ∧ d.2.factorization p ≤ e := by intro d hd obtain ⟨hdS, hdivx, hdivy⟩ := 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) obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 2 d.1 d.2 hp hq hpq hx hy hprod have hb : b ≠ 0 := by intro hh have hnod := mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq apply hnod rw [hxb, hh, pow_zero, one_mul] at hdivx exact hdivx have hc : c ≠ 0 := by intro hh have hnod := mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq apply hnod rw [hyc, hh, pow_zero, one_mul] at hdivy exact hdivy have hb1 : b = 1 := by omega have hc1 : c = 1 := by omega simp only [hb1, hc1, pow_one] at hxb hyc have hab : d.1.factorization p ≤ d.2.factorization p := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp rw [hxb, hyc] at hord nlinarith [hq.pos] have hbe : d.2.factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp rw [hyc] at hn nlinarith [hq.pos] exact ⟨hxb, hyc, hv, hab, hbe⟩ have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q ^ 2 * p ^ t) q (e - r) (e - 1) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t)) (fun _ h => (Finset.mem_filter.mp h).1) Prod.fst (fun d => d.1.factorization p) (by intro d hd; exact ⟨Or.inl rfl, (hdata d hd).1⟩) (by intro d hd obtain ⟨_, _, hv, hab, hbe⟩ := hdata d hd constructor <;> omega) dsimp [S] at hh omega