Integral Cayley graphs

DefinitionInteger matrix with integral spectrum#✓fully proved

A square integer matrix is integral: every complex root of its characteristic polynomial (every eigenvalue) is an integer.

def HasIntegralSpectrum {n : Type*} [Fintype n] [DecidableEq n] (A : Matrix n n ℤ) : Prop :=
  ∀ μ : ℂ, (A.map (Int.castRingHom ℂ)).charpoly.IsRoot μ → ∃ k : ℤ, (k : ℂ) = μ

Used by 2

Used byThe Kourovka 19.50(b) integrality claim · The Kourovka 19.50(a) integrality claim

DefinitionThe Kourovka 19.50(a) integrality claim#✓fully proved

This is the proposition that for every finite group \(G\) and every subset \(R \subseteq G\) such that every element of \(R\) is an involution (\(r^2 = 1\) and \(r \ne 1\)), \(R\) is closed under conjugation (\(g r g^{-1} \in R\) for all \(r \in R\) and \(g \in G\)) and \(R\) generates \(G\), the Cayley graph \(\mathrm{Cay}(G, R)\) is integral. Here \(\mathrm{Cay}(G, R)\) has vertex set \(G\), distinct \(x\) and \(y\) being adjacent when \(x^{-1} y \in R\) or \(y^{-1} x \in R\), and a graph is integral when every eigenvalue of its integer adjacency matrix (every complex root of the characteristic polynomial of that matrix) is an integer.

def involutionCayleyGraphIntegral : Prop :=
  ∀ (G : Type) [Group G] [Fintype G] [DecidableEq G] (R : Set G),
    (∀ r ∈ R, r ^ 2 = 1 ∧ r ≠ 1) → (∀ r ∈ R, ∀ g : G, g * r * g⁻¹ ∈ R) →
    Subgroup.closure R = ⊤ → HasIntegralSpectrum ((SimpleGraph.mulCayley R).adjMatrix ℤ)

Uses 1 · Used by 1

Statement usesInteger matrix with integral spectrum

Used byCayley graphs on normal sets of involutions are integral

DefinitionThe 3-cycles (1 2 k)#✓fully proved

For a natural number \(n\), this is the set of \(3\)-cycles \((1\,2\,k)\) with \(3 \le k \le n\) in the symmetric group \(S_n\). With the points numbered \(0, 1, \dots, n - 1\), these are the permutations \((0\,1\,k) = (0\,1)(1\,k)\) with \(2 \le k < n\), products composed right to left; the set is empty when \(n < 3\).

def threeCyclesOneTwo (n : ℕ) : Set (Equiv.Perm (Fin n)) :=
  {σ | ∃ a b k : Fin n, a.val = 0 ∧ b.val = 1 ∧ 2 ≤ k.val ∧ σ = Equiv.swap a b * Equiv.swap b k}

Used by 1

Used byThe Kourovka 19.50(b) integrality claim

DefinitionThe Kourovka 19.50(b) integrality claim#✓fully proved

For \(n \ge 3\) let \(S\) be the set of \(3\)-cycles \((1\,2\,k)\) with \(3 \le k \le n\) on the points \(1, \dots, n\), and let \(R = S \cup S^{-1}\), a subset of the alternating group \(A_n\). This is the proposition that for every \(n \ge 3\) the Cayley graph \(\mathrm{Cay}(A_n, R)\) is integral. Here \(\mathrm{Cay}(A_n, R)\) has vertex set \(A_n\), distinct \(x\) and \(y\) being adjacent when \(x^{-1} y \in R\) or \(y^{-1} x \in R\), and a graph is integral when every eigenvalue of its integer adjacency matrix (every complex root of the characteristic polynomial of that matrix) is an integer.

def alternatingThreeCycleCayleyGraphIntegral : Prop :=
  ∀ n : ℕ, 3 ≤ n → HasIntegralSpectrum ((SimpleGraph.mulCayley
    {g : alternatingGroup (Fin n) | (g : Equiv.Perm (Fin n)) ∈ threeCyclesOneTwo n ∨
      (g : Equiv.Perm (Fin n))⁻¹ ∈ threeCyclesOneTwo n}).adjMatrix ℤ)

