AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_free_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 pure p-power area p^t fit in the q times p^e square.

Statement

theorem mondrian_prime_free_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) (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 7
Used by 1

The proof, explained

The proof bounds the number of valid rectangle shapes of pure prime-power area p^t that fit inside a q * p^e square. Because each rectangle has area p^t, unique factorization implies both side lengths must be pure powers of p whose exponents sum to t. The conditions that the shorter side is at most the longer side, and the longer side fits within the square (at most q * p^e), constrain the exponent of the shorter side to an integer interval of length at most r + ⌊log_p(q)⌋, using the relation t + r = 2e. Applying an interval bound on prime-power side exponents (mondrian_shape_exponent_interval_bound) then limits the total number of shapes to at most r + ⌊log_p(q)⌋ + 1.

  1. Every valid rectangle of area p^t has side lengths that are pure powers of p whose exponents sum to t.

    We introduce S as the set of valid shapes mondrian_factor_shapes (q * p^e) (p^t), meaning pairs (d.1, d.2) with d.1 * d.2 = p^t, d.1 ≤ d.2, and d.2 ≤ q * p^e. Since p^t > 0, both sides are positive (via Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, and pow_pos). As each side divides the prime power p^t, mondrian_dvd_prime_pow_eq implies d.1 = p^(v_p(d.1)) and d.2 = p^(v_p(d.2)). Applying congrArg with the valuation function v_p and simplifying with Nat.factorization_mul and Nat.factorization_pow_self shows the exponents sum to t: v_p(d.1) + v_p(d.2) = t.

    lines 4–17

    uses mondrian_mem_factor_shapes, Nat.pos_of_mul_pos_right, pow_pos, Nat.pos_of_mul_pos_left, mondrian_dvd_prime_pow_eq, congrArg, Nat.factorization_mul, Nat.factorization_pow_self

      let S := mondrian_factor_shapes (q * p ^ e) (p ^ t)
      have hpow : ∀ d ∈ S, d.1 = p ^ d.1.factorization p ∧
          d.2 = p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t := 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 pow_pos hp.pos t)
        have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact pow_pos hp.pos t)
        have hxpow := mondrian_dvd_prime_pow_eq p t d.1 hp ⟨d.2, hprod.symm⟩
        have hypow := mondrian_dvd_prime_pow_eq p t d.2 hp ⟨d.1, by nlinarith [hprod]⟩
        have hh := congrArg (fun z : ℕ => z.factorization p) hprod
        have hv : d.1.factorization p + d.2.factorization p = t := by
          simpa [Nat.factorization_mul (by omega : d.1 ≠ 0) (by omega : d.2 ≠ 0),
            Nat.factorization_pow_self hp, hp.factorization_self] using hh
        exact ⟨hxpow, hypow, hv⟩
  2. The number of shapes in S is bounded above by (e + 1) - (e - r - ⌊log_p(q)⌋).

    We apply mondrian_shape_exponent_interval_bound with the shorter side d.1 = 1 * p^(v_p(d.1)) and exponent function v_p(d.1) over the interval [e - r - Nat.log p q, e]. For any shape d ∈ S, the upper bound d.2 ≤ q * p^e gives v_p(d.2) ≤ e + Nat.log p q by mondrian_prime_power_side_log_bound. The ordering d.1 ≤ d.2 gives v_p(d.1) ≤ v_p(d.2) by Nat.pow_le_pow_iff_right. Since v_p(d.1) + v_p(d.2) = t and t + r = 2e, linear arithmetic (omega) verifies both v_p(d.1) ≤ e (from 2 * v_p(d.1) ≤ t ≤ 2e) and v_p(d.1) = t - v_p(d.2) ≥ 2e - r - (e + Nat.log p q) = e - r - Nat.log p q.

    lines 18–30

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

      have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (p ^ t) 1
        (e - r - Nat.log p q) e S (pow_pos hp.pos t) (fun _ h => h)
        Prod.fst (fun d => d.1.factorization p) (by
          intro d hd
          exact ⟨Or.inl rfl, by simpa using (hpow d hd).1⟩) (by
          intro d hd
          obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd
          obtain ⟨hxpow, hypow, hv⟩ := hpow d hd
          have hb : d.2.factorization p ≤ e + Nat.log p q :=
            mondrian_prime_power_side_log_bound p q e _ hp (by simpa [← hypow] using hn)
          have hab : d.1.factorization p ≤ d.2.factorization p :=
            (Nat.pow_le_pow_iff_right hp.one_lt).mp (by simpa [← hxpow, ← hypow] using hord)
          constructor <;> omega)
  3. Simplifying the arithmetic bound completes the proof.

    Unfolding the definition of S in the bound, linear integer arithmetic (omega) simplifies (e + 1) - (e - r - Nat.log p q) to at most r + Nat.log p q + 1, closing the goal.

    lines 31–32

      dsimp [S] at hh
      omega
