Let us fix a positive natural number $N$. When $i$ is a natural number smaller than $N$, coprime with $N$, we let $\mu(i)$ be the unique number in $\{1, \ldots, N-1\}$ that is the multiplicative inverse of $N-i$ modulo $N$. I would like to know what is the maximum, when $i$ is in the range of the numbers from $1$ to $N-1$ that are coprime with $N$, of the function $f(i):=i+\mu(i)$.
5
-
1$\begingroup$ What about $\left(N-1\right)+\left(N-1\right)$ ? The question might be more interesting for the function $i+\mu\left(-i\right)$. $\endgroup$– darij grinbergCommented Sep 9, 2011 at 21:43
-
$\begingroup$ Sorry darij, this was what I meant. $\endgroup$– MathoverflowCommented Sep 9, 2011 at 22:03
-
$\begingroup$ I have edited the question after darij's observation. $\endgroup$– MathoverflowCommented Sep 9, 2011 at 22:05
-
6$\begingroup$ By symmetry it's $2N$ minus the minimum of $i + \mu(i)$. If we imagine that the points $(i,\mu(i))$ are randomly distributed in the square of size $N$, we expect the minimum to be of order $N / \sqrt{\phi(N)}$. Proving something like this is probably asking too much, but using upper bounds on Kloosterman sums one gets $O(N^{3/4})$ when $N$ is prime (see e.g. math.harvard.edu/~elkies/M229.09/kloos.pdf), and with some more work one can probably prove $O_\epsilon(N^{\frac34 + \epsilon})$ in general. $\endgroup$– Noam D. ElkiesCommented Sep 9, 2011 at 22:24
-
1$\begingroup$ [Indeed we shouldn't expect it to be $O(sqrt{N})$ even for $N$ prime, because that requires that $cN-1$ have a factor $O(\sqrt{N})$ for some $c = O(1)$; but $N^{1/2+\epsilon}$ might still be true.] $\endgroup$– Noam D. ElkiesCommented Sep 9, 2011 at 23:27
Add a comment
|