##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 689.10061

**Autor: ** Erdös, Paul; Sárközy, A.; Sós, V.T. (Turan Sós, V.)

**Title: ** On a conjecture of Roth and some related problems. I. (In English)

**Source: ** Irregularities of partitions, Pap. Meet., Fertod/Hung. 1986, Algorithms Comb. 8, 47-59 (1989).

**Review: ** [For the entire collection see Zbl 682.00006.]

For a fixed partition of the set of positive integers into k classes, let C be the set of those integers that can be represented as a sum of two different integers from the same class. Proving (in a much stronger form) a conjecture of K. F. Roth, the authors show that

(i) the number of even integers \leq M not in C is O(M^{1-2^{-k- 1}}),

(ii) for k = 2 this can be improved to O(log M),

(iii) but there is a 2-partition such that 2^{n}\not in C for all n.

The partition into odd and even numbers shows that not much more can be expected. (i)-(ii) yield a lower bound for the total number of elements represented; the authors improve this to M/2+O(1) for k < 4, and show that it can be < M/2-ck log M if k \geq 4. If every class is supposed to contain both even and odd integers, then, however, an improvement to (+1/(2k)-\epsilon)M is possible.

The representation of special elements (squares, primes) and more general representations are also considered.

[For part II, cf. Zbl 699.10068]

**Reviewer: ** I.Z.Ruzsa

**Classif.: ** * 11B05 Topology etc. of sets of numbers

**Keywords: ** partitions; addition of sets; combinatorial number theory

**Citations: ** Zbl 682.00006

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag