ON THE EXTREMAL ASPECT OF FROBENIUS’ PROBLEM

VSEVOLOD F. LEV

Abstract. The extremal problem of Erdős and Graham concerning the well-known diophantine problem of Frobenius was given an exact solution for linear forms with the set of coefficients of density 1/2 (or more). In the present paper, we advance this up to the density 1/3.

1. Historical review and summary of results

Consider the linear form

a_{1}x_{1} + ⋯ + a_{n}x_{n}

where the variables x_{1}, …, x_{n} are non-negative integers, and the coefficients a_{1}, …, a_{n} are positive integers, co-prime and pairwise distinct:

0 < a_{1} < ⋯ < a_{n}, gcd(a_{1}, …, a_{n}) = 1.

It is well-known, that the above form represents all sufficiently large integers, and it is a custom to denote by G = G(a_{1}, …, a_{n}) the greatest integer which has not such representation. Furthermore, following P. Erdős and R. L. Graham (see [4]), define

g(n, l) = max_{a_{n}=l} G,

the maximum being taken over all sets of n coefficients with the maximal coefficient equal to l (l ≥ n).

As observed without proof in [4], for l ≤ 2n − 1 the exact value of g(n, l) can be determined from simple density considerations:

g(n, l) = 2(l − n) − 1 if l ≤ 2n − 1.  (1)

For l = 2n the problem was solved in [3]:

g(n, 2n) = 2n + 1.

Eventually, for 2n < l ≤ 2n + c\sqrt{n} with sufficiently small positive constant c it was shown in [4] that

g(n, l) = \begin{cases}2(2l − 3n) + 1, if l ≢ 2 (mod 3), \\ 2(2l − 3n) − 1, if l ≡ 2 (mod 3). \end{cases}  (2)

2 VSEVOLOD F. LEV

For l > (2 + ε)n (ε > 0), only certain estimations for g(n, l) were known (cf. [4, 1]).

In this paper, we show (Theorem 4) that (2) holds for much more wide range of l, namely for 2n < l ≤ 3n − 2.

We also give two different proofs of (1): one which was apparently meant by P. Erdős and R. L. Graham, and another one due to an idea, incorporated in that proof and which also will be used in the proof of Theorem 4.

2. Dense sets

We first introduce some designations. For a finite set C ⊂ ℤ by l(C) we denote the difference between the maximal and the minimal elements of C. We say that C is normal if it resides at the segment [0; l(C)] (thus, 0, l(C) ∈ C) and also gcd(C) = 1.

By a gap in C we mean an integer which does not belong to C but fall between the minimal and the maximal elements of C. With the obvious modification, the notion of gap extends to infinite subsets of ℤ. The number of gaps in C will be denoted by g(C) (not to be confused with g(n, l) due to the context and the number and type of the arguments). Obviously, g(C) = l(C) + 1 − |C|.

Normal set C will be said to be dense, if l(C) ≤ 2|C| − 3; in other words, this means g(C) ≤ |C| − 2.

Define now A = {0, a_{1}, …, a_{n}}, l = l(A) = a_{n} (hence |A| = n + 1, l(sA) = sl for s ∈ ℕ) and let

S = S(A) = ⋃_{h=1}^{∞} hA = A ∪ 2A ∪ ⋯

Obviously, S is exactly the set of integers, represented by the original linear form, and therefore

G = G(A) = max_{c∉S(A)} c

is the maximal gap in S (where G(A) abbreviates G(a_{1}, …, a_{n})). Now, in view of i(hA) = (ih)A, iA ⊆ i(hA) (i, h ∈ ℕ) we have:

hS = S, S(hA) = S(A), G(hA) = G(A).

Lemma 1. If c_{1}, …, c_{k} ∈ S, 1 ≤ c_{1} < ⋯ < c_{k} ≤ c, and k ≥ c/2, then c ∈ S.

Proof. If c_{k} = c, there is nothing to proof. Else we have: 1 ≤ c_{1}, …, c_{k}, c − c_{1}, …, c − c_{k} ≤ c − 1, hence c_{i} = c − c_{j} for some i, j, and therefore c = c_{i} + c_{j} ∈ 2S = S. □

Let l ≤ 2n − 1. Clearly, for even l = 2m the set of n + 1 integers

