AFTD Auto-Formalizing Theoretical Domains

admissible_card_le_nat_sqrt

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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

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

    line 5

    uses Nat.le_sqrt'

      rw [Nat.le_sqrt']
  2. 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$.

    line 6

    uses admissible_card_sq_add_five_le

      have h := admissible_card_sq_add_five_le N A hA_sub hA_nonempty hA_adm
  3. $|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}$.

    line 7

    uses le_trans, Int.le_add_of_nonneg_right

      exact_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$.

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

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