If \(i_0\in \rowstwo(Z_\ell)\), then it is also in \(I\), since \(I'\setminus I \subseteq \rowsone(Z_\ell)\) (therefore we have \(i_0=i_2\)). So suppose that \(i_0 \in I' \setminus I\), therefore \(i_0\in \rowsone(Z_\ell)\), and in particular \(\dep(g_{i_0}) = \{ y_w \} \), since $g_{i_0}$ is 2-valued-like. However, \(i_0\in I'\setminus I\) implies by construction that there must be some \(i_2\in I\) such that \(\dep(g_{i_2})\cap \dep(g_{i_0}) \neq \emptyset\). But since \(\dep(g_{i_0}) = \left\{ w \right\} \), it follows that \(g_{i_2}\) depends on \(w\), as needed.

Finally, suppose for the sake of contradiction that \(i_1\in \rowsone(Z_\ell)\). Then since both \(g_{i_2}\) and \(g_{i_1}\) depend on the same coordinate \(w\), it follows by definition of \(I'\)  that \(i_1\in I'\), contrary to the fact that \(i_1\not\in I'\).
We conclude that \(i_1\in \rowstwo(Z_\ell) \setminus I\), as needed.

§.§.§ Analog of Corollary <ref>

As stated previously, like many of the results seen below, the generalization of <Ref> will be very similar to the one seen before, with \(\Ztwo_\ell\) playing the part that \(Z_\ell\) did in <Ref>. However, for this corr:deg2-exist-S in particular, we prove a slightly stronger result, which almost generalizes the stronger result <Ref>.

Indeed, as we see in <Ref>, once we define the generalization of the notion of shifted generalized polymorphisms for the current setting and generalize <Ref>, the generalization we obtain here would immediately imply a generalization of <Ref>.

The first step towards generalizing <Ref> resembles the original argument, therefore will directly follow a generalization of <Ref>:

Let \(\ell \in [k]\) and let \(S \in \supp(\hat{f}_0)\) such that \(S \cap \rows(Z_\ell)  \neq \emptyset  \). Then, either \(S \cap \rows(Z_\ell) \supseteq \rowstwo(Z_\ell)\), or there exists some \(S'\in \supp(\hat{f}_0)\) such that \(S' \cap \rowstwo(Z_\ell) \supsetneq S \cap \rowstwo(Z_\ell)\). Moreover, in the latter case \(S'\setminus \rows(Z_\ell) = S\setminus \rows(Z_\ell)\).

Note that:

* The last sentence in <Ref> implies that \(S'\) only differs from \(S\) with respect to \(Z_\ell\), a fact which we'll use in the next lemma which characterizes the inclusion-maximal sets of \(G_i\). In contrast, it will be certainly possible that \(S' \cap \rowsone(Z_\ell) \neq S\cap \rowsone(Z_\ell)\).

* The only difference between the proof of this lemma and that of <Ref> is that \(G_{i_0}\) here could be a dictator, but this can be easily ameliorated in light of <Ref>.

If \(\rowstwo(Z_\ell) = \emptyset\) then the claim is trivial, so we may assume \(\rowstwo(Z_\ell) \neq \emptyset\).

Suppose then that \(S\cap \rowstwo(Z_\ell) \subsetneq \rowstwo(Z_\ell)\), and let \(|S \cap \rowstwo(Z_\ell)| = r \), where \(0 \leq r < |\rowstwo(Z_\ell)|\). Denoting \(I = S \cap \rows(Z_\ell)\), we apply <Ref> to get some \(i_1 \in \rowstwo(Z_\ell) \setminus I\) and \(i_0\in I\) such that $g_{i_0}$ and $g_{i_1}$ depend on the same coordinate \(w\in \cols(Z_\ell)\); according to <Ref>, $f_w$ depends on both $i_0$ and $i_1$. We now show that there exists some set in \(\supp(\hat{f}_0)\) that contains \(S\cap \rowstwo(Z_\ell) +  i_1 \) and whose intersection with \(\rows(Z_0)\setminus \rows(Z_\ell)\) is the same as that of \(S\), proving the claim.

In view of <Ref> (recall that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced by the assumption in <Ref>), we now choose non-empty sets $T_i \in \supp(\hat{g}_i)$ for all $i \in S$. If $\deg(g_i) = 1$ then we choose the unique non-empty set in the support, and if $\deg(g_i) \ge 2$, we choose some set of size at least $2$. For $i = i_0$, we moreover require that $w \in T_{i_0}$. Choosing such a set is always possible since $g_{i_0}$ depends on $w$ and $g_{i_0}$ is 2-valued-like.

Apply <Ref> over \(S,\left\{ T_i \right\}_{i\in S}\) to get that \(T = \bigcup_{i\in S} T_i\in \supp(\hat{g}_0)\) contains \(w\), and that there are some \(\left\{ S_j \right\}_{j\in T}\) in the supports of \(\left\{ \hat{f}_j \right\}_{j \in T}\) such that every \(i\in S \cap \rowstwo(Z_\ell)\) appears at least twice in \(\left\{ S_j \right\}_{j\in T}\).

Apply <Ref> again, this time over \(T,\left\{ S_j \right\}_{j\in T\setminus w}\) and some \(S_w'\in \supp(\hat{f}_w)\) containing \(i_{1}\) (such a set exists since $f_w$ depends on $i_1$, via <Ref>). The resulting \(S' = \left( \bigcup_{j\in T - w} S_j \right) \cup S_w' \in \supp(\hat{f}_0)\) indeed contains \(\left( S \cap \rowstwo(Z_\ell)  \right) + i_1 \): it contains \(i_{1}\) since it contains \(S_w'\); it contains \(S \cap \rowstwo(Z_\ell)\) since every \(i\in S \cap \rowstwo(Z_\ell)\) appeared at least twice in \(\left\{ S_j \right\}_{j\in T}\), and so appears at least once in \(\left\{ S_j \right\}_{T - w}\). Finally, since \(w\in \cols(Z_\ell)\), the intersection of \(S'\) with \(\rows(Z_0) \setminus \rows(Z_\ell)\) is the same as that of \(S\), proving the claim.

From <Ref>, we obtain a generalization of <Ref>.

For every \(\ell\in [k]\) and every \(S \in \supp(\hat{f}_0)\) intersecting $\rows(Z_\ell)$, there exists some \(S'\in \supp(\hat{f}_0)\) such that \(\rowstwo(Z_\ell) \subseteq S'\) and \(S \setminus \rows(Z_\ell) = S' \setminus  \rows(Z_\ell)\).

In other words, for every \(S\in \supp(\hat{f}_0)\) that intersects \(\rows(Z_\ell)\) but does not contain \(\rowstwo(Z_\ell)\) there exists some other \(S'\in \supp(\hat{f}_0)\) that contains \(\rowstwo(Z_\ell)\) and is equivalent to \(S\) outside of \(\rows(Z_\ell)\). Note that this corollary implies nothing regarding the relation between \(S\cap \rowsone(Z_\ell)\) and \(S'\cap \rowsone(Z_\ell)\).

Even though <Ref> already serves as a generalization of <Ref>, the subsequent development requires a stronger result to hold. This result, as described in the start of this section, would later immediately imply a generalization of <Ref>, which is indeed a stronger result, and one that was proved only at a later stage in <Ref>.

Let \(\ell\in [k] \). Then every inclusion-maximal \(S\) in the support of \(\hat{f}_0\) that intersects \(\rows(Z_\ell)\) must include \(\rowstwo(Z_\ell)\).

This corr:s_incmax_multiple will follow from <Ref>
and the following lem:rowsone_inclusion_exists, similarly to how <Ref> followed from <Ref>:

Let \(\ell \in [k]\) and suppose that \(\rowstwo(Z_\ell) \neq \emptyset\). Let \(S \in \supp(\hat{f}_0)\) such that \(S \cap \rows(Z_\ell) \neq \emptyset\), and let \(S_0\in \supp(\hat{f}_0)\) be such that \(S_0 \supseteq \rowstwo(Z_\ell)\) and \(S_0 \setminus \rows(Z_\ell) = S\setminus \rows(Z_\ell)\). Then either \(S \subseteq S_0\), or there exist some \(S_1\in \supp(\hat{f}_0)\) and non-empty \(I' \subseteq \left( \rowsone(Z_\ell) \cap S \right) \setminus S_0\) such that \(S_0 \cup I' = S_1\).

Intuitively, either \(S\) is included within \(S_0\), which indeed contains \(\rowstwo(Z_\ell)\), or \(S_0\) has a supported superset \(S_1\) (which therefore also contains \(\rowstwo(Z_\ell)\)) that contains strictly more elements of \(S\) than \(S_0\) did, so is “closer” to containing \(S\) than \(S_0\) was.

Denote \(I \coloneqq S \cap \rowsone(Z_\ell)\).
If \(S \cap \rows(Z_\ell) \subseteq \rowstwo(Z_\ell)\) then \(I = \emptyset\), implying that \(S \subseteq S_0\) since \(S_0\supseteq \rowstwo(Z_\ell)\) and \(S\setminus \rows(Z_\ell) = S_0 \setminus \rows(Z_\ell)\) by the assumptions on \(S_0\).

Therefore, assume that \(S \cap \rows(Z_\ell) \not\subseteq \rowstwo(Z_\ell) \) and that \(S \not\subseteq S_0\), implying that \( I \not \subseteq S_0 \cap \rowsone(Z_\ell)\). Thus, there exists some \(i_0 \in I \setminus S_0\), where \(\dep(g_{i_0}) = \left\{ w \right\}\) for some \(w\in \cols(Z_\ell)\) (since \(g_{i_0}\) is 2-valued-like).

Since \(\rowstwo(Z_\ell) \neq \emptyset\), we can apply <Ref> on \(I = \left\{ i_0 \right\}\) and get some \(i_1\in \rowstwo(Z_\ell) \subseteq S_0\) such that $g_{i_1}$ also depends on \(w\). The set \(S_1\) we are looking for will be found by leveraging \(g_{i_1},S,S_0\) and three applications of <Ref> (\(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced by the assumption in <Ref>), where the output of the third application will be a set \(S_1\in \supp(\hat{f}_0)\) containing \(S_0 + i_0\) and not containing any \(i\in \rows(Z_0) \setminus \rows(S_0)\).

* The first application of <Ref> will be on \(S, \left\{ T_i \right\}_{i\in S}\), where \(T_i\) are arbitrary nonempty sets from the respective supports of \(\left\{ g_i \right\}_{i\in S}\), such that for every \(i\in \rowstwo(Z_\ell)\) we take \(T_i\) of size at least 2 (this is possible since $g_i$ is 2-valued-like). We get \(T = \bigcup_{i\in S} T_i \in \supp(\hat{g}_0)\) and some \(\left\{ S_j \right\}_{j\in T}\) in the supports of \(\left\{ \hat{f}_j \right\}_{j\in T}\) such that for every \(j\in T\), all \(i\in I\) where \(\dep(g_i) = \left\{ j \right\}\) are included in \(S_j\). Also, $w \in T$ since $i_0 \in S$ and $T_{i_0} = \{w\}$.

* The second application of <Ref> will be on \(S_0, \left\{ T_i' \right\}_{i\in S_0}\), where the \(T_i'\) sets are like in the previous item, with the additional stipulation that \(T_{i_1}'\) contains \(w\) as well as being of size at least 2 (this is possible since $g_{i_1}$ is 2-valued-like). We get a set \(T' = \bigcup_{i\in S_0} T_i' \in \supp(\hat{g}_0)\) that contains \(w\) (since \(w \in T_{i_1} \subseteq T'\)), and sets \(\left\{ S_j' \right\}_{j\in T'}\) in the supports of \(\left\{ \hat{f}_j \right\}_{j\in T'}\) such that in \(\left\{ S_j' \right\}_{j\in T'}\), every \(i\in \rowstwo(Z_\ell)\) appears at least twice (since \(\rowstwo(Z_\ell) \subseteq S_0\) by assumption), and every \(i\in \rowsone(Z_\ell) \cap S_0\) appears once.
Moreover, since the $T'_i$ are nonempty, $S_0 = \bigcup_{j \in T'} S_j'$.

* The third and final application of <Ref> will be over the sets \(T',S_w,\allowbreak\left\{ S_j' \right\}_{j\in T' - w}\), which results in \(S_1 = S_w \cup \left( \bigcup_{j\in T' - w} S_j' \right) \in \supp(\hat{f}_0)\).

We now show that this \(S_1\) indeed satisfies our requirements:

* \(S_1 \supseteq \rowstwo(Z_\ell)\): Every \(i\in \rowstwo(Z_\ell)\) appears at least twice in \(\bigcup_{j\in T'} S_j'\), therefore at least once in \(\bigcup_{j\in T' - w} S_j' \subseteq S_1\).

* \(S_1 \supseteq \left( S_0 \cap I  \right) + i_0 \): From <Ref> we have that \(i_0\in S_w \subseteq S_1\). Similarly, for every \(i \in I \cap S_0\) where \(\dep(g_i) = \left\{ w \right\}\) we again have \(i\in S_w \subseteq S_1\). Finally, if \(i\in I \cap S_0\) and \(\dep(g_i) = \left\{ j \right\} \neq \left\{  w \right\}\), then \(i \in S_j' \subseteq S_1\) from <Ref>.

* \(S_1 \setminus \rows(Z_\ell) = S_0 \setminus \rows(Z_\ell)\): Denoting $\tilde S = \bigcup_{j\in T' - w} S_j'$, we have $S_0 = S'_w \cup \tilde S$ and $S_1 = S_w \cup \tilde S$. If $i$ belongs to one of $S_w,S'_w$ then by construction, $g_i$ depends on $w$, and so $i \in \rows(Z_\ell)$. In particular, $S_0$ and $S_1$ only differ on indices in $\rows(Z_\ell)$.

The proof of <Ref> now follows from combining <Ref> and <Ref>:

If \(\rowstwo(Z_\ell) = \emptyset\) then the claim is trivial, so suppose that \(\rowstwo(Z_\ell) \neq \emptyset\).

From <Ref>, there exists some \(S_0\in \supp(\hat{f}_0)\) that contains \(\rowstwo(Z_\ell)\) and for which \(S\setminus \rows(Z_\ell) = S_0\setminus \rows(Z_\ell)\). Applying <Ref> repeatedly, we obtain some \(S' \supseteq S\) that includes \(\rowstwo(Z_\ell)\). Since $S$ is inclusion-maximal, in fact $S' = S$, and so $S$ includes $\rowstwo(Z_\ell)$.

§.§.§ Analog of Corollary <ref>

The generalization of <Ref> marks the first major divergence of the arguments in this section compared to the ones in <Ref>. Indeed, unlike in <Ref>, in this section no function from \(g_1,\dots,g_n, f_1, \dots, f_m\) is guaranteed to have a unique inclusion-maximal set in its Fourier support.

Evidently, the structure of the Fourier support of these functions is quite similar to that of \(f_0\) and \(g_0\), as seen in <Ref>. As such, sets in \(\supp(\hat{g}_i)\) and \(\supp(\hat{f}_j)\) indeed have similar decompositions to those of sets in \(\supp(\hat{f}_0), \supp(\hat{g}_0)\) as seen in <Ref>.
Let \(\ell \in [k]\), let \(i\in \rows(Z_\ell)\) and \(j\in \cols(Z_\ell)\). Denote

\begin{align*}
\dep(g_i) &= \depone(g_i) \sqcup \deptwo(g_i), \\
\dep(f_j) &= \depone(f_j) \sqcup \deptwo(f_j),
\end{align*}

\begin{align*}
\depone(g_i) &\coloneqq \left\{ j\in \dep(g_i) \mid \deg(f_j) = 1 \right\}, \\
\depone(f_j) &\coloneqq \left\{ i \in \dep(f_j) \mid \deg(g_i) = 1 \right\} ,
\end{align*}

\begin{align*}
\deptwo(g_i) &\coloneqq \left\{ j \in \dep(g_i) \mid \deg(f_j) \geq 2 \right\} , \\
\deptwo(f_j) &\coloneqq \left\{ i \in \dep(f_j) \mid \deg(g_i) \geq 2 \right\}.
\end{align*}

With these definitions in mind, we start by finding an analog of <Ref> with respect to the Fourier support of \(f_j\).

Let \(\ell \in [k]\), let \(i_0\in \rows(Z_\ell)\) and let \(T_{i_0}\in \supp(\hat{g}_{i_0})\) be inclusion-maximal. Then, either \(T_{i_0} \cap \deptwo(g_{i_0}) = \deptwo(g_{i_0})\) or there exists some \(T_{i_0}'\in \supp(\hat{g}_{i_0})\) such that \(T_{i_0}' \cap \deptwo(g_{i_0}) \supsetneq T_{i_0} \cap \deptwo(g_{i_0})\).

Denote \(J = \deptwo(g_{i_0}) \cap T_{i_0}\), and suppose that \(\emptyset \neq J \subsetneq \deptwo(g_{i_0}) \) and \(\deg(g_{i_0}) \geq 2\) (otherwise the claim is trivial, using the fact that $g_{i_0}$ is 2-valued-like).

Since $g_{i_0}$ is 2-valued like, $\deg(g_{i_0}) \geq 2$, and \(T_{i_0}\) is inclusion-maximal, the size of \(T_{i_0}\) is at least 2. Since \(J \subsetneq \deptwo(g_{i_0})\), there exists some \(j_0 \in \deptwo(g_{i_0}) \setminus J\). By definition of \(\deptwo(g_{i_0})\) we have \(\deg(f_{j_0}) \geq 2\), therefore there exists some \(i_1 \in \dep(f_{j_0}) - i_0\), implying that \(j_0 \in \dep(g_{i_1})\) from <Ref> (note that the degree of \(g_{i_1}\) may be 1), so in particular there exists some \(T_{i_1} \in \supp(g_{i_1})\) containing \(j_0\).

From <Ref> and since \(f_0\) depends on all of its inputs, there exists some inclusion-maximal set \(S\in \supp(\hat{f}_0)\) that contains \(i_1\), and from <Ref>, \(S\) must also contain \(i_0\) (since we are still assuming that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced, we may invoke this corr:s_incmax_multiple which depends on this property).

It remains to show that there exists some \(T_{i_0}'\in \supp(\hat{g}_{i_0})\) that contains \(J + j_0\); we obtain this \(T_{i_0}'\) by applying <Ref> twice:

* The first application of <Ref> will be on \(S,T_{i_0}, T_{i_1}\) and some arbitrary nonempty \(\left\{ T_i \right\}_{i\in S \setminus \left\{ i_0,i_1 \right\}}\) in the supports of \(\left\{ \hat{g}_i \right\}_{i\in S \setminus \left\{ i_0,i_1 \right\}}\). We get \(T = T_{i_0} \cup T_{i_1} \cup \left( \bigcup_{i\in S\setminus \left\{ i_0,i_1 \right\}} T_i \right) \in \supp(\hat{g}_0)\), where \(j_0\in T\) (since \(j_0\in T_{i_1}\)), and sets \(\left\{ S_j \right\}_{j\in T}\) in the supports of \(\left\{ \hat{f}_j \right\}_{j\in T}\), where \(S_j = \left\{ i\in S \mid j\in T_i  \right\}\). In particular, \(i_0\not\in S_{j_0}\) (since \(j_0\not\in T_{i_0}\)), and for every \(j \in J \subseteq T_{i_0}\) we have \(i_0\in S_j\).

* The second application of <Ref> will be on \(T,\left\{ S_j \right\}_{j\in T - j_0}, S_{j_0}'\), where \(S_{j_0}'\in \supp(\hat{f}_{j_0})\) is an arbitrary set containing \(i_0\) (using <Ref>). <Ref> implies that the set

\[
T_{i_0}' = \begin{cases}
\left\{ j\in T - j_0 \mid i_0\in S_j  \right\} + j_0,& \textnormal{if } i_0\in S_{j_0}', \\
\left\{ j\in T - j_0 \mid i_0\in S_j  \right\},& \textnormal{otherwise}
\end{cases}
\]

is in \(\supp(\hat{g}_{i_0})\). Since \(i_0 \in S_{j_0}'\), it follows that \(j_0\in T_{i_0}'\), and from <Ref> we know that \(J \subseteq T - j_0\) and \(i_0\in S_j\) for every \(j\in J\); thus, \(J + j_0 \subseteq T_{i_0}'\), as needed.

From <Ref> we immediately get:

For every \(\ell\in [k]\) and every \(i\in \rows(Z_\ell)\) there exists some \(T_{i} \in \supp(\hat{g}_i)\) such that \( \deptwo(g_{i})\subseteq T_{i}\).

We can now find the analog of <Ref>, which as stated previously indeed resembles <Ref>.

Let \(i_0\in \rows(Z_\ell) \). Then every inclusion-maximal \(T_{i_0}\in \supp(\hat{g}_{i_0})\) includes \(\deptwo(g_{i_0})\).

Suppose first that \(T_{i_0} \subseteq \deptwo(g_{i_0})\). From <Ref> (which depends on \(f_1,\dots,f_m,g_1,\dots,g_n\) being balanced, which is still assumed) there exists some inclusion-maximal \(T_{i_0}'\) that contains \(\deptwo(g_{i_0})\). Since \(\deptwo(g_{i_0})\) contains \(T_{i_0}\), it follows that \(T_{i_0} \subseteq T_{i_0}'\), therefore \(T_{i_0} = T_{i_0}'\) since \(T_{i_0}\) is inclusion-maximal.

Next, suppose that \(T_{i_0} \not \subseteq \deptwo(g_{i_0})\), so in particular \(J \coloneqq T_{i_0} \cap \depone(g_{i_0}) \neq \emptyset\). We continue in a similar manner to previous arguments, by applying <Ref> twice in order to obtain some \(T_{i_0}' \in \supp(\hat{g}_{i_0}) \) containing both \(T_{i_0}\) and \(\deptwo(g_{i_0})\), which therefore equals \(T_{i_0}\) since \(T_{i_0}\) is inclusion-maximal.

* The first application of <Ref> will be on \(S,T_{i_0}, \left\{ T_i \right\}_{i\in S - i_0}\), where \(S\) is some arbitrary set in \(\supp(\hat{f}_0)\) containing \(i_0\) (which exists since \(f_0\) depends on all of its inputs), and \(\left\{ T_i \right\}_{i\in S - i_0}\) are arbitrary nonempty sets in the supports of \(\left\{ \hat{g}_i \right\}_{i\in S - i_0}\). We get \(T = T_{i_0} \cup \left( \bigcup_{i\in S - i_0} T_i \right) \in \supp(\hat{g}_0)\) that contains \(J\) (since it contains \(T_{i_0}\supseteq J\)) and sets \(\left\{ S_j \right\}_{j\in T}\) in the supports of \(\left\{ \hat{f}_j \right\}_{j\in T}\), where \(S_j = \left\{ i\in S \mid j\in T_i  \right\}\). In particular, for every \(j\in J \subseteq T_{i_0} \subseteq T\) we have \(i_0\in S_j\).

* The second application of <Ref> will be on \(T',\left\{ S_j \right\}_{j\in J}, \left\{ S_j' \right\}_{j\in T' \setminus J}\), where \(T'\) is some arbitrary inclusion-maximal set in \(\supp(\hat{g}_0)\) containing \(T\), and the sets \(\left\{ S_j' \right\}_{j\in T' \setminus J}\) are arbitrary nonempty sets in the supports of \(\left\{ \hat{f}_j \right\}_{j\in T' \setminus J}\) that are taken so that \(i_0\in S_j'\) whenever \(i_0\in \dep(f_j)\). We get that

\[
T_{i_0}' =
\left\{ j\in J \mid i_0\in S_j  \right\} \cup
\left\{ j\in T' \setminus J \mid i_0\in S_j'  \right\} =
J \cup \left\{ j\in T' \setminus J \mid i_0\in S_j'  \right\}
\]

is in the support of \(\hat{g}_{i_0}\), where the second equality follows from the last sentence of the previous item.

From <Ref> (applied symmetrically on \(\hat{g}_0\)) we get that \(\colstwo(Z_\ell) \subseteq T'\). In fact, \(\colstwo(Z_\ell) \subseteq T' \setminus J\) since \(J \subseteq \colsone(Z_\ell)\), so in particular \(\deptwo(g_{i_0}) \subseteq T' \setminus J\) (since \(\deptwo(g_{i_0}) \subseteq \colstwo(Z_\ell)\)). Thus, since every \(S_j'\) contains \(i_0\) whenever \(i_0\in \dep(f_j)\) — which happens whenever $j \in \dep(g_{i_0})$ by <Ref> — it follows in particular that \(\deptwo(g_{i_0}) \subseteq \left\{ j \in T' \setminus J \mid i_0\in S_j' \right\}\), therefore \(\deptwo(g_{i_0}) \subseteq T_{i_0}'\).

Since \(T_{i_0} = J \sqcup \left( T_{i_0} \cap \deptwo(g_{i_0}) \right)\) by definition, it follows that

\[T_{i_0} = J \sqcup \left( T_{i_0} \cap \deptwo(g_{i_0}) \right) \subseteq J \cup \deptwo(g_{i_0}) \subseteq T_{i_0}',\]

therefore \(T_{i_0} = T_{i_0}'\) from the inclusion-maximality of \(T_{i_0}\).

As was the case in <Ref>, it is easy to show that the above generalization of <ref> holds also without assuming \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced. We do this now since the result will be useful in subsequent arguments.

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

The proof is virtually the same as that of <Ref>:
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 (and Boolean-like due to <Ref>), we may apply <Ref>. From the third and fourth items of <Ref>, the result holds also for \(f_1,\dots,f_m,g_1,\allowbreak\dots,g_n\).

§.§ Boolean-like characterization

The next few results will constitute the characterization of all Boolean-like generalized polymorphisms. As stated in the preliminaries section, and unlike the case in <Ref>, assuming that \(f_1,\dots,f_m,g_1,\dots,g_n\) are Boolean-like is an integral part of the characterization, since removing it requires a more involved argument.

However, in congruence to our argument in <Ref>, we retain the assumption of \(f_0,g_0\) depending on all of their inputs and that \(f_0,\dots,f_m,g_0,\dots,g_n\) are non-constant (as simplifying assumptions). Moreover, from this point on we no longer assume that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced, thus (temporarily) losing access to all preliminary results relying on this property. After proving a generalization of <Ref> in this section (without relying on any preliminary results that rely on balancedness), we prove a generalization of <Ref> in the next section, and in the process of which explicitly invoke <Ref>. Thus, we again obtain a similar (shifted) generalized polymorphism, \(F_0,\dots,F_m,G_0,\dots,G_n\), in which \(F_1,\dots,F_m,G_1,\dots,G_n\) are again balanced (and remain Boolean-like by <Ref>). In the main theorem, we use the obtained characterization for this type of generalized polymorphism to obtain a characterization of all Boolean-like general polymorphisms, and finally of all Boolean general polymorphisms.

At this point of the argument in <Ref>, in <Ref>, we defined a shifted generalized polymorphism and used it to show that \(g_1,\dots,g_n,f_1,\dots,f_m\) are affine shifts of monomials. Equivalently, we showed 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.  In principle, the forthcoming argument will be the same. However, as will be clarified in the next subsection, the change-of-variables from which the shift is composed of will now be applied over \(\Ztwo_0 = \bigcup_{\ell \in [k]} \Ztwo_\ell\) rather than over \(Z_0\). Furthermore, the characterization we produce in this section will only be applicable for Boolean-like \(f_1,\dots,f_m,g_1,\dots,g_n\).
(unlike the case in the previous section, where a characterization for all multilinear general polymorphisms was effectively obtained).

Thus, we start by generalizing <Ref> so that the subsequent definition of shifted generalized polymorphisms will be well-defined. Since we plan to only shift inputs in \(\Ztwo_0\), much of the argument goes through in the same way. In particular, we need to show that shifting the input doesn't invalidate the assumptions made in the preliminaries (except for balancedness, which we no longer assume):

Let \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\) be some set of real constants where \(\kappa_{ij} = 0\) if \(z_{ij}\not\in \Ztwo_0\). For every \(i\in [n]\), let \(\tilde{g}_i\) be defined as
\(\tilde{g}_i = g_i(x_1-\kappa_{i1},\dots, x_m-\kappa_{im})\), and for every \(j\in [m]\), let \(\tilde{f}_j\) be defined as \(\tilde{f}_j = f_j(y_1-\kappa_{1j},\dots,y_n - \kappa_{nj})\).

* \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\dots,\tilde{g}_n\) are boolean-like.

* For every \(i\in \rowstwo(Z_\ell)\) and \(j\in \colstwo(Z_\ell)\), the functions \(\tilde{g}_i\) and \(\tilde{f}_j\) have degree at least 2, and in particular,  \(\deptwo(g_i) = \deptwo(\tilde{g}_i)\) and \(\deptwo(f_j) = \deptwo(\tilde{f}_j)\) for every \(i\in [n]\) and \(j\in [m]\).

* \(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 decomposition into blocks (in the finer sense described in <Ref>) as
\(f_0,\dots, f_m,\allowbreak g_0,\dots,g_n\).

* For every \(z_{i_0j_0}\in \Ztwo_0\), every inclusion-maximal \(S^{i_0}\in \supp(\hat{f}_0)\) containing \(i_0\), and every inclusion-maximal \(\left\{ T_i \right\}_{i\in S^{i_0}}\) in the supports of \(\left\{ \hat{\tilde{g}}_i \right\}_{i\in S^{i_0} }\); the inclusion-maximal set \(V^{i_0}_{j_0} \in \supp(\hat{\tilde{f}}_{j_0})\) obtained from <Ref> satisfies:

\[
\hat{\tilde{f}}_{j_0}\left( V^{i_0}_{j_0} - i_0 \right) = \hat{f}_{j_0}\left(   V^{i_0}_{j_0} - i_0 \right) - \kappa_{i_0j_0}\hat{f}_{j_0}\left( V^{i_0}_{j_0} \right).
\]

Before proving this prop:general_shifted_reduction, let us take note of the following differences from <Ref>:

* The definition of \( \kappa_{ij} \) indicates that if either \(\deg(g_i) = 1\), or if \(\deg(g_i) \geq 2\)  and \(\deptwo(g_i) = \emptyset\), we get \(\tilde{g}_i \equiv g_i\) (and similarly for \(\tilde{f}_j\) functions).

* In <ref> we refer to <Ref>, which in essence allows us to apply <Ref> on \(f_0,\tilde{f}_1,\dots,\tilde{f}_m,g_0,\allowbreak \tilde{g}_1,\dots,\tilde{g}_n\) even if \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\allowbreak \dots,\tilde{g}_n\) are not necessarily balanced, as is the case here. This type of correspondence is common for several results in this paper that concern inclusion-maximal sets, and results for these sets being preserved under shifted translations (<Ref>) and under <Ref> (through its <Ref> and <Ref>).

* In <Ref>, the analog of the <Ref> in <Ref> required no proof when utilized in <Ref>; this is due to <Ref>. In the current setting, in which multiple inclusion-maximal sets are possible for any function with degree at least 2, this observation is not as trivial. Indeed, \(V^{i_0}_{j_0}\) may ostensibly be contained within multiple inclusion-maximal sets in \(\supp(\hat{f}_{j_0})\). Therefore, the expression for \(\hat{\tilde{f}}_{j_0}(V^{i_0}_{j_0} - i_0)\) could ostensibly depend on multiple super-sets, rather than just \(V^{i_0}_{j_0}\). The forthcoming proof's main concern is showing that this case cannot occur.

The proof of the first three items is almost identical to the one seen in <Ref>: since all \(\tilde{g}_i,\tilde{f}_j\), where \(i\in \rowstwo(Z_\ell),j\in \colstwo(Z_\ell)\) are shifted translations of $g_i,f_j$, <Ref> implies that their degree is also at least 2 — proving <ref> —  and <Ref> implies that they are 2-valued-like (recall that <Ref> and <Ref> do not require \(f_1,\dots,f_m,g_1,\dots,g_n  \) to be balanced), and therefore also Boolean-like (since the the Boolean-like property is equivalent to the 2-valued-like property for functions of degree at least \(2\)). The remaining \(i\in \rows(Z_\ell),j\in \cols(Z_\ell)\) are all in \(\rowsone(Z_\ell)\) and \(\colsone(Z_\ell)\), respectively, and for them \(\tilde{g}_i \equiv g_i\) and \(\tilde{f}_j \equiv f_j\) by definition, implying that they are Boolean-like since \(g_i,f_j\) are Boolean-like. Thus, every \(\tilde{g}_i,\tilde{f}_j\) is Boolean-like; implying <ref>.

The first part of <Ref> is trivial since the functions \(g_1,\dots,g_n,f_1,\dots,f_m\) are defined over \(z_{ij}\) variables, in which case the shift amounts to a change of variables on either side of <Ref>. The preservation of the decomposition into blocks (i.e. the second part of <Ref>) follows from <Ref>, and in particular the preservation of inclusion-maximal sets in the Fourier supports of the shifted functions (<Ref>), which implies preservation of \(\dep\)-sets of the shifted functions. Since the \(\dep\)-sets of the un-shifted functions are unaffected by the shift of other functions, \(Z_0\) is indeed preserved. The second item also implies that the shift also preserves whether a function has degree at least $2$ or not.

For <Ref>, it suffices to show that the only supersets of $V^{i_0}_{j_0} - i_0$ in the support of $\hat{f}_{j_0}$ are $V^{i_0}_{j_0}$ and possibly $V^{i_0}_{j_0} - i_0$. For the former, it follows immediately from <Ref> that \(V^{i_0}_{j_0}\in \supp(\hat{f}_{j_0})\). For the latter, suppose that $V \in \supp(\hat{f}_{j_0})$ is a superset of $V^{i_0}_{j_0} - i_0$, and let $V' \in \supp(\hat{f}_{j_0})$ be an inclusion-maximal set containing $V$. From <Ref> (which does not assume \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced), both $V^{i_0}_{j_0}$ and $V'$ contain $\deptwo(f_{j_0})$. Since $i_0 \in \deptwo(f_{j_0})$, this implies that $V' \supseteq (V^{i_0}_{j_0} - i_0) + i_0 = V^{i_0}_{j_0}$, and so $V' = V^{i_0}_{j_0}$ by inclusion-maximality of $V^{i_0}_{j_0}$. It follows that $V^{i_0}_{j_0} - i_0 \subseteq V \subseteq V^{i_0}_{j_0}$, as claimed.

With the preceding prop:general_shifted_reduction in mind, the subsequent section 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 are nonconstant; \(\tilde{f}_1,\dots,\tilde{f}_m,\tilde{g}_1,\dots,\tilde{g}_n\) are Boolean-like; and \(f_0,g_0\) 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 Boolean-like property by <Ref> and the other 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)\) and \(\deptwo(g_i) = \deptwo(\tilde{g}_i) = \deptwo(G_i)\) (from <ref>), we get \(\depone(g_i) = \depone(\tilde{g}_i) = \depone(G_i)\). To prevent ambiguity, we always denote the above sets as \(\dep(g_i), \deptwo(g_i), \depone(g_i)\).

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 Boolean-like (and not necessarily balanced); \(f_0,g_0\) depend on all of their inputs; and all functions are nonconstant; 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> and <Ref>) as its shifted generalized polymorphism, where \(F_1,\dots,F_m,G_1,\dots,G_n\) are Boolean-like and balanced, \(F_0,G_0\) depend on all their inputs, and \(G_0,\dots,G_n,F_0,\dots,F_m\) are nonconstant. 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, we translate these results back in terms of \(f_0,\dots,f_m,g_0,\dots,g_n\).

§.§.§ Characterizing Fj, Gi

In this section we present the (unique) construction of the shifted generalized polymorphism arising from \(f_0,\dots,f_m,g_0,\dots,g_n\), and characterize the obtained \(F_1,\dots,F_m,\allowbreak G_1,\dots, \allowbreak G_n\). As stated previously, we do not assume that \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced, only Boolean-like. As is the case with previous results, we assume that no function is constant and that \(f_0,g_0\) depend on all their inputs.

Even though we use similar methods to the ones seen in <Ref>, the characterization of \(F_j,G_i\) arising from them is quite different from the one obtained in <Ref>, wherein \(f_1, \dots, f_m,g_1,\dots, g_m\) are shown to be shifted monomials. In particular, as we now show, the inclusion of \(F_j,G_i\) with degree 1 adds a degree of freedom into the characterization of \(G_1, \dots, G_n,F_1, \dots, F_m \). This degree of freedom will manifest as a set of potentially arbitrary functions
\(\gamma_1,\dots,\gamma_n,\allowbreak \phi_1,\dots, \phi_m\), that are embedded inside some subset of the functions
\(G_1,\dots,G_n, \allowbreak F_1, \dots, F_m\). For now, we only show the existence of said functions, and when we characterize \(F_0\) and \(G_0\) in the next section, we prove that indeed these functions are not constrained in any way:

There exists a choice of \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\) that induce a shifted generalized polymorphism \(G_0,\dots,\allowbreak G_n,F_0,\dots,F_m\) from \(g_0,\dots,g_n,f_0,\dots,f_m\) by:

* Defining:

\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*}

* Obtaining \(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\]

(Making \(F_1,\dots,F_m,G_1,\dots,G_n\) balanced by definition.)

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

\begin{equation} \label{eq:gi_fj_general_characterization}
\begin{aligned}
G_i(y) &= \gamma_i(y|_{\depone(g_i)}) \cdot y_{\deptwo(g_i)} \text{ for some } \gamma_i\colon \{-1,1\}^{\depone(g_i)} \to \R, \\
F_j(x) &= \phi_j(x|_{\depone(f_j)}) \cdot x_{\deptwo(f_j)} \text{ for some } \phi_j\colon \{-1,1\}^{\depone(f_j)} \to \R.
\end{aligned}
\end{equation}

In particular, the shifted generalized polymorphism obtained is

\begin{align*}\label{eq:general_shifted_with_constants}
&F_0 \circ \left( \gamma_1\left( z_{1,\depone(g_1)}  \right) \cdot z_{1\deptwo(g_1)},\dots,\gamma_n\left( z_{n,\depone(g_n)} \right) \cdot z_{n\deptwo(g_n)} \right) =\\
&G_0 \circ \left( \phi_1\left( z_{\depone(f_1),1} \right) \cdot z_{\deptwo(f_1)1},\dots, \phi_m\left( z_{\depone(f_m),m}  \right) \cdot z_{\deptwo(f_m)} \right).
\end{align*}

* If $z_{ij} \notin Z_0^{\ge 2}$ then $\kappa_{ij} = 0$.

* If $\deg(g_i) = 1$ then $G_i = g_i$.

* If $\deg(f_j) = 1$ then $F_j = f_j$.

Observe that <Ref> indeed generalizes <Ref>: if all functions have degree at least 2 then all \(\depone(\cdot)\)-sets are empty, making all \(\gamma_i\) and \(\phi_j\) constant, and also \(\deptwo(g_i) = \dep(g_i)\) and \(\deptwo(f_j) = \dep(f_j)\) for every \(i\in [n]\) and \(j\in [m]\).

As is the case in <Ref>, we first show the result for all \(G_i\), and then use this characterization in a similar way in order to characterize the \(F_j\). To get the characterization for the \(G_i\), we first need to construct \(\tilde{g}_i\), which we do using <Ref> of <Ref>.
In order to invoke the latter, for every \(i_0\in [n]\) we need to fix some inclusion-maximal sets \(S^{i_0}\in \supp(\hat{f}_0)\) containing \(i_0\) and \(\left\{ T_i \right\}_{i\in S^{i_0}}\) in the supports of \(\left\{ \tilde{g}_i \right\}_{i\in S^{i_0}}\) to use it on. Evidently, it suffices to fix an arbitrary set of inclusion-maximal sets \(\left\{ T_i \right\}_{i\in [n]}\) from the Fourier supports of \(\left\{ \tilde{g}_i \right\}_{i\in [n]}\) and \(\left\{ S^i \mid i\in S^i \right\}_{i\in [n]}\) from the Fourier support of \(\hat{f}_0\) to be used in all applications of <Ref> in <Ref>.

For every \(i\in [n]\), fix some arbitrary inclusion-maximal set \(T_i\in \supp(\hat{g}_i)\), and some arbitrary inclusion-maximal set \(S^i \in \supp(\hat{f}_0)\) containing \(i\) (using <Ref>). Moreover, denote by \(T^i, \left\{ V^i_j \right\}_{j\in T^i}\) the inclusion-maximal sets (in the Fourier supports of \(g_0,\left\{ f_j \right\}_{j\in T^i}\), respectively) obtained by applying <Ref> over \(f_0,\dots,f_m,g_0,\dots,g_n\) and \(S^i,\left\{ T_{i'} \right\}_{i'\in S^i}\) (note that <Ref> does not assume \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced).

If $z_{ij} \notin \Ztwo_0$ we define $\kappa_{ij} = 0$.
If $z_{ij} \in \Ztwo_0$, then $j \in \deptwo(g_i)$, and so $j \in T_i$ by <Ref> (which also does not assume \(f_1,\dots,f_m,g_1,\dots,g_n\) are balanced). Consequently, $T^i = \bigcup_{i' \in S^i} T_{i'} \supseteq T_i$ contains $j$, and so $V_j^i$ is defined and belongs to $\supp(\hat{f}_j)$. We define $\kappa_{ij} = \hat{f}_j(V_j^i - i)/\hat{f}_j(V_j^i)$. Applying <Ref> with respect to the above \(\left\{ \kappa_{ij} \right\}_{z_{ij}\in Z_0}\), we obtain a generalized polymorphism \(f_0,\tilde{f}_1,\dots, \tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\). From <Ref>, all sets \(T_i,V_{j}^i\) defined above are also inclusion-maximal in the Fourier supports of \(\tilde{g}_i,\tilde{f}_j\), respectively.

For every \(z_{ij}\in \Ztwo_0\), we apply <Ref>, <ref> over \(S^{i_0}, \left\{ T_i \right\}_{i\in S^{i_0}}\) and deduce that

\begin{equation} \label{eq:deptwo_is_shifted_monomial}
\hat{\tilde{f}}_j(V^i_j - i) = \hat{f}_j(V^i_j - i) - \kappa_{ij} \hat{f}_j(V^i_j) = 0.
\end{equation}

Next, apply <Ref> over \(f_0,\tilde{f}_1,\dots, \tilde{f}_m,g_0,\tilde{g}_1,\dots,\tilde{g}_n\) and obtain the shifted generalized polymorphism \(F_0,\dots,F_m,G_0,\dots,G_n\) (in particular, \(F_1,\dots,F_m,G_1,\dots,G_n\) are balanced).

The combination of <Ref> and <ref>, <ref> in <Ref>  implies (by transitivity) that $\deg(G_i) = \deg(g_i)$ and $\deg(F_j) = \deg(f_j)$; that $G_i,g_i$ and $F_j,f_j$ depend on the same variables; and that a set is inclusion-maximal in $\supp(\hat{G}_i)$ iff it is inclusion-maximal in $\supp(\hat{g}_i)$ (and similarly for $F_j,f_j$). We use this freely below.

Let \(i_0\in [n]\). If \(\deg(G_{i_0}) = 1\) then also $\deg(g_{i_0}) = 1$. Since \(g_{i_0}\) is Boolean-like, it has the form \(g_{i_0} = \pm y_j\) for some \(j\in [m]\). Since $\deg(g_{i_0}) = 1$ we have $z_{i_0j} \notin \Ztwo_0$ and so $\kappa_{i_0j} = 0$, implying that $\tilde{g}_{i_0} = g_{i_0}$. Since $\E[g_{i_0}] = 0$, it follows that $G_{i_0} = g_{i_0}$.

We need to show that for some function $\gamma_{i_0}$,

\[
g_{i_0}(y) = \gamma_{i_0}(y|_{\depone(g_i)}) \cdot y_{\deptwo(g_i)}.
\]

There are two cases. If $\deg(f_j) \geq 2$ then \(\deptwo(g_{i_0}) = \left\{ j \right\}\) and \(\depone(g_{i_0}) = \emptyset\), and so the right-hand side reads $\gamma_{i_0}(\emptyset) \cdot y_j$. Hence we can set $\gamma_{i_0}(\emptyset)$ to be either $-1$ or $+1$ in order to satisfy the equation. Conversely, if \(\deg(f_j) = 1\), then \(\deptwo(g_{i_0}) = \emptyset\) and \(\depone(g_{i_0}) = \left\{ j \right\}\), therefore the right-hand side reads $\gamma_{i_0}(y_j) \cdot 1$. Again we can set $\gamma_{i_0}$ to satisfy the equation.

Suppose now that \(\deg(G_{i_0}) \geq 2\). We start the characterization of $G_{i_0}$ by showing that every set in \( \supp(\hat{G}_{i_0})\) contains \(\deptwo(G_{i_0})\), using the same type of argument seen in <Ref>. Suppose that there exists \(T_{i_0}' \in \supp(\hat{G}_{i_0}) \) such that \( \deptwo(G_{i_0}) \not\subseteq T_{i_0}'\). Since the inclusion-maximal \(T_{i_0}\) does contain \(\deptwo(\hat{G}_{i_0})\) (through <Ref>), there exists some \(j_0\in \left( \deptwo(G_{i_0}) \cap T_{i_0} \right) \setminus T_{i_0}'\). Since \(j_0\in T_{i_0}\), it is also in \(T^{i_0} = \bigcup_{i\in S^{i_0}} T_i\), and in particular \(V^{i_0}_{j_0}\) is an inclusion-maximal set in \(\supp(\hat{F}_{j_0})\) of size \(|V^{i_0}_{j_0}| \geq 2\) (since it is an inclusion-maximal set in $\supp(\hat{f}_{j_0})$, and $f_{j_0}$ has degree at least $2$ and is 2-valued-like).
Thus, there exists some $i_1 \in V^{i_0}_{j_0} - i_0$. Since $S^{i_0} = \bigcup_{j \in T^{i_0}} V^{i_0}_j$, also $i_1 \in S^{i_0}$. Since $F_{j_0}$ depends on $i_1$, by <Ref> we know that $G_{i_1}$ depends on $j_0$. Since $\deg(F_{j_0})  \geq 2$ (as follows from \(j_0\in \deptwo(G_{i_0})\)), in fact $j_0 \in \deptwo(G_{i_1})$, and so $j_0 \in T_{i_1}$ by <Ref>.

An application of <Ref>, with respect to $F_0,F_1,\ldots,F_m,G_0,G_1,\ldots,G_n$ and over the sets \(S^{i_0}, T_{i_0}',\allowbreak \left\{ T_i \right\}_{i\in S^{i_0}-i_0}\), shows that the set

\[
V_{j_0}' = \begin{cases}
\left\{ i\in S^{i_0} - i_0 \mid j_0\in T_{i} \right\} \cup \left\{ i_0 \right\},& \textnormal{ if } j_0\in T_{i_0}', \\
\left\{ i\in S^{i_0} - i_0 \mid j_0\in T_{i} \right\},& \textnormal{otherwise}
\end{cases}
\]

is in the support of \(\hat{F}_{j_0}\) (using $j_0 \in T_{i_1}$ and $i_1 \in S^{i_0} - i_0$).
Since \(j_0\not\in T_{i_0}'\) by assumption, we have \(V_{j_0}' = \left\{ i\in S^{i_0} - i_0 \mid j_0\in T_i \right\}\). Since \(V^{i_0}_{j_0} = \left\{ i\in S^{i_0} \mid j_0\in T_i \right\}\) by definition, we see that $V_{j_0}' = V^{i_0}_{j_0} - i_0$. However, this contradicts <Ref>, which showed that $V^{i_0}_{j_0} - i_0 \notin \supp(\hat{F}_{j_0})$.

Therefore, all sets in the support of \(\hat{G}_{i_0}\) include \(\deptwo(g_{i_0})\), that is, the Fourier expansion (<Ref>) of \(G_{i_0}\) is:

\[
G_{i_0}(y_1,\dots,y_m) = \sum_{\tau_i \subseteq \depone(g_i)} \hat{G}(\deptwo(g_i) \cup \tau_i) y_{\deptwo(g_i) \cup \tau_i}.
\]

If we define

\[
\gamma_{i_0} = \sum_{\tau_i \subseteq \depone(g_i)} \hat{G}(\deptwo(g_i) \cup \tau_i) y_{\tau_i}
\]

then we get $G_{i_0}(y) = \gamma_{i_0}(\depone(g_i)) \cdot y_{\deptwo(g_i)}$.

The characterization of the \(F_j\) follows from that of the \(G_i\), using a very similar argument. Let \(j_0\in [m]\). If \(\deg(F_{j_0}) = 1\) then the argument is exactly the same as above, so suppose that \(\deg(F_{j_0}) \geq 2\), and suppose for the sake of contradiction that there exists some \(V_{j_0}' \in \supp(\hat{F}_{j_0})\) that does not contain \(\deptwo(F_{j_0})\).  Thus, there exists some \(i_0\in \deptwo(F_{j_0}) \setminus V_{j_0}'\).

Since $F_{j_0}$ depends on $i_0$, according to <Ref>, the function $G_{i_0}$ depends on $j_0$, and so $j_0 \in \deptwo(G_{i_0})$ (since \(\deg(F_{j_0}) \geq 2\) by assumption). <Ref> then implies that $j_0 \in T_{i_0}$. Since $T^{i_0} = \bigcup_{i \in S^{i_0}} T_i \supseteq T_{i_0}$, also $j_0 \in T^{i_0}$.

Since $i_0 \in \deptwo(F_{j_0})$ (by assumption), we have $\deg(G_{i_0}) \geq 2$. Since $G_{i_0}$ is 2-valued-like, we have $|T_{i_0}| \geq 2$, and so we can pick $j_1 \in T_{i_0} - j_0 \subseteq T^{i_0} - j_0$. Therefore, since $V^{i_0}_{j_1} = \{i \in S^{i_0} : j_1 \in T_i\}$ and $i_0 \in S^{i_0}$ (both by construction), it follows that $i_0 \in V^{i_0}_{j_1}$.

Applying <Ref> with respect to $F_0,F_1,\ldots,F_m,G_0,G_1,\ldots,G_n$ and over \(T^{i_0},\allowbreak V_{j_0}', \left\{ V^{i_0}_{j} \right\}_{j\in T^{i_0} - j_0}\), we get that the set

\[
T_{i_0}' = \begin{cases}
\left\{ j\in T^{i_0} - j_0 \mid i_0\in V^{i_0}_j  \right\} + j_0,& \textnormal{if } i_0\in V_{j_0}', \\
\left\{ j\in T^{i_0} - j_0 \mid i_0\in V^{i_0}_j  \right\},& \textnormal{otherwise}
\end{cases}
\]

is in \(\supp(\hat{G}_{i_0})\) (using $i_0 \in V^{i_0}_{j_1}$ and $j_1 \in T^{i_0} - j_0$). Since \(i_0\not\in V_{j_0}'\) by construction, we get that $j_0 \notin T_{i_0}'$, contradicting the characterization of $G_{i_0}$, which shows that all sets in $\supp(\hat{G}_{i_0})$ contain $\deptwo(G_{i_0})$ (and in particular $j_0$).

As in the characterization of the $G_i$, we can define a function $\phi_{j_0}$ so that $F_{j_0}(x) = \phi_j(\depone(f_{j_0})) \cdot y_{\deptwo(f_{j_0})}$.

§.§.§ Characterizing F0, G0

The proof of this section is also quite similar to the one seen in <Ref>, the major difference being that \(F_0,G_0\) now have to take \(\gamma_1,\dots,\gamma_n,\phi_1,\dots\phi_m\) into account, which henceforth will always refer to the \(\gamma_1,\dots,\gamma_n,\phi,\dots,\phi_m\) obtained from <Ref>. As stated in the previous section, in this section we are given the shifted generalized polymorphism \(F_0,\dots,F_m,G_0,\dots,G_n\) constructed in the previous section, so in particular, \(F_1,\dots,F_m,G_1,\dots,G_n\) are balanced and Boolean-like, \(F_0,G_0\) depend on all their inputs, and no function is constant. In the main theorem, we use the characterization obtained for the shifted generalized polymorphism to obtain one for \(f_0,\dots,f_m,g_0,\dots,g_n\)

The characterization of \(F_0,G_0\) will contain a function \(h\) that will play the same part that \(h\) did in <Ref>. However, each of its \(k\) coordinates will now contain a slightly more complex function than the product of inputs that appears in <Ref>.

We start by finding \(h\) in much the same way as in <Ref>, that is, by first strengthening <Ref> to hold for all sets in the supports of \(\hat{F}_0,\hat{G}_0\), rather than just inclusion-maximal ones; this lem:all_S_T_contain_rowstwo_colstwo generalizes <Ref>:

Suppose that \(F_0,F_1,\dots,F_m,G_0,G_1,\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 \(\rowstwo(Z_\ell)\), and every set \(T\in \supp(\hat{G}_0)\) that intersects \(\cols(Z_\ell)\) contains \(\colstwo(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)\) be such that \(S\cap \rows(Z_\ell) \neq \emptyset\). Suppose for the sake of contradiction that $\rowstwo(Z_\ell) \not\subseteq S$.
An invocation of <Ref> with \(I = S\cap\rows(Z_\ell)\) implies that there exist some \(i_1\in \rowstwo(Z_\ell) \setminus S\), \(i_0\in I\), and \(w\in [m]\) such that \(w\in \dep\left( G_{i_0} \right)\cap \dep \left( G_{i_1} \right)\).

For each $i \in S - i_0$, choose an arbitrary inclusion-maximal set $T_i$ in the support of $\hat{G}_i$. Let $T_{i_0}$ be an arbitrary inclusion-maximal set in the support of $\hat{G}_{i_0}$ which contains $w$.

An application of <Ref> over \(S, \left\{ T_i \right\}_{i\in S}\) (recall that \(F_1,\dots,F_m,G_1,\dots,G_n\) are balanced, by construction) implies that \(V_w = \left\{ i\in S \mid w\in T_i \right\}\) is in the support of \(\hat{F}_w\), where \(i_1\not\in V_w\) since \(i_1\not\in S\). Moreover, from <Ref> it follows that every set in the support of \(\hat{F}_w\) contains \( \deptwo(f_w)\), so in particular \(\deptwo(f_w) \subseteq V_w\).

However, since \(i_1\in \rowstwo(Z_\ell)\), we get \(\deg(G_{i_1}) \geq 2\), therefore \(i_1\in \deptwo(F_w)\); and from <ref> in <Ref> we get that \(\deptwo(F_w) = \deptwo(f_w)\). In particular, we get \(i_1\in \deptwo(f_w) \subseteq V_w\), in contradiction to \(i_1\not\in V_w\).

Intuitively, the remainder of the argument in this section will vaguely resemble that of <Ref>: we show that inputs to \(f_0,g_0\) that refer to \(g_i,f_j\) of degree \(1\) (so are part of some \(\rowsone(Z_\ell)\) set) are treated differently from those with degree at least 2 (which are included in some \(\rowstwo(Z_\ell)\) set). Before we formalize this intuition, at this point we address a potential degeneracy in the partition of \(Z_0\) which we refer to in our argument; this degeneracy occurs when the partition of \(Z_0\) contains \(Z_\ell\) sets of size \(1\):

Let \(\ell\in [k]\), and let \(z_{ij}\in Z_\ell\). Then \(Z_\ell\) is the singleton \(Z_\ell = \left\{ z_{ij} \right\}\) if and only if \(i\in \rowsone(Z_\ell)\) and \(j\in \colsone(Z_\ell)\).

In other words, if \(Z_\ell\) is not a singleton, then every \(z_{ij}\) it contains must satisfy either \(\deg(g_i) \geq 2\) or \(\deg(f_j) \geq 2\) (or both).

In one direction, suppose without loss of generality that \(i\in \rowstwo(Z_\ell)\). Then there is some \(j'\in \dep(g_i) - j\), so by definition of \(Z_\ell\) we have \(z_{ij'}\in Z_\ell\), therefore \(|Z_\ell| \geq 2\) (so in particular \(Z_\ell\) is not a singleton).

For the other direction, suppose that \(|Z_\ell| \geq 2\); we show that either \(i\in \rowstwo(Z_\ell)\), or \(j\in \colstwo(Z_\ell)\), or both.

Since \(z_{ij} \in Z_\ell\) and \(Z_\ell\) is not the singleton \(\left\{ z_{ij} \right\}\), there exists some \(z_{i'j'}\in Z_\ell - z_{ij}\). Suppose without loss of generality that \(i'\neq i\) (a symmetric argument holds when we assume \(j'\neq j\)). Then \(I = \left\{ i \right\} \subsetneq \rows(Z_\ell)\) (since \(\left\{ i,i' \right\} \subseteq \rows(Z_\ell)\)), so by applying <Ref> on \(I\) we get that there is some \(i''\in \rows(Z_\ell) - i\) such that \(g_i\) and \(g_{i''}\) depend on the same coordinate \(w\in [m]\). By definition of \(Z_\ell\), this implies that \(z_{iw},z_{i''w} \in Z_\ell\). From <Ref>, it follows that \(i,i''\in \dep(f_w)\), and since \(f_w\) is 2-valued-like, it follows that that \(\deg(f_w) \geq 2\), so in particular \(w\in \colstwo(Z_\ell)\). If it so happens that \(j=w\), then we're done. Otherwise, \(j,w\in \dep(g_i)\), and since \(g_i\) is 2-valued-like, it follows that \(\deg(g_i) \geq 2\), and so \(i\in \rowstwo(Z_\ell)\).

Given that singleton \(Z_\ell\) sets require special care in the subsequent argument, we use the following notation to differentiate between them and the rest of the \(Z_\ell\) sets; we do so with respect to an index set \(K\subseteq [k]\) of some set \(\left\{ Z_\ell \right\}_{\ell\in K}\) for technical reasons elucidated in the subsequent lem:F0_G0_exist_Phi_Gamma.

Let \(K\subseteq [k]\). Then:

* Define \(\Kone \subseteq K\) as the set of all \(\ell\in K\) corresponding to singleton \(Z_\ell\) sets, that is:

\begin{align*}
\Kone &= \left\{ \ell\in K \mid |Z_\ell| = 1 \right\} \\
&= \left\{ \ell\in K \mid \exists z_{ij} \in Z_0 \text{ such that } Z_\ell = \left\{ z_{ij} \right\}\right\} \\
&= \left\{\ell\in K \mid \exists z_{ij}\in Z_0 \text{ such that } \rowsone(Z_\ell) = \left\{ i \right\} \text{ and } \colsone(Z_\ell) = \left\{ j \right\} \right\}
\end{align*}

* Define \(\Kneqone \subseteq K\) as the complement of \(\Kone\) inside \(K\), that is, all \(\ell\in K\) corresponding to non-singleton \(Z_\ell\) sets:

\begin{align*}
\Kneqone &= K \setminus \Kone \\
&= \left\{ \ell\in K \mid |Z_\ell| \geq 2\right\} \\
&= \left\{ \ell\in K \mid  \text{either }\rowstwo(Z_\ell) \neq \emptyset \text{ or } \colstwo(Z_\ell) \neq \emptyset  \text{ (or both)}\right\}.
\end{align*}

The third equality for each item follows from <Ref>.

By Combining <Ref> and the definitions above, we can group the terms of the Fourier expansions of \(f_0\) and \(g_0\) by the \(Z_\ell\) sets they intersect with. For any subset \(K\subseteq [k]\), we use the shorthand \(Z_K\) to denote the (disjoint) union of \(Z_\ell\) components indexed by \(K\), that is \(Z_K = \bigsqcup_{\ell\in K} Z_\ell \). Note that this definition also works for the sets in <Ref>, namely for every \(K\subseteq [k]\) we have \(Z_{\Kone} = \bigsqcup_{\ell\in \Kone} Z_\ell\) and \(Z_{\Kneqone} = \bigsqcup_{\ell\in \Kneqone} Z_\ell\). We also use the notation \(\pi(S) \subseteq [k]\) for every \(S\subseteq [n]\), to denote the set of all \(Z_\ell\) sets whose \(\rows(Z_\ell)\)-set \(S\) intersects; that is, for every \(\ell\in \pi(S)\) we have \(S\cap \rows(Z_\ell) \neq \emptyset\), and for every \(\ell \in [k] \setminus \pi(S)\) we have \(S \cap \rows(Z_\ell) = \emptyset\).

There are functions \(\left\{ \Phi^K \right\}_{K\subseteq [k]}\) and \(\left\{ \Gamma^K \right\}_{K\subseteq [k]}\), where for every \(K \subseteq [k]\) we have \(\Phi^K\colon \left\{ -1,1 \right\}^{\rowsone(Z_{\Kneqone})} \to \R\) and \(\Gamma^{K} \colon \left\{ -1,1 \right\}^{\colsone(Z_{\Kneqone})} \to \R\), such that

\[
F_0(x_1,\dots,x_n) =  \sum_{K\subseteq [k]} x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot  \Phi^K\left(  x|_{\rowsone(Z_{\Kneqone})} \right)
\]

\[
G_0(y_1,\dots,y_m) =  \sum_{K\subseteq [k]} y_{\colsone(Z_{\Kone})} \cdot y_{\colstwo(Z_{\Kneqone})}  \cdot \Gamma^K\left(  y|_{\colsone(Z_{\Kneqone})} \right).
\]

Note that \(\rowsone(Z_{\Kone})\) and \(\colsone(Z_{\Kone})\) could have also been written more generally as \(\rows(Z_{\Kone})\) and \(\cols(Z_{\Kone})\), since \(\emptyset = \rowstwo(Z_{\Kone}) = \colstwo(Z_{\Kone})\). We refrain from using this more general notation for the sake of readability.

We show the result for \(F_0\); the result for \(G_0\) and the definitions of \(\{\Gamma^K\}_{K\subseteq [k]}\) are done analogously. Considering \(F_0\)'s Fourier expansion, \(F_0 = \sum_{S\subseteq [n]} \hat{F}_0(S)x_S\), we may group the terms in the sum by their intersections with the (disjoint) \(\rows(Z_\ell)\) sets:

\[
F_0 = \sum_{S\subseteq [n]} \hat{F}_0(S) \cdot x_S = \sum_{K\subseteq [k]} \sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0(S) \cdot x_S.
\]

(In other words, we apply the partition of \(\rows(Z_0)\) into \(\left\{ \rows(Z_\ell) \right\}_{\ell\in [k]}\) onto every \(S\subseteq [n]\) and associate every \(S\) with the index-set \(K\) of exactly all \(\rows(Z_\ell)\)-sets it intersects.)

Decomposing this further by considering \(K = \Kone \sqcup \Kneqone\) and using distributivity:

\begin{align*}
F_0 &= \sum_{K\subseteq [k]} \sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0(S) \cdot x_S \\
&=\sum_{K\subseteq [k]} \sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0\left( \left( S\cap \rows\left( Z_{\Kone} \right) \right) \sqcup \left( S\cap \rows\left( Z_{\Kneqone} \right) \right) \right) \cdot \\
&\phantom{\sum_{K\subseteq [k]} \sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0~}\cdot x_{ \left( S\cap \rows\left(  Z_{\Kone}\right) \right)\sqcup \left( S\cap \rows\left( Z_{\Kneqone} \right) \right)} \\
&= \sum_{K\subseteq [k]} \sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0\left( \rows\left( Z_{\Kone} \right) \sqcup \left( S\cap \rows\left( Z_{\Kneqone} \right) \right) \right) \cdot x_{  \rows\left( Z_{\Kone} \right) \sqcup \left( S\cap \rows\left(  Z_{\Kneqone}\right) \right)} \\
&= \sum_{K\subseteq [k]} x_{\rows\left( Z_{\Kone} \right)}\sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0\left( \rows\left( Z_{\Kone} \right) \sqcup \left( S\cap \rows\left( Z_{\Kneqone} \right) \right) \right) \cdot x_{S\cap \rows(Z_{\Kneqone})} \\
&= \sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)}\sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0\left(  \rowsone\left( Z_{\Kone} \right) \sqcup \left( S\cap \rows\left( Z_{\Kneqone} \right) \right) \right) \cdot x_{S\cap \rows(Z_{\Kneqone})}
\end{align*}

where the third equality is due to the assumption that \(S\) intersects \(\rows(Z_\ell)\) for every \(\ell\in \Kone\subseteq K\) and given that for every \(\ell\in \Kone\), the set \(\rows(Z_\ell)\) is a singleton by definition; the fourth equality uses distributivity; and the fifth equality applies the identity \(\rows\left( Z_{\Kone} \right) = \rowsone\left( Z_{\Kone} \right)\), which holds since this set is a singleton.

Turning our attention to the expressions \(S\cap \rows(Z_{\Kneqone})\): we apply the decomposition in <Ref> to get

\[
S\cap\rows(Z_{\Kneqone}) = \left( S\cap\rowstwo(Z_{\Kneqone}) \right) \sqcup  \left( S\cap\rowsone(Z_{\Kneqone}) \right),
\]

and from <Ref>, we may decompose \(S\cap\rowstwo(Z_{\Kneqone})\) further into:

\begin{equation}\label{eq:S_intersect_rowstwo}
\begin{aligned}
S\cap\rowstwo(Z_{\Kneqone}) &= S\cap\rowstwo\left( \bigsqcup_{\ell \in \Kneqone} Z_\ell \right)=  \bigsqcup_{\ell\in \Kneqone} (S\cap\rowstwo(Z_{\ell})) \\
&= \bigsqcup_{\ell\in \Kneqone} \rowstwo(Z_{\ell}) = \rowstwo\left( \bigsqcup_{\ell \in \Kneqone} Z_\ell \right)  =\rowstwo(Z_{\Kneqone}),
\end{aligned}
\end{equation}

where the first equality follows by definition of \(Z_{\Kneqone}\); the second by the disjointedness of the \(Z_\ell\) sets; the third from <Ref> and since \(S\) intersects \(\rows(Z_\ell) \) for every \(\ell\in \Kneqone \subseteq K\) by construction; and the last two equalities again by disjointedness and definition of \(Z_{\Kneqone}\).

Substituting this into the Fourier expansion above, we get:

\begin{align*}
&F_0 = \\
&\sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)}\sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0\left( \rowsone\left( Z_{\Kone}  \right) \sqcup \rowstwo(Z_{\Kneqone}) \sqcup \left( S\cap \rowsone\left( Z_{\Kneqone} \right) \right) \right) \cdot \\
&\phantom{\sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)}\sum_{\substack{S\subseteq [n]: \\  \pi(S) = K}}\hat{F}_0} \cdot x_{\rowstwo\left( Z_{\Kneqone} \right)} \cdot x_{S\cap \rowsone(Z_{\Kneqone})} = \\
&= \sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)} \cdot x_{\rowstwo\left( Z_{\Kneqone} \right)} \cdot \\
&\phantom{\sum_{K\subseteq [k]}~~~}\cdot \sum_{\substack{S\subseteq [n]: \\ \pi(S) = K}}\hat{F}_0\left(  \rowsone\left( Z_{\Kone}  \right) \sqcup \rowstwo(Z_{\Kneqone}) \sqcup \left( S\cap \rowsone\left( Z_{\Kneqone} \right) \right) \right) \cdot \\
&\phantom{\sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)}} \cdot  x_{S\cap \rowsone(Z_{\Kneqone})}.
\end{align*}

If $\pi(S) = K$ then $S$ contains both $\rowsone(Z_{\Kone})$ and $\rowstwo(Z_{\Kneqone})$. Therefore the set $S$ is completely specified by $K$ and by \(S'\coloneqq S\cap \rowsone\left( \Kneqone \right) \subseteq\rowsone\left( \Kneqone \right) \). Therefore

\begin{align*}
&F_0 = \sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)} \cdot x_{\rowstwo\left( Z_{\Kneqone} \right)} \cdot \\
&\phantom{F_0 = \sum_{K\subseteq [k]} }\cdot \sum_{S' \subseteq \rowsone\left( \Kneqone \right)} \hat{F}_0\left(  \rowsone\left( Z_{\Kone}  \right) \sqcup \rowstwo(Z_{\Kneqone}) \sqcup  S'\right) \cdot x_{S'}.
\end{align*}

For every \(K\), we use the uniqueness of the Fourier expansion to define the function \(\Phi^K \colon \left\{ -1,1 \right\}^{\rowsone(\Kneqone)} \allowbreak\to \R\) whose Fourier coefficients are

\begin{align*}
\hat{\Phi}^K(S') \coloneqq \hat{F}_0\left(  \rowsone\left( Z_{\Kone}  \right) \sqcup \rowstwo(Z_{\Kneqone}) \sqcup S' \right), & \text{ for every } S'\subseteq \rowsone\left( \Kneqone  \right).
\end{align*}

Substituting this into the Fourier expansion of \(F_0\) above, we get:

\begin{align*}
F_0 &= \sum_{K\subseteq [k]} x_{\rowsone\left( Z_{\Kone} \right)} \cdot x_{\rowstwo\left( Z_{\Kneqone} \right)} \cdot \Phi^K\left( x|_{\rowsone\left( Z_{\Kneqone} \right)} \right).\qedhere
\end{align*}

The previous lem:F0_G0_exist_Phi_Gamma shows that the Fourier supports of both \(F_0\) and \(G_0\) depend on the sets \(\left\{ Z_\ell \right\}_{\ell\in [k]}\). In order to obtain a result that generalizes <Ref>, we need to find some function \(h\), defined over \(k\) inputs, which will be used in the expressions defining both \(F_0\) and \(G_0\). In order to do that, we need to find some way of equating these functions with each other. We do this by first substituting the inputs of \(F_0\) with \(G_1,\dots,G_n\) and the inputs of \(G_0\) with \(F_1,\dots,F_m\), from which we get:

\begin{align*}
&F_0 \circ (G_1,\dots,G_n) = \\
&\sum_{K\subseteq [k]} \left( \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i \right) \cdot \left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} G_i \right) \cdot \Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right)
\end{align*}

\begin{align*}
&G_0 \circ (F_1,\dots,F_m) =\\
&\sum_{K\subseteq [k]} \left( \prod_{j\in \colsone(Z_{\Kone})}F_j \right) \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} F_j \right)  \cdot \Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right).
\end{align*}

Considering the assumption \(F_0 \circ (G_1,\dots,G_n) = G_0 \circ (F_1,\dots,F_m)\), this becomes:

\begin{align*}
&\sum_{K\subseteq [k]} \left( \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i \right) \cdot \left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} G_i \right) \cdot \Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) = \\
&\sum_{K\subseteq [k]} \left( \prod_{j\in \colsone(Z_{\Kone})}F_j \right) \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} F_j \right)  \cdot \Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right).
\end{align*}

