# Sum of products of Fourier coefficients in finite field

Let $$\mathbb{F_q}$$ be some finite field and let $$f,g: \mathbb{F_q} \to \mathbb{C}$$. By $$\hat{f}, \hat{g}$$ let's denote the Fourier coefficients of $$f,g$$ with respect to the additive characters of the field.

How good an upper bound can we exhibit for the following sum (if it's possible to find a non-trivial bound)

$$\left| \ \sum_{\{a,b,c,d \in \mathbb{F_q} : a^2+ab=c^2+cd \}} \hat{f}(a)\cdot \overline{\hat{f}(c)}\cdot \hat{g}(b)\cdot \overline{\hat{g}(d)}\ \right| ?$$

I care about the particular case that $$f,g$$ are indicator functions, but I don't see how this should play a role here.

What about optimal (general) bounds for the sum $$\sum_{a\in \mathbb{F}^{*}_q} \left| \hat{f}(a) \right|$$?

I could trivially bound the latter sum in this case by $$|S|$$, but I was wondering if there is something better. We could also use Cauchy-Schwarz and then Plancherel's equality, but I was also wondering if there is a better bound for indicator functions.

• If $f$ has no particular form, then $\hat{f}$ has no particular form... Apr 23 at 12:01
• @mathworker21 For some problems of this type, knowing that $\hat{f}$ has no particular form, i.e. that $\hat{f}$ does not correlate strongly with any function on some explicit list, is sufficient to give a nontrivial bound. Apr 23 at 12:49
• For the second question, the Cauchy-Schwarz-Plancherel bound will be close to optimal for a random set. Apr 23 at 14:19
• @WillSawin I did not mean "$\hat{f}$ does not correlate strongly with any function on some explicit list" when I said "$\hat{f}$ has no particular form". I meant that $\hat{f}$ can be literally anything if $f$ can be anything. So there's no point to having fourier transforms in the problem. Apr 25 at 3:54
• @mathworker21 True, one may as well use $f$ and $g$ and then refer to the special case that $\hat{f}$ and $\hat{g}$ are Fourier transforms of indicator functions. Apr 25 at 10:05

I would do this:

First detect the equation with additive characters, then reverse the Fourier transforms on the $$g$$'s, then break into subsums $$\sum_{\{a,b,c,d \in \mathbb{F_q} : a^2+ab=c^2+cd \}} \hat{f}(a)\cdot \overline{\hat{f}(c)}\cdot \hat{g}(b)\cdot \overline{\hat{g}(d)}$$ $$= \frac{1}{q} \sum_{\{a,b,c,d , \lambda \in \mathbb{F}_q \}} \psi( \lambda( a^2+ab-c^2-cd)) \hat{f}(a)\cdot \overline{\hat{f}(c)}\cdot \hat{g}(b)\cdot \overline{\hat{g}(d)}$$

$$= \sum_{a,c,\lambda \in \mathbb{F}_q } \psi ( \lambda (a^2-c^2))\hat{f}(a)\cdot \overline{\hat{f}(c)}\cdot g(\lambda a)\cdot \overline{g(\lambda c)}$$

Now for any $$u \in \mathbb F_q$$ not equal to $$0,1,$$ or $$-1$$, the sum over the subset where $$c = a u$$ and $$a\neq 0$$ is possible to control: It is $$\sum_{a,\lambda \in \mathbb{F}_q , a\neq 0 } \psi ( \lambda a^2 (1-u^2) )\hat{f}(a)\cdot \overline{\hat{f}(a u)}\cdot g(\lambda a)\cdot \overline{g(\lambda a u )}$$ $$\sum_{a,b\in \mathbb{F}_q , a\neq 0 } \psi ( a b (1-u^2) )\hat{f}(a)\cdot \overline{\hat{f}(a u)}\cdot g(b)\cdot \overline{g(b u )}$$ which by Plancherel and Cauchy-Schwarz is bounded by

$$\sqrt{q \sum_{a \in \mathbb F_q,a\neq 0 } \left | \hat{f}(a)\cdot \overline{\hat{f}(a u)} \right|^2 \sum_{b \in \mathbb F_q} \left | g(b)\cdot \overline{g(b u )} \right|^2}$$ so the sum over all such $$u$$ is bounded by

$$\sqrt{q} \sum_{u \in \mathbb F_q, u\neq 1,0,-1} \sqrt{ \sum_{a \in \mathbb F_q,a\neq 0 } \left | \hat{f}(a)\cdot \overline{\hat{f}(a u)} \right|^2 \sum_{b \in \mathbb F_q} \left | g(b)\cdot \overline{g(b u )} \right|^2}$$

$$\leq \sqrt{q}\sqrt{\left(\sum_{u \in \mathbb F_q, u\neq 1,0,-1} \sum_{a \in \mathbb F_q,a\neq 0 } \left | \hat{f}(a)\cdot \overline{\hat{f}(a u)} \right|^2 \right) \left( \sum_{u \in \mathbb F_q, u\neq 1,0,-1} \sum_{b \in \mathbb F_q} g(b)\cdot \overline{g(b u )}\right)}$$

$$\leq \sqrt{q} ||f||_2^2 ||g||_2^2$$

The remaining terms are those where $$c=a, c=-a, c=0, a=0$$, or all $$4$$ of these conditions are satisfied. These terms will be lower-order for generic $$f,g$$ but can lead to the main term for special $$f,g$$, and in any case their size can be estimated in the same elementary way.

• So, in general, a good bound is $||f||^2 ||g||^2 O(\sqrt{q})$ ?
– User
Apr 23 at 18:29
• A further standard device is to average a bound over all functions, to have at least a heuristic for "random" functions. Apr 23 at 19:06
• @User I think it's pretty good. Note that there are choices for how to normalize the Fourier transform and the $L^2$ norm that drastically affect the shapes of bounds. I am normalizing the Fourier transform to be unitary and the $L^2$ norm so that the constant function $1$ has $L^2$ norm $\sqrt{q}$. The second one may be less standard. I would consider $||f||^2 ||g||^2O (q)$ to be trivial in this context so the bound I sketch would be nontrivial. Apr 23 at 19:10
• @WillSawin Oh, I just noticed the comment about normalization. So, the bound is very different if $\langle f, g \rangle : = 1/|q| \sum_{x\in \mathbb{F_q}} (f(x) \overline{g(x)})$ and so, in particular, $\hat{f}(a)=\langle f, \psi_a \rangle = 1/|q| \sum_{x\in \mathbb{F_q}} (f(x) \overline{\psi_a(x)} )$ ?
– User
Apr 23 at 20:18
• @User With that normalization it should be $||f||^2 ||g||^2 O(\sqrt{q})$ again because the two changes cancel out. Apr 24 at 1:37