AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_square_area_middle_shape_bound

theoremverified

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
Used by 1

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.

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

    lines 5–9

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

    lines 10–35

    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_one

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

    lines 36–44

    uses Nat.pow_le_pow_iff_right

        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⟩
  4. 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).

    lines 45–51

    uses mondrian_shape_exponent_interval_bound, Nat.mul_pos, pow_pos, Finset.mem_filter.mp, Prod.fst, Or.inl

      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)
  5. 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.

    lines 52–53

      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.

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