Irreducible polynomials of degree 144

If $f(x)$ divides $f(x^2)$ , so does $f(-x)$ . Now $f(x)$ and $f(-x)$ are both monic and irreducible. If $f(-x)=f(x)$ , then $f(x) = g(x^2)$ for some monic polynomial of degree $72$ . But then $g(x^2)$ divides $f(x^2)$ , and so $g(x)$ divides $f(x)$ , which is not possible. Thus $f(x)$ and $f(-x)$ are distinct monic irreducibles dividing $f(x^2)$ , which is a monic polynomial of degree $288$ . Thus $f(x^2) = f(x)f(-x)$ Since it is irreducible, $f(x)$ has $144$ distinct complex roots $a_1,a_2,\ldots,a_{144}$ . Then $f(x) \; = \; \prod_{j=1}^{144}(x - a_j) \\ f(-x) \; = \; \prod_{j=1}^{144}(-x-a_j) \; = \; \prod_{j=1}^{144}(x + a_j) \\ f(x)f(-x) \; = \; \prod_{j=1}^{144}(x^2 - a_j^2) \\ f(x^2) \; = \; \prod_{j=1}^{144}(x^2 - a_j)$ Thus if $S = \{a_1,a_2,\ldots,a_{144}\}$ is the set of roots of $f(x)$ , then $S = \{a_1^2,a_2^2,\ldots,a_{144}^2\}$ . In other words, $\alpha^2 \in S$ whenever $\alpha \in S$ . Moreover, the map $\alpha \mapsto \alpha^2$ is a bijection from $S$ to itself.

If $\alpha \in S$ , then $\alpha,\alpha^2\alpha^4,\alpha^8,\ldots$ all belong to $S$ . Since $S$ is a finite set, we must be able to find $i < j$ such that $\alpha^{2^i} = \alpha^{2^j}$ , and hence $\alpha^{2^j-2^i} = 1$ . Thus $\alpha$ is a root of unity, and $f(x)$ is its minimum polynomial. Hence we deduce that $f(x) = \Phi_k(x)$ is a cyclotomic polynomial for some integer $k$ for which $\varphi(k) = 144$ (where $\varphi$ is the Euler totient function). The roots of $f(x)$ are then the primitive $k$ th roots of unity.

Suppose that $k$ were even. If $\alpha \in S$ were a primitive $k$ th root of unity, then $\alpha^2$ would not be a primitive $k$ th root of unity, since $(\alpha^2)^{k/2} = 1$ . Thus we deduce that $k$ must be odd.

Conversely, suppose that $f(x) = \Phi_k(x)$ , where $k$ is an odd integer with $\varphi(k)=144$ . It is certainly true that $f(x)$ is monic and irreducible of degree $144$ . Suppose that $\alpha \in S$ . Then $(\alpha^2)^m = 1 \; \Rightarrow \; \alpha^{2m} = 1 \; \Rightarrow \; k|2m \; \Rightarrow \; k|m$ and hence $\alpha^2 \in S$ is also a primitive $k$ th root of unity. Suppose now that $\alpha,\beta \in S$ are such that $\alpha^2=\beta^2$ . If $\alpha=-\beta$ , then $-1=\alpha\beta^{-1}$ is also a $k$ th root of unity, and so $-1=(-1)^k=1$ . This contradiction implies that $\alpha=\beta$ . Thus the map $\alpha \mapsto \alpha^2$ is an injective map from $S$ to itself, and hence is a bijection from $S$ to itself. Hence $f(x^2)=f(x)f(-x)$ ,and so $f(x)$ divides $f(x^2)$ .

Thus the number of polynomials $f(x)$ with the desired properties is equal to the number of odd positive integers $k$ such that $\varphi(k) = 144$ . There are $5$ such integers $k$ , namely $185$ , $219$ , $273$ , $285$ and $315$ . Thus there are $5$ polynomials, namely $\Phi_{185}(x)$ , $\Phi_{219}(x)$ , $\Phi_{273}(x)$ , $\Phi_{285}(x)$ and $\Phi_{315}(x)$ .

Step 1 : Show that every root of f(x) is a root of unity.

The condition implies that if $\alpha$ is a root of f(x), then so is $\alpha^2$ . Since f(x) is irreducible of degree > 1, we can't have $\alpha = 0$ . Since f(x) has finitely many roots, the sequence $\alpha, \alpha^2, \alpha^4, \alpha^8, \ldots$ is eventually periodic, being a set of roots of f(x). Write $\alpha^{2^j} = \alpha^{2^k}$ ; since $\alpha \ne 0$ , we see that $\alpha$ is a root of unity.

_Step 2 : Identify the polynomial. _

Pick a root $\alpha$ of f(x) and let n be its order. The minimal polynomial for $\alpha$ is the n-th cyclotomic polynomial $\Phi_n(x)$ which has degree $\phi(n)$ , where $\phi$ denotes the Euler totient function. Since $\Phi_n(x)$ and $f(x)$ are both monic minimal polynomials for $\alpha$ , we have:

$f(x) = \Phi_n(x) \implies 144 = \deg(\Phi_n) = \phi(n).$

Furthermore, n must be odd, for if n were even, then $\alpha^2$ would have order n/2 and does not satisfy the polynomial $f(x) = \Phi_n(x)$ .

Step 3 : Find all n.

It remains to find all odd n such that $\phi(n) = 144$ , i.e.:

$n\prod_{i=1}^m \frac {p_i - 1}{p_i} = 144,$

where $p_i$ are the distinct prime factors of n. Note that $(p_i - 1) | 144$ ; hence find all even factors d of 144 such that d+1 is prime. This gives: $p_i = 3, 5, 7, 13, 17, 19, 37, 73$ , with corresponding values:

$\frac{p_i}{p_i - 1} = \frac 3 2, \frac 5 4, \frac 7 6, \frac {13}{12}, \frac {17}{16}, \frac {19}{18}, \frac {37}{36}, \frac {73}{72}.$

Since $n = 144\prod_i \frac {p_i}{p_i - 1}$ is odd, we need the product of the denominators $p_i-1$ to be divisible by 16. A bit of trial-and-error then gives the following solutions.

• $n = (73/72) \times (3/2) \times 144 = 219$ ;
• $n = (37/36) \times (5/4) \times 144 = 185$ ;
• $n = (19/18) \times (5/4) \times (3/2) \times 144 = 285$ ;
• $n = (13/12) \times (7/6) \times (3/2) \times 144 = 273$ ;
• $n = (7/6) \times (5/4) \times (3/2) \times 144 = 315$ .

Done

If x is a complex root of f, then so is x^2, so is x^4,...

To stop f from having an infinite number of roots, we need that all of its roots are roots of unity (0 can't be a root of it). Also, if w is a root of it so are w^2, w^4,... so eventually these must repeat and its roots are roots of unity.

As f is irreducible and monic and its roots are roots of unity, it's cyclotomic. Because its degree is 144, phi(n)=144.

It is easy to check that f(x) divides f(x^2) iff n is odd.

There are exactly 5 odd n such that phi(n)=144 so the answer is 5 and we are done.

Write $f(x^2)=f(x)g(x)$ . If $a$ is a root of $f(x)$ then
$f(a^2)=f(a)g(a)=0.g(a)=0$
$⇒$ $a^2$ is also a root of $f(x)$ . So if a is a root of f then so are $a^2, a^4, ...,a^{2^n}$ ,.....for all $n$ .
If $a^{2^n}$ = $a^{2^m}$ for some $m$ $<$ $n$ $⇒$ $a^{2^m.(2^{n-m}-1)}=1$ .
So $a$ is a root of $1$ , meaning that $f(x)$ is a cyclotomic polynomial of degree $144=2^{4}.3^{2}$ .

So we need to solve the equation $\phi (x)=144$ , with $x$ of the form $2^{r}.(2^{s} - 1)$ .
If $a$ is a primitive $2^{r}.(2^{s}-1)$ root of $1$ and $r$ $>$ $0$ , then $a^2$ is a primitive $2^{r-1}.(2^{s}-1)$ root of $1$ so $a^2$ would not be a root of $f(x)$ .
This means $r=0$ and $\phi (x)=\phi (2^{s}-1)=2^4.3^2$ . So ( $2^{s}-1$ ) must break up into odd primes $p_{1}, p_{2}, p_{3}...$ such that $\phi (p_{1}, p_{2}, p_{3}...)=2^4.3^2$ .
Combinations like $x=3.5.19$ , but fail to be of the form ( $2^{s}-1$ ).
As already noted, $f(x)$ is the $k_{th}$ cyclotomic polynomial. $k$ just divides $2^{s}.(2^{r}-1)$ , though; it's not equal to $2^{s}.(2^{r}-1)$ . Since a root $R$ gives rise to a root $R^2$ , and since this must also be a primitive root of unity, it follows that $R$ cannot have order divisible by $2$ . That is, the order of $R$ divides ( $2^{r}-1$ ).
From rodolfo's calculation , we actually have $1$ $\leq$ $m$ $<$ $n$ $<$ $145$ [ since the list must start containing duplicates after 144 entries ], hence $r=n-m$ satisfies $1$ $\leq$ $r$ $\leq$ $144$ .

Thus we need only check $k_{th}$ cyclotomic polynomials where $k$ divides ( $2^{r}-1$ ) for $1$ $\leq$ $r$ $\leq$ $144$ . This is a lengthy, though doable, check. The resulting $k$ 's are: $273, 315, 285, 219, 185$ . [I had Sage do the computations] Indeed, all $5$ of these polynomials have the desired property.
So, the answer must be $5$