# Short Primitive Vectors in a Lattice in $\mathbb{Z}^2$

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

• 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$. Sep 27 '15 at 21:17
• $(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? Sep 27 '15 at 21:38
• 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. Sep 27 '15 at 21:51
• All right, this problem is interesting, I will think about it. I think your bound $n^{\frac{1}{2}+\epsilon}$ can be obtained. 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$.

$\square$

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

$\square$

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.

• 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. Sep 27 '15 at 23:18
• @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. Sep 27 '15 at 23:25
• 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. Sep 27 '15 at 23:27