3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ If $f$ has no particular form, then $\hat{f}$ has no particular form... $\endgroup$ Apr 23 at 12:01
  • 2
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Apr 23 at 12:49
  • 2
    $\begingroup$ For the second question, the Cauchy-Schwarz-Plancherel bound will be close to optimal for a random set. $\endgroup$
    – Will Sawin
    Apr 23 at 14:19
  • $\begingroup$ @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. $\endgroup$ Apr 25 at 3:54
  • $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Apr 25 at 10:05

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ So, in general, a good bound is $ ||f||^2 ||g||^2 O(\sqrt{q}) $ ? $\endgroup$
    – User
    Apr 23 at 18:29
  • $\begingroup$ A further standard device is to average a bound over all functions, to have at least a heuristic for "random" functions. $\endgroup$ Apr 23 at 19:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Apr 23 at 19:10
  • $\begingroup$ @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)} ) $ ? $\endgroup$
    – User
    Apr 23 at 20:18
  • 1
    $\begingroup$ @User With that normalization it should be $||f||^2 ||g||^2 O(\sqrt{q})$ again because the two changes cancel out. $\endgroup$
    – Will Sawin
    Apr 24 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.