Quantum Boolean algebras

c

Journal “Algebra and Discrete Mathematics”

Quantum Boolean algebras

Rafael Díaz

Communicated by V. A. Artamonov

A b s t r ac t . We introduce quantum Boolean algebras which are the analogue of the Weyl algebras for Boolean affine spaces.

We study quantum Boolean algebras from the logical and the set theoretical viewpoints.

1. Introduction

After Stone [20] and Zhegalkin [23], Boole’s main contribution to science [5] can be understood as the realization that the mathematics of logical phenomena is controlled — to a large extend — by the field Z2 ={0,1} with two elements; in contrast the mathematics of classical physical phenomena is controlled — to a large extend — by the field R of real numbers. The switch from Z2 to R corresponds with a deep ontological jump from logical to physical phenomena. The switch from R toCcorresponds to the jump from classical to quantum physics.

What makes the logic/physics jump possible is the fact that Z2 may be regarded as an object of two different categories. On the one hand, it is a field (Z2,+, .) with sum and product defined by making 0 the neutral element and 1 the product unit. On the other hand, it is a set of truth values with 0 and 1 representing falsity and truth, respectively. Indeed, (Z2,∨,∧,(·)) is a Boolean algebra: a complemented distributive lattice with minimum 0 and maximum 1. The operations∨,∧, and (·) correspond with the logical connectives OR, AND, and NOT. The two viewpoints are

2010 MSC:06E75, 16S32, 81P10.

Key words and phrases:Boolean algebras, Weyl algebras, quantum logic.

related by the identities:a∨b=a+b+ab, a∧b=ab, a=a+ 1. These identities, together with the inverse relationa+b= (a∧b)∨(a∧b), allow us to switch back and forth from the algebraic to the logical viewpoint.

By and large, the logical and algebraic viewpoints have remained separated. In this work, in order to explore quantum-like phenomena in characteristic 2, we place ourselves at the jump. Our algebraic viewpoint is, in a sense, complementary to the quantum logic approach initiated by Birkhoff and von Neumann [3] based on the theory of lattices. For example, while the meet in quantum logic is a commutative connective, we propose in this work a quantum analogue for the meet which turns out to be non-commutative. The appearance of non-commutative operations is an essential feature of quantum mechanics [1, 7, 22].

We take as our guide the well-known fact that the quantization of canonical phase space may be identified with the algebra of differential operators on configuration space. In analogy with the real/complex case, we introduce the algebra BDO_n of Boolean differential operators onZⁿ₂. We provide a couple of presentations by generators and relations of BDOn, giving rise to the Boole-Weyl algebras BAnand the shifted Boole-Weyl algebras SBA_n. We call these algebras the quantum Boolean algebras.

We study the structural coefficients of BAn and SBAn in various bases.

Having introduced quantum Boolean algebras, we proceed to study them from the logical and set theoretical viewpoints. For us, the main difference between classical and quantum logic rest on the fact that classical observations, propositions, can be measured without, in principle, modifying the state of the system; quantum observations, in contrast, are quantum operators: the measuring process changes the state of the system.

Indeed, regardless of the actual state of the system, after measurement the system will be an eigenstate of the observable. Quantum observables are operators acting on the states of the system, and thus quite different to classical observables which are descriptions of the state of the system.

This work is organized as follows. In Section 2 we review some stan- dard facts on regular functions on affine spaces overZ2. In Section 3 we introduce BDOn, the algebra of Boolean differential operators on Zⁿ₂. In Section 4 we introduce the Boole-Weyl algebra BAn which is a presentation by generators and relations of BDOn. We describe the structural coefficients of BAn in several bases. In Section 5 we introduce the shifted Boole-Weyl algebra SBAn which is another presentation by generators and relations of BDOn, and describe the structural coefficients of SBAnin several bases. In Section 6 we discuss the logical aspects of our constructions: we introduce a quantum operational logic that generalizes

classical propositional logic, and for which Boolean differential operators play a semantic role akin to that played by truth functions in classical propositional logic. We use the theory of operads and props to describe our results. In Section 7 we adopt a set theoretical viewpoint and show that just as classical propositional logic is intimately related with PP(x), the Boolean algebra of sets of subsets of x, quantum operational logic is intimately related with PP(x⊔x) the quantum Boolean algebra of sets of subsets of two disjoint copies of x. In the final Section 8 we make some closing remarks and mention a few topics for future research.

