An average of generalized Dedekind sums
Travis Dillon Stephanie Gaston
math.NT

Quantum eigenvalue estimation via time series analysis
    Rolando D. Somma
    December 30, 2023
======================================================




We study a generalization of the classical Dedekind sum that incorporates two Dirichlet characters and develop properties that generalize those of the classical Dedekind sum. By calculating the Fourier transform of this generalized Dedekind sum, we obtain an explicit formula for its second moment. Finally, we derive upper and lower bounds for the second moment with nearly identical orders of magnitude.





§ INTRODUCTION


Let h and k be coprime integers with k>0. The classical Dedekind sum is defined as

    s(h,k) = ∑_j  k B_1(j/k) B_1(jh/k),

where B_1(x) is the first Bernoulli function

    B_1(x) = 
    0    if  x∈ℤ
    
    x - ⌊ x ⌋ - 1/2   otherwise.


Dedekind first studied this sum because of its connection to the transformation properties of the Dedekind eta function. Since then, Dedekind sums have been studied extensively in a wide variety of contexts, including modular forms, topology, combinatorial geometry, and quadratic reciprocity. 

Averages of Dedekind sums have attracted considerable attention. In <cit.>, Walum found an exact formula for the second moment of the classical Dedekind sum:

    ∑_a  p| s(a,p) | ^2
     = p^2/π^4(p-1)∑_ψ p 
    ψ(-1) = -1| L(1,ψ)|^4.

Following this, Conrey, Fransen, Klein, and Scott <cit.> and Zhang <cit.> studied the asymptotics of the second and higher moments.

Numerous authors have generalized the classical Dedekind sum in a variety of ways. In <cit.>, Berndt develops a generalization of the classical Dedekind sum that incorporates a Dirichlet character and higher Bernoulli functions. Dağlı and Can <cit.> generalized Berndt's sum to include two characters, and Stucker, Vennos, and Young <cit.> recently showed how to derive this generalized Dedekind sum using newform Eisenstein series. In this paper, we study the sum from <cit.> and <cit.>.  We follow the notation of <cit.>.

Let χ_1 and χ_2 be nontrivial primitive characters with moduli q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1. For γ = ([ a b; c d ]) ∈Γ_0(q_1q_2) with c≥ 1, the generalized Dedekind sum associated to χ_1 and χ_2 is given by

    (γ) = 
    ∑_j c ∑_n  q_1χ_2(j)χ_1(n)
    B_1(j/c) B_1(n/q_1 + aj/c) -.2cm.

Because the generalized Dedekind sum depends only on the entries in the first column of γ, it will at times be convenient to write (a,c) in place of (γ). Additionally, note that the generalized Dedekind sum depends only on the residue of a modulo c.

We will often make use of an alternate form of the generalized Dedekind sum. Let e(x) = exp(2π i x) and τ(χ,l) denote the Gauss sum ∑_n  qχ(n)e(nl/q). We write τ(χ) for τ(χ,1). For any character χ modulo q, define the first generalized Bernoulli function as 

    B_1,χ(x) = -τ(χ)/2π i∑_l ≠ 0χ(l)/le(lx/q) -.2cm.

This equation unifies the cases appearing in Definition 1 of <cit.>. Theorem 3.1 of <cit.> states a finite sum formula for B_1,χ for primitive characters χ:

    B_1,χ(x) = ∑_r  qχ(r)B_1(x+r/q) -.2cm.

Substituting (<ref>) into (<ref>) gives the alternate formula 

    (γ) =  ∑_j  cχ_2(j) B_1(j/c) B_1,χ_1(aj/c/q_1) -.2cm.


Lemma 2.2 of <cit.> shows that the generalized Dedekind sum (γ) is a crossed homomorphism from Γ_0(q_1q_2) into ℂ. Set χ(γ) = χ(d) for γ = ([ a b; c d ]), and let γ_1,γ_2 ∈Γ_0(q_1q_2). Then

    (γ_1γ_2) = (γ_1) + χ_1χ_2(γ_1)(γ_2).

If χ_1 = χ_2 = χ, then S_χ,χ(γ) is a homomorphism from Γ_0(q_1q_2) into ℂ.

Our main result is an exact formula for the second moment of (γ), which generalizes the result of Walum in <cit.>.  We use χ^⋆ to denote the primitive character that induces a given character χ and q(χ) to denote its conductor.

