AFTD Auto-Formalizing Theoretical Domains

nus_min_card_seven_eq_five

theoremverified

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

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.

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

    line 3

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

    line 4

    uses le_antisymm

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

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

    lines 6–7

    uses le_csInf

      · unfold nus_min_card
        refine le_csInf ⟨5, {0,1,2,3,4}, by decide, rfl⟩ ?_
  5. 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.

    lines 8–10

        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.

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