mondrian_prime_pair_encoding
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
- mondrian_factorization_le_scaled_prime_powA positive integer at most c times p to the e has p-adic exponent at most e when the prime p exceeds c.
- 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$.
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`.
uses
Nat.not_dvd_of_pos_of_lthave hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpcThe 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$.
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_selfhave 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
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$.
uses
mondrian_factorization_le_scaled_prime_powhave 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
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)$.
uses
congrArg,Nat.factorization_mul,Nat.ne_of_gt,Finsupp.add_applyhave 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
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$.
uses
Nat.mem_divisors.mprrefine ⟨by omega, hxval, Nat.mem_divisors.mpr ⟨?_, ?_⟩⟩
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.
uses
Nat.ordCompl_dvd_ordCompl_of_dvd· apply Nat.ordCompl_dvd_ordCompl_of_dvd _ p exact ⟨y, hxy.symm⟩
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`.
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.
- In Mathlib, the quotient $n / p^{v_p(n)}$ is called the order complement (`ordCompl`) of $n$ with respect to $p$; in paper mathematics this is standardly known as the $p$-free part of $n$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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))