Almost Fermat Primes

Study.com source

Pierre de Fermat was fluent in six languages. Yes I thought we would talk about Fermat today. Something I did not know about him is: he was fluent in French, Latin, Greek, Italian, Spanish, and Occitan. I am impressed since I never could handle another language, though Ken speaks several. Occitan is a relative of Catalan and some of its constituent dialects may be more-familiar names: Langue d’Oc, Provençal, Gascon, and Limousin.

Today Ken and I thought we would discuss something named for Fermat: Fermat primes. A Fermat prime is any prime of the form .

A Fermat prime is any prime of the form

No, we did not contradict or repeat ourselves. Understanding why can possibly be prime only when is a power of is the beginning of learning the language of number theory. Any other includes an odd prime factor . Put . Then where and ; note that uses being odd. The basic fact is that is always divisible by (which in this case equals ), so is not prime.

Fermat primes are quite useful, but unfortunately there seem to only be five of them:

There are applications of Fermat primes that could really use having an infinite family of them. A prime case—bad pun—is the beautiful work of Martin Fürer on fast multiplication of integers.

Generalized Fermat Primes

This has led us to seek larger families that might have similar applications. There are of course generalized Fermat primes, which are defined as primes of the form

for any base . Obviously for they are the Fermat primes.

These numbers seem to be in relative abundance. Indeed, currently the 13th largest known prime is the generalized Fermat number with and .

Whether there are infinitely many generalized Fermat primes is trivial for but already for it subsumes the fourth problem listed by Edmund Landau in his address to the International Congress of Mathematicians in 1912, twelve years after David Hilbert gave his famous list. The problem of whether infinitely many primes are one more than a square traces back at least to Leonhard Euler.

We are, however, interested in special primes amid lists of single-exponential rather than double-exponential density. Marin Mersenne studied primes of the form several decades before Fermat. Eleven of the twelve largest known primes have this form, but again no one knows whether there are infinitely many. So we consider other odd numbers near .

Almost Fermat Primes

Close to Fermat primes are primes among the numbers of the form:

A simple implementation of a probabilistic primality test, such as this in Python by Eli Bendersky, suffices to find them up to or so. The simplicity owes to Python’s arbitrary-precision integer arithmetic. After the list has gaps but also mini-clusters:

prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at
prime at

This gives an impression of greater abundance. The whole known sequence of such is A057732 at the Online Encyclopedia of Integer Sequences.

Bounded Almost Fermat (and Mersenne)

The sequence A059242 of such that is prime starts out . Then there is a big jump to .

There are some such that is always composite. An entertaining talk by Carl Pomerance ascribed to Paul Erdős but this needed to be fixed to . But we are interested concretely in small .

Our desire may ultimately be to have a fixed that gives a sequence of primes for that is not only infinite but has linear density in . That is, we want some fixed as well as such that for any prime in our sequence, there is and such that is prime. This ensures

(ignoring possible low-order exceptions to the second inequality), so that the next item in our sequence is polynomially bounded. Thinking of the -th element of our sequence as , we would get a rough bound

so that the density becomes analogous to that of Fermat numbers. We might allow to be slowly growing in , e.g., .

Here we are thinking of and as “magic primes” that may allow certain algorithmic ideas to succeed. The density condition ensures the existence of some of magnitude polynomial in the complexity parameter(s). If we only need that the length of is polynomial then we might tolerate a weaker density condition such as in the above.

Among values of we prioritize those of the form so that the binary expansion of has only three 1’s. Hence also we are less interested in the extension of Mersenne primes to negative . Here is a table with and :

The clusters of 3 seem to stand out the most. As noted above, there are no cases in this range. Of course, this is a small slice of data.

Open Problems

Are there ways to exploit the fact that there appear to be many almost-Fermat numbers? Of course proving there are an infinite number of them could be very hard.