"Parity testing set" for disjoint pairs of sets 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?
Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased 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 &lt; 1/4$. Plugging in known constructions of small-biased distributions gives an explicit construction with $|X| = O(n)$.