A = {0, 2, …, 2m} ∪ {4m − 2n + 1, 4m − 2n + 3, …, 2m − 1}

ON THE EXTREMAL ASPECT OF FROBENIUS’ PROBLEM 3

satisfies G(A) = 4m − 2n − 1 = 2(l − n) − 1, and also for odd l = 2m + 1 and

A = {0, 2, …, 2m} ∪ {4m − 2n + 3, 4m − 2n + 5, …, 2m + 1}

holds G(A) = 4m − 2n + 1 = 2(l − n) − 1.

The following theorem shows that this was “the worst” case.

Theorem 1 (Erdős-Graham). If A is dense, then G(A) ≤ 2(l − n) − 1. Thus, in view of the examples above,

g(n, l) = 2(l − n) − 1 if l ≤ 2n − 1.

Proof. Put c = 2(l − n) and observe that c < l. There are at least c − g(A) positive elements in A (and therefore, in S), not exceeding c. But c−g(A) ≥ c−|A|+2 = c/2+ (l−2n+1) ≥ c/2, hence c ∈ S by Lemma 1. By induction, also c+1, c+2, … ∈ S. □

Results of this paper will rely on the two following theorems due to G. Freiman (see [2]).

Theorem 2 (Freiman). For normal C holds:

|2C| ≥ min{l(C), 2|C| − 3} + |C|.

Corollary 1. If C is dense, then so is 2C, and in this case g(2C) ≤ g(C). If C is not dense, then |2C| ≥ 3|C| − 3.

Proof. Denote l = l(C). If C is dense, that is l ≤ 2|C|−3, then |2C| ≥ l+|C| > l+3/2, hence l(2C) = 2l < 2|2C|−3 and 2C is dense. Also, in this case g(2C) = 2l+1−|2C| ≤ l + 1 − |C| = g(C).

If C is not dense, the conclusion follows trivially. □

The next theorem follows immediately from another result of Freiman (see [2, Theorem 1.11]).

Theorem 3 (Freiman). Let C be normal, satisfy

|2C| = 3|C| − 3,

and also l(C) ≥ 2|C| − 1. Then either C consists of two arithmetic progressions with the same common difference, or |C| = 6.

We will also use the next lemma which seems to be of an independent interest.

Lemma 2. Let C be dense, and h ≥ 2. Then [l(C); (h − 1)l(C)] ⊂ hC.

4 VSEVOLOD F. LEV

Proof. Denote l = l(C). We start from the first non-trivial case: h = 3. First, show (following [2]) that if C is dense, then 2C may be represented in the form 2C = C′ ∪ (l + C′′), where C′ = 2C ∩ [0; l] and C′′ = (2C − l) ∩ [0; l] satisfy

C′, C′′ ⊇ C, C′ ∪ C′′ = [0; l].

It is enough to show that all residues modulo l occur among the elements of 2C, that is for each s = 1, …, l − 1 at least one of the two numbers s, l + s belongs to 2C. Let C = {c_{1}, …, c_{n}}, where 0 = c_{1} < ⋯ < c_{n} = l, and define i ∈ [1; n−1] by c_{i} < s ≤ c_{i+1}. Then our assertion follows from the fact that all the 2n − 1 > l + 1 numbers

c_{1}, …, c_{n},
s − c_{i}, …, s − c_{1}, l + s − c_{n−1}, …, l + s − c_{i+1}

fall into the interval [0; l] of the length l + 1.

Now

3C = 2C + C = (C′ + C) ∪ (l + C′′ + C) ⊇
⊇ 2C ∪ (l + 2C) ⊇ (l + C′′) ∪ (l + C′) =
= l + C′ ∪ C′′ = [l; 2l] .

The general case h ≥ 4 follows now by induction:

[l; (h − 2)l] ⊂ (h − 1)C ⊂ hC,
[2l; (h − 1)l] ⊂ l + (h − 1)C ⊂ hC .
□

Corollary 2. Assume A to be dense. An integer c > 0 is a gap in S if and only if c < l and also c is a common gap of all the sets A, 2A, …

Proof. If c ≥ l, then choose h in such a way that c ∈ [l; (h−1)l] and get c ∈ hA ⊂ S. □

