Put $V={\mathbb{R}}^d$ and write $a^{(k)}$ for the degree-$k$ component of a tensor. We use the truncated tensor algebraHere $V^{\otimes 0}=\mathbb{R}$, and products of degree above $N$ are discarded. The answers to the three printed parts follow with these conventions; the middle part is missing from the converted TeX.

Use binary codes, so the polynomial modulus is $f(X)=X^N+1=X^N-1$ in ${\mathbb{F}}_2[X]$. A cyclic code $C$ is a linear subspace of ${\mathbb{F}}_2^N$ invariant under the cyclic shift $(a_0,\dots ,a_{N-1})\mapsto (a_{N-1},a_0,\dots ,a_{N-2})$. Identify a word with $a(X)={\sum }_{i=0}^{N-1}{a}_i{X}^i$. Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo $f$. In the quotient ringmultiplication by $X$ is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of $R$. Conversely, an ideal is a linear subspace closed under multiplication by $X$, proving the correspondence.

Take the inverse image of $C$ in ${\mathbb{F}}_2[X]$. This is an ideal containing $(f)$. The polynomial division algorithm shows directly that it has a unique monic generator $g$: choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because $f$ belongs to the ideal, $g\mid f$. Conversely every monic divisor of $f$ defines an ideal of $R$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, $g$ is its nonzero polynomial representative of least polynomial degree. For the zero code, use $g=f$, whose residue in $R$ is zero; this standard convention covers that endpoint despite its having no nonzero codeword.

Let $r=\mathrm{deg}g$ and $k=N-r$, and put $h=f/g$. Every codeword has a unique representation $bg$ with $\mathrm{deg}b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\dots ,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with $g=1$.

For length 16, characteristic two gives $X^{16}+1=(X+1{)}^{16}$. Its only monic divisors are $(X+1{)}^j$ for $0\le j\le 16$. Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain $C_{16}\subset C_{15}\subset \cdots \subset C_0$. This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are $(X+1{)}^{16-j}$. An explicit expansion of each generator is ${\prod }_{b:\text{bit }b\text{ of }j\text{ is }1}(1+X^{2^b})$.

The canonical check polynomial of a cyclic code isIndeed $ah\equiv 0(\mathrm{mod}f)$ means $f\mid ah$. Since $f=gh$, cancellation in the polynomial ring gives $g\mid a$, exactly code membership. No coprimality of $g$ and $h$ is needed, including for length 16.

There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial $\tilde{h}$ to equal this canonical $h$. If $d=\gcd (f,\tilde{h})$, write $f=d{f}_1$ and $\tilde{h}=d{h}_1$ with $\gcd (f_1,h_1)=1$. Then $f\mid a\tilde{h}$ holds exactly when $f_1\mid a$, so its kernel is the ideal generated by $f/d$. ThereforeEquivalently $\tilde{h}=hu$ with $\gcd (u,g)=1$. Requiring the monic divisor of $f$ selects the canonical check polynomial of a cyclic code. For example $Xh$ gives the same kernel as $h$, since $X$ is a unit modulo $f$, but is generally a different polynomial. Given any permitted $\tilde{h}$, taking $\gcd (f,\tilde{h})$ recovers the canonical $h$.

To construct a parity-check matrix, write the canonical $h={\sum }_{l=0}^k{h}_l{X}^l$ and its reciprocal polynomial $h^{\ast }(X)=X^{k}h(X^{-1})$. Take coefficient vectors, padded to length $N$, ofas the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\dots ,N-1$ and are independent. For a word $a$, row $j$ has dot product ${\sum }_{l=0}^k{h}_{k-l}{a}_{j+l}$, the coefficient of $X^{k+j}$ in the ordinary product $ah$. If $a\in C$, then $ah=bf$ with $\mathrm{deg}b<k$. This product has no terms in degrees $k,\dots ,N-1$, so $H{a}^T=0$. The kernel of $H$ has dimension $N-r=k$, the same as $C$, proving $\ker H=C$. This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.

