Numerical semigroups generated by arithmetic progressions

TheoremTripathi's pseudo-Frobenius formula without assuming \(d > 0\)#✓fully proved

Let \(a\), \(h\) and \(k\) be positive integers and \(d\) a natural number with \(\gcd(a, d) = 1\), and let \(q\) and \(r\) be natural numbers with \(1 \le r \le k\) and \(a - 1 = qk + r\). Let \(S\) be the set of all sums \(c_0 a + \sum_{i=1}^{k} c_i (ha + id)\) with natural numbers \(c_0, \dots, c_k\). Then the natural numbers \(y \notin S\) such that \(y + s \in S\) for every nonzero \(s \in S\) are exactly the numbers

\[y = ha \left\lfloor \frac{x - 1}{k} \right\rfloor + (h - 1)a + dx\]

with \(x\) a natural number satisfying \(a - r \le x \le a - 1\).

The hypotheses force \(d > 0\): if \(d = 0\), then \(\gcd(a, d) = a = 1\), and \(a - 1 = qk + r\) with \(r \ge 1\) is impossible.

theorem tripathi_pseudo_frobenius_arithmetic_progression_general
    (a d h k : ℕ) (ha : 0 < a) (hh : 0 < h) (hk : 0 < k)
    (hgcd : Nat.gcd a d = 1) (q r : ℕ) (hr1 : 1 ≤ r) (hrk : r ≤ k)
    (hqr : a - 1 = q * k + r)
    (S : Set ℕ)
    (hS : S = { n | ∃ c : ℕ → ℕ, (∀ i, k < i → c i = 0) ∧
      n = ∑ i ∈ Finset.range (k + 1),
        c i * (if i = 0 then a else h * a + i * d) }) :
    { x | x ∉ S ∧ ∀ s ∈ S, s ≠ 0 → x + s ∈ S } =
      { y | ∃ x : ℕ, a - r ≤ x ∧ x ≤ a - 1 ∧
        y = h * a * ((x - 1) / k) + (h - 1) * a + d * x }

Used by 1

Used byTripathi's pseudo-Frobenius formula

TheoremTripathi's pseudo-Frobenius formula#✓fully proved

Let \(a\), \(d\), \(h\) and \(k\) be positive integers with \(\gcd(a, d) = 1\), and let \(q\) and \(r\) be natural numbers with \(1 \le r \le k\) and \(a - 1 = qk + r\). Let \(S\) be the set of all sums \(c_0 a + \sum_{i=1}^{k} c_i (ha + id)\) with natural numbers \(c_0, \dots, c_k\), that is, the additive monoid generated by \(a, ha + d, \dots, ha + kd\). Then the natural numbers \(y \notin S\) such that \(y + s \in S\) for every nonzero \(s \in S\) are exactly the numbers

\[y = ha \left\lfloor \frac{x - 1}{k} \right\rfloor + (h - 1)a + dx\]

with \(x\) a natural number satisfying \(a - r \le x \le a - 1\).

The case \(a = 1\) cannot occur, since then \(a - 1 = qk + r\) with \(r \ge 1\) is impossible. When \(k \ge a\), these numbers are exactly \((h - 1)a + dx\) for \(1 \le x \le a - 1\).

theorem tripathi_pseudo_frobenius_arithmetic_progression
    (a d h k : ℕ) (ha : 0 < a) (hd : 0 < d) (hh : 0 < h) (hk : 0 < k)
    (hgcd : Nat.gcd a d = 1) (q r : ℕ) (hr1 : 1 ≤ r) (hrk : r ≤ k)
    (hqr : a - 1 = q * k + r)
    (S : Set ℕ)
    (hS : S = { n | ∃ c : ℕ → ℕ, (∀ i, k < i → c i = 0) ∧
      n = ∑ i ∈ Finset.range (k + 1),
        c i * (if i = 0 then a else h * a + i * d) }) :
    { x | x ∉ S ∧ ∀ s ∈ S, s ≠ 0 → x + s ∈ S } =
      { y | ∃ x : ℕ, a - r ≤ x ∧ x ≤ a - 1 ∧
        y = h * a * ((x - 1) / k) + (h - 1) * a + d * x }

Sources

• Amitabha Tripathi, "The Frobenius Problem for Modified Arithmetic Progressions," Journal of Integer Sequences 16 (2013), Article 13.7.4, Theorem, lines 235–238, https://cs.uwaterloo.ca/journals/JIS/VOL16/Tripathi/trip22.tex It follows from tripathi_pseudo_frobenius_arithmetic_progression_general; the hypothesis hd is unused and keeps the source's shape.

Uses 1

Proof usesTripathi's pseudo-Frobenius formula without assuming \(d > 0\)

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.