In order to study parity structures for *S*, we introduce a ring whose
elements correspond naturally to subsets of
.
Let *R*_{S}
denote the free (commutative) boolean algebra over
generated
by idempotents corresponding to the elements of *S*; that is, define

(Note that this is similar to, but different from, the definition of a Stanley-Reisner ring, in which we take

Under this map, each subset of

We distinguish the element
of *R*_{S}; it corresponds under
to the collection of subsets
of *S* of size at most 1. Using *R*_{S} we obtain a ring-theoretic
characterization of the parity structures for *S*.

- (a)
- A subset
*T*of is a parity structure for*S*if and only if is in the ideal . - (b)
- The elements ,
with
*t*a monomial in an even number of the generators*x*_{s}, form an -basis for the ideal .

PROOF:Let *S* have size *n*, write *R* for *R*_{S}, and let *P* be
the set of all images under
of parity structures for *S*.
If *S* is empty, then all subsets of
are parity structures,
and
generates *R* as an ideal, so the theorem holds.
Hence we may assume that *n* is positive.

We first translate the set-theoretic condition for the subset *T*
of
to be a parity structure into an algebraic condition
on .
For any element *t* of *R* and any subset *b*
of *S*, write *t*(*b*) for the value of the polynomial *t* with each
indeterminant *x*_{s} set equal to 1 if *s* is in *b* and set
to 0 otherwise. This can be thought of as the evaluation of *t* on
the characteristic vector of *b*. For each subset *b* of *S* and each
element *c* of *T*, the term
of
will vanish on *b*
if *c* is not a subset of *b* and will give the value 1 otherwise.
Hence
gives the parity of the number of subsets of *b*
that lie in *T*. Therefore, *T* is a parity structure if and only if,
for every odd subset *b* of *S*, the value of
is 0.

Since polynomial specialization gives ring homomorphisms, for each
odd subset *b* of *S*, the map
from *R* to
given
by
is a homomorphism of rings.
And, as the previous remarks show that *P* is the intersection of the
kernels of these maps for all such subsets *b*, we see that *P* is an
ideal of *R*. Now order the odd subsets of *S* by increasing size
(with any order chosen for subsets of the same size)
as
.
Then the
matrix with (*i*,*j*)-entry equal
to
is upper triangular with 1's on the
main diagonal, so the homomorphisms
are linearly
independent over
.
Hence *P* has
dimension
2^{n} - 2^{n-1} = 2^{n-1} as an
-vector space.

Next we verify that *P* contains the ideal *I* generated
by
.
If *b* is any odd subset
of *S*, then *b* has |*b*| + 1 subsets of size 0 or 1, and |*b*| + 1
is even. Hence the collection of subsets of *S* of size at most 1
is a parity structure, and as the image of this collection under
is ,
we have
.
Since *P* is an ideal, it
contains *I* as a subset.

Now we show that *I* and *P* have the same size, hence must be equal.
Let *J* be the ideal
.
Notice that
and
are orthogonal idempotents
with sum 1, so *R* is the direct sum of *I* and *J* as rings.
Also, the linear map from *R* to itself sending *x*_{s0}
to
1 + *x*_{s0} (for some element *s*_{0} of *S*) and fixing *x*_{s}
for all other values of *s* is an automorphism of *R* (since *R*
can be viewed as the free boolean algebra generated
by
1 + *x*_{s0} and the other indeterminants *x*_{s}).
This automorphism interchanges
and
and, hence, also *I* and *J*, so *I* and *J* have the same dimension
as vector spaces over
.
Since their sum *R*
has dimension 2^{n}, the ideals *I* and *J* have dimension 2^{n-1}
over
.
Thus *I* and *P* have the same
-dimension,
and since *I* is a subset of *P*, they must be equal.
This completes the proof of part (a).

Finally, we prove part (b).
For every even-degree monomial *t*, the product
is the sum of *t* and some odd-degree monomials, so these products,
with *t* ranging over all even-degree monomials, are linearly
independent over
.
But there are 2^{n-1} such
products, and by the above calculations, the dimension of *P*
is 2^{n-1}, so the products form a basis for *P* over
.
This completes the proof of the theorem.

This result allows us to count immediately the parity structures for a finite set.

PROOF:Theorem 1 shows that the parity structures are in
bijection with an
-vector space of dimension 2^{n-1}.