24
$\begingroup$

Definitions:

Lagrange's theorem implies that for each prime $p$, the factors of $(p − 1)!$ can be arranged in unequal pairs, with the exception of $±1$, where the product of each pair $≡ 1 \pmod p$. See Wiki article on Wilson's theorem.

From the example in the link above, for $p=11$ we have

$$(11-1)!=[(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)] \equiv [-1]\cdot[1\cdot1\cdot1\cdot1] \equiv -1 \pmod{11}$$

Let the products of the pairs that $≡ 1 \pmod p$ be the multiset $A_p$, and $A_{p_n}$ the multiset for the $n$th prime.

For the above example then, $A_{p_5}=\{(2\cdot6),(3\cdot4),(5\cdot9),(7\cdot8)\}=\{12,12,45,56\}$.

Conjecture:

$$\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A_{p_n}}(k-1)}{(p_n)^3}\approx\frac18$$

where $p_n$ is the $n$th prime.

Examples:

For $p=11$ we have

$$\dfrac{11+11+44+55}{11^3}=\dfrac{1}{11}$$

For $p=997$ we have

$$\dfrac{123218233}{997^3}=\dfrac{123218233}{991026973}$$

Comments:

As @YCor noted below, the $-1$ in the $k-1$ can be removed, since its contribution tends to $0$. The conjecture can therefore be simplified to

$$\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A_{p_n}}k}{(p_n)^3}\approx\frac18$$

I have no idea whether the above statement is correct, or how to go about trying to find a proof. Any comments on the any of the above are most welcome.

$\endgroup$
  • $\begingroup$ You might as well take that $P_n$ outside the $\sum$. $\endgroup$ – barak manos Dec 7 '15 at 11:26
  • 2
    $\begingroup$ You might as well write it as $\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A}k-1}{(p_n)^3}\approx\frac18$. $\endgroup$ – barak manos Dec 7 '15 at 11:29
  • $\begingroup$ You can't say $A$ is a set, since you take multiplicities into account. Also you should denote it as $A_p$ and write $A_{p_n}$ instead of $A$ in the conjecture. $\endgroup$ – YCor Dec 7 '15 at 11:46
  • 1
    $\begingroup$ It might help to note that $\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k=2}^{n/2}k(n-k)-1}{n^3} = \frac{1}{12}$. $\endgroup$ – barak manos Dec 7 '15 at 11:58
  • 1
    $\begingroup$ With @YCor's notation, if it's reasonable to assume that $i$ and $c_i$ behave roughly independently then one would have $\frac1p \sum i c_i \approx \left(\frac1p \sum i\right) \left(\frac1p \sum c_i\right) \approx p^2/4$, so this heuristically justifies the $1/8$. $\endgroup$ – Sean Eberhard Dec 7 '15 at 12:05
35
$\begingroup$

For an integer $n$ with $1\leq n\leq p-1$, let $n^{-1}$ be the inverse of $n$ modulo $p$. It follows from Weil's bound on Kloosterman sums that for every $\epsilon>0$ the set $\{n: xp\leq n\leq (x+\epsilon) p, yp\leq n^{-1}<(y+\epsilon) p\}$ has cardinality $\epsilon^2p+\mathcal{O}(\sqrt{p}\log^2 p)$. Hence up to a relative error tending to 0 the sum in question can be replaced by an integral, that is $$ \sum_{n=1}^{p-1} n\cdot n^{-1} \sim p^3\int_0^1\int_0^1 xy\;dx\;dy = \frac{p^3}{4}. $$ (Note that the $\cdot$ on the left hand side refers to the multiplication of integers, not to modular multiplication). Here each pair $(a,b)$ with $ab\equiv 1\pmod{p}$ is counted twice, with the exception of $(1,1)$ and $(-1, -1)$, which contribute less than $p^2$. Hence up to an error $\mathcal{O}(p^2)$ the left hand side of the above expression is twice $\sum_{k\in A} k$, which proves your claim.

