mondrian_prime_free_height_two_chain_encoding
If x*y=q^s*r*p^a for primes p,q,r with p≠r, and q does not divide x, then y lies in one of the chains q^s*p^b or q^s*r*p^b.
Statement
theorem mondrian_prime_free_height_two_chain_encoding (p q r a s x y : ℕ)
(hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpr : p ≠ r)
(hxy : x * y = q ^ s * r * p ^ a) (hx : ¬ q ∣ x) :
∃ b : ℕ, y = q ^ s * p ^ b ∨ y = q ^ s * r * p ^ b- Source
- For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mondrian_two_prime_divisor_encodingEvery divisor x of q^s times p^t, for distinct primes p and q, is q^b times p to the p-adic exponent of x, with b at most s.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 2
- mondrian_no_perfect_three_prime_area_one_factorFor three distinct primes p,q,r with p>r+1, no perfect admissible integer square partition has common tile area q^s*r*p^a, for arbitrary…
- mondrian_three_prime_common_area_sides_divideFor primes p,q,r with p>r+1, if q divides the square side and every tile in a perfect admissible partition has area q^s*r*p^a, then q…
The proof, explained
Since q is prime and does not divide x, q^s is coprime to x, so divisibility of x * y = q^s * r * p^a by q^s implies that q^s divides y, allowing us to write y = q^s * z. Canceling q^s yields x * z = r * p^a, which implies that z divides r^1 * p^a. Applying the two-prime divisor encoding theorem to z gives z = r^b * p^c with b ≤ 1, and the two possible values b = 0 and b = 1 place y in the chains q^s * p^c and q^s * r * p^c, respectively.
q^s divides y, so y = q^s * z for some natural number z.
Since q is prime and does not divide x, q and x are coprime, which implies q^s and x are coprime. Since q^s divides the product x * y = q^s * r * p^a (using dvd_mul_right and dvd_mul_of_dvd_left), coprimality implies that q^s divides y. We let z be the quotient satisfying y = q^s * z.
uses
dvd_mul_of_dvd_left,dvd_mul_righthave hcop : (q ^ s).Coprime x := (hq.coprime_iff_not_dvd.mpr hx).pow_left s have hy : q ^ s ∣ y := hcop.dvd_mul_left.mp (by rw [hxy] exact dvd_mul_of_dvd_left (dvd_mul_right _ _) _) obtain ⟨z, hz⟩ := hy
x * z = r * p^a.
Substituting y = q^s * z into x * y = q^s * r * p^a gives x * (q^s * z) = q^s * (r * p^a), which rearranges to q^s * (x * z) = q^s * (r * p^a). Because q is prime, q > 0 and thus q^s > 0 by pow_pos. Canceling q^s from both sides using Nat.eq_of_mul_eq_mul_left yields x * z = r * p^a.
uses
Nat.eq_of_mul_eq_mul_left,pow_poshave hprod : x * z = r * p ^ a := by rw [hz] at hxy apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s) nlinarith [hxy]
z divides r^1 * p^a.
Rewriting r^1 as r using pow_one, the equality x * z = r * p^a shows that x witnesses that z divides r^1 * p^a.
uses
pow_onehave hzdiv : z ∣ r ^ 1 * p ^ a := by rw [pow_one] exact ⟨x, by nlinarith [hprod]⟩
z has the form r^b * p^(z.factorization p) with b ≤ 1, and choosing z.factorization p as the witness reduces the goal to showing y = q^s * p^(z.factorization p) ∨ y = q^s * r * p^(z.factorization p).
Applying mondrian_two_prime_divisor_encoding to the distinct primes p and r and the divisor relation z ∣ r^1 * p^a yields an exponent b ≤ 1 such that z = r^b * p^(z.factorization p). We supply z.factorization p as the witness for the existential quantifier in the goal.
uses
mondrian_two_prime_divisor_encodingobtain ⟨b, hb, hzb⟩ := mondrian_two_prime_divisor_encoding p r a 1 z hp hr hpr hzdiv refine ⟨z.factorization p, ?_⟩
The exponent b is either 0 or 1, splitting the proof into two cases.
Since b is a natural number with b ≤ 1, linear arithmetic (via omega) determines that b = 0 or b = 1. We perform a case analysis on these two alternatives.
have hbcase : b = 0 ∨ b = 1 := by omega rcases hbcase with rfl | rfl
In the case b = 0, y = q^s * p^(z.factorization p), satisfying the left disjunct.
When b = 0, the identity z = r^0 * p^(z.factorization p) simplifies to z = p^(z.factorization p) because r^0 = 1 (pow_zero) and 1 * p^k = p^k (one_mul). Multiplying both sides by q^s via congrArg and using y = q^s * z gives y = q^s * p^(z.factorization p).
uses
pow_zero,one_mul,congrArg· left simpa only [pow_zero, one_mul] using hz.trans (congrArg (fun v => q ^ s * v) hzb)
In the case b = 1, y = q^s * r * p^(z.factorization p), satisfying the right disjunct.
When b = 1, the identity z = r^1 * p^(z.factorization p) simplifies to z = r * p^(z.factorization p) because r^1 = r (pow_one). Multiplying both sides by q^s via congrArg, substituting y = q^s * z, and using the associativity of multiplication (Nat.mul_assoc) gives y = q^s * r * p^(z.factorization p).
uses
pow_one,Nat.mul_assoc,congrArg· right simpa only [pow_one, Nat.mul_assoc] using hz.trans (congrArg (fun v => q ^ s * v) hzb)
dvd_mul_of_dvd_left- If a divides b, then a divides b * c for any c.
dvd_mul_right- Any element a divides the product a * b.
Nat.eq_of_mul_eq_mul_left- For natural numbers, if n > 0 and n * m = n * k, then m = k.
pow_pos- Any power of a strictly positive element is strictly positive.
pow_one- Any element raised to the power 1 equals itself (a^1 = a).
mondrian_two_prime_divisor_encoding- For distinct primes p and q, every divisor x of q^s * p^t can be written as q^b * p^(x.factorization p) for some b ≤ s.
pow_zero- Any element raised to the power 0 equals 1 (a^0 = 1).
one_mul- Multiplying an element on the left by 1 leaves it unchanged (1 * a = a).
congrArg- If two inputs are equal, then applying any function to them yields equal outputs.
Nat.mul_assoc- Multiplication of natural numbers is associative: (n * m) * k = n * (m * k).
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_height_two_chain_encoding (p q r a s x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpr : p ≠ r) (hxy : x * y = q ^ s * r * p ^ a) (hx : ¬ q ∣ x) : ∃ b : ℕ, y = q ^ s * p ^ b ∨ y = q ^ s * r * p ^ b := by have hcop : (q ^ s).Coprime x := (hq.coprime_iff_not_dvd.mpr hx).pow_left s have hy : q ^ s ∣ y := hcop.dvd_mul_left.mp (by rw [hxy] exact dvd_mul_of_dvd_left (dvd_mul_right _ _) _) obtain ⟨z, hz⟩ := hy have hprod : x * z = r * p ^ a := by rw [hz] at hxy apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s) nlinarith [hxy] have hzdiv : z ∣ r ^ 1 * p ^ a := by rw [pow_one] exact ⟨x, by nlinarith [hprod]⟩ obtain ⟨b, hb, hzb⟩ := mondrian_two_prime_divisor_encoding p r a 1 z hp hr hpr hzdiv refine ⟨z.factorization p, ?_⟩ have hbcase : b = 0 ∨ b = 1 := by omega rcases hbcase with rfl | rfl · left simpa only [pow_zero, one_mul] using hz.trans (congrArg (fun v => q ^ s * v) hzb) · right simpa only [pow_one, Nat.mul_assoc] using hz.trans (congrArg (fun v => q ^ s * v) hzb)