<p>Recall that a distribution <span class="math-container">$Y$</span> over <span class="math-container">$\{0, 1\}^n$</span> is called <a href="https://en.wikipedia.org/wiki/Small-bias_sample_space" rel="nofollow noreferrer"><span class="math-container">$\epsilon$</span>-biased</a> if for every nonempty set <span class="math-container">$P \subseteq [n]$</span>, we have
<span class="math-container">$$
\left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}.
$$</span>
In other words, an <span class="math-container">$\epsilon$</span>-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error <span class="math-container">$\epsilon/2$</span>. I claim that an <span class="math-container">$\epsilon$</span>-biased distribution automatically also fools functions of the form <span class="math-container">$\mathsf{AND} \circ \mathsf{PARITY}$</span>. That is:</p>
<p><strong>Claim:</strong> Let <span class="math-container">$f \colon \{0, 1\}^n \to \{0, 1\}$</span> be of the form <span class="math-container">$f(x) = \wedge_{i = 1}^m \bigoplus_{j \in P_i} x_j$</span>, where <span class="math-container">$P_1, \dots, P_m \subseteq [n]$</span>. Let <span class="math-container">$Y$</span> be <span class="math-container">$\epsilon$</span>-biased and let <span class="math-container">$U$</span> be uniform random over <span class="math-container">$\{0, 1\}^n$</span>. Then
<span class="math-container">$$
\left|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]\right| \leq \epsilon.
$$</span></p>
<p><strong>Proof:</strong> We can use the Fourier expansion of the AND function:
<span class="math-container">$$
f(x) = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot \prod_{i \in T} (-1)^{\oplus_{j \in P_i} x_j} = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot (-1)^{\bigoplus_{i \in T, j \in P_i} x_j}
$$</span>
For a fixed <span class="math-container">$T \subseteq [m]$</span>, we have
<span class="math-container">$$
|\mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} Y_j}] - \mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} U_j}]| \leq 2 \cdot |\mathbb{E}[\oplus_{i \in T, j \in P_i} Y_j] - \mathbb{E}[\oplus_{i \in T, j \in P_i} U_j]| \leq \epsilon.
$$</span>
Therefore, by the triangle inequality,
<span class="math-container">$$
|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]| \leq \sum_{T \subseteq [m]} \frac{\epsilon}{2^m} = \epsilon. \qquad \square
$$</span>
Your condition, that <span class="math-container">$|S \cap P|$</span> and <span class="math-container">$|S \cap Q|$</span> are both odd, can be rephrased as a function <span class="math-container">$f$</span> as in the claim by considering the indicator vectors of all the sets under consideration. Under the uniform distribution, the condition is satisfied with probability <span class="math-container">$1/4$</span>. Therefore, it suffices to take <span class="math-container">$X$</span> to be the support of an <span class="math-container">$\epsilon$</span>-biased distribution with <span class="math-container">$\epsilon &lt; 1/4$</span>. Plugging in <a href="https://en.wikipedia.org/wiki/Small-bias_sample_space#Constructions_of_small_epsilon-biased_sets" rel="nofollow noreferrer">known constructions of small-biased distributions</a> gives an explicit construction with <span class="math-container">$|X| = O(n)$</span>.</p>

CC BY-SA 4.0
2020-12-22T11:46:59.893Z
Thank you! I'll look closer at this. Do you also have an idea of whether it's possible to replicate the same constant factor as in the probabilistic construction?
Magnus Wahlström
CC BY-SA 4.0
2020-12-23T20:22:59.620Z
I'm not sure, but I suspect that getting the right constant factor would be challenging.
William Hoza
CC BY-SA 4.0
2020-12-19T08:18:09.267Z
2020-12-19T08:18:09.267Z
William Hoza
<p>I'd like a construction of the following description.  Let <span class="math-container">$V$</span> be a set of <span class="math-container">$n$</span> elements.  I'd like a collection <span class="math-container">$X$</span> of subsets of <span class="math-container">$V$</span> such that for any pair <span class="math-container">$(P,Q)$</span> of disjoint subsets of <span class="math-container">$V$</span>, there is an element <span class="math-container">$S \in X$</span> such that <span class="math-container">$|S \cap P|$</span> and <span class="math-container">$|S \cap Q|$</span> are both odd.</p>
<p>Probabilistic arguments indicate that there exists solutions with <span class="math-container">$|X|=O(n)$</span>, but I'd like an explicit design.  I'd also like to know the best possible constant factor in the size <span class="math-container">$|X|$</span>.</p>
<p>It sounded basic enough that I thought it should be solved, or easily attackable, but I'm drawing a blank. Any pointers?</p>

