AFTD Auto-Formalizing Theoretical Domains

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