Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  575.10041
Autor:  Erdös, Paul; Harzheim, E.
Title:  Congruent subsets of infinite sets of natural numbers. (In English)
Source:  J. Reine Angew. Math. 367, 207-214 (1986).
Review:  If A is an infinite subset of the set N of natural numbers, A(x) denotes the number of elements of A which are \leq x. The main theorem states: If k and n are given natural numbers > 1 and if A(x) \geq \epsilon · x1-1/n for some positive \epsilon and all x of a final segment of N, then there exist k disjoint n-element subsets of A which are congruent by translation. Of course, this also implies that n disjoint k-element subsets of A exist which are congruent by translation. This improves an earlier result of the first author for k = n = 2 on B2-sequences, which was published in a paper of A.Stöhr [J. Reine Angew. Math. 194, 111-140 (1955; Zbl 066.03101)].
One obtains the corollary that for every two natural numbers k,n the set of prime numbers has k disjoint n-element subsets which are congruent by translation. Concerning the sharpness of the theorem there holds: If 0 < \alpha < 1-1/k-1/n+1/kn then for all sufficiently large natural numbers m there exists a subset of {1,...,m} which has at least m\alpha elements but no k disjoint congruent n-element subsets.
Classif.:  * 11B83 Special sequences of integers and polynomials
                   11B05 Topology etc. of sets of numbers
Keywords:  disjoint n-element subsets; congruent by translation
Citations:  Zbl 066.031

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page