Alternatively, a supplied check polynomial of a cyclic code reduced modulo $f$, $\tilde{h}={\sum }_{l=0}^{N-1}{\tilde{h}}_l{X}^l$, gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by $\tilde{h}$ modulo $f$, so its kernel is $C$ and its matrix rank is $r$. Selecting independent rows yields a rank-$r$ parity-check matrix even without initially normalizing the supplied polynomial.

The syndrome $s(y)=H{y}^T$ labels the coset $C+y$. Indeed $s(y)=s(z)$ if and only if $H(y-z{)}^T=0$, equivalently $y-z\in C$. There are $2^r$ cosets, each with $2^k$ words, and the syndrome classification of code cosets gives a bijection between them and ${\mathbb{F}}_2^r$. If $y=c+e$ is a transmitted codeword plus an error, then $s(y)=s(e)$: the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most $\lfloor (d-1)/2\rfloor$, since the corresponding error-correction balls are disjoint.

For the repetition code, the nonzero codeword is the all-ones word, soTheir product is $X^N+1$, and the generator polynomial degree $N-1$ gives dimension one. For the single parity-check code, membership is $a(1)=0$, equivalent to divisibility by $X+1$. ThusIts dimension is $N-1$; it is the even-weight code.

Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$, so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the $[7,4,3]$ Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.

We give the bounds for an alphabet of size $q\ge 2$, including the binary case $q=2$. Let $C$ be a length-$n$ code with $M$ codewords and minimum Hamming distance at least $d$, where $1\le d\le n$. Write $A_q(n,d)$ for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius $t$. The $j$th term chooses the changed coordinates and the $q-1$ alternative symbols in each.

For the Hamming bound, put $t=\lfloor (d-1)/2\rfloor$. Balls of radius $t$ around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most $2t<d$. Counting those balls inside the $q^n$ ambient words provesNo linearity is needed. For a linear code of dimension $k$ over ${\mathbb{F}}_q$, replace $M$ by $q^k$.

For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least $d$ from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius-$(d-1)$ balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has $M{V}_q(n,d-1)\ge q^n$, proving the existence boundOne may take the ceiling on the right because code size is integral.

For completeness, the sharper linear version is the Varshamov bound for linear codes. When $q$ is a prime power and $d\ge 2$, an $[n,k,\ge d]$ linear code exists providedSet $r=n-k$ and choose $n$ columns of an $r\times n$ parity-check matrix in order. When choosing column $l$, exclude all combinations of at most $d-2$ earlier columns, including the zero combination. There are at most ${\sum }_{j=0}^{d-2}\left(\genfrac{}{}{0ex}{}{l-1}{j}\right)(q-1{)}^j$ forbidden vectors, smaller than $q^r$ by the assumed inequality. A column can therefore be chosen. Inductively every set of at most $d-1$ chosen columns is independent: a relation involving the newest one would express it as a combination of at most $d-2$ earlier columns. The kernel has dimension at least $n-r=k$ and minimum Hamming distance at least $d$, since a low-weight kernel vector would be such a column relation. If its dimension is larger than $k$, take a $k$-dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.

To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is ${\log }_q((q-1)(1-x)/x)$, so it is increasing on $[0,1-1/q]$ and has maximum one at $1-1/q$. Stirling's formula gives, uniformly for integer $0\le j\le n$,The sum defining $V_q$ is between its largest summand and $(n+1)$ times that summand. For radius fractions tending to $\rho \le 1-1/q$, monotonicity of $H_q$ makes the largest exponent tend to $H_q(\rho )$. Consequently the Hamming ball volume exponent isFor $\rho >1-1/q$, the exponent is one: use a radius fraction just below $1-1/q$ for a lower bound and $V_q\le q^n$ for an upper bound.

Set $d_n=\max \{1,\lceil \delta n\rceil \}$ and define the asymptotic rate-distance function byThe code rate is $n^{-1}{\log }_{q}M$ and the relative minimum distance is $d/n$. A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to $\delta /2$, so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to $\delta$, giving the asymptotic Gilbert–Varshamov boundFor larger $\delta$, this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.

The asymptotic lower bound is also achievable by linear codes over a finite field. For $\delta >0$ and sufficiently large $n$, take redundancy $r_n=\lfloor {\log }_q{V}_q(n-1,d_n-2)\rfloor +1$, so $q^{r_n}>V_q(n-1,d_n-2)$. The linear existence condition produces dimension at least $n-r_n$; its rate has liminf at least $1-H_q(\delta )$. At $\delta =0$, use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere $h_2$ is the binary entropy function.

