---
abstract: 'The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way.'
address:
- |
    LAMSADE – CNRS\
    Université Paris-Dauphine\
    Place du Maréchal de Lattre de Tassigny\
    75775 Paris Cedex 16\
    France
- |
    University of Luxembourg\
    Computer Science and Communications Research Unit\
    6, rue Richard Coudenhove-Kalergi\
    L–1359 Luxembourg\
    Luxembourg
- |
    University of Luxembourg\
    Mathematics Research Unit\
    6, rue Richard Coudenhove-Kalergi\
    L–1359 Luxembourg\
    Luxembourg
author:
- Miguel Couceiro
- Erkko Lehtonen
- Karsten Schölzel
title: A complete classification of equational classes of threshold functions included in clones
---

Introduction and preliminaries
==============================

Introduction
------------

Two approaches to characterize properties of Boolean functions have been considered recently: one in terms of functional equations [@EFHH], another in terms of relational constraints [@Pippenger]. As it turns out, these two approaches have the same expressive power in the sense that they characterize the same properties (classes) of Boolean functions, which can be described as initial segments of the so-called “minor” relation between functions: for two functions $f$ and $g$ of several variables, $f$ is said to be a minor of $g$ if $f$ can be obtained from $g$ by identifying variables, permuting variables, or adding inessential variables (see Subsection \[susec:MinorsConstraints\]). Furthermore, a class is characterizable by a finite number of functional equations if and only if it is characterizable by a finite number of relational constraints (see, e.g., [@CF; @Pippenger]). For the sake of simplifying the presentation of constructions and proofs, we will focus on the approach by relational constraints.

