# Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$.

Is there a proof, preferably an elementary proof, that there are infinitely many composite pairs of the form $n!\pm1$?

The motivation for this question comes from my answer to this recent question. There, I show that every nonstandard model of Peano Arithmetic has a $\mathbb{Z}$-chain consisting entirely of composite numbers. The example I gave is that of a $\mathbb{Z}$-chain contained in the infinite interval $[N!+2,N!+N]$, where $N$ is any nonstandard natural number. I wonder if I could have picked some $\mathbb{Z}$-chain centered at $N!$ instead. A positive answer to the above question would mean that this is indeed possible. Note that it is important in this context that the proof is elementary, but I will also accept beautiful analytic arguments.

Andrey Rekalo pointed out that $(N!)^3 \pm 1$ are both composite. This means that, if $N$ is a nonstandard integer, then the $\mathbb{Z}$-chain centered at $(N!)^3$ has only composite numbers all but two have standard factors. I don't know if it's possible to find a $\mathbb{Z}$-chain all of whose elements have a standard factor.

-
I don't know of an elementary proof, but in practice it's very rare that either of $n!\pm1$ are prime, so the result is surely true. For example, both $n!+1$ and $n!-1$ are composite for all $4000\leq n\leq 6000$. Caldwell and Gallot found that $6380!+1$ and $6917!-1$ were prime, but it gets harder and harder to find examples up there. NB I discovered this by computing the first few n for which $n!+1$ was prime and looking it up in Sloane and chasing up the references. – Kevin Buzzard Jun 30 '10 at 19:59
If for a prime $q$, $2q−3$ is also prime, then $n=q-2$ makes for a composite pair. Simply put, this doesn't help – Dror Speiser Jun 30 '10 at 21:07
It seems like "elementary proof" has a specific technical meaning here; what is it? Also, just to be clear: we do not as yet know of any proof, right? – Pete L. Clark Jun 30 '10 at 22:19
@Pete: For the intended application to work, the proof has to be formalizable in PA. I'm not that picky, any proof will do for now. – François G. Dorais Jun 30 '10 at 22:25
@Dror: I don't think your assertion is correct. Try $q=13$ for a counterexample. Let me conjecture the slip you made: if $p$ (your $2q-3$) is a prime which is 3 mod 4 and $n=(p-1)/2$ then $(n!)^2$ is 1 mod $p$ but the problem is that $n!$ could be either $+1$ or $-1$ mod $p$. – Kevin Buzzard Jun 30 '10 at 23:03

Well, in the absence of any answers, perhaps this might help somebody to get a proper solution.

In order to show that there are infinitely many composite pairs of the form $n!\pm1$, it would suffice to prove that the expected number of prime numbers of the form $n!\pm1$ is relatively small, i.e. $$\limsup\limits_{N\to\infty}\frac{E|\{n=1,\dots,N|\ n!+1\ \mbox{or } n!-1\ \mbox{is prime}\}|}{N}=0.$$

Now, there is a note by Caldwell and Gallot (who were mentioned in Kevin Buzzard's comment avove) which contains a non-rigorous probabilistic argument yielding a heuristic estimate of the expectation.

In short, they start with a rough assumption that $n!\pm1$ behaves like a random variable and use the Stirling formula $\log n!\sim n(\log n-1)$. The prime number theorem shows that the probability of a random number of the size $\sim n!\pm1$ being prime is $$P_n\sim\frac{1}{n(\log n-1)},\quad n\gg 1.$$ Then they take into account Wilson's theorem and some other obvious obstacles to $n!\pm1$ behaving randomly, and obtain just a slightly weaker estimate $$P_n\sim\left(1-\frac{1}{4\log 2n}\right)\frac{e^\gamma}{n}$$ where $γ$ is the Euler–Mascheroni constant. The latter estimate translates into the estimate of the expected number of factorial primes of each of the forms $n!\pm1$, $n\leq N$
$$E_N\sim e^\gamma \log N,\quad N\gg 1.$$

Now, this is actually more than we need, and hopefully the probabilistic argument can be made rigorous to show that $E_N/N$ goes to $0$ as $N\to\infty$.

Is it true that for every positive integer $B$ there is a positive integer $N$ such that $N$ is divisible by all primes up to $B$, and $N \pm 1$ are both composite?

The modified question is easy. Take $N=(B!)^3$.

-
Andrey, sorry for redacting the modified question. Thank you for pointing out the easy answer. – François G. Dorais Jul 2 '10 at 15:43
Hakuna matata. – Andrey Rekalo Jul 2 '10 at 15:49

Explicit constructions of infinitely many examples seem to be difficult. Looking at a table of factorizations of $N! \pm 1$ I noticed the following pattern (and now I see that this is essentially what Dror suggested in his comment):

Assume that $q \equiv 3 \bmod 4$ and $p = \frac{q+3}2$ are prime numbers. Then for $n = p-2$, we have $p \mid n!-1$ and $q \mid n!+1$ if $h(-q) \equiv 1 \bmod 4$, where $h(m)$ denotes the class number of ${\mathbb Q}(\sqrt{m})$. Probabilistically, the class number of $h(-p)$ should be $\equiv 1 \bmod 4$ in half the cases.

-
Should probably mention in the final statement "for $p\equiv 3\mod 4$". – Dror Speiser Aug 31 '10 at 16:53

As far as nonstandard models go: we can indeed get $\mathbb{Z}$-like intervals $I$ such that each $x\in I$ has a standard factor. The proof is via Compactness, and the Chinese Remainder Theorem:

First, adjoin a constant symbol $c$ to our language. Let $p_i$ be the $i^{th}$ prime number, let $q_i=p_{2i}$, and let $r_i=p_{2i+1}$.

Define numbers $a_i$, $b_i$ by recursion as follows:

$a_0=0$, $a_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=a_j+kq_j)\rbrace$

$b_0=0$, $b_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=b_j+kr_j)\rbrace$

Now, for each $i\in\mathbb{N}$, let $\sigma_i$ express "$c$ is congruent to $-a_i$(mod$p_i$)", let $\tau_i$ express "$c$ is congruent to $b_i$(mod$p_i$)," and let $\Sigma=\lbrace \sigma_i: i\in\mathbb{N}\rbrace\cup\lbrace \tau_i: i\in\mathbb{N}\rbrace$. By the Chinese Remainder Theorem, every finite subset of $\Sigma$ is consistent with True Arithmetic $TA$, so by Compactness, $\Sigma$ itself is consistent with $TA$. So there is some nonstandard model of $TA$ in which $\Sigma$ holds; clearly, in such a model, every number in the $\mathbb{Z}$-like interval centered on $c$ has a standard factor.

I have no idea whether $every$ nonstandard model has such an interval, however.

-
Since CRT is a theorem of PA, couldn't this construction be carried out up to some nonstandard N to get the required Z-interval? – François G. Dorais Aug 31 '10 at 14:17