mondrian_large_prime_count_not_dvd
If enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot divide the required tile count.
Statement
theorem mondrian_large_prime_count_not_dvd (c p e k A : ℕ) (hc : 0 < c)
(hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)
(heq : k * A = (c * p ^ e) ^ 2)
(hcard : k ≤ (mondrian_factor_shapes (c * p ^ e) A).card) : ¬ p ∣ k- 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 4
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_prime_first_exponent_shape_boundWhen the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A…
- mondrian_prime_pow_gapFor p at least two, c less than p, and r at least two, c * (r + 1) is less than p to the r.
- mondrian_prime_shape_boundIf k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the…
- Used by 1
- mondrian_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
The proof, explained
The theorem is proved by contradiction: assuming p divides k, the exponent r = v_p(k) in the prime factorization of k must be at least 1. We split into two cases based on whether r = 1 or r ≥ 2. When r = 1, the number of available factor shapes is bounded by c, but p ∣ k forces p ≤ k ≤ c, contradicting c < p. When r ≥ 2, the shape count is bounded by (r + 1)c, which is strictly less than p^r ≤ k, contradicting the assumption that k is bounded by the number of factor shapes.
Assuming for contradiction that p divides k, the exponent of p in the prime factorization of k is at least 1.
Assume for contradiction that p ∣ k. Since k > 0, k is non-zero by Nat.ne_of_gt. Because p is prime, p ∣ k is equivalent to 1 ≤ v_p(k) by hp.dvd_iff_one_le_factorization, so p appears in the prime factorization of k with exponent at least 1.
uses
hp.dvd_iff_one_le_factorization,Nat.ne_of_gtintro hpk have hr := (hp.dvd_iff_one_le_factorization (Nat.ne_of_gt hk)).mp hpk
It suffices to consider the cases where the exponent v_p(k) is 1 versus at least 2.
We split into cases based on whether the exponent of p in the factorization of k equals 1 or not. Since the exponent is at least 1, the negation means it is at least 2.
by_cases hr1 : k.factorization p = 1The case v_p(k) = 1 leads to a contradiction.
When v_p(k) = 1, mondrian_prime_first_exponent_shape_bound implies that the number of available factor shapes is at most c. On the other hand, since p ∣ k and k > 0, we have p ≤ k by Nat.le_of_dvd. Combined with the hypothesis k ≤ |shapes|, this gives p ≤ k ≤ c, which contradicts c < p. Linear arithmetic (omega) closes this case.
uses
mondrian_prime_first_exponent_shape_bound,Nat.le_of_dvd· have hbound := mondrian_prime_first_exponent_shape_bound c p e k A hc hp hpc hk hA heq hr1 have hpkle := Nat.le_of_dvd hk hpk omega
The case v_p(k) ≥ 2 also leads to a contradiction, concluding the proof.
When v_p(k) ≠ 1, we have v_p(k) ≥ 2 because v_p(k) ≥ 1. By mondrian_prime_shape_bound, the number of factor shapes is at most (v_p(k) + 1) * c. Since p ≥ 2 (by hp.two_le), c < p, and v_p(k) ≥ 2, mondrian_prime_pow_gap guarantees that (v_p(k) + 1) * c < p^(v_p(k)). Moreover, Nat.ordProj_le (using k ≠ 0 from Nat.ne_of_gt) shows that p^(v_p(k)) ≤ k. Putting these together yields k ≤ |shapes| ≤ (v_p(k) + 1) * c < p^(v_p(k)) ≤ k, which implies k < k, an impossibility closed by omega.
uses
mondrian_prime_shape_bound,mondrian_prime_pow_gap,hp.two_le,Nat.ordProj_le,Nat.ne_of_gt· have hbound := mondrian_prime_shape_bound c p e k A hc hp hpc hk hA heq have hgap := mondrian_prime_pow_gap c p (k.factorization p) hp.two_le hpc (by omega) have hpow := Nat.ordProj_le p (Nat.ne_of_gt hk) omega
hp.dvd_iff_one_le_factorization- For a prime p and a non-zero natural number n, p divides n if and only if the exponent of p in n's prime factorization is at least 1.
Nat.ne_of_gt- A strictly positive natural number is non-zero (if 0 < k then k ≠ 0).
mondrian_prime_first_exponent_shape_bound- Under the theorem's hypotheses, if the exponent of p in k's prime factorization is 1, then the number of valid factor shapes of area A in a (c * p^e) × (c * p^e) square is at most c.
Nat.le_of_dvd- If a natural number divides a positive natural number, it is less than or equal to that number.
mondrian_prime_shape_bound- Under the theorem's hypotheses, the number of valid factor shapes of area A in a (c * p^e) × (c * p^e) square is at most (r + 1) * c, where r is the exponent of p in k's prime factorization.
mondrian_prime_pow_gap- For p ≥ 2, c < p, and r ≥ 2, the inequality (r + 1) * c < p^r holds.
hp.two_le- Every prime number is at least 2.
Nat.ordProj_le- For any prime p and non-zero natural number n, the prime power p^(v_p(n)) is at most 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_large_prime_count_not_dvd (c p e k A : ℕ) (hc : 0 < c) (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A) (heq : k * A = (c * p ^ e) ^ 2) (hcard : k ≤ (mondrian_factor_shapes (c * p ^ e) A).card) : ¬ p ∣ k := by intro hpk have hr := (hp.dvd_iff_one_le_factorization (Nat.ne_of_gt hk)).mp hpk by_cases hr1 : k.factorization p = 1 · have hbound := mondrian_prime_first_exponent_shape_bound c p e k A hc hp hpc hk hA heq hr1 have hpkle := Nat.le_of_dvd hk hpk omega · have hbound := mondrian_prime_shape_bound c p e k A hc hp hpc hk hA heq have hgap := mondrian_prime_pow_gap c p (k.factorization p) hp.two_le hpc (by omega) have hpow := Nat.ordProj_le p (Nat.ne_of_gt hk) omega