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