Use base-two logarithms and put $H=H(U_1)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Zero-probability letters can be omitted. The random variables $I_j=-{\log }_2{p}_{U_j}$ are self-information values, are IID, and have finite mean $H$ because the alphabet is finite. Independence givesFor an arbitrary $\delta >0$, define the typical setThe weak law of large numbers implies $P(T_{n,\delta })\to 1$. Every string in this set satisfiesThis is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.

For the upper bound, summing the lower bound on typical-string probabilities yields $|T_{n,\delta }|\le 2^{n(H+\delta )}$. For sufficiently large $n$, its probability is at least $1-\epsilon$, so it is an admissible set in the definition of $M(n,\epsilon )$. HenceFor the lower bound, let $A$ be any admissible set and write ${\eta }_n=P(T_{n,\delta }^c)\to 0$. ThenEach member of this intersection has probability at most $2^{-n(H-\delta )}$. Therefore, for all sufficiently large $n$,This applies in particular to a minimum-size admissible set, giving a liminf at least $H-\delta$. Letting $\delta \downarrow 0$ proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, $H=0$ and $M(n,\epsilon )=1$, consistent with the formula.

For coding, label the strings in an admissible set with distinct binary indices of length $\lceil {\log }_{2}M(n,\epsilon )\rceil$. A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically $H$ bits per source symbol describe any fixed fraction $1-\epsilon$ of the probability mass. More strongly, every rate $R>H$ permits block codes with error tending to zero: choose $\delta <R-H$, encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most $2^{n(H+\delta )}+1\le 2^{nR}$ for large $n$.

Conversely, a block encoder with at most $2^{nR}$ outputs can reconstruct at most that many distinct input strings correctly. If $R<H$, choose $0<\delta <H-R$. Its success probability is at mostThis gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate ${\log }_2|\{i:p_i>0\}|$.

Extend $f$ by zero outside $[1,N]\cap \mathbb{Z}$. Here is a dyadic endpoint convention for small Type I and Type II sums. Write $D_M=[M,2M)\cap \mathbb{Z}$, with $M$ a power of two. Type I sums are $\delta$-small if, for every $M\le N^{1/100}$, dyadic $K$ with $MK\le N$, and arbitrary integer intervals $I_m\subset D_K$,Type II sums are $\delta$-small if, for all dyadic $M,K\in [N^{1/100},N^{99/100}]$ and sequences $|a_m|,|b_n|\le 1$,Zero extension handles boxes crossing the endpoint $mn=N$. Fixed choices of open or closed dyadic endpoints do not matter, but interval uniformity and uniformity in both bounded coefficient sequences do matter. These are the estimates used in the Vinogradov Type I–II method.

An interesting technical step is Fourier separation of interval cutoffs. For an integer interval $I_m$, let $\widehat{1_{I_m}}(\theta )={\sum }_{r\in I_m}e(-r\theta )$. Discrete Fourier inversion givesThe exponential geometric sum bound gives a common envelope $H_N(\theta )\ll \min (N,\Vert \theta {\Vert }^{-1})$, with ${\int }_0^1{H}_N\ll \log (2N)$. Divide the interval transform by this envelope: at each frequency it is a bounded coefficient depending on $m$, and $e(n\theta )$ is a bounded coefficient depending on $n$. The Type II sum assumption therefore bounds the interval-cutoff sum by $O(\delta N\log N)$. Choosing the outer unit phases to turn each inner sum into its modulus extends the Type I sum bound to boxes where both variables are in the Type II range.

Take $U=V=\lfloor N^{1/3}\rfloor$. With subscripts denoting truncation of arithmetic functions, the Vaughan identity iswhere $\ast$ now means Dirichlet convolution. For completeness it follows from $\mu \ast 1=ϵ$ and $\Lambda \ast 1=\log$: expand ${\mu }_{>U}\ast {\Lambda }_{>V}\ast 1$, cancel the short terms, and retain $\Lambda$. The short first term contributes $O(N^{1/3}\log N)$ to the sum against $f$.

