🔢 mathematics

Linear Logic and the Hilbert Scheme

This paper introduces a geometric model of shallow multiplicative exponential linear logic (MELL) using the Hilbert scheme to interpret proofs as locally projective schemes, demonstrating that this framework is invariant under cut-elimination and revealing deep connections between proof theory and algebraic geometry.

Original authors: William Troiani, Daniel Murfet

Published 2026-03-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: William Troiani, Daniel Murfet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Turning Math Proofs into Geometric Shapes

Imagine you have a complex instruction manual for building a robot. In the world of computer science and math, this manual is called a proof. Usually, we read these proofs as a sequence of logical steps: "If A is true, then B is true."

This paper proposes a radical new way to look at these proofs. Instead of reading them as a list of sentences, the authors suggest we should build them as physical landscapes.

Think of a proof not as a story, but as a map.

The "atoms" of the proof (the basic building blocks) are like cities on a map.
The rules of logic are like roads connecting those cities.
A complete proof is a specific geometric shape (a "scheme") formed by how those roads are laid out.

The authors are asking: What does the map look like when we add a special "magic" ingredient to our logic?

The Ingredients: The "Normal" Logic vs. The "Magic" Logic

To understand the paper, we need two types of logic:

Multiplicative Logic (The "Normal" Stuff):
This is like a standard construction site. You have materials (formulas) and you connect them. If you have a brick and a beam, you can join them to make a wall. In the authors' previous work, they showed that these connections are like simple equations (e.g., $x = y$ ). If you have a proof, you can draw it as a set of lines where variables meet. It's like solving a simple algebra puzzle.
Exponential Logic (The "Magic" Stuff):
This is the tricky part. In linear logic, there is a symbol called ! (pronounced "bang"). It represents a "cofree coalgebra," which is a fancy way of saying: "You can copy this material as many times as you want, or throw it away."
- In normal logic, if you use a resource, it's gone.
- With the ! operator, you can duplicate it (like copying a file) or delete it (like trashing a draft).

The problem is: How do you draw a map of something that can copy itself?

The Solution: The "Hilbert Scheme" (The Infinite Copy Machine)

The authors realized that to map the "magic" part of the logic, they needed a new kind of geometry. They used a tool called the Hilbert Scheme.

The Analogy: The "Equation of Equations"

Normal Proofs: Imagine you have a set of equations like $x = y$ and $y = z$ . You can draw this as a single line connecting three points.
Magic Proofs (Exponentials): Now, imagine you have a machine that can take the equation $x = y$ $x = y$ and turn it into many different versions of itself. Maybe sometimes it becomes $x = z$ $x = z$ , and other times $x = w$ $x = w$ .
- The "Hilbert Scheme" is like a control panel for this machine.
- Instead of just drawing the line $x=y$ , you draw a space of all possible lines.
- The "magic" rules (like the Contraction rule, which copies a formula) become rules that tie the knobs on the control panel together.

In simple terms:

Multiplicative Logic = Equations between variables ( $x = y$ ).
Exponential Logic = Equations between the equations themselves (The rule that says "The way $x$ relates to $y$ must be the same as the way $x$ relates to $z$ ").

The Hilbert Scheme is the geometric object that holds all these "equations about equations." It's a shape that changes its form depending on how you copy or delete the parts of the proof.

The Main Discovery: The Shape Doesn't Change

The most exciting part of the paper is what happens when you run the program (or in math terms, perform "cut-elimination").

In computer science, running a program means simplifying it. You take a complex instruction and reduce it to a simpler one. In logic, this is called cut-elimination.

The Question: If I take a complex proof and simplify it, does the geometric shape I built for it change? Does the map get destroyed?
The Answer: No. The authors proved that even though the proof looks different on paper, the underlying geometric shape (the scheme) remains exactly the same.

The Analogy:
Imagine you have a complex origami crane. You unfold it, fold it differently, and unfold it again. The paper looks different at every step. But the authors proved that if you look at the "shadow" the paper casts on the wall (the geometric scheme), the shadow never changes. The shape is an invariant.

