mondrian_shape_exponent_interval_bound
A 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 minus lo members.
Statement
theorem mondrian_shape_exponent_interval_bound (p n A C lo hi : ℕ) (S : Finset (ℕ × ℕ))
(hA : 0 < A) (hS : S ⊆ mondrian_factor_shapes n A)
(g : (ℕ × ℕ) → ℕ) (f : (ℕ × ℕ) → ℕ)
(hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = C * p ^ f d)
(hf : ∀ d ∈ S, lo ≤ f d ∧ f d ≤ hi) : S.card ≤ hi + 1 - lo- 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_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_sorted_pairs_eq_of_sharedTwo increasing positive factor pairs of the same nonzero area that share a side length are equal.
- Used by 4
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- mondrian_prime_free_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of pure p-power area p^t fit in the q times p^e…
- 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…
- 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…
The proof, explained
The proof shows that the exponent function f maps S into the discrete interval [lo, hi] and is injective on S. Injectivity holds because any two pairs in S with equal exponents have the same value of g, forcing them to share a side length; since both are sorted factor pairs of A > 0, sharing a side length implies the pairs are identical. The bound on the size of S then follows from the pigeonhole principle for injective maps between finite sets, as the interval [lo, hi] has hi + 1 - lo elements.
f maps every element of S into the interval [lo, hi].
For any element d ∈ S, hypothesis hf gives lo ≤ f d ≤ hi. By Finset.mem_Icc.mpr, this double inequality means that f d belongs to the finite interval [lo, hi].
uses
Finset.mem_Icc.mprhave hmap : Set.MapsTo f ↑S ↑(Finset.Icc lo hi) := by intro d hd exact Finset.mem_Icc.mpr (hf d hd)
f is injective on S.
Suppose x, y ∈ S satisfy f x = f y. Since S ⊆ mondrian_factor_shapes n A, lemma mondrian_mem_factor_shapes implies that both x and y are sorted pairs with product A (x.1 * x.2 = A, y.1 * y.2 = A, x.1 ≤ x.2, and y.1 ≤ y.2). From the formula g d = C * p ^ (f d), the equality f x = f y gives g x = g y. Because g x ∈ {x.1, x.2} and g y ∈ {y.1, y.2}, the two pairs share at least one coordinate (x.1 = y.1, x.1 = y.2, x.2 = y.1, or x.2 = y.2). By mondrian_sorted_pairs_eq_of_shared, two sorted pairs with the same strictly positive product A that share a coordinate must be identical, concluding x = y.
uses
mondrian_mem_factor_shapes,mondrian_sorted_pairs_eq_of_sharedhave hinj : Set.InjOn f ↑S := by intro x hx y hy he obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes n A x).mp (hS hx) obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes n A y).mp (hS hy) have hh : g x = g y := by rw [(hg x hx).2, (hg y hy).2, he] apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo rcases (hg x hx).1 with hhx | hhx <;> rcases (hg y hy).1 with hhy | hhy <;> rw [hhx, hhy] at hh <;> tauto
The cardinality of S is at most hi + 1 - lo.
By Finset.card_le_card_of_injOn, the existence of an injection from S into the interval [lo, hi] implies that |S| ≤ |[lo, hi]|. The cardinality of [lo, hi] evaluates to hi + 1 - lo, completing the proof.
uses
Finset.card_le_card_of_injOnsimpa using Finset.card_le_card_of_injOn f hmap hinj
Finset.mem_Icc.mpr- An element lies in the closed interval [a, b] if it is bounded below by a and above by b.
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.
mondrian_sorted_pairs_eq_of_shared- Two sorted pairs of natural numbers with the same strictly positive product A that share at least one coordinate are equal.
Finset.card_le_card_of_injOn- If a map from a finite set s to a finite set t is injective on s, then |s| ≤ |t|.
- The final step uses `simpa` to automatically evaluate the cardinality of the discrete interval [lo, hi] as hi + 1 - lo while applying the injectivity bound.
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_shape_exponent_interval_bound (p n A C lo hi : ℕ) (S : Finset (ℕ × ℕ)) (hA : 0 < A) (hS : S ⊆ mondrian_factor_shapes n A) (g : (ℕ × ℕ) → ℕ) (f : (ℕ × ℕ) → ℕ) (hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = C * p ^ f d) (hf : ∀ d ∈ S, lo ≤ f d ∧ f d ≤ hi) : S.card ≤ hi + 1 - lo := by have hmap : Set.MapsTo f ↑S ↑(Finset.Icc lo hi) := by intro d hd exact Finset.mem_Icc.mpr (hf d hd) have hinj : Set.InjOn f ↑S := by intro x hx y hy he obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes n A x).mp (hS hx) obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes n A y).mp (hS hy) have hh : g x = g y := by rw [(hg x hx).2, (hg y hy).2, he] apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo rcases (hg x hx).1 with hhx | hhx <;> rcases (hg y hy).1 with hhy | hhy <;> rw [hhx, hhy] at hh <;> tauto simpa using Finset.card_le_card_of_injOn f hmap hinj