Pick a random pair $(a,b)\in\mathbb Z_n^2\backslash\{0,0\}$. Denote $N_2(a,b,n)$ to be minimum $\ell_r$ norm of vector $(x,y)$ as $(x,y)$ ranges over all non-zero integral solutions to $(x,y)\equiv t(a,b)\bmod n$ where $t\in\mathbb Z$ with $0<t<n$.

Now let integers $a,b$ be of size in $(\sqrt m,m-\sqrt m)$.

Let $p_1,p_2$ be primes of similar size some integer $m$ and let $t_1$ attain $N_2(a,b,p_1)$ and $t_2$ attain $N_2(a,b,p_2)$. From Dirichlet pigeonhole we know $N_2(a,b,p_1)$ and $N_2(a,b,p_2)$ are less than $\sqrt{2m}$.

Let $t$ attain $N_2(a,b,p_1p_2)$ (note $(t,p_1p_2)=1$ need not hold while $(t_1,p_1)=(t_2,p_2)=1$ holds).

Then $N_2(a,b,p_1p_2)$ seems to be typically $m\sqrt 2$.

  1. Is it possible for $N_2(a,b,p_1p_2)$ to be smaller than $\sqrt{2m}-\mu$ if $N_2(a,b,p_1)$ and $N_2(a,b,p_2)$ are greater than $\sqrt{2m}-\mu $ at a $\mu\in(0,\sqrt{2m})$?

  2. If so what is the probability?

This is the result from Akshay Venkatesh when $n$ is prime. Then it is true as $n\rightarrow\infty$ the distribution of $N_2(a,b,n)/\sqrt{n}$ coincides with distribution of $1/\sqrt y$ where $x+iy$ is picked at random with respect to hyperbolic measure from $\{z:|z|\geq1,|\mathcal R(z)|\leq\frac12\}$.


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.

Browse other questions tagged or ask your own question.