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.

  • $\begingroup$ 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? $\endgroup$ – lulu Mar 23 '18 at 18:36
  • $\begingroup$ @lulu My mistake. I needed $f\neq g$ $\endgroup$ – Mastrem Mar 23 '18 at 18:37
  • $\begingroup$ Ok....but then how is $S=\{X\}$ an example? $\endgroup$ – lulu Mar 23 '18 at 18:37
  • $\begingroup$ @lulu well, the condition holds for all pairs of distinct polynomials in $S$, doesn't it? $\endgroup$ – Mastrem Mar 23 '18 at 18:40
  • $\begingroup$ @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$) $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ subtract -1 to every polynomial to fix $0$ $\endgroup$ – Exodd Mar 23 '18 at 18:57
  • $\begingroup$ Oh yea. Good call, lol. $\endgroup$ – Valborg Mar 23 '18 at 19:00

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.