Let χ_1 and χ_2 be nontrivial primitive characters modulo q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1, and let q_1q_2 | c. Then

    ∑_a  c 
     (a,c) = 1|(a,c)|^2 =
    φ(c)/π^4∑_ψ c 
    ψχ_1(-1)=-1| L(1,ψ^⋆χ_1)|^2 | L(1,(ψχ_2)^⋆)|^2 
    | g_χ_1,χ_2(ψ;c)|^2,

where

    g_χ_1,χ_2(ψ;c) = τ((ψχ_2)^⋆) τ(ψ^⋆) τ(χ_1)
    ∑_d | c 
     d ≡ 0 q(ψ)χ_2(c/d)/φ(d)
        ((ψχ_2)^⋆μ∗ 1)(d) 
        (χ_1 ∗μψ^⋆)(d/q(ψ)) -.2cm.



We also bound the second moment above and below.

Let χ_1 and χ_2 be nontrivial primitive characters modulo q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1, and let q_1q_2 | c. Then

    ∑_a  c 
     (a,c) = 1|(a,c)|^2 = q_1 c^2+o(1).


Since (<ref>) has cq_1 terms, each of which is bounded by 1 in absolute value, Theorem <ref> is consistent with “square-root” cancellation.


The lower bound of Theorem <ref> implies the following corollary, which may be interpreted as a statement about the kernel of the crossed homomorphism (γ).

Let χ_1 and χ_2 be nontrivial primitive characters modulo q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1. Then for each positive c ≡ 0  q_1q_2, there exists an integer a coprime to c such that S_χ_1,χ_2(a,c) is nonzero.

