ON THE NUMBER OF

REPRESENTATIONS OF AN INTEGER BY A LINEAR FORM

Sinan Sertöz & Ali Özlük

Appeared in: İstanbul Üniv. Fen Fak. Mat. Derg., 50 (1991), 67–77 (1993)

1. INTRODUCTION The celebrated problem of Frobenius consists of determining the largest nat-

ural number g which cannot be expressed in the form

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

where a_{1}, a_{2}, ..., a_{n} are relatively prime natural numbers and x_{1}, x_{2}, ..., x_{n} are nonnegative integers. It is well known that for n = 2,

g = a_{1}a_{2} − a_{1} − a_{2}.  (2)

The existence of such a formula for n = 2, first given in [10], provoked a large number of researchers to look for similar formulas for higher n. For an introduction to the vast literature on Frobenius’s problem see, for example, [7],[8] and the references given there. Despite intense work on this problem no closed formula for n > 2, such as equation (2) is available. Algorithms for computing g however exist and we have given one such algorithm in [9].

In this note, in association with this problem, we investigate the number of different representations r_{n}(N; a_{1}, ..., a_{n}) = r_{n}(N) of N in the form of (1). We obtain by elementary means a formula for r_{n}(N) valid for sufficiently large N and for mutually prime a_{i}. For n = 3 we do not lose any generality by the latter restriction, see [4] and [7].

Before we state our results let us first set the notation to be used throughout this article. For a positive integer n define

P_{n} = ∏_{i=1}^{n} a_{i}  (3)
S_{n} = ∑_{i=1}^{n} a_{i}  (4)

and let N_{0} and x be defined by

N = N_{0}P_{n} + x , 0 ≤ x < P_{n}  (5)

i.e. N_{0} is the largest integer in \frac{N}{P_{n}} and x is the number remaining after dividing N by P_{n}. Also define S(a_{1}, ..., a_{n}) as the semigroup generated by the a_{i}’s over the natural numbers.

S(a_{1}, ..., a_{n}) = {a_{1}x_{1} + ⋯ + a_{n}x_{n} | x_{1}, ..., x_{n} ∈ N }  (6)

2 RESULTS AND COMMENTS We can now summarize our results in the following theorems and corollaries. (We number our results with the same index for easy reference.)

Theorem 1 : As N increases r_{n}(N) becomes asymptotically close to N^{n−1}/(∏_{i=1}^{n} a_{i})(n − 1)!. That is

r_{n}(N) ∼ \frac{N^{n−1}}{(∏_{i=1}^{n} a_{i})(n − 1)!} as N → ∞.  (7)

For small values of n, (n = 2, 3, 4), we know exactly what r_{n}(N) is:

Corollary 2 : (see [3]) When N ≥ P_{n} we have

r_{2}(N) = \frac{N}{P_{2}} − \frac{x}{P_{2}} + r_{2}(x)  (8)
r_{3}(N) = \frac{N(N + S_{3})}{2P_{3}} − \frac{x(x + S_{3})}{2P_{3}} + r_{3}(x)  (9)
r_{4}(N) = A − B · r_{4}(P_{4} − 2) + (B + N_{0}) · r_{4}(P_{4} − 1) + r_{4}(x)  (10)

where in the last equation the coefficients A and B are given by

A = \frac{1}{2} ∑_{k=1}^{N_{0}}(N − kP_{4} + 1)(N − kP_{4} + 2)  (11)
B = \frac{1}{2}N_{0}(N + x − P_{4} + 2).  (12)

Note that in the expression for A the leading coefficient is N^{3}/6P_{4} as expected. In general we observe that r_{n}(N) satisfies the following recursive relation which is the key theorem behind our results:

Theorem 3 : When N > P_{n} − S_{n} + n − 2 we have the following relation for r_{n}(N)

1 = ∑_{k=N−n+2}^{N} C_{N−k} · [r_{n}(k) − r_{n}(k − P_{n})]  (13)

where

