5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If your problem involves averaging over modulus $n$, then it might be possible to apply Large Sieve. $\endgroup$ – i707107 Sep 30 '15 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 '15 at 21:12
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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