AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_first_exponent_shape_bound

theoremverified

When the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A and p exceeding c.

Statement

theorem mondrian_prime_first_exponent_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) (hr : k.factorization p = 1) :
    (mondrian_factor_shapes (c * p ^ e) A).card ≤ 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 6
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

The proof establishes an upper bound of c on the number of valid Mondrian shapes of area A fitting in a c * p^e square by constructing an injection f from the set of shapes into the integer interval {1, ..., c}. Taking the p-adic valuation of k * A = (c * p^e)^2 shows that v_p(A) = 2e - 1. Because c < p and each coordinate of an admissible shape d = (d₁, d₂) is at most c * p^e, each coordinate's p-adic valuation is at most e, which forces exactly one coordinate to have valuation e. Dividing this unique coordinate by p^e yields an integer in {1, ..., c}, and this assignment is injective because an ordered factor pair of A is completely determined by any one of its components.

  1. p does not divide c, and the p-adic valuation of A satisfies 1 + v_p(A) = 2e.

    Since 0 < c < p, p cannot divide c, which implies that the p-adic exponent of c is zero. Taking the prime factorization at p of both sides of k * A = (c * p^e)^2 and expanding using v_p(k) = 1, v_p(c) = 0, and v_p(p^e) = e yields 1 + v_p(A) = 2(0 + e) = 2e.

    lines 5–13

    uses Nat.not_dvd_of_pos_of_lt, congrArg, Nat.factorization_mul, Nat.ne_of_gt, Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, pow_ne_zero, Nat.factorization_eq_zero_of_not_dvd, Nat.factorization_pow_self

      have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc
      have hvals : 1 + A.factorization p = 2 * e := by
        have hf := congrArg (fun z : ℕ => z.factorization p) heq
        rw [Nat.factorization_mul (Nat.ne_of_gt hk) (Nat.ne_of_gt hA), Finsupp.add_apply,
          Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul,
          Nat.factorization_mul (Nat.ne_of_gt hc) (pow_ne_zero e hp.ne_zero), Finsupp.add_apply,
          Nat.factorization_eq_zero_of_not_dvd hcnot,
          Nat.factorization_pow_self hp, hr] at hf
        simpa using hf
  2. Define the coordinate selection high and the reduction map f.

    For any factor pair d = (d₁, d₂), define high(d) to be d₁ if v_p(d₁) = e and d₂ otherwise. Then define f(d) = high(d) / p^e, which divides out the p^e factor from that coordinate.

    lines 14–15

      let high := fun d : ℕ × ℕ => if d.1.factorization p = e then d.1 else d.2
      let f := fun d : ℕ × ℕ => high d / p ^ e
  3. For every shape d, high(d) satisfies 0 < high(d) ≤ c * p^e and has p-adic valuation e.

    Any valid shape d satisfies d₁ * d₂ = A with 0 < d₁ ≤ d₂ ≤ c * p^e. Since c < p, the helper lemma mondrian_factorization_le_scaled_prime_pow guarantees that both v_p(d₁) ≤ e and v_p(d₂) ≤ e. Because v_p(d₁) + v_p(d₂) = v_p(A) = 2e - 1, the two integer valuations sum to 2e - 1 and neither exceeds e, which forces exactly one of them to equal e (and the other e - 1). Therefore, high(d) picks the coordinate with valuation e, which is positive and bounded above by c * p^e.

    lines 16–31

    uses mondrian_mem_factor_shapes, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, mondrian_factorization_le_scaled_prime_pow, congrArg, Nat.factorization_mul, Nat.ne_of_gt, Finsupp.add_apply, if_pos, And.intro, if_neg

      have hhigh : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A,
          0 < high d ∧ high d ≤ c * p ^ e ∧ (high d).factorization p = e := by
        intro d hd
        obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A d).mp hd
        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)
        have hxval := mondrian_factorization_le_scaled_prime_pow c p e d.1 hp hpc hx (hord.trans hn)
        have hyval := mondrian_factorization_le_scaled_prime_pow c p e d.2 hp hpc hy hn
        have hxyval : d.1.factorization p + d.2.factorization p = A.factorization p := by
          have hh := congrArg (fun z : ℕ => z.factorization p) hprod
          simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy),
            Finsupp.add_apply] using hh
        by_cases hh : d.1.factorization p = e
        · simpa only [high, if_pos hh] using And.intro hx (And.intro (hord.trans hn) hh)
        · have hyval' : d.2.factorization p = e := by omega
          simpa only [high, if_neg hh] using And.intro hy (And.intro hn hyval')
  4. For every shape d, high(d) = p^e * f(d).

    Because high(d) has p-adic exponent e, factoring high(d) into its prime-p part and prime-to-p part via Nat.ordProj_mul_ordCompl_eq_self yields high(d) = p^e * (high(d) / p^e) = p^e * f(d).

    lines 32–37

    uses Nat.ordProj_mul_ordCompl_eq_self

      have hrec : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A,
          high d = p ^ e * f d := by
        intro d hd
        have hf := Nat.ordProj_mul_ordCompl_eq_self (high d) p
        rw [(hhigh d hd).2.2] at hf
        exact hf.symm
  5. The function f maps shapes into the discrete interval {1, ..., c}. automation

    We verify 1 ≤ f(d) ≤ c. If f(d) < 1, then f(d) = 0, which would imply high(d) = p^e * 0 = 0, contradicting high(d) > 0. If f(d) > c, then f(d) ≥ c + 1, so high(d) = p^e * f(d) ≥ p^e * (c + 1) > c * p^e, contradicting high(d) ≤ c * p^e. Both contradictions are discharged using linear and nonlinear arithmetic solvers (omega and nlinarith).

    lines 38–51

    uses pow_pos, Finset.mem_Icc.mpr, Nat.mul_zero, Nat.mul_le_mul_left

      have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (c * p ^ e) A) ↑(Finset.Icc 1 c) := by
        intro d hd
        have hrec' := hrec d hd
        obtain ⟨hpos, hn, hv⟩ := hhigh d hd
        have hppos := pow_pos hp.pos e
        apply Finset.mem_Icc.mpr
        constructor
        · by_contra hn
          have hf0 : f d = 0 := by omega
          rw [hf0, Nat.mul_zero] at hrec'
          omega
        · by_contra hn
          have hm := Nat.mul_le_mul_left (p ^ e) (by omega : c + 1 ≤ f d)
          nlinarith
  6. The map f is injective on the set of shapes. automation

    If f(x) = f(y), then high(x) = p^e * f(x) = p^e * f(y) = high(y). This equality means that x and y share at least one coordinate (x₁ = y₁, x₁ = y₂, x₂ = y₁, or x₂ = y₂). Since x and y are both ordered pairs of factors of A, sharing any coordinate implies x = y by mondrian_sorted_pairs_eq_of_shared.

    lines 52–59

    uses mondrian_mem_factor_shapes, mondrian_sorted_pairs_eq_of_shared

      have hinj : Set.InjOn f ↑(mondrian_factor_shapes (c * p ^ e) A) := by
        intro x hx y hy he
        have hg : high x = high y := by rw [hrec x hx, hrec y hy, he]
        obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A x).mp hx
        obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A y).mp hy
        apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo
        dsimp [high] at hg
        split_ifs at hg <;> tauto
  7. The number of shapes is at most c.

    Since f is an injection from the set of valid shapes into {1, ..., c}, the cardinality of the domain is at most the cardinality of {1, ..., c}, which is c, by Finset.card_le_card_of_injOn.

    lines 60–61

    uses Finset.card_le_card_of_injOn

      have hcard := Finset.card_le_card_of_injOn f hmap hinj
      simpa using hcard
