%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publisher's TeX code    *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{11-SEP-1997,11-SEP-1997,11-SEP-1997,11-SEP-1997}
 
\documentclass{era-l}

%\newcommand{\cal}{\mathcal}
\newcommand{\al}{\alpha}
\newcommand{\gm}{\gamma}
\newcommand{\La}{\Lambda}
\newcommand{\ro}{\rho}
\newcommand{\fr}{\frac}
\newcommand{\dfr}{\dfrac}
\newcommand{\sg}{\sigma}
\newcommand{\pq}{\phi(q)}
\newcommand{\re}{\operatorname{Re}} %\text{Re}}
\newcommand{\im}{\operatorname{Im}} %\text{Im}}
\newcommand{\les}{\leqslant} 
\newcommand{\ges}{\geqslant}
\newcommand{\tth}{|\theta|\le 1}

\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}

\begin{document}

\title[A complete Vinogradov 3-primes theorem]{A complete 
Vinogradov 3-primes theorem under the Riemann hypothesis}

\author{J.-M. Deshouillers}

\address{Mathematiques Stochastiques, UMR 9936 CNRS-U.Bordeaux 1, 
U.Victor Segalen Bordeaux 2, F33076 Bordeaux Cedex, France}

\email{dezou@u-bordeaux2.fr}

\author{G. Effinger}

\address{Department of Mathematics and Computer Science,  Skidmore
College, 
Saratoga Springs, NY 12866}

\email{effinger@skidmore.edu}

\author{H. te Riele}

\address{Centre for Mathematics and Computer Science, P.O. Box 4079,
1009 AB Amsterdam, The Netherlands}

\email{herman.te.riele@cwi.nl}

\author{D. Zinoviev}

%\address{Department of Mathematics, Ohio State University, Columbus,
%OH 43210}
\address{Memotec Communications, Inc.,
600 Rue McCaffrey,
Montreal, QC, H4T1N1, Canada}

%\email{dzinov@math.ohio-state.edu}
\email{zinovid@memotec.com}

\subjclass{Primary 11P32}

\date{February 26, 1997}

\commby{Hugh Montgomery}

\issueinfo{3}{15}{January}{1997}
\dateposted{September 17, 1997}
\pagespan{99}{104}
\PII{S 1079-6762(97)00031-0}

\copyrightinfo{1997}{American Mathematical Society}

%\keywords{Goldbach, Vinogradov, 3-Primes Problem, Riemann Hypothesis}
\keywords{Goldbach, Vinogradov, 3-primes problem, Riemann hypothesis}

\begin{abstract}We outline a proof that if the Generalized Riemann
Hypothesis holds, then every odd number above $5$ is a sum of three
prime numbers. The proof involves an asymptotic theorem covering all
but a finite number of cases, an intermediate lemma, and an extensive
computation.
\end{abstract}

\maketitle

\section{Introduction}

By ``The 3-Primes Problem," we mean: {\it can every odd number greater
than $5$ be written as a sum of three prime numbers?} This problem was
first successfully attacked by Hardy and Littlewood in their seminal
1923 paper \cite{HL}; using their {\it Circle Method} and assuming a
``Weak Generalized Riemann Hypothesis," they proved that every
sufficiently large odd number could be so written. The second author
has calculated \cite{E} directly from that paper that ``sufficiently
large," assuming the ``full" Generalized Riemann Hypothesis (GRH
below, i.e., that all non-trivial zeros of all Dirichlet $L$-functions
have real part equal to 1/2), is approximately ${10^{50}}$. In 1926
Lucke \cite{Lu}, in an unpublished doctoral thesis under Edmund
Landau, had already shown that with some refinements the figure could
be taken as ${10^{32}}$. 

In 1937 Vinogradov \cite{V} used his ingenious methods for estimating
exponential sums to establish the desired asymptotic result while
avoiding the GRH entirely. However, the numerical implications of
avoiding the GRH are substantial: in 1956 Borodzkin \cite{B} showed
that sufficiently large in Vinogradov's proof meant numbers greater
than ${3^{3^{15}}} \approx 10^{7000000}$. This figure has since been
improved significantly, most recently by Chen and Wang \cite{CW}, who
have established a bound of ${10^{43000}}$, but in any case this
figure is far beyond hope of ``checking the remaining cases by
computer."

