%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-21/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}
\newtheorem*{corl}{Corollary}
\newtheorem*{ackn}{Acknowledgement}

\title{Sequences with Translates Containing Many Primes}
\author{Tom C. Brown\footnote{Partially supported by NSERC.},
Peter Jau-Shyong Shiue and X. Y. Yu\footnote{Supported by the National Science
Grant of the P.R. of China and the Science Grant of Zhejiang Province, P.R. China.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, P.~J.-S. Shiue, and X.Y. Yu, \emph{Sequences with translates
  containing many primes}, Canad. Math. Bull. \textbf{41} (1998), 15--19.}\bigskip\end{center}

\begin{abstract}Garrison \cite{garrison1990}, Forman \cite{forman1992}, and
Abel and Siebert \cite{abel+siebert1993} showed that for all positive
integers $k$ and $N$, there exists a positive integer $\lambda$ such
that $n^k+\lambda$ is prime for at least $N$ positive integers $n$.
In other words, there exists $\lambda$ such that $n^k+\lambda$
represents at least $N$ primes.

We give a quantitative version of this result. We show that there
exists $\lambda\leq x^k$ such that $n^k+\lambda$, $1\leq n\leq x$,
represents at least $\left(\frac1k + o(1)\right)\pi(x)$ primes,
as $x\to\infty$. We also give some related results.
\end{abstract}

\section{Introduction}

In \cite{abel+siebert1993}, Abel and Siebert make the wonderful
observation that if $A = \{a_n\}$ is a sequence of natural numbers and
$A(x) = \sum_{a_n\leq x}1$, then
\[ \sum_{\lambda\leq2x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda} 1 \geq
[\pi(2x) - \pi(x)]A(x), \]
where $p$ denotes a prime and $\pi(x)$ denotes the number of primes $p\leq x$.
They used this inequality, together with Chebyshev's inequalities, to show that
if $\limsup_{x\to\infty}\frac{A(x)}{\log x}=\infty$, then for all $N$ there
exists $\lambda$ such that $a_n+\lambda$ represents at least $N$ primes. Forman
\cite{forman1992} obtained the same result with methods different from those
of Abel and Siebert.

Earlier, Sierpenski \cite{sierpinski1964} showed that $n^2+\lambda$
represents arbitrarily many primes. Then Garrison \cite{garrison1990}
extended this to $n^k+\lambda$. Forman \cite{forman1992} and Abel and
Siebert \cite{abel+siebert1993} showed that $g(n)+\lambda$ represents
arbitrarily many primes, where $g(x)$ is any polynomial with integer
coefficients and positive leading coefficient.

In this note we consider sums of the form
\[ S(x) = \sum_{\lambda\leq2x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda} f(b_m) \text{ and }
T(x) = \sum_{\lambda\leq x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda} f(b_m), \]
where $A = \{a_n\}$ and $B = \{b_m\}$ are given sequences of natural
numbers and $f$ is a given nonnegative function defined on the natural
numbers. In particular, if $B$ is the sequence of primes and $f\equiv1$,
then $T(x) = (1 + o(1))A(x)\pi(x)$. This implies that if $A = \{n^k:n
\geq1\}$, then $T(x) = (1 + o(1))x^{\frac1k}\pi(x)$. It follows that
there exists a positive integer $\lambda\leq x^k$ such that $n^k+\lambda$,
$n\leq x$, represents at least $(\frac1k + o(1))\pi(x)$ primes.

\section{Results}

\begin{thrm}\label{t1} Let $A=\{a_n\}$, $B=\{b_m\}$ be sequences of natural
numbers, and let $f$ be a nonnegative function defined on the natural numbers.
Let $A(x) = \sum_{a_n\leq x}1$, $B(x) = \sum_{b_m\leq x}f(b_m)$.

Assume that $B(x) = (1 + o(1))x^\alpha\varphi(x)$, where $\varphi$ is monotonic
and $\lim_{x\to\infty}\frac{\varphi(2x)}{\varphi(x)} = 1$. Let $S(x)$ denote
the sum
\[ S(x) = \sum_{\lambda\leq2x}\sum_{a_n\leq x}\sum_{b_m=a_n+\lambda} f(b_m) \]
Then
\[ (2^\alpha - 1 + o(1))A(x)B(x)\leq S(x)\leq (3^\alpha + o(1))A(x)B(x). \]
\end{thrm}
\begin{proof} For the lower bound, we start with Abel and Seibert's inequality
\[ S(x) \geq [B(2x) - B(x)]A(x). \]
Next,
\[ \frac{B(2x) - B(x)}{B(x)} = \frac{(1 + o(1))(2x)^\alpha\varphi(2x)}{(1 + o(1))x^\alpha\varphi(x)} - 1 \to 2^\alpha - 1, \]
hence $B(2x) - B(x) = (2^\alpha - 1 + o(1))B(x)$.

For the upper bound, we write
\begin{align*}
S(x)
&= \sum_{a_n\leq x}\sum_{a_n + 1\leq b_m \leq a_n + 2x} f(b_m) \\
&= \sum_{a_n\leq x}[B(a_n + 2x) - B(a_n)] \leq \sum_{a_n\leq x}B(a_n + 2x).
\end{align*}

We now estimate $B(a_n + 2x)$ from above.

Let $a$ be an integer, $1\leq a\leq x$. Since $\varphi$ is monotonic, $x\leq
a + x\leq 2x$, and $\frac{\varphi(x)}{\varphi(x)} = 1$, $\frac{\varphi(2x)}{\varphi(x)}
\to1$, it follows that for every $\epsilon >0$ there exists $N = N(\epsilon)$ such
that
\[ \frac{\varphi(a + x)}{\varphi(x)} < 1 + \epsilon, ~~ x > N, ~ 1 \leq a \leq x. \]
From this it follows that $\frac{\varphi(3x)}{\varphi(x)} = \frac{\varphi(3x)}{\varphi(2x)}\cdot\frac{\varphi(2x)}{\varphi(x)} \to 1$.

Now since $2x\leq a + 2x \leq 3x$, $\varphi$ is monotonic, and
$\frac{\varphi(2x)}{\varphi(x)}\to 1$, $\frac{\varphi(3x)}{\varphi(x)}\to 1$, it
follows that for every $\epsilon > 0$ there exists $N = N(\epsilon)$ such that
\[ \frac{\varphi(a + 2x)}{\varphi(x)} < 1 + \epsilon, ~~ x > N, ~ 1 \leq a \leq x. \]

It now follows that for any $a = a(x)$, $1\leq a \leq x$, and any $\epsilon > 0$,
\[ \frac{B(a + 2x)}{B(x)} = \frac{(1 + o(1))(a + 2x)^\alpha\varphi(a + 2x)}
{(1 + o(1))x^\alpha\varphi(x)} < 3^\alpha + \epsilon \]
for sufficiently large $x$. Hence, independent of the choice of $a$, $1\leq a\leq x$,
\[ B(a + 2x) \leq (3^\alpha + o(1))B(x), \]
and
\[ S(x) \leq \sum_{a_n\leq x} B(a_n + 2x) \leq (3^a + o(1))A(x)B(x). \]
\end{proof}

Now we let $B$ be the sequence of primes.

\begin{thrm}\label{t2} Let $A=\{a_n\}$ be a sequence of natural numbers. Then
\[ S(x) = \sum_{\lambda\leq2x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda}1
\geq (1 + o(1))A(x)\pi(x), \]
where $p$ denotes a prime. Hence there exists $\lambda$, $1\leq\lambda\leq2x$,
such that $a_n+\lambda$, $1\leq a_n\leq x$ represents at least $(\frac12+o(1))
\frac{A(x)}x\pi(x)$ primes.\end{thrm}
\begin{proof} This proof is a direct application of the method of Abel and Siebert.
We have
\[ S(x) = \sum_{\lambda\leq2x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda}1
\geq (\pi(2x) - \pi(x))A(x) = (1 + o(1))A(x)\pi(x), \]
or
\[ \frac1{2x}\sum_{\lambda=1}^{2x}\left(\sum_{a_n\leq x}\sum_{p=a_n+\lambda}1\right)
\geq \left(\frac12 + o(1)\right)\frac{A(x)}x\pi(x), \]
so at least one $\lambda$, $1\leq\lambda\leq 2x$, has the required property.\end{proof}

We now improve this result by using part of the method of Theorem \ref{t1}.

\begin{thrm}\label{t3} Let $A=\{a_n\}$ be a sequence of natural numbers. Then
\[ T(x) = \sum_{\lambda\leq x}\sum_{a_n\leq x}\sum_{p=a_n+\lambda}1 =
(1 + o(1))A(x)\pi(x), \]
where $p$ denotes a prime. Hence there exists $\lambda$, $1\leq\lambda\leq x$,
such that $a_n+\lambda$, $1\leq a_n\leq x$ represents at least $(1+o(1))
\frac{A(x)}x\pi(x)$ primes.\end{thrm}
\begin{proof} As in the proof of Theorem \ref{t1}, we write
\[ T(x) = \sum_{a_n\leq x} \sum_{a_n+1\leq p\leq a_n+x}1 =
\sum_{a_n\leq x}[\pi(a_n + x) - \pi(a_n)]. \]

It is not hard to show that for every $\epsilon > 0$ there exists $N = N(\epsilon)$
such that
\[ 1 -\epsilon < \frac{\pi(a+x)-\pi(a)}{\pi(x)} < 1 + \epsilon, ~~x> N,~1\leq a\leq x. \]
(For fixed $\epsilon$, divide $[1,x]$ into subintervals of length $\epsilon x$, and
use the Prime Number Theorem to estimate $\frac{\pi(a+x)-\pi(a)}{\pi(x)}$ when $a\in
[(i-1)\epsilon x, i\epsilon x]$.)

Summing this over all $a_k$, $a_k\leq x$, gives
\[ (1-\epsilon)A(x)\pi(x) < T(x) < (1+\epsilon)A(x)\pi(x),~~x>N, \]
or $T(x) = (1+ o(1))A(x)\pi(x)$. The rest follows as in the proof of Theorem \ref{t2}.
\end{proof}

\begin{corl} Let $k\geq1$ be given. Then there exists a positive integer $\lambda
\leq x^k$ such that $n^k+\lambda$, $n\leq x$, represents at least $(\frac1k+o(1))\pi(x)$
primes.\end{corl}
\begin{proof} Setting $a_n=n^k$ in Theorem \ref{t3}, and replacing $x$ by $x^k$ in
the conclusion of Theorem \ref{t3} shows that there exists $\lambda$, $1\leq\lambda
\leq x^k$, such that $n^k+\lambda$, $1\leq n^k\leq x^k$, represents at least
\[ (1 + o(1))\frac{(x^k)^{\frac1k}}{x^k}\pi(x^k) = (1 + o(1))\frac{x}{x^k}
\frac{x^k}{\log x^k} = (1 + o(1))\frac{x}{k\log x} = \left(\frac1k + o(1)\right)\pi(x) \]
primes.\end{proof}

We now apply our methods to the case when $B$ is the sequence of square-free numbers.

\begin{thrm}\label{t4} Let $A=\{a_n\}$ be a given sequence of natural numbers. Let
$A(x) = \sum_{a_n\leq x}1$, and let $\alpha$ be any fixed real number with $\frac12
<\alpha<1$. Let $\epsilon>0$ be given. Then for all sufficiently large $x$, there
exists $\lambda$, $1\leq\lambda\leq x^\alpha$, such that more than $(\frac6{\pi^2}
- \epsilon)A(x)$ of the numbers $a_n+\lambda$, $a_n\leq x$, are square-free.\end{thrm}
\begin{proof} Let $B=\{b_m\}$ be the sequence of square-free numbers, and let $B(x)
= \sum_{b_m\leq x}1$. It is known (see \cite{hua1982}) that
\[ B(x) = \frac{6x}{\pi^2} + O(\sqrt{x}). \]
Let $\alpha$ be fixed, $1/2 < \alpha < 1$, and let $L$ denote the number
$L = [x^\alpha]$.

Let $\epsilon>0$ be given. Then
\begin{align*}
\sum_{\lambda=1}^L \sum_{a_n\leq x}\sum_{b_m=a_n+\lambda} 1
&= \sum_{a_n\leq x}\sum_{\lambda\leq L}\sum_{b_m=a_n+\lambda} 1 \\
&= \sum_{a_n\leq x}\sum_{a_n+1\leq b_m\leq a_n+L}1 \\
&= \sum_{a_n\leq x} (B(a_n + L) - B(a_n)) \\
&= \sum_{a_n\leq x}\left(\frac{6L}{\pi^2} + O(\sqrt{x+L})\right) \\
&= \sum_{a_n\leq x}\frac{6L}{\pi^2}(1 + o(1)) \\
&> \left(\frac6{\pi^2} - \epsilon\right)L \sum_{a_n\leq x}1 \\
&= \left(\frac6{\pi^2} - \epsilon\right)LA(x)
\end{align*}
holds for sufficiently large $x$. Hence there exists at least one $\lambda$,
$1\leq\lambda\leq L = [x^\alpha]$, for which
\[ \sum_{a_n\leq x}\sum_{b_m = a_n+\lambda}1 > \left(\frac6{\pi^2} - \epsilon\right)A(x), \]
which was to be proved.\end{proof}

\begin{ackn} The authors wish to express their sincere thanks to the referee for
very helpful comments and suggestions that led to a considerable improvement of
this paper.
\end{ackn}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}