%last modified 1999/10/101\documentstyle[11pt]{article}2%\documentclass[12pt]{article}3%\usepackage{amssymb}4\newtheorem{lemma}{Lemma}5\newtheorem{theorem}{Theorem}6\newtheorem{corollary}{Corollary}7\newtheorem{question}{Question}8\newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}}9\newcommand{\pow}[1]{{\mathcal P}(#1)}10\newcommand{\F}{\mbox{\bf F}}11\newcommand{\Ftwo}{\mathbf{F}_2}12\newcommand{\defn}[1]{{\em #1}}13\newcommand{\bij}{\varphi}14%\title{Classification of parity structures on finite sets}15\title{Parity structures and generating functions from Boolean rings}16\author{David Petrie Moulton\footnote{This work was17done while the first author was a Research Fellow18at the University of California at Berkeley.}\\19Department of Mathematics\\20University of Wisconsin\\21Madison, WI 53706\\22\and23William A.\ Stein\\24Department of Mathematics\\25University of California\\26Berkeley, CA 94720}27\date{\today}2829\begin{document}30\maketitle3132\begin{abstract}33Let~$S$ be a finite set and~$T$ be a subset of the power set of~$S$.34Call~$T$ a \defn{parity structure} for~$S$ if, for35each subset~$b$ of~$S$ of odd size, the number of subsets of~$b$36that lie in~$T$ is even. We classify parity structures using generating37functions from a free boolean ring.38We also show that if~$T$ is a parity structure, then, for each39subset~$b$ of~$S$ of even size, the number of subsets of~$b$ of40odd size that lie in~$T$ is even. We then give several other41properties of parity structures and discuss a generalization.42%Furthermore, we obtain refinements of the43%defining property and this resultant property by44%restricting to subsets of the~$b$'s of particular sizes.45\end{abstract}4647\section{Introduction}48We were led to consider parity structures while searching for49a new class of simplicial complexes. We classified parity50structures, but our original proof was based on a51technical induction using binomial coefficients.52Later we found a more conceptual proof that uses53generating functions obtained from a free boolean algebra54over the field~$\Ftwo$ of order~$2$. In Section~2 we describe55how to view parity structures as elements of this boolean algebra,56and we use this identification to classify parity57structures. We should point out that our classification can be58formulated and proved without this boolean ring with a comparable59amount of work, but we find our method more interesting and more60instructive. In Section~3 we use the classification to find another61property of parity structures. We then prove in Section~462that parity structures satisfy stronger versions of both the defining63property and this new one. Finally, in Sections~5 and 6 we discuss64some related issues involving an ideal~$\sigma R_{S}$ we define below,65and we give a generalization of parity structures.6667\section{Free boolean algebras and generating functions}68Call a finite set \defn{even} or \defn{odd} according to the parity69of its size. Let~$S$ be a finite set, and let~$T$ be any subset70of~$\pow S$, the power set of~$S$.71We say that~$T$ is a \defn{parity structure} for~$S$ if, for each72odd subset~$b$ of~$S$, the intersection~$\pow b \cap T$ is even;73that is, if each odd subset~$b$ has an even number of subsets74that lie in~$T$. A logician might imagine that~$T$ consists of75the subsets of~$S$ that are in some model, so that~$\pow b \cap T$ is76the power set of~$b$ within the model. We are simply requiring then77that, in this model, every odd set have an even number of subsets.78(This analogy is not perfect, of course, since~$b$ need not be79in~$T$, and ~$T$ is not necessarily closed under unions,80but it is an interesting point of view to take.)8182In order to study parity structures for~$S$, we introduce a ring whose83elements correspond naturally to subsets of~$\pow S$. Let~$R_{S}$84denote the free (commutative) boolean algebra over~$\Ftwo$ generated85by idempotents corresponding to the elements of~$S$; that is, define86$$87R_{S}88:= \frac{\Ftwo[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.89$$90(Note that this is similar to, but different from, the definition of91a Stanley-Reisner ring, in which we take~$x_{s}^{2} = 0$, rather92than~$x_{s}^{2} = x_{s}$.) Since~$R_{S}$ is spanned by idempotents93and has characteristic~$2$, it follows that all of its elements are94idempotents. Define a map~$\bij$ from~$\pow{\pow{S}}$ to~$R_{S}$ by95$$96T\bij = \sum_{b \in T} \,\prod_{s \in b} x_{s}.97$$98Under this map, each subset of~$S$ maps to the monomial that is the99product of the indeterminants corresponding to the elements of the100subset, and each subset of~$\pow S$ maps to the sum of the images101of its elements. As~$R_{S}$ is spanned by its monomials,~$\bij$ is a102bijection.103104We distinguish the element~$\sigma := 1 + \sum_{s \in S} x_{s}$105of~$R_S$; it corresponds under~$\bij$ to the collection of subsets106of~$S$ of size at most~$1$. Using~$R_{S}$ we obtain a ring-theoretic107characterization of the parity structures for~$S$.108109\begin{theorem}110\label{characterize}111Let~$S$ be a finite set.112\begin{itemize}113\item[(a)]114A subset~$T$ of~$\pow{S}$ is a parity structure for~$S$115if and only if~$T\bij$ is in the ideal~$\sigma R_S$.116\item[(b)]117The elements~$\sigma t$, with~$t$ a monomial in an even number of the118generators~$x_{s}$, form an~$\Ftwo$-basis for the ideal~$\sigma R_S$.119\end{itemize}120\end{theorem}121122\begin{proof}123Write~$R$ for~$R_{S}$.124If~$S$ is empty, then all subsets of~$\pow S$ are parity structures,125and~$\sigma = 1$ generates~$R$ as an ideal, so the theorem holds.126Hence we may assume that~$S$ has positive size~$n$. Let~$P$ be127the set of all images under~$\bij$ of parity structures for~$S$.128129We first translate the set-theoretic condition for the subset~$T$130of~$\pow S$ to be a parity structure into an algebraic condition131on~$T \bij$. For any element~$t$ of~$R$ and any subset~$b$132of~$S$, write~$t(b)$ for the value of the polynomial~$t$ with each133indeterminant~$x_{s}$ set equal to~$1$ if~$s$ is in~$b$ and set134to~$0$ otherwise. This can be thought of as the evaluation of~$t$ on135the characteristic vector of~$b$. For each subset~$b$ of~$S$ and each136element~$c$ of~$T$, the term~$c \bij$ of~$T \bij$ will vanish on~$b$137if~$c$ is not a subset of~$b$ and will give the value~$1$ otherwise.138Hence~$(T \bij)(b)$ gives the parity of the number of subsets of~$b$139that lie in~$T$. Therefore,~$T$ is a parity structure if and only if140for every odd subset~$b$ of~$S$, the value of~$(T \bij)(b)$ is~$0$.141142Since polynomial specialization gives ring homomorphisms, for each143odd subset~$b$ of~$S$, the map~$\pi_{b}$ from~$R$ to~$\Ftwo$ given144by~$t \pi_{b} = t(b)$ is a homomorphism of rings.145And, as the previous remarks show that~$P$ is the intersection of the146kernels of these maps for all such subsets~$b$, we see that~$P$ is an147ideal of~$R$. Now order the odd subsets of~$S$ by increasing size148(with any order chosen for subsets of the same size)149as~$b_{1}, b_{2}, \ldots, b_{2^{n-1}}$.150Then the~$2^{n-1} \times 2^{n-1}$ matrix with~$(i,j)$-entry equal151to~$(b_{i} \bij) \pi_{b_{j}}$ is upper triangular with~$1$'s on the152main diagonal, so the homomorphisms~$\pi_{b}$ are linearly153independent over~$\Ftwo$. Hence~$P$ has154dimension~$2^{n} - 2^{n-1} = 2^{n-1}$ as an~$\Ftwo$-vector space.155156%%157% We first show that~$P$ is closed under addition.158% Let~$T\bij$ and~$T'\bij$ be elements of~$P$,159% where~$T$ and~$T'$ are parity structures.160% Because addition in~$R$ is computed modulo~$2$,161% the element~$T\bij + T'\bij$ is the image162% under~$\bij$ of the symmetric difference~$T \oplus T^{\prime}$.163% Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$164% of~$S$, the number of subsets of~$b$ lying in~$T$ is even,165% as is the number lying in~$T'$, so the number166% of subsets of~$b$ lying in~$T \oplus T'$ is also even.167% Hence~$T \oplus T'$ is a parity structure,168% so~$T\bij + T'\bij = (T \oplus T^{\prime})\bij$ is in~$P$.169%%170171%%172% Next we show that~$P$ is an ideal. Since the indeterminants~$x_{s}$173% generate the ring~$R$, it is enough to show that for every element~$t$174% of~$P$ and~$s$ in~$S$, the product~$t x_{s}$ is also in~$P$. Let~$T$175% and~$T^{\prime}$ be the subsets of~$\pow S$ corresponding to~$t$ and176% to~$t x_{s}$, respectively. Since~$T$ is a parity structure, we know177% that every odd subset~$b$ of~$S$ has an even number of subsets lying178% in~$T$, and we must show that the same holds for~$T^{\prime}$.179% If~$s$ is not an element of~$b$, then every element of~$T^{\prime}$180% contains~$s$ and so is not a subset of~$b$. Then~$b$ has~$0$ subsets181% lying in~$T^{\prime}$, and the result holds. Hence we may assume182% that~$s$ is an element of~$b$.183%%184185%%186% Next we verify that~$P$ contains the ideal~$I$ generated187% by~$\sigma = 1 + \sum_{s\in S} x_s$.188% Consider a monomial~$t$ in~$R$, and189% let~$U$ be the subset of~$\pow S$ that corresponds190% to~$\sigma t = t + \sum_{s \in S} x_{s} t$.191% Let~$c$ be the subset of~$S$ such that~$t$~$equals~$c\bij$.192% In the sum~$\sigma t$, if~$s$ is in~$c$, then~$x_{s} t$ equals~$t$;193% otherwise, it equals~$(c \cup \{s\})\bij$.194% Thus~$U$ consists of each subset of~$S$ obtained by adding195% another element to~$c$, together with~$c$ itself exactly196% if~$c$ is even.197% Consider an odd subset~$b$ of~$S$. If~$c$ is not a subset of~$b$, then198% an even number, namely zero, of subsets of~$b$ are elements of~$U$.199% If~$c$ is a subset of~$b$, then the number of subsets200% of~$b$ in~$U$ is~$|b| - |c|$ or~$|b| - |c| + 1$,201% as~$c$ is odd or even, respectively.202% Since~$b$ is odd, there are an even number of subsets of~$b$ in~$U$.203% It follows that~$U$ is a parity structure,204% so~$\sigma t=U\bij$ is in~$P$.205% Since~$P$ is closed under addition, and~$R$ is generated206% additively by the elements~$t$, it follows that~$I$207% is a subset of~$P$.208%%209210Next we verify that~$P$ contains the ideal~$I$ generated211by~$\sigma = 1 + \sum_{s\in S} x_s$. If~$b$ is any odd subset212of~$S$, then~$b$ has~$|b| + 1$ subsets of size~$0$ or~$1$, and~$|b| + 1$213is even. Hence the collection of subsets of~$S$ of size at most~$1$214is a parity structure, and as the image of this collection under~$\bij$215is~$\sigma$, we have~$\sigma \in P$. Since~$P$ is an ideal, it216contains~$I$ as a subset.217218%%219% Take any subset~$N$ of~$\pow S$220% containing only even subsets of~$S$; we claim that221% there is a unique parity structure for~$S$ that we can obtain by adding222% odd subsets of~$S$ to~$N$. We will examine the odd subsets of~$S$ in223% order of increasing size to see which ones must be added to~$N$ to224% obtain a parity structure~$T$. For each subset~$b$ of~$S$ of size~$1$,225% we must include~$b$ in~$T$ if and only if an odd number of the proper226% subsets of~$b$ are already in~$T$ (which at this point happens exactly227% if the empty set is in~$N$). Once we have determined which subsets of228% size~$1$ to include, we consider subsets of~$S$ of size~$3$. Again, we229% can tell exactly which ones we must include, based on which smaller sets230% are already in~$T$. Continuing in this way, we determine the231% unique parity structure~$T$ of the required type. Since~$S$232% has~$n \geq 1$ elements, there are~$2^{n-1}$ even subsets of~$S$,233% and there are~$2^{2^{n-1}}$ possibilities for the collection~$N$.234% As each of these collections can be extended to exactly one235% parity structure by adding odd sets,236% we see that there are exactly~$2^{2^{n-1}}$ parity structures for~$S$.237% Hence~$P$ has size~$2^{2^{n-1}}$.238%%239240Now we show that~$I$ and~$P$ have the same size, hence must be equal.241Let~$J$ be the ideal~$(1 + \sigma) R$.242Notice that~$\sigma$ and~$1 + \sigma$ are orthogonal idempotents243with sum~$1$, so~$R$ is the direct sum of~$I$ and~$J$ as rings.244Also, the linear map from~$R$ to itself sending~$x_{s_{0}}$245to~$1 + x_{s_{0}}$ (for some element~$s_{0}$ of~$S$) and fixing~$x_{s}$246for all other values of~$s$ is an automorphism of~$R$ (since~$R$247can be viewed as the free boolean algebra generated248by~$x_{s_{0}} + 1$ and the other indeterminants~$x_{s}$).249This automorphism interchanges~$\sigma$ and~$1 + \sigma$250and, hence, also~$I$ and~$J$, so~$I$ and~$J$ have the same dimension251as vector spaces over~$\Ftwo$. Since their sum~$R$252has dimension~$2^{n}$, the ideals~$I$ and~$J$ have dimension~$2^{n-1}$253over~$\Ftwo$. Thus~$I$ and~$P$ have the same~$\Ftwo$-dimension,254and since~$I$ is a subset of~$P$, they must be equal.255This completes the proof of part (a).256257We now prove part (b).258For every even-degree monomial~$t$, the product~$\sigma t$259is the sum of~$t$ and some odd-degree monomials, so these products,260with~$t$ ranging over all even-degree monomials, are linearly261independent over~$\Ftwo$. But there are~$2^{n-1}$ such262products, and by the above calculations, the dimension of~$P$263is~$2^{n-1}$, so the products form a basis for~$P$ over~$\Ftwo$.264This completes the proof of the theorem.265\end{proof}266267This result allows us to count immediately the parity structures for268a finite set.269270\begin{corollary}271\label{count}272A set of size~$n$ has~$2^{2^{n-1}}$ parity structures.273\end{corollary}274275\begin{proof}276Theorem~\ref{characterize} shows that the parity structures are in277bijection with an~$\Ftwo$-vector space of dimension~$2^{n-1}$.278\end{proof}279280\section{Another property of parity structures}281%We now prove the alternate defining property of parity structures given282%in the introduction.283We now use the results of the previous section to prove another property284of parity structures for a set~$S$ involving even subsets of~$S$.285286\begin{theorem}287\label{another}288Let~$S$ be a finite set and~$T$ be a parity structure for~$S$.289Then for every even subset~$b$ of~$S$, the number of odd subsets of~$b$290that lie in~$T$ is even.291\end{theorem}292293\begin{proof}294Suppose that the property holds for two parity structures~$T$295and~$T^{\prime}$. Then for any even subset~$b$ of~$S$, the number of296odd subsets of~$b$ that lie in~$T$ is even, as is the number that lie297in~$T^{\prime}$. Thus the same holds for their symmetric difference.298And since the image under~$\bij$ of the symmetric difference of~$T$299and~$T^{\prime}$ is the sum of their images under~$\bij$, it suffices300to check the property for some collection of parity structures whose301images under~$\bij$ form an~$\Ftwo$-basis for~$R_{S}$.302Thus by the previous theorem, it is enough to check the property for303parity structures of the form~$(\sigma t) \bij^{-1}$, with~$t$304an even-degree monomial (in distinct indeterminants).305306Such a monomial~$t$ equals~$c\bij$ for some even subset~$c$ of~$S$.307>From the definition of~$\bij$, the parity308structure~$T = (\sigma t) \bij^{-1}$ consists of~$c$ together309with all subsets of~$S$ obtained by adding one new element to~$c$.310Now take any even subset~$b$ of~$S$. If~$c$ is not a subset of~$b$,311then the number of odd subsets of~$b$ that lie in~$T$ is zero, so we312may assume that~$c$ is a subset of~$b$. Then the odd subsets of~$b$313that lie in~$T$ are exactly those subsets of~$b$ obtained by adding a314new element to~$c$. But there are~$|b| - |c|$ such subsets, and since315both~$|b|$ and~$|c|$ are even, the number of such subsets is even.316This completes the proof of the theorem.317\end{proof}318319\section{Refinements of results}320We can now show that parity structures have stronger forms both of321the defining property and of the one given in the previous section.322These state not merely that some collection of sets is even, but that323when the collection is partitioned in some way according to sizes of324the sets involved, every part of the partition contains an even325number of sets.326327\begin{corollary}328\label{refine}329Let~$S$ be any finite set and~$T$ be any parity structure~$T$ for~$S$.330\begin{enumerate}331\item[a)]332For every odd subset~$b$ of~$S$ and every even natural number~$k$,333there are an even number of subsets of~$b$ of size~$k$ or~$k + 1$334that lie in~$T$.335\item[b)]336For every even subset~$b$ of~$S$ and every odd natural number~$k$,337there are an even number of subsets of~$b$ of size~$k$ that lie in~$T$.338\end{enumerate}339\end{corollary}340341\begin{proof}342As in the proof of Theorem~\ref{another}, it suffices to consider the343case when~$T$ is of the form~$\bij^{-1}(\sigma t)$ for some344even-degree monomial~$t$. But then parts a) and b) follow from345Theorems~\ref{characterize} and~\ref{another}, respectively,346for~$k$ equal to the degree of~$t$ (plus~$1$ for part b)),347and they hold trivially for all other values of~$k$.348\end{proof}349350\section{The ideal~$\sigma R_{S}$ and Halm\"os's ring}351We should like to make a few remarks pointing out another way to think352about the ideal mentioned in the proof of Theorem~\ref{characterize}.353It is straightforward to see that the ring~$R = R_{S}$,354with~$S$ of size~$n$, is semisimple and is isomorphic to~$\Ftwo^{n}$355via the set of primitive (central) orthogonal356idempotents~$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \,357| \, \epsilon_{s} \in \Ftwo\}$.358Since the ideals of~$\Ftwo$ are just itself and~$(0)$, the elements359of the ideal~$\sigma R$ are just those elements of~$R$ that have support360on the coordinates corresponding to the idempotents lying in~$\sigma R$.361An idempotent~$t = \prod (x_{s} + \epsilon_{s})$ will be in the362ideal~$\sigma R$ if and only if~$t$363equals~$\sigma t = t + \sum_{s \in S} x_{s} t$. This happens exactly if364an even number of the terms in the summation equal~$t$ (while the rest365vanish), which happens if and only if an even number of the field366elements~$\epsilon_{s}$ equal~$0$. To summarize, the elements367of~$\sigma R$ are the~$\Ftwo$-linear combinations of those368idempotents~$\prod (x_{s} + \epsilon_{s})$369that have an even number of the elements~$\epsilon_{s}$ equal to~$0$,370which is the same as having the lowest-degree term be of even degree.371372We now point out a relationship between the ring~$R_{S}$373used in our proofs above and a similar boolean ring Halm\"os discusses374in his boolean algebra book\cite{halmos}. For a set~$U$, he considers375the ring~$2^{U}$ of functions from~$U$ to~$\Ftwo$ with coordinatewise376addition and multiplication. Notice that the sum of the377characteristic functions of two subsets of~$U$ is the characteristic378function of their symmetric difference, while the product is the379characteristic function of their intersection. This construction can,380of course, be applied with the power set of~$S$ in place of~$U$ to381obtain the ring~$2^{\pow S}$. We can identify the elements of382each of the rings~$R_{S}$ and~$2^{\pow S}$ with383collections of subsets of~$S$, and in each ring, addition384corresponds to taking the symmetric difference of two collections.385Multiplication, however, has different interpretations in the two386rings. In~$R_{S}$, it corresponds to taking all unions of a subset387from the first collection and a subset from the second collection388(counted with appropriate multiplicities modulo~$2$), while389in~$2^{\pow S}$, it corresponds to taking the subsets that occur390in both collections. Both rings, however, are free boolean rings391of the same dimension over~$\Ftwo$, and so are isomorphic.392393As indicated above, the primitive orthogonal idempotents of394the ring~$R_{S}$ are (with our usual notation) all products of395the form~$\prod_{i=1}^{n} (x_{i} + \epsilon_{i})$ with each396term~$\epsilon_{i}$ an element of~$\Ftwo$.397A bit of calculation now shows that sending such an idempotent to398the function~$x_{i} \mapsto \epsilon_{i}$ and extending linearly399gives a natural isomorphism from~$R_{S}$ to~$2^{\pow S}$. Finally,400the element~$\sigma$ is the sum of those idempotents with an even401number of the terms~$\epsilon_{i}$ equal to~$0$, so corresponds402in~$2^{\pow S}$ to the sum of the characteristic functions of the403co-even subsets of~$S$ (those with even complement in~$S$).404405\section{A generalization of parity structures}406We now give a generalization of the notion of parity structures,407and we discuss some of our results above that can be extended to this408situation. In order to motivate our generalization, we note that a409subset~$T$ of the power set of~$S$ is a parity structure if and only410if for every subset~$b$ of~$S$, the product~$|b| \, |\pow{b} \cap T|$411is even.412413Let~$m$ be a positive integer,~$S$ be a finite set, and~$T$ be a414multiset whose elements are subsets of~$S$, each having a multiplicity415less than~$m$. We say that~$T$ is a \defn{mod-$m$ parity416multistructure} for~$S$ if, for each subset~$b$ of~$S$, the number~$m$417divides~$|b| \, |\pow{b} \cap T|$, where, in this intersection,418we count each set with the same multiplicity it has in~$T$.419If~$T$ actually is a set (that is, has all multiplicities at most~$1$),420then we say that it is a \defn{mod-$m$ parity structure}.421422In order to understand mod-$m$ parity multistructures, we use the ring423$$424R_{S,m}425:= \frac{{\bf Z}/m{\bf Z}[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, :426\, s \in S)}.427$$428We define a map~$\bij$ from the collection of multisets of subsets429of~$S$ to~$R_{S,m}$ just as before, by sending a subset~$a$ of~$S$430to~$\prod_{s \in a} x_{s}$ and extending linearly.431In this ring~$R_{S,m}$ we define~$\sigma$432to be~$\sum_{|a| < m} \prod_{s \in a} (-x_{s})$. Notice that both of433these definitions agree with our earlier ones in the case where~$m$434is~$2$. As in the proof of Theorem~\ref{characterize}, we can show435that the images under~$\bij$ of mod-$m$ parity multistructures form436the ideal~$\sigma R_{S,m}$. If~$S$ has size~$n$, then,437as in Corollary~\ref{count}, there will be a total438of~$m^{\sum_{i=0}^{\lfloor n/m \rfloor} {n \choose mi}}$439mod-$m$ parity multistructures. However, as we lack the automorphism440of~$R_{S}$ interchanging the ideals corresponding to~$I$ and~$J$ from441the proof of Theorem~\ref{characterize}, we do not obtain a442formula as simple as the one from that theorem.443444We can also generalize Theorem~\ref{another} and445Corollary~\ref{refine}. Again, the proofs are similar to the ones we446have for parity structures, but for the second, there is a bit of447calculation with binomial coefficients.448449\begin{theorem}450For every mod-$m$ parity multistructure~$T$ for a finite set~$S$451and every subset~$b$ of~$S$ of size divisible by~$m$, the number of452subsets of~$b$ of size relatively prime to~$m$ that lie in~$T$ is a453multiple of~$m$.454\end{theorem}455456For a collection~$T$ of subsets of a finite set~$S$ and a sequence of457natural numbers~$a_{1}, a_{2}, \ldots, a_{k}$,458write~$|T|_{a_{1}, a_{2}, \ldots, a_{k}}$ for the number of elements459of~$T$ having size equal to~$a_{i}$ for some value of~$i$.460461\begin{theorem}462Let~$T$ be a mod-$m$ parity multistructure for a finite set~$S$.463\begin{enumerate}464\item[a)]465For any subset~$b$ of~$S$ and any multiple~$k$ of~$m$, the number~$m$466divides~$|b| \, |\pow{b} \cap T|_{k, k+1, \ldots, k+m-1}$.467\item[b)]468For any subset~$b$ of~$S$ of size divisible by~$m$ and any natural469number~$k$, the number~$m$ divides~$(m,k) \, |\pow{b} \cap T|_{k}$,470where~$(m,k)$ is the greatest common divisor of~$m$ and~$k$.471\end{enumerate}472\end{theorem}473474It is harder, on the other hand, to understand mod-$m$ parity structures.475We know of two basic families: For any subset~$c$ of~$S$ of size476congruent to~$1$ modulo~$m$, the collection of subsets of~$S$ obtained477by adding~$m-1$ new elements to~$c$ form a mod-$m$ parity structure.478And for any subset~$c$ of~$S$ of size congruent to~$2$ modulo~$m$,479the collection of subsets of~$S$ obtained by adding either~$m-2$480or~$m-1$ new elements to~$c$ form a mod-$m$ parity structure.481Of course, any disjoint unions of collections of the above types will482also be mod-$m$ parity structures, but for~$m$ greater than~$2$,483these are the only examples we know. It would be nice to know484whether there are more, and we pose the following open problem:485486\begin{question}487How many mod-$m$ parity structures are there on a set of size~$n$?488\end{question}489490\begin{thebibliography}{9}491\bibitem{halmos}492Paul Halm\"os, something about boolean algebras.493\end{thebibliography}494\end{document}495496497498