Define the Erdős polynomial to be $f_n(x):= \sum \limits_{0 \leq i,j \leq n}^{}{x^{ij}}$ (the name is motivated by http://oeis.org/A027424).

For example for $n=5$, the polynomial is given by $x^{25}+2x^{20}+x^{16}+2x^{15}+2x^{12}+2x^{10}+x^9+2x^8+2x^6+2x^5+3x^4+2x^3+2x^2+x+11$.

Question 1: Is $f_n(x)$ always irreducible (over $\mathbb{Q}$)? If not, when is it irreducible?

It is irreducible for $n \leq 20$.

More generally, define for $k \geq 2$ the polynomial $f_n^k(x):= \sum \limits_{0 \leq i_1,i_2,...,i_k \leq n}^{}{x^{i_1 ... i_k}}$.

Question 2: Is $f_n^k(x)$ always irreducible? If not, when is it irreducible?

For $k=3$, it is irreducible for $n \leq 8$.

  • 1
    $\begingroup$ If my PARI code is correct, then the first conjecture is true for $n\leq100$. $\endgroup$ Oct 6 at 21:18
  • 2
    $\begingroup$ @ThomasBrowning, I have a test running in Sage which has got up to 167 so far without finding a counterexample. $\endgroup$ Oct 6 at 23:09
  • 2
    $\begingroup$ It seems like all roots of $f_n(x)$ might lie outside the unit circle. Not sure how to prove it, but this is the sort of thing that can sometimes be useful for proving irreducibility. $\endgroup$ Oct 7 at 6:22
  • 2
    $\begingroup$ Checked up to 232, but it's taken the past 12 hours to get from about 208 to 232 so I'm killing it now. $\endgroup$ Oct 7 at 20:17

Your Answer

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

Browse other questions tagged or ask your own question.