AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_shape_bound

theoremverified

If k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the square.

Statement

theorem mondrian_prime_shape_bound (c p e k A : ℕ) (hc : 0 < c)
    (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)
    (heq : k * A = (c * p ^ e) ^ 2) :
    (mondrian_factor_shapes (c * p ^ e) A).card ≤ (k.factorization p + 1) * c
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1
  • mondrian_large_prime_count_not_dvdIf enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot…

The proof, explained

To bound the number of unordered rectangle shapes of area A that fit in a (c * p^e) × (c * p^e) square, the proof first bounds unordered shapes by half of the ordered factor pairs. The number of ordered factor pairs is then controlled by (v_p(k) + 1) times the number of divisors of the p-free cofactor A / p^(v_p(A)). Since c < p, this cofactor is at most c^2 and thus has at most 2c divisors, from which integer arithmetic yields the upper bound (v_p(k) + 1) * c.

  1. Twice the number of valid unordered shapes is at most one more than the number of valid ordered factor pairs.

    By `mondrian_ordered_shape_half`, each unordered shape {d₁, d₂} of area A corresponds to two ordered pairs (d₁, d₂) and (d₂, d₁) unless d₁ = d₂ (a square, which occurs at most once), so 2 * |S| ≤ |S_ord| + 1.

    line 5

    uses mondrian_ordered_shape_half

      have h1 := mondrian_ordered_shape_half (c * p ^ e) A
  2. The number of ordered factor pairs fitting in the square is at most (v_p(k) + 1) times the number of divisors of the cofactor A / p^(v_p(A)).

    By `mondrian_ordered_prime_shape_bound`, the prime power factorization structure limits the valid ordered factor pairs to at most (v_p(k) + 1) * d(A / p^(v_p(A))), where d(·) counts divisors.

    line 6

    uses mondrian_ordered_prime_shape_bound

      have h2 := mondrian_ordered_prime_shape_bound c p e k A hc hp hpc hk hA heq
  3. The cofactor A / p^(v_p(A)) is at most c^2, and consequently has at most 2c divisors.

    By `mondrian_prime_cofactor_le`, removing the full p-part from A leaves a cofactor bounded by c^2 because c < p. Then `mondrian_divisors_card_le_two_mul_of_le_sq` bounds the number of divisors of any integer up to c^2 by 2c.

    lines 7–8

    uses mondrian_prime_cofactor_le, mondrian_divisors_card_le_two_mul_of_le_sq

      have h3 := mondrian_prime_cofactor_le c p e k A hc hp hpc heq
      have h4 := mondrian_divisors_card_le_two_mul_of_le_sq (A / p ^ (A.factorization p)) c h3
  4. The number of unordered shapes of area A fitting in the square is at most (v_p(k) + 1) * c.

    Multiplying the divisor bound by v_p(k) + 1 via `Nat.mul_le_mul_left` gives |S_ord| ≤ 2c * (v_p(k) + 1). Combining this with 2 * |S| ≤ |S_ord| + 1 gives 2 * |S| ≤ 2c * (v_p(k) + 1) + 1; nonlinear integer arithmetic (`nlinarith`) closes the goal by dividing by 2.

    lines 9–10

    uses Nat.mul_le_mul_left

      have h5 := Nat.mul_le_mul_left (k.factorization p + 1) h4
      nlinarith
mondrian_ordered_shape_half
Twice the number of unordered factor shapes of area A fitting in an n × n square is at most one more than the number of valid ordered factor pairs.
mondrian_ordered_prime_shape_bound
If k * A = (c * p^e)^2 with p prime and c < p, the number of ordered factor pairs of area A fitting in the (c * p^e) × (c * p^e) square is at most (v_p(k) + 1) times the number of divisors of the p-free cofactor A / p^(v_p(A)).
mondrian_prime_cofactor_le
If k * A = (c * p^e)^2 with p prime and c < p, the p-free cofactor A / p^(v_p(A)) is at most c^2.
mondrian_divisors_card_le_two_mul_of_le_sq
Any natural number D bounded by c^2 has at most 2c divisors.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers n ≤ m on the left by k preserves the inequality: k * n ≤ k * 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_shape_bound (c p e k A : ℕ) (hc : 0 < c)    (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)    (heq : k * A = (c * p ^ e) ^ 2) :    (mondrian_factor_shapes (c * p ^ e) A).card ≤ (k.factorization p + 1) * c := by  have h1 := mondrian_ordered_shape_half (c * p ^ e) A  have h2 := mondrian_ordered_prime_shape_bound c p e k A hc hp hpc hk hA heq  have h3 := mondrian_prime_cofactor_le c p e k A hc hp hpc heq  have h4 := mondrian_divisors_card_le_two_mul_of_le_sq (A / p ^ (A.factorization p)) c h3  have h5 := Nat.mul_le_mul_left (k.factorization p + 1) h4  nlinarith
See it in the graphDiscuss this resultChallenge it