finset_has_no_unique_sums_decidable
instance
Having no unique sums is a decidable property for finite subsets of an additive commutative monoid with decidable equality.
Statement
instance finset_has_no_unique_sums_decidable {G : Type*} [AddCommMonoid G] [DecidableEq G] (A : Finset G) : Decidable (finset_has_no_unique_sums A)
- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
- none listed
- 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.
- Used by 3
- nus_min_card_five_eq_fourThe minimal size of a set with no unique sums in Z/5Z is exactly 4 (witness {0,1,2,3}; no set of size ≤ 3 works).
- nus_min_card_seven_eq_fiveThe minimal size of a set with no unique sums in Z/7Z is exactly 5 (witness {0,1,2,3,4}; every set of size ≤ 4 fails).
- nus_exists_inclusion_minimal_subsetEvery 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…
Lean source view module on GitHub
/-- Having no unique sums is a decidable property for finite subsets of an additive commutative monoid with decidable equality. -/ instance finset_has_no_unique_sums_decidable {G : Type*} [AddCommMonoid G] [DecidableEq G] (A : Finset G) : Decidable (finset_has_no_unique_sums A) := by unfold finset_has_no_unique_sums infer_instance