Let N be a positive power of 2, N=2n. Then given any number a between 0 and N-1, it can be written as
with the coefficients ak equals to either 0 or 1 (they are the bits of the binary representation of a). Consider the product
where the numbers Ak are less than one, and
ie their binary representation is 0.ak...a0.
Prove that the above product is equal to N if a=0, and is zero otherwise.
Consider the sum Sumb=0..N-1 exp( 2 pi i a b / N ). This result is used in the quantum Fourier transform.
Marco Corvi - 2004