Next, we substitute all \(G_i\) and \(F_j\) of degree at least 2 with the expressions we got from <Ref> (degree 1 functions are left as they are for now, for notational simplicity), and get

\begin{equation}\label{eq:F0_G0_with_substitutions}
\begin{aligned}
&\sum_{K\subseteq [k]} \left( \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i \right) \cdot \left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \gamma_i\left( z|_{i,\depone(g_i)} \right) \cdot z_{i\deptwo(g_i)} \right) \cdot\\
&\phantom{\sum_{K\subseteq [k]}} \cdot \Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) = \\
&\sum_{K\subseteq [k]} \left( \prod_{j\in \colsone(Z_{\Kone})}F_j \right) \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(z|_{\depone(f_j),j}) \cdot z_{\deptwo(f_j)j} \right)  \cdot \\
&\phantom{\sum_{K\subseteq [k]}}\cdot\Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right).
\end{aligned}
\end{equation}

Much of the remaining argument for this section will be to factor out the commonalities between each side of <Ref>, showing the relationships between the remaining terms. In order to factor out commonalities in this way, we first show that the equality in <Ref> implies term-wise equality. That is, for every \(K\subseteq [k]\), the term induced by \(K\) on the LHS of <Ref> equals the term induced by \(K\) on the RHS of <Ref>:

Let \(K\subseteq [k]\). Then,

\begin{equation}\label{eq:termwise-equality}
\begin{aligned}
& \left( \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i \right) \cdot \left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \gamma_i\left( z|_{i,\depone(g_i)} \right) \cdot z_{i\deptwo(g_i)} \right) \cdot\\
&\phantom{\left( \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i \right)}\cdot\Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) = \\
&\left( \prod_{j\in \colsone(Z_{\Kone})}F_j \right) \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(z|_{\depone(f_j),j}) \cdot z_{\deptwo(f_j)j} \right)  \cdot \\
&\phantom{\left( \prod_{j\in \colsone(Z_{\Kone})}F_j \right)}\cdot\Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right).
\end{aligned}
\end{equation}

Let $S$ be a set in the support of the Fourier expansion of the LHS. We claim that $\pi(S) = K$. Clearly $\pi(S) \subseteq K$ by construction. Conversely, suppose that $\ell \in K$, and choose an arbitrary $i \in \rows(Z_\ell)$. Since $G_i$ is not constant, $S$ must contain $z_{ij}$ for some $j \in \cols(Z_\ell)$. This shows that $\pi(S) = K$. Similarly, $\pi(S) = K$ for any set in the support of the Fourier expansion of the RHS.

If we sum the parts of the Fourier expansion of the LHS of <Ref> supported by sets $S$ such that $\pi(S) = K$, then we get the LHS in the statement of the lemma. Similarly, if we sum the parts of the Fourier expansion of the RHS of <Ref> supported by sets $S$ such that $\pi(S) = K$, then we get the RHS in the statement of the lemma. Since both sides of <Ref> are equal, it follows that the LHS and the RHS in the statement of the lemma are also equal.