The next two terms give Type I sums. The logarithmic term has outer coefficient $\mu (m)$, $m\le U$, and inner factor $\log n$, removed by partial summation at a cost $O(\log N)$. In the other term the outer variable is $m=cd\le UV$ with coefficientThis logarithmic coefficient bound in Vaughan identity avoids a loss from a divisor weight. On boxes with short outer variable use the hypothesis directly; on boxes where both variables are at least $N^{1/100}$ use the extended bound proved above. Boxes with inner variable less than $N^{1/100}$ contain at most $O(N^{2/3+1/100})$ pairs in total and are treated trivially. All remaining inner scales are at most $N^{99/100}$ whenever the outer scale exceeds $N^{1/100}$.

For the final convolution, group the variables asBoth variables lie between constant multiples of $N^{1/3}$ and $N^{2/3}$, well inside the Type II range. Divide $b(n)$ by $\log N$, and apply the Type II sum estimate. If the product cutoff is kept explicitly, Fourier separation of interval cutoffs costs only one extra logarithm; zero extension also permits its omission. There are $O({\log }^{2}N)$ boxes in the dyadic decomposition. The coefficient bound and, where needed, partial summation cost at most one more logarithm. These estimates give the convenient boundWith $\delta =(\log N{)}^{-20}$, each term is $o(N)$, proving the assertion. The grouping of the long term uses the nonnegativity of the Von Mangoldt function; more usual groupings instead control a divisor coefficient by a second-moment truncation. Ben Green's notes, Sections 2.3–2.4 describe that standard alternative.

Now take the sign version of the Thue–Morse sequence, $f(n)=(-1{)}^{s_2(n)}$. Concatenation of binary digits gives $f(a{2}^j+r)=f(a)f(r)$ for $0\le r<2^j$. Expanding over all choices of digits proves the Thue–Morse Fourier productPair adjacent factors. If $u=|\cos (\pi t)|$, their modulus issince the maximum on $[0,1]$ occurs at $u=1/\sqrt{3}$. Thus $|S_j(\theta )|\ll 2^{\sigma j}$ uniformly, where $\sigma =\frac{1}{2}{\log }_{2}B=2-\frac{3}{4}{\log }_{2}3<1$.

Every integer interval $J\subset [0,N]$ is a disjoint union of aligned binary blocks with at most two blocks of each length. On such a block the digit concatenation identity and the Thue–Morse Fourier product give the same bound, up to a unit phase. Summing the geometric series proves the uniform interval cancellation for binary digit parityFor a fixed $m$, the sum ${\sum }_{n\in I_m}f(mn)$ is a sum over multiples of $m$ in an integer interval $J\subset [1,N]$. The additive character orthogonality filter givesIts modulus is $O(N^{\sigma })$, independently of $m$ and the interval. Summing at most $O(N^{1/100})$ outer values proves the small Type I sums for binary digit parity:This is smaller than $(\log N{)}^{-20}$ for sufficiently large $N$. It proves the required Type I cancellation; the substantially harder Type II cancellation is not needed for this final clause.

Put $S(\theta )={\sum }_{r=1}^{n}e(\theta r^3)$. Its modulus is the modulus of the Fourier transform in the question, independently of the sign convention. We use Hua's lemma in the cubic form ${\int }_0^1|S{|}^8{\ll }_{\delta }{n}^{5+\delta }$; the cubic eighth-moment proof by differencing establishes this from the subpower bound for the divisor function. Thereforeand $n\asymp N^{1/3}$ imply ${\sup }_m|S|{\gg }_{\delta }{n}^{1-\delta }$. Choose an actual $\theta \in m$ attaining at least half this bound; attainment of the supremum itself is unnecessary.

