Given a polynomial \(f: \mathbb{Z}\to \mathbb{Z}\) with positive integer coefficients, how many evaluations of \(f\) does it take to obtain the polynomial?

(An \(f: \mathbb{R}\to \mathbb{R}\) polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would render the answer unbounded. But the correct answer in this case is surprisingly small.)

It takes only 2 evaluations. Suppose in the following that \(b>0\). Let us note that a polynomial \(f(b) = a_n b^n + … + a_0 b^0\) specifies essentially a base \(b\) representation of the number \(f(b)\), in that \(a_n a_{n-1} … a_0\) is an expansion of \(f(b)\) in base \(b\). The only problem is this expansion is non-unique, as it is possible for any \(a_j \ge b\).

However, it is not possible for any \(a_j \ge f(b) + 1\), since for all \(j\), \(f(b) \ge a_j\) by the problem statement and assumption on \(b\). Then take \(B = f(b) + 1\). Now we are guaranteed that \(a_n a_{n-1} … a_0\) is the unique (and canonical) base \(B\) expansion of \(f(B)\), from which the polynomial coefficients immediately obtain.

So the two evaluations are at \(f(b)\) and \(f(B=f(b)+1)\).

Example: \(f(b) = 3b^2 + 2b + 1\). Evaluate at, e.g., \(b=1\) to get \(f(1) = 6\). Then evaluate at \(B=f(1)+1=7\) to get \(f(7)=162=321_{7}\).

If an integer \(n\) is reduced by the largest square less than it each time until it is terminated at zero, show that the number of steps taken is at most order \(\log \log n\).

More precisely, let \(f(n) = n – {\left\lfloor{\sqrt{n}}\right\rfloor}^2\) and \(g(n)=k\) be the minimum number of steps until \(f^k(n)=0\). Prove that there exists some fixed \(A\) such that \(g(n)< A \log \log n\) for all \(n\ge 3\).

Why is the convergence speed double log? Well, it really has to do with the fact that the remainder \(f(n)\) is of order square root of \(n\), and that ultimately has to do with the fact that the gaps between successive integer squares grow linearly. Each time \(f\) is applied to some \(n\), the remainder after the removal of the largest square is no more than the gap value between that square and the next square.

The proof goes something like this. \(m^2 – (m-1)^2 = 2m – 1 < 2m\), so \(f(n) \le (\left\lfloor{\sqrt{n}}\right\rfloor + 1)^2 - {\left\lfloor{\sqrt{n}}\right\rfloor}^2 < 2({\left\lfloor{\sqrt{n}}\right\rfloor + 1}) \le 2\sqrt{n} + 2 \le 4\sqrt{n}\), where the last step is valid for \(n \ge 1\). After applying \(f\) some \(k\) times iteratively, we get \(f^k(n) < \underbrace{4\sqrt{\cdots 4\sqrt{4\sqrt{n}}}}_k = 16^{\frac{1}{2} + \frac{1}{4} + \cdots + 2^{-k}} n^{2^{-k}} < 16 n^{2^{-k}}\).

Now, if for some \(k\), \(16 n^{2^{-k}} < 17\), then certainly there must be some \(K \le k\) such that the integer \(f^K(n) \le 16\), in which case the total number of steps to terminate is no more than \(k+4\). (For the 4, see graph below for termination cases for \(n\le 16\).)

Next we solve \(16 n^{2^{-k}} < 17 \) (*) for \(k\) by taking log twice, and using the monotonicity of log:

Clearly, if \(k > \frac{\log \log n}{\log 2}\), then (*) is satisfied, so the total number of steps required to terminate is given by \(g(n) \le \frac{\log \log n}{\log 2} + 4 < 44 \log \log n\) for \(n\ge 3\), QED.

]]> https://blog.yhuang.org/?feed=rss2&p=156 0