The next result will use the notation \(\sgn(G_i) \in \left\{ -1,1 \right\}\) (and similarly \(\sgn(F_j)\in \left\{ -1,1 \right\}\)) to denote the sign of a function whose form is \(G_i = \pm y_j\) for some \(j\in [m]\), in which case \(G_i = \sgn(G_i) \cdot y_j\). By definition of the Boolean-like property, the sign of a function is always defined for Boolean-like functions of degree 1. Furthermore, since Boolean-like functions of degree 1 have the form \(f(x) = \sgn(f) x_i\), we may refer to an unsigned \(f\) using the notation \(|f| = |\sgn(f)| x_i = x_i \).

<Ref> can be further simplified by factoring out the following factors, where in particular, the second item below generalizes <Ref>:

Let \(K\subseteq [k]\). Then there exists some \(s_K\in \left\{ -1,1 \right\}\) (that depends only on \(K\)) such that

* \(  \prod_{i\in \rowsone\left( Z_{\Kone} \right)}G_i = s_K \cdot \prod_{j\in \colsone(Z_{\Kone})}F_j  \),

* \(\prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} z_{i\deptwo(g_i)}=\prod_{j\in \colstwo(Z_{\Kneqone})}  z_{\deptwo(f_j)j}\).

* By definition of \(\Kone\), for every \(\ell\in Z_{\Kone}\) there exists some \(z_{ij}\in Z_0\) such that \(Z_\ell = \left\{ z_{ij} \right\}\). It follows that \(G_i,F_j\) are both dictators, and since they are Boolean-like, equal \(G_i = \sgn(G_i) z_{ij}\) and \(F_j = \sgn(F_j) z_{ij}\), respectively. Thus, every \(\ell\in Z_{\Kone}\) contributes the same \(z_{ij}\) to both sides, up to a sign. In particular, the item follows by taking

