0

Suppose $\mathbb F_q$ is the finite field of order $q$ and $\mathbb{F}_q^d$ is $d$-dimensional vector space over finite field $\mathbb{F}_q$. Given $f:\mathbb{F}_q^d\to \mathbb{C}$, define the Fourier transform $\hat{f}:\mathbb{F}_q^d\to \mathbb{C}$ by the formula $$\hat{f}(m)=q^{-d}\sum \limits_{x\in \mathbb{F}_q^d} e^{-\dfrac{2\pi i}{q} x\cdot m}$$ I was trying to prove Fourier inversion formula which states that $$f(x)=\sum \limits_{m\in \mathbb{F}_q^d}e^{\dfrac{2\pi i}{q} x\cdot m}\hat{f}(m)$$

In the RHS of the above equality I plugged in the value of $\hat{f}(m)$ in order to derive that it is actually $f(x)$. However, after some manipulations I ran into the following sum:

$$q^{-d}\sum \limits_{y\in \mathbb F_q^d} \left(\sum \limits_{m\in \mathbb F_q^d} e^{\dfrac{2\pi i}{q}(x-y)\cdot m} \right)f(y)$$ and this sum can be splitten into two sums where the first one corresponds to $y=x$ and the second over $y\neq x$.

The sum which corresponds to $y=x$ is equal to $q^{-d}f(x)|\mathbb F_q^d|=q^{-d}f(x)q^d=f(x).$

How to show that the second sum is equal to zero? I have tried but I failed.

Would be thankful to see the solution, please.

Remark: So we basically need to show that for $z\in \mathbb{F}_q^d, z\neq 0$ we have $$\sum \limits_{m\in \mathbb F_q^d} e^{\dfrac{2\pi i}{q} z\cdot m}=0.$$ Am I right?

EDIT: Here is the original version of the post.

Let $\mathbb{F}_q$ be a finite field of order $q$ and $\mathbb{F}_q^d$ be a $d$-dimensional vector space over $\mathbb{F}_q$, where $d\geq 2$.

Given $f:\mathbb{F}_q^d\to \mathbb{C}$ we define Fourier transform $\widehat{f}:\mathbb{F}_q^d\to \mathbb{C}$ by formula $$\widehat{f}(m)=q^{-d}\sum \limits_{x\in \mathbb{F}_q^d} \chi(-x\cdot m) f(x),$$ where $\chi$ is a non-trivial principal character on $\mathbb{F}_q$.

Lemma: With the notation above, $$f(x)=\sum \limits_{m\in \mathbb{F}_q^d}\chi(x\cdot m) \widehat{f}(m)$$ and $$\sum \limits_{m\in \mathbb{F}_q^d}|\widehat{f}(m)|^2=q^{-d}\sum \limits_{x\in \mathbb{F}_q^d}|f(x)|^2.$$ These identities are called Fourier inversion and Plancherel.

RFZ
  • 16,814
  • Something is wrong. A) The function $f$ does not appear in your definition of $\hat f$ at all. B) What is $m$ and $x\cdot m$? C) If $x\cdot m$ is an element of the field $\Bbb{F}_q$, then $e^{(2\pi i/q) z}$ makes no sense (except possibly when $q$ is a prime). You need an additive character of $\Bbb{F}_q$. – Jyrki Lahtonen Apr 01 '21 at 03:23
  • 1
    More precisely (elaborating on item C), if $x\in \Bbb{F}_p$, $p$ a prime, we get a well defined function $\chi:\Bbb{F}_p\to\Bbb{C}$ from the recipe $$\chi(\overline{n})=e^{2\pi in/p}.$$ Observe that $\overline{n}=\overline{m}$ if and only if $n\equiv m\pmod p$. The latter congruence implies that $e^{2\pi in/p}=e^{2\pi im/p}$, hence $\chi$ is well defined. But, when $q$ is a prime power, this makes no sense whatsoever. The elements of $\Bbb{F}_q$ are not residue classes of integers modulo $q$. – Jyrki Lahtonen Apr 01 '21 at 03:37
  • Elaborating on item A: Assume $q=p$, so the previous comment can be worked around. The basic character orthogonality results give immediately that, taking your definition literally: $$\hat{f}(0)=1$$ and $\hat{f}(m)=0$ otherwise. Irrespective of $f$. – Jyrki Lahtonen Apr 01 '21 at 03:42
  • @JyrkiLahtonen, please take a look at my edit. So my question is: 1) What does mean non-trivial principal character on $\mathbb{F}_q$? 2) How to find the explicit form of this character? Can you help me with those questions, please? – RFZ Apr 01 '21 at 14:57
  • @JyrkiLahtonen, $m$ is an element of $\mathbb{F}_q^d$ and $x\cdot m$ is just the dot product of $x\mathbb{F}_q^d$ and $m$ which means that $x\cdot m \in \mathbb{F}_q$ – RFZ Apr 01 '21 at 15:00
  • @JyrkiLahtonen, I'd be thankful if you can help me with my questions, please. – RFZ Apr 01 '21 at 15:20
  • Ok, the updated version makes sense. A common choice for $\chi$ is to precompose $\overline{n}\mapsto e^{2\pi in/p}$ with the trace function. Here the trace is the function (assuming $q=p^n$, $p$ a prime number) $$tr:\Bbb{F}q\to\Bbb{F}_p, x\mapsto x+x^p+x^{p^2}+\cdots+x^{p^{n-1}}=\sum{j=0}^{n-1}x^{p^j}.$$ The trace is surjective and linear over the prime field. Consequently the function $$\chi:\Bbb{F}_q\to\Bbb{C}, x\mapsto e^{2\pi i tr(x)/p}$$ is an additivive character and takes all the complex $p$the roots of unity as its values. – Jyrki Lahtonen Apr 02 '21 at 20:02
  • It being an additive character means that for all $x,y\in\Bbb{F}_q$ we have $$\chi(x+y)=\chi(x)\chi(y).$$ All the additive characters are gotten from this by the following recipe: fix $a\in\Bbb{F}_q$, and define the function $$\chi_a:\Bbb{F}_q\to\Bbb{C}^*, x\mapsto \chi(ax).$$ The characters form the dual group $\widehat{\Bbb{F}_q}$ with pointwise multiplication of values as the operation. The Fourier inversion formula then immediately follows from the standard dualities: – Jyrki Lahtonen Apr 02 '21 at 20:06
  • $$S(a):=\sum_{x\in\Bbb{F}q}\chi_a(x)=q\delta{a,0},$$ so $S(0)=q$ and $S(a)=0$ whenever $a\neq0$. Similarly $$\Sigma(x):=\sum_{a\in\Bbb{F}q}\chi_a(x)=q\delta{x,0}.$$ – Jyrki Lahtonen Apr 02 '21 at 20:08

0 Answers0