Combinatorial proof of $\Big|\prod\limits_{0 \leq i < j < N} (\zeta^j -\zeta^i)\Big| = \sqrt {N^N}$ for $\zeta \equiv \exp({2\pi i \over N})$ 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.
 A: 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<j} (z_i - z_j)|$
No combinatorial interpretation, though.
A: 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.
A: If you look at Combinatorial Proof of Vandermonde's determinant perhaps you can extract the desired combinatorial proof.
