finset_sum_collision_preserving_const_of_minimal
If 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 constant on A.
Statement
theorem finset_sum_collision_preserving_const_of_minimal {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (hmin : ∀ B : Finset G, B ⊂ A → ¬ finset_has_no_unique_sums B) {x : G → ℚ} (hx : finset_sum_collision_preserving A x) : ∀ a ∈ A, ∀ b ∈ A, x a = x b
- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_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 =…
- finset_has_no_unique_sums_max_layerLet 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}…
- 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.
- Used by 1
- nus_int_collision_preserving_const_of_minimalIf A is NUS, no proper subset of A is NUS, and x : G → ℤ is constant across additive collisions on A, then x is constant on A.
The proof, explained
Since A is a nonempty finite set, the rational weight x attains its maximum at some element a₀ ∈ A. By a key structural lemma, the maximum-weight layer {a ∈ A | x a = x a₀} is itself a NUS set. Because A is inclusion-minimal among NUS sets, this layer cannot be a proper subset and must equal all of A. It follows that every element of A has weight x a₀, so x is constant on A.
A is nonempty.
By definition of a NUS set, A has cardinality at least 2. In particular, its cardinality is strictly positive by linear arithmetic, which implies that A is nonempty by Finset.card_pos.mp.
uses
Finset.card_pos.mphave hne : A.Nonempty := by have h := hA.1 exact Finset.card_pos.mp (by omega)
There exists an element a₀ ∈ A maximizing x on A.
Because A is a nonempty finite set and the values of x lie in the linearly ordered field ℚ, Finset.exists_max_image guarantees that x attains a maximum at some a₀ ∈ A, so x a' ≤ x a₀ for all a' ∈ A.
uses
Finset.exists_max_imageobtain ⟨a₀, ha₀, hmax⟩ := Finset.exists_max_image A x hneThe maximum-weight layer {a ∈ A | x a = x a₀} is also a NUS set.
By finset_has_no_unique_sums_max_layer, since A is NUS, x is collision-preserving on A, x a ≤ x a₀ for all a ∈ A, and the upper bound x a₀ is achieved at a₀ ∈ A, the level set of elements achieving this maximum is itself a NUS set.
uses
finset_has_no_unique_sums_max_layerhave hNUS : finset_has_no_unique_sums (A.filter (fun a => x a = x a₀)) := finset_has_no_unique_sums_max_layer hA x hx (x a₀) (fun a ha => hmax a ha) ⟨a₀, ha₀, rfl⟩
The maximum-weight layer {a ∈ A | x a = x a₀} equals all of A.
The maximum-weight layer is a subset of A by Finset.filter_subset. If it were not all of A, it would be a proper subset by Finset.ssubset_iff_subset_ne.mpr; but the minimality hypothesis hmin asserts that no proper subset of A can be NUS, which contradicts the fact that this layer is NUS. Thus the layer must be equal to A.
uses
Finset.filter_subset,Finset.ssubset_iff_subset_ne.mprhave hsub : A.filter (fun a => x a = x a₀) ⊆ A := Finset.filter_subset _ _ have heq : A.filter (fun a => x a = x a₀) = A := by by_contra hne' exact hmin _ (Finset.ssubset_iff_subset_ne.mpr ⟨hsub, hne'⟩) hNUS
The weight function x is constant on A: for all a, b ∈ A, x a = x b.
Given any a, b ∈ A, rewriting with {c ∈ A | x c = x a₀} = A shows that both a and b belong to the maximum-weight layer. By Finset.mem_filter.mp, this means x a = x a₀ and x b = x a₀, and therefore x a = x b.
uses
Finset.mem_filter.mpintro a ha b hb have ha' : x a = x a₀ := by have : a ∈ A.filter (fun a => x a = x a₀) := by rw [heq]; exact ha exact (Finset.mem_filter.mp this).2 have hb' : x b = x a₀ := by have : b ∈ A.filter (fun a => x a = x a₀) := by rw [heq]; exact hb exact (Finset.mem_filter.mp this).2 rw [ha', hb']
Finset.card_pos.mp- A finite set is nonempty if and only if its cardinality is strictly positive.
Finset.exists_max_image- A real- or linearly-ordered-valued function on a nonempty finite set attains its maximum at some element of the set.
finset_has_no_unique_sums_max_layer- If A is a NUS set and x is a collision-preserving weight on A bounded by M that attains M, the maximum-weight layer {a ∈ A | x a = M} is also a NUS set.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
Finset.ssubset_iff_subset_ne.mpr- A subset that is not equal to the superset is a strict (proper) subset.
Finset.mem_filter.mp- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
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 2.1 (rational half) of arXiv:2610.09349: a collision-preserving rational weight on an inclusion-minimal NUS set is constant. -/theorem finset_sum_collision_preserving_const_of_minimal {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (hmin : ∀ B : Finset G, B ⊂ A → ¬ finset_has_no_unique_sums B) {x : G → ℚ} (hx : finset_sum_collision_preserving A x) : ∀ a ∈ A, ∀ b ∈ A, x a = x b := by have hne : A.Nonempty := by have h := hA.1 exact Finset.card_pos.mp (by omega) obtain ⟨a₀, ha₀, hmax⟩ := Finset.exists_max_image A x hne have hNUS : finset_has_no_unique_sums (A.filter (fun a => x a = x a₀)) := finset_has_no_unique_sums_max_layer hA x hx (x a₀) (fun a ha => hmax a ha) ⟨a₀, ha₀, rfl⟩ have hsub : A.filter (fun a => x a = x a₀) ⊆ A := Finset.filter_subset _ _ have heq : A.filter (fun a => x a = x a₀) = A := by by_contra hne' exact hmin _ (Finset.ssubset_iff_subset_ne.mpr ⟨hsub, hne'⟩) hNUS intro a ha b hb have ha' : x a = x a₀ := by have : a ∈ A.filter (fun a => x a = x a₀) := by rw [heq]; exact ha exact (Finset.mem_filter.mp this).2 have hb' : x b = x a₀ := by have : b ∈ A.filter (fun a => x a = x a₀) := by rw [heq]; exact hb exact (Finset.mem_filter.mp this).2 rw [ha', hb']