AFTD Auto-Formalizing Theoretical Domains

frobenius_extremal_family_mem_generator

theoremverified

If n ≥ 2, then q belongs to the extremal set family frobenius_extremal_family n q.

Statement

theorem frobenius_extremal_family_mem_generator (n q : ℕ) (hn : 2 ≤ n) : q ∈ frobenius_extremal_family n q
Source
scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:454
Verified
27 Oct 2026
Axioms
Quot.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 $2 \le n$, then $q$ belongs to 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 extremal family $S_{n,q}$ is defined as the union of multiples $\{i \cdot q \mid 1 \le i \le n - 1\}$ and a singleton. To show $q \in S_{n,q}$, it suffices to show that $q$ is in the first set. Taking $i = 1$ works because $1 \le n - 1$ holds whenever $n \ge 2$, and $1 \cdot q = q$.

  1. It suffices to show that $q$ belongs to the set of multiples $\{x \mid \exists i, 1 \le i \le n - 1 \land x = i \cdot q\}$.

    By definition, the extremal family `frobenius_extremal_family n q` is the union of $\{x \mid \exists i, 1 \le i \le n - 1 \land x = i \cdot q\}$ and the singleton $\{(n - 2) \cdot q + 1\}$. Applying `left` reduces the goal to showing membership in the first set.

    lines 3–4

      unfold frobenius_extremal_family
      left
  2. $q$ belongs to the set of multiples $\{x \mid \exists i, 1 \le i \le n - 1 \land x = i \cdot q\}$.

    We choose the witness $i = 1$. The three required conditions follow directly: $1 \le 1$ holds by reflexivity (`le_refl`), $1 \le n - 1$ follows from the hypothesis $n \ge 2$ by linear integer arithmetic (`omega`), and $q = 1 \cdot q$ simplifies immediately (`simp`).

    line 5

    uses le_refl

      exact ⟨1, le_refl 1, by omega, by simp⟩
le_refl
Inequality in a preorder is reflexive: $a \le a$ for any $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

/-- The generator q belongs to the extremal family S_{n,q} when n ≥ 2. -/theorem frobenius_extremal_family_mem_generator (n q : ℕ) (hn : 2 ≤ n) : q ∈ frobenius_extremal_family n q := by  unfold frobenius_extremal_family  left  exact ⟨1, le_refl 1, by omega, by simp⟩
See it in the graphDiscuss this resultChallenge it