Blurring the Lines between Discrete and Continuous Mathematics
Benjamin Skuse
The 11th Heidelberg Laureate Forum Spark Sessions – a selection of short plenary talks by laureates lasting 15-20 minutes each – were nothing if not eclectic, ranging from the inspirational to the absurd and everything in between.
For example, on Tuesday, 24 September, during the week’s first Spark Session, attendees were learning from Andrei Okounkov (Fields Medal – 2006) a new appreciation for the partition, a simple mathematical object that is central to a lot of today’s advanced mathematics. Moments later, they were absorbed by an extended anecdote from Ken Thompson (1983 Turing Award) involving a gang of wild animals stealing nuts from his home, and how he went about dealing with it.
The second Spark Session on Thursday, 26 September, was equally eclectic, with perhaps a small bias towards discussions of how AI will reshape society. But one talk stood out in terms of providing a very different, and perhaps useful, perspective on the entire field of mathematics: “Discrete or Continuous: Two Worlds of Math?” by Hungarian mathematician László Lovász.
The Right Mathematics for the Job
Lovász shared the 2021 Abel Prize with Avi Wigderson “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.” Lovász’s foundational contribution can be traced right back to his teenage years, when his mathematical hero and fellow Hungarian Paul Erdős inspired Lovász to enter the field of combinatorics, with specific emphasis on the properties of graphs.
Both combinatorics (the mathematics of patterns and counting patterns) and graph theory (the mathematics of connections) concern objects with discrete values. And Lovász and his peers studying these ‘discrete’ topics soon realized in the 1970s that this type of mathematics was directly applicable to the burgeoning field of computer science. As a result, Lovász’s entire career during the 20th Century straddled discrete mathematics and computer science, delivering foundational and influential discoveries in both fields along the way.
What he had not done until around the turn of the millennium was dip his toes into the more conventional world of continuous mathematics, to see where the boundaries lie between discrete and continuous mathematics, what the connections are, and whether analyzing the interactions between discrete and continuous worlds can open deeper mathematical understanding.
Interaction Between Two Different Worlds
In Lovász’s Spark Talk, he began by describing how the methods and concepts used in discrete and continuous mathematics are completely different. Continuous mathematics deals with objects like the real line and differential equations, and uses derivatives, integrals, Fourier expansions, and many more well-established methods of analysis. Objects in discrete mathematics are individually distinct, such as the integers. “In discrete mathematics, we also have methods – for example, induction or counting or random construction of a finite object – and these are also becoming more and more successful,” he said.
Where these two distinct branches of mathematics meet is the area that interests Lovász. The most obvious interaction between the two is in computing where continuous structures are, by necessity, discretized. “We approximate various continuous objects, like smooth surfaces, by some discrete objects, like a collection of triangles, which altogether approximate the surface,” offered Lovász. In fact, any numerical solution to a problem involving partial differential equations involves discretization.
What about the opposite of discretization; to make a discrete problem continuous? “Take a piece of steel – is this a discrete or continuous object?” asked Lovász. “Now we know that it’s a network of a finite number of atoms – it’s a discrete object – but if an engineer has to determine what happens if this steel is a part of a bridge, then he doesn’t go into analyzing all these atoms.” An engineer will instead approximate the discrete piece of steel as a continuous object, whose differential equations involve functions for density, pressure, temperature, etc. “You can solve these differential equations and the bridge stands.”
Phenomena Straddling Both Worlds
Though these connections had been known for quite some time, few had attempted to study and measure them rigorously until mathematicians began to look at the limit of graph sequences at the beginning of the 21st Century. “Suppose that there is a sequence of finite graphs or finite grids, and suppose that they get larger and larger in an infinite sequence,” Lovász explained.
A good example is complete graphs. These are objects where every pair of distinct vertices is connected by a unique edge. To look at, even a complete graph with 99 vertices will be almost identical to a complete graph with 100 vertices.
“As you go along, they become more and more similar, which means they become less and less distinguishable by some well-defined statistics,” said Lovász. “Several people contributed to the theory of what is the limit of this kind of graph sequence, and continuous objects appear in the limit.”
Lovász is most interested today in cases where a phenomenon appears in both the continuous and discrete setting. For example, famously the power series expansion connects discrete sequences and continuous analytic functions, like the following:
\[ f(x) = \frac{1}{1 – x} = \sum_{n=0}^{\infty}x^n, \quad |x| < 1. \]
This type of connection appears deep, and intuition and insight gained from considering one is often extremely useful in the other.
Getting Greedy
To illustrate that these types of connections can be found in much more obscure areas, Lovász turned to the familiar: graph theory. For this, he introduced some terminology. Matroids generalize various mathematical objects, such as graphs and vector spaces, and consist of two elements: the ground set and the independent set. For example, to define a matroid from a graph, we can establish the ground set to be the set of edges and then the independent sets as those sets of edges that do not contain a cycle. A cycle consists of a sequence of adjacent and distinct vertices in a graph, except for the first and last vertices which are one and the same.
Though this appears highly abstract, matroids can model many graph theory problems, and vice versa. Proving statements for matroids also proves them for all the objects matroids generalize, making matroid theory a powerful tool in many areas of discrete mathematics.
One area is optimization. If an optimization problem has the structure of a matroid, then the appropriate ‘greedy algorithm’ will solve it optimally. A greedy algorithm essentially makes locally optimal choices at each step to find a globally optimal solution to that optimization problem.
The greedy algorithm was first formulated as a solution to the minimal spanning tree problem by Czech mathematician Otakar Borůvka in 1926. A spanning tree for a graph is a subset of vertices that has no cycles but still connects every edge. Many spanning trees might be possible, but the minimal spanning tree has the minimum possible total edge weight.
An easy way to understand this is by picturing a telecommunications company laying broadband cables in your local area. If the company has to bury the cable only along certain roads (edges), they could draw a graph containing the houses (vertices) connected by those roads, and assign a larger edge weight to those roads where laying cable might be more expensive. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house, and a minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.
Borůvka’s greedy algorithm was designed to build up a spanning tree by selecting edges one by one so a cycle is never created and the ‘cheapest’ edge is always chosen that gives a new connection. “This algorithm gives the exact optimum and it’s a basic algorithm in matroid theory,” adds Lovász.
“It turns out that in the continuous setting there is a technical but very important theorem that says that if you have a submodular set function on the Borel sets, there is a charge (a finitely additive measure) which is less than or equal to this submodular function and equal to the beginning section,” said Lovász. Though he said that the details are unimportant, the point he was making was simple: “It’s sort of the continuous version of the greedy algorithm.”
With many other examples across mathematics, there is an entire discipline devoted to studying the connections between discrete and continuous mathematics, gradually weaving the two disparate fields together. But could this approach straddling discrete and continuous mathematical worlds be a clue as to how to tackle fundamental problems in other sciences, such as physics? Could it even help us intuit the nature of reality? Broadly speaking, conventional thinking suggests the universe is a four-dimensional continuum of space and time containing discrete objects. Might we be able to view the whole as both a continuum and a (vast) discrete structure, leaning on both perspectives to gain new insights?
In his short Talk, Lovász did not have time to dig into these deep questions. But he certainly provided food for thought.
The entire Spark Session, including Lovász’ talk, can be viewed below.
The post Blurring the Lines between Discrete and Continuous Mathematics originally appeared on the HLFF SciLogs blog.