MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not originally discrete, but have good discrete analogues? While a few examples arose in the answers to that earlier MO question, this wasn't what that question was asking, so I'm sure there are many more examples not mentioned there or at least not really explained there. What reminded me of this older MO question was seeing an MO question "Why is the Laplacian ubiquitous?", since that is an instance of an important notion which has a discrete analgoue.

In an answer, it would be interesting to hear about the relationship between the continuous and discrete versions of the notion, if possible, and references could also be helpful. Thanks!

share|cite|improve this question
I don't actually know if this is true, but I would guess that the Fourier transform was discovered before the discrete Fourier transform. – Qiaochu Yuan Aug 19 '12 at 16:50
That's a great example -- I actually wasn't so concerned about chronology, rather was interested in understanding better the interesting relationships between the discrete and continuous versions of things and thought it might be nice if there were a list of examples. You could certainly write an answer about the Fourier transform. – Patricia Hersh Aug 19 '12 at 17:01
Patricia, since you are asking for examples: please make this community wiki. There is no "right" answer here. – Vidit Nanda Aug 19 '12 at 17:53
@Vel: I thought some people could be more motivated to go to the trouble to write a good answer if I didn't make this CW -- there have been other questions like this that aren't CW, especially when a good answer could involve substantial mathematics. So I wanted to see if I could hold off on that, at least for awhile. – Patricia Hersh Aug 19 '12 at 18:20
Some people do not answer big list questions until they are CW. I have flagged the mods because only they can make existing answers CW. – Benjamin Steinberg Aug 20 '12 at 0:08

12 Answers 12

Negative curvature of Riemannian manifolds, originally a differentiable theory, has been discretized in several phases. The first phase might have been Dehn's algorithm for the word problem in a surface group; I am guessing that at the time this might have seemed more an "application" of hyperbolic geometry than a discretization of it. But then comes the next big phase, the development of small cancellation theory, in which Dehn's algorithm (and related tools) were applied to many abstractly defined groups. The culminating phase was the development (by Gromov among others) of the theory of hyperbolic groups.

share|cite|improve this answer

I'll give one answer to get things started: discrete Morse theory.

A discrete Morse function assigns a real number to each face in a simplicial complex or more generally to each cell in a regular CW complex. (With care, one can also work with non-regular CW complexes.) While in Morse theory there are critical points, each having an index, the discrete Morse theoretic analogue is a critical cell, with the dimension of a critical cell playing the role of index of a critical point. The Morse inequalities still hold, and one can still calculate Euler characteristic as alternating sum of Morse numbers (i.e. alternating sum of the number of critical cells of each dimension). The original regular CW complex will be (simple) homotopy equivalent to a CW complex having fewer cells (unless all cells are critical), namely a CW complex whose cells are indexed by the critical cells.

This analogue with Morse theory was established by Robin Forman in his paper "Morse theory for cell complexes", Adv. Math., 134 (1998), no. 1, 90-145. Another nice reference is his paper "A user's guide to discrete Morse theory". The idea has proven quite useful in the study of various simplicial complexes e.g. in combinatorics, and the idea appeared independently in work of Ken Brown under the name "collapsing scheme".

share|cite|improve this answer
You might add as a reference the paper of Bestvina and Brady, Morse theory and finiteness properties of groups. Invent. Math. 129 (1997), no. 3, 445–470. – Lee Mosher Aug 19 '12 at 16:02
Thanks! My description of the analogy was for Forman's notion, but it's a good idea to add this reference. – Patricia Hersh Aug 19 '12 at 17:46
We have to be careful with the simple homotopy claim. Given $f:X \to \mathbb{R}$ and setting $X^a = \lbrace \sigma \in X~|~f(\sigma) < a\rbrace $ there is a simple homotopy equivalence between $X^a$ and $X^b$ provided there are no critical values in $(a,b)$. On the other hand, when we cross a critical value, then we only have homotopy equivalence coming from the attaching map of the boundary of the critical cell: this need not be a simple homotopy equivalence. – Vidit Nanda Aug 19 '12 at 17:50
@Vel: I think one can also handle the critical cells by using some anticollapses, but I don't know a reference for this. Idea: once one removes critical cell $C$, one can see what elementary collapses to do to get down to $X^a$ and how they would carry the boundary of $C$ to have new attaching map $f_{C_a}$. Therefore, we first do an anticollapse by adding in cell $C'$ with attaching map $f_{C_a}$ along with a cell $D$ of dimension one higher that has $C'$ as a free face and also attaches to the cells $\sigma $ with $a\le f(\sigma ) \le b$. Now collapse away $C,D$ and the noncritical cells. – Patricia Hersh Aug 19 '12 at 18:49
Vel, my recollection is that Robin Forman made this statement various times at conferences that a discrete Morse function implies a simple homotopy equivalence, so probably that's how it became folklore. I think it's true, and hopefully the argument I gave above explains why. – Patricia Hersh Aug 20 '12 at 12:27

A simplicial set is a discrete analogue (and in many ways a generalizaion) of a topological space, giving rise to discrete notions of fibration, homotopy groups, etc etc.

share|cite|improve this answer

Trees (in particular, homogeneous) are discrete analogues of Cartan-Hadamard manifolds (in particular, of simply connected manifolds of constant negative curvature). Although dealing with trees is much easier technically, they were considered much later: function theory, harmonic analysis, automorphism groups, random walks vs Brownian motion, representation theory etc. One has to admit that mostly (not always, though) it was done by direct translation (sometimes almost verbatim) from continuous into discrete language.