2. Regular functions on Boolean affine spaces

Our main goal in this work is to study the Boolean analogue for the Weyl algebras, and to describe those algebras from a logical and a set theoretical viewpoints. Fixing a fieldk, the Weyl algebra Wn over kcan be identified with the k-algebra of algebraic differential operators on the affine space Aⁿ(k) = kⁿ. By definition [14, 19] the k-algebra k[Aⁿ] of regular functions on kⁿ is thek-algebra of maps

f:kⁿ→k

such that there exists a polynomial F ∈k[x1, . . . , xn] withf(a) =F(a) for alla∈kⁿ. Ifk is a field of characteristic zero, then the k-algebra of regular functions onkⁿcan be identified withk[x₁, . . . , xn] the polynomial ring of over k. Let∂1, . . . , ∂n be the derivations ofk[x1, . . . , xn] given by

∂ixj =δi,j for i, j∈[n] ={1, . . . , n}. The k-algebra DOn of differential operators onkⁿ is the subalgebra of

End_k(k[x₁, . . . , xn])

generated by∂i and the operators of multiplication byxi fori∈[n].

By definition, the Weyl algebra An is thek-algebra defined via gene- rators and relations as

khx₁,. . ., xn, y₁, . . . , yni/hxixj−xjxi, yiyj−yjyi, yixj−xjyi, yixi−xiyi−1i.

where khx₁, . . . , xn, y₁, . . . , yniis the free associative k-algebra generated byx₁, . . . , xn, y₁, . . . , yn, andhxixj−xjxi, yiyj −yjyi, yixj−xjyi, yixi− xiyi−1i is the ideal generated by the relations xixj =xjxi andyiyj = yjyi for i, j ∈ [n], yixj = xjyi for i 6= j ∈ [n], yixi = xiyi + 1 for i ∈ [n]. The Weyl algebra An comes with a natural representation

An → Endk(k[x1, . . . , xn]) sending yi to ∂i and xi to the operator of multiplication by xi. This representation induces an isomorphism of algebras An→DOn.

We proceed to study the analogue of the Weyl algebras for the Boolean affine spacesAⁿ(Z2) =Zⁿ₂. First, we review some basic facts on regular functions onZⁿ₂. Let M(Zⁿ₂,Z2) be theZ2-algebra of all maps from Zⁿ₂ to Z2 with pointwise addition and multiplication. TheZ2-algebraZ2[Aⁿ] of regular functions onZⁿ₂ is the sub-algebra of M(Zⁿ₂,Z2) consisting of the mapsf:Zⁿ₂ →Z2 for which there exists a polynomial F ∈Z2[x1, . . . , xn] such that f(a) = F(a) for all a ∈ Zⁿ₂. In this case Z2[Aⁿ] is not a polynomial ring; instead we have the following result.

Lemma 1. There is an exact sequence of Z2-algebras

0→ hx²₁+x₁, . . . ., x²_n+x_ni →Z2[x₁, . . . , x_n]→Z2[Aⁿ]→0 wherehx²₁+x₁, . . . ., x²_n+x_niis the ideal generated by the relationsx²_i =x_i

for i∈[n].

Therefore the ringZ2[Aⁿ] of regular functions onZⁿ₂ can be identified with the quotient ring

Z2[Aⁿ] =Z2[x₁, . . . , xn]/hx²₁+x₁, . . . ., x²_n+xni.

Often we think ofZⁿ₂ as a ring, with coordinate-wise sum and product.

We identify Zⁿ2 with P[n], the set of subsets of [n], via characteristic functions:a∈Zⁿ₂ is identified with the subset a⊆[n] such that i∈aif and only if ai = 1. With this identification the productab of elements in Zⁿ₂ agrees with the intersection a∩b of the sets a and b; the sum a+b corresponds with the symmetric differencea+b= (a∪b)\(a∩b);

the elementa+ (1, . . . ,1) is identified with the complementaof a. Note thata∪b=a+b+ab. We let PP[n] be the set of families of subsets of [n]. For a∈P[n], let m^a:Zⁿ₂ →Z2 be the characteristic function of the set {a} ⊆ P[n]. Fora∈ P[n] non-empty, let x^a ∈ Z2[x1, . . . , xn] be the monomial x^a=^Q_i∈axi. Also set x^∅ = 1. The monomial x^a defines the characteristic function x^a: Zⁿ₂ → Z2 of the set {b |a⊆ b} ⊆P[n]. For a∈P[n] non-empty, letw^a∈Z2[x1, . . . , xn] be given byw^a=^Q_i∈a(xi+1).

