Character sums over products of prime polynomials
Samuel Porritt
math.NT

Robust Least Squares for Quantized Data Matrices
    Richard Clancycor1
    December 30, 2023
================================================




We study sums of Dirichlet characters over polynomials in 𝔽_q[t] with a prescribed number of irreducible factors. Our main results are explicit formulae for these sums in terms of zeros of Dirichlet L-functions. We also exhibit new phenomena concerning Chebyshev-type biases of such sums when the number of irreducible factors is very large.





§ INTRODUCTION



 §.§ Set-up

Let 𝔽_q[t] be the polynomial ring in one variable over the finite field 𝔽_q and ℳ, 𝒫 be the subsets of monic and prime monic polynomials, respectively. Let ℳ_n be the set of monic polynomials of degree n. This paper concerns the sums of non-trivial Dirichlet characters χ : 𝔽_q[t] →ℂ

    π_k(n,χ)=∑_f ∈ℳ_n 
    Ω(f)=k χ(f),

where Ω(f) is the number of prime divisors of f counted with multiplicity. We shall use analytic arguments to relate the quantity π_k(n,χ) to the zeros of L(u,χ), the L-function associated to χ, which is defined as 
    L(u,χ):=∑_f ∈ℳχ(f)u^ f = ∏_p ∈𝒫(1-χ(p)u^ p)^-1.