Fix $\epsilon >0$ and put ${\epsilon }_0=\min (\epsilon ,1/6)$. The Dirichlet approximation theorem with $Q=\lfloor N^{1-{\epsilon }_0}\rfloor$ gives coprime integers $a,q$ satisfyingThe cubic Weyl inequality, which is the quantitative equidistribution estimate needed here, saysCompare it with the lower bound. Choose $\delta ,\eta >0$ so small that $b=4(\delta +\eta )/3<{\epsilon }_0/2$. It follows thatBut $n^{-1}=O(N^{-1/3})$ and $q/n^3=O(N^{-{\epsilon }_0})$. Both are $o(N^{-b})$, so for large $N$ the first term must supply this lower bound. Consequently $q{\ll }_{\epsilon }{N}^b{\ll }_{\epsilon }{N}^{\epsilon }$, while the approximation above gives $\Vert q\theta \Vert \ll N^{{\epsilon }_0-1}\le N^{\epsilon -1}$. Enlarging the constants covers bounded $N$. ThusHere $\Vert \cdot \Vert$ is distance modulo one. A ninth moment of this size therefore forces at least one near-rational frequency, rather than merely a large pointwise sum somewhere outside $m$.

Put $d=\gcd (k,p-1)$ and write $S(a)={\sum }_{x\in {\mathbb{F}}_p}e(a{x}^k/p)=p{G}_{a,p}$. The multiplicative group of a finite field is cyclic, so on its nonzero elements the $k$th-power map has kernel of size $d$. For $y\ne 0$, character orthogonality consequently giveswhere the sum is over its multiplicative characters. Thus, for $a\ne 0$,The term from the trivial character is $-1$ and cancels the initial one.

For a nontrivial character, the prime-field character Gauss sum identity can be proved directly. Since $|\chi (z)|=1$ on nonzero elements, substituting $y=tz$ givesThe inner sum is $p-1$ for $t=1$ and $-1$ otherwise. Since ${\sum }_{t\ne 0}\chi (t)=0$, the result is $p$. The triangle inequality now proves the power Gauss sum over a prime field boundThis also includes $d=1$, when the nonzero-frequency sum vanishes.

For $x\in {\mathbb{F}}_p$, additive character orthogonality counts its representations as three powers:The zero-frequency term is $p^2$. Each other term has $|S(a)|\le k\sqrt{p}$, soIf $p>k^6$, this is less than $p^2$, giving $R(x)>0$ for every $x$. Hence $p>k^6$ is a sufficient threshold for the three power summands over a large prime field conclusion.

Let $A(x)$ count primes $p\le x$ for which $p+2$ is also prime. We prove $A(x)\ll x/{\log }^{2}x$ using a quadratic Selberg sieve, then apply Abel summation.

For $F(n)=n(n+2)$, each odd prime has exactly two roots modulo that prime. The Chinese remainder theorem gives the polynomial root density in a sievefor odd squarefree integers $d$. Put $R=x^{1/8}$ and choose the optimizing real Selberg sieve weights ${\lambda }_d$, supported on these $d\le R$, with ${\lambda }_1=1$. If $p,p+2$ are prime and $p>R$, their weight $({\sum }_{d\mid F(p)}{\lambda }_d{)}^2$ is one. It is nonnegative for every other integer. Expanding the square therefore givesThe Selberg sieve diagonalization makes the main quadratic form $1/J(R)$, whereThe optimal Selberg weights have modulus at most one. Since ${\rho }_F([d,e])\le [d,e]\le R^2$, the remainder is at most $O(R^4)$.

For completeness, the lower bound on $J$ is where the second logarithm enters. Restrict to primes $3\le p\le y=R^{1/8}$ and put $k(p)=2/(p-2)$. The full product $W={\prod }_{3\le p\le y}(1+k(p))$ is $\asymp {\log }^{2}y$, since its logarithm is $2{\sum }_{3\le p\le y}1/p+O(1)$ and the Mertens second theorem applies. Give the associated squarefree divisor $d$ probability $k(d)/W$. Prime inclusion probabilities are $2/p$, so the Mertens first theorem givesfor large $R$. The Markov inequality shows that at least half the weight has $d\le R$. This proves the truncated Euler-product lower bound $J(R)\gg W\gg {\log }^{2}R$. Consequently the twin-prime upper bound from a quadratic sieve isFinally, Abel summation givesThe tail is dominated by ${\int }_3^{\infty }dt/(t{\log }^{2}t)<\infty$. Thus reciprocal-sum convergence from a counting bound proves convergence of the first reciprocal sum. The second is smaller termwise. We have proved Brun's theorem:Counting each twin prime just once changes at most a finite repetition and gives the same conclusion.

