10

This question is directly inspired by this question. Consider polynomials of the form $$p(x) = \prod_{i=1}^n(x-i)^2 - d.$$ For which values of $n$ and $d$ is $p(x)$ irreducible? There is a theorem of Polya, cited in the original question, which states that:

If for $n$ integral values of $x,$ a polynomial $q(x)$ of degree $n$ has values which are different from $0,$ are smaller in absolute value than $$\frac{\lceil n/2\rceil!}{2^{\lceil n/2\rceil}},$$ then $q(x)$ is irreducible over $\mathbb{Q}.$

This seems to not quite apply to the given type of polynomial (though it would, if there were no squares).

In this paper, there is a reference to a paper of Brauer, Brauer, and Hopf(!) from 1926 which addresses the question (of Schur) on irreducibility of polynomials of the form $g(f(x)),$ but it seems that their $g$ always has constant coefficient $1,$ so this is not directly applicable.

Surely, technology has advanced since those days, and even the Galois groups can be computed (I assume the Galois group is the full symmetric group for most choices of $n$ and $d.$)

What makes the whole thing strange is that the original question (with $n=2013$ and $d=2014$) was supposedly an entrance exam question at Peking university. So this is either child abuse, or there is some simple trick.

Community
  • 1
Igor Rivin
  • 95,560
  • That was the first thing I tried, actually, and the intermediate coefficients are NOT all even. – Igor Rivin Jan 08 '14 at 04:46
  • My comment was in response to a suggestion to use Eisenstein criterion mod 2, but that does not work. – Igor Rivin Jan 08 '14 at 04:47
  • 2
    I don't think the bit about the Galois group is right. After adjoining the square root of $d$ (degree 2 extension), we are left with a degree $n$ equation. Thus, unless $d$ is a square, the Galois group has a subgroup of index 2 that is a subgroup of $S_n.$ Of course, if $d$ is a square, we get a subgroup of $S_n$ "on the nose". – Victor Protsak Jan 08 '14 at 07:04
  • @VictorProtsak you are right, of course. – Igor Rivin Jan 08 '14 at 13:59
  • The original problem has now been solved over at math.SE http://math.stackexchange.com/a/630759/448 . – David E Speyer Jan 08 '14 at 18:12
  • I suspect that $2$-adic methods can get you somewhere in the original case: If $f(x) = g(x) h(x)$ with $g(0)$ even and $h(0)$ odd, then looking at the $2$-adic Newton polygon shows that $g$ has an irreducible factor of degree $\geq 2012$ and the Newton polygon of $f(x-1)$ shows that $h$ has an irreducible factor of degree $\geq 2014$. So the only possible factorization is degree $2012$ times $2014$. I feel like this should violate the required Galois structure, but I don't see a quick contradiction. – David E Speyer Jan 08 '14 at 18:13
  • @DavidSpeyer I guess none of us get to attend Peking university (the solution you allude to in the other comment is a 13 page Annals of Math(!) paper). – Igor Rivin Jan 08 '14 at 18:17
  • @Igor: Probably whomever posed the question had an erroneous solution in mind. This appears to have been a PhD-entrance exam, right? I've seen other situations in which written qualifying exams for PhD students have questions which stump faculty experts because the person who put the question on the exam didn't write out a complete solution and so didn't realize how hard it is. – user76758 Jan 08 '14 at 20:32
  • @user76758 perhaps they mistakenly thought Eisenstein's criterion worked... – Igor Rivin Jan 08 '14 at 20:42
  • @Igor: Yes, that sounds like a realistic possibility. Anyway, I prefer the admissions system using recommendation letters rather than entrance exams. :) – user76758 Jan 09 '14 at 00:20
  • @user76758 unfortunately, the recommendation letter system is also open to abuse. – Igor Rivin Jan 09 '14 at 00:25
  • 1
    @Igor: just to clarify, this problem was solved in an Annals paper from 1933. The standards of the Annals have changed dramatically in the past 80 years. – Michael Zieve Jan 09 '14 at 02:31
  • @MichaelZieve Yes, but not enough to make this an exam problem (SOME annals papers from those days are now standard material), but I don't think this is one of them. Of course, you are much (infinitely?) wiser in this field than I... – Igor Rivin Jan 09 '14 at 02:37
  • 1
    @Igor: first, that Annals paper doesn't answer the entrance exam question, since it only addresses the case $d=\pm 1$. Second, what is done in that Annals paper is certainly simple enough to be an exam problem. – Michael Zieve Jan 09 '14 at 03:56
  • @MichaelZieve fair enough... – Igor Rivin Jan 09 '14 at 04:13
  • @MichaelZieve Nice! DOes Polya's argument follow a similar scheme? – Igor Rivin Jan 09 '14 at 05:00
  • @MichaelZieve yes, this is markdown, so this: http://daringfireball.net/projects/markdown/syntax#link should tell you what you need to know. – Igor Rivin Jan 09 '14 at 05:04
  • 1
    I posted an answer to the entrance exam question (the case $n=2013$ and $d=2014$) over at math.SE math.stackexchange.com/a/630759/448. My argument applies for many other pairs of values $(n,d)$; I just need $n$ to be sufficiently large compared to the number of divisors of $d$. I don't know what happens when this condition fails. – Michael Zieve Jan 09 '14 at 05:08
  • By the way, Igor, we are lacking the context for the "entrance exam" situation. To illustrate what I mean, here are two real stories. 1. At his "candidacy minimum" exam at the chair of Algebra in MGU, a friend of mine (who is a well-known mathematician) was asked to prove that a stably free module over a ring of polynomials in $n$ variables is free (aka Serre's problem and Suslin's theorem). I was astonished to learn that, but while it's beyond fantasy to expect anyone to come up with their own proof, it turns out that this question was included in the official list of examination questions. – Victor Protsak Jan 09 '14 at 06:03
  • (cont'd) Moreover, while the conjecture had been long open, the recommended proof was not even that difficult to digest. 2. I took a PhD qualifying exam in analysis at Yale and was unable to solve one of the problems, no matter how hard I tried (it was one of these "till you drop" exams). It turns out that in order to solve it, one had to use Phragmén–Lindelöf principle, something that I had no clue about. Now, extensive archives of previous exams did not have such a question. But the professor in charge of the exam had just taught this material in the qualifying course, so it was still fair. – Victor Protsak Jan 09 '14 at 06:18
  • @MichaelZieve,very nice answer!.and I have post this problem:http://math.stackexchange.com/questions/632299/how-prove-x-14x-24-cdotsx-201342014-is-reducible – math110 Jan 09 '14 at 08:32
  • 1
    Hello,This problem is from Peking university graduate record examination questions(2014,0401) – math110 Jan 09 '14 at 08:45
  • it is said Provides the problems is the famous research number theory Peking university,and this exam is very hard. – math110 Jan 09 '14 at 08:59
  • Taking into account the level of the Chinese IMO team, the Chinese national competition, it is clear that the original problem is well at the level of a fair number of the candidates for admission. – O.R. Jan 09 '14 at 15:37
  • @ABC I disagree. Mike Zieve is pretty much the best in the world at this sort of thing, so the fact that he could come up with a nice (but nontrivial) solution means nothing regarding the problem's suitability. – Igor Rivin Jan 09 '14 at 19:00

1 Answers1

6

I prove here that $\prod_{i=1}^n (x-a_i)^2 + d$ is irreducible over $\mathbf{Q}$ whenever the $a_i$ are distinct integers, $n\ge 6$, and $d$ is squarefree, $d>1$, and $d\not\equiv 3\pmod{4}$.

The hypotheses on $d$ ensure that the ring of algebraic integers in $\mathbf{Q}(\sqrt{-d})$ is $\mathbf{Z}[\sqrt{-d}]$, and that the only units in this ring are $\pm 1$. Write $f(x):=\prod_{i=1}^n (x-a_i)$, and let $\alpha$ be a root of $f(x)^2+d$, so that $\beta:=f(\alpha)$ satisfies $\beta^2=-d$. Suppose that $f(x)^2+d$ is reducible over $\mathbf{Q}$, so that $[\mathbf{Q}(\alpha):\mathbf{Q}]<\deg(f(x)^2+d)=2n$. Since $$[\mathbf{Q}(\alpha):\mathbf{Q}]=[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)]\cdot [\mathbf{Q}(\beta):\mathbf{Q}] = 2[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)],$$ it follows that $[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)]<n$, so that $f(x)-\beta$ is reducible over $\mathbf{Q}(\sqrt{-d})$. Write $f(x)-\beta=g(x)h(x)$ with $g,h$ nonconstant polynomials in $\mathbf{Q}(\sqrt{-d})[x]$. Since $f(x)-\beta$ is monic, we may assume that both $g$ and $h$ are monic. Since $f(x)-\beta$ is a monic polynomial whose coefficients are algebraic integers, all of its roots are algebraic integers. Therefore both $g$ and $h$ are monic polynomials all of whose roots are algebraic integers, so the coefficients of $g$ and $h$ are algebraic integers; since these coefficients are also in $\mathbf{Q}(\sqrt{-d})$, it follows that $g$ and $h$ are in $\mathbf{Z}[\sqrt{-d}][x]$.

