On the Number of Solutions of a Diophantine Equation of Frobenius^{∗}

Sinan Sertöz Bilkent University Department of Mathematics 06533 Ankara, Turkey

1 Introduction

The linear Diophantine equation we are interested in is of the form

x_{1}a_{1} + ⋯ + x_{n}a_{n} = N,  (1.1)

where n > 1 is a fixed positive integer and for which we have a fixed set of integers 0 < a_{1} < ⋯ < a_{n} satisfying (a_{1}, ..., a_{n}) = 1. For any nonnegative integer N we say that a solution exists if there exist nonnegative integers x_{1}, ..., x_{n} satisfying equation (1.1). It is well known that for all sufficiently large N the equation has solutions. In fact for n = 2 the largest N for which no solution exists can be explicitly written as a_{1}a_{2} − a_{1} − a_{2}. However no such formula exists for n ≥ 3 as shown by Curtis in [2]. Several ingenious algorithms exist in the literature for calculating this bound which is known as the conductor. For example the reader may refer to [1, 8, 9, 10, 13] for several algorithms for calculating the conductor. The literature on this subject is vast and for different aspects of the problem we can mention for example [3, 4, 11, 12, 15].

∗Appeared in Discrete Mathematics and Applications, Vol 8, No 2, (1998), 153-162

We are interested in calculating how many solutions equation (1.1) has. In particular we want to find a formula, or an algorithm, which is fast in giving the answer. If we denote the number of solutions corresponding to N by f(N), considering that the a_{i}’s are fixed once and for all, then it is known that f(x) = P (x)+Δ(x) where P (x) is a polynomial in x of degree n−1 with leading coefficient 1/[(a_{1} ⋯ a_{n}) · (n − 1)!], and Δ(x) is a periodic function with period a_{1} ⋯ a_{n}.

In this article we apply an elementary approach to the problem of calculating Δ. We will utilise a roots of unity argument in constructing the desired periodic function. We will write the general form of f(x) for arbitrary n, however this involves complicated sums of roots of unity. Therefore we demonstrate the merit of this approach by explicitly working out the n = 2 case to obtain a computable expression for f(x). This problem was attacked in [5, 6, 14] from different points of view, but Δ was not explicitly written.

Apparently the problem of finding the conductor, together with its solution in the n = 2 case, first appeared in [16]. Later Frobenius, noting the ubiquity of the concept, raised the general question. Several related questions are also raised in [7]. In fact the problem may look deceptively specialized but nonetheless appears at most unexpected places in mathematics. Arf rings, Gorenstein rings, Weierstrass gaps are examples from geometry where the phenomena surfaces predominantly, and unexpectedly.

Acknowledgements: I thankfully acknowledge several useful discussions with S. Stepanov. His ideas and comments both helped me to overcome difficulties at several stages and to enjoy at a higher level the workings of arithmetic.

2 The General Case

We first set up our notation which we will use throughout. By the set of natural numbers we will mean ℕ = {0, 1, 2, ⋯}. We fix a positive integer n and a set of n integers

0 < a_{1} < a_{2} < ⋯ < a_{n},

which we assume to be relatively prime;

(a_{1}, a_{2}, ..., a_{n}) = 1.  (2.2)

Towards the end of the arguments we will assume further that these integers are mutually coprime but that will serve the purpose of achieving a more elegant formulation. We will nevertheless mention how to proceed in the general case of (2.2).

For any N ∈ ℕ we define the counting function

f(N) = #{ (x_{1}, x_{2}, ..., x_{n}) ∈ ℕ^{n} | a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{n}x_{n} = N }. (2.3)

As a notation we will sometimes use

f(a_{1}, ..., a_{n}; N) := f(N)  (2.4)

to emphasize dependence on a_{i}’s. The problem we address is to find a computable expression for f.

We start by considering the complex valued function

ϕ(z) = ∏_{i=1}^{n}(1 − z^{a_{i}})^{−1}.  (2.5)