\[s_K = \left(  \prod_{i\in \rowsone\left( Z_{\Kone} \right)} \sgn(G_i)  \right) \cdot \left(  \prod_{j\in \colsone(Z_{\Kone})} \sgn(F_j)  \right).\]

* Let \(z_{ij}\) be one of the literals appearing on the LHS. Then there is some \(\ell \in \Kneqone\) such that \(i\in \rowstwo(Z_\ell)\), and \(j\in \deptwo(g_i)\). In particular, \(\deg(g_i),\deg(f_j) \geq 2\), implying \(j\in \colstwo(Z_\ell)\). Since \(j\in \dep(g_i)\), we get from <Ref> that \(i\in \dep(f_j)\), and since \(\deg(g_i) \geq 2\), in fact \(i\in \deptwo(f_j)\). Thus, \(z_{ij}\) also appears on the RHS.
The other direction is completely analogous, implying the result.

Dividing both sides in <Ref> by the LHS of each of the items in <Ref> (and using \(s_K = \frac{1}{s_K}\)), we immediately obtain:

Let \(K\subseteq [k]\). Then

\begin{equation} \label{eq:gamma_Phi_eq_phi_Gamma}
\begin{aligned}
& \left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \gamma_i\left( z|_{i,\depone(g_i)} \right) \right) \cdot \Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) = \\
& s_K \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(z|_{\depone(f_j),j})  \right)  \cdot \Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right).
\end{aligned}
\end{equation}

The following technical claim will be used in the subsequent argument, and gives a general form for the coefficients of monomials appearing in <Ref>:

Let \(S'\subseteq \rowsone\left( \Kneqone  \right)\) and \(\left\{ \tau_i \mid \tau_i \subseteq \depone(g_i) \right\}_{i\in \rowstwo\left( Z_{\Kneqone} \right)}\). Then,

\[
\left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i(\tau_i) \right) \cdot \hat{\Phi}^K(S') \prod_{i\in S'} \sgn(G_i) = s_K \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right)  \right)\cdot \hat{\Gamma}^K\left( T' \right),
\]

where \(\sigma_j^{S'} = \left\{ i \in S' \mid \left\lvert G_i \right\rvert = z_{ij} \right\}\) and \(T' = \bigsqcup_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \tau_i\).

Since \(\rowstwo(Z_\Kneqone) \) and \(\rowsone(Z_\Kneqone)\) are disjoint, every \(z_{ij}\) appearing on the LHS of <Ref> appears either in the expression

\[ \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \gamma_i\left( z|_{i,\depone(g_i)} \right),\]

or in the expression

\[\Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) ,\]

but not in both.
Moreover, since all \(z_{ij}\) appearing on either side of <Ref> are included in \(Z_{\Kneqone}\), it follows from <Ref> that a \(z_{ij}\) appearing in the expression

\[\Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right)\]

cannot appear in the expression

\[\Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone(\Kneqone)} \right),\]

and vice versa — appearing in the former implies that \(\deg(g_i) = 1\) and in the latter that \(\deg(f_j) = 1\).

For every \(i\in S'\) the function \(G_i\) has the form \(G_i = \pm z_{ij}\) for some \(j\), since \(G_i\) is Boolean-like. Therefore, \(\prod_{i\in \rowstwo \left( Z_{\Kneqone} \right)} z_{i\tau_i} \prod_{i\in S'} \left\lvert G_i \right\rvert \) is also a monomial, so by comparing its coefficients in <Ref> we get

\[
\left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i(\tau_i) \right) \cdot \hat{\Phi}^K(S') \prod_{i\in S'} \sgn(G_i) = s_K \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right)  \right)\cdot \hat{\Gamma}^K\left( T' \right),
\]

