# Products of finite order rotations and quantum gates universality

Katarzyna Karnas1 and Adam Sawicki1

###### ?abstractname?

We consider a product of two finite order quantum $SU(2)$-gates $U_{1}$,
$U_{2}$ and ask when $U_{1}\cdot U_{2}$ has an infinite order. Using the fact
that $SU(2)$ is a double cover of $SO(3)$ we actually study the product
$O(\gamma,\vec{k}_{12})$ of two rotations $O(\phi,\vec{k}_{1})\in SO(3)$ and
$O(\phi,\vec{k}_{2})\in SO(3)$ about axes $\vec{k}_{1}$,
$\vec{k}_{2}\in\mathbb{R}^{3}$. In particular we focus on the case when
$\vec{k}_{1}\cdot\vec{k}_{2}=0$, and $\phi_{1}=\phi=\phi_{2}$ are rational
multiple of $\pi$ and show that $\gamma$ is not a rational multiple of $\pi$
unless $\phi\in\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$. The proof presented in
this paper boils down to finding all pairs
$\gamma,\phi\in\\{a\pi:a\in\mathbb{Q}\\}$ that are solutions of
$\cos\frac{\gamma}{2}=\cos^{2}\frac{\phi}{2}$.

1Center for Theoretical Physics PAS, Al. Lotników 32/46, 02-668, Warszawa,
Poland

##  1 Introduction

A finite subset $\mathcal{S}=\\{g_{1},\ldots,g_{k}\\}$ of a Lie group $G$ is
called a generating set if the set

$\displaystyle<\mathcal{S}>:=\\{g_{i_{1}}^{k_{1}}\cdot\ldots\cdot
g_{i_{m}}^{k_{m}}:g_{i_{j}}\in\mathcal{S},k_{j}\in\mathbb{N},i_{j}\in\\{1,\ldots,n\\}\\},$
(1)

consisting of all words built using elements of $\mathcal{S}$ is dense in $G$.
The problem of characterisation of generating sets for various types of Lie
groups has recently attracted much more interest, in particular due to its
direct connection to the quantum gates universality [4, 6, 16, 17, 18, 20, 21]
(c.f. [7, 23] for a similar problem of generating Hamiltonians). In short
words the set of quantum gates is universal if and only if it is a generating
set for $SU(d)$ or $SO(d)$. It is worth mentioning that for abelian $G$ the
smallest generating set consist of one element whereas for nonabelian it is
typically enough to use two elements [15].

Although $<\mathcal{S}>$ is closed under group multiplication it might not be
a group itself as the inverses of some elements may not be in $<S>$.
Nevertheless, its closure has a group structure (see fact 2.6 in [20]). As was
shown by Schur in his solution to the Burnside problem (see lemma 36.2 of
[8]), infinite but finitely generated groups of matrices over $\mathbb{R}$ or
$\mathbb{C}$ always contain infinite order elements. Note that the necessary
condition for $\mathcal{S}$ to be universal is that $<\mathcal{S}>$ contains
infinite number of elements. Verification of this can be thus accomplished by
pointing one infinite order element in $<\mathcal{S}>$. The efficiency of this
approach, however, is limited when all generators (elements of $\mathcal{S}$)
are of the finite order. In this case one should consider products of elements
from $\mathcal{S}$, as the noncommutativity of $G$ implies that the
composition of two (or more) finite order elements may be of infinite order.
In fact, the main step in the proof contained in [10] of the universality for
gates $\\{H,T\left(\frac{\pi}{8}\right)\\}\subset SU(2)$, where $H$ is the
Hadamard gate and $T_{\frac{\pi}{8}}$ is a phase gate (both are elements of
finite order), i.e.

$\displaystyle H=\frac{i}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\
1&-1\end{array}\right),\,\,T_{\frac{\pi}{8}}=\left(\begin{array}[]{cc}e^{i\pi/8}&0\\\
0&e^{-i\pi/8}\end{array}\right),$ (6)

is showing that $U=H\cdot T_{\frac{\pi}{8}}$ is of infinite order. The method
used in the proof boils down to finding the minimal polynomial for
$e^{i\phi}$, where the spectrum of $U$ is given by
$\\{e^{i\phi},e^{-i\phi}\\}$. If this polynomial is not a cyclotomic
polynomial then $\phi$ is not a rational multiple of $\pi$ and $U$ is of
infinite order. Although the application of this method for gates $H$ and
$T_{\frac{\pi}{8}}$ is a simple exercise [2] it becomes much more difficult
for $\\{H,T_{\phi}\\}$, where $\phi$ is any rational multiple of $\pi$ or for
an arbitrary pair of $SU(2)$ gates. In this short paper we discuss cases when
one can efficiently prove that the product of two finite order elements from
$SU(2)$ is of infinite order. As the group $SU(2)$ is the double cover of
$SO(3)$ we work with matrices belonging to $SO(3)$ rather than to $SU(2)$. In
particular we focus on the case when $\vec{k}_{1}\cdot\vec{k}_{2}=0$, and
$\phi_{1}=\phi=\phi_{2}$ are rational multiples of $\pi$ and show that
$\gamma$ is not a rational multiple of $\pi$ unless
$\phi\in\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$. The result obtained for this
case is presented as our main theorem whereas, to make our notation clearer,
we call all the previously known results as facts and our auxiliary results by
lemmas. Our proof boils down to finding all pairs
$\gamma,\phi\in\\{a\pi:a\in\mathbb{Q}\\}$ that are solutions of
$\cos\frac{\gamma}{2}=\cos^{2}\frac{\phi}{2}$. In order to show that $\gamma$
is not a rational multiple of $\pi$ one can for example find the minimal
polynomial for $e^{i\gamma}$ and check if this polynomial is cyclotomic. This
approach was studied in [19], where in section 3.1 the author shows that in
general the problem is intractable. Another approach that one could follow is
finding the minimal polynomial for $\cos^{2}\phi$ and showing that its
resultant with any of the Chebyshev polynomials in nonzero. This, however,
again turns out to be hopeless calculation. Our approach consists of the
following steps:

  1. 1.

Write equation $\cos\frac{\gamma}{2}=\cos^{2}\frac{\phi}{2}$ as
$2\cos\frac{\gamma}{2}=1+\cos\phi$.

  2. 2.

For $\phi$ \- a rational multiple of $\pi$ show that at least one coefficient
of the minimal polynomial of $\cos\phi$ is noninteger (see lemma 13).

  3. 3.

Prove that the minimal polynomial for $2\cos\frac{\gamma}{2}$ has integer
coefficients when $\gamma$ is rational multiple of $\pi$ (see lemma 16).

  4. 4.

Using the companion matrix formalism described in section 3.1 find formulas
for coefficients of the minimal polynomial of $1+\cos\phi$ in terms of the
coefficients of the minimal polynomial for $\cos\phi$ (see section 5).

  5. 5.

Show that coefficients of the minimal polynomial for $1+\cos\phi$ are not all
integers if $\phi\notin\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$ (see section 5).

The presented approach is both direct and simple. As we show all the above
steps involve easy calculations. In the last section we discuss some cases
when the rotation angles are not equal and the rotation axes are not
perpendicular.

##  2 Results

Let $O(\phi,\vec{k})$ be a rotation by $\phi$ around the axis $\vec{k}$. We
will consider three rotations about axes $\vec{k}_{x},\vec{k}_{y}$ and
$\vec{k}_{z}$ all by the same angle $\phi$:

$\displaystyle O(\phi,\vec{k}_{x})=\left(\begin{array}[]{ccc}1&0&0\\\
0&\cos\phi&\sin\phi\\\
0&-\sin\phi&\cos\phi\end{array}\right),\>O(\phi,\vec{k}_{y})=\left(\begin{array}[]{ccc}\cos\phi&0&\sin\phi\\\
0&1&0\\\
-\sin\phi&0&\cos\phi\end{array}\right),\>O(\phi,\vec{k}_{z})=\left(\begin{array}[]{ccc}\cos\phi&\sin\phi&0\\\
-\sin\phi&\cos\phi&0\\\ 0&0&1\end{array}\right).$ (16)

The corresponding $SU(2)$ matrices are:

$\displaystyle
U(\frac{\phi}{2},\vec{k}_{x})=\left(\begin{array}[]{cc}\cos\frac{\phi}{2}&\sin\frac{\phi}{2}\\\
-\sin\frac{\phi}{2}&\cos\frac{\phi}{2}\end{array}\right),\>U(\frac{\phi}{2},\vec{k}_{y})=\left(\begin{array}[]{cc}\cos\frac{\phi}{2}&i\sin\frac{\phi}{2}\\\
i\sin\frac{\phi}{2}&\cos\frac{\phi}{2}\end{array}\right),\>U(\frac{\phi}{2},\vec{k}_{z})=\left(\begin{array}[]{cc}e^{i\frac{\phi}{2}}&0\\\
0&e^{-i\frac{\phi}{2}}\end{array}\right).$ (23)

The product of any two of the above three rotations (16) is again a rotation
by an angle $\gamma$ where:

$\displaystyle 2\cos\gamma+1=\cos^{2}\phi+2\cos\phi.$ (24)

Using trigonometric identities we can write (24) in a simpler form:

$\displaystyle\pm\cos\frac{\gamma}{2}=\cos^{2}\frac{\phi}{2}.$ (25)

Note that the same equation is obtained from the product of any two unitary
matrices (23), i.e. the resulting matrix has spectrum
$\\{e^{-i\frac{\gamma}{2}},e^{i\frac{\gamma}{2}}\\}$, where $\gamma$ is
determined by equation (25). Our main technical result is

######  Theorem 1.

Assume $\phi$ is a rational multiple of $\pi$. Then $\gamma$ given by (25) is
a rational multiple of $\pi$ if and only if
$\phi\in\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$.

Using theorem 1, one easily deduces the following:

######  Corollary 2.

Assume $\phi$ is a rational multiple of $\pi$ and
$\phi\notin\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$. Let
$O(\phi,\vec{k}_{1}),O(\phi,\vec{k}_{2})\in SO(3)$ be rotations around
orthogonal axes $\vec{k}_{i}\perp\vec{k}_{j}$, by the angle $\phi$. Then
$O(\gamma,\vec{k})=O(\phi,\vec{k}_{1})O(\phi,\vec{k}_{2})$ is the rotation by
an angle $\gamma$ which is an irrational multiple of $\pi$. Moreover, the set
generated by $\\{O(\phi,\vec{k}_{1}),O(\phi,\vec{k}_{2})\\}$ or by the
corresponding unitary matrices
$\\{U(\phi/2\vec{k}_{1}),U(\phi/2,\vec{k}_{2})\\}$ is infinite if and only if
$\phi\notin\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$.

###### ?proofname? .

We only need to verify the case $\phi\in\\{\frac{k\pi}{2}:k\in\mathbb{Z}\\}$.
But in this case matrices (16) have entries in $\\{1,-1\\}$ and generate
either permutation group $S_{3}$ or finite abelian group. ∎

##  3 Number fields and minimal polynomials

In this section we present basic facts concerning minimal polynomials. Using
the companion matrix formalism we explain the relationship between the minimal
polynomials of two algebraic numbers and the minimal polynomial of their sum
and product.

Recall that $\alpha\in\mathbb{C}$ is an _algebraic number_ if it is a root of
a polynomial $p\in\mathbb{Q}[x]$, i.e. a polynomial with rational
coefficients. The order of $\alpha$ is the order of the monic polynomial
$m_{\alpha}\in\mathbb{Q}[x]$ of the least degree, having $\alpha$ as a root.
In other words $m_{\alpha}$ is irreducible over $\mathbb{Q}$, i.e. it cannot
be decomposed into a product of polynomials from $\mathbb{Q}[x]$. This monic
polynomial is called the minimal polynomial of $\alpha$ and is uniquely
determined by $\alpha$. If $\alpha$ is not algebraic then it is called
_transcendental_. Algebraic numbers form an infinite countable set,
$\mathbb{A}$ [3], whereas the set $\mathbb{T}$ of transcendental numbers is
uncountable and we have $\mathbb{A}\cup\mathbb{T}=\mathbb{C}$. The examples of
algebraic numbers are all integers, rational numbers or the numbers of the
form: $\sqrt[k]{n}$, $\cos\frac{2k\pi}{n}$, $e^{2ik\pi/n}$,
$\sin\frac{2k\pi}{n}$, where $n,k\in\mathbb{N}$. On the other hand the numbers
$\pi,e$ are known to be transcendental. Obviously if
$a\in\mathbb{A}\backslash\\{0\\}$ and $t\in\mathbb{T}$, then also $a^{-1},-a$
are algebraic numbers and $t^{-1},-t$ are transcendental numbers.

Having defined algebraic and transcendental numbers, we introduce the notion
of a field extension. Let $\mathbb{L}$ be a field that contains $\mathbb{Q}$
as a subfield and let $S$ be a subset of $\mathbb{L}$. We define the field
$\mathbb{Q}(S)$ to be the smallest field that contain both $\mathbb{Q}$ and
$S$. We will call $\mathbb{Q}(S)$ a field extension of $\mathbb{Q}$ obtained
by adjoining elements of $S$. If all elements in $\mathbb{Q}(S)$ are algebraic
numbers then the field $\mathbb{Q}(S)$ is called an algebraic field extension.
One can view $\mathbb{Q}(S)$ as a vector space over $\mathbb{Q}$. The
dimension of this space, denoted by $[\mathbb{Q}(S):\mathbb{Q}]$, will be
called a degree of $\mathbb{Q}(S)$ over $\mathbb{Q}$. If
$[\mathbb{Q}(S):\mathbb{Q}]<\infty$ the extension is the finite extension.
Finite extensions are algebraic as for any $\alpha\in\mathbb{Q}(S)$ numbers
$1,\alpha,\alpha^{2},\ldots,\alpha^{[\mathbb{Q}(S):\mathbb{Q}]}$ are linearly
dependent over $\mathbb{Q}$ which means there is a polynomial
$p\in\mathbb{Q}[x]$ which satisfies $p(\alpha)=0$. The converse is not true.

