AFTD Auto-Formalizing Theoretical Domains

admissible_card_sq_add_five_le

theoremverifiedformalization

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

Statement

theorem admissible_card_sq_add_five_le (N : ℕ) (A : Finset ℕ)
    (hA_sub : A ⊆ Finset.Icc 1 N) (hA_nonempty : A.Nonempty) (hA_adm : IsAdmissible A) :
    (A.card : ℤ) ^ 2 + 5 ≤ 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…
  • card_powersetCard_image_sum_geFor any finite set A of natural numbers and any k ≤ |A|, the number of distinct sums of k-element subsets of A is at least k(|A| - k) + 1.
  • pairwiseDisjoint_k_sum_of_isAdmissibleIf A is an admissible set of positive integers, then for any distinct integers k₁ and k₂, the set of sums of k₁-element subsets of A and…
  • sum_le_card_mul_of_subset_IccIf A is a subset of {1, ..., N} and B is a subset of A, then the sum of the elements of B is at most the cardinality of A multiplied by N.
Used by 1
  • admissible_card_le_nat_sqrtIf 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.

Read back from the Lean

For every natural number $N$ and every finite set of natural numbers $A$, if: 1. $A \subseteq \{1, \dots, N\}$ (i.e., $A \subseteq \mathrm{Icc}(1, N)$), 2. $A$ is nonempty, and 3. $A$ is admissible (that is, for any two subsets $B, C \subseteq A$, if the sum of elements in $B$ equals the sum of elements in $C$, then $|B| = |C|$), then $(|A|)^2 + 5 \le 6N$ holds in the integers.

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

