Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  469.10036
Autor:  Erdös, Paul
Title:  Some extremal problems on divisibility properties of sequences of integers. (In English)
Source:  Fibonacci Q. 19, 208-213 (1981).
Review:  The author studies various properties of subsets A = {a1 < a2 < ... < ak \leq n} of integers from 1 to n. The sequence A is said to have the property Pr(n) if no ai divides the product of r of the others. A is said to have the property P(n) if no ai divides the product of the others. It is said to have the property Q(n) if the products ai aj are all distinct. To his results in [Izv. Nauk. Inst. Mat. Mekh. Univ. Tomsk 2, 74-82 (1938; Zbl 020.00504)] he adds further results in this paper. to state them he defines some arithmetical functions. Let Sn denote all the integers from 1 to n. Let fr(n) denote the smallest integer such that Sn can be decomposed into g(n) sets each with the property Q(n). The author proves the results 2n ½ > fr(n) >> n ½/ log n and 2n ½ > g(n) >> n1/3/ log n. Next he proves the results that for every \epsilon > 0, there holds n1-1/r >> fr(n) >> \epsilonn^{1-(1/r)-\epsilon}. Another result about the divisor properties is that if A has the property that the product of any two ai is a multiple of all the others, then log(max k) is asymptotic to (\frac{2 log2}{3})\frac{log n}{log log n} as n ––> oo. I wish to quote on more result. Let F(n) be the smallest integer for which Sn can be decomposed into F(n) sets {Ai}1 \leq i \leq F(n) each having the property P. Then

F(n) = nExp((-c+o(1))(log n log log n) ½).

The author discusses many other deep results about sets A with ai+aj all distinct and so on. As usual the paper is full of interesting problems and partial solutions (sometimes complete solutions) and i would request the readers to consult the paper for more details.
Reviewer:  K.Ramachandra
Classif.:  * 11B83 Special sequences of integers and polynomials
                   11B05 Topology etc. of sets of numbers
                   11B13 Additive bases
Keywords:  extremal problems; divisibility properties; sequences of integers
Citations:  Zbl.020.005

© 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