nus_min_card_five_eq_four
The 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).
Statement
theorem nus_min_card_five_eq_four : nus_min_card 5 = 4- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- nus_min_card_le_of_has_no_unique_sumsIf A is a subset of Z/pZ with no unique sums, then m(p) ≤ |A|.
- finset_has_no_unique_sums_univ_zmodFor an odd prime p, the whole of Z/pZ has 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.
- 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.
The proof, explained
The theorem proves that the minimal size of a subset with no unique sums in ℤ/5ℤ is 4 by establishing both inequalities nus_min_card 5 ≤ 4 and 4 ≤ nus_min_card 5 via antisymmetry. The upper bound is witnessed by the 4-element subset {0, 1, 2, 3}, verified computationally by `decide`. The lower bound holds because the set of NUS cardinalities is nonempty (witnessed by the whole space ℤ/5ℤ) and an exhaustive finite search (`decide`) confirms that no subset of size at most 3 has no unique sums.
No subset of ℤ/5ℤ of cardinality at most 3 has the no-unique-sums property. automation
The decision procedure (`decide`) exhaustively inspects all subsets of ℤ/5ℤ of size at most 3 and verifies that none of them satisfies `finset_has_no_unique_sums`.
have hno : ∀ A : Finset (ZMod 5), A.card ≤ 3 → ¬ finset_has_no_unique_sums A := by decide
To prove nus_min_card 5 = 4, it suffices to show nus_min_card 5 ≤ 4 and 4 ≤ nus_min_card 5.
Equality in the natural numbers is reduced to the two inequalities nus_min_card 5 ≤ 4 and 4 ≤ nus_min_card 5 by antisymmetry of the order (`le_antisymm`).
uses
le_antisymmrefine le_antisymm ?_ ?_The minimal cardinality is at most 4 (nus_min_card 5 ≤ 4).
The four-element subset {0, 1, 2, 3} ⊆ ℤ/5ℤ is checked by finite evaluation (`decide`) to have no unique sums. Applying `nus_min_card_le_of_has_no_unique_sums` with this witness yields the upper bound.
uses
nus_min_card_le_of_has_no_unique_sums· exact nus_min_card_le_of_has_no_unique_sums ({0,1,2,3} : Finset (ZMod 5)) (by decide)
To establish 4 ≤ nus_min_card 5, it suffices to show that every subset with no unique sums has cardinality at least 4.
After establishing the primality of 5 and unfolding `nus_min_card 5` as the infimum of the cardinalities of NUS subsets, `le_csInf` reduces the lower bound to two checks: that the set of such cardinalities is nonempty, and that 4 bounds every element from below. Nonemptiness is witnessed by the full universe ℤ/5ℤ, which has no unique sums by `finset_has_no_unique_sums_univ_zmod` since 5 is prime and 5 ≠ 2.
uses
le_csInf,finset_has_no_unique_sums_univ_zmod· haveI : Fact (Nat.Prime 5) := ⟨by norm_num⟩ unfold nus_min_card refine le_csInf ?_ ?_ · exact ⟨(Finset.univ : Finset (ZMod 5)).card, Finset.univ, finset_has_no_unique_sums_univ_zmod (by norm_num), rfl⟩
Every subset of ℤ/5ℤ with no unique sums has cardinality at least 4, completing the lower bound.
Let A be an arbitrary subset with no unique sums. If |A| < 4, then |A| ≤ 3 by integer arithmetic (`omega`). But this contradicts the helper statement `hno` established on line 3, which asserts that no subset of size at most 3 has no unique sums. Therefore, |A| ≥ 4.
· rintro b ⟨A, hA, rfl⟩ by_contra h exact hno A (by omega) hA
le_antisymm- In any partial order, if a ≤ b and b ≤ a, then a = b.
nus_min_card_le_of_has_no_unique_sums- If a finite subset A of ℤ/pℤ has no unique sums, then the minimal cardinality nus_min_card p is at most |A|.
le_csInf- In a conditionally complete lattice, if a set s is nonempty and a is a lower bound for every element of s, then a ≤ sInf s.
finset_has_no_unique_sums_univ_zmod- For any prime p ≠ 2, the entire group ℤ/pℤ (as the universal Finset) has no unique sums.
- The exhaustive check that no subset of ℤ/5ℤ of size at most 3 has no unique sums (line 3), as well as the verification that {0, 1, 2, 3} does have no unique sums (line 5), are discharged by Lean's computational evaluator `decide` by evaluating all possibilities.
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.
/-- m(5) = 4: the least NUS subset of Z/5Z has four elements. -/theorem nus_min_card_five_eq_four : nus_min_card 5 = 4 := by have hno : ∀ A : Finset (ZMod 5), A.card ≤ 3 → ¬ finset_has_no_unique_sums A := by decide refine le_antisymm ?_ ?_ · exact nus_min_card_le_of_has_no_unique_sums ({0,1,2,3} : Finset (ZMod 5)) (by decide) · haveI : Fact (Nat.Prime 5) := ⟨by norm_num⟩ unfold nus_min_card refine le_csInf ?_ ?_ · exact ⟨(Finset.univ : Finset (ZMod 5)).card, Finset.univ, finset_has_no_unique_sums_univ_zmod (by norm_num), rfl⟩ · rintro b ⟨A, hA, rfl⟩ by_contra h exact hno A (by omega) hA