finset_has_no_unique_sums
def
A 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.
Statement
def finset_has_no_unique_sums {G : Type*} [AddCommMonoid G] [DecidableEq G] (A : Finset G) : Prop
- Defined in
- arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Sec. 1 (definition of NUS: |A| ≥ 2 and r_{A,2}(s) ≥ 2 for every s ∈ A + A).
- Verified
- 09 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 19
- 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…
- finset_sum_collision_preserving_const_of_minimalIf A is NUS, no proper subset of A is NUS (A is inclusion-minimal), and x is a rational collision-preserving weight on A, then x is…
- finset_has_no_unique_sums_exists_rep_neIf 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…
- finset_has_no_unique_sums_univ_zmod_threeThe whole of Z/3Z has no unique sums.
- 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_collision_subspace_finrank_ge_twoFor a NUS set A ⊆ Z/pZ, the space of F_p-valued collision-preserving functions on A has dimension at least 2: the constant functions and…
- not_finset_has_no_unique_sums_zmod_five_pairThe set {0, 1} in Z/5Z has unique sums (0 + 0 has only one representation).
- nus_int_collision_preserving_const_of_minimalIf A is NUS, no proper subset of A is NUS, and x : G → ℤ is constant across additive collisions on A, then x is constant on A.
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- finset_has_no_unique_sums_decidableHaving no unique sums is a decidable property for finite subsets of an additive commutative monoid with decidable equality.
- nus_min_card_le_of_has_no_unique_sumsIf A is a subset of Z/pZ with no unique sums, then m(p) ≤ |A|.
- nus_min_card_le_sq_of_midpoint_balancedIf B is a midpoint-balanced subset of Z/pZ, then m(p) ≤ |B|².
- finset_has_no_unique_sums_univ_zmodFor an odd prime p, the whole of Z/pZ has no unique sums.
- nus_min_card_ge_one_add_clogFor an odd prime p, m(p) ≥ 1 + ⌈log₂ p⌉: every subset of Z/pZ with no unique sums has at least 1 + ⌈log₂ p⌉ elements.
- finset_has_no_unique_sums_sumset_of_balancedIf B is a nonempty balanced finite subset of an abelian group, then its sumset B + B has no unique sums.
- finset_is_midpoint_balanced_of_has_no_unique_sumsFor an odd prime p, every subset of Z/pZ with no unique sums is balanced.
- finset_has_no_unique_sums_max_layerLet 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}…
- 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
/-- `A` 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`. -/ def finset_has_no_unique_sums {G : Type*} [AddCommMonoid G] [DecidableEq G] (A : Finset G) : Prop := 2 ≤ A.card ∧ ∀ a ∈ A, ∀ b ∈ A, 2 ≤ finset_unordered_sum_rep_count A (a + b)