3
$\begingroup$

This is perhaps a simple fact but I am struggling to prove it.

If A, B are distributed over some finite field $\mathbb{F}$, such that $aA + bB$ is $\epsilon$-close to uniform in $\mathbb{F}$ for every $a, b \in \mathbb{F}$ such that they are not both $0$. Then the random variable $(A,B)$ has joint distribution $\epsilon |\mathbb{F}|^2$-close to uniform in $\mathbb{F} \times \mathbb{F}$.

PS: By $\epsilon$-close to uniform distribution, I mean the statistical distance from the uniform distribution is at most $\epsilon$.

$\endgroup$
4
  • 2
    $\begingroup$ Which statistical distance measure do you want? $\endgroup$
    – Noah Stein
    Mar 18, 2013 at 11:25
  • $\begingroup$ By statistical distance I mean the following: Two random variables $A,B$ distributed on ${\mathcal A}$ have statistical distance $\epsilon$ if $$\sum_{a \in {\mathcal A}} |P(A = a) - P(B = a)| = \epsilon$$ $\endgroup$
    – Div
    Mar 18, 2013 at 17:29
  • $\begingroup$ I will be happy if we can somehow manage to prove that if $aA + bB$ is uniform in $\mathbb{F}$, for every $a, b \in \mathbb{F}$ such that not both are $0$, then (A, B) is uniform in $\mathbb{F} \times \mathbb{F}$. I have a proof for the case when $|\mathbb{F}|$ is a prime, but I want to prove for general finite fields. $\endgroup$
    – Div
    Mar 18, 2013 at 17:39
  • $\begingroup$ Do you have any examples in the way of lower bounds? $\endgroup$ Mar 21, 2013 at 21:35

1 Answer 1

5
$\begingroup$

I think the below is correct; it hasn't been very thoroughly checked. One moral seems to be that this question is nicer in the $L^2$ distance than the $L^1$ distance (because the proof uses Fourier analysis); but I think I can deduce something like your $L^1$ result at the end.

Write $k$ for the cardinality of $\mathbb{F}$. Let $F : \mathbb{F}^2 \rightarrow \mathbb{R}$ be the law of $(A, B)$, minus the uniform distribution; i.e. $F(x, y) = \mathbb{P}(A = x, B = y) - 1/k^2$.

For $a, b \in \mathbb{F}$ define $f_{a b}(r) = \sum_{x, y \in \mathbb{F}} F(x, y) 1\lbrace{a x + b y = r\rbrace}$. Alternatively, this is equivalent to $f_{a b}(r) = \mathbb{P}(a A + b B = r) - 1/k$.

So, as I understand it your hypothesis is that $\|f_{a b}\|_1 \le \varepsilon$ for all $(a, b) \ne (0, 0)$, and you want to conclude a bound on $\|F\|_1$, where I use the counting measure on $\mathbb{F}$ and $\mathbb{F}^2$ to define the $L^1$ norm.

My approach is to apply Fourier analysis to $F$ and $f_{a b}$; so it will be convenient to immediately replace the $L^1$ estimate on $f_{a b}$ with the weaker estimate $\|f_{a b}\|_2 \le \varepsilon$ (as $\|\cdot\|_1 \ge \|\cdot\|_2$ wrt the counting measure).

Fix $\chi$ a non-trivial character of $\mathbb{F}$. Then $\chi_r(x) = \chi(r x)$ ranges over all the characters of $\mathbb{F}$ as $r$ ranges over $\mathbb{F}$, and so the Fourier transform of $f_{a b}$ is

$$\widehat{f_{a b}}(r) = \sum_{s \in \mathbb{F}} f_{a b}(s) \chi_r(-s) = \sum_{x, y} F(x, y) \chi_r(-(a x + b y))$$

The characters on $\mathbb{F}^2$ are $\chi_{u, v}(x,y) = \chi(u x + v y)$, so we deduce

$$\widehat{f_{a b}}(r) = \sum_{x, y} F(x, y) \chi_{a r, b r}(-(x, y)) = \widehat{F}(a r, b r) $$

By Parseval's identity, we get that $\frac{1}{k} \sum_r |\widehat{f_{a b}}(r)|^2 \le \varepsilon^2$ for every $(a, b) \ne (0, 0)$. We remark that $\widehat{F}(0, 0) = \sum_{x, y} F(x, y) = 0$. Summing over all possible $a, b$ and double-counting, we get that

$$ \sum_{a, b} \sum_r |\widehat{F}(a r, b r)|^2 = (k - 1) \sum_{u, v} |\widehat{F}(u, v)|^2 \le k^3 \varepsilon^2$$

as each non-zero $(u, v)$ is counted once for each non-zero $r$, and we can ignore the zero terms. By another application of Parseval,

$$ \sum_{x, y} |F(x, y)|^2 = \frac{1}{k^2} \sum_{u, v} |\widehat{F}(u, v)|^2 \le \frac{k \varepsilon^2}{k - 1} $$

So, $\|F\|_2 \le \varepsilon \sqrt{\frac{k}{k-1}}$ : this is the $L^2$ result. Applying Cauchy-Schwarz we get something like

$$ \|F\|_1 \le k \|F\|_2 \le k \varepsilon \sqrt{\frac{k}{k - 1}} $$

which (even after Kevin Costello's correction below) means this result is stronger than you asked for by a factor $\sqrt{k (k - 1)}$, meaning I'm still slightly suspicious of the proof.

$\endgroup$
3
  • $\begingroup$ Am I missing something at the end here? It seems like you have $||F||_2^2 \leq \frac{k \epsilon}{k-1}$, not $||F||_2$. $\endgroup$ Mar 21, 2013 at 19:03
  • $\begingroup$ Kevin -- thanks! You're absolutely right, and that means there's also an $\varepsilon^2$ that needs tracing through the argument. I'll fix this now and see what I get. $\endgroup$ Mar 21, 2013 at 19:13
  • $\begingroup$ I think that's right -- third edit lucky. I think the $L^2$ result should give $\varepsilon$ up to a (basically) constant factor like $k / (k - 1)$, meaning the $L^1$ result should go as $k \varepsilon$ times some constant factor; i.e. this hasn't made too much difference to the conclusion. $\endgroup$ Mar 21, 2013 at 19:31

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.