Skip to main content
2 of 4
added 149 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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^2}\right)$$ is $$2\sum_{x^2 = D \; mod \;n \atop 2x<n}\cos\left(\frac{hx}{n^2}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 two 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]$

enter image description here

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

perhaps a near extreme is for $x$ about $\frac{3\sqrt{p}}2$, but that might be true (if at all) only for primes of the form $(2t)^2+1$ with $x=3t.$

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104