# A conjecture based on Wilson's theorem

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}$$

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.

• You might as well take that $P_n$ outside the $\sum$. Commented Dec 7, 2015 at 11:26
• 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$. Commented Dec 7, 2015 at 11:29
• 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.
– YCor
Commented Dec 7, 2015 at 11:46
• 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}$. Commented Dec 7, 2015 at 11:58
• 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$. Commented Dec 7, 2015 at 12:05

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.

• How can you get $O(\sqrt{p}\log p)$? I can prove asymptotic formula only with $O(\sqrt{p}\log^2 p)$. Commented Dec 10, 2015 at 2:20
• You are right, I was thinking in one dimension. I corrected the error term to $\mathcal{O}(\sqrt{p}\log^2 p)$. Commented Dec 10, 2015 at 22:08
• 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. Commented Dec 12, 2015 at 4:49
• @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).$ Commented Dec 14, 2015 at 12:34
• @martin Thank you for calculations, probably $O(\sqrt p\log p)$ is a right order for error term. Commented Dec 14, 2015 at 12:41

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$ ).

• 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)$$? Commented Dec 8, 2015 at 18:51
• Yes. But it must be $O(p_n^{5/2}\log^2p_n)$ instead of $O(p_n^{5/2})$. Commented Dec 9, 2015 at 2:12
• 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. Commented Dec 9, 2015 at 3:08
• @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). Commented Jan 29, 2018 at 11:25
• @JoseBrox I applied this technique in Frobenius problem, see 1 and 2. Reduction of Frobenius problem to a lattice proble is described here. Commented Feb 2, 2018 at 8:16