11
$\begingroup$

An almost eternal theme in Mathematics is the approximation of the Continuum by the Discrete. This core idea goes back at least to Archimedes, and remains active to these very days (and quite likely for the next thousand years) .

You have a continuous structure, say a sphere, and you approximate it as the limit of a series of discrete objects, say polyhedra.

I do not need to provide more examples, I am sure you all have plenty.

But, there is also, though by no means so prominent, a reverse direction.

I am not able to date precisely when it made its debut in the history of mathematics, but it most certainly appears in the revolutionary work of Fourier: take a discrete function, say the Heaviside step function, and approximate it via series of trigonometric functions:

enter image description here

So, here a discrete object is realized as a limit of continuous ones (in this case smooth functions).

I am especially intrigued by this possibility, which, pushed to the extreme, will depict a mathematical world where the Discrete is an emergent phenomenon, out of a Continuum

Thus I ask to everybody:

can you list active research in the way of approximating discrete structures via smooth ones?

For instance, a polyhedron via a series of smooth manifolds, or examples in analytic number theory, or patterns in finite combinatorics out of .....(fill the dots) .

Any thoughtful and possibly well documented answer will get my vote, regardless the domain chosen (in fact, the more examples I will harvest from heterogeneous disciplines, the happier I shall be).

On the other hand, to get the GREEN the stakes are higher: rather than single examples, a sketch of a general perspective on the Discrete as emerging from the Continuum

ADDENDUM: As pointed out by Andreas Blass, I have implicitly conflated two themes here:

  1. discrete as limit of the continuum
  2. emergence of the discrete from some background

Point 2) does not seem to necessarily imply point 1) and probably the same applies the other way around. Which one I am interested in? Easy: BOTH OF THEM.

But now that Andreas has already marked this point, the GREEN ANSWER would be, perhaps, a clarification on the relationship between 1 and 2 (inter alia)

$\endgroup$
8
  • 2
    $\begingroup$ The last line of your question, "the discrete as emerging from the continuum," could also include things like Thom's catastrophe theory, which don't fit the "approximation" theme of the earlier parts of the question. $\endgroup$ Aug 13, 2020 at 13:04
  • 2
    $\begingroup$ Central limit theorem, anyone? $\endgroup$ Aug 13, 2020 at 13:34
  • $\begingroup$ @AndreasBlass absolutely ! Yes, I conflated two things which are not necessarily entangled: 1) discrete as limit of the continuum and 2) emergence of the discrete. So, which one? Answer: I am interested in BOTH. Thom Morphogenesis is very welcome $\endgroup$ Aug 13, 2020 at 13:41
  • $\begingroup$ signal processing, lossy data compression of audio and video represented by discrete samples using psychoacoustic and psychovisual models... ask Siri or Alexa... $\endgroup$ Aug 14, 2020 at 14:26
  • 1
    $\begingroup$ Related: When has discrete understanding preceded continuous?. Cited there: László Lovász: "Discrete and Continuous: Two sides of the same?" He looks at e.g., the Laplacian, the Colin de Verdière’s invariant, and many other examples. PDF download. $\endgroup$ Aug 26, 2020 at 0:25

5 Answers 5

10
$\begingroup$

In combinatorics, there is no shortage of functions that are hard to compute. Here are two famous examples whose input is a simple graph $G=(V,E)$:

  • $\alpha(G):=$ size of the largest independent set $I\subseteq V$

  • $\operatorname{MaxCut}(G):=$ size of the largest cut-set $C\subseteq E$

Both of these discrete functions are $\mathsf{NP}$-hard to compute. However, there are polynomial time–computable functions $\{\alpha'_k\}_{k=1}^\infty$ and $\{\operatorname{MaxCut}'_k\}_{k=1}^\infty$ that map simple graphs to real numbers (i.e., continuous quantities) in a way that monotonically decreases and converges pointwise to the desired functions.

Warning: While the runtime of the $k$th function is polynomial for a fixed precision (at least under certain models), the exponent increases with $k$. See this thread for more details on runtime considerations for semidefinite programs.

To be explicit, $\alpha'_1$ denotes Schrijver's strengthening of Lovász's semidefinite relaxation of the independence number, $\operatorname{MaxCut}'_1$ denotes the Goemans–Williamson semidefinite relaxation of maximum cut, and the sequences arise from sum-of-squares hierarchies that strengthen these relaxations. The claimed pointwise convergence is a consequence of the identities

$$\alpha'_{\alpha(G)}(G)=\alpha(G),\qquad \operatorname{MaxCut}'_{\lceil |V|/2\rceil}(G)=\operatorname{MaxCut}(G),$$

