<p>Instead of choosing <span class="math-container">$z\in\{-1,1\}^{2^n}$</span> uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as <em>bent</em> functions:</p>

<blockquote>
  <p><strong>Definition.</strong> A Boolean function <span class="math-container">$f\colon\{-1,1\}^n\to\{-1,1\}$</span> is called <em>bent</em> if <span class="math-container">$|\hat{f}(S)|=2^{-n/2}$</span> for all <span class="math-container">$S\subseteq [n]$</span>.</p>
</blockquote>

<p>Such functions are known to exist; see, e.g., Chapter 6.3 of Ryan O'Donnell's <em>Analysis of Boolean functions</em> (2014) (or the <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1039" rel="nofollow noreferrer">online version</a>).</p>

CC BY-SA 4.0
2019-10-11T23:40:12.720Z
2019-10-11T23:40:12.720Z
Clement C.
<p>The XOR lemma states that if you have a distribution <span class="math-container">$D$</span> on <span class="math-container">$\{0,1\}^n$</span>, and all the Fourier coefficients of <span class="math-container">$2^n D$</span> are small, then it is close in <span class="math-container">$L_1$</span> to the uniform distribution. Specifically, suppose all Fourier coefficients are at most <span class="math-container">$\epsilon$</span>.</p>

<p>The argument is a simple application of Cauchy—Schwarz with the fact Fourier preserves the <span class="math-container">$L_2$</span> norm to obtain:</p>

<p><span class="math-container">$$|U-D|_1 \leq 2^{n/2} \epsilon$$</span></p>

<p>How tight is this? I obviously care about the exponent of <span class="math-container">$2$</span>, not a constant outside.</p>

<p>I was a certain a 'probabilistic' <span class="math-container">$D$</span> would show tightness but that doesn't seem to be the case. Below is an explanation:</p>

<p>Consider generating <span class="math-container">$D$</span> as follows: let <span class="math-container">$D(x)$</span> be <span class="math-container">$\frac{1}{2^n} + z(x)\frac{\epsilon}{2^{n/2}}$</span> where <span class="math-container">$z(x)$</span> is iid on <span class="math-container">$\{-1,1\}$</span>.</p>

<p>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 <span class="math-container">$2^{n/2}$</span> with our <span class="math-container">$z$</span>, and then we'll get more than <span class="math-container">$2^{n/2} \frac{\epsilon}{2^{n/2}}$</span>.</p>

<p>Thus tightness if it exists needs to come from a controlled pseudorandom construction.</p>

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

<p>First notice that if <span class="math-container">$f,g$</span> are each bent functions on a different set of variables, then so is <span class="math-container">$fg$</span>. Thus if there is one for <span class="math-container">$m,n$</span> variables, there is one for <span class="math-container">$m+n$</span>.</p>

<p>Now consider <span class="math-container">$1/2-1/2x+1/2y+1/2xy$</span>, it's a bent function in two varibles, so tensoring gives for any even <span class="math-container">$n$</span> gives a bent function.</p>

CC BY-SA 4.0
2019-10-11T14:48:14.727Z
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.
CC BY-SA 4.0
2019-10-11T14:52:33.147Z
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.
CC BY-SA 4.0
2019-10-11T15:31:51.880Z
@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
CC BY-SA 4.0
2019-10-11T19:30:52.953Z
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.
CC BY-SA 4.0
2019-10-11T23:27:44.700Z
@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
<co.combinatorics><pr.probability><boolean-functions><pseudorandomness>
How tight is the XOR lemma?
Andy
# How tight is the XOR lemma?

(Asked by: username_0 on 2019-10-11)

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.

**Tags:** co.combinatorics, pr.probability, boolean-functions, pseudorandomness
> **Comments:**
> **username_1**: 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)  
> **username_1**: 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?  
> **username_0**: @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  
> **username_1**: 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$)  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2019-10-11. Score: 4 | Accepted answer

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](http://www.contrib.andrew.cmu.edu/~ryanod/?p=1039)).


---

