Distribution of quadratic polynomials mod $n$ and $n^2$

Question

Suppose $n$ is odd, then both equations $x^2 = D \; mod \;n$ and $x^2 = D \; mod \;n^2$ have the same number of solutions for fixed $D$ coprime to $n$. What can be said about the relationship between the distribution of the two sets of roots? More precisely, for $h \neq 0$ can we have a reasonable upper bound for,

$$ \left|\sum_{x^2 = D \; mod \;n^2}e\left(\frac{hx}{n^2}\right) - \sum_{x^2 = D \; mod \;n}e\left(\frac{hx}{n}\right) \right| $$

Suppose $y$ is the corresponding root extension of $x$ ($mod \; n$) in $mod \; n^2$. I tried playing around with $\frac{x}{n} - \frac{y}{n^2}$, but failed to find anything useful.

Answer 1

What have you tried? An easy upper bound is $2^d$ where $d$ is the number of distinct prime factors of $n.$ Perhaps that can be improved slightly, but maybe not much. I think that for (not too small) $p$ prime and $h=1,$ one might decrease the bound from $4$ to $$2+2\cos(\frac{2\pi}{\sqrt{p}})\approx 4(1-\frac{\pi^2}{p})$$

Since the solutions come in pairs $\pm x$, your sum $$\sum_{x^2 = D \; mod \;n}e\left(\frac{hx}{n}\right)$$ is $$2\sum_{x^2 = D \; mod \;n \atop 2x<n}\cos\left(\frac{hx}{n}2\pi\right)$$ with a similar expression for $n^2$.

The number of roots is $2^d$ where $d$ is the number of distinct prime factors of $n$ so each sum is in the interval $(-2^{d-1},2^{d-1}).$ So an upper bound is $2^d.$

Here is some graphic data for the case that $n=401$ (a prime):

The smooth curve at the top is $2\cos(\frac{2\pi x}{401})$ corresponding to $D=x^2 \bmod 401$ and the jagged curve corresponds to the pair of square roots for $D$ $\bmod 401^2.$ I'll say a bit more below. The bottom graph is the absolute value of the difference which is certainly bounded by $4.$

My suggested upper bound was $4(1-\frac{\pi^2}{401})=3.9.$ As it turns out, the $8$ largest values are

$[35, 3.674818717], [183, 3.685930954], [167, 3.686713786], [28, 3.698890933],$$ [32, 3.715092914], [196, 3.725597801], [189, 3.743132538], [31, 3.758547372]$

The jagged curve is almost horizontal at first. This is $2\cos(\frac{2x\pi}{401^2})$ for $x \leq20$. Here $x^2 < 401$ so the solutions $\bmod 401^2$ are $x$ and $401^2-x.$ After that it quickly gets chaotic. At $x=31$ , so that $$D=159=961 \bmod 401$$, the smooth curve is at $2\cos(\frac{62\pi}{401})=1.78687$ and the jagged curve is at $-1.98988.$