← All problems

Erdős Problem #32 — Growth of complementary sequences to the primes

53 years old · traced to

Let a1<a2<⋯a_1 < a_2 < \cdots be an infinite sequence of integers. Straus and I conjectured that there is a sequence of density 00, b1<⋯b_1 < \cdots so that every integer is of the form ai+bja_i + b_j. Lorentz [1954] proved this conjecture. [...] We will call b1<⋯b_1 < \cdots the complementary sequence to a1<⋯a_1 < \cdots

Lorentz observed that if the aa's are the primes then (12.1) gives B(x)<c(log⁡x)3B(x) < c(\log x)^3. I proved that this can be improved to B(x)<c(log⁡x)2B(x) < c(\log x)^2 (Erdös [1954]). Clearly every complimentary sequence to the primes must satisfy

lim inf⁡B(x)log⁡x≥1.(12.2)\liminf \frac{B(x)}{\log x} \geq 1. \tag{12.2}

I am certain that (12.2) can be improved, but I could not even show

lim sup⁡B(x)log⁡x>1.\limsup \frac{B(x)}{\log x} > 1.

In the other direction I could not find a complementary sequence to the primes satisfying B(x)=o((log⁡x)2)B(x) = o((\log x)^2). Further I could not decide whether there is a complementary sequence to the primes b1<⋯b_1 < \cdots for which the number of solutions of n=p+bin = p + b_i is bounded.

References

P. Erdős, Problems and results on combinatorial number theory, A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., 1971), North-Holland (1973), 117-138.

Source: P. Erdős, Problems and results on combinatorial number theory, A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., 1971), North-Holland (1973), 117-138.

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.