We determine all $m$-ary Boolean functions $f_0,\ldots,f_m$ and $n$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation

\[
f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) =
\]

for all Boolean inputs $\{ z_{ij} : i \in [n], j \in [m] \}$. This extends characterizations by Dokow and Holzman <cit.> (who considered the case $g_0 = \cdots = g_n$) and by Chase, Filmus, Minzer, Mossel and Saurabh <cit.> (who considered the case $g_1 = \cdots = g_n$).

§ INTRODUCTION

When do two Boolean functions commute? Here are some examples:

\[
\bigoplus_{i=1}^n \bigoplus_{j=1}^m z_{ij} =
\bigoplus_{j=1}^m \bigoplus_{i=1}^n z_{ij}, \quad
\bigwedge_{i=1}^n \bigwedge_{j=1}^m z_{ij} =
\bigwedge_{j=1}^m \bigwedge_{i=1}^n z_{ij}, \quad
\bigvee_{i=1}^n \bigvee_{j=1}^m z_{ij} =
\bigvee_{j=1}^m \bigvee_{i=1}^n z_{ij}.
\]

Formally, let $B = \{\mathsf{True},\mathsf{False}\}$. We are looking for functions $f\colon B^n \to B$ and $g\colon B^m \to B$ satisfying

\begin{equation} \label{eq:fg}
f(g(z_{1\cdot}),\ldots,g(z_{n\cdot})) =
g(f(z_{\cdot1}),\ldots,f(z_{\cdot m})),
\end{equation}

or in short,

\[ f \circ g^n = g \circ f^m. \]

The examples above give some solutions for this equation. The first example shows that $f(x_1,\ldots,x_n) = x_1 \oplus \cdots \oplus x_n$ and $g(y_1,\ldots,y_m) = y_1 \oplus \cdots \oplus y_m$ constitute a solution, and the other two examples replace XOR with AND and OR.

Dokow and Holzman <cit.> determined all pairs of functions $(f,g)$ satisfying (<ref>) (in fact, they solved a more general equation, as described below). Ignoring the trivial cases, in which either $f$ or $g$ depends on at most one coordinate, the only solutions are:

* Both $f$ and $g$ are (possibly negated) XORs of a subset of their inputs.

* Both $f$ and $g$ are ANDs of a subset of their inputs.

* Both $f$ and $g$ are ORs of a subset of their inputs.

We explain below what is special about XOR, AND and OR.

Our result We consider a more general equation:

\begin{equation} \label{eq:general}
f_0(g_1(z_{1\cdot}),\ldots,g_n(z_{n\cdot})) =
g_0(f_1(z_{\cdot1}),\ldots,f_m(z_{\cdot m})),
\end{equation}

or in short,

\[ f_0 \circ (g_1,\ldots,g_n) = g_0 \circ (f_1,\ldots,f_m). \]

(See also <Ref> for a pictorial representation.) For reasons we explain below, we call functions $f_0,\ldots,f_n,g_0,\allowbreak\ldots,g_m$ satisfying this identity a generalized polymorphism.

Our main result determines all solutions to <Ref>:

* We first describe the general solution of <Ref>. The general solution is quite complicated, and we consider it a significant contribution of this work. Due to its complexity, we present below in several steps.

* We then prove that our general solution exhausts all solutions of <Ref>. The proof uses Boolean function analysis. In a nutshell, we compute the Fourier expansion of both sides of <Ref>, and compare coefficients. The required argument is long and intricate.

In the remainder of the introduction, we first discuss some relevant background and prior work. We then describe the general solution of <Ref>. Finally, we outline the proof that there are no other solutions.

\[
\begin{array}{|c|c|c|c|c|}
\cline{1-3} \cline{5-5}
z_{11} & \cdots & z_{1m} & \stackrel {g_1}\to & g_1(z_{1\cdot})
\\ \cline{1-3} \cline{5-5}
\vdots & \ddots & \vdots & \raisebox{2pt}{$\stackrel {g_i}\to$} & \vdots
\\ \cline{1-3} \cline{5-5}
z_{n1} & \cdots & z_{nm} & \stackrel {g_n}\to & g_n(z_{n\cdot})
\\ \cline{1-3} \cline{5-5}
\multicolumn{1}{c}{\downarrow \raisebox{1pt}{$\scriptstyle f_1$}} &
\multicolumn{1}{c}{\downarrow \raisebox{1pt}{$\scriptstyle f_j$}} &
\multicolumn{1}{c}{\downarrow \raisebox{1pt}{$\scriptstyle f_m$}} &
\multicolumn{1}{c}{} &
\multicolumn{1}{c}{\downarrow \raisebox{1pt}{$\scriptstyle f_0$}}
\\ \cline{1-3} \cline{5-5}
f(z_{\cdot 1}) & \cdots & f(z_{\cdot m}) & \stackrel {g_0}\to & \ast
\\ \cline{1-3} \cline{5-5}
\end{array}
\]

[Generalized polymorphism: commutative diagram]
$f_0 \circ (g_1,\ldots,g_n) = g_0 \circ (f_1,\ldots,f_m)$ if both ways to compute the bottom-right corner agree (in other words, the diagram commutes).

§.§ Background and prior work
<Ref> is related to the concept of polymorphism appearing in universal algebra. Let $\Sigma$ be a finite alphabet. A relation $P$ on $\Sigma^m$ is a subset of $\Sigma^m$. A function $f\colon \Sigma^n \to \Sigma$ is a polymorphism of $P$ if whenever $z_1,\ldots,z_n \in P$, also $f(z_1,\ldots,z_n) \in P$, where $f(z_1,\ldots,z_n)$ is obtained by applying $f$ to each of the $m$ coordinates, similarly to the way in which the bottom row of <Ref> is generated from the first $n$ rows.

Given a function $g\colon \Sigma^m \to \Sigma$, we can define the corresponding relation $P_g$:

\[
P_g = \{ (z, g(z)) : z \in \Sigma^m \}.
\]

This is an $(m+1)$-ary relation which states that applying $g$ to the first $m$ coordinates results in the last coordinate. <Ref> then holds (for a general alphabet $\Sigma$) precisely when $f$ is a polymorphism of $P_g$.

The generalization of <Ref> to predicates naturally appears in social choice theory.
In social choice theory, a relation is known as a domain, and the function $f\colon \Sigma^n \to \Sigma$ is known as an aggregator. The idea is that $f$ aggregates the opinions of $n$ individuals on various issues. An aggregator is valid if whenever the opinions of all individuals belong to the domain, the aggregated opinions also belong to the domain. A domain in which all polymorphisms are trivial is known as an impossibility domain, following the terminology of Dokow and Holzman <cit.>.

We illustrate this using Arrow's celebrated impossibility theorem <cit.>, in the special case of three candidates. Each individual provides a ranking over three candidates $A,B,C$ by stating whether she prefers $A$ over $B$, whether she prefers $B$ over $C$, and whether she prefers $C$ over $B$. The opinions are then aggregated by applying the function $f$ to each of the three issues. The function $f$ should be chosen so that this results in a ranking.

The domain in this case is the Not-All-Equal (NAE) predicate $\{(x,y,z) \in B^3 : \lnot (x=y=z)\}$, reflecting the fact that a ranking cannot satisfy $A \succ B \succ C \succ A$ or $A \prec B \prec C \prec A$. Arrow's theorem (in one form) states that the only polymorphisms of NAE are projections and anti-projections (known in this context collectively as dictatorships; usually anti-projections are ruled out by introducing an additional constraint). In other words, NAE is an impossibility domain.

It is natural to ask which other relations support only trivial polymorphisms (a polymorphism is trivial if it depends on at most one coordinate), and this question was answered for Boolean predicates (predicates on the alphabet $\Sigma = B$) by Dokow and Holzman <cit.>, continuing a line of work in the theory of judgement aggregation initiated by Wilson <cit.>, List and Pettit <cit.>, and Nehring and Puppe <cit.>. Szegedy and Xu <cit.> make the connection to universal algebra, and show that the Dokow–Holzman characterization essentially follows from Schaefer's dichotomy theorem <cit.> in its modern formulation (see <cit.>).

From this point of view, it is natural to allow the function $f$ to depend on the issue, and this is the problem that Dokow and Holzman <cit.> actually solve. In universal algebra, this corresponds to the multisorted setting, as explained by Szegedy and Xu. In the case of Arrow's theorem, this means that we have three different functions $f_{A\succ B},f_{B\succ C},f_{C\succ A}$, each aggregating the individual opinions on the stated issue. In this more general setting, we obtain new generalized polymorphisms, namely ones in which $(f_{A\succ B}, f_{B\succ C}, f_{C\succ A})$ corresponds to some constant ranking over the candidates.

A relation is a truth-functional agenda if it is of the form $\{ (z,g(z)) : z \in \Sigma^{m_1} \}$, for some $g\colon \Sigma^{m_1} \to \Sigma^{m_2}$. Dokow and Holzman <cit.> determine which Boolean truth-functional agendas are impossibility domains, and describe all non-trivial polymorphisms for possibility domains.[In fact, in some cases they only describe polymorphisms which satisfy some additional constraints, which are motivated by social choice theory.] When $m_2 = 1$ (which suffices in order to solve the general case), this amounts to finding all solutions to the equation

\[
f_0 \circ g^n = g \circ (f_1,\ldots,f_m).
\]

Their proof uses their characterization for general domains <cit.>.

Together with Minzer, Mossel and Saurabh <cit.>, we gave an alternative proof of this characterization using Boolean function analysis. We actually solved a slightly more general equation:

\[
f_0 \circ g^n = h \circ (f_1,\ldots,f_m).
\]

The same technique was used (independently) by Zhang <cit.> to determine all solutions to <Ref>.[We thank Reshef Meir for pointing us to this paper.]
In this work we use similar techniques to solve <Ref>, answering an open question in <cit.>.

Kalai <cit.> used Boolean function analysis to prove a quantitative version of Arrow's theorem, initiating a long line of work <cit.>. This line of work classifies functions $f$ which are approximate polymorphisms of NAE, in the sense that when the “votes” are chosen at random from the domain of NAE and aggregated according to $f$, then the result satisfies NAE with high probability. Functions satisfying this condition must be close to a projection or to an anti-projection.

Nehama <cit.> proved a similar result for the truth-functional predicate $P_\land = \{(x,y,z) \in B^3 : x \land y = z\}$, appearing in classic work of Kornhauser and Sager <cit.> and further considered by List and Pettit <cit.>. The paper of Kornhauser and Sager introduced the doctrinal paradox, which states that the majority function is not even an approximate polymorphism of $P_\land$. The only exact polymorphisms are oligarchies (conjunctions of a subset of the coordinates) and the constant zero function. Nehama showed that every approximate polymorphism of $P_\land$ is close to an exact polymorphism.
Nehama's results were improved quantitatively in <cit.> using techniques from Boolean function analysis, and were generalized to arbitrary truth-functional predicates in <cit.>.

§.§ Main theorem

We now discuss what the solutions to <Ref> look like. We start by describing simple solutions, and work up to the general case.

Simplifying assumptions
Let us start with some simplifying assumptions. If one of the functions $f_1,\ldots,f_m$ is constant, then we can fix its value in $g_0$, and so obtain a solution to <Ref> on a smaller domain. Therefore we can assume that $f_1,\ldots,f_m$ are not constant. Similarly, we can assume that $g_1,\ldots,g_n$ are not constant. By similarly restricting the domains of $f_0$ and $g_0$, we can assume that these functions depend on all inputs.

We proceed with some trivial solutions to <Ref>. If $f_0$ is constant (equivalently, $n = 0$) then since $f_1,\ldots,f_m$ are non-constant, $g_0$ must be constant as well (equivalently, $m = 0$). If $f_0$ depends on a single input then $f_0$ is either the identity or its negation. In the first case, <Ref> reads

\[
g_1(z_1,\ldots,z_m) = g_0(f_1(z_1),\ldots,f_m(z_m)),
\]

and in the second case, it reads.

\[
\lnot g_1(z_1,\ldots,z_m) = g_0(f_1(z_1),\ldots,f_m(z_m))
\]

Each of $f_1,\ldots,f_m$ is itself either the identity or its negation, and given $f_1,\ldots,f_m$, we can determine $g_1$ in terms of $g_0$ (or vice versa).

From now on, we assume that $f_0,g_0$ have at least two inputs and depend on all of them, and that $f_1,\ldots,f_m,g_1,\ldots,g_n$ are non-constant. We will describe the solution in two stages. First, we describe (in steps) the  solution when no $f_j,g_i$ is a dictator. Then we tackle the general case.

§.§.§ No dictators

At this point, it will be useful to consider a numerical encoding of $B$. We encode  as $-1$ and  as $1$ (this ensures that XOR translates to multiplication). Our choice of $\pm1$ rather than $0,1$ reflects the duality between AND and OR.

Here is one parametric solution of <Ref>:

\begin{equation} \label{eq:full-block}
\begin{aligned}
f_0 &= K \prod_{i=1}^n \frac{x_i + D_i}{C_i} + L, &
g_i &= C_i \prod_{j=1}^m (y_j + \kappa_{ij}) - D_i, \\
g_0 &= K \prod_{j=1}^m \frac{y_j + B_j}{A_j} + L, &
f_j &= A_j \prod_{i=1}^n (x_i + \kappa_{ij}) - B_j.
\end{aligned}
\end{equation}

Indeed, it is easy to check that both sides of <Ref> are equal to

\begin{equation} \label{eq:full-block-z}
K\prod_{i=1}^n \prod_{j=1}^m (z_{ij} + \kappa_{ij}) + L.
\end{equation}

<Ref> features functions of the form

\begin{equation} \label{eq:affine-character}
f(x_1,\ldots,x_n) = A \prod_{i=1}^n (x_i + \kappa_i) - B.
\end{equation}

This form captures several different Boolean functions:

* When $\kappa_1 = \cdots = \kappa_n = 0$, $A = \pm 1$, and $B = 0$, this is XOR (if $A = 1$) or its negation (if $A = -1$).

* When $\kappa_1,\ldots,\kappa_n,B \in \{\pm1\}$ and $A = 2B/\prod_{i=1}^n (2\kappa_i)$, this is an OR of literals (if $B = 1$) or an AND of literals (if $B = -1$). Indeed, in this case we can write

\begin{equation} \label{eq:AND-OR-like}
f(x_1,\ldots,x_n) = 2B \prod_{i=1}^n \frac{\kappa_i x_i + 1}{2} - B.
\end{equation}

(Note $x \mapsto \frac{x+1}{2}$ transforms $\{-1,1\}$ to $\{0,1\}$.)
We have $f(x) = B$ if $(x_1,\ldots,x_n) = (\kappa_1,\ldots,\kappa_n)$, and $f(x) = -B$ otherwise.

A short argument shows that these are in fact the only Boolean functions of the form given by <Ref>.

Applying this to <Ref>, we discover that either all functions are XOR-like (first case above), or all of them are AND/OR-like (second case above).

Single block

All variables $z_{ij}$ appear in <Ref>, which corresponds to the parametric solution given by <Ref>. However, this is not necessary. Given any subset $Z_0 \subseteq [n] \times [m]$, we can consider the following more general solution:

\begin{equation} \label{eq:single-block}
\begin{aligned}
f_0 &= K \prod_{i=1}^n \frac{x_i + D_i}{C_i} - L, &
g_i &= C_i \prod_{j\colon (i,j) \in Z_0} (y_j + \kappa_{ij}) - D_i, \\
g_0 &= K \prod_{j=1}^m \frac{y_j + B_j}{A_j} - L, &
f_j &= A_j \prod_{i\colon (i,j) \in Z_0} (x_i + \kappa_{ij}) - B_j.
\end{aligned}
\end{equation}

In this case, both sides of <Ref> amount to

\begin{equation} \label{eq:single-block-z}
K\prod_{(i,j) \in Z_0} (z_{ij} + \kappa_{ij}) - L.
\end{equation}

Once again, the classification of Boolean functions of the form given by <Ref> shows that either all functions are XOR-like, or all of them are AND/OR-like.

In more detail, either $L = 0$ (XOR-like case) or $L \in \{\pm1\}$ (AND/OR-like case). We describe these two cases separately.

When $L = 0$, we must have $D_i = 0$ for all $i \in [n]$ and $B_j = 0$ for all $j \in [m]$, and consequently $K,A_j,C_i \in \{\pm 1\}$. The solution is therefore

\begin{align*}
f_0 &= K \prod_{i=1}^n C_i x_i, &
g_i &= C_i \prod_{j\colon (i,j) \in Z_0} y_j, \\
g_0 &= K \prod_{j=1}^m A_j y_j, &
f_j &= A_j \prod_{i\colon (i,j) \in Z_0} x_i.
\end{align*}

Each function is either XOR or its negation. The two sides of <Ref> are both equal to

\[
K \prod_{(i,j) \in Z_0} z_{ij},
\]

and so there are no further constraints.

When $L \in \{\pm 1\}$, we must have $D_i,B_j \in \{\pm 1\}$ for all $i \in [n]$ and $j \in [m]$, and consequently $\kappa_{ij} \in \{\pm1\}$ for all $(i,j) \in Z_0$. Using the formulation in <Ref>, the solution becomes

\begin{align*}
f_0 &= 2L \prod_{i=1}^n \frac{D_i x_i + 1}{2} - L, &
g_i &= 2D_i \prod_{j\colon (i,j) \in Z_0} \frac{\kappa_{ij} y_j + 1}{2} - D_i, \\
g_0 &= 2L \prod_{j=1}^m \frac{B_j y_j + 1}{2} - L, &
f_j &= 2B_j \prod_{i\colon (i,j) \in Z_0} \frac{\kappa_{ij} x_i + 1}{2} - B_j.
\end{align*}

Each functions is either AND or OR, and the arguments may be negated. The two sides of <Ref> are both equal to

\[
2L \prod_{(i,j) \in Z_0} \frac{\kappa_{ij} z_{ij} + 1}{2} - L,
\]

and so there are no further constraints.

Multiple blocks We can generalize <Ref> even further by allowing several subsets $Z_1,\ldots,Z_k$ which are row- and column-disjoint. Suppose that for each $\ell \in [k]$, we are given an arbitrary subset $Z_\ell \subseteq I_\ell \times J_\ell$, where $I_1,\ldots,I_k$ are a partition of $[n]$ and $J_1,\ldots,J_k$ are a partition of $[m]$.

First, let us define $f_1,\ldots,f_m$ and $g_1,\ldots,g_n$. If $i \in I_\ell$ then

\[
g_i = C_i \prod_{j \colon (i,j) \in Z_\ell} (y_j + \kappa_{ij}) - D_i.
\]

Similarly, if $j \in J_\ell$ then

\[
f_j = A_j \prod_{i \colon (i,j) \in Z_\ell} (x_i + \kappa_{ij}) - B_j.
\]

For each block $\ell \in [k]$, we define

\begin{align*}
f_0^{(\ell)} &= K_\ell \prod_{i \in I_\ell} \frac{x_i + D_i}{C_i} - L_\ell, \\
g_0^{(\ell)} &= K_\ell \prod_{j \in J_\ell} \frac{y_j + B_j}{A_j} - L_\ell.
\end{align*}

For an arbitrary function $h\colon \{\pm1\}^k \to \{\pm1\}$, we define

\begin{align*}
f_0 &= h(f_0^{(1)}, \ldots, f_0^{(k)}), \\
g_0 &= h(g_0^{(1)}, \ldots, g_0^{(k)}).
\end{align*}

