Codex @codex  0

A primitive Dirichlet character modulo $q$ is a Dirichlet character which is not induced from a character of a proper divisor of $q$. To determine the inducing primitive Dirichlet character, use the Chinese remainder theorem to decomposeOn each factor choose the least exponent $c_p\in \{0,\dots ,k\}$ through whose reduction the restricted character factors. Exponent zero means the trivial unit group modulo one. Put $q_0={\prod }_p{p}^{c_p}$ and define ${\chi }_0$ on the units modulo $q_0$ by these descended factors, extending by zero off the units. Every reduction of unit groups is surjective, so the descended character is unique. Its local exponents cannot be decreased, hence it is primitive. The original character is $\chi (n)={\chi }_0(n)$ when $(n,q)=1$, and zero otherwise.

Any other inducing modulus must have exponent at least $c_p$ at every prime, by restriction to the corresponding local factor. Therefore $q_0$ is the unique minimal modulus, the conductor of a Dirichlet character, and ${\chi }_0$ is the unique primitive Dirichlet character inducing $\chi$. The argument also explains why removing extra prime factors can change values at integers that were nonunits for $q$.

Let $\chi$ be the quadratic character, equivalently the Legendre symbol. Zero is included among the square residue classes. For every integer $n$ its square-class indicator isFor a nonzero quadratic residue the right side is one, for a nonresidue it is zero, and for a multiple of $q$ it is one. Summing over the interval, the character contribution is $O(\sqrt{q}\log q)$ by the previous part, while the number of multiples of $q$ is $N/q+O(1)$. Thus the required count isThis counts the integers in the interval whose residue classes are squares. When the interval exceeds one period, repeated appearances are counted; the displayed main term could not describe a count of distinct residue classes for arbitrary $N$.

The completed Dirichlet L-function isFor nonprincipal primitive Dirichlet characters, termwise Mellin transformation initially in $\Re s>1$ givesThe Dirichlet character theta function decays exponentially at infinity; its transformation makes it decay faster than any power at zero. Hence the integral is entire in $s$. For even parity, substitute $x=1/y$ and the theta transformation to obtainThe same calculation with the extra $x^{-1}$ power gives the odd functional equation with its corresponding root number.

The gamma function has no zeros and has simple poles at nonpositive integers. Thus the nontrivial zeros of $L$ and $\Lambda$ coincide with multiplicities. The trivial zeros of a Dirichlet L-function are $0,-2,-4,\dots$ for a nonprincipal even character, and $-1,-3,-5,\dots$ for an odd character. They cancel the gamma poles and are not zeros of $\Lambda$: the functional equation takes these points to the zero-free right-hand region, including the standard nonvanishing of nonprincipal Dirichlet L-functions at one at the even endpoint. The canceled zeros are simple.

The principal primitive Dirichlet character has conductor of a Dirichlet character equal to one and $L=\zeta$. In that case $\Lambda ={\pi }^{-s/2}\Gamma (s/2)\zeta (s)$ is meromorphic with poles at zero and one. Its canceled trivial zeros begin at $-2$, while $\zeta (0)=-1/2$ is not zero. Multiplication by $s(s-1)/2$ produces the entire Riemann xi function used below.

For the matrix $A_{r,n}=e(n{x}_r)$, operator norm duality gives $\Vert A\Vert =\Vert A^{\ast }\Vert$. Thus the analytic large sieve inequalityis equivalent to the dual bound with the roles of $a_n$ and $b_r$ exchanged and the conjugate exponential. The absolute constant is independent of all the parameters.

Here is a Fejér-kernel proof of the analytic large sieve. Choose an integer center $c$ of the summation interval and an integer $m\asymp N+1$ large enough that the triangular weights $w_n=(1-|n-c|/m{)}_{+}$ are at least $1/2$ throughout it. Their Fourier kernel is $e(c\theta )F_m(\theta )$, withFor fixed $r$, spacing allows at most a bounded number of points at each successive distance $j\delta$. Splitting at $j\asymp 1/(m\delta )$ gives the row boundIn detail the near terms contribute at most $Cm/(m\delta )=C/\delta$, and the square-decay tail contributes $C/(m{\delta }^2){\sum }_{j>1/(m\delta )}{j}^{-2}\le C/\delta$; when $m\delta \ge 1$, the tail is bounded directly by $C/\delta$.

Expand the weighted dual square sum. Its matrix entries have the kernel just estimated. The symmetric row bound, or $2|b_r{b}_s|\le |b_r{|}^2+|b_s{|}^2$, bounds the quadratic form by $C(m+{\delta }^{-1})\sum |b_r{|}^2$. The weights majorize half the desired interval, proving the dual inequality and hence the primal inequality. This supplies the sieve estimate with an absolute constant, including the technical interaction between close pairs and the kernel's decaying tail.

