August « 2022 « The blog at the bottom of the sea

Before we get into umbral calculus I want to talk about discrete calculus.

Discrete calculus lets you do calculus operations on discrete functions. These are functions like $y=f(x)$ where x has to be an integer. Limits can no longer get arbitrarily close to 0 in discrete calculus since the smallest difference between integers is 1. One consequence of that is that derivatives (aka deltas aka $\Delta$ ) are calculated using finite differences, commonly forward differences. When the smallest valued difference is 1, it falls out naturally from the definition of the derivative, setting h to 1.

$\frac{d}{dx} f(x) = \lim_{h \to 0} \frac{f(x+h)-f(x)}{h}$

$\Delta f = f(x+1) - f(x)$

A nice thing is that there are lots of similarities between discrete calculus and regular calculus, such as the derivative of a constant being zero:

$\frac{d}{dx} c = 0$

$\Delta c = 0$

But there are plenty of differences. The product rule in calculus is different than the one in discrete calculus for example. (Note: this is because the extra term has a multiplier that approaches the limit, which is zero in regular calculus, but 1 in discrete calculus.)

$\frac{d}{dx}(f(x)g(x)) = \frac{d}{dx}(f(x)) g(x) + f(x) \frac{d}{dx}(g(x))$

$\Delta(f(x)g(x)) = \Delta(f(x) )g(x) + f(x) \Delta(g(x)) + \Delta(f(x)) \Delta(g(x))$

Here’s where umbral calculus comes in. It lets you turn a discrete calculus problem into a continuous calculus problem, and it lets you turn a continuous calculus problem into a discrete one.

In this post we are going to leverage umbral calculus to see how to craft functions that sum discrete functions. If you have a discrete quadratic polynomial f, you’ll get a cubic polynomial g that gives you the sum for all values f(n) for n ranging from 0 to x-1.

How To Do It

Firstly, we need a function that spits out the numbers we want to sum. The function input needs to be integers, but the function output doesn’t need to be.

Once we have our function, the process to get the function $g(x)$ that calculates sums of $f(x)$ is this:

Turn the discrete function into a continuous function.
Integrate the continuous function.
Convert the result from a continuous function back into a discrete function.

If we use $\Phi$ (phi) to denote converting a function from continuous to discrete, and $\Phi^{-1}$ to denote converting a function from discrete to continuous, it looks like this mathematically:

$g(x) = \Phi \int \Phi^{-1} f(x) dx$

When you plug an integer x into g, you get out the sum of $f(n)$ for all values of n from 0 to x-1.

If you want to get the sum of all values of $f(x)$ from a to b, you can calculate that as $g(b+1)-g(a)$ . This works because if you wanted the sum of numbers from 10 to 20, you could sum up all the numbers from 0 to 20, and subtract out the numbers from 0 to 10. This is also a discrete calculus definite integral.

That’s the overview, let’s talk about how to calculate $\Phi$ and $\Phi^{-1}$ .

Calculating Φ

Phi is the operator for converting continuous functions to discrete functions. Phi of powers of x are real easy to compute: They turn powers of x into falling factorials of x which are denoted $x_n$ . So, $x^n$ becomes $x_n$ .

The oddity of this mysterious conversion is what gave umbral (shadow) calculus it’s name. It took a while for people to understand why this works and formalize it. Until then they just knew it worked (although they had counter cases to an imperfect understanding so it didn’t always work), but didn’t know why, so was a bit mysterious.

The above makes it very easy to work with polynomials. In a couple sections will be a cheat sheet with a couple other transformations I scrounged up.

Some other rules of the phi operator include:

$\Phi(a f(x)) = a \Phi f(x)$

$\Phi(f(x) + g(x)) = \Phi f(x) + \Phi g(x)$

$\Phi f(x) \neq f(x) \Phi$

The last one is meant to show that left and right multiplication are not the same thing, so ordering needs to be carefully considered and conserved.

Here are a couple other useful properties that might be helpful, that I’ve scraped from other sources 🙂

$\Delta x_n = n x_{n-1}$

$\Delta \Phi \sin(x) = \Phi \cos(x)$

$\Phi e^{-x} = 0$

$(\Phi \sin(x))^2 + (\Phi \cos(x))^2 = \Phi e^x$

$\Delta 2^x = 2^x$

The last one implies that in discrete calculus, $e$ is 2. That is strange, isn’t it? If you work it out with a few values, you can see that it’s true!