The two sides of <Ref> are then both equal to

\[
h\left(K_1 \prod_{(i,j) \in Z_1} (z_{ij} + \kappa_{ij}) - L_1, \ldots, K_k \prod_{(i,j) \in Z_k} (z_{ij} + \kappa_{ij}) - L_k\right).
\]

It turns out that this is the general solution when the functions $f_1,\ldots,f_m,g_1,\ldots,g_n$ all depend on at least two inputs, as we show in <Ref>. As before, for each $\ell \in [k]$, either all the functions involving block $\ell$ are XOR-like, or all of them are AND/OR-like.

§.§.§ General case

Warm-up The situation becomes more complicated when we allow the functions $f_1,\ldots,f_m,g_1,\ldots,g_n$ to depend on a single input; we call such functions dictators. A dictator $\phi$ can be a projection $\phi(z) = z_i$ or an anti-projection $\phi(z) = -z_i$.

We start by describing a single block solution which is XOR-like and in which all dictators are projections (rather than anti-projections). As before, there is a subset $Z \subseteq I \times J$, where $I = [n]$ and $J = [m]$. We assume that all rows and columns contain some element of $Z$, and furthermore, that there are no “isolated” elements, which are unique in their row and column.

We decompose $I$ into two parts: $I^{=1}$ consists of those rows which contain a single element of $Z$, and $I^{\ge2}$ consists of the remaining rows, which contain at least two elements of $Z$. We decompose $J$ similarly into two parts, $J^{=1}$ and $J^{\ge2}$.

We proceed to decompose $Z$ into several parts. The main part is $Z^{\ge 2} = Z \cap (I^{\ge2} \times J^{\ge2})$. For each row $i \in I^{\ge2}$, let $P_i$ consist of all columns $j$ such that $(i,j)$ is the unique element of $Z$ in column $j$. Similarly, for each column $j \in J^{\ge2}$, let $Q_j$ consist of all rows $i$ such that $(i,j)$ is the unique element of $Z$ in row $i$. This covers all elements in $Z$ (if we identify $P_i$ with $\{(i,j) : j \in P_i\}$ and $Q_j$ with $\{(i,j) : i \in Q_j\}$) by our assumption that there are no isolated elements, which implies that $Z \cap (I^{=1} \times J^{=1}) = \emptyset$. See <Ref> for a pictorial representation.

(0,0) – (0,2) – (2,2) – (2,0) – cycle;
at (1,1) $Z^{\ge 2}$;
(2.2,1.33) – (2.2,2) – (3.2,2) – (3.2,1.33) – cycle;
(3.4,0.67) – (3.4,1.33) – (4.4,1.33) – (4.4,0.67) – cycle;
(4.6,0) – (4.6,0.67) – (5.6,0.67) – (5.6,0) – cycle;
(0,-.2) – (0,-1.2) – (.67,-1.2) – (.67,-.2) – cycle;
(.67,-1.4) – (.67,-2.4) – (1.33,-2.4) – (1.33,-1.4) – cycle;
(1.33,-2.6) – (1.33,-3.6) – (2,-3.6) – (2,-2.6) – cycle;
at (2.7,1.67) $P_1$;
at (3.9,1) $P_2$;
at (5.1,0.33) $P_3$;
at (0.33,-.7) $Q_1$;
at (1,-1.9) $Q_2$;
at (1.67,-3.1) $Q_3$;
[stealth-stealth] (0,2.2) – node [midway,above] $J^{\ge2}$ (2,2.2);
[stealth-stealth] (2.2,2.2) – node [midway,above] $J^{=1}$ (5.6,2.2);
[stealth-stealth] (-0.2,0) – node [midway,left] $I^{\ge2}$ (-0.2,2);
[stealth-stealth] (-0.2,-0.2) – node [midway,left] $I^{=1}$ (-0.2,-3.6);

[Decomposition of the input matrix]Decomposition of $Z$ into a central part $Z^{\ge 2}$, rows $P_i$, and columns $Q_j$. As the figure illustrates, $Z$ need not be a rectangle.

For each $i \in I^{\ge2}$, we have a function $p_i\colon \{\pm1\}^{P_i} \to \{\pm1\}$, and for each $j \in J^{\ge2}$, we have a function $q_j\colon \{\pm1\}^{Q_j} \to \{\pm1\}$. We can now describe the solution.

If $i \in I^{\ge2}$ then we define

\[
g_i(y) = \prod_{j\colon (i,j) \in Z^{\ge2}} y_j \times p_i(y|_{P_i}),
\]

where $y|_{P_i}$ is the projection of $y$ to the coordinates in $P_i$. If $i \in I^{=1}$ then $i \in Q_j$ for some $j \in J^{\ge2}$, and we define

\[
g_i(y) = y_j.
\]

Similarly, if $j \in J^{\ge2}$ then we define

\[
f_j(x) = \prod_{i\colon (i,j) \in Z^{\ge2}} x_i \times q_j(x|_{Q_j}).
\]

If $j \in J^{=1}$ then $j \in P_i$ for some $i \in I^{\ge2}$, and we define

\[
f_j(x) = x_i.
\]

We now define $f_0$ and $g_0$:

\begin{align*}
f_0(x) &= \prod_{i \in I^{\ge2}} x_i \times \prod_{j \in J^{\ge2}} q_j(x|_{Q_j}), \\
g_0(y) &= \prod_{j \in J^{\ge2}} y_j \times \prod_{i \in I^{\ge2}} p_i(y|_{P_i}).
\end{align*}

Both sides of <Ref> are equal to

\[
\prod_{(i,j) \in Z^{\ge2}} z_{ij} \times \prod_{i \in I^{\ge2}} p_i(z|_{i,P_i}) \times \prod_{j \in J^{\ge2}} q_j(z|_{Q_j,j}),
\]

where $z|_{i,P_i}$ is the restriction of $z$ to $\{(i,j) : j \in P_i\}$, and $z|_{Q_j,j}$ is defined analogously.

If $J^{=1} = I^{=1} = \emptyset$ then this is just a special case of the single block solution described in <Ref>. Conversely, if $J^{\ge2} = \emptyset$ and $I^{\ge2}$ is a singleton then this is a special case of the trivial solution with $n = 1$, while if $I^{\ge2} = \emptyset$ and $J^{\ge2}$ is a singleton then this is a special case of the trivial solution with $m = 1$. The solution described above is some kind of common generalization of all of these.

Single block

There are two ways in which the single block solution is not general. First, the dictatorial $f_j,g_i$ could be anti-projections rather than projections. Second, the solution we presented takes the special case $A=1,B=0$ of <Ref>. Here is the more general form.

If $i \in I^{\ge2}$ then

\[
g_i(y) = C_i \prod_{j\colon (i,j) \in Z^{\ge2}} (y_j + \kappa_{ij}) \times (p_i(y|_{P_i}) + \sigma_i) - D_i.
\]

If $i \in I^{=1}$ then $i \in Q_j$ for some $j \in J^{\ge2}$, and then

\[
g_i(y) = \mu_i y_j,
\]

where $\mu_i \in \{\pm1\}$.

Similarly, if $j \in J^{\ge2}$ then

\[
f_j(x) = A_j \prod_{i\colon (i,j) \in Z^{\ge2}} (x_i + \kappa_{ij}) \times (q_j(x|_{Q_j}) + \tau_j) - B_j.
\]

If $j \in J^{=1}$ then $j \in P_i$ for some $i \in I^{\ge2}$, and then

\[
f_j(x) = \lambda_j x_i,
\]

where $\lambda_j \in \{\pm1\}$.

We now define $f_0$ and $g_0$:

\begin{align*}
f_0(x) &= K \prod_{i \in I^{\ge2}} \frac{x_i + D_i}{C_i} \times \prod_{j \in J^{\ge2}} (q_j(\mu_i x_i |_{i \in Q_j}) + \tau_j) - L, \\
g_0(y) &= K \prod_{j \in J^{\ge2}} \frac{y_j + B_j}{A_j} \times \prod_{i \in I^{\ge2}} (p_i(\lambda_j y_j |_{j \in P_i}) + \sigma_i) - L.
\end{align*}

Here the input to $q_j$ consists of $x|_{Q_j}$, with the $i$'th entry multiplied by $\mu_i$, and the input to $p_i$ consists of $y|_{P_i}$ with the $j$'th entry multiplied by $\lambda_j$.

Both sides of <Ref> are equal to

\[
K \prod_{(i,j) \in Z^{\ge2}} (z_{ij} + \kappa_{ij}) \times \prod_{i \in I^{\ge2}} (p_i(z_{iP_i}) + \sigma_i) \times \prod_{j \in J^{\ge2}} (q_j(z_{Q_jj}) + \tau_j) - L.
\]

Since all functions involved are Boolean, there are constraints imposed on the various parameters. These constraints imply that either all functions are XOR-like, or all of them are AND/OR-like.

In more detail, if $L = 0$ then $D_i = \sigma_i = 0$ for all $i \in I^{\ge2}$ and $B_j = \tau_j = 0$ for all $j \in J^{\ge2}$. Consequently, $\kappa_{ij} = 0$ for all $(i,j) \in Z^{\ge2}$, and the remaining parameters $K,C_i,A_j$ each belong to $\{\pm1\}$. The non-dictatorial functions become

\begin{align*}
f_0 &= K \prod_{i \in I^{\ge2}} x_i \times \prod_{j \in J^{\ge2}} q_j(\mu_ix_i|_{i \in Q_j}), &
g_i &= C_i \prod_{j\colon (i,j) \in Z^{\ge2}} y_j \times p_i(y|_{P_i}), \\
g_0 &= K \prod_{j \in J^{\ge2}} y_j \times \prod_{i \in I^{\ge2}} p_i(\lambda_jy_j|_{j \in P_i}), &
f_j &= A_j \prod_{i\colon (i,j) \in Z^{\ge2}} x_i \times q_j(x|_{Q_j}).
\end{align*}

Conversely, if $L \in \{\pm1\}$ then $D_i,\sigma_i \in \{\pm1\}$ for all $i \in I^{\ge2}$ and $B_j,\tau_j \in \{\pm1\}$ for all $j \in J^{\ge2}$. Consequently, $\kappa_{ij} \in \{\pm1\}$ for all $(i,j) \in Z^{\ge2}$, and the remaining parameters $K,C_i,A_j$ are chosen so that all functions are AND/OR-like. Using the representation in <Ref>, the non-dictatorial functions become

\begin{align*}
f_0 &= 2L \prod_{i \in I^{\ge2}} \frac{D_i x_i + 1}{2} \times \prod_{j \in J^{\ge2}} \frac{\tau_j q_j(\mu_ix_i|_{i \in Q_j}) + 1}{2} - L, \\
f_j &= 2B_j \prod_{i\colon (i,j) \in Z} \frac{\kappa_{ij} x_i + 1}{2} \times \frac{\tau_j q_j(x|_{Q_j}) + 1}{2} - B_j, \\
g_i &= 2D_i \prod_{j\colon (i,j) \in Z} \frac{\kappa_{ij} y_j + 1}{2} \times \frac{\sigma_i p_i(y|_{P_i}) + 1}{2} - D_i, \\
g_0 &= 2L \prod_{j \in J^{\ge2}} \frac{B_j y_j + 1}{2} \times \prod_{i \in I^{\ge2}} \frac{\sigma_i p_i(\lambda_jy_j|_{j \in P_i}) + 1}{2} - L.
\end{align*}

Multiple blocks

In the general case, we might have multiple blocks. Each block is either in the form just described, or is a degenerate block $Z = \{(i,j)\}$. In the degenerate case, which we describe for simplicity for $n = m = 1$, all functions involved are dictators, and the signs have to agree:

\begin{align*}
f_0(x) &= \alpha x_1, & g_1(y) &= \beta y_1, \\
g_0(y) &= \gamma y_1, & f_1(x) &= \delta x_1,
\end{align*}

where $\alpha,\beta,\gamma,\delta \in \{\pm1\}$ satisfy $\alpha\beta = \gamma\delta$.

As in <Ref>, we have a partition $I_1,\ldots,I_k$ of $[n]$ and a partition $J_1,\ldots,J_k$ of $[m]$. For each $\ell \in [k]$, we are given a subset $Z_\ell \subseteq I_\ell \times J_\ell$, which gives rise to a solution involving $f_j$ for $j \in J_\ell$, $g_i$ for $i \in I_\ell$, and two functions $f_0^{(\ell)},g_0^{(\ell)}$. Moreover, each $Z_\ell$ is either a singleton, in which case the solution is described in the preceding paragraph, or $Z_\ell$ has no empty rows and columns and no isolated elements, in which case the solution is as described in the preceding part.

As in <Ref>, the final solution is given by

\begin{align*}
f_0 &= h(f_0^{(1)},\ldots,f_0^{(k)}), \\
g_0 &= h(g_0^{(1)},\ldots,g_0^{(k)}),
\end{align*}

for an arbitrary function $h\colon \{\pm1\}^k \to \{\pm1\}$.

This is the general solution under the simplifying assumptions we made at the outset of <Ref>. From this, it is straightforward to state the general solution to <Ref>. The formal statement appears in <Ref>.

§.§ On the proof

The main idea driving our approach is the identification of functions $f\colon \{\pm1\}^n \to \{\pm1\}$ with multilinear polynomials, provided by the “fundamental theorem of Boolean function analysis”. According to this theorem, every function $f\colon \{\pm1\}^n \to \mathbb{R}$ has a unique representation as a multilinear polynomial, known as its Fourier expansion:

\[
f(x_1,\ldots,x_n) = \sum_{S \subseteq [n]} \hat{f}(S) x_S, \quad x_S = \prod_{i \in S} x_i.
\]

The coefficients $\hat{f}(S)$ are called Fourier coefficients.

Since the Fourier expansion is unique, the functions $f_0,\ldots,f_m,g_0,\ldots,g_n$ form a generalized polymorphism if and only if the Fourier coefficients of $f_0 \circ (g_1,\ldots,g_n)$ and $g_0 \circ (f_1,\ldots,f_m)$ coincide.
This suggests the following two-step approach:

* Find all multilinear polynomials $f_0,\ldots,f_m,g_0,\ldots,g_n$ such that $f_0 \circ (g_1,\ldots,g_n) = g_0 \circ (f_1,\ldots,f_m)$.

* Deduce the main theorem by identifying those multilinear solutions which are Boolean-valued.

While this plan can be carried out in simpler cases, such as the equation $f \circ g^n = g \circ f^m$ or the more complicated equation considered in <cit.>, there are certain complications which prevent us from accomplishing the first step in full generality, and we have to put further restrictions on the functions, which stem from their being Boolean. Concretely, we assume that if $\deg f = 1$ then $f$ is a projection $x_i$ or an anti-projection $-x_i$, and this enables us to follow the plan.

By substituting the Fourier expansions of $g_1,\dots,g_n$ into the Fourier expansion of $f_0$, we obtain that the Fourier expansion of $f_0 \circ (g_1,\ldots,g_n)$ is

\[
\sum_{S \subseteq [n]} \sum_{\substack{T_i \subseteq [m] \\ \text{for } i \in S} } \hat{f}_0(S) \prod_{i \in S} \hat{g}_i(T_i) \prod_{i \in S} \prod_{j \in T_i} z_{ij}.
\]

Given a monomial $z_W = \prod_{(i,j) \in W} z_{ij}$, we can almost identify which sets $S,(T_i)_{i \in S}$ it came from. Let $I$ be the set of $i$ appearing in $W$. Then $S \supseteq I$; for each $i \in I$, $T_i = \{ j : (i,j) \in W \}$; and for each $i \notin I$, $T_i = \emptyset$.

The situation becomes a lot simpler if $\hat{g}_i(\emptyset) = 0$ for all $i \in [n]$, in which case the ambiguity regarding the provenance of a monomial $z_W$ disappears. Therefore in the proof we replace each $g_i$ with $G_i = g_i - \mathbb{E}[g_i]$, and replace $f_0$ accordingly with $F_0(x_1,\ldots,x_n) = f_0(x_1 + \mathbb{E}[g_1], \dots, x_n + \mathbb{E}[g_n])$, so that $F_0 \circ (G_1,\ldots,G_n) = f_0 \circ (g_1,\ldots,g_n)$.

Defining $G_0,F_1,\ldots,F_m$ analogously, the functions $F_0,\ldots,F_m,G_0,\ldots,G_n$ are also a generalized polymorphism, but they are no longer Boolean. Nevertheless, it is still the case that if $\deg F = 1$ then $F$ is a projection or an anti-projection.

Following these manipulations, we can state the basic identity which drives our entire approach. Let $F_0,\ldots,F_m,G_0,\ldots,G_n$ be a generalized polymorphism. Let $W \subseteq [n] \times [m]$. Suppose that $S$ is its projection to the first coordinate; that $T$ is its projection to the second coordinate; that for each $i \in S$, $T_i = \{ j : (i,j) \in W \}$; and that for each $j \in T$, $S_j = \{ i : (i,j) \in W \}$. The coefficients of $z_W$ in the Fourier expansions of $F_0 \circ (G_1,\ldots,G_n)$ and $G_0 \circ (F_1,\ldots,F_m)$ must coincide, and therefore

\begin{equation} \label{eq:main-eq}
\hat{F}_0(S) \prod_{i \in S} \hat{G}_i(T_i) =
\hat{G}_0(T) \prod_{j \in T} \hat{F}_j(S_j).
\end{equation}

We typically use this identity in the following way: given sets $S,(T_i)_{i \in S}$ in the supports of the relevant Fourier expansions (a set is in the support if the Fourier coefficient is non-zero), we calculate the sets $T,(S_j)_{j \in T}$, which must be in the supports of their relevant Fourier expansions.

Shifting the inputs

Consider once more the simpler equation $f \circ g^n = g \circ f^m$, and suppose that $\deg(f),\deg(g) \ge 2$, and that $f,g$ are Boolean and depend on all coordinates. Let $F = f - \mathbb{E}[f]$ and $G = g - \mathbb{E}[g]$. Using the ideas described above, we can show that $\hat{F}([n]) \neq 0$. Let $\Phi(x_1,\dots,x_n) = F(x_1 - \kappa,\dots,x_n - \kappa)$. Then

\[
\Phi(x) = \hat{F}([n]) x_{[n]} + (\hat{F}([n-1]) - \kappa \hat{F}([n])) x_{[n-1]} + \cdots,
\]

where the dots contain the remainder of the Fourier expansion. Choosing $\kappa$ judiciously, we can guarantee that $\hat\Phi([n-1]) = 0$. Amazingly, this implies that $\Phi(x) = C x_{[n]}$ for some constant $C \in \R$, and that by shifting the inputs to $G$ in the same way, we get $C y_{[m]}$.
Since $f,g$ are Boolean, we deduce that they must be AND, OR, XOR, or negated XOR.

In our case, we need to choose different shifts for different $f_j$, and furthermore, the shifts depend on the coordinate. This is how we get the $\kappa_{ij}$ parameters. This time, $F,G$ don't simplify to a simple monomial, but rather to the more complex formulas given above.

Paper organization We start with some preliminaries in <Ref>. We then prove <Ref>, which characterizes all generalized polymorphisms when all functions have degree at least $2$, in <Ref>, as an extended warm-up. We prove our main result, <Ref>, in <Ref>.

Acknowledgements This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.