In particular, the crossed homomorphism (γ) is always nontrivial. In contrast, the only homomorphism from Γ_0(1)=SL_2(ℤ) into ℂ is trivial, since the abelianization of SL_2(ℤ) is finite (for a nice proof of this well-known fact, see Keith Conrad's notes[<https://kconrad.math.uconn.edu/blurbs/grouptheory/SL(2,Z).pdf>]).

In Section <ref>, we establish a few basic properties of the generalized Dedekind sum. These properties are extensions of corresponding properties of the classical Dedekind sum, but it appears that they have yet to be documented in the literature. One such property writes the generalized Dedekind sum as a cotangent sum: 

Let χ_1 and χ_2 be characters modulo q_1 and q_2, respectively. Then for each positive c ≡ 0 q_1q_2, 

    (γ)
    = -1/4cq_2'∑_s  c   '∑_r  q_2(rπ/c)(sπ/c)  
        τ(χ_1,s)  τ(χ_2,(r+as)q_2/c),

where the primes indicate omission of the terms for which  is undefined.

Section <ref> is independent of the following sections, as the proofs of Theorems <ref> and <ref> do not depend upon its results.

Further work in this area could include sharper asymptotics of the second moment, along the lines of Zhang <cit.>, or asymptotics of higher moments, following Conrey, Fransen, Klein, and Scott <cit.>.











§ PROPERTIES OF THE GENERALIZED DEDEKIND SUM




 §.§ Arithmetic properties

Throughout this section, let χ_1 and χ_2 be characters modulo q_1 and q_2, respectively. The original definition for the generalized Dedekind sum requires χ_1 and χ_2 to be nontrivial and primitive characters such that χ_1χ_2(-1) = 1. However, we can extend the definition to any pair of characters via the finite sum formula (<ref>). With this extension, we can recover the classical Dedekind sum by taking χ_1 and χ_2 to be trivial. Consequently, all of the properties proved in this section subsume the analogous properties for the classical Dedekind sum.

We may similarly extend the definition of the generalized Dedekind sum to all a ∈ℤ and c ≡ 0 q_1q_2 through (<ref>). As mentioned in <cit.>, it is not hard to prove that s(h,k) = s(α h, α k) for all positive integers α, so this extension adds no new features in the classical case. The same is true in the general case, due to the following:

 
Let a and c be coprime integers with q_1q_2 | c. Then (a,c) = (α a, α c) for all positive integers α.


 
If χ_1χ_2(-1) = -1, then (γ) = 0 for all γ∈Γ_0(q_1q_2).


We prove Proposition <ref> by rewriting the sum over j in (<ref>) as

    ∑_j α c⟶∑_l α ∑_j  c

and change variables j → j + c l. Proposition <ref> is proven by changing variables j → -j and n→ -n in (<ref>) and using that B_1(-x) = -B_1(x).

We also present two arithmetic properties of the generalized Dedekind sum. For the remainder of this section, we assume that χ_1χ_2(-1) = 1.


Let c ≥ 1 and q_1q_2 | c. Then (-a,c) = -χ_2(-1) (a,c).



Let c ≥ 1 and q_1q_2 | c. Further, suppose that aa≡ 1 c. Then S_χ_1,χ_2(a,c) = χ_1(-a)χ_2(a)S_χ_1,χ_2(a,c).


Proposition <ref> can be proved by changing variables j→ -j in the the finite sum formula (<ref>). To prove Proposition <ref>, we substitute j → a(j-nc/q_1), then n → -an in (<ref>).  If γ = ([ a b; c d ]) ∈Γ_0(q_1q_2), then d ≡ac, so Proposition <ref> may be rewritten as (d,c) = χ_1(-1)χ_2(d)(a,c).

The classical Dedekind sum can be written in a variety of forms. Using that

    ∑_j  k B_1(hj/k) = 0,

Apostol <cit.> shows that 

    s(h,k) = ∑_j = 1^k-1j/k  B_1(hj/k),

eliminating one of the Bernoulli functions. Analogously, substituting j→ c-j and n → -n shows that

    ∑_j  c ∑_n  q_1χ_2(j)χ_1(n) B_1(n/q_1 + aj/c) = 0.

Therefore, the generalized Dedekind sum can be written as

    (γ) = 
    ∑_j=1^c-1 ∑_n  q_1j/c χ_2(j)χ_1(n) B_1(n/q_1 + aj/c) -.2cm.


The classical Dedekind sum can also be written as a cotangent sum, as in equation 26 of <cit.> and Exercise 11, Chapter 3 of <cit.>:

    s(h,k) = 1/4k∑_j = 1^k-1(π j/k) (π hj/k) -.2cm.

Proposition <ref> gives the corresponding result for the generalized Dedekind sum.




 §.§ Proof of Proposition <ref>

Rademacher and Grosswald <cit.> prove that

    B_1(j/c) = '∑_r  c( e(r/c) /1-e(r/c) + 1/2)e(rj/c) -.2cm.

With a bit of manipulation, this transforms into

    B_1(j/c) = i/2c '∑_r  c(π r/c) e(rj/c) -.2cm.

Substituting (<ref>) into (<ref>) gives

    (γ)
    = -1/4c^2'∑_r,s  c(rπ/c) (sπ/c)
     ∑_n  q_1χ_1(n)  e(sn/q_1)
    ∑_j  cχ_2(j)e(j(r+as)/c) -.2cm.

We substitute j → j + l q_2 in the sum over j to get

    ∑_j  cχ_2(j)e(j(r+as)/c)
    = ∑_j  q_2χ_2(j) e(j(r+as)/c)
        ∑_l  c/q_2
            e(l (r+as)/c/q_2) -.2cm.

From the othogonality relations for additive characters, the sum over l is c/q_2 if r+as ≡ 0 (mod c/q_2) and vanishes otherwise. If c/q_2 divides r+as, then (<ref>) simplifies as 

    c/q_2 τ(χ_2,(r+as)q_2/c) -.2cm.


The sum over n in (<ref>) is the Gauss sum τ(χ_1,s). Substituting the Gauss sums into (<ref>) gives

    (γ)
    = -1/4cq_2'∑_r,s  c 
     r + as ≡ 0  c/q_2(rπ/c)(sπ/c)  
        τ(χ_1,s)  τ(χ_2,(r+as)q_2/c),

and changing variables r→ -as+rc/q_2 finishes the proof.  

A special case occurs when χ_1 and χ_2 are primitive. Then the Gauss sums simplify as τ(χ,s) = τ(χ)χ(s), and the formula in Proposition <ref> becomes

    (γ) = -τ(χ_1)τ(χ_2)/4c q_2'∑_s  c  '∑_ r  q_2χ_1(s) χ_2(r) (π( r/q_2-as/c)) (π s/c) -.2cm.
















§ PROOF OF THEOREM <REF>


We prove Theorem <ref> by evaluating the Fourier transform of . Our approach will loosely follow that of Walum in <cit.>. Before we begin, we establish a character relation (Lemma <ref>) and evaluate three finite sums (Lemmas <ref>, <ref>, and <ref>). 

Throughout this section, χ_1 and χ_2 are nontrivial primitive characters modulo q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1.  We denote the principal character modulo q by χ_0,q.
Finally, we extend every Dirichlet character ψ to all of ℝ by setting ψ(x)=0 if x∉ℤ.




 §.§ Preliminary lemmas




For any c>0,

    ∑_d | c1/φ(d)∑_ψ dψ(m/c/d)ψ(n/c/d) =  1    if  m ≡ n  c
    
    0    if  m≢n c.



Suppose that m ≡ n (mod c) and (m,c) = k. The sum over ψ is 0 unless c/d = k, in which case it is φ(d). On the other hand, if m≢n (mod c), then the inner sum always vanishes.








If χ is a character modulo d | c, then

    ∑_r  cχ(r) B_1(r/c) = -τ(χ^⋆)/π i (χ^⋆μ∗ 1)(d)
    
    L(1,χ^⋆)    if χ(-1)=-1
    
    0    if χ(-1)=1.



Substituting

    χ(r) = χ^⋆(r) ∑_k | (d,r)μ(k),

into the sum over r to get

    ∑_r  cχ(r) B_1(r/c)
    = ∑_k | dμ(k) χ^⋆(k) ∑_r  c/kχ^⋆(r)B_1(r/c/k) -.2cm.

Consider the inner sum. If (q(χ),k) > 1, then χ^⋆(k)=0. We may therefore assume that (q(χ),k)=1, which implies that q(χ) | c/k. We substitute r → t + rq(χ), where t runs modulo q(χ) and r now runs modulo c/kq(χ). Using the orthogonality relations, the sum over r in (<ref>) becomes

    ∑_r = 0 ^c/kq(χ)-1 ∑_t = 1^q(χ)-1χ^⋆(t) (t+rq(χ)/c/k - 1/2) 
    = ∑_t = 1^q(χ)-1χ^⋆(t) ∑_r = 0 ^c/kq(χ)-1t/c/k.

The inner sum simplifies to t/q(χ). Using orthogonality and (<ref>), we obtain

    ∑_t = 1^q(χ)-1χ^⋆(t) t/q(χ)
    = ∑_t q(χ)χ^⋆(t) B_1(t/q(χ))
    = B_1,χ^⋆(0).

Applying (<ref>) gives

    B_1,χ^⋆(0)
    = -τ(χ^⋆)/π i L(1,χ^⋆)    if χ(-1)=-1
    
    0    if χ(-1)=1.

Substituting (<ref>) for the sum over r in (<ref>) proves the lemma.


The following result is Lemma 3.2 of <cit.> (corrected on Kowalski's website).

If ψ is a non-principal character modulo d then 

    τ(ψ,l) =
    τ(ψ^⋆) ∑_k | l 
     k| d/q(ψ)
        k ψ^⋆(l/k)
        ψ^⋆(d/kq(ψ)) μ(d/kq(ψ)) -.2cm.





If ψ is a character modulo d | c and χ is a primitive character modulo q| c, then

    ∑_t  cψ(t/c/d) B_1,χ(t/c/q)
    = -τ(χ) τ(ψ^⋆)/π i 
        (χ∗μψ^⋆)(d/q(ψ))
        
            L(1,χψ^⋆)     if χψ(-1) = -1
    
            0                                  if χψ(-1) =  1.



If c/d ∤ t, then the term vanishes, so we substitute t → (c/d)t and express B_1,χ as an infinite sum using (<ref>):

    ∑_t  cψ(t/c/d) B_1,χ(t/c/q)
       = ∑_t  dψ(t)B_1,χ(t(c/d)/c/q) 
       = -τ(χ)/2π i∑_l≠0χ(l)/l∑_t  dψ(a)  e(tl/d) -.2cm.


The sum over t is the Gauss sum τ(ψ,l). Using Lemma <ref>, (<ref>) becomes

    -τ(χ) τ(ψ^⋆)/2π i∑_k | d/q(ψ)ψ^⋆(d/kq(ψ))
        μ(d/kq(ψ)) χ(k)
        ∑_l ≠ 0χ(l)/lψ^⋆(l).

The sum over l is 2L(1,χψ^⋆) if χψ(-1) = -1 and 0 otherwise, which completes the proof.










If χ is a character modulo q | c, then 
    ∑_a  c 
     (a,c) = 1χ(a) = φ(c)    if χ is principal
    
    0    otherwise.
 



The sum is equal to

    ∑_a  c χ(a)χ_0,c(a)
    = φ(c)    if χχ_0,c is principal
    
    0    otherwise,

and χχ_0,c is principal exactly when χ is principal.






In the next theorem, we fix c and regard (a,c) as a function of a from (ℤ/cℤ)^× into ℂ.



Fourier transform of 


Let ξ be a character modulo c where q_1q_2 | c. The finite Fourier transform of (a,c) is

    S_χ_1,χ_2(ξ) = 
    ∑_a  c 
     (a,c) = 1(a,c) ξ(a)=
    φ(c)/(π i)^2
    L(1,(ξχ_2)^⋆) L(1,ξ^⋆χ_1)
    g_χ_1,χ_2(ξ;c)    if ξχ_1(-1) = -1
    
    0    if ξχ_1(-1) = 1,

where g_χ_1,χ_2(ξ;c) is as defined in (<ref>).



Substituting with (<ref>) into S_χ_1,χ_2(ξ) and setting t ≡ ar (mod c), we have

    S_χ_1,χ_2(ξ) =
    ∑_a  c 
     (a,c)=1  ∑_r,t  c 
     t ≡ ar  cχ_2(r)B_1(r/c)B_1,χ_1(t/c/q_1)ξ(a).


We use Lemma <ref> to replace the condition t ≡ ar in (<ref>).  Because (a,c)=1, we have ψ(ar/c/d)=ψ(a)ψ(r/c/d). This substitution separates the variables:

    ∑_d | c1/φ(d)∑_ψ d ( ∑_a  c 
     (a,c) = 1ψξ(a))
    (∑_r  cχ_2(r)ψ(r/c/d)B_1(r/c) ) ·
    
    (∑_t  cψ(t/c/d)B_1,χ_1(t/c/q_1) ) -.3cm.

Consider the sum over a.  The character ψξ is principal exactly when ψ^⋆ = ξ^⋆. Using Lemma <ref>, (<ref>) becomes

    φ(c)∑_d | c1/φ(d)∑_ψ d 
    ψ^⋆ = ξ^⋆ (∑_r  cχ_2(r)ψ(r/c/d)B_1(r/c) )
    (∑_t  cψ(t/c/d)B_1,χ_1(t/c/q_1) ) -.3cm.


If q(ξ) | d, then there is exactly one character ψ modulo d such that ψ^⋆ = ξ^⋆, namely ξ^⋆χ_0,d. If q(ξ) ∤ d, then there is no such character. 

Therefore, we may change the double sum over d and ψ to a single sum over d as shown

    ∑_d | c∑_ψ d 
    ψ^⋆ = ξ^⋆ ⟶∑_d | c 
     d ≡ 0 q(ξ),

where the character ψ corresponding to d in the right-hand sum is ξ^⋆χ_0,d. 

The sum over r is

    ∑_r  cχ_2(r)ψ(r/c/d)B_1(r/c)
    = χ_2(c/d) ∑_r  dχ_2(r)ψ(r)B_1(r/d) -.2cm.

We may assume that q_2 and c/d are coprime. Therefore q_2 | d, which implies that χ_2ψ is a character modulo d. Applying Lemmas <ref> and <ref> to the sum over r in (<ref>) and the sum over t in (<ref>), respectively, completes the proof.


To prove Theorem <ref>, apply Parseval's formula

    ∑_a  c 
     (a,c) = 1|(a,c)|^2 =
    1/φ(c)∑_ψ c|∑_a  c 
     (a,c) = 1(a,c) ψ(a) |^2 -.3cm.

The result follows immediately from substitution using Theorem <ref>.
















§ PROOF OF THEOREM <REF>


We prove Theorem <ref> by obtaining the upper bound and lower bounds individually. In this section, χ_1 and χ_2 are nontrivial primitive characters modulo q_1 and q_2, respectively, such that χ_1χ_2(-1) = 1, and q_1q_2 | c.



 §.§ Upper bound



For every ϵ > 0, we have

    ∑_a  c 
     (a,c) = 1|(a,c)|^2
    ≪_ϵ
    q_1 c^2+ϵ.




It is well known (see <cit.>) that there exists some K>0 so that for any character χ modulo q, we have

    | L(1,χ)|≤ K log q.

From applying this bound to (<ref>), it follows that

    ∑_a  c 
     (a,c) = 1|(a,c)|^2
    ≤
    K^4 log(c)^4 φ(c) ∑_ψ c 
    ψχ_1(-1)=-1| g_χ_1,χ_2(ψ;c)|^2.

We now bound the absolute value of g as defined in (<ref>). Using the triangle inequality and that q(ψχ_2) ≤ c, we have

    | g_χ_1χ_2(ψ;c)|^2
    ≤ q_1 c q(ψ)3pt∑_d | c 
     d ≡ 0 q(ψ)1/φ(d)| ((ψχ_2)^⋆μ∗ 1)(d)|| (χ_1 ∗μψ^⋆)(d/q(ψ))|^2 -.4cm.

The convolutions are bounded by the divisor function:

    | ((ψχ_2)^⋆μ∗ 1)(d) |≤∑_k | d|μ(k)  (ψχ_2)^⋆(k) |
    ≤σ_0(d)
    ≤σ_0(c),

where σ_k(n) = ∑_d| n d^k is the sum of divisors function. Likewise,

    | (χ_1 ∗μψ^⋆)(d/q(ψ)) |≤∑_k| d/q(ψ)|χ_1(d/k q(ψ)) μ(k)ψ^⋆(k) |
    ≤σ_0(d/q(ψ))
    ≤σ_0(c).

For each ϵ > 0, we have the bound σ_0(c) ϵ  c^ϵ for all positive integers c. Similarly, we have φ(d) ϵ d^1-ϵ.

Substituting these bounds into (<ref>) then using that d ≥ q(ψ), we find that the terms inside the sum over d are all at most c^ϵ/q(ψ). The sum contains at most σ_0(c) terms, so, in all,

    | g_χ_1,χ_2(ψ;c)|^2
    ≪_ϵ q_1 c^1+ϵ/q(ψ) .


Inserting (<ref>) into (<ref>), gives

    ∑_a  c 
     (a,c) = 1|(a,c)|^2
    ≪_ϵ
    q_1 φ(c) log(c)^4 ∑_ψ cc^1+ϵ/q(ψ)≪_ϵ
    q_1 c^2+ϵ∑_ψ c1/q(ψ).

We reorder the sum over ψ by its possible conductors. The number of characters modulo c with conductor d is at most φ(d), so

    ∑_ψ c1/q(ψ)≤∑_d| cφ(d)/d≤σ_0(c) ≪_ϵ  c^ϵ.

Inserting (<ref>) into (<ref>) completes the proof.










 §.§ Lower bound


We first prove some lemmas on primitive characters.  Let φ^⋆(n) denote the number of primitive characters modulo n. For n≥ 1 and p a prime, we have φ^⋆(p^n) = φ(p^n) - φ(p^n-1). Explicitly,

    φ^⋆(p^n) = 
        p^n (1-1/p)^2       if  n > 1
    
        p - 2                                  if  n = 1.



There are at least φ^⋆(p^n)/2 - 1 primitive characters with a given parity modulo p^n.


 If we let ∑^⋆ denote summation over primitive characters, then the sum

    ^⋆∑_χ p^n1-χ(-1)/2

counts the number of odd primitive characters modulo p^n. To finish the proof, we distribute the sum and use equation (3.8) of <cit.>, which states that

    ^⋆∑_χ qχ(m) =
    
    0      if  (m,q) > 1
    ∑_d | m-1 
     d | qμ(d) φ(q/d)      otherwise.

To count the number even primitive characters, we use the sum

    ^⋆∑_χ p^n1+χ(-1)/2

and apply (<ref>) again.












Let p be a prime, ξ be a character modulo p^k, and n≥ k. For each of the following three conditions and any ϵ > 0, there exists K_ϵ > 0 so that the number of primitive characters ψ modulo p^n with a given parity and which satisfy that condition is bounded below by K_ϵ p^n(1-ϵ):

    
  * ψξ is primitive, where n > k.
    
  * ψξ is primitive, where p > 3.
    
  * q(ψξ) ≥ p^n-1 for p^n ≠ 3, 4, 8.



We first prove the desired bound for all three conditions when n > k. In this case, ψξ is primitive for every primitive character ψ modulo p^n. So Lemma <ref> shows that there are φ^⋆(p^n)/2 - 1 characters that satisfy the chosen condition. Inspection of (<ref>) proves the lemma in this case.

Now suppose that n = k. To combine the proofs for parts 2 and 3, let m ∈{0,1}. We count the number of primitive characters of the given parity that do not satisfy the condition. If q(ψξ) < p^n-m, then ψ = ψ'ξ for some character ψ' modulo p^n-m-1. There are φ(p^n-m-1) such characters. We separate the cases n-m > 1 and n-m = 1.

If n-m > 1, exactly half of the characters modulo p^n-m-1 characters make the product ψξ have the desired parity. Subtracting these characters from the total number of primitive characters modulo p^n with the same parity, we find that there are at least 1/2(φ^⋆(p^n) - φ(p^n-m-1)) - 1 suitable primitive characters.

A straightforward calculation reveals that for n-m > 1,

    φ^⋆(p^n) - φ(p^n-m-1) = p^n(1-1/p)^2 - p^n-m-1(1-1/p).

Inspection of the case m=0 proves part 2, and inspection of the case m=1 proves part 3 with the exception of the case p^n = 16. By directly considering the group of Dirichlet characters modulo 16, we see that there is at least one primitive character that satisfies the conditions of part 3.

Now suppose that n-m = 1, so that p^n-m-1 = 1. There is at most one character ψ' so that ψξ has the desired property, so there are 1/2ϕ^⋆(p^n) - 2 suitable primitive characters. As before, inspection proves parts 2 and 3 for p^n ≠ 16. The remaining case is proved in the same way as before.



Part 3 of Lemma <ref> holds for p^n = 8 in the case that ψξ is odd.




For every ϵ > 0, we have

    ∑_ a  c 
     (a,c) = 1|(a,c)|^2
    ≫_ϵ q_1 c^2-ϵ-.1cm.




If χ is a real character modulo q | c, then Siegel's lower bound (see <cit.>) gives | L(1,χ) |ϵ q^-ϵ. If χ is complex, then we have the stronger result | L(1,χ) | (log q)^-1 (see <cit.>). In either case, | L(1,χ) |ϵ c^-ϵ.


We bound the second moment below by restricting the sum over ψ in (<ref>) to primitive characters:

    ∑_ a  c 
     (a,c) = 1|(a,c)|^2
    ≫_ϵ
    c^1-ϵ^⋆∑_ψ c 
    ψχ(-1) = -1| g_χ_1,χ_2(ψ;c)|^2 -.1cm.

Since ψ is primitive, q(ψ) = c and the sum over d in (<ref>) has only the term where d=c:

    ^⋆∑_ψ c 
    ψχ_1(-1) = -1| g_χ_1,χ_2(ψ;c)|^2
    = cq_1/φ(c)^2^⋆∑_ψ c 
    ψχ_1(-1) = -1
        q(ψχ_2) |∑_k | cμ(k) (ψχ_2)^⋆(k) |^2 -.4cm.


Heuristically, we would like to pick ψ modulo c so that ψχ_2 is primitive modulo c. Then q(ψχ_2) = c and k must be 1, leading to a direct lower bound. There are, however, a few problematic cases where no such ψ exists. Since there is only one primitive character modulo 3 and modulo 4, we cannot pick such a ψ when 3  c or 4 c. We separate these problematic cases by factoring c.

Suppose that c has factorization 2^α_23^α_3c' and q_2 has a factorization 2^β_23^β_3q_2', where c' and q_2' are coprime to 6. For ease of notation, set c_2 = 2^α_2 and c_3 = 3^α_3. Write χ_2 and ψ as products of primitive characters ξ_2ξ_3ξ' and ψ_2ψ_3ψ' corresponding to these factorizations.

For the time being, suppose that c_2 > 4, c_3 > 3, and c' > 1. The following method will require slight modification in the complementary cases. By positivity, the sum over ψ in (<ref>) is bounded below by

    ^⋆∑_ψ_2  c_2 
     q(ψ_2ξ_2) ≥ c_2/2 
    ψ_2ξ_2(-1) = -1^⋆∑_ψ_3  c_3 
     q(ψ_3ξ_3) ≥ c_3/3 
    ψ_3ξ_3(-1)=-1^⋆∑_ψ'  c' 
    ψ'ξ'  is primitive
    ψ'ξ'(-1)=-1
    q(ψχ_2) |∑_k | cμ(k)(ψχ_2)^⋆(k) |^2.

If we set
h(ψ,ξ; k,l) = q(ψξ)  (ψξ)^⋆(k) (ψξ)^⋆(l),
then (<ref>) factors as

    ∑_ k_2, l_2 | c_2 
     k_3, l_3 | c_3 
     k', l' | c'μ(k_2k_3k')μ(l_2l_3l') 
    7pt ^⋆∑_ψ_2  c_2 
     q(ψ_2ξ_2) ≥ c_2/2  
    ψ_2ξ_2(-1)=-1
        h(ψ_2,ξ_2;k_2k_3k',l_2l_3l')·
    
    7pt ^⋆∑_ψ_3  c_3 
     q(ψ_3ξ_3) ≥ c_3/3 
    ψ_3ξ_3(-1)=-1 
        h(ψ_3, ξ_3; k_2k_3k', l_2l_3l')7pt^⋆∑_ψ'  c' 
    ψ'ξ'  is primitive
    ψ'ξ'(-1)=-1
        h(ψ', ξ'; k_2k_3k', l_2l_3l')-.5cm.


Using Lemma <ref>, the assumption that c_2 > 4, c_3 > 3, and c' > 1 guarantees that each of these sums is nonempty. Since c_2 > 4, we know that q(ψ_2ξ_2) is even.  But k_2 and l_2 are both powers of 2, so each term in the sum over ψ_2 in (<ref>) vanishes unless k_2 = l_2 = 1.  Similar considerations for the other two sums yield that k_3 = l_3 = 1 and k' = l' = 1.

Using that h(ψ,ξ;1,1) = q(ψξ) and the restrictions q(ψ_2ξ_2)≥ c_2/2 and q(ψ_3ξ_3)≥ c_3/3, we bound (<ref>) below by

    c_2c_3c'/67pt ^⋆∑_ψ_2  c_2 
     q(ψ_2ξ_2) ≥ c_2/2 
    ψ_2ξ_2(-1)=-1
        1 7pt ^⋆∑_ψ_3  c_3 
     q(ψ_3ξ_3) ≥ c_3/3 
    ψ_3ξ_3(-1)=-1
        1 7pt^⋆∑_ψ'  c' 
    ψ'ξ'  is primitive
    ψχ_1(-1)=-1
        1 -.5cm.

Parts 2 and 3 of Lemma <ref> show that the product of sums is bounded below by c^1-ϵ, so (<ref>) is bounded below by q_1 c^2-ϵ. Combining this bound with (<ref>) finishes the proof for this case.

The proof of the remaining cases proceed similarly after modifying the parity conditions on the sums in (<ref>). Recall that q_1q_2 | c. If c' = 1, then either c_2 > 2^β_2 or c_3 > 3^β_3. Change the restriction on the sum over ψ_3 to ψ_3ξ_3(-1)=1. The same steps as before yield that k_2=l_2=k_3=l_3=1. Now the bound q_1 c^2-ϵ follows from parts 1 and 3 of Lemma <ref>.

If c_2 ≤ 4, then either ψ_2 = ξ_2 or 4 ∤ q_2. Suppose that ψ_2 = ξ_2. Factor the sum over ψ in (<ref>) as a sum over ψ_2, ψ_3, and ψ'. The sum over ψ_2 is bounded below by c_2/4, so (<ref>) is again bounded below by q_1 c^2-ϵ. On the other hand, if 4 ∤ q_2, then factor c as c_3c' and use similar arguments to the ones employed above. The case c_3 ≤ 3 is nearly identical.




Acknowledgements 

This research was conducted at the 2019 REU hosted at Texas A&M University and supported by NSF grant DMS-1757872. The authors thank Wei-Lun Tsai for his Sage advice and Professor Matthew Young for his support and guidance throughout the project.



abbrv

