GREEDY ALGORITHM, ARITHMETIC PROGRESSIONS, SUBSET SUMS AND DIVISIBILITY

P. ERDŐS, V. LEV, G. RAUZY, C. SÁNDOR, AND A. SÁRKÖZY

The four latter authors dedicate this paper to the memory of Paul Erdős

Abstract. We consider a number of density problems for integer sequences free of arithmetic progressions and sequences with certain divisibility properties. Sequences of the latter type that are generated by a computer using modifications of the greedy algorithm are also provided.

1. Notation

Throughout this paper we use the following notation.

The cardinality of the finite set S is denoted by |S|. The sets of all positive integers and of all non-negative integers are denoted by ℕ and ℕ_{0}, respectively. If A and B are subsets of the set of elements of an abelian group G, by A + B we denote the set of all distinct elements of G representable as a + b, where a ∈ A and b ∈ B; for B = {b} consisting of just one element, this is abbreviated by A + b. By P(A) we denote the set of all distinct elements of G representable in the form ∑_{a∈A} ε_{a}a where ε_{a} ∈ {0, 1} for all a (if A is infinite, then all but finitely many of ε_{a} must be equal to 0). The sums ∑_{a∈A} ε_{a}a are also called subset sums of A. Below, if the contrary is not stated explicitly, A, B, … denote (finite or infinite) subsets of ℕ_{0}. The notation {a_{1}, a_{2}, …} with a_{k} ∈ ℕ_{0} (k = 1, 2, …) assumes that a_{1} < a_{2} < · · ·. For n ∈ ℕ and A = {a_{1}, a_{2}, …} ⊆ ℕ_{0} we write n × A = {na_{1}, na_{2}, …}. The set A ⊆ ℕ_{0} is said to be 3-free if it contains no 3-term arithmetic progression. The maximum cardinality of a 3-free set contained in [1, n] is denoted by r_{3}(n). Finally, c, c_{1}, … denote positive constants, not necessarily equal in distinct formulas.

1991 Mathematics Subject Classification. Primary: 11B25.

Key words and phrases. Greedy algorithm, arithmetic progressions, subset sums, divisibility.

Research partially supported by Hungarian National Foundation for Scientific Research, Grant No. T 017433 and MKM fund FKFP 0139/1997. The work on this paper began when P. Erdős and A. Sárközy were visiting the Institut de Mathématiques de Luminy (UPR 9016 CNSR), Marseille.

2 P. ERDŐS, V. LEV, G. RAUZY, C. SÁNDOR, AND A. SÁRKÖZY

2. Stanley sequences

In 1936 Erdős and Turán [10] wrote: “… On the other hand, r_{3}(41) = 16, since {1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 40, 41} is a 3-free sequence. G. Szekeres has conjectured that r_{3}((3^{k} +1)/2) = 2^{k}. This is proved for k = 1, 2, 3, 4.” (No further details were given.)

In 1942 Salem and Spencer [20] disproved Szekeres’ conjecture by showing that

(2.1)  r_{3}(n) > n^{1−c_{1}/ log log n} (for n > n_{1})

and in 1946 Behrend [2] improved this to

(2.2)  r_{3}(n) > n exp(−c_{2}(log n)^{1/2}) (for n > n_{2}).

In the other direction, in 1953 Roth [19] proved that

r_{3}(n) < c_{3} \frac{n}{log log n} (for n > n_{3})

and recently Heath-Brown [16] and Szemerédi [25] improved this to

(2.3)  r_{3}(n) < n(log n)^{−c_{4}}  (for n > n_{4}).

Although by (2.1) and (2.2), Szekeres’ conjecture is far from the truth, in 1978 Odlyzko and Stanley [17] made an interesting observation which justifies a corrected form of this conjecture. As Erdős and Graham [7, p.22] write: “Stanley has raised the following question (generalizing an earlier question of Szekeres (see [10])). Starting with a_{0} = 0, a_{1} = a, form the infinite sequence a_{0}, a_{1}, a_{2}, … recursively by choosing a_{k+1} to be the least integer exceeding a_{k} which can be adjoined so that no 3-term arithmetic progression is formed. Can the a_{k} be explicitly determined? For example, if a = 1 then the a_{k} are just those integers which contain no 2 in their base 3 expansion. Similar characterizations are known when a = 3^{ν} and a = 2 · 3^{ν} (see [17]). However, the case of a = 4 (and all other values not equal to 3^{ν} or 2·3^{ν}) seems to be of a completely different nature. There are currently no conjectures for the a_{k} in this case.” It seems since then no advance has been made. Related questions were studied by Gerver (see [12, 13, 14]).

The importance of the observation of Odlyzko and Stanley is due to the fact that it sheds some light on the role and limitations of the “greedy algorithm” in combinatorial number theory. Indeed, the greedy algorithm is one of the most frequently used methods in this field; however, in most cases it produces rather weak estimates. It is a question of basic importance whether these estimates could be improved upon with some ingenuity and more careful application of the greedy algorithm or, perhaps, their weakness is a consequence of the limitations of the method. The observation of Odlyzko and Stanley shows that, at least in certain particular situations, the latter is the case.

GREEDY ALGORITHM 3

Based on these considerations, our first goal is to carry out further computer experiments in order to understand better the structure of Stanley type greedy algorithm generated sequences.

For A = {a_{1}, …, a_{t}} ⊆ ℕ_{0} we denote by S(A) the sequence defined by the following recursion. Let S(A) ∩ [0, a_{t}] = A, and if k ≥ t and a_{1}, …, a_{k} have been defined, we choose for a_{k+1} the smallest integer a > a_{k} such that {a_{1}, …, a_{k}} ∪ {a} is 3-free. This sequence S(A) will be called the Stanley sequence generated by A. Clearly a_{1} = 0 can be assumed, so the general case reduces to this one.

We have calculated the elements of S(A) up to 3^{8} = 6561 for certain special sets A. First we study the sets