This project constitutes the MSc thesis of the first author. We thank the thesis committee for their careful reading of the manuscript and helpful comments.

§ PRELIMINARIES

§.§ Basic definitions

We use standard notations, as seen in O'Donnell's excellent monograph <cit.>. All results concerning Boolean function analysis stated without proof can be found there.

The notation $z_{IJ}$ refers to the monomial $\prod_{i \in I} \prod_{j \in J} z_{ij}$. We also use similar self-explanatory notations such as $z_{iJ},z_{Ij}$. Similarly, the notation \(x_S\) refers to the monomial \(\prod_{i\in S} x_i\). A similar notation which we sometimes use, \(z|_{i,J}\), refers to the vector \((z_{ij_1},\dots,z_{ij_{r}})\), where \(J = \left\{ j_1,\dots,j_r \right\} \subseteq [m]\), and similarly \(z|_{I,j} = \left( z_{i_1j},\dots, z_{i_tj} \right)\), where \(I = \left\{i_1,\dots,i_t  \right\}\).

We use $[n]$ for $\{1,\ldots,n\}$. The Boolean cube is the set \(\left\{ -1,1 \right\}^{n}\). Unless stated differently, all functions denoted by \(f\) in this section are on the Boolean cube. For any \(S\subseteq [n]\), the Fourier character \(\chi_S \colon \left\{ -1,1 \right\}^{n} \to \left\{ -1,1 \right\}\) is defined by

\[
\chi_S(x) = \prod_{i\in S} x_i.
\]

In particular, $\chi_\emptyset$ is the constant $1$ function.

The coefficient of the monomial $\chi_S(x)$ in a polynomial $f(x)$ is denoted by $\hat{f}(S)$. For any monomial \(p(x) = \prod_{S\subseteq [n]} x_i \), the polynomial \(q(x)\) is called a shift of \(p(x)\) if there are constants \(\kappa_1,\dots,\kappa_n\) such that \(q(x) = p(x_1 + \kappa_1,\dots, x_n + \kappa_n)\). The polynomial \(q'(x)\) is called an affine shift of \(p(x)\) if there are also constants \(\kappa_0 \neq 0,\kappa_\emptyset\) such that \(q'(x) = \kappa_0 \cdot p(x_1 + \kappa_1,\dots, x_n + \kappa_n) + \kappa_{\emptyset}\). If \(\kappa_0 = 1\), the affine shift is also called a shifted translation.

The Fourier expansion theorem shows that every real function on the Boolean cube can be uniquely expressed as a multilinear real polynomial:

Every function \(f \colon \left\{ -1,1  \right\}^n \to \R\) can be uniquely expressed as a multilinear polynomial

\[
f(x) = \sum_{S\subseteq [n]} \hat{f}(S)\chi_S(x).
\]

This expression is called the Fourier expansion of \(f\), and in this context we refer to \(\hat{f}(S)\) as the Fourier coefficient of \(f\) on \(S\). Collectively, the coefficients are called the Fourier spectrum of \(f\). The sets $S \subseteq [n]$ for which $\hat{f}(S) \neq 0$ form the Fourier support of $f$, denoted $\supp(\hat{f})$.

In this work, we implicitly identify functions on $\{-1,1\}^n$ with multilinear polynomials. Given a multilinear polynomial $f$ on the variables $x_1,\dots,x_n$ and a set $S \subseteq [n]$, the Fourier coefficient $\hat{f}(S)$ is the coefficient of the monomial $\chi_S(x)$. We similarly extend the definition of $\supp(\hat{f})$.

For any \(f \colon \left\{ -1,1 \right\}^n \to \R\), inclusion-maximal sets in \(\supp(\hat{f})\) are invariant under shifted translations of \(f\):

Let \(f \colon \left\{ -1,1 \right\}^n \to \R\) be some nonconstant function, let \(F\) be some shifted translation of \(f\), and let \(S \subseteq [n]\) be some set in \(\supp(\hat{f})\). Then \(S\) is inclusion-maximal in \(\supp(\hat{f})\) if and only if it is inclusion-maximal in \(\supp(\hat{F})\).

The function \(f\) is not constant, therefore \(|S| \geq 1\). If we substitute $x_i = x_i + \kappa_i$ in the Fourier expansion of $f$, then the only contribution to $\prod_{i \in S} x_i$ comes from $\prod_{i \in S} (x_i + \kappa_i)$, showing that $\hat{F}(S) = \hat{f}(S) \neq 0$, and so $S \in \supp(\hat{F})$. If $S$ were not inclusion-maximal in $\supp(\hat{F})$, say $S \subsetneq S' \in \supp(\hat{F})$, then an identical argument shows that $S' \in \supp(\hat{f})$, contradicting the inclusion-maximality of $S$ in $\supp(\hat{f})$. Therefore $S$ is inclusion-maximal in $\supp(\hat{F})$.

The mean of a real function is defined as \(\E_{x \sim \left\{ -1,1 \right\}^n}f = \hat{f}(\emptyset)\). For notational simplicity, the notation \(\E f\) will always refer to \(\E_{x\sim \left\{ -1,1 \right\}^n}\), where \(\left\{ -1,1 \right\}^{n}\) is the domain of the function \(f\). A balanced, or unbiased real function is a function whose mean vanishes, that is \(\E f = 0\).

For any two \(S,T\subseteq [n]\) we have

\[ \E\left[ \chi_S(x) \cdot \chi_T(x) \right] = \begin{cases}
1, & \text{ if \(S = T\)},\\
0, & \text{otherwise},
\end{cases}
\]

and in particular

\[ \E\left[ \chi_S(x) \right] = \E\left[ \chi_S(x)\cdot 1 \right] = \E\left[ \chi_S(x)\cdot \chi_{\emptyset}(x) \right] = \begin{cases}
1, & \text{ if \(S = \emptyset\)},\\
0, & \text{otherwise}.
\end{cases}
\]

In other words, the Fourier characters are orthonormal with respect to the inner product $\langle f,g \rangle = \E[fg]$. In fact, they form an orthonormal basis of the space of real functions on $\left\{-1,1\right\}^n$.

From the linearity of expectation, this implies the following useful method for computing Fourier coefficients:

Let \(f\colon \left\{ -1,1 \right\}^n \to \R\) and \(S\subseteq [n]\), then

\[
\hat{f}(S) = \E[f(x)\cdot\chi_S(x)].
\]

Using this proposition and the linearity of expectation, we can describe the 2-norm of a function \(f\) in terms
of its Fourier coefficients. This important result is called
Parseval's theorem:

For any \(f \colon \left\{  -1,1 \right\}^{n} \rightarrow \R\),

\[
\left\lVert f \right\rVert_{2}^2 \coloneqq \E_{\mathbf{x}}\left[ f(\mathbf{x})^2 \right] = \sum_{S \subseteq [n]} \hat{f}(S)^2
\]

With the Fourier expansion theorem in mind, for any real function on the cube we define \(\deg(f)\) to be the degree of its (unique) Fourier expansion (as a polynomial).

For any real \(f\), the support of its Fourier expansion is the family of sets \(\supp(\hat{f}) = \left\{ S \subseteq [n] \;\middle|\; \hat{f}(S) \neq 0 \right\}\).

For any coordinate \(i\in [n]\) of \(f(x)\), we say that \(i\) is relevant for \(f\), or equivalently that \(f(x)\) depends on \(x_i\), if there exists at least one \(x\in \left\{ -1,1 \right\}^n\) such that \(f\left( x^{(i\rightarrow 1)} \right) \neq f\left( x^{(i\rightarrow -1)} \right)\), where $x^{(i\to b)}$ is obtained from $x$ by setting the $i$'th coordinate to $b$. The \(i\)'th discrete derivative of \(f\) is the operator

\[
\D_if(x) \coloneqq \frac{f\left( x^{(i\rightarrow 1)} \right) - f\left( x^{(i\rightarrow -1)} \right)}{2} = \sum_{\substack{S \subseteq [n] \\
i\in S}} \hat{f}(S)\prod_{j\in S - i} x_j.
\]

Observe that \(i\) is relevant for \(f \colon \left\{ -1,1 \right\}^n \to \R\) if and only if \(\left\lVert \D_if(x) \right\rVert_2^2   > 0 \).

Relevance is in fact encoded in the Fourier expansion of \(f\):

Let \(f\colon\left\{ -1,1 \right\}^n \to \R\) and let \(i\in [n]\). Then \(i\) is relevant for \(f\) if and only if there exists \(S\in \supp(\hat{f})\) such that \(i\in S\).

Suppose that \(i\not\in S\) for any \(S\in \supp(\hat{f})\), then \(x_i\) does not appear in any term of <Ref>. In particular, the polynomial \(f\left( x^{(i\rightarrow 1)} \right)\) equals the polynomial \(f\left( x^{(i\rightarrow -1)} \right)\) for any \(x\in \left\{ -1,1 \right\}^n\), therefore \(f\) does not depend on \(i\).

The other direction follows by applying Parseval's theorem on the norm of the i'th derivative of \(f\), obtaining that \(i\) is relevant for \(f\) if and only if \( \left\lVert \D_if(x) \right\rVert_2^2 = \sum_{\substack{S \subseteq [n] \\ i\in S}} \hat{f}(S)^2 > 0 \),
which is satisfied if and only if there exists at least one \(S\subseteq [n]\) such that \(i\in S\) and \(S\in \supp(\hat{f})\).

For any real \(f\), its set of relevant coordinates is denoted by:

\[
\dep(f) = \left\{ i\in [n] \mid i \textnormal{ is relevant for } f \right\} = \bigcup_{S\in \supp(f)} S.
\]

In particular, \(f\) is constant if and only if \(\dep(f) = \emptyset\).

A Boolean function is a \(\left\{ -1,1 \right\}\)-valued function. For any \(i\in [n]\), the Boolean function \(f(x) = x_i\) is called a projection, and its negation \(f(x) = -x_i\) is called an anti-projection.
A (not necessarily Boolean) function which depends on a single coordinate and is not constant is called a dictator; a Boolean dictator is either a projection or an anti-projection.

The set of degree $1$ Boolean functions contains only dictators:

Let \(f \colon \left\{ -1,1 \right\}^{n}  \to \left\{ -1,1 \right\} \). If \(\deg(f) = 1\) then there exists some \(i\in [n]\) such that \(f(x) = x_i\) or \(f(x) = -x_i\).

If \(\deg(f) = 1\), then \(f = c_0 + \sum_{i=1}^n c_i x_i\) for some constants \(c_i\in \R\). We show first that at most one of $c_1,\ldots,c_n$ is nonzero. Otherwise, there are two non-zero coefficients, without loss of generality $c_1,c_2$. By possibly flipping $x_1,x_2$ (an operation which preserves being Boolean), we can assume furthermore that \(c_1,c_2 > 0\). Then

\[
f(1,1,\dots,1) > f(1,-1,1,1...1) > f(-1,-1,1,1,\dots,1),
\]

so in particular \(f\) attains three distinct values, in contradiction to \(f\in \left\{ -1,1 \right\}\).

We conclude that $f = c_0 + c_i x_i$ for some $i \in [n]$, where $c_i \neq 0$. Hence $\{c_0 \pm c_i\} = \{\pm1\}$, which implies that $c_0 = 0$ and $c_i \in \{-1,1\}$.

The latter result can be generalized into the following claim:

Let \(f \colon \left\{ -1,1 \right\}^n \to \left\{ -1,1 \right\}\) and suppose that \(f\) depends on the coordinate \(w\in [n]\). Then, either \(f\) depends only on $w$, or the support of \(\hat{f}\) contains some \(S\) of size at least \(2\) that contains \(w\).

From <Ref> we know that there exists at least one \(S\in \supp(\hat{f}_0)\) containing \(w\), so it suffices to show that if the only \(S\) satisfying this is \(S = \left\{  w \right\}\), then \(f\) must be depend only on \(w\).

Assume without loss of generality that \(\hat{f}(S) > 0\) (the proof of the other case is similar). For any \(x\in \left\{ -1,1 \right\}^{n}\) we have \(f(x^{(w\mapsto -1)}) < f(x^{(w\mapsto 1)})\). Since \(f\in \left\{ -1, 1 \right\}\), it follows that \(f(x^{(w\mapsto-1)}) = -1\) and \(f(x^{(w\mapsto1)}) = 1\). In other words, $f(x)$ depends only on $x_w$.

In general, we refer to real-valued functions on the cube that satisfy the last two properties as functions that satisfy the 2-valued-like property:

A function $f\colon \{-1,1\}^n \to \R$ is 2-valued-like if

* \(\deg(f) = 1\) if and only if \(f\) is a dictator.

* If \(f\) is not a dictator then for every \(w\in \dep(f)\), the support of \(\hat{f}\) contains some \(S\) of size at least \(2\) that contains \(w\). (In particular, every inclusion-maximal set in $\hat{f}$ has size at least $2$.)

For functions with degree at least 2, being 2-valued-like is preserved under shifted translations:

Let \(f\colon \left\{ -1,1 \right\}^n \to  \R \) be some 2-valued-like function where \(\deg(f) \geq 2\), and let \(F\) be some shifted translation of \(f\). Then \(F\) is also 2-valued-like.

We first show that $F$ satisfies the second requirement in the definition of 2-valued-like. Suppose that $F$ depends on a coordinate $w$ but is not a dictator.
<Ref> implies that $f$ also depends on $w$, which by assumption is not a dictator. Since $f$ is 2-valued-like, $\supp(\hat{f})$ must contain a non-singleton set containing $w$. Considering an inclusion-maximal such set, <Ref> implies that $\supp(\hat{F})$ also contains such a set.

Since \(\deg(f) \geq 2\), the degree of \(F\) must also be at least 2, making the first requirement hold trivially. Indeed, if \(F\) depends on \(w\) and the only set in its Fourier support is \(\left\{ w \right\}\), then from <Ref> it would also be the only inclusion-maximal set in the Fourier support of \(f\), and in particular \(\deg(f) = 1\). Since \(f\) is 2-valued-like, it must be a dictator — contradicting the assumption of \(\deg(f) \geq 2\).

If \(A\) is an \(n \times m\) matrix then for any \(I\subseteq [n], J \subseteq [m]\), the submatrix \(B[I;J]\) is the matrix obtained from \(A\) by retaining only the rows in \(I\) and the columns in \(J\). We denote \(\rows(B) = I\) and \(\cols(B) = J\).

§.§ Setup

In this paper, our goal is to describe all Boolean generalized polymorphisms.
A multilinear generalized polymorphism consists of functions $g_0,g_1,\ldots,g_n\colon \{-1,1\}^m \to \R$ and $f_0,f_1,\ldots,f_m\colon \{-1,1\}^n \to \R$, for some integers $n,m \geq 0$, satisfying the equation

\[
g_0(f_1(\col_1(Z)), \ldots, f_m(\col_m(Z))) =
f_0(g_1(\row_1(Z)), \ldots, g_n(\row_n(Z))),
\]

where $Z = \{z_{ij} : i \in [n], j \in [m] \}$ is a two-dimensional array of variables ranging over $\{-1,1\}$. We denote the left-hand side by $(g \circ (f_1,\ldots,f_m))(Z)$ and the right-hand side by $(f \circ (g_1,\ldots,g_n))(Z)$, allowing us to succinctly state the equation as follows:

\begin{equation} \label{eq:generalized-polymorphism}
(g_0 \circ (f_1,\ldots,f_m))(Z) = (f_0 \circ (g_1,\ldots,g_n))(Z).
\end{equation}

Henceforth, we will assume that $f_0,g_1,\ldots,g_n,g_0,f_1,\ldots,f_m$ are a multilinear generalized polymorphism.

When $f_0,g_1,\ldots,g_n,g_0,f_1,\ldots,f_m$ are all Boolean functions, we refer to them as a Boolean generalized polymorphism. For brevity, we will sometimes refer to both multilinear generalized polymorphisms and Boolean generalized polymorphisms simply as generalized polymorphisms, or even just polymorphism whenever the association is obvious.

Both sides of <Ref> are multilinear polynomials over the variables $Z$. Accordingly, we generalize the definition of the Fourier expansion by using the index set $[n] \times [m]$ to refer to variables and Fourier coefficients. Explicitly, if $S \subseteq [n] \times [m]$ then

\[
\chi_S(z) = \prod_{(i,j) \in S} z_{ij},
\]

and $\hat{f}(S)$ is the coefficient of $\chi_S(z)$ in the unique multilinear expansion of $f$.

If we substitute the Fourier expansion (<Ref>) of both sides of <Ref>, we obtain

\begin{equation} \label{eq:general-expansion}
\sum_{S \subseteq [n]} \hat{f}_0(S) \prod_{i \in S} \sum_{ T_i \subseteq [m]} \hat{g}_i(T_i) \prod_{j \in T_i} z_{ij} =
\sum_{T \subseteq [m]} \hat{g}_0(T) \prod_{j \in T} \sum_{ S_j \subseteq [n]} \hat{f}_j(S_j) \prod_{i \in S_j} z_{ij}.
\end{equation}

According to <Ref>, the two sides agree as functions on $\{-1,1\}^n$ iff they are identical as multilinear polynomials in $Z$, that is, the coefficient of each monomial is identical on both sides. We use this crucial observation throughout this paper to interpret <Ref> as a polynomial equality, rather than an equality between functions on the cube.
Henceforth, whenever we say that two functions are equal, we mean that they are identical as (multilinear) polynomials.

As hinted at in the introduction, we make the following two assumptions on our input, which we justify when formulating our main result for each section:

* \(f_1,\dots,f_m,g_1,\dots,g_n\) are not constant functions (note that this assumption is only relevant for the preliminary results and <Ref>).

* Each of \(f_0,g_0\) depends on all of their inputs.

For a subset $W \subseteq Z$, we define $\rows(W)$ to consist of all $i \in [n]$ such that $W$ contains some $z_{ij}$. Similarly, $\cols(W)$ consists of all $j \in [m]$ such that $W$ contains some $z_{ij}$. In other words, if we think of $W$ as a subset of $[n] \times [m]$, then $\rows(W)$ is its projection to the first coordinate, and $\cols(W)$ is its projection to the second coordinate.

§.§ Partitioning the variables

The solution portrayed in <Ref> for <Ref> alluded to the existence of certain partitions of the input space which scaffold every general solution for <Ref>. Here we show that indeed any set of functions \(f_0,f_1,\dots,f_m,g_0,g_1,\dots,g_n\) satisfying <Ref> induce such a partition, where the partition is uniquely determined by the sets \( \left\{ \dep(g_i)  \right\}_{i\in \dep(f_0)},  \left\{ \dep(f_j)  \right\}_{j\in \dep(g_0)}\).

The set of variables that appear in <Ref> is

\[
Z_0 = \dep(f_0 \circ (g_1,\ldots,g_n)) = \dep(g_0 \circ (f_1,\ldots,f_m)) \subseteq Z.
\]

We now show that $Z_0$ consists of the coordinates that $g_i$ depend on (for $i \in \dep(f_0)$), and similarly for the $f_j$:

We have

\[
Z_0 = \bigcup_{j\in \dep(g_0)} \left\{ z_{ij} \mid i\in \dep(f_j) \right\} = \bigcup_{i\in \dep(f_0)}\left\{ z_{ij} \mid j\in \dep(g_i)  \right\}.
\]

