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(M1-2^{-k- 1}),
(ii) for k = 2 this can be improved to O(log M),
(iii) but there is a 2-partition such that 2n\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