Something related to this problem: Prove that for a set S⊂N, there exists a sequence {ai}∞i=0 in S such that for each n, ∑ni=0aixi is irreducible in Z[x] if and only if |S|≥2. 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: ∀{ai}i∈N∈S={a}:∑3k=0akxk=a(x3+x2+x+1) isn't irreducible in Z[X]. if |S|≥2 we take a,b∈S such that a=a′d,b=b′d,a′>b′,gcd(a′,b′)=1 we take {ai}i∈N∈S: a0=a,∀i>0,ai=b then we have ∀x∈Z:∀n∈N∑nk=0akxkd≡a′ (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