which follow from results in [Lasserre 2002] and [Fawzi-Saunderson-Parrilo 2016], respectively.

$\endgroup$
3
  • $\begingroup$ absolutely great answer! I had no idea about Lovasz number. You suggestion would be even more captivating if there was underneath something in the way of a smooth approximation of the embedded graph (something like a weird smooth hypersurfaces that approximated the embedded graph asymptotically). $\endgroup$ Aug 26, 2020 at 13:42
  • 2
    $\begingroup$ @MircoA.Mannucci - You may appreciate this geometric perspective: both problems can be viewed as maximizing a linear function over a finite collection of points. One can reformulate this as a linear program over the convex hull of these points, but there are exponentially many facets in the resulting polytope. Instead, a semidefinite relaxation considers a spectrahedron that contains this polytope. The SOS hierarchy amounts to a sequence of spectrahedra that converges to the polytope. See this paper for more information in the context of MaxCut: arxiv.org/abs/1812.11583 $\endgroup$ Aug 26, 2020 at 15:13
  • $\begingroup$ very very very intriguing: thanks again Dustin! This goes a long way toward what I ultimately have in mind, namely showing that virtually any discrete geometric object can be approximated by a suitable collection of smooth ones. Plus. it is actually intriguing to me as a data scientist, but that is another story $\endgroup$ Aug 26, 2020 at 15:17
8
$\begingroup$

Mirco, regarding your second question (emergence from the continuum): My view would be that the FUNDAMENTAL GROUP of topological objects is an example. It captures discrete properties of a continuous object, e.g. a sphere. Or seen as the deck transformation group, it expresses the discrete structure of the universal cover of a continuous object like torus, sphere, and so on.

$\endgroup$
2
  • $\begingroup$ The question is where do you draw the line in your OP. For example, one could argue the set of zeros of the sin function is also a discrete set emerging from a continous object. But I imagine this is not what you had in mind? $\endgroup$
    – Mary Sp.
    Aug 25, 2020 at 17:26
  • $\begingroup$ Interesting thought @MaryS. As for what I have in mind, yes, that too. But it is a bit ad hoc: rather, I would be interested in seeing entire discrete structures as emerging from continuous ones $\endgroup$ Aug 25, 2020 at 20:00
6
$\begingroup$

The emergence of particles as excited states (quanta) of underlying continuous fields in quantum field theory might fit the bill. See The Unquantum Quantum by David Tong, in the section titled Emergent Integers:

Erwin Schrödinger developed an alternative approach to quantum theory based on the idea of waves in 1925. The equation that he formulated to describe how these waves evolve contains only continuous quantities--no integers. Yet when you solve the Schrödinger equation for a specific system, a little bit of mathematical magic happens. Take the hydrogen atom: the electron orbits the proton at very specific distances. These fixed orbits translate into the spectrum of the atom. The atom is analogous to an organ pipe, which produces a discrete series of notes even though the air movement is continuous. At least as far as the atom is concerned, the lesson is clear: God did not make the integers. He made continuous numbers, and the rest is the work of the Schrödinger equation.

In other words, integers are not inputs of the theory, as Bohr thought. They are outputs. The integers are an example of what physicists call an emergent quantity. In this view, the term "quantum mechanics" is a misnomer. Deep down, the theory is not quantum. In systems such as the hydrogen atom, the processes described by the theory mold discreteness from underlying continuity.

Perhaps more surprisingly, the existence of atoms, or indeed of any elementary particle, is also not an input of our theories. Physicists routinely teach that the building blocks of nature are discrete particles such as the electron or quark. That is a lie. The building blocks of our theories are not particles but fields: continuous, fluidlike objects spread throughout space. The electric and magnetic fields are familiar examples, but there are also an electron field, a quark field, a Higgs field, and several more. The objects that we call fundamental particles are not fundamental. Instead they are ripples of continuous fields.

See Reason for the discreteness arising in quantum mechanics? for more information along these lines. In particular, note that compact operators (or more generally, operators with compact resolvents) have discrete spectra (see here and here). As this answer says:

There are several forms of discreteness in quantum theory. The simplest one is the discreteness of eigenvalues and the associated countable eigenstates. Those arise similarly to the discrete standing waves on a guitar string. The boundary conditions only allow certain standing waves that nicely fit into the enforced region in space. Even though the string is a continuous object, its spectrum becomes discontinuous and is naturally labeled with natural numbers.

Another reason for discreteness comes in with multi-particle systems. Quantum theory requires that a system that is realized in space-time contains a unitary representation of the symmetry group of space-time, the Lorentz group. In fact, you can define a particle in quantum theory as a subsystem that contains such a group representation. And because you can't have any non integer fraction of a unitary group representation, you need to have an integer number of them in your total system. So the number of particles is also an (expected) discrete feature, and it plays a role when you talk about single photons for example, that are either absorbed completely or not at all.

