17
$\begingroup$

The integer $(1^2+1)(2^3+1)(3^4+1)(4^5+1)$ is a square, namely $2^23^25^241^2$.

Question. What will be the next occurrence, or is there an occurrence of $$\prod_{i=1}^n (i^{i+1}+1)=k^2?$$

$\endgroup$
5
  • 1
    $\begingroup$ No more for $n \le 1000$ $\endgroup$ – David Loeffler Feb 22 at 11:01
  • 8
    $\begingroup$ Naive heuristic is that a "random" number $n$ is a square with probability $1/\sqrt(n)$. Taking a sum of these over your sequence for say $n>100$ gives a very small (in particular finite) value, so by Borel-Cantelli you should expect only finitely many of them to be squares, perhaos none at all after $n=4$. However the fact these are products would make me wary of trusting this heuristic too much. $\endgroup$ – Wojowu Feb 22 at 12:20
  • $\begingroup$ No more for $n \leq 10000$ (if my GAP script is correct) $\endgroup$ – Francesco Polizzi Feb 23 at 5:43
  • 3
    $\begingroup$ You can compute much higher if you just keep track of the parity of the exponents of the first few primes. Assuming that my code is correct, I've checked $n\leq10^7$ (using just the first 25 primes). $\endgroup$ – Thomas Browning Mar 1 at 2:28
  • $\begingroup$ Also, here's a small observation: $i^{i+1}+1$ is never divisible by 4, and is periodic modulo 4. From this, you can show that if the product is a square then $n\equiv0,3\pmod{4}$. $\endgroup$ – Thomas Browning Mar 1 at 2:36
21
+50
$\begingroup$

The following criterion will most likely cover all large $n$, but actually proving this is out of reach of current technology.

Proposition. Let $p$ be a Sophie Germain prime (so that $q := 2p+1$ is also prime) with $p = 11 \hbox{ mod } 12$, such that $(p-1)^p + 1$ is not divisible by $q^2$. Then $\prod_{i=1}^n (i^{i+1}+1)$ is not a square for any $p-1 \leq n < 2p$.

Proof. Suppose that one of the factors $i^{i+1}+1$ is divisible by the prime $q$ for some $i \leq n$. Then $i^{i+1} = -1 \hbox{ mod } q$. Since the multiplicative group of ${\bf F}_q$ is a cyclic group of order $q-1 = 2p$, we conclude that either $i+1$ is equal to $p$ mod $2p$, or $i = -1 \hbox{ mod } q$ and $i+1$ is odd. Since $i \leq n < 2p \leq 3p-1$, the first case only occurs at $i=p-1$; since $i \leq n < 2p = q-1$, the second case does not occur at all. Hence the only factor in $\prod_{i=1}^n (i^{i+1}+1)$ that could be divisible by $q$ is $(p-1)^p + 1$. Modulo $q$, $p-1$ is equal to $-3/2$, hence $(p-1)^p + 1$ is equal to $-(3/2)^p + 1$ mod $q$. By quadratic reciprocity, $3/2$ is a square mod $q$ when $p = 11 \hbox{ mod } 12$, so $(p-1)^p + 1$ is divisible by $q$, but by hypothesis it is not divisible by $q^2$. Hence the product is not a perfect square. $\Box$

(A slight generalisation of) the Hardy-Littlewood conjecture implies that there are infinitely many Sophie Germain primes $p$ with $p = 11 \hbox{ mod } 12$ (indeed their density in any large interval $[x,2x]$ would conjecturally be of the order of $1/\log^2 x$). The condition $(2p+1)^2 \not | (p-1)^p + 1$ is reminiscent of a non-Wieferich prime condition and it is likely that only very few Sophie Germain primes fail this condition, but this is challenging to prove rigorously. (For instance, even with the ABC conjecture, the number of non-Wieferich primes is only known to grow logarithmically, a result of Silverman.) Nevertheless, this strongly suggests that the above Proposition is sufficient to rule out squares for all sufficiently large $n$.

Each prime $p$ obeying the above conditions clears out a dyadic range of $n$, for instance $p=11$ obeys the conditions and so clears out the range $10 \leq n < 22$ (for all $n$ in this range the product is divisible by precisely one factor of the prime $23$). An algorithm to search for primes obeying these conditions should then keep essentially doubling the range for which no further squares are guaranteed to exist rather rapidly and numerically establish quite a large range of $n$ devoid of any additional squares.

EDIT: Here is a justification of why $q^2 | (p-1)^p + 1$ is a Wieferich type condition. If this holds, then on squaring we have $$ (p-1)^{2p} = 1 \hbox{ mod } q^2$$ hence on multiplying by $p-1$ $$ (p-1)^q = p-1 \hbox{ mod } q^2$$ and then multiplying by $2^q$ $$ (q-3)^q = 2^{q-1} (q-3) \hbox{ mod } q^2.$$ By the binomial theorem and Fermat's little theorem we have $(q-3)^q = -3^q \hbox{ mod } q^2$ and $2^{q-1} q = q \hbox{ mod } q^2$, hence $$ -3^q = q - 3 \times 2^{q-1} \hbox{ mod } q^2$$ which simplifies to $$ q^2 | 3 \times 3^{q-1} - 3 \times 2^{q-1} + q$$ which can be viewed as a variant of the Wieferich condition $$ q^2 | 2^{q-1} - 1.$$

$\endgroup$
3
  • 1
    $\begingroup$ Interesting idea re Wieferich, but I wonder. Let $F_q=(2^q-1)/q$. The Wieferich condition is $F_q\equiv0\pmod q$. Your condition is $F_q\equiv4\pmod q$. Sometimes $0$ mod $q$ is "different" from non-zero. For example, it's known that the $ABC$ conjecture implies infinitely many $q$ with $F_q\not\equiv0\pmod q$. Not clear if that proof will give infinitely many with $F_q\not\equiv4\pmod q$. In any case, a very nice analysis of the original question. $\endgroup$ – Joe Silverman Mar 2 at 22:12
  • $\begingroup$ Good point. Actually I realized I made a mistake in my previous edit and the Weiferich-type calculation is more complicated than I first thought, which only serves to reinforce your point. $\endgroup$ – Terry Tao Mar 2 at 22:25
  • $\begingroup$ I see. So with natural noation for Fermat quotients, your new condition is $$3F_q(3)-3F_q(2)\equiv-1\pmod q.$$ Would seem to raise (presumably currently unaswerable) questions of describing the set of primes $q$ such that $$P\bigl(F_q(a_1),F_q(a_2),...,F_q(a_n)\bigr)\equiv0\pmod q,$$ where $P$ is a fixed polynomial and $a_1,\ldots,a_n$ are fixed integers (with some sort of independence condition, e.g., $a_1,\ldots,a_n$ could be distinct primes). $\endgroup$ – Joe Silverman Mar 2 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.