mondrian_divisors_card_le_two_mul_of_le_sq
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- 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$.
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.
by_cases hD : D = 0 · simp [hD]
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.
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_truelet 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⟩
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$.
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_righthave 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]
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$.
uses
Finset.card_le_card_of_injOn,Nat.map_div_right_divisors,Finset.card_map,Nat.mul_commhave 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.
- The inequality $\min(d_1, d_2) \le c$ is proved by contradiction using non-linear arithmetic (`nlinarith`) to deduce $(c + 1)^2 \le d_1 d_2 = D \le c^2$, which is impossible.
- The equality between the number of divisors of $D$ and the cardinality of its divisor antidiagonal is formalized via the explicit embedding $d \mapsto (d, D / d)$ (`Nat.map_div_right_divisors`).
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_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