Parity structures and generating functions from Boolean rings

David Petrie Moulton^{∗} Department of Mathematics University of Wisconsin Madison, WI 53706

William A. Stein Department of Mathematics University of California Berkeley, CA 94720

October 27, 1999

Abstract

Let S be a finite set and T be a subset of the power set of S. Call T a parity structure for S if, for each subset b of S of odd size, the number of subsets of b that lie in T is even. We classify parity structures using generating functions from a free boolean ring. We also show that if T is a parity structure, then, for each subset b of S of even size, the number of subsets of b of odd size that lie in T is even. We then give several other properties of parity structures and discuss a generalization.

1 Introduction

We were led to consider parity structures while searching for a new class of simplicial complexes. We classified parity structures, but our original proof was based on a technical induction using binomial coefficients. Later we found a more conceptual proof that uses generating functions obtained from a free boolean algebra over the field F_{2} of order 2. In Section 2 we describe how to view parity structures as elements of this boolean algebra, and we use this identification to classify parity structures. We should point out that our classification can be formulated and proved without this boolean ring with a comparable amount of work, but we find our method more interesting and more instructive. In Section 3 we use the classification to find another property of parity structures. We then prove in Section 4 that parity structures satisfy stronger versions of both the defining property and this new one. Finally, in Sections 5 and 6 we discuss some related issues involving an ideal σR_{S} we define below, and we give a generalization of parity structures.

∗This work was done while the first author was a Research Fellow at the University of California at Berkeley.

2 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 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 P(b)∩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 P(b) ∩ 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 P(S). Let R_{S} denote the free (commutative) boolean algebra over F_{2} generated by idempotents corresponding to the elements of S; that is, define

R_{S} := \frac{F_{2}[x_{s} : s ∈ S]}{(x_{s}^{2} − x_{s} : s ∈ S)}.

(Note that this is similar to, but different from, the definition of a Stanley-Reisner ring, in which we take x_{s}^{2} = 0, rather than x_{s}^{2} = 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 φ from P(P(S)) to R_{S} by

T φ = ∑_{b∈T} ∏_{s∈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 P(S) maps to the sum of the images of its elements. As R_{S} is spanned by its monomials, φ is a bijection.

We distinguish the element σ := 1 + ∑_{s∈S} x_{s} of R_{S}; it corresponds under φ 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 P(S) is a parity structure for S if and only if T φ is in the ideal σR_{S}.

(b) The elements σt, with t a monomial in an even number of the generators x_{s}, form an F_{2}-basis for the ideal σR_{S}.

Proof: Let S have size n, write R for R_{S}, and let P be the set of all images under φ of parity structures for S. If S is empty, then all subsets of P(S) are parity structures, and σ = 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 P(S) to be a parity structure into an algebraic condition on T φ. 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φ of T φ will vanish on b if c is not a subset of b and will give the value 1 otherwise. Hence (T φ)(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 φ)(b) is 0.

Since polynomial specialization gives ring homomorphisms, for each odd subset b of S, the map π_{b} from R to F_{2} given by tπ_{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}, …, b_{2^{n−1}}. Then the 2^{n−1}×2^{n−1} matrix with (i, j)-entry equal to (b_{i}φ)π_{b_{j}} is upper triangular with 1’s on the main diagonal, so the homomorphisms π_{b} are linearly independent over F_{2}. Hence P has dimension 2^{n} − 2^{n−1} = 2^{n−1} as an F_{2}-vector space.

Next we verify that P contains the ideal I generated by σ = 1+∑_{s∈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 φ is σ, we have σ ∈ 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 + σ)R. Notice that σ and 1 + σ 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_{s_{0}} to 1 + x_{s_{0}} (for some element s_{0} 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_{s_{0}} and the other indeterminants x_{s}). This automorphism interchanges σ and 1 + σ and, hence, also I and J, so I and J have the same dimension as vector spaces over F_{2}. Since their sum R has dimension 2^{n}, the ideals I and J have dimension 2^{n−1} over F_{2}. Thus I and P have the same 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 σ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 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 F_{2}. This completes the proof of the theorem. □

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

Corollary 1 For n ≥ 1, a set of size n has 2^{2^{n−1}} parity structures.

Proof: Theorem 1 shows that the parity structures are in bijection with an F_{2}-vector space of dimension 2^{n−1}. □

3 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′ 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′. Thus the same holds for their symmetric difference. And since the image under φ of the symmetric difference of T and T′ is the sum of their images under φ, it suffices to check the result for some collection of parity structures whose images under φ form an F_{2}-basis for R_{S}. Hence by the previous theorem, it is enough to show that parity structures of the form (σt)φ^{−1}, with t an even-degree monomial (in distinct indeterminants) are quasi-parity structures.

Such a monomial t equals cφ for some even subset c of S. ¿From the definition of φ, the parity structure T = (σt)φ^{−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. □

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 quasiparity 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 ≥ 2, there are exactly 2^{3·2^{n−2}} quasi-parity structures for S.

4 Refinements of results

We now show that parity structures satisfy stronger versions both of the defining condition and of the condition in the definition of a quasi-parity structure. These refinements state not merely that some collection of sets is even, but that when the collection is partitioned in some way according to sizes of the sets involved, every part of the partition contains an even number of sets.

Corollary 2 Let S be any finite set and T be any parity structure for S.

a) For every odd subset b of S and every even natural number k, there are an even number of subsets of b of size k or k + 1 that lie in T.

b) For every even subset b of S and every odd natural number k, there are an even number of subsets of b of size k that lie in T.

Proof: As in the proof of Theorem 2, it suffices to consider the case when T is of the form φ^{−1}(σt) for some even-degree monomial t. But then parts a) and b) follow from Theorems 1 and 2, respectively, for k equal to the degree of t or this degree plus 1, and they hold trivially for all other values of k. □

