CoCalc -- Collaborative Calculation in the Cloud
Sharedwww / Tables / parity.texOpen in CoCalc
%last modified 1999/10/12
%David, put in a current address!
\newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}}
\newcommand{\pow}[1]{{\mathcal P}(#1)}
\newcommand{\F}{\mbox{\bf F}}
\newcommand{\defn}[1]{{\em #1}}
%\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\\
William A.\ Stein\\
Department of Mathematics\\
University of California\\
Berkeley, CA 94720}


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.

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
:= \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 

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$.  

Let~$S$ be a finite set.  
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$.  
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$.  

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.  

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

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

Theorem~\ref{characterize} shows that the parity structures are in 
bijection with an~$\Ftwo$-vector space of dimension~$2^{n-1}$.  

\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.  

Every parity structure for a finite set is also a quasi-parity 
structure for that set.  

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.  

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.
Let~$S$ be any finite set and~$T$ be any parity structure for~$S$.  
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$.  
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$.  

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$.  

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 
:= \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.  

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}, \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$.  

Let~$T$ be a mod-$m$ parity multistructure for a finite set~$S$.  
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}$.  
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$.  

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:  

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

Paul Halmos, {\sl Lectures on Boolean Algebras}, Springer-Verlag, 1970.