Problem 892

../

---

Statement. 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$.

Status. Open.

Source. erdosproblems.com/892, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #892, https://www.erdosproblems.com/892.

References.

• [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.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1935_note_sequences_integers_no_one_which
• erdos_1935_note_sequences_integers_no_one_which / theorem_p126
• erdos_1967_theorem_behrend
• erdos_1967_theorem_behrend / theorem_1
• erdos_1968_solvability_certain_equations_sequences_positive_upper
• erdos_1968_solvability_certain_equations_sequences_positive_upper / theorem_1
• erdos_1980_survey_problems_combinatorial_number_theory