🔢 mathematics

A proof of the cyclotomic conjecture and the non-existence of almost Moore digraphs

This paper proves the cyclotomic conjecture regarding the irreducibility of specific polynomials, thereby establishing the non-existence of almost Moore digraphs for any maximum out-degree $d>1$ and diameter $k>2$ .

Original authors: Jaskaran Kaur, Hitesh Kumar

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaskaran Kaur, Hitesh Kumar

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

Imagine you are a master architect trying to build the most efficient city possible. You have a strict rule: every building (a "node") can only send messages to a limited number of neighbors (the "degree"), and no message can take too many steps to reach any other building in the city (the "diameter"). In the world of mathematics, specifically a field called graph theory, this is known as the "degree-diameter problem." It's like trying to pack the maximum number of people into a room where everyone can only shake hands with a few people, and everyone must be able to say hello to everyone else within a specific number of introductions.

Mathematicians have long known there is a theoretical "perfect" city size, called the Moore bound, which represents the absolute maximum number of buildings you could possibly fit under these rules. However, these perfect cities are incredibly rare; they only exist in very simple, boring scenarios. This left mathematicians with a tantalizing question: What about cities that are just one building smaller than the perfect size? These are called "almost Moore digraphs." For decades, researchers have been hunting for these near-perfect structures, wondering if they exist for complex, large cities or if the laws of mathematics simply forbid them.

This paper, written by Jaskaran Kaur and Hitesh Kumar, acts as the final detective report that closes the case. The authors prove that these "almost perfect" cities do not exist for any complex scenario where the city has more than one outgoing connection per building and a path length greater than two. To solve this, they didn't just look at the city maps; they had to dive into the deep, abstract world of "cyclotomic polynomials." Think of these polynomials as the secret DNA or the underlying musical score of the city's structure. The paper proves a long-standing guess (the "cyclotomic conjecture") about how this DNA behaves. By showing that this mathematical DNA always breaks apart in a specific way when the city gets complex, they demonstrated that the "almost perfect" city is mathematically impossible to build.

The Mystery of the Missing City

In the world of directed networks (where connections have a specific direction, like one-way streets), mathematicians have a formula for the biggest possible city you can build with a given number of exits per building ( $d$ ) and a maximum travel time ( $k$ ). This formula, $M_{d,k} = 1 + d + \dots + d^k$ , is the "Moore bound." It's the theoretical ceiling.

We know that cities hitting this exact ceiling are almost non-existent. They only appear in trivial cases, like a simple loop or a fully connected hub. So, the big question was: What about cities that are just one step smaller? These "almost Moore digraphs" were the holy grail. If they existed, they would be the most efficient networks possible for complex systems.

For years, mathematicians checked small cases. They found some for specific, tiny setups, but for larger, more interesting numbers, the search came up empty. The problem was that proving they didn't exist required solving a very tricky puzzle involving cyclotomic polynomials. These are special mathematical expressions related to the roots of unity (think of them as the fundamental frequencies of a circle).

The Key to the Lock: The Cyclotomic Conjecture

The authors of this paper realized that the existence of these "almost perfect" cities depended entirely on a specific property of a polynomial called $F_{n,k}(x)$ . This polynomial is built by plugging a simple sum ( $1 + x + \dots + x^k$ ) into a cyclotomic polynomial ( $\Phi_n$ ).

In 1999, a mathematician named Gimbert proposed a "Cyclotomic Conjecture" to describe exactly when this polynomial $F_{n,k}(x)$ would break apart (be reducible) and when it would stay whole (be irreducible).

If the polynomial stays whole (irreducible), it acts like a solid, unbreakable block.
If it breaks apart (reducible), it splits into smaller pieces.

The connection is crucial: If the polynomial breaks apart in a specific way, it means an "almost Moore" city could exist. If the polynomial stays whole, the city is impossible. Previous researchers had proven this for small numbers, but the general case remained a mystery.

The Breakthrough: Proving the Conjecture

Kaur and Kumar stepped in to prove the conjecture for all numbers, not just the small ones. They treated the polynomial $F_{n,k}(x)$ like a complex machine and took it apart to see how its gears (the roots and coefficients) interacted.

They defined a helper polynomial, $q(x)$ , which is essentially the cyclotomic polynomial with a twist. They then analyzed the "greatest common divisor" between $q(x)$ and its mirror image, $q^\#(x)$ . This step was like checking if the machine had any loose screws that would cause it to fall apart.

Their analysis revealed a strict rule:

If $k$ is even: The polynomial breaks apart only if a specific number $n$ divides $k+2$ .
If $k$ is odd: The polynomial breaks apart only if $n$ is even and divides $2(k+2)$ .

In every other case, the polynomial remains irreducible (unbreakable).

The Final Verdict: No "Almost Perfect" Cities

With the conjecture proven, the authors applied the logic to the city-building problem. They showed that for any city with more than one exit per building ( $d > 1$ ) and a travel time of more than two steps ( $k > 2$ ), the mathematical conditions required for an "almost Moore" city to exist are never met.

The polynomial $F_{n,k}(x)$ stays irreducible in the exact way that prevents the city from forming. Consequently, the authors proved that no such digraphs exist.

This means that for any complex network you try to build under these rules, you cannot even get within one node of the theoretical maximum size. The gap between the best possible network and the theoretical limit is at least two nodes. The "almost perfect" city is a mathematical myth.

