8
$\begingroup$

$2$ is a fixed point of the iteration:

$$q_{n+1}:=\min_{p|(q_n-1)^2+1} p$$

Start with $q_1>2$ prime. Does this iteration hit $5$? (min runs over primes)

Improve this question
$\endgroup$
11
  • 8
    $\begingroup$ Maybe some indication of any numerical evidence you have gathered would be appropriate. $\endgroup$ Commented Nov 20 at 13:19
  • 3
    $\begingroup$ If $q_1$ is even, then $q_n=2$ for all $n>1$. It seems to hold for all odd $q_1$. I checked this for all primes $q_1<300000$ (one can speed up the calculation greatly by noting we just need $q_n<q_1$ for some $n$ for any prime $q_1>5$). Naive Collatz-type heuristic definitely supports this, since the least prime factor of $(n-1)^2+1$ is almost always much smaller than $n$. Proving this is likely not going to be feasible though. $\endgroup$ Commented Nov 20 at 13:51
  • 3
    $\begingroup$ Is it possible to prove that the sequence $q_n$ contains at least one composite number? $\endgroup$ Commented Nov 20 at 14:33
  • 3
    $\begingroup$ @mathematician123 That would imply there are infinitely many composite Fermat numbers, so this is certainly open. I guess that shows that OP's question, if true, is open too. $\endgroup$ Commented Nov 20 at 14:35
  • 5
    $\begingroup$ For $q_1 = 532391$, $q_5 = 1688269742883776695291918433$, and $q_6 = 5$. $\endgroup$ Commented Nov 20 at 14:50

1 Answer 1

Reset to default
17
$\begingroup$

Compiling comments into an answer. The answer is probably yes, but if so, it is most certainly open.

First let me address the last part - if we start with $q_1=F_k:=2^{2^k}+1$ is a Fermat prime, then we will have $q_n=F_{k+n-1}$ for as long as these Fermat numbers are prime. If the sequence ever goes back down to $5$, in particular this means some $F_{k+n-1}$ is composite. However, it is a well known open problem to show that infinitely many Fermat numbers are composite. Therefore a positive answer to the OP's question is certainly out of our reach.

To show that it probably holds, I can offer little more than a standard Collatz-style heuristic. If we treat factorizations of $q_n$ as "essentially random" (so ignoring structure of prime factors coming from the particular form these numbers have), then we have that $(q_n-1)^2+1$ has many prime factors - Hardy-Ramanujan theorem says it will have roughly $\log\log q_n$ factors almost surely. Thus except with vanishing probability it will have at least $4$ prime factors, and the least of them will be smaller than $q_n^{1/2}$. As $q_{n+1}$ will never exceed $q_n^2$, this is heavily skewed towards smaller numbers.

A much more basic heuristic is that if we eventually hit a composite, and its factors are "random", then there is 50% chance the least one $q_n$ is $3$ or $4$ modulo $5$. But then $(q_n-1)^2+1$ is divisible by $5$. So this iteration is likely to terminate much more quickly than mere size of factors would suggest.

Lastly, let me mention numercial checks - I have verified this for any prime value $q_1<532391$. $q_1=532391$ itself is outside my computational capability, as $q_{n+1}=(q_n-1)^2+1$ is prime for $n<4$, and $(q_4-1)^2+1=(q_1-1)^{16}+1$ is too large for me to factor. (Edit: while writing this answer, GNiklasch managed to factor it in the comments above, verifying the conjecture again. If anyone wants to continue numerical checks, be my guest.)

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This argument is a bit oversimplified since the probability of having less than $4$ prime factors is not exactly vanishingly small - it is something like $1/ \log q_n$. The probability that $q_{n+1} = (q_n-1)^2+1$ is prime is $1/(2 \log q_n)$ and so this should conjecturally happen for $N/ ( 2\log^2 N)$ numbers $<N$. To see that cycles probably never happen, you need to estimate the probability that $q_n$ grows for a while and then returns to $q_1$, and show that it sums over $q_1$ to a finite number. $\endgroup$ Commented Nov 20 at 19:05
  • 1
    $\begingroup$ This seems to be a consequence of two things: First, that the $q_n$ are all congruent to $2$ modulo $q_1$ until the first $n$ with $q_{n-1}^2+1$ composite, so that cycles can only happen by going up, then down, then up or down some more. Second, that the probability of getting $q_1$ as the least prime factor is roughly $1/(q_1\ log q_1) $ and as long as the number of chances you get to look for $q_1$ as the least prime factor doesn't overwhelm the other sources of improbability, you get $\sum_{ q_1 \textrm{prime} } 1/(q_1 \log q_1)$ which is finite. $\endgroup$ Commented Nov 20 at 19:09
  • $\begingroup$ @WillSawin It is vanishingly small in that it tends to 0. For large $q$, the least prime factor of $(q-1)^2+1$ is $q^2$ with some small probability, and less than $q^{1/2}$ with almost 100% probability, so this is a heavily biased random walk. This is the same sort of heuristic as one gives for Collatz. Of course it's oversimplified, and I admit it is but a heuristic. $\endgroup$ Commented Nov 20 at 19:49
  • 2
    $\begingroup$ To see that the random walk is biased is enough to conclude that there shouldn't be divergence to infinity, but I think a bit more care is needed to deduce, even at the heuristic level, that there shouldn't be cycles. Many biased random walks do still return to their origin with large probability. Of course the numerical evidence is pretty convincing. $\endgroup$ Commented Nov 20 at 20:23
  • $\begingroup$ @WillSawin That is true. Thank you for complementing my answer with this. $\endgroup$ Commented Nov 20 at 22:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.