AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_area_shape_bound

theoremverified

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

Statement

theorem mondrian_prime_area_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 * p ^ t)).card ≤ r + Nat.log p q + 1
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 9
Used by 1

The proof, explained

To bound the number of shapes of area q * p^t fitting into a square of side q * p^e, each shape is partitioned into a side coprime to q and a side divisible by q. Because p ≠ q, exactly one side is a pure prime power p^f, while the other side is q * p^(t - f). The square-fitting condition forces p^f ≤ q * p^e and q * p^(t - f) ≤ q * p^e, which restricts the exponent f to the integer interval [e - r, e + ⌊log_p(q)⌋] using t + r = 2e. An interval cardinality bound on the exponent f then proves there are at most r + ⌊log_p(q)⌋ + 1 such shapes.

  1. Define the set of valid rectangle shapes S, the side g(d) coprime to q, the remaining side o(d), and the p-adic exponent f(d) of g(d).

    We let S be the set of shapes of area q * p^t fitting into a square of side q * p^e. For any shape d, g(d) selects the side coprime to q (taking d.2 if q ∣ d.1 and d.1 otherwise), o(d) selects the side divisible by q, and f(d) is the exponent of p in g(d).

    lines 4–7

      let S := mondrian_factor_shapes (q * p ^ e) (q * p ^ t)
      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
  2. For any shape d ∈ S, its area is d.1 * d.2 = q * p^t, its dimensions satisfy d.1 ≤ d.2 ≤ q * p^e, and both side lengths are strictly positive.

    Unpacking membership d ∈ S using mondrian_mem_factor_shapes gives d.1 * d.2 = q * p^t and d.1 ≤ d.2 ≤ q * p^e. Since p and q are prime, q * p^t is strictly positive (by Nat.mul_pos and pow_pos), so both d.1 and d.2 are strictly positive by Nat.pos_of_mul_pos_right and Nat.pos_of_mul_pos_left.

    lines 8–14

    uses mondrian_mem_factor_shapes, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, Nat.mul_pos, pow_pos

      have hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧
          g d = p ^ f d ∧ o d = q * 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 ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd
        have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t))
        have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t))
  3. At least one of the sides d.1, d.2 is not divisible by q.

    By mondrian_two_prime_factor_pair_encoding, the powers of q in d.1 and d.2 sum to 1, meaning one side has exponent 0 and the other has exponent 1. If d.1 has exponent 0, then d.1 is a power of p (via pow_zero and one_mul); since p ≠ q, q does not divide any power of p by mondrian_distinct_prime_not_dvd_pow, so q ∤ d.1. The symmetric argument holds if d.2 has exponent 0.

    lines 15–25

    uses mondrian_two_prime_factor_pair_encoding, pow_zero, one_mul, mondrian_distinct_prime_not_dvd_pow

        have hfree : ¬ q ∣ d.1 ∨ ¬ q ∣ d.2 := by
          obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 1 d.1 d.2
            hp hq hpq hx hy (by simpa using hprod)
          have hbc' : b = 0 ∨ c = 0 := by omega
          rcases hbc' with hb | hc
          · left
            rw [hxb, hb, pow_zero, one_mul]
            exact mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq
          · right
            rw [hyc, hc, pow_zero, one_mul]
            exact mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq
  4. For every shape d ∈ S, the side g(d) is p^(f d) and o(d) is q * p^(v_p(o d)), with exponents summing to t and both sides bounded by q * p^e.

    We split into cases based on whether q ∣ d.1: if so, q ∤ d.2, and mondrian_prime_free_factor_pair_encoding (with Nat.mul_comm) yields d.2 = p^(v_p(d.2)) and d.1 = q * p^(v_p(d.1)); if not, the same lemma yields d.1 = p^(v_p(d.1)) and d.2 = q * p^(v_p(d.2)). In both cases, g(d) and o(d) match these forms, their exponents sum to t, and both sides satisfy the upper bound q * p^e. The conclusion is assembled using And.intro, Or.inr, and Or.inl.

    lines 26–35

    uses mondrian_prime_free_factor_pair_encoding, Nat.mul_comm, And.intro, Or.inr, Or.inl

        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 1 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 1 d.1 d.2 hp hq hpq hx hy
            (by simpa using 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))))
  5. The exponent f(d) satisfies e - r ≤ f(d) ≤ e + ⌊log_p(q)⌋, which bounds the cardinality |S| by (e + ⌊log_p(q)⌋) + 1 - (e - r).

    We apply mondrian_shape_exponent_interval_bound with area q * p^t > 0 (via Nat.mul_pos and pow_pos), C = 1, and interval bounds lo = e - r and hi = e + Nat.log p q. For any d ∈ S, g(d) = p^(f d) ≤ q * p^e gives f(d) ≤ e + Nat.log p q via mondrian_prime_power_side_log_bound. Meanwhile, o(d) = q * p^(v_p(o d)) ≤ q * p^e implies p^(v_p(o d)) ≤ p^e, so v_p(o d) ≤ e by Nat.pow_le_pow_iff_right. Since f(d) + v_p(o d) = t and t + r = 2e, linear arithmetic (omega) implies f(d) = t - v_p(o d) ≥ (2e - r) - e = e - r.

    lines 36–47

    uses mondrian_shape_exponent_interval_bound, Nat.mul_pos, pow_pos, mondrian_prime_power_side_log_bound, Nat.pow_le_pow_iff_right

      have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q * p ^ t) 1
        (e - r) (e + Nat.log p q) S (Nat.mul_pos hq.pos (pow_pos hp.pos t))
        (fun _ h => h) 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 : (o d).factorization p ≤ e := by
            apply (Nat.pow_le_pow_iff_right hp.one_lt).mp
            have := hon
            rw [hop] at this
            nlinarith [hq.pos]
          constructor <;> omega)
  6. The number of valid factor shapes is at most r + ⌊log_p(q)⌋ + 1.

    Unfolding S via dsimp [S], the bound becomes |mondrian_factor_shapes (q * p^e) (q * p^t)| ≤ e + Nat.log p q + 1 - (e - r). Linear arithmetic (omega) cancels e, simplifying the upper bound directly to r + Nat.log p q + 1.

    lines 48–49

      dsimp [S] at hh
      omega
