AFTD Auto-Formalizing Theoretical Domains

finset_has_no_unique_sums_univ_zmod

theoremverifiedformalization

For an odd prime p, the whole of Z/pZ has no unique sums.

Statement

theorem finset_has_no_unique_sums_univ_zmod {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) :
    finset_has_no_unique_sums (Finset.univ : Finset (ZMod p))
Formalizes
arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Sec. 1 (F_p itself is NUS: each s has (p+1)/2 ≥ 2 unordered representations).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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.
  • 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 4

The proof, explained

For an odd prime p, the entire group ℤ/pℤ has no unique sums, meaning that |ℤ/pℤ| ≥ 2 and every sum s = a + b has at least two representations as an unordered pair sum. Since p is an odd prime, the cardinality |ℤ/pℤ| = p is at least 3, which is ≥ 2. To find two distinct representations for any sum s, the proof branches on whether s = 1: if s = 1, the pairs {0, 1} and {2, -1} both sum to 1 and are distinct because p ≠ 2 and 1 ≠ 0; if s ≠ 1, the pairs {0, s} and {1, s - 1} both sum to s and are distinct because s ≠ 1 and 1 ≠ 0.

  1. The universe ℤ/pℤ has cardinality at least 2.

    By definition, a finset has no unique sums if its cardinality is at least 2 and every pair sum has at least two representations. Splitting the goal with `constructor`, the first requirement asks that |univ| ≥ 2. Rewriting using `Finset.card_univ` and `ZMod.card` transforms this into 2 ≤ p. Since p is prime, 2 ≤ p, and since p ≠ 2, we have 2 < p via `Nat.lt_of_le_of_ne`, which implies 2 ≤ p by `le_of_lt`.

    lines 3–6

    uses Finset.card_univ, ZMod.card, Nat.lt_of_le_of_ne, Fact.out, Ne.symm, le_of_lt

      constructor
      · rw [Finset.card_univ, ZMod.card p]
        have : 2 < p := Nat.lt_of_le_of_ne (Fact.out : p.Prime).two_le (Ne.symm hp)
        exact le_of_lt this
  2. To show every sum s = a + b in ℤ/pℤ has at least two representations, it suffices to consider separately the cases s = 1 and s ≠ 1.

    Fixing arbitrary elements a, b ∈ ℤ/pℤ, we unfold `finset_unordered_sum_rep_count` to reveal that we must show the set of unordered pairs in (ℤ/pℤ)⁽²⁾ summing to s = a + b has cardinality at least 2. We then split into two cases: s = 1 and s ≠ 1.

    lines 7–10

      · intros a _ b _
        unfold finset_unordered_sum_rep_count
        set s : ZMod p := a + b
        by_cases hs : s = 1
  3. When s = 1, it suffices to show that the unordered pairs {0, 1} and {2, -1} both sum to 1 and are distinct.

    To show the fiber has cardinality at least 2, we rewrite 2 ≤ |S| as 1 < |S| using `Nat.add_one_le_iff`. By `Finset.one_lt_card.2`, it suffices to exhibit two distinct elements in the fiber. We candidate the unordered pairs s(0, 1) and s(2, -1).

    lines 11–13

    uses Nat.add_one_le_iff, Finset.one_lt_card.2

        · rw [Nat.add_one_le_iff]
          apply Finset.one_lt_card.2
          refine ⟨s(0, 1), ?_, s(2, -1), ?_, ?_⟩
  4. Both {0, 1} and {2, -1} belong to the fiber of sums equal to s = 1.

    Unfolding membership in the filtered finset via `Finset.mem_filter`, membership in the universe holds trivially. We then check the sum conditions: 0 + 1 = 1 = s holds by `zero_add` and the hypothesis s = 1, while 2 + (-1) = 1 = s holds by ring arithmetic and s = 1.

    lines 14–22

    uses Finset.mem_filter, zero_add

          · rw [Finset.mem_filter]
            refine ⟨by simp, ?_⟩
            show (0 : ZMod p) + 1 = s
            rw [hs, zero_add]
          · rw [Finset.mem_filter]
            refine ⟨by simp, ?_⟩
            show (2 : ZMod p) + (-1) = s
            rw [hs]
            ring
  5. Assuming {0, 1} = {2, -1}, the equality branch 0 = 2 is impossible because p ≠ 2.

    By `Sym2.eq_iff`, equality of the unordered pairs {0, 1} = {2, -1} implies either (0 = 2 ∧ 1 = -1) or (0 = -1 ∧ 1 = 2). In the first branch, 0 = 2 in ℤ/pℤ implies p ∣ 2 by `CharP.cast_eq_zero_iff`. Since 2 > 0, this yields p ≤ 2 by `Nat.le_of_dvd`. Combined with 2 ≤ p for primes, antisymmetry gives p = 2, which contradicts the hypothesis p ≠ 2.

    lines 23–29

    uses Sym2.eq_iff, CharP.cast_eq_zero_iff, Nat.le_of_dvd, Fact.out, Nat.le_antisymm

          · intro h
            rw [Sym2.eq_iff] at h
            rcases h with ⟨h02, -⟩ | ⟨h0neg, -⟩
            · have hp2 : p ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h02.symm
              have hle := Nat.le_of_dvd (by decide) hp2
              have hge : 2 ≤ p := (Fact.out : p.Prime).two_le
              exact hp (Nat.le_antisymm hle hge)
  6. Assuming {0, 1} = {2, -1}, the equality branch 0 = -1 is impossible because 1 ≠ 0.

    In the second branch where 0 = -1 in ℤ/pℤ, negating both sides gives 1 = -(-1) = -0 = 0. But 1 ≠ 0 by `one_ne_zero`, yielding a contradiction.

    lines 30–34

    uses one_ne_zero

            · have : (1 : ZMod p) = 0 := by
                calc (1 : ZMod p) = - (-1) := by ring
                _ = - 0 := by rw [← h0neg]
                _ = 0 := by ring
              exact one_ne_zero this
  7. When s ≠ 1, it suffices to show that {0, s} and {1, s - 1} both sum to s and are distinct.

    Rewriting 2 ≤ |S| as 1 < |S| via `Nat.add_one_le_iff` and applying `Finset.one_lt_card.2`, it suffices to exhibit two distinct elements in the fiber. We candidate the unordered pairs s(0, s) and s(1, s - 1).

    lines 35–37

    uses Nat.add_one_le_iff, Finset.one_lt_card.2

        · rw [Nat.add_one_le_iff]
          apply Finset.one_lt_card.2
          refine ⟨s(0, s), ?_, s(1, s - 1), ?_, ?_⟩
  8. Both {0, s} and {1, s - 1} belong to the fiber of sums equal to s.

    Using `Finset.mem_filter`, membership in the universe is trivial. The sum condition 0 + s = s holds by `zero_add`, and 1 + (s - 1) = s holds by ring arithmetic.

    lines 38–45

    uses Finset.mem_filter, zero_add

          · rw [Finset.mem_filter]
            refine ⟨by simp, ?_⟩
            show (0 : ZMod p) + s = s
            exact zero_add s
          · rw [Finset.mem_filter]
            refine ⟨by simp, ?_⟩
            show (1 : ZMod p) + (s - 1) = s
            ring
  9. The unordered pairs {0, s} and {1, s - 1} are distinct when s ≠ 1.

    Assuming equality of the unordered pairs, `Sym2.eq_iff` implies either (0 = 1 ∧ s = s - 1) or (0 = s - 1 ∧ s = 1). The first case is refuted by 1 ≠ 0 via `one_ne_zero`. The second case gives s = 1, directly contradicting the assumption s ≠ 1.

    lines 46–50

    uses Sym2.eq_iff, one_ne_zero

          · intro h
            rw [Sym2.eq_iff] at h
            rcases h with ⟨h01, -⟩ | ⟨-, hs1⟩
            · exact one_ne_zero h01.symm
            · exact hs hs1
