AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_pair_encoding

theoremverified

For 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 between e minus the p-adic exponent of k and e, and its complementary factor divides the p-free part of A.

Statement

theorem mondrian_prime_pair_encoding (c p e k A x y : ℕ) (hc : 0 < c)
    (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)
    (heq : k * A = (c * p ^ e) ^ 2) (hx : 0 < x) (hy : 0 < y)
    (hxn : x ≤ c * p ^ e) (hyn : y ≤ c * p ^ e) (hxy : x * y = A) :
    e - k.factorization p ≤ x.factorization p ∧ x.factorization p ≤ e ∧
      (x / p ^ (x.factorization p)) ∈ (A / p ^ (A.factorization p)).divisors
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
Used by 1
  • mondrian_ordered_prime_shape_boundThe 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…

The proof, explained

The proof analyzes the $p$-adic valuations of both sides of the area equations $k A = (c p^e)^2$ and $x y = A$. Since $c < p$, the prime $p$ does not divide $c$, which enables equating the sum of the valuations $v_p(k) + v_p(A) = 2e$ and $v_p(x) + v_p(y) = v_p(A)$. The geometric bounds $x, y \le c p^e$ ensure that both $v_p(x) \le e$ and $v_p(y) \le e$, which together trap $v_p(x)$ between $e - v_p(k)$ and $e$. Finally, because $x$ divides $A$, removing the maximal powers of $p$ preserves divisibility, placing the $p$-free part of $x$ into the divisor set of the $p$-free part of $A$.

  1. The prime $p$ does not divide $c$.

    Since $0 < c < p$, the prime $p$ is strictly greater than the positive integer $c$, so $p$ cannot divide $c$ by `Nat.not_dvd_of_pos_of_lt`.

    line 7

    uses Nat.not_dvd_of_pos_of_lt

      have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc
  2. The sum of the $p$-adic valuations of $k$ and $A$ is $2e$, that is, $v_p(k) + v_p(A) = 2e$.

    Applying the valuation function $z \mapsto v_p(z)$ to both sides of $k \cdot A = (c \cdot p^e)^2$ via `congrArg` gives $v_p(k \cdot A) = v_p((c \cdot p^e)^2)$. Since $k, A > 0$, the left-hand side decomposes into $v_p(k) + v_p(A)$ by `Nat.factorization_mul`. On the right-hand side, the power 2 pulls out by `Nat.factorization_pow`, giving $2 \cdot v_p(c \cdot p^e) = 2 \cdot (v_p(c) + v_p(p^e))$. Because $p \nmid c$, $v_p(c) = 0$ by `Nat.factorization_eq_zero_of_not_dvd`. Since $p$ is prime, $v_p(p^e) = e$ by `Nat.factorization_pow_self`. Simplifying yields $2e$.

    lines 8–15

    uses 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 hvals : k.factorization p + 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] at hf
        simpa using hf
  3. The $p$-adic valuations of $x$ and $y$ are both at most $e$, that is, $v_p(x) \le e$ and $v_p(y) \le e$.

    Because $x \le c \cdot p^e$ and $y \le c \cdot p^e$ with $c < p$ and $p$ prime, the scaling bound `mondrian_factorization_le_scaled_prime_pow` applies directly to both $x$ and $y$.

    lines 16–17

    uses mondrian_factorization_le_scaled_prime_pow

      have hxval := mondrian_factorization_le_scaled_prime_pow c p e x hp hpc hx hxn
      have hyval := mondrian_factorization_le_scaled_prime_pow c p e y hp hpc hy hyn
  4. The sum of the $p$-adic valuations of $x$ and $y$ equals that of $A$, that is, $v_p(x) + v_p(y) = v_p(A)$.

    Applying $z \mapsto v_p(z)$ to both sides of $x \cdot y = A$ via `congrArg` and expanding the product valuation of positive integers $x$ and $y$ via `Nat.factorization_mul` yields the sum $v_p(x) + v_p(y) = v_p(A)$.

    lines 18–21

    uses congrArg, Nat.factorization_mul, Nat.ne_of_gt, Finsupp.add_apply

      have hxyval : x.factorization p + y.factorization p = A.factorization p := by
        have hh := congrArg (fun z : ℕ => z.factorization p) hxy
        simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy),
          Finsupp.add_apply] using hh
  5. The bounds $e - v_p(k) \le v_p(x) \le e$ hold, and membership in the divisors of the $p$-free part of $A$ reduces to divisibility and non-zeroness.

    The lower bound $e - v_p(k) \le v_p(x)$ follows from $v_p(k) + v_p(A) = 2e$, $v_p(x) + v_p(y) = v_p(A)$, and $v_p(y) \le e$ by linear arithmetic (`omega`). The upper bound $v_p(x) \le e$ is supplied directly by `hxval`. By `Nat.mem_divisors.mpr`, membership of $x / p^{v_p(x)}$ in the divisor set of $A / p^{v_p(A)}$ reduces to showing that it divides $A / p^{v_p(A)}$ and that $A / p^{v_p(A)} \neq 0$.

    line 22

    uses Nat.mem_divisors.mpr

      refine ⟨by omega, hxval, Nat.mem_divisors.mpr ⟨?_, ?_⟩⟩
  6. The $p$-free part of $x$ divides the $p$-free part of $A$, that is, $x / p^{v_p(x)} \mid A / p^{v_p(A)}$.

    Since $x \cdot y = A$, $x$ divides $A$ with cofactor $y$. By `Nat.ordCompl_dvd_ordCompl_of_dvd`, dividing out the maximal power of $p$ preserves divisibility.

    lines 23–24

    uses Nat.ordCompl_dvd_ordCompl_of_dvd

      · apply Nat.ordCompl_dvd_ordCompl_of_dvd _ p
        exact ⟨y, hxy.symm⟩
  7. The $p$-free part of $A$ is non-zero, that is, $A / p^{v_p(A)} \neq 0$.

    Since $A > 0$, its $p$-free part is strictly positive by `Nat.ordCompl_pos`, and hence non-zero by `Nat.ne_of_gt`.

    line 25

    uses Nat.ne_of_gt, Nat.ordCompl_pos

      · exact Nat.ne_of_gt (Nat.ordCompl_pos p (Nat.ne_of_gt hA))
