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