Theorem. Pólya-Vinogradov inequality

The number of quadratic residues in the interval \(m+[k]\) is \(\frac{k}{2} \pm \mathcal{O}(\sqrt{p}\log p)\).

In fact this is a more general fact about characters.

https://planetmath.org/PolyaVinogradovInequality

Theorem. \[|QR \cap (QR + a)| = \frac{p-3}{4}\]

proved at: https://mathoverflow.net/questions/332315/shifting-quadratic-residues

Theorem. Quadratic Gauss sum:

\[\left|\sum_{n=1}^{p} e^{2\pi i \frac{n^{2}}{p}}\right| \le \mathcal{O}(\sqrt{p}).\]

proved at: https://en.wikipedia.org/wiki/Quadratic_Gauss_sum

I also can basically get this estimate except with some polylog factors by using Pólya-Vinogradov inequality

Theorem. Weyl’s Criterion

A sequence \(x_1,x_2,\ldots\) is equidistributed iff

\[\lim_{n\to \infty} \frac{1}{n} \sum_{k=1}^{n} e^{2\pi i k x_k} = 0.\]

This is actually quite powerful. It reduces proving equidistribution to estimating a sum, specifically, showing that the sum is \(o(n)\). But estimating sums is something that seems pretty tractable.

Terry Tao also says that this is true for multi-dimensional sequences if you replace the one-dimensional \(k x_k\) with the dot product \(k\cdot x_k\).

https://mathworld.wolfram.com/WeylsCriterion.html https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/ https://en.wikipedia.org/wiki/Equidistributed_sequence

Theorem. Combining the above results we couuld get that the joint sequence of \(x, x^{2}\) is equidistributed in \(\mathbb{Z}_p\).