Today I Learned

April 28th

Today I learned that the Fourier transform for finite fields behaves as it does in local fields, from here . Two or so weeks ago we classified characters over finite fields $\FF_q$ as being generated by a nontrivial character $\psi_0:\FF_q\to\CC^\times,$ from which all characters take the form $x\mapsto\psi_0(ax)$ for some $a\in\FF_q.$

Because $\widehat{\FF_q}\cong\FF_q$ as Pontryagin duals, our theory of Fourier transforms is reasonably well-behaved. We don't have to think too hard about the necessary Haar measure because $\FF_q$ is a discrete topological space, so it adopts the counting measure. The "correct'' scale factor is as follows.

Observe that we don't have to worry about convergence issues because all sums are finite, which is much nicer than usual.

While the $1/\sqrt q$ might appear annoying, it's the correct thing to do under the isomoprhism $\FF_q\cong\widehat{\FF_q}.$ While we're in the Fourier world, this scale factor is what makes things behave. Indeed, we have the following.

Technically we only have to check this for a single nonzero $f$ to make sure we got the $1/\sqrt q$ scale factor, but we will go through the entire thing. Anyways, this is a matter of pushing everything through. Observe that\[\hat{\hat f}(x)=\frac1{\sqrt q}\sum_{y\in\FF_q}\hat f(y)\psi_0(-xy)=\frac1q\sum_{y,z\in\FF_q}f(z)\psi_0(-xy)\psi_0(-zy).\]Rearranging the sum, we have\[\hat{\hat f}(x)=\frac1q\sum_{z\in\FF_q}f(z)\left(\sum_{y\in\FF_q}\psi_0(-(z+x)y)\right)\]because $\psi_0$ is an additive character. Now, $y\mapsto\psi_0(-(z+x)y)$ is just another character, which we will call $\psi.$ We have two cases.

• If $z=-x,$ then $\psi(y)=1$ always, in which case, the inner sum $\sum_y\psi(y)$ is a full $q.$

• If $z\ne-x,$ then $\psi$ is a nontrivial character with, say, $\psi(a)\ne1.$ (Such $a$ exists because $\psi_0$ is a nontrivial character with, say, $\psi_0(a_0)\ne1,$ so we can use $a:=-a_0(z+x)^{-1}.$) However, $a\ne0,$ so addition by $a$ bijects $\FF_q,$ implying \[\psi(a)\sum_{y\in\FF_q}\psi(y)=\sum_{y\in\FF_q}\psi(a+y)=\sum_{y\in\FF_q}\psi(y).\] This rearranges to $(\psi(a)-1)\sum_y\psi(y)=0,$ so $\sum_y\psi(y)=0.$

Looking at the casework, we only care about the $z=-x$ case, in which case we have\[\hat{\hat f}(x)=\frac1q\cdot f(-x)\cdot q=f(-x),\]which is what we wanted. $\blacksquare$

While we're here, we pick up Parseval's identity, just to showcase how nice finite sums are.

There is some linear algebra going on in the background, as there usually is with Parseval's identity. Previously we proved that\[f(x)=\hat{\hat f}(-x)=\frac1{\sqrt q}\sum_{y\in\FF_q}\hat f(y)\psi(xy),\]which is our inverse Fourier transform; one can read this as saying the characters $x\mapsto\psi(ax)$ are a spanning set of vectors for the function $\FF_q\to\CC.$ If we use $\hat f(y)$ as coefficients, we can equip this space with an inner product and stuff, but we won't do so explicitly.

More directly, for $f,g:\FF_q\to\CC,$\[\sum_{x\in\FF_q}f(x)\overline{g(x)}=\sum_{x\in\FF_q}\left(\frac1{\sqrt q}\sum_{y\in\FF_q}\hat f(y)\psi(xy)\right)\left(\frac1{\sqrt q}\sum_{z\in\FF_q}\overline{\hat g(z)}\overline{\psi(xz)}\right).\]This sum rearranges into\[\sum_{x\in\FF_q}f(x)\overline{g(x)}=\sum_{y,z\in\FF_q}\hat f(y)\overline{\hat g(z)}\left(\frac1q\sum_{x\in\FF_q}\psi(x(y-z))\right).\]Now, when $y\ne z,$ this inner sum vanishes, which we showed in the casework of the previous proposition because it is a sum over a nontrivial character. When $y=z,$ the inner sum is $\frac1q\cdot q=1,$ and we get\[\sum_{x\in\FF_q}f(x)\overline{g(x)}=\sum_{y\in\FF_q}\hat f(y)\overline{\hat g(y)}.\]Plugging in $g=f$ gives the desired. $\blacksquare$

Just to say that I did, we wrote down\[\sum_{x\in\FF_q}f(x)\overline{g(x)},\]which is in fact the inner product described. Observe that orthogonality of characters is with respect to this inner product: if we fix $a,b\in\FF_1$ and consider the characters $x\mapsto\psi_0(ax)$ and $x\mapsto\psi_0(bx),$ then\[\sum_{x\in\FF_q}\psi_0(ax)\overline{\psi_0(bx)}=\sum_{x\in\FF_q}\psi((a-b)x)=q\cdot1_{a=b}.\]All of this is the usual theory with Fourier transforms or even representation of finite groups, but it's especially nice with our finite sums and well-behaved character groups.