%last modified 1999/10/12 %David, put in a current address! \documentstyle[11pt]{article} %\documentclass[12pt]{article} %\usepackage{amssymb} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{question}{Question} \newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}} \newcommand{\pow}[1]{{\mathcal P}(#1)} \newcommand{\F}{\mbox{\bf F}} \newcommand{\Ftwo}{\F_2} \newcommand{\defn}[1]{{\em #1}} \newcommand{\bij}{\varphi} %\title{Classification of parity structures on finite sets} \title{Parity structures and generating functions from Boolean rings} \author{David Petrie Moulton\footnote{This work was done while the first author was a Research Fellow at the University of California at Berkeley.}\\ Department of Mathematics\\ University of Wisconsin\\ Madison, WI 53706\\ \and William A.\ Stein\\ Department of Mathematics\\ University of California\\ Berkeley, CA 94720} \date{\today} \begin{document} \maketitle \begin{abstract} Let~$S$ be a finite set and~$T$ be a subset of the power set of~$S$. Call~$T$ a \defn{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. %Furthermore, we obtain refinements of the %defining property and this resultant property by %restricting to subsets of the~$b$'s of particular sizes. \end{abstract} \section{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~$\Ftwo$ 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~$\sigma R_{S}$ we define below, and we give a generalization of parity structures. \section{Free boolean algebras and generating functions} Call a finite set \defn{even} or \defn{odd} according to the parity of its size. Let~$S$ be a finite set, and let~$T$ be any subset of~$\pow S$, the power set of~$S$. We say that~$T$ is a \defn{parity structure} for~$S$ if, for each odd subset~$b$ of~$S$, the intersection~$\pow 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~$\pow 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~$\pow S$. Let~$R_{S}$ denote the free (commutative) boolean algebra over~$\Ftwo$ generated by idempotents corresponding to the elements of~$S$; that is, define $$ R_{S} := \frac{\Ftwo[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}^{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~$\bij$ from~$\pow{\pow{S}}$ to~$R_{S}$ by $$ T\bij = \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~$\pow S$ maps to the sum of the images of its elements. As~$R_{S}$ is spanned by its monomials,~$\bij$ is a bijection. We distinguish the element~$\sigma := 1 + \sum_{s \in S} x_{s}$ of~$R_S$; it corresponds under~$\bij$ 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$. \begin{theorem} \label{characterize} Let~$S$ be a finite set. \begin{itemize} \item[(a)] A subset~$T$ of~$\pow{S}$ is a parity structure for~$S$ if and only if~$T\bij$ is in the ideal~$\sigma R_S$. \item[(b)] The elements~$\sigma t$, with~$t$ a monomial in an even number of the generators~$x_{s}$, form an~$\Ftwo$-basis for the ideal~$\sigma R_S$. \end{itemize} \end{theorem} \begin{proof} Let~$S$ have size~$n$, write~$R$ for~$R_{S}$, and let~$P$ be the set of all images under~$\bij$ of parity structures for~$S$. If~$S$ is empty, then all subsets of~$\pow 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~$\pow S$ to be a parity structure into an algebraic condition on~$T \bij$. 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 \bij$ of~$T \bij$ will vanish on~$b$ if~$c$ is not a subset of~$b$ and will give the value~$1$ otherwise. Hence~$(T \bij)(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 \bij)(b)$ is~$0$. Since polynomial specialization gives ring homomorphisms, for each odd subset~$b$ of~$S$, the map~$\pi_{b}$ from~$R$ to~$\Ftwo$ 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} \bij) \pi_{b_{j}}$ is upper triangular with~$1$'s on the main diagonal, so the homomorphisms~$\pi_{b}$ are linearly independent over~$\Ftwo$. Hence~$P$ has dimension~$2^{n} - 2^{n-1} = 2^{n-1}$ as an~$\Ftwo$-vector space. %% % We first show that~$P$ is closed under addition. % Let~$T\bij$ and~$T'\bij$ be elements of~$P$, % where~$T$ and~$T'$ are parity structures. % Because addition in~$R$ is computed modulo~$2$, % the element~$T\bij + T'\bij$ is the image % under~$\bij$ of the symmetric difference~$T \oplus T^{\prime}$. % Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$ % of~$S$, the number of subsets of~$b$ lying in~$T$ is even, % as is the number lying in~$T'$, so the number % of subsets of~$b$ lying in~$T \oplus T'$ is also even. % Hence~$T \oplus T'$ is a parity structure, % so~$T\bij + T'\bij = (T \oplus T^{\prime})\bij$ is in~$P$. %% %% % Next we show that~$P$ is an ideal. Since the indeterminants~$x_{s}$ % generate the ring~$R$, it is enough to show that for every element~$t$ % of~$P$ and~$s$ in~$S$, the product~$t x_{s}$ is also in~$P$. Let~$T$ % and~$T^{\prime}$ be the subsets of~$\pow S$ corresponding to~$t$ and % to~$t x_{s}$, respectively. Since~$T$ is a parity structure, we know % that every odd subset~$b$ of~$S$ has an even number of subsets lying % in~$T$, and we must show that the same holds for~$T^{\prime}$. % If~$s$ is not an element of~$b$, then every element of~$T^{\prime}$ % contains~$s$ and so is not a subset of~$b$. Then~$b$ has~$0$ subsets % lying in~$T^{\prime}$, and the result holds. Hence we may assume % that~$s$ is an element of~$b$. %% %% % Next we verify that~$P$ contains the ideal~$I$ generated % by~$\sigma = 1 + \sum_{s\in S} x_s$. % Consider a monomial~$t$ in~$R$, and % let~$U$ be the subset of~$\pow S$ that corresponds % to~$\sigma t = t + \sum_{s \in S} x_{s} t$. % Let~$c$ be the subset of~$S$ such that~$t$~$equals~$c\bij$. % In the sum~$\sigma t$, if~$s$ is in~$c$, then~$x_{s} t$ equals~$t$; % otherwise, it equals~$(c \cup \{s\})\bij$. % Thus~$U$ consists of each subset of~$S$ obtained by adding % another element to~$c$, together with~$c$ itself exactly % if~$c$ is even. % Consider an odd subset~$b$ of~$S$. If~$c$ is not a subset of~$b$, then % an even number, namely zero, of subsets of~$b$ are elements of~$U$. % If~$c$ is a subset of~$b$, then the number of subsets % of~$b$ in~$U$ is~$|b| - |c|$ or~$|b| - |c| + 1$, % as~$c$ is odd or even, respectively. % Since~$b$ is odd, there are an even number of subsets of~$b$ in~$U$. % It follows that~$U$ is a parity structure, % so~$\sigma t=U\bij$ is in~$P$. % Since~$P$ is closed under addition, and~$R$ is generated % additively by the elements~$t$, it follows that~$I$ % is a subset of~$P$. %% 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~$\bij$ is~$\sigma$, we have~$\sigma \in P$. Since~$P$ is an ideal, it contains~$I$ as a subset. %% % Take any subset~$N$ of~$\pow S$ % containing only even subsets of~$S$; we claim that % there is a unique parity structure for~$S$ that we can obtain by adding % odd subsets of~$S$ to~$N$. We will examine the odd subsets of~$S$ in % order of increasing size to see which ones must be added to~$N$ to % obtain a parity structure~$T$. For each subset~$b$ of~$S$ of size~$1$, % we must include~$b$ in~$T$ if and only if an odd number of the proper % subsets of~$b$ are already in~$T$ (which at this point happens exactly % if the empty set is in~$N$). Once we have determined which subsets of % size~$1$ to include, we consider subsets of~$S$ of size~$3$. Again, we % can tell exactly which ones we must include, based on which smaller sets % are already in~$T$. Continuing in this way, we determine the % unique parity structure~$T$ of the required type. Since~$S$ % has~$n \geq 1$ elements, there are~$2^{n-1}$ even subsets of~$S$, % and there are~$2^{2^{n-1}}$ possibilities for the collection~$N$. % As each of these collections can be extended to exactly one % parity structure by adding odd sets, % we see that there are exactly~$2^{2^{n-1}}$ parity structures for~$S$. % Hence~$P$ has size~$2^{2^{n-1}}$. %% 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_{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~$\sigma$ and~$1 + \sigma$ and, hence, also~$I$ and~$J$, so~$I$ and~$J$ have the same dimension as vector spaces over~$\Ftwo$. Since their sum~$R$ has dimension~$2^{n}$, the ideals~$I$ and~$J$ have dimension~$2^{n-1}$ over~$\Ftwo$. Thus~$I$ and~$P$ have the same~$\Ftwo$-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~$\Ftwo$. 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~$\Ftwo$. This completes the proof of the theorem. \end{proof} This result allows us to count immediately the parity structures for a finite set. \begin{corollary} \label{count} For~$n \geq 1$, a set of size~$n$ has~$2^{2^{n-1}}$ parity structures. \end{corollary} \begin{proof} Theorem~\ref{characterize} shows that the parity structures are in bijection with an~$\Ftwo$-vector space of dimension~$2^{n-1}$. \end{proof} \section{Another property of parity structures} %We now prove the alternate defining property of parity structures given %in the introduction. 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 \defn{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. \begin{theorem} \label{another} Every parity structure for a finite set is also a quasi-parity structure for that set. \end{theorem} \begin{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~$\bij$ of the symmetric difference of~$T$ and~$T^{\prime}$ is the sum of their images under~$\bij$, it suffices to check the result for some collection of parity structures whose images under~$\bij$ form an~$\Ftwo$-basis for~$R_{S}$. Hence by the previous theorem, it is enough to show that parity structures of the form~$(\sigma t) \bij^{-1}$, with~$t$ an even-degree monomial (in distinct indeterminants) are quasi-parity structures. Such a monomial~$t$ equals~$c\bij$ for some even subset~$c$ of~$S$. >From the definition of~$\bij$, the parity structure~$T = (\sigma t) \bij^{-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. \end{proof} It is worth noting that the converse of Theorem~\ref{another} 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$. \section{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. \begin{corollary} \label{refine} Let~$S$ be any finite set and~$T$ be any parity structure for~$S$. \begin{enumerate} \item[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$. \item[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$. \end{enumerate} \end{corollary} \begin{proof} As in the proof of Theorem~\ref{another}, it suffices to consider the case when~$T$ is of the form~$\bij^{-1}(\sigma t)$ for some even-degree monomial~$t$. But then parts a) and b) follow from Theorems~\ref{characterize} and~\ref{another}, respectively, for~$k$ equal to the degree of~$t$ or this degree plus~$1$, and they hold trivially for all other values of~$k$. \end{proof} 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~\ref{refine}. \section{The ideal~$\sigma R_{S}$ and the ring~$2^{\pow S}$} We should like to make a few remarks pointing out another way to think about the ideal mentioned in the proof of Theorem~\ref{characterize}. It is straightforward to see that the ring~$R = R_{S}$, with~$S$ of size~$n$, is semisimple and is isomorphic to~$\Ftwo^{n}$ via the set of primitive (central) orthogonal idempotents~$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \, | \, \epsilon_{s} \in \Ftwo\}$. Since the ideals of~$\Ftwo$ are just itself and~$(0)$, the elements of the ideal~$\sigma R$ are just those elements of~$R$ that have support on the coordinates corresponding to the idempotents lying in~$\sigma R$. An idempotent~$t = \prod (x_{s} + \epsilon_{s})$ will be in the ideal~$\sigma R$ if and only if~$t$ equals~$\sigma t = t + \sum_{s \in 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~$\epsilon_{s}$ equal~$0$. To summarize, the elements of~$\sigma R$ are the~$\Ftwo$-linear combinations of those idempotents~$\prod (x_{s} + \epsilon_{s})$ that have an even number of the elements~$\epsilon_{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~\cite{halmos}. For a set~$U$, he considers the ring~$2^{U}$ of functions from~$U$ to~$\Ftwo$ 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^{\pow S}$. We can identify the elements of each of the rings~$R_{S}$ and~$2^{\pow 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^{\pow S}$, it corresponds to taking the subsets that occur in both collections. Both rings, however, are free boolean rings of the same dimension over~$\Ftwo$, 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~$\prod_{i=1}^{n} (x_{i} + \epsilon_{i})$ with each term~$\epsilon_{i}$ an element of~$\Ftwo$. A bit of calculation now shows that sending such an idempotent to the function~$x_{i} \mapsto \epsilon_{i}$ and extending linearly gives a natural isomorphism from~$R_{S}$ to~$2^{\pow S}$. Finally, the element~$\sigma$ is the sum of those idempotents with an even number of the terms~$\epsilon_{i}$ equal to~$0$, so corresponds in~$2^{\pow S}$ to the sum of the characteristic functions of the co-even subsets of~$S$ (those with even complement in~$S$). \section{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| \, |\pow{b} \cap 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 \defn{mod-$m$ parity multistructure} for~$S$ if, for each subset~$b$ of~$S$, the number~$m$ divides~$|b| \, |\pow{b} \cap 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 \defn{mod-$m$ parity structure}. In order to understand mod-$m$ parity multistructures, we use the ring $$ R_{S,m} := \frac{{\bf Z}/m{\bf Z}[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}. $$ We define a map~$\bij$ from the collection of multisets of subsets of~$S$ to~$R_{S,m}$ just as before, by sending a subset~$a$ of~$S$ to~$\prod_{s \in a} x_{s}$ and extending linearly. In this ring~$R_{S,m}$ we define~$\sigma$ to be~$\sum_{|a| < m} \prod_{s \in 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~\ref{characterize}, we can show that the images under~$\bij$ of mod-$m$ parity multistructures form the ideal~$\sigma R_{S,m}$. If~$S$ has size~$n$, then, as in Corollary~\ref{count}, there will be a total of~$m^{\sum_{i=0}^{\lfloor n/m \rfloor} {n \choose 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~\ref{characterize}, we do not obtain a formula as simple as the one from that theorem. We can also generalize Theorem~\ref{another} and Corollary~\ref{refine}. 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. \begin{theorem} 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$. \end{theorem} For a collection~$T$ of subsets of a finite set~$S$ and a sequence of natural numbers~$a_{1}, a_{2}, \ldots, a_{k}$, write~$|T|_{a_{1}, a_{2}, \ldots, a_{k}}$ for the number of elements of~$T$ having size equal to~$a_{i}$ for some value of~$i$. \begin{theorem} Let~$T$ be a mod-$m$ parity multistructure for a finite set~$S$. \begin{enumerate} \item[a)] For any subset~$b$ of~$S$ and any multiple~$k$ of~$m$, the number~$m$ divides~$|b| \, |\pow{b} \cap T|_{k, k+1, \ldots, k+m-1}$. \item[b)] For any subset~$b$ of~$S$ of size divisible by~$m$ and any natural number~$k$, the number~$m$ divides~$(m,k) \, |\pow{b} \cap T|_{k}$, where~$(m,k)$ is the greatest common divisor of~$m$ and~$k$. \end{enumerate} \end{theorem} 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: \begin{question} How many mod-$m$ parity structures are there on a set of size~$n$? \end{question} \begin{thebibliography}{9} \bibitem{halmos} Paul Halmos, {\sl Lectures on Boolean Algebras}, Springer-Verlag, 1970. \end{thebibliography} \end{document}