AFTD Auto-Formalizing Theoretical Domains

mondrian_ordered_prime_shape_bound

theoremverified

The number of ordered shapes of area A fitting in a c times p to the e square is at most the p-adic exponent of k plus one, times the number of divisors of the p-free part of A, when k times A is the square area and p exceeds c.

Statement

theorem mondrian_ordered_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) :
    (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)).card ≤
      (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card
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 1
  • mondrian_prime_pair_encodingFor an equal-area factor pair fitting in a c times p to the e square with p greater than c, the p-adic exponent of its first side lies…
Used by 1
  • mondrian_prime_shape_boundIf 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…

The proof, explained

The proof bounds the number of ordered shapes fitting in the square by defining an injection f(d₁, d₂) = (v_p(d₁), d₁ / p^(v_p(d₁))) from the set of valid divisor pairs into [e - v_p(k), e] × divisors(A / p^(v_p(A))). The image constraints follow from a previous lemma (mondrian_prime_pair_encoding), and injectivity holds because the prime power and p-free part reconstruct d₁, which in turn uniquely determines d₂ = A / d₁. The desired bound then follows directly by computing the cardinality of this Cartesian product.

  1. The encoding function f(d₁, d₂) = (v_p(d₁), d₁ / p^(v_p(d₁))) maps every valid shape in S into the product set [e - v_p(k), e] × divisors(A / p^(v_p(A))).

    Let S be the set of divisor pairs (d₁, d₂) of A fitting in a c * p^e square, so d₁ * d₂ = A with d₁, d₂ ≤ c * p^e. Since A > 0, both d₁ and d₂ are strictly positive. Applying the lemma mondrian_prime_pair_encoding, the p-adic valuation v_p(d₁) is bounded between e - v_p(k) and e, while the p-free part d₁ / p^(v_p(d₁)) divides the p-free part A / p^(v_p(A)). Thus f maps S into the Cartesian product of the integer interval [e - v_p(k), e] and the divisors of A / p^(v_p(A)).

    lines 6–17

    uses Finset.mem_filter.mp, Nat.mem_divisorsAntidiagonal.mp, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, mondrian_prime_pair_encoding, Finset.mem_product.mpr, Finset.mem_Icc.mpr

      let f := fun d : ℕ × ℕ => (d.1.factorization p, d.1 / p ^ (d.1.factorization p))
      let S := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)
      have hmap : Set.MapsTo f ↑S
          ↑(Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors) := by
        intro d hd
        obtain ⟨hdA, hxn, hyn⟩ := Finset.mem_filter.mp hd
        have hprod := (Nat.mem_divisorsAntidiagonal.mp hdA).1
        have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2)
        have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2)
        obtain ⟨hlo, hup, hmem⟩ := mondrian_prime_pair_encoding c p e k A d.1 d.2
          hc hp hpc hk hA heq hx hy hxn hyn hprod
        exact Finset.mem_product.mpr ⟨Finset.mem_Icc.mpr ⟨hlo, hup⟩, hmem⟩
  2. The encoding function f is injective on S.

    Suppose f(x) = f(y) for shapes x, y ∈ S. Reconstructing each first coordinate from its p-adic valuation and p-free part via Nat.ordProj_mul_ordCompl_eq_self shows x₁ = y₁. Since both pairs satisfy x₁ * x₂ = A and y₁ * y₂ = A with x₁ > 0, cancelling x₁ from x₁ * x₂ = x₁ * y₂ yields x₂ = y₂. By Prod.ext, x = y, so f is injective on S.

    lines 18–28

    uses congrArg, Nat.ordProj_mul_ordCompl_eq_self, Nat.mem_divisorsAntidiagonal.mp, Finset.mem_filter.mp, Nat.pos_of_mul_pos_right, Prod.ext, Nat.eq_of_mul_eq_mul_left

      have hinj : Set.InjOn f ↑S := by
        intro x hx y hy he
        have hw := congrArg (fun z : ℕ × ℕ => p ^ z.1 * z.2) he
        dsimp [f] at hw
        simp only [Nat.ordProj_mul_ordCompl_eq_self] at hw
        have hxp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hx).1).1
        have hyp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hy).1).1
        have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2)
        apply Prod.ext hw
        apply Nat.eq_of_mul_eq_mul_left hxpos
        rw [hxp, hw, hyp]
  3. The cardinality of S is bounded by (v_p(k) + 1) * |divisors(A / p^(v_p(A)))|.

    By Finset.card_le_card_of_injOn, the injectivity of f implies that |S| is at most the cardinality of the codomain product. The size of this Cartesian product is the length of the interval, (e + 1) - (e - v_p(k)), times the number of divisors of the p-free part of A. Because (e + 1) - (e - v_p(k)) ≤ v_p(k) + 1 by linear arithmetic, multiplying by the divisor count preserves the inequality, concluding the proof.

    lines 29–36

    uses Finset.card_le_card_of_injOn, Nat.mul_le_mul_right

      have hcard := Finset.card_le_card_of_injOn f hmap hinj
      calc
        S.card ≤ (Finset.Icc (e - k.factorization p) e ×ˢ
            (A / p ^ (A.factorization p)).divisors).card := hcard
        _ = (e + 1 - (e - k.factorization p)) *
            (A / p ^ (A.factorization p)).divisors.card := by simp
        _ ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card :=
          Nat.mul_le_mul_right _ (by omega)