If, however, we return to the original stance of Hardy and Littlewood
by assuming the truth of the GRH while at the same time using some of
the refined techniques of primarily Vinogradov and Linnik \cite{Li},
and using an extensive computer search, we do indeed arrive at the
following:

\begin{theorem} Assuming the GRH, every odd number greater than $5$ can
be expressed as a sum of three prime numbers.
\end{theorem}

The proof of this result falls naturally into three parts: an
asymptotic theorem handling all but a finite number of cases, a lemma
assuring the existence of primes relatively near unchecked odd
numbers, and a computer search for {\it $2$-primes} representations of
the remaining differences. We now outline each of these parts.

\section{The asymptotic theorem}

\begin{theorem}[Zinoviev] Assuming the GRH, every odd number greater 
than $10^{20}$ is a sum of three prime numbers.
\end{theorem}

We discuss here briefly the main ideas behind this result; for
complete details see \cite{Z}.

Fix $N\ge 9$. We are interested in the number of triples
$(p_1,p_2,p_3)$ of prime numbers which satisfy the equation

\begin{equation} N=p_1+p_2+p_3. \end{equation}
Following \cite{Li} we introduce the function 
\[ %$$
J(N)=\sum_{p_1+p_2+p_3=N}\log(p_1)\log(p_2)\log(p_3),
\] %$$
where the sum ranges over all triples of primes ($\ge 2$). If 
$J(N)> 0$ then there is at least one solution of (1). 
Here by $\Lambda(n)$ ($n$ is always a natural number)
we denote von Mangoldt's function: 
$\Lambda(n)=\log(p)$ if $n=p^k$ ($p$ is prime), and $\Lambda(n)=0$ 
otherwise. For any real number $\al$ set
\[ %$$
S(\al)=\sum_{n>1}\La(n)e^{-2\pi i\al n}e^{-n/N}.
\] %$$
Then we have
\[ %$$
S(\al)=\sum_{p>1}\log(p)e^{-2\pi i\al p}e^{-p/N}+
\theta N^{0.5}\log^2(N),
\] %$$
where $|\theta|\le 1$. Clearly, for any integer $m$
\[ %$$
\int_0^1e^{2\pi i\al m}d\al=\cases 1& \qquad \text{if }
m=0,\\0& \qquad \text{if } m\ne 0. \endcases 
\] %$$
Changing the order of summation and integration (see \cite{Li}), 
for some new real $\theta$ ($\tth$) we obtain
\[ %$$
J(N)=e\int_{-w}^{1-w}{S^3(\al)e^{2\pi i\al N}d\al}+\theta
N^{1.5}\log^3(N),
\] %$$
where $w=w(N)$ is a small number defined later. We will
express $J(N)$ as a sum of the leading term and the remainder.
Estimating the remainder from above, we will show that it
is less than the leading term when $N \ge 10^{20}$. We then
conclude that $J(N)>0$.

Following Linnik and Vinogradov, we subdivide the interval 
$[-w, 1-w]$ into the disjoint union of subsets 
$E_1',\ E_1'', \ E_2$. Our main idea is to refine this subdivision.
In particular we change the set of ``major arcs'', which in our
case is $E_1'$, making the intervals from this set smaller.
We do it as follows.

Let $Q=[1.1\log^2(N)],\ \tau=4900\log^4(N),\ w=1/\tau$. 