This corollary shows that gaps in S are exactly those gaps in A which are not overlapped by any element of 2A, 3A, …

Our second proof of Theorem 1 becomes now the matter of a few words.

Second proof of Theorem 1. As we have just saw, g(S) ≤ g(A) = l − n. Hence, by Lemma 1 each integer c ≥ 2(l − n) belongs to S. □

ON THE EXTREMAL ASPECT OF FROBENIUS’ PROBLEM 5

3. Almost dense sets

In this section we assume 2n < l ≤ 3n − 2, or otherwise 2|A| − 2 < l ≤ 3|A| − 5. By Corollary 1 we have then:

|2A| ≥ 3|A| − 3 = 3n ≥ l + 2,
l(2A) = 2l ≤ 2|2A| − 4,

hence 2A is dense. That is why we say that A is “almost dense”.

One of the main goals of this paper is to calculate g(n, l) for such sets. We start with examples, extracted actually from [4] and giving lower bounds for g(n, l).

First, assume l = 3m. Then

A = {0, 3, …, 3m} ∪ {6m − 3n + 2, 6m − 3n + 5, …, 3m − 1}

contains (m + 1) + (n − m) = n + 1 element, and clearly G(A) = 2(6m − 3n + 2) − 3 = 2(2l − 3n) + 1.

Next, assume l = 3m + 1 and consider

A = {0, 3, …, 3m} ∪ {6m − 3n + 4, 6m − 3n + 7, …, 3m + 1}.

Also in this case |A| = n + 1 and G(A) = 2(6m − 3n + 4) − 3 = 2(2l − 3n) + 1. Eventually, assume l = 3m + 2 and put

A = {0, 3, …, 3m} ∪ {6m − 3n + 5, 6m − 3n + 8, …, 3m + 2}.

Here |A| = n + 1 and G(A) = 2(6m − 3n + 5) − 3 = 2(2l − 3n) − 1.

It appears that these estimations are exact.

Theorem 4. Let 2n < l ≤ 3n − 2. Then

g(n, l) = \begin{cases}2(2l − 3n) + 1, if l ≢ 2 (mod 3), \\ 2(2l − 3n) − 1, if l ≡ 2 (mod 3). \end{cases}

Proof. In view of the examples above, it is sufficient to prove that the right-hand side gives an upper estimation for G(A). To this purpose we observe, that as shown at the beginning of this section, |2A| ≥ 3n, and also 2A is dense. Therefore, by Theorem 1

G(A) = G(2A) ≤ 2(l(2A) − (|2A| − 1)) − 1 =
= 2(2l − |2A|) + 1 ≤
≤ 2(2l − 3n) + 1.

This completes the proof for l ≢ 2(mod 3), and it remains to settle the case l ≡ 2 (mod 3). Obviously, the upper bound for l may be slightly improved here: l ≤ 3n − 4.

6 VSEVOLOD F. LEV

Also, we may assume |2A| = 3n = 3|A| − 3, for if |2A| ≥ 3n + 1, the calculation above shows that G ≤ 2(2l − 3n) − 1.

By Theorem 3 and in view of l ≥ 2n + 1 = 2|A| − 1, one of the two possibilities takes place:

i) A consists of two arithmetic progressions with the same common difference; ii) |A| = 6, and thus n = 5.

This two possibilities are considered below.

i) Let d ≥ 1 be the common difference of the progressions. One of the progressions starts at 0, and denote the minimal element of the second progression by c (obviously, gcd(c, d) = 1).

If the first progression contains nothing but 0, then

A = {0, l − (n − 1)d, l − (n − 2)d, …, l},

and l − (n − 1)d ≥ 1, hence

d ≤ ⌊\frac{l − 1}{n − 1}⌋ ≤ ⌊\frac{3n − 5}{n − 1}⌋ ≤ 2.

Therefore, either d = 1 or d = 2. In both cases G(A) may be easily calculated: – If d = 1, then A = {0, l − (n − 1), l − (n − 2), …, l} and

G = 2(l − (n − 1)) − 1 ≤ 2(2l − 3n) − 1.

– If d = 2, then A = {0, l − 2(n − 1), l − 2(n − 2), …, l} and

G = 2(l − 2(n − 1)) − 2 < 2(2l − 3n) − 1.

