# Let $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Prove $|S| < \infty$

Question:

Let $$S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$$. Prove $$|S| < \infty$$.

Notice this is not true in $$\mathbb R[X]$$, as $$|x-a|\leq2^x$$, $$a\in[0,1]$$ shows. After experimenting a few rounds on Desmos, I have found no $$p(x)\in \mathbb Z[X]$$ with degree $$\geq3$$ satisfy this property. It looks like a piece of cake, but it turns out that the behavior of $$|p(x)|$$ is quite chaotic (If we drop the absolute value, the problem will become uninteresting). Of course, $$2^x$$ is going to eventually dominate all polynomials. But how can I prove all but finitely many polynomials dominate $$2^x$$ at the beginning? I think I've underestimated the difficulty of the problem. Any hint is appreciated.

• Are you taking the naturals to start with zero, or with one? – Gerry Myerson Feb 22 '19 at 12:19
• @GerryMyerson Does that make a difference? – YuiTo Cheng Feb 22 '19 at 13:14
• I think $0$ counts as a natural number. – YuiTo Cheng Feb 22 '19 at 13:24

Hint: Show that if $$f,g\in S$$, then the least $$n\in\mathbb{N}$$ such that $$f(n)\neq g(n)$$ cannot be too large, by thinking about what you can say about $$g(n)-f(n)$$.

A full solution is hidden below.

Let $$f,g\in S$$ be distinct and let $$n$$ be the least natural number such that $$f(n)\neq g(n)$$. We can then write $$g(x)=f(x)+x(x-1)(x-2)\dots(x-n+1)h(x)$$ for some polynomial $$h$$ with integer coefficients such thhat $$h(n)\neq 0$$. In particular, $$|h(n)|\geq1$$ so that $$|g(n)-f(n)|\geq n!.$$ But since $$f,g\in S$$, $$|g(n)-f(n)|\leq 2^{n+1}$$, and so we must have $$2^{n+1}\geq n!$$, and so $$n\leq 5$$.

In other words, any two elements $$f,g\in S$$ such that $$f(x)=g(x)$$ for $$x=0,1,2\dots,5$$ must be equal. Since there are only finitely many possibilities for the values $$f(0),f(1),\dots,f(5)$$, this shows that $$S$$ is finite.

• It seems that this argument only shows the least $n$ such that $f(n) \neq g(n)$ is smaller or equal to $5$. What if $\exists m>5 f(m) \neq g(m)$? How could we rule out such cases? – YuiTo Cheng Feb 23 '19 at 4:41
• I don't know why you think that needs to be "ruled out" and you seem to be confused about how the argument works. Read the final paragraph again. – Eric Wofsey Feb 23 '19 at 4:59
• Oh, I get it. So you have constructed an injection $q: S \rightarrow \{(a_1, a_2, a_3, a_4, a_5) : a_i \leq 2^i, a_i \in \mathbb N\}$, right? – YuiTo Cheng Feb 23 '19 at 5:08
• One last word: what's the exact cardinality of $S$? – YuiTo Cheng Feb 23 '19 at 5:15
• That's right. I don't know the exact cardinality, and it seems like it might be quite difficult to find it. – Eric Wofsey Feb 23 '19 at 5:21