Also setw^∅ = 1. The monomial w^a defines the characteristic function w^a:Zⁿ₂ →Z2 of the set {b|b⊆a} ⊆P[n].

Lemma 2 below follows from the definitions above and the M¨obius inversion formula [18], which can be stated as follows. Given maps

f, g: P[n]→R, withR a ring of characteristic 2, then f(b) =^X

a⊆b

g(a) if and only if g(b) =^X

a⊆b

f(a).

Lemma 2. The following identities hold in Z2[Aⁿ]:

1)m^a=x^aw^a. 2) x^a=^X

a⊆b

m^b. 3) m^a=^X

a⊆b

x^b. 4) w^b=^X

a⊆b

m^a. 5)m^a=^X

a⊆b

w^b. 6) w^b =^X

a⊆b

x^a. 7) x^b =^X

a⊆b

w^a. 8) m^am^b=δabm^a. 9) x^ax^b =x^a∪b. 10) w^aw^b=w^a∪b.

Note that Z2[Aⁿ] = M(Zⁿ₂,Z2), indeed a map f:Zⁿ₂ → Z2 can be written as

f = ^X

f(a)=1

m^a= ^X

f(a)=1

x^aw^a= ^X

f(a)=1

Y

i∈a

xi

Y

i∈a

(xi+ 1)

= ^X

f(a)=1,b⊆a

x^a∪b= ^X

f(a)=1,a⊆b

x^b.

From Lemma 2 we see that there are several natural bases for the Z2-vector space

Z2[Aⁿ] =Z2[x₁, . . . , xn]/hx²₁+x₁, . . . ., x²_n+xni,

namely we can pick{m^a|a∈P[n]},{x^a|a∈P[n]}, or{w^a|a∈P[n]}.

We use the following notation to write the coordinates of f ∈Z2[Aⁿ] in each one of these bases

f = ^X

a∈P[n]

f(a)m^a= ^X

a∈P[n]

f_x(a)x^a= ^X

a∈P[n]

f_w(a)w^a.

We obtain three linear maps f →f,f →fx and f →fw fromZ2[Aⁿ] to M(Zⁿ₂,Z2). The coordinates f,f_x and f_w are connected, via the M¨obius inversion formula, by the relations:

fx(b) =^X

a⊆b

f(a), f(b) =^X

a⊆b

fx(a), fw(b) =^X

a⊆b

f(a),

f(b) =^X

a⊆b

fw(a), fx(a) =^X

a⊆b

fw(b), fw(a) =^X

a⊆b

fx(b).

The mapsf →fx andf →fw fail to be ring morphisms. Instead we have the identities:

(f g)x(c) = ^X

a∪b=c

fx(a)gx(b) and (f g)w(c) = ^X

a∪b=c

fw(a)gw(b).

We define a predicateO on finite sets as follows: given a finite seta, then Oa holds if and only if the cardinality of ais an odd number. In other words,O is the map from finite sets to Z2 such thatOa= 1 if and only if the cardinality ofais odd.

Example 3. Let C ∈ PP[n]. An ordered k-covering of a ∈ P[n] by elements of C is a tuple c₁, . . . , c_k ∈C such thatc₁∪ · · · ∪c_k = a. Let k-CovC(a) be the set ofk-coverings ofaby elements ofC. Then a∈P[n]

belongs toC if and only if|k-CovC(a)|is odd for everyk>1. Indeed, let f ∈Z2[Aⁿ] be given by

f =^X

c∈C

x^c = ^X

a∈P[n]

1C(a)x^a,

where 1C: P[n]→Z2 is the characteristic function ofC. Sincef^k=f for everyf ∈Z2[Aⁿ], we have

X

a∈P[n]

1C(a)x^a=f =f^k= ^X

a∈P[n]

X

a₁∪···∪ak=a

Yk

i=1

1C(ai)

x^a

= ^X

a∈P[n]

O(k-CovC(a))x^a.

We conclude that 1C(a) =O(k-CovC(a)), and thus a∈C if and only if

|k-Cov_C(a)|is odd.

3. Differential operators on Boolean affine spaces