In this paper we will deal with extensions $Q(S)$, where $S=\\{\alpha\\}$ and
$\alpha$ is an algebraic number of order $n$ whose minimal polynomial is
$m_{\alpha}\in\mathbb{Q}[x]$. For convenience the field $\mathbb{Q}(S)$ will
be denoted by $\mathbb{Q}(\alpha)$. Among elements belonging to
$\mathbb{Q}(\alpha)$ are all polynomial expressions in $\alpha$. It turns out
that these expressions already form a field which contains $\alpha$ and
$\mathbb{Q}$ and therefore they constitute $\mathbb{Q}(\alpha)$. We note that
for all $p\in\mathbb{Q}[x]$ satisfying $p(\alpha)=0$ the corresponding
expression is $0$. Thus $\mathbb{Q}(\alpha)$ is isomorphic
$\mathbb{Q}[x]/(m_{\alpha})$, where $(m_{\alpha})$ is an ideal of polynomials
vanishing on $\alpha$. Using the polynomial division formula, any element
$\beta\in\mathbb{Q}(\alpha)$ can be written as
$\beta=m_{\alpha}(\alpha)f(\alpha)+r(\alpha)$, where
$\mathrm{deg}\;r<\mathrm{deg}\;m_{\alpha}=n$. Thus any element of $Q(\alpha)$
is a polynomial in $\alpha$ of degree less than $n$ with coefficients in
$\mathbb{Q}$. Therefore $Q(\alpha)$ is a finite extension whose basis is
$\\{1,\alpha,\ldots,\alpha^{n-1}\\}$ and $[\mathbb{Q}(\alpha):\mathbb{Q}]=n$.
Hence any element $\beta\in\mathbb{Q}(\alpha)$ is algebraic and
$\mathbb{Q}(\beta)\subset\mathbb{Q}(\alpha)$. One can show that the order of
$\beta$ is a divisor of the order of $\alpha$, i.e. a divisor of $n$ and is
given by

$\displaystyle\mathrm{deg}\;m_{\beta}=[\mathbb{Q}(\beta):\mathbb{Q}]=[\mathbb{Q}(\alpha):\mathbb{Q}]/[\mathbb{Q}(\alpha):\mathbb{Q}(\beta)],$
(26)

where $m_{\beta}$ is the minimal polynomial for $\beta$.

Consider field extension $Q(e^{i\phi})$ where $\phi$ is a rational multiple of
$\pi$. As $e^{i\phi}$ is a root of unity, $Q(e^{i\phi})$ is a finite algebraic
extension. Next, $\sin\phi$, $\cos\phi$ depend on $e^{i\phi}$ as
$\cos\phi=\frac{e^{i\phi}+e^{-i\phi}}{2}$ and
$\sin\phi=\frac{e^{i\phi}-e^{-i\phi}}{2i}$ and therefore
$\mathbb{Q}(\cos\phi)\subset\mathbb{Q}(e^{i\phi})$ and
$\mathbb{Q}(\sin\phi)\subset\mathbb{Q}(e^{i\phi})$. The minimal polynomials of
these functions are characterised by several unique properties. In this paper
we place particular emphasis on the minimal polynomials $\psi_{n}$ for
$\cos\frac{2\pi}{n}$ and $\eta_{n}$ for $2\cos\frac{\phi}{2}$. Their
properties will be crucial in the proof of theorem 1, therefore we describe
them at length in section 4.

###  3.1 Companion matrix formalism

The notion of a minimal polynomial can be generalized to matrices over
$\mathbb{Q}$. We say that a square matrix $M\in\mathrm{M}_{n}(\mathbb{Q})$ is
a root of a polynomial $p\in\mathbb{Q}[x]$ if $p(M)=0$ (in other words $p$
_annihilates_ $M$). Let $\chi_{M}\in\mathbb{Q}[x]$ be the characteristic
polynomial of $M\in\mathrm{M}_{n}(\mathbb{Q})$. By the Cayley-Hamilton theorem
$M$ is a root of its own characteristic polynomial, i.e. $\chi_{M}(M)=0$. The
monic polynomial $m_{M}\in\mathbb{Q}[x]$ of the smallest degree that is
irreducible over $\mathbb{Q}$ and annihilates $M$ will be called the _minimal
polynomial_ of $M$. Conversely, to every minimal polynomial
$m_{\alpha}\in\mathbb{Q}[x]$ we can associate the matrix called a _companion
matrix_ $M_{\alpha}$, defined as follows:

######  Definition 3.

Let $m_{\alpha}$ be a minimal polynomial of $\alpha$ of degree
$\deg\;m_{\alpha}=d$ given by $m_{\alpha}(x)=x^{d}+\sum_{k=0}^{d-1}c_{k}\cdot
x^{k}$. The _companion matrix_ $M_{\alpha}$ is the $n\times n$ matrix over
$\mathbb{Q}$ defined as

$\displaystyle
M_{\alpha}=\left(\begin{array}[]{cccccc}0&0&0&\ldots&0&-c_{0}\\\
1&0&0&\ldots&0&-c_{1}\\\ 0&1&0&\ldots&0&-c_{2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\ldots&1&0&-c_{d-2}\\\
0&0&0&\ldots&1&-c_{d-1}\end{array}\right).$ (33)

One can show (see [1]) that

$\displaystyle\chi_{M_{\alpha}}=m_{M_{\alpha}}=m_{\alpha}.$ (34)

Assume $\alpha,\beta\in\mathbb{A}$ and their minimal polynomials are
$m_{\alpha}$ and $m_{\beta}$ respectively. Companion matrix formalism allows
us to find polynomials that annihilate $\alpha\beta$ and $\alpha+\beta$
knowing polynomials $m_{\alpha}$ and $m_{\beta}$. To this end we construct
matrices

$\displaystyle M_{\alpha\beta}=M_{\alpha}\otimes M_{\beta},\quad
M_{\alpha+\beta}=M_{\alpha}\otimes I_{\beta}+I_{\alpha}\otimes M_{\beta}.$
(35)

The characteristic polynomials of these matrices annihilate $\alpha\beta$ and
$\alpha+\beta$ respectively. We note, however, that $m_{\alpha+\beta}$,
$m_{\alpha\beta}$ may not be equal to characteristic polynomials of
$M_{\alpha+\beta}$ and $M_{\alpha\beta}$ as these matrices are not companion
matrices in the true sense of this word. Nevertheless, the equality holds when
either $\alpha$ or $\beta$ belongs to $\mathbb{Q}$.

######  Fact 4.

Assume that $\alpha\in\mathbb{Q}$ and $\beta\notin\mathbb{Q}$. Then
$[\mathbb{Q}(\alpha+\beta):\mathbb{Q}]=[\mathbb{Q}(\alpha\beta):\mathbb{Q}]=[\mathbb{Q}(\beta):\mathbb{Q}]$
and the minimal polynomials of $\alpha\beta$ and $\alpha+\beta$ are given by
the characteristic polynomials of

$\displaystyle M_{\alpha\beta}=\alpha M_{\beta},\quad M_{\alpha+\beta}=\alpha
I_{\beta}+M_{\beta},$ (36)

where $M_{\alpha}$ and $M_{\beta}$ are the companion matrices of $\alpha$ and
$\beta$.

###### ?proofname?.

Note that $m_{\alpha}$ is the first order polynomial $m_{\alpha}(x)=x-\alpha$.
Thus $M_{\alpha}$ is a $1\times 1$ matrix $M_{\alpha}=\alpha$. Using the
companion matrix formalism we know that the characteristic polynomials of the
matrices (36) annihilate $\alpha\beta$ and $\alpha+\beta$ respectively. We
also know that
$\mathbb{Q}(\beta)=\mathbb{Q}(\alpha+\beta)=\mathbb{Q}(\alpha\beta)$. Using
formula (26) we get that
$\mathrm{deg}\;m_{\alpha+\beta}=\mathrm{deg}\;m_{\alpha\beta}=[\mathbb{Q}(\beta):\mathbb{Q}]=\mathrm{deg}({m_{\beta}})$.
But the degrees of $\chi_{M_{\alpha\beta}}$ and $\chi_{M_{\alpha+\beta}}$ are
also $\mathrm{deg}\;m_{\beta}$. The result follows. ∎

In general the degrees for $\alpha,\beta\in\mathbb{A}$ are bounded by

$\max(\deg m_{\alpha},\deg m_{\beta})\leq\deg
m_{\alpha+\beta,\alpha\beta}\leq\deg m_{\alpha}\deg m_{\beta}.$

The lower bound corresponds to the case when one of the field extensions
$\mathbb{Q}(\alpha),\;\mathbb{Q}(\beta)$ is a subfield of the second one, e.g.
$\mathbb{Q}(\alpha)\subset\mathbb{Q}(\beta)$. Then both $\alpha+\beta$ and
$\alpha\beta$ belong to the larger field extension. In that case the degrees
of the minimal polynomials of $m_{\alpha+\beta}$ and $m_{\alpha\beta}$ are
equal to the degree of $\mathbb{Q}(\beta)$ by definition. The other case is
when $\mathbb{Q}(\alpha)$ and $\mathbb{Q}(\beta)$ have no common elements
different than rational numbers. Then $\mathbb{Q}(\alpha\beta)$ and
$Q(\alpha+\beta)$ are the field extensions of the degree at most
$[\mathbb{Q}(\alpha):\mathbb{Q}]\cdot[\mathbb{Q}(\beta):\mathbb{Q}]$. In order
to check it, let $\\{1,\alpha,\ldots,\alpha^{m}\\}$ be a basis of
$\mathbb{Q}(\alpha)$ and $\\{1,\beta,\ldots,\beta^{n}\\}$ be a basis of
$\mathbb{Q}(\beta)$ such that $\alpha^{i}\neq\beta^{j}$ for all $1\leq i\leq
m$, $1\leq j\leq n$. Then the basis of $\mathbb{Q}(\alpha\beta)$ consists of
all $\alpha^{i}\beta^{j}$’s and the maximal number of such _different_ basis
elements is
$[\mathbb{Q}(\alpha):\mathbb{Q}]\cdot[\mathbb{Q}(\beta):\mathbb{Q}]$. The same
holds for $\mathbb{Q}(\alpha+\beta)$. Thus typically we need to find
$\chi_{M_{\alpha\beta}}$ or $\chi_{M_{\alpha+\beta}}$ and factorize it over
$\mathbb{Q}$ obtaining
$\chi_{M_{\alpha+\beta,\alpha\beta}}=m_{\alpha+\beta,\alpha\beta}\cdot
p_{1}\cdot\ldots\cdot p_{k}$.

Polynomials with integer coefficients are characterised by special properties.
Particularly important are the _primitive_ polynomials for which the greatest
common divisor of their coefficients is equal to one. The set of primitive
polynomials is closed under multiplication in $\mathbb{Z}[x]$, in other words:

######  Fact 5.

[11] Let $f,g\in\mathbb{Z}[x]$ be primitive polynomials. Then the product
$f\cdot g$ is also a primitive polynomial.

Every polynomial with rational coefficients $f\in\mathbb{Q}[x]$ can be
associated with a primitive polynomial $\tilde{f}$ such, that

$\displaystyle f(x)=\alpha\tilde{f},\>\alpha\in\mathbb{Q},$ (37)

and the pair $(\tilde{f},\alpha)$ is unique. This fact allows us to formulate
the following theorem that we prove for the reader’s convenience.

######  Lemma 6 (Gauss lemma).

[11] Let $f$ be a polynomial with integer coefficients. $f$ is reducible over
$\mathbb{Q}$ if and only if it is reducible over $\mathbb{Z}$.

###### ?proofname?.

The first part of the proof is trivial since $\mathbb{Z}\subset\mathbb{Q}$.
Thus it is enough to prove that reducibility over $\mathbb{Q}$ implies
reducibility over $\mathbb{Z}$.

Let $f\in\mathbb{Z}[x]$ be a primitive polynomial, reducible over $\mathbb{Q}$
(if not, there is always a pair $(\tilde{f},\alpha)$ such, that $\tilde{f}$ is
primitive and $\alpha\in\mathbb{Z}$). Assume that $f$ decomposes as $f=g\cdot
h$, where $g,h\in\mathbb{Q}[x]$. By the identity (37) these polynomials can be
expressed as $g=\gamma\tilde{g}$, $h=\chi\tilde{h}$, where
$\gamma,\chi\in\mathbb{Q}$ and $\tilde{g},\tilde{h}$ are primitive
polynomials. Therefore we have $f=g\cdot h=\gamma\chi\tilde{g}\tilde{h}$,
where $\tilde{g}\cdot\tilde{h}$ is a primitive polynomial.

Let us substitute $\gamma\chi=\frac{p}{q}$ for some $p,q\in\mathbb{Z}$,
$\gcd(p,q)=1$. Hence

$\displaystyle qf=p\tilde{g}\cdot\tilde{h}.$ (38)

Since $f$ and $\tilde{g}\cdot\tilde{h}$ are primitive, the greatest common
divisor of the coefficients of the left and right hand side of (38) are equal
$q$ and $p$ respectively. Thus $p=q$, which implies $\gamma\chi=1$ and
$f=\tilde{g}\cdot\tilde{h}$ and $f=\tilde{g}\tilde{h}\in\mathbb{Z}[x]$. This
completes the proof. ∎

##  4 Trigonometric minimal polynomials

By trigonometric polynomials we will understand the minimal polynomials for
$\cos\phi,\sin\phi,2\cos\frac{\phi}{2},\tan\phi$, where $\phi$ is a rational
multiple of $\pi$. A detailed description of their properties was given in
e.g. [5, 22, 24, 25]. In this paper we will concentrate on minimal polynomials
for $\cos\phi$ and $2\cos\frac{\phi}{2}$, that are closely related to
Chebyshev polynomials of the first kind.

######  Definition 7.

Chebyshev polynomials of the first kind $T_{k}(x)$, $k=0,1,\ldots$ are defined
by the recurrence formula

$\displaystyle T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x),\>T_{0}(x)=1,\;T_{1}(x)=x.$
(39)

