“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?

• I suppose $P$ and $Q$ should be nonempty? – Emil Jeřábek Dec 16 '20 at 13:42
• Right, both are nonempty. – Magnus Wahlström Dec 22 '20 at 9:39

1 Answer

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 < 1/4$$. Plugging in known constructions of small-biased distributions gives an explicit construction with $$|X| = O(n)$$.

• 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 Dec 22 '20 at 11:46
• I'm not sure, but I suspect that getting the right constant factor would be challenging. – William Hoza Dec 23 '20 at 20:22