An $m$-ary function that represents all $n$-ary functions

Question

Motivation

It is well-known that any binary operator $*$ on the boolean ring $\{0,1\}$ can be represented using only one of the $\operatorname{NAND}$ and $\operatorname{NOR}$ operators. For example, $$x\rightarrow y=\big((x\operatorname{NOR}x)\operatorname{NOR}y\big)\operatorname{NOR}\big((x\operatorname{NOR}x)\operatorname{NOR}y\big)$$ and \begin{align}x\operatorname{XOR}y&= \Big(\big((p\operatorname{NAND}p)\operatorname{NAND}(q\operatorname{NAND}q)\big)\operatorname{NAND}\big((p\operatorname{NAND}p)\operatorname{NAND}(q\operatorname{NAND}q)\big)\Big) \\&\hphantom{123}\operatorname{NAND}\Big(\big((p\operatorname{NAND}p)\operatorname{NAND}(q\operatorname{NAND}q)\big)\operatorname{NAND}\big((p\operatorname{NAND}p)\operatorname{NAND}(q\operatorname{NAND}q)\big)\Big),\end{align} where $$p=\big(x\operatorname{NAND}(y\operatorname{NAND}y)\big)\operatorname{NAND}\big(x\operatorname{NAND}(y\operatorname{NAND}y)\big)$$ and $$q=\big((x\operatorname{NAND}x)\operatorname{NAND}y\big)\operatorname{NAND}\big((x\operatorname{NAND}x)\operatorname{NAND}y\big).$$ The notation $\rightarrow$ is the implication connective, and $\operatorname{XOR}$ is the exclusive-or operator.

Definitions

Let $S$ be a set and $f:S^m\to S$ is an $m$-ary function (or $m$-ary operator). A valid expression in $f$ is an expression $E(x_1,x_2,\ldots,x_n)$, where $x_1,x_2,\ldots,x_n\in S$ involving only finite iterations of $f$ and using only variables among $x_1,x_2,\ldots,x_n$.

For example, if $m=n=2$ and $0\in S$, $f\big(x_1,f(0,x_2)\big)$ is not a valid expression because there is a constant $0$ that is not in the form of the variables $x_1,x_2$. If $m=2$, $n=1$, $S=\mathbb{R}_{>0}$, and $f(x_1,x_2)=\sqrt{x_1\sqrt{x_2}}$, then this is also not a valid expression because it involves infinite iterations of $f$: $$f\Biggl(x,f\Big(x,f\big(x,f(\ldots)\big)\Big)\Biggr)=\sqrt{x\sqrt{x\sqrt{x\sqrt{\ldots}}}}\ (=x).$$ (However, if you want to represent the identity function $x\mapsto x$ on $S=\mathbb{R}_{>0}$ with the function $f(x_1,x_2)=\sqrt{x_1\sqrt{x_2}}$, this can be done without involving infinite iterations of $f$ like the previous example, i.e., $f\big(f(x,x),x\big)=\sqrt{(x\sqrt{x})\sqrt{x}}=x$.)

For $m=n=3$, this is a valid expression of $f$: $$f\Biggl(f\big(x_1,x_2,f(x_1,x_3,x_2)\big),f\Big(f\big(x_1,f(x_2,x_3,x_1),x_3\big),x_2,x_1\Big)\Biggr).$$ Also, not all variables need to be used. So, for $m=n=2$, $$f\big(x_1,f(x_1,x_1)\big)$$ is still a valid expression of $f$. In the previous example, one can say that this is a valid expression of $f$ with $m=2$ and $n=1$, as well. There can also be more variables than the number of arguments of $f$, that is, if $m=2$ and $n=3$, $$f\big(f(x_1,x_2),f(x_2,x_3)\big)$$ is a valid expression of $f$.

Let $g:S^n\to S$. We say that $g$ is representable by $f$ if there exists a valid expression $E(x_1,x_2,\ldots,x_n)$ of $f$ such that $$g(x_1,x_2,\ldots,x_n)=E(x_1,x_2,\ldots,x_n)$$ for all $x_1,x_2,\ldots,x_n\in S$. For an $m$-ary function $f:S^m\to S$, we say that $f$ is $n$-fulfilling if every $n$-ary function $g:S^n\to S$ is representable by $f$.

Question