Another example is provided by the discrete potential theory (sometimes interpreted as the theory of resistive electrical networks). Here, once again, in spite of being much more elementary it was developed significantly later than the continuous theory. I would say that in the latter case the discrete theory is more independent than in the case of geometry on trees.

Yet another example (where the discrete part is much more original) is buildings vs Riemannian symmetric spaces.

share|cite|improve this answer

One of my favorite examples of this is the "q-calculus", which is like a multiplicative version of the classical subject of calculus of finite differences. One can, using suitably defined "q" versions of the derivative, integral, and so on, recover analogues of most of the usual theorems in calculus. But what's more interesting is that this all ties in with noncommutative geometry and the field with one element (see John Baez's This Weeks Finds in Mathematical Physics).

share|cite|improve this answer
That last sentence needs some justification – Yemon Choi Aug 19 '12 at 21:25
You're right. I added a reference. – Aleksandar Bahat Aug 19 '12 at 22:02

Finite graphs are a rich source of discrete analogues (I will be partially repeating the OP and some other answers here):

  • The Laplacian on a finite graph is a discrete analogue of the Laplacian on a Riemannian manifold. In particular, it is possible to formulate the heat equation, the wave equation, and the Schrödinger equation on a finite graph. There are actually two Laplacians, a vertex Laplacian and an edge Laplacian, which give a discrete analogue of Hodge theory.

  • The Ihara zeta function of a finite graph is a discrete analogue of the Selberg zeta function of a Riemannian manifold. A regular graph satisfies an analogue of the Riemann hypothesis if and only if it is a Ramanujan graph. There is also an analogue of the Selberg trace formula in this setting; Terras has written extensively about this kind of thing.

  • The Picard group (or critical group, or sandpile group) of a finite graph is a discrete analogue of the Picard group of an algebraic curve. More generally a lot of the theory of algebraic curves can be transported to this setting, e.g. the Riemann-Roch theorem.

(Finite graphs are also a rich source of other kinds of analogues; for example the Ihara zeta function is also analogous to the Dedekind zeta function of a number field, with coverings of graphs analogous to extensions of number fields and the Picard group analogous to the class group. There is even an analogue of the analytic class number formula in this setting although I have forgotten the reference.)

share|cite|improve this answer
Thanks! Great answer! – Patricia Hersh Aug 24 '12 at 13:47

I would consider symbolic dynamics as a discrete version of usual dynamical systems. This may depend on whether you view infinite words on finite alphabets as discrete.

share|cite|improve this answer

Discrete difference equations generalize differential equations. In a similar spirit, divided difference operators generalize partial differentiation operators. Though such operators go back to Newton, there has a been a resurgence of interest in them since the work of Lascoux and Schutzenberger on Schubert polynomials. While partial differentiation operators satisfy commutativity relations $\partial_x \partial_y = \partial_y \partial_x$, the divided difference operators satisfy the nilHecke relations. This gives the discrete operators a certain richness that is not present in the continuous operators.

share|cite|improve this answer
As one reference on this topic, I really like the paper: Sergey Fomin and Richard Stanley, "Schubert polynomials and the nilCoxeter algebra", Adv. Math. 103 (1994), 196--207. – Patricia Hersh Aug 20 '12 at 14:16

A more or less elementary example: Sperner's lemma is a discrete/combinatorial analog to the Brouwer fixed point theorem. Furthermore, its one-dimensional case is a discrete analog to the intermediate value theorem.

share|cite|improve this answer

Continuous-time random walks on graphs are in some sense a discrete analogue of diffusions on a Riemannian manifold (of course, the reverse can be argued, but I think that diffusions play a more central role in modern probability theory). Of course, the most important diffusion is Brownian motion, i.e., the Markov process associated with the Laplace-Beltrami operator. From my perspective, the natural analogue of Brownian motion is the operator $\mathcal{L}_V$ given by (we use unweighted graphs for simplicity)

\begin{equation*} (\mathcal{L}_Vf)(x) := \sum\_{y\sim x}(f(y)-f(x)). \end{equation*}

A more 'common' choice might be the rate-1 continuous time random walk with generator $\mathcal{L}_C$ given by

\begin{equation*} (\mathcal{L}_Cf)(x) := \frac{1}{\deg(x)}\sum\_{y\sim x}(f(y)-f(x)). \end{equation*}

However, this choice of generator has several 'bad' properties if you want to view it as an analogue of Brownian motion -- for example, the generator is always bounded on $L^2(\deg)$, it cannot have discrete spectrum, and the associated random walk cannot explode; in contrast, the operator $\mathcal{L}_V$ may be unbounded, and discrete spectrum and explosiveness are possible.

Once you have this discrete (space) analogue of Brownian motion on a Riemannian manifold, a natural question is to ask what the discrete analogue of the Riemannian metric should be for this process. It is not too hard to find examples that show that the graph metric is a bad analogue, since the Riemannian metric governs heat flow (in some sense) on a Riemannian manifold (see e.g. here), but Gaussian heat kernel estimates do not hold for the random walk associated with $\mathcal{L}_V$ if you take the manifold heat kernel estimates and replace the distance function with the graph metric. A reasonable analogue has been formulated recently, see e.g. here and here.

share|cite|improve this answer

If you have a discrete data structure (say a tree), and you want to make a small change to it (i.e. insert a node at some location), it turns out that the original datatype can be described as a function, and the "small change" datatype is the derivative of the original datatype's function, that you can calculate with the usual rules for derivatives. The original article is here:

and it's been extended in various ways since then. Amazing stuff.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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