Sequences with Many Primes (Q5285736)

Let \(A=(a_ 0<a_ 1<a_ 2<\dots)\) and \(B=(b_ 0<b_ 1<b_ 2<\dots)\) be a pair of increasing sequences of integers. Write \(A\succeq B\) if for every \(M\) there is a nonnegative integer \(c\) such that \(B\) and \(A+c=(a_ 0+c,a_ 1+c,a_ 2+c,\dots)\) have at least \(M\) elements in common. For any real number \(r\), let \(\pi_ A(r)=\sup_{k=0,1,2,\dots}(k\mid a_ k\leq r)\). It is first proved that if \(\lim_{i\to\infty} {{a_ i- a_{i-1}} \over {\pi_ B(A)}}=0\) then \(A\succeq B\). This theorem, plus the prime number theorem, is then used to show that if \(A\) is an increasing sequence such that \(\lim_{i\to\infty} {{a_ i-a_{i-1}} \over {a_ i}} \log a_ i=0\), then given any \(M\) there are infinitely many distinct positive integers \(c\) such that the sequence \(A+c\) contains at least \(M\) primes. In particular, if \(f\) is any non-constant polynomial with positive leading coefficient, then for any \(M\) there are infinitely many \(c\geq 0\) such that the sequence \([f(n)]+c\) \((n=0,1,2,\dots)\) contains at least \(M\) primes. This generalizes a theorem by \textit{W. Sierpinski} [Bull. Soc. R. Sci. Liège 33, 259-260 (1964; Zbl 0127.268)], who showed that for any \(M\) there exists a positive integer \(c\) such that the sequence \(a_ n=n^ 2+c\) (\(n=0,1,2,\dots\)) contains at least \(M\) primes, and a theorem by the reviewer [Am. Math. Mon. 97, 316- 317 (1990; Zbl 0714.11056)], who extended Sierpinski's theorem to sequences \(a_ n=n^ k+c\), \(k\geq 2\). However, the condition that \(\lim_{i\to\infty} {{a_ i-a_{i-1}} \over {a_ i}} \log a_ i=0\) is also satisfied by some sequences \(A\) that grow faster than any polynomial. Additional results are also obtained.