For a given non-empty set $S$ and positive integers $m,n$, when does there exist a $n$-fulfilling $m$-ary function $f:S^m\to S$? Does there exist a set $S$ with $|S|\geq 3$ along with a positive integer $m$ such that for some an $m$-ary function $f:S^m\to S$ exists, and for any positive integer $n$, every $n$-ary function $g:S^n\to S$ is representatble by $f$.

Has there been a study on this type of questions? Any reference is greatly appreciated.

Known Results

If $S$ is infinite, then there are only countably many valid expressions of $f$ in $n$ variables, but there are uncountably many $n$-ary functions $g:S^n\to S$. Therefore, such a function $f$ does not exist. Hence, we can assume that $S$ is finite.

If $m=1$, then there exists an $n$-fulfilling function $f:S\to S$ if and only if $|S|=1$ or $\big(n,|S|\big)=(1,2)$. Clearly, the only valid expression of $f$ in any number of variables is of the form $f^k(x)$. Therefore, when $|S|>1$, there can only be one variable, so $n=1$. However, since the permutation group on $S$ is not abelian for $|S|>2$, we must have $|S|=2$ (provided that $|S|>1$).

Of course, if $|S|=1$, then any $m$-ary function $f:S^m\to S$ and any $n$-ary function $g:S^m\to S$ have the same image. So, this case is very trivial. If $|S|=2$, I think that we can identify $S$ as the boolean ring $\{0,1\}$ and use the $\operatorname{NAND}$ or $\operatorname{NOR}$ operators to represent any $n$-ary function $g:S^n\to S$.

For the Bounty Prize

I am willing to award the prize for

1. An example of $(S,m,n)$ with $|S|\geq 3$ and $m\geq 2$ such that there does not not exist an $m$-ary function $f:S^m\to S$ that is $n$-fulfilling, or a proof without an explicit construction that such $(S,m,n)$ exists.

2. An example of $(S,m,n)$ with $|S|\geq 3$ and $m\geq 2$ such that an $m$-ary function $f:S^m\to S$ is $n$-fulfilling, or a proof without an explicit construction that such $(S,m,n)$ exists.

3. Any stronger result than 1. and 2.

Answer 1

There is a universal binary ($m=2$) function for any finite domain.

As in Peter Košinár's answer, take to $S$ be the integers modulo $|S|.$ I assume $|S|\geq 3.$ Define

$$f(x,y)=\begin{cases}x+1&\text{ if $x=y,$}\\ 0&\text{ otherwise.}\end{cases}$$

Some easy gizmos:

• the successor function $s(x)=x+1$ can be defined in terms of $f$ by $s(x)=f(x,x)$
• the constant $0$ can be defined by $f(f(x,x),x)$
• any constant $c$ can be defined by expressions of the form $s(s(\dots s(s(0))\dots)),$ with $c$ applications of $s$ (taking a representative $c\in\{0,1,\dots,|S|-1\}$)

I will give constructions for:

1. the function $e_i:S^1\to S$ that sends $i$ to $1$ and everything else to $0$
2. a function $NOR:S^2\to S$ such that $NOR(0,0)=1$ and $NOR(0,1)=NOR(1,0)=NOR(1,1)=0.$ (It doesn't matter what happens with other inputs.)
3. a function $d:S^{|S|}\to S$ that outputs $c$ if the $c$'th input (counting from $0$) is $1$ and all other inputs are $0.$ For example $d(1,0,0,\dots,0)=0$ and $d(0,0,1,0,0,\dots,0)=2.$ (It doesn't matter what $d$ does to inputs not of this form for any $c.$)

(Mnemonic: "d" and "e" decode and encode, from a one-hot representation.)

The constructions are:

1. Use $e_i(x)=f(s^{|S|-i}(x),0)$ for $i\in\{0,1,\dots,|S|-1\}.$ Here $s^{|S|-i}$ means applying $s$ exactly $|S|-i$ times, effectively adding $|S|-i.$ This works because $s^{|S|-i}(x)=0$ if and only if $e_i(x)=1.$

2. $NOR(x,y)=e_1(f(x,y)).$

3. I will inductively construct functions $d_i:S^i\to S$ such that $d_i(x)=c$ whenever $x$ has a $1$ in position $c$ and zeroes elsewhere. I'll take the base case to be $i=2,$ which is easy: $d_i(x_0,x_1)=1.$ Given a construction for $d_i,$ construct $d_{i+1}$ by $d_{i+1}(x_0,\dots,x_{i+1})=f(d_i(OR(x_0,x_1),x_2,x_3,\dots,x_{i+1}),d_i(x_1,OR(x_0,x_2),x_3,\dots,x_{i+1})),$ where $OR(x,y)=NOR(NOR(x,y),NOR(x,y)).$ Then take $d=d_{|S|}.$