This section is far from exhaustive! Check out the links at the bottom of this post for some more information.

Let’s apply phi to a polynomial as an example of how it works…

$f(x) = 3x^2 + \frac{1}{2}x$

$\Phi f(x) = \Phi (3x^2 + \frac{1}{2}x)$

$\Phi f(x) = \Phi 3x^2 + \Phi \frac{1}{2}x$

$\Phi f(x) = 3 \Phi x^2 + \frac{1}{2} \Phi x$

$\Phi f(x) = 3 (x^2-x) + \frac{1}{2} x$

$\Phi f(x) = 3x^2 - 3x + \frac{1}{2} x$

$\Phi f(x) = 3x^2 - 2.5x$

Calculating Inverse Φ

Calculating inverse phi is less straight forward – at least as far as I know. There may be a more formulaic way to do it that I don’t know of. I’ll show the inverse phis I know and how they are derived, which should hopefully help if you need others.

Firstly, the inverse phi of x is just x. That’s an easy one.

x squared

Next up is the inverse phi of x squared. We know what phi of x squared is from the last section, so let’s start with that.

$\Phi x^2 = x^2 - x$

Since x is the same as the phi of x, we can replace the last term with phi of x.

$\Phi x^2 = x^2 - \Phi x$

Now let’s get the naked x squared term on the left side, and all the phi terms on the right side.

$x^2 = \Phi x^2 + \Phi x$

Lastly, we’ll left multiply both sides by inverse phi, and we are done!

$\Phi^{-1} x^2 = x^2 + x$

x cubed

Let’s start with the phi of x cubed.

$\Phi x^3 = x^3 - 3x^2 + 2x$

Let’s turn $2x$ into $3x-x$ .

$\Phi x^3 = x^3 - 3x^2 + 3x - x$

Next we factor -3 out of the middle two terms.

$\Phi x^3 = x^3 - 3(x^2 - x) - x$

The middle term is 3 times phi of x squared, so we can replace it with that. The -x on the end outside of the parens is also just negative phi of x so we’ll replace that too.

$\Phi x^3 = x^3 - 3 \Phi x^2 - \Phi x$

Like last time, let’s get the phi terms on the right and the non phi term on the left.

$x^3 = \Phi x^3 + 3 \Phi x^2 + \Phi x$

And again like last time, we can now left multiply by inverse phi to finish!

$\Phi^{-1} x^3 = x^3 + 3 x^2 + x$

Cheet Sheet

Here is a table of phi and inverse phi transforms.

The coefficients on the polynomials made from powers of x are the Stirling numbers. Phi relates to signed Stirling numbers of the first kind, and inverse phi relates to unsigned Stirling numbers of the second kind. That fact helps if you need to work with higher powers of x.

Example 1: f(x) = x

Let’s use what we know to come up with a function $g(x)$ which sums all integers from 0 to x-1.

Our recipe for making g from f starts out like this:

$g(x) = \Phi \int \Phi^{-1} f(x) dx$

Our function is just $f(x) = x$ , so we start at:

$g(x) = \Phi \int (\Phi^{-1} x) dx$

The inverse phi of x is just x.

$g(x) = \Phi \int (x) dx$

Integrating x gives us one half x squared. We can move the half outside of the phi.

$g(x) = \frac{1}{2} \Phi x^2$

We know the phi of x squared so we can plug it in and be done!

$g(x) = \frac{1}{2}(x^2 - x)$

If we plug in 1 to get the sum of all integers from 0 to 0, we get 0.

If we plug in 2 to get the sum of all integers from 0 to 1, we get 1. That is 0 + 1.

Plugging in 3 for summing 0 to 2, we get 3. That is 0 + 1 + 2.

Plugging in 4 gives us 6. That is 0 + 1 + 2 + 3.

Plugging in 5 gives us 10. 10 gives us 45. 100 gives us 4950. 200 gives us 19900. Plugging in a million gives us 499,999,500,000!

If we wanted to sum the integers between 5 and 9, we can do that too! We subtract g(5) from g(10), which is 45-10 or 35. That is 5+6+7+8+9.

So, we know that summing the integers between 100 and 199 is 14,950, since we have g(100) and g(200) above, which are 4950 and 19900 respectively.

Example 2: f(x) = x^2

Let’s find the function to sum squares of integers.

$g(x) = \Phi \int \Phi^{-1} x^2 dx$

Applying inverse phi…

$g(x) = \Phi \int (x^2 + x) dx$

integrating…

