# Polynomials of degree $\ge2$ whose images partition $\mathbb{N}$

I'm looking for a set of polynomials $S\subset \mathbb{Z}[X]$ such that $$f(\mathbb{Z})\cap g(\mathbb{Z})\cap\mathbb{N}=\emptyset$$
for all $f\neq g\in S$ and such that $$\bigcup_{f\in S}f(\mathbb{Z})\supset \mathbb{N}.$$ Now, this is pretty easy. Simply take $\{X\}\in \mathbb{Z}[X]$. However, I'm imposing the extra condition that $$\min\{\deg f:f\in S\}\ge 2.$$

Question does such a set of polynomials exist?

It's clear that such a set of polynomials must be infinite, but that's about as far as I got. Maybe one could generate these polynomials recursively, by taking the first few and then finding a polynomial which attains the lowest value not yet covered, while never obtaining a value already obtained by one of the others, but I fail to see how that would work exactly.

• Not sure I am following. Take any $f\in \mathbb Z$ for which $f(n)\in \mathbb N$ for some integer $N$. Then take $f=g$ in your first equality. Clearly $f(\mathbb Z)\cap f(\mathbb Z)\cap \mathbb N$ at least contains $f(n)$, no? – lulu Mar 23 '18 at 18:36
• @lulu My mistake. I needed $f\neq g$ – Mastrem Mar 23 '18 at 18:37
• Ok....but then how is $S=\{X\}$ an example? – lulu Mar 23 '18 at 18:37
• @lulu well, the condition holds for all pairs of distinct polynomials in $S$, doesn't it? – Mastrem Mar 23 '18 at 18:40
• @lulu Well, $3$ is a natural number, but as far as I know, not a square of an integer. Notice the direction of the set inclusion ($\supset$ instead of the usual $\subset$) – Mastrem Mar 23 '18 at 18:41

Allow me to assume that $0$ is not a natural number. If you want it to be, then we can probably fix this, but for now let's exclude it. Let $SF\subset\mathbb{N}$ be the set of square-free natural numbers. Consider the set of polynomials $P=\{nx^2|n\in SF\}$. I claim that these polynomials partition $\mathbb{N}$ in the way you want.
See the following post for the existence and uniqueness of factorizations of natural numbers into square and square-free parts: Show that every $n$ can be written uniquely in the form $n = ab$, with $a$ square-free and $b$ a perfect square
Now, it is clear by the existence part that $\bigcup f(\mathbb{Z})=\mathbb{N}$ for the polynomials $f\in P$. The uniqueness part guarantees us that the images of two different polynomials do not overlap.
EDIT: As Exodd noted below in a comment, you may simply subtract 1 from every polynomial in $P$ in order to fix the issue with $0$.
• subtract -1 to every polynomial to fix $0$ – Exodd Mar 23 '18 at 18:57
It is kind of a cheat, but since you are only requiring natural numbers, what about defining $$f_n(x) := -(n+1)x^2 +n$$ and and using the set $S := \{f_n|n\in \mathbb{N}\}$? As $f_n(x) < 0$ for all $x \neq 0$, we have$f_n(\mathbb{Z}) \cap \mathbb{N} = \{n\}$, so your conditions are trivially fulfilled.