From Romania TST 2004 Day 5 P3, I was introduced to the polynomial $$f(x)=\sum_{i=1}^{p-1} \left( \frac{i}{p} \right)x^{i-1}$$ This polynomial is clearly not irreducible - $x=1$ is a root.

Even more - this MO thread gives that for $p \equiv 1 \pmod{4}$, we have $$f(x)=(x-1)^2(x+1)k(x)$$ for a integer polynomial $k(x)$.

While the MO thread above asks for irreducibility of the $k(x)$, I am interested in the irreducibility of $$g(x)=1+xf(x)$$

Now I checked that this is irreducible for $p \le 17$ (I know, not a lot).

I tried to use Eisenstein Criterion to prove it - just like the irreducibility of cyclotomic polynomials, I substituted $x+1$ instead of $x$, but then I get $$g(x)=1+ \sum_{i=1}^{p-1} \left( \frac{i}{p} \right) (x+1)^i$$

Now let $$g(x) = \sum_{i=0}^{p-1} a_ix^i$$

We get $$a_k = \sum_{i=k}^{p-1} \binom{i}{k} \cdot \left(\frac{i}{p}\right)$$ So $a_{p-1} = \left( \frac{-1}{p} \right)$ and $a_0=1$ which is okay, but I can't seem to find a prime $q$ such that $q|a_i$ for all $1 \le i \le p-2$, i.e. an appropriate prime to use the Eisenstein Criterion.

Checking again for $p \le 11$, I couldn't find a prime for all of them.

So I scratched the $x+1$ idea and moved on with $x-1$.

We would get $$a_k = \sum_{i=k}^{p-1} (-1)^{i-k}\binom{i}{k} \cdot \left(\frac{i}{p}\right)$$

The problem is that the right primes for Eisenstein does not appear here as well.

I've tried to use Perron's and Cohn's Criterion but it obviously fails.

Question. Is $g(x)$ irreducible for all $p$?

If not, what is the counterexample?

If correct, is there a suitable irreducibility criterion for this problem?

Am I using 'overpowered' techniques on a problem that is easy? (I'm pretty sure I'm not)

  • 3
    $\begingroup$ I have tested if for a 1000 primes. They are all irreducible so this looks like this is always true. Some of these polynomials are also cyclotomic polynomials but some of them are not. Maybe that will help? $\endgroup$ Commented Dec 3, 2015 at 22:02
  • $\begingroup$ The Eisenstein criterion only has a chance of working for a prime $p$ if $p$ divides the discriminant of the polynomial. So perhaps you can check if the discriminant has some nice pattern to its form and then what primes are possible. See en.wikipedia.org/wiki/… and math.stackexchange.com/questions/1280964/… . Of course if you find it's not always Eisenstein, this doesn't mean it's not irreducible, but it's a start. $\endgroup$ Commented May 31, 2019 at 23:21


You must log in to answer this question.

Browse other questions tagged .