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

Abstract

For $n>2$ and $k>1$, define the polynomial \[F_{n,k}(x) = Φ_n(1 + x + \cdots + x^k),\] where $Φ_n$ denotes the $n$-th cyclotomic polynomial. The \emph{cyclotomic conjecture} proposed by Gimbert (1999) exactly describes the irreducibility of $F_{n,k}(x)$ over $\mathbb{Q}$ in terms of $n$ and $k$. Conde, Gimbert, González, Miller and Miret (2014) established that the cyclotomic conjecture, if true, would imply the non-existence of almost Moore digraphs - a well-known open question concerning the directed degree-diameter problem. In this article, we prove the cyclotomic conjecture and, as a consequence, show that there are no almost Moore digraphs with maximum out-degree $d$ and diameter $k$ for any $d>1$ and $k>2$.

Disclosure

“Acknowledgements The authors thank Gaurish Korpal for helpful comments. AI statement We acknowledge the use of AI tools during the ideation phase. We declare that the text is not AI-generated. References [1] Edy T. Baskoro, Arnau Messegué, and Josep M. Miret. New results regarding the permutation cycle structure of almost Moore digraphs. Discrete”

PDF page 15

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-23T05:06:53.161839Z

Structural counts