(2.4)  A = {0, 3^{ν}}

with ν = 0, 1, 2, 3, 4, 5, and

(2.5)  A = {0, 2 · 3^{ν}}

with ν = 0, 1, 2, 3, 4. These calculations seem to indicate that, letting

E = {∑_{i=0}^{∞} ε_{i}3^{i}: ε_{i} ∈ {0, 1}, ε_{1} + ε_{2} + ⋯ < ∞} ,

in accordance with the observation of Odlyzko and Stanley we have

(2.6)  S({0, 1}) = E

(which motivated Szekeres’ conjecture),

(2.7)  S({0, 3^{ν}}) = 3^{ν+1} × E + U_{ν},

where U_{ν} = {0} ∪ ((3^{ν} + (E ∩ [0, 3^{ν+1})))\{2 · 3^{ν}}), and

(2.8)  S({0, 2 · 3^{ν}}) = 3^{ν+2} × E + V_{ν},

where V_{ν} = {0} ∪ ((2 · 3^{ν} + (E ∩ [0, 3^{ν+2})))\{2 · 3^{ν+1}}). We proved (2.6) (but we do

not present the proof here since this is known), and (2.7) and (2.8) can be proven in the same way.

It is much more difficult to say anything about

(2.9)  S({0, a}) for a ≠ 3^{ν}, 2 · 3^{ν}

(as also the quotation above indicates). In Tables 2,3 and 4 we present the elements of S({0, a}) up to 3^{8} = 6561 for a = 4, 5, 7 (while in Table 1 the elements of E = S({0, 1}) are presented for comparison). As Guy [15, p.114] writes, in these cases the sequences S({0, a}) “behave quite erratically.”

4 P. ERDŐS, V. LEV, G. RAUZY, C. SÁNDOR, AND A. SÁRKÖZY

One might wonder what happens if we add yet another number to {0, a}, i.e. if we consider A = {0, a, b}. If S({0, a}) = {0, a, a_{3}, a_{4}, …} and b is chosen as b = a_{3} then clearly we have S({0, a, b}) = S({0, a}) so that for a = 3^{ν}, 2 · 3^{ν} the Stanley sequence S({0, a, a_{3}}) has a nice structure, while for a ≠ 3^{ν}, 2 · 3^{ν} the sequence S({0, a, a_{3}}) is of “erratic” type. The next question is what happens if a = 3^{ν} or 2 · 3^{ν} but we add a number other than a_{3}. In Tables 5 and 6 we present the Stanley sequences S({0, 1, 4}) and S({0, 1, 5}). It seems that again both sets of nice structure (e.g. S({0, 1, 4}) = {0, 1} ∪ ⋃_{i=1}^{∞}(2^{i−1} + 3^{i} + (E ∩ [0, 3^{i})))) and sets of the “erratic” type (e.g. S({0, 1, 5})) can occur.

Returning to case (2.9), it seems hopeless to make any “conjecture for the a_{k} in this case” (as Erdős and Graham suggest). Thus one at least might want to say something about the basic properties of such Stanley sequences. In what follows we list a few problems, inspired by our computer experiments, which do not seem absolutely hopeless.

The first question is: how dense can a Stanley sequence be? In particular:

Problem 1. Is it true that for every ε > 0 and every finite A ⊆ ℕ_{0}, the counting function S(A, x) of S(A) grows faster than x^{\frac{log 2}{log 3} −ε}:

S(A, x) = |\{s ∈ S(A): s ≤ x\}| > x^{\frac{log 2}{log 3} −ε} for x > x_{0}(ε)?

Problem 2. Is it true that the counting function always grows slower than x^{1−ε}:

lim sup_{x→∞} \frac{log S(A, x)}{log x} < 1?

If this is true, is this limit always ≤ \frac{log 2}{log 3}?

The next question: if S(A) = \{a_{1}, a_{2}, …\}, what can one say about the quotients \frac{a_{k+1}}{a_{k}}? In cases (2.4) and (2.5), the lim sup of these quotients is > 1.

Problem 3. Does there exist a finite set A ⊆ ℕ_{0} such that

lim sup_{k→∞} \frac{a_{k+1}}{a_{k}} = 1?

If such a set A exists, how small can one make the differences a_{k+1} − a_{k} in terms of a_{k} (for all k)?

One can ask the converse question: how large can one make the differences a_{k+1} − a_{k}? As (2.6), (2.7) and (2.8) show, in cases (2.4) and (2.5) we have

lim inf_{k→∞}(a_{k+1} − a_{k}) = 1.

GREEDY ALGORITHM 5

Problem 4. Does there exist a finite set A ⊆ ℕ_{0} such that the differences between consecutive elements of S(A) satisfy

lim_{k→∞}(a_{k+1} − a_{k}) = ∞?

Although these problems seem to be much easier than the original problem of describing Stanley sequences S(A), we were unable to settle any of them. (Indeed, all we could prove about Stanley sequences are formulas (2.6), (2.7) and (2.8).) This forced us to relax these problems even further, and to switch from Stanley sequences to more general ones. In this more general setting, we were able to prove certain non-trivial results; these results are presented in the next section, and Sections 4–9 are devoted to their proofs.

3. The results

A more general version of Problem 3 is the following: how small can one make the differences a_{k+1} −a_{k} in terms of a_{k} for a 3-free set A = {a_{1}, a_{2}, …}? By a result of Euler [11] (see also [5, p.572]), the set A = {1^{3}, 2^{3}, 3^{3}, …} is 3-free which shows that

a_{k+1} − a_{k} ≪ a_{k}^{2/3}

is possible. A trivial version of the greedy algorithm gives the same estimate. By a more elaborate version of the greedy algorithm we are able to improve it.

Theorem 1. There is an infinite 3-free set A = {a_{1}, a_{2}, …} such that

a_{1} = 1, a_{k} ∈ [k^{2}, k^{2} + k − 2] (k = 2, 3, …)

