Erdős Problem #892 — Primitive sequences dominated by prescribed sequences
Let be a sequence of integers. A sequence of positive integers is primitive if no term divides a distinct term. The first question asks for necessary and sufficient conditions on for the existence of a primitive sequence and a constant , independent of , such that
In particular, does such a sequence always exist if there are no indices with ? The bound as written entails for every for any sequence satisfying it. Erdős Problem #892 Erdős, Sárközi, and Szemerédi (1968)
The companion question asks for necessary and sufficient conditions on an increasing sequence for there to be a primitive set of positive integers such that, with a constant implied independently of ,
Background
The gcd condition compares a sequence with primitive sequences, but is weaker than primitivity itself: it only rules out a term that is the greatest common divisor of two later terms. Erdős, Sárközi, and Szemerédi studied how forbidding such gcd equations constrains the reciprocal mass of an integer sequence. Their 1968 account returned to the question of whether gcd avoidance suffices to construct a primitive sequence termwise bounded by a constant multiple of the given sequence, and reported that they could not decide it. Erdős, Sárközi, and Szemerédi (1967) Erdős, Sárközi, and Szemerédi (1968)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.