2

I am facing the following problem:

Let $n \in \mathbb{N}_{\geq0}$ and $f \in \mathbb{Z}[X]$ be a polynomial with $\deg f = 2n + 1$, as well as (in pairs different) $a_1, \dots, a_{2n+1}$ such that $f(a_i) \in \{+1, -1\}, \forall i \in {1,\dots,2n+1}$. Show that $f$ is irreducible in $\mathbb{Z}[X]$ and $\mathbb{Q}[X]$.

Usually I have some ideas to start with, but this time I am totally stuck. One 'idea' would have been to show that $f$ is primitive and then try to show that $f$ is irreducible in $\mathbb{F}_2[X]$.

Any hints, ideas? Thank you very much in advance.

johnnycrab
  • 1,952
  • 12
  • 14

1 Answers1

3

Suppose $f = gh, g, h \in \mathbb{Z}[x]$. We'll show that at least one of $g$ or $h$ is constant.

If $f(a) = \pm 1$, then $g(a)$ and $h(a)$ are also equal to $\pm 1$. One of these, WLOG $g$, has degree at most $n$. But $g(a) = \pm 1$ for $2n+1$ different values of $a$. By pigeonhole, it takes the same value (either $1$ or $-1$) at least $n+1$ times, and so since it has degree at most $n$, it must in fact be constant with that value.

Qiaochu Yuan
  • 419,620
  • 1
    I would phrase your argument a little differently. I would say that, since the $2n+1$ values $g(a_i)$ are each equal to 1 or -1, at least $n+1$ of them must be the same, so that $g$ must be this constant value. – marty cohen Nov 29 '15 at 00:26
  • @marty: mm, yeah, that's definitely cleaner. I went to the contrapositive to avoid a proof by contradiction but I think I was a little confused. I'll rewrite. – Qiaochu Yuan Nov 29 '15 at 00:37