and therefore

a_{k+1} − a_{k} ≤ 3\sqrt{a_{k}} (k = 1, 2, …).

Note that by (2.3), one can not get

a_{k+1} − a_{k} ≪ (log a_{k})^{c}

with small c.

Theorem 1 establishes the existence of an “almost regular” 3-free set with the elements a_{k} growing as k^{2}. In fact, our method allows one to prove the existence of a 3-free set whose elements lie in any reasonable system of intervals adjoined to k^{2} and of the length k − 1; say, we could require |a_{k} − k^{2}| < k/2. It seems plausible that there exist much more regular 3-free sets.

Problem 5. Fix ε > 0. Does there exist a 3-free set A = {a_{1}, a_{2}, …} such that

(3.1)  a_{k} = k^{2} + O(k^{ε}) as k → ∞?

Does there exist A such that (3.1) holds for any ε > 0? What are the answers if k^{2} is changed to k^{c} with a fixed exponent c ∈ (1, 2)?

We say that a 3-free set A ⊆ ℕ_{0} is maximal if it is not properly contained in any other 3-free set. Problem 4 inspires the following question.

Problem 6. Does there exist a maximal 3-free set A = {a_{1}, a_{2}, …} ⊆ ℕ_{0} such that

lim_{k→∞}(a_{k+1} − a_{k}) = ∞?

The answer is almost certainly affirmative but we were unable to show this.

If a_{i}, a_{j}, a_{k} ∈ A (a_{i} < a_{j} < a_{k}) form a 3-term arithmetic progression, then we have 2a_{j} = a_{i} + a_{k} whence a_{j} | (a_{i} + a_{k}), where a_{j} ∈ P(A) and a_{i} + a_{k} ∈ P(A). Thus the 3-free property can be extended to studying sequences A = {a_{1}, a_{2}, …} ⊆ ℕ with one of the following properties.

Property P. No a_{i} divides the sum of distinct a_{j} greater than a_{i}. That is,

a_{i} | a_{j_{1}} + ⋯ + a_{j_{l}} (i < j_{1} < ⋯ < j_{l})

never holds.

Property Q. A is non-dividing. That is,

a_{i} | a_{j_{1}} + ⋯ + a_{j_{l}} (j_{1} < ⋯ < j_{l}, i ≠ j_{k} for k = 1, 2, …, l)

never holds.

Property R. No non-zero element of P(A) divides any other one. That is,

∑_{a∈A} ε_{a}a | ∑_{a∈A} δ_{a}a (ε_{a}, δ_{a} ∈ {0, 1})

never holds, unless both sums are equal or the sum at the right is 0.

For n ∈ ℕ, let P (n), Q(n) and R(n) denote the cardinality of a maximal subset of [1, n] with Property P, Q, and R, respectively.

Theorem 2. For n ∈ ℕ let k = k(n) denote the greatest positive integer such that k^{2} + k − 2 < 2n. Then

\sqrt{2n} − 3/2 < k ≤ P (n) < 3\sqrt{n} + 1.

We remark that the lower bound seems to be closer to the truth and, perhaps, we have P (n) = (1 + o(1))\sqrt{2n}.

The upper-bound estimate of Theorem 2 will be derived from the following rather general result which, we believe, is of interest by itself.

GREEDY ALGORITHM 7

Theorem 3. Let A be a sequence of k elements of an abelian group G such that no element of G occurs in A more than M times. Suppose that P(A) does not contain 0 non-trivially:

∑_{a∈A} ε_{a}a ≠ 0

for any ε_{a} ∈ {0, 1}, unless ε_{a} = 0 for all a ∈ A. Then

k < 3\sqrt{M|G|}.

Corollary 1. Let A ⊆ [1, n], a ∈ [1, n], and suppose that a < min(A) (that is, all the elements of A are greater than a). Suppose, further, that no non-zero element of P(A) is divisible by a. Then |A| < 3\sqrt{n}.

Clearly, this corollary establishes the upper bound estimate in Theorem 2 (and in fact, gives a somewhat stronger result).

Dropping the assumption a < min(A), we can prove the following.

Corollary 2. Let A ⊆ [1, n], a ∈ [1, n], and suppose that no non-zero element of P(A) is divisible by a. Then |A| < 3\sqrt{2n}.

As the example A = \{1, 2, …, k\} ⊆ G = ℤ/nℤ with k ≤ 2\sqrt{n} − 1 shows, the constant 3 in Theorem 3 can not be replaced by any constant, less than \sqrt{2}.

Problem 7. Improve Theorem 3 to obtain the best constant possible.

Of course, Property Q implies Property P whence Q(n) ≤ P (n) (for all n ∈ ℕ); thus we have the following corollary of Theorem 2.

Corollary 3. Q(n) < 3\sqrt{n} + 1 for all n ∈ ℕ.

A set A ⊆ ℕ_{0} is said to be non-averaging if no arithmetic mean of two or more distinct members of A belongs to A. Denote by f(n) the size of a maximal non-averaging subset of [1, n]. Straus [23] proved that if f(n) ≫ n^{α} (Bosznay [3] verified this with α = \frac{1}{4}; on the other hand, Erdős and Sárközy [8] proved that f(n) ≪ \sqrt{n log n}) then Q(n) ≫ n^{α/(1+α)} so that, by these results of Straus and Bosznay we have

Q(n) ≫ n^{1/5}.

Here we suspect that the upper bound is closer to reality and, perhaps, we have Q(n) > n^{1/2−ε}.

Let P_{n} = {p ≤ n: p is a prime} be the set of all primes in [1, n]. Abbott [1] proved that, assuming f(n) ≫ n^{α}, the set P_{n} contains a subset satisfying Property Q and having cardinality at least cn^{α/(1+α)}/ log^{2} n. The following theorem slightly improves this result.

