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:

*

*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$.


*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).
 A: 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).
A: 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$.
