THE CONTINUOUS POSTAGE STAMP PROBLEM

VSEVOLOD F. LEV

Abstract. For a real set A consider the semigroup S(A), additively generated by A; that is, the set of all real numbers representable as a (finite) sum of elements of A. If A ⊆ (0, 1) is open and non-empty, then S(A) is easily seen to contain all sufficiently large real numbers, and we let G(A) := sup{u ∈ ℝ: u ∉ S(A)}. Thus G(A) is the smallest number with the property that any u > G(A) is representable as indicated above.

We show that if the measure of A is large, then G(A) is small; more precisely, writing for brevity α := mes A we have

G(A) ≤ \begin{cases}(1 − α) ⌊1/α⌋ & if 0 < α ≤ 0.1, \\ (1 − α + α\{1/α\}) ⌊1/α⌋ & if 0.1 ≤ α ≤ 0.5, \\ 2(1 − α) & if 0.5 ≤ α ≤ 1. \end{cases}

Indeed, the first and the last of these three estimates are the best possible, attained for A = (1 − α, 1) and A = (1 − α, 1) \ {2(1 − α)}, respectively; the second is close to the best possible and can be improved by α{1/α} ⌊1/α⌋ ≤ {1/α} at most.

The problem studied is a continuous analogue of the linear Diophantine problem of Frobenius (in its extremal settings due to Erdős and Graham), also known as the “postage stamp problem” or the “coin exchange problem”.

1. Background: the discrete postage stamp problem

Let A be a non-empty set of positive integers such that gcd(A) = 1. It is not difficult to see that all sufficiently large integers can be represented as a sum of elements of A. The problem of determining the largest integer G(A) which does not have such a representation is known as the “linear Diophantine problem of Frobenius”. Though this problem is computational by its nature, there are numerous papers concentrating on estimates of G(A).

Erdős and Graham posed in [EG72] the following extremal version of the Frobenius problem: given two positive integers l ≥ n, estimate

max{G(A): A ⊆ [1, l], |A| = n, gcd(A) = 1}.  (1)

The ideology here is that if A is dense, then G(A) must be small. The basic result on the problem of Frobenius-Erdős-Graham was obtained by Dixmier in [D90]. (Several years later it was independently established by the present author as a corollary of a general theorem on set addition; see [L97].) The exact value of (1) is known for some particular families of pairs (n, l) only, and also for l ≤ 3n − 2; see [L96a].

1991 Mathematics Subject Classification. Primary: 11P99, secondary: 11B13.

2. Preliminaries: examples and summary of results

Motivated by their work on primality testing, Lenstra and Pomerance [LP03] stated recently an analogue of the Frobenius-Erdős-Graham problem for bounded sets A of positive real numbers. The condition gcd(A) = 1 becomes then irrelevant, and scaling allows one to assume A ⊆ (0, 1); thus, the parameter l is gone. Furthermore, following [LP03] we assume that A is open; this ensures measurability and forces A to be a finite or countable union of open intervals. Let S(A) denote the set of all numbers, representable as a finite sum of elements of A; thus

S(A) = ⋃_{h=1}^{∞} hA,

where hA is the set of all sums of exactly h elements of A.

Is it true, by the analogy with the integer case, that S(A) contains all sufficiently large numbers? Set

G(A) := sup{u ∈ ℝ: u ∉ S(A)};

the question therefore is whether G(A) is finite for any open non-empty subset A ⊆ (0, 1). To proceed, we work out a simple, yet important, example.

Example 1. Suppose that A consists of one single interval: A = (β, γ), where γ > β ≥ 0. Then for h ≥ 1 we have hA = (hβ, hγ), hence hA and (h + 1)A intersect if and only if hγ > (h + 1)β, or equivalently h > β/(γ − β); that is,

h ≥ ⌊\frac{β}{γ − β} ⌋ + 1 = ⌊\frac{γ}{γ − β} ⌋ .

It follows that G(A) = ⌊γ/(γ − β)⌋ β. In particular, if A = (1 − α, 1) with α ∈ (0, 1] (so that α = mes A), then G(A) = (1 − α) ⌊1/α⌋.

Back to the general case, suppose that A ⊆ (0, 1) is open and non-empty. Then A contains an open interval; say, (β, γ) ⊆ A. In view of Example 1 every u > ⌊γ/(γ − β)⌋ β is representable as a sum of elements of (β, γ), hence as a sum of elements of A; this shows that G(A) is finite and indeed that G(A) ≤ ⌊γ/(γ − β)⌋ β.

The exact problem raised in [LP03] is to determine, for a fixed real number s > 0, how large the logarithmic measure ∫_{A} t^{−1} dt of an open subset A ⊆ (0, 1) can be, given that s ∉ S(A). This is essentially equivalent to the following question: given the logarithmic measure of A, how large can G(A) be? It is this question that is investigated in our paper, except that, following the lines of the classical Frobenius-Erdős-Graham problem, we will be concerned with the regular Lebesgue measure mes A rather than the logarithmic measure.^{1}

We now present two constructions of open sets A ⊆ (0, 1) such that, letting α = mes A, we have G(A) > (1 − α) ⌊1/α⌋ (compare with Example 1).

