Two-step closure: closed under contains all with
ProvedAddClosure.mem_of_add_closed_pairThis is a bounded, explicit form of the two-coin Frobenius (Chicken McNugget) theorem, phrased for sets closed under translations.
Let , let , and let with . Fix a bound and assume that is closed under adding and under adding as long as the result stays at most :
- ;
- .
Then every with
belongs to .
The threshold depends only on and not on ; this uniformity is what is needed when the threshold must serve a whole class of sets at once, as in Lemma 4.9 of Brakensiek–Guruswami and its bounded Remark. Taking large (or ) gives the unbounded statement. The result applies to any argument of the form "a set containing and closed under two translations contains every large element of the right residue class", e.g. numerical semigroups, reachable sums, and periodicity arguments.
Formalization Note The divisibility uses natural-number subtraction, which is exact here because . The case is allowed, where .
import Mathlib
namespace AddClosure
/-- Two-generator closure (bounded Frobenius form). Let `S ⊆ ℕ` contain `s` and be closed under
adding `p` and adding `q` whenever the result is at most `N`, with `p > 0`. Then every `m` with
`s + p q ≤ m ≤ N` and `gcd(p, q) ∣ m - s` lies in `S`. -/
theorem mem_of_add_closed_pair {S : Set ℕ} {s p q N : ℕ} (hp : 0 < p)
(hs : s ∈ S) (hP : ∀ x ∈ S, x + p ≤ N → x + p ∈ S)
(hQ : ∀ x ∈ S, x + q ≤ N → x + q ∈ S) {m : ℕ} (hm : s + p * q ≤ m) (hmN : m ≤ N)
(hg : Nat.gcd p q ∣ m - s) : m ∈ S := by sorry
end AddClosure