Theorem 4. If f(n) ≫ n^{α}, then for large n the set P_{n} contains a subset which satisfies Property Q and has cardinality ≫ n^{α/(1+α)}/ log n.

Concerning Property R, we prove the following.

Theorem 5. There is an absolute constant c such that for n ≥ 3 we have

\frac{log n}{log 2} − 1 < R(n) < \frac{log n}{log 2} + \frac{log log n}{2 log 2} + c.

As Lemma 1 below shows, there are no infinite sets A ⊆ ℕ with either of properties P, Q, or R. Related to this is

Theorem 6. If A = {a_{1}, a_{2}, …} ⊆ ℕ is an infinite sequence, then P(A) contains an infinite divisibility chain p_{1}|p_{2}| … (with p_{i} ∈ P(A), p_{1} < p_{2} < ⋯).

Note that by a theorem of Davenport and Erdős [4], if B ⊆ ℕ is a set of positive upper logarithmic density, then it contains an infinite divisibility chain. (This has been improved slightly by Erdős, Sárközy and Szemerédi [9] but it is not very far from the best possible.) By Theorem 6, the set P(A) must contain an infinite divisibility chain even if A and thus also P(A) is very thin; this seems to be an interesting property of subset sum sets.

4. Proof of Theorem 1

Let a_{1} = 1, a_{2} = 4. Assuming that a_{1}, …, a_{k−1} have already been defined, we show that a_{k} can be found on [k^{2}, k^{2} − k + 1] without violating the 3-free property.

We say that a ∈ [k^{2}, k^{2} + k − 2] is “bad” if a can not be chosen for a_{k}, that is if a = 2a_{j} − a_{i} for some a_{i}, a_{j} such that 1 ≤ i < j ≤ k − 1. Obviously, in this case a_{j} = (a + a_{i})/2 satisfies

(4.1)  \frac{k^{2} + a_{i}}{2} ≤ a_{j} ≤ \frac{k^{2} + k − 2 + a_{i}}{2} .

We prove that to any fixed i ∈ [1, k − 2] there corresponds at most one j ∈ [i + 1, k − 1] such that 2a_{j} − a_{i} is bad; this will show that there exist at most k − 2 bad a and thus will complete the proof as the total possible number of a is k − 1.

Indeed, suppose that for some i there exist two distinct values of j such that 2a_{i} − a_{j} is bad. Then by (4.1), one can find l ∈ ℕ satisfying

\frac{k^{2} + a_{i}}{2} ≤ l^{2} + l − 2 < (l + 1)^{2} ≤ \frac{k^{2} + k − 2 + a_{i}}{2} .

However, this yields

\frac{k}{2} − 1 = \frac{k^{2} + k − 2 + a_{i}}{2} − \frac{k^{2} + a_{i}}{2}

≥ (l + 1)^{2} − (l^{2} + l − 2) > l + 1

> \sqrt{\frac{k^{2} + a_{i}}{2}} > \frac{k}{\sqrt{2}},

a contradiction.

5. Proof of Theorem 3 and Corollaries 1 and 2

To prove Theorem 3, we need two classical results.

Theorem 7 (Olson, [18]). Let A be a set of (distinct) elements of an abelian group G, and suppose that 0 has no non-trivial representation in P(A):

∑_{a∈A} ε_{a}a = 0

with ε_{a} ∈ {0, 1} only when ε_{a} = 0 for all a ∈ A. Then

|P(A)| > 1 + \frac{1}{9}|A|^{2}.

The next result originates in the papers of P. Scherk and J.H.B. Kemperman (see, for example, [22]).

Theorem 8. Let A and B be two subsets of an abelian group G such that 0 ∈ A ∩ B, and suppose that the only representation of 0 in A + B is the trivial one: 0 = 0 + 0. Then |A + B| ≥ |A| + |B| − 1.

By induction, this theorem is easily extended to an arbitrary number of summands.

Corollary 4. Let A_{1}, …, A_{m} be m subsets of an abelian group G such that 0 ∈ A_{1} ∩ ⋯ ∩ A_{m}, and suppose that the only representation of 0 in A_{1} + ⋯ + A_{m} is the trivial one: 0 = 0 + ⋯ + 0. Then

|A_{1} + ⋯ + A_{m}| ≥ |A_{1}| + ⋯ + |A_{m}| − (m − 1).

We now ready to prove Theorem 3. Clearly, A can be represented as a union of m ≤ M sets A_{1}, …, A_{m}, each A_{k} having distinct elements. Since P(A) does not contain 0 non-trivially, neither does any P(A_{k}) (k = 1, …, m). By Theorem 7, we have

|P(A_{k})| > 1 + \frac{1}{9}|A_{k}|^{2} (k = 1, …, m).

Now, P(A_{1}) + ⋯ + P(A_{m}) does not contain 0 non-trivially; hence by Corollary 4

|G| ≥ |P(A_{1}) + ⋯ + P(A_{m})| ≥ |P(A_{1})| + ⋯ + |P(A_{m})| − (m − 1)

> \frac{1}{9}(|A_{1}|^{2} + ⋯ + |A_{m}|^{2}).

By the Cauchy-Schwartz inequality, we conclude that

|A| = |A_{1}| + ⋯ + |A_{m}| ≤ (m(|A_{1}|^{2} + ⋯ + |A_{m}|^{2}))^{1/2} < 3\sqrt{m|G|} ≤ 3\sqrt{M|G|}

which proves Theorem 3.

To prove Corollary 1, we write A = {a_{1}, …, a_{k}} and we consider a_{i} as elements of G = ℤ/aℤ. If a_{i_{1}} < ⋯ < a_{i_{M}} correspond to a common element of G, then obviously the a_{i_{j}} are all of the form a_{i_{j}} = r + t_{j}a, where r ∈ [1, a − 1] and 1 ≤ t_{j} < n/a. Applying Theorem 3 with M = n/a, we get

k < 3\sqrt{a · n/a} = 3\sqrt{n}.