This is huge because it means the "geometry" captures the true essence of the computation, regardless of how messy the steps look.

A Concrete Example: The Church Numerals

The paper uses "Church Numerals" (a way of representing numbers like 0, 1, 2 in logic) to show how this works.

The Number 2: In this logic, the number 2 is a proof that says "Do this action twice."
The Geometry: When they map the number 2 using their new method, the Hilbert Scheme reveals a specific geometric pattern.
The Result: The geometry shows that the "variables" inside the proof are related in a way that mathematically forces the number 2 to behave like 2. The "equations between equations" (the knobs on the control panel) lock together to create the value 2.

Why Does This Matter?

New Connections: It connects two worlds that usually don't talk to each other: Proof Theory (how we prove things) and Algebraic Geometry (the study of shapes defined by equations).
Understanding Computation: It suggests that computation isn't just about moving data around; it's about navigating a geometric landscape.
Future Potential: The authors hope this will help us understand more complex types of logic (like those used in quantum computing or advanced AI) by treating them as geometric objects.

Summary in One Sentence

This paper builds a new kind of "map" for computer logic proofs, showing that even when we use "magic" rules to copy and delete parts of a proof, the underlying geometric shape stays perfectly stable, revealing that computation is really just geometry in disguise.

1. Problem Statement

The paper addresses the challenge of providing a geometric interpretation for Multiplicative Exponential Linear Logic (MELL), specifically focusing on the exponential fragment (the ! modality).

Context: Previous work (specifically by the authors in [18]) established that proofs in Multiplicative Linear Logic (MLL) can be modeled as systems of linear equations, where the elimination of variables corresponds to cut-elimination.
The Gap: While MLL proofs correspond to equations between formulas, the exponential rules (Promotion, Dereliction, Contraction, Weakening) in MELL introduce a higher-order structure. The authors ask: What kind of equations, and thus what kind of geometry, represent the deduction rules associated with the exponential?
The Specific Challenge: Standard algebraic geometry models (using ideals and varieties) struggle to capture the semantics of the exponential !, which represents a "cofree coalgebra" or a space of proofs. The authors seek a model where the exponential is interpreted as a space of equations (equations between equations).

2. Methodology

The authors introduce a geometric model using algebraic geometry, specifically the Hilbert scheme, to interpret a restricted class of proofs called "shallow proofs."

A. Shallow Proofs

The model is initially restricted to shallow proofs (Definition 2.0.4), which satisfy:

All edges are labeled by formulas of depth $\le 1$ (where depth is defined inductively; atomic formulas have depth 0, and ! increases depth).
No nested boxes (no ! inside !).
The interior of every box is a "nearly linear" proof net (a specific structural constraint ensuring paths behave well).

B. The Geometric Construction

For every shallow proof $\pi$ , the authors construct a pair of schemes $(X(\pi), S(\pi))$ :

The Ambient Scheme $S(\pi)$ : A disjoint union of projective spaces ( $\coprod \mathbb{P}^n_k$ ).
- Atomic formulas map to $\mathbb{P}^1$ .
- Multiplicative connectives ( $\otimes, \parr$ ) map to Segre embeddings of products of projective spaces.
- The exponential !B maps to a disjoint union of Hilbert schemes (or projective spaces representing them) parameterizing closed subschemes of the space associated with $B$ .
- $S(\pi)$ represents the "atomic degrees of freedom" (coordinates) available in the proof.
The Proof Scheme $X(\pi)$ : A closed subscheme of $S(\pi)$ .
- $X(\pi)$ is defined by intersecting the subschemes associated with each link (Axiom, Cut, Tensor, Par, Dereliction, Promotion, Contraction, Weakening).
- Multiplicative Links: Defined by diagonals or graphs of Segre embeddings (standard linear equations).
- Exponential Links:
  - Dereliction (?A $\to$ A): Modeled using the universal closed subscheme of the Hilbert scheme. It introduces parameters that define the relationship between the equation space and the formula space.
  - Promotion (!B): Modeled by the graph of a morphism between Hilbert schemes. This captures the idea that promoting a proof creates a "space of proofs."
  - Contraction (?A $\otimes$ ?A $\to$ ?A): Modeled by identifying parameters (coefficients) of the equations associated with the two inputs, effectively creating "equations between equations."