It is known that the analogue of the Riemann hypotheis holds for such L-functions and in particular, using the same notation as <cit.>, we can factor the polynomial L(u,χ) as a product of linear factors

    L(u,χ)=:(1-√(q)u)^m_+(1+√(q)u)^m_-∏_j=1^d_χ(1-α_j(χ)u)^m_j∏_j'=1^d'_χ(1-β_j'(χ)u)

where |β_j'(χ)|=1 and α_j(χ) = √(q)e^iγ_j(χ) is non-real and has absolute value √(q). See for example, <cit.>. The α_j are distinct for distinct j and appear with multiplicity m_j. For our purposes, the β_j' are less important. We are interested in uniformity with respect to the variables n and k so, everywhere apart from equation (2) below, implied constants may depend on anything except n and k (in particular, on χ and q). It is convenient to use the normalisation

    π_k(n,χ):=π_k(n,χ)n(k-1)!(-1)^k/q^n/2(log n)^k-1.




 §.§ Brief background on Chebyshev's bias

Assume for the time being that L(± q^-1/2,χ) ≠ 0 and that each zero of L(u, χ) is simple. The corresponding assumption, that L(1/2,χ) ≠ 0 and all zeros are simple, is conjectured to hold for all number field Dirichlet L-functions. Then it follows from the work of Devin and Meng <cit.>, and Theorems <ref> and <ref> below, that for each fixed k,

    π_k(n,χ) = 1_χ^2 = χ_01+(-1)^n/2^k+∑_γ_j ≠ 0, πe^i n γ_j +O_k(1/log n).

The terms in this formula corresponding to non-real zeros of L(u,χ) oscillate around 0 as n increases. We can think of the other term as a `bias' term which biases π_k(n,χ) away from 0. It follows that, if χ is real then for each fixed k, the quantity (-1)^kπ_k(n,χ) is biased towards being positive rather than negative, but that “as
k increases, the biases become smaller and smaller"–<cit.>. The results of this paper include and generalise (2) to k(n) varying with n. We shall see that the bias term does indeed tend to 0 for certain sequences k(n) →∞, but, perhaps surprisingly, not if k(n) grows too quickly. In particular, there is a constant γ≈ 1.2021… such that if γ < k/log n < √(q), then the bias term is larger than the oscillating terms for every large even n.

In the case that k=1, the integer analogue of the explicit formula (2) has a corresponding bias term that is responsible for the phenomena known as Chebyshev's bias, named after Chebyshev who observed in 1853 that “There is a notable difference in the splitting of the prime numbers between the
two forms 4n + 3 and 4n + 1: the first form contains a lot more than the second". Chebyshev's observation was formalised by Rubenstein and Sarnak <cit.> who proved, under certain conjectures on the zeros of Dirichlet L-functions, that, if 

    S_k = { x ∈ℕ  :   (-1)^k∑_n ≤ x 
    Ω(n) = kχ(n) > 0 }

where χ is the non-trivial Dirichlet character mod 4, then the set S_1 has logarithmic density ≈ 0.996. Figure 1. shows the plots of the normalised character sum

    π_k^int(x) = (-1)^k(k-1)!log x/√(x) (loglog x)^k-1∑_n ≤ x 
    Ω(n) = kχ(n).


The phenomena has since been extensively studied and generalised in a number of directions. See <cit.> for an introduction to the topic. Ford and Sneed <cit.> proved, again under certain conjectures on the zeros of L(s,χ), that the set S_2 has logarithmic density ≈ 0.894. A more general theorem capturing the Chebyshev bias for fixed k ≥ 1 was proved for integers by Meng <cit.> and for polynomials by Devin and Meng <cit.>. For example, it follows from <cit.> and standard conjectures on the zeros of Dirichlet L-functions that the set S_k has logarithmic density δ_k where 1/2< δ_k < 1 and δ_k → 1/2 as k →∞. This suggests that in some sense the bias dissipates as k →∞. However, we shall see that, for polynomials and k(n) increasing with n, sometimes the bias is strong enough to ensure that (-1)^kπ_k(n,χ) >0 for all large even n.

From now on, χ will always denote a non-principal Dirichlet character modulo a fixed polynomial d ∈𝔽_q[t] and χ_0 will denote the principal character mod d. It may be helpful to bear in mind that for large values of n, the distribution of Ω(f), given a polynomial f selected uniformly at random from ℳ_n, is approximately normal with mean log n and standard deviation √(log n).

Because the behaviour of π_k(n, χ) depends on whether or not χ is real, we shall present the results for the two cases separately.



 §.§ When χ is not real



	Suppose χ^2 ≠χ_0 and let ϵ >0. With the same notation as in equation (1),
	
    π_k(n,χ)= ∑_γ_j≠ 0, πm_j^ke^i n γ_j + m_+^k +(-1)^n m_-^k
    	+  O( k/log n(∑_γ_j ≠ 0, πm_j^k + m_+^k + m_-^k ) )

	uniformly for 1≤ k ≤ q^1/2-ϵlog n.

When k is large with respect to n, this improves upon <cit.>, which requires that k = o(√(log n)) and has an error term involving a factor ( d)^k.

Theorem <ref> gives a main term and smaller error term in the range k = o(log n). A more general formula that describes the behaviour of π_k(n,χ) in the full range 1≤ k≤ q^1/2-ϵlog n can be extracted from the proof but is significantly more complicated to write down. If we assume certain simplifying assumptions, though, we can state the more general formula as follows.

	Suppose that χ^2 ≠χ_0 and that m_j = 1 for each j and m_±=0. Suppose k(n) is a sequence such that α = lim_n →∞k/log n exists and 0 ≤α <q^1/2.
	Then there exist non-zero constants h_j(α) such that
	
    π_k(n,χ) = ∑_γ_j ≠ 0, πh_j(α) e^i n γ_j + o(1).


Recall that the assumptions m_j=1 for each j and m_±=0 is conjectured to hold for number field Dirichlet L-functions.

	The coefficients h_j(α) are explicitly defined in terms of α and χ in the course of the proof but are quite lengthy to write down in full. An even more general formula that does not require the limit lim_n →∞k/log n to exist can be extracted from the proof but is more complicated to write down.




 §.§ When χ is real


The next two theorems show how the behaviour of π_k(n,χ) differs significantly when χ is real. The first deals with `small' values of k and again extends the range of a formula given in <cit.>.

	Suppose χ^2 = χ_0. With the same notation as in equation (1), uniformly for 1≤ k ≤ (log n)^1/2 we have
	
    π_k(n,χ)= ∑_γ_j≠ 0, πm_j^ke^i n γ_j + (m_++1/2)^k+(-1)^n(m_-+1/2)^k 
    
    	+  O(klog n∑_γ_j ≠ 0, πm_j^k + k^2log nmax_±{(m_±+1/2)^k }).

	Moreover, uniformly in the range 1≤ k ≤ (log n)^2/3 we have
	
    π_k(n,χ)= ∑_γ_j≠ 0, πm_j^ke^i n γ_j
    	+ (m_++1/2)^ke^(k-1)^22(m_++1/2)^2log n+(-1)^n(m_-+1/2)^ke^(k-1)^22(m_-+1/2)^2log n
    
    	+  O( klog n∑_γ_j ≠ 0, πm_j^k + (1k+k^3(log n)^2)max_±{ (m_±+1/2)^ke^(k-1)^22(m_±+1/2)^2log n}).


Notice that the error terms in the formulae above are essentially the same as the corresponding main terms but with certain extra factors involving k and log n. It is not too difficult to see that these extra factors are o(1) in the first formula if k = o(√(log n)). They are o(1) in the second if k →∞ and k = o((log n)^2/3). The change in behaviour and appearance of extra terms for k around √(log n) may explain why <cit.> required k = o(√(log n)). The significance of the threshold k around (log n)^2/3 will become apparent from the proof.

If we make the same simplifying assumptions as in Theorem <ref>, that is, the limit lim_n→k/log n exists and m_j = 1, m_± = 0, then we get a corresponding version for real χ that includes the bias term. The size of the bias term can be described in terms of the continuous function b(α) defined by

    b(α) = α(s(α)-1/2-log(2s(α))),  where  s(α) = 1/8α(√(1+16α) - 1).


Of particular significance is the fact that, if the real constants β≈ 0.3637… and γ≈ 1.2021… are defined by the two equations 
    e^β-1=4β^2   and γ = 1-β/4β^2,

then
b(α)<0 for 0 < α < γ and b(α) > 0 for α > γ.

	Suppose χ^2 = χ_0 and that m_j = 1 for each j and m_±=0. Suppose k(n) is a sequence such that α = lim_n →∞k/log n exists and 0 < α <q^1/2.
	Then there exist non-zero constants h_j(α) such that
	
    π_k(n,χ) = {h_+(α)+(-1)^n h_-(α) + o(1)}n^b((k-1)/log n) + ∑_γ_j ≠ 0, πh_j(α) e^i n γ_j + o(1)

	where
	
    h_±(α) = P_±(r)2^-r(r + 1)/2/Γ(r(r + 1)/2)L(± q^-1/2,χ)^-r/√(1+r^2/α)

	
    P_±(r) = ∏_p ∈𝒫(1+r χ(p)(± 1)^ p/q^ p/2)^-1(1-χ(p)(±1)^ p/q^ p /2)^-r(1-1/q^ p)^r(r+1)/2

	and r=r(α) is the positive root of
	
    r^2 + r/2 - α = 0.



	It follows that the oscillating terms dominate if 0 < α <γ, but that the bias terms dominate if γ < α <q^1/2, at least if n is even. This is perhaps surprising given the results in <cit.> and <cit.>, which, as explained in section 1.1 above, suggest that in some sense “as
	k increases, the biases become smaller and smaller". Since the conditions we assumed on the zeros of L(u,χ) are conjectured to hold for number field Dirichlet L-functions, we wonder whether something analogous happens in the number field setting. 


	The remark following Theorem <ref> concerning the coefficients h_j(α) applies verbatim to the coefficients h_j(α) in Theorem 4.




§ A SELBERG-DELANGE TYPE ARGUMENT


Let A>0 and u and z be complex variables satisfying |z|≤ A and |zu|<1. Deploying the Selberg-Delange method to study the quantity π_k(n,χ) entails studying the auxillary quantity

    M_z(n,χ) := ∑_f ∈ℳ_nχ(f) z^Ω(f) = ∑_k≥ 0z^k π_k(n,χ)

and then recovering π_k(n,χ) from M_z(n,χ) using Cauchy's integral formula. Now χ(f) z^Ω(f) is a multiplicative function of f and has Dirichlet series with Euler product given by

    G_z(u,χ):=∑_f ∈ℳχ(f)z^Ω(f)u^ f = ∏_p ∈𝒫(1-z χ(p) u^ p)^-1.

Since |𝒫_n| ≤ q^n, this product converges absolutely in the range |u| < min{|z|^-1, q^-1}. A direct application of the method makes use of the identity/definition

    G_z(u,χ) = L(u,χ)^z F_z(u,χ)

where

    F_z(u,χ):=∏_p ∈𝒫(1-z χ(p) u^ p)^-1)(1-χ(p) u^ p)^z