$\endgroup$
2
  • $\begingroup$ Yes this is a perspective which definitely goes along the lines sketched above. You got my vote. Yet, would be interesting to see what you said from a mathematical standpoint: how the discrete particles emerge from a quantized field rather than from a classical one? $\endgroup$ Aug 27, 2020 at 11:16
  • $\begingroup$ @MircoA.Mannucci I added a bit more. $\endgroup$
    – user76284
    Sep 25, 2020 at 21:30
5
$\begingroup$

Bill Lawvere has, for a long time now, promoted the idea that the discrete emerges as a limiting case by abstracting from the continuous. At the most general level, this manifests in the distinction between cohesive and constant (i.e. abstract) toposes of sets: Quantifiers and Sheaves, Continuously Variable Sets, Variable Quantities and Variable Structures in Topoi, Toward the Description in a Smooth Topos of the Dynamically Possible Motions and Deformations of a Continuous Body, Cohesive Toposes and Cantor's 'lauter Einsen', etc...

This line of thought is worked out more precisely with the concept of Axiomatic Cohesion wherein, roughly speaking, a topos $\mathscr{E}$ is exhibited as cohesive relative to a base topos $\mathscr{S}$ via a string of adjoints between them describing how the discrete spaces $X \in \mathscr{S}$ sit inside the larger topos $\mathscr{E}$ of more general (cohesive, combinatorial, etc...) spaces. Lawvere gave some lectures on this topic in Como in 2008 and there are accompanying lecture notes. The nLab page for cohesive toposes is also quite helpful.

To bring things back down to earth a little bit, in Left and Right Adjoint Operations on Spaces and Data Types, he descirbes, in the last section, the following situation. Suppose we have, in a cartesian closed category $\mathscr{C}$, a commutative ring object $R$ which we regard as the 'one-dimensional continuum'. We can form the correspinding 'complex numbers' ring $C = R[i]$ by defining complex multiplication on $R^2$ in the usual way. Inside of $C$ sits the multiplicative subgroup $S^1$ corresponding to the 'circle'. Finally, since we are in a cartesian closed category, we can extract from the map space $(S^1)^{(S^1)}$ the subspace $Z$ of those endomorphisms of $S^1$ which are group homomorphisms. This $Z$ can therefore be regarded as the 'integers' although it is important to note that it will not necessarily be the usual integers object $N[-1]$ derived from a natural numbers object $N$ in $\mathscr{C}$.

$\endgroup$
2
  • $\begingroup$ you got my vote, and you are dangerously closed to get the GREEN. I was aware of Lawvere's effort in this direction, though I have to say I did not have him in mind when I wrote the question. So, what is GREEN? If you read the previous answers, they all have something to do with the fundamental issue. Now, although I am pretty sure that Lawvere 's approach goes a very long way toward creating a fraework for the general theory of apporximating the discrete by the continuum I am not equally sure that it is comprehensive enough? Any thoughts? Anyways, KUDOS! $\endgroup$ Aug 27, 2020 at 12:09
  • 1
    $\begingroup$ Are there examples of $R$ which give an interesting $Z$ by this construction? $\endgroup$
    – user44143
    Sep 26, 2020 at 2:44
4
$\begingroup$

(Answer related to the one of Dustin Mixon.)

This appears as relaxation is discrete optimization: if you have an optimization problem $\min f(x)$ with a vector $x$ and the constraint that $x_i\in\{0,1\}$ for all entries $x_i$ of the vector $x$, this often becomes very hard. A common approach is to relax the constraint to $x_i\in [0,1]$. This is a continuous problem which is often easier to solve. There are several instances of the phenomenon of exact relaxation where you can prove that the relaxed problem happens to have a solution which is binary "by accident/magic".

$\endgroup$
3
  • $\begingroup$ very interesting! Can you elaborate more? Is there any partial result in the way of justifying the "magic"? I would think that the magic has to do with the fact that {0, 1} is the BOUNDARY of the unit interval, and that there is a convergent series of solutions which becomes close to 0 in all interior points. Am I off track? $\endgroup$ Aug 27, 2020 at 11:20
  • 1
    $\begingroup$ Typing "exact relaxation optimization" and "exact relaxation minimization" leads you to a few interesting papers. $\endgroup$
    – Dirk
    Aug 27, 2020 at 18:35
  • $\begingroup$ That answer is totally unimodular,man. $\endgroup$ Aug 28, 2020 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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