mondrian_mem_factor_shapes
A pair of dimensions d = (d.1, d.2) belongs to the factor shapes of area A fitting into a square of side n 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 a product of natural numbers a * b is strictly positive, then a is strictly positive.
Nat.pos_of_mul_pos_left
If a product of natural numbers a * b is strictly positive, then b is strictly positive.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
pow_pos
Any natural power of a strictly positive number is strictly positive.
mondrian_two_prime_factor_pair_encoding
If positive integers x and y satisfy x * y = q^s * p^t for distinct primes p and q, then the exponents of q in x and y sum to s, their p-adic valuations sum to t, and both numbers are products of powers of q and p.
pow_zero
Any number raised to the power 0 is 1.
one_mul
Multiplying any number by 1 leaves it unchanged.
mondrian_distinct_prime_not_dvd_pow
A prime q cannot divide any power of a distinct prime p.
mondrian_prime_free_factor_pair_encoding
If positive integers x and y satisfy x * y = q^s * p^t for distinct primes p and q, and q does not divide x, then x is a pure power of p and y contains the full factor of q^s.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
And.intro
Given proofs of propositions A and B, construct a proof of A ∧ B.
Or.inr
Given a proof of proposition B, construct a proof of the disjunction A ∨ B.
Or.inl
Given a proof of proposition A, construct a proof of the disjunction A ∨ B.
mondrian_shape_exponent_interval_bound
If each rectangle shape in a subset S has a side of the form C * p^(f d) with f(d) in the integer interval [lo, hi], then the cardinality of S is at most hi + 1 - lo.
mondrian_prime_power_side_log_bound
If p is prime and p^a ≤ q * p^e, then a ≤ e + ⌊log_p(q)⌋.
Nat.pow_le_pow_iff_right
For a base a > 1, a^n ≤ a^m if and only if n ≤ m.

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_prime_area_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 * p ^ t)).card ≤ r + Nat.log p q + 1 := by  let S := mondrian_factor_shapes (q * p ^ e) (q * p ^ t)  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 * 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 ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd    have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t))    have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t))    have hfree : ¬ q ∣ d.1 ∨ ¬ q ∣ d.2 := by      obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 1 d.1 d.2        hp hq hpq hx hy (by simpa using hprod)      have hbc' : b = 0 ∨ c = 0 := by omega      rcases hbc' with hb | hc      · left        rw [hxb, hb, pow_zero, one_mul]        exact mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq      · right        rw [hyc, hc, pow_zero, one_mul]        exact mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq    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 1 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 1 d.1 d.2 hp hq hpq hx hy        (by simpa using 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 * p ^ t) 1    (e - r) (e + Nat.log p q) S (Nat.mul_pos hq.pos (pow_pos hp.pos t))    (fun _ h => h) 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 : (o d).factorization p ≤ e := by        apply (Nat.pow_le_pow_iff_right hp.one_lt).mp        have := hon        rw [hop] at this        nlinarith [hq.pos]      constructor <;> omega)  dsimp [S] at hh  omega
See it in the graphDiscuss this resultChallenge it