The Frobenius Problem for Modified Arithmetic Progressions

Amitabha Tripathi Department of Mathematics Indian Institute of Technology Hauz Khas, New Delhi – 110016 India

               atripath@maths.iitd.ac.in

Abstract

For a set of positive and relatively prime integers A, let Γ(A) denote the set of integers obtained by taking all nonnegative integer linear combinations of integers in A. Then there are finitely many positive integers that do not belong to Γ(A). For the modified arithmetic progression A = {a, ha + d, ha + 2d, …, ha + kd}, gcd(a, d) = 1, we determine the largest integer g(A) that does not belong to Γ(A), and the number of integers n(A) that do not belong to Γ(A). We also determine the set of integers S^{⋆}(A) that do not belong to Γ(A) which, when added to any positive integer in Γ(A), result in an integer in Γ(A). Our results generalize the corresponding results for arithmetic progressions.

1 Introduction

Given a finite set A = {a_{1}, …, a_{k}} of positive integers with gcd A := gcd(a_{1}, …, a_{k}) = 1, let Γ(A) := {a_{1}x_{1} + ⋯ + a_{k}x_{k} : x_{i} ≥ 0} and Γ^{⋆}(A) = Γ(A) \ {0}. It is well known that Γ^{c}(A) := ℕ \ Γ(A) is finite. Although it was Sylvester [9] who first asked to determine

g(A) := max Γ^{c}(A),

and who showed that g(a_{1}, a_{2}) = (a_{1} − 1)(a_{2} − 1) − 1, it was Frobenius who was largely instrumental in giving this problem the early recognition, and it is after him that the problem is named. Ramírez-Alfonsín’s monograph on the Frobenius problem [5] gives an extensive survey. Related to the Frobenius problem is the problem of determining n(A) := |Γ^{c}(A)|. As in the case of determining g(A), it was Sylvester who showed that n(a_{1}, a_{2}) = \frac{1}{2}(a_{1}−1)(a_{2}−1).

Tripathi [11] introduced the following variation of the Frobenius problem. Let

S^{⋆}(A) := {n ∈ Γ^{c}(A) : n + Γ^{⋆}(A) ⊂ Γ^{⋆}(A)}.

Since g(A) is the largest integer in S^{⋆}(A), the determination of S^{⋆}(A) also provides the resolution of g(A). For the sake of convenience, we recall the following essential result regarding S^{⋆}(A) from [11]. Fix a ∈ A, and let m_{C} denote the smallest integer in Γ(A) ∩ C, where C denotes a nonzero residue class modulo a. If 𝒞 denotes the set of all nonzero residue classes modulo a, then

S^{⋆}(A) ⊆ {m_{C} − a : C ∈ 𝒞 }.  (1)

Moreover, if (x) denotes the residue class of x modulo a and m_{x} the least integer in Γ(A)∩(x), then

m_{j} − a ∈ S^{⋆}(A) ⟺ m_{j} − a ≥ m_{j+i} − m_{i} for 1 ≤ i ≤ a − 1.  (2)

Observe that S^{⋆}(A) ≠ ∅; in fact, g(A) is the largest integer in S^{⋆}(A). A complete description of S^{⋆}(A) would therefore lead to the determination of g(A).

The functions g and n are easily determined from the values of m_{C} by Lemma 1. Brauer and Shockley [2] proved (i) and Selmer [8] proved (ii); a short proof of both results may be found in [10].

Lemma 1. ([2, 8]) Let a ∈ A. Then

(i) g(A) = max_{C} m_{C} − a, the maximum taken over all nonzero classes C modulo a;

(ii) n(A) = \frac{1}{a} ∑_{C} m_{C} − \frac{1}{2}(a − 1), the sum taken over all nonzero classes C modulo a.

In cases when all but one integer in A have a nontrivial divisor, the following reduction formulae given by Lemma 2 is useful. Johnson [4] gave the reduction formulae for g(A) and Rødseth [7] for n(A); a short proof of both results may be found in [12].

Lemma 2. ([4, 7]) Let a ∈ A, let d = gcd (A \ \{a\}), and define A′ := \frac{1}{d}(A \ \{a\}).

(i) g(A) = d · g(A′ ∪ {a}) + a(d − 1);

(ii) n(A) = d · n(A′ ∪ \{a\}) + \frac{1}{2}(a − 1)(d − 1).

In this article, we determine g(A), n(A) and S^{⋆}(A) for the modified arithmetic progression A = {a, ha + d, ha + 2d, …, ha + kd} with gcd(a, d) = 1.