Next we consider the algebra of differential operators on affine Boolean spaces. Note that the partial derivatives∂_ionZ2[x₁, . . . , x_n] do not descent to well-defined operators onZ2[Aⁿ]; indeed if we had such an operator, then 0 = xi +xi = ∂ix²_i = ∂ixi = 1. The Boolean partial derivative

∂if:Zⁿ₂ →Z2 of a map f:Zⁿ₂ →Z2 is given [6, 17] by

∂if(x) =f(x+ei) +f(x)

where ei ∈Zⁿ₂ is the vector with vanishing entries except at position i.

This definition yields well-defined operators ∂i: Z2[Aⁿ]→ Z2[Aⁿ]. The

operators∂i are skew derivations; indeed they satisfy the twisted Leibnitz identity

∂_i(f g) = (∂_if)g+ (s_if)(∂_ig)

where the shift operators si:Z2[Aⁿ] → Z2[Aⁿ] are given by sif(x) = f(x+ei). Indeed:

∂i(f g)(x) =f(x+ei)g(x+ei) +f(x)g(x)

= [f(x+ei) +f(x)]g(x) +f(x+ei)[g(x+ei) +g(x)]

=∂if(x)g(x) +sif(x)∂ig(x).

The operators ∂i are nilpotent:

∂_i²f(x) =∂if(x+ei) +∂if(x) =f(x) +f(x+ei) +f(x+ei) +f(x) = 0.

Definition 4. TheZ2-algebra BDOn of Boolean differential operators on Zⁿ₂ is the Z2-subalgebra of End_Z2(Z2[Aⁿ]) generated by ∂i and the operators of multiplication by xi fori∈[n].

Theorem 5. The following identities hold for xi, ∂i, si ∈ BDOn and i∈[n]:

1. x²_i =xi; 2. ∂_i² = 0; 3. s²_i = 1; 4. ∂i=si+ 1;

5. ∂isi =si∂i=∂i; 6. si=∂i+ 1; 7. sixi =xisi+si= (xi+ 1)si; 8. ∂ixi =xi∂i+si=xi∂i+∂i+ 1.

Proof. We have already shown that x²_i = xi and ∂_i² = 0. For the other identities we have

• s²_if(x) =sif(x+ei) =f(x+ei+ei) =f(x);

• ∂if(x) =f(x+ei) +f(x) =sif(x) +f(x) = (si+ 1)f(x);

•si∂if(x) =∂if(x+ei) =f(x+ei+ei) +f(x+ei) =f(x) +f(x+ei) =

∂if(x);

• ∂_is_if(x) =s_if(x+e_i) +s_if(x) = f(x+e_i+e_i) +f(x+e_i) =f(x) + f(x+ei) =∂if(x);

•sixif(x) = (xi+1)f(x+ei) =xif(x+ei)+f(x+ei) =xisif(x)+sif(x) = (x_is_i+s_i)f(x);

• sif(x) = f(x+ei) = f(x +ei) + f(x) + f(x) = ∂if(x) + f(x) = (∂i+ 1)f(x);

• ∂_i(x_if)(x) =x_if(x+e_i) +f(x+e_i) +x_if(x) =x_i(f(x+e_i) +f(x)) + f(x+ei), thus

• ∂i(xif) =xi∂if +f(x+ei) = (xi∂i+si)f = (xi∂i+∂i+ 1)f.

The operator ∂i acts on the basesm^a,x^aand w^a as follows:

∂im^a=m^a+ei+m^a,

∂ix^a=

