# Joint (close to uniform) distribution in finite fields

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$.

-
Which statistical distance measure do you want? – Noah Stein Mar 18 '13 at 11:25
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$$ – Div Mar 18 '13 at 17:29
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. – Div Mar 18 '13 at 17:39
Do you have any examples in the way of lower bounds? – Kevin P. Costello Mar 21 '13 at 21:35

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.

-
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$. – Kevin P. Costello Mar 21 '13 at 19:03
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. – Freddie Manners Mar 21 '13 at 19:13
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. – Freddie Manners Mar 21 '13 at 19:31