2 The case A = {a, ha + d, ha + 2d, …, ha + kd}

For arithmetic progressions, Roberts [6] determined g(A), later simplified by Bateman [1], while Grant [3] determined n(A). A simple proof for both these results using Lemma 1 can be found in [10]. In fact, it is also possible to determine S^{⋆}(A) in this case; see [11]. The result about g(A) and n(A) when A consists of terms in arithmetic progression can be modified or extended in many ways. One such modification is to consider A = {a, ha + d, ha+2d, …, ha+kd} with gcd(a, d) = 1 and h, k ≥ 1. The result for g(A) is due to Selmer [8], but we provide a simpler proof that also leads to other results.

Henceforth let A = {a, ha + d, ha + 2d, …, ha + kd} with gcd(a, d) = 1 and h, k ≥ 1. Then g(A) denotes the largest N such that

ax_{0}+(ha+d)x_{1}+(ha+2d)x_{2}+⋯+(ha+kd)x_{k} = a (x_{0} + h ∑_{i=1}^{k} x_{i})+d (∑_{i=1}^{k} ix_{i}) = N (3)

has no solution in nonnegative integers, and n(A) the number of such integers N.

Lemma 3. For each x, 1 ≤ x ≤ a−1, the least positive integer of the form given by equation (3) in the class dx mod a is given by ha (1 + ⌊\frac{x−1}{k}⌋) + dx.

Proof. Let m_{dx} denote the least positive integer in the class (dx) modulo a. Then m_{dx} is the minimum value attained by the expression on the left in equation (3) subject to ∑_{i=1}^{k} ix_{i} = x and each x_{i} ≥ 0. If x = qk + r, 0 ≤ r ≤ k − 1, the sum x_{0} + h ∑_{i=1}^{k} x_{i} is minimized by choosing x_{k} = q, x_{r} = 1 and x_{i} = 0 for all other i, unless r = 0 in which case we must choose x_{r} = 0. Thus the minimum value for x_{0} + h ∑_{i=1}^{k} x_{i} is h(q + 1) if r ≠ 0 and hq if r = 0, which may be combined as h (1 + ⌊\frac{x−1}{k}⌋). Hence m_{dx} = ha (1 + ⌊\frac{x−1}{k}⌋) + dx.

Theorem 4. Let a, d, h, k be positive integers, with gcd(a, d) = 1. Then

(i) g(a, ha + d, ha + 2d, …, ha + kd) = ha ⌊\frac{a−2}{k}⌋ + (h − 1)a + d(a − 1);

(ii) n(a, ha + d, ha + 2d, …, ha + kd) = \frac{1}{2}h(a + r) (1 + ⌊\frac{a−2}{k}⌋) + \frac{1}{2}(a − 1)(d − 1), where r ≡ a − 2 mod k.

Proof.

(i)

g(a, ha + d, ha + 2d, …, ha + kd) = max_{C∈𝒞} m_{C} − a
= max_{1≤x≤a−1} (ha (1 + ⌊\frac{x−1}{k}⌋) + dx) − a
= ha ⌊\frac{a−2}{k}⌋ + (h − 1)a + d(a − 1).

(ii) Write a − 2 = qk + r, with 0 ≤ r ≤ k − 1. Then

n(a, ha + d, ha + 2d, …, ha + kd) = \frac{1}{a} ∑_{C∈𝒞} m_{C} − \frac{1}{2}(a − 1)

= \frac{1}{a} ∑_{x=1}^{a−1} (ha (1 + ⌊\frac{x−1}{k}⌋) + dx) − \frac{1}{2}(a − 1)

= h ∑_{x=0}^{a−2} (1 + ⌊\frac{x}{k}⌋) + \frac{1}{2}d(a − 1) − \frac{1}{2}(a − 1)
= h(k(1 + 2 + ⋯ + q) + (q + 1)(r + 1))
+\frac{1}{2}(a − 1)(d − 1)
= \frac{1}{2}h(a + r) (1 + ⌊\frac{a−2}{k}⌋) + \frac{(a−1)(d−1)}{2}.

Observation 5. The case when A consists of integers in arithmetic progression is the special case h = 1 in Theorem 4.

Recall that S^{⋆}(A) := {n ∈ Γ^{c}(A) : n + Γ^{⋆}(A) ⊂ Γ^{⋆}(A)}. Since g(A) is the largest element in S^{⋆}(A), the set S^{⋆}(A) is intimately linked with the Frobenius problem.