ϕ is a meromorphic function whose only poles are e_{a_{i}}^{k_{i}} for i = 1, ..., n and k_{i} = 0, ..., a_{i−1}, where we define for any integers 0 ≤ k < a the symbol e_{a}^{k} as

e_{a}^{k} = exp(2π\sqrt{−1} k/a).

We will write e_{a} for e_{a}^{1}, the primitive a-th root of unity.

The poles of ϕ are located on the unit circle, |z| = 1. The one at z = 1 is a pole of order n. However ϕ is analytic at the origin and has a power series expansion of the form

ϕ(z) = ∑_{m=0}^{∞} f(m)z^{m}, for |z| < 1.  (2.6)

This expansion for ϕ implies that for any integer N ∈ ℕ we have

f(N) = Res_{z=0} (\frac{ϕ(z)}{z^{N+1}} )
= \frac{1}{2π\sqrt{−1}} ∫_{|z|=ϵ} \frac{ϕ(z)}{z^{N+1}} dz,

for any 0 < ϵ < 1.

We therefore proceed to find the coefficient of z^{N} as given in equation (2.6), using equation (2.5). For this the following facts will be useful. We omit the proofs which are straightforward.

Fact 2.1 For any positive integer a ∈ ℕ we have the factorization

1 − t^{a} = ∏_{l=0}^{a−1}(1 − e_{a}^{l} t).

As a consequence of this we can rewrite equation (2.5) as

ϕ(z) = ∏_{j=0}^{n} ∏_{l=1}^{a_{j}−1}(1 − e_{a_{j}}^{l} z).

From this point on we explicitly assume that

(a_{i}, a_{j}) = 1 for i ≠ j.  (2.7)

This assumption has the advantage of simplifying the partial fractions expansion of the above expression of ϕ:

ϕ(z) = ∑_{i=1}^{n} \frac{K_{i}}{(1 − z)^{i}} + ∑_{j=1}^{n} ∑_{l=1}^{a_{j}−1} \frac{α_{j,l}}{(1 − e_{a_{j}}^{l} z)} ,  (2.8)

where K_{i} and α_{j,l} for i, j = 1, ..., n and l = 1, ..., a_{j} − 1 are complex constants which can be determined by the theory of partial fractions. In particular to determine the K_{i}’s we will use the following Fact 2.2 For i = 1, ..., n and for all |z| < 1 we have

\frac{1}{(1 − z)^{i}} = ∑_{m=0}^{∞} k_{i,m} z^{m}  (2.9)

where

k_{i,m} = \frac{(i + m − 1)!}{(i − 1)!m!} = ( \begin{matrix}i + m − 1 \\ m \end{matrix} )  (2.10)

with the usual understanding that 0! is replaced by 1.

Note that k_{i,m} = (m + 1)(m + 2) ⋯ (m + i − 1)/(i − 1)! and we can view it as a polynomial in m of degree i − 1.

On the other hand since |e_{a_{j}}^{l} z| < 1 we have

\frac{1}{1 − e_{a_{j}}^{l} z} = ∑_{m=0}^{∞} e_{a_{j}}^{ml} z^{m}.  (2.11)

Note here that the coefficients of z are periodic with period a_{j}. Putting equations (2.8), (2.9) and (2.11) together we obtain

ϕ(z) = ∑_{m=0}^{∞} (∑_{i=1}^{n} K_{i} k_{i,m} + ∑_{j=1}^{n} ∑_{l=1}^{a_{j}−1} α_{j,l}e_{a_{j}}^{ml}) z^{m}.

The coefficient of z^{N} is the value we are after:

f(N) = ∑_{i=1}^{n} K_{N} k_{i,N} + ∑_{j=1}^{n} ∑_{l=1}^{a_{j}−1} α_{j,l}e_{a_{j}}^{Nl}.  (2.12)

For notational convenience we introduce the following vectors:

K⃗ := (K_{1}, ..., K_{n}) ∈ ℂ^{n}
k⃗_{N} := (k_{1,N}, ..., k_{n,N}) ∈ ℂ^{n}
α⃗_{j} := (α_{j,1}, ..., α_{j,a_{j}−1}) ∈ ℂ^{a_{j}−1}
ω⃗_{j} := (e_{a_{j}}, e_{a_{j}}^{2}, ..., e_{a_{j}}^{a_{j}−1}) ∈ ℂ^{a_{j}−1}
ω_{j}^{N} := (e_{a_{j}}^{N}, e_{a_{j}}^{2N}, ..., e_{a_{j}}^{(a_{j}−1)N}) ∈ ℂ^{a_{j}−1}

where j = 1, ..., n and N ∈ ℕ. Note that for each a_{j} and for any integers N, M ∈ ℕ

ω_{j}^{N} = ω_{j}^{Nmod a_{j}}.

With this notation we can write

Theorem 2.3 (General Formula)

f(N) = K⃗ · k⃗_{N} + ∑_{j=1}^{n} α⃗_{j} · ω_{j}^{N}

where · denotes the usual inner product.

Observe that K⃗ · k⃗_{N} is a polynomial in N of degree n − 1. Each α⃗_{j} · ω_{j}^{N} is periodic of period a_{j}. Since (a_{1}, ..., a_{n}) = 1, the total term ∑_{j=1}^{n} α⃗_{j} · ω_{j}^{N} is periodic with period a_{1}a_{2} ⋯ a_{n}.

Calculating K⃗ and α⃗_{j}. Using elementary means we can obtain the entries of K⃗ = (K_{1}, ..., K_{n}) and α⃗_{j}. For example we can multiply both sides of equation (2.8) by (1 − z)^{n}, take the i-th derivative of both sides and evaluate at z = 0 to obtain

K_{i} = \frac{1}{(n − i)!} (\frac{(1 − z)^{n}}{∏_{j=1}^{n}(1 − z^{a_{j}})})_{z=0}^{(n−i)} , for i = 1, ..., n  (2.13)

where the superscript denotes the order of the derivative and the subscript denotes the point of evaluation. Similarly multiplying both sides of (2.8) by 1 − e_{a_{j}}^{l} z and evaluating at z = e_{a_{j}}^{−l} we obtain

α_{j,l} = ∏_{i=1, i≠j}^{n}(1 − e_{a_{j}}^{−la_{i}})^{−1} ∏_{s=1, s≠l}^{a_{j}}(1 − e_{a_{j}}^{s−l})^{−1}

= ∏_{i=1, i≠j}^{n}(1 − e_{a_{j}}^{−la_{i}})^{−1} ∏_{k=1}^{a_{j}}(1 − e_{a_{j}}^{k})^{−1}
= ∏_{i=1, i≠j}^{n}(1 − e_{a_{j}}^{−la_{i}})^{−1} · \frac{1}{a}.  (2.14)

The main difficulty of the simplification process lies in finding a expression for (2.14) amenable to summing over the given indices. We will find such an expression for n = 2. For large n a computable form for (2.13) is complicated but still seems possible.

Remark: If the a_{i}’s are not mutually coprime then the partial fraction expansion of f will involve terms of the form 1/(1 − e_{a}^{k})^{r}, and the determination of the coefficient with which it appears will be similar to determining the K_{i}’s. Clearly this will entail an enormous amount of bookkeeping.

The n = 3 Case: In [5, 6, 14] the polynomial part of f for n = 3 is determined by different approaches. Here we give the result from our approach for completeness. Certainly for the polynomial part we need to determine K_{1}, K_{2} and K_{3}, which are found as:

K_{1} = \frac{σ_{1}^{2} + σ_{2} − 6σ_{1} + 6}{12σ_{3}}
K_{2} = \frac{σ_{1} − 3}{2σ_{3}}
K_{1} = \frac{1}{σ_{3}}

where the σ_{i}’s are the elementary symmetric polynomials of a_{1}, a_{2}, a_{3} defined as usual as σ_{1} = a_{1} + a_{2} + a_{3}, σ_{2} = a_{1}a_{2} + a_{1}a_{3} + a_{2}a_{3} and σ_{3} = a_{1}a_{2}a_{3}.