where \(\sigma_i^{S'}\) and \(T'\) are as in the statement of the lem:termwise_compare.

Using <Ref>, we can begin to express \(\Phi^K\) in terms of the \(\phi_j\) and some fixed constant (and analogously for \(\Gamma^K\) and \(\gamma_i\)). We start by characterizing an arbitrary Fourier coefficient of \(\Phi^K\) in this way:

Let \(K\subseteq [k]\) and let \(S' \in \supp(\hat{\Phi}^K)\). Then there are \(T'\in \supp(\hat{\Gamma}^K)\) and constants \(h_{\Phi^K}, h_{\Gamma^K}\) that depend only on \(K\) such that

\begin{align*}
\hat{\Phi}^K\left( S' \right) &= h_{\Phi^K} \cdot \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right) \cdot \prod_{i \in S'} \sgn(G_i),  \\
\hat{\Gamma}^K\left( T' \right) &= h_{\Gamma^K} \cdot \prod_{i\in \rowstwo(Z_{\Kneqone})} \hat{\gamma}_i\left( \tau_i^{T'} \right) \cdot \prod_{j \in T'} \sgn(F_j),
\end{align*}

where \(\sigma_j^{S'} = \left\{ i \in S' \mid \left\lvert G_i \right\rvert = z_{ij} \right\}\) and \(\tau_i^{T'} = \left\{ j \in T' \mid \left\lvert F_j \right\rvert = z_{ij} \right\}\) . Moreover,

\begin{align*}
h_{\Phi^K} &= s_K \cdot  \frac{\hat{\Gamma}^K\left( \bigcup_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \tau_i\right)}{\prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i\left( \tau_i \right)} & \text{ for every } \left\{ \tau_i  \in \supp(\hat{\gamma}_i)\right\}_{i\in \rowstwo\left( Z_{\Kneqone} \right)}, \\
h_{\Gamma^K} &= s_K \cdot  \frac{\hat{\Phi}^K\left( \bigcup_{j\in \colstwo\left( Z_{\Kneqone} \right)} \sigma_j\right)}{\prod_{j\in \colstwo\left( Z_{\Kneqone} \right)} \hat{\phi}_j\left( \sigma_j \right)} & \text{ for every } \left\{ \sigma_j  \in \supp(\hat{\phi}_j)\right\}_{j\in \colstwo\left( Z_{\Kneqone} \right)}.
\end{align*}

In other words, for any set of supported \(\tau_i\) sets, the ratio \(\frac{\hat{\Gamma}^K\left( \bigcup_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \tau_i\right)}{\prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i\left( \tau_i \right)}\) equals the same value, which we denote by \(h_{\Phi^K} / s_K\) (and similarly for any set of \(\sigma_j\)'s).

We show the result for \(\hat{\Phi}^K(S')\); the result for \(\hat{\Gamma}^K(T')\) is analogous.

Let \(\left\{ \tau_i  \in \supp(\hat{\gamma}_i)\right\}_{i\in \rowstwo\left( Z_{\Kneqone} \right)}\). Applying <Ref> over the these sets and \(S'\), we get:

\begin{equation}
\left( \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i(\tau_i) \right) \cdot \hat{\Phi}^K(S') \prod_{i\in S'} \sgn(G_i) = s_K \cdot \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right)  \right)\cdot \hat{\Gamma}^K\left( T' \right),
\end{equation}

where \(\sigma_j^{S'} = \left\{ i \in S' \mid \left\lvert G_i \right\rvert = z_{ij} \right\}\) and \(T' = \bigsqcup_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \tau_i\) are in their respective supports, since the LHS is nonzero by assumption.

Moreover, since the LHS is nonzero, we have:

\begin{equation}\label{eq:Phi_monomial_compare}
\begin{aligned}
&\hat{\Phi}^K(S') \cdot \prod_{i\in S'} \sgn(G_i) =\\
&\left(  \frac{s_K \cdot \hat{\Gamma}^K\left( T' \right).}{ \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i(\tau_i)  } \right) \cdot \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right) =
h_{\Phi^K} \cdot  \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right),
\end{aligned}
\end{equation}

where $h_{\Phi^K}$ is given by the two formulas

\[
h_{\Phi^K} =
s_K \cdot  \frac{\hat{\Gamma}^K\left( \bigcup_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \tau_i\right)}{\prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \hat{\gamma}_i\left( \tau_i \right)} =
\frac{\hat{\Phi}^K(S') \cdot \prod_{i\in S'} \sgn(G_i)}{\prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right)}.
\]

The second formula depends only on $S'$, showing that $h_{\Phi^K}$ doesn't depend on the choice of $\tau_i$. Fixing such a choice, the value of $h_{\Phi^K}$ is the same for all $S'$, and so it depends only on $K$.

Since the previous result characterized all of the Fourier coefficients of \(\Phi^K\), we use the uniqueness of the Fourier expansion to characterize \(\Phi^K\) itself:

Let \(K\subseteq [k]\). Then

\begin{align*}
\Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) &= h_{\Phi^K} \cdot \prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(z|_{\depone(F_j),j}), \\
\Gamma^K\left(  \left( F_1,\dots,F_m \right)|_{\colsone\left( \Kneqone \right)} \right) &= h_{\Gamma^K} \cdot \prod_{i\in \rowstwo\left( Z_{\Kneqone} \right)} \gamma_i\left( z|_{i,\depone(G_i)} \right).
\end{align*}

We show the result for \(\Phi^K\), the result for \(\Gamma^K\) is analogous.

In light of <Ref>, the Fourier expansion of \(\Phi^K\) becomes:

\begin{align*}
&\Phi^K\left( \left( G_1,\dots,G_n \right)|_{\rowsone\left( Z_{\Kneqone} \right)} \right) =\\
&\sum_{S' \subseteq \rowsone\left( \Kneqone  \right)} \left( \hat{\Phi}^K(S') \prod_{i\in S'} G_i \right)
& \sum_{S' \subseteq \rowsone\left( \Kneqone  \right)}\left( \left( \hat{\Phi}^K(S') \prod_{i\in S'} \sgn(G_i) \right) \prod_{i\in S'} \left\lvert G_i \right\rvert \right)
& \sum_{S' \subseteq \rowsone\left( \Kneqone  \right)}\left( \left( h_{\Phi^K} \cdot \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right) \right) \prod_{i\in S' } \left\lvert G_i \right\rvert \right) =\\
& h_{\Phi^{K}}\sum_{S' \subseteq \rowsone\left( \Kneqone  \right)}\left( \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j^{S'} \right) \right) \prod_{i\in S' } \left\lvert G_i \right\rvert \right),
\end{align*}

where \(S' = \bigsqcup_{j\in \colstwo\left( Z_{\Kneqone}  \right)}\sigma_j^{S'}\) is a unique decomposition due to how the sets \(\sigma_j^{S'}\) are defined.

Since the decomposition of \(S'\) is unique, we can sum over all possible collections of \(\sigma_j\), instead of over every \(S'\). Denoting \(r^K = \left\lvert \colstwo\left( Z_{\Kneqone} \right)\right\rvert \), which we shorten into \(r\) to simplify the subsequent expressions, and enumerating the indices of \(\colstwo\left( Z_{\Kneqone} \right)\) by \(j_1,\dots,j_{r}\), we obtain

\begin{align*}
&= h_{\Phi^K} \cdot\\
&\cdot\sum_{\sigma_{j_1}\subseteq \depone(F_{j_1})} \dots \sum_{\sigma_{j_{r}}\subseteq \depone(F_{j_{r}})}\left( \left( \prod_{j\in \colstwo(Z_{\Kneqone})} \hat{\phi}_j\left( \sigma_j \right) \right) \prod_{i\in \bigsqcup_{j\in \colstwo\left( Z_{\Kneqone} \right)} \sigma_j } \left\lvert G_i \right\rvert \right) \\
&= h_{\Phi^K} \cdot \sum_{\sigma_{j_1}\subseteq \depone(F_{j_1})} \dots \sum_{\sigma_{j_{r}}\subseteq \depone(F_{j_{r}})}\left( \left( \hat{\phi}_{j_1}\left( \sigma_{j_1} \right) \cdot  z_{\sigma_{j_1}j_1}\right) \dots \left( \hat{\phi}_{j_{r}}\left( \sigma_{j_{r}} \right) \cdot z_{\sigma_{j_{r}}j_{r}}\right)  \right) \\
&= h_{\Phi^K} \cdot \left( \sum_{\sigma_{j_1}\subseteq \depone(F_{j_1})}\hat{\phi}_{j_1}(\sigma_{j_1}) \cdot  z_{\sigma_{j_1}j_1} \right) \dots \left( \sum_{\sigma_{j_{r}}\subseteq \depone(F_{j_{r}})} \hat{\phi}_{j_{r}}(\sigma_{j_{r}})  \cdot  z_{\sigma_{j_r}j_r} \right)      \\
&= h_{\Phi^K} \prod_{j\in \colstwo\left( Z_{\Kneqone} \right)} \left( \sum_{\sigma_j\subseteq \depone(F_j)} \left( \hat{\phi}_j(\sigma_j) \cdot z_{\sigma_jj} \right)\right)  \\
&= h_{\Phi^K} \prod_{j\in \colstwo\left( Z_{\Kneqone} \right)} \phi_j\left(  z|_{\depone(F_j),j} \right). \qedhere
\end{align*}

By substituting the previous result into <Ref>, we get a characterization of \(F_0\) and \(G_0\). Given some \(x\in \left\{ -1,1 \right\}^{[n]}\), the next result uses the notation \(x^{\sgn} \in \left\{ -1,1 \right\}^{[n]}\) to denote the vector obtained from \(x\) by replacing entries \(x_i\) with \(\sgn(G_i) \cdot x_i\) whenever \(\deg(G_i) = 1\), and leaving other entries as they are. In particular, all entries in \(x^{\sgn}|_{\rowsone\left( Z_1 \right)}\) will be of the form \(\sgn(G_i) \cdot x_i\). The notation \(y^{\sgn}\) is defined analogously.

Let \(h_{F_0}\colon \left\{ -1,1 \right\}^{[k]} \to \R\) and \(h_{G_0}\colon \left\{ -1,1 \right\}^{[k]} \to \R\) be the functions defined by the Fourier coefficients

\begin{align*}
\hat{h}_{F_0}(K) &= h_{\Phi^K} \cdot \prod_{j\in \colsone(Z_{\Kone})} \sgn(F_j) & \text{ for every } K\subseteq [k], \\
\hat{h}_{G_0}(K) &= h_{\Gamma^K} \cdot \prod_{i\in \rowsone(Z_{\Kone})} \sgn(G_i) & \text{ for every } K\subseteq [k].
\end{align*}

\begin{align*}
F_0 &= h_{F_0}\left( F_0^{(1)},\dots, F_0^{(k)}\right), \\
G_0 &= h_{G_0}\left( G_0^{(1)},\dots, G_0^{(k)}\right),
\end{align*}

\begin{align*}
F_0^{(\ell)}(x) &= \begin{cases}
x_{\rowstwo(Z_\ell)} \cdot  \prod_{j\in \colstwo(Z_\ell)} \phi_j\left( x^{\sgn}|_{\rowsone\left( Z_\ell \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(F_j) \cdot x_i & \text{ if } Z_\ell = \left\{ z_{ij} \right\}, \\
\end{cases}  \\
G_0^{(\ell)}(y) &= \begin{cases}
y_{\colstwo(Z_\ell)} \cdot  \prod_{i\in \rowstwo(Z_\ell)} \gamma_i\left( y^{\sgn}|_{\colsone\left( Z_\ell \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(G_i) \cdot y_j & \text{ if } Z_\ell = \left\{ z_{ij} \right\}.
\end{cases}
\end{align*}

We show the result for \(F_0\); the argument for \(G_0\) is analogous. Denoting \(\left\{ i_1,\dots,i_r \right\} = \rowsone\left( Z_{\Kneqone} \right) \), <Ref> becomes:

\begin{align*}
&F_0(x_1,\dots,x_n) = \\
&\sum_{K\subseteq [k]} x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot  \Phi^K\left( x_{i_1},\dots,x_{i_r} \right)  =\\
&  \sum_{K\subseteq [k]} x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot \\
&\phantom{\sum_{K\subseteq [k]}}\cdot \Phi^K\left( \sgn(G_{i_1})\cdot\sgn(G_{i_1})x_{i_1},\dots,\sgn(G_{i_r})\cdot\sgn(G_{i_r})x_{i_r} \right) =\\
&  \sum_{K\subseteq [k]} x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot  \Phi^K\left( \sgn(G_{i_1})\cdot x_{i_1}',\dots,\sgn(G_{i_r})\cdot x_{i_r}' \right),
\end{align*}

where we use the notation \(x_i' = \sgn(G_i) \cdot x_i \in \left\{ -1,1 \right\}\).

For $i \in \rowsone(Z_{\Kneqone})$, let $G_i = \sgn(G_i) \cdot z_{ij_i}$. The LHS of <Ref> is thus

\[
\Phi^K\left(\sgn(G_{i_1}) \cdot z_{i_1j_{i_1}}, \ldots, \sgn(G_{i_\ell}) \cdot z_{i_\ell j_{i_\ell}}\right).
\]

Substituting $z_{ij_i} = x_i'$ gives

\begin{align*}
&\Phi^K\left( \sgn(G_{i_1})\cdot x_{i_1}',\dots,\sgn(G_{i_r})\cdot x_{i_r}' \right) =\\
&h_{\Phi^K} \cdot \prod_{j \in \colstwo(Z_{\Kneqone})} \phi_j(z|_{\depone(F_j),j}) =\\
&h_{\Phi^K} \cdot \prod_{j \in \colstwo(Z_{\Kneqone})} \phi_j(\left(x'_{i_1},\ldots,x'_{i_r}\right)|_{\depone(F_j)}).
\end{align*}

Substituting this in the expression we had above, we get that $F_0(x_1,\ldots,x_n)$ equals

\begin{align*}
&\sum_{K\subseteq [k]}h_{\Phi^K} \cdot x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot   \prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(\left( x_{i_1}',\dots,x_{i_r}' \right)|_{\depone(F_j)}) =\\
&\sum_{K\subseteq [k]} \left( \hat{h}_{F_0}(K) \cdot \prod_{j\in \colsone(Z_{\Kone})} \sgn(F_j) \right) \cdot x_{\rowsone(Z_{\Kone})} \cdot x_{\rowstwo(Z_{\Kneqone})} \cdot \\
&\phantom{\sum_{K\subseteq [k]} \left( \hat{h}_{F_0}(K) \cdot \prod_{j\in \colsone(Z_{\Kone})} \sgn(F_j) \right)}\cdot\prod_{j\in \colstwo(Z_{\Kneqone})} \phi_j(\left( x_{i_1}',\dots,x_{i_r}' \right)|_{\depone(F_j)}).
\end{align*}

For each $K \subseteq [k]$ we have

\[
\prod_{j \in \colsone(Z_{\Kone})} \sgn(F_j) \cdot x_{\rowsone}(Z_{\Kone}) =
\prod_{\substack{\ell \in \Kone \\ Z_\ell = \{z_{ij}\}}} \sgn(F_j) \cdot x_i = \prod_{\ell \in \Kone} F_0^{(\ell)},
\]

using <Ref> in the first step.

In addition, for each $K \subseteq [k]$ we have

\begin{align*}
&x_{\rowstwo(Z_{\Kneqone})} \cdot \prod_{j \in \colstwo(Z_{\Kneqone})} \phi_j(\left(x'_{i_1},\dots,x'_{i_r}\right)|_{\depone(F_j)}) = \\&
\prod_{\ell \in \Kneqone} \left( x_{\rowstwo(Z_\ell)} \cdot \prod_{j \in \colstwo(Z_\ell)} \phi_j(\left(x'_{i_1},\dots,x'_{i_r}\right)|_{\depone(F_j)}) \right) = \\&
\prod_{\ell \in \Kneqone} \left( x_{\rowstwo(Z_\ell)} \cdot \prod_{j \in \colstwo(Z_l)} \phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}) \right) =
\prod_{\ell \in \Kneqone} F_0^{(\ell)},
\end{align*}

where in the penultimate step we extend the domain of $\phi_j$ from $\depone(F_j)$ into $\rowsone(Z_\ell) \supseteq \depone(F_j)$ by having $\phi_j$ ignore the extra inputs.

Altogether, this shows that

\[
F_0(x_1,\ldots,x_n) = \sum_{K \subseteq [k]} \hat{h}_{F_0}(K) \prod_{\ell \in K} F_0^{(\ell)} = h_{F_0} \circ (F_0^{(1)},\dots,F_0^{(k)}). \qedhere
\]

In order to fully characterize \(F_0\) and \(G_0\), all that's left is to show that \(h_{F_0} = h_{G_0} \):

\(h_{F_0} = h_{G_0}\).

By substituting <Ref> into the Fourier expansion of \(F_0 \circ (G_1,\dots,G_n) = G_0 \circ (F_1,\dots,F_m)\), we get

\begin{align*}
& F_0 \circ (G_1,\dots,G_n) \\
&= \sum_{K\subseteq [k]} \left( \hat{h}_{F_0}(K)  \cdot \prod_{\ell\in K} \left( F_0^{(\ell)} \circ \left( G_1,\dots,G_n \right) \right) \right)\\
&= \sum_{K\subseteq [k]}\left( \hat{h}_{G_0}(K)  \cdot \prod_{\ell\in K} \left( G_0^{(\ell)} \circ \left( F_1,\dots,F_m \right) \right) \right)\\
&= G_0 \circ (F_1,\dots,F_m).
\end{align*}

We show below that $F_0^{(\ell)} \circ (G_1,\ldots,G_n) = G_0^{(\ell)} \circ (F_1,\ldots,F_m)$ for all $\ell \in [k]$, and so

\[
\sum_{K \subseteq [k]} (\hat{h}_{F_0}(K) - \hat{h}_{G_0}(K)) \prod_{\ell \in K} F_0^{(\ell)} \circ (G_1,\ldots,G_n) = 0.
\]

The formula for $F_0^{(\ell)}$ shows that $F_0^{(\ell)}$ depends only on $x_i$ for $i \in \rows(Z_\ell)$.
Furthermore, it follows from <Ref> that $F_0^{(\ell)}$ is balanced, and so each monomial in $F_0^{(\ell)}$ includes some variable $x_i$, where $i \in \rows(Z_\ell)$. Indeed, if \(Z_{\ell}\) is a singleton, then \(F_0^{(\ell)}\) is balanced by definition. Otherwise, if \(Z_{\ell}\) a non-singleton and also not a single column, then \(\rowstwo(Z_{\ell})\neq \emptyset\), therefore every nonzero coefficient in \(F_0^{(\ell)}\) contains the factor \(x_{\rowstwo(Z_\ell)}\). Finally, if \(Z_\ell\) is a single column and not a singleton, then \(F_0^{(\ell)} = \phi_j = F_j\), since \(\deptwo(F_j) \subseteq \rowstwo(Z_\ell) = \emptyset\), and is therefore balanced since \(F_j\) is balanced.

Consequently, each monomial in

\[
\prod_{\ell \in K} \left(F_0^{(\ell)} \circ (G_1,\ldots,G_n)\right)
\]

involves only variables in $Z_K$, and contains at least one variable in $Z_\ell$ for each $\ell \in K$.
In particular, the monomials multiplying $\hat{h}_{F_0}(K) - \hat{h}_{G_0}(K)$ are different for different $K$, and so the uniqueness of the Fourier expansion forces $\hat{h}_{F_0}(K) = \hat{h}_{G_0}(K)$ for all $K \subseteq [k]$. We conclude that $h_{F_0} = h_{G_0}$.

It remains to show that for every $\ell \in K$, we have $F_0^{(\ell)} \cdot (G_1,\ldots,G_n) = G_0^{(\ell)} \cdot (F_1,\ldots,F_m)$.

If \(\ell\in \Kone\) then there exists some \(z_{ij}\in Z_0\) such that \(Z_\ell = \left\{ z_{ij} \right\}\) and \(F_0^{(\ell)}(x) = \sgn(F_j) \cdot x_i\). Therefore, \(F_0^{(\ell)}\circ \left( G_1,\dots,G_n \right) = \sgn(F_j)\cdot G_i = \sgn(F_j) \cdot \sgn(G_i) \cdot z_{ij}\), since \(G_i\) has degree \(1\) and is Boolean-like. Similarly, we get \(G_0^{(\ell)} \circ \left( F_1,\dots,F_m \right) = \sgn(G_i) \cdot F_j = \sgn(G_i) \cdot \sgn(F_j) \cdot z_{ij}\).

If $\ell \in \Kneqone$ then using the definition of \(F_0^{(\ell)}\) followed by substituting <Ref>, we get

\begin{equation} \label{eq:hF0}
\begin{aligned}
&F_0^{(\ell)} \circ \left( G_1,\dots,G_n \right) = \\
&(G_1,\dots,G_n)_{\rowstwo(Z_\ell)}  \cdot \prod_{j\in \colstwo(Z_\ell)} \phi_j(\left( G_1,\dots,G_n \right)^{\sgn}|_{\rowsone(Z_\ell)})  =\\
&\left( \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]}|_{\depone(g_i)}) \cdot z_{i\deptwo(g_i)} \right) \cdot \\
&\phantom{\left( \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]}|_{\depone(g_i)}) \cdot z_{i\deptwo(g_i)} \right.} \cdot \prod_{j\in \colstwo(Z_\ell)} \phi_j((G_1,\dots,G_n)^{\sgn} |_{\rowsone(Z_\ell)})  =\\
& \left( \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]}|_{\depone(g_i)}) \cdot z_{i\deptwo(g_i)} \right) \cdot \\
&\phantom{\left( \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]}|_{\depone(g_i)}) \cdot z_{i\deptwo(g_i)} \right.}\cdot\prod_{j\in \colstwo(Z_\ell)} \phi_j((G_1,\dots,G_n)^{\sgn} |_{\depone(f_j)})  =\\
&\left( \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]}|_{\depone(g_i)}) \cdot z_{i\deptwo(g_i)} \right) \cdot \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n],j}|_{\depone(f_j)}),
\end{aligned}
\end{equation}