Theorem 6. Let a, d, h, k be positive integers, with gcd(a, d) = 1. Write a − 1 = qk + r, with 1 ≤ r ≤ k. Then

S^{⋆}(a, ha + d, ha + 2d, …, ha + kd) = \{ha ⌊\frac{x−1}{k}⌋ + (h − 1)a + dx : a − r ≤ x ≤ a − 1\}.

Proof. Fix k ≥ 1, and let A = {a, ha + d, ha + 2d, …, ha + kd}. By equation (1) and Lemma 3,

S^{⋆}(A) ⊆ \{ha ⌊\frac{x−1}{k}⌋ + (h − 1)a + dx : 1 ≤ x ≤ a − 1\} .

By equation (2), ha⌊\frac{x−1}{k}⌋ + (h − 1)a + dx ∈ S^{⋆} if and only if for each y with 1 ≤ y ≤ a − 1,

ha⌊\frac{(x+y) mod a−1}{k}⌋ + d((x + y) mod a) ≤ ha (⌊\frac{x−1}{k}⌋ + ⌊\frac{y−1}{k}⌋) + (h − 1)a + d(x + y). (4)

Suppose k ≤ a − 1, and write a − 1 = qk + r with 1 ≤ r ≤ k. Then unless x = a − 1, x + y ≤ a − 1 for at least one y. For such a y, equation (4) reduces to proving the inequality

⌊\frac{x+y−1}{k}⌋ ≤ ⌊\frac{x−1}{k}⌋ + ⌊\frac{y−1}{k}⌋.

If we now write x = q_{1}k + r_{1}, y = q_{2}k + r_{2} with 1 ≤ r_{1}, r_{2} ≤ k, the reduced inequality above fails to hold precisely when r_{1} + r_{2} ≥ k + 1. Given x, and hence r_{1}, the choice y = r_{2} = k + 1 − r_{1} will thus ensure that equation (4) fails to hold provided x + y ≤ a − 1. However, such a choice for y is not possible precisely when x ≥ qk + 1 = a − r, so that equation (4) always holds in only these cases. Finally, it is easy to verify that equation (4) holds if x = a − 1. This shows S^{⋆} = \{ha⌊\frac{x−1}{k}⌋ + (h − 1)a + dx : a − r ≤ x ≤ a − 1\} if 1 ≤ k ≤ a − 1.

If k ≥ a, equation (4) reduces to d((x + y) mod a) ≤ d(x + y) + (h − 1)a. Thus S^{⋆}(A) = \{(h − 1)a + dx : 1 ≤ x ≤ a − 1\}, as claimed, since r = a − 1 and ⌊\frac{x−1}{k}⌋ = 0 in this case. This completes the proof.

Observation 7. The case when A consists of integers in arithmetic progression is the special case h = 1 in Theorem 6. Moreover, the result in the first part of Theorem 4 follows directly from Theorem 6.

3 Acknowledgments

The author wishes to thank the anonymous referee for his comments.

References

[1] P. T. Bateman, Remark on a recent note on linear forms, Amer. Math. Monthly, 65 (1958), 517–518.

[2] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math., 211 (1962), 215–220.

[3] D. D. Grant, On linear forms whose coefficients are in arithmetic progression, Israel J. Math., 15 (1973), 204–209.

[4] S. M. Johnson, A linear diophantine problem, Canad. J. Math., 12 (1960), 390–398.

[5] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford Lecture Series in Mathematics and its Applications, No. 30, Oxford University Press, 2005.

[6] J. B. Roberts, Note on linear forms, Proc. Amer. Math. Soc., 7 (1956), 465–469.

[7] Ø. J. Rødseth, On a linear diophantine problem of Frobenius, J. Reine Angew. Math., 301 (1978), 171–178.

[8] E. S. Selmer, On the linear diophantine problem of Frobenius, J. Reine Angew. Math., 293/294 (1977), 1–17.

[9] J. J. Sylvester, Problem 7382, in W. J. C. Miller, ed., Mathematical Questions, with their Solutions, from the “Educational Times”, 41 (1884), p. 21. Solution by W. J.

    Curran Sharp. Available at http://tinyurl.com/oe344rs.

[10] A. Tripathi, The coin exchange problem for arithmetic progressions, Amer. Math. Monthly, 101 (1994), 779–781.

[11] A. Tripathi, On a variation of the coin exchange problem for arithmetic progressions, Integers, 3 (2003), Article A01, 1–5.

[12] A. Tripathi, On a linear diophantine problem of Frobenius, Integers, 6 (2006), Article A14, 1–6.