3 The n = 2 Case

In the n = 2 case it is well known that for any integer N ∈ ℕ we have f(N) = || N/(a_{1}a_{2}) || + f(N − || N/(a_{1}a_{2}) || · a_{1}a_{2}), where || · || denotes the greatest integer function. In fact f(N) = 1 for all a_{1}a_{2} −a_{1} −a_{2} < N < a_{1}a_{2}, so it suffices to find f for 0 ≤ N ≤ a_{1}a_{2} − a_{1} − a_{2}. For this we define some auxiliary functions:

Definition 3.1 ε_{a|n} = \{ \begin{matrix}1 & if a|n \\ 0 & if a |̸n \end{matrix} Definition 3.2 r_{a,b,n} is defined for some positive integers a, b > 0 with (a, b) = 1 and n ≥ 0, as the unique solution of the equation bx+n ≡ 0 mod a, with 0 ≤ x ≤ a − 1.

With these definitions we state the main result of this work:

Theorem 3.3 For two positive integers a, b with (a, b) = 1, if we define for any N ∈ ℕ the function

f(N) = #{ (x, y) ∈ ℕ^{2} | ax + by = N }

then we have

f(N) = \frac{N + br_{a,b,N} + ar_{b,a,N}}{ab} + ε_{a|N} + ε_{b|N} − 1.

Before we prove the theorem we state two elementary lemmas whose proofs are briefly indicated.

Lemma 3.4 For any two integers a > 0 and N ≥ 0, we have

∑_{k=1}^{a−1} e_{a}^{kN} = aε_{a|N} − 1.

Proof: The proof is straightforward once it is observed that either e_{a}^{N} = 1 or e_{a}^{N} = e_{r} for some positive integer r dividing a. □

Lemma 3.5 If (a, b) = 1, then for any integer 1 ≤ k ≤ a − 1, we have

\frac{t^{a−1} + t^{a−2} + ⋯ + t + 1}{t − e_{a}^{kb}} = ∑_{i=0}^{a−2} C_{kb,a}(i)t^{a−2−i}  (3.15)

where

C_{m,a}(i) = 1 + e_{a}^{m} + e_{a}^{2m} + ⋯ + e_{a}^{im}.

Proof: Observe that

C_{kb,a}(i + 1) − e_{a}^{kb}C_{kb,a}(i) = 1,

for i = 0, ..., a − 3. Also observe that e_{a}^{kb}C_{kb,a}(a − 2) = e_{a}^{b}k + e_{a}^{2bk} + ⋯ + e_{a}^{(a−1)bk} = −1 as shown by lemma 3.4. Now multiply both sides of (3.15) by t − e_{a}^{bk} and simplify. □

We can now proceed with the proof of the theorem.

Proof of theorem 3.3: From equation(2.12) we write

f(N) = K_{1}k_{1,N} + K_{2}k_{2,N} + ∑_{k=1}^{a−1} α_{1,k}e_{a}^{kN} + ∑_{k=1}^{b−1} α_{2,k}e_{b}^{kN}. (3.16)

From equations (2.10), (2.13) and (2.14) we have

K_{1} = \frac{a + b − 2}{2ab}  (3.17)
K_{2} = \frac{1}{ab}  (3.18)
k_{1,N} = 1  (3.19)
k_{2,N} = N + 1  (3.20)
α_{1,k} = \frac{1}{1 − e_{a}^{−kb}} \frac{1}{a}
α_{2,k} = \frac{1}{1 − e_{b}^{−ka}} \frac{1}{b}.

Therefore it remains to evaluate the sum

∑_{k=1}^{a−1} α_{1,k}e_{a}^{kN} = \frac{1}{a} ∑_{k=1}^{a−1} \frac{e_{a}^{kN}}{1 − e_{a}^{−kb}}

= \frac{1}{a} ∑_{k=1}^{a−1} e_{a}^{kN} (1 − \frac{1}{1 − e_{a}^{kb}} )

= \frac{1}{a} ∑_{k=1}^{a−1} e_{a}^{kN} − \frac{1}{a} ∑_{k=1}^{a−1} \frac{e_{a}^{kN}}{1 − e_{a}^{kb}}

= \frac{1}{a}(aε_{a|N} − 1) − \frac{1}{a} ∑_{k=1}^{a−1} \frac{e_{a}^{kN}}{1 − e_{a}^{kb}}  (3.21)

where we have written the last line from lemma 3.4. We now proceed to evaluate the sum of roots of unity that appears in the above sum:

∑_{k=1}^{a−1} \frac{e_{a}^{kN}}{1 − e_{a}^{kb}} = ∑_{k=1}^{a−1} e_{a}^{kN} · \frac{1}{1 − e_{a}^{kb}}

= ∑_{k=1}^{a−1} e_{a}^{kN} · \frac{(1 − e_{a}^{b}) ⋯ ˆ (1 − e_{a}^{kb}) ⋯ (1 − e_{a}^{(a−1)b})}{(1 − e_{a}^{b}) ⋯ (1 − e_{a}^{kb}) ⋯ (1 − e_{a}^{(a−1)b})}

= ∑_{k=1}^{a−1} e_{a}^{kN} · \frac{1}{a} · ∏_{j=1, j≠k}^{a−1}(1 − e_{a}^{jb})

= \frac{1}{a} ∑_{k=1}^{a−1} e_{a}^{kN} · (\frac{t^{a−1} + t^{a−2} + ⋯ + t + 1}{t − e_{a}^{kb}} |_{t=1})

= \frac{1}{a} ∑_{k=1}^{a−1} e_{a}^{kN} · ∑_{i=0}^{a−2} C_{kb,a}(i)  (3.22)

where we write the last line from (3.15). We now calculate this last sum. For this first observe that

C_{kb,a}(0) = 1
C_{kb,a}(1) = 1 + e_{a}^{kb}
C_{kb,a}(2) = 1 + e_{a}^{kb} + e_{a}^{2kb}
⋮ ⋮ ⋮
C_{kb,a}(a − 2) = 1 + e_{a}^{kb} + e_{a}^{2kb} + ⋯ + e_{a}^{jkb} + ⋯ + e_{a}^{(a−2)kb}

∑_{i=0}^{a−2} C_{kb,a}(i) = (a − 1) + (a − 2)e_{a}^{kb} + ⋯ + (a − 1 − j)e_{a}^{jkb} + ⋯ + e_{a}^{(a−2)kb}
= ∑_{j=0}^{a−2}(a − 1 − j)e_{a}^{jkb}.

Now we multiply this with e_{a}^{kN} and sum over k:

∑_{k=1}^{a−1} e_{a}^{kN} · ∑_{i=0}^{a−2} C_{kb,a}(i) = ∑_{k=1}^{a−1} ∑_{j=0}^{a−2}(a − 1 − j)e_{a}^{k(N+jb)}

= ∑_{j=0}^{a−2}(a − 1 − j) ∑_{k=1}^{a−1} e_{a}^{k(N+jb)}

= ∑_{j=0}^{a−2}(a − 1 − j)(aε_{a|(N+jb)} − 1),  (3.23)

where the last equation follows from lemma 3.4. Note that since 0 ≤ j ≤ a−1 and (a, b) = 1, there is only one value of j which satisfies N + jb ≡ 0 mod a. In definition 3.2 we denoted this unique solution by r_{a,b,N}. Hence we have

aε_{a|(N+jb)} − 1 = \{ \begin{matrix}−1 & if j ≠ r_{a,b,N} \\ a − 1 & if j = r_{a,b,N} \end{matrix} .  (3.24)

Putting this in (3.23) we have

∑_{k=1}^{a−1} e_{a}^{kN} · ∑_{i=0}^{a−2} C_{kb,a}(i) = a(a − 1 − r_{a,b,N}) − ∑_{j=0}^{a−2}(a − 1 − j)
= a (\frac{a − 1}{2} − r_{a,b,N} ) .

Inserting this into (3.22) gives

∑_{k=1}^{a−1} \frac{e_{a}^{kN}}{1 − e_{a}^{kb}} = (\frac{a − 1}{2} − r_{a,b,N} ) .

Further inserting this into (3.21) gives

∑_{k=1}^{a−1} α_{1,k}e_{a}^{kN} = ε_{a|N} − \frac{a + 1}{2a} + \frac{r_{a,b,N}}{a} .  (3.25)

Similarly we find

∑_{k=1}^{b−1} α_{2,k}e_{b}^{kN} = ε_{b|N} − \frac{b + 1}{2b} + \frac{r_{b,a,N}}{b} .  (3.26)

Finally we substitute equations (3.25), (3.26), (3.17), (3.18), (3.19) and (3.20) into equation (3.16) and obtain

f(N) = \frac{N + br_{a,b,N} + ar_{b,a,N}}{ab} + ε_{a|N} + ε_{b|N} − 1.

as claimed. □

Remark: The fraction \frac{N + br_{a,b,N} + ar_{b,a,N}}{ab} is always an integer; a|(N + br_{a,b,N}) by definition, so a|(N + br_{a,b,N} + ar_{b,a,N}). Similarly b|(N + br_{a,b,N} + ar_{b,a,N}). But (a, b) = 1, so ab|(N + br_{a,b,N} + ar_{b,a,N}).

Remark: That we have obtained a computable formula can be checked easily; for example a simple Maple V program can calculate immediately that

f(1234567, 12345678; 123456789012345) = 8.

Recall equation (2.4) for notation.

References

[1] Brauer, A. T. & Shockley, J. E., Ona problem of Frobenius, J. angew reine Math., 211 (1962), 215-220.

[2] Curtis, F., On formulas for the Frobenius number of a numerical semigroup, Math. Scand., 67 (1990), 190-192.

[3] Davison, J. L., On the linear Diophantine problem of Frobenius, J. Number Theory, 48 (1994), 353-363.

[4] Djawadi, M. & Hofmeister, G., Linear Diophantine problems, Arch. Math. (Basel) 66 (1996), 19-29.

[5] Ehrhart, E., Sur un problème de géométrie diophantinne linéaire I, J. reine angew. Math. 226 (1965), 1-29.

[6] Ehrhart, E., Sur un problème de géométrie diophantinne linéaire II, J. reine angew. Math. 227 (1966), 30-54.

[7] Erdös, P. & Graham, R. L., On a linear Diophantine problem of Frobenius, Acta. Arith., 21 (1972), 399-408.

[8] Heap, B. R. & Lynn, M. S., On a linear Diophantine problem of Frobenius, an improved algorithm, Numer. Math., 7 (1965), 226-231.

[9] Johnson, S. M., A linear Diophantine equation, Canadian J. Math., 12 (1960), 390-398.

[10] Lewin, M., An algorithm for a solution of a problem of Frobenius, J. reine. angew. Math., 276 (1975), 68-82.

[11] Rodseth, O. J., On a linear Diophantine problem of Frobenius, J. reine angew. Math., 302 (1978), 171-178.

[12] Selmer, E. S., On the linear Diophantine problem of Frobenius, J. reine angew. Math. 293/294 (1977), 1-17.

[13] Sertöz, S., & Özlük, A., On a Diophantine problem Frobenius, Bull. Technical Univ. of Istanbul, 39 (1986), 41-51.

[14] Sertöz, S., & Özlük, A., On the number of representations of an integer by a linear form, Istanbul Univ. Journal of Math., 50 (1991), 67-77.

[15] Skupien, Z., A generalization of Sylvester’s and Frobenius’ problems on numerical semigroups, Acta Arith., 65 (1993), 353-366.

[16] Sylvester, J. J., Educational Times 41 (1884), 21.

Bilkent University Department of Mathematics 06533 Ankara, Turkey

sertoz@fen.bilkent.edu.tr