C_{m} = \{ \begin{matrix}(−1)^{m}( \begin{matrix}n − 2 \\ m \end{matrix} ) & for 0 ≤ m ≤ n − 2 \\ 0 & otherwise. \end{matrix}  (14)

Moreover we have: Corollary 4 : (see [3]) For every n there exists a polynomial L_{n}(X) of degree n−1 whose leading coefficient is the asymptotic limit of r_{n}(N), i.e. N^{n−1}/[P_{n}(n − 1)!], and if we define Δ_{n}(N) as

Δ_{n}(N) = r_{n}(N) − L_{n}(N)  (15)

then Δ_{n}(N) is periodic with period P_{n}.

As a consequence of this periodicity it suffices to know only L_{n}(N) and Δ_{n}(x) in order to understand the behaviour of r_{n}(N), where x is NmodP_{n} as in equation (5). This combined with corollary 2 leads to the following:

Corollary 5 : For n = 2, 3, 4 we have

Δ_{2}(x) = r_{2}(x) − \frac{x}{P_{2}}  (16)
Δ_{3}(x) = r_{3}(x) − \frac{x(x + S_{3})}{2P_{3}}  (17)
Δ_{4}(x) = r_{4}(x) + \frac{x^{3}}{6P_{4}} + (\frac{3 − P_{4} + 2r_{4}(P_{4} − 1) − 2r_{4}(P_{4} − 2)}{4P_{4}}) x^{2} +

(\frac{12 − 9P_{4} + P_{4}^{2} + 6[4 − P_{4}]r_{4}(P_{4} − 1) − 6[2 − P_{4}]r_{4}(P_{4} − 2)}{12P_{4}}) x (18)

We remark that the periodic function Δ(X) can be expressed as a trigonometrical sum using the a_{i}^{th} roots of unity, the analysis of which will be discussed elsewhere.

We give an interesting combinatorical proof for the following old but beautiful formula:

r_{3}(P_{3}) = \frac{P_{3} + S_{3}}{2} + 1.  (19)

Finally combining this formula with our full understanding of what happens in the n = 2 case and with the aid of our recursion formula we have an almost total understanding of what happens in the n = 3 case. Note that r_{3}(N) for N ≥ P_{3} is given by equation (9). The case for P_{3} − S_{3} + 1 ≤ N < P_{3} is covered by the following theorem. For N smaller than that no formula seems possible at present and we call it the erratic region. Corollary 6 :

r_{3}(P_{3}) = r_{3}(P_{3} − 1) + 2  (20)
r_{3}(P_{3} − t) = r_{3}(P_{3} − t − 1) + 1 for 1 ≤ t ≤ S_{3} − 2. (21)

In particular we have

r_{3}(P_{3} − S_{3} + 1) = \frac{P_{3} − S_{3}}{2} + 1.  (22)

In the last section we apply these results to the theory of Hilbert-Samuel polynomials. COMMENTS 1) This problem has been attacked by several authors. In particular Ehrhart has analyzed it in [2] and [3] where he has used what he calls Euler’s recursion formula. He then obtains formulas (8), (9) and (19). He has also observed the periodicity property of r_{n} as in equation (15). But he has tried to express the polynomial L_{n}(x) in terms of n′ = x + \frac{S_{3}}{2} . This approach it seems prevented him from obtaining the leading coefficient of L_{n}(x) for a general n as we did in theorem 1.

2) Our basic claim is that once r_{n}(N) is known for 0 ≤ N ≤ P_{n} then r_{n} for a general N can be obtained from that information by an appropriate polynomial. Our recursion formula (13) seems stronger than the ones used before hence making it possible to find the polynomial mentioned in corollary 4.

PROOFS AND DISCUSSIONS : We find it convenient to begin with the proof of our recursion formula. Proof of theorem 3 :

First observe that Q_{n}(x) which is defined as

Q_{n}(x) = \frac{(1 − x^{P_{n}})(1 − x)^{n−2}}{(1 − x^{a_{1}}) ⋯ (1 − x^{a_{n}})} − \frac{1}{1 − x}  (23)