1For a complete solution of the original problem of Lenstra and Pomerance see the paper of Bleichenbacher [B03]. The method of Bleichenbacher is based on linear programming and can be applied to handle the Lebesgue measure, too; however in this case it yields somewhat weaker results.

Example 2. Suppose that α ∈ (1/2, 1] and set A := (1 − α, 1) \ {2(1 − α)}. Then for h ≥ 2 we have hA = (h(1 − α), h) ⊇ [h − 1, h), whence

S(A) ⊇ ⋃_{h=2}^{∞}[h − 1, h) = [1, ∞)

and therefore G(A) = 2(1 − α).

Our second construction is more elaborate.

Example 3. Suppose that α ∈ (1/3, 1/2). Write

k := ⌈\frac{1}{1 − 2α}⌉ − 2, x := 1 − \frac{1}{k + 2}, and t := 2(1 − \frac{1}{k + 3})(1 − α),

so that k ≥ 2. One checks easily that

\frac{1}{2} (1 − \frac{1}{k + 1}) < α ≤ \frac{1}{2} (1 − \frac{1}{k + 2})

and

1 − \frac{1}{k} < x < \frac{1}{t} ≤ 1,

and we let

A := (\frac{tx}{k} , \frac{t}{k} ) ∪ (\frac{2tx}{k} , \frac{2t}{k}) ∪ ⋯ ∪ (\frac{(k − 1)tx}{k} , \frac{(k − 1)t}{k}) ∪ (tx , 1).

A routine verification shows that mes A = α; on the other hand,

G(A) = G((\frac{tx}{k} , \frac{t}{k} )) = \frac{t}{k} G((x, 1))

= \frac{t}{k} x ⌊\frac{1}{1 − x}⌋ = \frac{k + 1}{k} t = 2\frac{(k + 1)(k + 2)}{k(k + 3)} (1 − α)

= 2(1 + \frac{2}{k(k + 3)})(1 − α) > (1 − α) ⌊1/α⌋ .

We are now ready to state the main result of our paper.

Main Theorem. Let A ⊆ (0, 1) be an open set of measure α ∈ (0, 1]. Then

G(A) ≤ \begin{cases}(1 − α) ⌊1/α⌋ & if 0 < α ≤ 0.1, \\ (1 − α + α\{1/α\}) ⌊1/α⌋ & if 0.1 ≤ α ≤ 0.5, \\ 2(1 − α) & if 0.5 ≤ α ≤ 1. \end{cases}

As Examples 1 and 2 show, the first and the last of these three estimates are sharp while the second estimate can be improved by at most α {1/α} ⌊1/α⌋ ≤ {1/α}. On the other hand, we suspect that the first estimate can be extended onto the wider range α ∈ (0, 1/3]. Indeed, for no α ∈ (0, 1) were we able to construct an open set A ⊆ (0, 1) of measure α with G(A) larger than that provided by Examples 1–3.

We believe that with a slight refinement of our method one can replace 0.1 in the statement of the Main Theorem by a somewhat larger value; perhaps, 1/8 or so. However, to get closer to 1/3 one needs substantially new ideas.

The rest of this paper is devoted to the proof of the Main Theorem. In Section 3 we first settle the case of dense sets (α > 0.5); this is a simple part of the argument requiring nothing but an iterated application of the box principle. Using a theorem by Macbeath on addition of subsets of the torus group, we then derive the estimate for the range α ≥ 0.1.

The case α ≤ 0.1 is much subtler. In Section 4 we collect a number of auxiliary results from different sources needed to handle this case. Two more auxiliary results are established in Section 5. Having finished the preparations, we complete our treatment of the “sparse case” in Section 6.

3. Proof of the Main Theorem: 0.1 ≤ α ≤ 1

We use the box principle in the following “continuous” form.

Lemma 1. Let v be a positive real number and suppose that an open subset A ⊆ (0, v) satisfies mes A > v/2. Then v ∈ 2A.

Proof. Just notice that the sets A ⊆ (0, v) and v − A := {v − a: a ∈ A} ⊆ (0, v) have a non-empty intersection in view of mes A + mes(v − A) = 2 mes A > v. □

Proof of the Main Theorem for 0.5 < α ≤ 1. Suppose that A ⊆ (0, 1) is an open set with α := mes A ∈ (0.5, 1]; we are to show that (2(1 − α), ∞) ⊆ S(A).

First we observe that (2(1 − α), 1] ⊆ S(A): for if 2(1 − α) < u ≤ 1 then mes(A ∩ (0, u)) ≥ α − (1 − u) > u/2, hence u ∈ 2A ⊆ S(A) by Lemma 1.

Next we claim that [1, 2α) ⊆ S(A): this is because for any u ∈ [1, 2α) we can consider A as an open subset of (0, u) of measure α > u/2, and the claim follows by Lemma 1.

Finally, we use induction to prove that [1, 2^{k}(2α − 1) + 2(1 − α)) ⊆ S(A) for any integer k ≥ 1. For k = 1 this reduces to [1, 2α) ⊆ S(A), proven above. Suppose that k ≥ 2. Then by the induction hypothesis for any u satisfying

2^{k−1}(2α − 1) + 2(1 − α) ≤ u < 2^{k}(2α − 1) + 2(1 − α)

we have