Uses 2 · Used by 1

Statement usesInteger matrix with integral spectrum · The 3-cycles (1 2 k)

Used byThe 3-cycle Cayley graph of the alternating group is integral

TheoremCayley graphs on normal sets of involutions are integral#●ready to prove

Let \(G\) be a finite group and let \(R \subseteq G\) be a set of involutions (\(r^2 = 1\) and \(r \ne 1\) for every \(r \in R\)) that is closed under conjugation (\(g r g^{-1} \in R\) for all \(r \in R\) and \(g \in G\)) and generates \(G\). Then the Cayley graph \(\mathrm{Cay}(G, R)\), whose vertices are the elements of \(G\) with distinct \(x\) and \(y\) adjacent when \(x^{-1} y \in R\) or \(y^{-1} x \in R\), is integral: every eigenvalue of its integer adjacency matrix (every complex root of the characteristic polynomial of that matrix) is an integer.

The Kourovka Archive proof: every eigenvalue of \(\mathrm{Cay}(G, R)\) has the form \(\frac{1}{\chi(1)} \sum_{r \in R} \chi(r)\) for an irreducible character \(\chi\) of \(G\); this number is rational because characters take integer values on involutions, and it is an algebraic integer.

public theorem_wanted involutionCayleyGraphIntegral_holds : involutionCayleyGraphIntegral

Sources

• E. I. Khukhro and V. D. Mazurov (eds.), Unsolved Problems in Group Theory: The Kourovka Notebook, 21st issue, arXiv:1401.0300v49 (2026), Archive of Solved Problems, Problem 19.50 (D. V. Lytkina); resolution: (a) D. O. Revin, letter of 21 April 2018; A. Abdollahi, letter of 3 May 2018; (b) W. Guo, D. V. Lytkina, V. D. Mazurov and D. O. Revin, Integral Cayley graphs, Algebra Logic 58 (2019), no. 4, 297-305, doi:10.1007/s10469-019-09550-2, Kourovka Archive, Problem 19.50: (a) Yes, with a character-theoretic proof in the Archive (each eigenvalue is (1/χ(1)) ∑_{r ∈ R} χ(r), rational since characters take integer values on involutions); (b) Yes, https://arxiv.org/abs/1401.0300v49.

Uses 1

Statement usesThe Kourovka 19.50(a) integrality claim

TheoremThe 3-cycle Cayley graph of the alternating group is integral#●ready to prove

For every \(n \ge 3\), let \(S\) be the set of \(3\)-cycles \((1\,2\,k)\) with \(3 \le k \le n\) in the alternating group \(A_n\), and let \(R = S \cup S^{-1}\). Then the Cayley graph \(\mathrm{Cay}(A_n, R)\), whose vertices are the elements of \(A_n\) with distinct \(x\) and \(y\) adjacent when \(x^{-1} y \in R\) or \(y^{-1} x \in R\), is integral: every eigenvalue of its integer adjacency matrix (every complex root of the characteristic polynomial of that matrix) is an integer.

public theorem_wanted alternatingThreeCycleCayleyGraphIntegral_holds :
    alternatingThreeCycleCayleyGraphIntegral

Sources

• E. I. Khukhro and V. D. Mazurov (eds.), Unsolved Problems in Group Theory: The Kourovka Notebook, 21st issue, arXiv:1401.0300v49 (2026), Archive of Solved Problems, Problem 19.50 (D. V. Lytkina); resolution: (a) D. O. Revin, letter of 21 April 2018; A. Abdollahi, letter of 3 May 2018; (b) W. Guo, D. V. Lytkina, V. D. Mazurov and D. O. Revin, Integral Cayley graphs, Algebra Logic 58 (2019), no. 4, 297-305, doi:10.1007/s10469-019-09550-2, Kourovka Archive, Problem 19.50: (a) Yes, with a character-theoretic proof in the Archive (each eigenvalue is (1/χ(1)) ∑_{r ∈ R} χ(r), rational since characters take integer values on involutions); (b) Yes, https://arxiv.org/abs/1401.0300v49.

Uses 1

Statement usesThe Kourovka 19.50(b) integrality claim

4 fully proved2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.