In a similar manner we prove Corollary 2. In this case we have M ≤ n/a + 1, and therefore

k < 3\sqrt{a · (n/a + 1)} = 3\sqrt{n + a} ≤ 3\sqrt{2n}.

6. Proof of Theorem 2

As we have already noticed, the upper bound of Theorem 2 follows immediately from Corollary 1. To obtain the lower bound, we define A = {n − k + 1, n − k + 2, …, n} and show that A possesses Property P. Clearly, it suffices to show that if

(6.1)  n − k + 1 ≤ i < j_{1} < ⋯ < j_{l} ≤ n,

then the sum j_{1} + ⋯ + j_{l} falls between consecutive multiples of i, and in fact,

li < j_{1} + ⋯ + j_{l} < (l + 1)i

Indeed, the lower bound is trivial here, and it remains to prove the upper bound. It follows from (6.1) that

(6.2)  l ≤ k − 1

and

(6.3)  (l + 1)i ≥ (l + 1)(n − k + 1)

On the other hand, we have

(6.4)  j_{1} + ⋯ + j_{l} ≤ (n − l + 1) + (n − l + 2) + ⋯ + n = \frac{l(2n − l + 1)}{2}

By (6.3) and (6.4), it suffices to show that

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

or, equivalently,

0 < 2n − 2kl − 2k + l^{2} + l + 2 = (2n − k^{2} − k + 2) + (k − l)(k − 1 + l).

However, the first term here is positive by the definition of k and the second term is non-negative by (6.2) so the inequality holds.

7. Proof of Theorem 4

Denote N = ⌊n^{1/(1+α)}⌋. Let A ⊆ [1, N] be a non-averaging set of cardinality k = |A| such that

n^{α/(1+α)} ≪ k ≤ \frac{1}{3}n^{α/(1+α)} − 1.

We first show that all sets

A_{l} = l − A = {l − a: a ∈ A} ⊆ [1, n]; l = n − 2N, n − 2N + 1, …, n

are non-dividing. Indeed, assume that

s = \frac{(l − a_{1}) + ⋯ + (l − a_{t})}{l − a_{0}}

is an integer for some a_{0}, a_{1}, …, a_{t} ∈ A. Then

s < \frac{tn}{n − 3N} ≤ t + 1, s > \frac{tn − 3tN}{n} > t − 1,

hence s = t and

t(l − a_{0}) = (l − a_{1}) + ⋯ + (l − a_{t}),
a_{0} = (a_{1} + ⋯ + a_{t})/t,

contradicting the non-averaging property of A.

Next, for any prime p ∈ [n − 2N, n − N] and any a ∈ A we have

l = p + a ∈ [n − 2N, n]

and therefore p ∈ A_{l}. This shows that

∑_{l=n−2N}^{n} |A_{l} ∩ P_{n}| ≥ |A| (π(n − N) − π(n − 2N)) ≫ n^{α/(α+1)} \frac{N}{log n}

(we use here the well known fact that if x is sufficiently large and Θ ≥ 0.6 then the number of primes in the interval (x, x + x^{Θ}) is at least x^{Θ}/ log x in order of magnitude) whence the maximal of the cardinalities |A_{l} ∩ P_{n}| is ≫ n^{α/(α+1)}/ log n.

12 P. ERDŐS, V. LEV, G. RAUZY, C. SÁNDOR, AND A. SÁRKÖZY

8. Proof of Theorem 5

If A ⊆ [1, n] and no non-zero sum ∑_{a∈A} ε_{a}a (ε_{a} ∈ {0, 1}) divides any other, then all these sums are distinct. The upper bound of Theorem 5 is now immediate by a classical result of Erdős and Moser [6] (see also [7, p.60]), which establishes the estimate

|A| < \frac{log n}{log 2} + \frac{log log n}{2 log 2} + c

for A ⊆ [1, n] with pairwise distinct subset sums.

To obtain the lower-bound estimate, we show that

A = {2^{m} − 2^{m−1}, 2^{m} − 2^{m−2}, …, 2^{m} − 1}

satisfies Property R for any m ∈ ℕ (one then chooses m to be the maximal integer such that 2^{m} ≤ n + 1).

Indeed, suppose that

(8.1)  ∑_{i=0}^{m−1} ε_{i} (2^{m} − 2^{i}) = k ∑_{i=0}^{m−1} δ_{i} (2^{m} − 2^{i})

for some k ∈ ℕ and ε_{i}, δ_{i} ∈ {0, 1} such that, letting

ε = ∑_{i=0}^{m−1} ε_{i}2^{i}, δ = ∑_{i=0}^{m−1} δ_{i}2^{i},

we have

ε, δ ∈ [1, 2^{m} − 1], ε ≠ δ.

By (8.1), we get ε ≡ kδ (mod 2^{m}), and therefore k > 1. Moreover, there exists an integer t such that

(8.2)  ε = kδ + 2^{m}t

and again using (8.1) we obtain also

(8.3)  ∑_{i=0}^{m−1} ε_{i} = k ∑_{i=0}^{m−1} δ_{i} + t.

We observe now that

∑_{i=1}^{m−1} ε_{i} = (ε − 2 ⌊\frac{ε}{2}⌋) + (⌊\frac{ε}{2}⌋ − 2 ⌊\frac{ε}{4}⌋) + (⌊\frac{ε}{4}⌋ − 2 ⌊\frac{ε}{8}⌋) + ⋯

= ε − ⌊\frac{ε}{2}⌋ − ⋯ − ⌊\frac{ε}{2^{m}} ⌋

and similarly,

∑_{i=1}^{m−1} δ_{i} = δ − ⌊\frac{δ}{2}⌋ − ⋯ − ⌊\frac{δ}{2^{m}} ⌋ .

Thus, by (8.3) and (8.2)