mes(S(A) ∩ (0, u)) ≥ α + (2^{k−1}(2α − 1) + 2(1 − α) − 1)

= 2^{k−1}(2α − 1) + (1 − α) > u/2,

whence u ∈ 2S(A) = S(A) by Lemma 1. This proves the Main Theorem for the case 0.5 < α ≤ 1. □

We recall a classical theorem by Macbeath on addition of torus subsets.^{2} In this theorem and throughout the rest of the paper, for an integer h ≥ 1 and subsets A_{1}, …, A_{h} of an abelian group, we write

2In fact, the original Macbeath’ theorem is slightly stronger than its version presented below.

A_{1} + … + A_{h} := {a_{1} + … + a_{h}: a_{1} ∈ A_{1}, …, a_{h} ∈ A_{h}}.

We use the abbreviation hA for the sum of h instances of the same set A. (For the special case where A is an open subset of (0, 1) this notation was introduced at the beginning of Section 2.)

Theorem 1 (Macbeath [M53]). Suppose that A and B are open subsets of the torus group ℝ/ℤ. Then

mes(A + B) ≥ min{mes A + mes B, 1}.

Proof of the Main Theorem for 0.1 ≤ α ≤ 0.5. We actually show that if A ⊆ (0, 1) is a non-empty open set with α := mes A ≤ 0.5, then G(A) ≤ (1 − α + α {1/α}) ⌊1/α⌋; this strengthening of the second inequality of the Main Theorem will be used in Section 6 in the course of the proof of the first inequality.

Write σ := sup A and let A′ := {σ^{−1}a: a ∈ A}. Consider an open subset A_{0} ⊆ A′ such that mes A_{0} = α and sup A_{0} = 1. Then G(A) = σG(A′) ≤ σG(A_{0}) ≤ G(A_{0}), which shows that sup A = 1 can be assumed without loss of generality.

For positive integer j, set S_{j} := S(A) ∩ (j − 1, j), and denote by \overline{A} and \overline{S}_{j} the canonical images of A and S_{j}, respectively, in the torus group ℝ/ℤ. In view of the assumption sup A = 1 and since S_{j} are open sets, we have S_{j} + 1 ⊆ S_{j+1}, implying \overline{S}_{j} ⊆ \overline{S}_{j+1}. Now from S_{j} + A ⊆ S_{j} ∪ S_{j+1} ∪ \{j\} we get \overline{S}_{j} + \overline{A} ⊆ \overline{S}_{j} ∪ \overline{S}_{j+1} ∪ \{0\} = \overline{S}_{j+1} ∪ \{0\}, whence mes S_{j+1} ≥ min\{mes S_{j} + α, 1\} by Theorem 1. Induction by j yields

mes S_{j} ≥ min{jα, 1}; j ≥ 1.  (2)

Let k := ⌊1/α⌋ and write T := S(A) ∩ (0, k). By (2) we have

mes T = mes S_{1} + mes S_{2} + … + mes S_{k} ≥ (k(k + 1)/2) α > k/2.

Consequently, applying the third inequality of the Main Theorem (established above) to the open set T′ := {k^{−1}t: t ∈ T } ⊆ (0, 1) of measure mes T′ = k^{−1} mes T > 0.5, we obtain

G(A) = G(T) = kG(T′) ≤ 2k(1 − mes T′) = 2k(1 − k^{−1} mes T)

≤ 2k(1 − ((k + 1)/2)α) = (2 − (⌊1/α⌋ + 1) α) ⌊1/α⌋

= (1 − α + α{1/α}) ⌊1/α⌋ ,

as required. □

4. Auxiliary results

We gather here several results that will be used in Sections 5 and 6 to prove the first inequality of the Main Theorem.

We start with a basic theorem by Cauchy and Davenport. For a positive integer p by ℤ/pℤ we denote the group of residues modulo p.

Theorem 2 (Cauchy-Davenport [C13, D35]). For any prime p and any non-empty subsets A, B ⊆ ℤ/pℤ we have

|A + B| ≥ min{|A| + |B| − 1, p}.

Straightforward induction yields |A_{1} +…+A_{h}| ≥ min{|A_{1}|+…+|A_{h}|−(h−1), p} for any integer h ≥ 2 and non-empty subsets A_{1}, …, A_{h} ⊆ ℤ/pℤ. This readily implies the following corollary.

Corollary 1. Let h be a positive integer and p a prime number. Suppose that nonempty subsets A_{1}, …, A_{h} ⊆ ℤ/pℤ satisfy A_{1} + … + A_{h} ≠ ℤ/pℤ. Then

|A_{1}| + … + |A_{h}| ≤ p + h − 2.

The next lemma is due to Freiman. For a set S ⊆ ℝ denote by S (mod 1) the canonical image of S in the torus group ℝ/ℤ.

Lemma 2 (Freiman [F62]). Let n be a positive integer and let z_{1}, …, z_{n} ∈ ℝ/ℤ. Write S := ∑_{j=1}^{n} e^{2πiz_{j}}. Then there exists a real number β such that

#\{j ∈ [1, n]: z_{j} ∈ [β, β + 1/2) (mod 1)\} ≥ \frac{n + |S|}{2}.

We need yet another well-known result by Freiman.

