AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_power_shape_bound

theoremverified

For k at least two and positive A with k times A equal to the area of a p-power square, the number of available shapes is at most the p-adic exponent of k.

Statement

theorem mondrian_prime_power_shape_bound (p e k A : ℕ) (hp : Nat.Prime p)
    (hk : 2 ≤ k) (hA : 0 < A) (heq : k * A = (p ^ e) ^ 2) :
    (mondrian_factor_shapes (p ^ e) A).card ≤ k.factorization p
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 5
  • mondrian_dvd_prime_pow_eqA divisor x of a power of a prime p is p to its own p-adic exponent.
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

To bound the number of available factor shapes of area A fitting into a p^e × p^e square, the proof maps each valid shape (d.1, d.2) injectively to the p-adic valuation of its shorter side, v_p(d.1). Because k * A = (p^e)^2 and k ≥ 2, every divisor of A is a pure power of p, and the geometric constraints d.1 ≤ d.2 ≤ p^e together with d.1 * d.2 < (p^e)^2 force v_p(d.1) into the half-open integer interval [e - v_p(k), e). Since a power of p is determined by its exponent and the second dimension is uniquely determined by area, this mapping is injective, so the number of shapes cannot exceed the interval's size, which is at most v_p(k).

  1. The numbers k, A, and p^e are non-zero.

    Linear arithmetic establishes k ≠ 0 from k ≥ 2 and A ≠ 0 from A > 0. Since p is prime, p ≠ 0, and any power of a non-zero element in a reduced monoid with zero is non-zero (`pow_ne_zero`), giving p^e ≠ 0.

    lines 4–6

    uses pow_ne_zero

      have hkne : k ≠ 0 := by omega
      have hAne : A ≠ 0 := by omega
      have hnne : p ^ e ≠ 0 := pow_ne_zero e hp.ne_zero
  2. The area A divides p^(2 * e).

    By exponent rules and commutativity of multiplication (`pow_mul`, `Nat.mul_comm`), (p^e)^2 = p^(2 * e). Substituting the hypothesis k * A = (p^e)^2, we obtain k * A = p^(2 * e). Because A divides k * A (`dvd_mul_left`), A divides p^(2 * e).

    lines 7–10

    uses pow_mul, Nat.mul_comm, dvd_mul_left

      have hApow : A ∣ p ^ (2 * e) := by
        have hnp : (p ^ e) ^ 2 = p ^ (2 * e) := by rw [← pow_mul, Nat.mul_comm e 2]
        rw [← hnp, ← heq]
        exact dvd_mul_left A k
  3. The sum of the p-adic valuations of k and A is 2 * e.

    Applying the p-adic factorization to both sides of k * A = (p^e)^2 via `congrArg`, the left-hand side expands to v_p(k) + v_p(A) by the additivity of factorization on positive integers (`Nat.factorization_mul`, `Finsupp.add_apply`). The right-hand side simplifies to 2 * e by the power rule for factorizations (`Nat.factorization_pow`, `Finsupp.smul_apply`, `smul_eq_mul`) and the prime valuation v_p(p) = 1 (`Nat.factorization_pow_self`).

    lines 11–16

    uses congrArg, Nat.factorization_mul, Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, Nat.factorization_pow_self

      have hvals : k.factorization p + A.factorization p = 2 * e := by
        have hf := congrArg (fun z : ℕ => z.factorization p) heq
        rw [Nat.factorization_mul hkne hAne, Finsupp.add_apply,
          Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul,
          Nat.factorization_pow_self hp] at hf
        exact hf
  4. The map f(d) = v_p(d.1) sends each valid factor shape d into the discrete interval [e - v_p(k), e).

    Let d = (d.1, d.2) be a factor shape of area A in a square of side p^e (`mondrian_mem_factor_shapes`). Since d.1 * d.2 = A > 0, both d.1 and d.2 are strictly positive (`Nat.pos_of_mul_pos_right`, `Nat.pos_of_mul_pos_left`). Each divides A (`Dvd.intro`) and therefore divides p^(2 * e) (`dvd_trans`). By `mondrian_dvd_prime_pow_eq`, any divisor of a power of p is a power of p, so d.1 = p^(v_p(d.1)) and d.2 = p^(v_p(d.2)). Because k ≥ 2, we have A = (p^e)^2 / k < (p^e)^2; if d.1 ≥ p^e, then d.1 * d.2 ≥ (p^e)^2 > A (`Nat.mul_le_mul`), which is a contradiction. Hence d.1 < p^e, meaning v_p(d.1) < e (`Nat.pow_lt_pow_iff_right`). Similarly, d.2 ≤ p^e gives v_p(d.2) ≤ e (`Nat.pow_le_pow_iff_right`). Taking the p-adic valuation of d.1 * d.2 = A gives v_p(d.1) + v_p(d.2) = v_p(A) (`congrArg`, `Nat.factorization_mul`, `Nat.ne_of_gt`, `Finsupp.add_apply`). Combining this with v_p(k) + v_p(A) = 2 * e and v_p(d.2) ≤ e yields v_p(d.1) = v_p(A) - v_p(d.2) ≥ 2 * e - v_p(k) - e = e - v_p(k). Thus f(d) lies in [e - v_p(k), e) (`Finset.mem_coe`, `Finset.mem_Ico`).

    lines 17–47

    uses mondrian_mem_factor_shapes, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, Dvd.intro, dvd_trans, mondrian_dvd_prime_pow_eq, Nat.mul_le_mul, Nat.pow_lt_pow_iff_right, Nat.pow_le_pow_iff_right, congrArg, Nat.factorization_mul, Nat.ne_of_gt, Finsupp.add_apply, Finset.mem_coe, Finset.mem_Ico

      let f := fun d : ℕ × ℕ => d.1.factorization p
      have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (p ^ e) A)
          ↑(Finset.Ico (e - k.factorization p) e) := by
        intro d hd
        obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (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 hxdvd : d.1 ∣ p ^ (2 * e) := (Dvd.intro d.2 hprod).trans hApow
        have hydvd : d.2 ∣ p ^ (2 * e) := by
          apply dvd_trans _ hApow
          exact ⟨d.1, by nlinarith [hprod]⟩
        have hxpow := mondrian_dvd_prime_pow_eq p (2 * e) d.1 hp hxdvd
        have hypow := mondrian_dvd_prime_pow_eq p (2 * e) d.2 hp hydvd
        have hxlt : d.1 < p ^ e := by
          have hAlt : A < (p ^ e) ^ 2 := by nlinarith
          by_contra hnot
          have hle : p ^ e ≤ d.1 := by omega
          have hmul := Nat.mul_le_mul hle (hle.trans hord)
          nlinarith
        have hxe : d.1.factorization p < e := by
          apply (Nat.pow_lt_pow_iff_right hp.one_lt).mp
          simpa only [← hxpow] using hxlt
        have hye : d.2.factorization p ≤ e := by
          apply (Nat.pow_le_pow_iff_right hp.one_lt).mp
          simpa only [← hypow] using 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
        simp only [f, Finset.mem_coe, Finset.mem_Ico]
        omega
  5. The map f is injective on the set of factor shapes.

    Suppose two shapes x and y satisfy f(x) = f(y), so v_p(x.1) = v_p(y.1). Because x.1 and y.1 divide A ∣ p^(2 * e) (`mondrian_mem_factor_shapes`, `Dvd.intro`), they are prime powers of p (`mondrian_dvd_prime_pow_eq`), which implies x.1 = p^(v_p(x.1)) = p^(v_p(y.1)) = y.1 (`congrArg`). Since x.1 > 0 (`Nat.pos_of_mul_pos_right`) and x.1 * x.2 = A = y.1 * y.2 = x.1 * y.2, canceling x.1 gives x.2 = y.2 (`Nat.eq_of_mul_eq_mul_left`). Matching both coordinates gives x = y (`Prod.ext`).

    lines 48–61

    uses mondrian_mem_factor_shapes, Dvd.intro, mondrian_dvd_prime_pow_eq, congrArg, Nat.pos_of_mul_pos_right, Prod.ext, Nat.eq_of_mul_eq_mul_left

      have hinj : Set.InjOn f ↑(mondrian_factor_shapes (p ^ e) A) := by
        intro x hx y hy hxy
        obtain ⟨hxp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A x).mp hx
        obtain ⟨hyp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A y).mp hy
        have hxdvd : x.1 ∣ p ^ (2 * e) := (Dvd.intro x.2 hxp).trans hApow
        have hydvd : y.1 ∣ p ^ (2 * e) := (Dvd.intro y.2 hyp).trans hApow
        have hw : x.1 = y.1 := by
          rw [mondrian_dvd_prime_pow_eq p (2 * e) x.1 hp hxdvd,
            mondrian_dvd_prime_pow_eq p (2 * e) y.1 hp hydvd]
          exact congrArg (fun u => p ^ u) hxy
        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]
  6. The number of available shapes is at most v_p(k).

    By injectivity of f, the cardinality of the set of factor shapes is bounded by the cardinality of the target interval [e - v_p(k), e) (`Finset.card_le_card_of_injOn`). The size of this interval is e - (e - v_p(k)) ≤ v_p(k) (`Nat.card_Ico`), which establishes the theorem.

    lines 62–66

    uses Finset.card_le_card_of_injOn, Nat.card_Ico

      have hc := Finset.card_le_card_of_injOn f hmap hinj
      have hcard : (Finset.Ico (e - k.factorization p) e).card ≤ k.factorization p := by
        simp only [Nat.card_Ico]
        omega
      exact hc.trans hcard