C. Cut-Elimination Invariance

The core technical achievement is proving that the geometric model is invariant under cut-elimination. For any reduction step $\gamma: \pi \to \pi'$ , the authors construct explicit morphisms $S_\gamma$ and $T_\gamma$ between the ambient schemes and prove that they restrict to mutually inverse isomorphisms between the proof schemes $X(\pi)$ and $X(\pi')$ .

3. Key Contributions

Geometric Interpretation of the Exponential:
The paper provides the first concrete geometric model where the exponential modality ! is interpreted via the Hilbert scheme. The key insight is that while multiplicative proofs correspond to equations $x=y$ , exponential proofs correspond to equations between these equations (e.g., identifying the coefficients of polynomial equations).
Invariance Theorem (Theorem 3.1.3):
The authors prove that the locally projective pair $(X(\pi) \hookrightarrow S(\pi))$ is an invariant of proof nets under cut-reduction. This establishes the construction as a valid categorical interpretation of the shallow fragment of MELL.
Explicit Construction for Shallow Proofs:
The paper provides a rigorous, step-by-step definition of how to associate schemes to every link type in a shallow proof net, including the complex handling of Promotion and Dereliction using the representability of the Hilbert functor.
Analysis of Church Numerals:
The authors demonstrate the model with a detailed example using Church numerals (specifically $2X$ and $0X$ ).
- They show how the geometric content of the exponential (the "space of proofs") captures the arithmetic of the numeral.
- They illustrate how the Contraction rule imposes constraints on the coefficients of the polynomials defining the subschemes, effectively performing the arithmetic operation (e.g., $x = \phi^2 z$ for the numeral 2).

4. Results

Main Theorem: For any cut-reduction step $\gamma: \pi \to \pi'$ in the shallow fragment, there exists a commutative diagram in the category of schemes where the bottom row (the map between proof schemes $X(\pi)$ and $X(\pi')$ ) is an isomorphism.
Connection to Elimination Theory: The model generalizes the previous MLL result where cut-elimination corresponds to the elimination of variables. In the exponential case, cut-elimination corresponds to the elimination of parameters defining the equations, linking the process to the Buchberger algorithm and Gröbner bases (Remark 3.2.2).
Limitations: The model currently relies on the "shallow" restriction. The authors note that extending this to arbitrary MELL proofs requires overcoming technical hurdles related to the local freeness conditions in Lemma 3.0.10, which currently fails for non-shallow proofs (e.g., nested boxes).

5. Significance

Bridging Proof Theory and Algebraic Geometry: This work establishes a deep, non-trivial connection between the structural rules of linear logic and the moduli spaces of algebraic geometry. It suggests that the "geometry of interaction" can be realized through the parameterization of subschemes.
New Semantics for Exponentials: By interpreting ! as a Hilbert scheme, the paper offers a fresh perspective on the exponential modality, viewing it not just as a cofree coalgebra but as a moduli space of proofs.
Future Directions:
- Generalization: The authors propose extending the model to full MELL using a more general Hilbert scheme (parameterizing closed subschemes of projective schemes rather than just graded modules) to handle nested boxes.
- Connections to Other Models: The paper suggests investigating the relationship between this Hilbert scheme model and other MELL models involving matrix factorizations and quantum error correction codes.
- Classification: It opens the question of classifying which Hilbert functions arise specifically from valid proofs, potentially leading to new correctness criteria for proof nets.

In summary, this paper successfully constructs a geometric model for a significant fragment of linear logic, demonstrating that the complex structural rules of exponentials can be faithfully captured by the geometry of the Hilbert scheme, thereby unifying proof-theoretic reduction with algebraic geometric invariance.