Theorem 3 (Freiman, see [F66, Theorem 1.9]). Let A be a finite set of integers such that min A = 0 and gcd A = 1. Write n := |A| and l := max A. Then

|2A| ≥ min{l, 2n − 3} + n.

Now we quote a theorem by the present author which extends Theorem 3 to the case of h-fold set addition for any positive integer h.

Theorem 4 (Lev [L96b, Corollary 1]). Let A be a finite set of integers such that min A = 0 and gcd A = 1. Write n := |A|, l := max A, and κ := ⌊(l − 1)/(n − 2)⌋. Then for any integer h ≥ 1 we have

|hA| ≥ \begin{cases}\frac{h(h+1)}{2} (n − 2) + h + 1 & if h ≤ κ, \\ \frac{κ(κ+1)}{2} (n − 2) + κ + 1 + (h − κ)l & if h ≥ κ. \end{cases}

Corollary 2. Let A be a finite set of n := |A| ≥ 3 integers such that min A = 0 and gcd A = 1. Suppose that l := max A ≤ 2n − 4. Then for any integer h ≥ 1 we have

|hA| ≥ n + (h − 1)l.

Finally, we present a result which describes the structure of the sets hA and shows that under certain conditions, these sets contain long blocks of consecutive integers.

Theorem 5 (Lev, reformulation of [L97, Theorem 1]). Let A be a finite set of integers such that min A = 0 and gcd A = 1. Write n := |A|, l := max A, and κ := ⌊(l − 1)/(n − 2)⌋. Then for any integer h ≥ 2κ we have

[(2l − (κ + 1)(n − 2) − 2)κ, hl − (2l − (κ + 1)(n − 2) − 2)κ] ⊆ hA.

5. More auxiliary results

In this section we establish two more results needed to complete the proof of the Main Theorem. The first one is a “continuous version” of Theorem 5.

Theorem 6. Let A ⊆ (0, 1) be an open set such that inf A = 0 and sup A = 1. Write α := mes A and κ := ⌊1/α⌋. Then for any integer h ≥ 2κ we have

((2 − (κ + 1)α)κ, h − (2 − (κ + 1)α)κ) ⊆ hA.

A simple rescaling yields the following corollary.

Corollary 3. Let A be a non-empty bounded open set of real numbers. Write

v := inf A, w := sup A, λ := w − v, α := mes A, κ := ⌊λ/α⌋ .

Then for any integer h ≥ 2κ we have

(vh + (2λ − (κ + 1)α)κ, wh − (2λ − (κ + 1)α)κ) ⊆ hA.

Proof of Theorem 6. First we prove the assertion assuming that A is a union of a finite number, say m, of open intervals. For a sufficiently large integer l (it will be seen shortly what is sufficient for our purposes) define

A_{l} := {0} ∪ {z ∈ ℤ: [z/l, (z + 1)/l) ⊆ A}

and set n := |A_{l}|, so that A_{l} ⊆ [0, l − 1] and

αl − 2m + 1 ≤ n < αl + 1.  (3)

We have min A_{l} = 0, max A_{l} = l−1 since sup A = 1, and gcd A_{l} = 1 since A_{l} contains consecutive integers.

Let k := ⌊(l − 2)/(n − 2)⌋. By (3),

k ≤ \frac{l − 2}{n − 2} < \frac{1}{α} \frac{n + 2m}{n − 2} = \frac{1}{α} + O(1/n)

with the implicit constant depending on m and α, and it follows that k ≤ κ. On the other hand, we claim that k ≥ κ. Indeed, this is clear if α > 1/2 (where κ = 1), while for α ≤ 1/2 from (3) we get n < l/2 + 1 whence l > 2n − 2 and therefore

\frac{l − 2}{n − 2} > \frac{l}{n − 1} > \frac{1}{α} ≥ κ.

Thus, k = κ and by Theorem 5 as applied to the set A_{l} we have

[(2l − (κ + 1)(n − 2) − 4)κ, h(l − 1) − (2l − (κ + 1)(n − 2) − 4)κ] ⊆ hA_{l},

hence

[(2 − \frac{(κ + 1)(n − 2) + 4}{l}) κ, h − \frac{1}{l} − (2 − \frac{(κ + 1)(n − 2) + 4}{l}) κ] ⊆ hA.

It remains to notice that

(κ + 1)(n − 2) + 4 > (κ + 1)(αl − 2m − 1) = (κ + 1)αl + O(1).

Now that Theorem 6, and therefore Corollary 3, are established when A is a finite union of intervals, we turn to the general case. Evidently, for any set A satisfying the assumptions of the theorem and any ε > 0 we can find a subset A′ ⊆ A which is a union of a finite number of intervals and such that v′ := inf A′ < ε, w′ := sup A′ > 1 − ε, and α′ := mes A′ > α − ε. If ε is small enough then ⌊1/α′⌋ = ⌊1/α⌋ and applying Corollary 3 to the set A′ we get

(v′h + (2(w′ − v′) − (κ + 1)α′)κ, w′h − (2(w′ − v′) − (κ + 1)α′)κ) ⊆ hA′ ⊆ hA.

The assertion follows. □