is a polynomial of degree P_{n} − S_{n} + n − 2, since every root of the denominator is a root of the numerator with the same multiplicity. Using the fact that we are using only mutually prime integers a_{1}, ..., a_{n} we can show immediately that

\frac{1}{∏_{i=1}^{n}(1 − x^{a_{i}})} = ∑_{t=0}^{∞} r_{n}(t)x^{t}.  (24)

Substituting this and the usual expansion of 1/(1 − x) into equation (23) we obtain the following expression for Q_{n}:

Q_{n}(x) = ∑_{t=0}^{∞}[(1 − x^{P_{n}})(1 − x)^{n−2}r_{n}(t) − 1] x^{t}.  (25)

Since Q_{n}(x) is a polynomial the coefficient of x^{N} is zero beyond the degree of Q_{n}, and this is equivalent to the statement of theorem 3. □

We will now use this theorem to demonstrate a proof of corollary 2. See [3, prop 10.2,thm 10.5] for another proof of the n = 2, 3 cases.

Proof of corollary 2 : Putting n = 2 in equation (13) gives

r_{2}(N) = r_{2}(N − P_{2}) + 1.

By successively subtracting P_{2} from N we obtain equation (8) of the theorem. Putting n = 3 in equation (13) gives

r_{3}(N) = r_{3}(N − 1) + r_{3}(N − P_{3}) − r_{3}(N − P_{3} − 1) + 1  (26)

This equation is valid for N > deg Q_{3} = P_{3} − S_{3} + 1. By induction we find

r_{3}(N) = r_{3}(N − k) + r_{3}(N − P_{3}) − r_{3}(N − P_{3} − k − 1) + k.  (27)

We may substitute N − P_{3} for k in this equation. Noting that r_{3} of a negative number is zero we obtain

r_{3}(N) = r_{3}(P_{3}) + r_{3}(N − P_{3}) + N − P_{3}.  (28)

By successively subtracting P_{3} from N we obtain

r_{3}(N) = \frac{N^{2}}{2P_{3}} + (\frac{2r_{3}(P_{3}) − P_{3}}{2P_{3}} ) N + (\frac{xP_{3} − 2xr_{3}(P_{3}) − x^{3}}{2P_{3}} + r_{3}(x)) .(29)

We now substitute equation (19) in the above equation to obtain equation (9).

The last equation of the corollary is obtained in a similar but more tedious way and we leave it to the reader. □

We now give an interesting proof of equation (19) for completeness since we used it in the above proof. \underline{Proof of (19) :} We apply a reduction trick

r_{3}(P_{3}) = ∑_{t=0}^{P_{2}} r_{2}(P_{3} − ta_{3}).  (30)

Define f_{t} and k_{t} by

P_{3} − ta_{3} = f_{t}P_{2} + k_{t}, 0 ≤ k_{t} < P_{2}.  (31)

Using equation (8) in (30) gives

r_{3}(P_{3}) = ∑_{t=0}^{P_{2}}[f_{t} + r_{2}(k_{t})].  (32)

It is well known that r_{2}(m) = 0 for exactly half of the numbers between 0 and P_{2} − S_{2} inclusively. On the other hand it can be shown that r_{2}(m) = 1 for P_{2} − S_{2} + 1 ≤ m ≤ P_{2}. These give

∑_{t=0}^{P_{2}} r_{2}(k_{t}) = \frac{P_{2} + S_{2} + 1}{2}.  (33)

The other sum in (32) is the number of lattice points in and on the triangle, except the ones on the x−axis, defined by the line P_{2}y = P_{3} − a_{3}x in the first quadrant. (compare with (31)). These lattice points can be counted by first counting the lattice points in and on the rectangle defined by the three corners of the above triangle. Since (a_{3}, P_{2}) = 1, there are no lattice points on the diagonal. Thus the triangle contains half of all the lattice points of the rectangle. Subtracting from this number the P_{2} + 1 lattice points which lie on the x−axis we obtain

