finset_has_no_unique_sums_max_layer
Let A be NUS and let x be a rational collision-preserving weight on A. Then the set of elements of A maximizing x (i.e. {a ∈ A : x a = M} for a value M attained and dominating all of x on A) is again NUS.
Statement
theorem finset_has_no_unique_sums_max_layer {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (x : G → ℚ) (hx : finset_sum_collision_preserving A x) (M : ℚ) (hM : ∀ a ∈ A, x a ≤ M) (hMne : ∃ a ∈ A, x a = M) : finset_has_no_unique_sums (A.filter (fun a => x a = M))
- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- finset_has_no_unique_sumsA has no unique sums (is NUS): |A| ≥ 2 and every sum a + b with a, b ∈ A has at least two representations as an unordered pair from A.
- finset_unordered_sum_rep_countr_{A,2}(s): the number of unordered pairs {a, b} (a = b allowed) of elements of A with a + b = s.
- finset_sum_collision_preservingA rational-valued function x on A is collision-preserving if it satisfies every additive collision: x a + x b = x c + x d whenever a + b =…
- Used by 1
- finset_sum_collision_preserving_const_of_minimalIf A is NUS, no proper subset of A is NUS (A is inclusion-minimal), and x is a rational collision-preserving weight on A, then x is…
The proof, explained
To show that the maximal layer L = {a ∈ A : x a = M} of a collision-preserving weight on a NUS set A is again NUS, the proof relies on a rigid conservation property: if two elements of A sum to the same value as two elements of L, both must have weight M and therefore also belong to L. Applying this to a duplicated element a₀ ∈ L whose sum a₀ + a₀ has a second representation in A produces a second element in L, showing |L| ≥ 2. Furthermore, the conservation property ensures that the unordered representations of any sum p + q with p, q ∈ L in L are exactly its representations in A, so every such sum inherits at least two representations from A.
Definition of the top layer L = {a ∈ A : x a = M}, its membership characterization, and the inclusion L ⊆ A.
We work under classical logic (line 7). We define L as the subset of A where x takes its maximum value M (line 8). By definition of Finset.filter, an element a belongs to L if and only if a ∈ A and x a = M (lines 9-10). Because L is obtained by filtering A, it is a subset of A (line 11).
uses
Finset.mem_filter,Finset.filter_subsetclassical set L : Finset G := A.filter (fun a => x a = M) with hL have hmemL : ∀ a, a ∈ L ↔ a ∈ A ∧ x a = M := by intro a; rw [hL, Finset.mem_filter] have hAL : L ⊆ A := by rw [hL]; exact Finset.filter_subset _ _
Key property: any decomposition in A of a sum of two elements of L must consist entirely of elements of L.
Let p, q ∈ L and a, b ∈ A with a + b = p + q. Since p, q ∈ L, we have x p = M and x q = M. Because x is collision-preserving, x a + x b = x p + x q = 2M. Since M is the maximum of x on A, both x a ≤ M and x b ≤ M hold. Linear rational arithmetic (linarith) on these bounds and the sum forces x a = M and x b = M, so both a and b belong to L.
have key : ∀ p ∈ L, ∀ q ∈ L, ∀ a ∈ A, ∀ b ∈ A, a + b = p + q → x a = M ∧ x b = M := by intro p hp q hq a ha b hb hab obtain ⟨hpA, hpM⟩ := (hmemL p).mp hp obtain ⟨hqA, hqM⟩ := (hmemL q).mp hq have hcol : x a + x b = x p + x q := hx a ha b hb p hpA q hqA hab have ha' : x a ≤ M := hM a ha have hb' : x b ≤ M := hM b hb constructor <;> linarith
First NUS condition: the top layer L contains at least two elements (|L| ≥ 2).
We split the NUS property into two goals: showing |L| ≥ 2 and showing that every sum has at least two representations in L (line 20). By assumption, M is attained at some a₀ ∈ A, so a₀ ∈ L (lines 21-22). Since A has no unique sums, the sum a₀ + a₀ has at least two unordered representations from A, so its representation finset has cardinality > 1 (lines 23-24). Hence there is an unordered pair z in A different from {a₀, a₀} summing to a₀ + a₀ (line 25). Writing z as an unordered pair {c, d} with c, d ∈ A, we have c + d = a₀ + a₀ (lines 26-33). By the key property, x c = M and x d = M, so c, d ∈ L (line 34). Because {c, d} ≠ {a₀, a₀}, we must have c ≠ a₀ or d ≠ a₀ (lines 35-38). Either case provides an element in L distinct from a₀, proving |L| ≥ 2 (lines 39-41).
uses
Finset.exists_mem_ne,Sym2.exists,Finset.mem_filter,Finset.mk_mem_sym2_iff.mp,Sym2.lift_mk,not_or,not_not,Finset.one_lt_card.mpr,Ne.symmconstructor · obtain ⟨a₀, ha₀A, ha₀M⟩ := hMne have ha₀L : a₀ ∈ L := (hmemL a₀).mpr ⟨ha₀A, ha₀M⟩ have hrep : 2 ≤ finset_unordered_sum_rep_count A (a₀ + a₀) := hA.2 a₀ ha₀A a₀ ha₀A have hcard : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a₀ + a₀)).card := hrep obtain ⟨z, hzS, hzne⟩ := Finset.exists_mem_ne hcard (Sym2.mk a₀ a₀) obtain ⟨c, d, hcd⟩ := (Sym2.exists (α := G) (f := fun w => w = z)).mp ⟨z, rfl⟩ have hzS' : Sym2.mk c d ∈ A.sym2.filter (fun w => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ w = a₀ + a₀) := by rw [hcd]; exact hzS rw [Finset.mem_filter] at hzS' obtain ⟨hzA, hzsum⟩ := hzS' obtain ⟨hcA, hdA⟩ := Finset.mk_mem_sym2_iff.mp hzA have hsum : c + d = a₀ + a₀ := by rw [Sym2.lift_mk] at hzsum; exact hzsum obtain ⟨hcM, hdM⟩ := key a₀ ha₀L a₀ ha₀L c hcA d hdA hsum have hne : c ≠ a₀ ∨ d ≠ a₀ := by by_contra h simp only [not_or, not_not] at h exact hzne (by rw [← hcd, h.1, h.2]) rcases hne with h | h · exact Finset.one_lt_card.mpr ⟨a₀, ha₀L, c, (hmemL c).mpr ⟨hcA, hcM⟩, Ne.symm h⟩ · exact Finset.one_lt_card.mpr ⟨a₀, ha₀L, d, (hmemL d).mpr ⟨hdA, hdM⟩, Ne.symm h⟩
For any p, q ∈ L, the set of unordered pairs from L summing to p + q is identical to the set of unordered pairs from A summing to p + q.
Let p, q ∈ L. We show equality of the two sets of representations by extensionality (lines 42-49). For the forward inclusion, take an unordered pair z from A with sum p + q. For any element a in z, we write z = {a, b} for some b ∈ A; then a + b = p + q. Applying the key property, we obtain x a = M, so a ∈ L. Since this holds for every element of z, the pair z consists of elements of L (lines 50-60). For the reverse inclusion, any pair from L is already a pair from A because L ⊆ A, which implies L.sym2 ⊆ A.sym2 (lines 61-62).
uses
Finset.mem_filter,Finset.mem_sym2_iff.mpr,Sym2.mem_iff_exists.mp,Finset.mk_mem_sym2_iff.mp,Sym2.lift_mk,Finset.mem_sym2_iff.mp,Finset.sym2_mono· intro p hp q hq have hpA : p ∈ A := hAL hp have hqA : q ∈ A := hAL hq have hset : (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)) = (L.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)) := by ext z simp only [Finset.mem_filter] constructor · rintro ⟨hzA, hz⟩ refine ⟨Finset.mem_sym2_iff.mpr ?_, hz⟩ intro a ha obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp ha have hbA : b ∈ A := by have h1 : Sym2.mk a b ∈ A.sym2 := by rw [← hb]; exact hzA exact (Finset.mk_mem_sym2_iff.mp h1).2 have hab : a + b = p + q := by rw [hb, Sym2.lift_mk] at hz; exact hz exact (hmemL a).mpr ⟨Finset.mem_sym2_iff.mp hzA a ha, (key p hp q hq a (Finset.mem_sym2_iff.mp hzA a ha) b hbA hab).1⟩ · rintro ⟨hzL, hz⟩ exact ⟨Finset.sym2_mono hAL hzL, hz⟩
Second NUS condition: every sum in L has at least two representations in L, completing the proof.
By definition, the representation count of p + q in L and in A are the cardinalities of the respective sets of summing pairs (lines 63-66). Since these two sets are equal by the previous step, the representation counts are identical (line 67). Because A has no unique sums, the count in A is at least 2, and therefore the count in L is also at least 2 (line 68).
have h1 : finset_unordered_sum_rep_count L (p + q) = (L.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)).card := rfl have h2 : finset_unordered_sum_rep_count A (p + q) = (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)).card := rfl rw [h1, ← hset, ← h2] exact hA.2 p hpA q hqA
Finset.mem_filter- An element belongs to a filtered finset s.filter p if and only if it belongs to s and satisfies the predicate p.
Finset.filter_subset- Any filtered finset s.filter p is a subset of s.
Finset.exists_mem_ne- If a finite set has cardinality strictly greater than 1, then for any given element there exists an element in the set distinct from it.
Sym2.exists- There exists an element in the symmetric square satisfying a property if and only if there exist two elements whose unordered pair satisfies it.
Finset.mk_mem_sym2_iff.mp- If an unordered pair s(c, d) belongs to the symmetric square s.sym2, then both c and d belong to s.
Sym2.lift_mk- Evaluating the symmetric lift of a commutative binary operation on an unordered pair s(a, b) yields the operation applied to a and b.
not_or- The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
not_not- Double negation elimination: ¬¬p is equivalent to p.
Finset.one_lt_card.mpr- If a finset contains two distinct elements, its cardinality is strictly greater than 1 (at least 2).
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_sym2_iff.mpr- An unordered pair belongs to the symmetric square s.sym2 if every element in the pair belongs to s.
Sym2.mem_iff_exists.mp- If an element x belongs to an unordered pair z, then z = s(x, y) for some y.
Finset.mem_sym2_iff.mp- If an unordered pair belongs to s.sym2, then every element in the pair belongs to s.
Finset.sym2_mono- The symmetric square operation preserves inclusions: if s ⊆ t, then s.sym2 ⊆ t.sym2.
- In Mathlib, representations of a sum as an unordered pair from a finset A are formalized as elements of the symmetric square `A.sym2` whose sum (evaluated via `Sym2.lift`) equals the target.
- The definition `finset_has_no_unique_sums A` requires both `2 ≤ A.card` and that every sum of two elements of A has at least two representations as unordered pairs from A.
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 top layer of a collision-preserving weight on a NUS set is again NUS: this is the maximum-layer argument behind Lemma 2.1 of arXiv:2610.09349. -/theorem finset_has_no_unique_sums_max_layer {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (x : G → ℚ) (hx : finset_sum_collision_preserving A x) (M : ℚ) (hM : ∀ a ∈ A, x a ≤ M) (hMne : ∃ a ∈ A, x a = M) : finset_has_no_unique_sums (A.filter (fun a => x a = M)) := by classical set L : Finset G := A.filter (fun a => x a = M) with hL have hmemL : ∀ a, a ∈ L ↔ a ∈ A ∧ x a = M := by intro a; rw [hL, Finset.mem_filter] have hAL : L ⊆ A := by rw [hL]; exact Finset.filter_subset _ _ have key : ∀ p ∈ L, ∀ q ∈ L, ∀ a ∈ A, ∀ b ∈ A, a + b = p + q → x a = M ∧ x b = M := by intro p hp q hq a ha b hb hab obtain ⟨hpA, hpM⟩ := (hmemL p).mp hp obtain ⟨hqA, hqM⟩ := (hmemL q).mp hq have hcol : x a + x b = x p + x q := hx a ha b hb p hpA q hqA hab have ha' : x a ≤ M := hM a ha have hb' : x b ≤ M := hM b hb constructor <;> linarith constructor · obtain ⟨a₀, ha₀A, ha₀M⟩ := hMne have ha₀L : a₀ ∈ L := (hmemL a₀).mpr ⟨ha₀A, ha₀M⟩ have hrep : 2 ≤ finset_unordered_sum_rep_count A (a₀ + a₀) := hA.2 a₀ ha₀A a₀ ha₀A have hcard : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a₀ + a₀)).card := hrep obtain ⟨z, hzS, hzne⟩ := Finset.exists_mem_ne hcard (Sym2.mk a₀ a₀) obtain ⟨c, d, hcd⟩ := (Sym2.exists (α := G) (f := fun w => w = z)).mp ⟨z, rfl⟩ have hzS' : Sym2.mk c d ∈ A.sym2.filter (fun w => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ w = a₀ + a₀) := by rw [hcd]; exact hzS rw [Finset.mem_filter] at hzS' obtain ⟨hzA, hzsum⟩ := hzS' obtain ⟨hcA, hdA⟩ := Finset.mk_mem_sym2_iff.mp hzA have hsum : c + d = a₀ + a₀ := by rw [Sym2.lift_mk] at hzsum; exact hzsum obtain ⟨hcM, hdM⟩ := key a₀ ha₀L a₀ ha₀L c hcA d hdA hsum have hne : c ≠ a₀ ∨ d ≠ a₀ := by by_contra h simp only [not_or, not_not] at h exact hzne (by rw [← hcd, h.1, h.2]) rcases hne with h | h · exact Finset.one_lt_card.mpr ⟨a₀, ha₀L, c, (hmemL c).mpr ⟨hcA, hcM⟩, Ne.symm h⟩ · exact Finset.one_lt_card.mpr ⟨a₀, ha₀L, d, (hmemL d).mpr ⟨hdA, hdM⟩, Ne.symm h⟩ · intro p hp q hq have hpA : p ∈ A := hAL hp have hqA : q ∈ A := hAL hq have hset : (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)) = (L.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)) := by ext z simp only [Finset.mem_filter] constructor · rintro ⟨hzA, hz⟩ refine ⟨Finset.mem_sym2_iff.mpr ?_, hz⟩ intro a ha obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp ha have hbA : b ∈ A := by have h1 : Sym2.mk a b ∈ A.sym2 := by rw [← hb]; exact hzA exact (Finset.mk_mem_sym2_iff.mp h1).2 have hab : a + b = p + q := by rw [hb, Sym2.lift_mk] at hz; exact hz exact (hmemL a).mpr ⟨Finset.mem_sym2_iff.mp hzA a ha, (key p hp q hq a (Finset.mem_sym2_iff.mp hzA a ha) b hbA hab).1⟩ · rintro ⟨hzL, hz⟩ exact ⟨Finset.sym2_mono hAL hzL, hz⟩ have h1 : finset_unordered_sum_rep_count L (p + q) = (L.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)).card := rfl have h2 : finset_unordered_sum_rep_count A (p + q) = (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = p + q)).card := rfl rw [h1, ← hset, ← h2] exact hA.2 p hpA q hqA