Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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