New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

This paper presents new lower bounds for the degree/diameter problem, specifically $N(12,5)\ge 34{,}992$ and $N(16,5)\ge 147{,}456$, achieved through a novel discovery process where the author interacted directly with a standard web-accessible LLM to construct explicit graphs without using custom agent frameworks or pre-defined search strategies.

The Gist

The Big Picture: A Math Puzzle and a Digital Partner

Imagine a giant puzzle called the Degree/Diameter Problem. The goal is to build the largest possible "city" (a network of points and lines) where two rules are strictly followed:

1. The Degree Rule: Every building (point) can have at most a certain number of roads (lines) connecting to it.
2. The Diameter Rule: No matter which two buildings you pick, you must be able to drive from one to the other in a very short number of steps (no more than 5 steps).

Mathematicians have been trying to build the biggest possible cities that follow these rules for decades. The bigger the city, the better the score.

The Breakthrough:
This paper reports that a researcher, working alone with a standard web browser and an AI chatbot (ChatGPT), built two new "cities" that are significantly larger than any previously known ones.

• City A: A network with 34,992 buildings.
• City B: A network with 147,456 buildings.

Both cities follow the rule that you can get anywhere in 5 steps or less, and no building has more than 12 or 16 roads, respectively. These numbers beat the previous world records.

How They Did It: The "Controller" and the "Fiber"

The secret to building these massive cities wasn't just guessing. The researcher and the AI discovered a clever way to break the problem into two smaller, manageable pieces. Think of it like building a massive hotel chain:

1. The Controller (The Blueprint): Imagine a small, simple map of a few key hubs. This is the "Controller." Its job is to figure out the general direction. In this case, the AI found a small map with 144 hubs that ensures you can get from any hub to any other hub in exactly 5 steps without ever turning around immediately (a "non-backtracking" walk).
2. The Fiber (The Rooms): Now, imagine that at every single hub on that small map, you don't just have one building. Instead, you have a massive, complex tower of rooms. This is the "Fiber." The AI figured out a mathematical "elevator system" (using algebra and finite fields) that tells you exactly how to move between rooms in these towers based on which road you take.

The Magic Trick:
The genius of the discovery was realizing that if you get the small map (Controller) right, and you get the elevator system (Fiber) right, you can combine them to create a giant city. The small map handles the "big picture" navigation, and the elevator system handles the "fine details" of moving between millions of specific points.

The Human-AI Collaboration: A Dance of Guidance

This paper is unique because it doesn't claim the AI did the math alone, nor that the human did it alone. It describes a specific way they worked together:

• No Super-System: The researcher didn't build a complex robot or a specialized software engine. They just used the standard ChatGPT website, like anyone else.
• The Human as the Captain: The researcher acted like a ship captain. They didn't tell the AI how to build the elevator or what the map should look like. Instead, they gave high-level instructions like:
  • "Don't just copy old ideas."
  • "If we hit a dead end, stop and rethink the whole strategy."
  • "Give me a reason to believe this new idea will work before we try to build it."
• The AI as the Explorer: The AI explored thousands of mathematical possibilities. It tried many ideas that failed. When it got stuck, the human captain would say, "Stop, that path is a dead end. Try a different angle."

The "Aha!" Moment:
For a long time, the AI was trying to fix small errors in bad designs (like patching a leaky boat). The human captain stopped this and asked for a "new principle." The AI then proposed the Controller/Fiber idea (the "route-chart lift"). This was the moment the abstraction appeared. Once this new principle was found, the rest was about refining the details to break the records.

What This Paper Does Not Claim

It is important to stick to what the paper actually says:

• It is not a general proof that AI can solve all math problems. This was one specific case study.
• It is not about medical or clinical applications. This is purely about graph theory (math).
• It is not about the AI writing the final paper. The human researcher verified every step, wrote the proofs, and took responsibility for the final result. The AI was a tool for discovery, not the author.

Summary

Think of this paper as a logbook of a successful expedition. A human explorer used a digital compass (the AI) to navigate a mathematical jungle. The explorer didn't let the compass drive the car; they steered it, told it when to stop, and asked it to think of new routes. Together, they found a path to a massive, previously undiscovered mathematical structure, proving that even a standard browser-based AI, when guided by a human with a clear strategy, can help break world records in pure mathematics.

