24
$\begingroup$

In a recent article, Emmanuel Lecouturier proves a generalization of the following surprising result: for a Mersenne prime $N = 2^p - 1 \ge 31$, the element $$ S = \prod_{k=1}^{\frac{N-1}2} k^k $$ is a $p$-th power modulo $N$, and observed that he did not know an elementary proof. Neither do I.

Numerical experiments suggest that $s_p$ is actually a $6p$-th power modulo $N$. I can't even see why it is a quadratic residue, i.e., why the following result (not proved in the article cited) should hold: $$ T = \prod_{k=1}^{\frac{N+1}4} (2k-1) $$ is a square mod N.

For arbitrary primes $N \equiv 3 \bmod 4$, the following seems to hold: $$ \Big(\frac{T}{N} \Big) = \begin{cases} - (-1)^{(h-1)/2} & \text{ if } N \equiv 3 \bmod 16, \\ - 1 & \text{ if } N \equiv 7 \bmod 16, \\ (-1)^{(h-1)/2} & \text{ if } N \equiv 11 \bmod 16, \\ + 1 & \text{ if } N \equiv 15 \bmod 16, \end{cases} $$ where $h$ is the class number of the complex quadratic number field with discriminant $-N$. This suggests a possible proof using L-functions (i.e. using methods in (Congruences for L-functions, Urbanowicz, K.S. Williams) and explains the difficulty of finding an elementary proof.

My questions:

  1. Is this congruence for $(T/N)$ known?
  2. How would I start attacking this result using known results on L-functions?
$\endgroup$
3
  • 4
    $\begingroup$ I think you mean to have $(h-1)/2$ in the exponents instead of $h$. If $N \equiv 3 \pmod{4}$, the class number of $\mathbb{Q}(\sqrt{-N})$ is odd. $\endgroup$ Feb 12, 2016 at 22:23
  • $\begingroup$ I liked your formula for $(T/N)$ a lot, and I provided a proof below. $\endgroup$
    – GH from MO
    Feb 13, 2016 at 3:56
  • $\begingroup$ the Lucas-Lehmer test suggests that $3$ is a generator of $(\mathbb{Z}_N,\times)$, if you suppose it is, isn't $\prod_{k \le (N-1)/2} k^k$ simplified ? $\endgroup$
    – reuns
    Feb 23, 2016 at 2:26

2 Answers 2

22
$\begingroup$

1. First we show that $$\left(\frac{T}{N}\right) = \begin{cases} - (-1)^{(h-1)/2} & \text{ if } N \equiv 3 \bmod 16, \\ (-1)^{(h-1)/2} & \text{ if } N \equiv 11 \bmod 16. \\ \end{cases}$$ Consider the sets $$A_0:=\{1,2,\dots,\tfrac{N-1}{2}\},\quad A_1:=\{1,3,\dots,\tfrac{N-1}{2}\},\quad A_2:=\{2,4,\dots,\tfrac{N-3}{2}\},$$ $$ A_3:=\{1,2,\dots,\tfrac{N-3}{4}\},\quad A_4:=\{\tfrac{N+1}{4},\tfrac{N+5}{4},\dots,\tfrac{N-1}{2}\}.$$ Consider also the corresponding character sums $$S_i:=\sum_{a\in A_i}\left(\frac{a}{N}\right),\qquad i=0,1,2,3,4.$$ Modulo $N$, we have $2A_3=A_2$ and $-2A_4=A_1$. Therefore, $S_3=-S_2$ and $S_4=S_1$, and hence $S_1-S_2=S_3+S_4=S_0$. But also $S_1+S_2=S_0$, hence $S_1=S_0$ and $S_2=0$. On the other hand, it is known that $S_0=3h$, see e.g. Theorem 70 in Fröhlich-Taylor: Algebraic number theory. This means that $S_1=3h$, i.e. the number of quadratic nonresidues in $A_1$ equals $$ n=\frac{N+1}{8}-\frac{3h}{2}=\frac{N+5}{8}-2h+\frac{h-1}{2}.$$ We conclude $$ \left(\frac{T}{N}\right)=(-1)^n=(-1)^{(N+5)/8}(-1)^{(h-1)/2}. $$ This is the claimed formula (with Jeremy Rouse's correction).

2. Now we show that $$\left(\frac{T}{N}\right) = \begin{cases} - 1 & \text{ if } N \equiv 7 \bmod 16, \\ + 1 & \text{ if } N \equiv 15 \bmod 16. \end{cases}$$ We proceed as before, but this time we get $S_3=S_2$ and $S_4=-S_1$, so that $S_2-S_1=S_3+S_4=S_0$. Together with $S_2+S_1=S_0$, this yields $S_1=0$ and $S_2=S_0$. Hence the formula for $n$ simplifies to $n=(N+1)/8$, and we conclude $$\left(\frac{T}{N}\right)=(-1)^n=(-1)^{(N+1)/8}.$$

$\endgroup$
19
$\begingroup$

I answer only for the $3$-part of your question (I have to think more for the $2$-part).

Let $N$ be a prime $\equiv 1 \text{ (mod } 3\text{)}$. Let $\text{log} : (\mathbf{Z}/N\mathbf{Z})^{\times} \rightarrow \mathbf{F}_3$ be a discrete logarithm. We have the following identity: $$ \sum_{k=1}^{\frac{N-1}{2}} k \cdot \log(k) \equiv \frac{-\log(2)}{8} \cdot \frac{N-1}{3} \text{ (mod } 3\text{)}$$

The idea is to rewrite the left hand side as a sum over $(\mathbf{Z}/N\mathbf{Z})^{\times}$ in terms of Bernoulli polynomials (which, I think, is an old idea of my advisor Loïc Merel). The proof is the following (essentially Lemme $11$ of my preprint). Let $f : \mathbf{R} \rightarrow \mathbf{\mathbf{R}}$ be the $1$-periodic function defined by $f(x) = x$ if $x \in [0,\frac{1}{2}]$, $f(\frac{1}{2}) = \frac{1}{4}$ and $f(x)=0$ if $x \in ]\frac{1}{2},1[$. Let $E(x)$ be the integer part of $x$. Let $\overline{B_2}(x) = (x-E(x))^2-(x-E(x))$ and $\overline{B}_1(x) = (x-E(x))-\frac{1}{2}$ (except that $\overline{B}_1(0):=0$) be (essentially) the second and first periodic Bernoulli functions respectively. Then we have : $$f(x) = \frac{1}{4}\cdot \overline{B}_2(2x) - \overline{B}_2(x) + \frac{1}{2}\cdot \overline{B}_1(x-\frac{1}{2}) $$ (to find such identities systematically, it is convenient to compute the Fourier coefficients of $f$ and remark that the Bernoulli polynomials have nice Fourier coefficients).

Then we find : $$\sum_{k=1}^{\frac{N-1}{2}} k\cdot \log(k) \equiv \sum_{k \in (\mathbf{Z}/N\mathbf{Z})^{\times}} f(\frac{k}{N})\cdot \log(k) \text{ (mod } 3\text{)}$$ which you can simplify greatly with the Bernoulli functions (the $\log(2)$ comes from $2x$ inside $\overline{B_2}(2x)$).

In particular if $N \equiv 1 \text{ (mod } 9\text{)}$ then your $S$ is a $3$-rd power. If $N = 2^p-1 \geq 31$ is a Mersenne prime , then $\log(2) \equiv 0 \text{ (mod } 3\text{)}$ since $\log(2^p) \equiv p\log(2) \equiv0 \text{ (mod } 3\text{)}$ and $p>3$.

Although I didn't state it, I think I can also prove the following regarding the $3$-th power part: if $N = a^2-ab+b^2$ is a prime $\equiv 1 \text{ (mod } 9\text{)}$ then $b^{-2}\cdot(ab^2+ba^2)$ is a $3$-rd power modulo $N$. It follows from the same methods as in the preprint.

$\endgroup$

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.