kδ − k ⌊\frac{δ}{2}⌋ − ⋯ − k ⌊\frac{δ}{2^{m}} ⌋ + t = (kδ + 2^{m}t) − ⌊\frac{kδ + 2^{m}t}{2}⌋ − ⋯ − ⌊\frac{kδ + 2^{m}t}{2^{m}}⌋

= kδ − ⌊\frac{kδ}{2} ⌋ − ⋯ − ⌊\frac{kδ}{2^{m}} ⌋ + t,

k ⌊\frac{δ}{2}⌋ + ⋯ + k ⌊\frac{δ}{2^{m}} ⌋ = ⌊\frac{kδ}{2} ⌋ + ⋯ + ⌊\frac{kδ}{2^{m}} ⌋ .

This, however, is impossible as

k ⌊\frac{δ}{2^{i}} ⌋ ≤ ⌊\frac{kδ}{2^{i}} ⌋

for all i ∈ ℕ_{0}, and strict inequality holds if i is chosen so that

2^{i} ≤ kδ < 2^{i+1}.

9. Proof of Theorem 6

Let p_{1} = a_{1}, and assume that p_{1}, p_{2}, …, p_{k−1} ∈ P(A) have been defined so that p_{1}|p_{2}| … |p_{k−1} and p_{1} < p_{2} < ⋯ < p_{k−1}. Clearly, it suffices to prove the existence of p_{k} > p_{k−1} such that p_{k−1} | p_{k}. For this we need the following well-known lemma (see, for example, [21, Lemma 1]).

Lemma 1. If d ∈ ℕ and n_{1}, …, n_{d} are integers, then there are pairwise distinct j_{1}, …, j_{l} ∈ [1, d] such that d | n_{j_{1}} + ⋯ + n_{j_{l}}.

Now define the positive integer r by a_{r} ≤ p_{k−1} < a_{r+1}. Using Lemma 1 with p_{k−1} and a_{j} (j = r + 1, …, r + p_{k−1}) for d and n_{j}, respectively, we obtain that there are pairwise distinct j_{1}, …, j_{l} ≥ r + 1 such that

p_{k−1} | a_{j_{1}} + ⋯ + a_{j_{l}}.

Then writing p_{k} = a_{j_{1}} + ⋯ + a_{j_{l}} ∈ P(A) we have p_{k−1} | p_{k} and

p_{k} = a_{j_{1}} + ⋯ + a_{j_{l}} ≥ a_{r+1} > p_{k−1}

completing the proof of Theorem 6.

10. Acknowledgment

We would like to thank Professor A.M. Odlyzko for his valuable comments.

E = S({0, 1}) = {∑ ε_{i}3^{i}, ε_{i} ∈ {0, 1}}

The elements not exceeding 6561:

0 1

3 4 9 10 12 13

27 28 30 31 36 37 39 40

81 82 84 85 90 91 93 94 108 109 111 112 117 118 120 121

243 244 246 247 252 253 255 256 270 271 273 274 279 280 282 283 324 325 327 328 333 334 336 337 351 352 354 355 360 361 363 364

729 730 732 733 738 739 741 742 756 757 759 760 765 766 768 769 810 811 813 814 819 820 822 823 837 838 840 841 846 847 849 850 972 973 975 976 981 982 984 985 999 1000 1002 1003 1008 1009 1011 1012 1053 1054 1056 1057 1062 1063 1065 1066 1080 1081 1083 1084 1089 1090 1092 1093

2187 2188 2190 2191 2196 2197 2199 2200 2214 2215 2217 2218 2223 2224 2226 2227 2268 2269 2271 2272 2277 2278 2280 2281 2295 2296 2298 2299 2304 2305 2307 2308 2430 2431 2433 2434 2439 2440 2442 2443 2457 2458 2460 2461 2466 2467 2469 2470 2511 2512 2514 2515 2520 2521 2523 2524 2538 2539 2541 2542 2547 2548 2550 2551 2916 2917 2919 2920 2925 2926 2928 2929 2943 2944 2946 2947 2952 2953 2955 2956 2997 2998 3000 3001 3006 3007 3009 3010 3024 3025 3027 3028 3033 3034 3036 3037 3159 3160 3162 3163 3168 3169 3171 3172 3186 3187 3189 3190 3195 3196 3198 3199 3240 3241 3243 3244 3249 3250 3252 3253 3267 3268 3270 3271 3276 3277 3279 3280

6561

The number of elements not exceeding 6561: 257.

The maximal gap between the consecutive elements up to 6561: 3281.

S({0, 4})

The elements not exceeding 6561:

0

4 5 7

11 12 16 23 26

31 33 37 38 44 49 56 73 78 80

85 95 99 106 124 128 131 136 143 169 188 197 203 220 221 226 227 238

247 259 269 276 284 287 302 308 310 313 319 337 385 392 397 422 434 455 466 470 491 493 499 504 554 559 580 598 628 629 635 640 644 650 654 655 657 677 687 691 715 718

731 736 791 793 869 890 893 900 941 1005 1010 1022 1025 1048 1056 1057 1121 1124 1138 1168 1187 1199 1286 1290 1315 1322 1368 1372 1402 1411 1438 1444 1447 1453 1471 1475 1488 1494 1525 1528 1552 1564 1601 1624 1663 1670 1671 1709 1771 1792 1805 1811 1816 1835 1860 1868 1897 1900 1906 1910 1948 1950 1956 1991 2030 2062 2093 2121

2213 2291 2327 2366 2420 2482 2555 2570 2646 2654 2693 2708 2734 2735 2759 2765 2842 2854 2947 2954 2990 2995 3011 3037 3077 3132 3147 3151 3208 3228 3233 3259 3306 3343 3359 3361 3391 3454 3619 3634 3655 3660 3661 3718 3730 3733 3737 3766 3803 3829 3836 3838 3914 3930 3964 3968 3985 3991 4007 4067 4079 4138 4172 4221 4225 4256 4259 4279 4288 4301 4318 4326 4339 4372 4387 4432 4583 4691 4719 4735 4763 4771 4778 4805 4845 4877 4929 4935 4940 5020 5042 5142 5188 5226 5302 5357 5443 5478 5484 5534 5538 5545 5561 5736 5855 5915 5939 5997 6086 6107 6194 6200 6244 6356 6362 6398 6470 6503 6541