Technical Summary

Technical Summary: New Lower Bounds for the Degree/Diameter Problem via Interaction with a Browser-Accessible LLM

Problem Statement
The paper addresses the degree/diameter problem, which seeks to determine $N(\Delta, D)$, the maximum number of vertices in a simple undirected connected graph with a maximum degree of at most $\Delta$ and a diameter of at most $D$. While the Moore bound provides an upper limit for $N(\Delta, D)$, the exact value remains unknown for most parameter pairs. The specific focus of this work is improving the known lower bounds for diameter $D=5$ with maximum degrees $\Delta=12$ and $\Delta=16$.

Methodology
The study documents a mathematical discovery process conducted through a long dialogue with a browser-accessible Large Language Model (ChatGPT, identified as gpt-5-5-pro in metadata) via its standard web interface. Crucially, the author did not employ any external orchestration layers, custom agent frameworks, automated evaluators, or formal proof assistants. The search relied solely on the LLM's interactive capabilities and the author's meta-level interventions.

The discovery process involved:

1. Initial Exploration: Surveying literature and attempting various construction methods (e.g., permutation lifts, voltage graphs, random regular graphs), most of which failed to yield a certificate.
2. Abstraction Shift: A pivotal transition occurred when the LLM proposed a "route-chart lift" principle. This decomposed the problem into two independent finite design tasks:
   • Controller Problem: Constructing a small auxiliary graph (the "controller") where every pair of vertices is connected by a non-backtracking walk of a specific length.
   • Fiber Chart Problem: Constructing linear-algebraic data (a "route chart") over a finite field such that specific controllability matrices are nonsingular for all reduced words of the target length.
3. Meta-Level Interventions: The author guided the search by imposing constraints (e.g., avoiding web search, demanding ideas not essentially contained in existing literature, and requesting "a priori" reasons for success) and intervening when the search drifted into local repair or trial-and-error.

Key Contributions
The paper makes two primary contributions:

1. Improved Mathematical Lower Bounds:
   The authors present explicit constructions of simple undirected graphs that establish new lower bounds:

   • $N(12, 5) \ge 34,992$ (improving the previous record of 29,621).
   • $N(16, 5) \ge 147,456$ (improving the previous record of 132,496).

   These graphs are constructed by lifting a specific 144-vertex controller graph (derived from a 6-vertex multigraph via a $C_4 \times C_6$ voltage assignment) using a universal route chart over finite fields $\mathbb{F}_3$ and $\mathbb{F}_4$, respectively. The diameter is proven to be exactly 5.

2. Process Analysis of Human-AI Collaboration:
   The paper provides a detailed transcript-based analysis of a mathematical discovery process conducted without external automation. It highlights how meta-level interventions (such as requesting new principles or stopping local repair attempts) helped steer the LLM toward a successful abstraction (the route-chart lift) and a final solution. The authors emphasize that the LLM acted as an interactive discovery engine, while the author verified all claims, code, and certificates.

Results
The constructed graphs $G_3$ (12-regular, 34,992 vertices) and $G_4$ (16-regular, 147,456 vertices) satisfy the diameter constraint of 5. The improvements represent increases of approximately 18.13% and 11.29% over previous records, respectively. The constructions are verified through finite computation of the controller's non-backtracking walks and the nonsingularity of the controllability matrices for all reduced words of length 5.

Significance and Claims
The paper modestly claims significance in two areas:

• Mathematical: It provides the first explicit constructions for these specific parameters, pushing the known lower bounds closer to the Moore upper bounds.
• Methodological: It serves as a case study demonstrating that significant mathematical discovery is possible using only a standard browser interface for an LLM, without complex agentic systems. The authors explicitly state they do not treat the LLM as an author or autonomous prover; the human researcher retains full responsibility for the mathematical validity.

The paper does not claim that this specific strategy is generally effective or that the LLM possesses general mathematical reasoning capabilities beyond this specific instance. It frames the work as an observational report of a single successful case where human guidance and LLM generation combined to solve a specific open problem in graph theory.