22
$\begingroup$

For every integer $n\ge 2$ , define $$f(n):=\Phi_n(n)$$ where $\Phi(n)$ is the $n$ th cyclotomic polynomial. This can be considered as the "cyclotomic diagonalization"

Prove or disprove the conjecture that $f(n)$ is squarefree for every integer $n\ge 2$

The partial factorizations I determined with PARI/GP (usually, the factors upto $12-13$ digits are found) gave no exponent greater than $1$ upto $n=200$. A rigorous test upto $n=46$ revealed that upto this limit there are only squarefree values.

If it cannot be proven, a good heuristic would also be welcome.

$\endgroup$
9
  • $\begingroup$ The numbers are tabulated at oeis.org/A070518/b070518.txt $\endgroup$ – Gerry Myerson Jan 17 at 2:49
  • $\begingroup$ The bounty is in the spirit of the Pearl Dive project. I will also mention this in MathOverflow in case somebody there sees something. $\endgroup$ – Jyrki Lahtonen Jan 17 at 21:57
  • 3
    $\begingroup$ The conjecture is false ! For $n=28341$ , $p=283411$ , we have $p^2\mid \Phi_n(n)$. $\endgroup$ – Peter Jan 19 at 12:24
  • 1
    $\begingroup$ No further counterexamples for $p < 5 \cdot 10^{10}$. $\endgroup$ – Martin Hopf Jan 27 at 16:32
  • 1
    $\begingroup$ $p^2 \mid \Phi_n(n)$. No further counterexamples for $p < 2 \cdot 10^{11}$. $\endgroup$ – Martin Hopf Jan 31 at 16:11
14
+500
$\begingroup$

We want to show that the problem is equivalent to

For any number $n$ and any prime $q \mid n^n-1$, then $ord_{q^2}(n) \neq n$

We will see at the end why we expect this to be false, but also that counterexamples are very rare and are likely to have more than forty digits.

Recall the Moebius function defined here, and the notation $v_p(k)$ for the maximum exponent $\alpha$ such that $p^{\alpha} \mid k$. Notice that $v_p(xy) = v_p(x)+v_p(y)$ behaves like a logarithm. The key observation is the following:

Lemma. It holds $$ (**) \ \ \ \ v_p(\Phi_n(n) ) = \sum_{d \mid n} \mu \left (\frac{n}{d} \right ) v_p(n^d-1) $$

Proof. It is well known that

$$ \prod_{ d \mid n} \Phi_d(x) = x^n -1 $$

Now for any natural number $x$, taking $v_p$ yields

$$ \sum_{d \mid n} v_p \Phi_d(x) = v_p(x^n-1) $$

Applying the Moebius Inversion Formula we get $$ v_p \Phi_n(x) = \sum_{d \mid n} \mu \left ( \frac{n}{d} \right ) v_p(x^d-1)$$ and the thesis follow by specializing at $x=n$.

Main Proof. Now that we have a formula for the exponent, let's compute it. Set $r:= ord_p(n)$. Note that if $r$ does not divide $n$, it does not divide any of its divisors $d \mid n$; it follows that $n^d \neq 1 \pmod{p}$ for all $d$. Thus equation (**) yields $v_p(\Phi_n(n) ) = 0$. Let us suppose for the rest that $r \mid n$ and set $n'=n/r$.

Case 1. $n'=1$, that is $ord_p(n) = n$. In this case the only summand that contributes to the summation in (**) is $v_p(n^n-1)$. This is $\le 1$ if and only if $p^2 \nmid n^n - 1$. Note that $n = ord_p(n) \mid ord_{p^2}(n) $:

  • If the $ord_{p^2}(n)$ is equal to $n$, then $p^2 \mid n^n -1 $ and we found a counterexample;
  • If instead $ord_{p^2}(n)>n$, we must have that $n^n \neq 1 \pmod{p^2}$ and we are happy.

Case 2 $n' >1$. This part can seem heavy, but if you are familiar with Moebius Function you will recognize that this is just ordinary Yoga.

The summands that contribute to (**) are all the $d$ that are divisible by $r$. Note that any number $d$ such that $r \mid d \mid n$ can be written as $rd'$, where $d' \mid n'=n/r $. With this observation in mind we write

$$ v_p(\Phi_n(n) ) = \sum_{r \mid d \mid n} \mu \left (\frac{n}{d} \right ) v_p(n^d-1) = \sum_{d' \mid n'} \mu \left (\frac{r n'}{r d'} \right ) v_p(n^{rd'}-1) = \sum_{d' \mid n'} \mu \left (\frac{n'}{d'} \right ) v_p((n^r)^{d'}-1) $$

