In trying to answer (my own) recent question I'm looking for the name for the following type of self-composition of a function.

  • Let's define an infinite set of fixed coefficients $\{a_0,a_1,...\}$
  • Let us assume the domain for the function in question $ \mathbb N $
  • Let $g(n)$ be some simple function on $n$, say for example $g(n)=n$

Then let us define the self-composing of $f(n)$ with iteration-index denoted as $f^{\circ h}(n)$ by the following scheme:

$$ \begin{array} {} f^{\circ 0}(n) &= g(n) \\ f^{\circ h}(0)&=0 \\ f^{\circ h+1}(n) &= a_0 f^{\circ h}(n) + a_1 f^{\circ h}(n-1) + ... + a_{n-1} f^{\circ h}(1)\\ \end{array}$$

Example: if $a_0=a_1=...=a_k=...=1 $ and $g(n)=n$ then we have for $f^{\circ 1}(n)$ the sum-of-natural-numbers up to $n$, for $f^{\circ 2}(n)$ the sum-of-sums and so on.

Q: Is there a canonical name for this type of self-composition?

It's surely not "iteration"; I looked for "convolution" but this seems to be different - I'm without an idea what other term I could look for.


This can be written in terms of convolutions: For two functions $u,v\colon\mathbb{Z}\rightarrow\mathbb{R}$ you can define the convolution product formally as $$ u*v(k)=\sum_{i\in\mathbb{Z}}u(i)v(k-i). $$ In general this series does not converge in any sense, but assuming that $u(j)=v(j)=0$ for $j<0$, it is actually a finite sum for every $k\in\mathbb{Z}$ and for $k<0$ we even have $u*v(k)=0$. This means that the convolution restricts to product on $R:=\{u\colon\mathbb{Z}_{\ge0}\rightarrow\mathbb{R}\}$, in the sense that it makes $(R,+,*)$ a commutative ring. (Which is ismorphic to $\mathbb{R}[[x]]$, the ring of formal power series.)

Now in your case you have some $a\in R$ defined by $a(j)=a_j$ and start with an arbitrary $g\in R$. Then $f^{\circ 1}(k)=a*g(k)$ for $k\ge 1$ and $f^{\circ0}(0)=0.$ But if $v\in R$ satisfies $v(0)=0$ also $a*v(0)=0$, hence from there on it is just convolution: $f^{\circ 2}=a*f^{\circ 1}$ and so on. If you aready start with a function $g\in R$ with $g(0)=0$, then $$ f^{\circ h}=(a*\dots*a)*g=:a^{*h}*g. $$

  • $\begingroup$ Ah, good so! But can we go so far to say directly: "this is a self-convolution" (instead of saying "we can express this in terms of convolution")? I thought it might exist some technical term which is associated to this special form... $\endgroup$ – Gottfried Helms Apr 15 '18 at 9:57
  • $\begingroup$ Well, only $a$ gets convoluted with itself, not $g$. And yes there is a term for that, $a^{*n}=a*\dots*a$ (n-times) is called the $n$-fold convolution power. $\endgroup$ – Jan Bohr Apr 15 '18 at 13:44
  • $\begingroup$ Jan, thanks for your answer. I've looked at the wp-entry - difficult for me to "decode" .. so I'm not yet really convinced that "convolution power" is the best technical term to describe that self-composition. But I've not yet found a "better" one and also no one else stepped in so I'll "accept" your answer to close-the-case and at least have your suggestion as a guide how to look further around. $\endgroup$ – Gottfried Helms Apr 18 '18 at 8:55
  • $\begingroup$ You're welcome. Though I don't quite understand why you insist on the term "self-composition". Given any function $F\colon S\rightarrow S$ (on a set $S$), the self compositions would be $F\circ F, F\circ F \circ F$ and so on and I would denote this $F^{\circ n}$. This does not happen at the level of functions in $R$, but rather on the level of functions acting on $R$, specifically you could put $F\colon R\rightarrow R, F(u):=a*u$, then $F^{\circ n}(u) = a^{*n}*u$. $\endgroup$ – Jan Bohr Apr 18 '18 at 9:11
  • $\begingroup$ The reason I continue so far to use the term "self-composition" is that I understand it in a more (or even most) general form as "any polynomial or series where the function is reintroduced as argument " (or so...) Of course to avoid infinite recursion we need the function at varying arguments (or different powers of the function) at the coefficients of the polynomial/series. This is basically my intuitive understanding of such a general term "self-composition" - perhaps there is some triviality which makes this understanding messy and I didn't notice it yet... I'd try to change it then... $\endgroup$ – Gottfried Helms Apr 18 '18 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.