AFTD Auto-Formalizing Theoretical Domains

finset_has_no_unique_sums_max_layer

theoremverified

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

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.

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

    lines 7–11

    uses Finset.mem_filter, Finset.filter_subset

      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 _ _
  2. 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.

    lines 12–19

      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
  3. 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).

    lines 20–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.symm

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

    lines 42–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⟩
  5. 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).

    lines 63–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.

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

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