# Context for this discrete Cauchy integral formula

Notation: I will use the following conventions for discrete Fourier transforms (DFT) and discrete time Fourier transforms (DTFT): $$\mathcal{D}_N[x_j](k) := \sum_{j=0}^{N-1} e^{-2\pi i j k} x_j$$ $$\mathcal{D}^{-1}_N[y_k](j) := \frac{1}{N}\sum_{k=0}^{N-1} e^{2\pi i j k} y_k$$ $$\mathcal{F}[x_j](k) := \sum_{j=-\infty}^\infty e^{-2\pi i j k} x_j$$ $$\mathcal{F}^{-1}[y(k)](j) := \int_0^1 e^{2\pi i j k} y(k)$$ Additionally, $$\Omega_N$$ will denote the set of $$N^{th}$$ roots of unity.

Let $$f$$ be a polynomial of degree $$N$$ with coefficients $$c_j$$, $$j=0,1,\dots,N$$. Consider the list of all coefficients as a vector $$c$$. By taking a DFT of $$c$$ you can show that $$c_j = \mathcal{D}_N^{-1}\left[f\left(e^{-2\pi i k/N}\right)\right](j)\tag{1}$$ And analogously with a DTFT $$c_j = \mathcal{F}^{-1}\left[f\left(e^{-2\pi i k}\right)\right](j)\tag{2}$$

Actually the latter formula works perfectly well for analytic functions $$f$$, where $$c$$ is the the vector of Taylor coefficients, or with meromorphic functions and $$c$$ the Laurant coefficients.

I realized recently that this is basically just Cauchy's integral formula with a change of variables. To see this, expand out the inverse DTFT: \begin{align*} c_j & = \int_0^1 e^{2\pi i k j} f(e^{-2\pi i k}) dk \\ & = \oint_{S^1} z^{-j} f(z) \frac{dz}{2\pi i z} \\ & = \frac{1}{j!} \frac{d^j f(0)}{dz^j} \end{align*} Where the last line is from Cauchy's formula.

So far this is all familiar. However, from this perspective we see that eq. (1) can also be interpreted as a "discrete" version of Cauchy's integral formula, valid only for polynomials. Rewriting it slightly, we have \begin{align*} \frac{1}{j!}\frac{d^j f(0)}{dz^j} = c_j & = \frac{1}{N} \sum_k e^{2\pi i j k} f(e^{-2\pi i k/N})\\ & = \frac{1}{N} \sum_{z\in \Omega_N} z^{-j} f(z) \tag{3}\\ \end{align*}

This circle of ideas seems like it would be useful for e.g. efficiently determining coefficients of a "black box" polynomial that you can only evaluate. Or more generally any situation where you would want to use Cauchy's formula with a polynomial, this might be a convenient alternative. However, I've never seen any of this before in textbooks or other literature.

Question: What, if anything, are eqs. (1) and (3) useful for? Citations to literature welcome.

As I wrote this, I remembered vaguely something about "z-transforms". After looking this up, it seems very closely related, though not quite identical. I still haven't found anything exactly like eqs. (1) or (3).

• isn't this a well-known connection? see Taylor and Fourier series are the same Feb 26, 2021 at 16:40
• I might be wrong, but my understanding was that one of the basic applications of the Fast Fourier transform (which is just an algorithm to do DFT fast on a computer) is precisely to make use of (1) in settings where evaluation of a polynomial function is easy, but you want to compute things related to the coefficients. The standard example is probably integer arithmetic on computers -- look up the basic fast integer multiplication algorithms a la Schönhage-Strassen. Feb 26, 2021 at 17:20
• this MO posting addresses a similar correspondence: mathoverflow.net/a/350028/11260 Feb 26, 2021 at 18:35