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