Hence, we suppose that d ∈ A, and so S together with each element b contains all the elements b + d, b + 2d, … In particular, we see that d > 1, and also it is clear that G = G(c, d) = c(d − 1) − d = (c − 1)(d − 1) − 1. We must show thus that

(c − 1)(d − 1) ≤ 2(2l − 3n).

Consider the possible values of d.

– If d = 2, then

2(2l − 3n) = l + 3(l − 2n) > l > c − 1 = (c − 1)(d − 1).

– If d = 3, then in view of c ≡ l ≡ 2(mod 3) we have:

n ≤ \frac{l − 2}{3} + (\frac{l − c}{3} + 1) = \frac{2l − c + 1}{3},

hence 2l − 3n ≥ c − 1, and so 2(2l − 3n) ≥ 2(c − 1) = (c − 1)(d − 1).

– If d ≥ 4, then we have:

n ≤ ⌊\frac{l}{d}⌋ + (⌊\frac{l − c}{d}⌋ + 1) ≤ \frac{2l − c + d − 1}{d},

hence c ≤ 2l − dn + d − 1, and it follows that

(c − 1)(d − 1) ≤ (d − 1)(2l − dn + d − 2) = −(n − 1)d^{2} + (2l + n − 3)d − (2l − 2).

But the right-hand side is a quadratic polynomial of d with the maximum at

\frac{2l + n − 3}{2(n − 1)} ≤ \frac{7n − 11}{2(n − 1)} < \frac{8n − 8}{2(n − 1)} = 4.

Thus the value of the polynomial for d ≥ 4 is less then

3(2l − 4n + 2) = 2(2l − 3n) + 2(l − 3n + 3) < 2(2l − 3n).

ii) The second possibility is n = 5, and therefore l = 11 in view of 2n+1 = 3n−4 = 11. Since 2(2l − 3n) − 1 = 13, we have to show that 14, 15 ∈ S. By d we denote now the minimal positive element of A, so that 2 ≤ d ≤ 7 (d = 1 would imply S = ℤ^{+}; and d > 7 is incompatible with n = 5, l = 11). Consider the possible values of d.

– If d = 2, then 14 = 7d ∈ S. Also, if c is an odd element of A, then 15 = c + d · (15 − c)/2 ∈ S (since c, d ∈ S).

– If d = 3, then 14 = l + d ∈ S and also 15 = 5d ∈ S.

– If d = 4, then 15 = l + d ∈ S, and as follows from

14 = 2 · 5 + d = 6 + 2d = 2 · 7 = 10 + d,

the condition 14 ∉ S would imply 5, 6, 7, 10 ∉ S. The remaining numbers are only 4, 8, 9, 11, contradicting to n = 5.

– If d = 5, then 15 = 3d ∈ S, and as follows from

14 = 2 · 7 = 6 + 8 = 9 + d,

if 14 ∉ S, then 7, 9 ∉ S and of the two numbers 6, 8 at least one does not belong to S. The remaining numbers are only 5, 10, 11 and at most one of 6, 8, contradicting to n = 5.

– If d = 6, then as follows from

14 = 7 + 7 = 8 + d, 15 = 7 + 8 = 9 + d,

if 14 ∉ S or 15 ∉ S, then of the three numbers 7, 8, 9 at least two do not belong to S. Hence the numbers which possibly belongs to S are only 6, 10, 11 and at most one of 7, 8, 9, — contradiction.

– If d = 7, then A = {7, 8, …, 11}, and hence 14 = 7 + 7 ∈ S, 15 = 7 + 8 ∈ S. This completes the proof. □

References

[1] A. Brauer, On a problem of partitions, Amer. J. Math. 64 (1942), 343–346.

[2] G.A. Freiman, “Foundations of a Structural Theory of Set Addition,” (in Russian), Kazan. Gos. Ped. Inst., Kazan, 1966 = Translation of Mathematical Monographs, Vol. 37, American Mathematical Society, Providence, 1973.

[3] P. Erdős, Problem P-84, Can. Math. Bull. 14 (1971), 275–277.

[4] P. Erdős and R.L. Graham, On a linear diophantine problem of Frobenius, Acta Arith. XXI (1972), 399–408.

School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel-Aviv University, 69978 Tel-Aviv, Israel