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$ Commented Oct 6, 2021 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$ Commented Oct 6, 2021 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$ Commented Oct 7, 2021 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$ Commented Oct 7, 2021 at 20:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.