# 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),...$. Nov 12, 2012 at 15:27
• @anon Yes, I wrote the right parenthesis in the wrong place; corrected now. Thank you! Nov 12, 2012 at 18:16
• Ah I'm sorry, I misunderstood the intent at first. I understand. Nov 12, 2012 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. Nov 12, 2012 at 18:42

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(x)}[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(x)}[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(x)}[f(g)] \rightarrow D_{0,x}[g(x)]D_{0*D_{0,x}[g(x)],g(x)}[f(g)] \rightarrow D_{0,x}[g(x)]D_{0,g(x)}[f(g)] = g'(x)\cdot f'(g(x))$$

Which is the standard chain rule from calculus

• I made a correction in your answer. I hope it's okay! Anyway: Thanks for your awesome answer ;-) Have you already found any references where this chain rule is already used or proved in the literature, yet?! Sep 28, 2015 at 21:11
• Thank you! i haven't seen it in literature, but it's elementary enough of a derivation. You can expand it out via the definition, and the terms cancel to what it should be. The only reason that isn't rigorous is since you may be dividing by zero, if you use a functional step size. Dealing with that may be hairy so word of warning if that's the footing you want Sep 29, 2015 at 0:56
• Here's a paper I had whipped up some time back covering a lot of the ideas: vixra.org/abs/1502.0152 Sep 29, 2015 at 0:59

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 Mar 2, 2015 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.
– user14972
May 21, 2014 at 9:00

The difference quotient of the composition of two functions is found as the product of the two difference quotients; i.e., for any function $x=f(t)$ defined at two adjacent nodes $t$ and $t+\Delta t$ of a partition and any function $y=g(x)$ defined at the two adjacent nodes $x=f(t)$ and $x+\Delta x=f(t+\Delta t)$ of a partition, we have the difference quotients satisfy, provided $\Delta x\ne 0$, $$\frac{\Delta (g\circ f)}{\Delta t}(c)= \frac{\Delta g}{\Delta x}(f(c)) \cdot \frac{\Delta f}{\Delta t}(c),$$ where $c$ is the edge of the partition.

• It's a pretty good answer, but as you are posting 5+ years after the Question was asked, you should compare the information in previous Answers (esp. the Accepted Answer) with what you want to share. Mar 24, 2018 at 14:32

Here's a novel take on the problem and a really elegant way to see what the "natural" chain rule is for the discrete derivative.

First, we'll assume all of our functions are polynomials. It isn't that hard to extend to analytic functions, being essentially "infinite-degree polynomials", but we'll just look at polynomials now to keep it simple.

Then the chain rule of the usual derivative is really derived from the product and sum rules. Given only those two things, we can determine the chain rule.

One really elegant way to do this is to use the algebra of dual numbers, which are of the form $$a + b \epsilon$$, with $$\epsilon^2 = 0$$. Dual numbers enable a kind of "algebraization of calculus," which is typically called "automatic differentiation." Most functions which can be extended to the complex plane can be extended to the dual plane in a similarly natural way, and in general, for any polynomial (or analytic function) $$f(x)$$, we have

$$f(x + k \epsilon) = f(x) + f'(x) k \epsilon$$

simply due to the way that dual numbers work. If you haven't tried this, play around with it, because it is almost magic. You can plug $$x + \epsilon$$ into basically any polynomial or Taylor series, multiply things through and cancel out the $$\epsilon^2$$ terms, and it will automagically compute the derivatives of huge chains of compositions for you.

The reason this works so well is that the notion of $$\epsilon^2$$ being zero causes the product rule to naturally flow from the properties of the algebra. For instance, assuming you have two dual numbers of the form $$f(x) + f'(x) \epsilon$$ and $$g(x) + g'(x) \epsilon$$, their product will be

$$(f(x) + f'(x) \epsilon)(g(x) + g'(x) \epsilon) \\ = f(x)g(x) + (f'(x)g(x) + f(x)g'(x))\epsilon + (f'(x)g'(x))\epsilon^2\\ = f(x)g(x) + (f'(x)g(x) + f(x)g'(x))\epsilon$$

So you can see that the dual part of the product is indeed the derivative of the product of the two original functions. As a result of this, it's pretty easy to verify that this property, along with the linearity of derivative addition, gives the correct "chain rule" when composing functions (and it isn't that much harder to extend to analytic functions).

The discrete derivative has a slightly different product rule, and thus a different chain rule. To see this, we'll define a "generalized discrete derivative" with step size $$h$$ as the following:

$$f'_h(x) = \frac{f(x+h) - f(x)}{h}$$

Both the forward and backward difference are instances of this derivative, as is the usual true derivative:

$$f'_1(x) = f(x+1) - f(x) \\ f'_0(x) = f'(x) \\ f'_{-1}(x) = f(x) - f(x-1)$$

The "correct" product rule for this, although it's a little tedious to derive, happens to be:

$$[fg]'_h(x) = f(x)g'_h(x) + f'_h(x)g(x) + f'_h(x)g'_h(x) h$$

which is the same as the usual product rule, but with an extra $$f'_h(x)g'_h(x) h$$ term.

But now we have something particularly interesting. Let's try to use this to make a new "discrete dual algebra" which can perform "automatic discrete differentiation". Instead of an element $$\epsilon$$, we'll have an element $$\epsilon_h$$. So basically, let's assume that we already have two "discrete dual numbers" of the form $$f(x) + f'_h(x) \epsilon_h$$ and $$g(x) + g'_h(x) \epsilon_h$$, and we want to use this information to compute the discrete directive of their product as the "discrete dual" part of their product. How would the algebra need to work to make this happen?

$$(f(x) + f'(x) \epsilon_h)(g(x) + g'(x) \epsilon_h) \\ = f(x)g(x) + (f'(x)g(x) + f(x)g'(x))\epsilon_h + (f'(x)g'(x))\epsilon_h^2$$

It turns out the magic thing we want is to declare the relation $$\epsilon_h^2 = h \epsilon$$, which gives the correct expression for the product rule as the discrete dual part:

$$f(x)g(x) + (f'(x)g(x) + f(x)g'(x) + f'(x)g'(x) h)\epsilon_h$$

and this really does work. You can go play around with this for any polynomial you want and it will always give the right result: $$p(x+\epsilon_h) = p(x) + p'_h(x)\epsilon$$.

And now that we have linearity and our product rule, we can compute the correct chain rule for any polynomial. This post has gotten pretty long already, and deriving this turns out to involve a bunch of tedious algebra, so I will just skip to the end. As a first step, you have this result, for any polynomial (or again, analytic) function $$f(x)$$

$$f(x + k\epsilon_h) = f(x) + f'_{kh}(x) \, k \, \epsilon_h$$

And thus, we have our generalized chain rule for any generalized discrete derivative:

$$f(g(x + \epsilon_h)) = f(g(x) + g'_h(x) \epsilon_h) \\ = f(g(x)) + \left(f'_{g'_h(x)\cdot h}(g(x)) \cdot g'_h(x) \right) \epsilon_h$$

which is fairly elegant. It's very similar to the original chain rule, and indeed as $$h \to 0$$ you get the original chain rule. The interesting thing to note here is that the step size changes for what would normally be the $$f'(g(x))$$ term: instead of having a step size of $$h$$, it now has a step size of $$g'_h(x) \cdot h$$. But no problem.

Lastly, it turns out that all of these "discrete dual number" algebras are really just the same algebra, which is the algebra of "split complex numbers." The split-complex numbers are isomorphic to $$\Bbb R^2$$ with pointwise product and sum, and to represent our "discrete dual numbers" in this algebra, we send $$a + b \epsilon_h$$ to $$[a,a] + b[h,0] = [a+bh, a]$$. (Note that the one exception is with $$h=0$$, where you get the dual numbers instead.)

• This is the same chain rule that @SidharthGhoshal had above, although derived in a a pretty hip, rocket science-ish machine learning autodiff way. :) Feb 14 at 6:04
• Interesting. So, how would this chain rule (and derivative rule) look in terms of split-complex numbers? Jun 27 at 14:49
• Looks like $\epsilon_1=1/2+j/2$. Thus, $f(x+1/2+j/2)=f(x)+ (1/2+j/2)\Delta f(x)$, yes? Jun 27 at 14:54
• Would not $f(x+1)=f(x)+\Delta f(x)$ be a simplier formula? Jun 27 at 15:13
• I really like how you used first principles with first order expansion for this. When I had derived the chain rule I basically got very lucky with staring at my target expression and just brute force trying and guessing what kind of forms give me the expression I want. Eventually once I had the right thing it could be verified. Your approach seems a lot more intuitive to find since it asks "where would a chain rule manifest itself?" and you just directly go there and see what you find. Nov 2 at 23:17

I found a sort of answer I'm not seeing see here, it's narrow usage but it's helped me enough that I might as well share it.

The forward difference of $$f(x)$$ with respect to x will be written here as $$\Delta_{\partial x}f(x)$$ for clarity.

In the case that $$\Delta_{\partial x}g(x)$$ is some value $$k$$ which isn't a function of x, it's possible to reduce the composite function to the difference of a single function, with respect to a substituted variable like so:

$$\Delta_{\partial x}f(g(x)) = f(g(x+1))-f(g(x))$$ $$= f(g(x)+k)-f(g(x))$$ $$g(x) = u(x) \cdot k,h(x) = f(x\cdot k);$$ $$\Delta_{\partial x}f(g(x)) = f((u+1)\cdot k)-f(u\cdot k)$$ $$\Delta_{\partial x}f(g(x)) = h(u+1)-h(u)$$ $$\Delta_{\partial x}f(g(x)) = \Delta_{\partial u}h(u)$$