where the last equality follows from the projection over \(\depone(f_j)\), under which all \(G_i\) have the form \(G_i(z_{i,[m]}) = \sgn(G_i) z_{ij}\), where the \(\sgn(G_i)\) values are canceled out due to them being in a \((\cdot)^{\sgn}\) vector.

Similarly, we obtain

\begin{equation} \label{eq:hG0}
\begin{aligned}
&G_0^{(\ell)} \circ \left( F_1,\dots,F_m \right)
= \\
&(F_1,\dots,F_m)_{\colstwo(Z_\ell)}  \cdot \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(\left( F_1,\dots,F_m \right)^{\sgn}|_{\colsone(Z_\ell)}) =\\
&\left( \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n], j}|_{\depone(f_j)}) \cdot z_{\deptwo(f_j)j} \right) \cdot \\
&\phantom{\left( \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n], j}|_{\depone(f_j)}) \cdot z_{\deptwo(f_j)j} \right.}\cdot\prod_{i\in \rowstwo(Z_\ell)} \gamma_i((F_1,\dots,F_m)^{\sgn} |_{\colsone(Z_\ell)})=\\
&\left( \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n], j}|_{\depone(f_j)}) \cdot z_{\deptwo(f_j)j} \right) \cdot \\
&\phantom{\left( \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n], j}|_{\depone(f_j)}) \cdot z_{\deptwo(f_j)j} \right.}\cdot\prod_{i\in \rowstwo(Z_\ell)} \gamma_i((F_1,\dots,F_m)^{\sgn} |_{\depone(g_i)}) =\\
&= \left( \prod_{j\in \colstwo(Z_\ell)} \phi_j(z_{[n], j}|_{\depone(f_j)}) \cdot z_{\deptwo(f_j)j} \right) \cdot \prod_{i\in \rowstwo(Z_\ell)} \gamma_i(z_{i,[m]} |_{\depone(g_i)}).
\end{aligned}
\end{equation}

The result follows by comparing <Ref> with <Ref> and applying <Ref>, <Ref>.

Combining the last two results immediately implies

Let \(h\colon \left\{ -1,1 \right\}^{[k]} \to \R\) be the function defined by the Fourier coefficients

\begin{align*}
\hat{h}(K) &= h_{\Phi^K} \cdot \prod_{j\in \colsone(Z_{\Kone})} \sgn(F_j)  =
h_{\Gamma^K} \cdot \prod_{i\in \rowsone(Z_{\Kone})} \sgn(G_i) & \text{ for every } K \subseteq [k].
\end{align*}

\begin{align*}
F_0(x) &= h\left( F_0^{(1)},\dots, F_0^{(k)}\right), \\
G_0(y) &= h\left( G_0^{(1)},\dots, G_0^{(k)}\right),
\end{align*}

\begin{align*}
F_0^{(\ell)} &= \begin{cases}
x_{\rowstwo(Z_\ell)} \cdot  \prod_{j\in \colstwo(Z_\ell)} \phi_j\left( x^{\sgn}|_{\rowsone\left( Z_\ell \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(F_j) \cdot x_i & \text{ if } Z_\ell = \left\{ z_{ij} \right\}, \\
\end{cases}  \\
G_0^{(\ell)} &= \begin{cases}
y_{\colstwo(Z_1)} \cdot  \prod_{i\in \rowstwo(Z_1)} \gamma_i\left( y^{\sgn}|_{\colsone\left( Z_1 \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(G_i) \cdot y_j & \text{ if } Z_\ell = \left\{ z_{ij} \right\}.
\end{cases}
\end{align*}

§.§.§ Characterization

In the previous sections, we obtained a Boolean-like characterization for the functions appearing in the generalized polymorphism \(F_0,\dots,F_m,G_0,\dots,G_n\), where every \(F_j\) and \(G_i\) was obtained through reductions from \(f_j\) and \(g_i\), respectively. Next, we unroll these reductions and obtain a characterization for the original Boolean-like generalized polymorphism \(f_0,\dots,f_m,g_0,\dots,g_n\).

Let \(f_0,\dots,f_m,g_0,\dots,g_n\) be a generalized polymorphism, where \(f_0,g_0\) depend on all their inputs, and \(g_1,\dots,g_n,f_1,\dots,f_m\) are Boolean-like and non-constant. Then there are:

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

* a partition of \(Z_0\) into submatrices \(Z_0 = \bigsqcup_{\ell=1}^k Z_\ell\), 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_\ell\) for \(\ell > 0\)), such that for every \(z_{ij}\in Z_\ell\) we have \(\dep(g_i) \subseteq \cols(Z_\ell)\), \(\dep(f_j) \subseteq \rows(Z_\ell)\); and \(j'\in \dep(g_{i'})\) if and only if \(i' \in \dep(f_{j'})\) for every \(i'\in \rows(Z_\ell)\) and \(j'\in \cols(Z_\ell)\),

* an arbitrary multilinear polynomial \(h\colon \mathbb{R}^k \to \mathbb{R}\) that depends on all of its coordinates,

* arbitrary functions \(\left\{ \gamma_i \right\}_{i\in \rows(Z_0)},\left\{ \phi_j \right\}_{j\in \cols(Z_0)}\), where \(\gamma_i\colon \left\{ -1,1 \right\}^{\textnormal{Dep}_{\deg=1}(g_i)}\rightarrow \mathbb{R}\) and where \(\phi_j\colon \allowbreak \left\{ -1,1 \right\}^{\textnormal{Dep}_{\deg=1}(f_j)}\rightarrow \mathbb{R}\),

* real constants \(\left\{ D_i \right\}_{i\in [n]}\), \(\left\{ B_j \right\}_{j\in [m]}\) and \(\left\{ \kappa_{ij}  \right\}_{z_{ij} \in \Ztwo_0}\),
where $D_i = 0$ if $\deg(g_i) = 1$; $B_j = 0$ if $\deg(f_j) = 1$; and $\kappa_{ij} = 0$ if either $\deg(g_i) = 1$ or $\deg(f_j) = 1$,

such that:

\begin{equation} \label{eq:boolean_like_main}
\begin{aligned}
f_0 = h\left( f_0^{(1)},\dots, f_0^{(k)}\right), & & f_j(x) = \left( \prod_{i\in\deptwo(f_j)}\left( x_i + \kappa_{ij} \right) \right) \cdot \phi_j(x|_{\depone(f_j)}) + B_j,
\\
g_0 = h\left( g_0^{(1)},\dots, g_0^{(k)}\right), & & g_i(y) = \left( \prod_{j\in\deptwo(g_i)}\left( y_j + \kappa_{ij} \right) \right) \cdot \gamma_i(y|_{\depone(g_i)}) + D_i,
\end{aligned}
\end{equation}

\begin{align*}
f_0^{(\ell)}(x) &= \begin{cases}
\left( \prod_{i\in \rowstwo(Z_\ell)} (x_i - D_i) \right) \cdot  \prod_{j\in \colstwo(Z_\ell)} \phi_j\left( x^{\sgn}|_{\rowsone\left( Z_\ell \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(f_j) x_i & \text{ if } Z_\ell = \left\{ z_{ij} \right\}, \\
\end{cases}  \\
g_0^{(\ell)}(y) &= \begin{cases}
\left( \prod_{j\in \colstwo(Z_\ell)} (y_j - B_j) \right) \cdot  \prod_{i\in \rowstwo(Z_\ell)} \gamma_i\left( y^{\sgn} |_{\colsone\left( Z_\ell \right)} \right) & \text{ if } \left\lvert Z_\ell \right\rvert > 1, \\
\sgn(g_i) y_j & \text{ if } Z_\ell = \left\{ z_{ij} \right\}.
\end{cases}
\end{align*}

Conversely, suppose that we are given $Z_0$, a partition of $Z_0$ into submatrices, the functions $h,\gamma_i,\phi_j$, and the constant $D_i,B_j,\kappa_{ij}$, and use them to define functions $f_0,\ldots,f_m,g_0,\ldots,g_n$ as above. Then $f_0,\ldots,f_m,g_0,\allowbreak \ldots,g_n$ are a generalized polymorphism.

Let $f_0,\ldots,f_m,g_0,\ldots,g_n$ be a generalized polymorphism satisfying the stated constraints. We show that it has the required form.

Apply <Ref> to get a shifted generalized polymorphism \(F_0, \dots, F_m,\allowbreak G_0,\dots\allowbreak, G_n \) where all functions are non-constant; \(F_1,\dots,F_m,G_1,\dots,G_n\) are Boolean-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 forms in <Ref>, and from <Ref>, we get that \(F_0,G_0\) have the forms in <Ref>.

The characterization now results from unrolling the reductions. Starting with \(F_0\) (unrolling \(G_0\) is completely analogous): we unroll the reduction <Ref> made in <Ref> to obtain \(f_0\) from \(F_0\) so that:

\[
F_0(x_1,\dots,x_n) = f_0\left( x_1 + \hat{\tilde{g}}_1(\emptyset),\dots,  x_n + \hat{\tilde{g}}_n(\emptyset) \right),
\]

\[
F_0 \left(  x_1 - \hat{\tilde{g}}_1(\emptyset),\dots,  x_n - \hat{\tilde{g}}_n(\emptyset) \right) = f_0(x_1,\dots,x_n).
\]

Since \(g_1,\dots,g_n\) are Boolean-like, all \(g_i\) with \(i\in \rowsone(Z_0)\) have the form \(g_i(y) = \tilde{g}_i(y) = \pm y_j\) for some \(j\in [m]\), so in particular satisfy \(\hat{\tilde{g}}_i(\emptyset) = 0\). Thus, by setting \(D_i = \hat{\tilde{g}}_i(\emptyset) \) and substituting into the expression we got for \(F_0\), we get \(f_0\) in the form appearing in the thm:boolean_like_main.

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).
\]

Since \(\kappa_{ij} = 0\) for every \(j\in \depone(g_i)\), by substituting the above into <Ref> and using the values of \(D_i\) set above we get the characterization in <Ref>.

Converse direction. Let $f_0,\ldots,f_m,g_0,\ldots,g_n$ be defined as in the thm:boolean_like_main. Define

\begin{align*}
&F_0(x_1,\ldots,x_n) = f_0(x_1 + D_1, \dots, x_n + D_n),\\
& F_j(x_1,\ldots,x_n) = f_j(x_1 - \kappa_{1j}, \dots, x_n - \kappa_{nj}) - B_j, \\
&G_0(y_1,\ldots,y_m) = g_0(y_1 + B_1, \dots, y_m + B_m), \\
&G_i(y_1,\ldots,y_m) = g_i(y_1 - \kappa_{i1}, \dots, y_m - \kappa_{im}) - D_i.
\end{align*}

Then $F_0,\ldots,F_m,G_0,\ldots,G_n$ all have the forms specified by <Ref> and by <Ref>. Therefore the calculation in the proof of <Ref> shows that $F_0,\ldots,F_m,G_0,\ldots,G_n$ is a generalized polymorphism; while <Ref> makes some assumptions on $F_0,\ldots\allowbreak,F_m,G_0,\ldots,G_n$, these are not needed for the calculation. Since

\begin{align*}
&f_0 \circ (g_1(z_{11}-\kappa_{11},\ldots,z_{1m}-\kappa_{1m}),\ldots,g_n(z_{n1}-\kappa_{n1},\ldots,z_{nm}-\kappa_{nm})) = \\
&F_0 \circ (G_1(z_{11},\ldots,z_{1n}),\ldots,G_n(z_{n1},\ldots,z_{nm})) = \\
&F_0 \circ (G_1,\ldots G_n)
\end{align*}

and similarly

\begin{align*}
&g_0 \circ (f_1(z_{11} - \kappa_{11},\ldots,z_{n1} - \kappa_{n1}),\ldots,f_m(z_{1m}-\kappa_{1m},\ldots,z_{nm} - \kappa_{nm})) = \\
&G_0 \circ (F_1(z_{11},\ldots,z_{n1}),\ldots,F_m(z_{1m},\ldots,z_{nm}) = \\
&G_0 \circ (F_1,\ldots,F_m),
\end{align*}

it follows that $f_0,\ldots,f_m,g_0,\ldots,g_n$ is also a generalized polymorphism.

§.§ Boolean characterization

In this section, we combine <Ref> with <Ref> to obtain a version of <Ref> in the setting of Boolean generalized polymorphisms. For the moment, we retain our previous assumptions that \(f_0\) and \(g_0\) depend on all their inputs and that $g_1,\dots,g_n,f_1,\dots,f_m$ are non-constant, and start by characterizing what form Boolean \(g_1,\dots,g_n,f_1,\dots,f_m\) attain when they are part of a Boolean generalized polymorphism \(g_0,\dots,g_n,f_0,\dots,f_m\). We see that when \(g_0,\dots,g_n,f_0,\dots,f_m\) are all Boolean, then the functions \(\phi_j,\gamma_i\) associated with \(f_j,g_i\), respectively, are “almost Boolean”.  Moreover, any two functions out of \(g_1,\dots,g_n,f_1,\dots,f_m\) whose \(\gamma_i,\phi_j\) happen to be constant, are the same Boolean function up to possibly negated inputs.

Let \(f_0,\dots,f_m,g_0,\dots,g_n\) be a Boolean generalized polymorphism, where \(f_0,g_0\) depend on all their inputs, and \(g_1,\dots,g_n,f_1,\dots,f_m\) are non-constant.
Then the characterization in <Ref> holds with the following additional promise. For every $\ell \in [k]$, one of the following cases holds:

* The block $Z_\ell$ is a singleton, $Z_\ell = \{ z_{ij} \}$, and

\begin{align*}
f_j(x) = \sgn(f_j) x_i, &&
g_i(y) = \sgn(g_i) y_j, \\
f_0^{(\ell)}(x) = \sgn(f_j) x_i, &&
g_0^{(\ell)}(y) = \sgn(g_i) y_j.
\end{align*}

* For every $i \in \rows(Z_\ell)$ and for every $j \in \cols(Z_\ell)$ we have $D_i = B_j = 0$ and

\begin{align*}
f_j(x) &= \phi_j\left( x|_{\depone(f_j)} \right) x_{\deptwo(f_j)}, \text{ where } \phi_j \in \left\{ -1,1 \right\}, \\
g_i(y) &= \gamma_i\left( y|_{\depone(g_i)} \right) y_{\deptwo(g_i)}, \text{ where } \gamma_i \in \left\{ -1,1 \right\}.
\end{align*}

\begin{align*}
f_0^{(\ell)}(x) &= \prod_{i \in \rowstwo(Z_\ell)} x_i \cdot \prod_{j \in \colstwo(Z_\ell)} \phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}) \in \{-1,1\}, \\
g_0^{(\ell)}(y) &= \prod_{j \in \colstwo(Z_\ell)} y_j \cdot \prod_{i \in \rowstwo(Z_\ell)} \gamma_i(y^{\sgn}|_{\colsone(Z_\ell)}) \in \{-1,1\}.
\end{align*}

