notes2bib-rh.bib

% This is an auxiliary file used by the 'notes2bib' package.
% This file may safely be deleted.
% It will be recreated as required.

@misc{Note01,
  note = {{\bf How not to factor the numerator of a Bernoulli number:} \par As mentioned in Chapter~\ref {ch:envision}, the coefficient $B_k$ of the linear term of the polynomial $$ S_k(n)= 1^k+2^k+3^k+\dots +(n-1)^k $$ is (up to sign) the $k$-th {\bf Bernoulli number}. These numbers are rational numbers and, putting them in lowest terms, their numerators play a role in certain problems, and their denominators in others. (This is an amazing story, which we can't go into here!) \par One of us (Barry Mazur) in the recent article {\em How can we construct abelian Galois extensions of basic number fields?} (see \url {http://www.ams.org/journals/bull/2011-48-02/S0273-0979-2011-01326-X/}) found himself dealing (for various reasons) with the fraction $-B_{200}/400$, where $B_{200}$ is the two-hundredth Bernoulli number. The numerator of this fraction is quite large: it is---hold your breath---\ $$389\cdot 691\cdot 5370056528687 \ \ \ \ \text {times this 204-digit number:} $$\vskip 10pt $N:=3452690329392158031464109281736967404068448156842396721012$\newline $\mbox {}\,\,\,\qquad 9920642145194459192569415445652760676623601087497272415557$\newline $\mbox {}\,\,\,\qquad 0842527652727868776362959519620872735612200601036506871681$\newline $\mbox {}\,\,\,\qquad 124610986596878180738901486527$ \vskip 10pt and he {\it incorrectly asserted} that it was prime. Happily, Bartosz Naskr\c {e}cki spotted this error: our $204$-digit $N$ is {\it not} prime. \par How did he know this? By using the most basic test in the repertoire of tests that we have available to check to see whether a number is prime: we'll call it the ``{\bf Fermat $2$-test.}'' We'll first give a general explanation of this type of test before we show how $N$ {\it fails the Fermat $2$-test.} \par \par The starting idea behind this test is the famous result known as {\em Fermat's Little Theorem} where the ``little'' is meant to alliteratively distinguish it from you-know-what. \begin {theorem}[Fermat's Little Theorem] If $p$ is a prime number, and $a$ is any number relatively prime to $p$ then $a^{p-1} - 1$ is divisible by $p$. \end {theorem} A good exercise is to try to prove this, and a one-word hint that might lead you to one of the many proofs of it is {\em induction}.\footnote {Here's the proof: $$(N+1)^p \equiv N^p +1 \equiv (N+1)\ \mod p,$$ where the first equality is the binomial theorem and the second equality is induction.} \par Now we are going to use this as a criterion, by---in effect---restating it in what logicians would call its {\it contrapositive}: \begin {theorem}[The Fermat $a$-test] If $M$ is a positive integer, and $a$ is any number relatively prime to $M$ such that $a^{M-1} - 1$ is {\it not} divisible by $M$, then $M$ is {\it not} a prime. \end {theorem} \par Well, Naskr\c {e}cki computed $2^{N-1}-1$ (for the $204$-digit $N$ above) and saw that it is {\it not} divisible\footnote {The number $2^{N-1}-1$ has a residue after division by $N$ of\\ $3334581100595953025153969739282790317394606677381970645616725285996925$\newline $ 6610000568292727335792620957159782739813115005451450864072425835484898$\newline $ 565112763692970799269335402819507605691622173717318335512037457$.} by $N$. Ergo, our $N$ fails the Fermat $2$-test so is {\it not} prime. \par But then, given that it is so ``easy'' to see that $N$ is not prime, a natural question to ask is: what, in fact, is its prime factorization? This---it turns out---isn't so easy to determine; Naskr\c {e}cki devoted $24$ hours of computer time setting standard factorization algorithms on the task, and that was not sufficient time to resolve the issue. The factorization of the numerators of general Bernoulli numbers is the subject of a very interesting website run by Samuel Wagstaff (\url {http://homes.cerias.purdue.edu/~ssw/bernoulli}). Linked to this web page one finds (\url {http://homes.cerias.purdue.edu/~ssw/bernoulli/composite}) which gives a list of composite numbers whose factorizations have resisted all attempts to date. The two-hundredth Bernoulli number is 12th on the list. \par The page \url {http://en.wikipedia.org/wiki/Integer_factorization_records} lists record challenge factorization, and one challenge that was completed in 2009 involves a difficult-to-factor number with 232 digits; its factorization was completed by a large team of researchers and took around 2000 years of CPU time. This convinced us that with sufficient motivation it would be possible to factor $N$, and so we asked some leaders in the field to try. They succeeded! \begin {quote}\sf Factorisation of B200 \par by Bill Hart on 4 Aug 05, 2012 at 07:24pm \par We are happy to announce the factorization of the numerator of the 200th Bernoulli number: \par \begin {align*} N &= 389 \cdot 691 \cdot 5370056528687 \cdot c_{204}\\ c_{204} &= p_{90} \cdot p_{115}\\ p_{90} &= 149474329044343594528784250333645983079497454292\\ &= 838248852612270757617561057674257880592603\\ p_{115} &= 230988849487852221315416645031371036732923661613\\ &= 619208811597595398791184043153272314198502348476\\ &= 2629703896050377709 \end {align*} \par The factorization of the 204-digit composite was made possible with the help of many people: \begin {itemize} \item William Stein and Barry Mazur challenged us to factor this number. \item Sam Wagstaff maintains a table of factorizations of numerators of Bernoulli numbers at \url {http://homes.cerias.purdue.edu/~ssw/bernoulli/bnum}. According to this table, the 200th Bernoulli number is the 2nd smallest index with unfactored numerator (the first being the 188th Bernoulli number). \item Cyril Bouvier tried to factor the c204 by ECM up to 60-digit level, using the TALC cluster at Inria Nancy - Grand Est. \item {\sf yoyo@home} tried to factor the c204 by ECM up to 65-digit level, using the help of many volunteers of the distributed computing platform \url {http://www.rechenkraft.net/yoyo/}. After ECM was unsuccessful, we decided to factor the c204 by GNFS. \item Many people at the Mersenne forum helped for the polynomial selection. The best polynomial was found by Shi Bai, using his implementation of Kleinjung's algorithm in CADO-NFS: \url {http://www.mersenneforum.org/showthread.php?p=298264##post298264}. Sieving was performed by many volunteers using {\sf NFS@home}, thanks to Greg Childers. See \url {http://escatter11.fullerton.edu/nfs} for more details about {\sf NFS@home}. This factorization showed that such a distributed effort might be feasible for a new record GNFS factorization, in particular for the polynomial selection. This was the largest GNFS factorization performed by {\sf NFS@home} to date, the second largest being $2^{1040}+1$ at 183.7 digits. \item Two independent runs of the filtering and linear algebra were done: one by Greg Childers with msieve (\url {http://www.boo.net/~jasonp/qs.html}) using a 48-core cluster made available by Bill Hart, and one by Emmanuel Thom\'{e} and Paul Zimmermann with CADO-NFS (\url {http://cado-nfs.gforge.inria.fr/}), using the Grid 5000 platform. \item The first linear algebra run to complete was the one with CADO-NFS, thus we decided to stop the other run. \end {itemize} \par Bill Hart \end {quote} \par We verify the factorization above in SageMath as follows: \\ \par {\sf sage: p90 = 1494743290443435945287842503336459830794974542928382\\ 48852612270757617561057674257880592603\\ sage: p115 = 230988849487852221315416645031371036732923661613619\\ 2088115975953987911840431532723141985023484762629703896050377709\\ sage: c204 = p90 * p115\\ sage: 389 * 691 * 5370056528687 * c204 == -numerator(bernoulli(200))\\ True\\ sage: is\_prime(p90), is\_prime(p115), is\_prime(c204)\\ (True, True, False) } },
  key = {Note01},
  keywords = {note},
  presort = {mm},
}

@misc{Note02,
  note = {\label {bibnote:factor} Given an integer $n$, there are many algorithms available for trying to write $n$ as a product of prime numbers. First we can apply {\em trial division}, where we simply divide $n$ by each prime $2, 3, 5, 7, 11, 13, \ldots $ in turn, and see what small prime factors we find (up to a few digits). After using this method to eliminate as many primes as we have patience to eliminate, we typically next turn to a technique called {\em Lenstra's elliptic curve method}, which allows us to check $n$ for divisibility by bigger primes (e.g., around 10--15 digits). Once we've exhausted our patience using the elliptic curve method, we would next hit our number with something called the {\em quadratic sieve}, which works well for factoring numbers of the form $n=pq$, with $p$ and $q$ primes of roughly equal size, and $n$ having less than 100 digits (say, though the 100 depends greatly on the implementation). All of the above algorithms---and then some---are implemented in SageMath, and used by default when you type {\tt factor(n)} into SageMath. Try typing {\tt factor(some number, verbose=8)} to see for yourself. \par If the quadratic sieve fails, a final recourse is to run the {\em number field sieve} algorithm, possibly on a supercomputer. To give a sense of how powerful (or powerless, depending on perspective!) the number field sieve is, a record-setting factorization of a general number using this algorithm is the factorization of a 232 digit number called RSA-768 (see \url {https://eprint.iacr.org/2010/006.pdf}): \par $ n = 12301866845301177551304949583849627207728535695953347921973224521\\ 517264005072636575187452021997864693899564749427740638459251925573263\\ 034537315482685079170261221429134616704292143116022212404792747377940\\ 80665351419597459856902143413 $ \par \noindent {}which factors as $pq$, where\par \noindent {} $ p = 334780716989568987860441698482126908177047949837137685689124313889\\ 82883793878002287614711652531743087737814467999489 $ \par \noindent {}and\par \noindent {} $ q = 367460436667995904282446337996279526322791581643430876426760322838\\ 15739666511279233373417143396810270092798736308917. $ \par \noindent {}We encourage you to try to factor $n$ in SageMath, and see that it fails. SageMath does not yet include an implementation of the number field sieve algorithm, though there are some free implementations currently available (see \url {http://www.boo.net/~jasonp/qs.html}). },
  key = {Note02},
  keywords = {note},
  presort = {mm},
}

@misc{Note03,
  note = {We can use SageMath (at \url {http://sagemath.org}) to quickly compute the ``hefty number'' $p = 2^{43,112,609}-1$. Simply type {\tt p = 2\^{}43112609 - 1} to instantly compute $p$. In what sense have we {\em computed} $p$? Internally, $p$ is now stored in base $2$ in the computer's memory; given the special form of $p$ it is not surprising that it took little time to compute. Much more challenging is to compute all the base 10 digits of $p$, which takes a few seconds: {\tt d = str(p)}. Now type {\tt d[-50:]} to see the last 50 digits of $p$. To compute the sum $58416637$ of the digits of $p$ type {\tt sum(p.digits())}. },
  key = {Note03},
  keywords = {note},
  presort = {mm},
}

@misc{Note04,
  note = { In contrast to the situation with factorization, testing integers of this size (e.g., the primes $p$ and $q$) for primality is relatively easy. There are fast algorithms that can tell whether or not any random thousand digit number is prime in a fraction of second. Try for yourself using the SageMath command {\tt is\_prime}. For example, if $p$ and $q$ are as in endnote~\ref {bibnote:factor}, then {\tt is\_prime(p)} and {\tt is\_prime(q)} quickly output True and {\tt is\_prime(p*q)} outputs False. However, if you type {\tt factor(p*q, verbose=8)} you can watch as SageMath tries forever and fails to factor $pq$.},
  key = {Note04},
  keywords = {note},
  presort = {mm},
}

@misc{Note05,
  note = {In Sage, the function {\tt prime\_range} enumerates primes in a range. For example, {\tt prime\_range(50)} outputs the primes up to $50$ and {\tt prime\_range(50,100)} outputs the primes between $50$ and $100$. Typing {\tt prime\_range(10\^{}8)} in SageMath enumerates the primes up to a hundred million in around a second. You can also enumerate primes up to a billion by typing {\tt v=prime\_range(10\^{}9)}, but this will use a large amount of memory, so be careful not to crash your computer if you try this. You can see that there are $\pi (10^9) = 50{,}847{,}534$ primes up to a billion by then typing {\tt len(v)}. You can also compute $\pi (10^9)$ directly, without enumerating all primes, using the command {\tt prime\_pi(10\^{}9)}. This is much faster since it uses some clever counting tricks to find the number of primes without actually listing them all. \par In Chapter~\ref {sec:tinkering} we tinkered with the staircase of primes by first counting both primes and prime powers. There are comparatively few prime powers that are not prime. Up to $10^8$, only $1{,}405$ of the $5{,}762{,}860$ prime powers are not themselves primes. To see this, first enter {\tt a~=~prime\_pi(10\^{}8); pp~=~len(prime\_powers(10\^{}8))}. Typing {\tt (a,~pp,~pp-a)} then outputs the triple {\tt (5761455, 5762860, 1405)}.},
  key = {Note05},
  keywords = {note},
  presort = {mm},
}

@misc{Note06,
  note = {Hardy and Littlewood give a nice conjectural answer to such questions about gaps between primes. See Problem {\bf A8} of Guy's book {\em Unsolved Problems in Number Theory} (2004). Note that Guy's book discusses counting the number $P_k(X)$ of pairs of primes up to $X$ that differ by a fixed even number $k$; we have $P_k(X)\geq \Gap _k(X)$, since for $P_k(X)$ there is no requirement that the pairs of primes be consecutive.},
  key = {Note06},
  keywords = {note},
  presort = {mm},
}

@misc{Note07,
  note = {If $f(x)$ and $g(x)$ are real-valued functions of a real variable $x$ such that for any $\epsilon >0$ both of them take their values between $ x^{1-\epsilon }$ and $ x^{1+\epsilon }$ for $x$ sufficiently large, then say that $f(x)$ and $g(x)$ are {\bf good approximations of one another} if, for any positive $\epsilon $ the absolute value of their difference is less than $ x^{{1\over 2}+\epsilon }$ for $x$ sufficiently large. The functions $\Li (X)$ and $R(X)$ are good approximations of one another.},
  key = {Note07},
  keywords = {note},
  presort = {mm},
}

@misc{Note08,
  note = {This computation of $\pi (X)$ was done by David J. Platt in 2012, and is the largest value of $\pi (X)$ ever computed. See \url {http://arxiv.org/abs/1203.5712} for more details.},
  key = {Note08},
  keywords = {note},
  presort = {mm},
}

@misc{Note09,
  note = {In fact, the Riemann Hypothesis is equivalent to $|\Li (X) - \pi (X)| \leq \sqrt {X}\log (X)$ for all $X\geq 2.01$. See Section 1.4.1 of Crandall and Pomerance's book {\em Prime Numbers: A Computational Perspective}.},
  key = {Note09},
  keywords = {note},
  presort = {mm},
}

@misc{Note10,
  note = {For a proof of this here's a hint. Compute the difference between the derivatives of $\Li (x)$ and of $x/\log x$. The answer is $1/\log ^2(x)$. So you must show that the ratio of $\int _2^X dx/\log ^2(x)$ to $\Li (x)= \int _2^Xdx/\log (x)$ tends to zero as~$x$ goes to infinity, and this is a good calculus exercise.},
  key = {Note10},
  keywords = {note},
  presort = {mm},
}

@misc{Note11,
  note = {See \url {http://www.maths.tcd.ie/pub/HistMath/People/Riemann/Zeta/} for the original German version and an English translation.},
  key = {Note11},
  keywords = {note},
  presort = {mm},
}

@misc{Note12,
  note = {We have $$\psi (X) =\sum _{p^n \le X}\log p$$ where the summation is over prime powers $p^n$ that are $\le X$.},
  key = {Note12},
  keywords = {note},
  presort = {mm},
}

@misc{Note13,
  note = {See \url {http://en.wikipedia.org/wiki/Fast_Fourier_transform}},
  key = {Note13},
  keywords = {note},
  presort = {mm},
}

@misc{Note14,
  note = { \url {http://en.wikipedia.org/wiki/Distribution_\%28mathematics\%29} contains a more formal definition and treatment of distributions. Here is Schwartz's explanation for his choice of the word {\it distribution:} \begin {quote}``Why did we choose the name distribution? Because, if $\mu $ is a measure, i.e., a particular kind of distribution, it can be considered as a distribution of electric charges in the universe. Distributions give more general types of electric charges, for example dipoles and magnetic distributions. If we consider the dipole placed at the point $a$ having magnetic moment $M$, we easily see that it is defined by the distribution $-D_M \delta _{(a)}$. These objects occur in physics. Deny's thesis, which he defended shortly after, introduced electric distributions of finite energy, the only ones which really occur in practice; these objects really are distributions, and do not correspond to measures. Thus, distributions have two very different aspects: they are a generalization of the notion of function, and a generalization of the notion of distribution of electric charges in space. [...] Both these interpretations of distributions are currently used.''\end {quote}},
  key = {Note14},
  keywords = {note},
  presort = {mm},
}

@misc{Note15,
  note = { David Mumford suggested that we offer the following paragraph from\\ \url {http://en.wikipedia.org/wiki/Dirac_delta_function}\\ on the Dirac delta function: \begin {quote} An infinitesimal formula for an infinitely tall, unit impulse delta function (infinitesimal version of Cauchy distribution) explicitly appears in an 1827 text of Augustin Louis Cauchy. Sim\'{e}on Denis Poisson considered the issue in connection with the study of wave propagation as did Gustav Kirchhoff somewhat later. Kirchhoff and Hermann von Helmholtz also introduced the unit impulse as a limit of Gaussians, which also corresponded to Lord Kelvin's notion of a point heat source. At the end of the 19th century, Oliver Heaviside used formal Fourier series to manipulate the unit impulse. The Dirac delta function as such was introduced as a ``convenient notation'' by Paul Dirac in his influential 1930 book {\em Principles of Quantum Mechanics}. He called it the ``delta function'' since he used it as a continuous analogue of the discrete Kronecker delta. \end {quote}},
  key = {Note15},
  keywords = {note},
  presort = {mm},
}

@misc{Note16,
  note = {As discussed in\\ \url {http://en.wikipedia.org/wiki/Distribution_\%28mathematics\%29}, ``generalized functions'' were introduced by Sergei Sobolev in the 1930s, then later independently introduced in the late 1940s by Laurent Schwartz, who developed a comprehensive theory of distributions. },
  key = {Note16},
  keywords = {note},
  presort = {mm},
}

@misc{Note17,
  note = {If the \RH {} holds they are precisely the {\it imaginary parts of the ``nontrivial'' zeroes of the Riemann zeta function}.},
  key = {Note17},
  keywords = {note},
  presort = {mm},
}

@misc{Note18,
  note = { {\it The construction of $ \Phi (t)$ from $\psi (X)$:} \par Succinctly, for positive real numbers $t$, $$\Phi (t): \ = \ e^{- t/2}\Psi '(t),$$ where $\Psi (t) = \psi (e^t)$ (see Figure~\ref {fig:psi_200}), and $\Psi '$ is the derivative of $\Psi (t)$, viewed as a distribution. We extend this function to all real arguments $t$ by requiring $\Phi (t)$ to be an even function of $t$, i.e., $\Phi (-t)= \Phi (t)$. But, to review this at a more leisurely pace, \begin {enumerate} \par \item Distort the $X$-axis of our staircase by replacing the variable $X$ by $e^t$ to get the function $$\Psi (t):= \psi (e^t).$$ No harm is done by this for we can retrieve our original $\psi (X)$ as $$\psi (X) = \Psi (\log (X)).$$ Our distorted staircase has risers at ($0$ and) all positive integral multiples of logs of prime numbers. \par \par \par \par \item Now we'll do something that might seem a bit more brutal: {\it take the derivative of this distorted staircase $\Psi (t)$.} This derivative $\Psi '(t)$ is a {\it generalized} function with support at all nonnegative integral multiples of logs of prime numbers. \par \vskip 20pt \ill {bigPsi_prime}{1}{$\Psi '(t)$ is a (weighted) sum of Dirac delta functions at the logarithms of prime powers $p^n$ weighted by $\log (p)$ (and by $\log (2\pi )$ at $0$). The taller the arrow, the larger the weight.} \par \item Now---for normalization purposes---multiply $\Psi '(t)$ by the function $e^{-t/2}$ which has no effect whatsoever on the support. \end {enumerate} \vskip 20pt\ill {psi_200}{.4}{Illustration of the staircase $\psi (X)$ constructed in Chapter~\ref {sec:tinkering} that counts weighted prime powers.\label {fig:psi_200}} \par \par \par In summary: The generalized function that resulted from the above carpentry: $$\Phi (t) = e^{-t/2}\Psi '(t),$$ retains the information we want (the placement of primes) even if in a slightly different format. },
  key = {Note18},
  keywords = {note},
  presort = {mm},
}

@misc{Note19,
  note = { A version of the Riemann--von Mangoldt explicit formula gives some theoretical affirmation of the phenomena we are seeing here. We thank Andrew Granville for a discussion about this. \par \ill {granville}{0.25}{Andrew Granville} \par \par Even though the present endnote is not the place to give anything like a full account, we can't resist setting down a few of Granville's comments that might be helpful to people who wish to go further. (This discussion can be modified to analyze what happens unconditionally, but we will be assuming the \RH {} below.) The function ${\hat \Phi }_{\le C}(\theta )$ that we are graphing in this chapter can be written as: $${\hat \Phi }_{\le C}(\theta )= \sum _{n\le C}\Lambda (n)n^{-w}$$ where $w = {\frac {1}{2}}+i\theta $. This function, in turn, may be written (by Perron's formula) as \begin {align*} &{\frac {1}{2\pi i }}\lim _{T \to \infty }\int _{s=\sigma _o-iT}^{s=\sigma _o+iT}\sum _{n}\Lambda (n)n^{-w}\left ({\frac {C}{n}}\right )^{s}{\frac {ds}{s}}\\ &= {\frac {1}{2\pi i }}\lim _{T \to \infty }\int _{s=\sigma _o-iT}^{s=\sigma _o+iT}\sum _{n}\Lambda (n)n^{-w-s}C^{s}{\frac {ds}{s}}\\ &= -{\frac {1}{2\pi i }}\lim _{T \to \infty }\int _{s=\sigma _o-iT}^{s=\sigma _o+iT}\left ({\frac {\zeta '}{\zeta }}\right )(w+s){\frac {C^{s}}{s}}ds. \end {align*} \par Here, we assume that $\sigma _o$ is sufficiently large and $C$ is not a prime power. \par One proceeds, as is standard in the derivation of Explicit Formulae, by moving the line of integration to the left, picking up residues along the way. Fix the value of $w= {\frac {1}{2}}+i\theta $ and consider $$K_w(s,C):=\ \ {\frac {1}{2\pi i }}\left (\frac {\zeta '}{\zeta }\right )(w+s){\frac {C^{s}}{s}},$$ which has poles at $$s= 0, \ \ \ 1-w,\ \ \ {\rm and }\ \ \ \rho -w, $$ for every zero $\rho $ of $\zeta (s)$. We distinguish five cases, giving descriptive names to each: \par \begin {enumerate} \item {\it Singular pole:} $s= 1-w$. \item {\it Trivial poles:} $s= \rho -w$ with $\rho $ a trivial zero of $\zeta (s)$. \item {\it Oscillatory poles:} $s= \rho -w = i(\gamma -\theta ) \ne 0$ with $\rho = 1/2 + i \gamma (\ne w)$ a nontrivial zero of $\zeta (s)$. (Recall that we are assuming the \RH {}, and our variable $w= {\frac {1}{2}}+i\theta $ runs through complex numbers of real part equal to ${\frac {1}{2}}$. So, in this case, $s$ is purely imaginary.) \item {\it Elementary pole:} $s=0$ when $ w$ is not a nontrivial zero of $\zeta (s)$---i.e., when $0=s\ne \rho -w$ for any nontrivial zero $\rho $. \item {\it Double pole:} $s=0$ when $ w$ is a nontrivial zero of $\zeta (s)$---i.e., when $0=s=\rho -w$ for some nontrivial zero $\rho $. This, when it occurs, is indeed a double pole, and the residue is given by $m\cdot \log C +\epsilon $. Here $m$ is the multiplicity of the zero $\rho $ (which we expect always---or at least usually---to be equal to $1$) and $\epsilon $ is a constant (depending on $\rho $, but not on $C$). \par \end {enumerate} \par The standard technique for the ``Explicit formula'' will provide us with a formula for our function of interest ${\hat \Phi }_{\le C}(\theta )$. The formula has terms resulting from the residues of each of the first three types of poles, and of the {\it Elementary} or the {\it Double} pole---whichever exists. Here is the shape of the formula, given with terminology that is meant to be evocative: \par \par $$ {\bf (1)}\ \ \ {\hat \Phi }_{\le C}(\theta ) = {\Sing }_{\le C}(\theta ) + {\Triv }_{\le C}(\theta ) + {\Osc }_{\le C}(\theta ) + {\Elem }_{\le C}(\theta )$$ \par Or: \par $${\bf (2)}\ \ \ {\hat \Phi }_{\le C}(\theta ) = {\Sing }_{\le C}(\theta ) + {\Triv }_{\le C}(\theta ) + {\Osc }_{\le C}(\theta ) + {\Double }_{\le C}(\theta ),$$ \par \noindent the first if $w$ is not a nontrivial zero of $\zeta (s)$ and the second if it is. \par The good news is that the functions ${\Sing }_{\le C}(\theta ), {\Triv }_{\le C}(\theta )$ (and also ${\Elem }_{\le C}(\theta )$ when it exists) are smooth (easily describable) functions of the two variables $C$ and $\theta $; for us, this means that they are not that related to the essential information-laden {\it discontinuous} structure of $ {\hat \Phi }_{\le C}(\theta )$. Let us bunch these three contributions together and call the sum ${\Smooth }(C,\theta )$, and rewrite the above two formulae as: $$ {\bf (1)}\ \ \ {\hat \Phi }_{\le C}(\theta ) ={\Smooth }(C,\theta ) + {\Osc }_{\le C}(\theta ) $$ \par Or: \par $${\bf (2)}\ \ \ {\hat \Phi }_{\le C}(\theta ) = {\Smooth }(C,\theta )+ {\Osc }_{\le C}(\theta ) + m\cdot \log C +\epsilon ,$$ \par depending upon whether or not $w$ is a nontrivial zero of $\zeta (s)$. \par \par We now focus our attention on the Oscillatory term, ${\Osc }_{\le C}(\theta ) $, approximating it by a truncation: $$\Osc _w(C,X):= 2\sum _{|\gamma | < X} {{\frac {e^{i\log C\cdot (\gamma -\theta )}}{i(\gamma -\theta )}}}.$$ Here if a zero has multiplicity $m$, then we count it $m$ times in the sum. Also, in this formula we have relegated the ``$\theta $" to the status of a subscript (i.e., $w = {\frac {1}{2}} +i\theta $) since we are keeping it constant, and we view the two variables $X$ and $C$ as linked in that we want the cutoff ``$X$" to be sufficiently large, say $X \gg C^2$, so that the error term can be controlled. \par At this point, we can perform a ``multiplicative version'' of a Ces\`aro summation---i.e., the operator $F(c) \mapsto ({\Ces } F)(C):= \int _1^CF(c) dc/c.$ This has the effect of forcing the oscillatory term to be bounded as $C$ tends to infinity. \par This implies that for any fixed $\theta $, \begin {itemize} \item ${\Ces }{\hat \Phi }_{\le C}(\theta )$ is bounded independent of $C$ if $\theta $ is not the imaginary part of a nontrivial zero of $\zeta (s)$ and \item ${\Ces }{\hat \Phi }_{\le C}(\theta )$ grows as ${\frac {m}{2}}\cdot (\log C)^2 +O(\log C)$ if $\theta $ is the imaginary part of a nontrivial zero of $\zeta (s)$ of multiplicity $m$, \end {itemize} giving a theoretical confirmation of the striking feature of the graphs of our Chapter~\ref {ch:prime-to-spectrum}.},
  key = {Note19},
  keywords = {note},
  presort = {mm},
}

@misc{Note20,
  note = { A reference for this is: \par \vskip 10pt {\bf [I-K]: }H. Iwaniec; E. Kowalski, {\bf Analytic Number Theory}, {\em American Mathematical Society Colloquium Publications} {\bf 53} (2004). \par (See also the bibliography there.) \vskip 10pt Many ways of seeing the explicit relationship are given in Chapter 5 of {\bf [I-K]}. For example, consider Exercise 5 on page 109. \par $$\sum _{\rho }{\hat \phi }(\rho ) = -\sum _{n \ge 1}\Lambda (n)\phi (n) + I(\phi ),$$ \par where \begin {itemize} \item $\phi $ is any smooth complex-valued function on $[1,+\infty )$ with compact support,\item ${\hat \phi }$ is its Mellin transform $${\hat \phi }(s):= \int _0^{\infty }\phi (x)x^{s-1}dx,$$ \item the last term on the right, $I(\phi )$, is just $$I(\phi ):= \int _1^{\infty }(1-{\frac {1}{x^3-x}})\phi (x)dx$$ (coming from the pole at $s=1$ and the ``trivial zeroes''). \item The more serious summation on the left hand side of the equation is over the nontrivial zeroes $\rho $, noting that if $\rho $ is a nontrivial zero so is~${\bar \rho }$. \end {itemize} \par \par \par Of course, this ``explicit formulation'' is not {\it immediately} applicable to the graphs we are constructing since we cannot naively take ${\hat \phi }$ to be a function forcing the left hand side to be $G_C(x)$. \par See also Exercise 7 on page 112, which discusses the sums $$ x - \sum _{|\theta | \le C} {\frac {x^{{\frac {1}{2}} +i\theta }-1}{{\frac {1}{2}} +i\theta }}. $$},
  key = {Note20},
  keywords = {note},
  presort = {mm},
}

@misc{Note21,
  note = {You may well ask how we propose to order these correction terms if RH is false. Order them in terms of (the absolute value of) their imaginary part, and in the unlikely situation that there is more than one zero with the same imaginary part, order zeroes of the same imaginary part by their real parts, going from right to left.},
  key = {Note21},
  keywords = {note},
  presort = {mm},
}

@misc{Note22,
  note = {Bombieri, {\em The Riemann Hypothesis}, available at \url {http://www.claymath.org/sites/default/files/official_problem_description.pdf}},
  key = {Note22},
  keywords = {note},
  presort = {mm},
}