Arithmetic progressions modulo $p$ under the squaring map - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T19:32:24Z http://mathoverflow.net/feeds/question/54974 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54974/arithmetic-progressions-modulo-p-under-the-squaring-map Arithmetic progressions modulo $p$ under the squaring map Lavender Honey 2011-02-10T01:53:02Z 2011-02-18T18:39:45Z <p>I feel that the following problem should be known, but I'm not sure where to look for it.</p> <p>Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of residue classes coming from the first $\lfloor p \epsilon \rfloor$ integers. Let $B_p$ denote the squares (modulo $p$) of the elements of $A_p$. Then one might ask whether $$\lim_{p \rightarrow \infty} \frac{|A_p \cap B_p|}{|A_p|} =^{?} \epsilon.$$ It's true for $\epsilon = \frac{1}{2}$, but that's a degenerate case where $B_p$ can essentially be replaced by $\mathbf{F}^{\times 2}_p$, in which case the answer follows from any non-trivial upper bound on character sums (say the Polya-Vinagradov inequality). Is it true more generally?</p> http://mathoverflow.net/questions/54974/arithmetic-progressions-modulo-p-under-the-squaring-map/54989#54989 Answer by Aaron Meyerowitz for Arithmetic progressions modulo $p$ under the squaring map Aaron Meyerowitz 2011-02-10T04:56:53Z 2011-02-10T04:56:53Z <p>Based on a couple of experiments it seems very likely. There is a slight bias to be over $\epsilon$, maybe because the squares of the residues up to $\sqrt{\frac{p}{\epsilon}}$ are in the intersection and the later squares are pretty randomly scattered around. In the limit that effect goes to 0.</p> http://mathoverflow.net/questions/54974/arithmetic-progressions-modulo-p-under-the-squaring-map/54995#54995 Answer by Felipe Voloch for Arithmetic progressions modulo $p$ under the squaring map Felipe Voloch 2011-02-10T06:35:15Z 2011-02-10T06:35:15Z <p>This is a variant of a common theme. It should follow from more or less standard exponential sums estimates. The general buzzword is Erdos-Turan inequality. The answer should be yes and it might follow from the results of:</p> <p>A. Granville, I. E. Shparlinski and A. Zaharescu, On the distribution of rational functions along a curve over $\mathbb{F}_p$ and residue races, J. Number Theory, 112 (2005), 216--237.</p> <p>or C. Cobeli and A. Zaharescu, On the distribution of the $\mathbb{F}_p$-points on an affine curve in $r$ dimensions, Acta Arithmetica 99 (2001), 321--329.</p> <p>Or perhaps even earlier papers.</p>