AFTD Auto-Formalizing Theoretical Domains

frobenius_extremal_family_not_mem_zero

theoremverified

If q ≥ 1, then 0 does not belong to frobenius_extremal_family n q.

Statement

theorem frobenius_extremal_family_not_mem_zero (n q : ℕ) (hq : 1 ≤ q) : 0 ∉ frobenius_extremal_family n q
Source
scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:454
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • frobenius_extremal_familyFor natural numbers n and q, frobenius_extremal_family n q is the set of natural numbers consisting of all multiples i * q for 1 ≤ i ≤ n…

Read back from the Lean

For all natural numbers $n$ and $q$, if $1 \le q$, then $0$ is not a member of frobenius_extremal_family n q.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction. Assuming 0 belongs to frobenius_extremal_family n q, expanding the definition shows that 0 must either be a multiple i * q with i ≥ 1, or equal (n - 2) * q + 1. Both cases are impossible when q ≥ 1: the multiple i * q is a product of positive integers and hence nonzero, and (n - 2) * q + 1 is at least 1.

  1. Assuming 0 is in the extremal family, either 0 = i * q for some index i ≥ 1, or 0 = (n - 2) * q + 1.

    We assume for contradiction that 0 belongs to frobenius_extremal_family n q. Unfolding the definition of the family as {i * q | 1 ≤ i ≤ n - 1} ∪ {(n - 2) * q + 1}, membership in this union simplifies via Set.mem_union and Set.mem_singleton_iff to a disjunction: either 0 = i * q for some i with 1 ≤ i ≤ n - 1, or 0 = (n - 2) * q + 1.

    lines 3–5

    uses Set.mem_union, Set.mem_singleton_iff

      intro h
      simp only [frobenius_extremal_family, Set.mem_union, Set.mem_singleton_iff] at h
      rcases h with ⟨i, hi1, -, hi0⟩ | h0
  2. The case 0 = i * q with i ≥ 1 is impossible.

    Since i ≥ 1 and q ≥ 1, both factors are nonzero by linear arithmetic (omega). By mul_ne_zero, their product i * q is nonzero, contradicting the assumption that 0 = i * q.

    lines 6–7

    uses mul_ne_zero

      · have : i * q ≠ 0 := mul_ne_zero (by omega) (by omega)
        exact this hi0.symm
  3. The case 0 = (n - 2) * q + 1 is impossible. automation

    Because q ≥ 1 and arithmetic is in the natural numbers, (n - 2) * q + 1 ≥ 1 > 0, so it cannot equal 0. Presburger arithmetic (omega) detects this contradiction and closes the goal.

    line 8

      · omega
Set.mem_union
An element belongs to the union of two sets if and only if it belongs to the first set or the second set.
Set.mem_singleton_iff
An element belongs to a singleton set {b} if and only if it equals b.
mul_ne_zero
If two elements in a structure without zero divisors are nonzero, their product is nonzero.

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

/-- Zero does not belong to the extremal family S_{n,q} when q ≥ 1. -/theorem frobenius_extremal_family_not_mem_zero (n q : ℕ) (hq : 1 ≤ q) : 0 ∉ frobenius_extremal_family n q := by  intro h  simp only [frobenius_extremal_family, Set.mem_union, Set.mem_singleton_iff] at h  rcases h with ⟨i, hi1, -, hi0⟩ | h0  · have : i * q ≠ 0 := mul_ne_zero (by omega) (by omega)    exact this hi0.symm  · omega
See it in the graphDiscuss this resultChallenge it