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

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

2010-06-30T19:43:40Z

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.

Answer by Andrey Rekalo for Composite pairs of the form n!-1 and n!+1

2010-07-01T12:50:56Z

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$.

Edit added.

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$.

Answer by Noah S for Composite pairs of the form n!-1 and n!+1

2010-08-31T05:55:39Z

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.

Answer by Franz Lemmermeyer for Composite pairs of the form n!-1 and n!+1

2010-08-31T15:03:39Z

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.