Given $a,n$ coprime positive integers, let $L = \{(x,y)\in \mathbb{Z}^2, ax=y(n)\}$ be the lattice of all points satisfying $ax=y\pmod{n}$.

I want to find an order-of-magnitude bound on the shortest (minimizing say $\max(|x|,|y|)$) vector in $L$ with $x,y$ coprime. If you restrict to merely finding a nonzero vector an easy pigeonhole argument gives a bound of the form $|x|,|y|\ll\sqrt{n}$. Is this still true if we require additionally that $x,y$ are coprime? In particular note that just because $(x,y)$ is in the lattice doesn't mean $(x/g,y/g)$ is, where $g$ is their greatest common divisor - problems can occur if $g$ has common factors with $n$.

Explicitly can anyone prove the existence of a primitive point $|x|,|y|\ll n^{1/2+\varepsilon}$?

Note that if $a\ll \sqrt{n}$ then the problem is trivial by picking $(x,y)=(1,a)$. I am interested in bounds for generic $a\in (\mathbb{Z}/n\mathbb{Z})^\times$.

  • $\begingroup$ There is something wrong with your formulation. I don't think the $n$ in the error term is the same as the $n$ in the modulo. Take $a=1$ for instance. If $x\equiv y\pmod{n}$ then $x-y$ is an integer multiple of $n$. If it is non-zero (necessary if they are to be coprime) then it cannot be the case that both $x$ and $y$ are bounded in order by the square root of $n$. $\endgroup$
    – guest
    Sep 27 '15 at 21:17
  • $\begingroup$ $(1,1)$ is a solution, no? If $a$ is very small compared to $n$ then I'm happy with the solution $(1,a)$. I agree it is not immediately clear such a bound is true - can you provide an example where all the primitive points are much larger than just the shortest vectors in the lattice? $\endgroup$
    – Xiaoyu He
    Sep 27 '15 at 21:38
  • $\begingroup$ Then you are talking about a completely different problem than the one I had in mind. I thought the issue was to produce lots of primitive points on $L$ in a big box around the origin. You should make it clear for example that if $a\leq \sqrt{n}$, the problem is trivial. $\endgroup$
    – guest
    Sep 27 '15 at 21:51
  • $\begingroup$ All right, this problem is interesting, I will think about it. I think your bound $n^{\frac{1}{2}+\epsilon}$ can be obtained. $\endgroup$
    – guest
    Sep 27 '15 at 22:09

Edit: this answer inorrectly conflates multiplication and divison tables mod n so be warned that the proofs of the claims are wrong. I will edit when time permits.

For now, let me rephrase the problem in terms of a well known series of investigations in analytic number theory. I will show why $n^\frac{1}{2}$ cannot work and why I believe $n^{\frac{1}{2}+\epsilon}$ can.

Reduction: Since we are asking for coprime $x,y$ satisfying $ax\equiv y\pmod{n}$, we must also demand $(x,n)=(y,n)=1$. The reason is the following:

By Bezout, $kx+ly=1$. From the congruence, we get $$alx = 1-kx\pmod{n}$$ so $$(al+k)x\equiv 1\pmod{n} $$ so $x$ necessarily has to be invertible, same with $y$.

So the problem reduces to finding the smallest $N$ such that for every $a<n$ with $(a,n)=1$ we can find a pair $x,y$ coprime to each other and $n$, between $1$ and $N$, such that $$ax\equiv y\pmod{n} $$ or equivalently, such that $$a \equiv x^{-1}y\pmod{n}. $$

Definition: The multiplication table of size $N$, denoted $\mathcal{M}(N)$ is the $N\times N$ array with $(i,j)$ entry equal to $ij$. The mod n multiplication table $\mathcal{M}_n(N)$ is the array with $(i,j)$ entry equal to $ij\mod{n}$.

Claim: The optimal $N$ for the problem is the smallest $N$ for which $\mathcal{M}_n(N)$ has at least $\phi(n)$ distinct entries coprime to $n$.

Proof: If $a\equiv x^{-1}y$ has a solution for all $a$ coprime to $n$ then there are at least $\phi(n)$ distinct ratios and thus $\phi(n)$ distinct products coprime to $n$. Vice versa, if there are $\phi(n)$ distinct products coprime to $n$, then $a \equiv yz$ so $az^{-1}\equiv y\pmod{n}$ and if $z^{-1}$ and $y$ share common factors, we can just drop them since these factors will not be factors of $n$.


Claim: $N$ cannot be as small as $\sqrt{n}$.

Proof: Look at the $N\times N$ multiplication table. Its invertible entries are all smaller than $n$ so we can identify $\mathcal{M}_n(\sqrt{n})=\mathcal{M}(\sqrt{n})$, the integer multiplication table. The result follows now from the following two facts:

Proposition: There exists $C>0$ such that for every $n>2$, $$\phi(n) \geq C \frac{n}{\log\log{n}}.$$ This is a well known estimate for the Euler function.

Proposition: The number of distinct entries in $\mathcal{M}(\sqrt{n})$ is smaller than $\frac{n}{\log^c{n}}$ for appropriate $c>0$. This is a fairly recent result that follows from a sharper estimate of Kevin Ford's.

Combining the two theorems we see that the number of distinct entries, $\frac{n}{\log^c{n}}$, is beaten by the number of elements we demand to be distinct ($C \frac{n}{\log\log{n}}.$).


Conjecture (bold conjecture!): for every $\epsilon>0$ there exists $n_0$ such that for all $n>n_0$, the number of distinct elements in $\mathcal{M}_n(n^{\frac{1}{2}+\epsilon})$ is sufficient to beat the demands for $a$. From the reductions above we see that the conjecture is actually equivalent to your problem.

I think it is true: if we had $\mathcal{M}(n^{\frac{1}{2}+\epsilon})$ rather than the mod n version, we know there are sufficiently many entries, even coprime to $n$. Now I just need to think about the mod n reduced problem, but maybe you or some other answerer can beat me! After all, the reduction mod n does not create too many overlaps for $N$ still near $\sqrt{n}$, we just need exact control.

I need to write and prepare a midterm now, so I may take some time to update.

  • $\begingroup$ Do you mean to look at the "division table" where we take all ratios $i/j$ of things in the range? Not every $x < N$ will have multiplicative inverse $< N$ as well. $\endgroup$
    – Xiaoyu He
    Sep 27 '15 at 23:18
  • $\begingroup$ @XiaoyuHe yes I agree we need to work with the mod n division table rather than the multiplication table so my proofs of the two claims are not correct. I suspect if we work directly with the division table mod n we can get the claim, but I do not have time to think about this now. I will not delete the answer yet in case you want to think about something in there. $\endgroup$
    – guest
    Sep 27 '15 at 23:25
  • $\begingroup$ Yes, please keep the answer. It is helpful to think about the problem explicitly as the set of ratios of two intervals $[1,N]$, $[1,N]$, which reminds me of a calculation based on Kloosterman sums. I will work out the relevant details and see if that proof extends naturally to representations by $x^{-1} y$ to non-prime moduli. $\endgroup$
    – Xiaoyu He
    Sep 27 '15 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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