The paper concludes by confirming that the directed degree-diameter problem has a definitive answer for these parameters: the largest possible network is always at least two steps smaller than the Moore bound. The hunt for the "almost Moore" digraph is over; it never existed to begin with.

Technical Summary: A Proof of the Cyclotomic Conjecture and the Non-Existence of Almost Moore Digraphs

Problem Statement
The paper addresses two interconnected problems in algebraic graph theory and number theory. First, it seeks to resolve the Cyclotomic Conjecture proposed by Gimbert (1999), which concerns the irreducibility of the polynomial $F_{n,k}(x) = \Phi_n(1 + x + \dots + x^k)$ over the rational numbers $\mathbb{Q}$ , where $\Phi_n$ is the $n$ -th cyclotomic polynomial. Second, it addresses the Directed Degree-Diameter Problem, specifically the existence of "almost Moore digraphs." An almost Moore digraph is a directed graph with maximum out-degree $d$ and diameter $k$ having order $M_{d,k} - 1$ , where $M_{d,k} = 1 + d + \dots + d^k$ is the Moore bound. While Moore digraphs (order $M_{d,k}$ ) are known to exist only in trivial cases, the existence of almost Moore digraphs for $d > 1$ and $k > 2$ has remained an open question. Previous work by Conde et al. (2014) established that the truth of the Cyclotomic Conjecture implies the non-existence of such digraphs.

Methodology
The authors employ a combination of algebraic number theory and polynomial analysis to prove the conjecture. The core strategy involves analyzing the factorization of the polynomial $q(x) = s_k(x) - \zeta_n$ over the cyclotomic field $K = \mathbb{Q}(\zeta_n)$ , where $s_k(x) = 1 + x + \dots + x^k$ and $\zeta_n$ is a primitive $n$ -th root of unity.

Reduction to Field Irreducibility: The authors observe that the irreducibility of $F_{n,k}(x)$ over $\mathbb{Q}$ is linked to the irreducibility of $q(x)$ over $K$ . They define $g = \gcd(q, q^\#)$ , where $q^\#$ is the conjugate reciprocal of $q$ , and set $r = q/g$ .
Autocorrelation and Support Analysis: To prove the irreducibility of $r(x)$ over $K$ , the authors construct auxiliary polynomials $P(x) = (x-1)q(x)$ and analyze their autocorrelation coefficients $A_\ell(P)$ . By comparing these coefficients with those of a known polynomial $Q(x)$ , they derive constraints on the "support" (the set of indices of non-zero coefficients) of $P$ .
Trace and Norm Inequalities: Using the AM-GM inequality and properties of the trace and norm in the ring of integers $\mathcal{O}_K$ , the authors establish bounds on the number of non-zero coefficients. Specifically, they show that if $r(x)$ were reducible, the resulting polynomial $P$ would have a support size that contradicts the calculated trace sums.
Case Distinction: The proof is divided into two main cases based on the value of $k$ $k$ :
- Case $k \ge 3$ : The authors prove that $r(x)$ is irreducible over $K$ by showing that any hypothetical factorization leads to a contradiction regarding the support size of the associated polynomial $P$ .
- Case $k = 2$ : This boundary case is handled separately, utilizing specific properties of quadratic fields and direct computation of norms to establish irreducibility.

Key Contributions and Results
The paper provides a complete proof of the Cyclotomic Conjecture for all $n > 2$ and $k > 1$ .

Theorem 1.4 (Cyclotomic Conjecture):
- If $k$ is even, $F_{n,k}(x)$ is reducible over $\mathbb{Q}$ if and only if $n \mid (k+2)$ . In this case, it has exactly two irreducible factors.
- If $k$ is odd, $F_{n,k}(x)$ is reducible over $\mathbb{Q}$ if and only if $n$ is even and $n \mid 2(k+2)$ . In this case, it has exactly two irreducible factors.
- In all other cases, $F_{n,k}(x)$ is irreducible over $\mathbb{Q}$ .
Theorem 1.5 (Non-existence of Almost Moore Digraphs):
- As a direct consequence of Theorem 1.4 and the result by Conde et al. (2014), the paper proves that no almost Moore digraphs exist for any maximum out-degree $d > 1$ and diameter $k > 2$ .
- Consequently, for any digraph $G$ with maximum out-degree $d > 1$ and diameter $k > 2$ , the order $|V(G)|$ satisfies $|V(G)| \le M_{d,k} - 2$ .

Significance
The paper settles a long-standing conjecture in the field of algebraic graph theory. By proving the Cyclotomic Conjecture in full generality, the authors resolve the open question regarding the existence of almost Moore digraphs for all $d > 1$ and $k > 2$ . This result closes a significant gap in the directed degree-diameter problem, confirming that the Moore bound is not only unattainable for non-trivial cases but that the bound minus one is also unattainable. The methodology introduces a robust framework using autocorrelation coefficients and trace inequalities to analyze polynomial irreducibility over cyclotomic fields, which may have implications for similar problems in algebraic combinatorics. The authors note that while the non-existence of order $M_{d,k}-1$ is now established, the question of whether digraphs of order $M_{d,k}-2$ exist remains open.

The Mystery of the Missing City

The Key to the Lock: The Cyclotomic Conjecture

The Breakthrough: Proving the Conjecture

The Final Verdict: No "Almost Perfect" Cities

Technical Summary: A Proof of the Cyclotomic Conjecture and the Non-Existence of Almost Moore Digraphs

More like this