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$
8
  • $\begingroup$ You might as well take that $P_n$ outside the $\sum$. $\endgroup$ 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$ 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$ 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$ 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$
5
  • 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$ 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$ 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$ 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$ 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$
10
  • $\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$ 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$ 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$ 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$ 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.