Which functions can be obtained by applying these syntactic rules?

Question

Here's an intentionally weird question for ye all.

Start off with the expression $x$.

Rule 0. We're allowed get a new expression from an old expression by replacing a subexpression with an $\mathbb{R}$-affine combination of itself. For instance, from $x$ we can get the expression $$\frac{1}{2}x+\frac{1}{2}x.$$ From there we can get $$\frac{1}{2}x+\left(\frac{1}{3}\frac{1}{2}x+\frac{2}{3}\frac{1}{2}x\right).$$

Rule 1. We're allowed to get a new expression from an old expression by replacing some instance of $x$ with $x+1$. For instance, from $$\frac{1}{2}x+\frac{1}{2}x$$ we can get $$\frac{1}{2}(x+1)+\frac{1}{2}x.$$

Let $\cal E$ denote the set of expressions obtainable in this way. (And sorry for being so vague.)

Let $\mathcal{F}$ denote the set of functions $\mathbb{R} \rightarrow \mathbb{R}$ definable as $\lambda x.E$ for some $E \in \cal{E}$.

Question. Which functions are in $\mathcal{F}$?

Note that, since $$\left[\frac{1}{2}(x+1)+\frac{1}{2}x\right]\in \cal{E},$$ hence $$\left[\lambda x.x+\frac{1}{2}\right] \in \mathcal{F}.$$

More generally, since $$\left[a(x+1)+(1-a)x\right] \in \cal E,$$ hence $$\lambda x.(x+a) \in \cal F.$$ So the question is really whether we can get anything else through this process. I suspect the answer is "no", but I'm VERY far from having a proof of this.

Answer 1

Let's represent your syntactic expressions as finite binary trees such that:

1. Each node is either a leaf (no children) or a branch (two children).
2. Each leaf is labeled $x$ or $1$.
3. The two edges out of each branch are labeled by real numbers $\alpha$ and $\beta$.

Call such a tree a goblin tree.

Now there is a natural "expansion" function $f$ from goblin trees to the affine functions $\{ax + b\mid a,b\in \mathbb{R}\}$, defined recursively. If the root of $T$ is a leaf, $f(T)$ is $x$ or $1$, as it's labeled. If the root of $T$ is a branch with edges labeled $\alpha$ and $\beta$ leading to subtrees $T_1$ and $T_2$, then $f(T) = \alpha f(T_1) + \beta f(T_2)$.

Now your rules correspond to simple operations on goblin trees:

• Rule 0 takes a subtree $S$ of $T$ and replaces $S$ with a branch node with an edge labeled $\alpha$ leading to a copy of $S$ and an edge labeled $\beta$ leading to another copy of $S$, such that $\alpha+\beta = 1$.
• Rule 1 takes a leaf labeled $x$ and replaces it with a branch node with an edge labeled $1$ leading to a leaf labeled $x$ and an edge labeled $1$ leading to a leaf labeled $1$.

Let $L$ be the goblin tree consisting of a single leaf node labeled $x$. The result of applying Rule 0 or Rule 1 to a goblin tree is certainly a goblin tree, so every tree generated from $L$ by applications of Rule 0 and Rule 1 certainly corresponds (via $f$) to an affine function. It remains to show that we only get affine functions of the form $x + b$.

Given a goblin tree $T$, let $X(T)$ be the set of leaves of $T$ labeled $x$. To each $l\in X(T)$, we can assign a coefficient $a_l$, the product of the labels on the edges along the unique path from the root to $l$. It is straightforward to prove by induction, using the recursive definition of $f$, that the coefficient of $x$ in $f(T)$ is $\sum_{l\in X(T)} a_l$.

Now the coefficient of $x$ in $f(L)$ is $1$. Let's check that Rule 0 and Rule 1 leave $\sum_{l\in X(T)} a_l$ unchanged:

• If $T'$ is obtained from $T$ by Rule $0$ applied to a subtree $S$, then every $l\in X(T)$ which is in $S$ corresponds to two leaves $l_1$ and $l_2$ in $X(T')$, but $a_{l_1} = \alpha a_l$ and $a_{l_2} = \beta a_l$, so $a_{l_1}+a_{l_2} = a_l$.
• If $T'$ is obtained from $T$ by Rule $1$ applied to a leaf $l\in X(T)$, then $l$ corresponds to a single leaf $l'\in X(T')$, and $a_{l'} = 1\cdot a_l = a_l$.

Answer 2

$\cal E$ comprises the affine functions over $x$, i.e. the functions of the form $x \mapsto \alpha + \beta x$ for $\alpha, \beta \in \Bbb{R}$. You can prove this by induction over the number of applications of the rules (and it will simplify the induction if you prove a more general statement involving an arbitrary number of variables $x_1, x_2 \ldots$ to make rule 1 easier to state and work with).