∑_{t=0}^{P_{2}} f_{t} = \frac{P_{3} − P_{2} + a_{3} + 1}{2}.  (34)

Finally adding equations (33) and (34) gives the desired formula for r_{3}(P_{3}). □

Proof of theorem 1 : We use induction on n. The assertion for n = 2 follows from the equation (8) of theorem 2. We apply the reduction trick, which we used before, to r_{n+1}(N),

r_{n+1}(N) = ∑_{t=0}^{[ \frac{N}{a_{n+1}} ]} r_{n}(N − a_{n+1}t).  (35)

Defining y as y = N − a_{n+1}[N/a_{n+1}] and applying the induction hypothesis to the r_{n} of equation (35) we get

r_{n+1}(N) = ∑_{t=0}^{\frac{N−y}{a_{n+1}}} \{\frac{(N − a_{n+1}t)^{n−1}}{P_{n} · (n − 1)!} + O(N^{n−1})\}  (36)

where the O(·) notation is used in the sense that

lim_{N→∞} \frac{O(N^{n−1})}{N^{n−1}} = 0.

We can further simplify equation (36) by using the binomial theorem;

r_{n+1}(N) = ∑_{t=0}^{\frac{N−y}{a_{n+1}}} \frac{(N − a_{n+1}t)^{n−1}}{P_{n} · (n − 1)!} + O(N^{n})

= ∑_{t=0}^{\frac{N−y}{a_{n+1}}} (N^{n−1} − C_{1}^{n−1}N^{n−2}a_{n+1}t + ⋯ + (−1)^{n−1}a_{n+1}^{n−1}t^{n−1}) + O(N^{n−1})
= N^{n−1}(\frac{N}{a_{n+1}} − y + 1) − C_{1}^{n−1}N^{n−2}a_{n+1}(\frac{N^{2}}{2a_{n+1}} + ⋯)

+ ⋯ + (−1)^{k−1}C_{k−1}^{n−1}N^{n−k}a_{n+1}^{k−1}(\frac{N^{k}}{ka_{n+1}} + ⋯)

+ ⋯ + (−1)^{n−1}a_{n+1}^{n−1}(\frac{N^{n}}{na_{n+1}} + ⋯) + O(N^{n})

= \frac{N^{n}}{a_{n+1}} (1 − C_{1}^{n−1} \frac{1}{2} + ⋯ +

⋯ + (−1)^{k−1}C_{k−1}^{n−1} \frac{1}{k} + ⋯ + (−1)^{n−1} \frac{1}{n}) + O(N^{n})

= \frac{N^{n}}{a_{n+1}} · \frac{1}{n} + O(N^{n}).  (37)

This then completes the proof of theorem 1. □

Proof of corollary 4 : We can apply induction for this proof; the case n = 2 being already done in corollary 2 equation (8). For the general case we need the following interesting relation;

r_{n}(N) = ∑_{t=0}^{N} ϵ_{N−t}r_{n−1}(t; P_{2}, a_{3}, ..., a_{n})  (38)

where

