MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
For completeness, if you replace the condition $x \in [1, \sqrt{p})$ with $|x| \in [1, \sqrt{p})$, you do cover everything. – Hurkyl Apr 9 '12 at 17:33
up vote 8 down vote accepted

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

share|cite|improve this answer
Not only is it at most the number of coprime pairs in $[1,N]$ but indeed exactly that number. If $a/b \equiv c/d \bmod p$ then $ad-bc$ is a multiple of $p$, and $|ad-bc| \leq N^2 < p$ so $ad-bc=0$ and $a/b=c/d$. – Noam D. Elkies Apr 9 '12 at 19:12

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!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.