4
$\begingroup$

The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, suppose all Fourier coefficients are at most $\epsilon$.

The argument is a simple application of Cauchy—Schwarz with the fact Fourier preserves the $L_2$ norm to obtain:

$$|U-D|_1 \leq 2^{n/2} \epsilon$$

How tight is this? I obviously care about the exponent of $2$, not a constant outside.

I was a certain a 'probabilistic' $D$ would show tightness but that doesn't seem to be the case. Below is an explanation:

Consider generating $D$ as follows: let $D(x)$ be $\frac{1}{2^n} + z(x)\frac{\epsilon}{2^{n/2}}$ where $z(x)$ is iid on $\{-1,1\}$.

Even if we ignore this is probably not a distribution (I'm trying to point here that a probabilistic construction seems to fail so that's okay.) , this can't be turned into a tight example since there are so many Fourier coefficients, one of them will correlate significantly more in signs than the random $2^{n/2}$ with our $z$, and then we'll get more than $2^{n/2} \frac{\epsilon}{2^{n/2}}$.

Thus tightness if it exists needs to come from a controlled pseudorandom construction.

EDIT- As clement posted in a comment, bent functions are apparently a thing and clearly solve our tightness.

First notice that if $f,g$ are each bent functions on a different set of variables, then so is $fg$. Thus if there is one for $m,n$ variables, there is one for $m+n$.

Now consider $1/2-1/2x+1/2y+1/2xy$, it's a bent function in two varibles, so tensoring gives for any even $n$ gives a bent function.

Improve this question
$\endgroup$
5
  • $\begingroup$ Sorry if this is obvious, but why are you considering $\pm\varepsilon/\sqrt{2^n}$ instead of $\pm\varepsilon/{2^n}$? (Namely, what happens if you consider a random matching of the edges of the hypercube (to sum to 1) and set a u.a.r. $z(x)=-z(y)\in\{-1,1\}$ for each (x,y)$ in the matching) $\endgroup$
    – Clement C.
    Oct 11, 2019 at 14:48
  • $\begingroup$ As written, the function in your OP (assuming $\varepsilon \leq 1/2^{n/2}$ to have it non-negative) is not at $L_1$ distance $\varepsilon$ from uniform: each of the $2^n$ points contributes $\varepsilon/2^{n/2}$, so the $L_1$ distance is $2^{n/2}\varepsilon$. Which is consistent with the first part of your post, but is that consistent with the contradiction you claim at the end? $\endgroup$
    – Clement C.
    Oct 11, 2019 at 14:52
  • $\begingroup$ @ClementC. You're right I should have mentioned- I'm fixing the $L1$ distance to be $2^{n/2}\epsilon$ (as mine does) and then saying if you get the bias to be $\epsilon$ then you found a tight example, but in what I showed the bias is wayy more $\endgroup$
    – Andy
    Oct 11, 2019 at 15:31
  • 2
    $\begingroup$ Instead of a random $z$, have you considered either bent functions or $\varepsilon$-regular ones? (also, I am assuming you meant all Fourier coefficients *except the $\emptyset$ one at the beginning, since the uniform distribution itself corresponds to the constant $D$) $\endgroup$
    – Clement C.
    Oct 11, 2019 at 19:30
  • 2
    $\begingroup$ @ClementC. Oh wow, bent functions seem like exactly what I need if I understand them correctly from the wikipedia page (the savages describe them using walsh instesad of fourier). I'm having trouble finding a simple constructions, are you aware of one? Finally, if you add this as an answer I'll accept. $\endgroup$
    – Andy
    Oct 11, 2019 at 23:27

1 Answer 1

Reset to default
4
$\begingroup$

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions:

Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$.

Such functions are known to exist; see, e.g., Chapter 6.3 of Ryan O'Donnell's Analysis of Boolean functions (2014) (or the online version).

Improve this answer
$\endgroup$

Your Answer

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

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