13
$\begingroup$

A student of mine keeps coming again and again and telling "I've found a formula $n\mapsto f(n)$ giving all primes" or sometimes "infinitely many primes", where $f$ is a classical function (I mean made of exponentials and polynomials, just like Mersenne primes). Then follows a long discussion, me saying "nice try, but it doesn't work because ...", and him argumenting ... and trying to restrict $f$ to the primes ...

Today I told him something like: "you know, many great mathematicians tried to find such formulas, but never succeeded" and he answered: "maybe they didn't see something elementary, and I can find it".

Now the questions: let $\mathcal S$ be the algebra of sequences of integers (under $+$, $\times$ and $\circ$). Let $\mathcal S_0$ be the smallest subalgebra containing all polynomial sequences $n\mapsto P(n)$ for $P\in \mathbf Z[X]$, and all exponentials $n\mapsto a^n$ for $a\in\mathbf Z$. Let $\mathcal S_1$ be the subset of $\mathcal S_0$ made of sequences $n\mapsto f(n)$ satisfying $f(n)>n$ for any integer $n$.

Q1) Is there any result saying that no element of $\mathcal S_1$ can have an infinite subset of the set of primes as its image?

Or even better :

Q2) Is there any result saying that the image by an element $f$ of $\mathcal S_1$ of the set of prime numbers must contain infinitely many composite numbers?

And finally :

Q3) Is there any result saying that if $f$ is an element of $\mathcal S_0$ satisfying $f(n)>n$ for all $n$, and $u_n$ is the sequence obtained by choosing an initial value $u_0$ and by setting $u_{n+1}=f(u_n)$, then $(u_n)_n$ must contain at least one composite numbers?

(Ok, this is not exactly a research question, but answers would help research since it would enable me to reject his proposals directly, without the need of finding counter-examples). From this point of view, negative answers wouldn't be welcome !)

Improve this question
$\endgroup$
9
  • $\begingroup$ A bunch of relevant links: math.stackexchange.com/questions/1201359/… math.stackexchange.com/questions/940338/… math.stackexchange.com/questions/44290/… math.stackexchange.com/questions/392442/… $\endgroup$
    – M.G.
    Commented Feb 4, 2016 at 13:33
  • 2
    $\begingroup$ Have you seen this paper? Shapiro, Harold N.; Sparer, Gerson H. Composite values of exponential and related sequences. Comm. Pure Appl. Math. 25 (1972), 569–615. $\endgroup$
    – so-called friend Don
    Commented Feb 4, 2016 at 16:16
  • 3
    $\begingroup$ Although you said that negative answers are not welcome, let me give the following heuristic argument that there is no known result of the type you are asking for. Consider the question, why aren't all the Fermat numbers $2^{2^n}+1$ prime? Nobody ever cites a general result that implies that any expression with this syntactic form must fail to be prime for some $n$. $\endgroup$
    – Timothy Chow
    Commented Feb 4, 2016 at 16:31
  • 1
    $\begingroup$ @DenisSerre right, but in your very example, a positive answer to my (first) question would not say there are infinitely many such primes (which is an open problem) but that $n^2+1$ cannot be a prime for all values $n$ larger than a certain $N$ (which is not an open problem : think of $n=5k+2$), not even when restricted to primes (for the same reason + Dirichlet). $\endgroup$
    – few_reps
    Commented Feb 4, 2016 at 17:05
  • 1
    $\begingroup$ @few_reps : It is only a heuristic argument. However, in my experience, if there is a hammer, someone will usually mention it in passing, even if a simpler proof is available. In fact I think the classical nature of the problem makes it even more likely that a hammer would be cited if it existed. $\endgroup$
    – Timothy Chow
    Commented Feb 4, 2016 at 18:00

1 Answer 1

Reset to default
7
$\begingroup$

Do a web search for Diophantine Representation of prime numbers. You will find an article of that title containing a polynomial of degree 25 in 26 variables whose range intersected with the positive integers is exactly the prime numbers.

There are general results for polynomials of one variable which extend to several variables which show that the range (both positive and negative) cannot be exclusively primes. Also the Prime Pages online, and books by Ribenboim, contain essays on the subject addressing your question, references on such are easily found by web searches.

In short, he is right, there could be something elementary that others might have overlooked. If he can derive the degree 25 polynomial above on his own, I say have him keep looking, AFTER he reads and understands the essays.

Gerhard "Don't Spoil His Prime Fun" Paseman, 2016.02.04.

Improve this answer
$\endgroup$
7
  • $\begingroup$ If I can find answers to your specific questions, I will post them later. However, I think having such answers to the questions above will be less effective in dealing with him than encouraging him to do the research showing what has been done. Gerhard "Dampening His Ardor Is Allowed" Paseman, 2016.02.04. $\endgroup$
    – Gerhard Paseman
    Commented Feb 4, 2016 at 16:57
  • 1
    $\begingroup$ Derive the degree 25 polynomial on his own? Is this a joke? Is there any way to construct this other than by way of the general solution to Hilbert's tenth problem? $\endgroup$
    – Timothy Chow
    Commented Feb 4, 2016 at 18:03
  • 2
    $\begingroup$ You can view it as a joke. I view it as a tactic. If the poster is truly being pestered and wants something to divert/deflect/educate this person, I think presenting the fact of this polynomial's existence is almost tailor made for the purpose. Gerhard "Heard Of Proof By Intimidation?" Paseman, 2016.02.04. $\endgroup$
    – Gerhard Paseman
    Commented Feb 4, 2016 at 18:07
  • $\begingroup$ @GerhardPaseman : I didn't mean to spoil his fun ... of course. In fact, a positive answer would certainly be of the greatest interest to him (and to me, after all). If no such answer comes, then I might follow your advice, even if there are many cheaper results that could serve the same aims. $\endgroup$
    – few_reps
    Commented Feb 4, 2016 at 19:17
  • 1
    $\begingroup$ I spend time and thought in forming answers and in comments. The signature has become an integral part, sometimes a counterpoint, of the responses I craft. Sometimes it takes time to find the right sentiment, and sometimes I have to work to fit the sentiment into signature form. After much practice, and fortunately more acceptance than discouragement from this community, MathOverflow has now a collection of signatures almost as large as that of Ashleigh Brilliant. Gerhard "This Space Not For Rent" Paseman, 2016.02.04. $\endgroup$
    – Gerhard Paseman
    Commented Feb 5, 2016 at 5:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .