# How tight is the XOR lemma?

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.

• 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) – Clement C. Oct 11 '19 at 14:48 • 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? – Clement C. Oct 11 '19 at 14:52 • @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 – Andy Oct 11 '19 at 15:31 • 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\$) – Clement C. Oct 11 '19 at 19:30
• @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. – Andy Oct 11 '19 at 23:27

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