Feel free to delete this question if it has been asked somewhere else before.

I've recently stumbled upon this question on the Mathematics StackExchange and I've wondered how the polynomials for higher n would look. I am asking for irreducible polynomials, because without this restriction, one would get trivial polynomials like $f(x) = n*x$ for which each output is divisible by n. These can be reduced by e.g. the constant factor $n$ and hence would not be irreducible. If it is unclear, by "irreducible" I mean "irreducible over $\mathbb{Z}$", so only integer polynomials are allowed, no (ir)rationals.

I've made a bit of progress on this problem regarding some values of $n$ that I will list below. I am also well aware that many questions asking for specific cases have already been answered and I would just like to expand on them.

$n = 1: f(x) = x + C \land C \in \mathbb{Z}$. All of these are irreducible.

$n = 2: f(x) = x^2 + x + C$ or $f(x) = x^2 - x + C \land C \in \mathbb{Z} \land C \equiv 0 \mod{2}$. This is basically equivalent to stating that C must be even. Again, all of these are irreducible.

At this point I will omit the $C$ - term and just state that $ C \in \mathbb{Z} \land C \neq 0 \land C \equiv 0 \mod{n}$ for all n. Correct me if I am wrong on that.

In the question mentioned above, a polynomial for $n = 30$ is showcased, that can be made irreducible with a little bit of tweaking for C:

$n = 30: f(x) = x^5 - x + 30$. Thus $C = 30$.

This short analysis has lead me to a couple of questions:

(1) Are there infinitely many, non-trivial (irreducible) polynomials for a given n? If not, how many are there for a certain n? Is it bounded in any way?

(2) Does a pattern in the generated polynomials exist, or at least for a part of them?

(3) Is there a more efficient way than trial-and-error backtracking when trying to find a polynomial for given n?

So far I've just tried to find examples by trial-and-error and I am excited if there is any theory behind this question. Thank you in advance!

EDIT: Oh, and with "Trial and Error" I mean I looked at quadratic, cubic,... congruences for modulo n.

  • $\begingroup$ It would improve the body of your Question to spell out that you are interested in integer polynomials irreducible over $\mathbb Z$ (or equivalently, primitive and irreducible over $\mathbb Q$). If you simply mean the greatest common divisor of coefficients is $1$, this is conveyed by the term primitive integer polynomial. $\endgroup$ – hardmath May 22 at 19:48

For (2), I suspect it will be very hard to characterise all such polynomials, but one approach would be to consider a result from Polya and Ostrowski (1920) which states that every integer to integer polynomial must be a linear sum of binomial coefficients.

The answer to the other two parts is yes: Consider $(x-1)(x-2)\ldots(x-n)$, which clearly works.

Just as an aside, your definition of "irreducible" is not what most people mean -- for instance, $x^5-x=x(x-1)(x+1)(x^2+1)$ is reducible.

As a double aside:

Let $P(x)=(x-1)(x-2)\ldots(x-n)+pn$ for a prime $p>(2n)!\,$ Then we know that, by iterated triangle inequality, the polynomial $P(x)$ has no complex roots of magnitude less than $n$ (Suppose $|\alpha|<n$ is a root. Then $|(\alpha-1)(\alpha-2)\ldots(\alpha-n)|<(2n)!<pn$). Now suppose $P(x)=Q(x)R(x)$ for integer polynomials $Q,R$. Then the constant term of one of the polynomials is divisible by $p$, so the constant term of the other polynomial has absolute value at most $n$, so by Vieta's formula, it has at least one root with absolute value at most $n$, a contradiction.

Thus the family of $P$ above is an infinite family of solutions to the original question.

  • $\begingroup$ ... but with a little adjustment we find the irreducible $x^5-x+60$ $\endgroup$ – Hagen von Eitzen May 22 at 19:45
  • $\begingroup$ Ah yes, it is even stated in the other question. I forgot that, my bad. But the question still stands then for n = 30, since the construction method you mentioned builds off smaller polynomials and thus is reducible. @HagenvonElitzen Huh, that's interesting. Did you find it by accident/trial and error or did you apply a specific method? $\endgroup$ – TheOutrageousZ May 22 at 19:50
  • $\begingroup$ Technically speaking, your answer "builds off" smaller polynomials too. But anyways if you want you can just add a constant $kn$ to the end of the thing and it'll work $\endgroup$ – auscrypt May 22 at 19:52
  • $\begingroup$ @auscrypt I've just noticed that too. Damn. Is this really irreducible for each C (with the restrictions stated above)? I think it is, but I'm too lazy to see if I can prove it. $\endgroup$ – TheOutrageousZ May 22 at 20:04
  • $\begingroup$ I'll accept your answer anyway since you've shown a (hopefully) valid way to generate these. Thanks! $\endgroup$ – TheOutrageousZ May 22 at 20:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.