MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 added 2473 characters in body; added 18 characters in body

UPDATE: OK, I found an ad hoc trick to encode constants, again working on the natural numbers for simplicity. The first observation is that one never wants to have a fixed point $n$ where $n \star n = n$, as then any binary operation formed by composition with $\star$ must always map this fixed point to itself. So we do the next best thing, which is to enforce

$$ n \star n := 0$$for non-zero n, and$$ 0 \star 0 := 1$$(say). So $n \star n$ is always going to be either 0 or 1. Furthermore, if $n \star n$ is zero, then $(n \star n) \star (n \star n)$ is one, and if $n \star n$ is one, then $(n \star n) \star (n \star n)$ is zero. Hence if we then enforce$$ 0 \star 1 = 1 \star 0 = 2$$then we have the identity$$ ((n \star n) \star (n \star n)) \star (n \star n) = 2$$for all n, which allows us to define the constant 2 as a composition word from an arbitrary input n. If we then enforce$$ 0 \star 2 = 1 \star 2 := 3$$$$ 2 \star 0 = 2 \star 1 := 4$$then we can define the constants 3 and 4 also, since $3 = (n \star n) \star 2$ and $4 = 2 \star (n \star n)$. If we then enforce$$ 2 \star 3 := 5; 2 \star 4 := 6; 3 \star 2 := 7; 3 \star 4 := 8; 4 \star 2 := 9; 4 \star 3 := 10$$then we have now made all the constants from 5 to 10 definable, with no constraints as yet as to how $\star$ acts on these constants, other than to annihilate the diagonal ($5 \star 5 = 0$, etc.).

Now we need shift operators, say $f(n) := n+11$ and $g(n) := \max(n-11,0)$, to make room for all the constants that have been created. Encoding $g$ is easy, e.g. we can enforce$$ 5 \star n := g(n)$$for all $n$, as this does not conflict with the existing requirement that $5 \star 5 = 0$. Encoding $f$ is slightly trickier. We can write $f$ as a composition $f = h \circ k$, where $k: {\bf N} \to {\bf N}$ is an injective "Hilbert's hotel" map that maps $6$ to $0$ and avoids $7$ in the range, and $h: {\bf N} \to {\bf N}$ is such that $h(g(n)) = n+11$ for all $n$, and $h(7)=0$. Then we can enforce$$ 6 \star n := k(n)$$$$ 7 \star n := h(n)$$and $f(n)$ is then $f(n) = 7 \star ( 6 \star n )$.

Finally, we can encode pairing and coordinate functions as before:$$ 8 \star n := c_1(n)$$$$ 9 \star n := c_2(n)$$$$ n \star m := \pi( g(n) + g(m), g(n) * g(m) )$$for $n,m \geq 11$, where we choose the pairing function $\pi$ to only take values $11$ and greater to avoid collision. Then we can recover addition and multiplication as before.
show/hide this revision's text 2 added 341 characters in body; deleted 150 characters in body; edited body

With constants, the answer to Q1 is "yes". Let me work on the natural numbers ${\bf N} = \{0,1,2,\ldots,\}$ for notational simplicity(the integer case can be handled by a more complicated version of the same idea, using a few more unary functions to handle the sign). The idea is to identify ${\bf N}$ with the shifted naturals $4 + {\bf N}$ using the shift function $f(n) := n+4$ and its partial inverse $g(n) := \hbox{max}(n-4,0)$, and by using the exponential some pairing function $e(n) := 2^n$ and partial inverse \pi: {\bf N}^2 \to {\bf N}$ that is inverted by coordinate functions $l(n) c_1, c_2: = \hbox{max}(\lfloor \log_2 n {\bf N} \rfloor,0)$ to encode addition in terms of multiplication and unary functions {\bf N}$ (the thus $(n,m) = (c_1(\pi(n,m)), c_2(\pi(n,m))$ for all $n,m$). The point being is that the shift creates some "room" in which to store the unary functions)functions. More precisely, define

$$0 \star n := f(n)$$ $$1 \star n := g(n)$$ $$2 \star n := e(n)$$ c_1(n)$$ $$3 \star n := l(n)$$c_2(n)$$

for any n, and

$$n \star m := \pi( g(n) + g(m), g(n) * g(m)$$g(m) )$$

for $n,m \geq 4$. Then

$$ n * + m = c_1( f(n) \star f(m)$$ f(m) )$$ and $$ n + * m = lc_2( e(nf(n) * e(m\star f(m) )$$ and so one can write both multiplication and addition in terms of composition operations.

Clearly one can make the same idea work on the integers after placing them in one-to-one correspondence with the natural numbers (which distorts the addition and multiplication operations, but no actual properties of these operations were needed in the above construction).

I would imagine that some clever ad hoc trick would allow one to simulate constants such as 0,1,2,3, for instance by designing the $\star$ operation so that $n \star n$ is usually 0, though I don't see how to simulate four separate constants without using branching, which presumably is not allowed in this exercise.

show/hide this revision's text 1

With constants, the answer to Q1 is "yes". Let me work on the natural numbers ${\bf N} = \{0,1,2,\ldots,\}$ for notational simplicity (the integer case can be handled by a more complicated version of the same idea, using a few more unary functions to handle the sign). The idea is to identify ${\bf N}$ with the shifted naturals $4 + {\bf N}$ using the shift function $f(n) := n+4$ and its partial inverse $g(n) := \hbox{max}(n-4,0)$, and using the exponential function $e(n) := 2^n$ and partial inverse $l(n) := \hbox{max}(\lfloor \log_2 n \rfloor,0)$ to encode addition in terms of multiplication and unary functions (the point being that the shift creates some "room" in which to store the unary functions). More precisely, define

$$0 \star n := f(n)$$ $$1 \star n := g(n)$$ $$2 \star n := e(n)$$ $$3 \star n := l(n)$$

for any n, and

$$n \star m := g(n) * g(m)$$

for $n,m \geq 4$. Then

$$ n * m = f(n) \star f(m)$$ and $$ n + m = l( e(n) * e(m) )$$ and so one can write both multiplication and addition in terms of composition operations.

I would imagine that some clever ad hoc trick would allow one to simulate constants such as 0,1,2,3, for instance by designing the $\star$ operation so that $n \star n$ is usually 0, though I don't see how to simulate four separate constants without using branching, which presumably is not allowed in this exercise.