Now we use the Lifting The Exponent Lemma to split the $v_p$ factor. We get $$ \sum_{d' \mid n'} \mu \left (\frac{n'}{d'} \right )( v_p(n^r-1) + v_p(d') )= v_p(n^r-1) \sum_{d' \mid n'} \mu \left (\frac{n'}{d'} \right ) + \sum_{d' \mid n'} \mu \left (\frac{n'}{d'} \right ) v_p(d') $$

Since $n'>1$, the first summand is zero: indeed $\sum_{k \mid h} \mu(h/k) = 0$ for $h> 1$. The second factor is more interesting. Suppose $n'= p^{\alpha} m$ with $(m,p) =1$. Every divisor of $n'$ will uniquely write as $p^{\beta} m'$, where $\beta \le \alpha$ and $m' \mid m$. Using the fact that $\mu(ab) = \mu(a)\mu(b)$ for $a,b$ coprimes we get

$$\sum_{d' \mid n'} \mu \left (\frac{n'}{d'} \right ) v_p(d') = \sum_{\beta=0}^{\alpha} \sum_{m' \mid m} \mu(p^{\alpha-\beta}) \mu(m/m') \beta = \sum_{\beta= 0}^{\alpha} \mu(p^{\alpha-\beta})\beta \sum_{m' \mid m} \mu(m/m')$$

We have to do a little distinction here. If $m>1$ this is zero again by the "summation moebius" property. If $m=1$, we are basically saying that $n'=p^{\alpha}$. In this case the formula reduce to

$$ \sum_{\beta=0}^{\alpha} \mu(p^{\alpha-\beta}) \beta = \beta - (\beta-1) = 1$$

And... Voilà!

Heuristics. We want to show that it is almost certain that a counterexample exist, but it is very likely to have hundreds of digits. Define for $d \mid p(p-1)$: $$ X(p) = \{ 1 \le z \le p^2: \ \ (z,p) =1 \} $$ $$ X_d(p) := \{1 \le z \le p^2 : \ \ (z,p) = 1 \text{ and } ord_{p^2}(z) = d \} $$ Note that $$\# X(p) = \phi(p^2) = p(p-1) \ \ \ \ \#X_d(p) = \#\{\text{roots of } x^d-1 \text{ in } \mathbb{F}_p\} = d$$ It is reasonable to assume that $X_d(p)$ is a random set in $X(p)$; indeed, if I am not wrong, there are some results of Davenport, Erdos, Vinogradov showing that quadratic residues, cubic residues ecc. are equidistributed among $X(p)$, and you can say that $ord_{p^2}(z) = k$ if and only if $z$ is a $\phi(p)/k$ residue but not a $\phi(p)/kq$ residue for all $q \mid \phi(p)/k$. However, I am not expert enough to produce a real proof.

We say that $p$ is a counterexample to the cdp (cyclotomic diagonalization problem) if $p^2$ appears as a factor of some $\Phi_n(n)$. We have shown above that this can happen iff $ord_{p^2}(n) = n$. Note that such an $n$ should be a divisor of $\phi(p) = p(p-1)$, because $n = ord_{p^2}(n) \mid p(p-1)$ and must be also coprime with $p$ (otherwise $p \nmid n^n-1$). On balance, the $n$ that make $p$ a counterexample to the cdp must be searched among the divisors of $(p-1)$.

For any such divisor $b$, we must hope that $b \in X_b(p)$. Since $X_b(p)$ is a random set in $X(p)$, this happens with probability $\frac{b}{p(p-1)}$. So the probability that this does not happen for any divisor $b$ is

$$ \prod_{b \mid (p-1) } \left ( 1- \frac{b}{p(p-1)} \right ) $$ The logarithm of this sum can be estimated as $$ - \sum_{b \mid (p-1) } \frac{b}{p(p-1)} = - \frac{1}{p(p-1)} \sum_{b \mid q-1} b \le - \frac{1}{p} $$ Using the fact that $\sum_{b \mid q-1} b \ge q-1$. So the probability that $p$ is a counterexample is $\ge $

$$ 1- e^{-1/p} \simeq \frac{1}{p} $$

We use this logarithm-product strategy to estimate the probability $Q_x$ of finding a counterexample $\le x$. The probability of not having counterexamples up to $x$ is

$$ 1- Q_x = \prod_{p \le x} \left ( 1 - \frac{1}{p} \right ) \simeq exp(-\sum_{p \le x} \frac{1}{p} )\simeq exp(-\log \log x) = \frac{1}{\log(x)}$$

From which we get $Q_x \simeq 1- \frac{1}{\log x} $. This tends to $1$, so it is almost certain that a counterexample exists. On the other side, it goes to zero very slowly.

Example. Suppose you want to be $99\%$ sure to find a counterexample up to $x$. Then $$\frac{99}{100} \simeq 1- \frac{1}{\log x} \ \ \Leftrightarrow \ \ \ \log x \simeq 100 $$

Which implies $x \simeq e^{100} \simeq 10^{43}$.

P.S. I am missing the case $p=2$, in which the Lifting the Exponent Lemma is slightly different; it should work the same way, though (the only different passage is the last, I which I think it is enough to verify the case $\Phi_{2^n}(x) = x^{2^{n-1}}+1$ :) )

$\endgroup$
13
  • 1
    $\begingroup$ Interesting stuff, and surely Möbius is a natural approach. But you lost me in Case 1. Why would $p^2\mid f(n)$ imply that $n$ is a double root in $\Bbb{F}_p$? Consider for example $f(x)=x^2-1$. We have $9\mid f(1)$ but the roots of $f(x)$ in $\Bbb{F}_3$ are simple? $\endgroup$ – Jyrki Lahtonen Jan 17 at 10:02
  • $\begingroup$ Well... I think you are right. I also thought in the meantime that it Is the only part in which we really use $x=n$; but I only used that $x\le n$, so the argument would show thst $\Phi_n(x) $ is square free for every $x \le n$. This seems weird. $\endgroup$ – Andrea Marino Jan 17 at 10:53
  • $\begingroup$ Also, let me remark that I have tested the case $q^2 \mid p^p-1, p \mid q-1$ for $p, q$ primes up to $10^7$ and there is no counterexample. Seems like a number "can't" gain two factors $q$ in a unique power (which is compatible with LTE intuition in the case $q \mid n-1$) $\endgroup$ – Andrea Marino Jan 17 at 11:12
  • 1
    $\begingroup$ I thought better, and I think that in light of the new observations a counterexample can exist. However, with some resonable heuristic assumptions, I think that the counterexample for $p$ should have something like 300 digits, which is completely out of reach with a calculator... I'll add my heuristic soon. $\endgroup$ – Andrea Marino Jan 17 at 21:32
  • 1
    $\begingroup$ As an acceleration, I used that a prime factor $p\mid \Phi_n(n)$ must satisfy $p\equiv 1\mod n$ and that for a counterexample the order of $n$ modulo $p^2$ must be exactly $n$. This allowed me to check a relatively large range giving only one counterexample. $\endgroup$ – Peter Jan 19 at 21:01
10
$\begingroup$

Checking the pairs $n,p\le 10^6$ , I found one counterexample , namely :

$$283411^2\mid \Phi_{28341}(28341)$$

$\endgroup$
7
  • $\begingroup$ I think Mathematica's integer arithmetic can be trusted, and this checks out. $\endgroup$ – Jyrki Lahtonen Jan 19 at 21:11
  • $\begingroup$ partial factorization of the counterexample $\endgroup$ – Peter Jan 19 at 21:16
  • 3
    $\begingroup$ For the record: I have added this as the 55th answer to the "big-list" question Examples of eventual counterexamples. $\endgroup$ – Wolfgang Jan 21 at 20:14
  • $\begingroup$ I hope you are fine with Andrea getting the bounty. In the end I went with the popular vote, which was very close (8 to 7 at decision time). Yours gives more definite information, but users will find both answers useful. Plus, Andrea can use the points but you have a fair amount already. Looking forward to sponsoring similar interesting questions in the future. $\endgroup$ – Jyrki Lahtonen Jan 24 at 9:41
  • 2
    $\begingroup$ I mean I'd be also ok with the bounty being splitted! As Jyrki pointed out I have not much réputation, so this bounty could bè useful in the future and I thank you for that. However, I don't understand why Peter is not so convinced about my answer, honestly I think that a straight factorization would have been impossible to test for such big numbers, while the criterion I gave is much faster. I also gave the heuristic to such a counterexample to exist. I was wrong, though, in deducing that it would have been way larger; that's definitely on me. Best, Andrea $\endgroup$ – Andrea Marino Jan 24 at 15:48

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.