Problem 892

Is there a necessary and sufficient condition for a sequence of integers $b_1<b_2<\cdots$ that ensures there exists a primitive sequence $a_1<a_2<\cdots$ (i.e. no element divides another) with $a_n \ll b_n$ for all $n$ ?

In particular, is this always possible if there are no non-trivial solutions to $(b_i,b_j)=b_k$ ?

Similarly, find necessary and sufficient conditions on a sequence $n_1<n_2<\cdots$ that ensure there exists a primitive set $A$ such that

\lvert A\cap [1,2^{n_i}]\rvert \gg 2^{n_i}

for every $i$ .

Source: erdosproblems.com/892

Number theory
Primitive sets

Wiki page

Status

Open

No claim settles this problem.

ESS67: Erdős, P. and Sárközy, A. and Szemerédi, E., On a theorem of Behrend. J. Austral. Math. Soc. (1967), 9-16.
ESS68: Erdős, P. and Sárközi, A. and Szemerédi, E., On the solvability of certain equations in sequences of positive upper logarithmic density. J. London Math. Soc. (1968), 71-78.
Er35: Erdős, Paul, Note on Sequences of Integers No One of Which is Divisible By Any Other. J. London Math. Soc. (1935), 126-128.
Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.

Problem 892

Status

Proof claims

Discussion