No three algebraic conjugates of degree sixteen sum to zero
January 01, 1970
Abstract
Let \(d\) be the smallest positive integer, not divisible by \(3\), for which there exists an algebraic number over \(\mathbb{Q}\) of degree \(d\) whose some three algebraic conjugates sum to zero. Employing the classification of vertex-transitive graphs on 16 vertices of degree 6, we prove that \(d\neq 16\). This, combined with results obtained by Dubickas, Smyth and Stong [1], Dubickas and Jankauskas [2] and Virbalas [3], implies that \(d=20\).
1 Introduction↩︎
In 2004 Dubickas and Smyth [1] asked to prove or disprove the following: If \(\alpha+\alpha'+\alpha''=0\) for three distinct algebraic conjugates of an algebraic number \(\alpha\) of degree \(d\), then 3 divides \(d\). Stong (see [1]) provided a counterexample when \(d=20\). More precisely, he showed that the irreducible polynomial \[x^{20} + 4\cdot5^{9}\cdot x^{10} + 16\cdot5^{15}\] has three distinct roots, which sum to zero. Several authors (see, e.g., [2], [3]) were interested in the following natural question: what is the smallest positive integer \(d\), not a multiple of 3, for which there exists an algebraic number of degree \(d\) such that some three of its conjugates sum to zero? The above-mentioned counterexample of Stong implies that \(d\leqslant 20\). Dubickas and Jankauskas (see Theorem 1.2 in [2]) showed that such a minimal value of \(d\) lies in the range \(10\leqslant d \leqslant 20\). Note that, by Lemma 1 (see Section 2), \(d\) cannot be a prime number. Thus, \(d=10, 14, 16\) or \(20\). Recently, Virbalas (see Theorem 1.1 in [3]) showed that \(d\neq 2p\), where \(p\geqslant 5\) is a prime number. Thus, either \(d=16\) or \(d=20\). The main result of this paper states that \(d=20\).
Theorem 1. Let \(d\) be the smallest positive integer, not a multiple of \(3\), for which there exists an algebraic number of degree \(d\) whose some three algebraic conjugates sum to zero. Then \(d=20\).
The relation \(\alpha+\alpha'+\alpha''=0\) between three algebraic conjugates is a particular case of a more general relation \[\label{eqin1} a_1\alpha_1+a_2\alpha_2+\dotsb+a_n\alpha_n=0,\tag{1}\] where \(\alpha_1,\alpha_2,\dotsc,\alpha_n\) are the algebraic conjugates of an algebraic number \(\alpha\) of degree \(n\) and \(a_1,a_2,\dotsc,a_n\) are rational integers, not all zero. The relation 1 is called trivial if \(a_1=a_2=\dotsc=a_n\). One of the first general results was obtained by Kurbatov [4], who proved that there are no non-trivial relations 1 if the degree \(n\) is a prime number (see also [5] and [6]). Girstmair in [7] proposed a theoretical framework to study linear relations 1 , based on representation theory of finite groups, applied to the Galois group of the Galois closure of \(\mathbb{Q}(\alpha)\).
A lot of attention was devoted to the investigation of the relation 1 for small values of \(n\) and \(a_1,a_2,\dotsc,a_n\). See, e.g., [2], [8]–[14] for the results related to the linear relation \(\alpha_1+\alpha_2=\alpha_3\), [15] for the results related to the linear relations \(\alpha_1=\alpha_2+\alpha_3+\alpha_4\) and \(\alpha_1+\alpha_2=\alpha_3+\alpha_4\), [16], [17] for the classification of all possible relations in case when \(n=4\) and [18] for the multiplicative analog.
In the proof of Theorem 1 (see Section 3), we assume that there exists an algebraic number \(\alpha\) of degree 16 whose three algebraic conjugates sum to zero. Then we construct the graph \(\mathcal{G}\) whose set of vertices is the set \(\{\alpha_1,\alpha_2,\dotsc,\alpha_{16}\}\) of algebraic conjugates of \(\alpha\). Two distinct vertices \(\alpha'\) and \(\alpha''\) are adjacent if and only if there exists a conjugate \(\alpha'''\) such that \(\alpha'+\alpha''+\alpha'''=0\). We prove that the graph \(\mathcal{G}\) is vertex-transitive and every vertex has degree (valency) 6. Then we use the classification of such graphs. There are exactly 40 vertex-transitive graphs on 16 vertices of degree 6 (see, e.g., McKay and Royle [19]; the explicit list is maintained in [20]1). Then, using auxiliary results (see Section 2, and Lemma 7 and Lemma 8 in Section 3) and computations with SageMath [21] (the code is provided in the appendix), we show that neither of these 40 graphs is isomorphic to \(\mathcal{G}\).
2 Auxiliary results↩︎
As far as we know, the first general result, related to linear relations among algebraic conjugates of a given algebraic number, was obtained by Kurbatov [4]:
Lemma 1. The equality \[k_{1}\alpha_{1}+k_{2}\alpha_{2}+\cdots+k_{d}\alpha_{d} = 0\] with conjugates \(\alpha_{1}, \alpha_{2},\dots, \alpha_{d}\) of an algebraic number \(\alpha\) of prime degree \(d\) over \(\mathbb{Q}\) and \(k_{1}, k_{2},\dots, k_{d}\in\mathbb{Z}\) can only hold if \(k_{1} = k_{2} = \cdots = k_{d}\).
The following result of Smyth [22] will be used several times in the proof of Theorem 1 to eliminate impossible relations among algebraic conjugates.
Lemma 2. If \(\alpha_{1}, \alpha_{2}, \alpha_{3}\) are three conjugates of an algebraic number satisfying \(\alpha_{1}\neq\alpha_{2}\) then \(2\alpha_{1}\neq \alpha_{2} + \alpha_{3}\).
The following result, obtained by Dubickas [23] (see also [6]), is a generalization of Lemma \(\ref{intro7}\).
Lemma 3. If \(\beta_{1}, \beta_{2},\dots , \beta_{n}\), where \(n\geqslant 3\), are distinct algebraic numbers conjugate over a field of characteristic zero \(K\) and \(k_{1}, k_{2},\dots ,k_{n}\) are non-zero rational numbers satisfying \(|k_{1}| \geqslant|k_{2}|+\dots+|k_{n}|\) then \[k_{1}\beta_{1} + k_{2}\beta_{2} +\dots+ k_{n}\beta_{n}\notin K.\]
Also, we will use the following result, proved by Dubickas and Jankauskas in [2].
Lemma 4. The equality \[k_{1}\alpha_{1}+k_{2}\alpha_{2}+\cdots+k_{d}\alpha_{d} = 0\] with conjugates \(\alpha_{1}, \alpha_{2},\dots, \alpha_{d}\) of an algebraic number \(\alpha\) of degree \(d\) over \(\mathbb{Q}\) and \(k_{1}, k_{2},\dots, k_{d}\in\mathbb{Z}\) satisfying \(\sum_{i=1}^{d} k_{i}\neq 0\) can only hold if \(tr(\alpha) := \alpha_{1} + \alpha_{2} + \cdots + \alpha_{d} = 0\).
3 Proof of Theorem \(\ref{t1}\)↩︎
Proof. Let \(d\) be a positive integer, not divisible by \(3\). Let \(\alpha\) be an algebraic number over \(\mathbb{Q}\) of degree \(d\) whose some three algebraic conjugates sum to zero. Suppose that \(d\) is the smallest possible such positive integer.
Stong (see [1]) showed that the irreducible polynomial \[x^{20} + 4\cdot5^{9}\cdot x^{10} + 16\cdot5^{15}\] has three distinct roots, which sum to zero. Hence, \(d\leqslant 20\). On the other hand, Dubickas and Jankauskas (see Theorem 1.2 in [2]) proved that \(d\geqslant 10\). Moreover, by Lemma 1, \(d\) cannot be a prime number. Thus \(d\in\{10,14,16,20\}\). Recently, Virbalas (see Theorem 1.1 in [3]) proved that \(d\neq 2p\), where \(p\geqslant 5\) is a prime number. So \(d=16\) or \(d=20\). We will prove that \(d\neq 16\).
Assume, to the contrary, that there exists an algebraic number \(\alpha\) of degree \(d=16\) whose some three algebraic conjugates \(\alpha_{1},\alpha_{2},\alpha_{3}\) satisfy the relation \[\label{eq1} \alpha_{1}+\alpha_{2}+\alpha_{3}=0.\tag{2}\] Clearly, these three conjugates can’t be all equal. Moreover, if some two conjugates are equal, say \(\alpha_1=\alpha_2\), then \(2\alpha_1+\alpha_3=0\), which is impossible (we can choose an automorphism \(\pi\) of the Galois group of the normal closure of \(\mathbb{Q}(\alpha)\) which maps \(\alpha_1\) to \(\alpha'\) having the maximal absolute value \(m\); then \(2\alpha_1+\alpha_3=0\) is mapped to \(2\alpha'+\pi(\alpha_3)=0\) and \(2m=|2\alpha'|=|-\pi(\alpha_3)|\leqslant m\), which is impossible). Hence, all three conjugates in 2 are distinct.
Let \(\alpha_1,\alpha_2,\dotsc,\alpha_{16}\) be the algebraic conjugates of \(\alpha\). Lemma \(\ref{intro3}\) implies that \(tr(\alpha)=\alpha_{1}+\alpha_{2}+\dotsb+\alpha_{16}=0\). Let \(G\) be the Galois group of the normal closure of \(\mathbb{Q}(\alpha)\) over \(\mathbb{Q}\). Note that this normal closure is also the splitting field of the minimal polynomial of \(\alpha\) over \(\mathbb{Q}\), and therefore \(G\) is the Galois group of this polynomial. The group \(G\) corresponds to some transitive subgroup of the full symmetric group \(S_{16}\).
Two relations \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and \(\alpha_{i'}+\alpha_{j'}+\alpha_{k'}=0\), where all the summands are algebraic conjugates of \(\alpha\), are called distinct, if \[\{\alpha_{i},\alpha_{j},\alpha_{k}\}\neq \{\alpha_{i'},\alpha_{j'},\alpha_{k'}\}.\]
Lemma 5. For any two distinct relations \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and \(\alpha_{i'}+\alpha_{j'}+\alpha_{k'}=0\) we have that \(|\{i, j, k\}\cap \{i', j', k'\}|\leqslant 1\).
Proof. Since the relations are distinct, we have that \(|\{i, j, k\}\cap \{i', j', k'\}|\leqslant 2\). On the other hand, if say \(\{j, k\}= \{j', k'\}\), then \(\alpha_{i}=-\alpha_{j}-\alpha_{k}=-\alpha_{j'}-\alpha_{k'} = \alpha_{i'}\), which is impossible. Hence, the claim follows. ◻
Lemma 6. For any fixed \(i_0\in\{1,2,\dotsc,16\}\) the number of distinct relations of the form \(\alpha_{i_0}+\alpha_{j}+\alpha_{k}=0\) is less than 6.
Proof. Assume, to the contrary, that for a fixed \(i_0\) there exist six distinct relations of the form \(\alpha_{i_0}+\alpha_{j}+\alpha_{k}=0\). Lemma 5 implies that for any two distinct relations \(\alpha_{i_0}+\alpha_{j_1}+\alpha_{k_1}=0\) and \(\alpha_{i_0}+\alpha_{j_2}+\alpha_{k_2}=0\) the sets \(\{j_1,k_1\}\) and \(\{j_2,k_2\}\) are disjoint. Without loss of generality, we consider the following six relations (after relabeling the conjugates of \(\alpha\), if necessary): \[\begin{align} \alpha_{1}&+\alpha_{2}+\alpha_{3}=0,\\ \alpha_{1}&+\alpha_{4}+\alpha_{5}=0,\\ \alpha_{1}&+\alpha_{6}+\alpha_{7}=0,\\ \alpha_{1}&+\alpha_{8}+\alpha_{9}=0,\\ \alpha_{1}&+\alpha_{10}+\alpha_{11}=0,\\ \alpha_{1}&+\alpha_{12}+\alpha_{13}=0. \end{align}\] By adding all of them and using \(tr(\alpha)=0\), we obtain \[6\alpha_{1}+\alpha_{2}+\alpha_{3}+\dots+\alpha_{13}=5\alpha_{1}-\alpha_{14}-\alpha_{15}-\alpha_{16}=0,\] which is impossible by Lemma 3. ◻
We say that two relations \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and \(\alpha_{i'}+\alpha_{j'}+\alpha_{k'}=0\) are conjugate if there exists an automorphism \(\pi\in G\) such that \[\{\alpha_{i},\alpha_{j},\alpha_{k}\} = \{\pi(\alpha_{i'}),\pi(\alpha_{j'}),\pi(\alpha_{k'})\}.\] One can easily see that this conjugacy relation is an equivalence relation on the set of all possible relations of the form \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\).
Lemma 7. The following statements are true.
Any two relations of the form \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) are conjugate.
There are exactly 16 distinct such relations.
Each algebraic conjugate of \(\alpha\) appears in exactly 3 distinct such relations.
Proof. Consider a relation \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and its equivalence class \(\mathcal{C}(\alpha_{i},\alpha_{j},\alpha_{k})\), consisting of all the distinct relations that are conjugate to \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\). Let \(N=|\mathcal{C}(\alpha_{i},\alpha_{j},\alpha_{k})|\). Since the Galois group \(G\) acts transitively on the set \(\{\alpha_1,\alpha_2,\dotsc,\alpha_{16}\}\), each conjugate \(\alpha_{i}\) appears an equal number of times, say \(l\), in the relations in \(\mathcal{C}(\alpha_{i},\alpha_{j},\alpha_{k})\). We have \(N\) distinct relations in \(\mathcal{C}(\alpha_{i},\alpha_{j},\alpha_{k})\) and each such relation involves three distinct conjugates of \(\alpha\). Thus, there are \(3N\) appearances of conjugates of \(\alpha\) in \(\mathcal{C}(\alpha_{i},\alpha_{j},\alpha_{k})\). On the other hand, this number can be counted in a different way – each conjugate of \(\alpha\) appears exactly \(l\) times. Hence, \(3N = 16l\). So that \(l\) is divisible by 3. Since, by Lemma 6, \(l<6\), we obtain that \(l=3\) and accordingly \(N=16\).
Assume that there are two distinct equivalence classes. Each contains three distinct relations involving \(\alpha_1\). So that in total we have six distinct relations involving \(\alpha_1\). This contradicts Lemma 6. Hence, the lemma follows. ◻
By Lemma 7, we have exactly 16 distinct relations of the form \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and each \(\alpha_i\) appears in exactly 3 distinct such relations. Without loss of generality, we assume the following system of distinct relations: \[\label{eq2} \begin{alignedat}{6} &\alpha_{1} & &+ &\;\; &\alpha_{2} & &+ &\;\; &\alpha_{3} & &= 0,\\ &\alpha_{1} & &+ & &\alpha_{4} & &+ & &\alpha_{5} & &= 0,\\ &\alpha_{1} & &+ & &\alpha_{6} & &+ & &\alpha_{7} & &= 0,\\ &\alpha_{i_{4\,1}} & &+ & &\alpha_{i_{4\,2}} & &+ & &\alpha_{i_{4\,3}} & &= 0,\\ &\alpha_{i_{5\,1}} & &+ & &\alpha_{i_{5\,2}} & &+ & &\alpha_{i_{5\,3}} & &= 0,\\ & & &\vdots &&&&\vdots &&&&\vdots\\ &\alpha_{i_{16\,1}} & &+ & &\alpha_{i_{16\,2}} & &+ & &\alpha_{i_{16\,3}} & &= 0. \end{alignedat}\tag{3}\] This system of relations is equivalent to the following one: \[\label{eq3} \begin{alignedat}{13} -\alpha_{1}& &\;\; &= &\;\;&\alpha_{2} & &+&\;\; & \alpha_{3} & &= &\;\; &\alpha_{4} & &+ &\;\; &\alpha_{5}& &= &\;\; &\alpha_{6} & &+ &\;\; &\alpha_{7},\\ -\alpha_{2}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{3} & &= & &\alpha_{j_{2\,3}} & &+ & &\alpha_{j_{2\,4}}& &= & &\alpha_{j_{2\,5}} & &+ & &\alpha_{j_{2\,6}},\\ -\alpha_{3}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{2} & &= & &\alpha_{j_{3\,3}} & &+ & &\alpha_{j_{3\,4}} & &= & &\alpha_{j_{3\,5}} & &+ & &\alpha_{j_{3\,6}},\\ -\alpha_{4}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{5} & &= & &\alpha_{j_{4\,3}} & &+ & &\alpha_{j_{4\,4}} & & = & &\alpha_{j_{4\,5}} & &+ & &\alpha_{j_{4\,6}},\\ -\alpha_{5}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{4} & &= & &\alpha_{j_{5\,3}} & &+ & &\alpha_{j_{5\,4}} & &= & &\alpha_{j_{5\,5}} & &+ & &\alpha_{j_{5\,6}},\\ -\alpha_{6}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{7} & &= & &\alpha_{j_{6\,3}} & &+ & &\alpha_{j_{6\,4}} & &= & &\alpha_{j_{6\,5}} & &+ & &\alpha_{j_{6\,6}},\\ -\alpha_{7}& & &= &\;\;&\alpha_{1} & &+ & &\alpha_{6} & &= & &\alpha_{j_{7\,3}} & &+ & &\alpha_{j_{7\,4}} & &= & &\alpha_{j_{7\,5}} & &+ & &\alpha_{j_{7\,6}},\\ -\alpha_{8}& & &= &\;\;&\alpha_{j_{8\,1}} & &+ & &\alpha_{j_{8\,2}} & &= & &\alpha_{j_{8\,3}} & &+ & &\alpha_{j_{8\,4}} & &=& & \alpha_{j_{8\,5}} & &+ & &\alpha_{j_{8\,6}},\\ & & &\vdots &\;\;& & & & & & &\vdots& & & & & & & &\vdots& & & & & & \\ -\alpha_{16}& & &= &\;\;&\alpha_{j_{16\,1}} & &+ & &\alpha_{j_{16\,2}} & &= & &\alpha_{j_{16\,3}} & &+ & &\alpha_{j_{16\,4}} & &= & &\alpha_{j_{16\,5}} & &+ & &\alpha_{j_{16\,6}}. \end{alignedat}\tag{4}\]
Note that \(-\alpha_{1}, -\alpha_{2},\dots, -\alpha_{16}\) are the algebraic conjugates of \(-\alpha_{1}\). This implies that \(\deg(\alpha_{1}+\alpha_{2})=16\) and each sum \(\alpha_{i}+\alpha_{j}\) appearing in 4 is an algebraic conjugate of \(\alpha_{1}+\alpha_{2}\). Note that each algebraic conjugate of \(\alpha_{1}+\alpha_{2}\) has exactly three distinct representations as a sum \(\alpha_{i}+\alpha_{j}\) (see \((iii)\) in Lemma 7).
Now, we will introduce the graph theory approach to this problem. Consider the graph \(\mathcal{G}=(V, E)\) with the set of vertices \(V:=\{\alpha_{1}, \alpha_{2}, \dots, \alpha_{16}\}\). Two vertices \(\alpha_{i}\) and \(\alpha_{j}\) are connected by an edge, denoted \((\alpha_{i}, \alpha_{j})\) (or \((\alpha_{j}, \alpha_{i})\)), if the sum \(\alpha_{i}+\alpha_{j}\) is an algebraic conjugate of \(\alpha_{1}+\alpha_{2}\), i.e., the sum \(\alpha_{i}+\alpha_{j}\) appears in 4 . Note that each vertex of \(\mathcal{G}\) must have the same number of edges. In other words, graph \(\mathcal{G}\) is regular. This follows directly from the fact that each \(\alpha_{i}\) appears exactly six times in 4 (or, equivalently, each \(\alpha_{i}\) appears in three distinct relations \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) and each such relation implies two edges \((\alpha_i,\alpha_j)\) and \((\alpha_i,\alpha_k)\), connecting the vertex \(\alpha_i\)), i.e., \(\deg(v)=6\) for each \(v\in V\). In such a setting, \(\mathcal{G}\) must have \((16\cdot6)/2=48\) edges. Furthermore, since the Galois group \(G\) is transitive on the set of conjugates \(\{\alpha_{1}, \alpha_{2}, \dots, \alpha_{16}\}\) and, by Lemma 7, any two relations of the form \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) are conjugate, the graph \(\mathcal{G}\) must be vertex-transitive. It is known that there are exactly \(40\) vertex-transitive graphs on \(16\) vertices of degree \(6\). This was established by McKay and Royle [19] the complete enumeration of transitive graphs on at most 26 vertices. The explicit list is maintained in [20]2 (see also the House of Graphs [24]). All 40 of these graphs, named \(\mathcal{G}_{1},\mathcal{G}_{2},\dotsc, \mathcal{G}_{40}\), are given in Table [table:t1]. Note that these graphs are given in graph6 format (this format was invented by Brendan McKay [25], [26] and is recognized by SageMath [21]).
[h!]
\centering
\scalebox{0.85}{
\begin{tabular}{ |c|c| }
\hline
Graph & Code in $graph6$ format\\
\hline
\hline
$\mathcal{G}_{1}$ & OsaC???FzrMkYwXwJw@|?\\
$\mathcal{G}_{2}$ & OsaC???RxnNKYw$\setminus$WJs@\}?\\
$\mathcal{G}_{3}$ & OsaC???]ZrK\{XwFwB\{B\{?\\
$\mathcal{G}_{4}$ & OsaCB@\_EWrKrXeFwB\{B\{?\\
$\mathcal{G}_{5}$ & OsaKYCQGbRIjXKLWJEHqc\\
$\mathcal{G}_{6}$ & OsaKYCcQXRBKSbLDmTBi\_\\
$\mathcal{G}_{7}$ & OsaKYDDGgdLBUELQeibr?\\
$\mathcal{G}_{8}$ & OsaKYPDHOiDFEM[wMPRcg\\
$\mathcal{G}_{9}$ & OsaKg?dQGid$\setminus$[S[qLSQy\_\\
$\mathcal{G}_{10}$ & OsaKg?hSZEkkTIIdJWPyA\\
$\mathcal{G}_{11}$ & OsaKiCaC\textasciigrave RbMYKTYLabiC\\
$\mathcal{G}_{12}$ & OsaKiCdPPDaUBR]WNAboS\\
$\mathcal{G}_{13}$ & OsaSWSTOhDKiXQUEfBbr?\\
$\mathcal{G}_{14}$ & OsaSXCdOha\textasciigrave T[DRRNEAyC\\
$\mathcal{G}_{15}$ & OsaSXDCSXRbKTBIdmSBY@\\
$\mathcal{G}_{16}$ & OsaSYHBGpH\textasciigrave XDL]SNDBoK\\
$\mathcal{G}_{17}$ & Osedw?DOYFHBSZW$\setminus$Fg@w\textasciigrave \\
$\mathcal{G}_{18}$ & Osedw?HOYFGbSZW$\setminus$Fg@w\textasciigrave \\
$\mathcal{G}_{19}$ & Osedw@??pJhMP$\setminus$UWEjBpA\\
$\mathcal{G}_{20}$ & OsfDw?@G\textasciigrave bgmW$\setminus$RWFFAyA\\
\hline
\end{tabular}
\quad
\begin{tabular}{ |c|c| }
\hline
Graph & Code in $graph6$ format\\
\hline
\hline
$\mathcal{G}_{21}$ & OsfDw@@GXPCZP]TSFDayA\\
$\mathcal{G}_{22}$ & OsfLg?@WYHcZQYKXJcPuA\\
$\mathcal{G}_{23}$ & Osqsw@@AXCclW]USEXaxA\\
$\mathcal{G}_{24}$ & Osqsy@@GWRcdGtUEESqyA\\
$\mathcal{G}_{25}$ & OtaCXOTHOphhRKSsKTJcK\\
$\mathcal{G}_{26}$ & OtaLw?@OaRgn[S[Kdk?z@\\
$\mathcal{G}_{27}$ & OtaLw?@ObBiNQ[P[fg@x@\\
$\mathcal{G}_{28}$ & OtaLw?BOBBhNP[S[fa@y@\\
$\mathcal{G}_{29}$ & OtaLy@@AWJg[WFSFfg@x@\\
$\mathcal{G}_{30}$ & OtaLyD\textasciigrave SYQGhKBKB\textasciigrave eOXb\\
$\mathcal{G}_{31}$ & Ota$\setminus$W@@GYChJS]PZFc@u@\\
$\mathcal{G}_{32}$ & Otakw?@QYbKLPLOufc@u@\\
$\mathcal{G}_{33}$ & Otaky@@GWbhBPROlfc@u@\\
$\mathcal{G}_{34}$ & OtrTOGBW@\textasciigrave hIP]G|Bg\_tP\\
$\mathcal{G}_{35}$ & Ouj$\setminus$w?@?YBcMSUILIhPTI\\
$\mathcal{G}_{36}$ & O\{fL\_@HKQJCZCsBW\_pzp\_\\
$\mathcal{G}_{37}$ & O\{fL\_CCQP\textasciigrave GmCzB[C$\setminus$Joo\\
$\mathcal{G}_{38}$ & O\}akqPPWOV@iHIDHcROcj\\
$\mathcal{G}_{39}$ & O\textasciitilde{}aKYPDOxQBHHIGeacocj\\
$\mathcal{G}_{40}$ & O\textasciitilde{}z$\setminus$w?@?WB\_M?Z?V\_Fz\{?\\
\hline
\end{tabular}
}
\vspace{0,2cm}
\caption{All $40$ vertex-transitive graphs on $16$ vertices of degree $6$ (see \cite{HoltRoyle2020}).}
\label{table:t1}The goal is to prove that for all \(i=1,2,\dots 40\), graphs \(\mathcal{G}\) and \(\mathcal{G}_{i}\) are not isomorphic.
Note that a relation \(\alpha_{i}+\alpha_{j}+\alpha_{k}=0\) in 3 implies that \(\alpha_{i}+\alpha_{j}=-\alpha_{k}, \alpha_{i}+\alpha_{k}=-\alpha_{j}\), and \(\alpha_{j}+\alpha_{k}=-\alpha_{i}\) are algebraic conjugates of \(\alpha_{1}+\alpha_{2}=-\alpha_{3}\). In other words, edges \((\alpha_{i}, \alpha_{j}), (\alpha_{i}, \alpha_{k})\), and \((\alpha_{j}, \alpha_{k})\) form a triangle in our graph \(\mathcal{G}\). On the other hand, if for some three distinct \(\alpha_{a}, \alpha_{b}, \alpha_c\) we have that three edges \((\alpha_{a}, \alpha_{b}), (\alpha_{b}, \alpha_{c})\) and \((\alpha_{a}, \alpha_{c})\) belong to our graph \(\mathcal{G}\), then not necessarily the relation \(\alpha_{a}+ \alpha_{b}+\alpha_{c}=0\) holds. If it does, then we say that the vertices \(\alpha_{a}, \alpha_{b}, \alpha_{c}\) form a zero-sum triangle \(\triangle(\alpha_{a}, \alpha_{b}, \alpha_{c})\).
We will recall several concepts from Graph Theory. Let \(G=(V,E)\) be a graph. Two vertices that are connected directly by an edge are called adjacent vertices. A vertex is said to be incident to an edge (and the edge is incident to the vertex) if that vertex is one of the endpoints of the edge. The degree (or valency) of a vertex \(v\in V\) is defined as the number of edges in \(G\) that are incident to \(v\), and denoted by \(\deg_G(v)\). The set of all vertices that are adjacent to a given vertex \(v\in V\), except for \(v\) itself, is called the open neighborhood of \(v\), and denoted by \(N(v)\). Then the set \(N[v]:=N(v)\cup\{v\}\) is called the closed neighborhood of \(v\). For a given subset \(V'\) of the set of vertices \(V\) let \(E'\) be a subset of the set of edges \(E\) such that the edge \(vv'\in E\) belongs to \(E'\) if and only if both vertices \(v\) and \(v'\) belong to \(V'\). Such a graph \(\tilde{G}=(V',E')\) is called the induced graph on the subset of vertices \(V'\). For a given vertex \(v\) denote by \(G(v)\) the induced graph on the closed neighborhood \(N[v]\). Note that for \(v'\in G(v)\) the number \(\deg_{G(v)}(v')\) is the degree of the vertex \(v'\) with respect to the induced graph \(G(v)\) while \(\deg_{G}(v')\) is the degree of \(v'\) with respect to the graph \(G\).
Lemma 8. The following statements are true for the graph \(\mathcal{G}\).
Two distinct zero-sum triangles share at most one vertex.
Every edge \((\alpha,\alpha')\), \(\alpha\neq\alpha'\), belongs to exactly one zero-sum triangle \(\triangle(\alpha, \alpha', \alpha'')\) and the vertex \(\alpha''\) belongs to the open neighborhood \(N(\alpha)\) of \(\alpha\).
If for some three distinct vertices \(\alpha, \alpha', \alpha''\) we have that \(\alpha', \alpha''\in N(\alpha)\), \(\deg_{\mathcal{G}(\alpha)}(\alpha')=2\) and \((\alpha',\alpha'')\) is an edge in \(\mathcal{G}\), then \(\triangle(\alpha, \alpha', \alpha'')\) is a zero-sum triangle.
If \(\triangle(\alpha, \alpha_a, \alpha_b)\) and \(\triangle(\alpha, \alpha_c, \alpha_d)\) are two distinct zero-sum triangles, then either \((\alpha_a,\alpha_d)\) or \((\alpha_b,\alpha_c)\) is not an edge in \(\mathcal{G}\).
Proof. Part \((i)\) follows from the definition of the graph \(\mathcal{G}\) and Lemma 5.
\((ii)\). Let \((\alpha,\alpha')\), \(\alpha\neq\alpha'\), be an edge in \(\mathcal{G}\). Then, according to the definition of \(\mathcal{G}\), the sum \(\alpha+\alpha'\) is an algebraic conjugate of \(\alpha_1+\alpha_2=-\alpha_3\). Hence, \(\alpha+\alpha'=-\alpha''\), where \(\alpha''\) is an algebraic conjugate of \(\alpha\). So that \(\alpha+\alpha'+\alpha''=0\), which implies that the triangle \(\triangle(\alpha, \alpha', \alpha'')\) is a zero-sum triangle. Part \((i)\) ensures that \(\triangle(\alpha, \alpha', \alpha'')\) is the unique triangle containing the edge \((\alpha,\alpha')\). Moreover, \((\alpha,\alpha'')\) is also an edge in \(\mathcal{G}\), since \(\alpha+\alpha''=-\alpha'\) is an algebraic conjugate of \(\alpha_1+\alpha_2=-\alpha_3\). So \(\alpha''\) is adjacent to \(\alpha\), \(\alpha''\neq\alpha\), and therefore \(\alpha''\in N(\alpha)\).
\((iii)\). Since \(\alpha'\in N(\alpha)\), we have that \((\alpha,\alpha')\) is an edge in \(\mathcal{G}\). Applying part \((ii)\) we obtain that there exists a vertex \(\tilde{\alpha}\in N(\alpha)\) such that the triangle \(\triangle(\alpha, \alpha', \tilde{\alpha})\) is a zero-sum triangle. This together with \(\deg_{\mathcal{G}(\alpha)}(\alpha')=2\) imply that in the induced graph \(\mathcal{G}(\alpha)\) the vertex \(\alpha'\) is adjacent only to \(\alpha\) and \(\tilde{\alpha}\). On the other hand, the edge \((\alpha',\alpha'')\) is in \(\mathcal{G}\) and \(\alpha', \alpha''\in N(\alpha)\). Thus, the edge \((\alpha',\alpha'')\) belongs to the induced graph \(\mathcal{G}(\alpha)\), and therefore \(\alpha'\) is adjacent to \(\alpha''\) in \(\mathcal{G}(\alpha)\). Hence, \(\tilde{\alpha}=\alpha''\) and the claim follows.
\((iv)\). Assume, to the contrary, that \(\triangle(\alpha, \alpha_a, \alpha_b)\) and \(\triangle(\alpha, \alpha_c, \alpha_d)\) are two distinct zero-sum triangles and both \((\alpha_a,\alpha_d)\) and \((\alpha_b,\alpha_c)\) are edges in \(\mathcal{G}\). Part \((ii)\) implies the existence of zero-sum triangles \(\triangle(\alpha_a, \alpha_d, \alpha')\) and \(\triangle(\alpha_b, \alpha_c, \alpha'')\). Note that \(\alpha'\neq \alpha\), since, in view of part \((i)\), zero-sum triangles \(\triangle(\alpha, \alpha_a, \alpha_b)\) and \(\triangle(\alpha_a, \alpha_d, \alpha')\) share exactly one vertex \(\alpha_a\). Similarly, \(\alpha''\neq \alpha\). Now, the four obtained zero-sum triangles imply the relations \[\label{eql4} \begin{align} \alpha &+ \alpha_a + \alpha_b = 0,\\ \alpha &+ \alpha_c + \alpha_d = 0,\\ \alpha_a &+ \alpha_d + \alpha' = 0,\\ \alpha_b &+ \alpha_c + \alpha'' = 0. \end{align}\tag{5}\] By adding the first two relations in 5 and using the expressions for \(\alpha'\) and \(\alpha''\) from the last two relations in 5 , we obtain \[2\alpha+ (\alpha_a+\alpha_d)+(\alpha_b+\alpha_c)=2\alpha-\alpha'-\alpha''=0.\] This contradicts Lemma 2, since \(\alpha'\neq \alpha\). ◻
First, consider the graph shown in Figure 1.
Notice that the first three equations in 3 imply that this graph must be a subgraph of \(\mathcal{G}\). We check with SageMath [21] that neither of the following \(29\) graphs \[\mathcal{G}_{1}, \mathcal{G}_{2},\dots, \mathcal{G}_{19};\quad\mathcal{G}_{25}, \mathcal{G}_{26},\dots, \mathcal{G}_{33};\quad\mathcal{G}_{39}\] has a subgraph isomorphic to the graph FyTAG. Hence, \(\mathcal{G}\) is isomorphic to one of the graphs in the following set \[\label{eq11a} \{ \mathcal{G}_{20}, \mathcal{G}_{21}, \mathcal{G}_{22}, \mathcal{G}_{23}, \mathcal{G}_{24}, \mathcal{G}_{34},\mathcal{G}_{35}, \mathcal{G}_{36},\mathcal{G}_{37}, \mathcal{G}_{38}, \mathcal{G}_{40}\}.\tag{6}\]
We claim that \(\mathcal{G}\) is not isomorphic to any graph in the set \(\{\mathcal{G}_{34}, \mathcal{G}_{36}, \mathcal{G}_{37}, \mathcal{G}_{38}\}\). Indeed, consider the graph shown in Figure 2.
We will prove that this graph cannot be an induced subgraph of \(\mathcal{G}\). Assume, to the contrary, that the graph F}TJG is an induced subgraph of \(\mathcal{G}\). By \((ii)\) of Lemma 8, the edge \((\alpha_{k_{1}},\alpha_{k_{2}})\) belongs to a zero-sum triangle \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha')\), where \(\alpha'\in N(\alpha_{k_1})\). Since \(\alpha_{k_{3}}\) and \(\alpha_{k_{7}}\) are the only vertices in \(N(\alpha_{k_{1}})\) that are adjacent to \(\alpha_{k_{2}}\), we obtain that \(\alpha'=\alpha_{k_{3}}\) or \(\alpha_{k_{7}}\). Without loss of generality, assume \(\alpha'=\alpha_{k_{3}}\). Thus, \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_{3}})\) is a zero-sum triangle. Now part \((i)\) of Lemma 8 implies that neither \(\triangle(\alpha_{k_{1}}, \alpha_{k_{3}}, \alpha_{k_{4}})\) nor \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_{7}})\) is a zero-sum triangle. Applying \((ii)\) of Lemma 8, we obtain that the edges \((\alpha_{k_{3}},\alpha_{k_{4}})\) and \((\alpha_{k_{2}},\alpha_{k_{7}})\) belong to zero-sum triangles \(\triangle(\alpha_{k_{3}}, \alpha_{k_{4}}, \tilde{\alpha})\) and \(\triangle(\alpha_{k_{2}}, \alpha_{k_{7}}, \alpha'')\), respectively, and \(\tilde{\alpha},\alpha''\notin N[\alpha_{k_1}]=\{\alpha_{k_1},\alpha_{k_2},\dotsc,\alpha_{k_7}\}\).
Analogously, applying \((ii)\) of Lemma 8, we obtain that \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{5}})\) and \(\triangle(\alpha_{k_{1}}, \alpha_{k_{6}}, \alpha_{k_{7}})\) are zero-sum triangles, \(\triangle(\alpha_{k_{1}}, \alpha_{k_{5}}, \alpha_{k_{6}})\) is not a zero-sum triangle and there exists a vertex \(\alpha'''\) such that \(\triangle(\alpha_{k_{5}}, \alpha_{k_{6}}, \alpha''')\) is a zero-sum triangle and \(\alpha'''\notin N[\alpha_{k_1}]\).
Now, all obtained zero-sum triangles imply the relations \[\label{eq4} \begin{align} \alpha_{k_{1}} &+ \alpha_{k_{2}} + \alpha_{k_{3}} = 0,\\ \alpha_{k_{1}} &+ \alpha_{k_{4}} + \alpha_{k_{5}} = 0,\\ \alpha_{k_{1}} &+ \alpha_{k_{6}} + \alpha_{k_{7}} = 0,\\ \alpha_{k_{3}} &+ \alpha_{k_{4}} + \tilde{\alpha} = 0,\\ \alpha_{k_{5}} &+ \alpha_{k_{6}} + \alpha''' = 0,\\ \alpha_{k_{2}} &+ \alpha_{k_{7}} + \alpha'' = 0. \end{align}\tag{7}\] By adding the first three relations in 7 and using the expressions for \(\tilde{\alpha},\alpha'',\) \(\alpha'''\) from the last three relations in 7 , we obtain \[3\alpha_{k_{1}}+(\alpha_{k_{3}}+\alpha_{k_{4}})+(\alpha_{k_{5}}+\alpha_{k_{6}})+(\alpha_{k_{2}}+ \alpha_{k_{7}})=3\alpha_{k_{1}}-\tilde{\alpha}-\alpha'''-\alpha''=0.\] If \(\tilde{\alpha}=\alpha''=\alpha'''\), then the last equality implies \(\alpha_{k_{1}}=\tilde{\alpha}\), which is impossible, since \(\tilde{\alpha}\notin N[\alpha_{k_1}]\). Hence, the set \(\{\alpha_{k_1},\tilde{\alpha},\alpha'',\alpha'''\}\) contains at least three distinct numbers. But then the relation \(3\alpha_{k_{1}}-\tilde{\alpha}-\alpha'''-\alpha''=0\) contradicts Lemma 3. This proves that the graph F}TJG cannot be an induced subgraph of \(\mathcal{G}\).
We check with SageMath [21] that each graph in \(\{\mathcal{G}_{34}, \mathcal{G}_{36}, \mathcal{G}_{37}, \mathcal{G}_{38}\}\) contains an induced subgraph isomorphic to F}TJG. Hence, \(\mathcal{G}\) is not isomorphic to either of these graphs. This together with 6 imply that \(\mathcal{G}\) must be isomorphic to some graph in the following set \[\{\mathcal{G}_{20}, \mathcal{G}_{21}, \mathcal{G}_{22}, \mathcal{G}_{23}, \mathcal{G}_{24}, \mathcal{G}_{35}, \mathcal{G}_{40}\}.\]
Next, we will prove that \(\mathcal{G}\) is not isomorphic to either of the first five graphs in the set above, namely, \(\{\mathcal{G}_{20}, \mathcal{G}_{21}, \mathcal{G}_{22}, \mathcal{G}_{23}, \mathcal{G}_{24}\}\).
The 16 vertices of each graph \(\mathcal{G}_i\), \(i\in\{20,21,22,23,24\}\), are labeled with numbers \(1,2,\dotsc,16\). We will consider every such graph \(\mathcal{G}_i\) separately. Assuming that \(\mathcal{G}\) is isomorphic to \(\mathcal{G}_i\), we will show that it leads to a contradiction. We will identify each vertex \(v\in \{1,2,\dotsc,16\}\) of \(\mathcal{G}_i\) with \(\alpha_v\). So that instead of treating \(\mathcal{G}\) and \(\mathcal{G}_i\) as isomorphic graphs, we will treat them as coinciding graphs, i.e., \(\mathcal{G}=\mathcal{G}_i\).
Assume that \(\mathcal{G}=\mathcal{G}_{20}\). The induced subgraphs \(\mathcal{G}_{20}(\alpha_1)\) and \(\mathcal{G}_{20}(\alpha_6)\) are shown in Figure 3.
We have that \(\alpha_2,\alpha_6\in N(\alpha_1)\), \(\deg_{\mathcal{G}_{20}(\alpha_1)}(\alpha_2)=2\) and \((\alpha_2,\alpha_6)\) is an edge in \(\mathcal{G}_{20}\). Hence, part \((iii)\) of Lemma 8 implies that \(\triangle(\alpha_1,\alpha_2,\) \(\alpha_6)\) is a zero-sum triangle. Similarly, \(\alpha_1,\alpha_7\in N(\alpha_6)\), \(\deg_{\mathcal{G}_{20}(\alpha_6)}(\alpha_7)=2\) and \((\alpha_1,\alpha_7)\) is an edge in \(\mathcal{G}_{20}\). Again, applying part \((iii)\) of Lemma 8, we obtain that \(\triangle(\alpha_1,\alpha_6,\alpha_7)\) is a zero-sum triangle. So that zero-sum triangles \(\triangle(\alpha_1,\alpha_2,\alpha_6)\) and \(\triangle(\alpha_1,\alpha_6,\alpha_7)\) share two distinct vertices \(\alpha_1\) and \(\alpha_6\). This contradicts part \((i)\) of Lemma 8. Thus, \(\mathcal{G}\neq \mathcal{G}_{20}\).
Analogously, for every \(i\in\{21,22,23,24\}\), considering the induced subgraphs \(\mathcal{G}_{i}(\alpha_1)\) and \(\mathcal{G}_{i}(\alpha_6)\), which are given in Figures 4-7, and applying Lemma 8, we obtain that \(\mathcal{G}\neq \mathcal{G}_i\).
Hence, we are left with two cases: \(\mathcal{G}=\mathcal{G}_{35}\) or \(\mathcal{G}=\mathcal{G}_{40}\). To eliminate the first case, consider the graph shown in Figure 8.
We will prove that this graph cannot be an induced subgraph of \(\mathcal{G}\). Assume, on the contrary, that it is. By \((ii)\) of Lemma 8, the edge \((\alpha_{k_{1}},\alpha_{k_{2}})\) belongs to a zero-sum triangle \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha')\), where \(\alpha'\in N(\alpha_{k_1})\). Since \(\alpha_{k_{3}}\) and \(\alpha_{k_{4}}\) are the only vertices in \(N(\alpha_{k_{1}})\) that are adjacent to \(\alpha_{k_{2}}\), we obtain that \(\alpha'=\alpha_{k_{3}}\) or \(\alpha_{k_{4}}\). Thus, we have to consider two cases: \((i)\) \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_3})\) is a zero-sum triangle; \((ii)\) \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_4})\) is a zero-sum triangle.
Case \((i)\): \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_3})\) is a zero-sum triangle. By part \((ii)\) of Lemma 8, the edge \((\alpha_{k_{1}},\alpha_{k_{4}})\) belongs to a zero-sum triangle \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha'')\), where \(\alpha''\in N(\alpha_{k_1})\). We have that \(\alpha''\in \{\alpha_{k_2},\alpha_{k_3},\alpha_{k_5},\alpha_{k_6}\}\), since \(\alpha_{k_4}\) is not adjacent to \(\alpha_{k_7}\). Part \((i)\) of Lemma 8 implies that neither \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{2}})\) nor \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}},\) \(\alpha_{k_{3}})\) is a zero-sum triangle. Hence, \(\alpha''\in\{\alpha_{k_{5}},\alpha_{k_{6}}\}\).
Assume that \(\alpha''=\alpha_{k_{5}}\). Then we have zero-sum triangles \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{5}})\), \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_3})\), and \((\alpha_{k_{2}},\alpha_{k_{4}})\) together with \((\alpha_{k_{3}},\alpha_{k_{5}})\) are edges in \(\mathcal{G}\). This contradicts part \((iv)\) of Lemma 8.
Assume that \(\alpha''=\alpha_{k_{6}}\), so that \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{6}})\) is a zero-sum triangle. Part \((i)\) of Lemma 8 implies that \(\triangle(\alpha_{k_{1}}, \alpha_{k_{6}}, \alpha_{k_{7}})\) is not a zero-sum triangle, since it shares an edge with the zero-sum triangle \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{6}})\). Hence, \(\triangle(\alpha_{k_{1}}, \alpha_{k_{5}}, \alpha_{k_{7}})\) is a zero-sum triangle. Now, we have two zero-sum triangles \(\triangle(\alpha_{k_{1}}, \alpha_{k_{4}}, \alpha_{k_{6}})\) and \(\triangle(\alpha_{k_{1}}, \alpha_{k_{5}}, \alpha_{k_{7}})\), and \((\alpha_{k_{4}},\alpha_{k_{5}})\) together with \((\alpha_{k_{6}},\alpha_{k_{7}})\) are edges in \(\mathcal{G}\). This contradicts part \((iv)\) of Lemma 8.
Case \((ii)\): \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_4})\) is a zero-sum triangle. Part \((i)\) of Lemma 8 implies that neither \(\triangle(\alpha_{k_{1}}, \alpha_{k_{3}}, \alpha_{k_{2}})\) nor \(\triangle(\alpha_{k_{1}}, \alpha_{k_{3}}, \alpha_{k_{4}})\) is a zero-sum triangle, since they share an edge with the zero-sum triangle \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_{4}})\). Hence, \(\triangle(\alpha_{k_{1}}, \alpha_{k_{3}}, \alpha_{k_{5}})\) is a zero-sum triangle. Now, we have two zero-sum triangles \(\triangle(\alpha_{k_{1}}, \alpha_{k_{2}}, \alpha_{k_{4}})\) and \(\triangle(\alpha_{k_{1}}, \alpha_{k_{3}}, \alpha_{k_{5}})\), and \((\alpha_{k_{2}},\alpha_{k_{3}})\) together with \((\alpha_{k_{4}},\alpha_{k_{5}})\) are edges in \(\mathcal{G}\). This contradicts part \((iv)\) of Lemma 8.
This completes the proof that the graph Fummw cannot be an induced subgraph of \(\mathcal{G}\). We check with SageMath [21] that the graph \(\mathcal{G}_{35}\) contains an induced subgraph isomorphic to Fummw. Therefore \(\mathcal{G}\neq \mathcal{G}_{35}\) and we are left to consider the last option \(\mathcal{G}= \mathcal{G}_{40}\). To do so, consider the graph shown in Figure 9.
We will prove that this graph cannot be an induced subgraph of \(\mathcal{G}\). Assume, to the contrary, that it is. Part \((iii)\) of Lemma 7 implies that there exist three distinct relations \(\alpha_{k_{1}} + \alpha'_i + \alpha''_i = 0\), \(i\in\{1,2,3\}\), which correspond to three distinct zero-sum triangles \(\triangle(\alpha_{k_{1}}, \alpha'_i, \alpha''_i)\). Then part \((ii)\) of Lemma 8 yields \(\alpha'_i, \alpha''_i\in N(\alpha_{k_{1}})\) for every \(i\in\{1,2,3\}\). Moreover, applying part \((i)\) of Lemma 8, we obtain that any two of the three sets \(\{\alpha'_i, \alpha''_i\}\), \(i\in\{1,2,3\}\), are disjoint. Hence, \[\{\alpha'_1, \alpha''_1,\alpha'_2, \alpha''_2,\alpha'_3, \alpha''_3\} = N(\alpha_{k_{1}}) = \{\alpha_{k_{2}},\alpha_{k_{3}},\alpha_{k_{4}},\alpha_{k_{5}},\alpha_{k_{6}},\alpha_{k_{7}}\}.\] Now, adding up the relations \(\alpha_{k_{1}} + \alpha'_i + \alpha''_i = 0\), \(i\in\{1,2,3\}\), we obtain \[\label{eq8} 3\alpha_{k_{1}}+\alpha_{k_{2}}+\alpha_{k_{3}}+\alpha_{k_{4}}+\alpha_{k_{5}}+\alpha_{k_{6}}+\alpha_{k_{7}}=0.\tag{8}\] Analogously, considering the three relations \(\alpha_{k_{8}} + \tilde{\alpha}'_i + \tilde{\alpha}''_i = 0\), \(i\in\{1,2,3\}\), we obtain \[3\alpha_{k_{8}}+\alpha_{k_{2}}+\alpha_{k_{3}}+\alpha_{k_{4}}+\alpha_{k_{5}}+\alpha_{k_{6}}+\alpha_{k_{7}}=0.\] This equality, together with 8 , imply that \(\alpha_{k_{1}}=\alpha_{k_{8}}\), which is a contradiction. Hence, the graph G~z\(\setminus\)z{ cannot be an induced subgraph of \(\mathcal{G}\). We check with SageMath [21] that the graph \(\mathcal{G}_{40}\) contains an induced subgraph isomorphic to G~z\(\setminus\)z{. Therefore \(\mathcal{G}\neq \mathcal{G}_{40}\).
Finally, we have proved that \(\mathcal{G}\neq\mathcal{G}_{i}\), for \(i=1,2,\dots 40\). Thus, no algebraic number of degree \(d=16\) satisfies the relation 2 . ◻
4 SageMath code↩︎
# Load the codes of all 40 vertex-transitive graphs on 16 vertices of degree 6. These graphs are contained in the file 'alltrans16_k=06.txt' which is available at https://zenodo.org/records/4010122
Graph_strings = []
with open('alltrans16_k=06.txt', 'r') as file:
for line in file:
Graph_strings.append(line.strip())
# Determine all graphs in Graph_strings that have a subgraph isomorphic to FyTAG (code in graph6 format).
FyTAG = Graph({1:[2,3,4,5,6,7],2:[3],3:[],4:[5],5:[],6:[7],7:[]})
Graph_FyTAG =[]
for i in range(len(Graph_strings)):
G = Graph(Graph_strings[i])
if G.subgraph_search(FyTAG, induced=False) is not None:
Graph_FyTAG.append(G)
# Determine all graphs in Graph_FyTAG that don't have an induced subgraph isomorphic to FTJG (code in graph6 format).
FTJG = Graph({1:[2,3,4,5,6,7],2:[3],3:[4],4:[5],5:[6],6:[7],7:[2]})
Graph_FTJG =[]
for G in Graph_FyTAG:
if G.subgraph_search(FTJG, induced=True) is None:
Graph_FTJG.append(G)
# Let G be a graph and v -- one of its vertices. Then the induced graph G(v) can be obtained by calling G.subgraph([v]+G.neighbors(v)).
# Example with G=Graph_FTJG nad v=1:
Graph_FTJG[2].subgraph([1]+Graph_FTJG[2].neighbors(1))References↩︎
https://www.sagemath.orgSageMath, the Sage Mathematics Software System
(Version 10.6.0). 2025.