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.

Improve this question
$\endgroup$
8
  • $\begingroup$ You might as well take that $P_n$ outside the $\sum$. $\endgroup$
    – barak manos
    Dec 7, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:05

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Alexey Ustinov
    Dec 10, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$ ).

Improve this answer
$\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, 2015 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, 2015 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, 2015 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, 2018 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, 2018 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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