Continuous notions with compelling discrete analogues - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:31:22Z http://mathoverflow.net/feeds/question/105038 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues Continuous notions with compelling discrete analogues Patricia Hersh 2012-08-19T15:14:33Z 2012-08-24T13:33:34Z <p>Following up on the previous MO question <a href="http://mathoverflow.net/questions/17523/are-there-any-important-mathematical-concepts-without-discrete-analog" rel="nofollow">"Are there any important mathematical concepts without discrete analogue?"</a>, 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 <a href="http://mathoverflow.net/questions/54986/why-is-the-laplacian-ubiquitous" rel="nofollow">"Why is the Laplacian ubiquitous?"</a>, since that is an instance of an important notion which has a discrete analgoue. </p> <p>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!</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105041#105041 Answer by Patricia Hersh for Continuous notions with compelling discrete analogues Patricia Hersh 2012-08-19T15:52:25Z 2012-08-19T15:52:25Z <p>I'll give one answer to get things started: discrete Morse theory.</p> <p>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.</p> <p>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". </p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105043#105043 Answer by Lee Mosher for Continuous notions with compelling discrete analogues Lee Mosher 2012-08-19T16:00:46Z 2012-08-19T16:00:46Z <p>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 <a href="http://en.wikipedia.org/wiki/Small_cancellation_theory" rel="nofollow">small cancellation theory</a>, 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 <a href="http://en.wikipedia.org/wiki/Hyperbolic_group" rel="nofollow">hyperbolic groups</a>.</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105045#105045 Answer by R W for Continuous notions with compelling discrete analogues R W 2012-08-19T16:24:40Z 2012-08-19T16:24:40Z <p>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. </p> <p>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.</p> <p>Yet another example (where the discrete part is much more original) is buildings vs Riemannian symmetric spaces. </p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105050#105050 Answer by Sean Eberhard for Continuous notions with compelling discrete analogues Sean Eberhard 2012-08-19T19:37:22Z 2012-08-20T03:17:45Z <p>The <a href="http://en.wikipedia.org/wiki/Cheeger_constant" rel="nofollow">Cheeger inequality</a> is another example.</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105055#105055 Answer by Steven Landsburg for Continuous notions with compelling discrete analogues Steven Landsburg 2012-08-19T21:00:59Z 2012-08-19T21:00:59Z <p>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. </p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105057#105057 Answer by Aleksandar Bahat for Continuous notions with compelling discrete analogues Aleksandar Bahat 2012-08-19T21:21:06Z 2012-08-19T22:02:02Z <p>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).</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105072#105072 Answer by Benjamin Steinberg for Continuous notions with compelling discrete analogues Benjamin Steinberg 2012-08-20T03:46:22Z 2012-08-20T03:46:22Z <p>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. </p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105074#105074 Answer by Michael Joyce for Continuous notions with compelling discrete analogues Michael Joyce 2012-08-20T04:06:19Z 2012-08-20T04:06:19Z <p>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.</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105367#105367 Answer by Fernando Martin for Continuous notions with compelling discrete analogues Fernando Martin 2012-08-24T03:16:22Z 2012-08-24T03:22:28Z <p>A more or less elementary example: <a href="http://en.wikipedia.org/wiki/Sperner%27s_lemma" rel="nofollow">Sperner's lemma</a> 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.</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105369#105369 Answer by mfolz for Continuous notions with compelling discrete analogues mfolz 2012-08-24T05:21:56Z 2012-08-24T08:08:45Z <p>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)</p> <p>\begin{equation*} (\mathcal{L}_Vf)(x) := \sum_{y\sim x}(f(y)-f(x)). \end{equation*}</p> <p>A more 'common' choice might be the rate-1 continuous time random walk with generator $\mathcal{L}_C$ given by</p> <p>\begin{equation*} (\mathcal{L}_Cf)(x) := \frac{1}{\deg(x)}\sum_{y\sim x}(f(y)-f(x)). \end{equation*}</p> <p>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.</p> <p>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. <a href="http://www.math.uni-bielefeld.de/~grigor/super.pdf" rel="nofollow">here</a>), 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. <a href="http://arxiv.org/abs/1012.5050" rel="nofollow">here</a> and <a href="http://arxiv.org/abs/1201.5908" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105372#105372 Answer by Qiaochu Yuan for Continuous notions with compelling discrete analogues Qiaochu Yuan 2012-08-24T07:41:00Z 2012-08-24T07:41:00Z <p>Finite graphs are a rich source of discrete analogues (I will be partially repeating the OP and some other answers here): </p> <ul> <li><p>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 <a href="http://ncatlab.org/johnbaez/show/Circuit+theory+I" rel="nofollow">discrete analogue of Hodge theory</a>. </p></li> <li><p>The <a href="http://en.wikipedia.org/wiki/Ihara_zeta_function" rel="nofollow">Ihara zeta function</a> of a finite graph is a discrete analogue of the <a href="http://en.wikipedia.org/wiki/Selberg_zeta_function" rel="nofollow">Selberg zeta function</a> of a Riemannian manifold. A regular graph satisfies an analogue of the Riemann hypothesis if and only if it is a <a href="http://en.wikipedia.org/wiki/Ramanujan_graph" rel="nofollow">Ramanujan graph</a>. There is also an analogue of the <a href="http://en.wikipedia.org/wiki/Selberg_trace_formula" rel="nofollow">Selberg trace formula</a> in this setting; Terras has written extensively about this kind of thing. </p></li> <li><p>The <a href="http://mathoverflow.net/questions/83552/what-is-the-sandpile-torsor" rel="nofollow">Picard group</a> (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 <a href="http://arxiv.org/abs/math/0608360" rel="nofollow">Riemann-Roch theorem</a>. </p></li> </ul> <p>(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.) </p> http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105373#105373 Answer by none for Continuous notions with compelling discrete analogues none 2012-08-24T08:29:13Z 2012-08-24T08:29:13Z <p>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:</p> <ul> <li><a href="http://strictlypositive.org/diff.pdf" rel="nofollow">http://strictlypositive.org/diff.pdf</a></li> </ul> <p>and it's been extended in various ways since then. Amazing stuff.</p>