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