Author: William A. Stein
1%last modified 1999/10/12
2%David, put in a current address!
3\documentstyle[11pt]{article}
4%\documentclass[12pt]{article}
5%\usepackage{amssymb}
6\newtheorem{lemma}{Lemma}
7\newtheorem{theorem}{Theorem}
8\newtheorem{corollary}{Corollary}
9\newtheorem{question}{Question}
10\newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}}
11\newcommand{\pow}{{\mathcal P}(#1)}
12\newcommand{\F}{\mbox{\bf F}}
13\newcommand{\Ftwo}{\F_2}
14\newcommand{\defn}{{\em #1}}
15\newcommand{\bij}{\varphi}
16%\title{Classification of parity structures on finite sets}
17\title{Parity structures and generating functions from Boolean rings}
18\author{David Petrie Moulton\footnote{This work was
19done while the first author was a Research Fellow
20at the University of California at Berkeley.}\\
21Department of Mathematics\\
22University of Wisconsin\\
24\and
25William A.\ Stein\\
26Department of Mathematics\\
27University of California\\
28Berkeley, CA 94720}
29\date{\today}
30
31\begin{document}
32\maketitle
33
34\begin{abstract}
35Let~$S$ be a finite set and~$T$ be a subset of the power set of~$S$.
36Call~$T$ a \defn{parity structure} for~$S$ if, for
37each subset~$b$ of~$S$ of odd size, the number of subsets of~$b$
38that lie in~$T$ is even.  We classify parity structures using generating
39functions from a free boolean ring.
40We also show that if~$T$ is a parity structure, then, for each
41subset~$b$ of~$S$ of even size, the number of subsets of~$b$ of
42odd size that lie in~$T$ is even.  We then give several other
43properties of parity structures and discuss a generalization.
44%Furthermore, we obtain refinements of the
45%defining property and this resultant property by
46%restricting to subsets of the~$b$'s of particular sizes.
47\end{abstract}
48
49\section{Introduction}
50We were led to consider parity structures while searching for
51a new class of simplicial complexes.  We classified parity
52structures, but our original proof was based on a
53technical induction using binomial coefficients.
54Later we found a more conceptual proof that uses
55generating functions obtained from a free boolean algebra
56over the field~$\Ftwo$ of order~$2$.  In Section~2 we describe
57how to view parity structures as elements of this boolean algebra,
58and we use this identification to classify parity
59structures.  We should point out that our classification can be
60formulated and proved without this boolean ring with a comparable
61amount of work, but we find our method more interesting and more
62instructive.  In Section~3 we use the classification to find another
63property of parity structures.  We then prove in Section~4
64that parity structures satisfy stronger versions of both the defining
65property and this new one.  Finally, in Sections~5 and 6 we discuss
66some related issues involving an ideal~$\sigma R_{S}$ we define below,
67and we give a generalization of parity structures.
68
69\section{Free boolean algebras and generating functions}
70Call a finite set \defn{even} or \defn{odd} according to the parity
71of its size.  Let~$S$ be a finite set, and let~$T$ be any subset
72of~$\pow S$, the power set of~$S$.
73We say that~$T$ is a \defn{parity structure} for~$S$ if, for each
74odd subset~$b$ of~$S$, the intersection~$\pow b \cap T$ is even;
75that is, if each odd subset~$b$ has an even number of subsets
76that lie in~$T$.  A logician might imagine that~$T$ consists of
77the subsets of~$S$ that are in some model, so that~$\pow b \cap T$ is
78the power set of~$b$ within the model.  We are simply requiring then
79that, in this model, every odd set have an even number of subsets.
80(This analogy is not perfect, of course, since~$b$ need not be
81in~$T$, and ~$T$ is not necessarily closed under unions,
82but it is an interesting point of view to take.)
83
84In order to study parity structures for~$S$, we introduce a ring whose
85elements correspond naturally to subsets of~$\pow S$.  Let~$R_{S}$
86denote the free (commutative) boolean algebra over~$\Ftwo$ generated
87by idempotents corresponding to the elements of~$S$; that is, define
88$$89R_{S} 90:= \frac{\Ftwo[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}. 91$$
92(Note that this is similar to, but different from, the definition of
93a Stanley-Reisner ring, in which we take~$x_{s}^{2} = 0$, rather
94than~$x_{s}^{2} = x_{s}$.)  Since~$R_{S}$ is spanned by idempotents
95and has characteristic~$2$, it follows that all of its elements are
96idempotents.  Define a map~$\bij$ from~$\pow{\pow{S}}$ to~$R_{S}$ by
97$$98T\bij = \sum_{b \in T} \,\prod_{s \in b} x_{s}. 99$$
100Under this map, each subset of~$S$ maps to the monomial that is the
101product of the indeterminants corresponding to the elements of the
102subset, and each subset of~$\pow S$ maps to the sum of the images
103of its elements.  As~$R_{S}$ is spanned by its monomials,~$\bij$ is a
104bijection.
105
106We distinguish the element~$\sigma := 1 + \sum_{s \in S} x_{s}$
107of~$R_S$; it corresponds under~$\bij$ to the collection of subsets
108of~$S$ of size at most~$1$.  Using~$R_{S}$ we obtain a ring-theoretic
109characterization of the parity structures for~$S$.
110
111\begin{theorem}
112\label{characterize}
113Let~$S$ be a finite set.
114\begin{itemize}
115\item[(a)]
116A subset~$T$ of~$\pow{S}$ is a parity structure for~$S$
117if and only if~$T\bij$ is in the ideal~$\sigma R_S$.
118\item[(b)]
119The elements~$\sigma t$, with~$t$ a monomial in an even number of the
120generators~$x_{s}$, form an~$\Ftwo$-basis for the ideal~$\sigma R_S$.
121\end{itemize}
122\end{theorem}
123
124\begin{proof}
125Let~$S$ have size~$n$, write~$R$ for~$R_{S}$, and let~$P$ be
126the set of all images under~$\bij$ of parity structures for~$S$.
127If~$S$ is empty, then all subsets of~$\pow S$ are parity structures,
128and~$\sigma = 1$ generates~$R$ as an ideal, so the theorem holds.
129Hence we may assume that~$n$ is positive.
130
131We first translate the set-theoretic condition for the subset~$T$
132of~$\pow S$ to be a parity structure into an algebraic condition
133on~$T \bij$.  For any element~$t$ of~$R$ and any subset~$b$
134of~$S$, write~$t(b)$ for the value of the polynomial~$t$ with each
135indeterminant~$x_{s}$ set equal to~$1$ if~$s$ is in~$b$ and set
136to~$0$ otherwise.  This can be thought of as the evaluation of~$t$ on
137the characteristic vector of~$b$.  For each subset~$b$ of~$S$ and each
138element~$c$ of~$T$, the term~$c \bij$ of~$T \bij$ will vanish on~$b$
139if~$c$ is not a subset of~$b$ and will give the value~$1$ otherwise.
140Hence~$(T \bij)(b)$ gives the parity of the number of subsets of~$b$
141that lie in~$T$.  Therefore,~$T$ is a parity structure if and only if,
142for every odd subset~$b$ of~$S$, the value of~$(T \bij)(b)$ is~$0$.
143
144Since polynomial specialization gives ring homomorphisms, for each
145odd subset~$b$ of~$S$, the map~$\pi_{b}$ from~$R$ to~$\Ftwo$ given
146by~$t \pi_{b} = t(b)$ is a homomorphism of rings.
147And, as the previous remarks show that~$P$ is the intersection of the
148kernels of these maps for all such subsets~$b$, we see that~$P$ is an
149ideal of~$R$.  Now order the odd subsets of~$S$ by increasing size
150(with any order chosen for subsets of the same size)
151as~$b_{1}, b_{2}, \ldots, b_{2^{n-1}}$.
152Then the~$2^{n-1} \times 2^{n-1}$ matrix with~$(i,j)$-entry equal
153to~$(b_{i} \bij) \pi_{b_{j}}$ is upper triangular with~$1$'s on the
154main diagonal, so the homomorphisms~$\pi_{b}$ are linearly
155independent over~$\Ftwo$.  Hence~$P$ has
156dimension~$2^{n} - 2^{n-1} = 2^{n-1}$ as an~$\Ftwo$-vector space.
157
158%%
159 % We first show that~$P$ is closed under addition.
160 % Let~$T\bij$ and~$T'\bij$ be elements of~$P$,
161 % where~$T$ and~$T'$ are parity structures.
162 % Because addition in~$R$ is computed modulo~$2$,
163 % the element~$T\bij + T'\bij$ is the image
164 % under~$\bij$ of the symmetric difference~$T \oplus T^{\prime}$.
165 % Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$
166 % of~$S$, the number of subsets of~$b$ lying in~$T$ is even,
167 % as is the number lying in~$T'$, so the number
168 % of subsets of~$b$ lying in~$T \oplus T'$ is also even.
169 % Hence~$T \oplus T'$ is a parity structure,
170 % so~$T\bij + T'\bij = (T \oplus T^{\prime})\bij$ is in~$P$.
171 %%
172
173%%
174 % Next we show that~$P$ is an ideal.  Since the indeterminants~$x_{s}$
175 % generate the ring~$R$, it is enough to show that for every element~$t$
176 % of~$P$ and~$s$ in~$S$, the product~$t x_{s}$ is also in~$P$.  Let~$T$
177 % and~$T^{\prime}$ be the subsets of~$\pow S$ corresponding to~$t$ and
178 % to~$t x_{s}$, respectively.  Since~$T$ is a parity structure, we know
179 % that every odd subset~$b$ of~$S$ has an even number of subsets lying
180 % in~$T$, and we must show that the same holds for~$T^{\prime}$.
181 % If~$s$ is not an element of~$b$, then every element of~$T^{\prime}$
182 % contains~$s$ and so is not a subset of~$b$.  Then~$b$ has~$0$ subsets
183 % lying in~$T^{\prime}$, and the result holds.  Hence we may assume
184 % that~$s$ is an element of~$b$.
185 %%
186
187%%
188 % Next we verify that~$P$ contains the ideal~$I$ generated
189 % by~$\sigma = 1 + \sum_{s\in S} x_s$.
190 % Consider a monomial~$t$ in~$R$, and
191 % let~$U$ be the subset of~$\pow S$ that corresponds
192 % to~$\sigma t = t + \sum_{s \in S} x_{s} t$.
193 % Let~$c$ be the subset of~$S$ such that~$t$~$equals~$c\bij$. 194 % In the sum~$\sigma t$, if~$s$is in~$c$, then~$x_{s} t$equals~$t$; 195 % otherwise, it equals~$(c \cup \{s\})\bij$. 196 % Thus~$U$consists of each subset of~$S$obtained by adding 197 % another element to~$c$, together with~$c$itself exactly 198 % if~$c$is even. 199 % Consider an odd subset~$b$of~$S$. If~$c$is not a subset of~$b$, then 200 % an even number, namely zero, of subsets of~$b$are elements of~$U$. 201 % If~$c$is a subset of~$b$, then the number of subsets 202 % of~$b$in~$U$is~$|b| - |c|$or~$|b| - |c| + 1$, 203 % as~$c$is odd or even, respectively. 204 % Since~$b$is odd, there are an even number of subsets of~$b$in~$U$. 205 % It follows that~$U$is a parity structure, 206 % so~$\sigma t=U\bij$is in~$P$. 207 % Since~$P$is closed under addition, and~$R$is generated 208 % additively by the elements~$t$, it follows that~$I$209 % is a subset of~$P$. 210 %% 211 212Next we verify that~$P$contains the ideal~$I$generated 213by~$\sigma = 1 + \sum_{s\in S} x_s$. If~$b$is any odd subset 214of~$S$, then~$b$has~$|b| + 1$subsets of size~$0$or~$1$, and~$|b| + 1$215is even. Hence the collection of subsets of~$S$of size at most~$1$216is a parity structure, and as the image of this collection under~$\bij$217is~$\sigma$, we have~$\sigma \in P$. Since~$P$is an ideal, it 218contains~$I$as a subset. 219 220%% 221 % Take any subset~$N$of~$\pow S$222 % containing only even subsets of~$S$; we claim that 223 % there is a unique parity structure for~$S$that we can obtain by adding 224 % odd subsets of~$S$to~$N$. We will examine the odd subsets of~$S$in 225 % order of increasing size to see which ones must be added to~$N$to 226 % obtain a parity structure~$T$. For each subset~$b$of~$S$of size~$1$, 227 % we must include~$b$in~$T$if and only if an odd number of the proper 228 % subsets of~$b$are already in~$T$(which at this point happens exactly 229 % if the empty set is in~$N$). Once we have determined which subsets of 230 % size~$1$to include, we consider subsets of~$S$of size~$3$. Again, we 231 % can tell exactly which ones we must include, based on which smaller sets 232 % are already in~$T$. Continuing in this way, we determine the 233 % unique parity structure~$T$of the required type. Since~$S$234 % has~$n \geq 1$elements, there are~$2^{n-1}$even subsets of~$S$, 235 % and there are~$2^{2^{n-1}}$possibilities for the collection~$N$. 236 % As each of these collections can be extended to exactly one 237 % parity structure by adding odd sets, 238 % we see that there are exactly~$2^{2^{n-1}}$parity structures for~$S$. 239 % Hence~$P$has size~$2^{2^{n-1}}$. 240 %% 241 242Now we show that~$I$and~$P$have the same size, hence must be equal. 243Let~$J$be the ideal~$(1 + \sigma) R$. 244Notice that~$\sigma$and~$1 + \sigma$are orthogonal idempotents 245with sum~$1$, so~$R$is the direct sum of~$I$and~$J$as rings. 246Also, the linear map from~$R$to itself sending~$x_{s_{0}}$247to~$1 + x_{s_{0}}$(for some element~$s_{0}$of~$S$) and fixing~$x_{s}$248for all other values of~$s$is an automorphism of~$R$(since~$R$249can be viewed as the free boolean algebra generated 250by~$1 + x_{s_{0}}$and the other indeterminants~$x_{s}$). 251This automorphism interchanges~$\sigma$and~$1 + \sigma$252and, hence, also~$I$and~$J$, so~$I$and~$J$have the same dimension 253as vector spaces over~$\Ftwo$. Since their sum~$R$254has dimension~$2^{n}$, the ideals~$I$and~$J$have dimension~$2^{n-1}$255over~$\Ftwo$. Thus~$I$and~$P$have the same~$\Ftwo$-dimension, 256and since~$I$is a subset of~$P$, they must be equal. 257This completes the proof of part (a). 258 259Finally, we prove part (b). 260For every even-degree monomial~$t$, the product~$\sigma t$261is the sum of~$t$and some odd-degree monomials, so these products, 262with~$t$ranging over all even-degree monomials, are linearly 263independent over~$\Ftwo$. But there are~$2^{n-1}$such 264products, and by the above calculations, the dimension of~$P$265is~$2^{n-1}$, so the products form a basis for~$P$over~$\Ftwo$. 266This completes the proof of the theorem. 267\end{proof} 268 269This result allows us to count immediately the parity structures for 270a finite set. 271 272\begin{corollary} 273\label{count} 274For~$n \geq 1$, a set of size~$n$has~$2^{2^{n-1}}$parity structures. 275\end{corollary} 276 277\begin{proof} 278Theorem~\ref{characterize} shows that the parity structures are in 279bijection with an~$\Ftwo$-vector space of dimension~$2^{n-1}$. 280\end{proof} 281 282\section{Another property of parity structures} 283%We now prove the alternate defining property of parity structures given 284%in the introduction. 285Now we introduce another property of subsets of the power set of~$S$, 286this time one involving odd subsets of even subsets of~$S$. 287We say that a subset~$T$of the power set of~$S$is a 288\defn{quasi-parity structure} for~$S$if, for every even subset~$b$289of~$S$, the number of odd subsets of~$b$that lie in~$T$is even. 290This term is justified by our next theorem. 291 292\begin{theorem} 293\label{another} 294Every parity structure for a finite set is also a quasi-parity 295structure for that set. 296\end{theorem} 297 298\begin{proof} 299Suppose that~$T$and~$T^{\prime}$are both quasi-parity structures for 300a finite set~$S$. Then for any even subset~$b$of~$S$, the number of 301odd subsets of~$b$that lie in~$T$is even, as is the number that lie 302in~$T^{\prime}$. Thus the same holds for their symmetric difference. 303And since the image under~$\bij$of the symmetric difference of~$T$304and~$T^{\prime}$is the sum of their images under~$\bij$, it suffices 305to check the result for some collection of parity structures whose 306images under~$\bij$form an~$\Ftwo$-basis for~$R_{S}$. 307Hence by the previous theorem, it is enough to show that parity 308structures of the form~$(\sigma t) \bij^{-1}$, with~$t$an even-degree 309monomial (in distinct indeterminants) are quasi-parity structures. 310 311Such a monomial~$t$equals~$c\bij$for some even subset~$c$of~$S$. 312>From the definition of~$\bij$, the parity 313structure~$T = (\sigma t) \bij^{-1}$consists of~$c$together 314with all subsets of~$S$obtained by adding one new element to~$c$. 315Now take any even subset~$b$of~$S$. If~$c$is not a subset of~$b$, 316then the number of odd subsets of~$b$that lie in~$T$is zero, so we 317may assume that~$c$is a subset of~$b$. Then the odd subsets of~$b$318that lie in~$T$are exactly those subsets of~$b$obtained by adding a 319new element to~$c$. But there are~$|b| - |c|$such subsets, and since 320both~$|b|$and~$|c|$are even, the number of such subsets is even. 321Thus~$T$is a quasi-parity structure. 322This completes the proof of the theorem. 323\end{proof} 324 325It is worth noting that the converse of Theorem~\ref{another} is false. 326Since the definition of a quasi-parity structure refers only to those 327elements of~$T$that are odd subsets of~$S$, any collection of even 328subsets of~$S$will be a quasi-parity structure. On the other hand, 329the collection consisting of just the empty set will not be a parity 330structure, unless~$S$is empty. More generally, since quasi-parity 331structures are closed under taking symmetric differences, the symmetric 332difference of any parity structure and any collection of even subsets 333of~$S$will be a quasi-parity structure, and it can be shown that all 334quasi-parity structures are of this form. Moreover, for~$n \geq 2$, 335there are exactly~$2^{3 \cdot 2^{n-2}}$quasi-parity structures for~$S$. 336 337\section{Refinements of results} 338We now show that parity structures satisfy stronger versions both of the 339defining condition 340and of the condition in the definition of a quasi-parity structure. 341These refinements state not merely that some collection of sets is even, 342but that when the collection is partitioned in some way according to 343sizes of the sets involved, every part of the partition contains an even 344number of sets. 345 346\begin{corollary} 347\label{refine} 348Let~$S$be any finite set and~$T$be any parity structure for~$S$. 349\begin{enumerate} 350\item[a)] 351For every odd subset~$b$of~$S$and every even natural number~$k$, 352there are an even number of subsets of~$b$of size~$k$or~$k + 1$353that lie in~$T$. 354\item[b)] 355For every even subset~$b$of~$S$and every odd natural number~$k$, 356there are an even number of subsets of~$b$of size~$k$that lie in~$T$. 357\end{enumerate} 358\end{corollary} 359 360\begin{proof} 361As in the proof of Theorem~\ref{another}, it suffices to consider the 362case when~$T$is of the form~$\bij^{-1}(\sigma t)$for some 363even-degree monomial~$t$. But then parts a) and b) follow from 364Theorems~\ref{characterize} and~\ref{another}, respectively, 365for~$k$equal to the degree of~$t$or this degree plus~$1$, 366and they hold trivially for all other values of~$k$. 367\end{proof} 368 369Of course, given the fact that every quasi-parity structure is the 370symmetric difference of a parity structure and a collection of even 371sets, it easily follows that quasi-parity structures also satisfy the 372condition in part b) of Corollary~\ref{refine}. 373 374\section{The ideal~$\sigma R_{S}$and the ring~$2^{\pow S}$} 375We should like to make a few remarks pointing out another way to think 376about the ideal mentioned in the proof of Theorem~\ref{characterize}. 377It is straightforward to see that the ring~$R = R_{S}$, 378with~$S$of size~$n$, is semisimple and is isomorphic to~$\Ftwo^{n}$379via the set of primitive (central) orthogonal 380idempotents~$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \,
381| \, \epsilon_{s} \in \Ftwo\}$. 382Since the ideals of~$\Ftwo$are just itself and~$(0)$, the elements 383of the ideal~$\sigma R$are just those elements of~$R$that have support 384on the coordinates corresponding to the idempotents lying in~$\sigma R$. 385An idempotent~$t = \prod (x_{s} + \epsilon_{s})$will be in the 386ideal~$\sigma R$if and only if~$t$387equals~$\sigma t = t + \sum_{s \in S} x_{s} t$. This happens exactly if 388an even number of the terms in the summation equal~$t$(while the rest 389vanish), which happens if and only if an even number of the field 390elements~$\epsilon_{s}$equal~$0$. To summarize, the elements 391of~$\sigma R$are the~$\Ftwo$-linear combinations of those 392idempotents~$\prod (x_{s} + \epsilon_{s})$393that have an even number of the elements~$\epsilon_{s}$equal to~$0$, 394which is the same as having the lowest-degree term be of even degree. 395 396We now point out a relationship between the ring~$R_{S}$397used in our proofs above and a similar boolean ring Halmos discusses 398in his boolean algebra book~\cite{halmos}. For a set~$U$, he considers 399the ring~$2^{U}$of functions from~$U$to~$\Ftwo$with coordinatewise 400addition and multiplication. Notice that the sum of the 401characteristic functions of two subsets of~$U$is the characteristic 402function of their symmetric difference, while the product is the 403characteristic function of their intersection. This construction can, 404of course, be applied with the power set of~$S$in place of~$U$to 405obtain the ring~$2^{\pow S}$. We can identify the elements of 406each of the rings~$R_{S}$and~$2^{\pow S}$with 407collections of subsets of~$S$, and in each ring, addition 408corresponds to taking the symmetric difference of two collections. 409Multiplication, however, has different interpretations in the two 410rings. In~$R_{S}$, it corresponds to taking all unions of a subset 411from the first collection and a subset from the second collection 412(counted with appropriate multiplicities modulo~$2$), while 413in~$2^{\pow S}$, it corresponds to taking the subsets that occur 414in both collections. Both rings, however, are free boolean rings 415of the same dimension over~$\Ftwo$, and so are isomorphic. 416 417As indicated above, the primitive orthogonal idempotents of 418the ring~$R_{S}$are (with our usual notation) all products of 419the form~$\prod_{i=1}^{n} (x_{i} + \epsilon_{i})$with each 420term~$\epsilon_{i}$an element of~$\Ftwo$. 421A bit of calculation now shows that sending such an idempotent to 422the function~$x_{i} \mapsto \epsilon_{i}$and extending linearly 423gives a natural isomorphism from~$R_{S}$to~$2^{\pow S}$. Finally, 424the element~$\sigma$is the sum of those idempotents with an even 425number of the terms~$\epsilon_{i}$equal to~$0$, so corresponds 426in~$2^{\pow S}$to the sum of the characteristic functions of the 427co-even subsets of~$S$(those with even complement in~$S$). 428 429\section{A generalization of parity structures} 430We now give a generalization of the notion of parity structures, 431and we discuss some of our results above that can be extended to this 432situation. In order to motivate our generalization, we note that a 433subset~$T$of the power set of~$S$is a parity structure if and only 434if for every subset~$b$of~$S$, the product~$|b| \, |\pow{b} \cap T|$435is even. 436 437Let~$m$be a positive integer,~$S$be a finite set, and~$T$be a 438multiset whose elements are subsets of~$S$, each having a multiplicity 439less than~$m$. We say that~$T$is a \defn{mod-$m$parity 440multistructure} for~$S$if, for each subset~$b$of~$S$, the number~$m$441divides~$|b| \, |\pow{b} \cap T|$, where, in this intersection, 442each subset of~$b$is counted as many times as it occurs in~$T$. 443If~$T$actually is a set (that is, has all multiplicities at most~$1$), 444then we say that it is a \defn{mod-$m$parity structure}. 445 446In order to understand mod-$m$parity multistructures, we use the ring 447$$448R_{S,m} 449:= \frac{{\bf Z}/m{\bf Z}[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : 450\, s \in S)}. 451$$ 452We define a map~$\bij$from the collection of multisets of subsets 453of~$S$to~$R_{S,m}$just as before, by sending a subset~$a$of~$S$454to~$\prod_{s \in a} x_{s}$and extending linearly. 455In this ring~$R_{S,m}$we define~$\sigma$456to be~$\sum_{|a| < m} \prod_{s \in a} (-x_{s})$. Notice that both of 457these definitions agree with our earlier ones in the case where~$m$458is~$2$. As in the proof of Theorem~\ref{characterize}, we can show 459that the images under~$\bij$of mod-$m$parity multistructures form 460the ideal~$\sigma R_{S,m}$. If~$S$has size~$n$, then, 461as in Corollary~\ref{count}, there will be a total 462of~$m^{\sum_{i=0}^{\lfloor n/m \rfloor} {n \choose mi}}$463mod-$m$parity multistructures. However, as we lack the automorphism 464of~$R_{S}$interchanging the ideals corresponding to~$I$and~$J$from 465the proof of Theorem~\ref{characterize}, we do not obtain a 466formula as simple as the one from that theorem. 467 468We can also generalize Theorem~\ref{another} and 469Corollary~\ref{refine}. Again, the proofs are similar to the ones we 470have for parity structures, but for the second, there is a bit of 471calculation with binomial coefficients. 472 473\begin{theorem} 474For every mod-$m$parity multistructure~$T$for a finite set~$S$475and every subset~$b$of~$S$of size divisible by~$m$, the number of 476subsets of~$b$of size relatively prime to~$m$that lie in~$T$is a 477multiple of~$m$. 478\end{theorem} 479 480For a collection~$T$of subsets of a finite set~$S$and a sequence of 481natural numbers~$a_{1}, a_{2}, \ldots, a_{k}$, 482write~$|T|_{a_{1}, a_{2}, \ldots, a_{k}}$for the number of elements 483of~$T$having size equal to~$a_{i}$for some value of~$i$. 484 485\begin{theorem} 486Let~$T$be a mod-$m$parity multistructure for a finite set~$S$. 487\begin{enumerate} 488\item[a)] 489For any subset~$b$of~$S$and any multiple~$k$of~$m$, the number~$m$490divides~$|b| \, |\pow{b} \cap T|_{k, k+1, \ldots, k+m-1}$. 491\item[b)] 492For any subset~$b$of~$S$of size divisible by~$m$and any natural 493number~$k$, the number~$m$divides~$(m,k) \, |\pow{b} \cap T|_{k}$, 494where~$(m,k)$is the greatest common divisor of~$m$and~$k$. 495\end{enumerate} 496\end{theorem} 497 498It is harder, on the other hand, to understand mod-$m$parity structures. 499We know of two basic families: For any subset~$c$of~$S$of size 500congruent to~$1$modulo~$m$, the collection of subsets of~$S$obtained 501by adding~$m-1$new elements to~$c$forms a mod-$m$parity structure. 502And for any subset~$c$of~$S$of size congruent to~$2$modulo~$m$, 503the collection of subsets of~$S$obtained by adding either~$m-2$504or~$m-1$new elements to~$c$forms a mod-$m$parity structure. 505Of course, any disjoint unions of collections of the above types will 506also be mod-$m$parity structures, but for~$m$greater than~$2$, 507these are the only examples we know. It would be nice to know 508whether there are more, and we pose the following open problem: 509 510\begin{question} 511How many mod-$m$parity structures are there on a set of size~$n\$?
512\end{question}
513
514\begin{thebibliography}{9}
515\bibitem{halmos}
516Paul Halmos, {\sl Lectures on Boolean Algebras}, Springer-Verlag, 1970.
517\end{thebibliography}
518\end{document}
519
520
521