# Chain rule for discrete/finite calculus

In the context of discrete calculus, or calculus of finite differences, is there a theorem like the chain rule that can express the finite forward difference of a composition $∆(f\circ g)$ in simplified or otherwise helpful terms?

It's probably not possible for a general function, but it might be possible with some restrictions. I'm also interested in the reverse -- a substitution rule for indefinite sums, if such exists. Or, to be honest, in any strong wealth of technical information related to this topic.

-

Provided the values of $g$ lie in the domain of $f$ and $\Delta g(n)$ is an integer, you have the obvious rule $$\Delta(f\circ g)(n)=\sum_{d=0}^{\Delta g(n)-1}\Delta f\bigl(g(n)+d\bigr),$$ where the summation must be interpreted as a sum of negated terms in case $\Delta g(n)<0$, similarly to integrals whose upper limit is lower than their lower limit. The formula is probably not very useful though.

Added: I just found out that for such summations that might go in the wrong direction, the book Concrete Mathematics uses the notation $$\Delta(f\circ g)(n)=\sum\nolimits_0^{\Delta g(n)}\Delta f\bigl(g(n)+i\bigr)\,\delta i$$ (the factor $\delta i$ is always $1$, but serves to indicate the sum is over $i$; also the upper bound, here $\Delta g(n)$, is omitted from the range of $i$) to emphasize even more the analogy with an integral.

-
I think I might not understand your formula properly. How can you do this if $∆g$ is not constant? You would need to perform the summation on the arbitrary points $Δg(0),Δg(1),...$. –  GreĝRos Nov 12 '12 at 15:27
@anon Yes, I wrote the right parenthesis in the wrong place; corrected now. Thank you! –  Marc van Leeuwen Nov 12 '12 at 18:16
Ah I'm sorry, I misunderstood the intent at first. I understand. –  GreĝRos Nov 12 '12 at 18:20
Thanks! I'm sorry for the misunderstanding at first. You can actually make the sum from $g(n)$ to $g(n+1)$, or to $g(n)+Δg$, thus removing the inner function from the sum itself. Unfortunately, I'm not sure how to simplify it. It just evaluates back to $f(g(n)+Δg)-f \circ g(n)$, since Δf is going to just become f anyway. I've played around with a similar notion that also applies if Δg is not an integer; to a derivative and an integral. However, it all just ends up being similar to the normal formula. –  GreĝRos Nov 12 '12 at 18:42

While I doubt I'll ever find any general formulas, I've noticed that you can derive such a formula from many functions. For example, for $sin(x)$ we have: $$\sin{f(x)}⇒Δ\big({\sin{f(x)}}\big)=\sin{f(x+1)}-\sin{f(x)}=\sin{\big(f(x) + Δf(x)\big)}-\sin{f(x)}=$$ Using a trig identity: $$\sin{\big(\frac{1}{2}Δf(x)\big)}·\cos{\big(f(x)+\frac{1}{2}∆f(x) \big)}$$ For $2^{x}$, the discrete analog to $e^{x}$: $$Δ2^{f(x)}=2^{f(x)+Δf(x)}-2^{f(x)}=2^{f(x)}(2^{∆f(x)}-1)$$

While there is no chain rule to work with in discrete calculus, it seems that finding the differences (and hence, the discrete integrals) is somewhat easier.

-
See my answer, there is a general formula to the chain rule! and what you have is a special case of it! But... unless working with differences of step size 0 (aka the derivative) it isn't incredibly useful –  frogeyedpeas Mar 2 at 17:52

You may go with polynomials over $\mathbf F_2$, the smallest finite field and one of the representations of Boolean functions. Note, that in $\mathbf F_2$ for any $x$ (i.e. $1$ or $0$) the following relations hold:

$$x^2 = x, \quad x + x = 0.$$

The derivative is defined as:

$$\left(D \, f \right)(x) = f(x+1) - f(x)$$

which is also a finite difference. All the usual derivative properties, including the chain rule, are fulfilled. Indeed one can easily show it by studying every possible $f$ --- all the two of them: identity $x \mapsto x$ and negation $x \mapsto x+1$.

Well, considering one-variable functions $\mathbf F_2 \to \mathbf F_2$ is not very interesting and it is better to proceed with multivariable calculus on $\mathbf F_2^N = \underbrace{\mathbf F_2 \times \ldots \times \mathbf F_2}_N$. The directional derivative is defined as

$$\left(D_\boldsymbol u \, g \right)(\boldsymbol x) = g(\boldsymbol x+ \boldsymbol u) + g(\boldsymbol x)$$

where

$$g : \mathbf F_2^N \to \mathbf F_2, \quad \boldsymbol x, \boldsymbol u : \mathbf F_2^N$$

and $+$ is defined as component-wise addition:

$$\boldsymbol x + \boldsymbol u = \left(x_1 + u_1, \ldots , x_N + u_N \right).$$

The chain rule for the above g and $f : \mathbf F_2 \to \mathbf F_2$ is fulfilled:

$$\left(D_\boldsymbol u \; f \circ g \right)(\boldsymbol x) = (D_\boldsymbol u \; f) \, (g(\boldsymbol x)) \cdot (D_\boldsymbol u g)(\boldsymbol x),$$

which again is possible to prove by considering every possible $f$. At least this is how I was able to prove it, and I am not in anyway a mathematician. Unfortunately, a quick search over Google books reveals little (nothing?) on the chain rule for boolean functions. As for me I used "Boolean Functions in Coding Theory and Cryptography" by O. A. Loginov, A. A. Salnikov, and V. V. Yashchenko for the introduction to boolean functions, but again it does not go into the chain rule.

I would appreciate if anyone would point me some books or articles on the topic of derivatives of boolean functions, especially when one deals with functions of the type $\mathbf F_2^N \to \mathbf F_2^M$.

-
If you have a question, it is probably better to ask it in a question than in an answer. –  Hurkyl May 21 '14 at 9:00

I had engineered a solution a little while back!

let

$$D_{w,x}[f(x)]= \frac{f(x+w)-f(x)}{w}$$

Then the question amounts to finding a closed form to

$$D_{w,x}[f(g(x))] = \frac{f(g(x+w)) - f(g(x))}{w}$$

We note this can be rewritten as:

$$\frac{f(g(x+w)) - f(g(x))}{w} = \frac{f \left( g(x) + w* \frac{g(x+w) - g(x)}{w} \right) - f(g(x))}{w}$$

$$= \frac{f \left( g(x) + w* D_{w,x}[g(x)] \right) - f(g(x))}{w}$$

From here it becomes clear that

$$D_{wD_{w,x}[g(x)],g]}[f(g)] = \frac{f \left( g(x) + w* D_{w,x}[g(x)] \right) - f(g(x))}{wD_{w,x}[g(x)]}$$

Thus:

$$D_{w,x}[g(x)]D_{wD_{w,x}[g(x)],g]}[f(g)] = \frac{f \left( g(x) + w* D_{w,x}[g(x)] \right) - f(g(x))}{w} = D_{w,x}[f(g(x))]$$

This chain rule however is very complex, as it involves now variable step size being involved in the finite difference itself. But for the sake of completeness, here it is!

Furthrmore its clear that as the step size $w$ tends to 0. You determine that

$$D_{w,x}[g(x)]D_{wD_{w,x}[g(x)],g]}[f(g)] \rightarrow D_{0,x}[g(x)]D_{0*D_{0,x}[g(x)],g}[f(g)] \rightarrow D_{0,x}[g(x)]D_{0,g}[f(g)]$$

Which is the standard chain rule from calculus

-