* For every $i \in \rowsone(Z_\ell)$ and every $j \in \colsone(Z_\ell)$, the functions $f_j,g_i$ are dictators.
For every $i \in \rowstwo(Z_\ell)$ and for every $j \in \colstwo(Z_\ell)$ we have $B_j,D_i \in \{-1,1\}$, for every $z_{ij} \in \Ztwo_\ell$ we have $\kappa_{ij} \in \{-1,1\}$, and

\begin{align*}
f_j(x) &= \tilde\phi_j\left( x|_{\depone(f_j)} \right) \cdot 2B_j \prod_{i\in \deptwo(f_j)} \frac{\kappa_{ij} x_i + 1}{2} - B_j, \text{ where } \tilde\phi_j \in \left\{ 0,1 \right\}, \\
g_i(y) &= \tilde\gamma_i\left( y|_{\depone(g_i)} \right)\cdot 2D_i \prod_{j\in \deptwo(g_i)} \frac{\kappa_{ij} y_j + 1}{2} - D_i, \text{ where }  \tilde\gamma_i\in \left\{ 0,1 \right\}.
\end{align*}

\begin{align*}
f_0^{(\ell)}(x) &= 2 \prod_{i \in \rowstwo(Z_\ell)} \frac{D_i x_i + 1}{2} \prod_{j \in \colstwo(Z_\ell)} \tilde\phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}) - 1 \in \{-1,1\}, \\
g_0^{(\ell)}(y) &= 2 \prod_{j \in \colstwo(Z_\ell)} \frac{B_j y_j + 1}{2} \prod_{i \in \rowstwo(Z_\ell)} \tilde\gamma_i(y^{\sgn}|_{\colsone(Z_\ell)}) - 1 \in \{-1,1\}.
\end{align*}

Moreover, we have $f_0 = h(f_0^{(1)},\dots,f_0^{(k)})$ and $g_0 = h(g_0^{(1)},\dots,g_0^{(k)})$, where $h$ maps $\{-1,1\}^k$ to $\{-1,1\}$.

This result in tight in the sense that the functions $f_0,\dots,f_m,g_0,\dots,g_n$ are a Boolean generalized polymorphism. Therefore this gives a complete characterization of all Boolean generalized polymorphisms in which $f_0,g_0$ depend on all inputs and $g_1,\dots,g_n,f_1,\dots,f_m$ are non-constant (once we postulate that these additional properties hold).

In the second case, the functions $f_j,g_i,f_0^{(\ell)},g_0^{(\ell)}$ are all XOR-like, and in the third, they are all AND/OR-like; in both cases, the functions $\tilde\phi_j,\tilde\gamma_i$ are arbitrary, but they combine with the other variables as a component of the XOR (in the second case) or the AND/OR (in the third case). For more on this perspective, see the comments at the end of <Ref>.

The assumptions made here are a special case of those made in <Ref> — the only difference being that all of \(g_0,\dots,g_n,f_0,\dots,f_m\) are now Boolean, whereas in <Ref>, \(f_1,\dots,f_m,g_1,\dots,g_n\) are only Boolean-like (and $f_0,g_0$ are arbitrary functions depending on all inputs).  Thus, we apply <Ref>, and get that \(f_1,\dots,f_m,g_1,\dots,g_n\) are of the form described in <Ref>.

Suppose first that $Z_\ell = \{ z_{ij} \}$. Then $D_i = B_j = \kappa_{ij} = 0$, and so

\begin{align*}
f_j(x) &= \phi_j(x_i), & g_i(y) &= \gamma_i(y_j), \\
f_0^{(\ell)}(x) &= \sgn(f_j) \cdot x_i, & g_0^{(\ell)}(y) &= \sgn(g_i) \cdot y_j,
\end{align*}

where $\phi_j(x_i) = \pm x_i$ and $\gamma_i(y_j) = \pm y_j$. This is Case 1.

From now on, we assume that $|Z_\ell| \geq 2$. Suppose first that $\deptwo(g_i) = \emptyset$ for some $i \in \rows(Z_\ell)$. From <Ref> we infer that \(\rows(Z_\ell) = \left\{ i \right\}\). Indeed, if it were the case that \(I = \left\{ i \right\} \subsetneq \rows(Z_\ell)\), then from <Ref> there would be some \(i'\in \rows(Z_\ell) - i\) and \(w\in \cols(Z_\ell)\) such that both \(g_i\) and \(g_{i'}\) depend on \(w\); from <Ref> this implies that \(\left\{ i,i' \right\} \subseteq \dep(f_w)\), thus \(\deg(f_w) \geq 2\) from <Ref> — in contradiction to \(\deptwo(g_i) = \emptyset\). Moreover, since \(\rows(Z_\ell) = \left\{ i \right\}\) and no \(f_j\) is constant, it follows that \(\dep(f_j) = \deptwo(f_j) = \left\{ i \right\}\) for all \(j\in \cols(Z_\ell)\).

Since $\deg(f_j) = 1$ for all $j \in \cols(Z_\ell)$, <Ref> of <Ref> implies that $\kappa_{ij} = B_j = 0$ for all $j \in \cols(Z_\ell)$,
and so <Ref> gives the formulas

\begin{align*}
f_j(x) &= x_i \cdot \phi_j(), & g_i(y) &= \gamma_i(y|_{\depone(g_i)}) + D_i, \\
f_0^{(\ell)} &= x_i - D_i, & g_0^{(\ell)} &= \gamma_i(y^{\sgn}|_{\colsone(Z_\ell)}).
\end{align*}

Here $\phi_j \in \{-1,1\}$ has no inputs. In order to put this in the form given by Case 2,
we slightly adjust the functions involved. Define the functions$\gamma'_i(y) = \gamma_i(y) + D_i$, $h'(z) = h(z_1,\ldots,z_{i-1},z_i - D_i, z_{i+1},\ldots,z_\ell)$,

\begin{align*}
f'_j(x) &= \phi_j() \cdot x_i, & g_i(y) &= \gamma'_i(y|_{\depone(g_i)}), \\
f_0^{\prime(\ell)} &= x_i, & g_0^{\prime(\ell)} &= \gamma'_i(y^{\sgn}|_{\colsone(Z_\ell)}).
\end{align*}

By construction, $f'_j = f_j$, $g'_j = g_j$, and $f_0,g_0$ are given by the formulas in <Ref>, with $h,f_0^{(\ell)},g_0^{(\ell)}$ replaced with their primed versions. Therefore this is also a valid solution, which has the form of Case 2.

The case in which $\deptwo(f_j) = \emptyset$ for some $j \in \cols(Z_\ell)$ is similar.

Finally, suppose that $\deptwo(g_i),\deptwo(f_j) \neq \emptyset$ for all $i \in \rows(Z_\ell)$ and $j \in \cols(Z_\ell)$.
If $i \in \rowstwo(Z_\ell)$ then $\deg(g_i) \geq 2$ and so $|\dep(g_i)| \geq 2$ according to <Ref>. Hence either $|\deptwo(g_i)| \geq 2$ or $|\depone(g_i)| \geq 1$; in the latter case, this implies that $\gamma_i$ is non-constant. Similar reasoning holds for $j \in \colstwo(Z_\ell)$. Applying <Ref>, we get:

* For each $i \in \rowstwo(Z_\ell)$, either $D_i,(\kappa_{ij})_{j \in \deptwo(g_i)}$ are all $0$, or all belong to $\{-1,1\}$.

* For each $j \in \colstwo(Z_\ell)$, either $B_j,(\kappa_{ij})_{i \in \deptwo(f_j)}$ are all $0$, or all belong to $\{-1,1\}$.

By definition, $Z_\ell$ is connected. We claim that $\Ztwo_\ell$ is connected as well. Indeed, consider a shortest path from $z_{ij} \in \Ztwo_\ell$ to $z_{i'j'} \in \Ztwo_\ell$. Suppose that it goes through $z_{IJ} \in \Zone_\ell$, say $I \in \rowsone(Z_\ell)$. It must be preceded and followed by elements on the same column, contradicting minimality.

Considering $\kappa_{ij}$ for $z_{ij} \in \Ztwo_\ell$, it follows that one of the following two cases holds:

* $D_i = 0$ for all $i \in \rowstwo(Z_\ell)$, $B_j = 0$ for all $j \in \colstwo(Z_\ell)$, and $\kappa_{ij} = 0$ for all $z_{ij} \in \Ztwo_\ell$.

* $D_i \in \{-1,1\}$ for all $i \in \rowstwo(Z_\ell)$, $B_j \in \{-1,1\}$ for all $j \in \colstwo(Z_\ell)$, and $\kappa_{ij} \in \{-1,1\}$ for all $z_{ij} \in \Ztwo_\ell$.

In the first case, we immediately get Case 2. It is easy to verify that in this case, $\phi_j, \gamma_i \in \{-1,1\}$.

In the second case, when $j \in \colstwo(Z_\ell)$ we get

\begin{align*}
f_j(x) &= \prod_{i \in \deptwo(f_j)} (x_i + \kappa_{ij}) \cdot \phi_j(x|_{\depone(f_j)}) + B_j \\
&=\tilde\phi_j(x|_{\depone(f_j)}) \cdot (-2B_j) \prod_{i \in \deptwo(f_j)} \frac{\kappa_{ij}x_i + 1}{2} + B_j,
\end{align*}

\[
\tilde\phi_j = \phi_j \cdot \frac{\prod_{i \in \deptwo(f_j)} (2\kappa_{ij})}{-2B_j}.
\]

Since $f_j$ is Boolean, $\tilde\phi_j \in \{0,1\}$. Replacing $\phi_j$ with $\tilde\phi_j$, we get

\begin{align*}
f_0^{(\ell)}(x) &= \prod_{i \in \rowstwo(Z_\ell)} (x_i-D_i) \prod_{j \in \colstwo(Z_\ell)} \frac{-2B_j}{\prod_{i \in \deptwo(f_j)} (2\kappa_{ij})} \tilde\phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}) \\
&= \frac{\prod_{i \in \rowstwo(Z_\ell)} (-2D_i) \cdot \prod_{j \in \colstwo(Z_\ell)} (-2B_j)}{\prod_{z_{ij} \in \Ztwo_\ell} (2\kappa_{ij})} \cdot\\
&\phantom{=~}\cdot \prod_{i \in \rowstwo(Z_\ell)} \frac{-D_i x_i + 1}{2} \prod_{j \in \colstwo(Z_\ell)} \tilde\phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}).
\end{align*}

If we now negate $B_j,D_i$ then we get

\begin{align*}
f_0^{(\ell)}(x) &= M^{(\ell)} \cdot \prod_{i \in \rowstwo(Z_\ell)} \frac{D_i x_i + 1}{2} \prod_{j \in \colstwo(Z_\ell)} \tilde\phi_j(x^{\sgn}|_{\rowsone(Z_\ell)}) \in \{0, M^{(\ell)}\}, \\
g_0^{(\ell)}(y) &= M^{(\ell)} \cdot \prod_{j \in \colstwo(Z_\ell)} \frac{B_j y_j + 1}{2} \prod_{i \in \rowstwo(Z_\ell)} \tilde\gamma_i(y^{\sgn}|_{\colsone(Z_\ell)}) \in \{0, M^{(\ell)}\},
\end{align*}

\[
M^{(\ell)} = \frac{\prod_{i \in \rowstwo(Z_\ell)} (2D_i) \cdot \prod_{j \in \colstwo(Z_\ell)} (2B_j)}{\prod_{z_{ij} \in \Ztwo_\ell} (2\kappa_{ij})}.
\]

In order to make the functions $f_0^{(\ell)},g_0^{(\ell)}$ Boolean, we define

\begin{align*}
&f_0^{\prime(\ell)} = \frac{2}{M^{(\ell)}} f_0^{(\ell)} - 1, \quad
g_0^{\prime(\ell)} = \frac{2}{M^{(\ell)}} g_0^{(\ell)} - 1, \quad \\
& h'(z) = h\left(z_1,\dots,z_{\ell-1},\frac{M^{(\ell)}}{2}(z_\ell+1),z_{\ell+1},\dots,z_k\right).
\end{align*}

As before, this gives another solution, which has the form of Case 3.

We finish the proof by showing that $h$ maps $\{-1,1\}^k$ to $\{-1,1\}$. Since $f_0$ depends on all inputs, the functions $f_0^{(1)},\dots,f_0^{(k)}$ cannot be constant. Since $g_1,\dots,g_n$ are not constant, it follows that all inputs to $h$ can be achieved by some assignment to the input variables $z_{ij}$. Since $f_0$ is Boolean, it follows that $h$ is Boolean as well.

We can now finally state the main theorem of this work. In this theorem, we remove all assumptions. The proof is immediate from <Ref>.

Let $f_0,\dots,f_m\colon \{-1,1\}^n \to \{-1,1\}$ and $g_0,\dots,g_n\colon \{-1,1\}^m \to \{-1,1\}$ be arbitrary Boolean functions satisfying

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

Let $J \subseteq [m]$ consist of all $j$ such that $f_j$ is non-constant, and let $G_0\colon \{-1,1\}^J \to \{-1,1\}$ be obtained from $g_0$ by fixing the $\overline{J}$-coordinates to the constants $f_j$ for $j \in \overline{J}$. Similarly, let $I \subseteq [n]$ consist of all $i$ such that $g_i$ is non-constant, and define $F_0\colon \{-1,1\}^I \to \{-1,1\}$ analogously.

Let $\tilde J = \dep(G_0)$, and let $\tilde G_0$ be the restriction of $G_0$ to the coordinates in $\tilde J$. Define $\tilde I,\tilde F_0$ analogously.

Then the functions $\tilde F_0$ and $f_j$ for $j \in \tilde J$, together with the functions $\tilde G_0$ and $g_i$ for $i \in \tilde I$, have the form given in <Ref>, and the functions $f_j$ for $j \in J \setminus \tilde J$ and $g_i$ for $i \in I \setminus \tilde I$ are completely arbitrary.

Since <Ref> is tight, this result is tight as well: it describes all Boolean generalized polymorphisms, without any restrictions. In particular, the functions $f_j$ for $j \in J \setminus \tilde J$ and $g_i$ for $i \in I \setminus \tilde I$ are completely unrestricted, as are the values of $f_0,g_0$ which disagree with the constant $f_j,g_i$.