We show that \(Z_0 = \bigcup_{i\in \dep(f_0)}\left\{ z_{ij} \mid j\in \dep(g_i)  \right\}\) by double-inclusion; a symmetric proof shows that \(Z_0 = \bigcup_{j\in \dep(g_0)} \left\{ z_{ij} \mid i\in \dep(f_j) \right\} \).

If $f_0$ doesn't depend on $i_0$ or $g_{i_0}$ doesn't depend on $j_0$ then the Fourier expansion of $f_0 \circ (g_1,\ldots,g_n)$ doesn't contain $z_{i_0 j_0}$, and so $f_0 \circ (g_1,\ldots,g_n)$ doesn't depend on $z_{i_0 j_0}$. Consequently, if $z_{i_0j_0} \in Z_0$ then $f_0$ depends on $i_0$ and $g_{i_0}$ depends on $j_0$.

Conversely, suppose that $f_0$ depends on $i_0$ and that $g_{i_0}$ depends on $j_0$. Let $S_0$ be an inclusion-maximal set in $\supp(\hat{f}_0)$ containing $i_0$, and let $T_{i_0}$ be any set in $\supp(\hat{g}_{i_0})$ containing $j_0$. For any $i \in S_0$ other than $i_0$ we choose some non-empty $T_i \in \supp(\hat{g}_i)$; this is possible since $g_i$ is non-constant by assumption. Let

\[
U = \{ (i,j) : i \in S_0, j \in T_i \}.
\]

We will show that $f_0 \circ (g_1,\ldots,g_n)$ depends on $z_{i_0j_0}$ by showing that its Fourier coefficient on $U$ is non-zero, and applying <Ref>.

Indeed, any term on the left-hand side of <Ref> which contributes to this Fourier coefficient must correspond to some $S \supseteq S_0$ (a set $S \supsetneq S_0$ contributes if $\hat{g}_i(\emptyset) \neq 0$ for all $i \in S \setminus S_0$). Since $S_0$ is inclusion-maximal, necessarily $S = S_0$. For each $i \in S_0$ we must choose $T_i$ as above, and so there is a unique term which contributes to the Fourier coefficient. By construction, this term is non-zero, and so the Fourier coefficient is non-zero, as required.

The aforementioned partition into blocks will in fact be a partition of \(Z_0\) into submatrices. The partition is obtained imperatively as follows:

The partition of \(Z_0\) into blocks, which we denote by \(Z_0 = \bigsqcup_{\ell\in [k]} Z_\ell\), is the partition uniquely determined by the connected components of the undirected graph \(\GG[V,E]\), where \(V = Z_0\) and \(E = \left\{ \left\{ z_{ij},z_{i',j'} \right\} \mid i = i' \textnormal{ or } j = j' \right\}\).

This partition is row- and column-disjoint, since any two \(z_{ij}\) with the same \(i\) or the same \(j\) have an edge between them by construction.

The graph-theoretic formulation implies an intuitive visual representation of the partition inside \(Z\), in which $Z_0$ is in “block-diagonal form”, as demonstrated in <Ref>.

\begin{align*}
\newcommand\blue{\cellcolor{blue!10}}
\newcommand\red{\cellcolor{red!10}}
\newcommand\green{\cellcolor{green!10}}
\left(
\begin{array}{cccc}
z_{11} & z_{12}  & z_{13} & z_{14} \\
z_{21} & z_{22}  & z_{23} & z_{24} \\
z_{31} & z_{32}  & z_{33} & z_{34} \\
z_{41} & z_{42}  & z_{43} & z_{44} \\
z_{51} & z_{52}  & z_{53} & z_{54} \\
\end{array}
\right)
\overset{}{\longrightarrow}
\left(
\begin{array}{cccc}
z_{11}  & z_{12}  & z_{13} &  \blue Z_0 \\
z_{21}   & \blue Z_0  & z_{23} & \blue Z_0 \\
\blue Z_0   & z_{32}   & \blue Z_0 & z_{34}\\
z_{41}   & \blue Z_0   &  z_{43} & \blue Z_0 \\
\blue Z_0  &  z_{52}  &  z_{53} &  z_{54}\\
\end{array}
\right)
\overset{}{\longrightarrow}
\\
\\
\newcommand\blue{\cellcolor{blue!10}}
\newcommand\red{\cellcolor{red!10}}
\newcommand\green{\cellcolor{green!10}}
\left(
\begin{array}{cc|cc}
\blue Z_0  & z_{12}  &z_{13} &z_{11} \\
\blue Z_0   & \blue Z_0  & z_{23} &z_{21} \\
\blue Z_0   & \blue Z_0   & z_{43} & z_{41}\\\hline
z_{34}   &  z_{32}   &  \blue Z_0 & \blue Z_0 \\
z_{54}  &  z_{52}  &  z_{53} &  \blue Z_0\\
\end{array}
\right)
\overset{}{\longrightarrow}
\left(
\begin{array}{cc|cc}
\red Z_1  & z_{12}  &z_{13} &z_{11} \\
\red Z_1   & \red Z_1  & z_{23} &z_{21} \\
\red Z_1   & \red Z_1   & z_{43} & z_{41}\\\hline
z_{34}   &  z_{32}   &  \green Z_2 & \green Z_2 \\
z_{54}  &  z_{52}  &  z_{53} &  \green Z_2\\
\end{array}
\right)
\end{align*}

[Input matrix: block diagonal form]
Starting from \(Z\), we first highlight its subset \(Z_0\). By row and column permutations we get its equivalent block-diagonal form.

Henceforth, we will use $Z_0$ and its decomposition as defined in this section.

