Sharedwww / Tables / parity.texOpen in CoCalc
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}[1]{{\mathcal P}(#1)}
12
\newcommand{\F}{\mbox{\bf F}}
13
\newcommand{\Ftwo}{\F_2}
14
\newcommand{\defn}[1]{{\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
Madison, WI 53706\\
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