(x^a\i ifi∈a

0 otherwise and ∂iw^a=

(w^a\i ifi∈a 0 otherwise.

From these expressions we obtain that:

•∂if(a) = 1 if and only iff(a)6=f(a+ei), that is,

∂if = ^X

a∈P[n],f(a)6=f(a+ei)

m^a.

•(∂if)x(a) =fx(a∪i) if i /∈a, and (∂if)x(a) = 0 if i∈a, that is,

∂if = ^X

i∈a∈P[n]

fx(a)x^a−i.

•(∂if)w(a) =fw(a∪i) if i /∈a, and (∂if)w(a) = 0 if i∈a, that is,

∂if = ^X

i∈a∈P[n]

fw(a)w^a−i.

More generally one can show by induction, fora, b∈P[n], that:

∂^bm^a=^X

c⊆b

m^a+c,

∂^bx^a=

(x^a\b ifb⊆a

0 otherwise, and ∂^bw^a=

(w^a\b ifb⊆a 0 otherwise.

By definition BDOn⊆End_Z2(Z2[Aⁿ]) acts naturally onZ2[Aⁿ], so we get a map

BDO_n⊗_Z2Z2[Aⁿ]→Z2[Aⁿ].

Proposition 6. Consider maps D: P[n]×P[n]→Z2 and f: P[n]→Z2. 1. Let D= ^P

a,b∈P[n]

D(a, b)m^a∂^b ∈BDOn, f = ^P

c∈P[n]

f(c)m^c ∈ Z2[Aⁿ], and Df = ^P

a∈P[n]

Df(a)m^a. Then we have Df(a) =^X

e⊆b

D(a, b)f(a+e).

2. Let D= ^P

a,b∈P[n]

Dx(a, b)x^a∂^b ∈BDOn, f = ^P

c∈P[n]

fx(c)x^c ∈Z2[Aⁿ], andDf = ^P

e∈P[n]

Dfx(e)x^e. Then Dfx(e) = ^X

a,b⊆c

a∪(c\b)=e

Dx(a, b)fx(c).

Proof.

1. Df = ^X

a,b,c∈P[n]

D(a, b)f(c)m^a∂^bm^c = ^X

a,e⊆b,c

D(a, b)f(c)m^am^c+e

= ^X

a,e⊆b

D(a, b)f(a+e)m^a= ^X

a∈P[n]

X

e⊆b

D(a, b)f(a+e)

m^a.

2. Df = ^X

a,b,c∈P[n]

Dx(a, b)fx(c)x^a∂^bx^c = ^X

a,b⊆c

Dx(a, b)fx(c)x^a∪c\b

= ^X

e∈P[n]

X

a,b⊆c

a∪(c\b)=e

Dx(a, b)fx(c)

x^e.

Theorem 7. For n>1 we have BDOn= End_Z2(Z2[Aⁿ]).

Proof. Note that dim

End_Z2(Z2[Aⁿ])

= dim(Z2[Aⁿ])dim(Z2[Aⁿ]) = 2ⁿ2ⁿ= 2²ⁿ. The set {x^a∂^b |a, b ∈ P[n]} has 2²ⁿ elements and generates BDOn as a vector space over Z2; thus it is enough to show that it is a linearly independent set. Suppose that

X

a,b∈P[n]

f(a, b)x^a∂^b = ^X

b∈P[n]

X

a∈P[n]

f(a, b)x^a

∂^b = 0.

Pick a minimal setc∈P[n] such that ^P

a∈P[n]

f(a, c)x^a6= 0. We have X

a,b∈P[n]

f(a, b)x^a∂^b

(x^c) = ^X

b∈P[n]

X

a∈P[n]

f(a, b)x^a

∂^b(x^c)

= ^X

a∈P[n]

f(a, c)x^a= 0.

Therefore, since{x^a|a∈P[n]} is a basis forZ2[Aⁿ], we havef(a, c) = 0 in contradiction with the fact^P_a∈P[n]f(a, c)x^a 6= 0. We conclude that dim BDO_n= 2²ⁿ yielding the desired result.

Putting together Proposition 6 and Theorem 7 we get a couple of explicit ways of identifying BDO_n with M₂ⁿ(Z2), the algebra of square matrices of size 2ⁿ with coefficients in Z2. Note that M₂ⁿ(Z2) may be identified with M(P[n]×P[n],Z2). Moreover, we can identify M(P[n]× P[n],Z2) with the set of directed graphs with vertex set P[n] and without multiple edges as follows: given a matrixM ∈M2ⁿ(Z2) its associated graph has an edge frombtoaif and only ifMa,b= 1. Let R : BDOn→M₂ⁿ(Z2) be theZ2-linear map constructed as follows. Consider the bases

{m^a∂^b |a, b∈P[n]} for BDOn and {m^a|a∈P[n]} forZ2[Aⁿ].

For a, b ∈ P[n], let R(m^a∂^b) be the matrix of m^a∂^b on the basis m^a. The action of m^a∂^b on m^c is given by m^a∂^bm^c = m^aP_e⊆bm^c+e = P

e⊆bm^am^c+e=m^aifc+a⊆band zero otherwise. Therefore, the matrix R(m^a∂^b) is given forc, d∈P[n] by the rule

R(m^a∂^b)_c,d=

(1 ifc=aand d+a⊆b, 0 otherwise.

Example 8. The graph of R(m^{1,2}∂^{2,3}) is show in Figure 1.

F i g u r e 1 . Graph of the matrix R(m^{1,2}∂^{2,3}).

For a second representation consider theZ2-linear map S : BDOn→ M₂ⁿ(Z2) constructed as follows. Consider the bases

{x^a∂^b |a, b∈P[n]} for BDOn and {x^a|a∈P[n]} forZ2[Aⁿ].

For a, b∈ P[n] let S(x^a∂^b) be the matrix of x^a∂^b on the basisx^a. The action ofx^a∂^b on x^c is given by

x^a∂^bx^c =

(x^a∪c\b ifb⊆c, 0 otherwise.

Therefore, the matrix S(x^a∂^b) is given forc, d∈P[n] by the rule S(x^a∂^b)_c,d=

(1 ifc=a∪d\b and b⊆d, 0 otherwise.

Example 9. The graph associated to the matrix S(m^{1}∂^{3}) is shown in Figure 2.

F i g u r e 2 . Graph of the matrix S(m^{1}∂^{3}).

4. Boole-Weyl Algebras

First we motivate, from the viewpoint of canonical quantization, our definition of Boole-Weyl algebras. Canonical phase space for a field k of characteristic zero can be identified with the affine space kⁿ×kⁿ. The Poisson bracket on k[x₁, . . . , xn, y₁, . . . , yn] in canonical coordinates x1, . . . , xn, y1, . . . , yn on kⁿ×kⁿ is given by

{xi, xj}= 0, {yi, yj}= 0, {xi, yj}=δi,j.

Equivalently, the Poisson bracket is given forf, g∈k[x1, . . . , xn, y1, . . . , yn] by

{f, g}= Xn

i=1

∂f

∂xi

∂g

∂yi

− ∂f

∂yi

∂f

∂xi

.

Canonical quantization may be formulated as the problem of promoting the commutative variables xi and yj into non-commutative operators x_bi

and y_bj satisfying the commutation relations:

[x_bi,x_bj] = 0, [y_bi,y_bj] = 0, [y_bi,x_bj] =δi,j.

Note that the free algebra generated byx_bi andy_bj subject to the above relations is precisely what is called the Weyl algebra and its usually denoted by An. Now let k = Z2 and consider the affine phase spaces

Zⁿ₂ ×Zⁿ₂. Let x1, . . . , xn, y1, . . . , yn be canonical coordinates on Zⁿ₂ ×Zⁿ₂. The analogue of the Poisson bracket

{,}:Z2[A²ⁿ]⊗Z2[A²ⁿ]→Z2[A²ⁿ] can be expressed forf, g∈Z2[A²ⁿ] as

{f, g}= Xn

i=1

∂f

∂xi

∂g

∂yi

+ ∂f

∂yi

∂f

∂xi

, where _∂x^∂

i and_∂y^∂

i are the Boolean partial derivatives along the coordinates xi and yi. Clearly, the full set of axioms for a Poisson bracket will not longer hold, e.g. Boolean derivatives are skew derivations. Nevertheless, the bracket is still determined by its values on the canonical coordinates:

{xi, xj}= 0,{yi, yj}= 0,{xi, yj}=δi,j. Canonical quantization consists in promoting the commutative variablesx_i andy_j to non-commutative operatorsx_bi and y_bj satisfying the commutation relations:

[x_bi,x_bj] = 0, [y_bi,y_bj] = 0, [y_bi,x_bj] = 0 fori6=j, and [y_bi,x_bi]si = 1.

Note that in the last relation we use the twisted commutator [f, g]si =f g+ (sif)g;

this choice is expected since the operatorsy_bi are skew derivations instead of usual derivations. The relation [y_bi,x_bi]si = 1 can be equivalently written using commutators as [y_bi,x_bi] =y_bi+ 1.

Definition 10. The Boole-Weyl algebra BAnis the quotient ofZ2hx₁, . . . , xn, y1, . . . , yni, the free associative Z2-algebra generated by x1, . . . , xn, y₁, . . . , yn, by the ideal

hx²_i +xi, xixj+xjxi, yiyj+yjyi, y²_i, yixj+xjyi, yixi+xiyi+yi+ 1i.

Theorem 11. The mapZ2hx1, . . . , xn, y1, . . . , yni →End_Z2(Z2[Aⁿ])sen- ding xi to the operator of multiplication by xi, and yi to ∂i, descends to an isomorphism BAn→End_Z2(Z2[Aⁿ]) of Z2-algebras.

Proof. By Theorem 5 the given map descends. By definition it is a surjective map BAn→ BDOn= End_Z2(Z2[Aⁿ]). Moreover, this map is an isomorphisms since dim BAn

= dim End_Z2(Z2[Aⁿ]). Indeed using the commutation relations it is easy to check that the natural map

Z2[x₁, . . . , xn]/hx²_i +xii ⊗Z2[y₁, . . . , yn]/hy²_ii →BAn

is surjective. If ^P

a,b∈P[n]

f(a, b)x^a⊗y^b is in the kernel of the latter map, then the Boolean differential operator ^P

a,b∈P[n]

f(a, b)x^a∂^b would vanish, and therefore the coefficients f(a, b) must vanish as well. Thus

dim(BAn) = dim(Z2[x₁, . . . , xn]/hx²_i +xii)dim(Z2[y₁, . . . , yn]/hy_i²i)

= 2ⁿ2ⁿ= dim(Z2[Aⁿ])dim(Z2[Aⁿ]) = dim(End_Z2(Z2[Aⁿ])).

Theorem 12. The mapZ2hx₁, . . . , xn, y₁, . . . , yni →End_Z2(Z2[Aⁿ]) sen- ding xi to the operator of multiplication by wi = xi + 1, and yi to the operator∂_i, descends to an isomorphism BA_n →End_Z2(Z2[Aⁿ]) of Z2-algebras.

Proof. Follows from the fact that wi and ∂j satisfy exactly the same relation asxi and ∂j.

Corollary 13. Any identity in BAninvolvingxiand∂j has an associated identity involving wi and ∂j obtained by replacingxi by wi.

Lemma 14. Fora, b, c, d∈P[n]the following identities hold in BW_n: 1. y^bm^c = ^P

b1⊆b2⊆b

m^c+b2y^b1. 2. m^ay^bm^cy^d= ^P

d⊆e

e\d⊆a+c⊆b

m^ay^e. 3. y^bx^c = ^P

k₁⊆k2⊆b∩c

x^c\k2y^b\k1. 4. x^ay^bx^cy^d = ^P

a⊆e,d⊆f

c(a, b, c, d, e, f)x^ey^f, where c(a, b, c, d, e, f) = O{k1⊆k2 ⊆b∩c|a∪(c\k2) =e, b\k1 =f \d}.

Proof. 1. By Theorem 11 it is enough to show that the differential opera- tors associated with both sides of the equation are equal. Consider the operator of multiplication by f: Zⁿ₂ → Z2 and let g:Zⁿ₂ → Z2 be any other map. The twisted Leibnitz rule ∂i(f g) = (∂if)g+ (sif)∂igcan be extended, sincesi and ∂i commute, to the identity:

∂^b(f g) = ^X

b1⊔b2=b

(s^b2∂^b1f)∂^b2g, thus the following identity holds in BAn:

y^bf = ^X

b1⊔b2=b

s^b2(∂^b1f)y^b2 forf ∈Z2[x1, . . . , xn].

In particular we obtain that y^bm^c= ^X

b₁⊔b2⊆b

s^b2s^b1(m^c)y^b2 = ^X

b₁⊔b2⊆b

m^c+b1+b2y^b2 = ^X

b₁⊆b2⊆b

m^c+b2y^b1.

2. We have

m^ay^bm^cy^d= ^X

b₁⊆b2⊆b

m^am^c+b2y^b1y^d= ^X

b₁⊆b2⊆b

δ_a,c+b2m^ay^b1⊔d

= ^X

b₁⊆a+c⊆b

m^ay^b1⊔d= ^X

d⊆e

e\d⊆a+c⊆b

m^ay^e.

where the last identity follows from the fact thatb₂=a+cande=b₁⊔d.

3. From the relationsyixj =xjyi for i6= j and yixi =xiyi+yi+ 1 we can argue as follows. If a letteryi is placed just to the left of axj we can move it to the right, since these letters commute. If instead we have a productyixi, then three options arises:

a) yi moves to the right ofxi; b) yi absorbsxi;

c) xi and yi annihilate each other leaving an 1.

Callk₁ the set of indices for which c) occurs, and k₂ the set of indices for which either b) or c) occur. Thenk₁ ⊆k₂⊆b∩cand the set for which option a) occurs isb∩c\k2. Thus the desired identity is obtained. 4. We have

