admissible_card_sq_add_five_le
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.
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.
induction' m with m ih · simp
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.
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]
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.
uses
mul_add,Finset.sum_range_id_mul_tworw [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 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`).
uses
Finset.Nonempty.card_pos,pairwiseDisjoint_k_sum_of_isAdmissible,Finset.card_biUnionhave 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
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.
uses
Finset.mem_range,card_powersetCard_image_sum_ge,Finset.sum_le_sumhave 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
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.
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_zerohave 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
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.
uses
le_trans,Nat.mul_le_mul_left,admissible_card_sq_add_five_le_sum_formula,Nat.le_of_mul_le_mul_lefthave 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
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.
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.
- The helper lemma `admissible_card_sq_add_five_le_sum_formula` evaluates the polynomial sum 6 * ∑_{k=0}^m (k(m - k) + 1) purely via induction and finite-sum identities, which corresponds on paper to expanding the sum as (m + 1) + m ∑ k - ∑ k^2.
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.
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