Another property of parity structures

Now we introduce another property of subsets of the power set of S, this time one involving odd subsets of even subsets of S. We say that a subset T of the power set of S is a quasi-parity structure for S if, for every even subset b of S, the number of odd subsets of b that lie in T is even. This term is justified by our next theorem.

Theorem 2   Every parity structure for a finite set is also a quasi-parity structure for that set.

PROOF:Suppose that T and  $T^{\prime}$ are both quasi-parity structures for a finite set S. Then for any even subset b of S, the number of odd subsets of b that lie in T is even, as is the number that lie in  $T^{\prime}$. Thus the same holds for their symmetric difference. And since the image under $\varphi$ of the symmetric difference of T and  $T^{\prime}$ is the sum of their images under $\varphi$, it suffices to check the result for some collection of parity structures whose images under $\varphi$ form an  $\mbox{\bf F}_2$-basis for R_S. Hence by the previous theorem, it is enough to show that parity structures of the form  $(\sigma t) \varphi^{-1}$, with t an even-degree monomial (in distinct indeterminants) are quasi-parity structures.

Such a monomial t equals $c \varphi$ for some even subset c of S. >From the definition of $\varphi$, the parity structure  $T = (\sigma t) \varphi^{-1}$ consists of c together with all subsets of S obtained by adding one new element to c. Now take any even subset b of S. If c is not a subset of b, then the number of odd subsets of b that lie in T is zero, so we may assume that c is a subset of b. Then the odd subsets of b that lie in T are exactly those subsets of b obtained by adding a new element to c. But there are |b| - |c| such subsets, and since both |b| and |c| are even, the number of such subsets is even. Thus T is a quasi-parity structure. This completes the proof of the theorem. $\Box$

It is worth noting that the converse of Theorem 2 is false. Since the definition of a quasi-parity structure refers only to those elements of T that are odd subsets of S, any collection of even subsets of S will be a quasi-parity structure. On the other hand, the collection consisting of just the empty set will not be a parity structure, unless S is empty. More generally, since quasi-parity structures are closed under taking symmetric differences, the symmetric difference of any parity structure and any collection of even subsets of S will be a quasi-parity structure, and it can be shown that all quasi-parity structures are of this form. Moreover, for $n \geq 2$, there are exactly  $2^{3 \cdot 2^{n-2}}$ quasi-parity structures for S.