← All problems

Erdős Problem #892 — Primitive sequences dominated by prescribed sequences

46 years old · traced to

Let b1<b2<⋯b_1<b_2<\cdots be a sequence of integers. A sequence a1<a2<⋯a_1<a_2<\cdots of positive integers is primitive if no term divides a distinct term. The first question asks for necessary and sufficient conditions on (bn)(b_n) for the existence of a primitive sequence (an)(a_n) and a constant C>0C>0, independent of nn, such that

an≤Cbn(n≥1).a_n\le Cb_n\qquad(n\ge1).

In particular, does such a sequence always exist if there are no indices k<i<jk<i<j with gcd⁡(bi,bj)=bk\gcd(b_i,b_j)=b_k? The bound as written entails bn>0b_n>0 for every nn 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 n1<n2<⋯n_1<n_2<\cdots for there to be a primitive set AA of positive integers such that, with a constant implied independently of ii,

∣A∩[1,2ni]∣≫2nifor every i.|A\cap[1,2^{n_i}]|\gg 2^{n_i}\qquad\text{for every }i.

Erdős Problem #892

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

Progress summary

Never refreshed

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.