admissible_card_le_nat_sqrt
If A is a nonempty admissible subset of {1, ..., N}, then the cardinality of A is at most the integer square root of 6 times N.
Statement
theorem admissible_card_le_nat_sqrt (N : ℕ) (A : Finset ℕ)
(hA_sub : A ⊆ Finset.Icc 1 N) (hA_nonempty : A.Nonempty) (hA_adm : IsAdmissible A) :
A.card ≤ Nat.sqrt (6 * N)- Formalizes
- arXiv:2610.34372, Lemma 2.1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- IsAdmissibleA finite set A of positive integers is admissible if for any two subsets B and C of A, if the sum of elements in B equals the sum of…
- admissible_card_sq_add_five_leIf A is a nonempty admissible subset of {1, ..., N}, then the square of the cardinality of A plus 5 is at most 6 times N.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For every natural number $N$ and every finite set of natural numbers $A$, if $A \subseteq \{1, \dots, N\}$, $A$ is nonempty, and $A$ satisfies IsAdmissible (meaning that for any two subsets $B, C \subseteq A$, if the sum of elements in $B$ equals the sum of elements in $C$, then $B$ and $C$ have the same cardinality), then the cardinality of $A$ is at most $\lfloor \sqrt{6N} \rfloor$ (Nat.sqrt (6 * N)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To bound the cardinality $|A|$ by $\lfloor\sqrt{6N}\rfloor$, it suffices by properties of the integer square root to show $|A|^2 \le 6N$. This follows directly from the stronger inequality $|A|^2 + 5 \le 6N$ proved in `admissible_card_sq_add_five_le` for nonempty admissible subsets, since $|A|^2 \le |A|^2 + 5 \le 6N$.
It suffices to show that $|A|^2 \le 6N$.
Rewriting with `Nat.le_sqrt'` replaces the inequality $|A| \le \lfloor\sqrt{6N}\rfloor$ with the equivalent condition $|A|^2 \le 6N$.
uses
Nat.le_sqrt'rw [Nat.le_sqrt']The integer inequality $(|A| : \mathbb{Z})^2 + 5 \le 6N$ holds.
Applying the known bound `admissible_card_sq_add_five_le` to the hypotheses that $A \subseteq \{1, \dots, N\}$, $A$ is nonempty, and $A$ is admissible establishes that $(|A| : \mathbb{Z})^2 + 5 \le 6N$.
uses
admissible_card_sq_add_five_lehave h := admissible_card_sq_add_five_le N A hA_sub hA_nonempty hA_adm$|A|^2 \le 6N$, completing the proof.
Since $0 \le 5$ (checked by `decide`), `Int.le_add_of_nonneg_right` gives $(|A| : \mathbb{Z})^2 \le (|A| : \mathbb{Z})^2 + 5$. Transitivity (`le_trans`) with $(|A| : \mathbb{Z})^2 + 5 \le 6N$ yields $(|A| : \mathbb{Z})^2 \le 6N$. Finally, `exact_mod_cast` converts this integer inequality to $|A|^2 \le 6N$ in $\mathbb{N}$.
uses
le_trans,Int.le_add_of_nonneg_rightexact_mod_cast le_trans (Int.le_add_of_nonneg_right (by decide)) h
Nat.le_sqrt'- For natural numbers $m$ and $n$, $m \le \lfloor\sqrt{n}\rfloor$ if and only if $m^2 \le n$.
admissible_card_sq_add_five_le- For any nonempty admissible subset $A \subseteq \{1, \dots, N\}$, the integer inequality $(|A| : \mathbb{Z})^2 + 5 \le 6N$ holds.
le_trans- If $a \le b$ and $b \le c$, then $a \le c$.
Int.le_add_of_nonneg_right- For integers $a$ and $b$, if $0 \le b$, then $a \le a + b$.
- The tactic `exact_mod_cast` automatically handles the cast between the integer inequality and the goal over natural numbers.
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.
/-- The cardinality of a nonempty admissible subset of {1, ..., N} is at most sqrt(6N). -/theorem admissible_card_le_nat_sqrt (N : ℕ) (A : Finset ℕ) (hA_sub : A ⊆ Finset.Icc 1 N) (hA_nonempty : A.Nonempty) (hA_adm : IsAdmissible A) : A.card ≤ Nat.sqrt (6 * N) := by rw [Nat.le_sqrt'] have h := admissible_card_sq_add_five_le N A hA_sub hA_nonempty hA_adm exact_mod_cast le_trans (Int.le_add_of_nonneg_right (by decide)) h