Since the \(Z_\ell\) sets are connected components, for every two distinct \(i,i'  \in \rows(Z_\ell)\) there exist some \(j\in \dep(g_i)\) and \(j'\in \dep(g_{i'})\) and some path in \(\GG\) connecting \(z_{ij}\) to \(z_{i'j'}\). An important special case of this property pinpoints the commonality between \(g_i\) sets associated to the same \(Z_\ell\) component (and similarly for \(f_j\)'s and columns of the component):

Let $\emptyset \neq I \subsetneq \rows(Z_\ell)$ . Then there exist \(i_0\in I\) and \(i_1 \in \rows(Z_\ell) \setminus I\) such that \(g_{i_0}\) and \(g_{i_1}\) depend on the same coordinate \(w\in [m]\).

Let \(Z_\ell^I = \left\{ z_{ij} \mid i\in I, j\in \dep(g_i)\right\}\). Since $Z_\ell$ is a connected component of $\GG$, there must be an edge between some $z_{i_0j_0} \in Z_\ell^I$ and some $z_{i_1j_1} \in Z_\ell \setminus Z_\ell^I$. In view of the definition of $Z_\ell^I$, necessarily $i_0 \neq i_1$, and so $j_0 = j_1$ by the definition of $\GG$. According to <Ref>, this implies that $g_{i_0}$ and $g_{i_1}$ depend on the same coordinate $w$, which is the common value of $j_0$ and $j_1$.

§.§ Balanced functions

The most basic property of the structure of generalized polymorphisms is that the Fourier supports of the functions the polymorphism is composed of strongly correlate with one another. This property is more easily observable when considering generalized polymorphisms of balanced functions. Before showing this property, we show that any multilinear generalized polymorphism can be reduced into a multilinear generalized polymorphism where \(f_1,\dots,f_m,g_1,\dots,g_n\) are all balanced:

Let \(f_0,\dots,f_m \colon \left\{ -1,1 \right\}^{n} \to \R\) and \(g_0,\dots,g_n \colon \left\{ -1,1 \right\}^{m} \to \R\), and suppose that \(F_0,\dots,\allowbreak F_m \colon \left\{ -1,1 \right\}^{n} \to \R\) and \(G_0,\dots,G_n \colon \left\{ -1,1 \right\}^{m} \to \R\) are the functions defined as follows:
For every \(j\in [m]\), define \(F_j = f_j - \hat{f}_j(\emptyset)\) and \(G_0(y_1,\dots,y_m) = g_0(y_1 + \hat{f}_1(\emptyset),\dots, y_m + \hat{f}_m(\emptyset)) \) so that \(G_0\circ(F_1,\dots,F_m) = g_0\circ(f_1,\dots,f_m)\). Similarly, for every \(i\in [n]\), define \(G_i = g_i - \hat{g}_i(\emptyset)\) and \(F_0(x_1,\dots,x_n) = f_0(x_1+\hat{g}_1(\emptyset), \dots, x_n + \hat{g}_n(\emptyset))\) so that \(F_0\circ(G_1,\dots,G_n) = f_0\circ(g_1,\dots,g_n) \). Then:

* \(F_1,\dots,F_m,G_1,\dots,G_m\) are balanced.

* If \(f_1,\dots,f_m,g_1,\dots,g_n\) are 2-valued-like then so are \(F_1,\dots,F_m,G_1,\dots,G_n\) (respectively).

* For every \(i\in \{0\} \cup [n]\), a set \(S_i \subseteq [m]\) is inclusion-maximal in \(\supp(\hat{g}_i)\) if and only if \(S_i\) is inclusion-maximal in \(\supp(\hat{G}_i)\). Consequently, \(\dep(g_i) = \dep(G_i)\).

* For every \(j\in \{0\} \cup [m]\), a set \(T_j \subseteq [n]\) is inclusion-maximal in \(\supp(\hat{f}_j)\) if and only if \(T_j\) is inclusion-maximal in \(\supp(\hat{F}_j)\). Consequently, \(\dep(f_j) = \dep(F_j)\).

* \(f_0,\dots,f_m,g_0,\dots,g_n\) is a generalized polymorphism if and only if \(F_0,\dots,F_m,G_0,\allowbreak,\dots,G_n\) is a generalized polymorphism. Moreover, if they are both generalized polymorphisms, their \(Z_0\) sets coincide.

The first item follows immediately by definition of balancedness and the definition of \(F_1,\dots,F_m,\allowbreak G_1,\dots, G_n\).

The functions \(F_0,\dots,F_m,G_0,\dots,G_n\) are all shifted translations, making items three and four special cases of <Ref>.

We continue with the second item, concentrating on $f_j$ and $F_j$. Suppose that $f_j$ is 2-valued-like. We prove that $F_j$ is also 2-valued-like, starting with the first requirement in the definition. If $F_j$ is a dictator then clearly $\deg F_j = 1$. Conversely, if $\deg F_j = 1$ then also $\deg f_j = 1$ (by the fourth item), hence $f_j$ is a dictator. The function $F_j$ depends on the same coordinate.

We now prove that $F_j$ satisfies the second requirement in the definition of 2-valued-like. Suppose next that $F_j$ depends on a coordinate $w$ but is not a dictator. The fourth item implies that $f_j$ also depends on $w$, and as seen above, $f_j$ is also not a dictator. The second requirement now follows from <Ref>.

The first part of <Ref> follows by the polynomial identities \(F_0\circ(G_1,\dots,G_n) = f_0\circ(g_1,\dots,g_n) \) and \(G_0\circ(F_1,\dots,F_m) = g_0\circ(f_1,\dots,f_m)\), which imply that \(G_0\circ(F_1,\dots,F_m) = F_0\circ(G_1,\dots,G_n)\) if and only if \(g_0\circ(f_1,\dots,f_m) = f_0\circ(g_1,\dots,g_n)\).

The second part of <Ref> follows from the previous two items and <Ref>.

Even though our goal is to characterize Boolean generalized polymorphisms, all intermediate results hold either for multilinear generalized polymorphisms or for multilinear generalized polymorphisms of 2-valued-like multilinear polynomials. In light of this, all subsequent results will be formulated for multilinear generalized polymorphisms \(f_0,\dots,f_m,g_0,\dots,g_n\) whenever the 2-valued-like property isn't necessary, and otherwise formulated for multilinear generalized polymorphisms with 2-valued-like \(f_1,\dots,f_m,g_1,\dots,g_n\).

The correlation between Fourier supports, hinted at in the beginning of this section, is described in the next two lemmas. In light of <Ref>, we phrase them both for balanced \(f_1,\dots,f_m,g_1,\dots,g_n\). The exact way in which <Ref> is applied onto \(f_0,\dots,f_m,g_0,\dots,g_n\) will be made clear only in <Ref> and <Ref>, but for now it suffices to assume that \(f_1,\dots,f_m,g_1,\dots,g_n\) are given to us already balanced.

Let \(f_1,\dots,f_m,g_1,\dots,g_n\) be balanced multilinear polynomials corresponding satisfying (<ref>) for some multilinear \(f_0,g_0\). Then

*  For every \(S\in  \supp(\hat{f}_0)\) and \(\left\{ U_i \mid U_i \in  \supp(\hat{g}_i) \right\}_{i\in S}\), the following holds: \(T \coloneqq \bigcup_{i\in S} U_i \in  \supp(\hat{g}_0)\), and for every \(j\in T\), we have \( V_j \coloneqq \left\{ i\in S \mid j\in U_i  \right\} \in  \supp(\hat{f}_j)\).

*  For every \(T\in  \supp(\hat{g}_0)\) and \(\left\{ V_j \mid V_j \in  \supp(\hat{f}_j) \right\}_{j\in T}\), the following holds: \(S \coloneqq \bigcup_{j\in T} V_j \in  \supp(\hat{f}_0)\), and for every \(i\in S\), we have \( U_i \coloneqq \left\{ j\in T \mid i\in V_j  \right\} \in  \supp(\hat{g}_i)\).

We prove <Ref>; the proof of <Ref> is symmetric.

Given (<ref>), we use the assumptions \(\hat{f}_1(\emptyset) = \dots = \hat{f}_n(\emptyset) = \hat{g}_1(\emptyset) = \dots = \hat{g}_m(\emptyset) = 0\) to obtain

\begin{equation}
\label{eq:tautology_formula}
\sum_{S' \subseteq [n]} \hat{f}_0(S') \prod_{i \in S'} \sum_{\emptyset \neq T_i \subseteq [m]} \hat{g}_i(T_i) \prod_{j \in T_i} z_{ij} =
\sum_{T' \subseteq [m]} \hat{g}_0(T') \prod_{j \in T'} \sum_{\emptyset \neq S_j \subseteq [n]} \hat{f}_j(S_j) \prod_{i \in S_j} z_{ij}.
\end{equation}

By comparing coefficients for the monomial \(\prod_{i\in S}z_{iU_{i}}\) (recall that $z_{iU_i} = \prod_{j \in U_i} z_{ij}$), we get

\[ \hat{f_0}(S)\prod_{i\in S } \hat{g}_{i}(U_{i}) =  \hat{g_0}(T)\prod_{j\in T } \hat{f}_{j}(V_{j}), \]

where \(T = \bigcup_{S} U_{i}\) and \(V_{j} = \left\{ i\in S : j\in U_{i} \right\}\) (see <Ref>).

\begin{equation*}
\newcommand\blue{\cellcolor{blue!20}}
\newcommand\red{\cellcolor{red!20}}
\newcommand\green{\cellcolor{green!20}}
\newcommand\yellow{\cellcolor{yellow!30}}
\newcommand\brown{\cellcolor{brown!30}}
\begin{aligned}
\begin{array}{ccccc}
\red z_{11} & z_{12}  & z_{13} & \red z_{14} & z_{15}\\
z_{21} & z_{22}  & z_{23} & z_{24} & z_{25}\\
\blue z_{31} & \blue z_{32}  & z_{33} & z_{34} & z_{35}\\
z_{41} & z_{42}  & z_{43} & z_{44} & z_{45}\\
z_{51} & z_{52}  & z_{53} & z_{54} & z_{55}\\
\end{array}
\right)
\left(
\begin{array}{ccccc}
\green z_{11} & z_{12}  & z_{13} & \brown z_{14} & z_{15}\\
z_{21} & z_{22}  & z_{23} & z_{24} & z_{25}\\
\green z_{31} & \yellow z_{32}  & z_{33} & z_{34} & z_{35}\\
z_{41} & z_{42}  & z_{43} & z_{44} & z_{45}\\
z_{51} & z_{52}  & z_{53} & z_{54} & z_{55}\\
\end{array}
\right)
\end{aligned}
\end{equation*}

\begin{align*}
&\hat{f}_0(\left\{ 1,3 \right\})\cdot\hat{g}_1(\left\{ 1,4 \right\}) z_{11}z_{14}\cdot\hat{g}_3(\left\{ 1,2 \right\}) z_{31}z_{32} = \\
&\hat{g}_0(\left\{ 1,2,4 \right\}) \cdot \hat{f}_1(\left\{ 1,3 \right\})z_{11}z_{31}\cdot\hat{f}_2(\left\{ 3 \right\})z_{32}\cdot\hat{f}_4(\left\{ 1 \right\})z_{14}
\end{align*}

[<Ref>: an example]
Comparing coefficients for the monomial \(z_{11}z_{14}z_{31}z_{32}\) in (<ref>)

Since the LHS is nonzero by assumption, the RHS is also nonzero.

Out of all sets in the Fourier supports of the functions comprising a generalized polymorphism, the inclusion-maximal ones are particularly important. Their importance lies both due to their use in extremal combinatorial arguments, and since important special cases in our characterization involve affine shifts of monomials, which have a unique inclusion-maximal sets. With that in mind, a natural question to ask is under what assumptions <Ref> preserves inclusion-maximality of the sets it gets as input:

Suppose that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced multilinear functions satisfying <Ref> for some multilinear \(f_0,g_0\), let \(S \subseteq [n]\) be inclusion-maximal in the support of \(\hat{f}_0\) and \(\left\{ U_i \right\}_{i \in S}\) be inclusion-maximal in the supports of \(\left\{ g_i \right\}_{i \in S}\). Then, applying <Ref> on the functions \(f_0,\left\{ g_i \right\}_{i\in S}\) with respect to the sets \(S,\left\{ U_i \right\}_{i\in S}\) yields sets \(T,\left\{ V_j \right\}_{j \in T}\) such that \(T\) is inclusion-maximal in the support of \(\hat{g}_0\) and every \(V_j\) is inclusion-maximal in the support of \(\hat{f}_j\).

Suppose for the sake of contradiction that there exists some \(T \subsetneq T' \in \supp(\hat{g}_0)\) and let \(j_0\in T'\setminus T\). By definition of \(\left\{ V_j \right\}_{j\in T}\) as per <Ref>, observe that applying <Ref> on \(T,\left\{ V_j \right\}_{j\in T}\) results in the identities \(U_i = \left\{ j\in T \mid i\in V_j \right\}\) for every \(i\in S\) — in other words, applying the second item of <Ref> on the sets obtained from the first item, results in the same \(S,\left\{ U_i \right\}_{i\in S}\) we started off with.

Next, pick arbitrary nonempty \(\left\{ V_j'\in \supp(\hat{f}_j) \right\}_{j\in T'\setminus T}\) (this is possible since $f_j$ is not constant) and apply <Ref> over \(T',\left\{ V_j \right\}_{j\in T},\left\{ V_j' \right\}_{j\in T'\setminus T}\). We get that the set \(S' = \left( \bigcup_{j\in T}V_j \right) \cup \left( \bigcup_{j\in T'\setminus T} V_j' \right)\) is in \(\supp(\hat{F}_0)\) and that the sets \(U_i' =\left\{ j\in T \mid i\in V_j \right\} \cup \left\{ j\in T'\setminus T \mid i\in V_j' \right\}  \) are in \(\supp(\hat{G}_i)\). However, since \(S'\) contains the inclusion-maximal set \(S = \bigcup_{j\in T}V_j \), it follows that \(S = S'\), and in particular \(\emptyset \neq V_{j_0}' \subseteq \bigcup_{j\in T'\setminus T} V_j' \subseteq \bigcup_{j\in T}V_j\). Similarly, since \(U_i \subseteq U_i'\) for every \(i\in S \), the inclusion-maximality of \(U_i\) implies that \(U_i = U_i'\), and in particular \(\left\{ j\in T'\setminus T \mid i\in V_j' \right\}  \subseteq \left\{ j\in T \mid i\in V_j \right\} \). Finally, let \(i_0\in V_{j_0}'\). Since \(i_0 \in V_{j_0}'\subseteq \bigcup_{j\in T}V_j = S \), we have \(j_0\in \left\{ j\in T'\setminus T \mid i_0\in V_j' \right\} \subseteq \left\{ j\in T \mid i_0\in V_j \right\} = U_{i_0} \subseteq \bigcup_{i\in S} U_i = T  \)  — a contradiction to \(j_0\not\in T\). Therefore \(T\) is indeed inclusion-maximal in \(\supp(\hat{g}_0)\).

It remains to show that \(V_j\) is inclusion-maximal in \(\supp(\hat{f}_j)\) for every \(j\in T\); the argument is similar: let \(j_0\in T\), suppose for the sake of contradiction that there exists some \(V_{j_0}\subsetneq V_{j_0}' \in \supp(\hat{f}_{j_0})\), and let \(i_0\in V_{j_0}'\setminus V_{j_0}\). Apply <Ref> on \(T,V_{j_0}'\) and \(\left\{ V_{j} \right\}_{j\in T-j_0}\) and get that the set \(S' = \left( \bigcup_{j\in T- j_0} V_j \right) \cup  V_{j_0}' \) is in \(\supp(\hat{f}_0)\), and that for every \(i\in S'\), the set

\[
U_i' = \begin{cases}
\left\{ j\in T \mid i\in V_j \right\} \cup \left\{ j_0 \right\},& \textnormal{ if } i\in V_{j_0}', \\
\left\{ j\in T \mid i\in V_j \right\},& \textnormal{otherwise}
\end{cases}
\]

is in \(\supp(\hat{g}_i)\). Since \(V_{j_0}\subsetneq V_{j_0}'\), it follows that \(S = \bigcup_{j\in T} V_j \subseteq  S'\), implying that \(S = S'\) since \(S\) is inclusion-maximal, and in particular \(i_0\in V_{j_0}'\setminus V_{j_0} \subseteq \bigcup_{j\in T- j_0} V_j \subseteq S\) (since \(i_0\not\in V_{j_0}\) by construction). Since \(i_0\in S\), we get \(U_{i_0} = \left\{ j\in T \mid i_0\in V_j \right\}  \subseteq \left\{ j\in T \mid i_0\in V_j \right\} \cup \left\{ j_0 \right\} = U_{i_0}'\), implying that \(U_{i_0}' = U_{i_0}\) since \(U_{i_0}\) is inclusion-maximal, and in particular that \(j_0\in U_{i_0}' = U_{i_0}\) — a contradiction to \(i_0\not\in V_{j_0} = \left\{ i\in S \mid j_0\in U_i  \right\} \) (since \(i_0\in S\) and \(j_0\in U_{i_0}\)).

Since <Ref> preserves inclusion-maximal sets (<Ref>, <Ref>), a similar result can be formulated for potentially unbalanced \(f_1,\dots,f_m,g_1,\dots,g_n\):

Suppose that \(f_1,\dots,f_m,g_1,\dots,g_n\) are (not necessarily balanced) multilinear functions satisfying <Ref> for some multilinear \(f_0,g_0\), let \(S \subseteq [n]\) be inclusion-maximal in the support of \(\hat{f}_0\), and let \(\left\{ U_i \right\}_{i \in S}\) be inclusion-maximal in the supports of \(\left\{ g_i \right\}_{i \in S}\). Denote by \(F_0,\dots,F_m,G_0,\dots,G_n\) the generalized polymorphism obtained by applying <Ref>.

The sets \(T,\left\{ V_j \right\}_{j \in T}\) obtained by applying <Ref> over \(F_0,\dots,F_m,G_0,\dots,G_n\) and \(S,\left\{ U_i \right\}_{i\in S}\), are also inclusion-maximal in \(\supp(\hat{g}_0), \left\{ \supp(\hat{f}_j) \right\}_{j\in T}\), respectively.

By <Ref> in <Ref>, the sets \(S,\left\{ U_i \right\}_{i\in S}\) are also inclusion-maximal in the Fourier supports of \(F_0,\left\{ G_i   \right\}_{i\in S}\), hence the application of <Ref> is well-defined. By <Ref> in <Ref>, the resulting \(T,\left\{ V_j \right\}_{j\in T}\) are also inclusion-maximal in the Fourier supports of \(g_0, \left\{ f_j \right\}_{j\in T}\), as needed.

§.§ Boolean functions

Once we obtain a characterization for 2-valued-like functions, we immediately concern ourselves with specializing the result for the important case of Boolean functions.
This is achieved mainly by the use of the following two results, which explain why the main classification is composed mostly of XOR, AND and OR functions. As we show later on, the functions \(g_1,\dots,g_n,f_1,\dots,f_m\) end up being very similar to affine transformations of monomials, and Boolean functions which are affine transformations of monomials are indeed XOR, AND, or OR functions. This result is Lemma 6.3 in <cit.>; we include it along with its proof for the sake of completeness:

Suppose that $f\colon \{-1,1\}^n \to \{-1,1\}$ is given by

\[
f = A \prod_{i=1}^n (x_i + \kappa_i) - B,
\]

where $A \neq 0$ and $n \geq 2$. Then one of the following holds:

Case 1:
$\kappa_1 = \cdots = \kappa_n = B = 0$ and $A \in \{-1,1\}$, i.e.

\[
f = A \prod_{i=1}^n x_i, \text{ where } A \in \{-1,1\}.
\]

Case 2:
$\kappa_1,\ldots,\kappa_n,B \in \{-1,1\}$ and $A = 2B/\prod_{i=1}^n (2\kappa_i)$, i.e.

\[
f = 2B \prod_{i=1}^n \frac{\kappa_i x_i + 1}{2} - B, \text{ where } \kappa_1,\ldots,\kappa_n,B \in \{-1,1\}.
\]

Note that the first case in <Ref> corresponds to an XOR function, and the second case to either an AND or an OR function.

If $n = 1$ then $f \in \{x_1,-x_1\}$. Now suppose that $n \geq 2$.
Choose an assignment $y_i \neq -\kappa_i$ for all $i \in [n]$, and let $f(y) = F$, where $F + B \neq 0$. Let $\rho_i = (\kappa_i - y_i)/(\kappa_i + y_i)$, and let $y_S$ be the point different from $y$ on the indices in $S \subseteq [n]$. Then

\[
f(y_S) = (F + B) \prod_{i \in S} \rho_i - B.
\]

Since $f(y_S) \in \{-1,1\}$ for all $S$, the products $\prod_{i \in S} \rho_i$ must attain exactly two different values. In particular, considering singleton $S$, since $\rho_i \neq 1$ for all $i$, we deduce that all $\rho_i$ are equal to some $\rho \neq 1$. If $\rho \neq 0$ then $\rho^2 \neq \rho$, hence $\rho^2 = 1$, implying that $\rho = -1$. Furthermore, $-F = f(y_{\{1\}}) = (F+B)\rho - B$, and so

\[
\rho = \frac{B-F}{B+F}, \quad \kappa_i = \frac{1+\rho}{1-\rho} y_i = \frac{B}{F} y_i.
\]

If $\rho = -1$ then $B = 0$ and so $\kappa_1 = \cdots = \kappa_m = 0$.
If $\rho = 0$ then $B = F$ and so $\kappa_i = y_i$. In both cases, we can compute $A$ via $f(y) = F$.

Multiplying the shifted monomial in <Ref> by a function, even a completely arbitrary one, yields a similar result, as long as this arbitrary function is defined over a domain which is disjoint from the monomial:

Let \(n \geq 1\) and let \(f\colon \left\{ -1,1 \right\}^n \to \left\{ -1,1 \right\}\) satisfy

\[
f(z)= \phi(y) \prod_{i=1}^k (x_{i} + \kappa_{i}) - B,
\]

where \(y = (y_{1},\dots,y_{n-k})\) is the last \(n-k\) coordinates of \(z = (z_1,\dots,z_n)\), \(x = (x_1,\dots,x_k)\) is the first \(k\) coordinates of \(z\), \(\phi\colon \left\{ -1,1 \right\}^{n-k} \to \R\), and \(B, \kappa_1,\dots,\kappa_k\in \R\). Suppose that either (1) $\phi$ is not the constant zero function and $k \geq 2$, or (2) $\phi$ is not constant and $k \geq 1$.

Then one of the following holds:

Case 1:
$\kappa_1 = \cdots = \kappa_k = B = 0$ and $\phi\colon \{-1,1\}^{n-k} \to \{-1,1\}$, i.e.

\[
f(z) = \phi(y) \prod_{i=1}^k x_i.
\]

Case 2: $\kappa_1,\ldots,\kappa_k,B \in \{-1,1\}$ and  there exists some $\tilde{\phi}\colon \left\{ -1,1 \right\}^{n-k} \to \left\{ 0,1 \right\} $ such that

\[
f(z) = \tilde{\phi}(y)\cdot 2B \prod_{i=1}^k \frac{\kappa_i x_i + 1}{2} - B.
\]

If \(\phi\) is a constant function which is non-zero, then after denoting it by \(A\) we see that the assumptions of  <Ref> hold (since $k \geq 2$), so we apply <Ref> directly. Case 1 in <Ref> corresponds to Case 1 here, and similarly for Case 2.

If $\phi$ is non-constant then we can find an input $y \in \{-1,1\}^{n-k}$ and $j \in [n-k]$ such that $\phi(y) \neq \phi(y')$, where $y'$ is obtained from $y$ by flipping the $j$'th coordinate. Define

\[
f'(x,w) =
\begin{cases}
f(x,y) & \text{if } w = 1, \\
f(x,y') & \text{if } w = -1.
\end{cases}
\]

We can write

\[
f'(x,w) = \frac{\phi(y) - \phi(y')}{2} \prod_{i=1}^k (x_i + \kappa_i) \left(w + \frac{\phi(y) + \phi(y')}{\phi(y) - \phi(y')}\right) - B.
\]

To check this, note that

\begin{align*}
f'(x, 1) &= \frac{\phi(y) - \phi(y')}{2} \prod_{i=1}^k (x_i + \kappa_i) \left( \frac{2\phi(y)}{\phi(y) - \phi(y')}\right) - B = f(x,y), \\
f'(x, -1) &= \frac{\phi(y) - \phi(y')}{2} \prod_{i=1}^k (x_i + \kappa_i) \left( \frac{2\phi(y')}{\phi(y) - \phi(y')}\right) - B = f(x,y').
\end{align*}

Since $\phi(y) \neq \phi(y')$, the assumptions of  <Ref> hold with respect to \(f'\). Applying <Ref>, we consider how each of its results translate back to \(f\):

Case 1: \(\kappa_1 = \dots = \kappa_k = B = 0\). So \(f(z) = \phi(y)\prod_{i=1}^k x_i\). Substituting \(x_1=\dots=x_k = 1\), we see that \(\phi\in \left\{ -1,1 \right\}\).

Case 2: \(\kappa_1 , \dots , \kappa_k , B \in \left\{ -1,1 \right\} \). Substitute \(x_i=\kappa_i\) to obtain \(f''(y) \coloneqq f(z)|_{x_i=\kappa_i} = \phi(y)\prod_{i=1}^k 2\kappa_i - B\). Since \(f''\in \left\{ -B,B \right\}\), we have \(\phi(y) \in \left\{ 0, \frac{2B}{\prod_{i=1}^k \left( 2\kappa_i \right)} \right\}\). Denoting \(\tilde{\phi} = \phi / \frac{2B}{\prod_{i=1}^k \left( 2\kappa_i \right)} \in \left\{ 0,1 \right\}\) we get

\begin{align*}
f(z)  &= \left( \frac{2B}{\prod_{i=1}^k \left( 2\kappa_i \right)}\cdot\tilde{\phi}(y) \right)\prod_{i=1}^k(x_{i} + \kappa_{i}) - B \\
&= \tilde{\phi}(y)\cdot 2B \prod_{i=1}^k\frac{x_{i} + \kappa_{i}}{ 2\kappa_i } - B  = \tilde{\phi}(y)\cdot 2B \prod_{i=1}^k\frac{\kappa_i x_{i} + 1}{ 2 } - B,
\end{align*}

where the last equality follows from \(\kappa_i\in \left\{  -1,1\right\}\).

§ PROOF IN THE CASE OF MINIMUM DEGREE 2

Recall the simplifying assumptions we made in <Ref> and in <Ref>: we are given a multilinear generalized polymorphism, which we assume is composed of non-constant, 2-valued-like functions \(g_0,\dots,g_n,f_0,\dots, f_m \), where \(g_0,f_0\) depend on all their inputs.
We retain these simplifying assumptions throughout the section, and justify their use later on in <Ref>.

Moreover, the non-constant assumption will in fact be strengthened: throughout this section, we assume that the functions \(f_0,\dots,f_m,g_0,\dots,g_n\) all have degree at least 2. This assumption is integral to this section, and to its main result in particular. The more general case which relaxes this degree constraint is handled later in <Ref>.

Making this assumption brings about some profound benefits: first, for 2-valued-like functions, the combination of <Ref> and <Ref> (whose usage we later justify through <Ref>) yields many shortcuts to longer arguments made in <Ref>; second, the exclusion of degree 1 functions from \(f_1,\dots,f_m,g_1,\dots,g_n\) hides multiple degrees of freedom that are inherent in the general characterization in <Ref> — intuitively (and not very formally), this section contains one degree of freedom, located in the definitions of \(f_0\) and \(g_0\), while in <Ref>, every single dictator from \(f_1,\dots,f_m,g_1,\dots,g_m\) adds another degree of freedom to the characterization!

Plan of the proof

The proof consists of three main steps:

* <Ref>: The Fourier supports of $f_1,\ldots,f_m$ and $g_1,\ldots,g_n$ contain a unique inclusion-maximal set.

* <Ref>: After applying an affine transformation, $f_1,\ldots,f_m$ and $g_1,\ldots,g_n$ become monomials.

* <Ref>: The functions $f_0,g_0$ arise from a single function $h\colon \R^k \to \R$ whose inputs are the products of the row variables (in the case of $f_0$) or the column variables (in the case of $g_0$) belonging to each block.

Finally, <Ref> allows us to prove the main result of this section, <Ref>, in which we classify all Boolean generalized polymorphisms $f_0,\ldots,f_m,g_0,\allowbreak\ldots,g_n$ where $f_0,g_0$ depend on all their inputs and $f_0,\ldots,f_m,g_0,\ldots,g_n$ have degree at least $2$.

§.§ Preliminaries

Since nearly all subsequent preliminary results portrayed in <Ref> depend on <Ref>, we require \(f_1,\dots,f_m,g_1,\dots,g_n\) to be balanced throughout most of the section. To use these results in later sections, we apply <Ref> onto \(f_0,\dots,f_m,g_0,\allowbreak,\dots,g_n\) and obtain a similar generalized polymorphism \(G_0,\dots,G_n,F_0,\dots,F_m\) that is guaranteed to have balanced \(F_1,\dots,F_m,G_1,\dots,G_n\). Evidently, the particular way in which <Ref> is applied has a substantial effect on the complexity of the remaining arguments. Hence, for the sake of simplicity, we delay the actual application of <Ref> until <Ref>, and for now simply assume that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced, unless explicitly stated otherwise (as is the case in <Ref>).

An alternative way of justifying the arguments in this section, without assuming balancedness, is to apply <Ref> at the onset of the proofs for each of the subsequent preliminary results, continue the proof in the same way, then use the various results denoted in <Ref> to show that the result propagates back to the original \(f_0,\dots,f_m,g_0,\dots,g_n\). This approach is used more broadly in the main theorem, and as a special case, in <Ref>.  However, since applying this approach across all remaining preliminary results introduces unnecessary complications, we keep the assumption of balancedness for them.

Recall the partition of \(Z_0\) given in <Ref>. Since constructing the partition depended on the sets \(\dep(g_1),\dots,\dep(g_n),\dep(f_1),\dots,\dep(f_m)\), one can intuitively consider each partition set to be encoded within the \(g_i,f_j\) functions associated with it through their \(\dep(\cdot)\)-sets. A somewhat less intuitive observation, which the next claim begins to reveal, is that the entire partition is always implicitly encoded in the Fourier spectra of \(f_0\) and \(g_0\).

Let \(\ell \in [k]\) denote one of the sets in the partition \(Z_0 = \bigsqcup_{1}^k Z_i\), and let \(S \in \supp(\hat{f}_0)\) such that \(|S \cap \rows(Z_\ell)| = r > 0\). Then, either \(r = |\rows(Z_\ell)|\) or there exists some \(S'\in \supp(\hat{f}_0)\) such that \(\left\lvert S'\cap \rows(Z_\ell) \right\rvert  > r\). Similarly, if \(T\in \supp(\hat{g}_0)\) and \(|T\cap\cols(Z_\ell)| = c > 0\), then either \(c = |\cols(Z_\ell)|\) or there exists some \(T'\in \supp(\hat{g}_0)\) such that \(|T'\cap \cols(Z_\ell)| > c\).

In other words, the above lemma implies that for every \(\ell\in [k]\), there exists at least one monomial in the Fourier expansion of \(f_0\) that contains \(x_{\rows(Z_\ell)}\) as a factor, and at least one monomial in the Fourier expansion of \(g_0\) that contains \(y_{\cols(Z_\ell)}\) as a factor.

This claim also holds for multilinear functions that are not necessarily 2-valued-like, using a somewhat more involved argument, whose proof can be found at Appendix (TODO: write appendix).
The remaining arguments in this section are also formulated for 2-valued-like functions solely due to their dependence on this result. If we replace this lemma by the one in the appendix, then we get an identical characterization for multilinear functions in general — in fact, the reader can verify that the proofs of the remaining claims do not require any of the two properties stated in <Ref>.

We prove the claim only for \(f_0\), since the proof for \(g_0\) is symmetric.

Let $S \in \supp(\hat{f}_0)$ be such that $I = S \cap \rows(Z_\ell)$ has cardinality $r$ in the range $1 \leq r < |\rows(Z_\ell)|$. From <Ref>, there exist \(i_0\in I\) and \(i_1 \in \rows(Z_\ell) \setminus I\) such that \(g_{i_0}\) and \(g_{i_1}\) depend on the same coordinate \(w\in [m]\).

Since every \(\{g_i\}_{i\in I}\) has degree at least 2, there are \(\left\{ T_i \right\}_{i\in I}\) of size at least 2 in the supports of these \(g_i\)'s. Moreover, since $g_{i_0}$ is 2-valued-like and depends on $w$, we can choose a $T_{i_0}$ containing $w$ (this is the only usage of the 2-valued-like property in this section).
Apply <Ref> (recall that \(f_1,\dots,f_m,g_1,\dots,g_n\) are assumed to be balanced in the introduction of this section) over \(S,\left\{ T_i \right\}_{i\in I}\) and some arbitrary nonempty \(\{T_i\in \supp(\hat{g}_i)\}_{i\in S \setminus I}\) (a vacuous condition if $I = S$), and get that \(T = \bigcup_{i\in S} T_i\in \textnormal{supp}(\hat{g}_0)\) and for every \(j\in T\) the set \(S_j \coloneqq \left\{ i\in S \mid j\in T_i  \right\}\) is in \( \supp(\hat{f}_j)\). In particular, since \(|T_i| \geq 2\) for every \(i\in I\), the definition of the above \(S_j\)-sets implies that every \(i\in I\) is included within at least two sets out of \(\left\{ S_j \right\}_{j\in T}\). Note that $w \in T$ since $w \in T_{i_0}$.

Now apply <Ref> over \(T,\left\{ S_j \right\}_{j\in T - w}\) and some \(S_w'\in \supp(\hat{f}_w)\) containing \(i_1\) (one must exist due to <Ref>). The resulting \(S' = \bigcup_{T\setminus \left\{ w \right\}} S_j \cup S_w' \in \textnormal{supp}(\hat{f}_0)\) indeed contains \(I\cup \left\{ i_1 \right\}\): it contains \(i_1\) since it contains \(S_w'\); and it contains \(I\) since every \(i\in I\) appears at least twice in \(\left\{ S_j \right\}_T\), therefore appears at least once in \(\left\{ S_j \right\}_{T - w}\).

From <Ref> and the assumption that $f_0,g_0$ depend on all variables (and so the support of their Fourier expansions mention all variables by <Ref>) we immediately get:

For every \(\ell\in [k]\), there exist some \(S\in \textnormal{supp}(\hat{f}_0)\) and \(T \in \textnormal{supp}(\hat{g}_0)\) such that \(\rows(Z_\ell) \subseteq S\) and \(\cols(Z_\ell) \subseteq T\).

<Ref> implies that the Fourier expansions of \(f_0\) and \(g_0\) indeed include information regarding the partition in some way. In the next section we show that even more information about the partition is encoded within those functions. But for now, we use it to show how \(g_1,\dots,g_n,f_1,\dots,f_m\) relate to affine shifts of monomials.

One easily observable property of affine shifts of monomials \(f\) is that the supports of their Fourier expansions contain a single inclusion-maximal set, which is exactly \(\dep(f)\). We can show that this property holds in our case:

For every $i \in [n]$ and every $j \in [m]$:

* \(\supp(\hat{g}_i)\) contains a unique inclusion-maximal set, which is \(\dep(g_i)\).

* \(\supp(\hat{f}_j)\) contains a unique inclusion-maximal set, which is \(\dep(f_j)\).

Let \(i_0\in [n]\) and suppose that some set \(U_{i_0} \neq [m]\) is inclusion-maximal set in the support of \(\hat{g}_{i_0}\). We show that \(U_{i_0}\) is the only inclusion-maximal set in \(\supp(\hat{g}_i)\), and therefore must equal \(\dep(g_i)\) (due to <Ref>); the proof for \(\hat{f}_j\) is symmetric.

Let \(Z_\ell\) be the set in the partition of \(Z_0\) that contains \(i_0\). From <Ref> there exists some inclusion-maximal \(S \in \textnormal{supp}(\hat{f}_0)\) such that \(\rows(Z_\ell) \subseteq S\).  Suppose for the sake of contradiction that there is some inclusion-maximal \(U_{i_0}' \in \supp(\hat{g}_{i_0})\) such that \(U_{i_0}\neq U_{i_0}'\), and let \(w\in U_{i_0}'\setminus U_{i_0}\). Since \(\deg(f_w) \geq 2\), there exists some \(i_1\in \dep(f_w) - i_0\), so from <Ref> it follows that \(w\in \dep(g_{i_1})\). Since $f_w$ depends on both $i_0$ and $i_1$, by definition of \(Z_\ell\) it follows that \(i_1\in \rows(Z_\ell) \subseteq S\).  Let \( \left\{ U_i \right\}_{i\in S\setminus \left\{ i_0,i_1 \right\}}\) be arbitrary inclusion-maximal sets in the respective supports of \(\left\{ \hat{g}_i \right\}_{i\in S \setminus \left\{ i_0,i_1 \right\}}\), and let \(U_{i_1}\) be some inclusion-maximal set in the support of \(\hat{g}_{i_1}\) that contains \(w\) (using <Ref>).

Applying <Ref> and <Ref> on these \(S,\left\{ U_i \right\}_{i\in S}\), we get that \(T = \bigcup_{i\in S} U_i\in \textnormal{supp}(\hat{g}_0)\) and for every \(j\in T\) the set \(S_j \coloneqq \left\{ i\in S \mid j\in U_i  \right\}\) is inclusion-maximal in \( \supp(\hat{f}_j)\). Note that $w \in T$ since $w \in U_{i_1}$, and that $S_w$ contains $i_1$ but not $i_0$ (since \(w\not\in U_{i_0} \) by construction).

However, by applying <Ref> on \(S,\left\{ U_{i} \right\}_{i\in S-i_0}, U_{i_0}'\) we get that the set

\[S_{w}' \coloneqq \left\{ i_0 \right\} \cup \left\{ i\in S - i_0 \mid w\in U_i \right\} = \left\{ i_0 \right\} \cup S_w\]

is in \(\supp(\hat{f}_w)\). Since \(i_0\not\in S_w\), this implies that \(S_w \subsetneq S_w'\in \supp(\hat{f}_w)\), contradicting the inclusion-maximality of \(S_w\) in \(\supp(\hat{f}_w)\).

Having used the partition to get constraints on the Fourier expansions of \(f_0,g_0\), and using the latter to get constraints on the Fourier expansions of \(g_1,\dots,g_n,f_1,\dots,f_m\), we now combine both results to see how they relate to each other:

For every \(\ell\in [k]\):

* \(Z_\ell = \bigcup_{i\in \rows(Z_\ell)} \left\{ z_{ij} \mid j\in \dep(g_i) \right\} = \bigcup_{j\in \cols(Z_\ell)} \left\{ z_{ij} \mid i\in \dep(f_j) \right\}\).

* There exists some \(W\subseteq Z_0\) in the Fourier support of \(f_0\circ(g_1,\dots,g_n)\) that contains $Z_\ell$.

<Ref> follows by applying the partition of \(Z_0\) on <Ref>.

For the second item, use <Ref> to get some \(S\in \supp(\hat{f}_0)\) containing \(\rows(Z_\ell)\), then apply <Ref> on every \(i\in \rows(Z_\ell) \subseteq S\), and finally take some arbitrary sets \(U_i\) in the supports of \(\hat{g}_i\) for every \(i\in S\setminus \rows(Z_\ell)\).

The Fourier expansion of $f_0 \circ (g_1,\ldots,g_n)$ is

\[
\sum_{R \in \supp(\hat{f}_0)} \hat{f}_0(R) \prod_{i \in R} \sum_{T_i \in \supp(\hat{g}_i)} \hat{g}_i(T_i) \prod_{\substack{i \in R \\ j \in T_i}} z_{ij}.
\]

Since the functions $g_1,\ldots,g_n$ are balanced, each monomial appears exactly once in the sum. In particular, the Fourier coefficient of $W = \bigcup_{i \in S} \{ z_{ij} \mid j \in U_i\}$ is $\hat{f}_0(S) \prod_{i \in S} \hat{g}_j(U_i)$ which is non-zero, and so $W$ is the required set in the Fourier support of $f_0 \circ (g_1,\ldots,g_n)$.

As stated previously, <Ref> can be easily made to hold also when \(f_1,\dots,f_m,\allowbreak g_1,\dots,g_n\) are not necessarily balanced. We show this now, since applying it on unbalanced functions simplifies the notations used later on in the argument:

<Ref> holds also for possibly unbalanced \(f_1,\dots,f_m,g_1,\dots,g_n\).

Apply <Ref> over \(f_0,\dots,f_m,g_0,\dots,g_n\) to get \(F_0,\dots,F_m,G_0,\dots, G_n\).

Since \(F_1,\dots,F_m,G_1,\dots,\allowbreak G_m\) are balanced, we may apply <Ref>. From <ref> and <ref> of <Ref>, the result holds also for \(f_1,\dots,f_m,g_1,\allowbreak\dots,g_n\).

§.§ 2-valued-like characterization

The next few results will constitute the characterization of all multilinear 2-valued-like generalized polymorphisms.
As stated in the previous section, the 2-valued-like constraint is an artifact of the proof of <Ref>. If the latter is proved using the proof in the appendix, the forthcoming characterization would hold for all multilinear \(f_0,\dots,f_m,g_1,\dots,g_n\).
We retain the assumption that \(f_0,g_0\) depend on all coordinates, as well as the core assumption of this section, namely that \(f_0,\dots,f_m,g_0,\dots,g_n\) all have degree at least \(2\). Conversely, we no longer assume that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced. Therefore, before using any results that depend on this property, we will explicitly invoke <Ref>. Any repercussions on the characterization that this invocation have are discussed in the main theorem.

We start off the characterization by showing that \(f_1,\dots,f_m,g_1,\dots,g_n\) are monomials, up to some change of variables. In other words, the functions \(f_1,\dots,f_m,g_1,\dots,g_n\) are shifts of monomials, or equivalently, that there exists some shift of the inputs of \(f_1,\dots,f_m,g_1,\dots,g_n\) by some set of constants, under which \(f_1,\dots,f_m,g_1,\dots,g_n\) become monomials. Before shifting the input and showing this result, we need to show that shifting the input doesn't invalidate the assumptions made in the preliminaries (otherwise all of the preceding results cannot be applied after changing variables!):

For every \(i\in [n]\), let \(\tilde{g}_i\) be defined as
\(\tilde{g}_i = g_i(y_1-\kappa_{i1},\dots, y_m-\kappa_{im})\) for some constants \(\left\{ \kappa_{ij}\in \R \right\}_{j\in \dep(g_i)}\),
and for every \(j\in [m]\), let \(\tilde{f}_j\) be defined as \(\tilde{f}_j = f_j(x_1-\kappa_{1j},\dots,x_n - \kappa_{nj})\) for some constants \(\left\{ \kappa_{ij}\in \R \right\}_{i\in \dep(f_j)}\).

* For every \(i\in [n]\) and \(j\in [m]\), the functions \(\tilde{g}_i\) and \(\tilde{f}_j\) have degree at least 2 and are 2-valued-like.

* \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\) is a multilinear generalized polymorphism with the same \(Z_0\)-set
\( f_0,\dots,\allowbreak f_m,g_0,\dots,g_n\).

Since \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\dots,\tilde{g}_n\) are all shifted translations, <Ref> implies that their degree is also at least 2, and <Ref> implies that they are 2-valued-like.

The first part of the second item is trivial since the shift amounts to a change of variables on either side of <Ref>. The preservation of \(Z_0\) follows from the first item, and in particular the preservation of inclusion-maximal sets in the Fourier supports of the shifted functions (<Ref>), which implies preservation of \(\dep\)-sets and therefore of \(Z_0\).

With the preceding prop:shifted_reduction in mind, the subsequent lemma will shift the inputs in some way; in the resulting generalized polymorphism \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\) (defined over the same \(Z_0\)-set), all functions have degree at least \(2\), \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\dots,\tilde{g}_n\) are 2-valued-like, and \(f_0,g_0\) will depend on all of their inputs. We can then finally invoke <Ref> over \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\), and get a generalized polymorphism \(F_0,\dots,F_m,G_0,\dots,G_m\), which retains the above properties (the 2-valued-like property by <Ref> in <Ref> and the latter two from <Ref>, and <Ref>, <Ref> in <Ref>) and for which \(F_1, \dots F_m,G_1,\dots,G_n\) are all balanced (from <Ref>, <Ref>). In other words, we can reduce the original generalized polymorphism into one of this form, by applying <Ref>, followed by <Ref>, without losing the assumptions made about these functions. In fact, since \(\dep(G_i) = \dep(\tilde{g}_i) =  \dep(g_i)\) for all \(i\in [n]\) (and similarly for \(f_j,\tilde{f}_j\) and \(F_j\)), we will always refer to this set by \(\dep(g_i)\), to prevent any ambiguity about this fact.

Thus, given a multilinear generalized polymorphism \(f_0,\dots, f_m,g_0,\dots,g_n\), where \(f_1,\dots,f_m,g_1,\dots,g_n\) are 2-valued-like (and not necessarily balanced), \(f_0,g_0\) depend on all of their inputs, and all functions have degree at least \(2\), we refer to the generalized polymorphism \(F_0,F_1,\dots,F_m,G_0,G_1,\dots,G_n\) obtained from the former by shifting (<Ref>) and balancing (<Ref>) as its shifted generalized polymorphism, where \(F_1,\dots,F_m,G_1,\dots,G_n\) are 2-valued-like and balanced, \(F_0,G_0\) depend on all their inputs, and \(G_0,\dots,G_n,F_0,\dots,F_m\) all have degree at least \(2\). The subsequent arguments will concern only the (unique) construction and usage of the shifted general polymorphism \(F_0,\dots,F_m,G_0,\dots,G_m\) obtained from \(f_0,\dots,f_m,g_0,\dots,g_m\) in this way, and in the main theorem, <Ref>, we translate these results back in terms of \(f_0,\dots,f_m,g_0,\dots,g_n\).

There exists a choice of \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\) such that if we define

\begin{align*}
\tilde{g}_i = g_i(y_1-\kappa_{i1},\dots, y_m-\kappa_{im}), & \text{ for every \(i\in  [n]\),} \\
\tilde{f}_j = f_j(x_1-\kappa_{1j},\dots,x_n - \kappa_{nj}), & \text{ for every \(j\in [m]\)}
\end{align*}

and obtain \(F_0,F_1,\dots,F_m,G_0,G_1,\dots,G_n\) by applying <Ref> over the generalized polymorphism

\[f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\]

then for each \(i\in [n]\) and \(j\in [m]\), \(G_i\) and \(F_j\) have the following form:

\begin{align*}
G_i(y) = C_i \cdot y_{\dep(G_i)} = C_i\cdot y_{\dep(g_i)}, & \text{ for every \(i\in [n]\)}, \\
F_j(x) = A_j\cdot x_{\dep(F_j)} = A_j \cdot x_{\dep(f_j)}, & \text { for every \(j\in [m]\)}
\end{align*}

for some non-zero constants \(C_1,\dots,C_n,A_1,\dots,A_m\).

Note that $F_1,\dots,F_m,G_1,\dots,G_n$ are balanced by definition, and that the shifted generalized polymorphism obtained is

\begin{equation} \label{eq:deg2_shifted_with_constants}
F_0 \circ \left( C_1 \cdot z_{1\dep(G_1)},\dots,C_n \cdot z_{n\dep(G_n)} \right) = G_0 \circ \left( A_1 \cdot z_{\dep(F_1)1},\dots, A_m \cdot z_{\dep(F_m)m} \right).
\end{equation}

Consider the generalized polymorphism \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,\allowbreak g_0,\tilde{g}_1,\dots,\tilde{g}_n\) which we obtain from \(f_0,\dots,f_m,\allowbreak g_0,\dots,g_n\) by <Ref>.

Since the Fourier expansion of \(\tilde{f}_j\) is obtained from that of \(f_j\) by substitution, and given that both functions have degree at least two, we can describe the Fourier coefficients of \(\tilde{f}_j\) as multilinear combinations of the Fourier coefficients of \(f_j\). In particular, we obtain the following set of equations:

\[
\hat{\tilde{f}}_j\left( \dep(f_j) - i \right) = \hat{f}_j\left( \dep(f_j) - i \right) - \kappa_{ij}\hat{f}_j\left( \dep(f_j) \right)
\]

for any \(j\in [m]\) and \(i\in [n]\).

From <Ref> (applied over the generalized polymorphism \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\allowbreak\tilde{g}_1,\dots,\tilde{g}_n\)), we have \(\hat{f}_j\left( \dep(f_j) \right)\neq 0\), so we can define \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\dots,\tilde{g}_n\) by fixing the set of constants \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\) that act as the (unique) solutions for the set of equations:

\begin{equation} \label{eq:kappa-selection}
0 = \hat{\tilde{f}}_j\left( \dep(\tilde{f}_j) - i \right) = \hat{f}_j\left( \dep(f_j) - i \right) - \kappa_{ij}\hat{f}_j\left( \dep(f_j) \right)
\end{equation}

for every \(i\in [n],j\in [m]\). Explicitly, $\kappa_{ij} = \hat{f}_j(\dep(f_j)-i)/\hat{f}_j(\dep(f_j))$.

With \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\) in place and well-defined by our selection of \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\), we invoke <Ref> and obtain the shifted generalized polymorphism \(F_0,\dots,F_m,G_0,\allowbreak\dots,G_m\) (so in particular \(F_1,\dots,\allowbreak F_m,G_1,\dots,G_n\) are balanced, allowing us to use the preliminary results requiring this property).

We continue by showing that the shifted generalized polymorphism constructed through this solution set satisfies the results of the claim. In particular, we show that the only sets in the Fourier supports of \(G_1,\dots,G_n,F_1,\dots,F_m\) are the sets given by <Ref>, namely \(\dep(g_1,)\dots,\dep(g_n),\dep(f_1),\dots,\dep(f_m)\). We start by showing this for \(G_1,\dots,G_n\).

Let \(i_0\in [n]\) and let \(Z_\ell\subseteq Z_0\) be the set in the partition of \(Z_0\) such that \(i_0 \in \rows(Z_\ell)\). Use <Ref> to get some \(S\in \supp(\hat{F}_0)\) that contains \(\rows(Z_\ell)\), let \(U_{i_0}\subseteq [m]\) be some set distinct from \(\dep\left( g_{i_0} \right)\), and suppose for the sake of contradiction that \(U_{i_0} \in \supp\left( \hat{G}_{i_0} \right)\).

From <Ref> and <Ref>, we must have \(U_{i_0} \subsetneq \dep\left( g_{i_0} \right)\), therefore there exists some \(w\in \dep\left( g_{i_0}  \right) \setminus U_{i_0}\). Since \(F_w\) has degree at least 2, there be some \(i_1\in \rows(Z_\ell) - i_0 \subseteq S\) such that \(w\in \dep\left( g_{i_1} \right)\).

Applying <Ref> over \(S,U_{i_0}\) and \(\left\{ \dep\left( g_{i} \right) \right\}_{i\in S - i_0}\), we get that

\[T = \left( \bigcup_{i\in S - i_0} \dep(g_i) \right) \cup U_{i_0} \in \supp(\hat{f}_0)\]

and that for every \(j\in T\), the set

\[
V_j = \begin{cases}
\left\{ i\in S - i_0 \mid j\in \dep(g_i) \right\} \cup \left\{ i_0 \right\},& \textnormal{ if } j\in U_{i_0}, \\
\left\{ i\in S - i_0 \mid j\in \dep(g_i) \right\},& \textnormal{otherwise}
\end{cases}
\]

is in the support of \(\hat{F}_j\). Since \(w\in \dep\left( g_{i_1} \right)\subseteq T\) and \(w\not\in U_{i_0}\), it follows that \(V_w = \left\{ i\in S - i_0 \mid w\in \dep(g_i) \right\}\). Seeing as \(\dep(f_w) = \left\{ i\in \rows(Z_\ell) \mid w\in \dep(g_i) \right\}\), and given that \(\rows(Z_\ell) \subseteq S\) and \(i_0\in \dep(f_w)\), it follows that \(V_w = \dep(f_w) - i_0\). However, by construction (specifically, <Ref>), this set is not in $\supp(\hat{F}_w)$, and we reach a contradiction.

