mondrian_prime_free_factor_pair_encoding
In a positive factor pair of q^s times p^t whose first side is indivisible by q, that side is a pure p-power and the other side contains q^s.
Statement
theorem mondrian_prime_free_factor_pair_encoding (p q t s x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hpq : p ≠ q) (hx : 0 < x) (hy : 0 < y)
(hxy : x * y = q ^ s * p ^ t) (hfree : ¬ q ∣ x) :
x = p ^ x.factorization p ∧ y = q ^ s * p ^ y.factorization p ∧
x.factorization p + y.factorization p = t- Source
- Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- Used by 2
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- mondrian_prime_square_area_free_shape_boundFor distinct primes p and q and t+r=2e, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square have a side…
The proof, explained
The theorem characterizes factor pairs $x \cdot y = q^s p^t$ when $q \nmid x$. First, the general two-prime factorization gives $x = q^b p^{v_p(x)}$ and $y = q^c p^{v_p(y)}$ with $b + c = s$ and $v_p(x) + v_p(y) = t$. Since $q$ does not divide $x$, the exponent $b$ must be $0$, which forces $c = s$. Substituting these exponents into the decomposition shows that $x$ is a pure power of $p$ and $y$ contains the entire $q^s$ factor.
There exist exponents $b, c \in \mathbb{N}$ such that $b + c = s$, $x = q^b p^{v_p(x)}$, $y = q^c p^{v_p(y)}$, and $v_p(x) + v_p(y) = t$.
Apply `mondrian_two_prime_factor_pair_encoding` to the product $x y = q^s p^t$, decomposing $x$ and $y$ into their prime factors $p$ and $q$.
uses
mondrian_two_prime_factor_pair_encodingobtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t s x y hp hq hpq hx hy hxyThe exponent $b$ of $q$ in $x$ must be $0$.
Assume for contradiction that $b \neq 0$. By `dvd_pow_self`, $q \mid q^b$, which implies $q \mid q^b p^{v_p(x)} = x$ by `dvd_mul_of_dvd_left`. This contradicts the hypothesis `hfree` that $q \nmid x$.
uses
dvd_pow_self,dvd_mul_of_dvd_lefthave hb : b = 0 := by by_contra hh apply hfree rw [hxb] exact dvd_mul_of_dvd_left (dvd_pow_self q hh) _
The exponent $c$ of $q$ in $y$ equals $s$.
Since $b + c = s$ and $b = 0$, linear integer arithmetic (`omega`) determines that $c = s$.
have hc : c = s := by omega
$x = p^{v_p(x)}$, $y = q^s p^{v_p(y)}$, and $v_p(x) + v_p(y) = t$.
Substitute $b = 0$ and $c = s$ into the expressions for $x$ and $y$, simplifying $q^0$ to $1$ and $q^c$ to $q^s$, while retaining the sum of the $p$-exponents.
uses
And.introsimpa [hb, hc] using And.intro hxb (And.intro hyc hv)
mondrian_two_prime_factor_pair_encoding- A positive factor pair $x y = q^s p^t$ for distinct primes $p$ and $q$ factors as $x = q^b p^{v_p(x)}$ and $y = q^c p^{v_p(y)}$ with $b + c = s$ and $v_p(x) + v_p(y) = t$.
dvd_pow_self- An element divides any of its positive powers: if $n \neq 0$, then $a \mid a^n$.
dvd_mul_of_dvd_left- If $a$ divides $b$, then $a$ divides $b c$ for any $c$.
And.intro- Given proofs of propositions $A$ and $B$, constructs a proof of the conjunction $A \land B$.
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_free_factor_pair_encoding (p q t s x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (hx : 0 < x) (hy : 0 < y) (hxy : x * y = q ^ s * p ^ t) (hfree : ¬ q ∣ x) : x = p ^ x.factorization p ∧ y = q ^ s * p ^ y.factorization p ∧ x.factorization p + y.factorization p = t := by obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t s x y hp hq hpq hx hy hxy have hb : b = 0 := by by_contra hh apply hfree rw [hxb] exact dvd_mul_of_dvd_left (dvd_pow_self q hh) _ have hc : c = s := by omega simpa [hb, hc] using And.intro hxb (And.intro hyc hv)