AFTD Auto-Formalizing Theoretical Domains

finset_sum_collision_preserving_const_of_minimal

theoremverified

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

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.

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

    lines 7–9

    uses Finset.card_pos.mp

      have hne : A.Nonempty := by
        have h := hA.1
        exact Finset.card_pos.mp (by omega)
  2. 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.

    line 10

    uses Finset.exists_max_image

      obtain ⟨a₀, ha₀, hmax⟩ := Finset.exists_max_image A x hne
  3. The 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.

    lines 11–12

    uses finset_has_no_unique_sums_max_layer

      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⟩
  4. 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.

    lines 13–16

    uses Finset.filter_subset, Finset.ssubset_iff_subset_ne.mpr

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

    lines 17–24

    uses Finset.mem_filter.mp

      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']
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

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