Equivalently, $T_{k}(x)$’s are the polynomials satisfying

$\displaystyle T_{k}(\cos\phi)=\cos k\phi.$ (40)

From the formula (39) one can deduce properties of the coefficients of
Chebyshev polynomials.

######  Fact 8.

Let $T_{k}(x)=\sum_{i=0}^{k}c_{i}x^{i}$ be the Chebyshev polynomial of the
first kind of the degree $k$. The coefficients $c_{0},\ldots,c_{k}$ satisfy:

  1. 1.

$c_{0},\ldots,c_{k}$ are integer numbers.

  2. 2.

The leading coefficient $c_{k}$ is equal to $2^{k-1}$.

  3. 3.

$T_{k}(x)$ is a polynomial of only odd/even powers of $x$ if $k$ is an
odd/even number respectively.

  4. 4.

If $k$ is even, then the free term $c_{0}$ is given by $c_{0}=\pm 1$.

  5. 5.

If $k$ is odd, then the coefficients $c_{0},c_{1}$ are equal $c_{0}=0$,
$c_{1}=\pm k$.

Assume that $\phi$ is a rational multiple of $\pi$. In this case one can
express the minimal polynomial of $\cos\phi$ using the Chebyshev polynomials
and vice versa. The explicit expressions are given in the following:

######  Fact 9.

[22, 24] A minimal polynomial $\psi_{n}(x)$ of $\cos\frac{2\pi}{n}$ is a
polynomial defined as

$\displaystyle\psi_{1}(x)=x-\cos 2\pi=x-1,\quad\psi_{2}=x-\cos\pi=x+1,$ (41)
$\displaystyle\psi_{n}(x)=\prod_{\small\begin{array}[]{c}1\leq k\leq\lfloor
n/2\rfloor\\\
\gcd(k,n)=1\end{array}}\left(x-\cos\frac{2k\pi}{n}\right),\;n\geq 3,$ (44)
$\displaystyle\deg\psi_{n}(x)=\left\\{\begin{array}[]{cc}1&n=1,2\\\
\frac{\varphi(n)}{2}&n\geq 3\end{array}\right.,$ (47)

where $\varphi(n)$ is the _Euler totient function_ counting the positive
integers $k\leq n$ that are coprime to $n$. The canonical identity relating
$\psi_{n}(x)$ with Chebyshev polynomials of the first kind is of the form

$\displaystyle 2^{k}\prod_{d|n}\psi_{d}(x)=T_{k+1}(x)-T_{k}(x),\>\>n=2k+1,$
(48) $\displaystyle
2^{k}\prod_{d|n}\psi_{d}(x)=T_{k+1}(x)-T_{k-1}(x),\>\>n=2k.$ (49)

######  Remark 10.

Note that the sum in (44) is over $1\leq k\leq\lfloor n/2\rfloor$,
$\gcd(k,n)=1$ instead of $1\leq k\leq n$. It stems from the symmetry of
cosine, i.e. $\cos\phi=\cos(-\phi)$. Note that for every
$\phi=\frac{2k\pi}{n}$ the opposite angle is defined as
$-\phi=-\frac{2k\pi}{n}=\frac{2(n-k)\pi}{n}$. By properties of the greatest
common divisor [13], $\gcd(k,n)=1$ implies $\gcd(n-k,n)=1$. Thus every root
$\cos\frac{2k\pi}{n}$, where $1\leq k\leq\lfloor n/2\rfloor$, is equal to the
root $\cos\frac{2(n-k)\pi}{n}$ where $\lfloor n/2\rfloor<n-k<n$. Therefore
$\cos\frac{2k\pi}{n}$ for $1\leq k\leq\lfloor n/2\rfloor$ are all the possible
roots of $\psi_{n}(x)$.

Before we formulate the lemma describing a important property of $\psi_{n}(x)$
we will present definition of the Möbius function that allows us to invert
(49) and (48) and express $\psi_{n}(x)$ as a function of Chebyshev polynomials
[5].

######  Definition 11.

Möbius function is an integer function taking three possible values
$\mu(n)=\\{-1,0,1\\}$. It depends on the prime factorisation of $k$ (this
means a unique representation of $n$ as a product of prime numbers). Let
$n=p_{1}^{n_{1}}\ldots p_{m}^{n_{m}}$, then (1) $\mu(n)=0$ if at least one
$n_{i}$ is larger than one, (2) $\mu(n)=-1$ if $m$ is an odd number and
$n_{1}=\ldots=n_{m}=1$ (we say that $n$ is _square free_), (3) $\mu(n)=1$ if
$m$ is even and $n$ is square free.
The Möbius function satisfies the canonical identity [13]

$\displaystyle\sum_{d|n}\mu(d)=\left\\{\begin{array}[]{cc}0,&n>1\\\
1,&n=1\end{array}\right..$ (52)

######  Fact 12.

[5] For $n\geq 3$, odd and $m\geq 1$, $m,n\in\mathbb{N}$ the Möbius inverses
of (48) and (49), given by the Möbius inversion formula, are the following

$\displaystyle\psi_{n}(x)=\prod_{d|n}\left[2^{-\lfloor
d/2\rfloor}\left(T_{\lfloor d/2\rfloor+1}(x)-T_{\lfloor
d/2\rfloor}(x\right)\right]^{\mu(n/d)},$ (53)
$\displaystyle\psi_{2^{m}n}(x)=\prod_{d|n}\left[\frac{2^{-\lfloor
2^{m-1}d\rfloor}\left(T_{\lfloor 2^{m-1}d\rfloor+1}(x)-T_{\lfloor
2^{m-1}d\rfloor-1}(x\right)}{2^{-\lfloor 2^{m-2}d\rfloor}\left(T_{\lfloor
2^{m-2}d\rfloor+1}(x)-T_{\lfloor
2^{m-2}d\rfloor-1}(x\right)}\right]^{\mu(n/d)},\quad m>1,$ (54)
$\displaystyle\psi_{2^{m}n}(x)=\prod_{d|n}\left[\frac{2^{-d}\left(T_{\lfloor
d\rfloor+1}(x)-T_{\lfloor d\rfloor-1}(x)\right)}{2^{-\lfloor
d/2\rfloor}\left(T_{\lfloor d/2\rfloor+1}(x)-T_{\lfloor
d/2\rfloor}(x)\right)}\right]^{\mu(n/d)},\quad m=1.$ (55)

The following property of $\psi_{n}(x)$ is crucial in proving theorem 1.

######  Lemma 13.

At least one coefficient of $\psi_{n}(x)$ is non-integer if
$n\notin\\{1,2,4\\}$.

###### ?proofname?.

Note that $\cos\frac{2k\pi}{n}$, $\gcd(k,n)=1$ are integers for
$n\in\\{1,2,4\\}$, thus the corresponding minimal polynomials $\psi_{n}(x)$
belong to $\mathbb{Z}[x]$. In other cases one can distinguish the following
situations: 1) $n$ is an odd prime number, 2) $n$ is an odd composite number,
3) $n$ is an even composite number.

  1. 1.

In the case 1) $n$ has exactly two divisors and the formula (48) simplifies to

$\displaystyle\psi_{1}(x)\psi_{n}(x)=(x-1)\psi_{n}(x)=2^{-\lfloor
n/2\rfloor}\left(T_{\lfloor n/2\rfloor+1}(x)-T_{\lfloor
n/2\rfloor}(x)\right).$ (56)

Note that $T_{\lfloor n/2\rfloor+1}(x)-T_{\lfloor n/2\rfloor}(x)$ is a
difference of polynomials of the even and the odd degrees, therefore by fact 8
it has a free term equal $\pm 1$ hence the free term of the right hand side is
$\pm\frac{1}{2^{\lfloor n/2\rfloor}}$. Note that the free term of left hand
side is determined by the free term of $\psi_{n}(x)$. Comparing the left and
right side of (56) one can see that the free term of $\psi_{n}(x)$, i.e.
$c_{0}=\pm\frac{1}{2^{\lfloor n/2\rfloor}}$, must be a rational number since
we consider $n\leq 3$.

  2. 2.

In the case 2) we will prove that $\psi_{n}(x)$ has a non-integer free term by
applying formula (53) and using properties of the Möbius function. Let
$n=p_{1}^{n_{1}}\ldots p_{m}^{n_{m}}$ be the prime factorisation of $n$. Let
$\mathcal{D}_{n}^{+}$ and $\mathcal{D}_{n}^{-}$ be the sets of all square free
(as in definition 11) divisors of $n$ that have even and odd number of prime
divisors respectively. By (52) we have
$|\mathcal{D}_{n}^{+}|=|\mathcal{D}_{n}^{-}|$. Note that the free term of the
right hand side of (53) can be written in the form

$\displaystyle c_{0}=\pm\prod_{d|n}\left(\frac{1}{2^{\lfloor
d/2\rfloor}}\right)^{\mu(n/d)}=\pm\prod_{\frac{n}{d}\in\mathcal{D}_{n}^{+}\cup\mathcal{D}_{n}^{-}}\left(\frac{1}{2^{\lfloor
d/2\rfloor}}\right)^{\mu(n/d)}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}\lfloor
d/2\rfloor}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}\lfloor d/2\rfloor}}.$
(57)

We next raise $c_{0}$ to the power $p=2p_{1}\cdot\ldots\cdot p_{m}$

$\displaystyle
c_{0}^{p}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}p\lfloor
d/2\rfloor}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}p\lfloor
d/2\rfloor}}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}p(d-1)/2}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}p(d-1)/2}}=\frac{2^{-\frac{pk}{2}+\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}\frac{pd}{2}}}{2^{-\frac{pk}{2}+\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}\frac{pd}{2}}}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}\frac{pd}{2}}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}\frac{pd}{2}}}.$
(58)

Note that $c_{0}$ is non-integer if and only if $c_{0}^{p}<1$. In order to
find the appropriate condition we use the fact that if $x=\frac{n}{d}$ belongs
to $\mathcal{D}_{n}^{-}$ or $\mathcal{D}_{n}^{+}$ then

$\displaystyle p\cdot d=p\frac{n}{x}=2n\cdot y,$ (59)

where $y$ is the square-free product of such prime divisors of $n$ that do not
appear in prime factorisation of $x$. In particular, if $m$ is an even number
and $x\in\mathcal{D}_{n}^{+}$, then $y$ must also belong to
$\mathcal{D}_{n}^{+}$. Similarly $x\in\mathcal{D}_{n}^{-}$ implies that
$y\in\mathcal{D}_{n}^{-}$. When $m$ is odd one easily checks that
$x\in\mathcal{D}_{n}^{+}$ implies that $y\in\mathcal{D}_{n}^{-}$ and vice
versa.

Let us consider the case when $m$ is an even number. Taking $pd=2ny$ one can
rewrite (58) as

$\displaystyle
c_{0}^{p}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}\frac{pd}{2}}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}\frac{pd}{2}}}=\frac{2^{\sum_{y\in\mathcal{D}_{n}^{-}}ny}}{2^{\sum_{y\in\mathcal{D}_{n}^{+}}ny}}=\frac{2^{n\sum_{y\in\mathcal{D}_{n}^{-}}y}}{2^{n\sum_{y\in\mathcal{D}_{n}^{+}}y}}.$
(60)

As one can easily see $c_{0}^{p}<1$ if the following holds

$\displaystyle\sum_{y\in\mathcal{D}_{n}^{+}}y-\sum_{y\in\mathcal{D}_{n}^{-}}y>0.$
(61)

Note that this expression is equivalent to the product

$\displaystyle\sum_{y\in\mathcal{D}_{n}^{+}}y-\sum_{y\in\mathcal{D}_{n}^{-}}y=(1-p_{1})\ldots(1-p_{m}),$
(62)

which is always larger than zero if $m$ is even, thus $c_{0}$ is non-integer
in this case.

Next let us consider $n$ such, that $m$ is an odd number. Doing mutatis
mutandis to the case when $m$ is even one can transform (58) to the form

$\displaystyle
c_{0}^{p}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}pd}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}pd}}=\frac{2^{\sum_{y\in\mathcal{D}_{n}^{+}}ny}}{2^{\sum_{y\in\mathcal{D}_{n}^{-}}ny}}=\frac{2^{n\sum_{y\in\mathcal{D}_{n}^{+}}y}}{2^{n\sum_{y\in\mathcal{D}_{n}^{-}}y}},$
(63)

thus the condition for $c_{0}^{p}<1$ is given by

$\displaystyle\sum_{y\in\mathcal{D}_{n}^{+}}y-\sum_{y\in\mathcal{D}_{n}^{-}}y=(1-p_{1})\ldots(1-p_{m})<0.$
(64)

Note that this is always satisfied if $m$ is odd, which means that $c_{0}^{p}$
is indeed smaller than one. This way we have proven lemma 13 for the case when
$n>1$ and $n$ is odd.

  3. 3.

In case 3) we will use the similar approach as for case 2). Recall that every
even number $n$ can be represented as $n=2^{\eta}k$, where $k$ \- odd and
$\eta\in\mathbb{Z}_{+}$. This allows us to define $\psi_{n}(x)$ by the formula
(54). Let us define the sets $\mathcal{D}_{n}^{+}$ and $\mathcal{D}_{n}^{-}$
like previously. Using fact 8 one can extract the free terms from (54) and
(55) as

$\displaystyle
c_{0}=\prod_{d|k}\left(\frac{2}{2^{2^{\eta-2}d}}\right)^{\mu(k/d)}=\frac{2^{2^{\eta-2}\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}d}}{2^{2^{\eta-2}\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}d}},\quad\eta>1,$
(65) $\displaystyle c_{0}=\prod_{d|k}\left(\frac{1}{2^{\lfloor
d/2\rfloor}}\right)^{\mu(k/d)}=\frac{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{-}}\lfloor
d/2\rfloor}}{2^{\sum_{\frac{n}{d}\in\mathcal{D}_{n}^{+}}\lfloor
d/2\rfloor}},\quad\eta=1.$ (66)