Another result of this section can be considered as a strengthening of Corollary 1 for the special case of equal set summands. Its proof roughly follows the lines of a well-known argument by Freiman (see [F66, Theorem 2.1]).

For a positive integer p and an integer set S, by S (mod p) we denote the canonical image of S in the residue group ℤ/pℤ. The set of non-zero elements of ℤ/pℤ is denoted (ℤ/pℤ)^{×}.

Lemma 3. For any integer k ≥ 8 there exists an integer p_{0} with the following property. Let p > p_{0} be a prime number and suppose that a set A ⊆ ℤ/pℤ satisfies n := |A| > p/(k + 1) and kA ≠ ℤ/pℤ. Then A is contained in an arithmetic progression of at most (p − 2n)/(k − 2) + 1 terms.

Proof. We split the argument into several steps.

Step 1. For z ∈ ℤ/pℤ set Â(z) := ∑_{a∈A} e^{−2πiaz/p} and let M := max{|Â(z)|: z ∈ (ℤ/pℤ)^{×}}. Fix an element g ∈ ℤ/pℤ such that g ∉ kA. Then

∑_{z=0}^{p−1} (Â(z))^{k}e^{2πi \frac{gz}{p}} = 0

and using Parseval’s identity we get

n^{k} = − ∑_{z=1}^{p−1} (Â(z))^{k}e^{2πi \frac{gz}{p}} ≤ ∑_{z=1}^{p−1} |Â(z)|^{k} ≤ M^{k−2} ∑_{z=1}^{p−1} |Â(z)|^{2} = M^{k−2}n(p − n).

It follows that

M ≥ n (\frac{n}{p − n})^{1/(k−2)} > κn

with κ := k^{−1/(k−2)}. Choose z ∈ (ℤ/pℤ)^{×} so that M = |Â(z)| and therefore |Â(z)| > κn. By Lemma 2 there exists an integer u such that

#\{a ∈ A: az ∈ [u, u + (p − 1)/2] (mod p)\} > \frac{1 + κ}{2} n.

Thus, if d is the inverse of z modulo p and if we set v := du then, letting A_{1} := {v, v + d, …, v + ((p − 1)/2)d} ∩ A and n_{1} := |A_{1}|, we have

n_{1} > \frac{1 + κ}{2} n.  (4)

Set B_{1} := {b ∈ [0, (p − 1)/2]: v + bd ∈ A_{1}}. Applying a suitable linear transformation to A, we can assume without violating (4) that v = 0 ∈ A_{1} (whence min B_{1} = 0), d = 1, and gcd(B_{1}) = 1, and we write then l_{1} := max B_{1}. Thus B_{1} ⊆ [0, l_{1}] and A_{1} = B_{1} (mod p). Evidently, we have |B_{1}| = |A_{1}| and since l_{1} ≤ (p − 1)/2 it is easily seen that |2A_{1}| = |2B_{1}|.

Step 2. We claim that l_{1} < p/6. First, we prove that l_{1} ≤ 2n_{1} − 4. For, assuming l_{1} ≥ 2n_{1} − 3, by Theorem 3 we obtain |2A_{1}| = |2B_{1}| ≥ 3n_{1} − 3; then in view of 2A_{1} + 2A_{1} + (k − 4)A ⊆ kA ≠ ℤ/pℤ, applying Corollary 1 to two instances of the set 2A_{1} and k − 4 instances of the set A we get

p + k − 4 ≥ 2|2A_{1}| + (k − 4)|A| > (6n_{1} − 6) + (k − 4) n

> (3(κ + 1) + (k − 4)) n − 6 > \frac{k − 1 + 3κ}{k + 1} p − 6

= p + \frac{3κ − 2}{k + 1} p − 6. (5)

However, since 3κ > 2 this is wrong for sufficiently large p, a contradiction. We see that l_{1} ≤ 2n_{1} − 4 and applying Theorem 3 once again we get

|2A_{1}| = |2B_{1}| ≥ n_{1} + l_{1}.  (6)

If k is even then from (k/2)(2A_{1}) ⊆ kA ≠ ℤ/pℤ, applying Corollary 1 to k/2 instances of the set 2A_{1} we get

p + \frac{k}{2} − 2 ≥ \frac{k}{2} |2A_{1}| ≥ \frac{k}{2} (n_{1} + l_{1}),

hence

l_{1} < \frac{2}{k} p − n_{1} + 1 < (\frac{2}{k} − \frac{κ + 1}{2(k + 1)}) p + 1 < \frac{1}{6} p,

as the expression in the parentheses is smaller than 1/6 for k ≥ 8. Similarly, if k is odd then from \frac{k−1}{2} (2A_{1}) + A ⊆ kA ≠ ℤ/pℤ we obtain

p + \frac{k + 1}{2} − 2 ≥ \frac{k − 1}{2} (l_{1} + n_{1}) + n

which yields

l_{1} < \frac{2}{k − 1} p − (\frac{2}{k − 1} + \frac{κ + 1}{2}) n + 1

< (\frac{2}{k − 1} − \frac{2}{k^{2} − 1} − \frac{κ + 1}{2(k + 1)}) p + 1

= (\frac{2k}{k^{2} − 1} − \frac{κ + 1}{2(k + 1)}) p + 1 < \frac{1}{6} p,