Denote by $E(a,q)$ (where if $q>1$, then $(a,q)=1$,
$010^{20}$ (not necessarily odd), GRH implies that 
\[ %$$
|S(\al)|<0.18\,\fr{N}{\log(N)}.
\] %$$
\end{lemma}

The proof of this lemma uses the Riemann-Hadamard method which
involves summation over the zeroes of $L$-functions. 

The leading term is treated using the circle method of Hardy and
Littlewood, as used by Vinogradov and Linnik.

\section{An intermediate lemma} 

Now, by the asymptotic theorem, our problem is reduced to considering
odd numbers which are $\le 10^{20}$. For these, we need the following:

\begin{lemma} If the GRH holds and if $6\le n \le 10^{20}$, then there
exists a prime number $p$ such that $4\le n-p \le 1.615 \times
10^{12}$.
\end{lemma}

\begin{proof}The conclusion of the lemma obviously holds for $n <
10^{12}$, say. For larger $n$, we apply Schoenfeld \cite{Sc}, equation
(6.1). Let $\Theta (n) = \sum_{p\le n}\log p$; if the GRH holds, and if
$n \ge 23 \times 10^8$, we have
\[ %$$ 
|\Theta(n) - n| < \frac{1}{8\pi}\sqrt{n}(\log n-2)\log n.\] %$$
Just suppose that there is no prime in the interval $(n-h,n]$ except
possibly for two of the six consecutive numbers from $n-5$ through
$n$; then we have 
\[ %$$
2\log n >
\Theta(n)-\Theta(n-h)=(\Theta(n)-n)-(\Theta(n-h)-(n-h))+h,\] %$$
whence by the above,
\[ %$$
h < \frac{1}{4\pi}\sqrt{n}(\log n-2)\log n + 2\log n.\] %$$
Since $n \le 10^{20}$, we get $h<1.615 \times 10^{12}$. We conclude
then that there must be a prime $p$ such that $4 \le n-p \le 1.615
\times 10^{12}$.
\end{proof}
 
We note here that the GRH actually implies an estimate on
$|\Theta(n)-n|$ which has a {\it single} $\log$ factor; see Ivic
\cite{I} for example. However, the second author, in working through
the details of such an estimate, found that the constant obtained was
large enough so that, at the level $n=10^{20}$, Schoenfeld's estimate
gives a slightly better numerical result.

\section {The computer search for 2-primes representations}

Finally, then, if $n$ is an odd number $\le 10^{20}$ and $p$ is as in
the previous lemma, then $m=n-p$ is even and $\le 1.615 \times
10^{12}$. But for $m$ we have the following:

\begin{theorem}[Deshouillers and te Riele] Every even number $4\le m
\le 10^{13}$ is a sum of two prime numbers.
\end{theorem}

For a complete exposition of this and related results, see \cite{DtR}.

Let $p_i$ be the $i$th odd prime number.
\par
The usual approach \cite{GLtR},
\cite{Si} to verify the Goldbach conjecture
on a given interval $[a,b]$ is to find, for every even
$e\in[a,b]$, the smallest odd prime $p_i$ such that $e-p_i$ is a
prime.
An efficient way to do this is to generate the set of primes
\[ %$$
{\mathcal Q}(a,b)=\{q~|~q %{\rm 
\text{~prime~and~} a-\epsilon_a\le q\le b\},\] %$$
where $\epsilon_a$ is chosen in a suitable way,
and to generate the sets of even numbers
${\mathcal E}_0\subset{\mathcal E}_1\subseteq{\mathcal E}_2\subseteq\cdots$,
defined by ${\mathcal E}_0=\emptyset$,
\[%$$
{\mathcal E}_{i+1}={\mathcal E}_i\cup({\mathcal Q}(a,b)+p_{i+1}),~~i=0,1,\dots,
\footnotemark\]%$$
\footnotetext{By ${\mathcal Q}(a,b)+p_{i+1}$ we mean the set:
$\{q+p_{i+1}|q\in{\mathcal Q}(a,b)\}$.}until ${\mathcal E}_{j}$ 
covers {\it all} the even numbers 
in the interval $[a,b]$ for some $j$.
The set ${\mathcal Q}(a,b)$ is generated with the sieve of Eratosthenes:
this is
the most time-consuming part of the computation.
For the choice of $\epsilon_a$ it is sufficient that $\epsilon_a$
exceeds
the largest odd prime used in the generation of the sets ${\mathcal E}_j$.
In the computations checking the Goldbach conjecture up to $4\times
10^{11}$
\cite{Si}, the largest {\it small} odd prime needed was $p_{446}=3163$
(this is the
smallest prime $p$ for which $244885595672-p$ is prime).
\par
A more efficient idea, which we have implemented, is to find, for
every
even $e\in[a,b]$, a prime $q$, close to $a$,
for which $e-q$ is a prime. To do that efficiently, a set of $k$
consecutive
primes $q_1, q_2, \dots, q_k$ close to $a$ is generated, for suitably
chosen $k$, and a large set ${\mathcal P}$ of all the odd primes up to
about
$b-a$ is precomputed (with the sieve of Eratosthenes)
in order to check the numbers $e-q$ for primality.
For the actual check of the interval $[a,b]$, we generate the sets of
even
numbers
${\mathcal F}_0\subset{\mathcal F}_1\subseteq{\mathcal F}_2\subseteq\cdots$,
defined by
${\mathcal F}_0=\emptyset$,
\[ %$$
{\mathcal F}_{i+1}={\mathcal F}_i\cup({\mathcal P}+q_{i+1}),~~i=0,1,\dots,\] %$$
until ${\mathcal F}_j$ covers {\it all} the even numbers in the interval
$[a,b]$
for some $j$.
In our experiments, we have chosen the intervals $[a,b]$ to have a
fixed
length of $10^8$. The largest possible prime we may need in the set
${\mathcal P}$ lies close to $b-q_1$. By the prime number theorem,
$q_1\approx a-k\log a$, so that $b-q_1\approx10^8+k\log a$.
For the choice of $k$ we notice that the density of the odd primes
among the
odd numbers up to $10^8$ is about $0.115$
(there are $5761454$ odd primes below $10^8$). This means that a
proportion
of about $0.885$ of the even
numbers in $[a,b]$ is {\it not} covered by the set
${\mathcal F}_1={\mathcal P}+q_1$; {\it if} the primes up to $10^8$ were
uniformly
distributed, which they are {\it not}, a proportion of about $0.885^2$
of
the even
numbers would not be covered by ${\mathcal F}_2$. After $151$ steps, this
proportion is
reduced to below $10^{-8}$. It turned out that $k=360$ was sufficient
for
our experiments. For $a\approx10^{13}$ this implies that the largest
prime
in the set ${\mathcal P}$ must have a size close to $10^8+10^4$.
\par
In the first approach, a {\it small} set of small primes up to $5000$,
say,
has to be available,
and for each interval $[a,b]$ to be treated, {\it all} the primes in
$[a,b]$ have to be generated. In the second approach, a {\it large}
set of
small primes up to about $10^8+10^4$ has to be generated (only once),
and for each interval $[a,b]$ to be treated, one has to find the
largest
$k$ primes $\le a$. Of course, this is much cheaper than to find {\it
all}
the primes in the interval $[a,b]$.
The price to pay is that for each $e\in[a,b]$ {\it some} prime $p$ is
found
for which $e-p$ is prime, but in general this $p$ is neither the
smallest nor
the largest such prime.
\par
For the actual generation of $k$ primes close to $a$ we have used
Jaeschke's
computational results \cite{J}, stating that if a positive integer
$n<2152302898747$ is a strong pseudoprime with respect to the first
five primes $2, 3, 5, 7, 11$, then $n$ is prime; corresponding bounds
for
the first six and seven primes
are $3474749660383$ and $341550071728321$, respectively.
\par
We have implemented the second approach on a Cray C98 vector computer
and verified the Goldbach conjecture for all even numbers
$>4\times10^{11}$
and $\le10^{13}$.
After the generation of $k$ primes near $a$,
the actual verification was carried out by sieving with a long array
of
64-bit integers called ODD, where each bit represents an odd number
$<10^8+10^4$, the bit being
1 if the corresponding odd number is prime, and 0 if it is composite.
Generating ${\mathcal F}_{i+1}$ from ${\mathcal F}_i$ amounts to doing an
``or''
operation between one long array of integers and a shifted version
of the array ODD. This can be carried out very efficiently on the Cray
C98.
In one typical run, we handled 5000 consecutive intervals of length
$10^8$.
Close to $10^{13}$ the time to generate
$5000\times 360$ large primes was about $2600$ CPU-seconds, and the
total
sieving time was about $5040$ seconds. The total time
used to cover the interval $[4\times10^{11},10^{13}]$ was
approximately 53
(low
priority) CPU-hours.
The largest number of large primes which we needed was $328$: for
$e=7379095622422$ and first prime $q_1=7378999992031$ it turned out
that $e-q_i$ is composite for $i=1,\dots,327$, and prime for $i=328$
($q_{328}=7379000002739$ and $e-q_{328}=95619683$).

%\  \

\section*{Acknowledgment} %. 
The second author wishes to thank Paul T. Bateman and
Marshall Ash for helpful correspondences on this topic.

\bibliographystyle{amsplain}
\begin{thebibliography}{99}

\bibitem{B}
K. G. Borodzkin, \textit{On I. M. Vinogradov's constant}, Proc. 3rd
All-Union Math. Conf., vol. 1, Izdat. Akad. Nauk SSSR, Moscow, 1956. (Russian)
\MR{20:6973a}
\bibitem{CW}
Jingrun Chen and Tianze Wang, \textit{On the odd Goldbach problem},
Acta Math. Sinica \textbf{32} (1989), 702--718.
\MR{91e:11108}
%\bibitem{DtR}
%Jean-Marc Deshouillers and Herman te Riele, \textit{New experimental
%results concerning the Goldbach conjecture}, in preparation.
\bibitem{DtR}
Jean-Marc Deshouillers, Herman te Riele, and Yannick Saouter, 
\textit{New experimental
results concerning the Goldbach conjecture}, to appear.
\bibitem{E}
Gove Effinger, \textit{Some numerical implication of the Hardy and
Littlewood analysis of the $3$-primes problem}, submitted for publication.
\bibitem{GLtR}
A. Granville, J. van de Lune, and H. te Riele, \textit{Checking the
Goldbach conjecture on a vector computer}, Number Theory and
Applications (R.A. Mollin, ed.), Kluwer Academic Publishers, 1989,
423--433.
 \MR{93c:11085}
\bibitem{HL}
G. H. Hardy and L. E. Littlewood, \textit{Some problems of `Partitio
Numerorum'. III: On the expression of a number as a sum of primes},
Acta Mathematica \textbf{44} (1922), 1--70.
\bibitem{I}
A. Ivic, \textit{The Riemann zeta-function}, J. Wiley and Sons, 1985.
 \MR{87d:11062}
\bibitem{J}Gerhard Jaeschke,
{\it On strong pseudoprimes to several bases},
Math. Comp. {\bf 61} (1993), 915--926.
 \MR{94d:11004} 
\bibitem{K}
A. A. Karatsuba, \textit{Basic analytic number theory},
Springer-Verlag, 1993.
 \MR{94a:11001}
\bibitem{Li}
U. V. Linnik, \textit{The new proof of Goldbach-Vinogradov's theorem},
Mat. Sb. \textbf{19} (1946), 3--8.
 \MR{8:317c} 
\bibitem{Lu}
Bruno Lucke, \textit {Zur Hardy-Littlewoodschen Behandlung des
Goldbachschen Problems}, Doctoral Dissertation, G\"ottingen, 1926.
\bibitem{R}
Paulo Ribenboim, \textit{The book of prime number records},
Springer-Verlag,  1988.
\MR{89e:11052}
\bibitem{Sc}
Lowell Schoenfeld, \textit {Sharper bounds for the Chebyshev functions
$\Theta(x)$ and $\Psi(x)$}, Mathematics of Computation \textbf{30}
(1976),  337--360.
\MR{56:15581b}
\bibitem{Si}
Matti K. Sinisalo, \textit{Checking the Goldbach conjecture up to $4
\times 10^{11}$}, Mathematics of Computation \textbf {61} (1993),
931--934.
\MR{94a:11157}
\bibitem{V}
I. M. Vinogradov, \textit{Representation of an odd number as a sum of
three primes}, Comptes Rendues (Doklady) de l'Academy des Sciences de
l'USSR \textbf {15} (1937), 191--294.
%\bibitem{Z}
%Dmitrii Zinoviev, \textit{On Vinogradov's Constant in Goldbach's
%Ternary Problem}, Journal of Number Theory, to appear.
\bibitem{Z}
Dmitrii Zinoviev, \textit{On Vinogradov's constant in Goldbach's
ternary problem}, Journal of Number Theory, {\bf 65} (1997), 
334--358. 
\end{thebibliography}

\end{document}


%=========================================================================
%Gove Effinger                      
%Associate Professor, Mathematics and Computer Science
%Skidmore College, Saratoga Springs, NY 12866         

%PHONE: (518) 584-5000 Ext. 2531, FAX (518) 584-3023
%INTERNET: effinger@skidmore.edu
%WWW: http://www.skidmore.edu/~effinger
%=========================================================================

%-------------------
%End of network mail
\endinput
02-Sep-97 08:05:18-EST,529000;000000000000
Return-path: 
Received: from AXP14.AMS.ORG by AXP14.AMS.ORG (PMDF V5.1-8 #1)
 id <01IN5RIB64O0000AN7@AXP14.AMS.ORG>; Tue, 2 Sep 1997 08:05:14 EST
Date: Tue, 02 Sep 1997 08:05:11 -0400 (EDT)
From: "pub-submit@ams.org " 
Subject: ERA/9700
To: pub-jour@MATH.AMS.ORG
Reply-to: pub-submit@MATH.AMS.ORG
Message-id: <01IN5RTPJW7Y000AN7@AXP14.AMS.ORG>
MIME-version: 1.0
Content-type: TEXT/PLAIN; CHARSET=US-ASCII


Return-path: 
Received: from gate1.ams.org by AXP14.AMS.ORG (PMDF V5.1-8 #1)
 with SMTP id <01IN0BADQ3DS0008ZV@AXP14.AMS.ORG>; Fri, 29 Aug 1997 10:17:54 EST
Received: from leibniz.math.psu.edu ([146.186.130.2])
 by gate1.ams.org via smtpd (for axp14.ams.org [130.44.1.14]) with SMTP; Fri,
 29 Aug 1997 14:17:31 +0000 (UT)
Received: from pascal.math.psu.edu (aom@pascal.math.psu.edu [146.186.130.199])
 by math.psu.edu (8.8.5/8.7.3) with ESMTP id KAA19911 for
 ; Fri, 29 Aug 1997 10:17:19 -0400 (EDT)
Received: (from aom@localhost) by pascal.math.psu.edu (8.8.5/8.7.3)
 id KAA24706 for pub-submit@MATH.AMS.ORG; Fri, 29 Aug 1997 10:17:16 -0400 (EDT)
Date: Fri, 29 Aug 1997 10:17:16 -0400 (EDT)
From: Alexander O Morgoulis 
Subject: *accepted to ERA-AMS, Volume 3, Number 1, 1997*
To: pub-submit@MATH.AMS.ORG
Message-id: <199708291417.KAA24706@pascal.math.psu.edu>

%% Modified August 28, 1997 by A. Morgoulis
%% Modified August 26, 1997 by A. Morgoulis
%% Modified August 25, 1997 by A. Morgoulis


% Date: 2-SEP-1997
%   \pagebreak: 0   \newpage: 0   \displaybreak: 0
%   \eject: 0   \break: 0   \allowbreak: 0
%   \clearpage: 0   \allowdisplaybreaks: 0
%   $$: 29   {eqnarray}: 0
%   \linebreak: 0   \newline: 0
%   \mag: 0   \mbox: 0   \input: 0
%   \baselineskip: 0   \rm: 1   \bf: 2   \it: 16
%   \hsize: 0   \vsize: 0
%   \hoffset: 0   \voffset: 0
%   \parindent: 0   \parskip: 0
%   \vfil: 0   \vfill: 0   \vskip: 0
%   \smallskip: 0   \medskip: 0   \bigskip: 0
%   \sl: 0   \def: 0   \let: 0   \renewcommand: 0
%   \tolerance: 0   \pretolerance: 0
%   \font: 0   \noindent: 0
%   ASCII 13 (Control-M Carriage return): 0
%   ASCII 10 (Control-J Linefeed): 0
%   ASCII 12 (Control-L Formfeed): 0
%   ASCII 0 (Control-@): 0
%