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.

Follow-up question: Let $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Find $|S|$.

  • $\begingroup$ Are you taking the naturals to start with zero, or with one? $\endgroup$ – Gerry Myerson Feb 22 '19 at 12:19
  • $\begingroup$ @GerryMyerson Does that make a difference? $\endgroup$ – YuiTo Cheng Feb 22 '19 at 13:14
  • $\begingroup$ I think $0$ counts as a natural number. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – YuiTo Cheng Feb 23 '19 at 4:41
  • $\begingroup$ 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. $\endgroup$ – Eric Wofsey Feb 23 '19 at 4:59
  • $\begingroup$ 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? $\endgroup$ – YuiTo Cheng Feb 23 '19 at 5:08
  • $\begingroup$ One last word: what's the exact cardinality of $S$? $\endgroup$ – YuiTo Cheng Feb 23 '19 at 5:15
  • $\begingroup$ That's right. I don't know the exact cardinality, and it seems like it might be quite difficult to find it. $\endgroup$ – Eric Wofsey Feb 23 '19 at 5:21

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.