We conclude that \(\supp(\hat{G}_i) = \left\{ \dep(g_i) \right\}\), therefore there exists some \(C_i\in \R\) such that

\begin{equation} \label{eq:Gi_characterization}
G_i(y) = C_i \cdot y_{i\dep(g_i)}.
\end{equation}

It remains to show that

\begin{equation} \label{eq:fj_characterization}
F_j(x) = A_j \cdot x_{\dep(f_j)j}
\end{equation}

for every \(j\in [m]\), for some constants \(A_j\in \R\). Showing this can be done using a symmetric argument, with the sole difference being that \(\hat{G}_i\left( \dep(g_i) - j \right) = 0\) now follows from <Ref> instead of from <Ref>.

Before moving on to the characterization of \(f_0\) and \(g_0\), let us recall <Ref>. We showed there that \(f_0\) and \(g_0\) are “aware" of the partition of \(Z_0\), in that for every \(Z_\ell\), each contains at least one set in its Fourier support that includes \(\rows(Z_\ell)\) and \(\cols(Z_\ell)\), respectively. Evidently, once we know that \(f_1,\dots,f_m,g_1,\dots,g_n\) are monomials (up to a change of variables), a much stronger claim can be made:

Suppose that \(F_0,\dots,F_m,G_0,\dots,G_n\) is the shifted polymorphism obtained from <Ref>. Then for every \(\ell\in [k]\), every set \(S\in \supp(\hat{f}_0)\) that intersects \(\rows(Z_\ell)\) contains \(\rows(Z_\ell)\), and every set \(T\in \supp(\hat{g}_0)\) that intersects \(\cols(Z_\ell)\) contains \(\cols(Z_\ell)\).

We show the result for \(F_0\), the result for \(G_0\) is similar.

Let \(\ell \in [k]\) and let \(S\in \supp(\hat{F}_0)\) such that \(S\cap \rows(Z_\ell) \neq \emptyset\). Suppose for the sake of contradiction that \(S\cap\rows(Z_\ell) \subsetneq \rows(Z_\ell)\), then from <Ref> there exist some \(i_1\in \rows(Z_\ell) \setminus S\), \(i_0\in S \cap \rows(Z_\ell)\), and \(w\in [m]\) such that \(w\in \dep\left( g_{i_0} \right)\cap \dep \left( g_{i_1} \right)\).

An application of <Ref> over \(S, \left\{ \dep(g_i) \right\}_{i\in S}\) implies that

\[V_w = \left\{ i\in S \mid w\in \dep(g_i) \right\}\]

is in the support of \(\hat{f}_w\), where \(i_1\not\in V_w\) since \(i_1\not\in S\). However \(V_w\neq \dep(f_w)\) since \(i_1\in \dep(f_w)\setminus V_w\), in contradiction to <Ref>.

Combining <Ref> and <Ref> immediately implies that the Fourier support of a shifted generalized polymorphism “respects” the partition of \(Z_0\):

Let \(W\subseteq Z_0\) be some set in the Fourier support of a shifted general polymorphism
\(F_0,F_1,\dots,F_m,\allowbreak G_0,G_1,\dots,G_n\), let \(\ell\in [k]\) and suppose that \(W\cap Z_\ell \neq \emptyset\). Then, \(Z_\ell \subseteq W\).

It will be helpful to work through the characterization of \(F_0\) and \(G_0\) without carrying around the constants \(C_1,\dots,C_n,A_1,\dots,A_m\). By applying the reduction

\begin{equation} \label{eq:f0_constant_reduction}
F'_0(x_1,\dots,x_n) = F_0(C_1x_1,\dots,C_nx_n)
\end{equation}

\begin{equation} \label{eq:g0_constant_reduction}
G'_0(y_1,\dots,y_m) = G_0(A_1y_1,\dots,A_m y_m),
\end{equation}

it is trivial to verify that all assumptions on the shifted generalized polymorphism \(G_0,G_1,\dots,G_n,F_0,F_1,\dots\allowbreak, F_m\) are preserved under this reduction, and in particular \(F'_0,G'_0\) are still of degree at least two and depend on all their inputs. Moreover, \(G_0',\dots,G_n,F_0',\dots,F_m\) is a shifted generalized polymorphism over the same \(Z_0\) set.

Given this reduction and <Ref>, the characterization of \(F'_0,G'_0\) becomes easy as well:

Suppose that \(F'_0,F_1,\dots,F_m,G'_0,G_1,\dots,G_m\) is a generalized polymorphism, where \(G_i\) and \(F_j\) are given by <Ref>, and in addition
\(C_i = A_j = 1\) for all $i \in [n]$ and $j \in [m]$. Then there exists a function \(h\colon \{-1,1\}^k \to \R\) such that

\begin{equation} \label{eq:f0_characterization}
F'_0(x) = h\left( \prod_{i\in \rows(Z_1)}   x_i,\dots, \prod_{i\in \rows(Z_k)}  x_i \right)
\end{equation}

\begin{equation}\label{eq:g0_characterization}
G'_0(y)  = h\left( \prod_{j\in \cols(Z_1)}  y_j,\dots, \prod_{j\in \cols(Z_k)} y_j\right) .
\end{equation}

From <Ref>, there exist constants \(\alpha_K\) such that

\[
F'_0 \circ (G_1,\dots,G_n) =
\sum_{K \subseteq [k]} \alpha_{K} \prod_{\ell \in K} \prod_{z_{ij}\in Z_\ell} z_{ij} =
\sum_{K \subseteq [k]} \alpha_{K} \prod_{\ell \in K} \prod_{i\in \rows(Z_\ell)} z_{i\dep(G_i)}.
\]

From the uniqueness of the Fourier expansion, there exists a unique real-valued function \(h_{F'_0}\colon \left\{ -1,1 \right\}^{k} \to \R\) with a Fourier expansion \(h_{F'_0}(x) = \sum_{K \subseteq [k]} \alpha_{K} x_{K}\), and in particular