We can now express an arbitrary function $g:S^n\to S$ in three parts: first convert all the inputs to binary using the $n|S|$ expressions of the form $e_i(x_j)$; then use the fact that $NOR$ is universal for binary functions to express each indicator function of whether the output should be $k,$ i.e. the functions $e_k(g(x)),$ in terms of the $e_i(x_j)$; then use $d$ to convert this binary representation of the output of $g$ into the correct output - in notation, $d(g_0(x),\dots,g_{|S|-1}(x))$ where $g_k(x)=e_k(g(x))$ (which can be expressed without $g$ as mentioned previously).

Answer 2

Let $m=4$ and $S:=\mathbb{Z_k}$ of residues modulo $k\geq 3$ (all arithmetical operations will be considered modulo $k$).

We will define $f(x,y,a,b)$ as follows: $$ \begin{equation} f(x,y,a,b)= \begin{cases} (x+1) & \text{if } y=x\\ 0 & \text{if } y=(x+1)\\ a & \text{if } y\not\in\{x,x+1\} \wedge x=0\\ b & \text{if } y\not\in\{x,x+1\} \wedge x\not=0\\ \end{cases} \end{equation} $$

As we will see, this essentially smuggles two unrelated functions under one umbrella and uses the equality of first two arguments as the distinguishing factor.

The first two lines of the definition of $f$ allow us to use any single variable to produce explicit constants: $$\begin{array}{lll} 0 & = & f(x,f(x,x)) \\ 1 & = & f(0, 0) = f(f(x,f(x,x)), f(x,f(x,x))) \\ & \ldots &\\ (k-1) & = & f(k-2, k-2) \\ \end{array}$$

We can also implement addition of a constant to variable: $$\begin{array}{lll} x+1 & = & f(x,x) \\ x+2 & = & f(x+1, x+1) = f(f(x,x),f(x,x))\\ & \ldots &\\ \end{array}$$

Furthermore, since we are working modulo $k$, so we can also subtract constants too (subtracting $1$ is equivalent to adding $(k-1)$).

Since $|S|\geq 3$, the value $(x+2)$ is always distinct both from $x$ and $(x+1)$ so an expression of the form $f(x,(x+2),a,b)$ can serve as the if-then-else primitive: $$ITE(x,a,b) := f(x, x+2, a, b)$$

This, in turn, gives us the array indexing primitive (given an array, it returns $x$-th member of the array $a$ or the last element if $x$ is too big): $$\begin{equation} SELECT(x, [a_0, a_1, \ldots, a_t])= \begin{cases} a_0 & \text{if }t=0\\ ITE(x, a_0, SELECT\left(x-1, [a_1, \ldots, a_t])\right) & \text{otherwise}\\ \end{cases} \end{equation}$$

Note that the constants, addition/subtraction, if-then-else and select primitives are all just syntactic sugar and simply abbreviate a much longer valid expression.

Now, any unary function $g(x_1)$ can be represented as a valid expression; after all, a unary function is fully defined by the array of its values: $$g(x_1)=SELECT(x_1, [g(0),g(1),\ldots,g(k-1)])$$

Functions of higher arity just involve nesting of selects: $$\begin{array}{llll} g(x_1,x_2) & = & SELECT(x_1, [ & \\ & & & SELECT(x_2, [g(0,0), g(0,1), \ldots, g(0,k-1)]),\\ & & & SELECT(x_2, [g(1,0), g(1,1), \ldots, g(1,k-1)]),\\ & & & \ldots \\ & & & SELECT(x_2, [g(k-1,0), g(k-1,1), \ldots, g(k-1,k-1)])\\ & & ])\\ \end{array}$$

Generalization to any higher dimension is straightforward.

Thus, we have shown that $m=4$ suffices for any $|S|\geq 3$ and one $f$ can be used for any $n$ (note that the definition of $f$ depends on $S$, so although our definition of it works "uniformly" for any $|S|$, it is not a single function $f$ for all $S$; just for all $n$).

This leaves the question open for $m=2$ and $m=3$.