CC BY-SA 4.0
2020-12-16T13:42:49.883Z
I suppose $P$ and $Q$ should be nonempty?
Emil Jeřábek
CC BY-SA 4.0
2020-12-22T09:39:35.893Z
Right, both are nonempty.
Magnus Wahlström
<reference-request><co.combinatorics><extremal-combinatorics>
"Parity testing set" for disjoint pairs of sets
Magnus Wahlström
# "Parity testing set" for disjoint pairs of sets

(Asked by: username_0 on 2020-12-16)

I'd like a construction of the following description. Let $V$ be a set of $n$ elements. I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there is an element $S \in X$ such that $|S \cap P|$ and $|S \cap Q|$ are both odd.

Probabilistic arguments indicate that there exists solutions with $|X|=O(n)$, but I'd like an explicit design. I'd also like to know the best possible constant factor in the size $|X|$.

It sounded basic enough that I thought it should be solved, or easily attackable, but I'm drawing a blank. Any pointers?

**Tags:** reference-request, co.combinatorics, extremal-combinatorics

> **Comments:**
> **username_1**: I suppose $P$ and $Q$ should be nonempty?  
> **username_0**: Right, both are nonempty.  

---

## 1 answers

### Answer by username_2 on 2020-12-19. Score: 4 | Accepted answer

Recall that a distribution $Y$ over $\{0, 1\}^n$ is called [$\epsilon$-biased](https://en.wikipedia.org/wiki/Small-bias_sample_space) if for every nonempty set $P \subseteq [n]$, we have
$$
\left|\mathbb{E}[\oplus\_{i \in P} Y\_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}.
$$
In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\epsilon/2$. I claim that an $\epsilon$-biased distribution automatically also fools functions of the form $\mathsf{AND} \circ \mathsf{PARITY}$. That is:

**Claim:** Let $f \colon \{0, 1\}^n \to \{0, 1\}$ be of the form $f(x) = \wedge\_{i = 1}^m \bigoplus\_{j \in P\_i} x\_j$, where $P\_1, \dots, P\_m \subseteq [n]$. Let $Y$ be $\epsilon$-biased and let $U$ be uniform random over $\{0, 1\}^n$. Then
$$
\left|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]\right| \leq \epsilon.
$$

**Proof:** We can use the Fourier expansion of the AND function:
$$
f(x) = \sum\_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot \prod\_{i \in T} (-1)^{\oplus\_{j \in P\_i} x\_j} = \sum\_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot (-1)^{\bigoplus\_{i \in T, j \in P\_i} x\_j}
$$
For a fixed $T \subseteq [m]$, we have
$$
|\mathbb{E}[(-1)^{\oplus\_{i \in T, j \in P\_i} Y\_j}] - \mathbb{E}[(-1)^{\oplus\_{i \in T, j \in P\_i} U\_j}]| \leq 2 \cdot |\mathbb{E}[\oplus\_{i \in T, j \in P\_i} Y\_j] - \mathbb{E}[\oplus\_{i \in T, j \in P\_i} U\_j]| \leq \epsilon.
$$
Therefore, by the triangle inequality,
$$
|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]| \leq \sum\_{T \subseteq [m]} \frac{\epsilon}{2^m} = \epsilon. \qquad \square
$$
Your condition, that $|S \cap P|$ and $|S \cap Q|$ are both odd, can be rephrased as a function $f$ as in the claim by considering the indicator vectors of all the sets under consideration. Under the uniform distribution, the condition is satisfied with probability $1/4$. Therefore, it suffices to take $X$ to be the support of an $\epsilon$-biased distribution with $\epsilon < 1/4$. Plugging in [known constructions of small-biased distributions](https://en.wikipedia.org/wiki/Small-bias_sample_space#Constructions_of_small_epsilon-biased_sets) gives an explicit construction with $|X| = O(n)$.

> **Comments:**
> **username_0**: Thank you! I'll look closer at this. Do you also have an idea of whether it's possible to replicate the same constant factor as in the probabilistic construction?  
> **username_2**: I'm not sure, but I suspect that getting the right constant factor would be challenging.  

---

