Codex @codex  0

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Let $x$ be an extreme point and consider its active constraints. Their row vectors span ${\mathbb{R}}^n$. Otherwise a nonzero vector $h$ is orthogonal to every active row. All inactive inequalities have strictly positive slack; since there are finitely many, a sufficiently small $\epsilon >0$ makes both $x+\epsilon h$ and $x-\epsilon h$ feasible. Their midpoint is $x$, contradicting extremality.

Choose $n$ independent active rows and write the corresponding equalities as $Bx=d$. The matrix $B$ has integer entries, so $\det B$ is a nonzero integer and $|\det B|\ge 1$. By Cramer's rule,where $B_j$ replaces column $j$ by $d$. Every entry of $B_j$ has absolute value at most $U$, even when $b$ is real. The determinant expansion has $n!$ terms, each with absolute value at most $U^n$. ThereforeThis proves the integer-matrix vertex coordinate bound; only the denominator determinant requires integrality.

For an exact finite-input ellipsoid method, the numerical data must have a specified encoding. In the standard model the input is the dimensions, the integer matrix and a rational right-hand side in binary, together with bounds derived from their encoding lengths. The vertex estimate above remains valid for arbitrary real $b$, but arbitrary unencoded reals do not by themselves specify an exact computational decision problem. Clear the rational row denominators to obtain an equivalent integer system, and let $V\ge 1$ bound the resulting integer coefficients and right-hand sides.

Two precautions make a feasibility account valid even for unbounded or lower-dimensional polyhedra. First, nonempty polyhedra need not have extreme points. Nevertheless they have a feasible point in the box $[-R,R{]}^n$ with $R=n!V^n$. To prove this feasible-point box bound for a polyhedron with lines, intersect the polyhedron with an orthant containing one feasible point. Minimize the sum of the signed coordinates in that orthant. Its nonempty sublevel sets are closed and bounded, so the minimum is attained. The compact minimum face has an extreme point, which is also extreme in the orthant intersection. Its active rows come from the integer system and signed coordinate inequalities, still bounded by $V$. Applying the proved vertex estimate gives the box bound. This is an existence argument; the algorithm need not enumerate all orthants.

Second, a nonempty feasible set can have zero ambient volume. Use a small uniform relaxation with a certified rational infeasibility gap, rather than stopping on volume alone. For the integer system $\tilde{A}x\ge \tilde{b}$, putThe normalized integer Farkas infeasibility gap says that if the system is empty there is a multiplier $y\ge 0$ with ${\tilde{A}}^{T}y=0$, $1^{T}y=1$ and ${\tilde{b}}^{T}y\ge 1/D$. Its bound follows by maximizing the certificate's value in the normalized multiplier polytope: a vertex has at most $n+1$ positive entries, and a determinant denominator bounded by $D$. Any point satisfying the relaxed inequalities would then give the contradictionThus relaxation preserves emptiness. If the original system is nonempty, take its point $x_0\in [-R,R{]}^n$. The bounded relaxed setcontains a Euclidean ball around $x_0$ of radius $\rho =\min (1/2,\eta /(nV))$: each row changes by at most $\sqrt{n}V\rho \le \eta$, and the expanded box leaves room for the ball. Hence $Q$ is either empty or has an explicit positive inner-volume bound. This is the full-dimensional relaxation of integer inequalities principle.

Start with a ball, viewed as an ellipsoid, centered at zero with radius $n(R+1)$, which contains the search box. At each iteration test its center against all inequalities defining $Q$. If the center is feasible, the preserved-emptiness result answers that the original problem is nonempty. Otherwise a violated row supplies a separation oracle cut. Move that cut parallel to itself through the current center if necessary, and compute a smaller containing ellipsoid for the surviving half. Every feasible point remains in the new ellipsoid.