For an admissible set A ⊆ {1, ..., N}, any two subsets with equal sums must have the same size, which implies that the sets S_k of sums of k-element subsets are pairwise disjoint for all 0 ≤ k ≤ |A|. The cardinality of their union is therefore ∑_{k=0}^{|A|} |S_k|, bounded below by ∑_{k=0}^{|A|} (k(|A| - k) + 1) using a lower bound on k-element subset sums. On the other hand, all such sums lie in {0, ..., |A|N}, giving an upper bound of |A|N + 1. Multiplying by 6 and applying the polynomial sum identity 6 * ∑_{k=0}^m (k(m - k) + 1) = m(m^2 + 5) + 6 yields |A|(|A|^2 + 5) ≤ |A|(6N), from which cancelling |A| > 0 yields |A|^2 + 5 ≤ 6N.

  1. The base case m = 0 of the polynomial sum identity holds: 6 * (0 * 0 + 1) = 0 * (0^2 + 5) + 6.

    We prove the sum identity 6 * ∑_{k=0}^m (k(m - k) + 1) = m(m^2 + 5) + 6 by induction on m. In the base case m = 0, the sum has only the single term k = 0, giving 6 * 1 = 6 on the left and 0 + 6 = 6 on the right.

    lines 3–4

      induction' m with m ih
      · simp
  2. In the induction step, the sum for m + 1 splits into the sum for m, the arithmetic sum ∑_{x=0}^m x, and the boundary term 1.

    Using `Finset.sum_range_succ`, we isolate the last term k = m + 1, which evaluates to (m + 1) * 0 + 1 = 1. For each index x ≤ m, the term x(m + 1 - x) + 1 expands to (x(m - x) + 1) + x. Splitting the sum across this addition decomposes the sum into ∑_{x=0}^m (x(m - x) + 1) + ∑_{x=0}^m x.

    lines 5–17

    uses Finset.sum_range_succ, Finset.sum_add_distrib, Finset.sum_congr, Finset.mem_range, mul_add, mul_one

      · rw [Finset.sum_range_succ]
        have hlast : (m + 1) * (m + 1 - (m + 1)) + 1 = 1 := by simp
        rw [hlast]
        have hstep : ∑ x ∈ Finset.range (m + 1), (x * (m + 1 - x) + 1) =
            (∑ x ∈ Finset.range (m + 1), (x * (m - x) + 1)) + ∑ x ∈ Finset.range (m + 1), x := by
          rw [← Finset.sum_add_distrib]
          apply Finset.sum_congr rfl
          intro x hx
          simp only [Finset.mem_range] at hx
          have : m + 1 - x = (m - x) + 1 := by omega
          rw [this, mul_add, mul_one]
          omega
        rw [hstep]
  3. The induction step holds: 6 * ∑_{k=0}^{m+1} (k(m + 1 - k) + 1) = (m + 1)((m + 1)^2 + 5) + 6.

    Multiplying the decomposed sum by 6, we apply the induction hypothesis `ih` to the first part, replacing 6 * ∑_{k=0}^m (k(m - k) + 1) with m(m^2 + 5) + 6. We rewrite 6 * ∑_{x=0}^m x as 3 * (2 * ∑_{x=0}^m x) and evaluate the inner term as (m + 1) * m using the standard identity for the sum of the first m integers (`Finset.sum_range_id_mul_two`). Ring arithmetic confirms that the resulting expressions on both sides are algebraically equal polynomials in m.

    lines 18–24

    uses mul_add, Finset.sum_range_id_mul_two

        rw [mul_add, mul_add, ih]
        have hsum := Finset.sum_range_id_mul_two (m + 1)
        have : m + 1 - 1 = m := by omega
        rw [this] at hsum
        have h6 : 6 * ∑ x ∈ Finset.range (m + 1), x = 3 * ((∑ x ∈ Finset.range (m + 1), x) * 2) := by ring
        rw [h6, hsum]
        ring
  4. The sets S_k of subset sums of size k from A (for 0 ≤ k ≤ |A|) are pairwise disjoint, and the size of their union is the sum of their individual sizes.

    Since A is nonempty, |A| > 0. By definition, A is admissible if any two subsets with the same element sum have the same cardinality. Hence, if k₁ ≠ k₂, no sum of k₁ elements can equal a sum of k₂ elements (`pairwiseDisjoint_k_sum_of_isAdmissible`). The size of their union is therefore the sum of the sizes of each S_k (`Finset.card_biUnion`).

    lines 30–38

    uses Finset.Nonempty.card_pos, pairwiseDisjoint_k_sum_of_isAdmissible, Finset.card_biUnion

      have hm : 0 < A.card := Finset.Nonempty.card_pos hA_nonempty
      have hdisj : (↑(Finset.range (A.card + 1)) : Set ℕ).PairwiseDisjoint
          (fun k => (A.powersetCard k).image (Finset.sum · id)) := by
        intro i hi j hj hij
        exact pairwiseDisjoint_k_sum_of_isAdmissible hA_adm hij
      have hcard_union : ((Finset.range (A.card + 1)).biUnion
          (fun k => (A.powersetCard k).image (Finset.sum · id))).card =
          ∑ k ∈ Finset.range (A.card + 1), ((A.powersetCard k).image (Finset.sum · id)).card :=
        Finset.card_biUnion hdisj
  5. The union of the sets S_k contains at least ∑_{k=0}^{|A|} (k(|A| - k) + 1) elements.

    For every k ≤ |A|, the number of distinct sums of k elements from A is bounded below by k(|A| - k) + 1 via `card_powersetCard_image_sum_ge`. Summing these lower bounds over all k from 0 to |A| bounds the cardinality of the disjoint union from below.

    lines 39–47

    uses Finset.mem_range, card_powersetCard_image_sum_ge, Finset.sum_le_sum

      have h_term_le : ∀ k ∈ Finset.range (A.card + 1),
          k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card := by
        intro k hk
        simp only [Finset.mem_range] at hk
        exact card_powersetCard_image_sum_ge A k (by omega)
      have hsum_le_card : ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤
          ((Finset.range (A.card + 1)).biUnion (fun k => (A.powersetCard k).image (Finset.sum · id))).card := by
        rw [hcard_union]
        exact Finset.sum_le_sum h_term_le
  6. The union of the sets S_k is a subset of {0, ..., |A| * N}, so its cardinality is at most |A| * N + 1.

    Since every element of A is at most N, any subset sum of A is between 0 and |A| * N (`sum_le_card_mul_of_subset_Icc`). Thus, all generated subset sums belong to the interval {0, ..., |A| * N}. Since this interval contains |A| * N + 1 integers, the union has cardinality at most |A| * N + 1.

    lines 48–60

    uses Finset.mem_biUnion, Finset.mem_range, Finset.mem_image, Finset.mem_powersetCard, Finset.mem_Icc, Nat.zero_le, sum_le_card_mul_of_subset_Icc, Finset.card_le_card, Nat.card_Icc, tsub_zero

      have h_sub_Icc : (Finset.range (A.card + 1)).biUnion
          (fun k => (A.powersetCard k).image (Finset.sum · id)) ⊆ Finset.Icc 0 (A.card * N) := by
        intro x hx
        simp only [Finset.mem_biUnion, Finset.mem_range, Finset.mem_image, Finset.mem_powersetCard] at hx
        rcases hx with ⟨k, hk, B, ⟨hB_sub, hB_card⟩, rfl⟩
        rw [Finset.mem_Icc]
        refine ⟨Nat.zero_le _, ?_⟩
        exact sum_le_card_mul_of_subset_Icc N A hA_sub B hB_sub
      have hcard_le : ((Finset.range (A.card + 1)).biUnion
          (fun k => (A.powersetCard k).image (Finset.sum · id))).card ≤ A.card * N + 1 := by
        have := Finset.card_le_card h_sub_Icc
        simp only [Nat.card_Icc, tsub_zero] at this
        exact this
  7. The natural number inequality |A|^2 + 5 ≤ 6 * N holds.

    Chaining the lower and upper bounds gives ∑_{k=0}^{|A|} (k(|A| - k) + 1) ≤ |A| * N + 1. Multiplying both sides by 6 and rewriting the left-hand side with our sum formula gives |A|(|A|^2 + 5) + 6 ≤ 6(|A| * N + 1) = |A|(6N) + 6. Subtracting 6 yields |A|(|A|^2 + 5) ≤ |A|(6N). Since |A| > 0, cancelling |A| from both sides leaves |A|^2 + 5 ≤ 6N.

    lines 61–68

    uses le_trans, Nat.mul_le_mul_left, admissible_card_sq_add_five_le_sum_formula, Nat.le_of_mul_le_mul_left

      have hsum_le : ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤ A.card * N + 1 :=
        le_trans hsum_le_card hcard_le
      have hmul_le : 6 * ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤ 6 * (A.card * N + 1) :=
        Nat.mul_le_mul_left 6 hsum_le
      rw [admissible_card_sq_add_five_le_sum_formula] at hmul_le
      have : 6 * (A.card * N + 1) = A.card * (6 * N) + 6 := by ring
      have hmul_le' : A.card * (A.card ^ 2 + 5) ≤ A.card * (6 * N) := by omega
      have hle : A.card ^ 2 + 5 ≤ 6 * N := Nat.le_of_mul_le_mul_left hmul_le' hm
  8. The inequality holds in the integers: (|A| : ℤ)^2 + 5 ≤ 6 * N.

    Casting the inequality |A|^2 + 5 ≤ 6N from natural numbers to integers completes the proof of the theorem.

    lines 69–71

      have hcast : ((A.card ^ 2 + 5 : ℕ) : ℤ) ≤ ((6 * N : ℕ) : ℤ) := by exact_mod_cast hle
      push_cast at hcast
      exact hcast
