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