¹

1 Introduction↩︎

In this study, we provide two results that relate the Tutte polynomials.

The first result is as follows: In [1], de la Harpe and Jones introduced graph-invariant polynomials. We refer to these polynomials as \(n\)-state polynomials.

The main focus of this paper is on non-directed graphs. Let \(G\) be a graph and \(X\) be a finite set with \(n\) elements. \(W_n=(x_{ij})\) is an \(|X|\times |X|\) symmetric matrix indexed by the elements of \(X\). We assume that \(X=\{1,2,\ldots,n\}\) and \(x_{ij}\) are variables. Moreover, let \(\sigma:V(G)\rightarrow X\) be a state function. Subsequently, the \(n\)-state polynomials with \(n(n+1)/2\) variables are defined as follows:

The special values of these polynomials are approximately the same as certain known polynomial invariants for graphs. For example, let \[W_{{\rm Negami}}= \begin{pmatrix} x_1+y&y&\cdots &y\\ y&x_1+y&\cdots &y\\ \vdots&\vdots&\ddots &\vdots\\ y&y&\cdots &x_1+y \end{pmatrix}.\] Then, \(Z_{W_{\rm Negami}}(G)\) are known as Negami polynomials [2]. In [3], Oxley demonstrated that \(Z_{W_{\rm Negami}}(G)\) is essentially equivalent to the Tutte polynomials [4]–[6]. Therefore, \(n\)-state polynomials are a generalization of the Tutte polynomials.