Several properties of functions can be charaterized by relational constraints (or, equivalently, by functional equations. In fact, uncountably many properties are expressible by such objects, even in the simplest interesting case of functions of several variables, i.e., the Boolean functions (see [@CP; @Pippenger]). Classical examples of such properties include idempotency, monotonicity and linearity. More contemporary examples include submodularity, supermodularity and the combination of the two, i.e., modularity (see, e.g., [@CouMar; @Lovasz; @Singer; @Topkis]).

Another noteworthy example is thresholdness that is the property of those Boolean functions whose true points can be separated from the false points by a hyperplane when considered as elements of the $n$-dimensional real space ${\mathbb{R}}^n$. Threshold functions have been widely studied in the literature on Boolean functions, switching theory, system reliability theory, game theory, etc.; for background see, e.g., [@Isbell; @Muroga; @Peleg1; @Peleg2; @Taylor; @Winder].

Despite being a property expressible by relational constraints, thresholdness cannot be captured by a finite set of relational constraints (see Hellerstein [@Hellerstein]). However, by imposing additional conditions such as linearity or preservation of componentwise conjunctions or disjunctions of tuples, the resulting classes of threshold functions may become characterizable by a finite number of relational constraints. In fact, these examples can be obtained from the class of threshold functions by intersecting it with certain clones, namely, those of linear functions, conjunctions and disjunctions, respectively. (Recall that a clone is a class of functions that contains all projections and is closed under functional composition.) Another noteworthy and well-known example of such an intersection is the class of “majority games”, which results as the intersection with the clone of self-dual monotone functions. The natural question is then: Is the class of majority games characterizable by a finite number of relational constraints?

In this paper we answer negatively to this question. In fact, we will determine, for each clone of Boolean functions, whether its intersection with the class of threshold functions is finitely characterizable by relational constraints. Moreover, we provide finite or infinite characterizing sets of relational constraints accordingly.

The paper is organized as follows. In the remainder of this section, we recall basic notions and results that will be needed throughout the paper. The main results are presented in Section \[sec:main\], in particular, the classification of all intersections $C \cap {T}$, where $C$ is a clone and ${T}$ is the class of all threshold functions, as well as the corresponding characterizing set of relational constraints. For the reader’s convenience, the constructions needed for the main results will be left for Section \[sec:constructions\]. One of the main tools in our proof is Taylor and Zwicker’s [@Taylor] theorem on the existence of a $k$-asummable function that is not $(k+1)$-asummable. In Section \[sec:magic\], we slightly refine Taylor and Zwicker’s result and show how the classes of functions characterizable by the relational constraints that arise in our current work are related to each other. Appendix \[App:Post\] provides a list of the clones of Boolean functions and relations characterizing them.

Boolean functions
-----------------

Throughout the paper, we denote the set $\{1, \dots, n\}$ by ${[{n}]}$ and the set $\{0, 1\}$ by ${\mathbb{B}}$. A *Boolean function* is a map $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ for some positive integer $n$ called the *arity* of $f$. Typical examples of Boolean functions include

-   the $n$-ary $i$-th *projection* ($i \in {[{n}]}$) $e^{(n)}_i \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $(a_1, \dots, a_n) \mapsto a_i$;

-   *negation* ${\overline{\cdot}} \colon {\mathbb{B}}\to {\mathbb{B}}$, ${\overline{0}} = 1$, ${\overline{1}} = 0$;

-   *conjunction* $\wedge \colon {\mathbb{B}}^2 \to {\mathbb{B}}$, $x \wedge y = 1$ if and only if $x = y = 1$;

-   *disjunction* $\vee \colon {\mathbb{B}}^2 \to {\mathbb{B}}$, $x \vee y = 0$ if and only if $x = y = 0$;

-   *modulo-$2$ addition* $\oplus \colon {\mathbb{B}}^2 \to {\mathbb{B}}$, $x \oplus y = (x + y) \bmod 2$.

The set of all Boolean functions is denoted by $\Omega$ and the set of all projections is denoted by $I_c$.

The preimage ${{f}^{-1}(1)}$ of $1$ under $f$ is referred to as the set of *true points*, while ${{f}^{-1}(0)}$ is referred to as the set of *false points*.

The $i$-th variable of a Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ is said to be *essential* in $f$, or that $f$ depends on $x_i$, if there are $a_1, \ldots, a_{i-1},a_{i+1}, \ldots,a_n \in {\mathbb{B}}$ such that $$f(a_1, \ldots, a_{i-1},0,a_{i+1}, \ldots, a_n) \neq f(a_1, \ldots, a_{i-1}, 1, a_{i+1}, \ldots, a_n).$$

The *dual* of a Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ is the function ${{f}^{\mathrm{d}}} \colon {\mathbb{B}}^n \to {\mathbb{B}}$ given by $${{f}^{\mathrm{d}}}(x_1, \dots, x_n)
= {\overline{f({\overline{x}}_1, \dots, {\overline{x}}_n)}}.$$ A function $f$ is *self-dual* if $f = {{f}^{\mathrm{d}}}$.

If $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ and $g_1, \dots, g_n \colon {\mathbb{B}}^m \to {\mathbb{B}}$, then the *composition* of $f$ with $g_1, \dots, g_n$ is the function $f(g_1, \dots, g_n) \colon {\mathbb{B}}^m \to {\mathbb{B}}$ given by $$f(g_1, \dots, g_n)(\aa) = f(g_1(\aa), \dots, g_n(\aa))$$ for all $\aa \in {\mathbb{B}}^m$. A *clone* of Boolean functions is a subset $C$ of the set $\Omega$ of all Boolean functions that satisfies the following two conditions:

-   $I_c \subseteq C$, i.e., $C$ contains all projections,

-   if $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $g_1, \dots, g_n \colon {\mathbb{B}}^m \to {\mathbb{B}}$ and $f, g_1, \dots, g_n \in C$, then $f(g_1, \dots, g_n) \in C$, i.e., $C$ is closed under composition.

The clones of Boolean functions were completely described by Post [@Post], and they are often referred to as *Post’s classes.* We provide a list of all clones of Boolean functions in Appendix \[App:Post\].

Minors and relational constraints {#susec:MinorsConstraints}
---------------------------------

We will denote tuples in ${\mathbb{B}}^m$ by boldface letters and their entries with corresponding italic letters, e.g., $\mathbf{a} = (a_1, \dots, a_m)$. Tuples $\mathbf{a} \in {\mathbb{B}}^m$ may be viewed as mappings $\mathbf{a} \colon {[{m}]} \to {\mathbb{B}}$, $i \mapsto a_i$. With this convention, given a map $\sigma \colon {[{n}]} \to {[{m}]}$, we can write the tuple $(a_{\sigma(1)}, \dots, a_{\sigma(n)})$ as $\mathbf{a} \circ \sigma$, or simply $\mathbf{a} \sigma$.

A function $f \colon {\mathbb{B}}^m \to {\mathbb{B}}$ is a *minor* of another function $g \colon {\mathbb{B}}^n \to {\mathbb{B}}$ if there exists a map $\sigma \colon {[{n}]} \to {[{m}]}$ such that $f(\mathbf{a}) = g(\mathbf{a} \sigma)$ for all $\mathbf{a} \in {\mathbb{B}}^m$; in this case we write $f \leq g$. Functions $f$ and $g$ are *equivalent,* denoted $f \equiv g$, if $f \leq g$ and $g \leq f$. In other words, $f$ is a minor of $g$ if $f$ can be obtained from $g$ by permutation of arguments, addition and deletion of inessential arguments and identification of arguments. Functions $f$ and $g$ are equivalent if each one can be obtained from the other by permutation of arguments and addition and deletion of inessential arguments.

The minor relation $\leq$ is a quasi-order (i.e., a reflexive and transitive relation) on the set of all Boolean functions, and the relation $\equiv$ is indeed an equivalence relation. For further background see, e.g., [@CL1; @CL2; @CP; @EFHH; @Pippenger] In what follows, we shall consider minors of the following special form. Let $n \geq 2$, and let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. For any two-element subset $I$ of ${[{n}]}$, we define the function $f_I \colon {\mathbb{B}}^{n-1} \to {\mathbb{B}}$ by the rule $f_I(\aa) = f(\aa \delta_I)$ for all $\aa \in {\mathbb{B}}^{n-1}$, where $\delta_I \colon {[{n}]} \to {[{n-1}]}$ is given by the rule $$\label{eq:deltaI}
\delta_I(i) =
\begin{cases}
i, & \text{if $i < \max I$,} \\
\min I, & \text{if $i = \max I$,} \\
i - 1, & \text{if $i > \max I$.}
\end{cases}$$ In other words, if $I = \{i, j\}$ with $i < j$, then $$f_I(a_1, \dots, a_{n-1}) = f(a_1, \dots, a_{j-1}, a_i, a_j, \dots, a_{n-1}).$$ Note that $a_i$ occurs twice on the right side of the above equality: both at the $i$-th and at the $j$-th position. The function $f_I$ will be referred to as an *identification minor* of $f$.

It was shown by Pippenger [@Pippenger] that the classes of functions closed under taking minors are characterizable by so-called relational constraints. We will briefly survey some results which we will use hereinafter. An $m$-ary *relational constraint* is a couple $(R, S)$ of $m$-ary relations $R$ (the *antecedent*) and $S$ (the *consequent*) on ${\mathbb{B}}$ (i.e., $R, S \subseteq {\mathbb{B}}^m$). We denote the antecedent and the consequent of a relational constraint $Q$ by $R(Q)$ and $S(Q)$, respectively. If both $R(Q)$ and $S(Q)$ equal the binary equality relation, then $Q$ is called the binary *equality constraint*. Furthermore, we refer to constraints with empty antecedent and empty consequent as *empty constraints*, and to constraints where the antecedent and consequent are the full relation ${\mathbb{B}}^m$, for some $m\geq 1$, as *full constraints*. The set of all relational constraints is denoted by $\Theta$.

A function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ *preserves* an $m$-ary relational constraint $(R, S)$, denoted $f \triangleright (R, S)$, if for every $\mathbf{a}^{1}, \dots, \mathbf{a}^{n} \in R$, we have $f(\mathbf{a}^1, \dots, \mathbf{a}^n) \in S$. (Regarding tuples $\mathbf{a}^i$ as unary maps, $f(\mathbf{a}^1, \dots, \mathbf{a}^n)$ denotes the $m$-tuple whose $i$-th entry is $f(\mathbf{a}^1, \dots, \mathbf{a}^n)(i) = f(a^1_i, \dots, a^n_i)$.)

The preservation relation gives rise to a Galois connection between functions and relational constraints that we now briefly describe; for further background, see [@C; @CP; @Pippenger]. Define $\operatorname{cPol}\colon \mathcal{P}(\Theta) \to \mathcal{P}(\Omega)$, $\operatorname{cInv}\colon \mathcal{P}(\Omega) \to \mathcal{P}(\Theta)$ by $$\begin{aligned}
\operatorname{cPol}(\mathcal{Q}) &= \{f \in \Omega : \text{$f \triangleright Q$ for every $Q \in \mathcal{Q}$}\}, \\
\operatorname{cInv}(\mathcal{F}) &= \{Q \in \Theta : \text{$f \triangleright Q$ for every $f \in \mathcal{F}$}\}.\end{aligned}$$ We say that a set $\mathcal{F}$ of functions is *characterized* by a set $\mathcal{Q}$ of relational constraints if $\mathcal{F} = \operatorname{cPol}(\mathcal{Q})$. Dually, $\mathcal{Q}$ is *characterized* by $\mathcal{F}$ if $\mathcal{Q} = \operatorname{cInv}(\mathcal{F})$. In other words, sets of functions characterizable by relational constraints are exactly the fixed points of $\operatorname{cPol}\circ \operatorname{cInv}$, and, dually, sets of relational constraints characterizable by functions are exactly the fixed points of $\operatorname{cInv}\circ \operatorname{cPol}$.

Preservation of a relational constraint generalizes the notion of preservation of a relation, as in the classical $\mathrm{Pol}$–$\mathrm{Inv}$ theory of clones and relations, which establishes that the clones on finite sets are exactly the classes of functions that are characterized by relations (see [@BKKR; @Geiger]). In this framework, a function $f$ preserves a relation $R$ if and only if $f$ preserves the relational constraint $(R, R)$. Hence, clones are exactly the classes that are characterized by relational constraints of the form $(R, R)$ for some relation $R$.

The following result reassembles various descriptions of the Galois closed sets of functions, which can be found in [@CP; @EFHH; @Pippenger].

\[thm:characterizablefunctions\] Let $\mathcal{F}$ be a set of functions. The following are equivalent.

1.  \[thm:characterizablefunctions:item1\] $\mathcal{F}$ is closed under taking minors.

2.  \[thm:characterizablefunctions:item2\] $\mathcal{F}$ is characterizable by relational constraints.

3.  \[thm:characterizablefunctions:item3\] $\mathcal{F}$ is of the form $$\operatorname{forbid}(A) := \{f \in \Omega : \text{$g \nleq f$ for all $g \in A$}\}$$ for some antichain $A$ with respect to the minor relation $\leq$.

It follows from the equivalence of \[thm:characterizablefunctions:item1\] and \[thm:characterizablefunctions:item2\] in Theorem \[thm:characterizablefunctions\] that the union and the intersection of classes that are characterizable by relational constraints are characterizable by relational constraints.

Note that the antichain $A$ in item \[thm:characterizablefunctions:item3\] of Theorem \[thm:characterizablefunctions\] is unique up to equivalence. In fact, $A$ can be chosen among the minimal elements of $\Omega \setminus \mathcal{F}$; the elements of $A$ are called *minimal forbidden minors for $\mathcal{F}$*.

As we will see, there are classes of functions that, even though characterizable by relational constraints, are not characterized by any finite set of relational constraints. A set of functions is *finitely characterizable* if it is characterized by a finite set of relational constraints.

The following theorem is a refinement of Theorem \[thm:characterizablefunctions\] and provides a description for finitely characterizable classes.

\[thm:finitelycharacterizablefunctions\] Let $\mathcal{F}$ be a set of functions. The following are equivalent.

1.  $\mathcal{F}$ is finitely characterizable.

2.  $\mathcal{F}$ is of the form $\operatorname{forbid}(A)$ for some finite antichain $A$ with respect to the minor relation $\leq$.

The Galois closed sets of relational constraints were likewise described by Pippenger [@Pippenger]; this description was extended to arbitrary, possibly infinite, underlying sets in [@CF]. We shall briefly survey Pippenger’s description of the Galois closed sets of constraints.

An $m$-ary relational constraint $(R,S)$ is a *simple minor* of an $(m+p)$-ary relational constraint $(R',S')$ if there is $h \colon \{1, \ldots, n\} \to \{1, \ldots, m+p\}$ such that $$\begin{aligned}
  R
   \left(\begin{array}{c}
   x_1\\
   \vdots \\
   x_m\\
   \end{array}\right)
  &
\quad  \iff  \quad 
\exists x_{m+1} \ldots \exists x_{m+p} \quad 
R'
   \left(\begin{array}{c}
   x_{h(1)}\\
   \vdots \\
   x_{h(n)}\\
   \end{array}\right)
\intertext{and}
  S
   \left(\begin{array}{c}
   x_1\\
   \vdots \\
   x_m\\
   \end{array}\right)
  &
\quad \iff \quad 
\exists x_{m+1} \ldots \exists x_{m+p} \quad 
S'
   \left(\begin{array}{c}
   x_{h(1)}\\
   \vdots \\
   x_{h(n)}\\
   \end{array}\right).
 \end{aligned}$$

Note that simple minors subsume the notions of permutation, diagonalization and projection of arguments; for background see [@CF; @Pippenger].

A constraint $(R,S)$ is obtained from a constraint $(R',S)$ by *restricting the antecedent* if $R\subseteq R'$. Likewise, $(R,S)$ is obtained from a constraint $(R,S')$ by *extending the consequent* if $S\supseteq S'$. A constraint $(R,S\cap S')$ is said to be obtained from $(R,S)$ and $(R, S')$ by intersecting consequents.

A set $\mathcal{Q}$ of relational constraints is said to be *minor-closed* if it contains the binary equality constraint, the unary empty constraint, and it is closed under taking simple minors, restricting antecedents, and extending and intersecting consequents.

We can now state Pippenger’s [@Pippenger] description of the Galois closed sets of relational constraints.

\[thm:characterizableconstraints\] Let $\mathcal{Q}$ be a set of relational constraints. The following are equivalent.

1.  \[thm:characterizableconstraints:item1\] $\mathcal{Q}$ is characterizable by some set of functions.

2.  \[thm:characterizableconstraints:item2\] $\mathcal{Q}$ is minor-closed.

The following lemma provides a noteworthy tool for showing that certain classes of threshold functions are not finitely characterizable.

\[lemma:finiteDescendingChainIffFinitelyCharacterizable\] Let $C$ and $C_i$ for all $i \geq 1$ be classes of functions that are closed under taking minors, such that $C  = \bigcap_{i \geq 1} C_i$, and $C_{i+1} \subseteq C_i$ for all $i \geq 1$. If $C$ is finitely characterizable by constraints, then there exists $\ell \in {\mathbb{N}}$ such that $C_j = C_\ell$ for all $j \geq \ell$.

By Theorem \[thm:characterizablefunctions\], each minor-closed class $C_i$ is characterized by some set $\mathcal{Q}_i$ of relational constraints, i.e., $C_i = \operatorname{cPol}\mathcal{Q}_i$ for all $i \geq 1$.

Assume that $C$ is finitely characterizable. Then there is some finite set $\mathcal{P}$ of constraints with $C = \operatorname{cPol}\mathcal{P}$, and thus $\operatorname{cInv}C = \operatorname{cInv}\operatorname{cPol}\mathcal{P}$. Since $$C = \bigcap_{i \geq 1} \operatorname{cPol}\mathcal{Q}_i = \operatorname{cPol}\bigcup_{i \geq 1} \mathcal{Q}_i$$ we can construct each $P \in \mathcal{P}$ from the constraints in $\bigcup_{i \geq 1} \mathcal{Q}_i$. Since the constraints are finite, all such constructions are finite. In particular, only a finite number of constraints from $\bigcup_{i \geq 1} \mathcal{Q}_i$ are used for each $P \in \mathcal{P}$. Since $\mathcal{P}$ is finite, this implies that only a finite number of constraints are needed to construct all $P \in \mathcal{P}$. Therefore $$C = \operatorname{cPol}\mathcal{P} \supseteq \operatorname{cPol}\bigcup_{i = 1}^l \mathcal{Q}_i
= \bigcap_{i=1}^l \operatorname{cPol}\mathcal{Q}_i
= \operatorname{cPol}\mathcal{Q}_l = C_l$$ holds for some $l \in {\mathbb{N}}$. Now this implies that for any $j \geq l$, $$C \subseteq C_j \subseteq C_l \subseteq C$$ and consequently $C = C_j = C_l$ for all $j \geq l$.

Main results: classification and characterizations of Galois closed sets of threshold functions {#sec:main}
===============================================================================================

Motivation
----------

A *threshold function* is a Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ such that there exist *weights* $w_1, \dots, w_n \in {\mathbb{R}}$ and a *threshold* $t \in {\mathbb{R}}$ fulfilling $$f(x_1, \dots, x_n) = 1 \iff \sum_{i=1}^n w_i x_i \geq t.$$ Another, equivalent, definition is the following. An $n$-ary Boolean function $f$ is called a *threshold function* if there is a hyperplane in ${\mathbb{R}}^n$ strictly separating the true points of $f$ from the false points of $f$, considered as elements of ${\mathbb{R}}^n$. The set of all threshold functions is denoted by ${T}$.

The class of threshold functions has remarkable invariance properties. For instance, it is closed under taking negations and duals (see Lemma \[lem:dualBl\]). Moreover, the class of threshold functions is also closed under taking minors of its members; hence it is characterizable by relational constraints by Theorem \[thm:characterizablefunctions\]. However, no finite set of relational constraints suffices.

\[thm:Hell\] The class of threshold functions is not finitely characterizable.

Imposing some additional conditions on threshold functions, we may obtain proper subclasses of ${T}$ that are finitely characterizable. Easy examples arise from the intersections of ${T}$ with the clones $L$, $\Lambda$, $V$ (see Appendix \[App:Post\]). However, as we have seen, other intersections $C \cap T$ may fail to be finitely characterizable, e.g., for $C = \Omega$.

This fact gives rise to the following problem.

Which clones $C$ of Boolean functions have the property that $C \cap {T}$ is finitely characterizable?

In the following subsection we present a solution to this problem.

Classification and characterizations of intersections of the class of threshold functions with clones
-----------------------------------------------------------------------------------------------------

We start by observing that $$L \cap {T}= \Omega(1), \qquad
\Lambda \subseteq {T}, \qquad
V \subseteq {T},$$ from which it follows that the intersection $C \cap {T}$ is a clone for any clone $C$ contained in one of $L$, $V$ and $\Lambda$. Hence, the characterization of $C \cap {T}$ for any such clone $C$ is given by the relational constraint $(R, R)$, where $R$ is the relation characterizing $C \cap {T}$ given in Appendix \[App:Post\].

We proceed to characterizing the intersections $C \cap {T}$ for the remaining clones $C$; as we will see, none of these is finitely characterizable. A characterization of the class ${T}$ of all threshold functions (i.e., for $C = \Omega$) is easily obtained with the help of the notion of asummability.

For $k \geq 2$, a Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ is *$k$-asummable* if for any $m \in \{2, \dots, k\}$ and for all $\aa_1, \dots, \aa_m \in f^{-1}(0)$ and $\bb_1, \dots, \bb_m \in f^{-1}(1)$, it holds that $$\aa_1 + \dots + \aa_m \neq \bb_1 + \dots + \bb_m.$$ (Addition here is standard vector addition in ${\mathbb{R}}^n$.) A function is *asummable* if it is $k$-asummable for all $k \geq 2$. It is well known that asummability characterizes threshold functions; see [@Chow; @Elgot; @Muroga].

\[thm:thresholdasummable\] A Boolean function is threshold if and only if it is asummable.

Define for $n \geq 1$, the $2n$-ary relational constraint $B_n$ as $$\begin{aligned}
R(B_n) & := \{ (x_1, \dots, x_{2n}) \in {\mathbb{B}}^{2n} : \sum_{i=1}^n x_i = \sum_{i=n+1}^{2n} x_i \} \\
S(B_n) & := {\mathbb{B}}^{2n} \setminus \{ (\underbrace{0,\dots,0}_{n},\underbrace{1,\dots,1}_n), 
                                  (\underbrace{1,\dots,1}_{n},\underbrace{0,\dots,0}_n) \}. \end{aligned}$$ Note that in the definition of $R(B_n)$ we employ the usual addition of real numbers. Denoting by $w(\aa)$ the *Hamming weight* of a tuple $\aa \in {\mathbb{B}}^n$ (i.e., the number of nonzero entries in $\aa$), we can equivalently define $R(B_n)$ as $\{(x_1, \dots, x_{2n}) \in {\mathbb{B}}^{2n} : w(x_1, \dots, x_n) = w(x_{n+1}, \dots, x_{2n})\}$.

\[lem:PolBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ and $\ell \geq 2$. Then $\aa_1 + \dots + \aa_\ell \neq \bb_1 + \dots + \bb_\ell$ for all $\aa_1, \dots, \aa_\ell \in f^{-1}(0)$ and $\bb_1, \dots, \bb_\ell \in f^{-1}(1)$ if and only if $f$ preserves $B_\ell$.

Assume first that $f$ does not preserve $B_\ell$. Then there exists a matrix $$M = \begin{pmatrix}
  m_1^1 & m_2^1 & \dots & m_n^1 \\
  m_1^2 & m_2^2 & \dots & m_n^2 \\
  \vdots & \vdots &  & \vdots \\
  m_1^{2 \ell} & m_2^{2 \ell} & \dots & m_n^{2 \ell}
\end{pmatrix} = \begin{pmatrix} 
  M^1 \\
  M^2 \\
  \vdots \\
  M^{2 \ell}
\end{pmatrix}
= (M_1, M_2, \dots, M_n),$$ i.e., $M^1, \dots, M^{2 \ell} \in {\mathbb{B}}^n$ are the rows of $M$, and $M_1, \dots, M_n \in {\mathbb{B}}^{2 \ell}$ are the columns of $M$, such that

-   $M_1, \dots, M_n \in R(B_\ell)$, and

-   $\zz := g(M_1, \dots, M_n) := \begin{pmatrix} g(M^1) \\ \vdots \\ g(M^{2 \ell}) \end{pmatrix} \notin S(B_\ell)$.

Thus $\zz \in \{ (\underbrace{0,\dots,0}_l,\underbrace{1,\dots,1}_l), 
(\underbrace{1,\dots,1}_l,\underbrace{0,\dots,0}_l)\}$. As $B_\ell$ is invariant under swapping the first $\ell$ rows with the last $\ell$ rows, we can assume that $\zz = (\underbrace{0, \dots, 0}_\ell, \underbrace{1, \dots, 1}_\ell)$. Then $M^1, \dots, M^\ell \in f^{-1}(0)$ and $M^{\ell + 1}, \dots, M^{2 \ell} \in f^{-1}(1)$, and $M^1 + \dots + M^\ell = M^{\ell + 1} + \dots + M^{2 \ell}$ by the definition of $B_\ell$.

Assume then that there exist $\aa_1, \dots, \aa_\ell \in f^{-1}(0)$ and $\bb_1, \dots, \bb_\ell \in f^{-1}(1)$ such that $\aa_1 + \dots + \aa_\ell = \bb_1 + \dots + \bb_\ell$. Let $M$ be the $2 \ell \times n$ matrix whose rows are $\aa_1, \dots, \aa_\ell, \bb_1, \dots, \bb_\ell$. The columns of $M$ are tuples in $R(B_\ell)$, but $f(M) = (\underbrace{0, \dots, 0}_\ell, \underbrace{1, \dots, 1}_\ell) \notin S(B_\ell)$. We conclude that $f$ does not preserve $B_\ell$.

Now it is easy to define a set of relational constraints that characterizes $k$-asummable functions. For $k \geq 2$, let $\mathcal{A}_k := \{B_n : 2 \leq n \leq k\}$.

\[lem:k-asummable\] Let $k \geq 2$. A Boolean function $f$ is $k$-asummable if and only if $f \in \operatorname{cPol}(\mathcal{A}_k)$.

Follows immediately from the definition of $k$-asummability and Lemma \[lem:PolBl\].

Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. The following are equivalent.

1.  \[cor:thr:item:thr\] $f$ is a threshold function.

2.  \[cor:thr:item:Ak\] $f \in \bigcap_{k \geq 2} \operatorname{cPol}(\mathcal{A}_k)$.

3.  \[cor:thr:item:Bn\] $f \in \operatorname{cPol}(\{B_n : n \geq 2\})$.

The equivalence of \[cor:thr:item:thr\] and \[cor:thr:item:Ak\] follows immediately from Theorem \[thm:thresholdasummable\] and Lemma \[lem:k-asummable\]. Conditions \[cor:thr:item:Ak\] and \[cor:thr:item:Bn\] are equivalent, because $$\bigcap_{k \geq 2} \operatorname{cPol}(\mathcal{A}_k)
= \operatorname{cPol}\Bigl( \bigcup_{k \geq 2} \mathcal{A}_k \Bigr)
= \operatorname{cPol}\Bigl( \bigcup_{k \geq 2} \{B_n : 2 \leq n \leq k\} \Bigr)
= \operatorname{cPol}(\{B_n : n \geq 2\}).
\qedhere$$

Since $\mathcal{A}_k \subseteq \mathcal{A}_k \cup \{B_{k+1}\} = \mathcal{A}_{k+1}$, it is clear that $\operatorname{cPol}(\mathcal{A}_{k+1}) \subseteq \operatorname{cPol}(\mathcal{A}_k)$ for all $k \geq 2$. Taylor and Zwicker have shown in [@Taylor] that for every $k \geq 2$, there exist $k$-asummable functions that are not $(k+1)$-asummable. Hence these inclusions are strict for every $k$.

\[theorem:strictAkInclusions\] For all $k \geq 2$, $\operatorname{cPol}(\mathcal{A}_{k+1}) \subset \operatorname{cPol}(\mathcal{A}_k)$.

\[thm:characterization\] The set $\operatorname{cPol}(\{ B_n : n \geq 2 \})$ is the class of all threshold functions. Moreover, for every clone $C$, the subclass $C \cap {T}$ of threshold functions is characterized by the set $\{B_n : n \geq 2\} \cup \mathcal{Q}_C$, where $\mathcal{Q}_C$ is the set of relational constraints characterizing the clone $C$, as given in Appendix \[App:Post\].

From Theorems \[theorem:strictAkInclusions\] and \[thm:characterization\] it follows that $${T}= \bigcap_{k \geq 2} \operatorname{cPol}(\mathcal{A}_k) \subset \dots \subset \operatorname{cPol}(\mathcal{A}_{\ell+1}) \subset \operatorname{cPol}(\mathcal{A}_\ell) \subset \dots \subset \operatorname{cPol}(\mathcal{A}_2)$$ holds for all $\ell \geq 3$, i.e., the sets $\operatorname{cPol}(\mathcal{A}_k)$ with $k \geq 2$ form an infinite descending chain, whose intersection is the set ${T}$ of all threshold functions.

Theorem \[thm:characterization\] provides an infinite set of relational constraints characterizing the set $C \cap {T}$ for each clone $C$. As Theorem \[thm:classification\] will reveal, the characterization provided is optimal for the clones not contained in $L$, $V$ or $\Lambda$ in the sense that for such clones $C$, the set $C \cap {T}$ is not finitely characterizable by relational constraints.

In order to proceed, we need the following lemma. Its proof is somewhat technical and is deferred to Section \[sec:constructions\].

\[lem:GCf\]

Let $f$ be a Boolean function, and let $C \in \{SM, M_cU_\infty, M_cW_\infty\}$. There exists a Boolean function $G_C(f)$ that satisfies the following conditions:

1.  $G_C(f) \in C$,

2.  for all $n \geq 2$, $f \in \operatorname{cPol}B_n$ if and only if $G_C(f) \in \operatorname{cPol}B_n$.

This brings together Corollaries \[cor:GSM\], \[cor:GMcUinfty\] and \[cor:GMcWinfty\], which will be proved in Section \[sec:constructions\].

\[rem:OldTheorem-theorem:strictCcapAkInclusions\] Lemma \[lem:GCf\] gives rise to a noteworthy refinement of Theorem \[theorem:strictAkInclusions\]. Indeed, by Theorem \[theorem:strictAkInclusions\], there is some $f \in \operatorname{cPol}(\mathcal{A}_k) \setminus \operatorname{cPol}(\mathcal{A}_{k+1})$ and, by Lemma \[lem:GCf\], there exists a function $G_E(f) \in E \subseteq C$ satisfying $G_{E}(f) \in \operatorname{cPol}(\mathcal{A}_k) \setminus \operatorname{cPol}(\mathcal{A}_{k+1})$. This implies that $G_{E}(f) \in (C \cap \operatorname{cPol}(\mathcal{A}_k)) \setminus (C \cap \operatorname{cPol}(\mathcal{A}_{k+1}))$ and thus $C \cap \operatorname{cPol}(\mathcal{A}_{k+1}) \subset C \cap \operatorname{cPol}(\mathcal{A}_k)$ for all $k \geq 2$.

This shows that if $C$ is a clone of Boolean functions satisfying $E \subseteq C$ for some $E \in \{ SM, M_cU_\infty, M_cW_\infty \}$, then $C \cap \operatorname{cPol}(\mathcal{A}_{k+1}) \subset C \cap \operatorname{cPol}(\mathcal{A}_k)$ for all $k \geq 2$.

= \[circle, fill=black,scale=0.5\] = \[scale=2,draw=none, fill=none, label distance=-4\] (P2) \[label=above:$\Omega$\] at (7.0 ,10.0) ; (T0) \[label=above left:$T_0$\] at (7.0-1.5,10.0-.5) ; (T1) \[label=above right:$T_1$\] at (7.0+1.0,10.0-.5) ; (T) at (7.0-.5,10.0-1.0) ; (M) \[label=above left:$M$\] at (6.76 ,9.38) ; (T0M) at (7.23-1.5, 9.51-.5) ; (T1M) at (6.76+1.0, 9.38-.5) ; (TM) at (7.23-.5, 9.51-1.0) ; (L) \[label=above right:$L$\] at (7.0 , 5.2) ; (T0L) at (7.0-1.5, 5.2-.5) ; (T1L) at (7.0+1.0, 5.2-.5) ; (TL) at (7.0-.5, 5.2-1.0) ; (AV) at (7.0 , 3.0) ; (T0AV) at (7.0-1.5, 3.0-.5) ; (T1AV) at (7.0+1.0, 3.0-.5) ; (TAV) at (7.0-.5, 3.0-1.0) ; (P21) \[label=right:[$\Omega(1)$]{}\] at (7.0,3.8) ; (S) \[label=right:$S$\] at (6.85,7.0) ; (SL) at (6.75,4.7) ; (SP21) at (6.65,2.5) ; (ST) at (6.5,6.5) ; (SM) \[label=below left:$SM$\] at (6.15,6.0) ;

/in [ P2/T0, P2/T1, T0/T, T1/T, M/T0M, M/T1M, T0M/TM, T1M/TM, P2/M, T0/T0M, T1/T1M, T/TM, L/T0L, L/T1L, T0L/TL, T1L/TL, P2/L, T0/T0L, T1/T1L, T/ST, ST/TL, AV/T0AV, AV/T1AV, T0AV/TAV, T1AV/TAV, L/P21, P21/AV, T0L/T0AV, T1L/T1AV, TL/TAV, P2/S, S/ST, S/SL, L/SL, SL/TL, SL/SP21, P21/SP21, SP21/TAV, ST/SM, SM/TAV]{} () – ();

(DiffT0xT) at ( 1.0,-0.7); (DiffT0xM) at ( 2.0,-0.3); (DiffT0xTM) at ( 3.0,-1.0); (T02) \[label=left:$U_2$\] at (-0.1, 8.5) ; (T02T) at ($ (T02) + (DiffT0xT)  $) ; (T02M) at ($ (T02) + (DiffT0xM)  $) ; (T02TM) at ($ (T02) + (DiffT0xTM) $) ; (T03) \[label=left:$U_3$\] at ($ (T02) - ( 0.0, 1.0) $) ; (T03T) at ($ (T03) + (DiffT0xT)  $) ; (T03M) at ($ (T03) + (DiffT0xM)  $) ; (T03TM) at ($ (T03) + (DiffT0xTM) $) ; (T0H) \[draw=none, fill=none, scale=0.1\] at ($ (T02) - ( 0.0, 1.5) $) ; (T0HT) \[draw=none, fill=none, scale=0.1\] at ($ (T0H) + (DiffT0xT)  $) ; (T0HM) \[draw=none, fill=none, scale=0.1\] at ($ (T0H) + (DiffT0xM)  $) ; (T0HTM) \[draw=none, fill=none, scale=0.1\] at ($ (T0H) + (DiffT0xTM) $) ; (T0e) \[label=left:$U_{\infty}$\] at ($ (T02) - ( 0.0, 2.3) $) ; (T0eT) at ($ (T0e) + (DiffT0xT)  $) ; (T0eM) at ($ (T0e) + (DiffT0xM)  $) ; (T0eTM) \[label=right:$M_cU_{\infty}$\] at ($ (T0e) + (DiffT0xTM)  $) ;

\(A) \[label=below:$\Lambda$\] at (.5+3.5,3.7) ; (AT1) at ($ (A) + ( 1.0,-0.5) $) ; (AT0) at ($ (A) + (-1.5,-0.5) $) ; (AT) at ($ (A) + (-0.5,-1.0) $) ;

(DiffT1xT) at (-1.0,-0.7); (DiffT1xM) at (-2.0,-0.3); (DiffT1xTM) at (-3.0,-1.0); (T12) \[label=right:$W_2$\] at (13.6, 8.5) ; (T12T) at ($ (T12) + (DiffT1xT)  $) ; (T12M) at ($ (T12) + (DiffT1xM)  $) ; (T12TM) at ($ (T12) + (DiffT1xTM) $) ; (T13) \[label=right:$W_3$\] at ($ (T12) - ( 0.0, 1.0) $) ; (T13T) at ($ (T13) + (DiffT1xT)  $) ; (T13M) at ($ (T13) + (DiffT1xM)  $) ; (T13TM) at ($ (T13) + (DiffT1xTM) $) ; (T1H) \[draw=none, fill=none, scale=0.1\] at ($ (T12) - ( 0.0, 1.5) $) ; (T1HT) \[draw=none, fill=none, scale=0.1\] at ($ (T1H) + (DiffT1xT)  $) ; (T1HM) \[draw=none, fill=none, scale=0.1\] at ($ (T1H) + (DiffT1xM)  $) ; (T1HTM) \[draw=none, fill=none, scale=0.1\] at ($ (T1H) + (DiffT1xTM) $) ; (T1e) \[label=right:$W_{\infty}$\] at ($ (T12) - ( 0.0, 2.3) $) ; (T1eT) at ($ (T1e) + (DiffT1xT)  $) ; (T1eM) at ($ (T1e) + (DiffT1xM)  $) ; (T1eTM) \[label=left:$M_cW_{\infty}$\] at ($ (T1e) + (DiffT1xTM)  $) ;

\(V) \[label=below:$V$\] at (9.5,3.7) ; (VT0) at ($ (V) + (-1.0,-0.5) $) ; (VT1) at ($ (V) + ( 1.5,-0.5) $) ; (VT) at ($ (V) + ( 0.5,-1.0) $) ;

/in [ T02/T02T, T02/T02M, T02T/T02TM, T02M/T02TM, T03/T03T, T03/T03M, T03T/T03TM, T03M/T03TM, T0e/T0eT, T0e/T0eM, T0eT/T0eTM, T0eM/T0eTM, T12/T12T, T12/T12M, T12T/T12TM, T12M/T12TM, T13/T13T, T13/T13M, T13T/T13TM, T13M/T13TM, T1e/T1eT, T1e/T1eM, T1eT/T1eTM, T1eM/T1eTM, T02/T03, T02T/T03T, T02M/T03M, T02TM/T03TM, T03/T0H, T03T/T0HT, T03M/T0HM, T03TM/T0HTM, T12/T13, T12T/T13T, T12M/T13M, T12TM/T13TM, T13/T1H, T13T/T1HT, T13M/T1HM, T13TM/T1HTM, T0eM/AT0, T0eTM/AT, T1eM/VT1, T1eTM/VT, A/AT0, A/AT1, AT0/AT, AT1/AT, V/VT0, V/VT1, VT0/VT, VT1/VT, A/AV, AT0/T0AV, AT1/T1AV, AT/TAV, V/AV, VT0/T0AV, VT1/T1AV, VT/TAV, T02TM/SM, T12TM/SM, T0/T02, T0M/T02M, T/T02T, TM/T02TM, T1/T12, T1M/T12M, T/T12T, TM/T12TM]{} () – (); (M) edge \[out=215, in=70\] (A); (T1M) edge \[out=215, in=90\] (AT1); (M) edge \[out=325, in=110\] (V); (T0M) edge \[out=325, in=90\] (VT0);

/in [ T0H/T0e, T0HT/T0eT, T0HM/T0eM, T0HTM/T0eTM, T1H/T1e, T1HT/T1eT, T1HM/T1eM, T1HTM/T1eTM]{} () – ();

plot coordinates[ ($(AT0)   +(-1.5,-0.2)$) ($ (L)    +( 0.1, 0.4)$) ($(VT1)   +( 1.5,-0.2)$) ]{};

\[thm:classification\] Let $C$ be a clone of Boolean functions. The subclass $C \cap {T}$ of threshold functions is finitely characterizable if and only if $C$ is contained in one of the clones $L$, $V$, $\Lambda$.

This theorem is illustrated by Figure \[figure:PostsLattice\].

We have already observed that $C \cap {T}$ is finitely characterizable for every subclone $C$ of $L$, $V$ or $\Lambda$.

Now we consider all the other clones. Let $C$ be a clone such that $C \not\subseteq D$ for all $D \in \{L, V, \Lambda\}$. We can read off of Post’s lattice (see Figure \[figure:PostsLattice\]) that there is some $E \in \{SM, M_cU_\infty, M_cW_\infty\}$ such that $E \subseteq C$. It follows from Theorem \[theorem:strictAkInclusions\] and Lemma \[lem:GCf\] that for every $k \geq 2$, there exists a function $f_k \in E$ such that $f_k \in \operatorname{cPol}B_\ell$ whenever $2 \leq \ell \leq k$ and $f_k \notin \operatorname{cPol}B_{k+1}$. Note that $f_k \notin C \cap {T}$.

Suppose, on the contrary that $C \cap {T}$ is finitely characterizable. By Theorem \[thm:finitelycharacterizablefunctions\], $C \cap {T}$ is of the form $\operatorname{forbid}(A)$ for some finite antichain $A$ of minimal forbidden minors. Each one of the functions $f_k$ has a minor in $A$. Since $A$ is finite, there is an element $g \in A$ and an infinite set $S \subseteq {\mathbb{N}}$ such that $g \leq f_k$ for all $k \in S$. The function $g$ is not threshold, so there exists $p \in {\mathbb{N}}$ such that $p \geq 2$ and $g \notin \operatorname{cPol}B_p$. Being infinite, the set $S$ contains an element $q$ with $p \leq q$. Then we have $g \leq f_q$ and $f_q \in \operatorname{cPol}B_p$. We also have $g \in \operatorname{cPol}B_p$, because $\operatorname{cPol}B_p$ is closed under taking minors. This yields the desired contradiction.

Alternatively, Theorem \[thm:classification\] can be proved using Lemma \[lemma:finiteDescendingChainIffFinitelyCharacterizable\] and Remark \[rem:OldTheorem-theorem:strictCcapAkInclusions\].

As before if $C$ is a subclone of $L$, $V$ or $\Lambda$, then $C \cap {T}$ is finitely characterizable. As for any other clone $C$, we know (once again reading off of Post’s lattice) that there is some $E \in \{SM, M_cU_\infty, M_cW_\infty\}$ such that $E \subseteq C$. By Remark \[rem:OldTheorem-theorem:strictCcapAkInclusions\], we have $C \cap \operatorname{cPol}(\mathcal{A}_{k+1}) \subset C \cap \operatorname{cPol}(\mathcal{A}_k)$ for all $k \geq 2$. Furthermore, $$C \cap {T}= C \cap \bigcap_{n \geq 2} \operatorname{cPol}(\mathcal{A}_k)
 = \bigcap_{n \geq 2} (C \cap \operatorname{cPol}(\mathcal{A}_k)),$$ i.e., we have an infinite descending chain the intersection of which equals $C \cap {T}$. By Lemma \[lemma:finiteDescendingChainIffFinitelyCharacterizable\] we thus conclude that $C \cap {T}$ is not finitely characterizable.

Constructions {#sec:constructions}
=============

In order to prove Lemma \[lem:GCf\], we will construct from a given Boolean function $f$, for each $C \in \{S, M_c, SM, U_\infty, M_cU_\infty, M_cW_\infty \}$, a Boolean function $G_C(f)$ that satisfies the following conditions:

1.  $G_C(f) \in C$,

2.  for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_C(f) \in \operatorname{cPol}B_\ell$.

We do this step by step. We first construct functions $G_S(f)$ and $G_{M_c}(f)$ with the desired properties. Using these two constructions as building blocks, we can construct $G_{SM}$ as $G_{M_c}(G_S(f))$. Then we construct $G_{U_\infty}(f)$, and, building upon this, we finally get $G_{M_cU_\infty}(f) := G_{U_\infty}(G_{M_c}(f))$ and $G_{M_cW_\infty}(f) := {{(G_{M_cU_\infty}(f))}^{\mathrm{d}}}$.

Construction of $G_{S}(f)$ {#subsec:ST}
--------------------------

Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. Then we define $G_{S}(f) \colon {\mathbb{B}}^{n+1} \to {\mathbb{B}}$ by $$G_{S}(f)(x_1, \dots, x_{n+1}) = (x_{n+1} \wedge f(x_1, \dots, x_n)) \vee ({\overline{x}}_{n+1} \wedge {{f}^{\mathrm{d}}}(x_1, \dots, x_n)).$$

\[lemma:anytoS\] For any $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, the function $G_{S}(f)$ is self-dual.

Let $g := G_{S}(f)$. Then $$\begin{aligned}
  {{g}^{\mathrm{d}}}(\mathbf{x}, x_{n+1}) &=
  {\overline{({\overline{x}}_{n+1} \wedge f({\overline{\mathbf{x}}})) \vee ({\overline{{\overline{x}}}}_{n+1} \wedge {{f}^{\mathrm{d}}}({\overline{\mathbf{x}}}))}} \\
  &= (x_{n+1} \vee {{f}^{\mathrm{d}}}(\mathbf{x})) \wedge ({\overline{x}}_{n+1} \vee f(\mathbf{x})) \\
  &= (x_{n+1} \wedge {\overline{x}}_{n+1}) \vee (x_{n+1} \wedge f(\mathbf{x})) \vee ({{f}^{\mathrm{d}}}(\mathbf{x}) \wedge {\overline{x}}_{n+1}) \vee ({{f}^{\mathrm{d}}}(\mathbf{x}) \wedge f(\mathbf{x})) \\
  &= (x_{n+1} \wedge f(\mathbf{x})) \vee ({{f}^{\mathrm{d}}}(\mathbf{x}) \wedge {\overline{x}}_{n+1}) \\
  &= g(\mathbf{x}, x_{n+1}),
  \end{aligned}$$ where the second last equality holds since $${{f}^{\mathrm{d}}}(\mathbf{x}) \wedge f(\mathbf{x}) \leq (x_{n+1} \wedge f(\mathbf{x})) \vee ({{f}^{\mathrm{d}}}(\mathbf{x}) \wedge {\overline{x}}_{n+1})$$ for every $x_{n+1}$.

\[lemma:ST:fNotinBlimpliesgNotinBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. If $f \notin \operatorname{cPol}B_\ell$ for some $\ell \geq 2$, then $G_{S}(f) \notin \operatorname{cPol}B_\ell$.

Assume that $f \notin \operatorname{cPol}B_\ell$, and let $g := G_{S}(f)$. Then there are $\yy_1, \dots, \yy_n \in R(B_\ell)$ with $f(\yy_1, \dots, \yy_n) \notin S(B_\ell)$. Since $g(x_1, \dots, x_n, 1) = f(x_1, \dots, x_n)$, we have $$g(\yy_1,\dots,\yy_n,\11) = f(\yy_1,\dots,\yy_n) \notin S(B_\ell).$$ Since also $\11 \in R(B_\ell)$, we conclude that $g \notin \operatorname{cPol}B_\ell$.

\[lemma:ST:fInBlImpliesgInBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. If $f \in \operatorname{cPol}B_\ell$ for some $\ell \geq 2$, then $G_{S}(f) \in \operatorname{cPol}B_\ell$.

Let $g := G_{S}(f)$. Suppose, on the contrary, that $g \notin \operatorname{cPol}B_\ell$. Then there is some matrix $M$ given by $$M = \begin{pmatrix}
      m_1^1 & m_2^1 & \dots & m_{n+1}^1 \\
      m_1^2 & m_2^2 & \dots & m_{n+1}^2 \\
      \vdots & \vdots &  & \vdots \\
      m_1^{2\ell} & m_2^{2\ell} & \dots & m_{n+1}^{2\ell}
    \end{pmatrix} = \begin{pmatrix} 
      M^1 \\
      M^2 \\
      \vdots \\
      M^{2\ell}
    \end{pmatrix}
    = (M_1,M_2,\dots,M_{n+1}),$$ i.e., $M^1,\dots,M^{2\ell} \in {\mathbb{B}}^{n+1}$ are the rows of $M$, and $M_1,\dots,M_{n+1} \in {\mathbb{B}}^{2\ell}$ are the columns of $M$, such that

-   $M_1,\dots,M_{n+1} \in R(B_\ell)$, and

-   $\zz := g(M_1,\dots,M_{n+1}) := \begin{pmatrix} g(M^1) \\ \vdots \\ g(M^{2\ell}) \end{pmatrix} 
            \notin S(B_\ell)$.

Thus $\zz \in \{ (\underbrace{0,\dots,0}_\ell,\underbrace{1,\dots,1}_\ell), 
  (\underbrace{1,\dots,1}_\ell, \underbrace{0,\dots,0}_\ell)\}$. As $B_\ell$ is invariant under swapping the first $\ell$ coordinates with the last $\ell$ coordinates, we can assume that $\zz = (\underbrace{0,\dots,0}_\ell, \underbrace{1,\dots,1}_\ell)$.

We now look at the last column $M_{n+1}$ of $M$. Since $\sum_{i=1}^\ell m_{n+1}^i = \sum_{i=\ell+1}^{2\ell} m_{n+1}^i$, and since $B_\ell$ is totally symmetric on the first $\ell$ rows and on the last $\ell$ rows, we can assume that $$M_{n+1} = (\underbrace{0,\dots,0}_\alpha, \underbrace{1,\dots,1}_\beta,
               \underbrace{0,\dots,0}_\alpha, \underbrace{1,\dots,1}_\beta)$$ holds for some $\alpha,\beta \geq 0$ with $\alpha+\beta = \ell$.

We will now construct a matrix $K$ with $$K = \begin{pmatrix}
      k_1^1 & k_2^1 & \dots & k_n^1 \\
      k_1^2 & k_2^2 & \dots & k_n^2 \\
      \vdots & \vdots &  & \vdots \\
      k_1^{2\ell} & k_2^{2\ell} & \dots & k_n^{2\ell}
    \end{pmatrix} = \begin{pmatrix} 
      K^1 \\
      K^2 \\
      \vdots \\
      K^{2\ell}
    \end{pmatrix}
    = (K_1,K_2,\dots,K_n),$$ that satisfies $K_1, \dots, K_n \in R(B_\ell)$ and $f(K_1, \dots, K_n) \notin S(B_\ell)$. This will yield the desired contradiction since we started with the assumption that $f \in \operatorname{cPol}B_\ell$.

We define $k_j^i$ for $1 \leq i \leq 2\ell$ and $1 \leq j \leq n$ by $$\def\arraystretch{1.2}
    k_j^i = \left\{\begin{array}{llr@{{} \leq i \leq {}}l}
      \overline{m}_j^{i+\ell} & \text{if } & 1          & \alpha \\
      m_j^i                & \text{if } & \alpha+1   & \ell \\
      \overline{m}_j^{i-\ell} & \text{if } & \ell+1        & \ell+\alpha \\
      m_j^i                & \text{if } & \ell+\alpha+1 & 2\ell
    \end{array}\right.$$ In other words, matrix $K$ is obtained from $M$ by omitting the last column, negating rows $1, \dots, \alpha$ and $\ell + 1, \dots, \ell + \alpha$, and then swapping rows $1, \dots, \alpha$ with rows $\ell + 1, \dots, \ell + \alpha$.

We need to show that $K_j \in R(B_\ell)$ for all $j \in [n]$. Let $j \in [n]$ be arbitrary, and let $$a := \sum_{i=1}^\alpha m_j^i, \qquad
    b := \sum_{i=\alpha+1}^\ell m_j^i, \qquad
    c := \sum_{i=\ell+1}^{\ell+\alpha} m_j^i, \qquad
    d := \sum_{i=\ell+\alpha+1}^{2\ell} m_j^i.$$ Since $M_j \in R(B_\ell)$ we have $$\label{equation:ST:abEqualscd}
    a+b = \sum_{i=1}^\ell m_j^i = \sum_{i=\ell+1}^{2\ell} m_j^i = c + d.$$ For $K_j$ we find the following: $$\begin{aligned}
    \sum_{i=1}^\alpha k_j^i & 
     = \sum_{i=1}^\alpha \overline{m}_j^{i+\ell} 
     = \sum_{i=1}^\alpha (1-m_j^{i+\ell}) 
     = \alpha - \sum_{i=\ell+1}^{\ell+\alpha} m_j^i 
     = \alpha - c, \displaybreak[0]\\
    \sum_{i=\alpha+1}^\ell k_j^i & = \sum_{i=\alpha+1}^\ell m_j^i = b, \displaybreak[0]\\
    \sum_{i=\ell+1}^{\ell+\alpha} k_j^i & 
     = \sum_{i=\ell+1}^{\ell+\alpha} \overline{m}_j^{i-\ell}
     = \sum_{i=\ell+1}^{\ell+\alpha} (1-m_j^{i-\ell})
     = \alpha - \sum_{i=1}^{\alpha} m_j^i 
     = \alpha - a, \displaybreak[0]\\
    \sum_{i=\ell+\alpha+1}^{2\ell} k_j^i & = \sum_{i=\ell+\alpha+1}^{2\ell} m_j^i = d.
  \end{aligned}$$ From this it follows that $$\sum_{i=1}^\ell k_j^i  = \alpha - c + b \overset{\eqref{equation:ST:abEqualscd}}{=} 
    \alpha - a + d = \sum_{i=\ell+1}^{2\ell} k_j^i,$$ and thus $K_j \in R(B_\ell)$ for all $j \in [n]$.

We now show that $f(K^i) = 0$ if $1 \leq i \leq \ell$, and $f(K^i) = 1$ if $\ell+1 \leq i \leq 2\ell$. We need to consider four different cases for $i$:

-   $1 \leq i \leq \alpha$. Then $(\overline{K}^i,0) = M^{i+\ell}$, and $$\overline{f(K^i)} = {{f}^{\mathrm{d}}}(\overline{K}^i) = g(\overline{K}^i, 0) = g(M^{i+\ell}) = 1.$$ Hence $f(K^i) = 0$.

-   $\alpha+1 \leq i \leq \ell$. Then $(K^i,1) = M^i$, and $$f(K^i) = g(K^i,1) = g(M^i) = 0.$$

-   $\ell+1 \leq i \leq \ell+\alpha$. Then $(\overline{K}^i,0) = M^{i-\ell}$, and $$\overline{f(K^i)} = {{f}^{\mathrm{d}}}(\overline{K}^i) = g(\overline{K}^i, 0) = g(M^{i-\ell}) = 0.$$ Hence $f(K^i) = 1$.

-   $\ell+\alpha+1 \leq i \leq 2\ell$. Then $(K^i,1) = M^i$, and $$f(K^i) = g(K^i,1) = g(M^i) = 1.$$

Thus we have $$f(K_1,\dots,K_n) = \begin{pmatrix} f(K^1) \\ \vdots \\ f(K^\ell) \\ f(K^{\ell+1}) \\ \vdots \\ f(K^{2\ell}) \end{pmatrix}
      = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ \vdots \\1 \end{pmatrix} \notin S(B_\ell),$$ in contradiction to $f \in \operatorname{cPol}B_\ell$. We conclude that $g \in \operatorname{cPol}B_\ell$.

\[cor:GS\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_S(f) \in S$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_S(f) \in \operatorname{cPol}B_\ell$.

This brings together Lemmas \[lemma:anytoS\], \[lemma:ST:fNotinBlimpliesgNotinBl\] and \[lemma:ST:fInBlImpliesgInBl\].

Construction of $G_{M_c}(f)$ and $G_{SM}(f)$ {#subsec:SMT}
--------------------------------------------

Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. We define the Boolean function $G_{M_c}(f) \colon {\mathbb{B}}^{2n} \to {\mathbb{B}}$ by the following rules

-   If $w(\xx) < n$, then $G_{M_c}(f)(\xx) := 0$.

-   If $w(\xx) > n$, then $G_{M_c}(f)(\xx) := 1$.

-   If $\xx = (\aa, \overline{\aa})$ for some $\aa \in {\mathbb{B}}^n$, then $G_{M_c}(f)(\xx) := f(\aa)$.

-   If $w(\xx) = n$ and there exists $i \in [n]$ such that $x_i = x_{n+i}$ and $x_j \neq x_{n+j}$ for all $j < i$, then $G_{M_c}(f)(\xx) := x_i$.

It is easy to verify that the function $G_{M_c}(f)$ is defined on every tuple $\xx \in {\mathbb{B}}^{2n}$.

\[lemma:StoSM\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$.

1.  \[lemma:StoSM:item1\] $G_{M_c}(f) \in M_c$, i.e., $G_{M_c}(f)$ is monotone and constant-preserving.

2.  \[lemma:StoSM:item2\] If $f$ is self-dual, then $G_{M_c}(f)$ is self-dual.

Let $g := G_{M_c}(f)$.

Let $\xx,\yy \in {\mathbb{B}}^{2n}$ with $\xx < \yy$. Then $w(\xx) < w(\yy)$ and one of the following cases applies: $w(\xx) < n$ or $w(\yy) > n$. In the former case, we have $g(\xx) = 0 \leq g(\yy)$; in the latter case, we have $g(\xx) \leq 1 = g(\yy)$. We conclude that $g$ is monotone. Since $w(\00) = 0 < n$ and $w(\11) = 1 > n$, it holds that $f(\00) = 0$ and $f(\11) = 1$, i.e., $f$ preserves both constants.

Assume that $f$ is self-dual. Let $\xx \in {\mathbb{B}}^{2n}$.

If $w(\xx) > n$ then $w(\overline{\xx}) < n$, and thus $(g(\xx),g(\overline{\xx})) = (1,0)$. Similarly, if $w(\xx) < n$ then $w(\overline{\xx}) > n$, and thus $(g(\xx),g(\overline{\xx})) = (0,1)$.

If $\xx = (\aa, \overline{\aa})$ for some $\aa \in {\mathbb{B}}^n$, then $(g(\xx), g(\overline{\xx})) = (f(\aa), f(\overline{\aa})) \in \{ (0,1),(1,0) \}$ since $f$ is self-dual.

Otherwise, there is some $i \in [m]$ with $x_i = x_{m+i}$ and $x_j \neq x_{m+j}$ for all $j < i$. This holds also for the negation of $\xx$, and thus $(g(\xx), g(\overline{\xx})) \in \{ (0,1),(1,0) \}$.

We conclude that $g$ is self-dual.

\[lemma:SM:fnotinBlimpliesgnotinBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. If $f \notin \operatorname{cPol}B_\ell$ for some $\ell \geq 2$, then $G_{M_c}(f) \notin \operatorname{cPol}B_\ell$.

Let $f \notin \operatorname{cPol}B_\ell$ and $g := G_{M_c}(f)$. Then there are $\yy_1,\dots,\yy_n \in R(B_\ell)$ with $f(\yy_1,\dots,\yy_n) \notin S(B_\ell)$. Also $\overline{\yy}_1,\dots,\overline{\yy}_n \in R(B_\ell)$ and thus $$g(\yy_1,\dots,\yy_n,\overline{\yy}_1,\dots,\overline{\yy}_n) = f(\yy_1,\dots,\yy_n) \notin S(B_\ell).$$ Therefore $g \notin \operatorname{cPol}B_\ell$.

\[lemma:SM:finBlimpliesginBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$ with $f \in \operatorname{cPol}B_\ell$ for some $\ell \geq 2$. Then $G_{M_c}(f) \in \operatorname{cPol}B_\ell$.

Let $g := G_{M_c}(f)$. Suppose, on the contrary, that $g \notin \operatorname{cPol}B_\ell$. Then there is some matrix $M$ given by $$M = \begin{pmatrix}
      m_1^1 & m_2^1 & \dots & m_{2n}^1 \\
      m_1^2 & m_2^2 & \dots & m_{2n}^2 \\
      \vdots & \vdots &  & \vdots \\
      m_1^{2\ell} & m_2^{2\ell} & \dots & m_{2n}^{2\ell}
    \end{pmatrix} = \begin{pmatrix} 
      M^1 \\
      M^2 \\
      \vdots \\
      M^{2\ell}
    \end{pmatrix}
    = (M_1,M_2,\dots,M_{2n}),$$ i.e., $M^1,\dots,M^{2\ell} \in {\mathbb{B}}^{2n}$ are the rows of $M$, and $M_1,\dots,M_{2n} \in {\mathbb{B}}^{2\ell}$ are the columns of $M$, such that

-   $M_1,\dots,M_{2n} \in R(B_\ell)$, and

-   $\zz := g(M_1,\dots,M_{2n}) := \begin{pmatrix} g(M^1) \\ \vdots \\ g(M^{2\ell}) \end{pmatrix} 
            \notin S(B_\ell)$.

Thus $\zz \in \{ (\underbrace{0,\dots,0}_\ell,\underbrace{1,\dots,1}_\ell), 
  (\underbrace{1,\dots,1}_\ell,\underbrace{0,\dots,0}_\ell)\}$. As $B_\ell$ is invariant under swapping the first $\ell$ coordinates with the last $\ell$ coordinates, we can assume that $\zz = (\underbrace{0,\dots,0}_\ell,\underbrace{1,\dots,1}_\ell)$.

We have the following possibilities for $M^i$ with $1 \leq i \leq 2\ell$:

1.  \[enum:finQlimpliesginQl:smallweight\] $w(M^i) \neq n$;

2.  \[enum:finQlimpliesginQl:equalpairs\] $w(M^i) = n$ and there is some $b \in [n]$ with $m^i_b = m^i_{n+b}$;

3.  \[enum:finQlimpliesginQl:fromf\] $w(M^i) = n$ and $m^i_b \neq m^i_{n+b}$ for all $b \in [n]$, i.e., there is some $\aa_i \in {\mathbb{B}}^n$ with $M^i = (\aa_i,\overline{\aa_i})$.

We show that case \[enum:finQlimpliesginQl:smallweight\] cannot happen, since the weight of each row $M^i$ of $M$ is exactly $n$. Since $g(M^i) = 0$ for $1 \leq i \leq \ell$, we have $w(M^i) \leq n$ for $1 \leq i \leq \ell$. Similarly, we have $w(M^i) \geq n$ for $\ell+1 \leq i \leq 2\ell$. Thus $\sum_{i=1}^\ell w(M^i) \leq n\ell$ and $\sum_{i=\ell+1}^{2\ell} w(M^i) \geq n\ell$. Because $M_j \in R(B_\ell)$ for $1 \leq j \leq 2n$, we get $$\sum_{i=1}^\ell w(M^i) = \sum_{i=1}^\ell \sum_{j=1}^{2n} m_j^i 
     = \sum_{j=1}^{2n} \sum_{i=1}^\ell m_j^i 
     = \sum_{j=1}^{2n} \sum_{i=\ell+1}^{2\ell} m_j^i 
     = \sum_{i=\ell+1}^{2\ell} \sum_{j=1}^{2n} m_j^i 
     = \sum_{i=\ell+1}^{2\ell} w(M^i)$$ Therefore $\sum_{i=1}^\ell w(M^i) = \sum_{i=\ell+1}^{2\ell} w(M^i) = n\ell$, and $w(M^i) = n$ for $1 \leq i \leq 2\ell$. Thus the case \[enum:finQlimpliesginQl:smallweight\] cannot happen for $M^i$.

We will show that case \[enum:finQlimpliesginQl:equalpairs\] is also not possible. Suppose, on the contrary, that there is some $i \in [2\ell]$ and some $b \in [n]$ such that $m^i_b = m^i_{n+b}$, and $m^i_a \neq m^i_{n+a}$ for all $a < b$. We can assume that $b$ is the smallest number with this property.

Now we consider the weights of $M_b$ and $M_{n+b}$. Because $b$ is minimal, we have that $m^{i'}_a \neq m^{i'}_{n+a}$ for all $a < b$. Thus we have $(m^{i'}_b, m^{i'}_{n+b}) \in \{ (0,0),(0,1),(1,0) \}$ for $1 \leq i' \leq \ell$, and $(m^{i'}_b, m^{i'}_{n+b}) \in \{ (0,1),(1,0),(1,1) \}$ for $\ell+1 \leq i' \leq 2\ell$. Then $$\begin{aligned}
    \sum_{i' = 1}^{\ell} (m^{i'}_b + m^{i'}_{n+b}) & 
    \leq n, \\
    \sum_{i' = \ell+1}^{2\ell} (m^{i'}_b + m^{i'}_{n+b}) &  
    \geq n,
  \end{aligned}$$ and at least one of these inequalities holds strictly. This implies that one of the following holds: $$\begin{aligned}
    \sum_{i' = 1}^\ell m^{i'}_b    & < \sum_{i' = \ell+1}^{2\ell} m^{i'}_b         \quad \text{or} \\
    \sum_{i' = 1}^\ell m^{i'}_{n+b} & < \sum_{i' = \ell+1}^{2\ell} m^{i'}_{n+b}.
  \end{aligned}$$ This means that $M_b \notin R(B_\ell)$ or $M_{n+b} \notin R(B_\ell)$, in contradiction to the assumption. Thus no such $b$ exists, and case \[enum:finQlimpliesginQl:equalpairs\] cannot happen.

Thus case \[enum:finQlimpliesginQl:fromf\] applies for all $M^i$, i.e., $M^i = (\aa_i,\overline{\aa_i})$ for some $\aa_i \in {\mathbb{B}}^n$ holds for all $i \in [2\ell]$. By the definition of $g$ and since $f \in \operatorname{cPol}B_\ell$, we obtain $$\zz  = g\begin{pmatrix} M^1 \\ \vdots \\ M^{2\ell} \end{pmatrix} 
       = f\begin{pmatrix} \aa_1 \\ \vdots \\ \aa_{2\ell} \end{pmatrix}
       = f(M_1,\dots,M_n)
       \in S(B_\ell).$$ But this is a contradiction to $\zz \notin S(B_\ell)$. Thus the matrix $M$ cannot exist, and we have $g \in \operatorname{cPol}B_\ell$.

\[cor:GMc\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_{M_c}(f) \in M_c$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_{M_c}(f) \in \operatorname{cPol}B_\ell$.

This brings together Lemmas \[lemma:StoSM\]\[lemma:StoSM:item1\], \[lemma:SM:fnotinBlimpliesgnotinBl\] and \[lemma:SM:finBlimpliesginBl\].

Let $G_{SM}(f) := G_{M_c}(G_{S}(f))$. Then we can conclude the following corollary from the preceding lemmas.

\[cor:GSM\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_{SM}(f) \in SM$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_{SM}(f) \in \operatorname{cPol}B_\ell$.

By Corollary \[cor:GS\], we have $G_{S}(f) \in S$, and by Lemma \[lemma:StoSM\], we get $G_{SM}(f) = G_{M_c}(G_S(f)) \in SM$.

By Corollary \[cor:GS\], the condition $f \in \operatorname{cPol}B_\ell$ is equivalent to $G_S(f) \in \operatorname{cPol}B_\ell$, which is in turn equivalent to $G_{SM}(f) = G_{M_c}(G_S(f)) \in \operatorname{cPol}B_\ell$ by Corollary \[cor:GMc\].

Construction of $G_{U_\infty}(f)$, $G_{M_cU_\infty}(f)$ and $G_{M_cW_\infty}(f)$ {#subsec:MCT}
--------------------------------------------------------------------------------

Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. Define $G_{U_\infty}(f) \colon {\mathbb{B}}^{n+1} \to {\mathbb{B}}$ by $$G_{U_\infty}(f)(x_1, \dots, x_{n+1}) = x_{n+1} \wedge f(x_1, \dots, x_n).$$

\[lemma:SMtoMcUinfty\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$.

1.  \[lemma:SMtoMcUinfty:item1\] $G_{U_\infty}(f) \in U_\infty$.

2.  \[lemma:SMtoMcUinfty:item2\] If $f$ is monotone, then $G_{U_\infty}(f)$ is monotone.

3.  \[lemma:SMtoMcUinfty:item3\] If $f(\11) = 1$, then $G_{U_\infty}(f)$ preserves both constants.

4.  \[lemma:SMtoMcUinfty:item4\] If $f \in M_c$, then $G_{U_\infty}(f) \in M_cU_\infty$.

Let $g := G_{U_\infty}(f)$.

\[lemma:SMtoMcUinfty:item1\] By the definition of $g$ we have that if $g(x_1,\dots,x_{n+1}) = 1$ then $x_{n+1} = 1$. Thus $g \in U_\infty$.

\[lemma:SMtoMcUinfty:item2\] Let $\xx, \yy \in {\mathbb{B}}^{n+1}$, and assume that $\xx < \yy$. If $x_{n+1} = 0$, then $g(\xx) = 0 \leq g(\yy)$. If $x_{n+1} = 1$, then also $y_{n+1} = 1$, and since $f$ is monotone, we have $$g(\xx) = f(x_1, \dots, x_n) \leq f(y_1, \dots, y_n) = g(\yy).$$ We conclude that $g$ is monotone.

\[lemma:SMtoMcUinfty:item3\] By the definition of $g$, we have $g(\00) = 0$. Furthermore, if $f(\11) = 1$, then we have $g(\11) = f(\11) = 1$.

\[lemma:SMtoMcUinfty:item4\] Follows immediately from the previous items.

\[lemma:McUinfty:fnotinBlimpliesgnotinBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. If $f \notin \operatorname{cPol}B_\ell$ for some $\ell \geq 2$, then $G_{U_\infty}(f) \notin \operatorname{cPol}B_\ell$.

The proof is exactly the same as the proof of Lemma \[lemma:ST:fNotinBlimpliesgNotinBl\].

\[lemma:McUinfty:finBlimpliesginBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. If $f \in \operatorname{cPol}B_\ell$ for some $\ell \geq 2$, then $G_{U_\infty}(f) \in \operatorname{cPol}B_\ell$.

Let $g := G_{U_\infty}(f)$.

Suppose, on the contrary, that $g \notin \operatorname{cPol}B_\ell$. Then there is some matrix $M$ given by $$M = \begin{pmatrix}
      m_1^1 & m_2^1 & \dots & m_{n+1}^1 \\
      m_1^2 & m_2^2 & \dots & m_{n+1}^2 \\
      \vdots & \vdots &  & \vdots \\
      m_1^{2\ell} & m_2^{2\ell} & \dots & m_{n+1}^{2\ell}
    \end{pmatrix} = \begin{pmatrix} 
      M^1 \\
      M^2 \\
      \vdots \\
      M^{2\ell}
    \end{pmatrix}
    = (M_1,M_2,\dots,M_{n+1}),$$ i.e., $M^1,\dots,M^{2\ell} \in {\mathbb{B}}^{n+1}$ are the rows of $M$, and $M_1,\dots,M_{n+1} \in {\mathbb{B}}^{2\ell}$ are the columns of $M$, such that

-   $M_1,\dots,M_{n+1} \in R(B_\ell)$, and

-   $\zz := g(M_1,\dots,M_{n+1}) := \begin{pmatrix} g(M^1) \\ \vdots \\ g(M^{2\ell}) \end{pmatrix} 
            \notin S(B_\ell)$.

Thus $\zz \in \{ (\underbrace{0,\dots,0}_\ell,\underbrace{1,\dots,1}_\ell), 
  (\underbrace{1,\dots,1}_\ell,\underbrace{0,\dots,0}_\ell)\}$. As $B_\ell$ is invariant under swapping the first $\ell$ coordinates with the last $\ell$ coordinates, we can assume that $\zz = (\underbrace{0,\dots,0}_\ell,\underbrace{1,\dots,1}_\ell)$.

We now look at the last column $M_{n+1}$ of $M$. Since $\sum_{i=1}^\ell m_{n+1}^i = \sum_{i=\ell+1}^{2\ell} m_{n+1}^i$, and since $B_\ell$ is totally symmetric on the first $\ell$ rows and on the last $\ell$ rows, we can assume that $$M_{n+1} = (\underbrace{0,\dots,0}_\alpha, \underbrace{1,\dots,1}_\beta,
               \underbrace{0,\dots,0}_\alpha, \underbrace{1,\dots,1}_\beta)$$ holds for some $\alpha,\beta \geq 0$ with $\alpha+\beta = \ell$.

If $\alpha > 0$ then $g(M^{\ell+1}) = g(m_1^{\ell+1},\dots,m_n^{\ell+1},0) = 0 \land f(m_1^{\ell+1},\dots,m_n^{\ell+1}) = 0$, in contradiction to $g(M^{\ell+1}) = 1$. Thus $\alpha = 0$, and $M_{n+1} = \11$. But then $f(M_1,\dots,M_n) = g(M_1,\dots,M_n,\11) = \zz \notin S(B_\ell)$, which implies that $f \notin \operatorname{cPol}B_\ell$. This contradicts the assumption $f \in \operatorname{cPol}B_\ell$, and we conclude that $g \in \operatorname{cPol}B_\ell$.

\[cor:GUinfty\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_{U_\infty}(f) \in U_\infty$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_{U_\infty}(f) \in \operatorname{cPol}B_\ell$.

This brings together Lemmas \[lemma:SMtoMcUinfty\]\[lemma:SMtoMcUinfty:item1\], \[lemma:McUinfty:fnotinBlimpliesgnotinBl\] and \[lemma:McUinfty:finBlimpliesginBl\].

Let $G_{M_cU_\infty}(f) := G_{U_\infty}(G_{M_c}(f))$ and $G_{M_cW_\infty}(f) := {{G_{M_cU_\infty}(f)}^{\mathrm{d}}}$.

\[cor:GMcUinfty\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_{M_cU_\infty}(f) \in M_cU_\infty$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_{M_cU_\infty}(f) \in \operatorname{cPol}B_\ell$.

By Corollary \[cor:GMc\], we have $G_{M_c}(f) \in M_c$, and by Lemma \[lemma:SMtoMcUinfty\], we get $G_{M_cU_\infty}(f) = G_{U_\infty}(G_{M_c}(f)) \in M_cU_\infty$.

By Corollary \[cor:GMc\], the condition $f \in \operatorname{cPol}B_\ell$ is equivalent to $G_{M_c}(f) \in \operatorname{cPol}B_\ell$, which in turn is equivalent to $G_{M_cU_\infty}(f) = G_{U_\infty}(G_{M_c}(f)) \in \operatorname{cPol}B_\ell$ by Corollary \[cor:GUinfty\].

Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$. We define the functions $\overline{f} \colon {\mathbb{B}}^n \to {\mathbb{B}}$ and $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, for $\uu \in {\mathbb{B}}^n$, as $$\begin{aligned}
\overline{f}(\aa) &= \overline{f(\aa)}, \\
f^\uu(\aa) &= f(\aa \oplus \uu).\end{aligned}$$ Note that ${{f}^{\mathrm{d}}} = \overline{f^\11}$, where $\11 := (1, \dots, 1) \in {\mathbb{B}}^n$.

\[lem:dualBl\] Let $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, and let $\ell \geq 2$. The following are equivalent:

1.  $f \in \operatorname{cPol}B_\ell$,

2.  $f^\uu \in \operatorname{cPol}B_\ell$ for any $\uu \in {\mathbb{B}}^n$,

3.  $\overline{f} \in \operatorname{cPol}B_\ell$,

4.  ${{f}^{\mathrm{d}}} \in \operatorname{cPol}B_\ell$.

$\text{(i)} \iff \text{(ii)}$: Let $\aa^1, \dots \aa^n \in R(B_\ell)$. Since $R(B_\ell)$ is invariant under taking negations of its members, we also have $\overline{\aa^1}, \dots \overline{\aa^n} \in R(B_\ell)$. Let $\uu \in {\mathbb{B}}^n$, and let $\bb^i := \aa^i$ if $u_i = 0$ and $\bb^i := \overline{\aa^i}$ if $u_i = 1$, for $i \in {[{n}]}$. If $f \in \operatorname{cPol}B_\ell$, then $$f^\uu(\aa^1, \dots, \aa^n) = f(\bb^1, \dots, \bb^n) \in S(B_\ell);$$ hence $f^\uu \in \operatorname{cPol}B_\ell$. The converse implication holds, since $(f^\uu)^\uu = f$.

$\text{(i)} \iff \text{(iii)}$: Assume that $f \in \operatorname{cPol}B_\ell$, and let $\aa^1, \dots \aa^n \in R(B_\ell)$. Then $f(\aa^1, \dots, \aa^n) \in S(B_\ell)$. Since $S(B_\ell)$ is invariant under taking negations of its members, we have $$\overline{f}(\aa^1, \dots, \aa^n) 
= \overline{f(\aa^1, \dots, \aa^n)}
\in S(B_\ell);$$ hence $\overline{f} \in \operatorname{cPol}B_\ell$. The converse implication holds, since $\overline{\overline{f}} = f$.

$\text{(i)} \iff \text{(iv)}$: This follows immediately from the equivalence of (i), (ii) and (iii), because ${{f}^{\mathrm{d}}} = \overline{f^\11}$.

\[cor:GMcWinfty\] For any Boolean function $f \colon {\mathbb{B}}^n \to {\mathbb{B}}$, $G_{M_cW_\infty}(f) \in M_cW_\infty$ and for all $\ell \geq 2$, $f \in \operatorname{cPol}B_\ell$ if and only if $G_{M_cW_\infty}(f) \in \operatorname{cPol}B_\ell$.

Since $M_cW_\infty = \{{{f}^{\mathrm{d}}} : f \in M_cU_\infty\}$, the claim follows from Lemma \[lem:dualBl\] and Corollary \[cor:GMcUinfty\].

Simple games and magic squares revisited {#sec:magic}
========================================

In their proof of the existence of $k$-asummable functions that are not $(k+1)$-asummable (see Theorem \[theorem:strictAkInclusions\]), Taylor and Zwicker constructed a certain family of functions [@Taylor]. We recall their construction here, and then we will refine Theorem \[theorem:strictAkInclusions\] and determine how the sets $\operatorname{cPol}B_n$ are related to each other. We will also show that Taylor and Zwicker’s functions actually constitute an antichain of minimally non-threshold functions.

Fix an integer $k \geq 3$. For $p, q \in {[{k}]}$, define the $k \times k$ matrix $A^{p,q} = (a_{i,j})$ as follows: $$a_{i,j} =
\begin{cases}
k - 1, & \text{if $(i,j) = (p,q)$,} \\
1, & \text{if $i \neq p$ and $j \neq q$,} \\
0, & \text{otherwise.}
\end{cases}$$ For example, if $k = 4$, then $A^{2,3} = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 0 & 3 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix}$. Let $B$ be the $k \times k$ matrix all of whose entries are equal to $k - 1$.

Let $S$ be a subset of ${[{k}]} \times {[{k}]}$. We refer to $S$ as the $i$-th *row* if $S = \{(i, j) : j \in {[{k}]}\}$, and we refer to $S$ as the $j$-th *column* if $S = \{(i, j) : i \in {[{k}]}\}$.

\[lem:roworcolumn\] Let $S \subseteq {[{k}]} \times {[{k}]}$. Then $\sum_{(p,q) \in S} A^{p,q} = B$ if and only if $S$ is a row or a column.

It is clear that if $S$ is a row or a column, then $\sum_{(p,q) \in S} A^{p,q} = B$.

Assume then that $\sum_{(p,q) \in S} A^{p,q} = B$. Clearly $S$ is nonempty, so choose an element $(p,q)$ of $S$; clearly $S$ contains another element $(p',q')$. If $p \neq p'$ and $q \neq q'$, then the entry on row $p$ column $q$ in the sum $\sum_{(p,q) \in S} A^{p,q}$ is at least $k$; hence the sum cannot be equal to $B$. Thus either $p = p'$ or $q = q'$. It is easy to see that in the former case, all remaining entries of $S$ must be on the $p$-th row, and all elements of the $p$-th row must be in $S$; in the latter case, all remaining entries of $S$ must be on the $q$-th column, and all elements of the $q$-th column must be in $S$. We conclude that $S$ is either a row or a column.

We define a function $\phi \colon {[{R}]}^{k \times k} \to {\mathbb{N}}$ that maps each $k \times k$ matrix with entries in ${[{R}]}$ to an integer, where $R$ is a sufficiently large integer that will be specified below. The function $\phi$ is defined as follows: for a matrix $M$, read the entries of $M$ from left to right and from top to bottom; the resulting string is the representation of $\phi(M)$ in base $R$. For $p, q \in {[{k}]}$, denote $w^{p,q} := \phi(A^{p,q})$ and $t := \phi(B)$. For example if $k = 4$, then $w^{2,3} = 1101003011011101_R$ and $t = 3333333333333333_R$. We must choose $R$ in such a way that when we add these numbers to form the sum $\sum_{(p,q) \in S} w^{p,q}$ for any $S \subseteq {[{k}]} \times {[{k}]}$, no carry will occur. Thus, the number $(k-1)^2 + (k-1) + 1 = k^2 - k + 1$, or anything larger, would be fine.

It is easy to see that the function $\phi$ has the following preservation property: for any $S \subseteq {[{k}]} \times {[{k}]}$, $\phi(\sum_{(p,q) \in S} A^{p,q}) = \sum_{(p,q) \in S} \phi(A^{p,q})$. It thus follows from Lemma \[lem:roworcolumn\] that for all $S \subseteq {[{k}]} \times {[{k}]}$, it holds that $\sum_{(p,q) \in S} w^{p,q} = t$ if and only if $S$ is a row or a column.

Fix a bijection $\beta \colon {[{k}]} \times {[{k}]} \to {[{k^2}]}$. The *characteristic tuple* of a subset $S$ of ${[{k}]} \times {[{k}]}$ is the tuple $\ee_S \in {\mathbb{B}}^{k^2}$, whose $i$-th entry is $1$ if $i = \beta(p,q)$ for some $(p,q) \in S$ and $0$ otherwise. With no risk of confusion, we will refer to the characteristic tuples of rows and columns also as *rows* and *columns,* respectively.

Let $\ww = (w^{\beta^{-1}(1)}, \dots, w^{\beta^{-1}(k^2)})$.

For any $n$-tuples $\aa, \bb \in {\mathbb{R}}^n$, the *dot product* is defined as $$\aa \cdot \bb = \sum_{i=1}^n a_i b_i.$$

Taylor and Zwicker’s function $f_k \colon {\mathbb{B}}^{k^2} \to {\mathbb{B}}$ is defined by the following rule: $f_k(\xx) = 1$ if and only if $\xx \cdot \ww > t$ or $\xx$ is a row. Note that for all $\xx \in {\mathbb{B}}^{k^2}$, $\xx \cdot \ww = t$ if and only if $\xx$ is a row or a column.

\[lem:fkBl\] Let $k \geq 3$ and $\ell \geq 2$. Then $f_k$ preserves $B_\ell$ if and only if $k$ is not a divisor of $\ell$.

If $\ell = mk$ for some integer $m$, then let $\aa^1, \dots, \aa^\ell$ comprise $m$ occurrences of each column, and let $\bb^1, \dots, \bb^\ell$ comprise $m$ occurrences of each row. Then, the $\aa^i$ are false points of $f_k$ and the $\bb^i$ are true points, and $\aa^1 + \dots + \aa^\ell = (m, \dots, m) = \bb^1 + \dots + \bb^\ell$. Thus $f_k$ is not $\ell$-asummable. Lemma \[lem:PolBl\] implies that $f_k$ does not preserve $B_\ell$.

Assume then that $k$ is not a divisor of $\ell$. Suppose, on the contrary, that $f_k$ does not preserve $B_\ell$. By Lemma \[lem:PolBl\], there exist $\aa^1, \dots, \aa^\ell \in f^{-1}(0)$ and $\bb^1, \dots, \bb^\ell \in f^{-1}(1)$ such that $\aa^1 + \dots + \aa^\ell = \bb^1 + \dots + \bb^\ell$. Since $\xx \cdot \ww \leq t$ for any false point $\xx$ of $f_k$, and $\xx \cdot \ww \geq t$ for any true point $\xx$, we have $$\sum_{i = 1}^\ell \aa^i \cdot \ww \leq \ell t
\qquad
\text{and}
\qquad
\sum_{i = 1}^\ell \bb^i \cdot \ww \geq \ell t.$$ On the other hand, since $\aa^1 + \dots + \aa^\ell = \bb^1 + \dots + \bb^\ell$, we have $$\sum_{i = 1}^\ell \aa^i \cdot \ww
= (\aa^1 + \dots + \aa^\ell) \cdot \ww
= (\bb^1 + \dots + \bb^\ell) \cdot \ww
= \sum_{i = 1}^\ell \bb^i \cdot \ww.$$ Consequently, $\aa^i \cdot \ww = t$ and $\bb^i \cdot \ww = t$ for all $i \in {[{\ell}]}$, and we conclude that each $\aa^i$ is a column and each $\bb^i$ is a row. Since $k$ is not a divisor of $\ell$, there necessarily exist two columns that have a different number of occurrences among $\aa^1, \dots, \aa^\ell$. Then $\phi^{-1}(\aa^1 + \dots + \aa^n)$ is a matrix that is constant along each column, but there are two columns with distinct values. This contradicts the fact that the matrix $\phi^{-1}(\bb^1 + \dots + \bb^n)$ is constant along each row. This completes the proof, and we conclude that $f_k$ preserves $B_\ell$.

\[lem:mod2sum\] The modulo-$2$ addition operation ${\oplus}$ preserves $B_\ell$ if and only if $\ell$ is odd.

The false points of $\oplus$ are $(0,0)$ and $(1,1)$, while the true points are $(0,1)$ and $(1,0)$. Hence the sum of any $\ell$ false points is of the form $(m,m)$ for some $m$ with $0 \leq m \leq \ell$. The sum of any $\ell$ true points is of the form $(m, \ell - m)$ for some $m$ with $0 \leq m \leq \ell$.

If $\ell$ is odd, then $m \neq \ell - m$ for any $m$. It follows that $\aa^1 + \dots + \aa^\ell \neq \bb^1 + \dots + \bb^\ell$ for any false points $\aa^1, \dots, \aa^\ell$ and any true points $\bb^1, \dots, \bb^\ell$. By Lemma \[lem:PolBl\], $\oplus$ preserves $B_\ell$.

If $\ell$ is even, say $\ell = 2k$, then $$\begin{gathered}
\underbrace{(0,0) + \dots + (0,0)}_k + \underbrace{(1,1) + \dots + (1,1)}_k = \\
\underbrace{(0,1) + \dots + (0,1)}_k + \underbrace{(1,0) + \dots + (1,0)}_k.\end{gathered}$$ By Lemma \[lem:PolBl\], $\oplus$ does not preserve $B_\ell$.

Let $\ell, m \geq 2$. Then $\operatorname{cPol}B_\ell \subseteq \operatorname{cPol}B_m$ if and only if $m$ divides $\ell$.

Assume first that $m$ does not divide $\ell$. If $m \neq 2$, then by Lemma \[lem:fkBl\], $f_m \in \operatorname{cPol}B_\ell$ but $f_m \notin \operatorname{cPol}B_m$. If $m = 2$, then by Lemma \[lem:mod2sum\], ${\oplus} \in \operatorname{cPol}B_\ell$ but ${\oplus} \notin \operatorname{cPol}B_m$. In either case, we conclude that $\operatorname{cPol}B_\ell \not\subseteq \operatorname{cPol}B_m$.

Assume then that $\ell = km$ for some integer $k$. Let $f \in \operatorname{cPol}B_\ell$. Let $\aa^1, \dots, \aa^n \in R(B_m)$. For each $i \in \{1, \dots, n\}$, define the tuple $\bb^i \in {\mathbb{B}}^\ell$ as $$\bb^i = (\underbrace{a^i_1, \dots, a^i_1}_k, \dots, \underbrace{a^i_m, \dots, a^i_m}_k, \underbrace{a^i_{m + 1}, \dots, a^i_{m + 1}}_k, \dots, \underbrace{a^i_{2m}, \dots, a^i_{2m}}_{k}).$$ It is clear that $\bb^i \in R(B_\ell)$. Let $\zz := f(\bb^1, \dots, \bb^n)$, that is, $$\zz = (\underbrace{f(a^1_1, \dots, a^n_1), \dots, f(a^1_1, \dots, a^n_1)}_k, \dots, \underbrace{f(a^1_{2m}, \dots, a^n_{2m}), \dots, f(a^1_{2m}, \dots, a^n_{2m})}_k).$$ Since $f \in \operatorname{cPol}B_\ell$, we have $\zz \in S(R_\ell)$. Then $$\zz \in {\mathbb{B}}^\ell \setminus \{(\underbrace{0, \dots, 0}_\ell, \underbrace{1, \dots, 1}_\ell), (\underbrace{1, \dots, 1}_\ell, \underbrace{0, \dots, 0}_\ell))\}.$$ This implies that $$f(\aa^1, \dots, \aa^n) \in {\mathbb{B}}^m \setminus \{(\underbrace{0, \dots, 0}_m, \underbrace{1, \dots, 1}_m), (\underbrace{1, \dots, 1}_m, \underbrace{0, \dots, 0}_m))\}.$$ Thus $f \in \operatorname{cPol}B_m$, and we conclude that $\operatorname{cPol}B_\ell \subseteq \operatorname{cPol}B_m$.

\[prop:tzantichain\] The functions $f_k$ ($k \geq 3$) are pairwise incomparable by the minor relation.

Let $m \neq n$, and consider the comparability of $f_m$ and $f_n$. Since all variables are essential in $f_m$ and in $f_n$, and the number of essential variables cannot increase when taking minors, we have that $f_m \not\leq f_n$ whenever $m > n$. If $m < n$, then $n$ is not a divisor of $m$ but $n$ is a divisor of itself. By Lemma \[lem:fkBl\], $f_n$ preserves $B_m$ and $f_m$ does not preserve $B_m$. Since every minor of $f_n$ preserves all relational constraints $f_n$ does, we must have that $f_m \not\leq f_n$ also in this case.

\[prop:tzmonotone\] For every $k \geq 3$, the function $f_k$ is monotone.

Let $\xx, \yy \in {\mathbb{B}}^{k^2}$. If $\xx < \yy$, then, since each $w^{p,q}$ is positive, $\xx \cdot \ww < \yy \cdot \ww$. Therefore one of the following conditions holds: $\xx \cdot \ww < t$ or $\yy \cdot \ww > t$. In the former case, $f(\xx) = 0 \leq f(\yy)$. In the latter case, $f(\xx) \leq 1 = f(\yy)$.

\[prop:tzminnonthr\] For every $k \geq 3$, the function $f_k$ is minimally non-threshold.

We need to show that every identification minor of $f_k$ is threshold. Let $(p,q)$ and $(p',q')$ be distinct elements of ${[{k}]} \times {[{k}]}$, let $I = \{\beta(p,q), \beta(p',q')\}$, and assume without loss of generality that $\beta(p,q) < \beta(p',q')$. We will show that $(f_k)_I$ is $\ell$-asummable for every $\ell \geq 2$ and hence threshold by Theorem \[thm:thresholdasummable\]. Let $\ell \geq 2$, and let $\aa^1, \dots, \aa^\ell \in ((f_k)_I)^{-1}(0)$, $\bb^1, \dots, \bb^\ell \in ((f_k)_I)^{-1}(1)$. Suppose, on the contrary, that $\aa^1 + \dots + \aa^\ell = \bb^1 + \dots + \bb^\ell$. Let $\vv \in {\mathbb{B}}^{k^2 - 1}$ be the tuple obtained from $\ww$ by replacing its $\beta(p,q)$-th entry by $w_{\beta(p,q)} + w_{\beta(p',q')}$ and deleting the $\beta(p',q')$-th entry. (Before proceeding, we ask the reader to recall the definition of $\delta_I$ from  in Section \[susec:MinorsConstraints\].) It clearly holds that $\xx \cdot \vv = \xx \delta_I \cdot \ww$ for all $\xx \in {\mathbb{B}}^{k^2 - 1}$. Therefore $((f_k)_I)(\xx) = f_k(\xx \delta_I) = 1$ if and only if $\xx \cdot \vv = \xx \delta_I \cdot \ww > t$ or $\xx \delta_I$ is a row. Note that if $\xx \delta_I$ is a row or a column, then $\xx \cdot \vv = \xx \delta_I \cdot \ww = t$. In a similar way as we argued in the proof of Lemma \[lem:fkBl\], we have $$\ell t
\geq \sum_{i = 1}^\ell \aa^i \cdot \vv
= (\aa^1 + \dots + \aa^\ell) \cdot \vv
= (\bb^1 + \dots + \bb^\ell) \cdot \vv
= \sum_{i = 1}^\ell \bb^i \cdot \vv
\geq \ell t.$$ Hence $\aa^i \cdot \vv = t$ and $\bb^i \cdot \vv = t$ for all $i \in {[{\ell}]}$, that is, $\aa^i \delta_I$ is a column and $\bb^i \delta_I$ is a row for all $i \in {[{\ell}]}$.

Since $(p,q) \neq (p',q')$, we have $p \neq p'$ or $q \neq q'$. If $p \neq p'$, then none of the rows $\bb^i \delta_I$ is the $p$-th row; hence $\phi^{-1}(\bb^1 \delta_I + \dots + \bb^\ell \delta_I)$ is a matrix with a row full of $0$’s, while $\phi^{-1}(\aa^1 \delta_I + \dots + \aa^\ell \delta_I)$ has no row full of $0$’s. If $q \neq q'$, then none of the columns $\aa^i \delta_I$ is the $q$-th column; hence $\phi^{-1}(\aa^1 \delta_I + \dots + \aa^\ell \delta_I)$ is a matrix with a column full of $0$’s, while $\phi^{-1}(\bb^1 \delta_I + \dots + \bb^\ell \delta_I)$ has no column full of $0$’s. On the other hand, $$\aa^1 \delta_I + \dots + \aa^\ell \delta_I
= (\aa^1 + \dots + \aa^\ell) \delta_I
= (\bb^1 + \dots + \bb^\ell) \delta_I
= \bb^1 \delta_I + \dots + \bb^\ell \delta_I.$$ We have reached a contradiction.

We conclude that $(f_k)_I$ is $\ell$-asummable for every $\ell \geq 2$ and hence threshold.

Taylor and Zwicker’s functions $f_k$ constitute an infinite antichain of monotone, minimally non-threshold functions (Propositions \[prop:tzantichain\], \[prop:tzmonotone\], \[prop:tzminnonthr\]). It should be noted here that this antichain does not, however, characterize the set of monotone threshold functions in terms of forbidden minors, i.e., $M \cap {T}\neq \operatorname{forbid}(\{f_k : k \geq 3\})$. For example, there exist self-dual monotone non-threshold functions of arity $6$ (see, e.g., [@BioIba]), which clearly fail to have any of the $f_n$ as a minor.

Post classes {#App:Post}
============

We provide a concise description of all clones of Boolean functions as well as characterizing sets of relations $R$ – or, equivalently, relational constraints $(R,R)$ – for some clones; the characterizion of the remaining clones is easily derived by noting that if $C_1 = \operatorname{cPol}(\mathcal{Q}_1)$ and $C_2 = \operatorname{cPol}(\mathcal{Q}_2)$, then $C_1 \cap C_2 = \operatorname{cPol}(\mathcal{Q}_1 \cup \mathcal{Q}_2)$. We make use of notations and terminology appearing in [@FP] and [@JGK].

$\Omega$ denotes the clone of all Boolean functions. It is characterized by the empty relation.

$T_0$ and $T_1$ denote the clones of $0$- and $1$-preserving functions, respectively, i.e., $$T_0 = \{f \in \Omega : f(0, \dots, 0) = 0\}
\quad \text{and} \quad 
T_1 = \{f \in \Omega : f(1, \dots, 1) = 1\}.$$ They are characterized by the unary relations $\{0\}$ and $\{1\}$, respectively.

$T_c$ denotes the clone of constant-preserving functions, i.e., $T_c = T_0 \cap T_1$.

$M$ denotes the clone of all monotone functions, i.e., $$M = \{f \in \Omega : \text{$f(\mathbf{a}) \leq f(\mathbf{b})$ whenever $\mathbf{a} \leq \mathbf{b}$}\}.$$ It is characterized by the binary relation ${\leq} := \{(0,0), (0,1), (1,1)\}$.

$M_0 = M \cap T_0$, $M_1 = M \cap T_1$, $M_c = M \cap T_c$.

$S$ denotes the clone of all self-dual functions, i.e., $$S = \{f \in \Omega : {{f}^{\mathrm{d}}} = f\}.$$ It is characterized by the binary relation $\{(0,1),(1,0)\}$.

$S_c = S \cap T_c$, $SM = S \cap M$.

$L$ denotes the clone of all linear functions, i.e., $$L = \{f \in \Omega :  f = c_0 \oplus c_1 x_1 \oplus \dots \oplus c_n x_n\}.$$ It is characterized by the quaternary relation $\{(a,b,c,d) \in {\mathbb{B}}^4 : a \oplus b \oplus c = d\}$.

$L_0 = L \cap T_0$, $L_1 = L \cap T_1$, $LS = L \cap S$, $L_c = L \cap T_c$.

Let $a \in \{0,1\}$. A set $A \subseteq \{0,1\}^n$ is said to be *$a$-separating* if there is some $i\in [n]$ such that for every $(a_1, \dotsc, a_n) \in A$ we have $a_i = a$. A function $f$ is said to be *$a$-separating* if $f^{-1}(a)$ is $a$-separating. The function $f$ is said to be *$a$-separating of rank $k \geq 2$* if every subset $A \subseteq f^{-1}(a)$ of size at most $k$ is $a$-separating.

For $m \geq 2$, $U_m$ and $W_m$ denote the clones of all $1$- and $0$-separating functions of rank $m$, respectively. They are characterized by the $m$-ary relations ${\mathbb{B}}^m \setminus \{(0, \dots, 0)\}$ and ${\mathbb{B}}^m \setminus \{(1, \dots, 1)\}$, respectively.

$U_\infty$ and $W_\infty$ denote the clones of all $1$- and $0$-separating functions, respectively, i.e., $U_\infty = \bigcap_{k \geq 2} U_k$ and $W_\infty = \bigcap_{k \geq 2} W_k$.

$T_cU_m = T_c \cap U_m$ and $T_cW_m = T_c \cap W_m$, for $m = 2, \dotsc, \infty$.

$MU_m = M \cap U_m$ and $MW_m = M \cap W_m$, for $m = 2, \dotsc, \infty$.

$M_cU_m = M_c \cap U_m$ and $M_cW_m = M_c \cap W_m$, for $m = 2, \dotsc, \infty$.

$\Lambda $ denotes the clone of all conjunctions and constants, i.e., $$\begin{gathered}
\Lambda = \{f \in \Omega : f = x_{i_1} \wedge \dotsb \wedge x_{i_n}\} \cup 
\{\mathbf{0}^{(n)}: n\geq 1\} \cup \{\mathbf{1}^{(n)}: n\geq 1\}.\end{gathered}$$ It is characterized by the ternary relation $\{(a,b,c) : a \wedge b = c\}$.

$\Lambda_0 = \Lambda \cap T_0$, $\Lambda_1 = \Lambda \cap T_1$, $\Lambda_c = \Lambda \cap T_c$.

$V$ denotes the clone of all disjunctions and constants, i.e., $$\begin{gathered}
V = \{f \in \Omega : f = x_{i_1} \vee \dotsb \vee x_{i_n}\}  \cup 
\{\mathbf{0}^{(n)}: n\geq 1\} \cup \{\mathbf{1}^{(n)}: n\geq 1\}.\end{gathered}$$ It is characterized by the ternary relation $\{(a,b,c) : a \vee b = c\}$.

$V_0 = V \cap T_0$, $V_1 = V \cap T_1$, $V_c = V \cap T_c$.

$\Omega (1)$ denotes the clone of all projections, negations, and constants. It is characterized by the ternary relation $\{(a,b,c) : \text{$a = b$ or $b = c$}\}$.

$I^* = \Omega(1) \cap S$, $I = \Omega(1) \cap M$.

$I_0 = I \cap T_0$, $I_1 = I \cap T_1$.

$I_c$ denotes the smallest clone containing only projections, i.e., $I_c = I \cap T_c$.

[99]{}

Bioch, J. C., Ibaraki, T.: Generating and approximating nondominated coteries, IEEE Trans. Parallel Distrib. Syst. **6**(9), 905–914 (1995)

Bodnarčuk, V. G., Kalužnin, L. A., Kotov, V. N., Romov, B. A.: Galois theory for Post algebras, I, II, Kibernetika **3**, 1–10, **5**, 1–9 (1969) (Russian). English translation: Cybernetics **5**, 243–252, 531–539 (1969)

Chow, C. K.: Boolean functions realizable with single threshold devices, Proc. Institute of Radio Engineers, Vol. 49, Jan. 1961, pp. 370–371

Couceiro, M.: On Galois connections between external functions and relational constraints: arity restrictions and operator decompositions, Acta Sci. Math. (Szeged) **72**, 15–35 (2006)

Couceiro, M., Foldes, S.: On closed sets of relational constraints and classes of functions closed under variable substitution, Algebra Universalis **54**, 149–165 (2005)

Couceiro, M., Lehtonen, E.: On the effect of variable identification on the essential arity of functions on finite sets, Internat. J. Found. Comput. Sci. **18**, 975–986 (2007)

Couceiro, M., Lehtonen, E.: Generalizations of Świerczkowski’s lemma and the arity gap of finite functions, Discrete Math. **309**, 5905–5912 (2009)

Couceiro, M., Marichal, J.-L.: Discrete integrals based on comonotonic modularity, Axioms **2**(3), 390–403 (2013)

Couceiro, M., Pouzet, M.: On a quasi-ordering on Boolean functions, Theoret. Comput. Sci.  **396**, 71–87 (2008)

Denecke, K., Erné, M., Wismath, S. L. (eds.), Galois Connections and Applications, Kluwer Academic Publishers, Dordrecht (2004)

Ekin, O., Foldes, S., Hammer, P. L., Hellerstein, L.: Equational characterizations of Boolean function classes, Discrete Math. **211**, 27–51 (2000)

Elgot, C. C.: Truth functions realizable by single threshold organs, AIEE Conf. Paper 60-1311, Oct. 1960, revised Nov. 1960; also IEEE Symposium on Swithing Circuit Theory and Logical Design, Sept. 1961, pp. 225–245

Foldes, S., Pogosyan, G. R.: Post classes characterized by functional terms, Discrete Appl. Math. **142**, 35–51 (2004)

Geiger, D.: Closed systems of functions and predicates, Pacific J. Math. **27**, 95–100 (1968)

Hellerstein, L.: On generalized constraints and certificates, Discrete Math. **226**, 211–232 (2001)

Isbell, J. R.: A class of majority games, Q. J. Math. **7**(1), 183–187 (1956)

Jablonski, S. W., Gawrilow, G. P., Kudrjawzew, W. B.: Boolesche Funktionen und Postsche Klassen, Vieweg, Braunschweig, 1970.

Jeroslow, R. G.: On defining sets of vertices of the hypercube by linear inequalities, Discrete Math. **11**, 119–124 (1975)

Lau, D.: Function Algebras on Finite Sets, Springer-Verlag, Berlin, Heidelberg (2006)

Lay, S. R.: Convex sets and their applications, Dover (2007).

Lovász, L.: Submodular functions and convexity, Mathematical programming, 11th int. Symp., Bonn 1982, pp. 235–257 Muroga, S.: Threshold Logic and Its Applications, Wiley-Interscience, New York (1971)

Peleg, B.: A theory of coalition formation in committees, J. Math. Econom. **7**(2), 115–134 (1980)

Peleg, B.: Coalition formation in simple games with dominant players, Internat. J. Game Theory **10**, 11–33 (1981)

Pippenger, N.: Galois theory for minors of finite functions, Discrete Math. **254**, 405–419 (2002)

Pöschel, R.: Concrete representation of algebraic structures and a general Galois theory. In: Kautschitsch, H., Müller, W. B., Nöbauer, W. (eds.), Contributions to General Algebra (Proc. Klagenfurt Conf., 1978), pp. 249–272, Verlag Johannes Heyn, Klagenfurt (1979)

Post, E.: The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematical Studies, vol. 5, Princeton University Press, Princeton, NJ (1941)

Singer, I.: Extensions of functions of 0-1 variables and applications to combinatorial optimization, Numer. Funct. Anal. Optim. **7**, 23–62 (1984)

Taylor, A., Zwicker, W.: Simple games and magic squares, J. Combin. Theory Ser. A **71** 67–88 (1995)

Topkis, D. M.: Minimizing a submodular function on a lattice, Oper. Res. **26**(2), 305–321 (1978)

Winder, R. O.: Threshold Logic, Ph.D. thesis, Mathematics Department, Princeton University (1962)