and this product converges absolutely for |u| < min{|z|^-1, q^-1/2}.
The crucial identity/definition we shall make use of is

    G_z(u,χ) = L(u,χ)^zL(u^2,χ^2)^z(z-1)/2 E_z(u,χ)

where 
    E_z(u,χ) = ∏_p ∈𝒫(1-z χ(p) u^ p)^-1(1-χ(p)u^ p)^z(1-χ^2(p)u^2  p)^z(z-1)/2

and this product converges absolutely for |u| < min{|z|^-1, q^-1/3}. This gives an explicit representation of the Dirichlet series for χ(f)z^Ω(f) beyond the radius |u| = q^-1/2 and will allow us to extract an explicit formula for M_z(n,χ) in terms of the zeros of L(u,χ) which are on the circle |u| = q^-1/2.
The key point being that E_z(u,χ), and hence G_z(u,χ), is holomorphic for |u|<min{|z|^-1, q^-1/3}. This follows because in that range

    |1-χ(p)zu^ p| ≥ 1 - |zu^ p| ≥ 1-|zu|>0
 so the factors (1-χ(p)z u^ p)^-1 have no poles and

    (1-zT)^-1(1-T)^z(1-T^2)^z(z-1)/2
       = (1+zT+z^2T^2 + O(T^3))(1-zT+z(z-1)/2T^2+ O(T^3))(1-z(z-1)/2T^2+O(T^4)) 
       = 1+ O(T^3)

so each factor in the Euler product of E_z(u,χ) is 1+O(u^3 p), hence the product converges absolutely and defines a holomorphic fucntion for |u|<min{|z|^-1, q^-1/3}.

Before starting the proof, let's take a minute to be clear about what these expressions mean. Having factored L(u,χ) over its zeros ρ as

    L(u,χ)=∏_ρ  :   L(ρ,χ) = 0(1-u/ρ)^m_ρ
 as in equation (1), we define

    L(u,χ)^z:=exp(z ∑_ρm_ρlog(1-u/ρ))

where log is defined on the set ℂ\ [0,-∞) and takes real values on the positive reals and define L(u^2,χ^2)^z(z-1)/2 similarly. These expressions define functions L(u,χ)^z and L(u^2,χ^2)^z(z-1)/2, holomorphic in u and z for all z ∈ℂ and all u ∈ℂ\⋃_ρ{u   :   1-u/ρ∈ℝ_≤ 0}.