The number of elements not exceeding 6561: 266.

The maximal gap between the consecutive elements up to 6561: 175.

The elements not exceeding 6561:

0

5 6 8

9 14 15 17

27 31 32 36 38 42 43 51 65 73 74

82 89 100 101 107 109 123 152 154 165 174 177 179 190 198 211 216 220 227 233 236

260 319 328 335 336 356 361 362 370 373 406 433 444 453 465 468 470 481 490 517 521 523 528 540 541 546 562 616 696

733 748 749 755 758 791 794 811 816 825 842 843 878 910 912 984 994 997 1079 1085 1089 1095 1100 1102 1103 1108 1139 1153 1166 1171 1187 1192 1195 1225 1241 1264 1267 1273 1302 1332 1369 1370 1385 1404 1419 1528 1592 1603 1696 1698 1707 1775 1847 1875 1883 1901 1902 1907 1935 2003 2009 2033 2092 2110 2137 2145

2203 2228 2237 2244 2254 2256 2386 2387 2401 2413 2422 2424 2449 2456 2459 2506 2545 2551 2552 2560 2608 2624 2630 2676 2679 2693 2747 2748 2774 2779 2783 2786 2797 2827 2842 2843 2863 2881 2914 2932 2954 3063 3091 3100 3196 3265 3416 3418 3454 3455 3556 3597 3599 3626 3774 3867 3869 3880 3881 3888 3908 3940 4048 4080 4207 4237 4289 4340 4421 4535 4571 4602 4613 4627 4645 4668 4681 4704 4710 4712 4718 4777 4782 4786 4894 4972 4984 4992 4994 5036 5118 5157 5172 5176 5227 5268 5436 5437 5446 5461 5511 5513 5582 5599 5722 5760 5768 5778 5787 5789 5793 5816 5873 5884 5889 5912 5942 5943 5960 5976 6039 6089 6123 6130 6134 6187 6208 6209 6219 6222 6223 6239 6260 6263 6276 6278 6401 6415 6419 6435 6505 6559

The number of elements not exceeding 6561: 277.

The maximal gap between the consecutive elements up to 6561: 168.

The elements not exceeding 6561:

0

7 8 10 11 17 18 21

30 33 37 38 40 51 54 61 77 79

83 86 88 96 110 119 123 130 153 157 170 173 178 179 194 197 207 211 214 219 232 240

247 251 256 282 290 344 362 365 399 409 439 444 452 455 467 488 493 496 500 506 514 520 538 541 549 555 574 575 581 597 608 616 618 623 626 633 682

771 776 812 852 895 973 1048 1105 1114 1119 1121 1135 1168 1188 1197 1200 1210 1227 1230 1240 1243 1247 1261 1274 1277 1300 1304 1309 1316 1317 1329 1336 1337 1350 1362 1393 1409 1455 1476 1492 1496 1530 1533 1540 1554 1561 1562 1566 1572 1580 1597 1638 1639 1658 1726 1733 1747 1759 1809 1841 1893 1910 1983 2020 2111

2428 2441 2565 2609 2675 2734 2754 2789 2792 2794 2803 2825 2838 2924 2940 2958 3017 3032 3035 3096 3128 3131 3158 3167 3169 3172 3181 3191 3200 3208 3214 3229 3263 3292 3301 3344 3346 3363 3372 3374 3379 3413 3416 3479 3490 3493 3498 3543 3551 3571 3574 3619 3637 3643 3677 3680 3705 3706 3718 3720 3738 3754 3762 3816 3832 3840 3842 3876 3877 3904 3977 4005 4035 4042 4100 4167 4176 4220 4250 4263 4291 4293 4370 4397 4422 4481 4505 4528 4567 4570 4593 4739 4749 4771 4815 5269 5287 5321 5535 5575 5619 5685 5745 5919 6036

The number of elements not exceeding 6561: 247.

The maximal gap between the consecutive elements up to 6561: 454.

S({0, 1, 4})

The elements not exceeding 6561:

0 1

4 5

11 12 14 15

31 32 34 35 40 41 43 44

89 90 92 93 98 99 101 102 116 117 119 120 125 126 128 129

259 260 262 263 268 269 271 272 286 287 289 290 295 296 298 299 340 341 343 344 349 350 352 353 367 368 370 371 376 377 379 380

761 762 764 765 770 771 773 774 788 789 791 792 797 798 800 801 842 843 845 846 851 852 854 855 869 870 872 873 878 879 881 882 1004 1005 1007 1008 1013 1014 1016 1017 1031 1032 1034 1035 1040 1041 1043 1044 1085 1086 1088 1089 1094 1095 1097 1098 1112 1113 1115 1116 1121 1122 1124 1125

2251 2252 2254 2255 2260 2261 2263 2264 2278 2279 2281 2282 2287 2288 2290 2291 2332 2333 2335 2336 2341 2342 2344 2345 2359 2360 2362 2363 2368 2369 2371 2372 2494 2495 2497 2498 2503 2504 2506 2507 2521 2522 2524 2525 2530 2531 2533 2534 2575 2576 2578 2579 2584 2585 2587 2588 2602 2603 2605 2606 2611 2612 2614 2615 2980 2981 2983 2984 2989 2990 2992 2993 3007 3008 3010 3011 3016 3017 3019 3020 3061 3062 3064 3065 3070 3071 3073 3074 3088 3089 3091 3092 3097 3098 3100 3101 3223 3224 3226 3227 3232 3233 3235 3236 3250 3251 3253 3254 3259 3260 3262 3263 3304 3305 3307 3308 3313 3314 3316 3317 3331 3332 3334 3335 3340 3341 3343 3344