$g(x) = \Phi (\frac{1}{3}x^3 + \frac{1}{2}x^2)$

Splitting it into two phi terms, and moving the fractions out of phi…

$g(x) = \frac{1}{3} \Phi x^3 + \frac{1}{2} \Phi x^2$

Applying phi…

$g(x) = \frac{1}{3} (x^3-3x^2+2x) + \frac{1}{2} (x^2 - x)$

$g(x) = \frac{1}{6}(2x^3-6x^2+4x) + \frac{1}{6}(3x^2-3x)$

$g(x) = \frac{1}{6}(2x^3-3x^2+x)$

Plugging in 2 gives 1, which is 0 + 1.

3 gives 5, which is 0 + 1 + 4.

4 gives 14, which is 0 + 1 + 4 + 9.

5 gives 30, which is 0 + 1 + 4 + 9 + 16.

if we want to get the sum of values for x between 2 and 4, we calculate g(5)-g(2), which is 30-1 = 29. That is 4+9+16.

It works!

Example 3: f(x) = x^2 – x/2

This last example is to show that while the function f has to take in integers, it doesn’t have to give out integers.

Let’s do the dance…

$g(x) = \Phi \int \Phi^{-1} (x^2 - \frac{1}{2}x) dx$

$g(x) = \Phi \int (\Phi^{-1} x^2 - \frac{1}{2} \Phi^{-1} x) dx$

$g(x) = \Phi \int (x^2 + x - \frac{1}{2} x) dx$

$g(x) = \Phi \int (x^2 + \frac{1}{2} x) dx$

$g(x) = \Phi (\frac{1}{3} x^3 + \frac{1}{4} x^2)$

$g(x) = \frac{1}{3} \Phi x^3 +\frac{1}{4} \Phi x^2$

$g(x) = \frac{1}{3} (x^3-3x^2+2x) +\frac{1}{4}(x^2 - x)$

$g(x) = \frac{1}{12} (4x^3-12x^2+8x + 3x^2 - 3x)$

$g(x) = \frac{1}{12} (4x^3-9x^2+5x)$

Plugging in 1 gives 0.

2 gives 1/2, which is 1 – 1/2.

3 gives 3.5, which is (1-1/2) + (4-1).

4 gives 11, which is (1-1/2) + (4-1) + (9-1.5).

5 gives 25, which is (1-1/2) + (4-1) + (9-1.5) + (16-2).

6 gives 47.5, which is (1-1/2) + (4-1) + (9-1.5) + (16-2) + (25-2.5).

It works!

Closing and Links

Finding formulas that sum ranges of discrete functions is pretty cool, but is it very useful?

Well, if you divide a sum by the count of values in the sum, that gives you an average.

That average is also equivalent to doing Monte Carlo integration using regular spaced samples. I’m not a fan of regular spaced samples, but for constant time sampling of arbitrary sample counts, I think I might make an exception!

How about converting problems between the continuous and discrete domain, is that very useful for other things? Not real sure.

Can this be extended to multi dimensional integrals? I bet so!

If you have more info about any of the above, I’d love to hear it!

This video is what first turned me onto this topic and it is quite good. I’ve watched it about 10 times, trying to scrape all the info out of it. https://www.youtube.com/watch?v=D0EUFP7-P1M

This video is also very good. https://www.youtube.com/watch?v=ytZkmV-7EbM

Thanks for reading!

$x^n$	$\Phi x^n \text{ aka } x_n$	$\text{ Expanded}$
$x$	$x$	$x$
$x^2$	$x(x-1)$	$x^2 - x$
$x^3$	$x(x-1)(x-2)$	$x^3-3x^2+2x$

$f(x)$	$\Phi f(x)$	$\Phi^{-1} f(x)$
$x$	$x$	$x$
$x^2$	$x^2-x$	$x^2+x$
$x^3$	$x^3-3x^2+2x$	$x^3 + 3 x^2 + x$
$e^{ax}$	$(a+1)^x$	$\text{?}$
$\sin(x)$	$\sqrt{2^x} \sin{\frac{x \pi}{4}}$	$\text{?}$
$\cos(x)$	$\sqrt{2^x} \cos{\frac{x \pi}{4}}$	$\text{?}$
$\ln(x)$	$H_{x-1} \text{ (Harmonic Series)}$	$\text{?}$

The blog at the bottom of the sea

Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis

Monthly Archives: August 2022

Calculating Discrete Sums With Umbral Calculus