Of course, given the fact that every quasi-parity structure is the symmetric difference of a parity structure and a collection of even sets, it easily follows that quasi-parity structures also satisfy the condition in part b) of Corollary 2.

5 The ideal σR_{S} and the ring 2^{P(S)}

We should like to make a few remarks pointing out another way to think about the ideal mentioned in the proof of Theorem 1. It is straightforward to see that the ring R = R_{S}, with S of size n, is semisimple and is isomorphic to F_{2}^{n} via the set of primitive (central) orthogonal idempotents {∏_{s∈S}(x_{s} + ϵ_{s}) | ϵ_{s} ∈ F_{2}}. Since the ideals of F_{2} are just itself and (0), the elements of the ideal σR are just those elements of R that have support on the coordinates corresponding to the idempotents lying in σR. An idempotent t = ∏(x_{s}+ϵ_{s}) will be in the ideal σR if and only if t equals σt = t+∑_{s∈S} x_{s}t. This happens exactly if an even number of the terms in the summation equal t (while the rest vanish), which happens if and only if an even number of the field elements ϵ_{s} equal 0. To summarize, the elements of σR are the F_{2}-linear combinations of those idempotents ∏(x_{s} + ϵ_{s}) that have an even number of the elements ϵ_{s} equal to 0, which is the same as having the lowest-degree term be of even degree.

We now point out a relationship between the ring R_{S} used in our proofs above and a similar boolean ring Halmos discusses in his boolean algebra book [1]. For a set U, he considers the ring 2^{U} of functions from U to F_{2} with coordinatewise addition and multiplication. Notice that the sum of the characteristic functions of two subsets of U is the characteristic function of their symmetric difference, while the product is the characteristic function of their intersection. This construction can, of course, be applied with the power set of S in place of U to obtain the ring 2^{P(S)}. We can identify the elements of each of the rings R_{S} and 2^{P(S)} with collections of subsets of S, and in each ring, addition corresponds to taking the symmetric difference of two collections. Multiplication, however, has different interpretations in the two rings. In R_{S}, it corresponds to taking all unions of a subset from the first collection and a subset from the second collection (counted with appropriate multiplicities modulo 2), while in 2^{P(S)}, it corresponds to taking the subsets that occur in both collections. Both rings, however, are free boolean rings of the same dimension over F_{2}, and so are isomorphic.

