In this paper we address the question “How many properties of Boolean functions can be defined by means of linear equations?” It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related with the theory of function minors and stable classes, a topic that has been widely investigated in recent years by several authors including Maurice Pouzet.
(1)
This motivated several studies that considered syntactic restrictions on functional equations and relational constraints.
Foldes and Pogosyan [
Getting back to linearly definable classes of Boolean functions, in [
f (X vi) = 0.
I✓{ 1,...,k+1} i2 I This shows that even in the case of Boolean functions, there are infinitely many linearly definable classes. Other examples were also provided, but it remained until recently an open problem to determine whether there are uncountably many linearly definable classes as is the case with classes definable by unrestricted functional equations. The answer follows from a result of Sparks [21, Theorem 1.3], namely, there are a countably infinite number of linearly definable classes.
In this paper we refine this result by explicitly describing the linearly definable classes of Boolean functions. After recalling some basic notions and results on function minors and stability under composition with clones in Section 2, we then completely describe the lattice of linearly definable classes (Section 3). Using this result and Post’s classification of Boolean clones, we can easily determine the classes which are stable under right and left compositions with clones C1 and C2 containing the clone of constant-preserving linear functions (Section 4). 2
Basic notions and preliminary results Throughout this paper, let N and N+ denote the set of all nonnegative integers and the set of all positive integers, respectively. For any n 2 N, the symbol [n] denotes the set { i 2 N | 1 i n }. in FAB, and for any C ✓ F AB, we let C(n) := C \ F A(nB) and call it the n-ary part of C.
Let A and B be sets. A mapping of the form f : An ! B for some n 2 N+ is called a function of several arguments from A to B (or simply a function). The number n is called the arity of f and denoted by ar(f ). If A = B, then such a function is called an operation on A. We denote by FAB and OA the set of all functions of several arguments from A to B and the set of all operations on A, respectively. For any n 2 N+, we denote by F A(nB) the set of all n-ary functions Example 2.1. For b 2 B and n 2 N, the n-ary constant function c(bn) : An ! B is given by the rule (a1, . . . , an) 7! b for all a1, . . . , an 2 A.
Example 2.2. In the case when A = B, for n 2 N and i 2 [n], the i-th n-ary projection pri(n) : An ! A is given by the rule (a1, . . . , an) 7! ai for all a1, . . . , an 2 A.
Let f : An ! B and i 2 [n]. The i-th argument is essential in f if there exist a1, . . . , an, a0i 2 A such that f (a1, . . . , an) 6= f (a1, . . . , ai 1, a0i, ai+1, . . . , an).
f (g1, . . . , gn)(a) := f (g1(a), . . . , gn(a)), for all a 2 Am.
2.1
Minors and functional composition Let f : Bn ! C and g1, . . . , gn : Am f (g1, . . . , gn) : Am ! C given by the rule !
The composition of f with g1, . . . , gn is the function Let : [n] ! [m]. Define the function f : Am ! B by the rule
f (a1, . . . , am) = f (a (1), . . . , a (n)), for all a1, . . . , am 2 A. Such a function f is called a minor of f . Intuitively, minors of f are all those functions that can be obtained from f by manipulation of its arguments: permutation of arguments, introduction of fictitious arguments, identification of arguments. It is clear from the definition that the minor f can be obtained as a composition of f with m-ary projections on A:
f = f (pr( m(1)), . . . , pr( m(n))).
We write f g if f is a minor of g. The minor relation is a quasiorder (a reflexive and transitive relation) on FAB, and it induces an equivalence relation ⌘ on FAB and a partial order on the quotient FAB/⌘ in the usual way: f ⌘ g if f g and g f , and f /⌘ g/⌘ if f g.
Functional composition can be extended to classes of functions. Let C ✓ F BC and K ✓ F AB. The composition of C with K is defined as
CK := { f (g1, . . . , gn) | f 2 C(n), g1, . . . , gn 2 K(m), n, m 2 N+ }.
It follows immediately from definition that function class composition is monotone, i.e., if C, C0 ✓ F BC and K, K0 ✓ F AB satisfy C ✓ C0 and K ✓ K0, then CK ✓ C0K0. 2.2
Clones, minor closure and stability under compositions with clones A class C ✓ O A is called a clone on A if CC ✓ C and C contains all projections. The set of all clones on A is a closure system in which the greatest and least elements are the clone OA of all operations on A and the clone of all projections on A, respectively.
Definition 2.3. Let K ✓ F AB, C1 ✓ O B, and C2 ✓ O A. We say that K is stable under left composition with C1 if C1K ✓ K, and that K is stable under right composition with C2 is KC2 ✓ K. If both C1K ✓ K and KC2 ✓ K hold, we say that K is (C1, C2)-stable. If K, C ✓ O A and K is (C, C)-stable, we say that K is C-stable. The set of all (C1, C2)-stable subsets of FAB is a closure system.
Remark 2.4. A set K ✓ F AB is minor-closed if and only if it is stable under right composition with the set of all projections on A. Every clone is minor-closed. A clone C is (C, C)-stable.
Lemma 2.5. Let C1 and C10 be clones on B and C2 and C20 clones on A such that C1 ✓ every K ✓ F AB, it holds that if K is (C10, C20)-stable then K is (C1, C2)-stable.
C10 and C2 ✓
Proof. Assume that K is (C10, C20)-stable. It follows from the monotonicity of function class composition that C1K ✓ C10K ✓
K and
KC2 ✓
KC20 ✓
K.
3
The lattice of linearly definable classes of Boolean functions
Recall that operations on {0, 1} are called Boolean functions. In this section we completely describe the lattice of
linearly definable classes of Boolean functions. The starting point is the following characterization of these classes first
obtained for Boolean functions in [
Theorem 3.1. A class of Boolean functions is linearly definable if and only if it is stable under left and right compositions with the clone of constant-preserving linear Boolean functions.
Hence to completely describe the linearly definable classes it suffices to determine those that are stable under left and right compositions with the clone of constant-preserving linear Boolean functions. This will be presented in Subsection 3.2.
The class of all Boolean functions is denoted by ⌦ . It is well known that every f 2 ⌦ (n) is represented by a unique multilinear polynomial over the two-element field, i.e., a polynomial with coefficients in {0, 1} in which no variable appears with an exponent greater than 1. This polynomial is known as the Zhegalkin polynomial of f , and it can be written as where xS is a shorthand for Qi2 S xi and where Mf ✓ P ([n]) is the family of index sets corresponding to the tmheonnowmeisaalsyothfaft.fNhoatsectohnasttxa;nt=ter1man1d;oPtheSr2;wixseS f=ha0s. cTohnesttaenrmttserxmS 0w. iWthitSh o6=ut; anayrericsaklloefdcmonofnuosmioina,lsw. eIfw; i2ll oMftefn, denote functions by their Zhegalkin polynomials, and we refer to the set Mf as the set of monomials of f . The degree of a Boolean function f , denoted deg(f ), is the size of the largest monomial of f , i.e., f = X xS ,
S2 Mf deg(f ) := Sm2aMxf |S| for f 6= 0, and we agree that deg(0) := 0. For k 2 N, we denote by Dk the class of all Boolean functions of degree at most k. Clearly Dk ( Dk+1 for all k 2 N. A Boolean function f is linear if deg(f ) 1.2 We denote by L the class of all linear functions. Thus L = D1.
For a 2 { 0, 1}, let Ca := { f 2 ⌦ | f (0, . . . , 0) = a } and Ea := { f 2 ⌦ | f (1, . . . , 1) = a }. Clearly C0 \ C1 = ; and C0 [ C1 = ⌦ ; similarly, E0 \ E1 = ; and E0 [ E1 = ⌦ . It is easy to see that Ca is the class of all Boolean functions with constant term a.
For a 2 { 0, 1}, a Boolean function f is a-preserving if f (a, . . . , a) = a. A function is constant-preserving if it is both 0- and 1-preserving. We denote the classes of all 0-preserving, of all 1-preserving, and of all constant-preserving functions by T0, T1, and Tc, respectively. Note that Tc = T0 \ T1. It follows from the definitions that T0 = C0, T1 = E1, and Tc = C0 \ E1.
Remark 3.2. The reason why we have introduced multiple notation for the classes T0 = C0 and T1 = E1 is to facilitate writing certain statements in a parameterized form and to make reference, as the case may be, to either the classes Ca (a 2 { 0, 1}), Ea (a 2 { 0, 1}), or Ta (a 2 { 0, 1}).
The parity of a Boolean function f , denoted par(f ), is a number, either 0 or 1, which is given by par(f ) := |Mf \ {;}| mod 2.
We call a function even or odd if its parity is 0 or 1, respectively. We denote by P0 and P1 the classes of all even and of all odd functions, respectively. Clearly P0 \ P1 = ; and P0 [ P1 = ⌦ .
For a 2 { 0, 1}, let a denote the negation of a, that is, a := 1 a. A function f is self-dual if f (a1, . . . , an) = f (a1, . . . , an), for all a1, . . . , an 2 { 0, 1}.
A function f is reflexive (or self-anti-dual) if f (a1, . . . , an) = f (a1, . . . , an) for all a1, . . . , an 2 { 0, 1}. We denote by S the class of all self-dual functions. Let Sc := S \ Tc, the class of constant-preserving self-dual functions. We also let L0 := L \ T0, L1 := L \ T1, LS := L \ S, and Lc := L \ Tc. It is easy to verify that L0 = L \ C0, L1 = (L \ P0 \ C1) [ (L \ P1 \ C0), Lc = L \ P1 \ C0, and LS = L \ P1.
It was shown by Post [
Mf | S ( A }| mod 2.
The characteristic rank of f , denoted by (f ), is the smallest integer m such that ch(S, f ) = 0 for all subsets S ✓ [n] with |S| m. Clearly, (f ) n because ch([n], f ) = 0. For k 2 N, denote by Xk the class of all Boolean functions of characteristic rank at most k. For any k 2 N, we have Xk ( Xk+1. The inclusion is proper, as witnessed by the function x1 . . . xk+1 2 Xk+1 \ Xk. Moreover, for any k 2 N, we have Dk ✓ Xk.
Reflexive and self-dual functions have a beautiful characterization in terms of the characteristic rank. Lemma 3.3 (Selezneva, Bukhman [20, Lemmata 3.1, 3.5]).
1. A Boolean function f is reflexive if and only if (f ) = 0.
2Strictly speaking, functions of degree at most 1 are affine in the sense of linear algebra. We go along with the term linear that is common in the context of clone theory and especially in the theory of Boolean functions.
⌦ P0
C0
E0
E1
C1
P1 C0 \ E0
C1 \ E1
C0 \ E1
C1 \ E0
3. A Boolean function f is self-dual if and only if f is odd and (f ) = 1.
In other words, X0 = X1 \ P0 is the class of all reflexive functions, X1 \ P1 is the class of all self-dual functions, and X1 is the class of all self-dual or reflexive functions.
We can now present the main result of the paper, namely, a complete description of the Lc-stable classes or, equivalently, of the linearly definable classes of Boolean functions. Of particular importance is the poset of the eleven classes ⌦ , P0, P1, C0, C1, E0, E1, C0 \ E0, C0 \ E1, C1 \ C0, C1 \ E1 that is shown in Figure 1. It is noteworthy that the four minimal classes of this poset are pairwise disjoint, and that the six lower covers of ⌦ are precisely the unions of the six different pairs of minimal classes.
⌦ , Dk, Xk, Di \ Xj , D0,
Ca, Dk \ Ca, Xk \ Ca, Di \ Xj \ Ca,
D0 \ Ca, for a, b 2 { 0, 1} and i, j, k 2 N+ with i > j
Ea, Dk \ Ea, Xk \ Ea, Di \ Xj \ Ea, ; , 1.
Pa, Dk \ Pa, Xk \ Pa, Di \ Xj \ Pa,
Ca \ Eb, Dk \ Ca \ Eb, Xk \ Ca \ Eb, Di \ Xj \ Ca \ Eb, The lattice of Lc-stable classes is shown in Figure 2. In order to avoid clutter, we have used some shorthand notation. The diagram includes multiple copies of the 11-element poset of Figure 1 (the shaded blocks) connected by thick triple lines. Each thick triple line between a pair of such blocks represents eleven edges, each connecting a vertex of one poset to its corresponding vertex in the other poset. We have labeled in the diagram the meet-irreducible classes, as well as a few other classes of interest; the remaining classes are intersections of the meet-irreducible ones. The proof of Theorem 3.4 is omitted for space constraints. The proof has two parts. First we need to verify that the classes listed in Theorem 3.4 are Lc-stable. Since intersections of Lc-stable classes are Lc-stable, it suffices to show this for the meet-irreducible classes; this is rather straightforward. Secondly, we need to verify that there are no other Lc-stable classes. This is a more difficult task and can be accomplished by proving that each class K is generated by any subset of K that contains for each proper subclass C of K an element in K \ C. 4
Stability under clones containing Lc Using Theorem 3.4 together with Lemma 2.5 it is straightforward to determine the (C1, C2)-stable classes for any clones C1 and C2 containing Lc. Such classes must occur among the Lc-stable classes by Lemma 2.5, so it is just a matter of deciding which ones are (C1, C2)-stable. In particular, we obtain the C-stable classes for every clone C containing Lc, i.e., the clones ⌦ , T0, T1, Tc, S, Sc, L, L0, L1, LS and Lc.
P0
C0
E0
C1
P1
D4 \ X3 D3 \ X2 D2 \ X1
X4
X3 D4 \ X2 D3 \ X1
D4 \ X1
X2
X0
S X1
Sc
(i) The Lc-stable classes are ⌦ , Ca, Ea, Pa, Ca \ Eb, Dk, Dk \ Ca, Dk \ Ea, Dk \ Pa, Dk \ Ca \ Eb, Xk, Xk \ Ca, Xk \ Ea, Xk \ Pa, Xk \ Ca \ Eb, Di \ Xj , Di \ Xj \ Ca, Di \ Xj \ Ea, Di \ Xj \ Pa, Di \ Xj \ Ca \ Eb, D0, D0 \ Ca, ; , for a, b 2 { 0, 1} and i, j, k 2 N+ with i > j 1. (ii) The LS-stable classes are ⌦ , Xk, X1 \ Pa, Dk, D1 \ Pa, Di \ Xj , Di \ X1 \ Pa, D0, ; , for a 2 { 0, 1} and i, j, k 2 N+ with i > j 1. (iii) The L0-stable classes are ⌦ , C0, Dk, Dk \ C0, D0, D0 \ C0, ; , for k 2 N+. (iv) The L1-stable classes are ⌦ , E1, Dk, Dk \ E1, D0, D0 \ C1, ; , for k 2 N+. (v) The L-stable classes are ⌦ , Dk, D0, ; , for k 2 N+. (vii) The S-stable classes are ⌦ , X1 \ Pa, D0, ; , for a 2 { 0, 1}. (viii) The Tc-stable classes are ⌦ , Ca, Ea, P0, Ca \ Eb, D0, D0 \ Ca, ; , for a, b 2 { 0, 1} (ix) The T0-stable classes are ⌦ , C0, D0, D0 \ C0, ; . (x) The T1-stable classes are ⌦ , E1, D0, D0 \ C1, ; .
(xi) The ⌦ -stable classes are ⌦ , D0, ; .