# Computation of modified Gauss sums

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).

• 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. Jan 24 at 13:47
• @Aurel: yes all at once, so FFT is conceivable. Jan 24 at 15:58
• 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)$. Jan 24 at 16:03

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).

• Thanks Will, this pretty much answers my second question (and thanks for correcting my typo in the case of quadratic characters). Jan 24 at 19:13
• I accepted Will's answer, but am still interested in question 1, in addition to Aurel's suggestion of using FFT 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$$.

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