Background. Fast Fourier Transform (FFT) is an algorithm used to quickly calculate the discrete Fourier transform (DFT) of a sequence. It is widely used in signal processing, image analysis, and data compression.
I am trying to implement FFT on the λ-calculus for a code-golf challenge, with as little code as possible. Complex numbers are complex (pun intended), since they require real numbers, which aren't simple to construct.
A possible solution is to perform FFT on a simple base field like GF(3), with $ \{-1, 0, 1\} $, which can be implemented with little code. The problem is that such field doesn't have all the roots of unity. For example, we can perform FFT over two "scalar" GF(3) elements, since we have two roots of unity ($ -1 $ and $ 1 $), and over four "complex" GF(3) elements, since we have four roots of unity ($ -1, 1, -i, i $). But for lists of length four or more, this isn't possible, since we can't express arbitrary expressions in the form of $ a \cos(x) + b \sin(x)i $ on GF(3).
Now, what if we kept adding dimensions? By using quaternions, we could perform FFT over eight GF(3) elements, as there are eight roots of unity ($ -1, 1, -i, i, -j, j, -k, k $), and this generalizes to any hypercomplex number. However, from octonions and beyond, multiplication isn't associative, which is a property that is required for FFT.
Question. Can FFT be implemented using Clifford Algebra over GF(3) to overcome the problem of not having enough roots of unity?