Cross-posted from M.SE.

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

Here are my ideas so far to reduce to a character sums bound.

We want to show that the number $S(a)=\#\{ax\equiv y (n): |x|, |y| \le N, x,y$ coprime to n$\}$ is nonzero; then $N$ is an upper bound for the primitive point's size. By discrete Fourier analysis against the Dirichlet characters mod $n$,

$$S(a)=\frac{\phi(N,n)^2}{\phi(n)} + \frac{1}{\phi(n)}\sum_{\chi \ne \chi_1} \Big |\sum_{|y| \le N} \chi(y)\Big|^2 \chi(a)^{-1}.$$

Here $\phi(N,n)$ is the number of $|y|\le N$ coprime to $n$.

Applying Polya-Vinogradov to the inner sums just misses a nontrivial bound - is there any bound on these short character sums on average, twisted by $\chi(a)^{-1}$? This method seems doomed to fail because the choice of $a=1$ gives a large (positive) error term.

  • $\begingroup$ If your problem involves averaging over modulus $n$, then it might be possible to apply Large Sieve. $\endgroup$ Sep 30, 2015 at 21:06
  • $\begingroup$ Unfortunately not, I'd like it for any fixed $n$. If it helps I only need the case squarefree $n$ but I don't see a particular reason this makes the problem easier. $\endgroup$
    – Xiaoyu He
    Sep 30, 2015 at 21:12

1 Answer 1


Suppose $n=2m$ and $a=m+1$. Clearly $(a,m)=1$. Then there are no $x,y$ odd with $ax \equiv y$ mod $n$, $x<m$, $y<m$. Indeed in this case

$$y \equiv ax= mx+x \equiv m+x \mod 2m$$

Clearly this cannot be satisfied for $0<x<m$, $0<y<m$.

You can try to write the sum instead using additive characters instead and you will see this kind of obstruction as a large term coming from a single additive character.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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