By properties of the Möbius function all the sums and products are over the
same number of divisors. Note that (66) and (57) are exactly equal, whereas
(65) has a very similar form to (57). Using very similar reasoning as in the
case 2) we obtain immediately that $c_{0}$ is non-integer unless $n=2,4$,
which completes the proof.

∎

#### Example:

In this paragraph we will illustrate the method presented in the proof of
lemma 13 with the example for $n=15$. First, $\mathcal{D}^{+}_{n}=\\{1,15\\}$
and $\mathcal{D}^{-}_{n}=\\{3,5\\}$. The coefficient $c_{0}$ of $\psi_{15}(x)$
is given by

$\displaystyle c_{0}=\frac{2^{\lfloor 5/2\rfloor+\lfloor
3/2\rfloor}}{2^{\lfloor 15/2\rfloor+\lfloor 1/2\rfloor}}.$ (67)

Using the reasoning presented for the case 2) we raise $c_{0}$ to the power
$p=30$ and obtain the condition

$\displaystyle
c_{0}^{30}=\frac{2^{15(5+3)-15}}{2^{15(15+1)-15}}=\frac{2^{15\sum_{y\in\mathcal{D}_{15}^{-}}y}}{2^{15\sum_{y\in\mathcal{D}_{15}^{+}}y}}<1\Leftrightarrow\sum_{y\in\mathcal{D}_{15}^{+}}y-\sum_{y\in\mathcal{D}_{15}^{-}}y=16-8>0.$

Thus we have shown that $c_{0}<1$. On the other hand one can see immediately
from definition (67) than $c_{0}$ for $\psi_{15}(x)$ is equal to
$2^{-8}\notin\mathbb{Z}$.

The proof of theorem 1 presented in this paper is based also on properties of
minimal polynomials for $2\cos\frac{\pi}{n}$. However, before we describe
them, we will recall the notion of cyclotomic polynomials. Since
$2\cos\frac{k\pi}{n}$ is a sum of two roots of unity $e^{ik\pi/n}$ and
$e^{-ik\pi/n}$ one can conclude that properties of minimal polynomials for
double cosines depend on properties of cyclotomic polynomials.

######  Definition 14.

A cyclotomic polynomial $\Phi_{n}(x)$ is the polynomial with integer
coefficients, irreducible over $\mathbb{Q}$, defined as

$\displaystyle\Phi_{n}(x)=\prod_{\small\begin{array}[]{c}1\leq k\leq n\\\
\gcd(k,n)=1\end{array}}\left(x-e^{2i\pi k/n}\right),$ (70)

and satisfying the identity $1-x^{n}=\prod_{d|n}\Phi_{d}(x)$. $\Phi_{n}(x)$ is
the minimal polynomial of an $n$-th root of identity.

The basic facts concerning minimal polynomials for double cosines are the
following:

######  Lemma 15.

[5, 25] The minimal polynomial for $2\cos\frac{\pi}{n}$ is a polynomial
defined as

$\displaystyle\eta_{n}(x)=2^{\deg\psi_{2n}(x)}\psi_{2n}\left(\frac{x}{2}\right).$
(71)

Using fact 9 one can write it explicitly as:

$\displaystyle\eta_{1}(x)=x+2,$ (72)
$\displaystyle\eta_{n}(x)=\prod_{\small\begin{array}[]{c}1\leq k\leq n\\\
\gcd(k,2n)=1\end{array}}\left(x-2\cos\frac{k\pi}{n}\right),\>n\leq 2$ (75)

###### ?proofname?.

Note that for arbitrary $1\leq k\leq n$, s.t. $\gcd(k,2n)=1$,
$\cos\frac{k\pi}{n}$ is a root of the polynomial $\psi_{2n}(x)$ of a degree
$d=\deg\psi_{2n}(x)=\frac{\varphi(2n)}{2}$ with the coefficients
$c_{0},\ldots,c_{d-1},c_{d}$. Since $2\cos\frac{\pi}{n}$ is a product of $2$
and a root of $\cos\frac{k\pi}{n}$, the companion matrix
$M_{2\cos\frac{k\pi}{n}}$ is given by $M_{2\cos\frac{k\pi}{n}}=2\cdot
M_{\cos\frac{k\pi}{n}}$ (35) and by fact 4 the minimal polynomial
$\eta_{n}(x)$ is equal to the characteristic polynomial
$\chi_{M_{2\cos\frac{k\pi}{n}}}$. Let us write this matrix explicitly. The
polynomial $\eta_{n}(x)$ is given by

$\displaystyle\eta_{n}(x)=\chi_{M_{2\cos\frac{k\pi}{n}}}=\det\left(\begin{array}[]{cccc}-x&0&\ldots&-2c_{0}\\\
2&-x&\ldots&-2c_{1}\\\ 0&2&\ldots&-2c_{2}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&\ldots&2&-2c_{d-1}-x\end{array}\right).$ (81)

The substitution $x\to 2y$ transforms (81) to the form
$\eta_{n}(2y)=\chi_{2M_{\cos\frac{k\pi}{n}}}$. Since $M_{\cos\frac{k\pi}{n}}$
is a $d\times d$ matrix we arrive at

$\displaystyle\eta_{n}(2y)=\det
2(M_{\cos\frac{k\pi}{n}}-yI)=2^{d}\psi_{2n}(y)=2^{d}\psi_{2n}\left(\frac{x}{2}\right),$
(82)

which is exactly (71). The proof is complete ∎

Another property of $\eta_{n}(x)$ that is crucial for the proof of theorem 1
is proven in the following.

######  Lemma 16.

All the coefficients of $\eta_{n}(x)$ are integers.

###### ?proofname?.

In order to prove this fact we use lemma 6 and properties of cyclotomic
polynomials. First, note that
$2\cos\frac{k\pi}{n}=2\cos\frac{2k\pi}{2n},\;\gcd(k,2n)=1$ can be written as a
sum $e^{ik\pi/n}+e^{-ik\pi/n}$, where both $e^{ik\pi/n}$ and $e^{-ik\pi/n}$
are roots of the cyclotomic polynomial $\Psi_{2n}(x)$, whose companion matrix
will be denoted by $M_{\Psi_{2n}(x)}$. Since $\Psi_{2n}(x)$ is a polynomial
with integer coefficients, $M_{\Psi_{2n}(x)}$ has only integer entries.

Recall that using (35) $2\cos\frac{\pi}{n}$ is a root of the characteristic
polynomial of the matrix defined as

$\displaystyle M=M_{\Psi_{2n}(x)}\otimes I+I\otimes M_{\Psi_{2n}(x)},$ (83)

and $\chi{{}_{M}}$ belongs obviously to $\mathbb{Z}[x]$. The degree of the
minimal polynomial of $2\cos\frac{\pi}{n}$ is smaller than the degree of
$\chi_{M_{2\cos\frac{\pi}{n}}}$ as
$\mathbb{Q}(2\cos\frac{k\pi}{n})\subset\mathbb{Q}(e^{ik\pi/n})$. This means,
the characteristic polynomial of $M$ can be factorized as a product of at
least two polynomials

$\chi_{M}=\eta_{n}(x)\cdot
p(x),\>\>\mathrm{where\>in\>general}\>\>p(x),\eta_{n}(x)\in\mathbb{Q}[x].$

Since $\chi_{M}$ belongs to $\mathbb{Z}[x]$, by lemma 6 the polynomials
$\eta_{n}(x)$ and $p(x)$ have integer coefficients. As $\chi_{M}$ is monic,
$p(x)$ and $\eta_{n}(x)$ are also monic and the result follows. ∎

##  5 The proof of theorem 1

The aim of this section is to decide, using the tools presented in previous
sections, for which $\phi=\frac{2k\pi}{n}$ the left hand side of the equation

$\displaystyle 2\cos\frac{\gamma}{2}=\cos\phi+1,$ (84)

is a root of the minimal polynomial $\eta_{m}(x)$ for some $m\in\mathbb{N}$.

The minimal polynomial $m_{\cos\phi+1}(x)$ can be found using the companion
matrix formalism explained in section 3.1. It follows that $\cos\phi+1$ is a
root of the characteristic polynomial of the matrix
$M_{\cos\phi+1}=M_{\cos\phi}+I$, where

$\displaystyle M_{\cos\phi}=\left(\begin{array}[]{cccc}0&0&\ldots&-c_{0}\\\
1&0&\ldots&-c_{1}\\\ 0&1&\ldots&-c_{2}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&\ldots&0&-c_{d-1}\end{array}\right),$

Note that the field extensions
$\mathbb{Q}({2\cos\frac{\gamma}{2}})=\mathbb{Q}(\cos\phi+1)$ and
$\mathbb{Q}(\cos\phi)$ are of the same algebraic degree (see fact 4),
therefore the characteristic polynomial of $M_{\cos\phi+1}$ is exactly the
minimal polynomial $m_{2\cos\frac{\gamma}{2}}(x)$. One can compute
$\chi_{M_{\cos\phi+1}}$ as the determinant of the following matrix:

$\displaystyle
M_{\cos\phi+1}-Ix=\left(\begin{array}[]{cccccc}1-x&0&0&\ldots&0&-c_{0}\\\
1&1-x&0&\ldots&0&-c_{1}\\\ 0&1&1-x&\ldots&0&-c_{2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\ldots&1&1-x&-c_{d-2}\\\
0&0&\ldots&0&1&1-c_{d-1}-x\end{array}\right).$ (91)

Expansion with respect to the first row gives us to the following expression:

$\displaystyle
m_{2\cos\frac{\gamma}{2}}(x)=\chi_{M_{\cos\phi+1}}(x)=\det(M_{\cos\phi+1}-Ix)=\sum_{i=0}^{d}\omega_{i}\cdot
x^{i}=$ (92)
$\displaystyle=-\left[\sum_{i=0}^{d-3}c_{i}(-1)^{d+i+1}(1-x)^{i}\right]+(1-x)^{d-2}[x^{2}+x(c_{d-1}-2)+c_{d-2}-c_{d-1}+1].$
(93)

One can simplify (93) using the binomial formula. As a result we obtain the
following relations between the coefficients of $\psi_{n}(x)$ and
$\chi_{M_{\cos\phi+1}}$:

$\begin{array}[]{c}\omega_{0}=\sum_{i=0}^{d-3}c_{i}(-1)^{d+i}+(c_{d-2}-c_{d-1}+1)(-1)^{d},\\\
\omega_{1}=\sum_{i=1}^{d-3}c_{i}(-1)^{d+1+i}+{d-2\choose
0}(c_{d-1}-2)-{d-2\choose 1}(c_{d-2}-c_{d-1}+1),\\\
\omega_{2}=\sum_{i=2}^{d-3}c_{i}(-1)^{d+i+2}{i\choose 2}+{d-2\choose
0}-{d-2\choose 1}(c_{d-2}+1)+{d-2\choose 2}(c_{d-2}-c_{d-1}+1),\\\ \vdots\\\
\omega_{k}=\sum_{i=k}^{d-3}c_{i}(-1)^{d+i+k}{i\choose k}+{d-2\choose
k}(-1)^{k}(c_{d-2}-c_{d-1}+1)+{i\choose k-1}(-1)^{k-1}(c_{d-1}-2)+{d-2\choose
k-2}(-1)^{k-2}\\\ \vdots\\\
\omega_{d-3}=-c_{d-3}+(c-2)(-1)^{d-3}(c_{d-2}-c_{d-1}+1)+{d-2\choose
d-4}(-1)^{d-4}(c_{d-1}-2)+(-1)^{d-5}{d-2\choose d-5},\\\
\omega_{d-2}=(-1)^{d-2}(c_{d-2}-c_{d-1}+1)+(d-2)(-1)^{d-3}(c_{d-1}-2)+(-1)^{d-4}{d-2\choose
d-4},\\\ \omega_{d-1}=(-1)^{d}(c_{d-1}-2)+(d-2)(-1)^{d-1},\\\
\omega_{d}=(-1)^{d}.\end{array}$ (94)

Recall that by lemma 15 the coefficients of $m_{2\cos\frac{\gamma}{2}}(x)$
must be all integers if $\gamma$ is a rational multiple of $\pi$. One has to
check if this condition is satisfied by all $\omega_{i}$’s starting from
$\omega_{d-1}$. For this coefficient we have:

$(-1)^{d-2}(c_{d-1}-2)+(d-2)(-1)^{d-3}\in\mathbb{N}\Rightarrow
c_{d-1}\in\mathbb{N}.$

Note that $\omega_{d-1}\notin\mathbb{N}$ if and only if
$c_{d-1}\notin\mathbb{N}$. In this case we are done, however there are
polynomials $\psi_{n}(x)$ for which $c_{d-1}\in\mathbb{N}$. In this case we
consider the equation for $\omega_{d-2}$:

$\omega_{d-2}=(-1)^{d-2}(c_{d-2}-c_{d-1}+1)+(d-2)(-1)^{d-3}(c_{d-1}-2)+(-1)^{d-4}{d-2\choose
d-4}\in\mathbb{N}\Rightarrow c_{d-2}\in\mathbb{N}.$

Assuming that $c_{d-1}\in\mathbb{Z}$, the coefficient $\omega_{d-2}$ is non-
integer only if $c_{d-2}\notin\mathbb{Z}$. One can use the same reasoning for
the other $\omega_{i}$’s step by step and notice from (94) that each
$\omega_{i}$ depends on the coefficients $c_{d-1},\ldots,c_{i+1},c_{i}$, where
$c_{i}$ is multiplied by the factor $(-1)^{d+2i}{i\choose i}=\pm 1$. If all of
the coefficients $c_{d-1},\ldots,c_{i+1},c_{i}$ are integers, then also
$\omega_{i}$ belongs to $\mathbb{Z}$. Hence all $\omega_{1},\ldots,\omega_{d}$
are integers if and only if $c_{1},c_{2},\ldots,c_{d-1},c_{d}\in\mathbb{Z}$.
On the other hand we have shown in lemma 13 that $\psi_{n}(x)$ has always at
least one non-integer coefficient if $n\notin\\{1,2,4\\}$. Therefore at least
one $\omega_{i}$ does not belong to $\mathbb{Z}$ and
$m_{2\cos\frac{\gamma}{2}}$ cannot be the minimal polynomial $\eta_{m}(x)$ for
any $m\in\mathbb{Z}$. This means, $\gamma$ must be an irrational multiple of
$\pi$.

Finally we consider what happens in the exceptional cases when
$\phi=\\{\frac{\pi}{2},\pi,\frac{3\pi}{2},2\pi\\}$, i.e. when
$n\in\\{1,2,4\\}$.

  1. 1.

Let $\phi=\pm\frac{\pi}{2}$. The corresponding minimal polynomial and its
companion matrix are of the form $\psi_{4}(x)=x$ and
$M_{\cos\frac{\pi}{2}}=0$. Thus $M_{\cos\phi+1}=1$ and its minimal polynomial
is $m_{M_{\cos\phi+1}}(x)=x-1$. We have that $x-1=\eta_{3}(x),$ thus
$\gamma=\frac{k\pi}{3}$.

  2. 2.

Let $\phi=2\pi$, then $\psi_{1}(x)=x-1$, $M_{\cos 2\pi}=1$. The companion
matrix for $M_{\cos\phi+1}$ is a $1\times 1$ matrix equal to
$M_{\cos\phi+1}=1+1=2$. Thus $m_{M_{\cos\phi+1}}(x)=x-2$. This polynomial
corresponds to $\gamma=2\pi$.

  3. 3.

Assume $\phi=\pi$, then $\psi_{2}(x)=x+1$, $M_{\cos\pi}=-1$ and
$M_{\cos\phi+1}=1-1=0$. Thus the minimal polynomial of
$m_{\cos\phi+1}(x)=x=\eta_{2}(x)$ which is the minimal polynomial of
$2\cos\gamma/2$ for $\gamma=\pi$.

##  6 More examples

Assume now that we have two finite order $SU(2)$-gates. They can be written as
$U(\phi_{1},\vec{k}_{1})$ and $U_{2}(\phi_{2},\vec{k}_{2})$ where

$\displaystyle U(\phi,\vec{k})=\cos\phi
I+\sin\phi\left(k_{x}X+k_{y}Y+k_{z}Z\right),\,\,\vec{k}=[k_{x},k_{y},k_{z}],\,\,k_{x}^{2}+k_{y}^{2}+k_{z}^{2}=1,$
(95)

and both $\phi_{1}$ and $\phi_{2}$ are rational multiples of $\pi$. Their
product is
$U(\gamma,\vec{k}_{\gamma})=U(\phi_{1},\vec{k}_{1})U_{2}(\phi_{2},\vec{k}_{2})$,
where

$\displaystyle\cos\gamma=\cos\phi_{1}\cos\phi_{2}+\sin\phi_{1}\sin\phi_{2}\vec{k}_{1}\cdot\vec{k}_{2}.$
(96)

Under our assumptions $\cos\phi_{1}$, $\cos\phi_{2}$ and $\sin\phi_{1}$,
$\sin\phi_{2}$ are algebraic numbers. It is well known that the sum and the
product of an algebraic number and a transcendental number is transcendental.
Moreover, if $\cos\phi$ is transcendental then $\phi$ is an irrational
multiple of $\pi$. Thus if $\cos\theta=\vec{k}_{1}\cdot\vec{k}_{2}$ is
transcendental then $U(\gamma,\vec{k}_{\gamma})$ is of infinite order. In the
following we show that it can also happen when $\cos\theta$ is an algebraic
number.

###  6.1 Gates $H$ and $T(\phi)$

Let us consider a popular in quantum computation set of unitary gates
$\mathcal{S}=\\{H,T\left(\phi\right)\\}$, where
$H=U(\frac{\pi}{2},\frac{1}{\sqrt{2}}(\vec{k}_{z}+\vec{k}_{y}))$ is the
Hadamard gate, and $T\left(\phi\right)=U(\phi,\vec{k}_{z})$ is a phase gate.
Explicit matrices are given by:

$\displaystyle H=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\
-1&1\end{array}\right),\>T\left(\phi\right)=\left(\begin{array}[]{cc}e^{i\phi}&0\\\
0&e^{-i\phi}\end{array}\right).$ (101)