ϵ_{N−t} = \{ \begin{matrix}1 & if N − t ∈ S(a_{1}, a_{2}) \\ 0 & otherwise. \end{matrix}  (39)

We briefly indicate a proof of this: recalling equations (8) and (24) we can write

\frac{1 − x^{P_{2}}}{(1 − x^{a_{1}})(1 − x^{a_{2}})} = ∑_{t=0}^{∞} ϵ_{t}x^{t}.  (40)

Again in the same vein we play with the right hand side of equation (24)

\frac{1}{(1 − x^{a_{1}}) ⋯ (1 − x^{a_{n}})} = \frac{1 − x^{P_{2}}}{(1 − x^{a_{1}})(1 − x^{a_{2}})} \frac{1}{(1 − x^{P_{2}})(1 − x^{a_{3}}) ⋯ (1 − x^{a_{n}})}. (41)

Finally the following interesting fact

Q_{2}(x) = − ∑_{n∉S(a_{1},a_{2})} x^{n}.  (42)

combined with the equations (40) and(41) yields the desired equation (38). Going back to the proof we need to observe that r_{n−1}(t; P_{2}, a_{3}, ..., a_{n}) can be written as a polynomial plus a periodic part which has period equal to P_{2}a_{3} ⋯ a_{n} = P_{n}. The sum of these terms will again be a polynomial plus a periodic part with the right period. The degree of this polynomial is given by theorem 1. □

Corollary 5 follows upon inspection. We pass to the proof of corollary 6;

Proof of corollary 6 : Returning to equation (27) note that we chose k such that N − k was equal to P_{3} and our calculations sailed off smoothly. However we are allowed to make N − k as small as P_{n} − S_{n} + 1 and N as small as P_{3} − S_{3} + 2, not necessarily at the same time. First let N = P_{3} and k = 1 in equation (27) and recall that r_{3} of a negative number is zero. This will give

r_{3}(P_{3}) = r_{3}(P_{3} − 1) + 2.  (43)

Next letting N = P_{3} − t and k = 1, where 1 ≤ t ≤ S_{3} − 2, we have

r_{3}(P_{3} − t) = r_{3}(P_{3} − t − 1) + 1 for 1 ≤ t ≤ S_{3} − 2.  (44)

This gives us the interesting fact that the number of representations of N increases by one as N increases from P_{3}−S_{3}+1 to P_{3}−1. Combining this with equation (43) and with the formula of r_{3}(P_{3}) given in equation (19) will finally give us

r_{3}(P_{3} − S_{3} + 1) = \frac{P_{3} − S_{3}}{2} + 1.  (45)

Thus equations (9, 43, 44, 45) allow us to have a complete understanding of the n = 3 case except the erratic interval up to P_{3} − S_{3}. □

\underline{REMARK :} Note that in equation (36) we treated r_{n}(N − a_{n+1}t) as obeying the induction hypothesis even when N − a_{n+1}t is small. This is justified by the following analysis for these small values: When a_{1}, ..., a_{n+1} are fixed there are only finitely many values of t, say K of such t, for which r_{n}(N − a_{n+1}t) is not of the required form. For each such term we can replace r_{n}(X) by \frac{X^{n−1}}{P_{n}(n−1)1} + (r_{n}(X) − \frac{X^{n−1}}{P_{n}(n−1)1}) which is of the form \frac{X^{n−1}}{P_{n}(n−1)1} + O(N^{n}). The \frac{X^{n−1}}{P_{n}(n−1)1} term contributes to (36) as claimed in (37). Only K of the O(N^{n}) terms are added for each such contribution. The number of m’s for which r_{n}(m) is not of the required form depends only on a_{1}, ..., a_{n}, hence there is a finite upper bound for K independent of N. Hence K terms of the form O(N^{n}) still add up to a term of the same form as claimed in (37).

HILBERT-SAMUEL POLYNOMIALS

Basic reference for the definitions used here is [1]. Let A = ⨁_{m=0}^{∞} A_{m} be a graded Noetherian ring, generated as a A_{0}-algebra by ξ_{1}, ..., ξ_{n} which are homogeneous elements of A of degrees a_{1}, ..., a_{n}. Let M = ⨁_{m=0}^{∞} M_{m} be a finitely generated graded A-module, and λ be an additive function on the class of finitely generated A_{0}-modules with values in Z. An example of such λ is the dimension function. Then the Poincare series of M with respect to λ is P (M, x) = ∑_{m=0}^{∞} λ(M_{m})x^{m}. It is known that P (M, x) = [f(x)/ ∏_{i=1}^{m}(1 − x^{a_{i}})] for some polynomial f(x) with integer coefficients (Hilbert-Serre). The research here concentrates on obtaining more information on P (M, x) and interpreting this information geometrically.

Denote the order of the pole of P (M, x) at x = 1 by d. Let f(x) = g(x)(1−x)^{r}, where g(1) ≠ 0 and r = m−d. Now we apply our results to conclude the following theorem:

Theorem : If (a_{i}, a_{j}) = 1 for i ≠ j, then for m sufficiently large

λ(M_{m}) = F (m) + δ(m)

where F (x) is a polynomial with rational coefficients of degree d − 1 and δ is a periodic function from integers to integers, its period dividing P_{n} = a_{1} ⋯ a_{n}. The leading term of F (x) is

\frac{g(1)}{(d − 1)!P_{n}} x^{d−1}, for d ≥ 2.

Corollary : Define H_{i}(m) = λ(M_{i+mP_{n}}) for 0 ≤ i ≤ P_{n}. Then for m large enough each H_{i}(x) is a polynomial with rational coefficients and they all have the same leading term given by the above theorem. In fact H_{i}(x) and H_{j}(x) differ by an additive constant.

Corollary : (Hilbert-Serre, [1]) When all a_{i} = 1, then for m large enough λ(M_{m}) is a polynomial. (P_{n} = 1 so we have only H_{0}(x) defined and λ(M_{m}) = H_{0}(m) for large m.)

We conclude by quoting a result of Morales which is related to ours.

Theorem of Morales : (see [5]). When a_{1}, ..., a_{n} are arbitrary let k_{n} = l.c.m.(a_{1}, ..., a_{n}) and define H_{i}(m) = λ(M_{i+mk_{n}}) for 0 ≤ i ≤ k_{n}. Then for sufficiently large m each H_{i}(x) is a polynomial with rational coefficients. In [6] Morales applies these results to examine the geometry of space curves in lower dimensional spaces.

References

[1] M.F. Atiyah, I.G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley, Reading, Mass. (1969).

[2] E. Ehrhart, Sur un probleme de geometrie diophantienne lineaire.I, J. reine angew. Math. 226 (1965) 1-29.

[3] E. Ehrhart, Sur un probleme de geometrie diophantienne lineaire.II, J. reine angew. Math. 227 (1966) 30-54.

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

[5] M. Morales, Fonctions de Hilbert, genre geometrique d’une singularite quasi homogene Cohen-Macaulay, C.R.Acad.Sc. Paris, t. 301, Serie 1, no 14, (1985) 699-702.

[6] M. Morales, Syzygies of monomial curves and a linear problem of Frobenius, Preprint of Max-Planck Institut fur Mathematik,Bonn, (1987).

[7] O.J. Rodseth, 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] S. Sertöz, A. Özlük, On a Diophantine problem of Frobenius, Bulletin of the Technical University of Istanbul, 39 (1986) 41-51.

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

