# 22.10 The Parity Language

We study a combinatorial property of the Parity language (the set of binary words with an even number of 1s). Let $$n$$ be a word size, $$\textit{Parity}_n$$ be the subset of Parity of words of length $$n$$, $$\overline{\textit{Parity}}_n$$ be the subset of the complement of Parity of words of length $$n$$.

For two subset $$A$$ and $$B$$, we say that $$B$$ has a limit in $$A$$ if there is a word $$u\in A$$ such that for every position $$i$$ there exists a word $$v$$ in $$B$$ that matches $$u$$ on that position (ie. $$u_i = v_i$$).

Let $$p$$ be any polynomial. Show: $\exists A \subseteq \textit{Parity}_n, \ \forall A'\subseteq A, \ |A'|\geq \frac{|A|}{p(n)}, \exists B \subseteq \overline{\textit{Parity}}_n,$ $\forall B' \subseteq B, \ |B'|\geq \frac{|B|}{p(n)},\ B' \textit{ has a limit in } A'$

Note that the set $$B$$ can be chosen accordingly to the choice of $$A'$$.

This property is useful while studying the expressive power of depth-3 boolean circuits in $$\textit{AC}^0$$. A similar property has been proved for depth-3 circuits with bounded top fan-in in a recent LICS paper, and can be traced back to Hastad, Jukna and Pudlak. Here, the goal is to extend this combinatorial statement for a bigger class of languages, and for a more general notion of limit to describe precisely the regular languages definable thanks to depth-4 circuits with bounded top fan-in.