\[
h_{F'_0}\left( \prod_{i\in \rows(Z_1)} z_{i\dep(G_i)},\dots,\prod_{i\in \rows(Z_k)} z_{i\dep(G_i)} \right) = F'_0 \circ (G_1,\dots,G_n).
\]

Similarly, there is a function \(h_{G'_0}\colon \left\{ -1,1 \right\}^k \to \R\) and constants \(\beta_K\) such that \(h_{G'_0} = \sum_{K\subseteq [k]} \beta_K y_K\) and in particular

\[
h_{G'_0} \left(  \prod_{j\in \cols(Z_1)} z_{\dep(F_1)1},\dots,\prod_{j\in \cols(Z_k)} z_{j\dep(F_j)} \right) = G'_0\circ(F_1,\dots,F_m).
\]

Since \(F'_0\circ(G_1,\dots,G_n) = G'_0 \circ(F_1,\dots,F_m)\), we conclude by defining \(h\) as \(h_{F'_0} \equiv h_{G'_0}\).

Having characterized all functions appearing in the generalized polymorphism, we can now write the main result, with all simplifying assumptions lifted, except for the following:

* All of \(f_0,\dots,f_m,g_0,\dots,g_n\) have degree at least 2 — this is a core assumption for this section, and will only be lifted in the next section.

* \(f_0,g_0\) depend on all their inputs — any coordinate \(j\in [m]\) that \(g_0\) does not depend on corresponds to a completely arbitrary \(f_j\), which effectively does not appear in <Ref>, and similarly for irrelevant coordinates of \(f_0\), as we show formally in the conclusion of <Ref>.

* \(f_1,\dots,f_m,g_1,\dots,g_n\) are 2-valued-like — as stated previously, this is an artifact of the proof for the current section.

Suppose that \(f_0,\dots,f_m,g_0,\dots,g_n\) is a multilinear generalized polymorphism, where \(f_0,g_0\) depend on all their inputs, \(\deg(g_0),\dots,\deg(g_n),\deg(f_0),\dots,\allowbreak\deg(f_m) \geq 2\), and \(f_1,\dots,f_m,g_1,\dots,g_n \) are 2-valued-like. Then there are:

* a subset of the input matrix \(Z_0 \subseteq Z\),

* a partition of \(Z_0\) into submatrices \(Z_0 = \bigsqcup_{1}^k Z_i\), where the submatrices are pairwise disjoint in rows and in columns (meaning every row or column in \(Z_0\) is included within exactly one \(Z_i\) for \(i > 0\)),

* an arbitrary function \(h\colon \left\{ -1,1 \right\}^k \to \R \),

* real constants \(\left\{ A_j \right\}_{[m]}, \left\{ B_j \right\}_{[m]}, \left\{ C_i \right\}_{[n]}, \left\{ D_i \right\}_{[n]} \),

* real constants \(\left\{ \kappa_{ij}\right\}_{z_{ij}\in Z_0}\),

such that:

\begin{align*}
f_0(x) & = h\left( \prod_{i\in \rows(Z_1)}   \left(  \frac{x_i - D_i}{C_i} \right),\dots, \prod_{i\in \rows(Z_k)}  \left(  \frac{x_i-D_i}{C_i}\right)\right),\\
f_j(x) & = A_j \prod_{i \in \dep(f_j)} \left( x_i + \kappa_{ij} \right) + B_j, \\
g_0(y) & = h\left( \prod_{j\in \cols(Z_1)}  \left(  \frac{y_j - B_j}{A_j}  \right),\dots, \prod_{j\in \cols(Z_k)} \left( \frac{y_j - B_j}{A_j}  \right)\right), \\
g_i(y) & = C_i \prod_{j \in \dep(g_i)} (y_j + \kappa_{ij} ) + D_i.
\end{align*}

Apply <Ref> to get a shifted generalized polymorphism \(F_0, \dots, F_m,\allowbreak G_0, \allowbreak \dots, G_n \) where all functions have degree at least \(2\), \(F_1,\dots,F_m,G_1,\dots,G_n\) are 2-valued-like and balanced, and \(F_0,G_0\) depend on all of their inputs. From <Ref>, the functions \(G_1,\dots,G_n,F_1,\dots,F_m\) have the form <Ref> and <Ref>. Define $F'_0,G'_0$ using <Ref> and <Ref>. The functions $F'_0,F_1,\ldots,F_m,G'_0,\allowbreak G_1,\allowbreak \ldots,G_n$ satisfy the same properties as $F_0,\ldots,F_m,G_0,\ldots,G_n$.

Applying <Ref>, we get that \(F'_0,G'_0\) are given by <Ref> and <Ref>.

The characterization now results from unrolling the reductions. Starting with \(F'_0\) (unrolling \(G'_0\) is completely analogous): we unroll <Ref> to obtain \(F_0\) from \(F_0'\); then unroll the application of <Ref> on \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\), to obtain \(f_0\) from \(F_0\). Thus:

\[
F'_0(x_1,\dots,x_n) = F_0\left( C_1 \cdot x_1 ,\dots, C_n \cdot x_n \right) =  f_0\left( C_1 \cdot x_1 + \hat{\tilde{g}}_1(\emptyset),\dots, C_n \cdot x_n + \hat{\tilde{g}}_n(\emptyset) \right),
\]

\[
F'_0 \left(  \frac{x_1 - \hat{\tilde{g}}_1(\emptyset)}{C_1},\dots,  \frac{x_n - \hat{\tilde{g}}_n(\emptyset)}{C_n} \right) = f_0(x_1,\dots,x_n).
\]

Substituting this into <Ref> and setting \(D_i = \hat{\tilde{g}}_i(\emptyset)\) yields the result in <Ref>.

Similarly for \(G_1, \dots, G_n\) (getting \(F_1,\dots, F_m\) is again completely analogous), for every \(i\in [n]\) we unroll <Ref> to get \(\tilde{g}_i\) from \(G_i\), then unroll the definition of \(\tilde{g}_i\) to obtain \(g_i\) from \(\tilde{g}_i\). Thus,

\[
G_i(y_1,\dots,y_m) = \tilde{g}_i(y_1,\dots,y_m) -\hat{\tilde{g}}_i(\emptyset) = g_i(y_1 - \kappa_{i1},\dots, y_m - \kappa_{im}) - \hat{\tilde{g}}_i(\emptyset),
\]

\[
G_i(y_1+\kappa_{i1},\dots,y_m+\kappa_{1m}) + \hat{\tilde{g}}_i(\emptyset) = g_i(y_1,\dots,y_m).
\]

Substituting into <Ref> and using the values of \(D_i\) set above, we get the characterization in <Ref>.

§.§ Boolean characterization

Since Boolean functions are trivially 2-valued-like, we can combine the 2-valued-like characterization obtained in <Ref> with <Ref> and obtain a characterization for all Boolean generalized polymorphisms of degree at least 2.
We proceed by first characterizing Boolean \(g_1,\dots,g_n,f_1,\dots,f_m \):

Suppose that \(g_0,\dots,g_n,f_0,\dots,f_m\) is a Boolean generalized polymorphism, where all functions have degree at least 2, and \(f_0,g_0\)  depend on all their inputs. Then for every \(\ell\in [k]\), one of the following holds:

* For all \(i\in \rows(Z_\ell)\) and \(j\in \cols(Z_\ell)\),

\begin{align*}
f_j = A_j \prod_{i=1}^{\dep(f_j)} x_i, \text{ where } A_j \in \{-1,1\},
\end{align*}

\begin{align*}
g_i = C_i \prod_{j=1}^{\dep(g_i)} y_j, \text{ where } C_i \in \{-1,1\}.
\end{align*}

* There exists a \(\left\{ -1,1 \right\}\)-assignment \(\left\{ \kappa_{ij} \right\}_{(i,j)\in Z_\ell} \in \left\{ -1,1 \right\}^{|Z_\ell|}\) such that for all \(i\in \rows(Z_\ell)\) and \(j\in \cols(Z_\ell)\),

\begin{align*}
f_j = 2B_j \prod_{i=1}^{\dep(f_j)} \frac{\kappa_{ij} x_i + 1}{2} - B_j, \text{ where } B_j \in \{-1,1\},
\end{align*}

\begin{align*}
g_i = 2D_i \prod_{j=1}^{\dep(g_i)} \frac{\kappa_{ij} y_j + 1}{2} - D_i, \text{ where } D_i \in \{-1,1\}.
\end{align*}

<Ref> gives a formula for $g_1,\ldots,g_n,f_1,\ldots,f_m$ in terms of the parameters $A_j,B_j,C_i,D_i,\kappa_{ij}$. Since the functions are Boolean, <Ref> implies that for each $j \in [n]$, one of the following cases holds:

* $B_j = 0$ and $\kappa_{ij} = 0$ for all $i \in \dep(f_j)$.

* $B_j \in \{-1,1\}$ and $\kappa_{ij} \in \{-1,1\}$ for all $i \in \dep(f_j)$.

Similarly, for each $i \in [m]$, one of the following cases holds:

* $D_i = 0$ and $\kappa_{ij} = 0$ for all $j \in \dep(g_i)$.

* $D_i \in \{-1,1\}$ and $\kappa_{ij} \in \{-1,1\}$ for all $j \in \dep(g_i)$.

In particular, if $z_{ij} \in Z_\ell$ then $g_i$ and $f_j$ belong to the same case, since they share $\kappa_{ij}$. The definition of $Z_\ell$ as a connected component implies that the functions $f_j$ for $j \in \cols(Z_\ell)$ and the functions $g_i$ for $i \in \rows(Z_\ell)$ all belong to the same case. This implies the corollary using the formulas in <Ref>.

Putting everything together, we obtain a classification of all Boolean generalized polymorphisms of degree at least 2:

Suppose that \(g_0,g_1,\dots,g_n,f_0,f_1,\dots,f_m\) is a boolean generalized polymorphism, where all functions have degree at least 2, and \(f_0,g_0\)  depend on all their inputs. Then there exist

* a subset of the input matrix \(Z_0 \subseteq Z\),

* a partition of \(Z_0\) into non-contiguous submatrices \(Z_0 = \bigsqcup_{1}^k Z_i\), where the submatrices are pair-wise disjoint in rows and in columns (meaning every row or column in \(Z_0\) is included within exactly one \(Z_i\) for \(i > 0\)),

* an arbitrary function \(h\colon\left\{ -1,1 \right\}^k \to \left\{ -1,1 \right\} \),

* for every $\ell \in [k]$, functions $f_0^{(\ell)}\colon \{-1,1\}^{\rows(Z_\ell)} \to \{-1,1\}$ and $g_0^{(\ell)}\colon \{-1,1\}^{\cols(Z_\ell)} \allowbreak\to \{-1,1\}$,

such that

\begin{align*}
f_0(x) &= h\left(f_0^{(1)}(x|_{\rows(Z_1)}), \ldots, f_0^{(k)}(x|_{\rows(Z_k)})\right), \\
g_0(y) &= h\left(g_0^{(1)}(y|_{\cols(Z_1)}), \ldots, g_0^{(k)}(y|_{\cols(Z_k)})\right),
\end{align*}

and for every $\ell \in [k]$, one of the following cases holds:

* For all \(i\in \rows(Z_\ell)\) and \(j\in \cols(Z_\ell)\) we have

\begin{align*}
g_i &= C_i \prod_{j \in \dep(g_i)} y_j, \text{ where } C_i \in \{-1,1\}, \\
f_j &= A_j \prod_{i \in \dep(f_j)} x_i, \text{ where } A_j \in \{-1,1\},
\end{align*}

\begin{align*}
f_0^{(\ell)} &= \prod_{i \in \rows(Z_\ell)} \frac{x_i}{C_i}, \\
g_0^{(\ell)} &= \prod_{j \in \cols(Z_\ell)} \frac{y_j}{A_j}.
\end{align*}

* For all \(i\in \rows(Z_\ell)\) and \(j\in \cols(\ell)\),

\begin{align*}
g_i &= 2D_i \prod_{j \in \dep(g_i)} \frac{\kappa_{ij} y_j + 1}{2} - D_i, \text{ where } D_i,\kappa_{ij} \in \{-1,1\}, \\
f_j &= 2B_j \prod_{i \in \dep(f_j)} \frac{\kappa_{ij} x_i + 1}{2} - B_j, \text{ where } B_j,\kappa_{ij} \in \{-1,1\},
\end{align*}

\begin{align*}
f_0^{(\ell)} &= 2\prod_{i \in \rows(Z_\ell)} \frac{D_i x_i + 1}{2} - 1, \\
g_0^{(\ell)} &= 2\prod_{j \in \cols(Z_\ell)} \frac{B_j y_j + 1}{2} - 1.
\end{align*}

The formulas for $g_i,f_j$ follow directly from
<Ref> shows that for some $h'\colon \{-1,1\}^k \to \R$,

\begin{align*}
f_0(x) & = h'\left( \prod_{i\in \rows(Z_1)} \left(  \frac{x_i - D'_i}{C'_i} \right),\dots, \prod_{i\in \rows(Z_k)} \left(  \frac{x_i-D'_i}{C'_i}\right)\right),\\
g_0(y) & = h'\left( \prod_{j\in \cols(Z_1)}  \left(  \frac{y_j - B'_j}{A'_j}  \right),\dots, \prod_{j\in \cols(Z_k)} \left( \frac{y_j - B'_j}{A'_j}  \right)\right),
\end{align*}

where the parameters $A'_j,B'_j,C'_i,D'_i$ are defined according to the two cases in the statement of the theorem:

* $A'_j = A_j$, $B'_j = 0$, $C'_i = C_i$, $D'_i = 0$.

* $A'_j = 2B_j/\prod_{i \in \dep(f_j)} (2\kappa_{ij})$, $B'_j = -B_j$, $C'_i = 2D_i/\prod_{j \in \dep(g_i)} (2\kappa_{ij})$, $D'_i = -D_i$.

The inputs to the function $h'$ are not necessarily in $\{-1,1\}$. By applying appropriate affine shifts, we will ensure that the input is indeed in $\{-1,1\}$, obtaining the function $h$ as well as the functions $f_0^{(\ell)},g_0^{(\ell)}$. Since the inputs to $h$ are $\{-1,1\}$ and each input can be achieved, and since $f_0,g_0$ are $\{-1,1\}$-valued, it follows that $h$ maps $\{-1,1\}^k$ to $\{-1,1\}$.

Suppose that the $\ell$'th block obeys <Ref>. The $\ell$'th input to $h'$ in the definition of $f_0$ is

\[
\prod_{i \in \rows(Z_\ell)} \frac{x_i}{C_i},
\]

which is already in $\{-1,1\}$. Therefore in this case we define $f_0^{(\ell)},g_0^{(\ell)}$ to be the $\ell$'th inputs to $h'$ in the definitions of $f_0,g_0$ above.

If the $\ell$'th block instead obeys <Ref>, the $\ell$'th input to $h'$ in the definition of $f_0$ is

\[
\prod_{(i,j) \in Z_\ell} (2\kappa_{ij}) \prod_{i \in \rows(Z_\ell)} \frac{x_i + D_i}{2D_i} =
\prod_{(i,j) \in Z_\ell} (2\kappa_{ij}) \prod_{i \in \rows(Z_\ell)} \frac{D_i x_i + 1}{2}.
\]

If $x_i \neq D_i$ for some $i \in \rows(Z_\ell)$ then this equals $0$, and otherwise it equals the first product above. In particular,

\[
2\prod_{i \in \rows(Z_\ell)} \frac{D_i x_i + 1}{2} - 1
\]

is $\{-1,1\}$-valued. Moreover, the transformation needed to get from the $\ell$'th input to $h'$ in the definition of $f_0$ to this one is the same as the transformation needed to get from the $\ell$'th input to $h'$ in the definition of $g_0$ to this one. Therefore we define $f_0^{(\ell)},g_0^{(\ell)}$ accordingly, and modify $h'$ by applying the inverse of this transformation to the $\ell$'th input.

By transforming this result to hold on the \(\left\{ 0,1 \right\}\)-cube rather than the \(\left\{ -1,1 \right\}\)-cube (using the correspondence \(0 \iff 1\) and \(1 \iff -1\)), we get that:

* for every \(i\in [n],j\in [m]\), all \(g_i,f_j\) are (possibly negated) XOR/AND/OR functions of literals.

* \(f_0,g_0\) are obtained by applying a Boolean function \(h\) to (possibly negated) XOR/AND/OR of literals.

* for every block \(Z_\ell\), its associated functions \(\left\{ g_i \right\}_{i\in \rows(Z_\ell)}, \left\{ f_j \right\}_{j\in \cols(Z_\ell)}, f_0^{(\ell)}, g_0^{(\ell)}\) are either all (possibly negated) XORs of literals, or all (possibly negated) AND/ORs of literals.

§ PROOF IN THE GENERAL CASE

Recall the characterization made in <cit.> for the special case of generalized polymorphisms of the form \(f_0 \circ g^n = g_0 \circ (f_1,\dots,f_m)\). The characterization laid out in <cit.> showed that up to input negation, either all functions are XORs of literals, or all are ANDs/ORs of literals. This holds for all generalized polymorphisms of that form, except for a few special cases involving dictator functions and arbitrary functions.

Comparing this result to the main result of the previous section, <Ref>, shows that the constraint $g_1=\dots=g_n$ enforces a uniformity of structure, and without it there exist solutions combining the XOR type with the AND/OR type.

The main result of the current section, <Ref>, explains where the special cases of dictators and arbitrary functions originate from, and shows how both the XOR/AND/OR case and the dictator/arbitrary-function case seen in <cit.> blend into a single characterization of generalized polymorphisms.

In the previous section, we allowed \(g_1,\dots,g_n\) to be distinct while constraining them and \(f_1,\dots,f_m\) to have degree of at least 2. This kept their structure roughly the same as in <cit.>, with one key exception: the set of functions \(g_1,\dots,g_n,f_1,\dots,f_m\) naturally partitions into disjoint sets, where all functions associated with the same partition set behave very similarly to the entire characterization seen in <cit.>, and where the functions \(f_0^{(\ell)},g_0^{(\ell)}\) associated with that partition set play the role that \(f_0\) and \(g_0\) did in <cit.>. Moreover, the generalized polymorphism in its entirety amounts to an arbitrary Boolean function with these instances interpolated into its entries. Constraining the degrees of $g_1,\dots,g_n,f_1,\dots,f_m$ also allowed us to avoid the dictator/arbitrary-function case encountered in <cit.>.

With the degree constraint lifted, we see in the current section that without loss of generality, each dictator \(g_i\) adds a degree of freedom manifesting itself as an arbitrary function \(\phi_j\) interpolated into the function \(f_j\) (and analogously for dictator \(f_j\)'s). The difference between this degree of freedom and the special cases seen in <cit.> is that the uniformity of structure arising from \(g_1=\dots=g_n\) made this special case permeate throughout all functions in the polymorphism in <cit.>, while here, the non-uniform nature of the characterization explored in the previous section helps contain this degree of freedom within a smaller isolated scope.

The characterization obtained in this section will resemble the one seen in <Ref> (an arbitrary Boolean function \(h\) with <cit.>-like characterizations interpolated into its entries), along with the aforementioned arbitrary \(\phi_j\) functions embedded into the structure of \(f_j\) (and similarly, arbitrary functions $\gamma_i$ embedded into the structure of $g_i$).

Plan of the proof

The proof consists of three main steps:

* <Ref>: For every function out of $f_1,\ldots,f_m$ and $g_1,\ldots,g_n$, there exists a unique subset of its support that is included within every inclusion-maximal set in the Fourier support.

* <Ref>: After applying an affine transformation, each of $f_1,\ldots,f_m$ and $g_1,\ldots,g_n$ becomes a product of a monomial (over the unique set of coordinates mentioned in the previous item) with an arbitrary (but possibly constant) function, which we denote by \(\phi_1,\dots,\phi_m\) and \(\gamma_1,\dots,\gamma_n\), respectively.

* <Ref>: The functions $f_0,g_0$ arise from a single function $h\colon \R^k \to \R$ whose inputs are typically products of the row variables with \(\phi_j\) functions with possibly negated inputs from that block (in the case of $f_0$), or products of column variables with \(\gamma_i\) functions with possibly negated inputs from that block (in the case of $g_0$).

Finally, <Ref> allows us to prove the main result of this section, <Ref>, in which we classify all Boolean generalized polymorphisms $f_0,\ldots,f_m,g_0,\ldots,\allowbreak g_n$ without any assumptions.

§.§ Preliminaries

We start this section from the same point in the argument as in the outset of <Ref>. Namely, we retain all assumptions made there, except for the assumption all degrees being at least 2, which is lifted, and the assumption of all functions being 2-valued-like, which is replaced with a stronger property:

A function $f\colon \{-1,1\}^n \to \R$ is Boolean-like if

* \(f\) is 2-valued-like.

* \(\deg(f) = 1\) if and only if \(f\) is of the form $\pm z$, where $z$ is one of the inputs.

Since Boolean-like functions only differ from 2-valued-like functions when they have degree \(1\), we will sometimes refer to Boolean-like functions of degree larger than 1 as 2-valued-like.

Before going over all of the assumptions for this section in more detail, we show that <Ref>, which we used to obtain balancedness for the functions \(f_1,\dots,f_m,g_1,\dots\allowbreak,g_n\) in <Ref>, also preserves the Boolean-line property for \(f_1,\dots,f_m,g_1,\dots,g_n\):

Let \(f_0,\dots,f_m \colon \left\{ -1,1 \right\}^{n} \to \R\) and \(g_0,\dots,g_n \colon \left\{ -1,1 \right\}^{m} \to \R\), and let \(F_0,\dots,F_m,G_0,\dots,G_n\) be the functions defined in <Ref>. Then, if \(f_1,\dots,f_m,g_1,\allowbreak\dots,g_n\) are Boolean-like, then also \(F_1,\dots,F_m,G_1,\allowbreak\dots,G_n\) are Boolean-like.

In other words, when \(f_1,\dots,f_m,g_1,\dots,g_n\) are Boolean-like, items 1, 3, 4 and 5 in <Ref> still hold (since they are independent of the Boolean-like property), whereas the second item is strengthened to show that the Boolean-like property is preserved, and not just the (weaker) 2-valued-like property.

Since \(f_1,\dots,f_m,g_1,\dots,g_n\) are Boolean-like, they are in particular 2-valued-like. Therefore, the second item of <Ref> implies that \(F_1,\dots,F_m,G_1,\dots,G_n\) are 2-valued-like. It remains to show that if a function among \(F_1,\dots,F_m,G_1,\dots,G_n\) has degree \(1\) then it has the form \(\pm z\), where \(z\) is one of its inputs (the other direction is trivial since \(\pm z\) has degree \(1\) by definition). We show this for an arbitrary \(g_i\), the proof for the \(f_j\) functions is similar.

Let \(i\in [n]\), and suppose that \(\deg(G_i) = 1\). Since \(G_i\) is 2-valued-like, there exists some \(j\in [m]\) such that \(G_i = \hat{G}_i(j)y_j + \hat{G}_i(\emptyset)\). Since \(G_i = g_i - \hat{g}_i(\emptyset) \), it follows that \(g_i = \hat{G}_i(j)y_j + \hat{G}_i(\emptyset) + \hat{g}_i(\emptyset)\), so in particular \(\deg(g_i) = 1\). Since \(g_i\) is Boolean-like, in fact \(g_i = \hat{G}_i(j)y_j\), and in particular \(\hat{G}_i(j) \in \left\{ -1,1 \right\}\) and \(\hat{g}_i(\emptyset) + \hat{G}_i(\emptyset) = 0 \). Furthermore, since \(g_i = \pm y_{j}\), by definition \(\hat{g}_i(\emptyset) = 0\), hence also \(\hat{G}_i(\emptyset) = 0\).
Substituting these values back into the Fourier expansion of \(G_i\), we get that \(G_i = \pm y_{j}\), as needed.

In total, the assumptions we make in this section are as follows:

* The functions \(f_0,\dots,f_m,g_0,\dots,g_n\) are non-constant: in the previous section we assumed these functions have degree at least \(2\). There, it was an integral assumption included in the main result. Here, we only assume these functions are non-constant, for the sake of simplicity, and lift this assumption when we get to the main theorem.

* The functions \(f_0,g_0\) depend on all of their inputs: as was the case in the previous section, we keep this assumption throughout the section for the sake of readability.

* The functions \(f_1,\dots,f_m,g_1,\dots,g_n\) are Boolean-like:
unlike in the previous section, where the 2-valued-like property was an artifact of the proof of a single preliminary result, in this section both the Boolean-like property and the 2-valued-like property are used heavily. In fact, the additional assumption made in the previous section, that all functions have degree at least 2, simplified the arguments there to such an extent that we were able to obtain a characterization for multilinear generalized polymorphisms, rather than our stated goal of characterizing Boolean generalized polymorphisms. Evidently, lifting the Boolean-like assumption in this section (or even the 2-valued-like assumption) makes the argument much more involved. Indeed, the heavy usage of the 2-valued-like property and the Boolean-like property helps mitigate the complexity of the argument when allowing functions to attain any degree.
when allowing functions to attain any degree, the argument becomes substantially more complex; the Boolean-like property helps mitigate this.
After obtaining a characterization for this setting, we use it in order to obtain a characterization for Boolean generalized polymorphisms.

* The functions \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced: similar to what we did in the previous section, we assume balancedness for the next few sections, before lifting this assumption when we get to the generalization of <Ref>. Once again, during the (unique) construction of the shifted generalized polymorphism arising from \(f_0,\dots,f_m,g_0,\dots,g_n\), we explicitly invoke <Ref> in order to obtain balanced \(F_1,\dots,F_m,G_1,\dots,G_n\).

§.§.§ Obtaining a finer decomposition

The decomposition \(Z_0 = \bigsqcup_{\ell\in [k]} Z_\ell\) suffices for the proof seen in <Ref>, which assumes that all functions appearing in the generalized polymorphism have degree at least 2. When this assumption is removed, we see that every \(Z_\ell\) must be partitioned further, to differentiate between dictator functions and functions of degree at least $2$ (these are the only two cases according to <Ref>.)

Let \(Z_\ell\) be one of the sets in the partition of \(Z_0\).

* The notation \(\rowsone(Z_\ell) \subseteq \rows(Z_\ell)\) denotes all \(i\in \rows(Z_\ell)\) corresponding to dictator \(g_i\) functions. That is ,

\[
\rowsone(Z_\ell) = \left\{ i\in \rows(Z_\ell) \mid \deg(g_i) = 1 \right\}.
\]

* The notation \(\rowstwo(Z_\ell) \subseteq \rows(Z_\ell)\) denotes the remaining rows, that is

\[
\rowstwo(Z_\ell) = \left\{  i\in \rows(Z_\ell) \mid \deg(g_i) \geq 2\right\}.
\]

* The notation \(\Ztwo_\ell\) denotes all \(z_{ij}\in Z_\ell\) such that \(i\in \rowstwo(Z_\ell)\) and \(j\in \colstwo(Z_\ell)\).

Effectively, this implies that each \(Z_\ell\) can be decomposed into a “star" form by applying row and column permutations, as demonstrated in <Ref>. For any \(Z_\ell\), observe that if no \(g_i,f_j\) associated with it is a dictator, we have \(\Ztwo_\ell = Z_\ell\). Moreover, as we show in subsequent subsections, all preliminary results shown in the previous section have an analogue in the current section, with \(\Ztwo_\ell\) playing the part that \(Z_\ell\) did there.

\begin{equation*}
\left(
\begin{array}{ccccc}
\ddots & & \vdots & &  \iddots\\
& \gray Z_\ell  & z_{23} & z_{24} & \\
& \gray Z_\ell  & z_{23} & z_{24} & \\
\dots & \gray Z_\ell  & \gray Z_\ell & \gray Z_\ell &\dots \\
& \gray Z_\ell  & \gray Z_\ell & z_{44}  & \\
\iddots & & \vdots & &\ddots \\
\end{array}
\right)
\end{equation*}

\begin{equation*}
\downarrow
\end{equation*}

\begin{equation*}
\left(
\begin{array}{ccccc}
\ddots & & \vdots & &  \iddots\\
& \green i\in\rows_{=1}Z_\ell  & z_{23} & z_{24} & \\
& \green i\in\rows_{=1}Z_\ell  & z_{23} & z_{24} & \\
\dots & \red Z_\ell^{\geq 2}  & \red Z_\ell^{\geq 2} & j\in\blue\cols_{= 1}Z_\ell &\dots \\
& \red Z_\ell^{\geq 2}  & \red Z_\ell^{\geq 2} & z_{44}  & \\
\iddots & & \vdots & &\ddots \\
\end{array}
\right)
\end{equation*}

\begin{align*}
\end{align*}

\begin{align*}
\left(
\begin{array}{ccccc}
\ddots & & \vdots & &  \iddots\\
& i\in\green \rows_{=1}Z_\ell  & z_{23} & z_{24} & \\
& i\in\green\rows_{=1}Z_\ell  & z_{23} & z_{24} & \\
\dots & \red i\in\rows_{\geq 2}Z_\ell  & \red i\in\rows_{\geq 2}Z_\ell & \red i\in\rows_{\geq 2}Z_\ell &\dots \\
& \red i\in\rows_{\geq 2}Z_\ell  & \red i\in\rows_{\geq 2}Z_\ell & z_{44}  & \\
\iddots & & \vdots & &\ddots \\
\end{array}
\right)_,
\end{align*}

\begin{align*}
\left(
\begin{array}{ccccc}
\ddots & & \vdots & &  \iddots\\
& \red j\in\cols_{\geq 2}Z_\ell  & z_{23} & z_{24} & \\
& \red j\in\cols_{\geq 2}Z_\ell  & z_{23} & z_{24} & \\
\dots & \red j\in\cols_{\geq 2}Z_\ell  & \red j\in\cols_{\geq 2}Z_\ell & \blue j\in\cols_{= 1}Z_\ell &\dots \\
& \red j\in\cols_{\geq 2}Z_\ell  & \red j\in\cols_{\geq 2}Z_\ell & z_{44}  & \\
\iddots & & \vdots & &\ddots \\
\end{array}
\right)
\end{align*}

\begin{equation*}
\end{equation*}

[Decomposing the submatrices of the input matrix partition]
The first matrix depicts some block \(Z_\ell\) out of the block-diagonal matrix \(Z\). We can decompose it into \(Z_\ell^{\geq 2}\), which can be informally thought of as the intersection of \(\rows_{\geq 2}(Z_\ell)\) and \(\cols_{\geq 2}(Z_\ell)\), where every other \(z_{ij}\in Z_\ell \setminus Z_\ell^{\geq 2}\) is associated with either a dictator \(g_i\) or a dictator \(f_j\). In this section, the set \(Z_\ell^{\geq 2}\) will have a similar structure to that of \(Z_\ell\) in the previous section (where all functions had degree at least 2), while the remaining parts of \(Z_\ell\) will have a wholly different form.

In the previous section, we saw in <Ref> that every strict subset of \(\rows(Z_\ell)\) relates to its complement in \(\rows(Z_\ell)\) by some coordinate shared between \(g_i\) functions inside the subset and outside of it. In light of the finer partition seen above, we prove an analogue of this claim for strict subsets of \(\rowstwo(Z_\ell)\).

Let $\emptyset \neq I \subseteq \rows(Z_\ell)$ be such that \(\rowstwo(Z_\ell) \not\subseteq I\). Then there exist \(i_0\in I\) and \(i_1 \in \rowstwo(Z_\ell) \setminus I\) such that \(g_{i_0}\) and \(g_{i_1}\) depend on the same coordinate \(w\in [m]\).

Define \(I' \subseteq \rows(Z_\ell)\) by adding to \(I\) all \(i'\in \rowsone(Z_\ell)\) such that \(g_{i'}\) depends on the same coordinate as some \(g_i\) where \(i\in I\). Formally

\[
I' = I \cup \left\{ i'\in \rowsone(Z_\ell) \;\middle|\; \dep(g_{i'}) \cap \left( \bigcup_{i\in I} \dep(g_i) \right) \neq \emptyset\right\}.
\]

Since \(I' \cap \rowstwo(Z_\ell) = I \cap \rowstwo(Z_\ell) \) by construction, we have \(\rowstwo(Z_\ell) \subsetneq I'\) by the assumption on \(I\). Therefore, we may apply <Ref> on \(I'\) and obtain some \(i_0\in I'\) and \(i_1\in \rows(Z_\ell) \setminus I'\) that depend on the same coordinate \(w\). Since \(I'\supseteq I\), we have \(i_1\not \in I\), so it remains to show that \(i_1\in \rowstwo(Z_\ell)\) and that there is some \(i_2\in I\) that depends on \(w\) (or in other words, that we may assume that \(i_0\in I\)).