1
$\begingroup$

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).

$\endgroup$
3
  • 2
    $\begingroup$ isn't this a well-known connection? see Taylor and Fourier series are the same $\endgroup$ Commented Feb 26, 2021 at 16:40
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 26, 2021 at 17:20
  • 1
    $\begingroup$ this MO posting addresses a similar correspondence: mathoverflow.net/a/350028/11260 $\endgroup$ Commented Feb 26, 2021 at 18:35

0

You must log in to answer this question.

Browse other questions tagged .