congrArg
Applying a function to equal arguments yields equal values.
Finsupp.add_apply
The value of the sum of two finitely supported functions at an argument is the sum of their values at that argument.
Finsupp.smul_apply
Scalar multiplication on a finitely supported function acts pointwise.
mondrian_factorization_le_scaled_prime_pow
For a prime $p$ and non-zero $x \le c \cdot p^e$ with $c < p$, the $p$-adic exponent $v_p(x)$ is at most $e$.
Nat.factorization_eq_zero_of_not_dvd
If a prime $p$ does not divide $n$, the $p$-adic exponent of $n$ is 0.
Nat.factorization_mul
The prime factorization of a product of two non-zero natural numbers is the sum of their 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 $p$-adic exponent of $p^n$ is $n$.
Nat.mem_divisors.mpr
An element belongs to the divisor set of $m$ if it divides $m$ and $m$ is non-zero.
Nat.ne_of_gt
A strictly greater natural number is not equal to a smaller one (in particular, a positive integer is non-zero).
Nat.not_dvd_of_pos_of_lt
A positive natural number cannot be divided by any strictly larger natural number.
Nat.ordCompl_dvd_ordCompl_of_dvd
If $a$ divides $b$, then the $p$-free part of $a$ divides the $p$-free part of $b$.
Nat.ordCompl_pos
For any non-zero natural number $n$, its $p$-free part is strictly positive.
pow_ne_zero
A non-zero base raised to any power is non-zero.
smul_eq_mul
Scalar multiplication by a natural number on $\mathbb{N}$ is ordinary 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_pair_encoding (c p e k A x y : ℕ) (hc : 0 < c)    (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)    (heq : k * A = (c * p ^ e) ^ 2) (hx : 0 < x) (hy : 0 < y)    (hxn : x ≤ c * p ^ e) (hyn : y ≤ c * p ^ e) (hxy : x * y = A) :    e - k.factorization p ≤ x.factorization p ∧ x.factorization p ≤ e ∧      (x / p ^ (x.factorization p)) ∈ (A / p ^ (A.factorization p)).divisors := by  have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc  have hvals : k.factorization p + 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] at hf    simpa using hf  have hxval := mondrian_factorization_le_scaled_prime_pow c p e x hp hpc hx hxn  have hyval := mondrian_factorization_le_scaled_prime_pow c p e y hp hpc hy hyn  have hxyval : x.factorization p + y.factorization p = A.factorization p := by    have hh := congrArg (fun z : ℕ => z.factorization p) hxy    simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy),      Finsupp.add_apply] using hh  refine ⟨by omega, hxval, Nat.mem_divisors.mpr ⟨?_, ?_⟩⟩  · apply Nat.ordCompl_dvd_ordCompl_of_dvd _ p    exact ⟨y, hxy.symm⟩  · exact Nat.ne_of_gt (Nat.ordCompl_pos p (Nat.ne_of_gt hA))
See it in the graphDiscuss this resultChallenge it