nus_min_card_seven_eq_five
The 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).
Statement
theorem nus_min_card_seven_eq_five : nus_min_card 7 = 5- 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 proof establishes that the minimal size of a subset with no unique sums in ℤ/7ℤ is 5 by proving matching upper and lower bounds. For the upper bound, the explicit 5-element subset {0, 1, 2, 3, 4} is verified by computation to have no unique sums. For the lower bound, an exhaustive check confirms that every subset of size at most 4 fails the condition, so the infimum of all valid sizes must be at least 5.
No subset of ℤ/7ℤ with cardinality at most 4 has the no-unique-sums property. automation
Because ℤ/7ℤ is finite, the property that a subset has no unique sums is decidable. The `decide` tactic checks every subset of ℤ/7ℤ of size at most 4 by exhaustive computation and confirms that none satisfies the condition.
have hno : ∀ A : Finset (ZMod 7), A.card ≤ 4 → ¬ finset_has_no_unique_sums A := by decide
To show nus_min_card 7 = 5, it suffices to prove nus_min_card 7 ≤ 5 and 5 ≤ nus_min_card 7.
By antisymmetry of the partial order on natural numbers (`le_antisymm`), establishing the upper bound and the lower bound separately implies equality.
uses
le_antisymmrefine le_antisymm ?_ ?_The minimal cardinality of a set with no unique sums in ℤ/7ℤ is at most 5.
By `nus_min_card_le_of_has_no_unique_sums`, any subset with no unique sums witnesses an upper bound on the minimal cardinality. The 5-element subset {0, 1, 2, 3, 4} ⊆ ℤ/7ℤ is verified to have no unique sums by `decide`, which gives nus_min_card 7 ≤ 5.
uses
nus_min_card_le_of_has_no_unique_sums· exact nus_min_card_le_of_has_no_unique_sums ({0,1,2,3,4} : Finset (ZMod 7)) (by decide)
To show 5 ≤ nus_min_card 7, it suffices to show that every subset of ℤ/7ℤ with no unique sums has size at least 5.
Unfolding `nus_min_card 7` expresses it as the infimum of the sizes of all subsets with no unique sums. By `le_csInf`, 5 is a lower bound on this infimum provided the set of sizes is nonempty (witnessed by {0, 1, 2, 3, 4}, which has size 5 and is verified by `decide` to have no unique sums) and 5 is a lower bound for every candidate size.
uses
le_csInf· unfold nus_min_card refine le_csInf ⟨5, {0,1,2,3,4}, by decide, rfl⟩ ?_
Every subset of ℤ/7ℤ with no unique sums has size at least 5.
Let A be an arbitrary subset of ℤ/7ℤ with no unique sums. Suppose for contradiction that |A| < 5; then |A| ≤ 4 by linear arithmetic (`omega`). But this directly contradicts the earlier exhaustive verification that no subset of size at most 4 has the no-unique-sums property.
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, a ≤ sInf s holds whenever the set s is nonempty and a is a lower bound for every element of s.
- The exhaustive checks on lines 3, 5, and 7 are carried out by `decide`, which evaluates the decidable predicate `finset_has_no_unique_sums` over subsets of the finite group ℤ/7ℤ via computation in the Lean kernel.
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(7) = 5: the least NUS subset of Z/7Z has five elements. -/theorem nus_min_card_seven_eq_five : nus_min_card 7 = 5 := by have hno : ∀ A : Finset (ZMod 7), A.card ≤ 4 → ¬ 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,4} : Finset (ZMod 7)) (by decide) · unfold nus_min_card refine le_csInf ⟨5, {0,1,2,3,4}, by decide, rfl⟩ ?_ rintro b ⟨A, hA, rfl⟩ by_contra h exact hno A (by omega) hA