We look for angles $\phi$ for which the product $HT_{\phi}$ is of infinite
order. An example value of such $\phi$, $\phi=\frac{\pi}{8}$, was given in
[2]. A more general answer can be found using the method presented in previous
sections. The matrices $H$ and $T(\phi)$ represented as rotation matrices from
$SO(3)$ are of the form

$\displaystyle\mathrm{Ad}_{H}=\left(\begin{array}[]{ccc}-1&0&0\\\ 0&0&1\\\
0&1&0\end{array}\right),\>\>\mathrm{Ad}_{T(\phi)}=\left(\begin{array}[]{ccc}\cos
2\phi&\sin 2\phi&0\\\ -\sin 2\phi&\cos 2\phi&0\\\ 0&0&1.\end{array}\right)$
(108)

The product of $\mathrm{Ad}_{H}$ and $\mathrm{Ad}_{T(\phi)}$ is a rotation by
angle $\gamma$ given by

$\displaystyle\mathrm{tr}\mathrm{Ad}_{H}\mathrm{Ad}_{T(\phi)}=\mathrm{tr}O(\gamma,\vec{k}),$
$\displaystyle-\cos 2\phi=2\cos\gamma+1\Rightarrow-2\cos\gamma=\cos 2\phi+1,$

but from trigonometric identities we have that $-\cos\gamma=\cos(\gamma+\pi)$
thus we can write

$\displaystyle 2\cos\gamma^{\prime}=\cos
2\phi+1,\>\>\gamma^{\prime}=\gamma+\pi.$ (109)

Note that equation (109) is of the same form as (84), thus by theorem 2 we can
say immediately that $\mathrm{Ad}_{H}\cdot\mathrm{Ad}_{T(\phi)}$ is of
infinite order if and only if

$\displaystyle 2\phi\neq\\{0,\pi,\pm\frac{\pi}{2}\\}.$ (110)

Hence the gate $HT(\phi)$ is of infinite order if and only if

$\displaystyle\phi\neq\\{0,\pi,\pm\frac{\pi}{2},\frac{\pi}{4},\frac{3\pi}{4}\\}.$
(111)

##  7 Acknowledgment

This work was supported by National Science Centre, Poland under the grant
SONATA BIS: 2015/18/E/ST1/00200.

##  ?refname?

  * [1] S. Axler (2015) _Linear algebra done right_ (Undergraduate Texts in Mathematics, Springer, 2015).
  * [2] P. O. Boykin et. al., _On Universal and Fault-Tolerant Quantum Computing_ , arXiv:quant-ph/9906054 (1999).
  * [3] A. Baker, _Transcendental Number Theory_ (Cambridge University Press, 1975).
  * [4] A. Barenco et al., Elementary gates for quantum computation, Phys. Rev. A 52 (1995), 3457-3467.
  * [5] A. Bayad, I. N. Cangul, _The minimal polynomial of $2\cos(p/q)$ and Dickson polynomials_, Appl. Math. Comp. 218 (2013), 7014-7022.
  * [6] A. Bouland, S. Aronson, _Generation of Universal Linear Optics by Any Beamsplitter_ , Phys. Rev. A 89, 062316 (2014).
  * [7] A. M. Childs et al., Characterization of universal two-qubit Hamiltonians, Quantum Info. Comput. 11 (2011), 19-39.
  * [8] W. Curtis, I. Reiner, _Representation Theory of Finite Groups and Associative Algebras_ (Interscience Publishers, John Wiley and sons, 1962).
  * [9] A. W. Harrow, B. Recht, and I. L. Chuang, Efficient discrete approximations of quantum gates, J. Math. Phys. 43:9 (2002), 4445-4451.
  * [10] M. Nielsen, I. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000).
  * [11] H. M. Edwards, _Galois theory_ (Graduate Texts in Mathematics, Springer, 1998).
  * [12] M. Field, _Generating Sets for compact semisimple Lie Groups_ , Proc. Amer. Math. Soc. 127 (1999), 3361-3365.
  * [13] G. H. Hardy, E. M. Wright, _An introduction to the Theory of Numbers_ (Oxford at the Clarendon Press, 1960).
  * [14] V. Kliuchnikov et. al., _A Framework for Approximating Qubit Unitaries_ , arXiv:1510.03888 (2015).
  * [15] M. Kuranishi, _Two elements generations on semi-simple Lie groups_ , Kodai Math. Sem. Rep. 1 (1949), 5-6.
  * [16] M. Oszmaniec, J. A. Gutt, M. Kuś, Classical simulation of fermionic linear optics augmented with noisy ancillas Phys. Rev. A 90, 020302 (2014).
  * [17] A. Politi et al., Silica-on-Silicon Waveguide Quantum Circuits, Science 320 (2008), 646-649.
  * [18] M. Reck et al., Experimental realization of any discrete unitary operator, Phys. Rev. Lett. 73 (1994), 58-61.
  * [19] A. Sawicki, Universality of beamsplitters, Quantum Info. Comput. 16, 3&4 (2016), 0291-0312.
  * [20] A. Sawicki, K. Karnas, Universality of single qudit gates, arXiv:1609.05780 (2016).
  * [21] A. Sawicki, K. Karnas Criteria for universality of quantum gates, arXiv:1610.00547 (2016).
  * [22] W. Waitkins, J. Zeitlin, _The Minimal Polynomial of $\cos(2\pi/n)$_, The American Mathematical Monthly 100, 5 (1993), 471-474.
  * [23] Z. Zimborás _et al._ , Symmetry criteria for quantum simulability of effective interactions, Phys. Rev. A 92, 042309 (2015).
  * [24] http://oeis.org/A181875.
  * [25] https://oeis.org/A187360.


* Guédon and Vershynin [2016] Olivier Guédon and Roman Vershynin.  Community detection in sparse networks via grothendieck’s inequality.  _Probability Theory and Related Fields_ , 165(3):1025–1049, Aug 2016.  ISSN 1432-2064.  doi: 10.1007/s00440-015-0659-z.
  * Jiang et al. [2020] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song.  A faster interior point method for semidefinite programming.  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 910–918. IEEE, 2020.
  * Krivine [1978] Jean-Louis Krivine.  Constantes de grothendieck et fonctions de type positif sur les spheres.  _Séminaire Analyse fonctionnelle (dit" Maurey-Schwartz")_ , pages 1–17, 1978.
  * Ling [2020] Shuyang Ling.  Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods.  _arXiv preprint arXiv:2008.05341_ , 2020.
  * Makarychev et al. [2016] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan.  Learning communities in the presence of errors.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pages 1258–1291, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * Mathieu and Schudy [2010] Claire Mathieu and Warren Schudy.  Correlation clustering with noisy input.  In _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_ , pages 712–728. SIAM, 2010.
  * McSherry [2001] Frank McSherry.  Spectral partitioning of random graphs.  In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ , pages 529–537. IEEE, 2001.
  * Moitra et al. [2016] Ankur Moitra, William Perry, and Alexander S. Wein.  How robust are reconstruction thresholds for community detection?  In _Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’16, page 828–841, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450341325.
  * Mossel et al. [2014] Elchanan Mossel, Joe Neeman, and Allan Sly.  Consistency thresholds for binary symmetric block models.  _arXiv preprint arXiv:1407.1591_ , 3(5), 2014.
  * Nesterov and Nemirovskii [1990] YE Nesterov and AS Nemirovskii.  Optimization over positive semidefinite matrices: Mathematical background and user’s manual.  _USSR Acad. Sci. Centr. Econ. & Math. Inst_, 32, 1990.
  * Nesterov and Nemirovsky [1988] Yurii Nesterov and A Nemirovsky.  A general approach to polynomial-time algorithms design for convex programming.  _Report, Central Economical and Mathematical Institute, USSR Academy of Sciences, Moscow_ , 1988.
  * Ng et al. [2001] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In _Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic_ , NIPS’01, page 849–856, Cambridge, MA, USA, 2001. MIT Press.
  * Olsson et al. [2007] Carl Olsson, Anders P Eriksson, and Fredrik Kahl.  Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming.  In _2007 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1–8. IEEE, 2007.
  * Peche and Perchet [2020] Sandrine Peche and Vianney Perchet.  Robustness of community detection to random geometric perturbations.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Roughgarden [2020] Tim Roughgarden.  Introduction.  In Tim Roughgarden, editor, _Beyond the Worst-Case Analysis of Algorithms_ , pages 1–24. Cambridge University Press, 2020.  doi: 10.1017/9781108637435.002.
  * Rubinstein and Vardi [2017] Aviad Rubinstein and Shai Vardi.  Sorting from noisier samples.  In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’17, page 960–972, USA, 2017. Society for Industrial and Applied Mathematics.
  * Shi et al. [2020] Yunpeng Shi, Shaohan Li, and Gilad Lerman.  Robust multi-object matching via iterative reweighting of the graph connection laplacian.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Spielman and Teng [2004] Daniel A. Spielman and Shang-Hua Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  _J. ACM_ , 51(3):385–463, May 2004.  ISSN 0004-5411.  doi: 10.1145/990308.990310.
  * Steinhardt [2017] Jacob Steinhardt.  Does robustness imply tractability? A lower bound for planted clique in the semi-random model.  _CoRR_ , abs/1704.05120, 2017.
  * Stephan and Massoulié [2019] Ludovic Stephan and Laurent Massoulié.  Robustness of spectral methods for community detection.  In _Conference on Learning Theory_ , pages 2831–2860. PMLR, 2019\.
  * Tao [2012] Terence Tao.  _Topics in random matrix theory_ , volume 132.  American Mathematical Soc., 2012.
  * Van Gael and Zhu [2007] Jurgen Van Gael and Xiaojin Zhu.  Correlation clustering for crosslingual link detection.  In _IJCAI_ , pages 1744–1749, 2007.
  * Vandenberghe and Boyd [1996] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  _SIAM review_ , 38(1):49–95, 1996.


