Set of integers having finite intersection with the image of any polynomial of degree $\geq 2$

Question

Is there a set $A$ of positive integers such that

• $\sum_{n \in A} \frac{1}{n} = \infty$, and

• there is no polynomial $f \in \mathbb{Z}[x]$ of degree at least $2$ which takes infinitely many values in $A$?

Added on Feb 16, 2015: Seva answered this question completely. He proved even a great deal more -- namely, that there is a partition of $\mathbb{N}$ into

• a set $A$ of asymptotic density $1$ of 'non-values of non-linear polynomials', which has finite intersection with the image of any polynomial $f \in \mathbb{Z}[x]$ of degree $\geq 2$, and

• a set $B$ of asymptotic density $0$ of 'values of non-linear polynomials', which contains all but finitely many positive values taken by any polynomial $f \in \mathbb{Z}[x]$ of degree $\geq 2$.

Answer 1

There are countably many polynomials with integer coefficients of degree at least $2$; write them all in a sequence as $P_1,P_2,P_3,...\ $ For every $k\ge 1$, the set $A_k$ of all positive integers which are not the values of any of $P_1,...,P_k$ has a divergent sum of reciprocals: $\sum_{a\in A_k} 1/a=\infty$. Consequently, we can find pairwise disjoint, finite subsets $A_k'\subset A_k$ such that $\sum_{a\in A_k'} 1/a>1$. Now let $A:=\cup_{k\ge 1} A_k'$. By the construction, the series $\sum_{a\in A}1/a$ diverges, and for each $k\ge 1$, the image of $P_k$ is disjoint with $A_k'\cup A_{k+1}'\cup\ldots$; hence, has a finite intersection with $A$.

Indeed, a slight variation of this argument shows that there is a subset $A\subset{\mathbb N}$ of asymptotic density $1$ such that every non-linear polynomial with integer coefficients represents a finite number of elements of $A$ only. To see this, for every $k\ge 1$ fix an integer $N_k$, and let $B_k$ be the set of all positive integers larger than $N_k$ that are representable by $P_k$. We can choose $N_k$ large enough to have $|B_k\cap[1,x]|<2^{-k} x^{2/3}$ for every positive integer $x$, and then the set $B:=\cup_{k\ge 1} B_k$ will have zero asymptotic density. Consequently, the set $A:={\mathbb N}\setminus B$ will have asymptotic density $1$, and we will also have $A\cap{\rm Im} P_k\subseteq[1,N_k]$ for each $k\ge 1$.