IV - Discrete Mathematics & Algorithms

The Mathematics of Logic and Finite Structures

Discrete Mathematics and Algorithms are the mathematics of things that can be counted and steps that can be carried out one at a time. This matters more than it looks like at first. However continuous the mathematics of the other sections may be, the moment any of it is actually run on a machine, it becomes finite and discrete. Real numbers become finitely many bits, smooth motion becomes a sequence of steps, and every computation is, underneath, a finite process on a finite machine. Discrete mathematics is what stays exact under that translation: the study of structures with no rounding and no limit-taking, where objects can be counted precisely and reasoning proceeds one careful logical step at a time. Taken far enough, this same viewpoint turns back on computation itself and asks the sharpest question there is — not how fast a problem can be solved, but whether it can be solved at all, and what a machine can never decide.

Within the Compass, this section is the discrete counterpart to the continuous mathematics of Section II (Calculus to Optimization & Analysis). Where that section asks in what space an algorithm converges, this one asks what can be computed in the first place — the limits that constrain every method in the sections around it. It inherits the algebraic language of Section I (Linear Algebra to Algebraic Foundations), where the arithmetic of finite systems underwrites both the logic of machines and the primitives of secure communication. And it hands its counting arguments to Section III (Probability & Statistics), where enumerating possibilities becomes the first step in measuring how likely they are.

Two long arcs grow out of this section. The first is category theory. By this point the reader has met many different kinds of structure-preserving map — between groups, between spaces, between vector spaces — and is ready to see that these were all instances of a single pattern. Category theory is the language that names that pattern, describing mathematical structures entirely in terms of how their maps compose. In a sense, it is the natural summit of everything discrete and structural that comes before it. The second arc is cryptography, whose whole security rests on problems believed to be too hard to solve in reasonable time. That foundation was shaken by the arrival of the quantum computer, which can break some of the classical hardness assumptions outright. The response has been to rebuild encryption on new mathematical problems, drawn from the geometry of lattices, that are believed to resist quantum attack. This section develops both the attack and the defense, from the algorithm that threatens today's ciphers to the post-quantum schemes now being deployed to replace them.