Does there exist a a sequence $a_{0},a_{1},a_{2},\dots$ in $\mathbb N$, such that for each $i\neq j, (a_{i},a_{j})=1$, and for each $n$, the polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ is irreducible in $\mathbb Z[x]$? By Omid Hatami
Problem
Source: Iran TST 2007, Day 3
Tags: algebra, polynomial, number theory proposed, number theory
22.05.2007 22:05
Sure -- the simplest example I can think of is to take $a_{n}= p_{n}$ for a sufficiently fast increasing sequence of primes, so that all zeros of $\sum_{i=0}^{n}p_{i}z^{i}= 0$ lie inside $|z| < 1$ (for instance, it suffices that $p_{n}> p_{n-1}+\cdots+p_{0}$). Was this also your original solution? Of course, "most" sequences you take have this property, but for "most" explicit (closed-form given) sequences it should be very difficult if impossible to prove the irreducibility. I propose this more difficult problem: is there an infinite set $A$ of positive integers such that for any pairwise different elements $a_{0},\ldots,a_{n}\in A$ the polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ is irreducible?
22.05.2007 22:27
Very nice idea, to use the fact that if all the complex roots are inside the unit circle, then the polynomial is irriducible in Z!
23.05.2007 03:36
Of course this came to my mind vess. I wanted to find all subsets $S\subset \mathbb N$ such that there exists a sequence $a_{0},a_{1},\dots\in S$ such that $\sum_{i=0}^{n}a_{i}x^{i}$ is irreducible for each $n$. I proposed this problem as part (a) of the problem, but it was removed before the exam: Find the size of smallest $S\subset \mathbb N$ such that the following sequence exists. It is easily proved with Eisenstein that for $S=\{p,q\}$ ($p,q$ primes) the sequence $a_{0}=p$, and $a_{i}=q$ for $i\geq 1$ satisfies the problem conditions. Of course more than this could be said. If $S$ has two square-free elements, then also with Eisenstein we can prove that such sequence exists. But for the set $\{4,9\}$, I have no idea. I would be very happy if anyone finds all subset $S\subset\mathbb N$ such that for the the sequnce exists.
23.05.2007 16:35
I can reproduce an idea of Ljunggren to prove that every two-element set $S$ has your property. Does this answer your question completely? Of course, Eisenstein can't be applied in this general case (e.g., for $\{4,9\}$). To get an idea how to do this, take a quick look at the slides http://www.math.sc.edu/~filaseta/seminars/SeminarNotes102901.pdf and http://www.math.sc.edu/~filaseta/seminars/michiganlect00.pdf and, even better, browse some papers of M. Filaseta on his webpage. (Obviously, one of the best places to look for irreducible polynomials ) But the problem I intended was different, have you thought on this: construct an infinite set $A$ such that for any $n$ and every (not just some!) sequence $a_{0},\ldots, a_{n+1}$ of $n+1$ pairwise different elements of $A$, the polynomial $\sum_{0}^{n}a_{i}x^{i}$ is irreducible (hence allowing arbitrary rearrangements of the sequence)?
23.04.2013 14:30
I think it is same as the problem China TST 2006 problem
16.03.2014 00:22
"Very nice idea, to use the fact that if all the complex roots are inside the unit circle, then the polynomial is irriducible in Z!" Please, could someone explain, why is it true? For example, the polynom (2x-1)^2.
21.10.2015 02:46
I think this works : We proceed inductively,taking a suitable base case $2+3x$ as a polynomial and then after having assumed a construction for $a_1,...,a_{n-1}$ we define $a_n$ as a number having no prime dividing any of the previous terms and $a_n$ much larger in absolute value than the sum of absolute values of $a_i's$ for $i=0,1,...,n-1$. Now, Perron's criterion for irreducibility nails it.
05.06.2016 05:55
anantmudgal09 wrote: $a_n$ much larger in absolute value than the sum of absolute values of $a_i's$ for $i=0,1,...,n-1$. Now, Perron's criterion for irreducibility nails it. Unfortunately this is not true because Perron's criterion only applies when the coefficient in front of $x^{n-1}$ is very large. However the recursive construction can be salvaged. Suppose we have $a_0, a_1, \dots, a_{n}$ such that all polynomials $\sum_{t = 0}^{k} a_{i_t} x^t$ with $i_0, i_1, \dots, i_k$ distinct indices in $[0,n]$ are irreducible. We want to find $a_{n+1}$ so that the same holds if some $i_t$ equals $n+1$. Abstractly, we need a finite family of polynomials $\{P_{\alpha}(x) + a_{n+1} x^{t_{\alpha}}\} $ to be simultaneously irreducible. By Hilbert's irreducibility theorem, every polynomial in the family is irreducible for "almost all" $a_{n+1}$. The result follows.
22.01.2021 18:39
Sorry for reviving. vess wrote: Sure -- the simplest example I can think of is to take $a_{n}= p_{n}$ for a sufficiently fast increasing sequence of primes, so that all zeros of $\sum_{i=0}^{n}p_{i}z^{i}= 0$ lie inside $|z| < 1$ (for instance, it suffices that $p_{n}> p_{n-1}+\cdots+p_{0}$). I couldn't understand how this directly implies it's irreducible. Could someone please explain?
22.01.2021 22:52
If you mean why the zeroes of $P(x):=\sum_{i=0}^{n}p_{i}z^{i}$ lie inside $|z|<0$ it's due to the Rouche's theorem ( $p_nz^n$ and $P(z)$ have the same number of roots inside $|z|<1$ providing $p_{n}> p_{n-1}+\cdots+p_{0}$ ). If the question is why $P$ is irreducible then here's why: Suppose $P(x)=Q(x)R(x)$ and both $Q,R$ are with integer coefficients. Then one of them, say $Q$, is monic (with senior coefficient $1$) since all $p_i$ are primes. So, $Q$ is a monic polynomial with all roots lying inside $|z|<1.$ It means the constant term of $Q$ has absolute value less than $1$, hence it must be $0$. But $z=0$ is not root of $P$.
22.01.2021 23:28
Thank you very much.
16.06.2023 11:38