As indicated above, the primitive orthogonal idempotents of the ring R_{S} are (with our usual notation) all products of the form ∏_{i=1}^{n}(x_{i}+ϵ_{i}) with each term ϵ_{i} an element of F_{2}. A bit of calculation now shows that sending such an idempotent to the function x_{i} ↦ ϵ_{i} and extending linearly gives a natural isomorphism from R_{S} to 2^{P(S)}. Finally, the element σ is the sum of those idempotents with an even number of the terms ϵ_{i} equal to 0, so corresponds in 2^{P(S)} to the sum of the characteristic functions of the co-even subsets of S (those with even complement in S).

6 A generalization of parity structures

We now give a generalization of the notion of parity structures, and we discuss some of our results above that can be extended to this situation. In order to motivate our generalization, we note that a subset T of the power set of S is a parity structure if and only if for every subset b of S, the product |b| |P(b) ∩ T | is even.

Let m be a positive integer, S be a finite set, and T be a multiset whose elements are subsets of S, each having a multiplicity less than m. We say that T is a mod-m parity multistructure for S if, for each subset b of S, the number m divides |b| |P(b) ∩ T |, where, in this intersection, each subset of b is counted as many times as it occurs in T. If T actually is a set (that is, has all multiplicities at most 1), then we say that it is a mod-m parity structure.

In order to understand mod-m parity multistructures, we use the ring

R_{S,m} := \frac{Z/mZ[x_{s} : s ∈ S]}{(x_{s}^{2} − x_{s} : s ∈ S)}.

We define a map φ from the collection of multisets of subsets of S to R_{S,m} just as before, by sending a subset a of S to ∏_{s∈a} x_{s} and extending linearly. In this ring R_{S,m} we define σ to be ∑_{|a|<m} ∏_{s∈a}(−x_{s}). Notice that both of these definitions agree with our earlier ones in the case where m is 2. As in the proof of Theorem 1, we can show that the images under φ of mod-m parity multistructures form the ideal σR_{S,m}. If S has size n, then, as in

Corollary 1, there will be a total of m∑{⌊n/m⌋ \atop i=0} ^{\binom{n}{mi}} mod-m parity multistructures. However, as we lack the automorphism of R_{S} interchanging the ideals corresponding to I and J from the proof of Theorem 1, we do not obtain a formula as simple as the one from that theorem.

We can also generalize Theorem 2 and Corollary 2. Again, the proofs are similar to the ones we have for parity structures, but for the second, there is a bit of calculation with binomial coefficients.

Theorem 3 For every mod-m parity multistructure T for a finite set S and every subset b of S of size divisible by m, the number of subsets of b of size relatively prime to m that lie in T is a multiple of m.

For a collection T of subsets of a finite set S and a sequence of natural numbers a_{1}, a_{2}, …, a_{k}, write |T |_{a_{1},a_{2},...,a_{k}} for the number of elements of T having size equal to a_{i} for some value of i.

Theorem 4 Let T be a mod-m parity multistructure for a finite set S.

a) For any subset b of S and any multiple k of m, the number m divides |b| |P(b) ∩ T |_{k,k+1,...,k+m−1}.

b) For any subset b of S of size divisible by m and any natural number k, the number m divides (m, k) |P(b) ∩ T |_{k}, where (m, k) is the greatest common divisor of m and k.

It is harder, on the other hand, to understand mod-m parity structures. We know of two basic families: For any subset c of S of size congruent to 1 modulo m, the collection of subsets of S obtained by adding m − 1 new elements to c forms a mod-m parity structure. And for any subset c of S of size congruent to 2 modulo m, the collection of subsets of S obtained by adding either m − 2 or m − 1 new elements to c forms a mod-m parity structure. Of course, any disjoint unions of collections of the above types will also be mod-m parity structures, but for m greater than 2, these are the only examples we know. It would be nice to know whether there are more, and we pose the following open problem:

Question 1 How many mod-m parity structures are there on a set of size n?

References

[1] Paul Halmos, Lectures on Boolean Algebras, Springer-Verlag, 1970.