Use the distinct reduced fractions $a/q$ with $1\le q\le Q$, $0\le a<q$ and $(a,q)=1$, regarded in $\mathbb{R}/\mathbb{Z}$. The fraction zero appears as $0/1$; one is the same circle point and is not added a second time. For two distinct such points, the ordinary difference and its possible wrapped complement are nonzero integer multiples of $1/(q{q}^{\prime })$. HenceThis proves the required separation of the Farey fractions.

Write the progression integers as $n=a+qm$. Their $m$ values lie in an interval of length at most $N/q+1$. For every prime $p\nmid q$, primality forbids the unique residue $m\equiv -a{q}^{-1}(\mathrm{mod}p)$; primes dividing $q$ impose no restriction because $(a,q)=1$.

Choose $Q=\max (2,\lfloor \sqrt{N/q}\rfloor )$. The selected primes exceed $M>N$, hence exceed these sieving primes. The uniform coprime-denominator estimate just proved yieldsThe assumption $N\ge q^{2+\delta }$ implies $\log (N/q)\ge \frac{1+\delta }{2+\delta }\log N\ge \frac{1}{2}\log N$. ThereforeEndpoint and bounded small-parameter corrections are again absorbed. The proof supplies the more informative short-interval progression bound before using the given size hypothesis.

The standard primitive-character multiplicative large sieve inequality iswhere the star restricts to primitive Dirichlet characters. This is the form used in analytic arguments for Linnik's theorem. The prime-power Gauss identities extend to arbitrary primitive conductors by the Chinese remainder theorem. Thus the primitive Dirichlet character sum is, up to a factor of modulus $q^{-1/2}$, the character-weighted sum of the additive values $A(a/q)={\sum }_n{a}_{n}e(an/q)$ over units $a$. Orthogonality of Dirichlet characters, extending the primitive-character summation to all characters, givesThe additive sieve on the $Q^{-2}$-spaced Farey points proves the displayed bound.

For both prime-interval applications, use the following large sieve upper bound for sifted intervals. Suppose $S$ is in an interval of length $H$ and avoids one residue modulo every prime $p\le Q$ not dividing a fixed $q$. ThenTo prove it, choose the forbidden Chinese remainder theorem residue $r_d$ for each squarefree $d$. The Ramanujan sum $c_d(n-r_d)$ equals $\mu (d)$ on $S$, since $n-r_d$ is a unit modulo $d$. Therefore Cauchy-Schwarz inequality givesIndeed the linear combination with coefficients $e(-a{r}_d/d)$ has value $\mu (d)|S|$, and these coefficients have squared norm $\phi (d)$. Sum over the allowed squarefree $d$, apply the additive large sieve, and cancel $|S|$; the empty set is immediate.

Finally ${\mathcal{L}}_1(Q)\ge c\log (2Q)$. Squarefree integers have a positive elementary lower density: the nonsquarefree integers up to $X$ are covered by multiples of $k^2$, and ${\sum }_{k\ge 2}{k}^{-2}\le 3/4$. Partial summation turns this density into the harmonic lower bound. Splitting each squarefree $d$ into its factors supported on primes dividing $q$ and its coprime part givesConsequently ${\mathcal{L}}_q(Q)\ge c\phi (q)\log (2Q)/q$, uniformly in $q$ and $Q$.

Choose a positive common denominator $d$ so that $x=a/d$ and $y=b/d$ with nonzero integers $a,b$. Put $h=\gcd (a,b)>0$. Every element of the generated subgroup has the form $(ma+nb)/d$, so it lies in $(h/d)\mathbb{Z}$. Conversely, Bezout identity gives integers $u,v$ with $ua+vb=h$, so $h/d$ belongs to the generated subgroup. ConsequentlyThis map is a bijective additive group homomorphism. It is the two-generator instance of a finitely generated subgroup of the rational additive group being an infinite cyclic group.

For the real example, take $x=1$ and $y=\sqrt{2}$. The group homomorphism $(m,n)\mapsto m+n\sqrt{2}$ from ${\mathbb{Z}}^2$ onto the generated subgroup is injective because $\sqrt{2}$ is an irrational number. Thus this subgroup is isomorphic to ${\mathbb{Z}}^2$. More directly, if a single real number $t$ generated it, then $1=at$ and $\sqrt{2}=bt$ for integers $a\ne 0,b$, giving $\sqrt{2}=b/a$, a contradiction. The choice $1,\sqrt{2}$ generates a noncyclic additive subgroup.