CharP.cast_eq_zero_iff
In a ring of characteristic p, the cast of a natural number x is zero if and only if p divides x.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` on a finite type equals the cardinality of the type.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.one_lt_card.2
If a finite set contains at least two distinct elements, its cardinality is strictly greater than 1.
Fact.out
Extracts the underlying proposition asserted by a `Fact` typeclass instance.
Nat.add_one_le_iff
For natural numbers, n + 1 ≤ m if and only if n < m.
Nat.le_antisymm
If n ≤ m and m ≤ n for natural numbers, then n = m.
Nat.le_of_dvd
If a natural number divides a strictly positive natural number, it is less than or equal to it.
Nat.lt_of_le_of_ne
A natural number less than or equal to another and not equal to it is strictly less than it.
Ne.symm
Disequality is symmetric: if a ≠ b, then b ≠ a.
Sym2.eq_iff
Two unordered pairs {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
ZMod.card
The cardinality of the ring ℤ/nℤ is n.
le_of_lt
A strict inequality implies the corresponding non-strict inequality.
one_ne_zero
In a nontrivial ring, 1 is not equal to 0.
zero_add
Zero is an additive identity on the left: 0 + a = a.

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

theorem finset_has_no_unique_sums_univ_zmod {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) :    finset_has_no_unique_sums (Finset.univ : Finset (ZMod p)) := by  constructor  · rw [Finset.card_univ, ZMod.card p]    have : 2 < p := Nat.lt_of_le_of_ne (Fact.out : p.Prime).two_le (Ne.symm hp)    exact le_of_lt this  · intros a _ b _    unfold finset_unordered_sum_rep_count    set s : ZMod p := a + b    by_cases hs : s = 1    · rw [Nat.add_one_le_iff]      apply Finset.one_lt_card.2      refine ⟨s(0, 1), ?_, s(2, -1), ?_, ?_⟩      · rw [Finset.mem_filter]        refine ⟨by simp, ?_⟩        show (0 : ZMod p) + 1 = s        rw [hs, zero_add]      · rw [Finset.mem_filter]        refine ⟨by simp, ?_⟩        show (2 : ZMod p) + (-1) = s        rw [hs]        ring      · intro h        rw [Sym2.eq_iff] at h        rcases h with ⟨h02, -⟩ | ⟨h0neg, -⟩        · have hp2 : p ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h02.symm          have hle := Nat.le_of_dvd (by decide) hp2          have hge : 2 ≤ p := (Fact.out : p.Prime).two_le          exact hp (Nat.le_antisymm hle hge)        · have : (1 : ZMod p) = 0 := by            calc (1 : ZMod p) = - (-1) := by ring            _ = - 0 := by rw [← h0neg]            _ = 0 := by ring          exact one_ne_zero this    · rw [Nat.add_one_le_iff]      apply Finset.one_lt_card.2      refine ⟨s(0, s), ?_, s(1, s - 1), ?_, ?_⟩      · rw [Finset.mem_filter]        refine ⟨by simp, ?_⟩        show (0 : ZMod p) + s = s        exact zero_add s      · rw [Finset.mem_filter]        refine ⟨by simp, ?_⟩        show (1 : ZMod p) + (s - 1) = s        ring      · intro h        rw [Sym2.eq_iff] at h        rcases h with ⟨h01, -⟩ | ⟨-, hs1⟩        · exact one_ne_zero h01.symm        · exact hs hs1
See it in the graphDiscuss this resultChallenge it