$\endgroup$
  • 4
    $\begingroup$ How can you get $O(\sqrt{p}\log p)$? I can prove asymptotic formula only with $O(\sqrt{p}\log^2 p)$. $\endgroup$ – Alexey Ustinov Dec 10 '15 at 2:20
  • 1
    $\begingroup$ You are right, I was thinking in one dimension. I corrected the error term to $\mathcal{O}(\sqrt{p}\log^2 p)$. $\endgroup$ – Jan-Christoph Schlage-Puchta Dec 10 '15 at 22:08
  • $\begingroup$ But your error term can be valid. In the question mathoverflow.net/questions/175822/incomplete-kloosterman-sum the error term was $O(\sqrt{p}\log p)$ indeed. In the case $f(x,y)=xy$ situation can be similar. $\endgroup$ – Alexey Ustinov Dec 12 '15 at 4:49
  • $\begingroup$ @AlexeyUstinov certainly $O(\sqrt{p}\log p)$ looks feasible: plot 1, plot 2 where first plot is $\left(\left(p_n/2\right)^3-\sum\limits_{k \in A_{p_n}}{k}\right)/\left(p_n^{5/2}\log p_n\right),$ second is $ \text{expr.} ~/\left(p_n ^{5/2}\log^{2} p_n\right).$ $\endgroup$ – martin Dec 14 '15 at 12:34
  • 1
    $\begingroup$ @martin Thank you for calculations, probably $O(\sqrt p\log p)$ is a right order for error term. $\endgroup$ – Alexey Ustinov Dec 14 '15 at 12:41
11
$\begingroup$

If $f(x,y)$ is a "good" function, then $$\sum_{xy\equiv 1\mod p}f(x,y)=\frac{1}{p}\sum_{x,y=0}^{p-1}f(x,y)-R_p[f],$$ where $R_p[f]$ is a "small" error term (see Lemma 5 here). In your case $f(x,y)=xy$, so the main term is $p^3/4.$ Usually $R_p[f]=O(p^{1/2+\varepsilon}\|f\|)$ while the main term is like $p\|f\|$. In this case error term is $O(p^{5/2+\varepsilon}).$

This observation has a lot of applications in problems connected with lattices (because bases are parametrized by equation $ad-bc=n$, so $ad\equiv n\mod b$ ).

$\endgroup$
  • $\begingroup$ thanks for the great answer! So in this case $$\left(p_n/2\right)^3-\sum\limits_{k \in A_{p_n}}{k}=\mathcal{O}\left(p_n\ ^{5/2}\right)$$? $\endgroup$ – martin Dec 8 '15 at 18:51
  • 1
    $\begingroup$ Yes. But it must be $O(p_n^{5/2}\log^2p_n)$ instead of $O(p_n^{5/2})$. $\endgroup$ – Alexey Ustinov Dec 9 '15 at 2:12
  • 1
    $\begingroup$ And this $\log$ is impotant because usually (numerically, it is not proved) normalized error term (in our case $R_p\cdot p^{-5/2}$) is gaussian i.e. unbounded. $\endgroup$ – Alexey Ustinov Dec 9 '15 at 3:08
  • 1
    $\begingroup$ @Jose Brox The "history" goes back to the theory of numerical integration and uniform distribution theory. When you replace given function $f$ by its Fourier series you'll get error term depending on Fourier corfficients of $f$ and trigonometric sums of a given net. This argument was used by Weyl in his pioneer work Über die Gleichverteilung von Zahlen mod. Eins (1916). Basic latice problem is a distribution of vectors in reduced basis. Conditions from Lemma 5 can be replaced for another ones (see the proof). $\endgroup$ – Alexey Ustinov Jan 29 '18 at 11:25
  • 1
    $\begingroup$ @JoseBrox I applied this technique in Frobenius problem, see 1 and 2. Reduction of Frobenius problem to a lattice proble is described here. $\endgroup$ – Alexey Ustinov Feb 2 '18 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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