nus_exists_inclusion_minimal_subset
Every finite set with no unique sums contains an inclusion-minimal one: there is a subset B of A that has no unique sums and none of whose proper subsets has no unique sums.
Statement
theorem nus_exists_inclusion_minimal_subset {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) : ∃ B : Finset G, B ⊆ A ∧ finset_has_no_unique_sums B ∧ ∀ C : Finset G, C ⊂ B → ¬ finset_has_no_unique_sums C
- Source
- step towards nus_min_card_ge_near_quadratic
- Verified
- 25 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_has_no_unique_sums_decidableHaving no unique sums is a decidable property for finite subsets of an additive commutative monoid with decidable equality.
- Used by 1
- nus_min_card_ge_near_quadratic_of_rank_hadamard_boundIf every NUS set A ⊆ Z/pZ satisfies log p ≤ K(√|A| + |A|/log p)·log|A| with K ≥ 1, then m(p) ≥ (1/(32K²))(log p/log log p)² for every…
The proof, explained
The proof finds an inclusion-minimal subset by minimizing cardinality. Consider the family of all subsets of A that have no unique sums; this family is nonempty because A belongs to it. Since the family is finite, it contains an element B of minimal cardinality. If B had a proper subset C that also had no unique sums, C would belong to the family and have strictly smaller cardinality than B, contradicting the minimality of |B|.
The collection S of subsets of A having no unique sums is nonempty, as it contains A.
Enable classical reasoning for decidability. Define S as the sub-collection of the power set of A consisting of sets with no unique sums. Since A ⊆ A and A has no unique sums by hypothesis, A belongs to S.
uses
Finset.mem_filter,Finset.mem_powerset_selfclassical let S := A.powerset.filter (fun B => finset_has_no_unique_sums B) have hS : A ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_powerset_self A, hA⟩
There exists an element B ∈ S of minimal cardinality, which is a subset of A having no unique sums.
Because S is a nonempty finite set, there exists an element B ∈ S minimizing the cardinality function. Unpacking membership in S shows that B ⊆ A and B has no unique sums.
uses
Finset.exists_min_image,Finset.mem_filter,Finset.mem_powersetobtain ⟨B, hB_mem, hB_min⟩ := Finset.exists_min_image S Finset.card ⟨A, hS⟩ rw [Finset.mem_filter] at hB_mem rcases hB_mem with ⟨hBA, hB_nus⟩ rw [Finset.mem_powerset] at hBA
To show that B is inclusion-minimal, assume for contradiction that some proper subset C ⊂ B has no unique sums; then C must also belong to S.
Present B as the required witness. To show that no proper subset has no unique sums, suppose C ⊂ B does. Transitivity of inclusion (C ⊂ B ⊆ A) gives C ⊆ A. Since C has no unique sums, it satisfies the membership condition for S, so C ∈ S.
uses
Finset.mem_filter,Finset.mem_powerset.mprrefine ⟨B, hBA, hB_nus, fun C hCB hC_nus => ?_⟩ have hCA : C ⊆ A := hCB.1.trans hBA have hCS : C ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_powerset.mpr hCA, hC_nus⟩
Contradiction: B cannot minimize cardinality in S if C ∈ S is strictly smaller than B. automation
Since C ∈ S and B minimizes cardinality in S, we have |B| ≤ |C|. But C is a strict subset of B, so |C| < |B|. The linear arithmetic tactic `omega` detects that |B| ≤ |C| and |C| < |B| cannot both hold, completing the proof by contradiction.
uses
Finset.card_lt_cardhave h_le := hB_min C hCS have h_lt := Finset.card_lt_card hCB omega
Finset.mem_filter- An element belongs to a filtered sub-finset if and only if it belongs to the original finset and satisfies the filter predicate.
Finset.mem_powerset_self- Every finite set belongs to its own power set.
Finset.exists_min_image- Any nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
Finset.mem_powerset- A finite set belongs to the power set of another if and only if it is a subset of it.
Finset.mem_powerset.mpr- If a finite set is a subset of another, then it belongs to the other's power set.
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality.
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.
/-- Every NUS set contains an inclusion-minimal NUS subset (opening line of Section 2 of Hou-Yang). -/theorem nus_exists_inclusion_minimal_subset {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) : ∃ B : Finset G, B ⊆ A ∧ finset_has_no_unique_sums B ∧ ∀ C : Finset G, C ⊂ B → ¬ finset_has_no_unique_sums C := by classical let S := A.powerset.filter (fun B => finset_has_no_unique_sums B) have hS : A ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_powerset_self A, hA⟩ obtain ⟨B, hB_mem, hB_min⟩ := Finset.exists_min_image S Finset.card ⟨A, hS⟩ rw [Finset.mem_filter] at hB_mem rcases hB_mem with ⟨hBA, hB_nus⟩ rw [Finset.mem_powerset] at hBA refine ⟨B, hBA, hB_nus, fun C hCB hC_nus => ?_⟩ have hCA : C ⊆ A := hCB.1.trans hBA have hCS : C ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_powerset.mpr hCA, hC_nus⟩ have h_le := hB_min C hCS have h_lt := Finset.card_lt_card hCB omega