Finset.mem_filter.mp
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filter predicate.
Nat.mem_divisorsAntidiagonal.mp
If a pair of numbers belongs to the antidiagonal of divisors of n, their product equals n.
Nat.pos_of_mul_pos_right
If the product of two natural numbers is positive, then the first factor is positive.
Nat.pos_of_mul_pos_left
If the product of two natural numbers is positive, then the second factor is positive.
mondrian_prime_pair_encoding
For rectangle dimensions x and y at most c * p^e with x * y = A and k * A = (c * p^e)^2 where c < p, the p-adic valuation of x is bounded between e - v_p(k) and e, and the p-free part of x divides the p-free part of A.
Finset.mem_product.mpr
A pair belongs to the Cartesian product of two finite sets if its first component is in the first set and its second component is in the second set.
Finset.mem_Icc.mpr
A number belongs to the closed interval [a, b] if it is greater than or equal to a and less than or equal to b.
congrArg
Applying a function to equal inputs yields equal outputs.
Nat.ordProj_mul_ordCompl_eq_self
Multiplying the prime power p^(v_p(n)) by the p-free part n / p^(v_p(n)) reconstructs n.
Prod.ext
Two pairs are equal if their first components are equal and their second components are equal.
Nat.eq_of_mul_eq_mul_left
A positive common factor on the left of an equality of natural numbers can be cancelled.
Finset.card_le_card_of_injOn
If a function maps a finite set injectively into another finite set, the cardinality of the domain is at most the cardinality of the codomain.
Nat.mul_le_mul_right
Multiplying both sides of an inequality of natural numbers by a number on the right preserves the inequality.

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_ordered_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) :    (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)).card ≤      (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card := by  let f := fun d : ℕ × ℕ => (d.1.factorization p, d.1 / p ^ (d.1.factorization p))  let S := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)  have hmap : Set.MapsTo f ↑S      ↑(Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors) := by    intro d hd    obtain ⟨hdA, hxn, hyn⟩ := Finset.mem_filter.mp hd    have hprod := (Nat.mem_divisorsAntidiagonal.mp hdA).1    have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2)    have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2)    obtain ⟨hlo, hup, hmem⟩ := mondrian_prime_pair_encoding c p e k A d.1 d.2      hc hp hpc hk hA heq hx hy hxn hyn hprod    exact Finset.mem_product.mpr ⟨Finset.mem_Icc.mpr ⟨hlo, hup⟩, hmem⟩  have hinj : Set.InjOn f ↑S := by    intro x hx y hy he    have hw := congrArg (fun z : ℕ × ℕ => p ^ z.1 * z.2) he    dsimp [f] at hw    simp only [Nat.ordProj_mul_ordCompl_eq_self] at hw    have hxp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hx).1).1    have hyp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hy).1).1    have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2)    apply Prod.ext hw    apply Nat.eq_of_mul_eq_mul_left hxpos    rw [hxp, hw, hyp]  have hcard := Finset.card_le_card_of_injOn f hmap hinj  calc    S.card ≤ (Finset.Icc (e - k.factorization p) e ×ˢ        (A / p ^ (A.factorization p)).divisors).card := hcard    _ = (e + 1 - (e - k.factorization p)) *        (A / p ^ (A.factorization p)).divisors.card := by simp    _ ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card :=      Nat.mul_le_mul_right _ (by omega)
See it in the graphDiscuss this resultChallenge it