The number of elements not exceeding 6561: 256.

The maximal gap between the consecutive elements up to 6561: 1126.

S({0, 1, 5})

The elements not exceeding 6561:

0 1

5 6 8 13 14 17 19

31 35 36 40 42 46 47 60 68 82

95 97 98 102 110 111 113 121 137 139 142 146 170 233 235 240

251 254 263 281 282 285 290 297 302 303 306 318 336 342 344 374 376 393 414 417 476 487 555 584 597 614 618 621 629 633 643 660 663 685 690 694 700 709 714 722

753 761 763 764 776 802 805 848 874 880 881 902 911 915 937 962 970 1010 1016 1021 1037 1101 1157 1166 1294 1296 1299 1337 1373 1419 1469 1474 1496 1534 1543 1560 1607 1608 1613 1631 1633 1640 1648 1674 1675 1697 1721 1765 1810 1815 1818 1836 1840 1846 1848 1849 1859 1863 1875 1885 1906 1942 2010 2016 2071 2080 2082 2094 2121 2127 2141 2152 2159 2170

2208 2215 2242 2265 2287 2375 2417 2431 2466 2549 2559 2622 2737 2747 2774 2826 2829 2862 3064 3135 3177 3189 3285 3289 3341 3405 3422 3431 3471 3512 3643 3647 3706 3758 3759 3779 3791 3859 3877 3894 3896 3905 3949 3965 3967 3971 4035 4068 4138 4173 4204 4215 4266 4275 4286 4302 4324 4325 4330 4331 4343 4350 4352 4367 4372 4502 4509 4533 4546 4576 4591 4598 4610 4612 4616 4670 4712 4726 4748 4758 4775 4879 4887 4912 4914 4923 4982 5012 5111 5115 5126 5163 5180 5190 5201 5224 5262 5289 5290 5306 5325 5342 5387 5410 5532 5588 5628 5675 5685 5731 5741 5755 5796 5839 5890 6006 6041 6063 6107 6134 6171 6186 6191 6214 6218 6295 6304 6426 6558

The number of elements not exceeding 6561: 278.

The maximal gap between the consecutive elements up to 6561: 202.

References

[1] H.L. Abbott, Extremal problems on non-averaging and non-dividing sets, Pacific J. Math. 91 (1980), 1–12.

[2] F. Behrend, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A. 32 (1946), 331–332.

[3] Á. Bosznay, On the lower estimation of non-averaging sets, Acta Math. Hung. 53 (1989), 155–157.

[4] H. Davenport and P. Erdős, On sequences of positive integers, Acta Arith. 2 (1937), 147–151; see also Indian J. Math. 15 (1951), 19–29.

[5] L.E. Dickson, History of the Theory of Numbers, vol. II, Chelsea, New York, 1952.

[6] P. Erdős, Problems and results in additive number theory, Colloque sur la Théorie des Nombres, Bruxelles, 1955; Liège and Paris, 1956, 127–137.

[7] P. Erdős and R.L. Graham, Old and new problems and results in combinatorial number theory. Monographies de L’Enseignement Mathématique 28, Université de Genève, L’Enseignement Mathématique, Genéve, 1980.

[8] P. Erdős and A. Sárközy, On a Problem of Straus, Disorder in Physical Systems. A volume in honor of J. M. Hammersley, Oxford Science Publ. (1990), 55–66.

[9] P. Erdős, A. Sárközy and E. Szemerédi, On divisibility properties of sequences of integers, Studia Sci. Math. Hung. 1 (1966), 431–435.

[10] P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261– 264.

[11] L. Euler, Algebra, 2, 1770, Art. 247; French transl., 2, 1774, 355-360; Opera omnia, (1), I, 491.

[12] J. Gerver, Sets of integers with no long arithmetic progressions, Math. Comp. 33 (1979), 1353– 1359.

[13] J. Gerver, Irregular sets of integers generated by the greedy algorithm, Math. Comp. 40 (1983), 667–676.

[14] J. Gerver, Greedily partitioning the natural number into sets free generated by the greedy algorithm, Proc. Amer. Math. Soc. 102 (1988), 765–772.

[15] R.K. Guy, Unsolved Problems in Number Theory. Unsolved Problems in Intuitive Mathematics, vol. I, Springer-Verlag, New York, 1981.

[16] D.R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385–394.

[17] A.M. Odlyzko and R.P. Stanley, Some curious sequences constructed with the greedy algorithm. Bell Laboratories internal memorandum (1978).

[18] J.E. Olson, Sums of sets of group elements, Acta Arith. 28 (1975), 147–156.

[19] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109.

[20] R. Salem and D.C. Spencer, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. USA 28 (1942), 561–563.

[21] A. Sárközy, Finite addition theorems, II. J. Number Theory 48 (1994), 197–218.

[22] P. Scherk, Distinct elements in a set of sums, American Math. Monthly 62 (1995), 46.

[23] E.G. Straus, Non averaging sets, Proc. Symp. Pure Math., AMS, Providence 19 (1971), 215–222.

[24] E. Szemerédi, On a conjecture of Erdős and Heilbronn, Acta Arith. 17 (1970), 227–229.

[25] E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hung. 56 (1990), 155–158.

P. Erdős: Mathematical Institute of the Hungarian Academy of Sciences, H-1053 Budapest, Reáltanoda u. 13-15, Hungary

V. Lev: Department of Mathematics, University of Georgia, Athens, GA 30602

E-mail address: seva@@math.uga.edu

G. Rauzy: Institute de Mathématiques de Luminy, UPR 9016 CNRS, 163 Avenue de Luminy, Case 930 F-13288 Marseille Cédex 09, France

C. Sándor and A. Sárközy: Eötvös Loránd University, Department of Algebra and Number Theory, H-1088 Budapest, Múzeum krt. 6-8, Hungary