Generalized polymorphisms

Abstract

We find all functions $f_0,f_1,\dots ,f_m:\{0,1{\}}^n\to \{0,1\}$ and $g_0,g_1,\dots ,g_n:\{0,1{\}}^m\to \{0,1\}$ satisfying the following identity for all $n\times m$ matrices $(z_{ij})\in \{0,1{\}}^{n\times m}$: \[ f_0(g_1(z_{11},\dots,z_{1m}),\dots,g_n(z_{n1},\dots,z_{nm})) = g_0(f_1(z_{11},\dots,z_{n1}),\dots,f_m(z_{1m},\dots,z_{nm})). \] Our results generalize work of Dokow and Holzman (2010), which considered the case $g_0=g_1=\cdots =g_n$, and of Chase, Filmus, Minzer, Mossel and Saurabh (2022), which considered the case $g_0\ne g_1=\cdots =g_n$.

arXiv comment19 pages