Nested expressions as compositions of functions?

[Stephen Tashi]

TL;DR Summary

How can we express nested expressions as a compositions of functions?

How can we write (finite) nested expressions as compositions of functions?

For example (using Horner's technique), consider:
$P(x) = 3 + 2x + 4x^2 + 6 x^3 = 3 + x(2 + x(4 + x(6) ) )$

The way I see to do it is to use functions of two variables.

$f_3(x,y) = 6$
$f_2(x,y) = 4 + xy$
$f_1(x,y) = 2 + xy$
$f_0(x,y) = 3 + xy$

$P(x) = f_0(x,(f_1(x,f_2(x,f_3(x,x)))))$

It seems unnatural to introduce two variables in order to get a nested expression in one variable, but I see no way around it.

 

[fresh_42]

If two variables are necessary, you can still consider functions $f\times g \, : \,(x,y) \longrightarrow h(f(x),g(y)$ but this isn't necessary here. We have only scalar multiples $M_c$ and additional shifts $A_s$. Every $f_i$ can be written as $f_i(x)=\left(A_{s_i} \circ M_{c_i} \right)(x) := s_i + c_ix$. Hence we have
$$
(f_j \circ f_i)(x)=(A_{s_j}\circ M_{c_j}\circ A_{s_i}\circ M_{c_i})(x)= (A_{s_j}\circ M_{c_j}\circ A_{s_i})(c_ix)=(A_{s_j}\circ M_{c_j})(s_i+c_i x)=(A_{s_j})(c_j(s_i+c_ix)x)=s_j+ (c_j(s_i+c_ix)x)
$$
This shows, that you parameterized the functions, not the variable. Of course any $A_s\circ M_c$ can be written as affine linear function $L(s,c)(x)=s+cx$ which gives you one parameter $(s,c)\in \mathbb{R}\times \mathbb{R}^\times$ instead of two.

 

[Stephen Tashi]

Every $f_i$ can be written as $f_i(x)=\left(A_{s_i} \circ M_{c_i} \right)(x) := s_i + c_ix$.

I don't understand what definition you are using for the composition of functions. For example, if $f_1(x) = 3 + 5x$ and $f_2(x) = 4 + 6x$ then $f_1(f_2(x)) = 4 + 6( 3 + 5x) = 22 + 30x$ and I don't get any $x^2$ term.

 

[fresh_42]

You're right, what a stupid mistake me made. We would need an additional operator $R_x\, : \,p(x)\longrightarrow p(x)\cdot x$ to increase the powers of $x$ - just as many as there are (ring) operations: addition, scalar multiplication and normal multiplication. We could define $R_{q(x)}(p(x))=p(x)\cdot q(x)$ but that would overload the index.