admissible_card_sq_add_five_le_sum_formula
The algebraic identity 6 * ∑_{k=0}^m (k(m - k) + 1) = m(m^2 + 5) + 6.
Finset.sum_range_succ
A sum over the range 0, ..., n + 1 equals the sum over 0, ..., n plus the term at index n.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions equals the sum of each function separately.
Finset.sum_congr
Two sums over equal finsets are equal if their summands agree on every element.
mul_add
Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
mul_one
Multiplication by 1 on the right is the identity: a * 1 = a.
Finset.sum_range_id_mul_two
Twice the sum of the first n natural numbers equals n * (n - 1).
Finset.Nonempty.card_pos
A nonempty finite set has strictly positive cardinality.
pairwiseDisjoint_k_sum_of_isAdmissible
For an admissible set A, subsets of different cardinalities have disjoint sets of subset sums.
Finset.card_biUnion
The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
Finset.mem_range
An element k belongs to Finset.range n if and only if k < n.
card_powersetCard_image_sum_ge
The number of distinct subset sums of size k from a set A is at least k * (|A| - k) + 1.
Finset.sum_le_sum
If each summand f(i) is bounded by g(i), then the sum of f(i) is bounded by the sum of g(i).
Finset.mem_biUnion
An element belongs to a finset biUnion if and only if it belongs to one of the component sets.
Finset.mem_image
An element y is in the image f(s) if and only if y = f(x) for some x in s.
Finset.mem_powersetCard
A subset belongs to powersetCard n s if and only if it is contained in s and has cardinality n.
Finset.mem_Icc
An element x is in the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Nat.zero_le
Every natural number is greater than or equal to zero.
sum_le_card_mul_of_subset_Icc
The sum of any subset of A, where A ⊆ {1, ..., N}, is bounded above by |A| * N.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Nat.card_Icc
The cardinality of the integer interval [a, b] is b + 1 - a.
tsub_zero
Subtracting zero from any element in an ordered subtractive structure leaves it unchanged: a - 0 = a.
le_trans
Transitivity of the partial order: if a ≤ b and b ≤ c, then a ≤ c.
Nat.mul_le_mul_left
Multiplying both sides of an inequality by a natural number preserves the inequality: if n ≤ m, then k * n ≤ k * m.
Nat.le_of_mul_le_mul_left
If c * a ≤ c * b and c > 0, then a ≤ b for 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

