CoCalc Public Fileswww / papers / parity / old / parity.texOpen in with one click!
Author: William A. Stein
1
%What do you think? Any comments? And where should it go? I was
2
%thinking perhaps _Discrete_Math_.
3
%---------------------
4
%last modified 1999/9/18 -was
5
\documentclass[11pt]{article}
6
\usepackage{amssymb}
7
\newtheorem{lemma}{Lemma}
8
\newtheorem{theorem}{Theorem}
9
\newtheorem{corollary}{Corollary}
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}{\mathbf{F}_2}
14
\newcommand{\defn}[1]{{\em #1}}
15
\newcommand{\bij}{\varphi}
16
\title{Classification of parity structures on finite sets}
17
\author{David Petrie Moulton\\
18
Department of Mathematics\\
19
University of Wisconsin\\
20
Madison, WI 53706\\
21
\and
22
William A.\ Stein\\
23
Department of Mathematics\\
24
University of California\\
25
Berkeley, CA 94720}
26
\date{\today}
27
28
\begin{document}
29
\maketitle
30
31
\begin{abstract}
32
Let~$S$ be a finite set, and consider a subset~$T$ of the power set of~$S$.
33
We say that~$T$ is a \defn{parity structure} for~$S$ if, for
34
each subset~$b$ of~$S$ of odd cardinality, the number of subsets of~$b$
35
that lie in~$T$ is even. We classify parity structures using generating
36
functions from a free boolean ring.
37
We also show that~$T$ is a parity structure if and only if, for each
38
subset~$b$ of~$S$ of even size, the number of subsets of~$b$ of odd size
39
that lie in~$T$ is even.
40
%Furthermore, we obtain refinements of the
41
%defining property and this resultant property by
42
%restricting to subsets of the~$b$'s of particular sizes.
43
\end{abstract}
44
45
\section{Introduction}
46
We were led to consider parity structures while searching for
47
new classes of simplicial complexes. We classified parity
48
structures; however, the first proof is based on a
49
technical induction using binomial coefficients.
50
Later we found a more conceptual proof that uses
51
generating functions obtained from a free boolean algebra
52
over the finite field~$\Ftwo$ of order~$2$.
53
The conceptual proof and classification also yields
54
additional properties of parity structures.
55
56
\section{Free boolean algebras and generating functions}
57
Call a finite set \defn{even} or \defn{odd}
58
according to the parity of its cardinality.
59
Let~$S$ be a finite set, and let~$T$ be any subset of the
60
power set~$\pow S$ of~$S$.
61
We say that~$T$ is a \defn{parity structure} for~$S$ if, for each
62
odd subset~$b$ of~$S$, the intersection $T \cap \pow b$ is even.
63
Thus each odd subset~$b$ has an even number of subsets
64
that lie in~$T$.
65
66
In order to study parity structures for~$S$, we introduce a
67
ring whose elements correspond naturally to elements of $\pow{\pow S}$.
68
Let~$R_{S}$ denote the free commutative boolean algebra over~$\Ftwo$
69
generated by idempotents corresponding to the elements of~$S$;
70
equivalently,
71
$$
72
R_{S} := \frac{\Ftwo[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.
73
$$
74
Because~$\Ftwo$ has characteristic~$2$, every element
75
of the right hand side is idempotent.
76
Associate to any subset of~$S$ the monomial that is the product of
77
the variables corresponding to the elements of the subset.
78
A sum of monomials represents a collection of subsets
79
of~$S$. This defines a bijection~$\bij$ from
80
$\pow{\pow{S}}$ to $R_{S}$ defined by
81
$$
82
\bij : T \mapsto \sum_{b \in T} \,\prod_{s \in b} x_{s}.
83
$$
84
Under this bijection, each subset of~$S$ maps to a monomial,
85
and each subset of~$\pow S$ maps to the sum of the images
86
of its elements, as indicated above.
87
88
We distinguish the element
89
$\sigma := 1 + \sum_{s \in S} x_{s}$ of~$R_S$;
90
it corresponds under~$\bij$ to
91
the collection of subsets of~$S$ of cardinality at most~$1$.
92
Using~$R_{S}$ we obtain a ring-theoretic characterization of
93
the parity structures.
94
\begin{theorem}
95
Let~$S$ be a finite set, and let~$T$ be a subset of~$\pow{S}$.
96
Then~$T$ is a parity structure for~$S$ if and only if~$\bij(T)$
97
is in the ideal generated by~$\sigma$. The
98
elements~$t \sigma$, with~$t$ a monomial in an even number
99
of the generators~$x_{s}$, form a basis
100
for this ideal as a vector space over~$\Ftwo$.
101
\end{theorem}
102
\begin{proof}
103
If $S$ is empty, then all subsets of $\pow S$ are parity structures,
104
and $\sigma = 1$ generates $R_{S}$ as an ideal, so the theorem holds.
105
Hence we may assume that $S$ has positive size~$n$.
106
Let~$P$ be the set of all images under $\bij$ of parity structures
107
for~$S$.
108
109
We first show that~$P$ is closed under addition.
110
Let $\bij(T)$ and $\bij(T')$ be elements of~$P$,
111
where~$T$ and~$T'$ are parity structures.
112
Because addition in $R_{S}$ is computed modulo~$2$,
113
the element $\bij(T) + \bij(T')$ is the image
114
under~$\bij$ of the symmetric difference $T \oplus T^{\prime}$.
115
Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$
116
of~$S$, the number of subsets of~$b$ lying in~$T$ is even,
117
as is the number lying in $T'$, so the number
118
of subsets of~$b$ lying in $T \oplus T'$ is also even.
119
Hence $T \oplus T'$ is a parity structure, so
120
$\bij(T) + \bij(T') = \bij(T \oplus T^{\prime})$ is in~$P$.
121
122
Next we verify that $P$ contains the ideal~$I$ generated by
123
$\sigma = 1 + \sum_{s\in S} x_s$.
124
Consider a monomial~$t$ in~$R_{S}$, and
125
let~$U$ be the subset of $\pow S$ that corresponds
126
to $\sigma t = t + \sum_{s \in S} x_{s} t$.
127
Let $c$ be the subset of~$S$ such that $t=\bij(c)$. In the sum
128
$\sigma t$, if $s\in c$, then~$x_{s} t$ equals~$t$;
129
otherwise, it equals $\bij(c \cup \{s\})$.
130
Thus~$U$ consists of each subset of~$S$ obtained by adding
131
another element to~$c$, together with~$c$ itself exactly
132
if~$c$ is even.
133
Consider an odd subset $b\subset S$. If $c\not\subset b$, then
134
an even number, namely zero, of subsets of~$b$ are elements of~$U$.
135
If $c\subset b$, then the number of subsets
136
of~$b$ in~$U$ is $|b| - |c|$ or $|b| - |c| + 1$,
137
as~$c$ is odd or even, respectively.
138
Since~$b$ is odd, there are an even number of subsets of~$b$ in~$U$.
139
It follows that~$U$ is a parity structure,
140
so $\sigma t = \bij(U)\in P$.
141
Since~$P$ is closed under addition, and $R_{S}$ is generated
142
additively by the elements~$t$, it follows that~$I$
143
is a subset of~$P$.
144
145
The next step is to verify that~$I$ and~$P$
146
have the same size, hence must be equal.
147
Take any subset $N$ of $\pow S$
148
containing only even subsets of $S$; we claim that
149
there is a unique parity structure for $S$ that we can obtain by adding
150
odd subsets of $S$ to $N$. We will examine the odd subsets of $S$ in
151
order of increasing size to see which ones must be added to $N$ to
152
obtain a parity structure $T$. For each subset $b$ of $S$ of size $1$,
153
we must include $b$ in $T$ if and only if an odd number of the proper
154
subsets of $b$ are already in $T$ (which at this point happens exactly
155
if the empty set is in $N$). Once we have determined which subsets of
156
size $1$ to include, we consider subsets of $S$ of size $3$. Again, we
157
can tell exactly which ones we must include, based on which smaller sets
158
are already in $T$. Continuing in this way, we determine the
159
unique parity structure $T$ of the required type. Since $S$ has
160
$n \geq 1$ elements, there are $2^{n-1}$ even subsets of $S$,
161
and there are $2^{2^{n-1}}$ possibilities for the collection $N$.
162
As each of these collections can be extended to exactly one
163
parity structure by adding odd sets,
164
we see that there are exactly $2^{2^{n-1}}$ parity structures for $S$.
165
Hence $P$ has size $2^{2^{n-1}}$.
166
167
Let $J$ be the ideal $(1 + \sigma) R_{S}$.
168
Notice that $\sigma$ and $1 + \sigma$ are orthogonal idempotents
169
with sum $1$, so $R_{S}$ is the direct sum of $I$ and $J$ as rings.
170
Also, the linear map from $R_{S}$ to itself sending $x_{s_{0}}$ to
171
$x_{s_{0}} + 1$ (for some element $s_{0}$ of $S$) and fixing $x_{s}$
172
for all other values of $s$ is an automorphism of $R_{S}$ (since this
173
ring can be viewed as the free boolean algebra generated by
174
$x_{s_{0}} + 1$ and the other indeterminants $x_{s}$).
175
This automorphism interchanges $\sigma$ and $1 + \sigma$
176
and, hence, also $I$ and $J$, so $I$ and $J$ have the same dimension
177
as vector spaces over $\F_{2}$.
178
Since their sum, $R_{S}$, has dimension $2^{n}$, the ideals $I$
179
and $J$ have dimension $2^{n-1}$ and size $2^{2^{n-1}}$.
180
Thus $I$ and $P$ have the same size, and since $I$ is a subset of $P$,
181
they must be equal.
182
183
Finally, for every even-degree monomial $t$, the product $\sigma t$
184
is the sum of $t$ and some odd-degree monomials, so these products,
185
with $t$ ranging over all even-degree monomials, are linearly
186
independent over $\F_{2}$. But there are $2^{n-1}$ such
187
products, and by the above calculations, the dimension of $P$ is
188
$2^{n-1}$, so the products form a basis for $P$ over $\F_{2}$.
189
This completes the proof of the theorem.
190
\end{proof}
191
192
\section{A second parity property}
193
We now prove the alternate defining property of parity structures given
194
in the introduction.
195
\begin{theorem}
196
Let $S$ be a finite set and $T$ be a subset of $\pow S$.
197
Then $T$ is a parity structure for $S$ if and only if for each
198
subset $b$ of $S$ of even size, the number of subsets of $b$
199
of odd size that lie in $T$ is even.
200
\end{theorem}
201
\begin{proof}
202
First we prove that all parity structures satisfy this alternate
203
property. Notice that if the property holds for two parity
204
structures, then, as in the proof of the previous theorem, it will hold
205
for their symmetric difference. And since the image under $\bij$ of the
206
symmetric difference of two parity structures is the sum of their
207
images under $\bij$, it suffices to check the property for some
208
collection of parity structures whose images under $\bij$ form an
209
$\F_{2}$-basis for $R_{S}$. Thus by the previous theorem, it suffices
210
to check the property for parity structures of the form
211
$(\sigma t) \bij^{-1}$, with $t$ an even-degree monomial (in
212
distinct indeterminants).
213
214
Such a monomial $t$ equals $\bij(c)$ for some even subset $c$ of $S$.
215
>From the definition of $\bij$, the parity structure
216
$T = (\sigma t) \bij^{-1}$ consists of $c$ together
217
with all subsets of $S$ obtained by adding one new element to $c$.
218
Now take any even subset $b$ of $S$. If $c$ is not a subset of $b$,
219
then the number of odd subsets of $b$ that lie in $T$ is zero, so we
220
may assume that $c$ is a subset of $b$. Then the odd subsets of $b$
221
that lie in $T$ are exactly those subsets of $b$ obtained by adding a
222
new element to $c$. But there are $|b| - |c|$ such subsets, and since
223
both $|b|$ and $|c|$ are even, the number of such subsets is even.
224
225
To prove that any collection satisfying the property actually is a
226
parity structure, we note that a similar construction-and-counting
227
procedure to that in the previous theorem shows that there are
228
exactly $2^{2^{|S|-1}}$ subsets of $\pow S$ satisfying the property.
229
Since this is the same as the number of parity structures, and every
230
parity structure satisfies the property, the result follows. This
231
completes the proof of the theorem.
232
\end{proof}
233
234
\section{Refinements of Results}
235
We can now show that parity structures have stronger forms of
236
both the defining property and the one given in the previous section.
237
These state not merely that some collection of sets is even, but that
238
when the collection is partitioned in some way according to sizes of
239
the sets involved, every part of the partition contains an even
240
number of sets.
241
\begin{corollary}
242
For any finite set $S$ and any subset $T$ of $\pow S$, the following
243
are equivalent:
244
\begin{enumerate}
245
\item[a)]
246
$T$ is a parity structure for $S$.
247
248
\item[b)]
249
For every odd subset $b$ of $S$, there are an even number of subsets
250
of $b$ that lie in $T$.
251
252
\item[c)]
253
For every odd subset $b$ of $S$ and every even natural number $k$, there
254
are an even number of subsets of $b$ of size $k$ or $k + 1$ that lie
255
in $T$.
256
257
\item[d)]
258
For every even subset $b$ of $S$, there are an even number of odd
259
subsets of $b$ that lie in $T$.
260
261
\item[e)]
262
For every even subset $b$ of $S$ and every odd natural number $k$,
263
there are an even number of subsets of $b$ of size $k$ that lie in
264
$T$.
265
\end{enumerate}
266
\end{corollary}
267
268
\begin{proof}
269
Parts a) and b) are equivalent by definition, and the equivalence of
270
b) and d) is just the result of the previous theorem.
271
Parts b) and d) follow immediately from c) and e), respectively,
272
so it remains only to prove the converses of these last two implications.
273
As in the proofs of the previous theorems, it suffices to consider the
274
case when $T$ is of the form $\bij^{-1}(\sigma t) $ for some
275
even-degree monomial $t$. But then parts c) and e) follow from
276
b) and d), respectively, for $k$ equal to the degree of $t$ (plus $1$
277
for part e)), and they hold trivially for all other values of $k$.
278
\end{proof}
279
280
\section{The Ideal $\sigma R_{S}$}
281
We would like to close with a few remarks pointing out another way to
282
think about the ideal mentioned in the proof of the first theorem.
283
It is straightforward to see that the ring $R_{S}$, with $S$ of size
284
$n$, is semisimple and is isomorphic to $\Ftwo^{n}$
285
via the set of (central) orthogonal idempotents
286
$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \,
287
| \, \epsilon_{s} \in \F_{2}\}$.
288
Since the ideals of $\F_{2}$ are just itself and $(0)$, the elements
289
of the ideal $\sigma R_{S}$ are just those elements of $R_{S}$
290
that have support on the coordinates corresponding to the
291
idempotents lying in $\sigma R_{S}$. An idempotent
292
$t = \prod (x_{s} + \epsilon_{s})$
293
will be in the ideal $\sigma R_{S}$ if and only if $t$ equals
294
$\sigma t = t + \sum_{s \in S} x_{s} t$. This happens exactly if an
295
even number of the terms in the summation equal $t$ (while the rest
296
vanish), which happens if and only if an even number of the field
297
elements $\epsilon_{s}$ equal $0$. To summarise, the elements
298
of $\sigma R_{S}$ are the $\F_{2}$-linear combinations of those
299
idempotents $\prod (x_{s} + \epsilon_{s})$
300
that have an even number of the elements $\epsilon_{s}$ equal to $0$,
301
which is the same as having the lowest-degree term have even degree.
302
303
\section{Acknowledgment}
304
This work was done while the first author was a Research Fellow
305
at the University of California at Berkeley.
306
\end{document}
307
308
309