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

Question

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

This is a follow-up question to this. (Thanks to @EricWofsey for brilliant answer.) Please see the previous post to see his proof since I don't want to reproduce it here. I'm phrasing this as a separate question because I want to accept his answer. Still, it's not obvious to me that what's the exact cardinality of $S$. I haven't found any polynomials with degree $> 3$ satisfy this property. The one who gave the initial problem to me didn't know the answer, either. There is enough evidence to suspect this is going to be much harder. Can someone provide some insight? Many thanks.

Answer 1

If I have not made a calculation error: There are exactly 49 such polynomials (all of degree at most 3). They are the 23 polynomials \begin{multline*} \{x-1,x,x+1,2 x-1,2 x,x^2-4 x+1,x^2-3 x,x^2-3 x+1,x^2-2 x-1,\\ x^2-2 x,x^2-2x+1,x^2-x-1,x^2-x,x^2-x+1,x^2-1,2 x^2-5 x+1,\\ 2 x^2-4 x,x^3-6 x^2+6 x+1,x^3-6 x^2+7x-1,x^3-6 x^2+7 x,\\ x^3-6 x^2+8 x-1,x^3-5 x^2+4 x,x^3-5 x^2+4 x+1\}, \end{multline*} their negatives, and the constant polynomials $-1$, $0$, and $1$. It's not that hard an exercise to confirm that each of these polynomials satisfies the appropriate bounds, so let me describe how I showed that these are the only candidates for such polynomials.

As Eric Wofsey showed, each polynomial $p(x)\in S$ is characterized by the $6$-tuple $\big( (p(0), p(1), \dots, p(5) \big)$. There are $3\times5\times9\times17\times33\times65 = 4{,}922{,}775$ such $6$-tuples.

However, the values of a polynomial $p(x)$ with integer coefficients have the property that if $i \equiv j\pmod m$, then $p(i)\equiv p(j)\pmod m$. This observation leads to several consistency checks that can be done to eliminate most of the $6$-tuples in the list above; indeed, only $537$ of them survive these filters.

For each surviving $6$-tuple, we compute the interpolating polynomial of degree at most $5$ taking those values at $0,1,\dots,5$. It turns out that all such polynomials have coefficients in $\frac12\mathbb Z$.

Some of these polynomials $p(x)$ satisfied the bound $|p(6)| \le 2^6$. If not, then (again using Eric Wofsey's idea) we can try adding multiples of $\frac12x(x-1)(x-2)(x-3)(x-4)(x-5)$ to $p(x)$ to minimize its absolute value at $6$. (There is a factor of $\frac12$ here because at this stage we are allowing coefficients in $\frac12\mathbb Z$.) But for many of the $537$ polynomials, there is no such modification that yields an absolute value at $x=6$ that is at most $2^6$. This proves that the corresponding $6$-tuples do not yield any polynomial in $S$.

Only $183$ polynomials/$6$-tuples remain after this stage. We do a similar test to see whether any modification of each polynomial satisfies $|p(7)| \le 2^7$; only $67$ polynomials/$6$-tuples survive. We do a similar test to see whether any modification of each remaining polynomial satisfies $|p(8)| \le 2^8$; only $49$ polynomials/$6$-tuples survive—the $49$ candidate polynomials described above. (And trying the same procedure at $x=9$ and $x=10$ didn't narrow the set down any more; and each remaining polynomial in the set happened to have coefficients not just in $\frac12\mathbb Z$ but actually in $\mathbb Z$.)

I used Mathematica to do my calculations, and my code is below if it helps anyone verify the calculations. Once the code was written, the calculations took about 30 seconds on my laptop.

r[t_] := Range[-t, t]

possibleValues = Flatten[Outer[List, r@1, r@2, r@4, r@8, r@16, r@32], 5];

mc[i_, j_, m_][L_] := Mod[L[[i]] - L[[j]], m] == 0

consistentValues = Select[possibleValues,
  mc[1, 3, 2][#] && mc[1, 4, 3][#] && mc[1, 5, 4][#] && mc[1, 6, 5][#]
     && mc[2, 4, 2][#] && mc[2, 5, 3][#] && mc[2, 6, 4][#] && mc[3, 6, 3][#] &];

consistentPolynomials5 = Expand@InterpolatingPolynomial[Transpose[{Range[0,5],#}],x]
  & /@ consistentValues;

centerPolynomialAt[p_,t_] := p - Product[x-j, {j,0,t-1}] Round[p /. x->t, t!/2]/(t!)

possiblePolynomials6 = centerPolynomialAt[#, 6] & /@ consistentPolynomials5;

consistentPolynomials6 = Select[possiblePolynomials6, Abs[(# /. x -> 6)] <= 2^6 &];

possiblePolynomials7 = centerPolynomialAt[#, 7] & /@ consistentPolynomials6;

consistentPolynomials7 = Select[possiblePolynomials7, Abs[(# /. x -> 7)] <= 2^7 &];

possiblePolynomials8 = centerPolynomialAt[#, 8] & /@ consistentPolynomials7;

consistentPolynomials8 = Select[possiblePolynomials8, Abs[(# /. x -> 8)] <= 2^8 &];

consistentPolynomials8positive = Select[consistentPolynomials8,
  Last@CoefficientList[#, x] > 0 &];

SortBy[consistentPolynomials8positive, Reverse@CoefficientList[#, x] &]