as the expression in the last pair of parentheses is smaller than 1/6 for k ≥ 9.

Step 3. Our next claim is that A ⊆ [−l_{1}, 2l_{1}](mod p); informally, if we extend the interval [0, l_{1}](mod p) (in which A_{1} resides) by l_{1} in both directions, then the resulting interval covers the whole set A. This follows from the observation that if a ∈ A is not contained in this extended interval, then 2A_{1} and a + A_{1} are disjoint subsets of 2A; hence |2A| ≥ |a + A_{1}| + |2A_{1}| ≥ 2n_{1} + l_{1} ≥ 3n_{1} − 1 by (6); this, however, leads to a contradiction as in (5): just notice that 2A + 2A + (k − 4)A ≠ ℤ/pℤ and apply Corollary 1 to two instances of 2A and k − 4 instances of A. This shows that A is contained in a set of 3l_{1} + 1 ≤ (p + 1)/2 consecutive elements of ℤ/pℤ, and applying again a suitable linear transformation to A we can assume that A = B (mod p) for a set B ⊆ [0, (p − 1)/2] such that 0 ∈ B and gcd B = 1.

Step 4. Let l := max B. We have

l ≤ 2n − 4 :  (7)

for otherwise |2A| = |2B| ≥ 3n − 3 by Theorem 3 and again we get a contradiction as in (5). Applying Theorem 3 once again we get |2A| = |2B| ≥ l + n. Now by Corollary 1 for k even from (k/2)(2A) ≠ ℤ/pℤ we obtain

p + \frac{k}{2} − 2 ≥ \frac{k}{2} |2A| ≥ \frac{k}{2} (l + n),

l < \frac{2}{k} p − n + 1 < (\frac{2}{k} − \frac{1}{k + 1}) p + 1 < \frac{p}{k − 1}  (8)

and for k odd from \frac{k−1}{2}(2A) + A ≠ ℤ/pℤ we obtain

p + \frac{k + 1}{2} − 2 ≥ \frac{k − 1}{2} |2A| + |A| ≥ \frac{k − 1}{2} (l + n) + n,

l < \frac{2}{k − 1} p − (1 + \frac{2}{k − 1}) n + 1 = \frac{2}{k − 1} p − \frac{k + 1}{k − 1} n + 1 < \frac{p}{k − 1} + 1. (9)

Step 5. From (8), (9), and the definition of l we conclude that

|(k − 1)A| ≥ |(k − 1)B| − k,  (10)

hence recalling (7) and using Corollary 2 we get |(k − 1)A| ≥ n + (k − 2)l − k. Now applying Corollary 1 to the sets (k − 1)A and A we obtain

p ≥ 2n + (k − 2)l − k,  (11)

implying

l < \frac{p − 2n}{k − 2} + 2 < \frac{1 − 2/(k + 1)}{k − 2} p + 2 < \frac{p}{k − 1}

an thus providing a small, but important strengthening of (9). Now (10) can be strengthened to |(k − 1)A| = |(k − 1)B|, and accordingly (11) to p ≥ 2n + (k − 2)l. Therefore l ≤ (p − 2n)/(k − 2) from which the assertion follows. This proves Lemma 3. □

6. Proof of the Main Theorem: 0 < α ≤ 0.1

Proof of the Main Theorem for 0 < α ≤ 0.1. Write k := ⌊1/α⌋ ≥ 10 and suppose, for a contradiction, that G(A) > (1 − α)k. As in the proof of Lemma 3, we proceed by steps.

Step 1. Without loss of generality we can assume that A satisfies the following three conditions:

(i) A is a finite union of open intervals; (ii) (2A) ∩ (0, 1) = A (informally, “A is closed under addition in (0, 1)”); (iii) sup A = 1.

For if (i) fails, we consider a subset A′ ⊆ A which is a finite union of open intervals and the measure of which α′ := mes A′ is sufficiently close to α; specifically, we request that ⌊1/α′⌋ = k and G(A) > (1 − α′)k. Then G(A′) ≥ G(A) > (1 − α′)k and we simply replace A with A′ and α with α′.

Now assume that (i) holds and replace A with A′′ := S(A) ∩ (t, 1), where t ∈ [0, 1) is so chosen that mes A′′ = α. Clearly, this new set remains a finite union of open intervals and in addition satisfies (2A′′)∩(0, 1) = A′′. Also, G(A′′) ≥ G(A) > (1−α)k.

Eventually, assuming both (i) and (ii) write σ := sup A and replace A with A′′′ := {σ^{−1}a: a ∈ A}∩(t, 1), where (as above) we choose t ∈ [0, 1) so that mes A′′′ = α. Then (i) and (ii) remain valid and (iii) becomes true, too, while G(A′′′) ≥ G(A) > (1−α)k.

Let m denote the number of intervals in A.

Step 2. Write \overline{A} := A(mod 1); we claim that

k(\overline{A} ∪ \{0\}) ≠ ℝ/ℤ.  (12)

Assume the opposite. Then for any real u ∈ (k − 1, k) there exist integers s ∈ [1, k] and z ≥ 0 and elements a_{1}, …, a_{s} ∈ A such that u = a_{1} + … + a_{s} + z. Since A is an open set and in view of sup A = 1 we conclude that u ∈ S(A), whence

