2
$\begingroup$

I've been playing with Fourier transform a little and discovered the identity quoted in the title. More precisely, writing the matrix for the Fourier transform in ${\mathbb Z} / N {\mathbb Z}$ as

$A = {1 \over \sqrt{N}} \pmatrix{ \zeta^0& \zeta^0 & \cdots & \zeta^0 \cr \zeta^0& \zeta^1 & \cdots & \zeta^{N-1} \cr \vdots & \vdots &\ddots &\vdots \cr \zeta^0& \zeta^{N-1} & \cdots & \zeta^1 \cr }$

(with $\zeta \equiv \exp({2 \pi i \over N})$) one easily obtains the quoted identity by using the famous determinant of Vandermonde matrix and the fact that the transform is unitary.

Now, I'd be interested whether the identity can be proven directly, and ideally given a nice combinatorial interpretation. I suppose this should be possible because of lot of structure in the problem but I wasn't able to come up with anything yet.

  • 0
    @Qiaochu: thank you, this is the closest to an answer yet. I am not sure I follow though; could you be a little bit more explicit about that connection (even if it doesn't work or is just sketchy). It would be nice if you posted a CW answer so that we could see what it leads to.2011-01-19

3 Answers 3

3

It can be derived directly by considering the n-roots of one $z_k = exp(\frac{i 2\pi k}{N})$

$F(z) = z^N-1 = (z-z_0) ... (z-z_{N-1})$

First, this readily implies (by setting $z=0$) that

$ \prod z_i = (-1)^{N+1}$

Second, by deriving $F(z)$ and evaluating at, say, $z=z_0$ we get

$ N z_0^{N-1} = (z_0 - z_1) (z_0 - z_2) ... (z_0 - z_{N-1}) $

Rearranging, writing the same equation for all $z_i$, multiplying all them, and using the previous equation, we get at your result.

$ N^N (\prod z_i)^{N-1} = \prod_{i \ne j} (z_i - z_j) $

$ N^N (-1)^{N+1} = \prod_{i \ne j} (z_i - z_j) $

$N^{N/2} = | \prod_{i

No combinatorial interpretation, though.

  • 0
    apologies not necessary, you didn't sound critical. thanks for the corrections2011-01-19
2

This is not an answer. I worked out some of the details relevant to my comment above here and here. A rough summary is as follows:

  • The discriminant of $t^n + pt + q$ turns out to equal $(-1)^{ {n \choose 2} } ((1 - n)^{n-1} p^n + n^n q^{n-1} )$. This is a generalization of the fact you want to prove ($p = 0, q = -1$).
  • There is a unique power series $t$ in the variable $q$ which satisfies $t = q + t^n$ ($p = -1$) and $t(0) = 0$. It turns out to be precisely $t = \sum \frac{1}{(n-1)k + 1} {nk \choose k} q^{(n-1)k + 1}$ for combinatorial reasons; $t$ counts what I call "$n$-ary trees" in the blog post above (but you should read the definition carefully).
  • Therefore $\frac{dt}{dq} = \sum {nk \choose k} q^{(n-1)k}$. It turns out that the relation $t = q + t^n$ implies a corresponding algebraic relation for $\frac{dt}{dq}$, and the leading term of this algebraic relation is, up to sign, the discriminant of $t^n - t + q$.

Unfortunately I do not know a conceptual reason why the third bullet point is true. You can see it directly in the case $n = 2$, where the discriminant of $t^2 - t + q$ is $1 - 4q$ and

$\frac{dt}{dq} = \sum {2k \choose k} q^k = \frac{1}{\sqrt{1 - 4q}}.$

Here $t$ is the generating function for the Catalan numbers. You can also work out what happens when $n = 3$ by the cubic formula, but after that things become troublesome.

  • 0
    Nice, thank you very much! I'll try to play with these ideas a little and see whether I'll think of something.2011-01-20
1

If you look at Combinatorial Proof of Vandermonde's determinant perhaps you can extract the desired combinatorial proof.

  • 0
    After a quick peek, I don't think this helps. The proof in the article assumes that $zeta^i$ ($x_i$ in their setting) are integers which is a completely different problem from my case of $N$th roots of unity.2011-01-19