shobber wrote: $A_1, A_2, \cdots A_k$ are [a partition of the set of positive integers]. Prove that for some $i \in \{ 1,2,\cdots,k \}$, there exsits infinity many non-factorable n-th degree polynomials so that coefficients of one polynomial are pairwise distinct and all the coeficients are in $A_i$. This is immediate if you have some quantitative version of the statement that "among monic degree $n$ polynomials the set of irreducible (non-factorizable) polynomials has density 1". One of the sets, say $A_i$, has positive upper density larger than $c > 0$. The set of polynomials with coefficients in $A_i$ has upper density at least $c^n$ in the set of degree $n$ polynomials; in particular, it must intersect the set of irreducible polynomials.

Well, that's nice, but I didn't know this density fact, so I solved it using Eisenstein's irreducibility criterion (EIC). EIC: If we have polynomial $f\in Z[x]$ $f(x)=a_{n}x^{n}+...+a_{1}x+a_{0}$ and prime $p$ such that $p/a_{i}$ for $i=0,...,n-1$ $p$ does not divide $a_{n}$ and $p^{2}$ does not divide $a_{0}$, then $f$ is irreducible. Solution to the problem: Let $p$ be a prime. Let $N_{1}= N-pN$. $(pN =\{ p,2p,... \})$ Consider all $j$ such that $A_{j}\cap pN$ is not finite set. Lets call the name of the set of such j's $J$. We have infinite many numbers divisible by $p$, but not divisible by $p^{2}$. So exist $K$, such that $K$ is subset of$J$ and if $k\in K$ then exist numbers in $A_{k}$ divisible by $p$, but not divisible by $p^{2}$. If $k\in K$ and $A_{k}\cap N_{1}\neq \emptyset$ then we do the following: 1.take $a_{n}$ be in $A_{k}\cap N_{1}$.(fixed) 2.take $a_{0}$ be in $A_{k}$ and $a_{0}$is divisible by $p$, but not divisible by $p^{2}$.(fixed) 3.take $a_{i}$ (i=1,...,n-1) be in $A_{k}$, $a_{i}$ is divisible by $p$and $a_{i}\neq a_{0}$, and all $a_{i}$ different. Then $f$ is irreducible! And there can be taken infinite number of such polynomials. Then the problem is solved! So for all $k\in K$, $A_{k}\cap N_{1}= \emptyset$ Now take $p_{2}\neq p$ and $N_{2}= N_{1}-p_{2}N_{1}$. By similar arguement there are another sets $A_{l}$ such that $A_{l}$ is subset of $N_{1}$ and $A_{l}\cap N_{2}= \emptyset$. Building $N_{3}, N_{4}$ and so on we reach moment when there are no $A_{i}$ left, contradiction! P.S. Sorry for the poor writing, I tried to make it as clear as I can.

Some parts of the proof are not clear to me so I'll try to rewrite it. We can assume that all subsets are nonempty. Let $ p_1<p_2<...$ be prime numbers. Let $ T_i=\mathbb{N} \backslash p_{i}\mathbb{N}$ and $ K_i=\{ap| a\in T_i\}$. We first consider $ K_1$, which is clearly infinite set, hence there exists nonempty family of subsets $ F_1$ such that $ A\in F_1 \Rightarrow |A\cap K_1|=\infty$ (by this I mean that intersection of these two sets is infinite). If we can find $ A\in F_1$ such that $ |A\cap T_1|\neq 0$ then if $ a\in A$ and $ a\in T_1$ we can take $ a_n=a$ and other coefficients in the set $ K_1$ to get infinietly many irreducible polynomials (using Eisenstein Criterion), hence we can assume, that $ A\in F_1\Rightarrow |A\cap T_1|=0$. By the same argument we get nonempty families of subsets $ F_i$ such that $ A\in F_i\Rightarrow |A\cap T_i|=0$, so for every $ i>0$ there exists subset $ A_{t(i)}$ such that $ |A_{t(i)}\cap T_i|=0$. Using Pigeonhole Principle there is a subset (WLOG) $ A_1$ and numbers $ i_1, i_2,...$ such that $ |A_1 \cap T_{i_m}|=0$ for $ m=1,2,...$. We assumed $ A_1$ is nonempty so we can find $ x\in A$. Let $ l\in \mathbb{N}$ such that $ p_{i_l}>x$. Then $ |A_1 \cap T_{i_l}|=0$ and since $ x<p_{i_l}\Rightarrow x\perp p$ we have $ x\in T_{i_l}$ and $ x$ is not an element of $ A_1$, contradiction.

Clearly one set $A_i$ contains an infinite subset $S$ of primes. Consider polynomials of the form $P(x)= \sum_{i=0}^{n} a_ix^i $ with $a_n$, $a_{n-1}$, $...$, $a_1$ chosen arbitrarily from $S$ and $a_0$ chosen such that $|a_0| > |a_1| + ... + |a_n|$. Its clear there are infitely many such polynomials. We claim they are irreducible. First, suppose $P(x)$ has a complex root $z$ such that $|z| \le 1$. Then $ |a_0| > |a_1| + ... + |a_n| \ge |a_1||z| + ... + |a_n||z^n| \ge |a_1z^1 + ... + a_nz^n| = |a_0| $ Which is a contradiction. It follows all roots of $P(x)$ have modulus greater than $1$. Suppose $P(x)=f(x)g(x)$ with $f$, $g$ integer polynomials of degree at least $1$. Then $a_0=|P(0)|=|f(0)||g(0)|$. Since $a_0$ is prime, it follows one of $|f(0)|$, $|g(0)|$ is $1$, WLOG $|f(0)|$. But then the modulus of the product of the roots of $f$ at most $1$, hence $f$ has a root of modulus at most $1$, so $P$ does too, a contradiction.

i've got the same solution as malcolm

Alternatively, we can use Perron's irreducibility criterion after noting that one of the sets is infinite.

What's Perron's irreducibillity criterion?