(k − 1, k) ⊆ S(A).  (13)

However, as shown in Section 3 (see remark at the beginning of the proof of the Main Theorem for 0.1 ≤ α ≤ 0.5) we have

G(A) ≤ (1 − α + α{1/α})k < k.  (14)

Comparing (13) and (14) we get G(A) ≤ k − 1 ≤ (1 − α)k, a contradiction establishing (12).

Fix a large prime number p (it can be figured out from the subsequent argument exactly how large p is to be) and define

A_{p} := {0} ∪ {z ∈ ℤ: [z/p, (z + 1)/p) ⊆ A},

so that A_{p} ⊆ [0, p − 1]. Write \overline{A}_{p} := A_{p} (mod p) and let z ∈ [1, p − 1]. If the canonical image \overline{z} of z in ℤ/pℤ satisfies \overline{z} ∈ k\overline{A}_{p}, then clearly [z/p, (z + 1)/p)(mod 1) ⊆ k(\overline{A} ∪ \{0\}). It follows that k\overline{A}_{p} = ℤ/pℤ would imply [1/p, 1)(mod 1) ⊆ k(\overline{A} ∪ \{0\}), which is wrong for sufficiently large p in view of (12) and 0 ∈ k(\overline{A} ∪ \{0\}). Thus

k\overline{A}_{p} ≠ ℤ/pℤ.  (15)

Step 3. Set n := |\overline{A}_{p}|. By (i), for p large enough we have

n = αp + O(1) > p/(k + 1)  (16)

(with the implicit constant depending on the number of intervals m). By (15), (16), and Lemma 3, there exist \overline{d} ∈ [1, (p − 1)/2](mod p) and non-negative integers n_{1}, n_{2} such that

n_{1} + n_{2} ≤ \frac{p − 2n}{k − 2}  (17)

and \overline{A}_{p} ⊆ \{−n_{1}\overline{d}, …, −\overline{d}, 0, \overline{d}, …, n_{2}\overline{d}\}. (Recall, that 0 ∈ A_{p}.) Clearly, we can assume without loss of generality that −n_{1}\overline{d}, n_{2}\overline{d} ∈ \overline{A}_{p}. Let d ∈ [1, (p − 1)/2] be the integer such that \overline{d} is the canonical image of d.

Evidently, \overline{A}_{p} is a union of at most m + 1 arithmetic progressions with difference 1. The longest of these progressions has at least n/(m + 1) terms, hence there exist integers s ≥ n/(m + 1) and x_{1}, …, x_{s} ∈ [−n_{1}, n_{2}] such that

(x_{i+1} − x_{i})d ≡ 1 (mod p);  i = 1, …, s − 1.  (18)

Define d′ ∈ (−p/2, p/2) by dd′ ≡ 1(mod p). Multiplying (18) by d′ we get x_{i+1}−x_{i} ≡ d′ (mod p) whence x_{i+1} − x_{i} = d′ and therefore x_{s} − x_{1} = (s − 1)d′, implying

|d′| ≤ \frac{n_{2} + n_{1}}{s − 1} < \frac{p}{k − 2} \frac{3m}{n} < \frac{k + 1}{k − 2} · 3m < 5m  (19)

by (16) and (17).

We have either |dd′| = 1, in which case d = 1, or |dd′| ≥ p − 1, and then

d ≥ \frac{p − 1}{5m − 1} > \frac{p}{5m}  (20)

by (19). We proceed to show that indeed d = 1.

Step 4. Assume that (20) holds true. We observe that property (ii) implies

2(\overline{A}_{p} ∩ [0, (p − 1)/2] (mod p)) ⊆ \overline{A}_{p}.  (21)

It follows, in particular, that

n_{1}\overline{d} ∈ [0, (p − 1)/2] (mod p) :  (22)

for otherwise −n_{1}\overline{d} ∈ [1, (p − 1)/2](mod p) and then −2n_{1}\overline{d} ∈ \overline{A}_{p} by (21), hence −2n_{1} ∈ [−n_{1}, n_{2}], which is wrong. Similarly,

n_{2}\overline{d} ∈ [(p + 1)/2, p] (mod p).  (23)

Set

N_{1} := #\{x ∈ [−n_{1}, −n_{1}/2): x\overline{d} ∈ [0, (p − 1)/2] (mod p)\}
= #\{x ∈ (n_{1}/2, n_{1}]: x\overline{d} ∈ [(p + 1)/2, p] (mod p)\}

and

N_{2} := #\{x ∈ (n_{2}/2, n_{2}]: x\overline{d} ∈ [0, (p − 1)/2] (mod p)\}.

We show that

N_{i} ≥ \frac{n_{i}}{8} − \frac{p}{2d};  i = 1, 2;  (24)

then in view of (20), (17), and (16) we will get

N_{1} + N_{2} ≥ \frac{n_{1} + n_{2}}{8} − \frac{p}{d}

> n_{1} + n_{2} − \frac{7}{8} (n_{1} + n_{2}) − 5m

≥ n_{1} + n_{2} − \frac{7}{8} \frac{p − 2n}{k − 2} − 5m

= n_{1} + n_{2} − n + \frac{4k − 1}{4(k − 2)} n − \frac{7}{8} \frac{p}{k − 2} − 5m