mondrian_mem_factor_shapes
A pair d = (d.1, d.2) 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 a product a * b is positive, then a is positive.
pow_pos
A positive number raised to any power is positive.
Nat.pos_of_mul_pos_left
If a product a * b is positive, then b is positive.
mondrian_dvd_prime_pow_eq
Any divisor x of a prime power p^e has the form p^(v_p(x)).
congrArg
Equality is preserved under applying a function: if a = b, then f(a) = f(b).
Nat.factorization_mul
The prime factorization of a product of positive integers is the sum of their individual factorizations: v_p(a * b) = v_p(a) + v_p(b).
Nat.factorization_pow_self
For a prime p, the p-adic valuation of p^n is n: v_p(p^n) = n.
mondrian_shape_exponent_interval_bound
If a subset S of valid factor shapes has one side of the form C * p^(f d) with exponent f(d) confined to [lo, hi], then |S| ≤ hi + 1 - lo.
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)⌋.
Nat.pow_le_pow_iff_right
For 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_free_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) (p ^ t)).card ≤ r + Nat.log p q + 1 := by  let S := mondrian_factor_shapes (q * p ^ e) (p ^ t)  have hpow : ∀ d ∈ S, d.1 = p ^ d.1.factorization p ∧      d.2 = p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t := 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 pow_pos hp.pos t)    have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact pow_pos hp.pos t)    have hxpow := mondrian_dvd_prime_pow_eq p t d.1 hp ⟨d.2, hprod.symm⟩    have hypow := mondrian_dvd_prime_pow_eq p t d.2 hp ⟨d.1, by nlinarith [hprod]⟩    have hh := congrArg (fun z : ℕ => z.factorization p) hprod    have hv : d.1.factorization p + d.2.factorization p = t := by      simpa [Nat.factorization_mul (by omega : d.1 ≠ 0) (by omega : d.2 ≠ 0),        Nat.factorization_pow_self hp, hp.factorization_self] using hh    exact ⟨hxpow, hypow, hv⟩  have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (p ^ t) 1    (e - r - Nat.log p q) e S (pow_pos hp.pos t) (fun _ h => h)    Prod.fst (fun d => d.1.factorization p) (by      intro d hd      exact ⟨Or.inl rfl, by simpa using (hpow d hd).1⟩) (by      intro d hd      obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd      obtain ⟨hxpow, hypow, hv⟩ := hpow d hd      have hb : d.2.factorization p ≤ e + Nat.log p q :=        mondrian_prime_power_side_log_bound p q e _ hp (by simpa [← hypow] using hn)      have hab : d.1.factorization p ≤ d.2.factorization p :=        (Nat.pow_le_pow_iff_right hp.one_lt).mp (by simpa [← hxpow, ← hypow] using hord)      constructor <;> omega)  dsimp [S] at hh  omega
See it in the graphDiscuss this resultChallenge it