Free boolean algebras and generating functions

Call a finite set even or odd according to the parity of its size. Let S be a finite set, and let T be any subset of  ${\mathcal P}(S)$, the power set of S. We say that T is a parity structure for S if, for each odd subset b of S, the intersection  ${\mathcal P}(b) \cap T$ is even; that is, if each odd subset b has an even number of subsets that lie in T. A logician might imagine that T consists of the subsets of S that are in some model, so that  ${\mathcal P}(b) \cap T$ is the power set of b within the model. We are simply requiring then that, in this model, every odd set have an even number of subsets. (This analogy is not perfect, of course, since b need not be in T, and  T is not necessarily closed under unions, but it is an interesting point of view to take.)

In order to study parity structures for S, we introduce a ring whose elements correspond naturally to subsets of  ${\mathcal P}(S)$. Let R_S denote the free (commutative) boolean algebra over  $\mbox{\bf F}_2$ generated by idempotents corresponding to the elements of S; that is, define

$$R_{S} := \frac{\mbox{\bf F}_2[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.$$

(Note that this is similar to, but different from, the definition of a Stanley-Reisner ring, in which we take  x_s² = 0, rather than  x_s² = x_s.) Since R_S is spanned by idempotents and has characteristic 2, it follows that all of its elements are idempotents. Define a map $\varphi$ from  ${\mathcal P}({\mathcal P}(S))$ to R_S by

$$T\varphi= \sum_{b \in T} \,\prod_{s \in b} x_{s}.$$

Under this map, each subset of S maps to the monomial that is the product of the indeterminants corresponding to the elements of the subset, and each subset of  ${\mathcal P}(S)$ maps to the sum of the images of its elements. As R_S is spanned by its monomials, $\varphi$ is a bijection.

We distinguish the element  $\sigma := 1 + \sum_{s \in S} x_{s}$ of R_S; it corresponds under $\varphi$ to the collection of subsets of S of size at most 1. Using R_S we obtain a ring-theoretic characterization of the parity structures for S.

Theorem 1   Let S be a finite set.

(a)

A subset T of  ${\mathcal P}(S)$ is a parity structure for S if and only if $T\varphi$ is in the ideal  $\sigma R_{S}$.

(b)

The elements $\sigma t$, with t a monomial in an even number of the generators x_s, form an  $\mbox{\bf F}_2$-basis for the ideal  $\sigma R_{S}$.

PROOF:Let S have size n, write R for R_S, and let P be the set of all images under $\varphi$ of parity structures for S. If S is empty, then all subsets of  ${\mathcal P}(S)$ are parity structures, and  $\sigma = 1$ generates R as an ideal, so the theorem holds. Hence we may assume that n is positive.

We first translate the set-theoretic condition for the subset T of  ${\mathcal P}(S)$ to be a parity structure into an algebraic condition on $T\varphi$. For any element t of R and any subset b of S, write t(b) for the value of the polynomial t with each indeterminant x_s set equal to 1 if s is in b and set to 0 otherwise. This can be thought of as the evaluation of t on the characteristic vector of b. For each subset b of S and each element c of T, the term $c \varphi$ of $T\varphi$ will vanish on b if c is not a subset of b and will give the value 1 otherwise. Hence  $(T \varphi)(b)$ gives the parity of the number of subsets of b that lie in T. Therefore, T is a parity structure if and only if, for every odd subset b of S, the value of  $(T \varphi)(b)$ is 0.

Since polynomial specialization gives ring homomorphisms, for each odd subset b of S, the map $\pi_{b}$ from R to  $\mbox{\bf F}_2$ given by  $t \pi_{b} = t(b)$ is a homomorphism of rings. And, as the previous remarks show that P is the intersection of the kernels of these maps for all such subsets b, we see that P is an ideal of R. Now order the odd subsets of S by increasing size (with any order chosen for subsets of the same size) as  $b_{1}, b_{2}, \ldots, b_{2^{n-1}}$. Then the  $2^{n-1} \times 2^{n-1}$ matrix with (i,j)-entry equal to  $(b_{i} \varphi) \pi_{b_{j}}$ is upper triangular with 1's on the main diagonal, so the homomorphisms $\pi_{b}$ are linearly independent over  $\mbox{\bf F}_2$. Hence P has dimension  2ⁿ - 2^n-1 = 2^n-1 as an  $\mbox{\bf F}_2$-vector space.

Next we verify that P contains the ideal I generated by  $\sigma = 1 + \sum_{s\in S} x_s$. If b is any odd subset of S, then b has |b| + 1 subsets of size 0 or 1, and |b| + 1 is even. Hence the collection of subsets of S of size at most 1 is a parity structure, and as the image of this collection under $\varphi$ is $\sigma$, we have  $\sigma \in P$. Since P is an ideal, it contains I as a subset.

Now we show that I and P have the same size, hence must be equal. Let J be the ideal  $(1 + \sigma) R$. Notice that $\sigma$ and  $1 + \sigma$ are orthogonal idempotents with sum 1, so R is the direct sum of I and J as rings. Also, the linear map from R to itself sending x_s0 to  1 + x_s0 (for some element s₀ of S) and fixing x_s for all other values of s is an automorphism of R (since R can be viewed as the free boolean algebra generated by  1 + x_s0 and the other indeterminants x_s). This automorphism interchanges $\sigma$ and  $1 + \sigma$ and, hence, also I and J, so I and J have the same dimension as vector spaces over  $\mbox{\bf F}_2$. Since their sum R has dimension 2ⁿ, the ideals I and J have dimension 2^n-1 over  $\mbox{\bf F}_2$. Thus I and P have the same  $\mbox{\bf F}_2$-dimension, and since I is a subset of P, they must be equal. This completes the proof of part (a).

Finally, we prove part (b). For every even-degree monomial t, the product $\sigma t$ is the sum of t and some odd-degree monomials, so these products, with t ranging over all even-degree monomials, are linearly independent over  $\mbox{\bf F}_2$. But there are 2^n-1 such products, and by the above calculations, the dimension of P is 2^n-1, so the products form a basis for P over  $\mbox{\bf F}_2$. This completes the proof of the theorem. $\Box$

This result allows us to count immediately the parity structures for a finite set.

Corollary 1   For $n \geq 1$, a set of size n has  2^2n-1 parity structures.

PROOF:Theorem 1 shows that the parity structures are in bijection with an  $\mbox{\bf F}_2$-vector space of dimension 2^n-1. $\Box$