Sinan Sertöz  Ali Özlük
Bilkent University  University Of Maine
Department of Mathematics  Department of Mathematics
P.K. 8, 06572 Maltepe  Neville Hall, Orono, Maine
Ankara, Turkey  04469 U.S.A.

ABSTRACT

We investigate the number of representations r_{n}(N) for an integer N given in the Diophantine form

N = a_{1}X_{1} + ⋯ + a_{n}X_{n}

where a_{1}, ..., a_{n} are mutually prime natural numbers and X_{1}, ..., X_{n} are nonnegative integers. We obtain a formula for the leading coefficient of the polynomial part of r_{n} for any n. We also show that r_{n} satisfies a rather strong recursive relation through which we can analyze the n = 3 case more thoroughly than done before. We apply these results to Hilbert polynomials of finitely generated modules.

ÖZET

Aralarında asal olan a_{1}, ..., a_{n} gibi n tam sayının negatif olmayan tam katsayılarla oluşturulan lineer bileşenleri arasında N tam sayısının kaç değişik şekilde görüleceğini r_{n}(N) ile gösterelim. Bu makalede r_{n}(N)’in polinom kısmının ilk terimini her n için veren bir formül buluyoruz. Ayrıca r_{n}(N) fonksiyonunun N değişkeni üzerinde güçlü bir tekrar denklemi sağladığını gösteriyoruz. Bunu kullanarak n = 3 halini ayrıntılı olarak inceleyebiliyoruz. Bulduğumuz genel sonuçları Hilbert polinomları teorisine uyguluyoruz.