lemma admissible_card_sq_add_five_le_sum_formula (m : ℕ) :    6 * ∑ k ∈ Finset.range (m + 1), (k * (m - k) + 1) = m * (m ^ 2 + 5) + 6 := by  induction' m with m ih  · simp  · rw [Finset.sum_range_succ]    have hlast : (m + 1) * (m + 1 - (m + 1)) + 1 = 1 := by simp    rw [hlast]    have hstep : ∑ x ∈ Finset.range (m + 1), (x * (m + 1 - x) + 1) =        (∑ x ∈ Finset.range (m + 1), (x * (m - x) + 1)) + ∑ x ∈ Finset.range (m + 1), x := by      rw [← Finset.sum_add_distrib]      apply Finset.sum_congr rfl      intro x hx      simp only [Finset.mem_range] at hx      have : m + 1 - x = (m - x) + 1 := by omega      rw [this, mul_add, mul_one]      omega    rw [hstep]    rw [mul_add, mul_add, ih]    have hsum := Finset.sum_range_id_mul_two (m + 1)    have : m + 1 - 1 = m := by omega    rw [this] at hsum    have h6 : 6 * ∑ x ∈ Finset.range (m + 1), x = 3 * ((∑ x ∈ Finset.range (m + 1), x) * 2) := by ring    rw [h6, hsum]    ring/-- The cardinality m of a nonempty admissible subset of {1, ..., N} satisfies m^2 + 5 <= 6N. -/theorem admissible_card_sq_add_five_le (N : ℕ) (A : Finset ℕ)    (hA_sub : A ⊆ Finset.Icc 1 N) (hA_nonempty : A.Nonempty) (hA_adm : IsAdmissible A) :    (A.card : ℤ) ^ 2 + 5 ≤ 6 * N := by  have hm : 0 < A.card := Finset.Nonempty.card_pos hA_nonempty  have hdisj : (↑(Finset.range (A.card + 1)) : Set ℕ).PairwiseDisjoint      (fun k => (A.powersetCard k).image (Finset.sum · id)) := by    intro i hi j hj hij    exact pairwiseDisjoint_k_sum_of_isAdmissible hA_adm hij  have hcard_union : ((Finset.range (A.card + 1)).biUnion      (fun k => (A.powersetCard k).image (Finset.sum · id))).card =      ∑ k ∈ Finset.range (A.card + 1), ((A.powersetCard k).image (Finset.sum · id)).card :=    Finset.card_biUnion hdisj  have h_term_le : ∀ k ∈ Finset.range (A.card + 1),      k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card := by    intro k hk    simp only [Finset.mem_range] at hk    exact card_powersetCard_image_sum_ge A k (by omega)  have hsum_le_card : ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤      ((Finset.range (A.card + 1)).biUnion (fun k => (A.powersetCard k).image (Finset.sum · id))).card := by    rw [hcard_union]    exact Finset.sum_le_sum h_term_le  have h_sub_Icc : (Finset.range (A.card + 1)).biUnion      (fun k => (A.powersetCard k).image (Finset.sum · id)) ⊆ Finset.Icc 0 (A.card * N) := by    intro x hx    simp only [Finset.mem_biUnion, Finset.mem_range, Finset.mem_image, Finset.mem_powersetCard] at hx    rcases hx with ⟨k, hk, B, ⟨hB_sub, hB_card⟩, rfl⟩    rw [Finset.mem_Icc]    refine ⟨Nat.zero_le _, ?_⟩    exact sum_le_card_mul_of_subset_Icc N A hA_sub B hB_sub  have hcard_le : ((Finset.range (A.card + 1)).biUnion      (fun k => (A.powersetCard k).image (Finset.sum · id))).card ≤ A.card * N + 1 := by    have := Finset.card_le_card h_sub_Icc    simp only [Nat.card_Icc, tsub_zero] at this    exact this  have hsum_le : ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤ A.card * N + 1 :=    le_trans hsum_le_card hcard_le  have hmul_le : 6 * ∑ k ∈ Finset.range (A.card + 1), (k * (A.card - k) + 1) ≤ 6 * (A.card * N + 1) :=    Nat.mul_le_mul_left 6 hsum_le  rw [admissible_card_sq_add_five_le_sum_formula] at hmul_le  have : 6 * (A.card * N + 1) = A.card * (6 * N) + 6 := by ring  have hmul_le' : A.card * (A.card ^ 2 + 5) ≤ A.card * (6 * N) := by omega  have hle : A.card ^ 2 + 5 ≤ 6 * N := Nat.le_of_mul_le_mul_left hmul_le' hm  have hcast : ((A.card ^ 2 + 5 : ℕ) : ℤ) ≤ ((6 * N : ℕ) : ℤ) := by exact_mod_cast hle  push_cast at hcast  exact hcast
See it in the graphDiscuss this resultChallenge it