AFTD Auto-Formalizing Theoretical Domains

mondrian_divisors_card_le_two_mul_of_le_sq

theoremverified

An integer D at most c squared has at most 2c positive divisors.

Statement

theorem mondrian_divisors_card_le_two_mul_of_le_sq (D c : ℕ) (hDc : D ≤ c ^ 2) :
    D.divisors.card ≤ 2 * c
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 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • 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…

The proof, explained

If $D = 0$, the claim holds because $0$ has no positive divisors. For $D > 0$, each divisor $d$ corresponds to a unique factorization $d_1 d_2 = D$. The proof defines an injection from these factor pairs into $\{1, \dots, c\} \times \{\mathrm{true}, \mathrm{false}\}$ by sending $(d_1, d_2)$ to its minimum $\min(d_1, d_2)$ and the comparison flag $d_1 \le d_2$. Because $d_1 d_2 = D \le c^2$, the smaller factor cannot exceed $c$, so the target set has size $2c$. The injectivity of this mapping bounds the number of divisors by $2c$.

  1. The inequality holds when $D = 0$.

    If $D = 0$, the set of divisors of $D$ is empty and has cardinality $0$. Since $2c \ge 0$, the inequality $0 \le 2c$ is trivially true.

    lines 3–4

      by_cases hD : D = 0
      · simp [hD]
  2. The map $f(d_1, d_2) = (\min(d_1, d_2), d_1 \le d_2)$ maps every factor pair of $D$ into $\{1, \dots, c\} \times \mathrm{Bool}$.

    Assuming $D \ne 0$, any pair $(d_1, d_2)$ with $d_1 d_2 = D$ consists of strictly positive integers, so $\min(d_1, d_2) \ge 1$. If both factors were strictly greater than $c$, their product would satisfy $D = d_1 d_2 \ge (c + 1)^2 > c^2$, contradicting $D \le c^2$. Hence $\min(d_1, d_2) \le c$, placing the first component in the integer interval $[1, c]$, while the boolean condition $d_1 \le d_2$ trivially belongs to the universe of booleans.

    lines 5–20

    uses Nat.mem_divisorsAntidiagonal.mp, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, lt_of_lt_of_le, min_le_left, min_le_right, Nat.mul_le_mul, Finset.mem_coe, Finset.mem_product, Finset.mem_Icc, Finset.mem_univ, and_true

      let f := fun d : ℕ × ℕ => (min d.1 d.2, decide (d.1 ≤ d.2))
      have hmap : Set.MapsTo f ↑D.divisorsAntidiagonal
          ↑(Finset.Icc 1 c ×ˢ (Finset.univ : Finset Bool)) := by
        intro d hd
        obtain ⟨hprod, _⟩ := Nat.mem_divisorsAntidiagonal.mp hd
        have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2)
        have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2)
        have hmin : min d.1 d.2 ≤ c := by
          by_contra hn
          have h1 : c < d.1 := lt_of_lt_of_le (by omega : c < min d.1 d.2) (min_le_left _ _)
          have h2 : c < d.2 := lt_of_lt_of_le (by omega : c < min d.1 d.2) (min_le_right _ _)
          have hm := Nat.mul_le_mul (by omega : c + 1 ≤ d.1) (by omega : c + 1 ≤ d.2)
          nlinarith
        simp only [f, Finset.mem_coe, Finset.mem_product, Finset.mem_Icc, Finset.mem_univ,
          and_true]
        exact ⟨by omega, hmin⟩
  3. The map $f$ is injective on the divisor pairs of $D$.

    Suppose $f(x) = f(y)$ for two pairs $x, y$ in the antidiagonal of divisors of $D$. Then their minimums and their order booleans coincide. If $x_1 \le x_2$, the boolean match implies $y_1 \le y_2$, so $x_1 = \min(x_1, x_2) = \min(y_1, y_2) = y_1$. Since $x_1 x_2 = D = y_1 y_2$ and $x_1 > 0$, dividing by $x_1$ yields $x_2 = y_2$, so $x = y$. Symmetrically, if $x_1 > x_2$, then $y_1 > y_2$, giving $x_2 = y_2$ and therefore $x_1 = y_1$, which again yields $x = y$.

    lines 21–42

    uses congrArg, Nat.mem_divisorsAntidiagonal.mp, Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, min_eq_left, Prod.ext, Nat.eq_of_mul_eq_mul_left, min_eq_right, Nat.eq_of_mul_eq_mul_right

      have hinj : Set.InjOn f ↑D.divisorsAntidiagonal := by
        intro x hx y hy he
        have hm := congrArg Prod.fst he
        have hb := congrArg Prod.snd he
        dsimp [f] at hm hb
        obtain ⟨hxp, _⟩ := Nat.mem_divisorsAntidiagonal.mp hx
        obtain ⟨hyp, _⟩ := Nat.mem_divisorsAntidiagonal.mp hy
        have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2)
        have hypos : 0 < x.2 := Nat.pos_of_mul_pos_left (by omega : 0 < x.1 * x.2)
        by_cases hxord : x.1 ≤ x.2
        · have hyord : y.1 ≤ y.2 := by simpa [hxord] using hb.symm
          have hw : x.1 = y.1 := by simpa [min_eq_left hxord, min_eq_left hyord] using hm
          apply Prod.ext hw
          apply Nat.eq_of_mul_eq_mul_left hxpos
          rw [hxp, hw, hyp]
        · have hyord : ¬ y.1 ≤ y.2 := by simpa [hxord] using hb.symm
          have hw : x.2 = y.2 := by
            simpa [min_eq_right (by omega : x.2 ≤ x.1),
              min_eq_right (by omega : y.2 ≤ y.1)] using hm
          apply Prod.ext _ hw
          apply Nat.eq_of_mul_eq_mul_right hypos
          rw [hxp, hw, hyp]
  4. The number of positive divisors of $D$ is at most $2c$.

    Because $f$ injectively maps the antidiagonal divisor pairs of $D$ into $\{1, \dots, c\} \times \mathrm{Bool}$, the cardinality of the antidiagonal is at most $c \cdot 2 = 2c$. Furthermore, the antidiagonal of divisor pairs is in bijection with the divisors of $D$ via $d \mapsto (d, D / d)$, so $|D.\mathrm{divisors}|$ equals the number of antidiagonal pairs and is therefore at most $2c$.

    lines 43–45

    uses Finset.card_le_card_of_injOn, Nat.map_div_right_divisors, Finset.card_map, Nat.mul_comm

      have hc := Finset.card_le_card_of_injOn f hmap hinj
      rw [← Nat.map_div_right_divisors, Finset.card_map] at hc
      simpa [Nat.mul_comm] using hc
