%last modified 1999/10/121%David, put in a current address!2\documentstyle[11pt]{article}3%\documentclass[12pt]{article}4%\usepackage{amssymb}5\newtheorem{lemma}{Lemma}6\newtheorem{theorem}{Theorem}7\newtheorem{corollary}{Corollary}8\newtheorem{question}{Question}9\newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}}10\newcommand{\pow}[1]{{\mathcal P}(#1)}11\newcommand{\F}{\mbox{\bf F}}12\newcommand{\Ftwo}{\F_2}13\newcommand{\defn}[1]{{\em #1}}14\newcommand{\bij}{\varphi}15%\title{Classification of parity structures on finite sets}16\title{Parity structures and generating functions from Boolean rings}17\author{David Petrie Moulton\footnote{This work was18done while the first author was a Research Fellow19at the University of California at Berkeley.}\\20Department of Mathematics\\21University of Wisconsin\\22Madison, WI 53706\\23\and24William A.\ Stein\\25Department of Mathematics\\26University of California\\27Berkeley, CA 94720}28\date{\today}2930\begin{document}31\maketitle3233\begin{abstract}34Let~$S$ be a finite set and~$T$ be a subset of the power set of~$S$.35Call~$T$ a \defn{parity structure} for~$S$ if, for36each subset~$b$ of~$S$ of odd size, the number of subsets of~$b$37that lie in~$T$ is even. We classify parity structures using generating38functions from a free boolean ring.39We also show that if~$T$ is a parity structure, then, for each40subset~$b$ of~$S$ of even size, the number of subsets of~$b$ of41odd size that lie in~$T$ is even. We then give several other42properties of parity structures and discuss a generalization.43%Furthermore, we obtain refinements of the44%defining property and this resultant property by45%restricting to subsets of the~$b$'s of particular sizes.46\end{abstract}4748\section{Introduction}49We were led to consider parity structures while searching for50a new class of simplicial complexes. We classified parity51structures, but our original proof was based on a52technical induction using binomial coefficients.53Later we found a more conceptual proof that uses54generating functions obtained from a free boolean algebra55over the field~$\Ftwo$ of order~$2$. In Section~2 we describe56how to view parity structures as elements of this boolean algebra,57and we use this identification to classify parity58structures. We should point out that our classification can be59formulated and proved without this boolean ring with a comparable60amount of work, but we find our method more interesting and more61instructive. In Section~3 we use the classification to find another62property of parity structures. We then prove in Section~463that parity structures satisfy stronger versions of both the defining64property and this new one. Finally, in Sections~5 and 6 we discuss65some related issues involving an ideal~$\sigma R_{S}$ we define below,66and we give a generalization of parity structures.6768\section{Free boolean algebras and generating functions}69Call a finite set \defn{even} or \defn{odd} according to the parity70of its size. Let~$S$ be a finite set, and let~$T$ be any subset71of~$\pow S$, the power set of~$S$.72We say that~$T$ is a \defn{parity structure} for~$S$ if, for each73odd subset~$b$ of~$S$, the intersection~$\pow b \cap T$ is even;74that is, if each odd subset~$b$ has an even number of subsets75that lie in~$T$. A logician might imagine that~$T$ consists of76the subsets of~$S$ that are in some model, so that~$\pow b \cap T$ is77the power set of~$b$ within the model. We are simply requiring then78that, in this model, every odd set have an even number of subsets.79(This analogy is not perfect, of course, since~$b$ need not be80in~$T$, and ~$T$ is not necessarily closed under unions,81but it is an interesting point of view to take.)8283In order to study parity structures for~$S$, we introduce a ring whose84elements correspond naturally to subsets of~$\pow S$. Let~$R_{S}$85denote the free (commutative) boolean algebra over~$\Ftwo$ generated86by idempotents corresponding to the elements of~$S$; that is, define87$$88R_{S}89:= \frac{\Ftwo[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.90$$91(Note that this is similar to, but different from, the definition of92a Stanley-Reisner ring, in which we take~$x_{s}^{2} = 0$, rather93than~$x_{s}^{2} = x_{s}$.) Since~$R_{S}$ is spanned by idempotents94and has characteristic~$2$, it follows that all of its elements are95idempotents. Define a map~$\bij$ from~$\pow{\pow{S}}$ to~$R_{S}$ by96$$97T\bij = \sum_{b \in T} \,\prod_{s \in b} x_{s}.98$$99Under this map, each subset of~$S$ maps to the monomial that is the100product of the indeterminants corresponding to the elements of the101subset, and each subset of~$\pow S$ maps to the sum of the images102of its elements. As~$R_{S}$ is spanned by its monomials,~$\bij$ is a103bijection.104105We distinguish the element~$\sigma := 1 + \sum_{s \in S} x_{s}$106of~$R_S$; it corresponds under~$\bij$ to the collection of subsets107of~$S$ of size at most~$1$. Using~$R_{S}$ we obtain a ring-theoretic108characterization of the parity structures for~$S$.109110\begin{theorem}111\label{characterize}112Let~$S$ be a finite set.113\begin{itemize}114\item[(a)]115A subset~$T$ of~$\pow{S}$ is a parity structure for~$S$116if and only if~$T\bij$ is in the ideal~$\sigma R_S$.117\item[(b)]118The elements~$\sigma t$, with~$t$ a monomial in an even number of the119generators~$x_{s}$, form an~$\Ftwo$-basis for the ideal~$\sigma R_S$.120\end{itemize}121\end{theorem}122123\begin{proof}124Let~$S$ have size~$n$, write~$R$ for~$R_{S}$, and let~$P$ be125the set of all images under~$\bij$ of parity structures for~$S$.126If~$S$ is empty, then all subsets of~$\pow S$ are parity structures,127and~$\sigma = 1$ generates~$R$ as an ideal, so the theorem holds.128Hence we may assume that~$n$ is positive.129130We first translate the set-theoretic condition for the subset~$T$131of~$\pow S$ to be a parity structure into an algebraic condition132on~$T \bij$. For any element~$t$ of~$R$ and any subset~$b$133of~$S$, write~$t(b)$ for the value of the polynomial~$t$ with each134indeterminant~$x_{s}$ set equal to~$1$ if~$s$ is in~$b$ and set135to~$0$ otherwise. This can be thought of as the evaluation of~$t$ on136the characteristic vector of~$b$. For each subset~$b$ of~$S$ and each137element~$c$ of~$T$, the term~$c \bij$ of~$T \bij$ will vanish on~$b$138if~$c$ is not a subset of~$b$ and will give the value~$1$ otherwise.139Hence~$(T \bij)(b)$ gives the parity of the number of subsets of~$b$140that lie in~$T$. Therefore,~$T$ is a parity structure if and only if,141for every odd subset~$b$ of~$S$, the value of~$(T \bij)(b)$ is~$0$.142143Since polynomial specialization gives ring homomorphisms, for each144odd subset~$b$ of~$S$, the map~$\pi_{b}$ from~$R$ to~$\Ftwo$ given145by~$t \pi_{b} = t(b)$ is a homomorphism of rings.146And, as the previous remarks show that~$P$ is the intersection of the147kernels of these maps for all such subsets~$b$, we see that~$P$ is an148ideal of~$R$. Now order the odd subsets of~$S$ by increasing size149(with any order chosen for subsets of the same size)150as~$b_{1}, b_{2}, \ldots, b_{2^{n-1}}$.151Then the~$2^{n-1} \times 2^{n-1}$ matrix with~$(i,j)$-entry equal152to~$(b_{i} \bij) \pi_{b_{j}}$ is upper triangular with~$1$'s on the153main diagonal, so the homomorphisms~$\pi_{b}$ are linearly154independent over~$\Ftwo$. Hence~$P$ has155dimension~$2^{n} - 2^{n-1} = 2^{n-1}$ as an~$\Ftwo$-vector space.156157%%158% We first show that~$P$ is closed under addition.159% Let~$T\bij$ and~$T'\bij$ be elements of~$P$,160% where~$T$ and~$T'$ are parity structures.161% Because addition in~$R$ is computed modulo~$2$,162% the element~$T\bij + T'\bij$ is the image163% under~$\bij$ of the symmetric difference~$T \oplus T^{\prime}$.164% Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$165% of~$S$, the number of subsets of~$b$ lying in~$T$ is even,166% as is the number lying in~$T'$, so the number167% of subsets of~$b$ lying in~$T \oplus T'$ is also even.168% Hence~$T \oplus T'$ is a parity structure,169% so~$T\bij + T'\bij = (T \oplus T^{\prime})\bij$ is in~$P$.170%%171172%%173% Next we show that~$P$ is an ideal. Since the indeterminants~$x_{s}$174% generate the ring~$R$, it is enough to show that for every element~$t$175% of~$P$ and~$s$ in~$S$, the product~$t x_{s}$ is also in~$P$. Let~$T$176% and~$T^{\prime}$ be the subsets of~$\pow S$ corresponding to~$t$ and177% to~$t x_{s}$, respectively. Since~$T$ is a parity structure, we know178% that every odd subset~$b$ of~$S$ has an even number of subsets lying179% in~$T$, and we must show that the same holds for~$T^{\prime}$.180% If~$s$ is not an element of~$b$, then every element of~$T^{\prime}$181% contains~$s$ and so is not a subset of~$b$. Then~$b$ has~$0$ subsets182% lying in~$T^{\prime}$, and the result holds. Hence we may assume183% that~$s$ is an element of~$b$.184%%185186%%187% Next we verify that~$P$ contains the ideal~$I$ generated188% by~$\sigma = 1 + \sum_{s\in S} x_s$.189% Consider a monomial~$t$ in~$R$, and190% let~$U$ be the subset of~$\pow S$ that corresponds191% to~$\sigma t = t + \sum_{s \in S} x_{s} t$.192% Let~$c$ be the subset of~$S$ such that~$t$~$equals~$c\bij$.193% In the sum~$\sigma t$, if~$s$ is in~$c$, then~$x_{s} t$ equals~$t$;194% otherwise, it equals~$(c \cup \{s\})\bij$.195% Thus~$U$ consists of each subset of~$S$ obtained by adding196% another element to~$c$, together with~$c$ itself exactly197% if~$c$ is even.198% Consider an odd subset~$b$ of~$S$. If~$c$ is not a subset of~$b$, then199% an even number, namely zero, of subsets of~$b$ are elements of~$U$.200% If~$c$ is a subset of~$b$, then the number of subsets201% of~$b$ in~$U$ is~$|b| - |c|$ or~$|b| - |c| + 1$,202% as~$c$ is odd or even, respectively.203% Since~$b$ is odd, there are an even number of subsets of~$b$ in~$U$.204% It follows that~$U$ is a parity structure,205% so~$\sigma t=U\bij$ is in~$P$.206% Since~$P$ is closed under addition, and~$R$ is generated207% additively by the elements~$t$, it follows that~$I$208% is a subset of~$P$.209%%210211Next we verify that~$P$ contains the ideal~$I$ generated212by~$\sigma = 1 + \sum_{s\in S} x_s$. If~$b$ is any odd subset213of~$S$, then~$b$ has~$|b| + 1$ subsets of size~$0$ or~$1$, and~$|b| + 1$214is even. Hence the collection of subsets of~$S$ of size at most~$1$215is a parity structure, and as the image of this collection under~$\bij$216is~$\sigma$, we have~$\sigma \in P$. Since~$P$ is an ideal, it217contains~$I$ as a subset.218219%%220% Take any subset~$N$ of~$\pow S$221% containing only even subsets of~$S$; we claim that222% there is a unique parity structure for~$S$ that we can obtain by adding223% odd subsets of~$S$ to~$N$. We will examine the odd subsets of~$S$ in224% order of increasing size to see which ones must be added to~$N$ to225% obtain a parity structure~$T$. For each subset~$b$ of~$S$ of size~$1$,226% we must include~$b$ in~$T$ if and only if an odd number of the proper227% subsets of~$b$ are already in~$T$ (which at this point happens exactly228% if the empty set is in~$N$). Once we have determined which subsets of229% size~$1$ to include, we consider subsets of~$S$ of size~$3$. Again, we230% can tell exactly which ones we must include, based on which smaller sets231% are already in~$T$. Continuing in this way, we determine the232% unique parity structure~$T$ of the required type. Since~$S$233% has~$n \geq 1$ elements, there are~$2^{n-1}$ even subsets of~$S$,234% and there are~$2^{2^{n-1}}$ possibilities for the collection~$N$.235% As each of these collections can be extended to exactly one236% parity structure by adding odd sets,237% we see that there are exactly~$2^{2^{n-1}}$ parity structures for~$S$.238% Hence~$P$ has size~$2^{2^{n-1}}$.239%%240241Now we show that~$I$ and~$P$ have the same size, hence must be equal.242Let~$J$ be the ideal~$(1 + \sigma) R$.243Notice that~$\sigma$ and~$1 + \sigma$ are orthogonal idempotents244with sum~$1$, so~$R$ is the direct sum of~$I$ and~$J$ as rings.245Also, the linear map from~$R$ to itself sending~$x_{s_{0}}$246to~$1 + x_{s_{0}}$ (for some element~$s_{0}$ of~$S$) and fixing~$x_{s}$247for all other values of~$s$ is an automorphism of~$R$ (since~$R$248can be viewed as the free boolean algebra generated249by~$1 + x_{s_{0}}$ and the other indeterminants~$x_{s}$).250This automorphism interchanges~$\sigma$ and~$1 + \sigma$251and, hence, also~$I$ and~$J$, so~$I$ and~$J$ have the same dimension252as vector spaces over~$\Ftwo$. Since their sum~$R$253has dimension~$2^{n}$, the ideals~$I$ and~$J$ have dimension~$2^{n-1}$254over~$\Ftwo$. Thus~$I$ and~$P$ have the same~$\Ftwo$-dimension,255and since~$I$ is a subset of~$P$, they must be equal.256This completes the proof of part (a).257258Finally, we prove part (b).259For every even-degree monomial~$t$, the product~$\sigma t$260is the sum of~$t$ and some odd-degree monomials, so these products,261with~$t$ ranging over all even-degree monomials, are linearly262independent over~$\Ftwo$. But there are~$2^{n-1}$ such263products, and by the above calculations, the dimension of~$P$264is~$2^{n-1}$, so the products form a basis for~$P$ over~$\Ftwo$.265This completes the proof of the theorem.266\end{proof}267268This result allows us to count immediately the parity structures for269a finite set.270271\begin{corollary}272\label{count}273For~$n \geq 1$, a set of size~$n$ has~$2^{2^{n-1}}$ parity structures.274\end{corollary}275276\begin{proof}277Theorem~\ref{characterize} shows that the parity structures are in278bijection with an~$\Ftwo$-vector space of dimension~$2^{n-1}$.279\end{proof}280281\section{Another property of parity structures}282%We now prove the alternate defining property of parity structures given283%in the introduction.284Now we introduce another property of subsets of the power set of~$S$,285this time one involving odd subsets of even subsets of~$S$.286We say that a subset~$T$ of the power set of~$S$ is a287\defn{quasi-parity structure} for~$S$ if, for every even subset~$b$288of~$S$, the number of odd subsets of~$b$ that lie in~$T$ is even.289This term is justified by our next theorem.290291\begin{theorem}292\label{another}293Every parity structure for a finite set is also a quasi-parity294structure for that set.295\end{theorem}296297\begin{proof}298Suppose that~$T$ and~$T^{\prime}$ are both quasi-parity structures for299a finite set~$S$. Then for any even subset~$b$ of~$S$, the number of300odd subsets of~$b$ that lie in~$T$ is even, as is the number that lie301in~$T^{\prime}$. Thus the same holds for their symmetric difference.302And since the image under~$\bij$ of the symmetric difference of~$T$303and~$T^{\prime}$ is the sum of their images under~$\bij$, it suffices304to check the result for some collection of parity structures whose305images under~$\bij$ form an~$\Ftwo$-basis for~$R_{S}$.306Hence by the previous theorem, it is enough to show that parity307structures of the form~$(\sigma t) \bij^{-1}$, with~$t$ an even-degree308monomial (in distinct indeterminants) are quasi-parity structures.309310Such a monomial~$t$ equals~$c\bij$ for some even subset~$c$ of~$S$.311>From the definition of~$\bij$, the parity312structure~$T = (\sigma t) \bij^{-1}$ consists of~$c$ together313with all subsets of~$S$ obtained by adding one new element to~$c$.314Now take any even subset~$b$ of~$S$. If~$c$ is not a subset of~$b$,315then the number of odd subsets of~$b$ that lie in~$T$ is zero, so we316may assume that~$c$ is a subset of~$b$. Then the odd subsets of~$b$317that lie in~$T$ are exactly those subsets of~$b$ obtained by adding a318new element to~$c$. But there are~$|b| - |c|$ such subsets, and since319both~$|b|$ and~$|c|$ are even, the number of such subsets is even.320Thus~$T$ is a quasi-parity structure.321This completes the proof of the theorem.322\end{proof}323324It is worth noting that the converse of Theorem~\ref{another} is false.325Since the definition of a quasi-parity structure refers only to those326elements of~$T$ that are odd subsets of~$S$, any collection of even327subsets of~$S$ will be a quasi-parity structure. On the other hand,328the collection consisting of just the empty set will not be a parity329structure, unless~$S$ is empty. More generally, since quasi-parity330structures are closed under taking symmetric differences, the symmetric331difference of any parity structure and any collection of even subsets332of~$S$ will be a quasi-parity structure, and it can be shown that all333quasi-parity structures are of this form. Moreover, for~$n \geq 2$,334there are exactly~$2^{3 \cdot 2^{n-2}}$ quasi-parity structures for~$S$.335336\section{Refinements of results}337We now show that parity structures satisfy stronger versions both of the338defining condition339and of the condition in the definition of a quasi-parity structure.340These refinements state not merely that some collection of sets is even,341but that when the collection is partitioned in some way according to342sizes of the sets involved, every part of the partition contains an even343number of sets.344345\begin{corollary}346\label{refine}347Let~$S$ be any finite set and~$T$ be any parity structure for~$S$.348\begin{enumerate}349\item[a)]350For every odd subset~$b$ of~$S$ and every even natural number~$k$,351there are an even number of subsets of~$b$ of size~$k$ or~$k + 1$352that lie in~$T$.353\item[b)]354For every even subset~$b$ of~$S$ and every odd natural number~$k$,355there are an even number of subsets of~$b$ of size~$k$ that lie in~$T$.356\end{enumerate}357\end{corollary}358359\begin{proof}360As in the proof of Theorem~\ref{another}, it suffices to consider the361case when~$T$ is of the form~$\bij^{-1}(\sigma t)$ for some362even-degree monomial~$t$. But then parts a) and b) follow from363Theorems~\ref{characterize} and~\ref{another}, respectively,364for~$k$ equal to the degree of~$t$ or this degree plus~$1$,365and they hold trivially for all other values of~$k$.366\end{proof}367368Of course, given the fact that every quasi-parity structure is the369symmetric difference of a parity structure and a collection of even370sets, it easily follows that quasi-parity structures also satisfy the371condition in part b) of Corollary~\ref{refine}.372373\section{The ideal~$\sigma R_{S}$ and the ring~$2^{\pow S}$}374We should like to make a few remarks pointing out another way to think375about the ideal mentioned in the proof of Theorem~\ref{characterize}.376It is straightforward to see that the ring~$R = R_{S}$,377with~$S$ of size~$n$, is semisimple and is isomorphic to~$\Ftwo^{n}$378via the set of primitive (central) orthogonal379idempotents~$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \,380| \, \epsilon_{s} \in \Ftwo\}$.381Since the ideals of~$\Ftwo$ are just itself and~$(0)$, the elements382of the ideal~$\sigma R$ are just those elements of~$R$ that have support383on the coordinates corresponding to the idempotents lying in~$\sigma R$.384An idempotent~$t = \prod (x_{s} + \epsilon_{s})$ will be in the385ideal~$\sigma R$ if and only if~$t$386equals~$\sigma t = t + \sum_{s \in S} x_{s} t$. This happens exactly if387an even number of the terms in the summation equal~$t$ (while the rest388vanish), which happens if and only if an even number of the field389elements~$\epsilon_{s}$ equal~$0$. To summarize, the elements390of~$\sigma R$ are the~$\Ftwo$-linear combinations of those391idempotents~$\prod (x_{s} + \epsilon_{s})$392that have an even number of the elements~$\epsilon_{s}$ equal to~$0$,393which is the same as having the lowest-degree term be of even degree.394395We now point out a relationship between the ring~$R_{S}$396used in our proofs above and a similar boolean ring Halmos discusses397in his boolean algebra book~\cite{halmos}. For a set~$U$, he considers398the ring~$2^{U}$ of functions from~$U$ to~$\Ftwo$ with coordinatewise399addition and multiplication. Notice that the sum of the400characteristic functions of two subsets of~$U$ is the characteristic401function of their symmetric difference, while the product is the402characteristic function of their intersection. This construction can,403of course, be applied with the power set of~$S$ in place of~$U$ to404obtain the ring~$2^{\pow S}$. We can identify the elements of405each of the rings~$R_{S}$ and~$2^{\pow S}$ with406collections of subsets of~$S$, and in each ring, addition407corresponds to taking the symmetric difference of two collections.408Multiplication, however, has different interpretations in the two409rings. In~$R_{S}$, it corresponds to taking all unions of a subset410from the first collection and a subset from the second collection411(counted with appropriate multiplicities modulo~$2$), while412in~$2^{\pow S}$, it corresponds to taking the subsets that occur413in both collections. Both rings, however, are free boolean rings414of the same dimension over~$\Ftwo$, and so are isomorphic.415416As indicated above, the primitive orthogonal idempotents of417the ring~$R_{S}$ are (with our usual notation) all products of418the form~$\prod_{i=1}^{n} (x_{i} + \epsilon_{i})$ with each419term~$\epsilon_{i}$ an element of~$\Ftwo$.420A bit of calculation now shows that sending such an idempotent to421the function~$x_{i} \mapsto \epsilon_{i}$ and extending linearly422gives a natural isomorphism from~$R_{S}$ to~$2^{\pow S}$. Finally,423the element~$\sigma$ is the sum of those idempotents with an even424number of the terms~$\epsilon_{i}$ equal to~$0$, so corresponds425in~$2^{\pow S}$ to the sum of the characteristic functions of the426co-even subsets of~$S$ (those with even complement in~$S$).427428\section{A generalization of parity structures}429We now give a generalization of the notion of parity structures,430and we discuss some of our results above that can be extended to this431situation. In order to motivate our generalization, we note that a432subset~$T$ of the power set of~$S$ is a parity structure if and only433if for every subset~$b$ of~$S$, the product~$|b| \, |\pow{b} \cap T|$434is even.435436Let~$m$ be a positive integer,~$S$ be a finite set, and~$T$ be a437multiset whose elements are subsets of~$S$, each having a multiplicity438less than~$m$. We say that~$T$ is a \defn{mod-$m$ parity439multistructure} for~$S$ if, for each subset~$b$ of~$S$, the number~$m$440divides~$|b| \, |\pow{b} \cap T|$, where, in this intersection,441each subset of~$b$ is counted as many times as it occurs in~$T$.442If~$T$ actually is a set (that is, has all multiplicities at most~$1$),443then we say that it is a \defn{mod-$m$ parity structure}.444445In order to understand mod-$m$ parity multistructures, we use the ring446$$447R_{S,m}448:= \frac{{\bf Z}/m{\bf Z}[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, :449\, s \in S)}.450$$451We define a map~$\bij$ from the collection of multisets of subsets452of~$S$ to~$R_{S,m}$ just as before, by sending a subset~$a$ of~$S$453to~$\prod_{s \in a} x_{s}$ and extending linearly.454In this ring~$R_{S,m}$ we define~$\sigma$455to be~$\sum_{|a| < m} \prod_{s \in a} (-x_{s})$. Notice that both of456these definitions agree with our earlier ones in the case where~$m$457is~$2$. As in the proof of Theorem~\ref{characterize}, we can show458that the images under~$\bij$ of mod-$m$ parity multistructures form459the ideal~$\sigma R_{S,m}$. If~$S$ has size~$n$, then,460as in Corollary~\ref{count}, there will be a total461of~$m^{\sum_{i=0}^{\lfloor n/m \rfloor} {n \choose mi}}$462mod-$m$ parity multistructures. However, as we lack the automorphism463of~$R_{S}$ interchanging the ideals corresponding to~$I$ and~$J$ from464the proof of Theorem~\ref{characterize}, we do not obtain a465formula as simple as the one from that theorem.466467We can also generalize Theorem~\ref{another} and468Corollary~\ref{refine}. Again, the proofs are similar to the ones we469have for parity structures, but for the second, there is a bit of470calculation with binomial coefficients.471472\begin{theorem}473For every mod-$m$ parity multistructure~$T$ for a finite set~$S$474and every subset~$b$ of~$S$ of size divisible by~$m$, the number of475subsets of~$b$ of size relatively prime to~$m$ that lie in~$T$ is a476multiple of~$m$.477\end{theorem}478479For a collection~$T$ of subsets of a finite set~$S$ and a sequence of480natural numbers~$a_{1}, a_{2}, \ldots, a_{k}$,481write~$|T|_{a_{1}, a_{2}, \ldots, a_{k}}$ for the number of elements482of~$T$ having size equal to~$a_{i}$ for some value of~$i$.483484\begin{theorem}485Let~$T$ be a mod-$m$ parity multistructure for a finite set~$S$.486\begin{enumerate}487\item[a)]488For any subset~$b$ of~$S$ and any multiple~$k$ of~$m$, the number~$m$489divides~$|b| \, |\pow{b} \cap T|_{k, k+1, \ldots, k+m-1}$.490\item[b)]491For any subset~$b$ of~$S$ of size divisible by~$m$ and any natural492number~$k$, the number~$m$ divides~$(m,k) \, |\pow{b} \cap T|_{k}$,493where~$(m,k)$ is the greatest common divisor of~$m$ and~$k$.494\end{enumerate}495\end{theorem}496497It is harder, on the other hand, to understand mod-$m$ parity structures.498We know of two basic families: For any subset~$c$ of~$S$ of size499congruent to~$1$ modulo~$m$, the collection of subsets of~$S$ obtained500by adding~$m-1$ new elements to~$c$ forms a mod-$m$ parity structure.501And for any subset~$c$ of~$S$ of size congruent to~$2$ modulo~$m$,502the collection of subsets of~$S$ obtained by adding either~$m-2$503or~$m-1$ new elements to~$c$ forms a mod-$m$ parity structure.504Of course, any disjoint unions of collections of the above types will505also be mod-$m$ parity structures, but for~$m$ greater than~$2$,506these are the only examples we know. It would be nice to know507whether there are more, and we pose the following open problem:508509\begin{question}510How many mod-$m$ parity structures are there on a set of size~$n$?511\end{question}512513\begin{thebibliography}{9}514\bibitem{halmos}515Paul Halmos, {\sl Lectures on Boolean Algebras}, Springer-Verlag, 1970.516\end{thebibliography}517\end{document}518519520521