> n_{1} + n_{2} − n + \frac{1}{8(k − 2)} (\frac{2(4k − 1)}{k + 1} − 7) p − 5m

= n_{1} + n_{2} − n + \frac{k − 9}{8(k − 2)(k + 1)} p − 5m

> n_{1} + n_{2} + 1 − n

so that there exists an integer x ∈ [−n_{1}, −n_{1}/2) ∪ (n_{2}/2, n_{2}] such that x\overline{d} ∈ \overline{A}_{p} ∩ [0, (p − 1)/2](mod p). Considering the doubling 2x\overline{d} and taking into account (21) we obtain then a contradiction.

Step 5. As we have just shown, to prove that d = 1 it suffices to establish (24). We address the estimate of N_{1} only; N_{2} can be estimated in a similar way. Clearly, we can assume that n_{1} > 0, and then by (22) there exists a non-negative integer t such that

\frac{2tp}{2d} ≤ n_{1} < \frac{(2t + 1)p}{2d}.

For any integer s ∈ [(t/2) + 1, t] we have

\frac{(2s − 1)p}{2d} ≥ \frac{(t + 1)p}{2d} > \frac{n_{1}}{2} and \frac{2sp}{2d} ≤ \frac{2tp}{2d} ≤ n_{1},

hence the interval

I_{s} := (\frac{(2s − 1)p}{2d}, \frac{2sp}{2d}]

satisfies I_{s} ⊆ (n_{1}/2, n_{1}]. The length of I_{s} is p/(2d) > 1; thus the number of integers x ∈ I_{s} is at least p/(4d) and evidently, \overline{d}x ∈ [(p+1)/2, p](mod p) for any such integer. It follows that

N_{1} ≥ ∑_{(t/2)+1≤s≤t} |I_{s}| ≥ ⌊\frac{t}{2}⌋ \frac{p}{4d} > (\frac{t}{2} − 1) \frac{p}{4d} > \frac{n_{1}}{8} − \frac{p}{2d},

as required.

Step 6. We proved that d = 1 and comparing (23) with (17) we conclude that n_{2} = 0; that is, \overline{A}_{p} ⊆ [−n_{1}, 0](mod p). Letting τ := inf A and λ := 1 − τ we obtain

τ ≥ 1 − \frac{n_{1} + 1}{p} ≥ 1 − (\frac{p − 2n}{k − 2} + 1) p^{−1} = 1 − \frac{1 − 2n/p}{k − 2} − \frac{1}{p};

recalling (16) we get τ ≥ 1 − (1 − 2α)/(k − 2), whence

λ ≤ \frac{1 − 2α}{k − 2} = α (1 + \frac{1/α − k}{k − 2} ) < α (1 + \frac{1}{k − 2}) < 2α.

To complete the proof we invoke Corollary 3 which gives

(hτ + 2(λ − α), h − 2(λ − α)) ⊆ hA ⊆ S(A)

for any integer h ≥ 2. It remains to observe that if h ≥ k, then

h − 2(λ − α) = (h + 1)τ + (h + 1)λ − 1 − 2(λ − α)
= (h + 1)τ + 2(λ − α) + (4α + (h − 3)λ − 1)
≥ (h + 1)τ + 2(λ − α) + (h + 1)α − 1
> (h + 1)τ + 2(λ − α)

and therefore

G(A) ≤ kτ + 2(λ − α) = k − (k − 2)λ − 2α ≤ k − (k − 2)α − 2α = (1 − α)k,

contrary to the assumption. This completes the proof of the Main Theorem. □

References

[B03] D. Bleichenbacher, The continuous postage stamp problem, preprint (2003).

[C13] A.L. Cauchy, Recherches sur les nombres, J. École polytech. 9 (1813), 99–116.

[D35] H. Davenport, On the addition of residue classes, J. London Math. Soc. 10 (1935), 30–32.

[D90] J. Dixmier, Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius, J. Number Theory 34 (2) (1990), 198–209.

[F62] G.A. Freiman, Inverse problems of additive number theory. VII. The addition of finite sets. IV. The method of trigonometric sums, (Russian) Izv. Vysš. Učebn. Zaved. Matematika 6 (31) (1962), 131–144.

[F66] , Nachala strukturnoĭ teorii slozheniya mnozhestv (Russian) [Elements of a structural theory of set addition], Kazan. Gosudarstv. Ped. Inst; Elabuž. Gosudarstv. Ped. Inst., Kazan, 1966. English translation in: Translations of Mathematical Monographs, Vol. 37, American Mathematical Society, Providence, R. I., 1973.

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

[LP03] H.W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, preprint (2003).

[L96a] V. Lev, On the extremal aspect of the Frobenius problem, J. Combin. Theory Ser. A 73 (1) (1996), 111–119.

[L96b] , Structure theorem for multiples addition and the Frobenius problem, J. Number Theory 58 (1) (1996), 79–88.

[L97] , Optimal representations by sumsets and subset sums, J. Number Theory 62 (1) (1997), 127–143.

[M53] A.M. Macbeath, On measure of sum sets. II. The sum-theorem for the torus, Proc. Cambridge Philos. Soc. 49 (1953), 40–43.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il