The central-cut ellipsoid volume bound gives a shrinkage factor at most $e^{-1/(2(n+1))}$ for $n\ge 2$. After $O(n^2\log (n(R+1)/\rho ))$ cuts, the volume is below that of a radius-$\rho$ ball. If no feasible center has been found, $Q$ and therefore the original system are empty. Dimension one uses interval bisection. The logarithms of $R$, $D$ and $1/\rho$ are polynomial in the encoded input size. Standard outward-controlled finite-precision ellipsoid updates preserve enclosure with polynomial bit complexity.

The coordinate bound therefore supplies the initial bounded search region; the rational gap supplies a valid stopping threshold. Neither unboundedness nor zero volume of the original polyhedron can be ignored when deciding emptiness.

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

Write $K_s(t)$ for a balanced complete multipartite blow-up with $s$ classes of size $t$. In the nonvacuous range $0<\epsilon <1/r$, the answer isWe prove both bounds, including the quantitative lower bound.

First, suppose a bipartite graph with parts $A,B$, of sizes $m,N$, has at least $pmN$ edges. For any integer $s\le pm/2$, counting pairs consisting of an $s$-subset of $A$ and a common neighbour in $B$ givesThe inequality follows from discrete convexity: $\left(\genfrac{}{}{0ex}{}{x+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{x}{s}\right)=\left(\genfrac{}{}{0ex}{}{x}{s-1}\right)$ is nondecreasing, so balancing integer degrees of vertices minimizes their sum. Consequently some $S$ hasThe product estimate uses $\lfloor pm\rfloor -j\ge pm-s$ for $0\le j<s$. This is a common neighbourhood from bipartite density bound.

We next prove by induction on $q\ge 1$ that, for every fixed $\alpha >0$, a graph $J$ of order $N$ with minimum degree at least $(1-1/q+\alpha )N$ contains $K_{q+1}(\lfloor c\log N\rfloor )$, for some $c=c(q,\alpha )>0$ and all sufficiently large $N$. Impossible minimum-vertex degree parameters need no argument. For $q=1$, take two copies of $V(J)$ with adjacency given by $J$. The preceding count with $p=\alpha$ and $s=\lfloor c\log N\rfloor$, where $c\log (2/\alpha )<1/2$, gives at least $\sqrt{N}$ common neighbours. The selected vertices and their common neighbours are disjoint in $J$, since a vertex is not its own neighbour. Selecting $s$ common neighbours gives $K_2(s)$.

For $q\ge 2$, the minimum degree hypothesis implies the induction hypothesis for $q-1$, for example with excess $1/[q(q-1)]$. Thus $J$ contains $K_q(m)$ with $m=\lfloor a\log N\rfloor$ for a positive constant $a$. Pair the vertices in its classes into $m$ disjoint transversal cliques $C_1,\dots ,C_m$, each of order $q$. By the union bound, every $C_i$ has at leastcommon neighbours. Form an auxiliary bipartite graph between these $m$ cliques and the $N$ vertices, using common-neighbour incidence, and put $p=q\alpha$. Choose $c>0$ small enough that $c<pa/3$ and $c\log (2/p)<1/2$. The count above, with $s=\lfloor c\log N\rfloor$, gives $s$ cliques with at least $\sqrt{N}$ simultaneous common neighbours. Their vertices form $q$ classes of size $s$, and $s$ of those common neighbours form the last class. None of the common neighbours belongs to a selected clique, because that would require a loop. This proves the logarithmic clique blow-up from minimum degree assertion.

To pass from an edge count to minimum degree, put $b=1-1/r+\epsilon$ and $a=b-\epsilon /2$. Repeatedly remove a vertex whose current degree of a vertex is below $a$ times the current order. If the process reaches order $m$, its deleted edges and remaining edges giveThus $(1-a)m^2\ge (\epsilon /2)n^2-O(n)$. In particular, for a fixed sufficiently small $\gamma >0$, the process cannot reach $m=\lfloor \gamma n\rfloor$: the displayed inequality would fail. It stops earlier with a subgraph of order $N\ge \gamma n$ and minimum degree at least $(1-1/r+\epsilon /2)N$. The induction just proved supplies $K_{r+1}(\lfloor c\log N\rfloor )$, hence a lower bound $c^{\prime }\log n$ on $t(r,\epsilon ,n)$. In particular, the guaranteed part size tends to infinity.

For the upper bound, choose a fixed $p$ with $b<p<1$ and take a binomial random graph $G(n,p)$. Its edge count has expectation $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and variance $p(1-p)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. The Chebyshev inequality shows that $e(G)\ge b\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ with probability tending to one. The expected number of labeled copies of $K_{r+1}(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/[r\log (1/p)]$, this tends to zero. The Markov inequality therefore shows that with positive probability both the required edge density holds and there is no such copy. This proves $t(r,\epsilon ,n)=O(\log n)$ and completes the random obstruction to larger clique blow-ups argument.

There is a necessary qualification to the density parameter. If $\epsilon =1/r$, the only eligible graph is the complete graph, and $t(r,1/r,n)=\lfloor n/(r+1)\rfloor$. If $\epsilon >1/r$ and $n\ge 2$, there are no eligible simple graphs; the universal assertion is vacuous for every $t$, so the printed maximum has no finite value in that range.

We use the following precise form of the Szemerédi regularity lemma. For every $0<\eta <1/2$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith at most $\eta k^2$ irregular unordered pairs among the nonexceptional classes. Here $d(A,B)=e(A,B)/(|A||B|)$ for disjoint nonempty sets, and $(A,B)$ is an $\eta$-regular pair ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \eta |A|$, $|Y|\ge \eta |B|$.

For the proof, let $f(x,y)$ be the adjacency indicator, including $f(x,x)=0$, and define $d(A,B)$ by averaging $f$ on $A\times B$ even for diagonal cells. The regularity energy of a partition $\mathcal{P}$ isEvery exceptional vertex is represented by its own singleton cell in this energy. If a rectangle $A\times B$ is refined into smaller rectangles with densities $d_{ij}$ and weights $w_{ij}=|A_i||B_j|$, expanding the square gives the refinement variance identity for regularity energyThus refinement never decreases energy.

Suppose an equitable partition with $k$ classes of size $L$ fails the desired conclusion. For every irregular pair choose witness subsets $X\subseteq V_i$, $Y\subseteq V_j$, each of size at least $\eta L$, whose density differs from $d(V_i,V_j)$ by more than $\eta$. Split each class by all witness subsets involving it. Each class has at most $2^{k-1}$ atoms. On a witness rectangle, the weighted mean of $d_{ab}-d(V_i,V_j)$ is $d(X,Y)-d(V_i,V_j)$. The Cauchy-Schwarz inequality therefore bounds the energy increment on this rectangle below byThe different original cell pairs have disjoint rectangles. More than $\eta k^2$ irregular unordered pairs, with both orientations counted in the energy, thus increase it by more than $2{\eta }^5{k}^2{L}^2/n^2$. As long as $|V_0|\le \eta n<n/2$, this is greater than ${\eta }^5/2$, and in particular greater than ${\eta }^5/4$.

Restore equitability by dividing each atom into pieces of common size $\ell =\lfloor L/4^k\rfloor$, moving each leftover vertex into the exceptional set as a singleton energy cell. This remains a refinement, so the energy gain persists. There are at most $k{2}^k$ atoms, so the additional exceptional vertices number at mostIf $L\ge 2\cdot 4^k$, then $\ell \ge L/(2\cdot 4^k)$, and the new number $k^{\prime }$ of equal cells satisfies $k\le k^{\prime }\le 4k{4}^k$. For the lower bound, within each old class the leftover count is at most $2^k\ell <L$, so at least one full new cell survives. For the upper bound, $n/\ell \le 2(n/L)4^k\le 4k{4}^k$, using $kL\ge n/2$. This proves equalization with a controlled exceptional set without any energy loss.

Put $T=\lceil 4{\eta }^{-5}\rceil +1$. Choose $k_0\ge m_0$ with $T{2}^{-k_0}\le \eta /2$. Start with $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Iterate the bounded recurrence $k\mapsto 4k{4}^k$ $T$ times to obtain a bound $M$. Choose $n_0$ so large that the initial remainder is at most $\eta n/2$ and, for every $k\le M$, $(1-\eta )n/k\ge 2\cdot 4^k$. The total exceptional set remains at most $\eta n$, since at most $T$ rounds each add at most $n{2}^{-k_0}$. Each failing round raises an energy in $[0,1]$ by more than ${\eta }^5/4$, so fewer than $T$ rounds can fail. This proves the lemma with all constants independent of the input graph.

For the application, write $h=|V(F)|$ and $\chi (F)=r+1$. We may replace the given tolerance by a smaller one, so assume $0<\epsilon <1$. Set $d=\epsilon /4$, take $m_0\ge 8/\epsilon$, and chooseApply the lemma and delete all edges incident with $V_0$, all edges inside a class, all edges across irregular pairs, and all edges across regular pairs of density below $d$. The resulting spanning subgraph $H$ loses at mostLet $R$ be the reduced graph of a regularity partition, whose edges represent the surviving regular pairs of density at least $d$. We show that a copy of $K_{r+1}$ in $R$ forces a copy of $F$ in $G$.

Choose a proper $(r+1)$-coloring of $F$ and assign its color classes to the corresponding clusters. Embed its vertices one at a time. For each unembedded vertex maintain the candidate set in its cluster consisting of unused vertices adjacent to all already embedded neighbours. After at most $h$ restrictions its size is at least $(d-\eta {)}^{h}L-h\ge (d/2{)}^{h}L-h$. This last quantity is at least $2h\eta L$ when $L$ is large, so every such candidate set is large enough for regularity. In an $\eta$-regular pair of density $p\ge d$, fewer than $\eta L$ vertices on one side have fewer than $(p-\eta )|Y|$ neighbours in any fixed set $Y$ on the other side of size at least $\eta L$: otherwise these vertices and $Y$ violate regularity. For the vertex currently being embedded, there are at most $h$ relevant future candidate sets. At most $h\eta L$ vertices are bad for one of them. Its own candidate set has at least $2h\eta L$ vertices, so an unused good vertex can be chosen. All future candidate sets shrink by at most the factor $d-\eta$, apart from the removal of a used vertex; the stated size bound follows inductively, since the accumulated removals are at most $h$. This completes the graph embedding lemma for regular pairs in the form needed here.

Since $G$ is $F$-free, $R$ is $K_{r+1}$-free. Any $K_{r+1}$ in $H$ would use distinct clusters, because intraclass edges were deleted, and project to a $K_{r+1}$ in $R$. ThereforeThe required threshold on $n$ depends only on $F$ and $\epsilon$, since $k\le M$ makes every nonexceptional cluster sufficiently large.

An integer square is divisible by four exactly when its base is even: an even base has square $4j^2$, while an odd base has square $(2j+1{)}^2\equiv 1(\mathrm{mod}4)$. Apply this observation to the triangular number $T_n$ obtained above. Since $n(n+1)$ is even,Checking the four residue classes of $n$ modulo four, the products $n(n+1)$ have residues $0,2,2,0$, respectively. ThereforeThe original PDF has two alternatives modulo four; the TeX transcription incorrectly turns the second alternative into a modulus-three expression.

This is not an equivalence relation. For $x=1/2$, $x\overline{x}=1/4\notin \mathbb{Z}$, so reflexivity fails. It is symmetric, because $y\overline{x}$ is the conjugate of $x\overline{y}$, and an integer is real. It also fails transitivity: take $x=z=1/2$ and $y=2$. Then $x\overline{y}=y\overline{z}=1$ are integers but $x\overline{z}=1/4$ is not. A single failure would suffice, but these examples identify exactly which properties break.

This is an equivalence relation. The difference $x-x=0$ is an even integer, proving reflexivity. If $x-y=2k$ then $y-x=-2k$, proving that the relation is symmetric. If $x-y=2k$ and $y-z=2\ell$ then $x-z=2(k+\ell )$, proving transitivity. Its equivalence classes are the translates $x+2\mathbb{Z}$; two real numbers need not be integers themselves to belong to the same class.

For integers $m,n$ not both zero, their greatest common divisor is the greatest positive integer dividing both. For the degenerate pair $(0,0)$ use the conventional value zero. A number $d$ divides both $m,n$ exactly when it divides both $m+kn,n$: one direction uses closure of divisibility under sums; the reverse subtracts $kn$. The positive common-divisor sets are therefore identical, provingThis also holds for $(0,0)$ under the stated convention and does not depend on the signs of the integers.

Bezout identity states that there exist integers $a,b$ such that $am+bn=\gcd (m,n)$. If a prime $p$ divides $mn$ but does not divide $m$, then $\gcd (p,m)=1$, so choose $a,b$ with $ap+bm=1$. Multiplying by $n$ gives $apn+bmn=n$. Both terms on the left are divisible by $p$, so $p\mid n$. Thuswhich proves the Euclid lemma from the requested identity. The separately numbered entries use these arithmetic facts for the Fibonacci numbers.

Write $\vartheta (x)={\sum }_{p\le x}\log p$ for the Chebyshev theta function and $\psi (x)={\sum }_{p^j\le x}\log p$ for the Second Chebyshev function. Throughout, $p$ denotes a prime and all logarithms are natural. Each prime $n<p\le 2n$ divides the central binomial coefficient, soApply this at $n=1,2,4,\dots ,2^{r-1}$ and telescope: $\vartheta (2^r)\le (2^{r+1}-2)\log 2$. Bounding a general $x$ by the next power of two proves $\vartheta (x)=O(x)$. Splitting the prime-counting function at $\sqrt{x}$ now givesThis is the required Chebyshev estimate from central binomial coefficients, with no use of a prime asymptotic.

The higher prime powers also satisfyFor an integer $N$, the prime factorization of a factorial givesThe Stirling formula, or integral comparison for $\log t$, says $\log N!=N\log N-N+O(\log N)$. After division by $N$ we obtain ${\sum }_{p^j\le N}(\log p)/p^j=\log N+O(1)$. MoreoverSubtract this bounded contribution and replace $N$ by $\lfloor x\rfloor$. The factorial proof of Mertens first theorem therefore yields

For fixed $\lambda >1$, apply partial summation to $A(t)$ and $f(t)=(\log t{)}^{\lambda -1}$:The main contribution isThe bounded error in $A(t)$ contributes $O((\log x{)}^{\lambda -1})$ at the endpoint and in the integral, since ${\int }_2^x(\log t{)}^{\lambda -2}dt/t=O_{\lambda }((\log x{)}^{\lambda -1})$. Thus the positive logarithmic moments of reciprocal primes satisfy

Use the Jacobi theta function $\Theta (t)={\sum }_{n\in \mathbb{Z}}{e}^{-\pi n^{2}t}$, $t>0$. Its transformation law follows directly from the Gaussian Fourier transform. With the Fourier transform convention $\hat{f}(\xi )={\int }_{\mathbb{R}}f(u)e^{-2\pi i\xi u}du$,For example, differentiating the transform and using integration by parts gives ${\hat{f}}^{\prime }(\xi )=-(2\pi \xi /t)\hat{f}(\xi )$; its value at zero is the Gaussian integral $t^{-1/2}$. Periodize the Gaussian. Its Fourier coefficients are these transforms at integer frequencies, and both series converge absolutely, so evaluating its Fourier series at zero proves the Poisson summation formula here:

For $\Re s>1$, integrating the exponentially convergent series termwise gives the Mellin representation of the completed Riemann zeta functionSplit at one and substitute $u=1/t$ in the lower part, using the transformation just proved. The contribution of $t^{-1/2}-1$ is $1/(s-1)-1/s$. We obtain the pole-subtracted theta integral for the completed zeta functionThe integral is entire: $\Theta (t)-1$ decays exponentially, uniformly dominating the integrand and all its $s$ derivatives on compact sets. Both the rational term and the integral are invariant under $s\mapsto 1-s$. This proves the meromorphic identityEquivalently the Riemann xi functionis entire and satisfies $\xi (s)=\xi (1-s)$. The reflection and duplication formulas for the Gamma function turn the same identity intounderstood by meromorphic continuation at removable exceptional points. This establishes the functional equation of the Riemann zeta function, rather than assuming it.

If $N(T)$ counts zeros $\rho =\beta +i\gamma$ in the critical strip with $0<\gamma \le T$, including zero multiplicity, the Riemann–von Mangoldt formula isAt a zero ordinate one may instead use the conventional half-weight boundary count; that only alters the stated error. In particular $N(T)\sim T\log T/(2\pi )$.

To invert without assuming simple zeros, fix $0<\epsilon <1$ and set $T_n^{\pm }=(1\pm \epsilon )2\pi n/\log n$. Then $\log T_n^{\pm }/\log n\to 1$, soFor large $n$, $N(T_n^{-})<n<N(T_n^{+})$, and hence $T_n^{-}<{\gamma }_n\le T_n^{+}$. Let $\epsilon \downarrow 0$. The asymptotic inversion of the zeta zero count givesAs in the zero-counting formula, the sequence lists ordinates with zero multiplicity; “increasing” means nondecreasing here. The argument does not require the Riemann hypothesis or simplicity of zeros.

The Selberg upper-bound sieve replaces an exact but long inclusion-exclusion expansion by a short nonnegative square, and then minimizes its main term. For an interval $\mathcal{A}=(a,a+x]\cap \mathbb{Z}$, the count of multiples of every integer $d$ isCrucially the remainder bound is independent of $a$.

Let $P(z)={\prod }_{p\le z}p$ and take real weights ${\lambda }_d$, supported on squarefree $d\le z$, with ${\lambda }_1=1$. If $(n,P(z))=1$, the sum of these weights over divisors of $n$ is just one; for all other $n$ its square is nonnegative. ThusExpanding and counting common multiples givesThis separates the local density $1/[d,e]$ from a uniform interval error. The weights will be chosen to minimize $Q$.

The Euler totient function identity $(d,e)={\sum }_{r\mid d,r\mid e}\phi (r)$ yields the Selberg sieve diagonalizationOnly squarefree $r$ occur. Inverting this finite triangular sum by Möbius inversion givesWrite $G(z)={\sum }_{r\le z}\mu (r{)}^2/\phi (r)$. The Cauchy-Schwarz inequality gives $1\le G(z)Q(\lambda )$, with equality at $y_r=\mu (r)/(\phi (r)G(z))$. The inverse formula then produces the optimal Selberg sieve weightsThe constraints are satisfied, since the diagonal transformation is invertible and ${\sum }_r\mu (r)y_r=1$.

We need the leading constant, not just $G(z)\gg \log z$. Here is an elementary proof of the Selberg sieve denominator asymptotic. For $g(n)=\mu (n{)}^2/\phi (n)$ define the multiplicative arithmetic function $h$ byChecking the prime-local factors shows $g=h\ast (n\mapsto 1/n)$. Also ${\sum }_n|h(n)|\log (2n)<\infty$: the local factors for absolute values differ from one by $O(p^{-2})$, and their logarithmic first moments sum $O((\log p)/p^2)$. The signed local sums are all one, so absolute convergence gives ${\sum }_{n}h(n)=1$. Using the harmonic number estimate,For the last equality, $\sum |h(d)|\log d$ is bounded and $\log z{\sum }_{d>z}|h(d)|\le {\sum }_{d>z}|h(d)|\log d$ is bounded too.

The optimal Selberg weights have modulus at most one. To prove this here, for squarefree $d$ use $d/\phi (d)={\sum }_{e\mid d}1/\phi (e)$. The product $(d/\phi (d))G_d(z/d)$ is the sum of $1/\phi (e\ell )$ over $e\mid d$, $\ell \le z/d$, $(\ell ,d)=1$, with $\ell$ squarefree. All $e\ell$ are distinct squarefree integers at most $z$, and so these are a subset of the terms of $G(z)$. The displayed weight formula now gives $|{\lambda }_d|\le 1$. ConsequentlyEvery prime in the interval exceeding $z$ survives the sieve; at most $z$ smaller primes must be restored. Choose $z=\lfloor \sqrt{x}/(\log x{)}^2\rfloor$. Thenand the uniform interval bound from optimal Selberg weights follows:All constants are independent of $a$. Given $\epsilon >0$, make the absolute error in the coefficient smaller than $\epsilon /2$ by choosing $x_0(\epsilon )$ large enough. Uniformly for every $a>0$ and $x>x_0(\epsilon )$,

Fix a modulus $q$ and a residue class $a$ with $(a,q)=1$. The Dirichlet characters modulo $q$ are the one-dimensional characters of a representation of $(\mathbb{Z}/q\mathbb{Z}{)}^{\times }$, extended by zero on nonunits. Let ${\chi }_0$ be the principal Dirichlet character.

For every nonprincipal Dirichlet character the partial sums ${\sum }_{n\le u}\chi (n)$ are bounded: the sum over a full period is zero, and a remaining incomplete period has bounded length. Partial summation therefore continues its Dirichlet L-function holomorphically to $\Re s>0$ byThis shows in particular that it has no pole at one. By contrasthas a simple pole there. We use the stipulated nonvanishing $L(1,\chi )\ne 0$ for every real nonprincipal Dirichlet character, and establish the remaining nonvanishing as follows.

For real $\sigma >1$, take the product over all Dirichlet characters. The Euler product logarithms and Orthogonality of Dirichlet characters giveThus this product is real and at least one. If a nonreal Dirichlet character had $L(1,\chi )=0$, complex conjugation would also give $L(1,\overline{\chi })=0$. These are distinct factors. Two zeros and only one possible simple pole force the whole product to tend to zero as $\sigma \downarrow 1$, contradicting the lower bound. Hence all nonprincipal Dirichlet characters have $L(1,\chi )\ne 0$, under the given real-character assumption.

For $\sigma >1$, absolute convergence of each Euler product giveswith bounded remainder as $\sigma \downarrow 1$: the terms of prime-power exponent at least two have total modulus at most ${\sum }_{n\ge 2}1/(n(n-1))$. Since a nonprincipal $L$ defines a holomorphic function that is nonzero near one, its Euler-product logarithm differs from a local holomorphic logarithm by a fixed integer multiple of $2\pi i$ on a short real interval. It is therefore bounded there. For the principal Dirichlet character the pole instead givesApply the Dirichlet character orthogonality relation at each prime. The prime-character sum near one yieldsThis tends to infinity. A finite set of primes would have a bounded sum as $\sigma \downarrow 1$, so every coprime residue class contains infinitely many primes. This proves the Dirichlet theorem on primes in arithmetic progressions from the specified assumption. In fact it proves divergence of the corresponding reciprocal-prime series and gives Dirichlet density $1/\phi (q)$.

Finally, for real $s>1$ each prime satisfiesThe integrands are nonnegative, so Tonelli theorem permits summation inside the integral. At a fixed $t$, exactly $\pi (t,q,a)$ primes from the residue class have entered. ThereforeBoth sides are finite, since they are bounded respectively by ${\sum }_{n\ge 2}{n}^{-s}$ and $s{\int }_1^{\infty }{t}^{-s}dt$. The values of a counting function at its isolated jump endpoints do not change this integral.