I'll be in Canada for the next two weeks and "structure-preserving maps, Part II" is still a work in progress, so until then have a snippet that I will return to later:

---

Recall my musings on Newton polynomials. I neglected to realize that there is in fact an extremely efficient computational process that lets you write a polynomial of degree in Newton form given only of its values.

The key is Lemma 2 from the above post, which is exactly analogous to the operation that takes the Taylor series of a function



to its derivative. Essentially, we remove the first coefficient and shift all of the other ones to the left; in other words,

.

The property shared here is that just as . Now, recall that we find a Taylor series by repeatedly differentiating and plugging in zero. In other words,

.

The same process can be applied here. In other words, given that we find that . So all we have to do is take repeated finite differences (exactly analogous to taking repeated derivatives) and look at the first row of a table!

Let's redo the example from the above post. Our first four values were . In tabular format,

$ \begin{tabular}{ | l | c | c | c | c | r | } x & P(x) & \Delta & \Delta^2 & \Delta^3 & \Delta^4 \\ \hline 0 & 0 & 1 & 14 & 36 & 24 \\ 1 & 1 & 15 & 50 & 60 \\ 2 & 16 & 65 & 110 & \\ 3 & 81 & 175 & & \\ 4 & 256 & & & \\ \hline \end{tabular}$.

The coefficients in the top row are exactly the Newton polynomial coefficients we found earlier. Splendid! Note that this gives an extremely efficient method to interpolate a Newton polynomial through any values . Finding a polynomial through those values in terms of the standard basis just requires expanding out each Newton polynomial.

Among the many benefits of the above technique, note how it trivializes Problem 2 from the original post. See Newton's forward difference formula.

---

Practice Problem 1 (Generalization of Problem 2): A polynomial of degree satisfies . Find . (Note that it is not necessary that be an integer or even real.)

Practice Problem 2: Use the results of Practice Problem 1 to solve the practice problem in the original post. (Hint: how do you decompose a periodic function into a sum of functions of the form ? When the period is , what values can take?) Compare with the solutions presented in the original thread.