x^ay^bx^cy^d= ^X

k₁⊆k2⊆b∩c

x^a∪c\k2y^(b\k1)⊔d= ^X

a⊆e,d⊆f

c(a, b, c, d, e, f)x^ey^f, wherec(a, b, c, d, e, f) =O{k₁⊆k₂⊆b∩c|a∪(c\k₂) =e, b\k₁=f\d}.

Example 15. y^{1}m^{1} =m^{1}+m^∅+m^{∅}y^{1}; m^{1}y^{1}m^{1}y^{1} = m^{1}y^{1}; y^{1}m^{1,2} =m^{1,2}+m^{2}+m^{2}y^{1}; m^{2}y^{1}m^{1,2}y^{1} = m^{2}y^{1};y^{1,2}m^{1,2,3}=m^{1,2,3}+m^{2,3}+m^{1,3}+m^{1}+m^{2,3}y^{1}+ m^{3}y^{1}+m^{1,3}y^{2}+m^{3}y^{2}+m^{3}y^{1,2};m^{3}y^{1,2}m^{1,2,3}y^{1} = m^{3}y^{1,2}.

Example 16. For i∈[k] assume given Ai ∈PP[n] and fi =^P_a∈Aiy^a. Then

f1· · ·fk= ^X

b∈P[n]

