AFTD Auto-Formalizing Theoretical Domains

mondrian_shape_exponent_interval_bound

theoremverified

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

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.

  1. 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].

    lines 6–8

    uses Finset.mem_Icc.mpr

      have hmap : Set.MapsTo f ↑S ↑(Finset.Icc lo hi) := by
        intro d hd
        exact Finset.mem_Icc.mpr (hf d hd)
  2. 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.

    lines 9–16

    uses mondrian_mem_factor_shapes, mondrian_sorted_pairs_eq_of_shared

      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
  3. 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.

    line 17

    uses Finset.card_le_card_of_injOn

      simpa 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|.

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_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
See it in the graphDiscuss this resultChallenge it