mondrian_prime_free_height_encoding
If x*y=q^s*p^t for primes p and q and q does not divide x, then y is q^s times a power of p; the primes need not be distinct.
Statement
theorem mondrian_prime_free_height_encoding (p q s t x y : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hxy : x * y = q ^ s * p ^ t) (hx : ¬ q ∣ x) :
∃ a, y = q ^ s * p ^ a- Source
- For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mondrian_dvd_prime_pow_eqA divisor x of a power of a prime p is p to its own p-adic exponent.
- 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 1
- mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.
The proof, explained
Since q is prime and does not divide x, the power q^s is coprime to x. Because q^s divides x * y = q^s * p^t, Euclid's lemma forces q^s to divide y, allowing us to write y = q^s * z. Substituting this into the product equation and cancelling the non-zero factor q^s leaves x * z = p^t, so z divides p^t. Any divisor of a power of the prime p must itself be a power of p, which shows that y is q^s times a power of p.
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 that q^s is coprime to x (by `pow_left`). From the equation x * y = q^s * p^t, q^s divides x * y (by `dvd_mul_right`). Because q^s is coprime to x, Gauss's lemma implies that q^s divides y. We unpack this divisibility to obtain an integer quotient z such that y = q^s * z.
uses
pow_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_right _ _) obtain ⟨z, hz⟩ := hy
x * z = p^t.
Substituting y = q^s * z into x * y = q^s * p^t gives x * (q^s * z) = q^s * p^t, which can be rearranged to q^s * (x * z) = q^s * p^t. Since q is prime, q is strictly positive, hence q^s > 0 by `pow_pos`. Cancelling the common factor q^s from both sides using `Nat.eq_of_mul_eq_mul_left` yields x * z = p^t.
uses
pow_pos,Nat.eq_of_mul_eq_mul_lefthave hprod : x * z = p ^ t := by rw [hz] at hxy apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s) nlinarith [hxy]
z is a power of p, specifically z = p ^ (z.factorization p).
The relation x * z = p^t shows that z divides p^t. Since p is prime, any divisor of a power of p is itself a power of p. Applying `mondrian_dvd_prime_pow_eq` gives z = p ^ (z.factorization p), where z.factorization p is the multiplicity of p in z.
uses
mondrian_dvd_prime_pow_eqhave hzpow := mondrian_dvd_prime_pow_eq p t z hp ⟨x, by nlinarith [hprod]⟩
There exists an exponent a such that y = q^s * p^a.
We provide a = z.factorization p as the witness. Since y = q^s * z, multiplying both sides of z = p ^ (z.factorization p) by q^s using `congrArg` gives y = q^s * p ^ (z.factorization p).
uses
congrArgrefine ⟨z.factorization p, ?_⟩ rw [hz] exact congrArg (fun v => q ^ s * v) hzpow
pow_left- If m is coprime to k, then any power m^n is also coprime to k.
dvd_mul_right- An element a divides the product a * b.
Nat.eq_of_mul_eq_mul_left- If n > 0 and n * m = n * k for natural numbers, then m = k.
pow_pos- A strictly positive element raised to any power is strictly positive.
mondrian_dvd_prime_pow_eq- If p is prime and x divides p^e, then x is p raised to the multiplicity of p in x.
congrArg- If two inputs are equal, then applying the same function to them yields equal outputs.
- The exponent `z.factorization p` represents the multiplicity of the prime p in the prime factorization of z (its p-adic valuation).
- The tactic `nlinarith` is used in lines 10 and 11 to handle the ring arithmetic of associativity and commutativity of 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
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_encoding (p q s t x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hxy : x * y = q ^ s * p ^ t) (hx : ¬ q ∣ x) : ∃ a, y = q ^ s * p ^ a := 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_right _ _) obtain ⟨z, hz⟩ := hy have hprod : x * z = p ^ t := by rw [hz] at hxy apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s) nlinarith [hxy] have hzpow := mondrian_dvd_prime_pow_eq p t z hp ⟨x, by nlinarith [hprod]⟩ refine ⟨z.factorization p, ?_⟩ rw [hz] exact congrArg (fun v => q ^ s * v) hzpow