A question regarding simultaneous congruences

Question

I am not sure if this problem is of the appropriate difficulty for math overflow, but here it is.

Suppose we are considering pairs $(x,y)$ with $1 \leq x,y \leq p-1$ for some prime $p$. As points over $\mathbb{F}_p^2$, we can define the usual projective equivalence relation where we consider $(x,y)$ and $(x', y')$ to be equivalent if there exists non-zero $\rho \in \mathbb{F}_p$ such that $(x,y) \equiv (\rho x', \rho y') \pmod{p}$. It is easy to show that every point $(x,y)$ with $1 \leq x,y \leq p-1$ is equivalent to $(1, z)$ for some $z$.

My question is, for a given $p$, how many pairs $(x,y)$ (as above) are equivalent to a point of the form $(u,v)$, where $1 \leq u, v < \sqrt{p}$? It is not true that all pairs work for every $p$. For example, if $p = 11$ and $(x,y) = (3,5)$, then $3\rho \in [1, 3]$ for $\rho = 1, 4, 8$. However, $5\rho \in [1,3]$ for $\rho = 5,7,9$, and these two sets have empty intersection. Hence $(3,5)$ is not equivalent to a point of the form $(u,v)$ with $1 \leq u,v \leq 3$.

Can anything useful be said? I am interested to know, ideally, conditions to ensure that $(x,y)$ is equivalent to a point in the box $[1, \sqrt{p}) \times [1, \sqrt{p})$ and if this is not available, an estimate for the size of the set of exceptions.

Thanks for any insights.

Answer 1

The size of the exceptional set is $\Omega(p^2)$ and indeed, there are at most $\frac6{\pi^2}(1+o(1))p^2$ pairs, projectively equivalent to a point inside the square $Q:=[1,N]\times[1,N]$, where $N=\lfloor\sqrt p\rfloor$. To see this, notice that if a point from $Q$ is an integer multiple of another point from $Q$, then the two points determine the same equivalence class. Hence, the number of classes, determined by the points of $Q$, does not exceed the number of points of $Q$ with co-prime coordinates, and this number is known to be $\frac6{\pi^2}(1+o(1))N^2$ as $N\to\infty$. Finally, every class contains exactly $p-1$ points $(x,y)\in{\mathbb F}_p$, totalling to at most $\frac6{\pi^2}(1+o(1))N^2(p-1)=\frac6{\pi^2}(1+o(1))p^2$ points, equivalent to a point from $Q$.

Answer 2

That's a very interesting problem. If one restricts to initial point $(x,1)$, its like a generalization of the question of points $(x,y) \in (\mathbb{F}_p)^2$ so that $xy\equiv 1 \bmod p$ with $(x,y)$ in certain regions of $[1,p]^2$. There's some relevant info on that in the comments at the question "Small residue class with small reciprocal" (Small residue classes with small reciprocal) where $x,y$ are both restricted. Based on that question you can get $(x,1)$ equivalent to a point in the box $[1,p^{3/4}]^2$ with $x \in [1,p^{3/4}]$. On the general question of points $(x,y)\in (\mathbb{F}_p)^2$ for curves satisfying certain conditions with $(x,y)$ in certain regions of $[1,p]^2$, there seems to be limitations imposed by lower bounds on "discrepancy" (after the curves are suitably normalized). I do not know about lower bounds on discrepancy, but there are upper bounds on discrepancy, by Granville, Shparlinski and Zaharescu:

A. Granville, I. E. Shparlinski, A. Zaharescu, On the Distribution of Rational Functions Along a Curve over $\mathbb{F}_p$ and Residue Races, J. Number Theory, vol 112 (2005), 216--237.

In your problem, if restricted to initial point $(x,1)$, you are asking if there is some $a \in [1,\sqrt{p}]$ so that there is a solution $(x,y)$ on the curve $xy\equiv a \bmod p$ where $x \in X=\mbox{set determined by the conditions you might want to specify}$ but $y \in [1,\sqrt{p}]$ so that $(x,1)$ is equivalent to $(a,y)$. For fixed $a$, if $|X|\sqrt{p}/p^2$ compares favourably with the upper bounds on discrepancy mentioned, I think you get a solution, and varying $a$ in the given range gives more freedom. Sorry if I've strayed a bit from your question!