Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

While teaching number theory this quarter, I have come across a phenomenon which was already addressed in another MO posting, but I have new questions. Let $p$ be a prime congruent to 3 mod 4. Then an elementary refinement of Wilson's theorem says that $\frac{p-1}2!$ is congruent to $\pm 1$ mod $p$. In fact, a published result of Mordell says that it is congruent to $(-1)^{(h+1)/2}$, where $h$ is the class number of the imaginary quadratic number field $\mathbb{Q}(\sqrt{-p})$. Mordell's identity is taken to mean that (1) you cannot expect $\frac{p-1}2! \in \mathbb{Z}/p$ to be governed by any very simple property of $p$ such as a congruence, and (2) we can conjecture but not prove that the density of both values is $\frac12$. So I wonder about the following:

(1) What is fastest known algorithm to compute $\frac{p-1}2! \in \mathbb{Z}/p$? I read somewhere that you can compute $h$ in time $O(p^{1/5})$, but for this question (actually for the interest of the class) I only care about $h$ mod 4.

(2) Never mind the density, is it known that both values occur infinitely often?

(3) If it is known that both values occur infinitely often, then is it known, for each $\text{gcd}(n,a) = 1$, that they occur infinitely often when $p = kn+a$? (It is of course Dirichlet's theorem that there are infinitely many such primes.)


Update: There as an subexponential time algorithm of McCurley to compute the class number $h$. I can believe that computing $h$ mod 4 wouldn't be any faster.

share|improve this question
    
Of course, in question 3 I want to exclude congruences that contradict that $p$ is 3 mod 4. –  Greg Kuperberg Feb 13 '13 at 6:32
    
Note that when $p\equiv 3\pmod 4$, the class number formula gives $$h=-\frac1p\sum_{r=1}^{p-1} \bigg(\frac rp \bigg) r \equiv \sum_{j=0}^{(p-3)/4} \bigg(\frac {4j+1}p \bigg) - \sum_{k=0}^{(p-3)/4} \bigg(\frac {4k+3}p \bigg) + 2 \pmod4.$$ Don't know if this helps. This expression is related to $$\sum_{r=1}^{p-1} \bigg( \frac rp \bigg) e^{2\pi ir/4},$$ which has something to do with Polya's identity.... –  Greg Martin Feb 13 '13 at 9:00

1 Answer 1

Regarding your question (1), here are two articles I know dealing with the problem of computing factorials :

Crandall, Dilcher, Pomerance. A search for Wieferich and Wilson primes. Math. Comp. 66 (1997), no. 217, 433--449. (MR1372002)

Costa, Gerbicz, Harvey. A search for Wilson primes.

(Recall that Wilson primes are those primes $p$ such that $(p-1)! \equiv -1 \mod{p^2}$.)

It turns out that there exists an algorithm to compute the product of $N$ terms in arithmetic progression in no more than $O(N^{\alpha+\epsilon})$ multiplications, with $\alpha = \frac{\sqrt{5}-1}{2} = 0.618...$ (see p. 441 in the first article). They also mention an algorithm to compute $(p-1)! \mod{p^2}$ in time $O(p^{1/2+\epsilon})$.

The second article seems to use a somewhat different method and achieves an average polynomial time algorithm to compute this quantity, making use of the fact that there are redundant products when considering many values of $p$.

Both articles always work mod $p^2$. It is certainly faster to work only mod $p$, but I'm not sure whether this has an impact on the theoretical running time of the algorithms.

share|improve this answer
1  
These are interesting techniques for computing factorials in general, but it looks like they do not produce a better individual-case algorithm than what you can get from Mordell's identity and algorithms for the class number. On the other hand, the technique of computing a whole bunch of values at once is great. –  Greg Kuperberg Feb 14 '13 at 16:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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