Version: 02:02

# The average Euler-genus of the vertex-amalgamation of signed graphs

Yichao Chen  School of Mathematics, SuZhou University of Science and
Technology, Suzhou, 215009, China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we first generalize a theorem for counting the number of faces
of an oriented embedding of a graph that passing through a given cut-edge set
[S. Stahl, Trans. Amer. Math. Soc. 259 (1980), 129–145] to all surfaces. Then
we extend Stahl’s bounds for the average genus of the vertex-amalgamation of
graphs [S. Stahl, Discrete Math. 142 (1995), 235–245] to signed graphs.

###### Key words and phrases:

Embedding, Exterior permutation, Interior permutation, Signed graph, Excepted
genus

###### 1991 Mathematics Subject Classification:

Primary: 05C10

##  1\. Introduction

A graph $G$ is often permitted to have both loops and multiple edges in graph
embeddings. Since the genus is a homeomorphic invariant, we suppose the graphs
in the paper are simple. It is well known that all closed surfaces are
classified into the orientable surfaces $O_{i}$, with $i$ handles $(i\geq 0)$,
and the non-orientable surfaces $N_{j}$, with $j$ crosscaps $(j>0)$. We will
use $S$ to denote a surface without regard to orientability. An embedding of
$G$ into a closed surface $S$ is a cellular embedding. If a graph $G$ has an
embedding in a surface $S$ with $n$ vertices, $m$ edges and $r$ faces, the
following classical  Euler’s formula tell us that

$n-m+r=2-\gamma^{E},$

where $\gamma^{E}$ is the Euler-genus of the surface $S$ and

