AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_square_area_free_shape_bound

theoremverified

For 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 indivisible by q.

Statement

theorem mondrian_prime_square_area_free_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 ^ 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 6
Used by 2

The proof, explained

Any shape of area q^2 * p^t fitting in a q * p^e square with at least one side indivisible by q must have that side entirely free of q (a pure power of p), while the other side carries the full factor q^2. The bounding box restricts both side lengths, confining the p-exponent of the q-free side to an explicit integer interval of length at most r, using the relation t + r = 2e. Since shapes are uniquely determined by this exponent, the interval bound lemma shows that at most r such shapes can exist.

  1. Define the set of relevant shapes S and helper functions for each shape's sides and p-exponent.

    Note that the primes p and q are positive. Define S as the set of shapes of area q^2 * p^t fitting into a q * p^e square where at least one side is not divisible by q. For any shape d, define g(d) to select the side not divisible by q (d₂ if q ∣ d₁, and d₁ otherwise), o(d) to select the other side, and f(d) as the exponent of p in the prime factorization of g(d).

    lines 5–11

      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)
      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 each shape d ∈ S, g(d) is a pure power p^(f(d)), o(d) is q^2 * p^(v_p(o(d))), their p-exponents sum to t, and both sides are at most q * p^e.

    Unpack membership in S: the side lengths satisfy d₁ * d₂ = q^2 * p^t, d₁ ≤ d₂ ≤ q * p^e, and both sides are strictly positive. Since at least one side is not divisible by q, split into cases on whether q ∣ d₁. If q ∣ d₁, then q ∤ d₂, and `mondrian_prime_free_factor_pair_encoding` gives d₂ = p^(v_p(d₂)) and d₁ = q^2 * p^(v_p(d₁)) with exponents summing to t; here g(d) = d₂ and o(d) = d₁. If q ∤ d₁, the same lemma applies directly to (d₁, d₂), giving g(d) = d₁ = p^(v_p(d₁)) and o(d) = d₂ = q^2 * p^(v_p(d₂)). In both cases, both side lengths are bounded above by d₂ ≤ q * p^e.

    lines 12–28

    uses Finset.mem_filter.mp, mondrian_mem_factor_shapes, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, Nat.mul_comm, mondrian_prime_free_factor_pair_encoding

      have hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧
          g d = p ^ f d ∧ o d = q ^ 2 * 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 ⟨hdS, hfree⟩ := 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)
        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 2 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 2 d.1 d.2 hp hq hpq hx hy 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))))
  3. The number of shapes in S is bounded by the width of the interval for the exponent f(d), namely (e + ⌊log_p q⌋ + 1) - (e + ⌊log_p q⌋ + 1 - r).

    Apply `mondrian_shape_exponent_interval_bound` with C = 1, lower bound lo = e + ⌊log_p q⌋ + 1 - r, and upper bound hi = e + ⌊log_p q⌋. For any d ∈ S, g(d) = p^(f(d)) ≤ q * p^e implies f(d) ≤ e + ⌊log_p q⌋ by `mondrian_prime_power_side_log_bound`. The cofactor side o(d) = q^2 * p^(v_p(o(d))) ≤ q * p^e implies v_p(o(d)) + ⌊log_p q⌋ + 1 ≤ e by `mondrian_prime_square_cofactor_side_bound`. Since f(d) + v_p(o(d)) = t and t + r = 2e, linear arithmetic (`omega`) deduces that f(d) ≥ e + ⌊log_p q⌋ + 1 - r.

    lines 29–38

    uses mondrian_shape_exponent_interval_bound, Nat.mul_pos, pow_pos, Finset.mem_filter.mp, mondrian_prime_power_side_log_bound, mondrian_prime_square_cofactor_side_bound

      have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q ^ 2 * p ^ t) 1
        (e + Nat.log p q + 1 - r) (e + Nat.log p q) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t))
        (fun _ h => (Finset.mem_filter.mp h).1) 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 := mondrian_prime_square_cofactor_side_bound p q e ((o d).factorization p)
            hp hq hpq (by rwa [← hop])
          constructor <;> omega)
  4. The number of shapes in S is at most r. automation

    Unfolding the definition of S in the interval bound, linear integer arithmetic (`omega`) simplifies (e + ⌊log_p q⌋ + 1) - (e + ⌊log_p q⌋ + 1 - r) to at most r.

    lines 39–40

      dsimp [S] at hh
      omega
Finset.mem_filter.mp
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Nat.mul_comm
Multiplication on natural numbers is commutative: n * m = m * n.
Nat.pos_of_mul_pos_left
If a product of natural numbers is strictly positive, its second factor is strictly positive.
Nat.pos_of_mul_pos_right
If a product of natural numbers is strictly positive, its first factor is strictly positive.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
mondrian_mem_factor_shapes
A pair (d₁, d₂) is a factor shape of area A fitting in an n × n square if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
mondrian_prime_free_factor_pair_encoding
If two positive integers x and y have product q^s * p^t for distinct primes p and q, and q does not divide x, then x is a pure power of p, y is q^s times a power of p, and their p-adic exponents sum to t.
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⌋.
mondrian_prime_square_cofactor_side_bound
For distinct primes p and q, if q^2 * p^a ≤ q * p^e, then a + ⌊log_p q⌋ + 1 ≤ e.
mondrian_shape_exponent_interval_bound
If every shape in a set S has a side equal to C * p^(f(d)) with f(d) restricted to [lo, hi], then the number of shapes in S is at most hi + 1 - lo.
pow_pos
A positive base raised to any natural power is strictly positive.

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_free_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 ^ 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)  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 ^ 2 * 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 ⟨hdS, hfree⟩ := 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)    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 2 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 2 d.1 d.2 hp hq hpq hx hy 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 ^ 2 * p ^ t) 1    (e + Nat.log p q + 1 - r) (e + Nat.log p q) S (Nat.mul_pos (pow_pos hq.pos 2) (pow_pos hp.pos t))    (fun _ h => (Finset.mem_filter.mp h).1) 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 := mondrian_prime_square_cofactor_side_bound p q e ((o d).factorization p)        hp hq hpq (by rwa [← hop])      constructor <;> omega)  dsimp [S] at hh  omega
See it in the graphDiscuss this resultChallenge it