Now substitute $x=a_i$ into the identity $f(x)-\beta=g(x)h(x)$, to get $-\beta=g(a_i)h(a_i)$. Hence $g(a_i)$ is an element of $\mathbf{Z}[\sqrt{-d}]$ which divides $\beta$, so taking norms gives $N(g(a_i))\mid N(\beta)=d$. Since $d$ is squarefree, the only elements of $\mathbf{Z}[\sqrt{-d}]$ whose norm divides $d$ are $\pm 1$ and $\pm\sqrt{-d}$. Thus $g(a_i)\in\{\pm 1,\pm\sqrt{-d}\}$.

First suppose that $g(a_i)$ takes the same value (call it $c$) for every $i$. Then $g(x)-c=f(x)G(x)$ for some $G(x)\in\mathbf{Z}[\sqrt{-d}][x]$, which is impossible since $0<\deg(g)<\deg(f)$.

Hence there exist $i,j$ with $g(a_i)\ne g(a_j)$. Since $n\ge 6$, it follows that there exist $r,s$ for which $g(a_r)\ne g(a_s)$ and $a_r\ge a_s+3$: for, this is clear if $\lvert a_i-a_j\rvert\ge 3$, and if $\lvert a_i-a_j\rvert<3$ then there exists $k$ such that $\lvert a_i-a_k\rvert\ge 3$ and $\lvert a_j-a_k\rvert\ge 3$, and we must have either $g(a_i)\ne g(a_k)$ or $g(a_j)\ne g(a_k)$.

Finally, $a_r-a_s$ divides $g(a_r)-g(a_s)$ in $\mathbf{Z}[\sqrt{-d}]$. Since $a_r-a_s$ is an integer $\ge 3$, and $g(a_r),g(a_s)$ are distinct elements of $\{\pm 1, \pm\sqrt{-d}\}$, this is impossible.

Michael Zieve
  • 6,387