$\gamma^{E}=\left\\{\begin{array}[]{ll}2k,&\hbox{If $S=O_{k}$;}\\\ h,&\hbox{If
$S=N_{h}$.}\end{array}\right.$

A rotation at a vertex $v$ of a graph $G$ is a cyclic ordering of the edge-
ends incident at $v$. A rotation system $R$ of a graph $G$ is an assignment of
a rotation at every vertex of $G$. There is an one-to-one correspondence
between the orientable embeddings and rotation systems.

An embedding of a graph $G$ on an arbitrary surface $S$ can be described
combinatorially by a signed rotation system (or a general rotation system)
$(R,\sigma),$ where $R$ is a rotation system of $G$ and $\sigma$ is the twist-
indicator, i.e., if $\sigma(e)=-1$, then the edge $e$ is twisted; otherwise
$\sigma(e)=1$ and $e$ is untwisted. A switch of a signed rotation system at a
vertex $v$ means reversing the rotation about $v$ and changing the sign on
each of its incident edges. Two signed rotation system are equivalent if one
can be transformed into another by a sequence of switches. For terms not
defined in this paper, we refer to [16].

A permutation-partition pair $(P,\Pi)$ consists of an arbitrary permutation
$P$ and an arbitrary partition $\Pi,$ both defined over some common underlying
set $S.$ It is a combinatorial generalization of graphs and graph embeddings.
The notion of a permutation-partition pair was introduced by Stahl in [28]. It
was also independently rediscovered in [2, 3], called IDS by Archdeacon. For
undefined terminologies on $(P,\Pi)$, see [30].

A signed graph $\Sigma=(G,\sigma)$ is a graph $G$ together with a mapping
$\sigma$ which assigns $+1$ or $-1$ to each edge of the graph $G.$ If
$\sigma(e)=1,$ we call the edge positive, otherwise $\sigma(e)=-1$ and the
edge is negative. An embedding of a signed graph $\Sigma=(G,\sigma)$ can be
described combinatorially by a signed rotation system $(R,\sigma),$ where $R$
is the rotation system of $G,$ and $\sigma$ can be thought of as the twist-
indicator. There are many researches on signed graph embeddings, see [9, 21,
22, 24, 25, 26, 36, 37, 38, 39], etc.

Two embeddings $(R_{1},\sigma),$ and $(R_{2},\sigma)$ of $\Sigma=(G,\sigma)$
are equivalent if their rotation system $R_{1}$ and $R_{2}$ are the same. Let
the sample space $\Omega$ consist of all inequivalent embeddings $\Sigma$. The
Euler-genus random variable $\gamma^{E}$ is define as

$\gamma^{E}:\Omega\longrightarrow\\{0,1,\ldots,\\}.$

If $(R,\sigma)$ embeds $\Sigma$ on $S_{i}$, then $\gamma^{E}(R,\sigma)=i.$ The
average Euler-genus $\gamma_{avg}^{E}(\Sigma)$ of a signed graph $\Sigma$ is
the expected value of the Euler-genus random variable, over all labeled
embeddings of $\Sigma,$ using the uniform distribution

$P(\Sigma)=\frac{1}{\prod_{v\in V(G)}(d_{v}-1)!},$

i.e.,

(1.1)
$\displaystyle\gamma_{avg}^{E}(\Sigma)=\frac{\displaystyle\sum_{R\in\Omega}\gamma^{E}(R,\sigma)}{\prod_{v\in
V(G)}(d_{v}-1)!}.$

Note that the average genus of a single graph was introduced in [14] by Gross
and Furst and was further developed in [15, 4, 5, 6, 7]. Recently, Loth,
Halasz, Masařík, Mohar, and Šámal [18] and Loth and Mohar [19] obtained tight
lower bounds for the average genus. The author proved that nonorientable
average genus of a random graph is close to its maximum nonorientable genus
[10]. We may refer to [8, 32, 34] for more topics on average genus.

Given an oriented embedding of a graph $G$, Stahl [27] proved a local counting
theorem that provided an expression for the number of distinct faces which
contain a specific vertex on their boundary in terms of the orbits of the
product of two permutations. The two permutations were derived from Edmonds’
rotation systems. He then used this expression to give new proofs of several
classical theorems in topological graph theory, such as the Duke’s
interpolation theorem and the additivity theorem for the genus of Battle,
Harary, Kodama, and Youngs. The local counting theorem was also independently
rediscovered, in a more geometrical form, in [17, 18], etc. For other works
related to the local counting theorem, see [28, 29, 32, 11], etc.

Let $U$ be a subset of the vertex set $V(G)$ of a graph $G$. Then the boundary
of $U$, denoted by $\partial(U)$, is the set of oriented edges of $G$ that
emanate from a vertex of $U$ and terminate at a vertex of $V(G)-U$. In [28],
Stahl generalized the local counting theorem to the case of containing edges
of $\partial U$ for an oriented embedding. Given an embedding of $G$ on an
arbitrary surface $S$, here we obtain an expression for the number of distinct
faces which contain the edges of $\partial U.$ Our result can be thought of as
a generalization of Stahl’s theorem to nonorientable embeddings.

The paper is organized as follows. In Section 2, we prove the counting theorem
for graph embeddings. Upper and lower bounds for the average Euler-genus of
the vertex-amalgamation of signed graphs is given in Section 3.

##  2\. The counting theorem

###  2.1. Combinatorial embeddings of graphs

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E.$ Suppose that
$K=\\{1,\alpha,\beta,\gamma\\}$ is the Klein four-group. Given an edge $a\in
E,$ we introduce its two sides and two ends. Assume $a$ itself at one end and
on one side. Let $\alpha$ be the permutation that interchanges symbols at the
same end but different sides of an edge, for each edge. Let $\beta$ be the
permutation that interchanges symbols at the same side but different ends of
an edge, for each edge. We call the set $Ka=\\{a,\alpha a,\beta a,\gamma a\\}$
a quadricell.

An embedding $(R,\sigma)$ of $G$ on some surfaces induces a bi-rotation system
$P$ on $V$ such that at each vertex, all its incident semi-edges are with a
cyclic order, called a bi-rotation. Since each edge is considered as a
quadricell, the bi-rotation at a vertex $v$ is

$\left\\{(a,Pa,\ldots,P^{(m-1)}a),(\alpha a,\alpha P^{-1}a,\ldots,\alpha
P^{-(m-1)}a)\right\\}.$

We denote by $\langle P,\gamma\rangle$ the group of permutations $P,\gamma$
generated by them. Tutte provided an axiomatization for any embedding of $G$,
as stated in the following result of Tutte.

An embedding $M$ (or a map) is an ordered triple $(\alpha,\beta,P)$ of
permutations acting on a set $S$ of $4m$ elements, such that

  1. (1)

for any $a\in S,$ then $a,\alpha a,\beta a,\gamma a$ are distinct.

  2. (2)

$\alpha P=P\alpha^{-1}$.

  3. (3)

for each $a\in S$, the orbits of $P$ through $a$ and $\alpha a$ are distinct.

  4. (4)

$\langle P,\gamma\rangle$ acts transitively on $S.$

It’s known that if the action of $\langle P,\gamma\rangle$ on $S$ is
transitive, then $M$ is non-orientable, otherwise there are precisely two
orbits, and $M$ is orientable. For more on Tutte’s axiomatization of graph
embeddings, see [20, 35], etc.

###  2.2. The counting theorem

Suppose that the rotation at every vertex $v$ of $G$ is counter-clockwise.
Given an oriented edge $e$, we denote $e^{l}$ and $e^{r}$ as the left side and
the right side of $e$, respectively. We also denote $e^{+}$ and $e^{-}$ as the
lower end and the upper end of $e$, respectively. Under this convention,
$e^{l_{+}}$, $e^{r_{+}}$, $e^{l_{-}},$ and $e^{r_{-}}$ denote the lower left
side, the lower right side, the upper left side, and the upper right side of
$e$ respectively, as shown in Figure 2.1.

Figure 2.1.

Let $(R,\sigma)$ be a signed rotation system of $G$ with $\sigma(e)=1$ for
$e\in\partial(U)$ and let $\iota_{(R,\sigma)}$ be the embedding of $G$ induced
by $(R,\sigma)$. Let $U\subseteq V(G)$. Any rotation system $(R,\sigma)$ of
$G$ induces two permutations, exterior permutation $Ext_{R,U}$ and interior
permutation $Int_{R,U}$ on $\partial(U)$ as follows. When we say $e^{l},$ we
mean its left upper end or left lower end of $e^{l},$ namely, we have
$e^{l}\in\\{e^{l_{+}},e^{l_{-}}\\}.$ Similarly, the edge $e^{r}$ means its
right upper end or right lower end and $e^{r}=e^{r_{+}}$ or $e^{r_{-}}.$ For
any $e\in\partial(U),$ and let $\delta\in\\{+,-\\}$, we define

$Ext_{R,U}(e)=\gamma[P\gamma]^{x(e)}(e^{r_{\delta}}),\ \ \ \ \
Int_{R,U}(e)=\gamma[\gamma{P}]^{y(e)}(e^{l_{\delta}})$

where $x(e)$ and $y(e)$ are the least positive integers such that
$[P\gamma]^{x(e)}(e^{r_{\delta}})\in\\{e_{s}^{l_{-}},e_{s}^{l_{+}}\\}$ for
some $e_{s}\in\partial(U)$, and $[\gamma
P]^{x(e)}(e^{l_{\delta}})\in\\{e_{t}^{r_{+}},e_{t}^{r_{-}}\\}$ for some
$e_{t}\in\partial(U)$ respectively. When $U$ consists of a vertex $u$, i.e.,
$U=\\{u\\}$, then we also denote $Ext_{R,U}$ and $Int_{R,U}$ as $Ext_{R,u}$
and $Int_{R,u}$, respectively.

We have an intuitive explanation for $Ext_{R,U}$. For each oriented edge $e$
in $\partial(U)$, let ${F}_{e}$ be the face of the embedding
$\iota_{(R,\sigma)}$ whose boundary contains $e$. Staring from
$e^{r_{\delta}},$ then follow along the boundary of $F_{e}$ until the first
edge $e_{s}^{l,-}$ or $e_{s}^{l,+}$ belonging to $\partial(U)$ in encountered,
this edge is $Ext_{R,U}(e)$, namely, $Ext_{R,U}(e)=e_{s}.$

Again, here’s an intuitive explanation for $Int_{R,U}.$ Staring from
$e^{l_{\delta}}$, then follow along the boundary of $F_{e}$ until the first
edge $e_{t}^{r_{+}},$ or $e_{t}^{r_{-}}$ belonging to $\partial(U)$ in
encountered, this edge is $Int_{R,U}(e)$. Then $Int_{R,U}(e)=e_{t}$.

Here, we give a proof that $Ext_{R,U}$ is indeed a permutation of
$\partial(U).$ We only need to give a proof for the case $U=\\{u\\}$, because
we can contract $U$ into a vertex $u$ by shrinking the edges so that the
resulting graph is still embedded in the same surface.

By definition, $Ext_{R,U}(e)=f^{r}$ for some $f\in\partial(U).$ Thus
$Ext_{R,U}(e)\in\partial(U).$ We now go to show that $Ext_{R,U}$ is injective.
If there exit two different edges $e,f\in\partial(U)$ such that
$Ext_{R,U}(e)=Ext_{R,U}(f)$. By symmetry, we can assume that $x(e)$ is greater
than or equal to $x(f).$ Thus

$\gamma[P\gamma]^{x(e)-x(f)-1}(e^{r_{\delta}})=P^{-1}(f^{r_{\delta}}).$

Note that $x(e)-x(f)-1$ is less than $x(e).$

If $x(e)=x(f)$, then

$P^{-1}(f^{r_{\delta}})=P^{-1}(e^{r_{\delta}}),$

thus $f=e$ which contradicts $e\neq f$.

If $x(e)=x(f)+1$, then

$P\gamma(e^{r_{\delta}})=(f^{r_{\delta}}).$

This means $e,f$ lie on the boundary of the same face and $e,f$ are adjacent
in the face, this contradicts that $G$ is a simple graph, again it’s
impossible.

If $x(e)-x(f)\geq 2$, then
$\gamma[P\gamma]^{x(e)-x(f)-1}(e^{r_{\delta}})=P^{-1}(f^{r_{\delta}})$. If
$f^{r_{\delta}}=f^{r_{+}},$ then the initial point of $P^{-1}(f^{r_{+}})$ is
the same as that of $f$ and is therefore in $\partial(U),$ which contradicts
the minimality of $x(e).$ Otherwise
$\gamma[P\gamma]^{x(e)-x(f)+1}(e^{r_{-}})=P\gamma(f^{r_{-}})=Pf^{l_{+}}$,
again the initial point of $P(f^{l_{+}})$ is the same as that of $f$ and is
therefore in $\partial(U).$ This also implies that $x(f)\geq 2$. Thus
$x(e)-x(f)+1<x(e)$, it’s impossible.

In summary, $Ext_{R,U}$ is a permutation of $\partial(U).$ Similarly, we can
also prove that $Int_{R,U}$ is a permutation of $\partial(U).$

Given a permutation $P$, we denote by $||P||$ the number of orbits in the
permutation $P$. We have the following counting theorem for a graph embedding.

######  Theorem 2.1.

Suppose that $U$ is a set of vertices of a graph $G,$ and let $(R,\sigma)$ be
a signed rotation system of $G$ with $\sigma(e)=1$ for any $e\in\partial(U).$
Then the number of faces of the embedding $\iota_{(R,\sigma)}$ whose
boundaries contain arcs of $\partial(U)$ is $||Ext_{R,U}\circ Int_{R,U}||.$

###### Proof.

Note that $||Int_{R,U}\circ Ext_{R,U}||=||Ext_{R,U}\circ Int_{R,U}||,$ we
prove that the number of faces of the embedding $\iota_{(R,\sigma)}$ whose
oriented boundaries contain arcs of $\partial(U)$ is $||Int_{R,U}\circ
Ext_{R,U}||.$ Let $e=Ext_{R,U}(d),$ and let $f=Int_{R,U}(e)$. Assume
$Int_{R,U}(e)=\gamma[\gamma P]^{x(e)}(e^{l_{\delta}}).$ Then

$Int_{R,U}\circ Ext_{R,U}(d)=\gamma[\gamma
P]^{x(e)}\gamma(P\gamma)^{y(d)}(d^{r_{\delta}})=[P\gamma]^{x(e)+y(d)}(d^{r_{\delta}}).$

Since $d$ and $[P\gamma]^{x(e)+y(d)}(d^{r_{\delta}})$ belong to $\partial(U).$
We have the following claim.

Claim: $x(e)+y(d)$ is the least such integer that
$[P\gamma]^{x(e)+y(d)}(d^{r_{\delta}})=f^{l}$ for $f\in\partial(U).$

Suppose that $[P\gamma]^{m}(d^{r_{\delta}})=g^{l}$ for some $g\in\partial(U).$
We have $\gamma[P\gamma]^{m}(d^{r_{\delta}})=g^{r},$ namely,

$[\gamma P]^{m-y(d)}\gamma[P\gamma]^{y(d)}(d^{r_{\delta}})=g^{r},$

for some $g\in\partial(U).$

Since $e=Ext_{R,U}(d)=\gamma[P\gamma]^{y(d)}(d^{r_{\delta}})$, hence we have
$[\gamma P]^{m-y(d)}(e)=g^{r},$ for some $g\in\partial(U).$ This implies that
$m-y(d)\geq x(e),$ i.e., $m\geq x(e)+y(d).$

By the claim, the orbits of $Ext_{R,U}\circ Int_{R,U}$ are obtained from those
of the faces $P\gamma$ of the embedding $\iota_{(R,\sigma)}$ by deleting all
the edges not in $\partial(U).$ The theorem follows. ∎

######  Remark 2.2.

Another way to define $Ext_{R,U}$ and $Int_{R,U}$ are as follows:

$Ext_{R,U}(e)=\gamma[\gamma P]^{x(e)}(e^{l_{\delta}}),\ \ \ \ \
Int_{R,U}(e)=\gamma[P\gamma]^{x(e)}(e^{r_{\delta}})$

where $x(e)$ and $y(e)$ are the least positive integers such that $[\gamma
P]^{x(e)}(e^{l_{\delta}})\in\\{e_{s}^{r_{-}},e_{s}^{r_{+}}\\}$ for some
$e_{s}\in\partial(U)$, and
$[P\gamma]^{x(e)}(e^{r_{\delta}})\in\\{e_{t}^{l_{+}},e_{t}^{l_{-}}\\}$ for
some $e_{t}\in\partial(U)$ respectively.

Let’s illustrate Theorem 2.1 with two examples.

######  Example 2.1.

Let $G=(V,E)$ be the graph of Figure 2.2 with the vertex set
$V(G)=\\{u,v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$.

Figure 2.2.

Suppose that the rotation system of $G$ at every vertex is counter-clockwise,
i.e., the vertex rotation of $G$ at $u$ is $(123456).$ Let $U=\\{u\\}$ and
$\partial(U)=\\{1,2,3,4,5,6\\}.$ All the edges of $G$ are untwisted except the
edge $v_{3}v_{4},$ i.e., $\sigma(v_{3}v_{4})=-1$ and $\sigma(e)=1,$ for $e\in$
$E(G)\setminus v_{3}v_{4}.$

We let

$\alpha=\prod_{i=1}^{9}(i^{l_{+}}i^{r_{+}})(i^{l_{-}}i^{r_{-}}),\ \
\beta=\prod_{j=1}^{9}(j^{l_{+}}j^{r_{+}})(j^{l_{-}}j^{r_{-}}),$

and

$\displaystyle P=$
$\displaystyle(1^{r_{+}}2^{r_{+}}3^{r_{+}}4^{r_{+}}5^{r_{+}}6^{r_{+}})(6^{l_{+}}5^{l_{+}}4^{l_{+}}3^{l_{+}}2^{l_{+}}1^{l_{+}})(7^{r_{+}}1^{l_{-}})(7^{l_{+}}1^{r_{-}})(7^{l_{-}}2^{l_{-}})(7^{r_{-}}2^{r_{-}})(8^{r_{+}}3^{l_{-}})$
$\displaystyle(8^{l_{+}}3^{r_{-}})(8^{l_{-}}4^{r_{-}})(8^{r_{-}}4^{l_{-}})(9^{r_{+}}5^{l_{-}})(9^{l_{+}}5^{r_{-}})(9^{l_{-}}6^{l_{-}})(9^{r_{-}}6^{r_{-}}).$

Also, we compute the number of faces of the embedding, we get

$\displaystyle P\alpha\beta=$
$\displaystyle(1^{r_{+}}7^{r_{+}}2^{l_{-}}3^{r_{+}}8^{r_{+}}4^{r_{-}}3^{l_{+}}8^{l_{+}}4^{l_{-}}5^{r_{+}}9^{r_{+}}6^{l_{-}})(1^{r_{-}}6^{l_{+}}9^{r_{-}}5^{r_{-}}4^{l_{+}}8^{l_{-}}3^{l_{-}}4^{r_{+}}8^{r_{-}}3^{r_{-}}2^{l_{+}}7^{r_{-}})$
$\displaystyle(6^{r_{+}}9^{l_{-}}5^{l_{-}})(6^{r_{-}}5^{l_{+}}9^{l_{+}})(2^{r_{+}}7^{l_{-}}1^{l_{-}})(2^{r_{-}}1^{l_{+}}7^{l_{+}})$
$\displaystyle=$ $\displaystyle(1^{r_{+}}\cdots 2^{l_{-}}3^{r_{+}}\cdots
4^{r_{-}}3^{l_{+}}\cdots 4^{l_{-}}5^{r_{+}}\cdots 6^{l_{-}})(6^{l_{+}}\cdots
5^{r_{-}}4^{l_{+}}\cdots 3^{l_{-}}4^{r_{+}}\cdots 3^{r_{-}}2^{l_{+}}\cdots
1^{r_{-}})$ $\displaystyle(6^{r_{+}}\cdots 5^{l_{-}})(5^{l_{+}}\cdots
6^{r_{-}})(2^{r_{+}}\cdots 1^{l_{-}})(1^{l_{+}}\cdots 2^{r_{-}}).$

For exterior permutation, if we start from the edge $1^{r_{+}}$ in

$(1^{r_{+}}\cdots 2^{l_{-}}3^{r_{+}}\cdots 4^{r_{-}}3^{l_{+}}\cdots
4^{l_{-}}5^{r_{+}}\cdots 6^{l_{-}}),$

we get

$1\rightarrow 2,\ 3\rightarrow 3,\ 4\rightarrow 4,\ 5\rightarrow 6$

Then by $(6^{r_{+}}\cdots 5^{l_{-}})$ and $(2^{r_{+}}\cdots 1^{l_{-}})$, we
get

$6\rightarrow 5,\ 2\rightarrow 1,$

Thus

$Ext_{R,U}=(12)(3)(4)(56),$

and the interior permutation is

$Int_{R,U}=(654321).$

Thus,

$Ext_{R,U}\circ Int_{R,U}=(12)(3)(4)(56)(654321)=(2)(6)(4315).$

######  Remark 2.3.

The orbit $(2)$ of $(2)(6)(4315)$ represents the face

$(2^{r_{+}}\cdots 1^{l_{-}})(1^{l_{+}}\cdots 2^{r_{-}}).$

Similarly, the orbits $(6)$ and $(4315)$ represent faces

$(6^{r_{+}}\cdots 5^{l_{-}})(5^{l_{+}}\cdots 6^{r_{-}})$

and

$(1^{r_{+}}\cdots 2^{l_{-}}3^{r_{+}}\cdots 4^{r_{-}}3^{l_{+}}\cdots
4^{l_{-}}5^{r_{+}}\cdots 6^{l_{-}})(6^{l_{+}}\cdots 5^{r_{-}}4^{l_{+}}\cdots
3^{l_{-}}4^{r_{+}}\cdots 3^{r_{-}}2^{l_{+}}\cdots 1^{r_{-}})$

respectively.

If we swap the edges $2$ and $3$ in the permutation $R$ and other bits of $R$
inherit completely, we denote the resulting permutation as $R^{{}^{\prime}}$,
namely, we let

$\displaystyle P^{{}^{\prime}}=$
$\displaystyle(1^{r_{+}}3^{r_{+}}2^{r_{+}}4^{r_{+}}5^{r_{+}}6^{r_{+}})(6^{l_{+}}5^{l_{+}}4^{l_{+}}2^{l_{+}}3^{l_{+}}1^{l_{+}})(7^{r_{+}}1^{l_{-}})(7^{l_{+}}1^{r_{-}})(7^{l_{-}}2^{l_{-}})(7^{r_{-}}2^{r_{-}})$
$\displaystyle(8^{r_{+}}3^{l_{-}})(8^{l_{+}}3^{r_{-}})(8^{l_{-}}4^{r_{-}})(8^{r_{-}}4^{l_{-}})(9^{r_{+}}5^{l_{-}})(9^{l_{+}}5^{r_{-}})(9^{l_{-}}6^{l_{-}})(9^{r_{-}}6^{r_{-}}).$

If we start from the edge $3^{r}$, then

$Ext_{R^{{}^{\prime}},U}=(321465)$

and the interior permutation is

$Int_{R^{{}^{\prime}},U}=(654231).$

We have

$Ext_{R^{{}^{\prime}},U}\circ Int_{R^{{}^{\prime}},U}=(63415)(2).$

######  Example 2.2.

Let $G=(V,E)$ be the graph of Figure 2.3 with the vertex set
$V(G)=\\{u,v,w,x,y,z\\}$.

Figure 2.3.

Suppose that the rotation system of $G$ at every vertex is counter-clockwise.
Let $U=\\{u,v\\}$ and $\partial(U)=\\{1,2,3,4\\}.$ All the edges of $G$ are
untwisted except the edges $uv,$ and $wx,$ i.e., $\sigma(uv)=\sigma(wx)=-1$
and $\sigma(e)=1,$ for $e\in$ $E(G)\setminus\\{uv,wx\\}.$ Let

$\alpha=\prod_{i=1}^{9}(i^{l_{+}}i^{r_{+}})(i^{l_{-}}i^{r_{-}}),\ \
\beta=\prod_{j=1}^{9}(j^{l_{+}}j^{r_{+}})(j^{l_{-}}j^{r_{-}}),$

and

$\displaystyle P=$
$\displaystyle(2^{r_{+}}3^{r_{+}}9^{l_{-}})(3^{l_{+}}2^{l_{+}}9^{r_{-}})(1^{r_{+}}9^{r_{+}}4^{r_{+}})(1^{l_{+}}4^{l_{+}}9^{l_{+}})(6^{r_{-}}2^{r_{-}}7^{r_{-}})(6^{l_{-}}7^{l_{-}}2^{l_{-}})$
$\displaystyle(6^{r_{+}}1^{l_{-}}5^{l_{-}})(6^{l_{+}}5^{r_{-}}1^{r_{-}})(7^{r_{+}}8^{r_{+}}3^{r_{+}})(7^{l_{+}}3^{r_{-}}8^{l_{+}})(5^{r_{+}}4^{l_{-}}8^{l_{-}})(5^{l_{+}}8^{r_{-}}4^{r_{-}}).$

An exterior permutation for the embedding of $G$ is

$Ext_{R,U}=(1432),$

and an interior permutation is as the following

$Int_{R,U}=(14)(32).$

Thus,

$Ext_{R,U}\circ Int_{R,U}=(13)(2)(4),$

namely, the number of faces containing the edges of $\partial(U)$ is $3.$

It’s easy to see that if $U=\\{u\\}$, then $Int_{R,u}$ is the counter-
clockwise rotation of the edges which incident with $u.$ Furthermore, the
following property follows..

######  Lemma 2.4.

Let $U=\\{u_{1},u_{2},\ldots,u_{k}\\}$ be an independent set of vertices of a
connected signed graph $\Sigma,$ then, for any embedding of $\Sigma,$

$Int_{R,U}=R^{1}R^{2}\cdots R^{k},$

where $R^{i}$ is the rotation of the edges which incident with $u_{i}$ for
$i=1,2,\ldots,k.$

##  3\.  the average Euler-genus of the vertex-amalgamation of signed graphs

Let $H$ be a subgraph of $G$, the induced rotation system $R$ of $G$ on $H$ is
obtained by deleting all edges of $G-H$ from the rotation system $R.$

For $k\geq 2$, let $\Sigma^{i}$ ($1\leq i\leq k$) be a set of disjoint signed
graphs, each $\Sigma^{i}$ contains a common set
$U=\\{u_{1},u_{2},\ldots,u_{l}\\}$ of vertices. Then we denote the vertex-
amalgamation of the signed graphs $\Sigma^{1},\Sigma^{2},\ldots,\Sigma^{k}$
over $U$ by $\Sigma=\bigcup_{U}\Sigma^{i}$ as the signed graph obtained by
identifying distinct copies of $U.$ For minimum genus and maximum genus of
vertex-amalgamation of graphs, see [1, 2, 3, 12, 13, 29], etc.

For $d\geq 0,$ the harmonic sum $h_{d}$ is given by

$h_{0}=0,h_{1}=1$

and

$h_{d}=1+1+\frac{1}{2}+\cdots+\frac{1}{d-1}$

for $d\geq 2.$

The following theorem was proved in [31].

######  Theorem 3.1.

[31] Let $(P,\Pi)$ be a permutation-partition pair such that
$\Pi=(\Pi_{1},\Pi_{2},\ldots,\Pi_{k})$ and $d_{i}=|\Pi_{i}|$ for
$i=1,2,\ldots,k$. If $\mu$ denotes the mean of the number of regions in the
random embedding of $(P,\Pi)$, then
$\mu(P,\Pi)\leq\displaystyle\sum_{i=1}^{k}h_{d_{i}}.$

The following theorem generalizes Stahl’s bound [33] for the average Euler-
genus of the vertex-amalgamation of graphs to signed graphs. The ideas are the
same, we give a detailed proof here for completeness.

######  Theorem 3.2.

Let $\Sigma^{i}$, $i=1,2,\ldots,k,$ be connected signed graphs, and let
$U=\\{u_{1},u_{2},\ldots,u_{l}\\}$ be an independent set of vertices of
$\Sigma^{i}$ and $\Sigma=\bigcup_{U}\Sigma_{i}.$ Suppose that

$d_{\Sigma}(u_{j})=d_{j}$

and

$d_{\Sigma^{i}}(u_{j})=d_{i,j},\ i=1,\ldots,k,j=1,\ldots,l.$

Then

$\displaystyle-\displaystyle\sum_{i=1}^{l}h_{d_{i}}\leq\gamma_{avg}^{E}(\Sigma)-\displaystyle\sum_{i=1}^{k}\gamma_{avg}^{E}(\Sigma^{i})-(k-1)(l-2)\leq\displaystyle\sum_{i=1}^{k}\displaystyle\sum_{j=1}^{l}h_{d_{i,j}}.$

###### Proof.

We denote $\rho_{avg}(\Sigma)$ the average number of faces in the random
embedding of $\Sigma$ into $S_{i}$ with Euler-genus $i.$ From the Euler
formula,

$|V(\Sigma)|-|E(\Sigma)|+\rho_{avg}(\Sigma)=2-\gamma_{avg}^{E}(\Sigma),$

thus we only need to prove the following formula

$\displaystyle-\displaystyle\sum_{i=1}^{k}\displaystyle\sum_{j=1}^{l}h_{d_{i,j}}\leq\rho_{avg}(\Sigma)-\displaystyle\sum_{i=1}^{k}\rho_{avg}(\Sigma^{i})\leq\displaystyle\sum_{i=1}^{k}h_{d_{i}}.$

If $R$ is a rotation system of $G,$ then $(R,\sigma)$ is a signed rotation
system of $\Sigma=(G,\sigma).$ For $1\leq i\leq k$, let $R^{i}$ be the induced
rotation system of $G$ on $G^{i}$, i.e.,$\Sigma^{i}=(G^{i},R^{i}).$

By Theorem 2.1,

$\displaystyle\rho(\Sigma,R)$ $\displaystyle=||Ext_{(R,U)}\circ
Int_{(R,U)}||+|F|,$ $\displaystyle\rho(\Sigma^{i},R^{i})$
$\displaystyle=||Ext_{(R^{i},U)}\circ Int_{(R^{i},U)}||+|F^{i}|,\ \ (1\leq
i\leq k).$

where $F$ ($F^{i}$) consists of all the faces of $(R,\sigma)$ (
$(R^{i},\sigma)$ )that contain no arcs of $\partial(U).$ Here
$Ext_{(R^{i},U)}$ and $Int_{(R^{i},U)}$ are permutations of $\partial(U)\cap
G^{i}.$

It’s clear that

$\displaystyle|F|=\displaystyle\sum_{i=1}^{k}|F^{i}|.$

From the discussion above, we have

$\displaystyle\rho(\Sigma,R)-\displaystyle\sum_{i=1}^{k}\rho(\Sigma^{i},R^{i})$
$\displaystyle=$ $\displaystyle||Ext_{(R,U)}\circ
Int_{(R,U)}||-\displaystyle\sum_{i=1}^{k}||Ext_{(R^{i},U)}\circ
Int_{(R^{i},U)}||$ $\displaystyle\leq$ $\displaystyle||Ext_{(R,U)}\circ
Int_{(R,U)}||.$

Let $R$ take all elements in $\Omega$ of $G$ with uniform probability
$\frac{1}{|\Omega|}$. Then,

$\displaystyle\frac{1}{|\Omega|}\displaystyle\sum_{R\in\Omega}(\rho(\Sigma,R)-\displaystyle\sum_{i=1}^{k}\rho(\Sigma^{i},R^{i}))$
$\displaystyle\leq$
$\displaystyle\frac{1}{|\Omega|}\displaystyle\sum_{R\in\Omega}||Ext_{(R,U)}\circ
Int_{(R,U)}||$

which is equivalent to

(3.2)
$\displaystyle\rho_{avg}(\Sigma)-\displaystyle\sum_{i=1}^{k}\rho_{avg}(\Sigma^{i})\leq||Ext_{(R,U)}\circ
Int_{(R,U)}||.$

By Lemma 2.4,

$Int_{R,U}=R^{1}R^{2}\cdots R^{k},$

Then we obtain a permutation-partition pair $(P,\Pi)$, where

$P=Ext_{(R,U)}$

and

$\Pi=\\{{\partial(U)\cap G^{i}|i=1,2,\ldots,k}\\}.$

Note that $|\partial(U)\cap G^{i}|=d_{j}$, and by Theorem 3.1, the expected
value of $||Ext_{(R,U)}\circ Int_{(R,U)}||$ is less than or equal to

$\displaystyle\sum_{i=1}^{k}h_{d_{i}}.$

Since this bound is independent of $Ext_{(R,U)}$ for any $R$ of $G$, thus,

$\displaystyle\rho_{avg}(\Sigma)-\displaystyle\sum_{i=1}^{k}\rho_{avg}(\Sigma^{i})\leq\displaystyle\sum_{i=1}^{k}h_{d_{i}}.$

We next prove the other bound, again by Equation (3), it follows that

$\displaystyle\rho_{avg}(\Sigma)-\displaystyle\sum_{i=1}^{k}\rho_{avg}(\Sigma^{i})\geq-\displaystyle\sum_{i=1}^{k}||Ext_{(R^{i},U)}\circ
Int_{(R^{i},U)}||.$

Similarly, we have

$||Ext_{(R^{i},U)}\circ
Int_{(R^{i},U)}||\leq\displaystyle\sum_{j=1}^{l}h_{d_{i,j}}.$

Thus

(3.3)
$\displaystyle\rho_{avg}(\Sigma)-\displaystyle\sum_{i=1}^{k}\rho_{avg}(\Sigma^{i})\geq-\displaystyle\sum_{i=1}^{k}\displaystyle\sum_{j=1}^{l}h_{d_{i,j}}.$

The result follows. ∎

## References

  * [1] S.R. Alpert, The genera of amalgamations of graphs, Trans. Amer. Math. Soc., 78 (1973),1–39.
  * [2] D. Archdeacon, The nonorientable genus is additive,  J. Graph Theory 10 (1986), 363–383.
  * [3] D. Archdeacon, The orientable genus is nonadditive,  J. Graph Theory 10 (1986), 385–402.
  * [4] J. Chen and J.L. Gross, Limit points for average genus (I) 3-connected and 2-connected simplicial graphs, J. Combin. Theory Ser. B 55 (1992), 83–103.
  * [5] J. Chen and J.L. Gross, Limit points for average genus (II) 2-connected non-simplicial graphs, J. Combin. Theory Ser. B  56 (1992), 108–129.
  * [6] J. Chen and J.L. Gross, Kuratowski-type theorems for average genus, J. Combin. Theory Ser. B 57 (1993), 100–121.
  * [7] J. Chen, J.L. Gross and R.G. Rieper, Lower bounds for the average genus, J. Graph Theory, 19 (1995), 281–296.
  * [8] Y. Chen, Lower bounds for the average genus of a CF-graph, Electron. J. Combin., 17(1) (2010) $\sharp$R150.
  * [9] Y. Chen, Permutation-bipartition pairs, 2022.arXiv:2204.04359v3, Apr 2022.
  * [10] Y. Chen, Permutation-bipartition pairs II, 2022+.
  * [11] Y. Chen, J.L. Gross, and T. Mansour, On the genus distributions of wheels and of related graphs, Discrete Math. 341 (2018) 934-945.
  * [12] Y. Chen, J.L. Gross, T. Mansour, and T.W. Tucker, Recurrences for the genus polynomials of linear sequences of graphs, Math. Slovaca, 3 (2020), 505–526.
  * [13] R.W. Decker, H.H. Glover, and J.P. Huneke, The genus of 2-connected graphs, J. Graph Theory, 5 (1981), 95–102.
  * [14] J. L. Gross, and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph,  J. Graph Theory 11 (1987), 205–220.
  * [15] J.L. Gross, E.W. Klein, and R.G. Rieper, On the average genus of a graph, _Graphs and Combinatorics_ 9(2-4)(1993), 153-162.
  * [16] J.L. Gross and T.W. Tucker, Topological Graph Theory, Dover, 2001; (original edn. Wiley, 1987).
  * [17] J. L. Gross, T. Mansour, T. W. Tucker, and D. G-L. Wang, Combinatorial conjectures that imply local log-concavity of graph genus polynomials, European Journal of Combinatorics 52 (2016), 207–222.
  * [18] J. C. Loth, K. Halasz, T. Masařík, B. Mohar, and R. Šámal, Random 2-cell embeddings of multistars, Proceedings of the American Mathematical Society, to appear, arXiv:2103.05036v2, 2021.
  * [19] J. C. Loth, and B. Mohar, Expected number of faces in a random embedding of any graph is at most linear, arXiv:2202.07746v1, 2022.
  * [20] Y.P. Liu, Theory of polyhedra, Science press, Beijing 2008.
  * [21] S. Lv, The largest demigenus over all signatures on $K_{3,n}$, Graphs Combin., 31(1) (2015), 169-181.
  * [22] S. Lv and Z. Yuan, The smallest surface that contains all signed graphs on $K_{4,n}$, Discrete Math. 341(1) (2018), 732-747.
  * [23] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Press, 2001.
  * [24] J. Širán, Characterization of signed graphs which are cellularly embeddable in no more than one surface, Discrete Math. 94(1) (1991), 39–44.
  * [25] J. Širán, Duke’s theorem does not extend to signed graph embeddings, Discrete Math. 94 (1991), 233–238.
  * [26] J. Širán, and M. Škoviera, Characterization of the maximum genus of a signed graph, J. Combin. Theory B 52(1)(1991), 124–146.
  * [27] S. Stahl, A counting theorem for topological graph theory, Theory and applications of graphs in Proceedings, Conf. Western Michigan Univ., Kalamazoo, Mich., 1976 (Y. Alavi and D. R. Lick, Rds.), Lecture Notes in Math. Springer-Verlag, Berlin/New York, 642 (1976), 534–544.
  * [28] S. Stahl, Permutation-partition pairs: A combinatorial generalization of graph embeddings, Trans. Amer. Math. Soc. 259 (1980), 129–145.
  * [29] S. Stahl, Permutation-partition Pairs II: Bounds on the genus of the amalgamation of graphs, Trans. Amer. Math. Soc. 271(1) (1982), 175–182.
  * [30] S. Stahl, Permutation-partition pairs III: Embedding distributions of linear families of graphs, J. Combin. Theory B 52 (1991), 191–218.
  * [31] S. Stahl, An upper bound for the average number of regions, J. Combin. Theory B 52 (1991), 219–221.
  * [32] S. Stahl, Region distributions of some small diameter graphs, Discrete Math. 89 (1991), 281–299.
  * [33] S. Stahl, Bounds for the average genus of the vertex-amalgamation of graphs,  Discrete Math. 142 (1-3)(1995), 235–245.
  * [34] S. Stahl, On the average genus of the random graph, J. Graph Theory, 20(1) (1995), 1–18.
  * [35] W.T. Tutte, Graph theory, Cambridge University Press, 2001.
  * [36] T. Zaslavsky, Orientation embedding of signed graphs, Journal of Graph Theory, 16(5) (1992), 399–422.
  * [37] T. Zaslavsky, The projective-planar signed graphs, Discrete Math. 113 (1993), 223–247.
  * [38] T. Zaslavsky, The order upper bound on parity embedding of a graph, J. Combin. Theory Ser B  68 (1996), 149–160.
  * [39] T. Zaslavsky, The largest parity demigenus of a simple graph, J. Combin. Theory Ser B  70 (1997), 325–345.