And.intro
Proofs of a and b combine to prove the conjunction a ∧ b.
Finset.card_le_card_of_injOn
If a function maps a finite set s into a finite set t injectively, then |s| ≤ |t|.
Finset.mem_Icc.mpr
If a ≤ x and x ≤ b, then x belongs to the closed discrete interval [a, b].
Finsupp.add_apply
The value of the sum of two finitely supported functions at an element is the sum of their individual values.
Finsupp.smul_apply
Evaluating the scalar multiple of a finitely supported function at an element equals the scalar multiple of the evaluated function.
Nat.factorization_mul
The prime factorization of the product of two positive integers is the sum of their individual prime factorizations.
Nat.factorization_pow
The prime factorization of n^k is k times the prime factorization of n.
Nat.factorization_pow_self
For a prime p, the exponent of p in the prime factorization of p^n is n.
Nat.factorization_eq_zero_of_not_dvd
If a prime p does not divide n, then the exponent of p in the prime factorization of n is zero.
Nat.mul_zero
Multiplying any natural number by zero yields zero.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.
Nat.ne_of_gt
If b < a, then a ≠ b.
Nat.not_dvd_of_pos_of_lt
A positive natural number n is not divisible by any strictly larger natural number m.
Nat.ordProj_mul_ordCompl_eq_self
Multiplying the p-part of n, p^(v_p(n)), by the quotient n / p^(v_p(n)) recovers n.
Nat.pos_of_mul_pos_left
If a product a * b is strictly positive, then b is strictly positive.
Nat.pos_of_mul_pos_right
If a product a * b is strictly positive, then a is strictly positive.
congrArg
If two inputs are equal, the values of a function applied to them are equal.
if_pos
If a condition c is true, the if-then-else expression evaluates to the then-branch.
if_neg
If a condition c is false, the if-then-else expression evaluates to the else-branch.
mondrian_factorization_le_scaled_prime_pow
For a prime p > c and positive integer x ≤ c * p^e, the p-adic exponent of x is at most e.
mondrian_mem_factor_shapes
A pair d = (d₁, d₂) belongs to mondrian_factor_shapes n A if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
mondrian_sorted_pairs_eq_of_shared
If two ordered factor pairs of A > 0 share at least one coordinate, then the two pairs are identical.
pow_ne_zero
A power of a non-zero element in a reduced monoid with zero is non-zero.
pow_pos
A strictly positive number raised to any power is strictly positive.
smul_eq_mul
Scalar multiplication of natural numbers agrees with standard multiplication.

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_first_exponent_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) (hr : k.factorization p = 1) :    (mondrian_factor_shapes (c * p ^ e) A).card ≤ c := by  have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc  have hvals : 1 + A.factorization p = 2 * e := by    have hf := congrArg (fun z : ℕ => z.factorization p) heq    rw [Nat.factorization_mul (Nat.ne_of_gt hk) (Nat.ne_of_gt hA), Finsupp.add_apply,      Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul,      Nat.factorization_mul (Nat.ne_of_gt hc) (pow_ne_zero e hp.ne_zero), Finsupp.add_apply,      Nat.factorization_eq_zero_of_not_dvd hcnot,      Nat.factorization_pow_self hp, hr] at hf    simpa using hf  let high := fun d : ℕ × ℕ => if d.1.factorization p = e then d.1 else d.2  let f := fun d : ℕ × ℕ => high d / p ^ e  have hhigh : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A,      0 < high d ∧ high d ≤ c * p ^ e ∧ (high d).factorization p = e := by    intro d hd    obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A d).mp hd    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)    have hxval := mondrian_factorization_le_scaled_prime_pow c p e d.1 hp hpc hx (hord.trans hn)    have hyval := mondrian_factorization_le_scaled_prime_pow c p e d.2 hp hpc hy hn    have hxyval : d.1.factorization p + d.2.factorization p = A.factorization p := by      have hh := congrArg (fun z : ℕ => z.factorization p) hprod      simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy),        Finsupp.add_apply] using hh    by_cases hh : d.1.factorization p = e    · simpa only [high, if_pos hh] using And.intro hx (And.intro (hord.trans hn) hh)    · have hyval' : d.2.factorization p = e := by omega      simpa only [high, if_neg hh] using And.intro hy (And.intro hn hyval')  have hrec : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A,      high d = p ^ e * f d := by    intro d hd    have hf := Nat.ordProj_mul_ordCompl_eq_self (high d) p    rw [(hhigh d hd).2.2] at hf    exact hf.symm  have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (c * p ^ e) A) ↑(Finset.Icc 1 c) := by    intro d hd    have hrec' := hrec d hd    obtain ⟨hpos, hn, hv⟩ := hhigh d hd    have hppos := pow_pos hp.pos e    apply Finset.mem_Icc.mpr    constructor    · by_contra hn      have hf0 : f d = 0 := by omega      rw [hf0, Nat.mul_zero] at hrec'      omega    · by_contra hn      have hm := Nat.mul_le_mul_left (p ^ e) (by omega : c + 1 ≤ f d)      nlinarith  have hinj : Set.InjOn f ↑(mondrian_factor_shapes (c * p ^ e) A) := by    intro x hx y hy he    have hg : high x = high y := by rw [hrec x hx, hrec y hy, he]    obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A x).mp hx    obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A y).mp hy    apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo    dsimp [high] at hg    split_ifs at hg <;> tauto  have hcard := Finset.card_le_card_of_injOn f hmap hinj  simpa using hcard
See it in the graphDiscuss this resultChallenge it