Archive for December 2011
This post is part of a series
So far in this series we’ve touched on a few applications of discrete calculus, but these were still at a fairly high level of abstraction. In this post, we lay some foundations for some very concrete applications that will allow us to actually start calculating things.
The Binary Tree
A particularly nice directed graph with many applications is the binary tree – a portion of which is illustrated below:
A node in the binary tree is labelled , where the first integer denotes the “spatial” position, i.e. its location at a given time, and the second integer denotes the “temporal” position.
A general discrete 0-form on a binary tree is written as usual as
where the sum is only over nodes of the binary tree and not over all integers. For instance, if is in the binary tree, then and are not.
Due to the special nature of the binary tree, a general discrete 1-form may also be reduced to a single sum over nodes, but in two distinct ways. First, we can group edges directed away from a given node. Second, we can group edges directed toward a given node.
In the first case, we can write
which is referred to as the left-component form and in the second case, we can write
which is referred to as the right-component form. These are two equivalent ways of expressing the same general discrete 1-form with
To see why these are referred to as left- and right-component forms, denote
and define a pair of basis 1-forms
Next, we can define left- and right-component 0-forms
respectively so that a discrete 1-form may be expressed in left-component form as
or equivalently in right-component form as
In other words, the left- and right- component forms of the bases allow us to express a general discrete 1-form form in terms of left- or right-component discrete 0-forms.
The exterior derivative of a general discrete 0-form on a binary tree is given in left-component form as
From this, we can read off the left-components which we’ll denote as
Similarly, the right-components are given by
Although, strictly speaking, coordinates (other than node labels) are not necessary for performing computations in discrete calculus, it is helpful when comparing to continuum calculus to introduce coordinate 0-forms to the binary tree
where is the spatial distance between endpoints of a directed edge at successive time steps, and
where is the temporal spacing between successive temporal nodes.
In this special case, we have
These relations can be inverted resulting in
and the discrete calculus begins to resemble the continuum calculus.
The coordinates and were referred to as “noncommutative” above because although discrete 0-forms commute, i.e.
in general, discrete 0-forms and discrete 1-forms do not commute. A straightforward computation results in the following commutation relations
from which it follows that
From here, there are two continuum limits one could consider that lead to different calculi. In the first, we could set
In this case, all commutation relation vanish and the continuum is also a commutative limit, i.e. the coordinates commute in this limit and we’re left with the usual deterministic continuum calculus.
In the second limit, we could set
In this case, the second and third commutation relations vanish, but the first one remains
This limit gives rise to stochastic calculus (or a very close cousin). Motivated by this, the discrete calculus on a binary tree when setting
but keeping finite is referred to as discrete stochastic calculus.
This post is part of a series
As stated in the Introduction, one of the motivations for this series is to work in parallel with John Baez’ series on network theory to highlight some applications of discrete calculus. In this post, I reformulate some of the material in Part 11 pertaining to Noether’s theorem.
The State-Time Graph
The directed graphs associated with discrete stochastic mechanics are described in the post The Discrete Master Equation, where the simple state-time graph example below was presented
Conceptually, the thing to keep in mind is that any transition from one state to another requires a time step. Therefore a transition from node to node is more precisely a transition from node to node .
On a state-time graph, a discrete 0-form can be written as
and a discrete 1-form can be written as
The Master Equation
The master equation for discrete stochastic mechanics can be expressed simply as
where is a discrete 0-form representing the state at all times with
and is a discrete 1-form representing transition probabilities with
for all . When expanded into components, the master equation becomes
Observables and Expectations
A general discrete 0-form on a state-time graph is defined over all states and all time. However, occasionally, we would like to consider a discrete 0-form defined over all states at a specific point in time. To facilitate this in a component-free manner, denote
so the identity can be expressed as
The discrete 0-form is a projection that projects a general discrete 0-form to a discrete 0-form defined only at time . For instance, given a discrete 0-form , let
In discrete stochastic mechanics, an observable is nothing more than a discrete 0-form
The expectation of an observable with respect to a state is given by
where was defined in a previous post. Note:
In preparation for the discrete Noether’s theorem, note that
For these commutators to vanish, we must have
This implies if and only if is constant on each connected component of the state-time graph.
In this section, we determine the conditions under which the expectation of an observable is constant in time, i.e.
for all . This is a fairly straightforward application of the discrete master equation, i.e.
indicating the condition we’re looking for is
In this section, we demonstrate that when both and are constant in time, this implies
which, in turn, implies . To do this, we first expand
The condition for this trace to vanish is the same as the condition for the commutators above to vanish, i.e.
Expanding the trace further results in
Summing over and when and are constants results in
while summing and in the third term results in
by definition of the transition 1-form. Consequently, when and are constants, it follows that
Finally, this implies if and only if and are constant in time.
This post is part of a series
The Graph Operator
In my last post, I mentioned the graph operator
and the fact the exterior derivative of a discrete 0-form can be expressed as a commutator
I then let myself speculate that the graph conductance 1-form
could be nothing more than the graph operator. In this post, I hope to explain a bit more how that might work.
Recall that the discrete Ohm’s Law
gives the total current
If we did not need to probe the current in any one of the individual parallel directed edges, it would be tempting to replace them with a single effective directed edge representing the total current flowing them, i.e.
In doing so, we could also replace the conductances with a single effective conductance
Could it be that ?
Let denote a partition of the set of directed edges from node to node and express the graph operator as
and is the number of directed edges in the subset . This would only make sense if we were not going to probe into any single directed edge within any element of the partition.
Comparing this to the conductance
we see that the graph conductance can be interpreted as the graph operator where each directed edge of our electric network is actually composed of a number of fundamental directed edges, i.e. conductance is simply counting the number of sub-paths within each directed edge.
As before, thinking about this (as time allows) raises more questions than answers. For example, if the above makes any sense and is in any way related to nature, this would imply a fundamental unit of conductance and that conductance should be quantized, i.e. come in integer multiples of the fundamental unit. For completely unrelated (?) reasons, conductance is observed to be quantized due to the waveguide like nature of small, e.g. nano, wires and the fundamental unit of conductance is given by
where is the electron charge and is Planck constant.
This also makes me think of the geometric origin of inhomogeneous media. In vacuum, I would expect there to be just a single directed edge connecting any two nodes. Hence, I would expect in vacuum. In the presence of matter, e.g. components of an electrical network, there should be bunches of directed edges between any two nodes.
This post is part of a series
The first equation is essentially the discrete calculus version of Ohm’s Law, where
is a discrete 1-form representing conductance,
is a discrete 0-form representing voltage, and
In components, this becomes
The second equation is a charge conservation law which simply says
is the sum of all currents into node and
is the sum of all currents out of node . This is more general than it may first appear. The reason is that directed graphs are naturally about spacetime, so the currents here are more like 4-dimensional currents of special relativity. The equation
is related to the corresponding Maxwell’s equation
where is the adjoint exterior derivative and is the 4-current 1-form
This also implies the discrete Ohm’s Law appearing above is 4-dimensional and actually a bit more general than the usual Ohm’s Law.
I’ve been thinking about this off and on since then as time allows, but questions seem to be growing exponentially.
For one, the equation
is curious because it implies that is a derivative, i.e.
Further, although by pure coincidence, in my paper with Urs, we introduced the graph operator
and showed that for any directed graph and any discrete 0-form that
Is it possible that and are related?
I think they are. This brings thoughts of spin networks and Penrose, but I’ll try to refrain from speculating too much beyond mentioning it.
If they were related, this would mean that the discrete Ohm’s Law above simplifies even further to
In components, the above becomes
This expresses an effective conductance in terms of the total number of directed edges connecting the two nodes in either direction, i.e.
If the ‘s appearing in the conductance 1-form are themselves effective conductances resulting from multiple more fundamental directed edges, then we do in fact have
Applications from here can go in any number of directions, so stay tuned!
This post is part of a series
Another Note on Notation
In a previous post, I introduced a slightly generalized notation in order to deal with directed graphs with multiple directed edges between any two nodes, e.g. parallel elements in electrical networks. However, the revised notation now makes some simpler calculations look more cumbersome. This is an example of what my adviser called the conservation of frustration. For example, the coboundary is now given by:
Applied to a general discrete 0-form, this becomes
To re-simplify the notation while maintaining the advantages of the new generalized notation, we can define
and we’re back to
as before. Furthermore, we have
where is the number of directed edges from node to node .
Trace and Inner Products
Given a discrete 0-form , we define its trace via
Similarly, given a discrete 1-form , its trace is given by
With the trace, we can define the inner product of discrete 0-forms via
and the inner product of discrete 1-forms via
where is the edge product.
With the inner products defined above, a simple calculation shows
so the graph divergence is the adjoint of the coboundary.
In relating discrete calculus to algebraic topology, typically, in algebraic topology you would have a coboundary operator for cochains and a boundary operator for chains. With discrete calculus, we have both and for discrete forms.
The graph Laplacian of a discrete 0-form is given by
More generally, we could define a graph Laplace-Beltrami operator
Graph Dirac Operator
The graph Dirac operator is essentially the “square root” of the graph Laplace-Beltrami operator. Since and , we have
so the/a graph Dirac operator is given by