Something related to this problem: Prove that for a set $ S\subset\mathbb N$, there exists a sequence $ \{a_{i}\}_{i = 0}^{\infty}$ in $ S$ such that for each $ n$, $ \sum_{i = 0}^{n}a_{i}x^{i}$ is irreducible in $ \mathbb Z[x]$ if and only if $ |S|\geq2$. By Omid Hatami
Problem
Source: Iranian National Olympiad (3rd Round) 2007
Tags: number theory proposed, number theory
29.08.2007 04:12
if $ |S|<2$ we must have $ |S|=1$ ($ S=\{a\}$) we have for $ n=3$: $ \forall\{a_{i}\}_{i\in\mathbb{N}}\in S=\{a\}:\sum_{k = 0}^{3}a_{k}x^{k}=a(x^{3}+x^{2}+x+1)$ isn't irreducible in $ \mathbb{Z}[X]$. if $ |S|\ge 2$ we take $ a,b\in S$ such that $ a=a'd,b=b'd,a'>b',gcd(a',b')=1$ we take $ \{a_{i}\}_{i\in\mathbb{N}}\in S:\ a_{0}=a,\forall i>0,a_{i}=b$ then we have $ \forall x\in\mathbb{Z}:\forall n\in\mathbb{N}\frac{\sum_{k=0}^{n}a_{k}x^{k}}{d}\equiv a'\ (mod\ b')\not\equiv 0\ (mod\ b')$ then $ \forall n\in\mathbb{N},\forall x\in\mathbb{Z}:\sum_{k=0}^{n}a_{k}x^{k}\neq 0$ so $ \forall n\in\mathbb{N}:\ \sum_{k = 0}^{n}a_{k}x^{k}$ is irreducible in $ \mathbb{Z}[X]$.
04.08.2020 17:38
Obviously above solution for $\mid S\mid \geq 2$ is wrong It’s the right time for “BUMP”.
07.11.2020 14:51
yes @above, you're rigth \bump
08.10.2021 08:28
Iranian National Olympiad (3rd Round) 2007 wrote: Prove that for a set $ S\subset\mathbb N$, there exists a sequence $ \{a_{i}\}_{i = 0}^{\infty}$ in $ S$ such that for each $ n$, $$ \sum_{i = 0}^{n}a_{i}x^{i}$$is irreducible in $ \mathbb Z[x]$ if and only if $ |S|\geq2$. Here's a proof for the $|S| \ge 2$(the 'if' direction') Choose primes \begin{align*} p_1=a_0 10^2+a_1 \\ p_2=a_0 10^3+a_1 10^2+a_2 \\ . \\.\\.\\.\\p_n=\sum_{i = 0}^{n}a_{i}10^{i} \end{align*}which by Dirchlet's theorem exist, hence by Cohn's irreduciblity Criterion $$ \sum_{i = 0}^{n}a_{i}x^{i}$$is irreducible.$\blacksquare$