AFTD Auto-Formalizing Theoretical Domains

nus_min_card_five_eq_four

theoremverified

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

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.

  1. 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`.

    line 3

      have hno : ∀ A : Finset (ZMod 5), A.card ≤ 3 → ¬ finset_has_no_unique_sums A := by decide
  2. 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`).

    line 4

    uses le_antisymm

      refine le_antisymm ?_ ?_
  3. 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.

    line 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} : Finset (ZMod 5)) (by decide)
  4. 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.

    lines 6–9

    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⟩
  5. 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.

    lines 10–12

        · 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.

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

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