Analysis of functions over Galois fields

Question

I'm trying to understand how harmonic analysis generalises to functions over finite (Galois) fields.

In particular I'm trying to understand - how to meaningfully map the function to somehow "work on roots of unity" (I'm new in this field, so it could be that I'm not asking the right question, and if so, please explain what is the question I should be asking).

In the context of analysis of Boolean functions, we start with some function: $f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$, but instead of considering that function, we consider a related function: $f':\{0,1\}^n\rightarrow \{-1,1\}$ such that $f'(x)=(-1)^{f(x)}$. Now we can talk about the Fourier transform of $f'$ which is: $$ \hat{f'}(\alpha) = 2^{-n}\sum_{x} f'(x)(-1)^{\sum_{i=1}^n x_i\alpha_i} $$

Similarly, one can easily generalise this to prime finite fields. Let $p$ be a prime and $\omega_p=e^{\frac{2\pi i}{p}}$. We can generalise the above to functions $g:\mathbb{F}_p^n\rightarrow\mathbb{F}_p$ (I use $\mathbb{F}_p$ and $\mathbb{Z}_p$ interchangeably). Let $g':\mathbb{F}_p^n\rightarrow\{\omega_p^j\}_{j=0}^{p-1}$ such that $g'(x)=\omega_p^{g(x)}$, and $$ \hat{g'}(\alpha) = p^{-n}\sum_{x} g'(x)\omega_p^{\sum_{i=1}^n x_i\alpha_i} $$

Now, let $q = p^s$ for some $s\in \mathbb{N}$ and a function $h:\mathbb{F}_q^n\rightarrow \mathbb{F}_q$ over the Galois field $\mathbb{F}_q$. What we did previously was to consider a related function whose output that maps to the roots of unity. However, in this setting, the $p$'th root of unity, $\omega_p$ cannot be used like it was used before - in $\mathbb{Z}_p$, every element was mapped to a single root of unity by the mapping $x\rightarrow \omega_p^x$. But now, there are $p^s$ elements in $\mathbb{F}_q$ and only $p$ roots of unity modulo $p$. Of course we cannot use $\omega_{q}$ with the same mapping as before, as $\mathbb{F}_q$ is not isomorphic to $\mathbb{Z}_q$.

So my question is how does one define Fourier analysis of functions defined over finite fields.

Thanks!

Answer 1

For any finite abelian group $A$, there is a discrete Fourier transform that takes in complex-valued functions $f: A \to \mathbb{C}$. The transformed function is a complex-valued function on the dual group $A^\vee = \operatorname{Hom}(A,\mathbb{C}^\times)$, and is given by the formula:

$$\hat{f}(\chi) = \sum_{a \in A} f(a)\overline{\chi}(a).$$

Note: Some sources use $\chi$ instead of the complex conjugate $\overline{\chi}$.

The case you seem to consider is given by setting $A = \mathbb{F}_q^n$.

Unless you have a specific application in mind, I do not recommend starting with a function to $\mathbb{F}_q$ and choosing a lift to $\mathbb{C}$. It seems to require some rather arbitrary choices, and the results are unlikely to be informative.