and_true
For any proposition $p$, the conjunction $p \wedge \mathrm{True}$ is equivalent to $p$.
congrArg
Equal arguments to a function produce equal results: if $a = b$, then $f(a) = f(b)$.
Finset.card_le_card_of_injOn
An injection between finite sets implies the cardinality of the domain is at most the cardinality of the codomain.
Finset.card_map
Mapping a finite set through an embedding preserves its cardinality.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_Icc
An element $x$ belongs to the discrete interval $[a, b]$ if and only if $a \le x$ and $x \le b$.
Finset.mem_product
A pair belongs to the Cartesian product $s \times t$ of two finsets if and only if its first component is in $s$ and its second is in $t$.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if $a < b$ and $b \le c$, then $a < c$.
min_eq_left
If $a \le b$, then $\min(a, b) = a$.
min_eq_right
If $b \le a$, then $\min(a, b) = b$.
min_le_left
The minimum of two elements is at most the first element.
min_le_right
The minimum of two elements is at most the second element.
Nat.eq_of_mul_eq_mul_left
If $n > 0$ and $n \cdot m = n \cdot k$ for natural numbers, then $m = k$.
Nat.eq_of_mul_eq_mul_right
If $m > 0$ and $n \cdot m = k \cdot m$ for natural numbers, then $n = k$.
Nat.map_div_right_divisors
Mapping each divisor $d$ of $n$ to $(d, n / d)$ produces the antidiagonal of divisor pairs of $n$.
Nat.mem_divisorsAntidiagonal.mp
A pair belongs to the antidiagonal of divisors of $n$ only if its components multiply to $n$ and $n \neq 0$.
Nat.mul_le_mul
Multiplication of natural numbers preserves non-strict inequalities: if $a \le b$ and $c \le d$, then $a \cdot c \le b \cdot d$.
Nat.mul_comm
Multiplication of natural numbers is commutative: $n \cdot m = m \cdot n$.
Nat.pos_of_mul_pos_left
If the product of two natural numbers is positive, then the second factor is positive.
Nat.pos_of_mul_pos_right
If the product of two natural numbers is positive, then the first factor is positive.
Prod.ext
Two ordered pairs are equal if and only if their respective first and second components are equal.

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_divisors_card_le_two_mul_of_le_sq (D c : ℕ) (hDc : D ≤ c ^ 2) :    D.divisors.card ≤ 2 * c := by  by_cases hD : D = 0  · simp [hD]  let f := fun d : ℕ × ℕ => (min d.1 d.2, decide (d.1 ≤ d.2))  have hmap : Set.MapsTo f ↑D.divisorsAntidiagonal      ↑(Finset.Icc 1 c ×ˢ (Finset.univ : Finset Bool)) := by    intro d hd    obtain ⟨hprod, _⟩ := Nat.mem_divisorsAntidiagonal.mp hd    have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2)    have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2)    have hmin : min d.1 d.2 ≤ c := by      by_contra hn      have h1 : c < d.1 := lt_of_lt_of_le (by omega : c < min d.1 d.2) (min_le_left _ _)      have h2 : c < d.2 := lt_of_lt_of_le (by omega : c < min d.1 d.2) (min_le_right _ _)      have hm := Nat.mul_le_mul (by omega : c + 1 ≤ d.1) (by omega : c + 1 ≤ d.2)      nlinarith    simp only [f, Finset.mem_coe, Finset.mem_product, Finset.mem_Icc, Finset.mem_univ,      and_true]    exact ⟨by omega, hmin⟩  have hinj : Set.InjOn f ↑D.divisorsAntidiagonal := by    intro x hx y hy he    have hm := congrArg Prod.fst he    have hb := congrArg Prod.snd he    dsimp [f] at hm hb    obtain ⟨hxp, _⟩ := Nat.mem_divisorsAntidiagonal.mp hx    obtain ⟨hyp, _⟩ := Nat.mem_divisorsAntidiagonal.mp hy    have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2)    have hypos : 0 < x.2 := Nat.pos_of_mul_pos_left (by omega : 0 < x.1 * x.2)    by_cases hxord : x.1 ≤ x.2    · have hyord : y.1 ≤ y.2 := by simpa [hxord] using hb.symm      have hw : x.1 = y.1 := by simpa [min_eq_left hxord, min_eq_left hyord] using hm      apply Prod.ext hw      apply Nat.eq_of_mul_eq_mul_left hxpos      rw [hxp, hw, hyp]    · have hyord : ¬ y.1 ≤ y.2 := by simpa [hxord] using hb.symm      have hw : x.2 = y.2 := by        simpa [min_eq_right (by omega : x.2 ≤ x.1),          min_eq_right (by omega : y.2 ≤ y.1)] using hm      apply Prod.ext _ hw      apply Nat.eq_of_mul_eq_mul_right hypos      rw [hxp, hw, hyp]  have hc := Finset.card_le_card_of_injOn f hmap hinj  rw [← Nat.map_div_right_divisors, Finset.card_map] at hc  simpa [Nat.mul_comm] using hc
See it in the graphDiscuss this resultChallenge it