Let $\chi$ be a primitive Dirichlet character of conductor $q$. I want to compute numerically $$G(k)=\sum_{n\bmod q}\chi(n)e^{2\pi i n(n-k)/(2q)}$$ for all $k$ with $0\le k<2q$ with $k\equiv q\pmod2$ (thanks to this last condition the sum $G(k)$ is well defined). I have two questions:

  1. For now I compute these values in a naive way, so using $q*q$ steps (of course precomputing the $2q$th roots of unity). Is there a better method (even reducing to $q^2/2$ steps would be nice)? Imagine $q=10^5$ or $q=10^6$.

  2. When $q$ is not prime, $G(k)$ is often equal to $0$. For instance if $p$ is a prime congruent to $3$ mod 4 dividing $q$ and $k$, it seems that $G(k)=0$, at least for quadratic characters (but I am interested in all characters). My question is: give a necessary and sufficient condition for $G(k)=0$ (sufficient would already be nice).

  • 1
    $\begingroup$ Do you want to quickly evaluate for a single $k$, or all $k$ at once? If the latter, this is an evaluation of a polynomial at the the roots of unity, so you could use FFT. $\endgroup$
    – Aurel
    Jan 24 at 13:47
  • $\begingroup$ @Aurel: yes all at once, so FFT is conceivable. $\endgroup$ Jan 24 at 15:58
  • 2
    $\begingroup$ I realised afterwards that a complexity of $O(q^2)$ could only mean computing all the $G(k)$. Then the FFT version should be $O(q\log q)$. $\endgroup$
    – Aurel
    Jan 24 at 16:03

2 Answers 2


For the second question, if $p$ is an odd prime dividing $q$, $p$ divides $k$ with at least the multiplicity with which it divides $q$, and $\chi_p(-1)=-1$, where $\chi_p$ is the $p$-adic part of $\chi$, then $G(k)=0$.

This generalizes what you wrote in the $\chi$ quadratic case. In that case, the multiplicity which which $p$ divides $q$ is always one, and $\chi(-1)=-1$ if and only if $p$ is congruent to $3$ mod $4$.

Indeed, the Chinese remainder theorem gives

$$G(k)=\frac{1}{2} \sum_{n\bmod 2q}\chi(n)e^{2\pi i n(n-k)/(2q)} = \prod_{ p \mid 2q} \sum_{n \bmod p^{v_p(2q)}} \chi_p (n) e^{ 2 \pi i \lambda_p n (n-k)/ p^{v_p(2q)}}$$

where $v_p(2q)$ denotes the $p$-adic valuation of $2q$, $\lambda_p$ is the inverse of $q/ p^{v_p(2q)}$ modulo $p^{v_p(2q)}$, and $\chi_p$ is the $p$-adic part of $\chi$.

Fixing on an odd prime $p$, we see that if $k$ is a multiple of $p^{v_p(2q)}=p^{v_p(q)}$, the factor at $p$ simplifies to

$$ \sum_{n \bmod p^{v_p(2q)}} \chi_p (n) e^{ 2 \pi i \lambda_p n^2/ p^{v_p(2q)}}$$

and if $\chi_p(-1)= -1$ then the terms for $n$ and $-n$ in the sum always cancel, giving a value of $0$.

If $\chi(-1)= 1$ then we get a sum of two Gauss sums and I don't see any reason it should be zero.

In general, if $v_p(2q)=1$, the local factor is a nice complete exponential sum. For fixed $k \neq 0$ mod $p$, Katz's equidistribution theory will tell us that the sum is nonzero for a density 1 subset of characters $\chi$. This probably can be proven also for fixed $\chi$ and a density one set of values of $k$, but might be harder to prove (at least by this method - there may be a clever congruence that proves nonvanishing).

  • $\begingroup$ Thanks Will, this pretty much answers my second question (and thanks for correcting my typo in the case of quadratic characters). $\endgroup$ Jan 24 at 19:13
  • $\begingroup$ I accepted Will's answer, but am still interested in question 1, in addition to Aurel's suggestion of using FFT $\endgroup$ Jan 24 at 22:15

I might be missing something, but I believe the below gives $O(q \log q)$ to compute $G(k)$ for all $k$.

For a FFT-type solution to the first question, we write $k = 2k' + (q\bmod 2)$ (where we in particular mean the residue of $q\bmod 2$ in $\{0,1\}$), and note that

$$\exp\left(-\frac{2\pi i n(2k'+(q\bmod 2))}{2q}\right) = \exp\left(-\frac{2\pi i nk'}{q}\right)\exp\left(-\frac{2\pi i n(q\bmod 2)}{2q}\right) = \zeta_q^{-nk'}\zeta_{2q}^{-n(q\bmod 2)}.$$

We can therefore write

$$G(2k'+(q\bmod 2)) = \sum_{n\bmod q} \chi(n)\zeta_{2q}^{n^2-n(q\bmod 2)}\zeta_q^{-nk'}$$

Let $a_n = \chi(n)\zeta_{2q}^{n^2-n(q\bmod 2)}$. Then computing $G(k)$ for all $k\in [0, 2q)$ such that $k\equiv q\bmod 2$ reduces to evaluating the polynomial

$$A(x) = \sum_{n = 0}^{q-1}a_nx^n$$

at the points $\zeta_q^{-k'}$ for $k'\in [0,q)$. This can be done with the standard complex DFT. To see this, we use the exposition of the complex DFT in terms of matrix multiplications, namely that evaluating $A(x)$ on $q$ points $x_0,\dots, x_{q-1}$ is equivalent to multiplying the vector $(a_0,\dots, a_{q-1})$ by the Vandermonde matrix associated with those points, i.e. computing the product

$$ \begin{pmatrix} 1 & 1 & 1&\dots & 1\\ 1 & \zeta_q^{-1} & \zeta_q^{-2} & \dots & \zeta_q^{-(q-1)}\\ 1 & \zeta_q^{-2} & \zeta_q^{-4}&\dots & \zeta_q^{-2(q-1)} \\ \vdots & & & \ddots&\vdots\\ 1 & \zeta_q^{-(q-1)} & \zeta_q^{-2(q-1)} & \dots & \zeta_q^{-(q-1)(q-1)} \end{pmatrix}\begin{pmatrix} a_0\\ a_1\\ \vdots\\ a_{q-1} \end{pmatrix} $$

This product can be computed in $O(q\log q)$ time using standard FFT techniques. Note that the $i$th coordinate of the output is precisely $\sum_{n = 0}^{q-1} a_n \zeta_q^{-in} = \sum_{n = 0}^{q-1} \chi(n)\zeta_{2q}^{n^2-n(q\bmod 2)}\zeta_q^{-ni} = \sum_{n = 0}^{q-1} \chi(n)\zeta_{2q}^{n(n-2i-(q\bmod 2))}$, i.e. is precisely $G(2i+(q\bmod 2)) = G(k)$ for some $k\in[0, 2q)$ with $k\equiv q\bmod 2$.

  • $\begingroup$ Thank you, this is the detailed explanation of what Aurel suggested. $\endgroup$ Jan 25 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.