O{(a1, . . . , ak)∈A1×. . .×Ak |a1⊔ · · · ⊔ak =b}y^b.

In particular, for A∈PP[n] andf =^P_a∈Ay^a, we get that f^k= ^X

b∈P[n]

O{a₁, . . . , a_k∈A|a₁⊔ · · · ⊔a_k=b}y^b. For example, ifA= P[n] then fork>2 we have

f^k= ^X

b∈P[n]

O{a₁, . . . , a_k∈P[n]|a₁⊔· · ·⊔a_k=b}y^b = ^X

b∈P[n]

(k^|b| mod 2)y^b, thusf^k=f ifkis odd and f^k = 1 ifk is even.

From Lemma 2 we see that there are several natural basis for BAn, namely:

{m^ay^b|a, b∈P[n]}, {x^ay^b |a, b∈P[n]}, {w^ay^b |a, b∈P[n]}.

We write the coordinates of f ∈BAn in these bases as:

f = ^X

a,b∈P[n]

fm(a, b)m^ay^b = ^X

a,b∈P[n]

fx(a, b)x^ay^b = ^X

a,b∈P[n]

fw(a, b)w^ay^b. These coordinates systems are connected by the relations:

fx(b, c) =^X

a⊆b

fm(a, c), fm(b, c) =^X

