Given $n\in\Bbb N$ is there an $a_n\in\Bbb N$ such that for every $a>a_n$ there are two distinct integers $0<b<c<a$ such that $b^i\bmod a,c^i\bmod a\in(\sqrt a,\sqrt a\log a)$ for every $i\in\{1,\dots,n\}$?
If so what is minimum such $a$?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Could you prove this for $n=2$? Is it true that if $m$ is large enough, then there are at least two (distinct) elements $b\in{\mathbb Z}_m$ such that both $b$ and $b^2$ belong to $(\sqrt m,\sqrt m\log m)\pmod m$? Have you tried using exponential sums to prove this? $\endgroup$– SevaFeb 14, 2016 at 20:50
-
$\begingroup$ @Seva I am not familiar with exp sums. $\endgroup$– TurboFeb 14, 2016 at 20:58
-
$\begingroup$ Ok, still, how about $n=2$? $\endgroup$– SevaFeb 14, 2016 at 20:59
-
1$\begingroup$ I think $n=2$ is fine, just take $b:=[\sqrt{a}]+1$ and $c:=[\sqrt{a}]+2$. $\endgroup$– GH from MOFeb 14, 2016 at 22:19
-
2$\begingroup$ BTW I find this question quite interesting. I am surprised by the lack of upvotes. $\endgroup$– GH from MOFeb 14, 2016 at 22:25
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
8
This is only a heuristic, but perhaps it can be made rigorous with some effort (using Weil's bound etc).
I write $m$ instead of your $a$. Let $I:=(\sqrt m,\sqrt m\log m)\pmod m$. You want to show that there are at least two distinct values of $b\in{\mathbb Z}_m$ such that $b,\dotsc,b^n\in I$. The number of such $b$ is $$ \frac1{m^n} \sum_{x_1,\dotsc,x_n\in I} \sum_{u_1,\dotsc,u_n\in{\mathbb Z}_m} \sum_{b\in{\mathbb Z}_m} e^{ \frac{(b-x_1)u_1+\dotsb+(b^n-x_n)u_n}{m} }. $$ The main term obtained for $u_1=\dotsb=u_n=0$ is $|I|^n/m^{n-1}$, which is of the order of magnitude $m^{1-n/2}(\log m)^n$. This is a small number for $n\ge 3$ and $m$ large, and it is thus plausible to expect that in this case you cannot (in general) find even one single $b\in{\mathbb Z}_m$ with the property in question.
-
$\begingroup$ I was thinking of similar conclusion on the way here in my car. I thought it is impossible for $n\geq 3$. I did not know this exp sum trick. So if this main term is small then it is definitely impossible to have such pairs of b or just heuristically? Can we make this definite? Also could you show why main term is as you calculated? $\endgroup$– TurboFeb 15, 2016 at 9:07
-
$\begingroup$ @Turbo: calculating the main term is a triviality, just plug in $u_1=\dotsb =u_n=0$. The non-trivial thing is to estimate the remainder term, which is the rest of the sum. If it turns out to be smaller in absolute value than the main term, then yes, it is definitely impossible to find $b$ as you want. $\endgroup$– SevaFeb 15, 2016 at 9:41
-
$\begingroup$ here in this problem is remainder computation hard? is this exp sum kind of general trick at some 'non-trivial' things? $\endgroup$– TurboFeb 15, 2016 at 10:29
-
$\begingroup$ also conversely what you would have expected if say up to $n=40$ we could 'definitely' expect such pairs? $\endgroup$– TurboFeb 15, 2016 at 10:31
-
$\begingroup$ @Turbo: one cannot say whether it is hard without actually trying, for which unfortunately I don't have time now. Maybe, it is easy. Anyway, this is not just a "trick"; dating back to Gauss, exponential / character sums form is a rich area with many famous mathematicians involved and lots of top-rate research done on it. And, I don't understand your question starting with "also conversely". $\endgroup$– SevaFeb 15, 2016 at 10:34