Moreover, let \(W_{{\rm extNegami}}=(x_{ij})\), \[x_{ij}= \left\{ \begin{array}{l} x_i+y\;(i=j<n),\\ x_n+y\;(i=j\geq n),\\ y. \end{array} \right.\] Then, \(Z_{W_{\rm extNegami}}(G)\) are known as extended Negami polynomials [7].

In this study, we demonstrate that \(n\)-state polynomials are complete invariants for graphs.

According to the proof of Theorem 1, for \(n\geq 2\), a graph \(G\) with \(n\) vertices is determined by the \(n\)-state polynomials, which have \(n(n+1)/2\) variables. In this study, we consider the following problems:

The first purpose of this study is to introduce polynomial invariants for graphs and to provide an answer to Problem 1. The number of variables of our polynomials is one. Furthermore, for any given graph \(G\), if the degree of our polynomial is sufficiently large, then the set of terms of our polynomial is one-to-one corresponding to the set of terms of the \(n\)-state polynomial with the same degree. We refer to such polynomials as pseudo \(n\)-state polynomials, denoted by \(Z_{\widetilde{W}_n}(G)\), which are explained in the following.

For \(\ell\in\mathbb{N}\), we denote the \(\ell\)-th prime number as \(P(\ell)\). We set the functions \(a(i)\) on \(\mathbb{N}\) and \(b(i,j)\) on \(\mathbb{N}^2\) such that \[\displaystyle a(i,j) := \left(\frac{i(i + 1)}{2}+(j-i)\right).\] Let \(\widetilde{W}_n=(\widetilde{W}_n(i,j))\) be the \(n\times n\) symmetric matrix such that, for \(i\geq j\), \[\widetilde{W}_n(i,j) := \left\{ \begin{array}{l} P(n^{n a(i,i)}) x^{P(n^{n a(i,i)})}\;(if i=j),\\ P(n^{n a(i,j)}) x^{P(n^{n a(i,j)})}\;(if i> j). \end{array} \right.\] Next, we present the definition of the pseudo \(n\)-state polynomials:

We note that the number of variables of our polynomials is one. For example, for \(n=2\), \[\widetilde{W}_2= \begin{pmatrix} 7 x^{7}&53 x^{53}\\ 53 x^{53}&311 x^{311} \end{pmatrix}\] and for \(n=3\), \[\widetilde{W}_3 = \begin{pmatrix} 103 x^{103} & 5519 x^{5519} & 7867547 x^{7867547} \\ 5519 x^{5519} & 220861 x^{220861} & 262960091 x^{262960091} \\ 7867547 x^{7867547} & 262960091 x^{262960091} & 8448283757 x^{8448283757} \end{pmatrix}.\] Then, the pseudo \(2\)-state polynomial for the complete graph \(K_2\) is \[Z_{\widetilde{W}_2}(K_2)= 311 x^{311}+106 x^{53}+7 x^7\] and the pseudo \(3\)-state polynomial for the complete graph \(K_3\) is \[\begin{align} Z_{\widetilde{W}_3}(K_3)&= 1752546015417169494746495151 x^{8974203939}\\ &+1568803100908626481902639 x^{8464018851}\\ &+602983567540694711837927399093 x^{25344851271}\\ &+45816295551192560609823 x^{526141043}\\ &+68507927876961253578 x^{270833157}\\ &+19126573401337581 x^{15735197}\\ &+10773507110137381 x^{662583}+20181854789463 x^{231899}\\ &+9411942549 x^{11141}+1092727 x^{309}. \end{align}\] The first main result in this paper is as follows:

In the following, we present the second result of the study. Let \(L_1\) and \(L_2\) be two non-isomorphic lattices. We state that \(L_1\) and \(L_2\) are theta series equivalent if those theta series are the same: \[\theta_{L_1}(q)=\theta_{L_2}(q).\] The problem of determining theta series equivalent lattices is discussed in Prof. Conway’s book [8] under the title “Can You Hear the Shape of a Lattice?”

For example, it is well known, as per the example of Milnor, that \(E_8^2\) and \(D_{16}^+\) are theta series equivalent [8], [9], and several examples are provided in [8].

In this study, we present a method to find theta series equivalent lattices using matroids and their Tutte polynomials. The second main result is as follows:

The remainder of this paper is organized as follows: In Section 2, we summarize basic facts of matroids, codes, and lattices. In Section 3, we provide the proofs of Theorems 1 and 2. In Section 4, we provide the proof of Theorem 3. Finally, in Section 5, we present several remarks.

All computer calculations in this study were performed with the aid of Magma [10] and Mathematica [11].

2 Preliminaries↩︎

In this section, we summarize basic facts of matroids, codes, and lattices.

2.1 Matroids↩︎

Let \(E\) be a set. A matroid \(M\) on \(E=E(M)\) is a pair \((E,\mathcal{I})\), where \(\mathcal{I}\) is a non-empty family of subsets of \(E\) with the following properties: \[\begin{cases} (i) & ifI\in \mathcal{I}andJ\subset I,thenJ\in \mathcal{I}; \\ (ii) & ifI_1,I_2\in \mathcal{I}and |I_1|<|I_2|, \\ & then there existse\in I_2\setminus I_1 \\ & such thatI_1\cup \{e\}\in \mathcal{I}. \end{cases}\] Each element of the set \(\mathcal{I}\) is known as an independent set. A matroid \((E, \mathcal{I})\) is isomorphic to another matroid \((E', \mathcal{I}')\) if there exists a bijection \(\varphi\) from \(E\) to \(E'\) such that \(\varphi(I)\in \mathcal{I}'\) holds for each member \(I\in \mathcal{I}\), and \(\varphi^{-1}(I')\in \mathcal{I}\) holds for each member \(I'\in \mathcal{I}'\).

It follows from the second axiom that all maximal independent sets in a matroid \(M\) take the same cardinality, known as the rank of \(M\). These maximal independent sets \(\mathcal{B}(M)\) are referred to as the bases of \(M\). The rank \(\rho(A)\) of an arbitrary subset \(A\) of \(E\) is the cardinality of the largest independent set contained in \(A\).

We provide examples below.

The following fact is used in the proof of Theorem 3:

The classification of matroids is one of the most important problems in the theory of matroids. The Tutte polynomials are a tool for classifying the matroids. Let \(M\) be a matroid on the set \(E\) with a rank function \(\rho\). The Tutte polynomial of \(M\) is defined as follows [4]–[6]: \[\begin{align} T(M)&:=T(M;x,y)\\ &:=\sum_{A\subset E}(x-1)^{\rho (E)-\rho (A)}(y-1)^{|A|-\rho (A)}. \end{align}\]

It can easily be demonstrated that \(T(M;x,y)\) is a matroid invariant. Two matroids are \(T\)-equivalent if their Tutte polynomials are equivalent. It is well known that there exist two inequivalent matroids, which are \(T\)-equivalent (for example, see [12] or Section 4), and these examples are key facts for the proof of Theorem 3.

2.2 Codes↩︎

Let \(\mathbb{F}_2\) be the finite field of two elements. A linear code \(C\) with length \(n\) is a linear subspace of \(\mathbb{F}_{2}^{n}\). An inner product \(({x},{y})\) on \(\mathbb{F}_2^n\) is given by \[(x,y)=\sum_{i=1}^nx_iy_i,\] where \(x,y\in \mathbb{F}_q^n\) with \(x=(x_1,x_2,\ldots, x_n)\) and \(y=(y_1,y_2,\ldots, y_n)\). The dual of the linear code \(C\) is defined as follows: \[C^{\perp}=\{{y}\in \mathbb{F}_{2}^{n}\mid ({x},{y}) =0 \text{ for all }{x}\in C\}.\]

A linear code \(C\) is known as self-dual if \(C=C^{\perp}\). For \(x \in\mathbb{F}_2^n\), the weight \(\mathop{\mathrm{wt}}(x)\) is the number of its nonzero components. A self-dual code \(C\) is doubly even if all codewords of \(C\) have a weight that is divisible by four.

Let \(C\) be a linear code of length \(n\). The weight enumerator associated with \(C\) is \[w_{C}(x,y)=\sum_{c\in C}x^{n-\mathop{\mathrm{wt}}(c)}y^{\mathop{\mathrm{wt}}(c)}.\] For example, let \(C\) be a doubly even self-dual code. Then, \[w_{C}(x,y)\in\mathbb{C}[P_8,P_{24}],\] where \(P_{8}=x^8+14x^4y^4+y^8, P_{24}=x^4y^4(x^4-y^4)^4\) [9], [13].

2.3 Lattices↩︎

A lattice in \(\mathbb{R}^{n}\) is a subgroup \(L \subset \mathbb{R}^{n}\) with the property that there exists a basis \(\{e_{1}, \ldots, e_{n}\}\) of \(\mathbb{R}^{n}\) such that \(L =\mathbb{Z}e_{1}\oplus \cdots \oplus\mathbb{Z}e_{n}\). \(n\) is known as the rank of \(L\). The dual lattice of \(L\) is the lattice \[L^{\sharp}:=\{y\in \mathbb{R}^{n}\mid (y,x) \in\mathbb{Z}, \;\forall x\in L\},\] where \((x,y)\) is the standard inner product. A lattice \(L\) is integral if \((x,y) \in\mathbb{Z}\) for all \(x\), \(y\in L\). An integral lattice \(L\) is referred to as even if \((x,x) \in 2\mathbb{Z}\) for all \(x\in L\). An integral lattice \(L\) is referred to as unimodular if \(L^{\sharp}=L\).

The norm of a vector \(x\) is defined as \((x, x)\). A unimodular lattice with even norms is said to be even. An \(n\)-dimensional even unimodular lattice exists if and only if \(n \equiv 0 \pmod 8\). For example, the unique even unimodular lattice of rank \(8\), namely \(E_8\), exists, and only two even unimodular lattices of rank \(16\) exist, namely \(E_8^2\) and \(D_{16}^+\), which we mentioned as Milnor’s example of Problem 2. Moreover, the unique even unimodular lattice without roots of rank \(24\) is the Leech lattice \(\Lambda_{24}\).

Let \(\mathbb{H} :=\{z\in\mathbb{C}\mid {\rm Im}(z) >0\}\) be the upper half-plane.

For example, we consider an even unimodular lattice \(L\). Then, the theta series \(\theta_{L}(q)\) of \(L\) is a modular form with respect to \(SL_{2}(\mathbb{Z})\). More precisely, we have \[\theta_{L}\in \mathbb{C}[E_4,\Delta]\] where \[\begin{align} E_4(q)&:=1+240\sum_{n=1}^{\infty}\sigma_{3}(n)q^{2n}, \\ E_6(q)&:=1-504\sum_{n=1}^{\infty}\sigma_{5}(n)q^{2n}, \\ \Delta(q)&:=\frac{E_4(q)^3-E_6(q)^2}{1728}. \end{align}\] where \(\sigma_{k-1}(n):=\sum_{d\mid n}d^{k-1}\) [9], [13].

3 Proofs of Theorems 1 and 2↩︎

3.1 Proof of Theorem 1↩︎

In this section, we prove Theorem 1.

3.2 Proof of Theorem 2↩︎

In this section, we prove Theorem 2.

4 Proof of Theorem 3↩︎

In this section, we present the proof of Theorem 3. Prior to this, in Section 4.1, we provide a relationship between matroids and codes, and in Section 4.2, we present a relationship between codes and lattices.

4.1 Relationship between matroids and codes↩︎

In [14], a relationship between the weight enumerators of codes and the Tutte polynomials of matroids was presented.

Let \(M\) be a vector matroid obtained from the \(k\times n\) matrix \(A\). Then, the row space of \(A\) is a code over \(\mathbb{F}_2\) of length \(n\). We denote such a code as \(C_M\). The Tutte polynomial of a vector matroid \(M\) and the weight enumerator of \(C_M\) exhibit the following relation:

4.2 Relationship between codes and lattices↩︎

We propose a method to construct lattices from codes over \(\mathbb{F}_2\), which is referred to as Construction A [15], [16]. Let \(\rho\) be a map from \(\mathbb{Z}^n\) to \(\mathbb{F}_2^n\) sending \((x_i)\) to \((x_i\pmod{2})\). If \(C\) is a \(\mathbb{F}_{2}\) code of length \(n\), we have an \(n\)-dimensional unimodular lattice \[L_C=\frac{1}{\sqrt{2}}\{x\in \mathbb{Z}^n \mid \rho (x)\in C\}.\] The following is an established fact [13]:

We explain Milnor’s example of Problem 2 [9]. There exist non-isomorphic doubly even self-dual codes of length \(16\), \(e_8^2\) and \(d_{16}^+\) [9]. Then, according to section 2.2, their weight enumerators are the same: \[w_{e_8^2}(x,y)=w_{d_{16}^+}(x,y)=P_8^2=(x^8+14x^4y^4+y^8)^2.\] Moreover, we obtain the non-isomorphic unimodular lattices of rank \(16\), \(E_8^2=L_{e_8^2}\) and \(D_{16}^+=L_{d_{16}^+}\), with the same theta series: \[\begin{align} \theta_{E_8}(q)&=\theta_{D_{16}^+}(q)\\ &=w_{e_8^2}(\theta_3,\theta_2)=w_{d_{16}^+}(\theta_3,\theta_2) =(\theta_{3}^8+14\theta_{3}^4\theta_{2}^4+\theta_{2}^8)^2=E_4(q). \end{align}\] Therefore, this example arises from the following concept:

The main idea of the proof of Theorem 3 is that we add “Matriods” to the above diagram:

Thus, first, we have non-isomorphic graphic matroids with the same Tutte polynomials, following which we obtain non-isomorphic codes and lattices, which have the same theta series. We explain this in further detail in the following section.

4.3 Proof of Theorem 3↩︎

In this section, we demonstrate the proof of Theorem 3.

Proof of Theorem 3. Let \(G_1\) and \(G_2\) be the graphs in Figure 1 [17].

Furthermore, for \(i\in \{1,2\}\) and \(n\in \mathbb{Z}_{\geq 0}\), let \(G_i(n)=G_i \ast P_n\) be the joining of the graphs \(G_i(n)\) and \(P_n\), where \(P_n\) indicates the path graph with \(n\) edges. Note that the joining \(G = G_1 \ast G_2\) of graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) is the graph union of the \(G_1\) and \(G_2\) together with all edges joining \(V_1\) and \(V_2\).

For \(i\in\{1,2\}\) and \(m\in \mathbb{Z}_{\geq 0}\), let \(G_i(m,n)\) be the graphs with \(m\) times edge subdivisions with respect to the edges: \[v_1v_2, v_3v_4, v_5v_6, v'_1v'_2, v'_3v'_4, v'_5v'_6.\] We note that, for \(i\in \{1,2\}\), the number of edges of \(G_i(m,n)\) is \(3m+11n+24\).

It was demonstrated in [17] that \(G_1(m,n)\) and \(G_2(m,n)\) are non-isomorphic graphic matroids with the same Tutte polynomials. For \(i\in \{1,2\}\), let \(M_i\) be the vector matroid with respect to the incident matrix of \(G_i(m,n)\). Then, according to Fact 1 and Theorem 4, we can obtain the non-isomorphic codes \(C_{M_1}\) and \(C_{M_2}\) with length \(3m+11n+24\) that have the same weight enumerator.

Let \(\varphi:\mathbb{F}_2\rightarrow \mathbb{F}_2^4\) be a map such that \[0\mapsto 0000, 1\mapsto 1111.\] For \(i\in \{1,2\}\), we define a new code with length \(4(3m+11n+24)\): \[\widetilde{C}_{M_i}:= \{(\varphi(c_i))\mid (c_i)\in {C}_{M_i}\}.\] We note that \(\widetilde{C}_{M_i}\) is doubly even. According to [18], [19] and Theorem 5, we can obtain the non-isomorphic lattices \(L_{\widetilde{C}_{M_1}}\) and \(L_{\widetilde{C}_{M_2}}\) with the same theta series.

The rank of \(L_{\widetilde{C}_{M_1}}\) and \(L_{\widetilde{C}_{M_2}}\) is \(4(3m+11n+24)\). We remark that \[3m+11n+24\] represents the numbers \[\{24, 27, 30, 33, 35, 36, 38, 39, 41, 42\}\cup \{i\in \mathbb{Z}\mid i\geq 44\}.\] This completes the proof of Theorem 3. ◻

5 Concluding remarks↩︎

We provide the following remarks:

1. According to the proof of Theorem 2, the pseudo \(3m\)-state polynomials recover the graph structure with a number of edges less than or equal to \(m\). It is natural to ask whether there exists a function \(f(n)\) on \(n\in \mathbb{N}\) such that the polynomials with \(f(n)\) variables recover the graph structure with a number of vertices less than or equal to \(n\).

2. Problem: For \(n\in \mathbb{N}\), determine the set of graphs \(\mathcal{G}_n\) such that the pseudo \(n\)-state polynomials determine any graph \(G\in \mathcal{G}_n\).

3. Problem: In [20], [21], we defined a complete invariant for matroids. For a graphic matroid, determine whether or not this invariant is a special value of \(n\)-state polynomials.

4. In the proof of Theorem 3, we demonstrated that \(L_{\widetilde{C}_{M_1}}\) and \(L_{\widetilde{C}_{M_2}}\) are non-isomorphic with rank \(4d\), where \[d\in \{24, 27, 30, 33, 35, 36, 38, 39, 41, 42\}\cup \{i\in \mathbb{Z}\mid i\geq 44\}.\] However, for \[d\in \{24, 27, 30, 33, 35\},\] we showed, with the aid of Magma, that \(L_{{C}_{M_1}}\) and \(L_{{C}_{M_2}}\) are non-isomorphic. Therefore, we have the following conjecture:

   Conjecture 1. \(L_{{C}_{M_1}}\) and \(L_{{C}_{M_2}}\), as defined in the proof of Theorem 3, are non-isomorphic.

   If Conjecture 1 is true,

   we obtain examples of Problem 2 for rank \[d\in \{24, 27, 30, 33, 35, 36, 38, 39, 41, 42\}\cup \{i\in \mathbb{Z}\mid i\geq 44\}.\]

5. The Tutte polynomials of genus \(g\) were defined in [20] and we discuss their properties in a forthcoming paper [21]. According to Theorem 4, there is a correspondence between the Tutte polynomials and weight enumerators.

   Thus, it is also natural to ask whether there is a correspondence between the Tutte polynomials and weight enumerators of genus \(g\).

   It is well known that the weight enumerators of genus \(g\) yield the Siegel theta series. Therefore, if such a correspondence exists, we may obtain examples whereby the non-isomorphic lattices have the same Siegel theta series.

6. Using the concept of this study and the following diagram:

   Matroids \(\longrightarrow\) Codes \(\longrightarrow\) Lattices \(\longrightarrow\) Vertex operator (super) algebras,

   we may obtain the non-isomorphic vertex operator (super) algebras with the same trace function.

Acknowledgments↩︎

The authors thank Prof. Akihiro Munemasa and Prof. Manabu Oura for their helpful discussions on this research. The authors would also like to thank the anonymous reviewers for their beneficial comments on an earlier version of the manuscript. This work was supported by JSPS KAKENHI (18K03217, 18K03388).

References↩︎