finset_has_no_unique_sums_exists_rep_ne
If A has no unique sums and a, b ∈ A, then the sum a + b has a second representation c + d with c, d ∈ A all four of c, d distinct from a and b.
Statement
theorem finset_has_no_unique_sums_exists_rep_ne {G : Type*} [AddCancelCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) {a b : G} (ha : a ∈ A) (hb : b ∈ A) : ∃ c ∈ A, ∃ d ∈ A, a + b = c + d ∧ c ≠ a ∧ c ≠ b ∧ d ≠ a ∧ d ≠ b
- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
The proof, explained
Because $A$ has no unique sums, the element $a + b$ has at least two unordered sum representations as pairs from $A$. Since $\{a, b\}$ is one representation, there must exist another representation $\{u, v\}$ distinct from $\{a, b\}$ with $u, v \in A$ and $u + v = a + b$. By cancellativity of the commutative monoid, if either $u$ or $v$ matched either $a$ or $b$, the remaining elements would also be forced to match, yielding $\{u, v\} = \{a, b\}$ and creating a contradiction. Thus, choosing $c = u$ and $d = v$ provides a representation whose entries avoid both $a$ and $b$.
The finset of unordered pairs from $A$ whose sum is $a + b$ has cardinality strictly greater than 1.
Because $A$ has no unique sums (`finset_has_no_unique_sums`), the number of representations of $a + b$ as an unordered sum from $A$ is at least 2. Unfolding `finset_unordered_sum_rep_count` and applying linear arithmetic over $\mathbb{N}$ shows that this cardinality is strictly greater than 1.
classical have h2 := hA.2 a ha b hb unfold finset_unordered_sum_rep_count at h2 have h1 : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a + b)).card := by omega
There exists an unordered pair $z \in A.\text{sym2}$ summing to $a + b$ such that $z \ne s(a, b)$.
Since the finset of pairs summing to $a + b$ contains at least two elements, `Finset.exists_mem_ne` guarantees there is an element $z$ in this set distinct from the pair $s(a, b)$.
uses
Finset.exists_mem_neobtain ⟨z, hz, hz0⟩ := Finset.exists_mem_ne h1 (Sym2.mk a b)The pair $z$ has the form $s(u, v)$ with $u, v \in A$ and $u + v = a + b$.
By induction on the quotient type `Sym2` via `Sym2.ind`, the pair $z$ can be written as $s(u, v)$. Unfolding membership in the filtered finset using `Finset.mem_filter` and evaluating the sum with `Sym2.lift_mk` gives $u + v = a + b$. By `Finset.mk_mem_sym2_iff`, membership in $A.\text{sym2}$ means both $u \in A$ and $v \in A$.
uses
Finset.mem_filter,Sym2.ind,Sym2.lift_mk,Finset.mk_mem_sym2_iffrw [Finset.mem_filter] at hz induction z using Sym2.ind with | h u v => simp only [Sym2.lift_mk] at hz obtain ⟨hzA, huv⟩ := hz rw [Finset.mk_mem_sym2_iff] at hzA obtain ⟨hu, hv⟩ := hzA
Choosing $c = u$ and $d = v$ reduces the goal to proving $u \ne a$, $u \ne b$, $v \ne a$, and $v \ne b$.
We supply $u$ and $v$ as the existential witnesses. Since $u, v \in A$ and $a + b = u + v$, the membership and sum equalities are satisfied, leaving only the four distinctness requirements to prove.
refine ⟨u, hu, v, hv, huv.symm, ?_, ?_, ?_, ?_⟩$u \ne a$
Suppose, for contradiction, that $u = a$. Substituting this into $u + v = a + b$ yields $a + v = a + b$, which by left cancellation (`add_left_cancel`) implies $v = b$. This means $s(u, v) = s(a, b)$, contradicting the fact that $z \ne s(a, b)$.
uses
add_left_cancel· intro h apply hz0 have hv_eq : v = b := by rw [h] at huv exact add_left_cancel huv subst h subst hv_eq rfl
$u \ne b$
Suppose, for contradiction, that $u = b$. Rewriting $a + b$ as $b + a$ using commutativity (`add_comm`), we obtain $b + v = b + a$, which implies $v = a$ by left cancellation (`add_left_cancel`). Thus $s(u, v) = s(b, a)$, which equals $s(a, b)$ by symmetry of unordered pairs (`Sym2.eq_swap`), contradicting $z \ne s(a, b)$.
uses
add_comm,add_left_cancel,Sym2.eq_swap· intro h apply hz0 have hv_eq : v = a := by rw [h, add_comm a b] at huv exact add_left_cancel huv subst h subst hv_eq exact Sym2.eq_swap
$v \ne a$
Suppose, for contradiction, that $v = a$. Commuting the sum $a + b$ to $b + a$ (`add_comm`), the equation becomes $u + a = b + a$. By right cancellation (`add_right_cancel`), we get $u = b$. Then $s(u, v) = s(b, a) = s(a, b)$ by `Sym2.eq_swap`, contradicting $z \ne s(a, b)$.
uses
add_comm,add_right_cancel,Sym2.eq_swap· intro h apply hz0 have hu_eq : u = b := by rw [h, add_comm a b] at huv exact add_right_cancel huv subst h subst hu_eq exact Sym2.eq_swap
$v \ne b$
Suppose, for contradiction, that $v = b$. Substituting this into $u + v = a + b$ gives $u + b = a + b$, so right cancellation (`add_right_cancel`) forces $u = a$. Hence $s(u, v) = s(a, b)$, contradicting $z \ne s(a, b)$.
uses
add_right_cancel· intro h apply hz0 have hu_eq : u = a := by rw [h] at huv exact add_right_cancel huv subst h subst hu_eq rfl
add_comm- Addition in a commutative magma satisfies $a + b = b + a$.
add_left_cancel- In an additive structure with left cancellation, $a + b = a + c$ implies $b = c$.
add_right_cancel- In an additive structure with right cancellation, $a + b = c + b$ implies $a = c$.
Finset.exists_mem_ne- In any finite set with cardinality strictly greater than 1, there exists an element distinct from any specified element.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
Finset.mk_mem_sym2_iff- An unordered pair $s(a, b)$ belongs to the symmetric square of a finset $s$ if and only if both $a \in s$ and $b \in s$.
Sym2.eq_swap- The unordered pair $s(a, b)$ is equal to $s(b, a)$.
Sym2.ind- To prove a property for all elements of $\text{Sym2}(\alpha)$, it suffices to prove it for pairs of the form $s(x, y)$.
Sym2.lift_mk- Evaluating the lift of a symmetric function to $\text{Sym2}$ on an unordered pair $s(a, b)$ gives the value of the function on $(a, b)$.
- The proof formalizes unordered pairs of elements from $G$ using the symmetric square quotient type `Sym2 G`, where $s(x, y)$ denotes the unordered pair $\{x, y\}$.
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.
/-- In a NUS set every sum of two elements has a repair whose two entries avoid both summands. -/theorem finset_has_no_unique_sums_exists_rep_ne {G : Type*} [AddCancelCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) {a b : G} (ha : a ∈ A) (hb : b ∈ A) : ∃ c ∈ A, ∃ d ∈ A, a + b = c + d ∧ c ≠ a ∧ c ≠ b ∧ d ≠ a ∧ d ≠ b := by classical have h2 := hA.2 a ha b hb unfold finset_unordered_sum_rep_count at h2 have h1 : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a + b)).card := by omega obtain ⟨z, hz, hz0⟩ := Finset.exists_mem_ne h1 (Sym2.mk a b) rw [Finset.mem_filter] at hz induction z using Sym2.ind with | h u v => simp only [Sym2.lift_mk] at hz obtain ⟨hzA, huv⟩ := hz rw [Finset.mk_mem_sym2_iff] at hzA obtain ⟨hu, hv⟩ := hzA refine ⟨u, hu, v, hv, huv.symm, ?_, ?_, ?_, ?_⟩ · intro h apply hz0 have hv_eq : v = b := by rw [h] at huv exact add_left_cancel huv subst h subst hv_eq rfl · intro h apply hz0 have hv_eq : v = a := by rw [h, add_comm a b] at huv exact add_left_cancel huv subst h subst hv_eq exact Sym2.eq_swap · intro h apply hz0 have hu_eq : u = b := by rw [h, add_comm a b] at huv exact add_right_cancel huv subst h subst hu_eq exact Sym2.eq_swap · intro h apply hz0 have hu_eq : u = a := by rw [h] at huv exact add_right_cancel huv subst h subst hu_eq rfl