Write $F(s)=-{\zeta }^{\prime }(s)/\zeta (s)$ and ${\psi }_{\Gamma }={\Gamma }^{\prime }/\Gamma$. The global partial-fraction expansion of the zeta logarithmic derivative isHere $\gamma$ is the Euler--Mascheroni constant, and the sum includes multiplicities of the Nontrivial zeros of the Riemann zeta function. The paired terms are locally absolutely convergent away from their poles, by the Riemann–von Mangoldt formula. This identity follows by differentiating the genus-one Hadamard factorization of the Riemann xi function and using the Gamma function recurrence.

We first prove the classical zero-free region of the Riemann zeta function. The Euler-product nonvanishing of the Riemann zeta function and its functional equation place every nontrivial zero in the closed strip $0\le \beta \le 1$; no assertion about zeros on its boundary is needed yet. The real logarithmic derivative of Riemann xi and the digamma function asymptotic imply, for $1<\sigma \le 2$ and $|t|\ge 1$,Every summand being subtracted is nonnegative. If $\beta +it$ is a zero, retaining its summand gives $\Re F(\sigma +it)\le C\log (|t|+2)-1/(\sigma -\beta )$; at height $2t$ the upper bound $C\log (|t|+2)$ suffices. At real $\sigma$ the simple pole of $\zeta$ gives $F(\sigma )=1/(\sigma -1)+O(1)$.

For $\sigma >1$, the Dirichlet series $F(s)={\sum }_n\Lambda (n)n^{-s}$ has nonnegative coefficients. The identity $3+4\cos u+\cos 2u=2(1+\cos u{)}^2\ge 0$ therefore gives the three-four-one zero-free-region argumentWith $L=\log (|t|+2)$, a zero at $\beta +it$ would consequently satisfyChoose $\sigma =1+a/L$, with an absolute $a>0$ sufficiently small, and put $c=a/8$. If $\beta \ge 1-c/L$, this inequality would imply $4/(a+c)\le 3/a+C$. But $4/(a+a/8)-3/a=5/(9a)>C$ for small enough $a$, a contradiction.

For any fixed $t\ne 0$, the same positivity inequality as $\sigma \downarrow 1$ excludes a zero at $1+it$: its negative contribution has coefficient at least four, whereas the real pole contributes only three. Any zero at $1+2it$ only strengthens the contradiction. The pole at $s=1$ has a zero-free punctured neighbourhood. By compactness, the remaining bounded-height portion of the line has a zero-free neighbourhood as well. Shrink $c$ to combine these facts with the large-height bound. Hencewith the understanding that $s=1$ is a pole.

The Riemann–von Mangoldt explicit formula for the Second Chebyshev function, with half weight at a prime-power endpoint, isThe zero sum uses symmetric height truncation. To estimate it, take a half-integer $x$ and use the truncated explicit formula for the second Chebyshev functionThe zero-free region gives $|x^{\rho }|\le x\exp (-c\log x/\log (T+2))$ for these zeros. The Riemann–von Mangoldt formula and partial summation give ${\sum }_{|\Im \rho |\le T}|\rho {|}^{-1}\ll {\log }^2(T+2)$. Choose $T=\exp (\sqrt{\log x})$. Both the zero sum and the truncation error are then $O(x{e}^{-c^{\prime }\sqrt{\log x}})$ after reducing the positive constant to absorb logarithmic factors. Replacing an arbitrary $X$ by $\lfloor X\rfloor +1/2$ preserves the Von Mangoldt function sum and changes the main term by at most one. This proves the requested form of the Prime number theorem:

Use $e(t)=e^{2\pi it}$ and the Fourier transform convention $\hat{f}(\xi )={\int }_{\mathbb{R}}f(x)e(-x\xi )dx$, initially for an integrable function. For the interval indicator function, direct integration givesThe integral bound is one, and the displayed numerator has modulus at most two. By the convolution theorem, the Fourier transform of the $m$-fold convolution is its $m$th power. Thus the Fourier decay of repeated interval convolutions givesAt zero, interpret the second term of the minimum as infinity.