a⊆b

fx(a, c), fw(b, c) =^X

a⊆b

fm(a, c), fm(b, c) =^X

a⊆b

fw(a, c), fx(a, c) =^X

a⊆b

fw(b, c), fw(a) =^X

a⊆b

fx(b, c).

Theorem 17.Forf, g∈BAnthe following identities hold fora, e, h∈P[n]:

1) (f g)m(a, e) = ^P

b,c,d⊆e

e\d⊆a+c⊆b

fm(a, b)gm(c, d).

2) (f g)x(e, h) = ^P

a⊆e,b,c,d⊆h

c(a, b, c, d, e, h)fx(a, b)gx(c, d),where

c(a, b, c, d, e, h) =Oⁿk₁⊆k₂ ⊆b∩c|a∪(c\k₂) =e, b\k₁ =h\d^o. Proof. 1. Let f = ^P_a,b∈P[n]fm(a, b)m^ay^b, g = ^P_c,d∈P[n]gm(c, d)m^cy^d, then

f g= ^X

a,b,c,d∈P[n]

f_m(a, b)g_m(c, d)m^ay^bm^cy^d

= ^X

a,b,c,d,e∈P[n]

fm(a, b)gm(c, d) ^X

d⊆e

e\d⊆a+c⊆b

m^ay^e

= ^X

d⊆e,e\d⊆a+c⊆b

f_m(a, b)g_m(c, d)m^ay^e.