AFTD Auto-Formalizing Theoretical Domains

mondrian_large_prime_count_not_dvd

theoremverified

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.

  1. 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.

    lines 5–6

    uses hp.dvd_iff_one_le_factorization, Nat.ne_of_gt

      intro hpk
      have hr := (hp.dvd_iff_one_le_factorization (Nat.ne_of_gt hk)).mp hpk
  2. 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.

    line 7

      by_cases hr1 : k.factorization p = 1
  3. The 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.

    lines 8–10

    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
  4. 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.

    lines 11–14

    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

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
See it in the graphDiscuss this resultChallenge it