The formula for M_z(n,χ) we need is given by Proposition <ref> below. First though we prove a simple integral lemma.


	Let A,δ>0. Let ℋ be the Hankel contour of radius 1 around 0 going along the negative real axis to -nδ. Uniformly for |z|≤ A we have
	
    1/2π i∫_ℋw^zdw/(1-w/n)^n+1 = 1/Γ(-z) + O(1/n)



	We may suppose n is sufficiently large. By Corollary 0.18 from <cit.> we have
	
    1/2π i∫_ℋw^ze^w dw = 1/Γ(-z) + O(e^-nδ/2)

	so it suffices to show that
	
    ∫_ℋ|w^z(1/(1-w/n)^n+1-e^w)||dw| = O(1/n).

	On the region w > -n/2 we have
	
    1/(1-w/n)^n+1-e^w = e^-(n+1)log(1-w/n) -e^w = e^w + O(1/n) -e^w = O(e^w/n)

	and ∫_ℋ|w^z e^w||dw| = O(1). On the rest of the integral
	
    ∫_-n/2^-nδ|w^z(1/(1-w/n)^n+1-e^w) ||dw| ≪ n^A+1e^- c n
 for some c>0 when |z|≤ A. This proves the lemma.



	For all ϵ>0 the following holds uniformly for |z|≤ q^1/2-ϵ. If χ^2 ≠χ_0,
	
    M_z(n,χ) =  ∑_ρ  : 
     L(ρ, χ) = 0 
     |ρ|=q^-1/2ρ^-nn^-z m_ρ-1{F_z(ρ,χ)c_ρ^z/Γ(-z m_ρ) + O(n^-1) }

	and if χ^2=χ_0,
	
    M_z(n,χ) =  ∑_ρ  : 
     L(ρ, χ) = 0 
     |ρ|=q^-1/2
    ρ≠± q^-1/2ρ^-nn^-z m_ρ-1{F_z(ρ,χ)c_ρ^z/Γ(-z m_ρ) + O(n^-1) }
    
    	+ ∑_± (± 1)^n q^n/2n^-1 -zm_± +z(z-1)/2 {E_z(± q^-1/2,χ)c_±^z (ϕ(d)/2q^ d)^z(z-1)/2/Γ(-zm_±+z(z-1)/2)  + O(n^-1) }

	for some constants c_ρ, c_± defined in the course of the proof.



	
	Applying Cauchy's integral formula with r<q^-1/2 gives
	
    M_z(n,χ) = 1/2π i∫_|u|=rG_χ(u,z) du/u^n+1.

	We shift this contour to write the left hand side in terms of the singularities of G_z(u,χ) with |u|=q^-1/2. If χ^2 ≠χ_0, these ρ consist just of the zeros of L(u,χ). If χ^2 = χ_0 however, we also have to include the points ± q^-1/2. For each such singularity ρ, let ℋ_ρ be the contour that consists of a circle of radius 1/n traversed clockwise around ρ and the two line segments on the ray from 0 to ρ joining this small circle to the circle |u|=q^ϵ/2-1/2. We may replace ϵ by min{1/10,ϵ} if necessary to ensure q^ϵ/2-1/2<q^-1/3.
