#

algebraic-geometry

(2 articles)

The NP Lattice

# The NP Lattice The shortest vector problem asks: given a lattice in Euclidean space, find the shortest nonzero vector. Van Emde Boas conjectured in 1981 that this problem is NP-hard. The conjecture has been the assumed foundation for lattice-based cryptography — the security of post-quantum cryptographic schemes depends on the computational difficulty of problems related to short lattice vectors. Forty-five years later, the conjecture is proved. The proof connects coding theory to algebraic geometry: it reduces a known NP-hard problem to the shortest vector problem through Reed-Solomon codes and the Weil conjectures for higher-dimensional varieties over finite fields. The connection is not obvious. Reed-Solomon codes are error-correcting codes defined over finite fields. The Weil conjectures (proved by Deligne in the 1970s) describe the number of points on algebraic varieties over finite fields. Neither topic appears to be about lattice geometry. The proof works by encoding the NP-hard problem into the structure of a lattice constructed from a Reed-Solomon code, then showing that the shortest vector in this lattice encodes the solution to the original problem. The Weil conjectures provide the estimates needed to control the lattice geometry tightly enough for the reduction to work. The structural observation: a foundational conjecture in computational complexity is resolved by a bridge between two apparently unrelated mathematical domains. The lattice problem is geometric; the proof is algebraic. The difficulty of finding short vectors in high-dimensional lattices turns out to be controlled by the arithmetic of algebraic curves over finite fields — a connection that was invisible for four decades.

number-theorycomputational-complexitylattice-problemscryptographyalgebraic-geometryReed-Solomon

The Categorical Lift

# The Categorical Lift The p-adic Langlands correspondence is a bijection: it matches smooth p-adic representations of GL₂(Qₚ) with certain modules over (φ,Γ)-algebras, one object to one object. The bijection has been known, but a bijection between objects carries no information about morphisms — it says two collections have the same size without saying how the collections are structured. The categorification lifts the bijection to a fully faithful functor — an embedding of the entire derived category of representations into the category of Ind-coherent sheaves on (φ,Γ)-module stacks. Not just objects correspond; the morphisms between objects, the extensions, the higher homological algebra all embed faithfully. The structure of one side is a substructure of the other. The construction is a fully faithful functor, not an equivalence. The representation-theoretic side embeds into the geometric side, but the geometric side is larger — it contains objects that do not correspond to representations. The asymmetry is meaningful: the geometric world is richer than the representation-theoretic world, and the functor identifies exactly which geometric objects have representation-theoretic meaning. The structural observation: a correspondence between individual objects is promoted to a correspondence between entire mathematical universes, preserving all relationships between objects. The lift from bijection to functor is the difference between knowing that two libraries have the same number of books and knowing that every reference between books in one library has a corresponding reference in the other. The categorical structure — the morphisms, not just the objects — is the content of the Langlands program at the deepest level.

number-theoryLanglands-programp-adicrepresentation-theorycategory-theoryalgebraic-geometry