Polynomials for natural numbers and irreducible polynomials for prime numbers?

Question

Let $p$ be a prime and $n$ be a natural number.

Define inductively for prime numbers: $f_1(x) := 1$, $f_2(x):=x$, $f_p(x) := 1+\prod_{q\mid p-1} f_q(x)^{v_q(p-1)}$.

Is $f_p(x)$ always irreducible for each prime $p$?

Let $f_n(x):= \prod_{p\mid n} f_p(x)^{v_p(n)}$ for each natural number $n$.

Motivation: Define the arithmetic derivative as $n' := f'_n(x)|_{x=2}$. Then using an approach similar to here, I think that I can prove that for each prime $p>2$ we have:

$$\frac{p-1}{(p-1)'} \le \operatorname{rad}(p-1).$$

Thanks for your help.

Edit: Another motivation: If $f_p(x)$ is irreducible for each prime $p$ then we have the following by definition of $f_n(x)$:

$n$ is a prime number $\iff$ $f_n(x)$ is irreducible.

The degrees of $f_n(x)$ are the same as A064415:

$$0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 4, 4, 5, 5, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 4, 5, 5, 4, 5, 5, 5, 5, 5, 4, 6, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 4, 6, 6, 5, 6, 5, 5, 6, 6, 5, 5, 6, 5, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 5$$

which has been studied by Erdős, Granville, Pomerance and Spiro. This can be seen as follows: If $d(n) := \deg(f_n(x))$ then the function $d$ has the following properties:

$$d(1)= 0, d(2) = 1, d(mn) = d(m)+d(n) \forall m,n, d(p) = d(p-1) \forall \text{ primes } p > 2$$

which is one definiton of the OEIS sequence above.

Second edit: Here are more properties, for some of which I have used the irreducibility hypothesis as being true (wording: "should") and others for which I hope, but do not know if they are useful in proving the "irreducibility":

1. $n = a \cdot b \iff f_a(x)\cdot f_b(x) = f_n(x)$.
2. $f_n(x)$ is a separable polynomial $\iff n = \operatorname{rad}(n)$.
3. $\gcd(f_m(x),f_n(x)) = f_{\gcd(m,n)}(x)$.
4. If $p$ is a prime number, then $f_{p-1}(x)+1$ should (by the irreducibility hypothesis) be an irreducble polynomial.
5. If $f_{p-1}(x) +1$ is not irreducible, then $p$ should not be prime.
6. Let $W(m,n) = m'n-n'm$ denote the Wronskian and let the arithmetic derivative be defined as $n':=f'_n(x)|_{x=2}$. Assume that $m,n$ have $\gcd(m,n)=1$ and $W(m,n)\neq 0$. Then by the Mason–Stothers theorem for natural numbers, as linked above, we should get: $$mn(m+n) \le \operatorname{rad}(mn) \operatorname{rad}(f_m(x)+f_n(x))|_{x=2} \cdot |W(m,n)|.$$
7. Let $\left < f,g \right > = \int_{-1}^1 f(x) g(x) \operatorname{d}x$ and $P_n$ be the Legendre poylnomials. Then $$f_n(x) = \sum_{l=0}^{d(n)} \frac{2l+1}{2} \left < f_n, P_l \right > P_l(x).$$
8. Since $f_n(2)=n$ we get from 7.: $$n = \sum_{l=0}^{d(n)} \frac{2l+1}{2} \left < f_n, P_l \right > P_l(2).$$
9. $p>2$ is prime $\iff$ we should have $f_p(x) = 1+f_{p-1}(x)$.
10. If $G_n := ( \left < f_a, f_b \right >)_{1 \le a,b \le n}$ is the Gram matrix, then $\operatorname{rank}(G_n) = \operatorname{floor}(\frac{\log(n)}{\log(2)})+1$.
11. $\forall n \in \mathbb{N}: f_n(x) = (x \cdot h_n(x)+\operatorname{floor}(\frac{n}{2}))\cdot(x-2)+n$ for some $h_n(x) \in \mathbb{Z}[x]$.
12. It should be $\operatorname{rad}(f_n(x)) = \prod_{p|n}f_p(x)$.
13. It should be $\operatorname{rad}(f_n(x))|_{x=2} = \operatorname{rad}(n)$.
14. As the product of two primitive polynomials is primitive, we get by induction on $p$: $f_p(x)$ is primitive and so $f_n(x)$ is primitive as a product of primitive polynomials.

Edit: It is enough to show that $|\theta-2|>1$ for all roots $\theta$ of $f_p(x)$ and here is a proof and the idea by Nicolae Bonciocat which goes back to Weisner (1934) : L. Weisner, Criteria for the irreducibility of polynomials, Bull. Amer. Math. Soc. 40 (1934), 864–870.:

Assume that $f_p(X)=a_nX^n+\dotsb a_1X+a_0$ and $f_p(X)=f_1(X)f_2(X)$ with $f_1,f_2\in\mathbb{Z}[X]$ and $\deg f_1=m\geq 1$, $\deg f_2=t\geq 1$. Then $p=f_p(2)=f_1(2)f_2(2)$, and since $p$ is a prime number, one of $f_1(2)$ and $f_2(2)$ must have absolute value equal to $1$, say $|f_1(2)|=1$. On the other hand, if we write $f_1$ as $f_1(X)=b_mX^m+\dotsb b_1X+b_0$, with $b_m$ a divisor of $a_n$, we have $f_1(X)=b_m(X-\theta_1)\dotsm (X-\theta _m)$ for some roots $\theta _1,\dots ,\theta _m$ of $f_p$, so $1=|f_1(2)|=|b_m|\dotsm |2-\theta_1|\dotsm |2-\theta _m|$. Since $|b_m|\geq 1$, if we assume that $|\theta -2|>1$ for each root $\theta$ of $f_p$ (in particular for $\theta _1,\dots ,\theta _m$), we obtain $1\geq |2-\theta_1|\cdots |2-\theta _m|>1$, a contradiction. Thus $f_p$ must be irreducible.

I have checked in SageMath for $p \le 104729$ that the roots satisfy this criterion.

It seems possible to extend this procedure to the rationals:

$$f_{\frac{a}{b}}(x):=\frac{f_a(x)}{f_b(x)}, \text{ for } \gcd(a,b)=1$$

and for negative or zero set:

$$f_{-q}(x):=-f_q(x)$$

$$f_{0}(x):=0.$$

Using this method, I have visualized pairs of primes $p,q$ as $$f_{p}(x)/f_q(x)$$ in the complex plane. One can not escape the fascination of these images. It looks like some sort of force field between the zeros and the poles of the function, where the particles are either the zeros or the poles and the field is given by the contour plot:

SageMath-Code to produce the images.

Answer 1

I believe I have a proof that the polynomials $f_p(x)$ are irreducible for all primes $p$.

I recognize that it's not great form in general to post multiple answers to a MathOverflow question, but since my other answer explores a side quest while this one addresses the original problem, I hope I can be forgiven this once.

---

The proof is based off of the argument given in the original post (idea from Nicolae Bonciocat, going back to Weisner) that if all roots $\theta$ of $f_p(x)$ are far enough from $x=2$ then $f_p(x)$ is irreducible. My other answer explains why the condition $|\theta-2|>1$ does not hold in general. We'll see instead that the condition $\text{Re}(\theta)<\frac32$ is sufficient to prove irreducibility, and that this condition does always hold.

Lemma 1: Let $g(x)\in\mathbb{Z}[x]$ be a non-constant monic polynomial with constant term $\pm 1$. If $g(x)$ is not a power of $(x+1)$, then there exists a root of $g(x)$ with real part greater than or equal to $-\frac12$.

Proof: (Edit: simplified proof thanks to a comment by Fedor Petrov) Suppose all roots of $g(x)$ have real part less than $-\frac12$; this implies $|\theta+1|<|\theta|$ for all roots $\theta$ of $g(x)$. So letting $h(x)\in\mathbb{Z}[x]$ be any irreducible factor of $g(x)$, we have $$|h(-1)|=\prod_{\theta:g(\theta)=0}|1+\theta|<\prod_{\theta:g(\theta)=0}|\theta|=|h(0)|=1,$$ so that $h(-1)=0$ and hence $h(x)=x+1$. Thus $g(x)=(x+1)^n$.

Lemma 2: For all primes $p$, the roots of $f_p(x)$ have real part less than $\frac32$.

Proof: This is evidently true for $p=2$. For $p\geq 3$ we prove a stronger claim by induction: if $z\in\mathbb{C}$ has $\text{Re}(z)\geq\frac32$ then $|f_p(z)|>2$. We'll check this explicitly for $p=3,5$. Writing $z=a+bi$ with $a\geq\frac32$, we have $$|f_3(z)|=|(a+1)+bi|\geq a+1 >2,$$ $$|f_5(z)|^2=|(a+bi)^2+1|^2=(a^2+(b-1)^2)(a^2+(b+1)^2)\geq a^4>4.$$ Now if $p\geq 7$, we have by the triangle inequality $$|f_p(z)|\geq \prod_{q\mid p-1} |f_q(z)|^{v_q(p-1)}-1.$$ If $p-1$ has any odd prime factor $q$, then $|f_2(z)|\geq\frac32$ and $|f_q(z)|>2$, so $|f_p(z)|>\frac32\cdot 2-1=2$. If on the other hand $p-1=2^k$ then $k\geq 3$ and so $|f_p(z)|>(\frac32)^3-1>2$.

Proposition: $f_p(x)$ is irreducible for all primes $p$.

Proof: Suppose $f_p(x)$ factors into non-constant polynomials $f_1(x)$ and $f_2(x)$. Since $f_p(2)=p$, we can assume without loss of generality that $f_1(2)=\pm 1$. Then $g(x):=f_1(x+2)$ is a monic integer polynomial with constant term $\pm 1$. If $g(x)$ is a power of $(x+1)$ then $f_1(1)=0$, contradicting $f_p(1)>0$. So by Lemma 1, $g(x)$ has a root with real part $\geq -\frac 12$. Thus $f_1(x)$ has a root with real part $\geq \frac 32$. This is automatically also a root of $f_p(x)$, contradicting Lemma 2.

Answer 2

This doesn't answer the main question (Edit: I have a different answer now that does), but it addresses the later edit (and is a bit too long for a comment): we do not have $|\theta-2|>1$ for all roots $\theta$ of $f_p(x)$. For a counterexample, take $$p=82213227818185749890859077=2^2\cdot 17\cdot 65537^5 + 1.$$ Then $$f_p(x)=x^2(x^4+1)(x^{16}+1)^5+1$$ has a root $\theta\approx 1.02017 + 0.19805 i$ with $|\theta-2|\approx 0.99965$. Primes of the form $k\cdot 65537^m+1$ for larger values of $m$ tend to produce counterexamples with roots even closer to $2$.

The polynomial $f_p(x)$ is still irreducible though, so the main question remains open.

Edit: Here's the method I used for finding this counterexample, and how to very quickly find many more counterexamples. As a warning, I haven't made any effort to be particularly rigorous or precise (or concise); this is just to provide a bit of intuition.

Key observation: If $f(x)$ is a polynomial, and $\theta$ is a root of $f(x)$ with multiplicity $m>1$, then when we replace $f(x)$ with $f(x)+1$, the root $\theta$ "explodes outwards:" $f(x)+1$ has a ring of $m$ roots around $\theta$. (Unrelated aside: if you walk through a redwood forest you'll often find redwood trees packed tightly together around a circle, see this image for example. These so-called "fairy rings" form when a large redwood tree is stressed, damaged, or cut down: when this happens, its roots sprout a bunch of new redwood trees in a circle around the original.)

Notably, this does not happen for simple roots: if $f(x)$ is a polynomial of large degree, and $\theta$ is a simple root of $f(x)$ relatively far from $x=0$, then in general $f(x)+1$ should have a simple root very close to $\theta$. (Roughly speaking, since $\theta$ isn't too close to $0$ we should expect that $f'(\theta)$ will be large, and so the distance between $\theta$ and a root of $f(x)+1$ is about $\frac{1}{|f'(\theta)|}\approx 0$.)

Now our goal is to find a polynomial $f_p(x)$ whose roots stretch as far to the right as possible in the complex plane (and in particular, into the circle of radius 1 around $x=2$). By construction, $f_p(x)-1$ is a product of terms of the form $f_q(x)^{m_q}$ for smaller primes $q$. If $m_q=1$, then each root of $f_q(x)$ will give us an essentially identical root of $f_p(x)$; we can't get very far using these. However, if $m_q$ is large, then each root of $f_q(x)$ will sprout a ring of roots of $f(x)$ - including some roots to the right, in the direction we want to go.

So here's the journey we take:

1. Start with $f_2(x)=x$. If we raise it to a large power and add one, the root $x=0$ will explode outwards. Since $65537$ is a Fermat prime, we have $f_{65537}(x)=x^{16}+1$. And indeed, the roots of $f_{65537}$ are the primitive $32$-nd roots of unity, a ring of $16$ roots around the origin: one of these, $e^{\pi i/16}$, is already extremely close to the circle of radius 1 around 2.
2. If we now raise $f_{65537}(x)$ to a large power $m$ and add one, the root $x=e^{\pi i/16}$ will explode outwards. Unfortunately there is no prime of the form $65537^m+1$, so $f_p(x)$ will never equal $f_{65537}(x)^m+1$. So we instead look for primes of the form $k\cdot 65537^m+1$. This corresponds to multiplying $f_{65537}(x)^m$ by some polynomial $f_k(x)$ and then adding $1$: importantly, $e^{\pi i/16}$ is still a root of multiplicty $m$, and so will still radiate outwards into a ring of $m$ roots upon adding $1$ at the end. Setting $m=5$, we find $k=68$ to be the smallest natural number such that $k\cdot 65537^5+1$ is prime, and sure enough, one of the sprouts coming out of $e^{\pi i/16}$ does cross the finish line.

Here's the plot of all the complex roots of $f_{65537}(x)=x^{16}+1$ in purple, the roots of $f_{17}(x)=x^4+1$ in red, and the roots of $f_p(x)$ in blue. You can also see a portion of the circle of radius 1 around $x=2$. Note that $f_{17}(x)$ divides $f_p(x)-1$ with multiplicity $1$, and so the red roots barely move at all; by contrast, since $f_{65537}(x)$ divides $f_p(x)-1$ with multiplicity $5$, the purple roots burst outwards into five new roots. Also $f_2(x)=x$ divides $f_p(x)-1$ with multiplicity $2$, so the origin bursts into two roots of $f_p(x)$, visible on the imaginary axis.

So to summarize, the goal is to find a sequence $p_1,p_2,\ldots$ of primes such that a large power of $p_i$ divides $p_{i+1}-1$. In our case this was $2,65537,68\cdot 65537^5+1$, but many other sequences will also do the trick. For each such sequence we should expect to get a sort of cascading fireworks effect: for each successive prime $p_{i+1}$, the roots of $f_{p_{i+1}}(x)$ will include a little exploded ring around each of the roots of $f_{p_i}(x)$.