pow_ne_zero
A power of a non-zero element in a reduced monoid with zero is non-zero.
pow_mul
Powers of powers satisfy (a^m)^n = a^(m * n).
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
dvd_mul_left
An element divides any product of which it is a factor: a ∣ b * a.
congrArg
Functions preserve equality: if a₁ = a₂, then f(a₁) = f(a₂).
Nat.factorization_mul
The prime factorization of a product of positive integers is the sum of their factorizations.
Finsupp.add_apply
Evaluation of a sum of finitely supported functions is the sum of their evaluations: (g₁ + g₂) a = g₁ a + g₂ a.
Nat.factorization_pow
The prime factorization of n^k is k times the factorization of n.
Finsupp.smul_apply
Evaluation of a scalar multiple of a finitely supported function: (b • v) a = b • v a.
smul_eq_mul
Scalar multiplication in a multiplicative structure is standard multiplication: a • b = a * b.
Nat.factorization_pow_self
For a prime p, the p-adic valuation of p^n is n.
mondrian_mem_factor_shapes
A pair d is a valid factor shape of area A in an n × n square iff d.1 * d.2 = A, A ≠ 0, d.1 ≤ d.2, and d.2 ≤ n.
Nat.pos_of_mul_pos_right
If a product of natural numbers is positive, then its first factor is positive.
Nat.pos_of_mul_pos_left
If a product of natural numbers is positive, then its second factor is positive.
Dvd.intro
If a * c = b, then a divides b.
dvd_trans
Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.
mondrian_dvd_prime_pow_eq
Any divisor of a prime power p^e is uniquely given by p^(v_p(x)).
Nat.mul_le_mul
Multiplication preserves the order ≤ on natural numbers.
Nat.pow_lt_pow_iff_right
For a base greater than one, a^n < a^m iff n < m.
Nat.pow_le_pow_iff_right
For a base greater than one, a^n ≤ a^m iff n ≤ m.
Nat.ne_of_gt
If b < a, then a ≠ b.
Finset.mem_coe
Coercion from Finset to Set preserves membership.
Finset.mem_Ico
An element x belongs to the half-open interval [a, b) iff a ≤ x and x < b.
Prod.ext
Two ordered pairs are equal if their corresponding components are equal.
Nat.eq_of_mul_eq_mul_left
A positive factor can be canceled from the left of an equation: if n > 0 and n * m = n * k, then m = k.
Finset.card_le_card_of_injOn
An injective map from a finite set s to a finite set t implies |s| ≤ |t|.
Nat.card_Ico
The cardinality of the discrete interval [a, b) is b - 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_power_shape_bound (p e k A : ℕ) (hp : Nat.Prime p)    (hk : 2 ≤ k) (hA : 0 < A) (heq : k * A = (p ^ e) ^ 2) :    (mondrian_factor_shapes (p ^ e) A).card ≤ k.factorization p := by  have hkne : k ≠ 0 := by omega  have hAne : A ≠ 0 := by omega  have hnne : p ^ e ≠ 0 := pow_ne_zero e hp.ne_zero  have hApow : A ∣ p ^ (2 * e) := by    have hnp : (p ^ e) ^ 2 = p ^ (2 * e) := by rw [← pow_mul, Nat.mul_comm e 2]    rw [← hnp, ← heq]    exact dvd_mul_left A k  have hvals : k.factorization p + A.factorization p = 2 * e := by    have hf := congrArg (fun z : ℕ => z.factorization p) heq    rw [Nat.factorization_mul hkne hAne, Finsupp.add_apply,      Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul,      Nat.factorization_pow_self hp] at hf    exact hf  let f := fun d : ℕ × ℕ => d.1.factorization p  have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (p ^ e) A)      ↑(Finset.Ico (e - k.factorization p) e) := by    intro d hd    obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (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 hxdvd : d.1 ∣ p ^ (2 * e) := (Dvd.intro d.2 hprod).trans hApow    have hydvd : d.2 ∣ p ^ (2 * e) := by      apply dvd_trans _ hApow      exact ⟨d.1, by nlinarith [hprod]⟩    have hxpow := mondrian_dvd_prime_pow_eq p (2 * e) d.1 hp hxdvd    have hypow := mondrian_dvd_prime_pow_eq p (2 * e) d.2 hp hydvd    have hxlt : d.1 < p ^ e := by      have hAlt : A < (p ^ e) ^ 2 := by nlinarith      by_contra hnot      have hle : p ^ e ≤ d.1 := by omega      have hmul := Nat.mul_le_mul hle (hle.trans hord)      nlinarith    have hxe : d.1.factorization p < e := by      apply (Nat.pow_lt_pow_iff_right hp.one_lt).mp      simpa only [← hxpow] using hxlt    have hye : d.2.factorization p ≤ e := by      apply (Nat.pow_le_pow_iff_right hp.one_lt).mp      simpa only [← hypow] using 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    simp only [f, Finset.mem_coe, Finset.mem_Ico]    omega  have hinj : Set.InjOn f ↑(mondrian_factor_shapes (p ^ e) A) := by    intro x hx y hy hxy    obtain ⟨hxp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A x).mp hx    obtain ⟨hyp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A y).mp hy    have hxdvd : x.1 ∣ p ^ (2 * e) := (Dvd.intro x.2 hxp).trans hApow    have hydvd : y.1 ∣ p ^ (2 * e) := (Dvd.intro y.2 hyp).trans hApow    have hw : x.1 = y.1 := by      rw [mondrian_dvd_prime_pow_eq p (2 * e) x.1 hp hxdvd,        mondrian_dvd_prime_pow_eq p (2 * e) y.1 hp hydvd]      exact congrArg (fun u => p ^ u) hxy    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 hc := Finset.card_le_card_of_injOn f hmap hinj  have hcard : (Finset.Ico (e - k.factorization p) e).card ≤ k.factorization p := by    simp only [Nat.card_Ico]    omega  exact hc.trans hcard
See it in the graphDiscuss this resultChallenge it