Then (5) becomes
	
    ∑_ρ∈𝒮1/2π i∫_ℋ_ρG_z(u,χ) du/u^n+1 + O(∫_|u|=q^ϵ/2 - 1/2| G_z(u,χ)du/u^n+1| )
    	=:∑_ρ∈𝒮 I_ρ + O(q^n(1/2-ϵ/2))

	Here we have used the fact that G_z(u,χ) is uniformly bounded in the region |u|≤ q^ϵ/2-1/2, |z|≤ q^1/2-ϵ. Let us now evaluate each of these Hankel contours, first the non-real ρ, then ρ = ± q^-1/2.
	
	Case 1: Non-real ρ.
	
	Since F_z(u,χ) is holomorphic in u on ℋ_ρ we may use the approximation  F_z(u, χ) = F_z(ρ,χ)+O(|u-ρ|) for the singularities ρ = q^-1/2e^-iγ_j≠± q^-1/2 to get
	
    I_ρ  =  F_z(ρ,χ)1/2π i∫_ℋ_ρL(u,χ)^zdu/u^n+1
    	+ O(∫_ℋ_ρ|u-ρ||L(u,χ)^z| |du|/|u|^n+1).

	In the error term, change variable to w=n(1-u/ρ) so u=ρ(1-w/n) to get
	
    ∫_ℋ_ρ|(1-u/ρ)^1+zm_ρ(L(u,χ)/(1-u/ρ)^m_ρ)^z||du|/|u|^n+1   ≪ q^n/2|n^-2-z m_ρ|∫_ℋ|w^1+z  m_ρ||dw|/|(1-w/n)^n+1|
       ≪ q^n/2|n^-2-zm_ρ|

	since |L(u,χ)/(1-u/ρ)^m_ρ| is bounded above and below by positive constants on the contour of integration. Here ℋ is the contour from Lemma 1 with δ = q^ϵ/2 - 1.
	
	To evaluate the main term, again change to the variable w=n(1-u/ρ) in the first integral above to get
	
    ρ^-nn^-1/2π i∫_ℋL(ρ(1-w/n),χ)^zdw/(1-w/n)^n+1.

	Now if we define c_ρ≠ 0 by L(u,χ) = (1-u/ρ)^m_ρ(c_ρ + O(|1-u/ρ|)), or equivalently, as  c_ρ=L(u,χ)/(1-u/ρ)^m_ρ|_u=ρ and c_ρ^z=exp(z ∑_ρ'≠ρm_ρ'log(1-ρ/ρ')), then 
    ( L(u,χ)/(1-u/ρ)^m_ρ)^z = c_ρ^z + O(|1-u/ρ|)

	and
	
    L(ρ(1-w/n),χ)^z = (w/n)^ z m_ρc_ρ^z + O(|w/n|^z m_ρ+1).

	By Lemma <ref>, this gives as main term
	
    c_ρ^zρ^-nn^-zm_ρ-1/2π i∫_ℋw^z m_ρdw/(1-w/n)^n+1 =  c_ρ^zρ^-nn^-z m_ρ-1/Γ(-z m_ρ) + O(q^n/2|n^-zm_ρ-2|)

	and another error term bounded by
	
    ≪ q^n/2|n^-z m_ρ-2|∫_ℋ|w^z m_ρ+1||dw|/|(1-w/n)^n+1|≪ q^n/2|n^-z m_ρ-2|.


	Case 2: Real ρ.
	
	Now let's look at the singularities ± q^-1/2. If χ^2 is not principal, then exactly the same argument still works with ρ = ± q^-1/2 and the convention m_± q^-1/2=m_± because in that case F_z(u, χ) = L(u^2,χ^2)E_z(u,χ) is holomorphic near u = ± q^-1/2.
	
	Suppose then that χ^2=χ_0 is principal. We now have to worry about the extra poles of L(u^2,χ_0) at u=± q^-1/2. First near u = q^-1/2, change to the variable w = n(1-q^1/2u) so u= q^-1/2(1-w/n). Then we want to evaluate
	
    q^n/2n^-1/2π i∫_ℋL(1-w/n/q^1/2,χ)^z L((1-w/n)^2/q,χ_0)^z(z-1)/2E_z(1-w/n/q^1/2,χ) dw/(1-w/n)^n+1

	Defining c_+≠ 0 by L(u,χ)/(1-uq^1/2)^m_+ = c_+ + O(|1-uq^1/2|), along the contour of integration we have
	
    L(1-w/n/q^1/2,χ)^z = (w/n)^z m_+c_+^z+O(|w/n|^z m_+ +1)

	and since L(u, χ_0)=1/1-qu∏_p|d(1-u^ p) and ∏_p|d(1-q^- p) = q^- dϕ(d) we have 
    L((1-w/n)^2/q,χ_0)^z(z-1)/2 = (n/2wϕ(d)/q^ d)^z(z-1)/2 + O(|n/w|^z(z-1)/2-1).

	We also have,
	
    E_z(1-w/n/q^1/2,χ) = E_z(q^-1/2,χ)+ O(|w/n|)

	which together give the main term as
	
    q^n/2n^-1 -zm_+ +z(z-1)/2 E_z(q^-1/2,χ)c_+^z (ϕ(d)/2q^ d)^z(z-1)/21/2π i∫_ℋw^z m_+ - z(z-1)/2/(1-w/n)^n+1 dw 
    
    	= q^n/2n^-1 -zm_+ +z(z-1)/2 E_z(q^-1/2,χ)c_+^z (ϕ(d)/2q^ d)^z(z-1)/2/Γ(-zm_++z(z-1)/2)
    	+ O(q^n/2|n^-zm_++z(z-1)/2-2|)

	with the error terms all being O(q^n/2|n^-zm_++z(z-1)/2-2|).
	
	The -q^-1/2 term is essentially the same. Together this proves Proposition <ref>.




§ SADDLE POINT LEMMAS
 
The following two lemmas allow us to deduce a formula for π_k(n,χ) from one for M_z(n,χ).

	Let A>0 and let p_n(z)=∑_k≥ 0c_k(n)z^k be a sequence of polynomials such that uniformly for n≥ 1 and |z|≤ A
	
    p_n(z)=n^a z(f(z) + O( n^-1))

	for some real constant a>0 and some function f(z) that is holomorphic on {z ∈ℂ  :   |z|≤ A}. Then uniformly for 1≤ k ≤ a A log n,
	
    c_k(n) = (alog n)^k/k!(f(k/a log n) + O(k/(log n)^2)).



	By Cauchy's integral formula,
	
    c_k(n) = 1/2π i∫_|z|=rp_n(z)dz/z^k+1.

	We choose r to minimise the trivial bound
	
    |c_k(n)| ≪ r·max_|z|=r|n^a z/z^k+1| = n^a r/r^k.

	Since a>0, the maximum occurs at z = r = k/(alog n). From (6) we have
	
    c_k(n) = 1/2 π i∫_|z|=rn^ az f(z)dz/z^k+1 + O(E)

	where E = 1/n∫_|z|=r|n^az/z^k+1||dz|.
	Using
	
    1/2 π i∫_|z|=r (z-r)n^a zdz/z^k+1 = (a log n)^k-1/(k-1)! - r(a log n)^k/k! = 0
 and the approximation
	
    f(z) = f(r) + f'(r)(z-r) + O(|z-r|^2)
 this becomes
	
    c_k(n) = f(r)(a log n)^k/k! + O(r^-k-1∫_|z|=r|n^a z(z-r)^2||dz| + E ).

	The integral in the error term is bounded by
	
    r^3∫_-π^π|1-e^iθ|^2e^kcosθ dθ≪ r^3∫_-∞^∞θ^2 e^k(1-θ^2/5)dθ≪ r^3e^kk^-3/2

	which contributes an error of
	
    ( k/(alog n))^2-ke^kk^-3/2≪ a^k(log n)^k-2e^k√(k)/k^k≪ a^kk(log n)^k-2/k!

	by Stirling's formula. The other term E in the error contributes at most
	
    ≪r^-k-1/n∫_|z|=r|n^a(z-r)||dz| ≪r^-k/n∫_-1/2^1/2n^-art^2dt ≪1/n(alog n)^ke^k/k^k+1/2≪1/n(a log n)^k/k!

	again by Stirling's formula.

We also need the following quadratic variant of Lemma 2.

	Let A>0 and let p_n(z)=∑_k≥ 0c_k(n)z^k be a sequence of polynomials such that uniformly for n≥ 1 and |z|≤ A
	
    p_n(z)=n^a z^2 + bz(f(z) + O( n^-1))

	for some real constants a>0 and b>0 and some function f(z) that is holomorphic on {z ∈ℂ  :   |z|≤ A} with f(0)=1. Let r be the positive root of the quadratic
	
    r^2+b/2ar - k/2a log n = 0.
 Then uniformly for 1≤ k ≤min{(log n)^1/2,bA log n} we have
	
		
  * 
    c_k(n) = (b log n)^k/k!(1 + O(k^2/log n) ).

		

		 In the range 1≤ k ≤min{(log n)^2/3, bA log n } we have
		
  * 
    c_k(n) = (b log n)^k/k!e^a k^2/b^2 log n(1 + O(1/k + k^3/(log n)^2)).

		

		 In the range 1≤ k ≤ 2aA^2 log n we have
		
  * 
    c_k(n) = n^ar^2+br/r^k(f(r)/√(2π(4ar^2+br)log n) + O((r log n)^-3/2)).

	



	Part (a) follows from the proof of Lemma <ref> with r=k/(b log n) and the approximation
	
    n^a z^2 = 1+ O(k^2/log n)
 which holds for |z| = r. For part (c) we again use Cauchy's formula and the saddle point method. This time we choose r to minimise the bound
	
    |c_k(n)| ≪ r ·max_|z|=r|n^az^2+bz/z^k+1| = n^ar^2+br/r^k.

	The maximum occurs at z=r because a>0 and b>0. By differentiating, this is minimised when
	
    r^2+b/2ar - k/2a log n = 0, or r=b/4a(√(1+8ak/b^2 log n)-1).

	Notice that in the range k≤ 2aA^2 log n we have
	
    r ≤b/4a(√(1+16a^2A^2/b^2)-1)≤ A

	since √(1+x)≤ 1+√(x) for all x>0 so this is a valid choice for r.
	Now from (7) and
	
    f(z) = f(r) + f'(r) (z-r) + O(|z-r|^2)

	it follows that
	
    c_k(n) = f(r) I_1 + f'(r)I_2 + O(I_3) + O(E)

	where
	
    I_1    = 1/2 π i∫_|z|=rn^az^2+bz/z^k+1dz 
    
    	I_2    = 1/2 π i∫_|z|=rn^az^2+bz/z^k+1(z-r)dz 
    
    	I_3    = ∫_|z|=r|n^az^2+bz/z^k+1(z-r)^2||dz| 
    
    	E    = n^ar^2+br-1/r^k.

	Writing z=re^2 π i t and rearranging slightly this can we written
	
    c_k(n) = n^ar^2 +br/r^k{ f(r)J_1 + r f'(r)J_2 + O(r^2 J_3) + O(1/n) }

	where
	
    J_1    = ∫_-1/2^1/2n^(ar^2(e^4 π i t-1) + br(e^2π i t-1)e^-k 2π itdt
    
    	J_2    =  ∫_-1/2^1/2n^(ar^2(e^4 π i t-1) + br(e^2π i t-1)e^-k 2π it(1-e^2π i t)dt
    
    	J_3    = ∫_-1/2^1/2n^(ar^2(cos(4π t)-1) + br(cos(2 π t)-1)|1-e^2π i t|^2dt.

	The integrals I_1 and I_2 could be written explicitly as a sum of k terms. Instead, we will asymptotically evaluate J_1 by expanding around the point t=0. This will give a main term and smaller error term provided k →∞. This is akin to approximating the integral 1/2π i∮e^z/z^k+1dz=1/k! by e^kk^-k/√(2π k). For small values of k, part (a) is better.
	
	Let δ = (r log n)^-1/4. Using e^ix = 1+ix-x^2/2-ix^3/6+O(x^4) for all x and the definition of r we have
	
    J_1    = ∫_-δ^δn^ar^2(-8π^2t^2 -i32π^3t^3/3 +O(t^4) )+br(-2π^2 t^2 -i4π^3t^3/3 + O(t^4))dt + O(n^-br δ^2)
       = ∫_-δ^δn^-(4ar^2+br)2π^2t^2(1+O(t^6(rlog n)^2 + t^4r log n))dt + O(n^-br δ^2) 
       = 1/√(2π (4 ar^2+br)log n) + O((r log n)^-3/2).

	And in a similar vein,
	
    J_2    = ∫_-δ^δn^ar^2(-8π^2t^2 -i32π^3t^3/3 +O(t^4) )+br(-2π^2 t^2 -i4π^3t^3/3 + O(t^4))(-2π i t + O(t^2))dt  + O(n^-br δ^2) 
       ≪∫_-δ^δn^-(4ar^2+br)2π^2t^2(t^6(r log n)^2 + t^4r log n + t^2)dt + n^-br δ^2≪ (r log n)^-3/2

	and
	
    J_3 ≪∫_-∞^∞n^-br t^2t^2 dt ≪ (r log n)^-3/2,

	which proves part (c).
	
	To prove part (b), we approximate r and eliminate it from the expression given in part (c). Recall the definition of r
	
    r = b/4a(√(1+8ak/b^2 log n)-1) =k/b log n - 2ak^2/b^3(log n)^2 + O(k^3/(log n)^3)

	so k/2 ≤ b r log n ≤ 2 k for n sufficiently large and
	
    f(r) = f(0) + O(r) = 1 + O(k/log n)

	and the expression from part (c) becomes
	
    n^ar^2 + br/r^k1/√(2 π (4ar^2+br)log n)(1 + O (1/k + k/log n)).

	Using the identity ar^2+br/2-k/2 log n=0 and (7) the main term rearranges to
	
    n^k/2log n+br/2r^-k/√(2 π (2k-br log n)) = (b log n)^ke^k e^-ak^2/b^2log n + O(k^3/(log n)^2)/√(2 π (k+2ak^2/b^2 log n+O(k^3/(log n)^2))(k-2ak^2/b^2 log n + O(k^3/(log n)^2))^-k
    
    	= (b log n)^ke^k/k^k √(2 π k) e^-ak^2/b^2log n(1 + O(k/log n + k^3/(log n)^2))(1-2ak/b^2 log n + O(k^2/(log n)^2))^-k
    
    	=  (b log n)^k/k! e^ak^2/b^2log n(1 + O(1/k + k/log n + k^3/(log n)^2)).

	Here we have used (1 - x + O(y))^-k = e^xk(1+O(kx^2 + ky)) when kx^2, ky ≪ 1.
	Finally, we may leave out the k/log n term because 1/k + k^3/(log )^2≥k/log n.




§ PROOFS OF THEOREMS


The proofs proceed by applying Lemmas <ref> and <ref> to Proposition <ref>.



 §.§ Proof of Theorem <ref>

Suppose χ^2 ≠χ_0. We would like to apply Lemma <ref> to the polynomial

    p_n(z)=1/zM_-z(n,χ) =  - ∑_f ∈ℳ_nχ(f) (-z)^Ω(f)-1 = ∑_k≥ 1(-1)^kπ_k(n,χ)z^k-1

so that (-1)^kπ_k(n,χ) is the coefficient of z^k-1. However, p_n(z) isn't itself of the form required by Lemma <ref>. By Proposition <ref>, it is a sum over ρ of terms of the required form. But it is clear from the proof of Lemma <ref> that we can apply it to each summand separately which is what we shall do. So in our application of Lemma <ref> to the summand ρ from Proposition <ref>, we may take A= q^1/2-ϵ and have a=m_ρ>0 and

    f(z)  = 1/zF_-z(ρ, χ)c_ρ^-z/Γ(z m_ρ) = m_ρ F_-z(ρ, χ) c_ρ^-z/Γ(1+z m_ρ).

Then Theorem <ref> follows after using

    f((k-1)/(a log n)) = f(0) + O(k/log n) = m_ρ + O(k/(log n)).




 §.§ Proof of Theorem <ref>

Suppose χ^2 = χ_0. With the same p_n(z) as in the proof of Theorem <ref>, this time we need Lemma <ref> and Lemma <ref> parts (a) and (b). Again, we don't apply these lemmas directly to p_n(z), but it is clear from the proofs that we may apply them to each summand in Proposition 5 separately. For the ρ≠± q^-1/2 terms we apply Lemma <ref> just as above. For the ρ = ± q^-1/2 terms we apply Lemma <ref> part (a) in the range 1≤ k ≤ (log n)^1/2 and part (b) in the range 1≤ k ≤ (log n)^2/3 with a = 1/2, b = m_± + 1/2 and 

    f(z)    =  E_-z(± q^-1/2,χ)c_±^-z(ϕ(d)/2q^ d)^z(z+1)/2/zΓ(zm_±+z(z+1)/2)
       = (m_±+(z+1)/2) E_-z(± q^-1/2,χ)c_±^-z(ϕ(d)/2q^ d)^z(z+1)/2/Γ(1+zm_±+z(z+1)/2)
 so that f(0) = m_± + 1/2.



 §.§ Proof of Theorems <ref> and <ref>


Suppose m_j = 1 for each j and m_± = 0.
This time we apply Lemma <ref> and Lemma <ref> part (c) to the same p_n(z) using Proposition <ref>. For χ^2 ≠χ_0 and Theorem <ref> we just apply the proof of Theorem <ref> and the approximation

    f((k-1)/(log n)) = f(α ) + o(1).

We see therefore that h_j(α) = F_-α(ρ,χ)c_ρ^-α/Γ(1+α) where ρ = α_j(χ)^-1. Also, in the case that m_ρ=1, it follows from the definition of c_ρ given in the proof of Proposition <ref> that c_ρ = -ρ L'(ρ, χ).

For χ^2 = χ_0 and Theorem <ref>, we have the two extra terms ρ = ± q^-1/2. We can evaluate these with Lemma <ref> part (c) applied with a = b = 1/2 and

    f_±(z)  =  E_-z(± q^-1/2,χ)c_±^-z(ϕ(d)/2q^ d)^z(z+1)/2/zΓ(z(z+1)/2).

Then r>0 satisfies

    r^2+r/2-k-1/log n = 0.
 Since k(n) →∞ as n →∞ we also have r log n →∞ as n →∞. Note that since m_± = 0, we have c_± = L(± q^-1/2,χ). Therefore, using ∏_p|d(1-q^- p) = ϕ(d)/q^ d, one can check that f_±(r) = h_±(α)√(1+r^2/α) + o(1) with h_±(α) defined as in the statement of Theorem 4. To finish the proof of Theorem <ref> it therefore suffices to show that

    n^r^2/2+r/2/r^k-11/√(2π(2r^2+r/2)log n) = (1+o(1))(log n)^k-1/(k-1)!1/√(1+r^2/α)n^b((k-1)/log n)

where b is defined by (2) and check the stated conditions on the sign of b. This is a straightforward calculation using the definition of r and Stirling's formula. The left hand side of (10) is

    (log n)^k-1/(k-1)!(k-1)!/(rlog n)^k-1n^r/4+k-1/2 log n/√(2π(k-1) (log n/k-1r^2 + 1))
    
    =  (log n)^k-1/(k-1)!(k-1)!e^k-1/(k-1 )^k-1n^r/4-k-1/2log n+k-1/log nlog(k-1/rlog n)/√(2π(k-1) (log n/k-1r^2 + 1))
    
    =(1+o(1))(log n)^k-1/(k-1)!n^u(s-1/2-log(2s))/√(1+r^2/α)

where u=(k-1)/log n and s=r/2u. Now s is the positive root of the quadratic equation 
    s^2+s/4u-1/4u=0

so

    u = 1-s/4s^2

and

    s=1/8u(-1+√(1+16u))

from which it follows that 0 ≤ s ≤ 1. This proves (10) with b defined by (3) since α = lim_n →∞ u. Finally, it is easy to check the conditions on the sign of b by noting that s-1/2-log(2s) is strictly decreasing on (0,1) and equal to 0 at s = β where β is the unique solution to β-1/2=log (2β) with 0≤β≤ 1.



§ ACKNOWLEDGEMENTS


We would like to thank Lucile Devin for helpful comments on an earlier draft of this paper and making available the paper <cit.>. This work was supported by the Engineering and Physical Sciences Research Council [EP/L015234/1] via the EPSRC Centre for Doctoral Training in Geometry and Number Theory (The London School of Geometry and Number Theory), University College London.


L-M
L. Devin, X. Meng,
Chebyshev's bias for products of irreducible polynomials,
preprint, arXiv:1809.09662

F-S,
K. Ford and J. Sneed,
Chebyshev's bias for products of two primes,
Experiment. Math.
19
(2010),
no. 4,
385–398.

G-M
A. Granville and G. Martin,
Prime number races,
Amer. Math. Monthly 113 (2006), no. 1, 1–33.

M
X. Meng,
Chebyshev’s bias for products of k primes,
Algebra Number Theory 12 (2018), no. 2, 305–341

Rosen
M. Rosen,
Number Theory in Function Fields,
Springer-Verlag,
(2002).

R-S
M. Rubinstein, and P. Sarnak,
Chebyshev's bias,
Experiment. Math.,
3
(1994)
173–197.

Ten
G. Tenenbaum,
An Introduction to Analytic and Probabilistic Number Theory,
Cambridge University Press,
(1995).



