\section{Quantum Pseudo-Plactic Algebra}

The diagonal matrix  elements of the coorinate ring
$\C[GL_q(V)]$ of a quantum group close a subalgebra which is the noncommutative reincarnation of the  algebra of the functions on the torus. Krob and Thibon conjectured \cite{KT}  that the diagonal subalgebra
in $\C[GL_q(V)]$ is a cubic algebra that will be referred to as the {\it quantum pseudo-plactic algebra}.

\begin{deff}
The quantum  pseudo-plactic algebra $\PP_q(W)$
of the vector space $V$ with ordered basis,
$W = \bigoplus_{i=1}^D \C(q) a_i$ is the
quotient of the
free associative algebra $T(W)$ of $W$
by the two-sided ideal $\I$ generated
 by the cubic relations
\beq
\label{ppq}
\ba{lccc}
[[a,c],b] &=&0  &a<b<c \\[4pt]
[[a,b],a]_{q^2} &=&0  &a<b \\[4pt]
[b,[a,b]]_{q^2} &=&0  &a<b
\ea
\eeq
which we are referring to as quantum pseudo-Knuth relations.
Here $[x,y]_q$ stands for the deformed commutator
$[x,y]_q:=xy-q yx$ and $[x,y]=[x,y]_1$. Let $\I_q$ be
the  two-sided ideal  generated by the
quantum pseudo-Knuth
relations then one has
\[
\PP_q(W) = T(W)/\I_q(W) \ .
\]
\end{deff}
{\bf Remark.}	The algebra		$\PP(W)$ has as a factor the coordinate ring of the quantum torus,  $y x=q^2 x y$ for $x<y$ .

The specialization at $q=1$ of the quantum pseudo-plactic algebra
relations
\beq
\label{}
\ba{cccc}
[[a,c],b] &=&0  &a<b<c \\[4pt]
[[a,b],a] &=&0  &a<b \\[4pt]
[b,[a,b]] &=&0  &a<b
\ea
\eeq
 involve only commutators  thus $\PP_1(W) = T(W)/\I_1(W)$ is an universal enveloping algebra of a Lie algebra.
The specialization $\PP_1(W)$ will be referred to as pseudo-plactic algebra and denoted by $\PP(W) =T(W)/\I(W)$.

\noindent
{\bf Remark.} The specialization at $q=1$ of the  diagonal subalgebra  $\C[GL_q(V)]$  is a commutative algebra which is different from  the cubic pseudo-plactic algebra $\PP(W)$.

The quantum Schur-Weyl duality  is
the  double centralizing property  on ${\rm{End}}(T(V))$ of the action of the Hecke algebra $\h=\bigoplus_{r \geq 0} \hr$ and the (co)action
of the quantum group $\C[GL_q(V)]$. A
Schur functor is mapping a $\h$-module to a $\C[GL_q(V)]$-comodule
(or equivalently to a $\Uq(V)$-module).
The quantum pseudo-Knuth ideal $\I_q(W)$ inherts
 $\C[GL_q(V)]$-comodule structure upon restriction from
the diagonal subalgebra of $\C[GL_q(V)]$. Thus
 the quantum pseudo-plactic algebra $\PP_q(W)$
allow for a description \cite{P} based on Schur functors
\[
\PP_q(W)=\bigoplus_{n\geq 0} \PP_q (W)_n =
\bigoplus_{n\geq 0} \PP_q (n)\otimes_{\hn} W^{\otimes n}
\]
where $W$ is the diagonal in
$V\otimes V^\ast$, {\it i.e.}, the elements
invariant under transposition.
Let  $\h$-module $\I_q=\oplus_{r\geq 0}\I_q(r)$ be the Schur functor
pre-image of the quantum pseudo-Knuth ideal $\I_q(W)$.
Then the
the collection $\{\PP_q(r) \}_{r\geq 0}$ of  $\hr$-modules determines a $\h$-module
\[
\PP_q=\bigoplus_{r\geq 0} \PP_q(r) = \bigoplus_{r\geq 0} \hr/\I_q(r)  \
\]
which will be referred to as quantum pre-plactic algebra.

Similarly  we define the pre-plactic algebra $\PP$ to be a collection $\{ \PP(r) \}_{r\geq 0}$ of  $\S_r$-modules (see Definition \ref{prep}).
We are going to endow the pre-plactic algebra $\PP$   with a structure of a Hopf algebra
induced from the Malvenuto-Reutenauer
Hopf structure on
$\S=\bigoplus_{n\geq 0} \Q\S_n $ which we now briefly revise.

\section{Malvenuto-Reutenauer Hopf Algebra}

Malvenuto and Reutenauer \cite{MR}
have considered a Hopf algebra structure on $\S$
related to the Solomon descent
algebra \cite{S}.
There is a dual Hopf structure on $\S$
known also as
the algebra of free quasi-symmetric functions \cite{DHT}.

Given two permutations $\alpha \in \S_{r}$ and $\beta \in \S_{p}$, the product $\ast$ on $\S=\cup_{n\geq 0} \Q[\S_n]$ is induced (by linearity) from
$$
\begin{array}{rccc}
\ast :& \Q[\S_r]\times \Q[ \S_p] &\rightarrow & \Q[ \S_{r+p}]
\uparrow^{\S_{r+p} }_{\S_r\times \S_p}\ , \\[6pt]
&\alpha \times \beta &\mapsto&\alpha \ast \beta = \mathop{\sum}\limits_{\tiny\ba{c}st(u)=\alpha \\  st(v)=\beta \ea}
u v  \ .
\end{array}
$$
Here $st(w)$  is the standard word  in $ \S_n$ of
the word $w=w_1 \dots w_n$ of length $n$, i.e., the image of the unique increasing injective function from
$\{w_1, \dots w_n \}$ to $\{1, \dots  n \}$.

Similarly the coproduct $\Delta$ in  $\S$ is induced from
$$
\begin{array}{rccc}
\Delta:& \Q[ \S_r ] &\longrightarrow &
\mathop{\bigoplus}\limits_{i=0}^{r}
\Q[\S_i]\otimes \Q[\S_{r-i}]\downarrow^{\S_r}_{\S_i\times \S_{r-i}} \ ,\\
[4pt]
&\alpha &\mapsto& \Delta(\alpha) = \sum_{i=0}^{r} \alpha_{\{1,\ldots,i\}}\otimes
st(\alpha_{\{i+1,\ldots,r\}})
\end{array}
$$
Here $\alpha_I$ is the word obtained from $\alpha$ by erasing the letters outside $I$.

Let $\langle \,\, | \, \, \rangle$ stands for  the scalar product   such that
 the  basis of permutation words in $\S$ is orthonormal $\langle \alpha | \beta \rangle=\delta_{\alpha,\beta}$, $\alpha \in \S_{r}$ and $\beta \in \S_{p}$.
The dual Hopf structure  $\ast', \Delta'$
on $\S$
 is in linear duality with the structure $\ast, \Delta$,
{\it i.e.}, it is a convolution algebra  defined through
$$
\langle \alpha \ast \beta | \gamma \rangle =
\langle \alpha \otimes \beta| \Delta' \gamma
\rangle
\qquad
\langle \alpha \ast' \beta| \gamma \rangle =
\langle \alpha \otimes \beta| \Delta \gamma \rangle
 \qquad \alpha, \beta, \gamma \in \S \ .
$$
giving rise to the product and the coproduct
\beqa
\alpha \ast' \beta &=& sh(\alpha, \bar{\beta}) \ , \\
\Delta'\alpha&=&\mathop{\sum}\limits_{\alpha=uv} st(u)\otimes st(v) \ .
\eeqa
The dual Hopf algebra $(\S,\ast^\prime, \Delta^\prime)$
is isomorphic to  the algebra of the free quasi-symmetric functions $\bf FQSym$ \cite{DHT}.
Throughout this paper we will be dealing only  with the bialgebra
structures of $\S$, for the explicit formulas for the antipode see
\cite{AS}.

\section{Poirier-Reutenauer Hopf algebra}
The celebrated Robinson-Schensted algorithm \cite{K} establishes a one-to-one correspondence between  permutations $\alpha$ and pairs $(P,Q)$ of Standard Young Tableaux (SYT) of the same form
$$
RS: \S \rightarrow SYT\times SYT \qquad  RS: \alpha \mapsto (P(\alpha),Q(\alpha)) \ .
$$
Two  permutations $\alpha$ and $\beta$ are $P$-equivalent, i.e., $P(\alpha)=P(\beta)$,
if and only if their words are congruent $\alpha \sim \beta$ with respect to the plactic congruence generated by the Knuth equivalence relations \cite{K} (without repeating letters)
\beq
bac \sim bca \qquad  acb\sim cab  \qquad a<b<c \ .
\eeq

\begin{deff}Let
$Tab$ be  the quotient $ Tab:= \S / \mathfrak K$
where
 $\mathfrak K$ is the ``Knuth'' submodule of $\S$ generated by the elements $\alpha -\beta$,
$\alpha,\beta \in \S$, such that $\alpha \sim \beta$.
\end{deff}
To any $t\in SYT$ we can associate its plactic class $c(t)$, which is the sum of
the elements in $\alpha\in \S$, such that $P(\alpha)=t$
\beq
\label{plcl}
c(t) = \sum_{\alpha: t=P(\alpha)} \alpha \,\,  \subset \S \ .
\eeq
\begin{deff}
Let us denote by $Tab' = \bigoplus_{t\in SYT} \, \Q \, c(t)$ the $\Q$-span of all plactic classes.
\end{deff}

Poirier and Reutenauer proved that the Malvenuto-Reutenauer Hopf structures on $\S$
induce Hopf structures on the $\S$-modules $Tab$ and $Tab'$.

\begin{thm}\cite{PR}.
The submodule $\mathfrak K$ of $\S$ is an ideal and a coideal of $(\S,\ast,\Delta)$.
The quotient $ Tab $
is a  Hopf\, factor-algebra $(Tab, \ast, \Delta)$.
\label{tabiso}
\end{thm}

\begin{thm}\cite{PR}. The submodule $Tab' \subset \S$ is a Hopf subalgebra $ (Tab',\ast',\Delta')$
of the Hopf algebra $ (\S,\ast',\Delta')$.
The Hopf algebras $(Tab,\ast,\Delta)$  and $ (Tab',\ast',\Delta')$ are canonically dual.
\end{thm}

The Hopf subalgebra $ (Tab',\ast',\Delta')$ of the Malvenuto-Reutenauer algebra $(\S,\ast',\Delta')$ is isomorphic to  the algebra
of the free symmetric functions $\bf FSym$ \cite{DHT}.

\section{Pre-Plactic Hopf Algebra}

Let $u\in \S_p$ and $v\in \S_r$ be (the words of) two permutations.
We denote by $\mathfrak I$ the  two-sided ideal $\I$   in $\S$ generated by elements
\beq
\label{}
u[b[ac]]v:=u( bac - bca - acb + cab)v \in \Z[\S_{p +3+r} ]
\qquad a<b<c
\eeq
The relations in the ideal are among the
relations of the quantum pseudo-plactic algebra $\PP_q(W)$,
namely the multilinear part of the ideal $\I_q(W)$ and $\I(W)$.
The idea is to have a kind of  ``operadic approach" to the
algebra $\PP_q(W)$.

\begin{lemma} The submodule $\mathfrak I\subset \S$ is a Hopf ideal of the Hopf algebra $(\S, \ast, \Delta)$.
\end{lemma}
{\bf Proof.}
The ideal $\mathfrak I$ is generated in $\Z[\S_3] \subset \S$
by the element $[2[13]]$. By definition it is a graded ideal
$\mathfrak I=\oplus_{n\geq 0} \mathfrak I(n)$ with degrees
\beq
\label{ideal}
\mathfrak I(n)= \sum_{i,j:i+j+3=n} \Q[ \S_i] \ast [2[13]] \ast \Q[  \S_j] \subset \Q[\S_n] \qquad \Rightarrow \qquad
\mathfrak I= ([2[13]]) \ .
\eeq
 The module $\mathfrak I$ is a submodule of the  module $\mathfrak K$, having as generators differences of the ``Knuth" generators in
$\mathfrak K$ hence the inclusions of submodules $\mathfrak I \subset \mathfrak K \subset \S$. It is easy to see that
$\mathfrak I$ is also coideal with respect to $\Delta.$
{${\Box}$}

\begin{deff}
\label{prep}
 The pre-plactic algebra $\PP$ is
the quotient Hopf algebra $\S/\mathfrak I$
$$\PP:=\S/ ([2[13]]) \ .$$
\end{deff}

The factor algebra $\PP$ inherits the grading of $\S$,
\[
\PP = \bigoplus_{n\geq 0} \PP(n) = \bigoplus_{n\geq 0} \Q[\S_n ]/ \mathfrak I(n) \ .
\]

We are going to calculate the dimensions $\dim \PP(n)$.
To this end we  take up with the dimensions of the graded ideal
$\mathfrak I$. We first introduce some notations about partitions.

Let $\lambda=(\lambda_1, \ldots, \lambda_k)$ be a
partition $\lambda_1\geq \lambda_2\geq \ldots \geq\lambda_k>0$ with
 $r$ nonzero parts.  The graphic representation of $\lambda$ is the Young diagram
whose $i$-th row is of length $\lambda_i$, $i=1,\ldots,k$.
By $\lambda'$ we denote the diagram transposed to
$\lambda$.
A dual description $\lambda=[1^{m_1}2^{m_2}\ldots
k^{m_k}]$ is provided by the multiplicities $m_i(\lambda)=\lambda'_i-\lambda'_{i+1}$  yielding the number of rows of length $i$. One has $|\lambda|=\sum_{i=1}^k i \, m_i(\lambda)=
\sum_{i=1}^k \lambda_i$ with $k=\sum m_i(\lambda)$.

\begin{prop} The dimensions of the  graded ideal $\mathfrak I=\bigoplus_{n\geq 0} \mathfrak I(n)$ are counted by

\beq
\label{my}
\dim \mathfrak I(n)=
{\sum_{ k >0 }} \,\,
 {\sum_{\scriptsize\ba{c}{\Lambda}\vdash
 n \\  \Lambda \neq 1^n\ea}} (-1)^{1+(|{\Lambda}|-k)/2}
\frac{k!}{ \prod_{i=1}^k{m_i({\Lambda}) !}}
\frac{n!}{\prod_{i=1}^k  {\Lambda}_i!}
\eeq
where the sum runs
over all partitions ${\Lambda}=({\Lambda}_1, \ldots, {\Lambda}_k)$ of $n$ with $k$ odd parts ($\Lambda_i=2\lambda_i+1$)
except the partition $\Lambda=1^n$.

\end{prop}
{\bf Proof.}
Our strategy in counting the dimension
$\dim \mathfrak I(n)$ is a recurrent use of the formula for the dimension of an intersection
\beqa
\label{inter}
\dim \sum_{\alpha} A_\alpha&=& \sum_{\alpha} \dim A_\alpha - \sum_{\alpha_1<\alpha_2}
\dim A_{\alpha_1}\cap A_{\alpha_2}  + \sum_{\alpha_1<\alpha_2<\alpha_3}
\dim A_{\alpha_1}\cap A_{\alpha_2} \cap A_{\alpha_3}  \nonumber
\\ &-&  \ldots
+ (-1)^{l+1} \dim A_{\alpha_1}\cap A_{\alpha_2}\cap A_{\alpha_3} \cap \ldots
 \cap A_{\alpha_l}
\eeqa
where the  family of spaces $\{ A_\alpha\}$
such that
$\mathfrak I(n) = \sum_{\alpha} A_\alpha$
is indexed by a finite ordered set
of cardinality  $l$.

We put  into correspondence  the composition $c=1^i31^j$
of $n=i+j+3$
with the subspace $A_c=\Q[ \S_i] \ast [2[13]] \ast \Q[  \S_j]\subset \mathfrak I(n)$.
It is convenient  to set $A_1:=\Q[\S_1]$ then one has
$$A_{1^j}
= A_1^{\ast j}=  \Q[\S_j] \qquad A_3=\Q [2[13]
$$
where $A_3$ is identified with the generator of the ideal $\mathfrak I= ([2[13]])$.
With the new conventions the   expression (\ref{ideal}) for the
graded  ideal takes the succinct form
\beq
\label{ideal1}
\mathfrak I(n)=
\sum_{i=0}^{n-3} A_{1^j} \ast A_3 \ast A_{1^{n-3-i}}=\sum_{i=0}^{n-3}  A_{1^i31^{n-3-i} }  \ .
\eeq

\begin{lemma}
\label{zeroint}
The neighboring subspaces of $\mathfrak I(n)$
in the sum eq.(\ref{ideal1}) have zero intersection
\beq
\label{gint}
A_{1^k31^{l+1}}\cap A_{1^{k+1}31^l}=\emptyset \ .
\eeq
\end{lemma}
{\bf Proof of the lemma.}
The  $\S_4$-module $\mathfrak I(4)$ is a sum of two subspaces $\mathfrak I(4)=A_{31}+A_{13}$ and its dimension
is given by the intersection formula eq. (\ref{inter})
\[
\dim \mathfrak I(4)=\dim A_{31}+ \dim A_{13} -
\dim  A_{13}\cap A_{31}  \ .
\]
One can write explicitly the basis of $A_{31}=A_3 \ast A_1$,
it consists of the four elements in $\Q [\S_4]$
\[
r_1 =[[13]2]4 \qquad r_2=[[14]2]3 \qquad r_3=[[14]3]2 \qquad
r_4=[[24]3]1
\]
whereas the basis of $A_{13}=A_1\ast A_3$ is spanned by
\[
l_1=4[[13]2] \qquad l_2=3[[14]2] \qquad l_3=2[[14]3] \qquad l_4=1[[24]3] \ .
\]

An element $w$ belongs to the  intersection
$A_{13} \cap A_{31}$ when it can be represented
$w= \sum_i c_i l_i=\sum_i d_i r_i $
with  coefficients $c_i$ and $d_i$.
However the only solution turns out to be $c_i=0=d_i$.
We conclude that the intersection is
empty,
\[A_{13}\cap A_{31}=\emptyset \ . \]

The $\S_5$-module $\mathfrak I(5)$ is  in the linear
enveloppe of three subspaces,
$$\mathfrak I(5)=A_{1^23}+A_{131}+A_{31^2}$$
and the vanishing $A_{13}\cap A_{31}=\emptyset$
readily implies
 the zero intersections $A_{1^23}\cap A_{131}=\emptyset$
and $A_{131}\cap A_{31^2}=\emptyset$.

The statement eq.(\ref{gint}) follows by induction of the degree $\mathfrak I(n)$
of the ideal $\mathfrak I$. $\Box$

However the intersection $A_{1^23}\cap A_{31^2}$ is not trivial
(see Lemma \ref{int} below).

Let us  introduce some concise notations for the intersections
$$
A_{1^23}\cap A_{31^2} =:A_5\qquad
A_{31^3}\cap A_{1^231} =: A_{51} \qquad
A_{31^3}\cap A_{1^33} =: A_{33} \ .  $$
Then the latter lemma implies the succinct expressions of
the dimensions
\beq
\ba{ccl}
\dim \I(i) &= &0 \qquad i<3 \\
\dim \I(3) &= &\dim A_3 \\
\dim \I(4) &= &\dim A_{31}+ \dim A_{13}\\
\dim \I(5)&=&\dim A_{31^2}+\dim A_{131} +\dim A_{1^23}
- \dim A_5 \\
\dim \I(6)&=&
\dim A_{31^3}+ \dim A_{131^2} + \dim A_{1^231} + \dim A_{1^33}
 \\ &&
-\dim A_{51} - \dim A_{15} - \dim A_{33}
 \ea
\eeq
A non-trivial (maximal) intersection
$A_7:= A_{31^4} \cap A_{1^231^2} \cap A_{1^43}$
will appear in $\I(7)$.
In general on any odd degree $2k+1$  an intersection
of $k$ subspaces
takes place.

\begin{lemma}
\label{int}
Let the space   $A_{2n+1}$ be the  intersection of $n$
subspaces\footnote{
Note that only next to neighboring terms from the sum
$\I(2n+1)=\sum A_{1^k3 1^{2n-2-k}}$

appear in the intersection, as the intersections
of neighboring terms is empty due to lemma \ref{zeroint}.}
$A_{1^k31^{2n-k-2}}$
\beq
\label{odd}
A_{2n+1}:=A_{31^{2n-2}}\cap A_{1^231^{2n-4}}\cap
A_{1^431^{2n-6}}\cap \ldots \cap A_{1^{2n-2}3} \in \I(2n+1) \ .
\eeq
The intersection $A_{2n+1}$ is maximal in $\I(2n+1)$
and it is one dimensional
\[
\qquad \dim A_{2n+1}=1 \ .
\]
\end{lemma}
{\bf Proof of the lemma.} For $n=1$ the
spatement of the lemma is trivial
\[
\dim \I(3) = \dim A_3 =1 \ .
\]

The first non-trivial statement
is for the space $A_5$.
For a commutative algebra with three generators $x,y,z$
 one has the antisymmetric combination
\beq
\label{xyz}
x\wedge y\wedge z:=x[yz]+y[zx]+z[xy]=[yz]x+[zx]y+[xy]z
\eeq
which spans a one dimensional space. Note that
the generators $x=[15]$, $y=[24]$ and $z=3$ in $\PP(5)$
commute\footnote{ The relation
$[[15],[24]] = [[[15] 2]4]+ [2 [[15]4]]$ is implied by the Jacoby identity.} and  generate a maximal commutative subalgebra.
Hence we have a one dimensional subspace
\[
[15]\wedge[24]\wedge 3 \in \I(5) \ .
\]

The following element belongs to the intersection $A_5=A_{1^23}\cap A_{31^2}$
\[
[15][[24]3]+ [24][3[15]] \equiv
[[24]3][15]+[3[15]][24] =[15]\wedge[24]\wedge 3
\quad mod \quad [[15][24]] \ .
\]
The relation
$[[15],[24]] $ can be represented also as $[15]\wedge[24]$
thus for the intersection space we get
\[
A_5=A_{1^23}\cap A_{31^2}= \Q [15]\wedge[24]\wedge 3
\quad mod \quad [15]\wedge[24]  \ .
\]
Therefore $A_5$ belongs to the ideal $\mathfrak I(5)$ and  it is one dimensional
\[
\dim A_5=1 \ .
\]
So we have proven the lemma when $n=2$.

We proceed by induction.
 In $\mathfrak I(6)$  the maximal commutative subalgebra
is generated by $[16]$, $[25]$ and $[34]$. Hence
according to eq.  (\ref{xyz}) we get the antisymmetrized combination
$[16]\wedge [25]\wedge [34] \in \mathfrak I(6)$
which generates between others the following relations in $\PP(7)$,
\[

4[17]\wedge [26]\wedge [35] \in \I(7) \qquad [17]\wedge [26]\wedge [35]4 \in \I(7) \ .
\]
The maximal commutative subalgebra is $\PP(7)$ is generated by
the ``long'' generators
$[17]$, $[26]$, $[35]$ and the ``short'' generator  $4$.
The commutative subalgebra
gives rise to  the space
\[
[17]\wedge[26]\wedge[35]\wedge 4 \quad mod \quad
[17]\wedge[26]\wedge[35]
\]
which belongs to
the one-dimensional  intersection $A_7=A_{31^4}\cap A_{1^231^2}\cap A_{1^43}$.

By induction on $n$  we obtain an unique element
in the $\S_{2n+1}$-module $\mathfrak I(2n+1)$
\[
[1 \,2n+1]\wedge [2 \, 2n] \wedge \ldots \wedge [n\, n+2]
\wedge
n+1    \ ,
\]
which after factoring gives rise  to
the intersection space (\ref{odd})
\[
A_{2n+1}=\Q [1 \,2n+1]\wedge [2 \, 2n] \wedge \ldots \wedge [n\, n+2]
\wedge
n+1 \quad mod \quad
[1 \,2n+1]\wedge [2 \, 2n] \wedge \ldots \wedge [n\, n+2]
\ .
\]
We are done with the lemma. $\Box$

From the above examples the general pattern for $\dim \mathfrak I(n)$ is clear, we have summation with alternating signs  over
the dimensions of subspaces $A_c =
A_{ c_1}\ast \ldots \ast A_{ c_k}\subset \Q[ \S_n]$
 labelled by  compositions $c$ of $n$ having only odd parts
\[
\dim \mathfrak I(n) = \sum_{c: |c|=n} \pm \dim A_c
\]
where the sum is over all compositions of $n$ with odd parts
(except $c=1^n$) and the sign $\pm$ is $(-1)^{k+1}$ if
$A_c$ stems from intersection of $k$ elementary subspaces $A_{1^i31^{n-3-i}}$.

Subspaces $A_{c}$ and $A_{c'}$ whose compositions  after ordering are mapped to the same partition $\Lambda$
will have same dimension $\dim A_{c} =\dim  A_{c'}= \dim A_{\Lambda}$. Therefore the sum over compositions $c$ can be replaced
by the sum over partitions $\Lambda$ at the expense of the multiplicities
\[
\dim \mathfrak I(n) = \sum_{k> 0}
{\sum_{\scriptsize\ba{c}{\Lambda}\vdash
 n \\  \Lambda \neq 1^n\ea}} \pm  \frac{k!}{\prod_{i=1}^k m_i(\Lambda) !} \dim A_{\Lambda}
\]

Since $\dim A_{2i+1}=1$,
the dimension of a subspace $A_\Lambda =
A_{\Lambda_1}\ast \ldots \ast A_{\Lambda_k}\subset \Q[ \S_n]$ is
\[
\dim A_\Lambda = \frac{n!}{\prod_{i=1}^k \Lambda_i!}
\qquad |\Lambda|=n \ .
\]
Any subspace $A_{\Lambda_i}=A_{2\lambda_i+1}$ is in the intersection of $\lambda_i$ elementary subspaces
$A_{1^i31^j}$
hence the subspace $A_\Lambda$
lays in the intersection of $\sum_{i=1}^k \lambda_i$ subspaces.
The summation over partitions  $\Lambda$ having only odd parts is equivalent to the summation over partitions $\lambda$ (skipping
the empty diagram $\lambda=0$ corresponding to $\Lambda\neq 1^n$). The alternating sign factor is
fixed by the number of intersections
$\sum_{i=1}^k \lambda_i=(|\Lambda|-k)/ 2$.
These observations  together yields
the final expression eq.(\ref{my}).

\section{Counting snakes and pre-plactic algebra}

The term ``snake" for an alternating permutation was coined by
 Vladimir Arnold \cite{Arnold}.

\begin{deff} An alternating permutation or {\it snake} is a permutation
  $$\sigma=\left(\ba{cccc}1 &2 &\ldots& n \\
	\sigma_1&\sigma_2 & \ldots& \sigma_n\ea\right)\in \S_n \qquad \mbox{such that}\qquad \sigma_1>\sigma_2<\sigma_3>\ldots \ .$$
		The word of the permutation $\sigma$ is the word
	$\sigma_1 \sigma_2 \ldots\sigma_n$.
	We denote by $E_n$ the number of snakes,
	$E_n=\#\{\sigma\in \S_n| \sigma_1>\sigma_2<\sigma_3>\ldots\}$.
\end{deff}

The alternating permutations are counted by D\'esir\'e Andr\'e \cite{Andre}. Their number is generated
by the series $$y(x):=\sum_{n\geq 0} E_n\frac{x^n}{n!}=\sec x + \tan x$$
satisfying the equation\footnote{For a survey on alternating permutations see \cite{Stanley}}
\beq
\label{sny}
 2y'=y^2 +1 \qquad y(0)=1 \ .
\eeq

 Arnold also  referred to  the numbers $E_n$ as to   Bernoulli-Euler numbers for the following reason:
the Euler numbers $E_{2n}$ appear from the expansion of
$$\sec x= \sum_{n\geq 0} E_{2n}\frac{x^{2n}}{(2n)!}$$
whereas the {\it tangent numbers} $E_{2n+1}$
$$
\tan x = \sum_{n\geq 0} E_{2n+1}\frac{x^{2n+1}}{(2n+1)!}
$$
are related to the Bernoulli numbers $E_{2n+1}=B_{2n}\frac{4^n(4^n-1)}{2n}$. Arnold introduced ``snakes" for other Coxeter groups
than $A_n$, their numbers
are topological invariants of bifurcation diagrams \cite{Arnold}.

We found an expression of the snakes numbers $E_n$
through summation over Young partitions which to the best of
our knowledge is new.

\begin{prop}
The number of snakes
 is given by the formula
\beq
\label{BE}
\frac{E_{n+1}}{n!}=\sum_{k > 0}
 \sum_{\Lambda \vdash n }  \frac{(-1)^{(|\Lambda|-k)/2}k!}{\prod_{i=1}^k  \Lambda_i ! \prod_{i=1}^k{m_i(\Lambda) !}}\qquad \mbox{with} \qquad \Lambda_i= 2 \lambda_i + 1
\eeq
where the sum is over all partitions $\Lambda$ of $n$ with
only odd parts.
\end{prop}

{\bf Proof.} Differentiating the generating series $y(x)$ one gets
\[
y^\prime(x)=\sum_{n=0}^\infty E_{n+1} \frac{x^n}{n!}
=\frac{1}{1-\sin x}
= \sum_{k\geq 0} \sin^k x=
\sum_{k\geq 0} \left(\sum_{\lambda=0}^\infty
(-1)^{\lambda} \frac{x^{2\lambda +1}}{(2\lambda+1)!} \right)^k
\]
The result follows by the binomial expansion and
equating the coefficients of $x^n$.$\Box$

We are now ready to prove the main result of this paper
namely the snakes numbers are the coefficients in
 the generating series for the $\S$-module $\PP$.

\begin{thm}
The generating series of the $\S$-module $\PP=\bigoplus_{n\geq 0} \PP(n)$
is given by
\[
\sum_{n\geq 0}\dim \PP(n)\frac{x^n}{n!}
=
\sum_{n=0}^\infty E_{n+1}\frac{x^n}{n!} \ .
\]
\end{thm}
{\bf Proof.} The homogeneous degree $\PP(n)$ of the pre-plactic algebra is
 $\PP(n)=\Q[\S_n]/\mathfrak I(n)$ hence
\beq
\label{match}
\dim \PP(n) = n!- \dim \mathfrak I(n) \ .
\eeq
The dimension of the ideal  $\dim \mathfrak I(n)$ was
found in  eq. (\ref{my}) from where we get
\[
\dim \PP(n)=
{\sum_{ k >0 }}\,\,
 \sum_{{\Lambda}\vdash
 n } (-1)^{(|{\Lambda}|-k)/2}
\frac{k!}{ \prod_{i=1}^k{m_i({\Lambda}) !}}
\frac{n!}{\prod_{i=1}^k  {\Lambda}_i!}  \ .
\]
Note that by removing the restriction $\Lambda\neq 1^n$ in eq. (\ref{my}) we incorporated the extra  term $n!$ in $\dim \PP(n)$
We now realize that the expression for $\dim \PP(n)$
  coincides with the formula eq. (\ref{BE}) for the snakes number
$E_{n+1}$
which readily implies the result $\dim \PP(n)=E_{n+1}$.

\section{Hopf structure and Hilbert-Poincar\'e Series}

{\bf Tensor algebra.}
The free associative algebra $T(V)$ generated by $D$-dimensional
vector space $V$ is naturally a  $GL(V)$-module.
Its character reads
\[
ch_{T(V)}(x)=\frac{1}{1-(x_1+ \ldots + x_D)}= \sum_{n\geq 0} (x_1+ \ldots + x_D)^n = \sum_\lambda s_\lambda(x) f^\lambda \ .
\]

By Schur-Weyl duality the image of
$T(V)=\bigoplus_{n\geq 0} V^{\otimes n}$ is the $\S$-module
$\S=\bigoplus_{n\geq 0} \S_n$
with generating series
\beq
\label{cs}
g_{\S}(x)=\frac{1}{1-x} = \sum_{n\geq 0} n!\frac{x^n}{n!}=
\exp \ln \frac{1}{(1-x)} = \exp \sum_{k\geq 1} \frac{x^k}{k}=
\exp \sum_{k\geq 1} (k-1)!\frac{x^k}{k!}
\eeq
where $(k-1)!$ is the dimension of the
space $Lie(k)\subset \Q[\S_k]$ of primitive Lie elements.

\noindent
{\bf Parastatistics algebra $PS(V)$.}
The universal enveloping algebra (UEA) of the  two step nilpotent Lie algebra
$PS(V):=U(V\oplus\wedge^2 V)$ arises in the parastatistics Fock spaces \cite{D-VP} and it will be referred to as the {\it parastatistics algebra} $PS(V)$. The algebra
\[
PS(V) = T(V)/([[V,V],V])
\]
is a factor algebra of the tensor algebra $T(V)$ by the two-sided
ideal generated in $Lie(V)_3:=[[V,V],V]$ which is also a Hopf ideal
for the standard Hopf structure on $T(V)$.
The character of the $GL(V)$-module $PS(V)$ is also representable
as the sum of all Schur polynomials
\beq
\label{sch}
ch_{PS(V)}(x)=\prod_{i=1}^D \frac{1}{(1-x_i)}
\prod_{1\leq i<j\leq D} \frac{1}{(1-x_i x_j)} = \sum_{\lambda} s_\lambda(x_1, \ldots, x_D) \ .
\eeq
The latter identity implies
that in the decomposition of $PS(V)$ into irreducible representation
every Schur module  apprears once and  exactly once,
$$PS(V)= \bigoplus_{n\geq 0} PS(n)\otimes_{\S_n} V^{\otimes n}
\cong \bigoplus_\lambda S_\lambda(V) \ .$$

The $\S$-module $PS=\bigoplus_{n\geq 0} PS(n) \cong \bigoplus_\lambda S_\lambda$ is the Schur-Weyl dual of the  $GL(V)$-module
$PS(V) $. The dimension  of the irreducible $\S_n$-module $S_\lambda$
is the number $f_\lambda$ of  the Standard Young tableaux of shape
$\lambda$, $f_\lambda:=\dim S_\lambda$.
Hence the generating series of the Standard Young Tableaux
yields the generating series of the $\S$-module $PS$
\beq
\label{css}
g_{PS}(x)=\exp \left({x+ \frac{x^2}{2}}\right)=\sum_{n\geq 0} x^n\sum_{\lambda \vdash n} f_\lambda  \ .
\eeq

\noindent
{\bf Plactic algebra $\Pl(V)$.}
The plactic algebra $\Pl(V)$ turns out to be a ``crystal" limit
of a quantum deformation $PS_q(V)$ on the parastatistics algebra
$PS(V)$ for the singular value $q=0$ of the deformation parameter,
$\Pl(V)= PS_0(V)$ \cite{LP2}. The deformed algebra $PS_q(V)$
is a module of the quantum UEA $U_q \mathfrak gl_D$.
 The irreducible $U_q \mathfrak gl_D$-modules are the quantum Schur modules $S_\lambda^q(V)$ having the same dimensions as the Schur modules $S_\lambda(V)$. Hence the character formula (\ref{sch})
gives also the multi-graded dimensions of the deformed algebra $PS_q(V)$  and its specialization: the plactic algebra $\Pl(V)$
\[
ch_{PS(V)}(x)=ch_{PS_q(V)}(x)=ch_{\Pl(V)}(x)
\]

By quantum Schur-Weyl duality to the  $U_q \mathfrak gl_D$-module
 $$PS_q(V)=
\bigoplus_{r\geq 0} PS_q(r)\otimes_{\hr} V^{\otimes r}
\cong \bigoplus_\lambda S^q_\lambda(V)  $$ one attaches the Hecke algebra modules
$PS_q\cong \bigoplus_\lambda S_\lambda^q$.

The Poirier-Reutenauer algebra can be seen as the $q=0$ limit
of direct sum of Hecke algebra modules \cite{LP3}.
 The plactic classes (\ref{plcl}) close a commutatuve
Hopf subalgebra (with respect to the shuffle) of the Malvenuto-Reutenauer algebra . Thus the generating series (\ref{css}) is also counting the plactic classes which span the Poirier-Reutenauer algebra $Tab^\prime$
\[
g_{PS}(x)= g_{PS_q}(x)=g_{Tab}(x) \ .
\]

The  series eq.(\ref{css}) is a truncation of the generating series
$\exp \sum_{k\geq 1} \frac{x^k}{k}$  of $\S$
reflecting  the factorization of the free Lie algebra
to the two-step nilpotent Lie algebra.
As a digression we now prove an identity which is one more truncation of the generating series  of $\S$
\begin{lemma}
 The snake numbers satisfy the  identity

\beq
\label{ide}
\sum_{n\geq 0} E_{n+1}\frac{x^n}{n!} =
\exp {\sum_{n\geq 1} E_{n-1}\frac{x^n}{n!}}  \ .
\eeq
\end{lemma}
{\bf Proof.}  The number of alternating permutations
$E_n$ is generated by the series $y(x)=\sec x + \tan x$
which is a solution of the equation $2y^\prime = y^2+1$. The identity is equivalent
to the following integro-differential equation
\beq
\label{intdif}
 y^{\prime}(x)  =\sum_{n\geq 0} E_{n+1} \frac{x^n}{n!}=
\exp {\int_0^{x} y(t)dt}
\eeq
for the generating series $y(x)=\sum_{n\geq 0} E_n\frac{x^n}{n!} =\sec x + \tan x$ of  the snakes numbers $E_n$.

Indeed the differention of the eq. (\ref{intdif}) yields
\[
 y^{\prime\prime}(x) = y(x)\exp {\int_0^{x} y(t)dt}\qquad
\Rightarrow \qquad
y^{\prime\prime} =yy^\prime  \qquad \Leftarrow \qquad (2 y^\prime)^{\prime} = (y^2+1)^\prime
\]
which is the same as the differentiation of the equation
(\ref{sny}) for the generating function $y(x)$ of the snakes numbers.
$\Box$

\noindent
{\bf Pre-plactic algebra $\PP$ and  pseudo-plactic algebra $\PP(W)$.}
The left hand side of the   identity (\ref{ide})
is
the generating series of the pre-placitic  algebra $\PP$.
Then the natural interpretation of the numbers in the exponent
of the identity (\ref{ide}) is as dimensions of
the space of primitive Lie  elements  ${\prPP}(n)$
of the Hopf algebra $\PP$
\[
g_{\PP}(x)=\sum_{n\geq 0} \dim \PP(n)\frac{x^n}{n!}
=\exp \left( {\sum_{n\geq 1} \dim \prPP(n)\frac{x^n}{n!}}\right) \ .
\]
The Malvenuto-Reutenauer algebra $\S$ is a Hopf algebra which
is not cocommutative and it is not an UEA of its Lie algebra.
The primitive elements of $\S$ with respect to $\Delta$ are indexed by the connected permutations \cite{DHT, PR}.
However among the primitives of $\S_n$ we single out the Lie
primitives which are Lie elements $Lie(n)$, $\dim Lie(n)=(n-1)!$.
Some of these primitive elements are in the ideal of $\PP(n)$
but the identity (\ref{ide}) that the dimension
 of the non-vanishing
Lie elements  ${\prPP}(n)$ is given  by the snake number $E_{n-1}$.
To set the  bijection between alternating permutations and some
commutative subalgebra of (pre-plactic) classes in $(\S,\ast^\prime, \Delta^\prime)$ is an interesting open problem that we hope to address in a near future.

{In summary, snakes numbers yields the dimensions of both
the factorizable and nonfactorizable (primitive) elements
of $\PP$.  Hence the Hopf algebra $\PP$ is a categorification
of the snakes numbers in the same fashion as
the Malvenuto-Reutenauer Hopf algebra is a categorification
of the factorial numbers $n!$.

\begin{thm} The character of the $GL(V)$-module $\PP(W)$
is given by
\beq
ch_{\PP(W)}(x_1, \ldots, x_D) =
{\prod_{n=1}^{\infty} \prod_{1\leq i_1<\ldots < i_n\leq D}
{(1-x_{i_1} x_{i_2}\ldots x_{i_n})^{-E_{n-1}}} } \ .
\eeq
It coincides with the character of
the $U_q \mathfrak{gl}_D$-module $\PP_q(W)$
\[
ch_{\PP(W)}(x_1, \ldots, x_D) =ch_{\PP_q(W)}(x_1, \ldots, x_D)  \ .
\]
\end{thm}
{\bf Proof.}
The primitive Lie elements $[[a,b],a]$ and $[b,[a,b]]$, $1\leq a<b\leq D$ with repeating letters are  generators of the ideal $\I(W)$ of $\PP(W)$. Hence any bracketing of Lyndon words with repeating letter is in the ideal $\I(W)$. Therefore the non-vanishing  primitive Lie elements in $\prPP(V)_n$ stem from Lyndon words
of length $n$  without repeating letter (from the alphabet
$\{x_1, \ldots, x_D\}$).
Then the Poincar\'e-Birkhoff-Witt theorem implies the expression for the character $ch_{\PP(W)}(x_1, \ldots, x_D)$. The
character $ch_{\PP_q(W)}(x_1, \ldots, x_D)$ is the same
since $\PP_q(W)$ is a deformation of $\PP(W)$.

\begin{cor}
The Hilbert series of the pseudo-plactic algebra $\PP(W)$
and $\PP_q(W)$ reads
\beq
H_{\PP(W)}(t)=
\prod_{n=1}^{\infty} {(1-t^n)^{-E_{n-1}{\tiny \left(\ba{c}\dim V\\n \ea\right)}} } \ .
\eeq
\end{cor}

\subsection*{Outlook and perspectives}
We designed the quantum pre-plactic algebra $\PP_q$ as a tool for proving the conjecture of Krob and Thibon about the isomorphism between the quantum pseudo-plactic algebra and the diagonal subalgebra of $\C[GL_q(V)]$ \cite{KT}. The sketch of this approach is given in the proceedings \cite{P}.

The pre-plactic algebra $\PP$ turn out to be an object with a rich combinatorial structure. An interesting open problem is to construct bijection between  snakes and the  primitive Lie elements in $\PP$. Another problem is to clarify the connection between the
pre-plactic algebra $\PP$ and the non-commutative trigonometric
functions in $\bf FQSym$ \cite{NCsnakes} realization of snakes
of type $A$. More distant goal will be to study the diagonal subalgebra of functions on quantum groups
$\C[SO_q(n)]$ and $\C[Sp_q(2n)]$  and how they are related to the Arnold's snakes of type $B$ and $D$.

\subsection*{Acknowledgement}
It is my pleasure to thank Anton Alekseev,
Peter Dalakov, Tekin Dereli, Michel Dubois-Violette,
 G\'erard Duchamp, Ludmil Hadjiivanov
and Oleg Ogievetsky for their interest in that work and for many inspiring discussions.
This work
has been supported  by Grant DFNI T02/6 of the Bulgarian National Science Foundation, TUBITAK 2221 program
and  a Ko\c c University grant.


\section{Introduction}

A homeomorphism $\phi$ from a closed orientable surface $S_g$ to itself is called \textit{pseudo-Anosov} if there is a pair of transverse measured folations $\mathcal{F}_s$ and $\mathcal{F}_u$ of $S_g$ in which $\phi$ stretches $\mathcal{F}_u$ by a real number $\lambda > 1$, and contracts $\mathcal{F}_s$ by a factor of $\lambda^{-1}$. The number $\lambda$ is known as the \textit{stretch factor} of $\phi$. Thurston showed in \cite{MR956596} that the stretch factor of any pseudo-Anosov map is an algebraic unit whose degree over $\mathbb{Q}$ is bounded above by $6g-6$. It is an open problem as to exactly which algebraic units appear as stretch factors of pseudo-Anosov maps.

\vspace{1em}
There are several well known constructions of pseudo-Anosov maps. Thurston provided a construction, known as \textit{Thurston's construction}, which describes pseudo-Anosov maps as products of Dehn twists around simple closed curve that divide the surface into disks. We will give an overview of this construction in the next section but for a more complete treatment see either \cite{FLP}, Expos\'e 13, or  \cite{MR2850125}. In \cite{MR930079}, Penner describes another construction involving products of Dehn twists. These constructions can produce the same pseudo-Anosov map but there are pseudo-Anosov maps that arise from one and not the other. In a recent paper \cite{MR3447112}, Shin and Strenner showed that if $\lambda$ is a stretch factor of a pseudo-Anosov map coming from Penner's construction then $\lambda$ does not have Galois conjugates on the unit circle. Whereas, Veech showed that if $\lambda$ is a stretch factor coming from Thurston's construction then $\mathbb{Q}(\lambda + \lambda^{-1})$ is a totally real number field, for which we provide a proof in the next section.

\vspace{1em}
In this paper we will focus on Thurston's construction, and a certain type of algebraic unit known as a \textit{Salem number}. Salem numbers have complex conjugates on the unit circle so they cannot arise as stretch factors from Penner's construction. On the other hand, there are Salem numbers that appear as stretch factors from Thurston's construction, and many of the smallest known stretch factors are Salem numbers. A natural question to ask is if we can get every Salem number as a stretch factor. We prove the following:

\vspace{1em}
\textbf{Theorem A.} \textit{For any Salem number $\lambda$, there are positive integers $k$ and $g$ such that $\lambda^k$ is the stretch factor of a pseudo-Anosov homeomorphism of $S_g$ arising from Thurston's construction, where $g$ depends only on the degree of $\lambda$ over $\mathbb{Q}$.}

\vspace{1em}
Since we know that $\mathbb{Q}(\lambda + \lambda^{-1})$ is a totally real number field when $\lambda$ is a stretch factor from Thurston's construction, it is natural to ask which totally real number fields arise this way. We also prove:

\vspace{1em}
\textbf{Theorem B.} \textit{Every totally real number field is of the form $K = \mathbb{Q}(\lambda + \lambda^{-1})$, where $\lambda$ is the stretch factor of a pseudo-Anosov map arising from Thurston's construction.}

\vspace{1em}
The structure of the paper is as follows: In section 2 we discuss Thurston's constructions, highlighting the information that will be relevant to results of the paper. In section 3 we discuss a new way of constructing a closed orientable surface from a nonsingular positive integer matrix. This will allow us to convert our algebraic results back into topological information, which will be important for proving both Theorem A and B. In section 4 we define Salem numbers and discuss their relation to Thurston's construction, then prove Theorem A in section 5. In sections 6 and 7 we develop some algebraic number theory and conclude by proving Theorem B.

\vspace{1em}
\textbf{Acknowledgements.} I would like to thank my advisor Darren Long for many helpful conversations and advice given as these ideas took shape. I would also like to thank Michael Dougherty and David Wen for listening to me talk at length about these results. Last, but not least, I would like to thank my wife Jacqueline for being my emotional support and for teaching me the basics of Adobe Illustrator so that I could make the graphics.

\section{Thurston's Construction}

In this section we give an overview of Thurston's construction of pseudo-Anosov maps. Our goal is to provide the basic framework of the construction and establish some of the key ideas that we will use in this paper. For a more in depth discussion see \cite{FLP}. We also provide a proof of the result from Veech that if $\lambda$ is a stretch factor of a pseudo-Anosov map arising from this construction then $\mathbb{Q}(\lambda + \lambda^{-1})$ is a totally real number field. We begin with the following definitions:

\begin{definition}
A \textit{multicurve} $C = \left\{ C_1, C_2,...,C_n\right\}$ on a surface $S$ is a union of finitely many disjoint simple closed curves on $S$. For the purposes of this paper we will also require that each $C_i$ is \textit{essential}, i.e., not isotopic to a point, and no two $C_i$'s are parallel, i.e., not isotopic.
\end{definition}

\begin{definition}
Let $C = \left\{ C_1, ..., C_n \right\}$ and $D = \left\{ D_1,...,D_m\right\}$ be a pair of multicurves on a closed orientable surface $S_g$. We say that $C \cup D$ \textit{fills} $S_g$ if every component of $S_g - (C \cup D)$ is a disk. We also say that $C$ and $D$ are \textit{tight} if $i(C_i,D_j) = |C_i \cap D_j|$, where $i(\cdot,\cdot)$ denotes the geometric intersection number.
\end{definition}

We will denote the Dehn twist about a simple closed curve $\alpha$ by $T_{\alpha}$, with the convention that we are twisting to the right with respect to the orientation of $S_g$. We now give an overview of Thurston's construction following the discussion given in \cite{Long}.

\begin{thm}[Thurston's Construction] Suppose that $C = \left\{ C_1,...,C_n \right\}$, $D = \left\{ D_1, ..., D_m\right\}$ are tight, filling multicurves on a closed, orientable surface $S_g$. To each $C_i \in C$ assign an integer $n_i > 0$ and to each $D_j \in D$ assign an integer $m_j > 0$. Then the maps
	\[
		\begin{array}{lcr}
				T_C = \displaystyle\prod_{i}T_{{C}_i}^{n_i} \hspace{.2in} & \textit{and} & \hspace{.2in} T_D = \displaystyle\prod_{j}T_{{D}_j}^{m_j}
			\end{array}
	\]
can be represented by matrices in PSL$(2;\mathbb{R})$ and any word $\theta = w(T_C,T_D)$ which corresponds to a hyperbolic class $[\theta] \in \text{SL}(2;\mathbb{R})$ is pseudo-Anosov with stretch factor the larger of the two eigenvalues.
\end{thm}

\vspace{1em}
The first step in this construction is to give a branched flat structure to $S_g$, that is, a way to view the surface as a flat manifold except at a finite number of points. We do this by describing a way of decomposing the surface into glued up rectangles. Let $C = \left\{ C_1,...,C_n\right\}$ and $D = \left\{ D_1,...,D_m\right\}$ be tight, filling multicurves on $S_g$. $C\cup D$ defines a cell structure on $S_g$ since the complement of $C \cup D$ is a union of disks. We define a dual cell structure of $C \cup D$ where we take a co-vertex for each cell, a co-edge for each edge, and a co-cell for each vertex. In a neighborhood of each vertex, we see four segments originating from the vertex so each co-cell will have four sides. We can think of the dual cell structure as placing rectangles on each vertex and then identify sides of the rectangles that have an arc of some $C_i$ or $D_j$ between them.

\begin{figure}[ht]
		\centering
	  \includegraphics[scale=.3]{Dualcomplex.pdf}
		\caption{A pair of tight, filling multicurves on $S_2$ with co-cells at each vertex.}
	\end{figure}

Assigning lengths to sides of the rectangles allows us to identify each co-cell with a rectangle in $\mathbb{R}^2$. So we can view $S_g$ as a union of these metric rectangles, hence we have given $S_g$ a branched flat structure.

\begin{figure}[ht]
		\centering
	  \includegraphics[scale=.3]{branchedflatstructure.pdf}
		\caption{$S_2$ as a union of rectangles.}
	\end{figure}

\newpage

There is quite a bit of choice for the length of the sides of each rectangle and this freedom can be used to show the following:

\begin{prop}Assign a positive integer $n_i$ to each $C_i \in C$ and a positive integer $m_j$ to $D_j$. Then there is a branched flat structure on $S_g$ for which both the maps $$T_C = \displaystyle\prod_{i}T_{C_i}^{n_i} \hspace{.1in} \textit{and} \hspace{.1in} T_D = \displaystyle\prod_{j}T_{D_j}^{m_j}$$ are affine.
\end{prop}

\vspace{1em}
By \textit{affine} we mean that lines in the branched flat structure are mapped to lines. The Dehn twists about the $C_i$ and $D_j$ act on the branched flat structure by skewing the rectangles, so we wish to find a choice for side lengths so that the slope of the sides after twisting $n_i$ times about $C_i$ is constant in $i$. Similarly, twisting $m_j$ times about $D_j$ is constant in $j$. We require that the height of each rectangle lying along $C_i$ to have constant height $h_i$ and that each rectangle lying along $D_j$ has constant width $\ell_j$. If we let $i(D_r,C_s) = Q_{rs}$ then it can be shown that $T_C$ is affine if
	\[\tan(\theta) = \displaystyle\frac{h_i}{n_i\displaystyle\sum_{r}\ell_rQ_{ri}} \hspace{.2in} \text{for all} \ i,\]
where $\theta$ is the angle between the image of the vertical edges along $C_i$ with the horizontal edges along $C_i$ after skewing by $T_C$. Similarly, the condition that $T_D$ is affine is
	\[\tan(\phi) = \displaystyle\frac{\ell_j}{m_j\displaystyle\sum_{s}h_sQ_{sj}} \hspace{.2in} \text{for all} \ j.\]

It can be shown that the choice of $\ell_j$ are from a Perron-Frobenius eigenvector with eigenvalue $\nu$ of the matrix $MQNQ^T$ where $Q_{ij} = i(D_i,C_j)$ and $M$ and $N$ are diagonal matrices whose diagonal entries are $m_j$ and $n_i$, respectively. The $h_i$ come from a Perron-Frobenius eigenvector, also with eigenvalue $\nu$, of the matrix $QNQ^TM$. These give dimensions of the rectangles in which $T_C$ and $T_D$ are affine. With our chosen convention of twisting, these lengths give the following representations (after some rescaling of the $\ell_i$):
\begin{align}
	[T_C] = \begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix} \hspace{.2in} \text{and} \hspace{.2in} [T_D] = \begin{bmatrix} 1 & 0 \\ -\nu & 1\end{bmatrix}
	\end{align}
which are matrices in $PSL(2;\mathbb{R})$. Now any word $\phi = w(T_C,T_D)$ such that $[\phi] \in SL(2;\mathbb{R})$ is hyperbolic ($|\text{tr($[\phi]$)}| > 2$) will be pseudo-Anosov. Since $[\phi]$ is hyperbolic it has two real eigenvalues, $\lambda$ and $\lambda^{-1}$, the stretch factor of $\phi$ is $|\lambda|$, and all lines parallel to the eigenspaces descend to transverse measured foliations on $S_g$. We end this section by proving the following:

\begin{thm}[Veech] If $\lambda$ is the stretch factor of a pseudo-Anosov map arising from Thurston's construction then $\mathbb{Q}(\lambda + \lambda^{-1})$ is a totally real number field.
\end{thm}

\begin{proof} Let $C$ and $D$ be tight, filling multicurves on a closed orientable surface, and let $M$, $N$ and $Q$ be nonnegative integer matrices defined as above.  Consider the matrix

	\[\Lambda = \begin{bmatrix}
									\mathbf{0} & M^{1/2}QN^{1/2}\\
									N^{1/2}Q^TM^{1/2} & \mathbf{0}
								\end{bmatrix}\]

$\Lambda$ is symmetric so it has real eigenvalues which means
	\[\Lambda^2 = \begin{bmatrix}
									M^{1/2}QNQ^TM^{1/2} & \mathbf{0}\\
									\mathbf{0}          & N^{1/2}Q^TMQN^{1/2}
								\end{bmatrix}\]
has nonnegative eigenvalues, hence $M^{1/2}QNQ^TM^{1/2}$ has nonnegative eigenvalues. Conjugating this matrix by $M^{1/2}$ gives $MQNQ^T$, thus $MQNQ^T$ has nonnegative eigenvalues. This tells us that $\nu$ is totally nonnegative, so $\mathbb{Q}(\nu)$ is totally real. Now if $\lambda$ is a stretch factor arising from the above construction then $\lambda$ is a root of degree 2 polynomial in $\mathbb{Q}(\nu)[x]$ of the form
	\[ x^2 -(\lambda + \lambda^{-1})x + 1\]
so $\lambda + \lambda^{-1} \in \mathbb{Q}(\nu)$, and therefore $\mathbb{Q}(\lambda + \lambda^{-1})$ is also totally real.
\end{proof}

\section{Constructing Surfaces from Positive Integer Matrices.}

In this section we describe a new construction in which we build a closed orientable surface $S$ from a nonsingular positive integer matrix $Q$, where on $S$ are two tight, filling multicurves $C$ and $D$ whose intersection matrix is $Q$. This construction serves as the central link between the algebraic results of this paper and topological ones. We will need it prove both Theorem A and Theorem B so we state and prove it here.

\begin{thm}
Given a nonsingular positive square integer matrix $Q$, there is a closed orientable surface $S$ with tight, filling multicurves $C =\left\{ C_1,...,C_n\right\}$ and $D = \left\{ D_1,...,D_n \right\}$ such that $Q_{ij} = i(D_i,C_j)$.
\end{thm}

\begin{proof} We start by taking $n$ rectangular strips where the $j$th strip is divided into $\displaystyle\sum_{i =1}^{n}Q_{ij}$ rectangles each oriented clockwise. Since the matrix $QQ^T$ is positive then it has a positive eigenvector with entries $\ell_i$. All vertical edges along the $j$th strip will have length $\ell_j$, where as $\ell_1$ will be the width of the first $Q_{1j}$ rectangles, and $\ell_2$ will be the width of the next $Q_{2j}$ rectangles, etc. We now take the central curve of each strip and call it $C_j$ for $j = 1,...,n.$

\vspace{1em}
Now we construct curves $D_i$ as follows: For a fixed $i \in \left\{ 1,...,n \right\}$ there are $Q_{ij}$ rectangles of size $\ell_i \times \ell_j$ lying along the $j$th strip, and we imagine a curve that passes from the top of the left most $\ell_i \times \ell_j$ rectangle through the bottom, then wraps back around the $j$th strip and passes through the next $\ell_i \times \ell_j$ rectangle and continues this way until it reaches the right most $\ell_i \times \ell_j$ rectangle. The curve then continues to the $j+1$st strip and wraps around each $\ell_i \times \ell_{j+1}$ rectangle in similar fashion. After the curve wraps around each strip it closes up, so we have a simple closed curve which we call $D_i$. This gives us gluing instructions where we glue two edges, matching orientation, if they are connected by an arc of some $D_i$. We also identify the two vertical sides of each strip.
\begin{figure}[h]
		\centering
	  \includegraphics[scale=.25]{cellstructure.pdf}
		\caption{A piece of the cell structure. Edges of different cells are identified if there is an arc of some $D_i$ between them.}
	\end{figure}

Since we glue these strips together where each edge is identified with another, always matching orientation, then we get a closed orientable surface $S$. The condition that the matrix be nonsingular ensures that no two rows are the same, which means that none of the $D_i$ intersect a $C_j$ in exactly the same way, so no two components of $C$ or no two components of $D$ are parallel. By construction, every intersection of $D_i$ with $C_j$ has the same sign so the geometric and algebraic intersection numbers of  these curves are the same. This ensures that no $D_i$ forms a bigon with any $C_j$, hence the multicurves $C = \left\{ C_1,...,C_n\right\}$ and $D = \left\{ D_1,...,D_n\right\}$ are tight. Finally, taking the dual cell structure gives a cell structure of $S$ whose vertices are the points of intersection between each $D_i$ and $C_j$, and whose edges are arcs of some $D_i$ or $C_j$. Hence, the complement of $C \cup D$ are disks, so $C$ and $D$ fill $S$.
\end{proof}

\textbf{Remark.} We can do this construction more generally where you label each box along a $C_j$ strip with some ordering of each of the $D_i$'s, making sure that $D_i$ appears $Q_{ij}$-times. Then you make some choice of how to connect the various $D_i$ boxes across each strip, keeping in mind that the intersections must all have the same sign to ensure there are no bigons. For example, you can have $D_1$ wrap around $C_1$ twice then hit $C_2$ once, then $C_3$ twice, back up to $C_1$ once, etc. until all the $D_1$ boxes have been connected. This will still give an orientable surface with $C$ and $D$ as tight filling multicurves that intersect the correct number of times. For this more general construction, the genus of the surface is difficult to ascertain as different choices in arranging the curves can change the surface you obtain. For the construction given in the proof of Theorem 3.1 we can explicitly find the genus.

\begin{prop}
Let $Q$ be a nonsingular positive integer $n\times n$ matrix whose entries are all greater than or equal to $2$. If $S$ is the closed orientable surface of genus $g$ obtained by following the construction given in the proof of Theorem $3.1$, then $g = n^2 - n + 1$.
\end{prop}

A proof of this is included in a forthcoming paper that will go into more detail about properties of this construction. For now we see that this gives an upper bound for the genus of the surface. If we us the general construction described in the above remark we should be able to find a smaller genus surface with tight, filling multicurves whose intersection matrix is $Q$. We end this section by asking the following question:

\begin{question} For a given nonsingular positive integer matrix $Q$, what is the minimum genus surface that can be constructed, using the general construction, having tight filling multicurves $C$ and $D$ where $Q_{ij} = i(D_i, C_j)$?
\end{question}

\section{Initial Observations}

In this section we define Salem numbers, and look at two situations relating Salem numbers to Thurston's construction. The first observation will show that Salem numbers arise as stretch factors of pseudo-Anosov maps coming from Thurston's construction, and the second will lead us to a strategy for proving Theorem A.

\begin{definition}
A real algebraic unit $\lambda > 1$ is called a \textit{Salem number} if $\lambda^{-1}$ is a Galois conjugate, and all other conjugates lie on the unit circle.
\end{definition}

From this definition we can deduce the following properties of Salem numbers:

\begin{prop}
Let $\lambda$ be a Salem number. Then,
	\begin{enumerate}
			\item $\lambda^k$ is a Salem number for any positive integer $k$.\\
			\item $\lambda + \lambda^{-1}$ is a totally real algebraic integer.\\
			\item The Galois conjugates of $\lambda + \lambda^{-1}$ lie in the interval $(-2,2)$.
		\end{enumerate}
	\end{prop}

Since $\lambda + \lambda^{-1}$ is totally real, it is at least plausible that there are Salem numbers that are stretch factors arising from Thurston's construction. The following observation gives conditions when a Salem number arises as a stretch factor from Thurston's construction.

\vspace{1em}
\textbf{Observation 1.} \textit{There are Salem numbers that arise as stretch factors of pseudo-Anosov maps arising from Thurton's construction.}

\vspace{1em}
Suppose you have two tight, filling multicurves $C$ and $D$ where $|D| = 2$ and $|C| = k$, then $MQNQ^T$ is a $2 \times 2$ matrix. If $m_1 = m_2$, then it is also symmetric since $M$ commutes with $QNQ^T$. This matrix has two positive eigenvalues $\nu$ and $\mu$, where $\nu > \mu$ and which are roots of an integer polynomial
	\[x^2 - ax + b\]
where $\nu + \mu = a$ and $\nu\mu = b$. Now $T_C$ and $T_D$ are represented by the matrices in $(1)$ and their product gives
	\[[T_C][T_D] = \begin{bmatrix} 1- \nu & 1 \\ -\nu & 1\end{bmatrix}\]
The characteristic polynomial is $x^2 - (2 - \nu)x + 1$ and the polynomial
\[f(x) = (x^2 - (2-\nu)x + 1)(x^2 - (2 -\mu)x + 1)\]
is an integer polynomial, and if we assume $|2 - \nu| > 2$ and $|2 - \mu| < 2$ then $f(x)$ will have two real roots, $\lambda$ and $\lambda^{-1}$, and two complex roots on the unit circle. This tells us that $\lambda$ is a Salem number of degree $4$ over the rationals.

\vspace{1em}
This situation is not difficult to set up.

\begin{example} Let $C = \left\{ C_1, C_2, C_3\right\}$ and $D = \left\{ D_1, D_2\right\}$ be the tight, filling multicurves on $S_2$ as in figure $1$.
We will choose $m_1 = m_2 = n_1 = n_2 = 2$ and $n_3 = 1$. Then
	\[
	   MQNQ^{T} = \begin{bmatrix} 8 & 4 \\ 4 & 6\end{bmatrix},
	\]
 where $\nu = 7 + \sqrt{17}$ and $\mu = 7 - \sqrt{17}$. We can see that $|2 - \nu| > 2$ and $|2 - \mu| < 2$, so $T_CT_D$ is a pseudo-Anosov map whose stretch factor is the Salem number
\[\lambda = \displaystyle\frac{5 + \sqrt{17} + \sqrt{38 + 10\sqrt{17}}}{2}.\]
\end{example}

The above is meant to highlight that Salem numbers arise without much effort from Thurston's construction, and they can appear when $MQNQ^T$ is symmetric. An obvious simplification then is if $Q$ is symmetric and  $M = N = I$.

\vspace{1em}
\textbf{Observation 2.} \textit{Salem numbers can arise as stretch factors when $Q$ is symmetric and $M = N = I$.}

\vspace{1em}
Suppose $S$ is a surface with tight, filling multicurves $C$ and $D$ with $|C| = |D|$ whose intersection matrix $Q$ (which is a square symmetric matrix) has $\lambda + \lambda^{-1}$ as an eigenvalue with positive eigenvector $\mathbf{v}$. Let $M = N = I$, then we have
	\[
		MQNQ^{T} = Q^2.
	\]
So we get that
\[
	[T_C] = \begin{bmatrix} 1 & 1\\ 0 & 1\end{bmatrix} \hspace{.2in}  \text{and} \hspace{.2in} [T_D] = \begin{bmatrix} 1 & 0 \\ -(\lambda + \lambda^{-1})^2 & 1\end{bmatrix}
\]
which gives
	\[[T_C][T_D] = \begin{bmatrix} 1 - (\lambda + \lambda^{-1})^2 & 1 \\ -(\lambda + \lambda^{-1})^2 & 1\end{bmatrix}\]
which has characteristic polynomial $x^2 + (\lambda^2 + \lambda^{-2})x + 1$ whose roots are $-\lambda^2$ and $-\lambda^{-2}$. Hence, up to projectivization, $T_CT_D$ has $\lambda^2$ as its stretch factor.

\vspace{1em}
With the above observations in mind our strategy for proving Theorem A is as follows: We will show that for any Salem number $\lambda$ there is a positive integer $k$ where $\lambda^k + \lambda^{-k}$ is the dominating eigenvalue of a positive symmetric integer matrix $Q$ with a corresponding positive eigenvector. From there we use the construction given in section 3 to build a closed orientable surface with two tight, filling multicurves having $Q$ as their intersection matrix. The discussion following observation $2$ shows that applying Thurston's construction to these multicurves with $M = N = I$ will give a pseudo-Anosov map with stretch factor $\lambda^{2k}$.

\section{Proof of Thereom A}

In this section we will assume that $\lambda$ is a Salem number. Some of the results here will be used to prove Theorem B, so we state them in their full generality with the goal of applying them to $\lambda + \lambda^{-1}$. Our starting point is the following theorem due to Estes, a proof of which can be found in \cite{Estes}.

\begin{thm}[Estes]
Let $\alpha$ be a totally real algebraic integer of degree $n$ over $\mathbb{Q}$, and $f(x)$ is its minimal polynomial. Then $\alpha$ is an eigenvalue of a rational symmetric matrix of size $(n + e) \times (n + e)$ whose characteristic polynomial is $f(x)(x-1)^e$, and $e \in \left\{ 1, 2\right\}$.
\end{thm}

Since $\lambda + \lambda^{-1}$ is a totally real algebraic integer, then by Estes we know that there is a rational symmetric matrix $Q$ having the following eigenvalues: $\lambda + \lambda^{-1}$, the Galois conjugates of $\lambda + \lambda^{-1}$, and $1$ with multiplicity $1$ or $2$. Though Estes makes no claims about the eigenvectors related to these eigenvalues we can without loss of generality assume that $\lambda + \lambda^{-1}$ has a positive eigenvector. We do this by using the following:

\begin{prop}
The set $O(n;\mathbb{Q})$, orthogonal matrices with rational entries, is a dense subgroup of $O(n)$. Consequently, $SO(n;\mathbb{Q})$ is a dense subgroup of $SO(n)$.
\end{prop}

A proof for this can be found in \cite{schmutz}. We use Proposition $5.2$ as follows: Since every element $U$ of $SO(n)$ has the property that $U^{-1} = U^T$ then a symmetric matrix conjugated by an $SO(n)$ matrix remains symmetric. $Q$ has eigenvalue $\lambda + \lambda^{-1}$, so we conjugate $Q$ by an $SO(n)$ matrix so the resulting matrix has a positive eigenvector corresponding to $\lambda + \lambda^{-1}$. We then perturb the entries of $U$ so that they are all rational and now the resulting matrix is still rational and symmetric having a positive eigenvector $\mathbf{v}$ corresponding to $\lambda + \lambda^{-1}$.

\vspace{1em}
We now want a rational matrix having $\lambda$ as an eigenvalue with the goal of finding a power of that matrix that has integer entries. Consider the matrix
	\[\mathcal{M} = \begin{bmatrix} Q & -I \\ I & \mathbf{0}\end{bmatrix},\]

where $I$ is the $(n + e) \times (n + e)$ identity matrix. We will use powers of this matrix to find a positive symmetric integer matrix having $\lambda^k + \lambda^{-k}$ as an eigenvalue for some $k$. We will now establish several important properties:

\begin{prop} The characteristic polynomial of $\mathcal{M}$ is $p(x)(x^2 - x + 1)^e$ where $p(x)$ is the minimal polynomial of $\lambda$ over $\mathbb{Q}$. Therefore, $\mathcal{M}$ has integral characteristic polynomial, and $\det(\mathcal{M}) = 1$.
\end{prop}

\begin{proof} We will first show that $\mu$ is an eigenvalue for $\mathcal{M}$ if and only if $\mu + \mu^{-1}$ is an eigenvalue for $Q$. If $\mu$ is an eigenvalue for $\mathcal{M}$ then there is a vector $\begin{bmatrix} \mathbf{x} \\ \mathbf{y}\end{bmatrix}$ such that
	\begin{align*}
				\mathcal{M}\begin{bmatrix} \mathbf{x} \\ \mathbf{y}\end{bmatrix}   &= \begin{bmatrix} \mu\mathbf{x} \\ \mu\mathbf{y}\end{bmatrix}\\
				\begin{bmatrix}Q\mathbf{x} - \mathbf{y} \\ \mathbf{x}\end{bmatrix} &= \begin{bmatrix} \mu\mathbf{x} \\ \mu\mathbf{y}\end{bmatrix}
		\end{align*}
so $\mathbf{y} = \mu^{-1}\mathbf{x}$, and thus we have $Q\mathbf{x} = (\mu + \mu^{-1})\mathbf{x}$, therefore $\mu + \mu^{-1}$ must be an eigenvalue of $Q$.

\vspace{1em}
Now, if $\mu + \mu^{-1}$ is an eigenvalue of $Q$ with corresponding eigenvector $\mathbf{x}$, then we have
\begin{align*}
			\mathcal{M}\begin{bmatrix} \mathbf{x} \\ \mu^{-1}\mathbf{x}\end{bmatrix} &= \begin{bmatrix} Q\mathbf{x} - \mu^{-1}\mathbf{x} \\ \mathbf{x}\end{bmatrix}\\
																																									 &= \begin{bmatrix} (\mu + \mu^{-1})\mathbf{x} - \mu^{-1}\mathbf{x} \\ \mu\cdot\mu^{-1}\mathbf{x}\end{bmatrix}\\
																																									 &= \mu\begin{bmatrix} \mathbf{x} \\ \mu^{-1}\mathbf{x} \end{bmatrix}
		\end{align*}

Hence, $\mu$ is an eigenvalue of $\mathcal{M}$. Therefore, since $\lambda + \lambda^{-1}$ and its conjugates are eigenvalues of $Q$ then $\lambda$ and its conjugates are eigenvalues of $\mathcal{M}$. Also, since $1$ is an eigenvalue with multiplicity $e$ then $\mathcal{M}$ must have an eigenvalue $\mu$ such that $\mu + \mu^{-1} = 1$, in other words $\mu^2 - \mu + 1 = 0$, hence
	\[ \mu = \displaystyle\frac{1 + i\sqrt{3}}{2} \hspace{.2in} \text{and} \hspace{.2in} \mu^{-1} = \displaystyle\frac{1 - i\sqrt{3}}{2}\]
(where $\mu$ is a primitive $6$th root of unity) and if $\mathbf{y}$ is an eigenvector of $Q$ corresponding to $1$ then $\begin{bmatrix} \mathbf{y} \\ \mu^{-1}\mathbf{y}\end{bmatrix}$ and $\begin{bmatrix} \mathbf{y} \\ \mu\mathbf{y}\end{bmatrix}$ are eigenvectors of $\mathcal{M}$ corresponding to $\mu$ and $\mu^{-1}$, respectively. So if $1$ has multiplicity $e$, then $\mu$ and $\mu^{-1}$ are eigenvalues of $\mathcal{M}$ both with multiplicity $e$. Therefore, we have shown that the characteristic polynomial of $\mathcal{M}$ has the desired form.

\vspace{1em}
Finally, since $\lambda$ and $\mu$ are algebraic units then the characteristic polynomial of $\mathcal{M}$ is integral, and the product of the eigenvalues is $1$ so $\det(\mathcal{M}) = 1$.
\end{proof}

The fact that $\det(\mathcal{M}) = 1$ is true for any square matrix $Q$ since $I$ and $\mathbf{0}$ commute we have
	\[\det(\mathcal{M}) = \det(Q\cdot\mathbf{0} + I^2) = 1\]
but most importantly this tells us that $\mathcal{M}^{-1}$ exists. It is easy to check that
	\[\mathcal{M}^{-1} = \begin{bmatrix} \mathbf{0} & I \\ -I & Q\end{bmatrix}\]
and notice that
	\[\mathcal{M} + \mathcal{M}^{-1} = \begin{bmatrix} Q & \mathbf{0} \\ \mathbf{0} & Q \end{bmatrix}\]

We will show that this behavior holds for all powers of $\mathcal{M}$.

\begin{prop}[Skew Property] $\mathcal{M}^k + \mathcal{M}^{-k}$ is a block diagonal matrix of the form $\begin{bmatrix} \mathcal{Q}_k & \mathbf{0} \\ \mathbf{0} & \mathcal{Q}_k\end{bmatrix}$ for any integer $k$. Here $\mathcal{Q}_k$ is a rational symmetric matrix whose characteristic polynomial is $g_k(x)(x - a)^e$, where $g_k(x)$ is the minimal polynomial of $\lambda^k + \lambda^{-k}$, and $a \in \left\{-2,-1,1,2\right\}$.
\end{prop}

\begin{proof}
First we will show that for any $k$ we have $\mathcal{M}^k = \begin{bmatrix} Q_k & -Q_{k-1} \\ Q_{k-1} & Q_k - Q\cdot Q_{k-1}\end{bmatrix}$ where $Q_k$ is an integral combination of powers of $Q$. We define $Q_0 = I$ and $Q_1 = A$. We will proceed by induction: For $k = 2$ we get
	\[\mathcal{M}^2  = \begin{bmatrix} Q^2 - I & -Q \\ Q & -I\end{bmatrix}\]
So $Q_2 = Q^2 - I$, and $-I = Q_2 - Q\cdot Q_1$. Now assume that this form holds for $k$, then
	\[\mathcal{M}^{k} = \begin{bmatrix} Q_{k} & -Q_{k-1} \\ Q_{k-1} & Q_{k} - Q\cdot Q_{k-1}\end{bmatrix}\]
in which case we have
	\begin{align*}
			\mathcal{M}^{k+1} &= \begin{bmatrix} Q & -I \\ I & \mathbf{0}\end{bmatrix}\begin{bmatrix} Q_{k} & -Q_{k-1} \\ Q_{k-1} & Q_{k} - Q\cdot Q_{k-1}\end{bmatrix}\\
										    &= \begin{bmatrix} Q\cdot Q_{k} - Q_{k-1} & -Q_{k} \\ Q_{k} & -Q_{k-1} \end{bmatrix}
		\end{align*}
so if $Q_{k+1} = Q\cdot Q_k - Q_{k-1}$ then we have that
	\[\begin{bmatrix} Q_{k+1} & -Q_k \\ Q_k & Q_{k+1} - Q\cdot Q_k \end{bmatrix}\]

A similar inductive argument shows that $Q^{-k}$ has the form $\begin{bmatrix} Q_k - Q\cdot Q_{k-1} & Q_{k-1} \\ -Q_{k-1} & Q_k\end{bmatrix}$ for all $k$. Therefore, we have that
	\[\mathcal{M}^{k} + \mathcal{M}^{-k} = \begin{bmatrix} 2Q_k - Q\cdot Q_{k-1} & \mathbf{0} \\ \mathbf{0} & 2Q_k - Q\cdot Q_{k-1}\end{bmatrix}\]
so $\mathcal{Q}_k = 2Q_k - Q\cdot Q_{k-1}$, which is an integral combination of powers of $Q$ so $\mathcal{Q}_k$ is a rational symmetric matrix. Now that we have established the skew-property where $\mathcal{M}^{k} + \mathcal{M}^{-k}$ is a block diagonal matrix where the $(1,1)$-block and the $(2,2)$-block are equal rational symmetric matrices, then we can see that not only are the eigenvalues of $\mathcal{M}^{k} + \mathcal{M}^{-k}$ of the form $\nu_k + \nu_k^{-1}$, where $\nu_k$ is an eigenvalue of $\mathcal{M}^k$ but also that $\nu_k + \nu_k^{-1}$ is an eigenvalue of $\mathcal{M}^{k} + \mathcal{M}^{-k}$ if and only if $\nu_k + \nu_k^{-1}$ is an eigenvalue of each diagonal block.

\vspace{1em}
We immediately get from this that $\lambda^k + \lambda^{-k}$ and its conjugates are eigenvalues of $\mathcal{Q}_k$. Since $\mathcal{M}^k$ has $\mu^k$ and $\mu^{-k}$ as eigenvalues then we need to determine the possibilities for $\mu^k + \mu^{-k}$. Since $\mu$ is a primitive $6$th root of unity we have the following chart where $g_k(x)$ denotes the minimal polynomial of $\lambda^k + \lambda^{-k}$:
\begin{center}
	\begin{tabular}{ |l|c|c|c| }
		\hline
$k \equiv b \mod 6$ & $\mu^k + \mu^{-k}$ & \text{Characteristic Polynomial of $\mathcal{Q}_k$} \\
		\hline
$b = 0$ & $2$ & $g_k(x)(x - 2)^e$\\
$b = 1,5$ & $1$ & $g_k(x)(x - 1)^e$\\
$b = 2,4$ & $-1$ & $g_k(x)(x + 1)^e$\\
$b = 3$   & $-2$ & $g_k(x)(x + 2)^e$\\
		\hline
	\end{tabular}
\end{center}
Therefore, we have proved Proposition $5.4$.
\end{proof}

Since $\mathcal{Q}_k$ is an integral combination of powers of $Q$, then it is clear that the eigenspaces of $\mathcal{Q}_k$ and $Q$ are exactly the same for all $k$. Therefore, since $Q$ has a positive eigenvector $\mathbf{v}$ corresponding to $\lambda + \lambda^{-1}$, then $\mathcal{Q}_k$ also has eigenvector $\mathbf{v}$ corresponding to $\lambda^k + \lambda^{-k}$. The goal now is to use this, in conjunction with the next proposition, to show that there is a $k$ where $\mathcal{Q}_k$ is a positive symmetric integral matrix.

\begin{prop}
Let $M \in M_n(\mathbb{Q})$ such that $\det(M) = \pm 1$ and the characteristic polynomial of $M$ has integer coefficients. Then some power of $M$ is integral.
\end{prop}

\begin{proof}
Since we can replace $M$ with $M^2$ then without loss of generality we can assume $\det(M) = 1$. Let $\Omega$ be the rational canonical form of $M$, which by assumption has integer entries. Thus, there is a nonsingular rational matrix $A$ such that $A^{-1}MA = \Omega$. Now $A = \frac{1}{c}P$ and $A^{-1} = \frac{1}{d}P'$ where
	\[PP' = cdI\]
$c,d$ are nonzero integers and $P,P'$ are integer matrices. Let $\overline{\Omega}$ be the matrix obtained from $\Omega$ by reducing its entries modulo $cd$. Since $\det(\Omega) = 1$ then $\det(\overline{\Omega}) = 1$, so  $\overline{\Omega} \in SL(n;\mathbb{Z}/cd\mathbb{Z})$. Since $SL(n;\mathbb{Z}/cd\mathbb{Z})$ is a finite group there is a positive integer $k$ such that
	\[\Omega^{\hspace{.01in}k} \equiv I \mod cd\]
that is, there an integer matrix $B$ such that $\Omega^k = I + cdB$. Now
\begin{align*}
		M^k &= A\Omega^kA^{-1}\\
				&= A(I + cdB)A^{-1}\\
				&= I + cdABA^{-1}\\
				&= I + PBP'
	\end{align*}
where $PBP'$ is an integer matrix, and thus $M^k$ is an integer matrix.
\end{proof}

Since $\mathcal{M}$ is a rational matrix with determinant $1$ and integer characteristic polynomial, then by the above proposition there is a $k$ such that $\mathcal{M}^k$ is an integer matrix. This means that $\mathcal{Q}_k$ is a symmetric integer matrix having $\lambda^k + \lambda^{-k}$ as an eigenvalue. We have now shown that every Salem number has a power $k$ such that $\lambda^k + \lambda^{-k}$ is an eigenvalue of a symmetric integral matrix. Now we want to show that we can raise $k$ high enough to get a positive matrix.

\vspace{1em}
$\mathcal{Q}_k$ is symmetric so we know there is an orthonormal basis of eigenvectors of $\mathcal{Q}_k$. Since there is a positive eigenvector $\mathbf{v}$ corresponding to $\lambda^{k} + \lambda^{-k}$ then for any standard basis vector $\mathbf{e}_i$
	\[\mathbf{e_i} = c_i\mathbf{v} + \mathbf{w}_i\]
where $\mathbf{w}_i$ lies in the orthogonal complement of Span$\left\{\mathbf{v}\right\}$, which is spanned by the other eigenvectors of $\mathcal{Q}_k$. Thus, for each $i$ we have $c_i = \mathbf{v}\cdot \mathbf{e_i} > 0$. Applying $\mathcal{Q}_k$ to both sides gives
\[\mathcal{Q}_k\mathbf{e}_i = c_i(\lambda^k + \lambda^{-k})\mathbf{e}_i + \mathcal{Q}_k\mathbf{w}_i\]
since $\lambda^k$ is a Salem number, the conjugates of $\lambda^k + \lambda^{-k}$ are real numbers in the interval $(-2,2)$. As we see above the vectors making up $\mathbf{w}_i$ are each scaled by a number in the interval $[-2,2]$, but $\lambda^k + \lambda^{-k}$ grows without bound, so eventually $\mathcal{Q}_k\mathbf{e}_i$ is a positive vector for any $i$.

\vspace{1em}
So, if we start with an integer $k$ such that $\mathcal{M}^k$ is integral, then $\mathcal{M}^{nk}$ is integral for any positive integer $n$, so choose $n$ large enough so that $\mathcal{Q}_{nk}$ is a positive symmetric integer matrix. Therefore, we have shown that for any Salem number $\lambda$ there is a positive integer $k$ such that $\lambda^k + \lambda^{-k}$ is an eigenvalue of a positive symmetric integral matrix.

\vspace{1em}
With this we can finish the proof as follows: Since $\mathcal{Q}_k$ is a nonsingular positive symmetric integer matrix having $\lambda^k + \lambda^{-k}$ as an eigenvalue with positive eigenvector $\mathbf{v}$, we can use Theorem $3.1$ to find a surface with tight, filling multicurves $C$ and $D$ whose intersection matrix is $\mathcal{Q}_k$. By Proposition $3.2$, the genus of this surface is $g = (n + e)^2 - (n + e) + 1$, where $n = [\mathbb{Q}(\lambda):\mathbb{Q}]$. Choosing $M = N = I$ and following discussion proceeding observation $2$, we see that $T_CT_D$ is a pseudo-Anosov map coming from Thurston's construction with stretch factor $\lambda^{2k}$.

\vspace{1em}
\textbf{Brief Summary.} Let $\lambda$ be a Salem number. Using Estes we find a rational symmetric matrix $Q$ having $\lambda + \lambda^{-1}$, its conjugates, and $1$ as eigenvalues. Without loss of generality we can assume that $Q$ has a positive eigenvector $\mathbf{v}$ corresponding to $\lambda + \lambda^{-1}$ since we can always conjugate $Q$ by an $SO(n;\mathbb{Q})$ matrix to rotate an eigenvector of $\lambda + \lambda^{-1}$ into the first orthant. We define the matrix $\mathcal{M} = \begin{bmatrix} Q & -I\\ I & \mathbf{0}\end{bmatrix}$ which has $\lambda$, its conjugates, and the $6$th roots of unity $\mu$ and $\mu^{-1}$ as eigenvalues. Thus, $\mathcal{M}$ has determinant $1$, integer characteristic polynomial, $\mathcal{M}^{-1}$ exists and has the skew-property where $\mathcal{M}^k + \mathcal{M}^{-k}$ is a block diagonal matrix where the $(1,1)$ and $(2,2)$ blocks are equal; call these blocks $\mathcal{Q}_k$.

\vspace{1em}
$\mathcal{Q}_k$ has $\lambda^k + \lambda^{-k}$ as an eigenvalue, and all other eigenvalues lie in the interval $[-2,2]$ and by above arguments we can power up $\mathcal{M}$ so that $\mathcal{Q}_k$ is positive and integral. Using Theorem $3.1$, we know there is a surface with two tight filling multicurves $C$ and $D$ having $\mathcal{Q}_k$ as their intersection matrix. Applying Thurston's construction with $M = N = I$ we get a pseudo-Anosov map $T_CT_D$ having $\lambda^{2k}$ as its stretch factor.

\section{Powers of Rational Symmetric Matrices}

Over the next two sections we will establish some final results, develop some background algebraic number theory and prove Theorem B. We start this section by proving a condition for when a real symmetric matrix will have a positive power and then conclude this section by showing that any rational symmetric matrix with a dominating eigenvalue larger than $1$ is conjugate to a rational symmetric matrix that has a positive power.

\begin{prop}
If $Q$ is a real symmetric matrix with a unique dominating eigenvalue $\lambda > 1$ and a positive eigenvector $\mathbf{v}$, then there is some power of $Q$ that is positive.
\end{prop}

\begin{proof}[Sketch of Proof.] The proof of this is very similar to the proof that $\mathcal{Q}_k$ is eventually positive. Every standard basis vector can be written as
\[\mathbf{e}_i = c_i\mathbf{v} + \mathbf{w}_i\]
 with $c_i > 0$ for each $i$, and applying $Q^k$ to both sides gives
\[Q^k\mathbf{e}_i = c_i\lambda^k\mathbf{v} + Q^k\mathbf{w}_i\]
Since $\lambda > \mu$ for all other eigenvalues $\mu$ then the sum $c_i\lambda^k\mathbf{v} + Q^k\mathbf{w}_i$ is eventually a positive vector. Hence, $Q^k\mathbf{e}_i$ is eventually positive for all $i$. So there is a $k$ such that $Q^k$ is a positive matrix.
\end{proof}

\begin{prop}
If $Q \in M_n(\mathbb{Q})$ is symmetric, and has a unique dominating eigenvalue $\lambda > 1$ with corresponding eigenvector $\mathbf{v}$. Then there is a matrix $U \in SO(n;\mathbb{Q})$ such that $UA^kU^{T}$ is a positive symmetric rational matrix for some positive integer $k$.
\end{prop}

\begin{proof} By Proposition $5.2$ $SO(n;\mathbb{Q})$ is dense in $SO(n)$, so we can conjugate $Q$ by an $SO(n,\mathbb{Q})$ matrix $U$ so that $\lambda$ now has a positive eigenvector. By Proposition $6.1$ we know there is some $k$ such that $UA^kU^{T}$ is a positive symmetric rational matrix.
\end{proof}

\section{Proof of Theorem B}

Before getting to the proof of Theorem B we will develop some algebraic number theory that we will use to prove the following:

\begin{thm}
Given a totally real number field $K$, there is an algebraic unit $\alpha \in K$ such that $\alpha > 1$, $K = \mathbb{Q}(\alpha)$, $K = \mathbb{Q}(\alpha^m)$ for all positive integers $m$, and all conjugates of $\alpha$ are positive, less than 1.
\end{thm}

First a couple definitions:

\begin{definition}
Given a basis $\mathbf{e}_1,...,\mathbf{e}_n$ for $\mathbb{R}^n$, then the $\mathbf{e}_i$ form a basis for a free $\mathbb{Z}$-module $L$ of rank $n$, namely,
	\[L = \mathbb{Z}\mathbf{e}_1 \oplus ... \oplus \mathbb{Z}\mathbf{e}_n\]
A set $L$ constructed this way is called a \textit{lattice} in $\mathbb{R}^n$.
\end{definition}

\vspace{1em} It is a well known fact that every number field $K$ of degree $n$ over $\mathbb{Q}$ has exactly $n$ embeddings into $\mathbb{C}$. Since we are talking about totally real number fields, these embeddings will be into $\mathbb{R}$. Let $\sigma_1,...,\sigma_n$ be these embeddings, where $\sigma_1$ denotes the inclusion embedding.

\begin{definition} Let $K$ be a totally real number field of degree $n$. We define the \textit{logarithmic embedding} of $K$ into $\mathbb{R}^n$ by
	\[ \lambda(x) = (\log|\sigma_1(x)|,...,\log|\sigma_n(x)|)\]
for all nonzero $x \in K$. Note: that $\lambda(xy) = \lambda(x) + \lambda(y)$, so $\lambda$ is a homomorphism from the multiplicative group $K^*$ to the additive group $\mathbb{R}^n$.
\end{definition}

The logarithmic embedding is used to prove the Dirichlet Unit Theorem, which gives a complete description of the unit group of a number field. A proof for this theorem can be found in \cite{MR2779252}, but we will just state it:

\begin{thm}[Dirichlet Unit Theorem]
Let $K$ be a number field, $r_1$ is the number of real embbedings, and $r_2$ is the number of complex embeddings (up to conjugacy). Then the unit group $U$ of $K$ is isomorphic to $G \times \mathbb{Z}^{r_1 + r_2 - 1}$, where $G$ is a finite cyclic group consisting of all the roots of unity in $K$.
\end{thm}

Since we are considering number fields $K$ that are totally real then if $[K: \mathbb{Q}] = n$ we have $r_1 = n$, $r_2 = 0$ and $G = \left\{ -1, 1\right\}$. Hence, the unit group of $K$ is isomorphic to $\left\{ -1, 1 \right\} \times \mathbb{Z}^{n-1}$. That is, there are units $u_1,...,u_{n-1}$ such that every unit of $K$ is of the form
 \[\pm u_{1}^{m_1}\cdots u_{n-1}^{m_{n-1}}\]
where $m_i$ are integers.

\vspace{1em}
The logarithmic embedding maps the unit group $U$ of $K$ to the hyperplane
\[ H = \left\{ (x_1,...,x_n) \ \left\vert \ \displaystyle\sum_{i=1}^{n}{x_i} = 0\right\}\right. .\]
In fact, if $u_1,...,u_{n-1}$ are the generators for $U$ then $\left\{ \lambda(u_1),...,\lambda(u_{n-1})\right\}$ is a basis for $H$, hence $\lambda(U)$ is a lattice in $H$.

\begin{proof}[Proof of Theorem $7.1$.] \textit{Step} 1: We start by proving the following claim:

\vspace{1em}
\textit{Claim}: Suppose $\alpha$ is a unit that generates the field, which is bigger than 1, and all its Galois conjugates are less than $1$ in absolute value. Then $K = \mathbb{Q}(\alpha^m)$ for any positive integer $m$.

\begin{proof} Let $\left\{ \sigma_2(\alpha),...,\sigma_{n}(\alpha) \right\}$ be the Galois conjugates of $\alpha$. If there is a positive integer $m$ such that $\mathbb{Q}(\alpha^m)$ is a proper subfield of $\mathbb{Q}(\alpha)$, then $\alpha^m$ has the following Galois conjugates (reordering if necessary) $\left\{ \sigma_2(\alpha)^m,...,\sigma_k(\alpha)^m\right\}$, where $k < n$. Since $\alpha$ and $\alpha^m$ are algebraic units we have that
	\[	|\alpha\sigma_2(\alpha)\cdots\sigma_{n}(\alpha)| = 1\]
and
	\[		|\alpha^m\sigma_2(\alpha)^m\cdots\sigma_{k}(\alpha)^m| = 1.\]
This tells us that
\[   |\alpha\sigma_2(\alpha)\cdots\sigma_{k}(\alpha)| = 1\]
therefore
\[   |\sigma_{k+1}(\alpha)\cdots\sigma_{n}(\alpha)| = 1\]
which is impossible since $|\sigma_i(\alpha)| < 1$ for $i = 2,...,n$. Therefore, $K = \mathbb{Q}(\alpha^m)$ for any positive integer $m$.
\end{proof}

\textit{Step} 2: Now we will find such a unit. Let $u_1,...,u_{n-1}$ be positive generators for the unit group of $K$. Since $\left\{ \lambda(u_1),..., \lambda(u_{n-1})\right\}$ is a basis for $H$ then we can take rational numbers $a_1,...,a_{n-1}$ such that
	\begin{align*}
				&(1) \ \displaystyle\sum_{i=1}^{n-1}a_i\log|u_i| > 1\\
				&(2) \ \displaystyle\sum_{i=1}^{n-1}a_i\log|\sigma_j(u_i)| < 0, \ 2\leq j \leq n - 1\\
				&(3) \ \text{The entries of } a_1\lambda(u_1)+...+a_{n-1}\lambda(u_{n-1}) \text{ sum to 0}\\
				&(4) \ \text{All entries of } a_1\lambda(u_1)+...+a_{n-1}\lambda(u_{n-1}) \text{ are distinct.}
		\end{align*}
Clearing denominators gives us an integer combination
	\[b_1\lambda(u_1)+...+b_{n-1}\lambda(u_{n-1})\]
that also has the above properties. Now take $u \in U$ to be the element
	\[ u = u_1^{b_1}\cdots u_{n-1}^{b_{n-1}}\]

By construction no two entries of $\lambda(u)$ are identical, hence $\sigma_i(u) \neq \sigma_j(u)$ for $i \neq j$, so $u$ has $n$ distinct Galois conjugates, therefore the minimal polynomial of $u$ over $\mathbb{Q}$ has degree $n$. Hence, $K = \mathbb{Q}(u)$. Also, by construction, $\log|u| > 1$ so $|u| > 1$ but $|\sigma_i(u)| < 1$ for all $2 \leq i \leq n$, so by step $1$ any power of $u$ generates $K$. Let $\alpha = u^2$, then $\alpha > 1$, all its conjugates are positive less than $1$, $K = \mathbb{Q}(\alpha)$ and $K = \mathbb{Q}(\alpha^m)$ for all positive integers $m$.
\end{proof}

We now have all the pieces to prove the following:

\begin{lem} Let $K$ be a totally real number field. Then there is an algebraic unit $\alpha$ such that $K = \mathbb{Q}(\alpha)$ and $\alpha$ is the dominant eigenvalue of a positive symmetric integral matrix that is the intersection matrix of a pair of tight, filling multicurves on some orientable closed surface.
\end{lem}

\begin{proof}
Let $K$ be a totally real number field, then by Theorem $7.1$ we can find an algebraic unit $\beta$ so that $\beta > 1$, $K=\mathbb{Q}(\beta^m)$ for all positive integers $m$, and all conjugates of $\beta$ are positive less than $1$. By Theorem $5.1$ (Estes) there is a rational symmetric matrix $B$ having $\beta$ as its unique dominating eigenvalue greater than 1, and whose characteristic polynomial is $f(x)(x - 1)^e$, where $f(x)$ is the minimal polynomial of $\beta$ over $\mathbb{Q}$. Note that $f(x)$ has integer coefficients and since $\beta$ is a unit then the constant term of $f(x)$ is 1, so $\det(B) = \pm1$.

\vspace{1em}
Now, by Proposition $6.2$ we can conjugate $B$ by an $SO(n + e; \mathbb{Q})$ matrix $U$ where there is a positive integer $k$ such that $Q = UB^kU^{T}$ is a positive rational matrix, without loss of generality assume $k$ is even. Now, $Q$ is a positive rational matrix whose eigenvalues are $\beta^k$, its conjugates, and $1$, hence the coefficients of the characteristic polynomial of $Q$ are integers, and $\det(Q) = (\pm1)^k = 1$.

\vspace{1em}
Applying Proposition $5.5$, we know there is some positive integer $\ell$ so that $Q^{\ell}$ is integral and if we let $\alpha = \beta^{k\ell}$ then $ K = \mathbb{Q}(\alpha)$ where $\alpha$ is the dominating eigenvalue of $Q^{\ell}$, which is a positive symmetric integral matrix. Now apply Theorem $3.1$ to find a closed orientable surface with multicurves $C = \left\{ C_1,...,C_{(n + e)}\right\}$ and $D = \left\{ D_1,...,D_{(n+e)}\right\}$ such that $i(D_i,C_j) = Q_{ij}^{\ell}$.
\end{proof}

We end the paper by proving Theorem B, which we restate here.

\vspace{1em}
\textbf{Theorem B.} \textit{Every totally real number field is of the form $K = \mathbb{Q}(\lambda + \lambda^{-1})$, where $\lambda$ is the stretch factor of a pseudo-Anosov map arising from Thurston's construction.}

\begin{proof} Let $K$ be a totally real number field. By Lemma $7.5$ we can find a unit $\alpha$ such that $K = \mathbb{Q}(\alpha)$ and $\alpha$ is the dominating eigenvalue of a positive symmetric integral matrix $Q$ that is the intersection matrix of a pair of tight, filling multicurves, $C$ and $D$, on a closed orientable surface $S$. Without loss of generality we can assume $\alpha > 2$. Applying Thurston's construction with $M = N = I$ we have $\alpha^2$ as the dominating eigenvalue of $MQNQ^T = Q^2$, and the following representations of $T_C$ and $T_D$:
	\[
				[T_C] = \begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix} \hspace{.1in} \text{and} \hspace{.1in} [T_D] = \begin{bmatrix} 1 & 0 \\ -\alpha^2 & 1\end{bmatrix}
	\]
Multiplying these matrices gives
	\[
			[T_C][T_D] = \begin{bmatrix} 1 - \alpha^2 & 1 \\ -\alpha^2 & 1\end{bmatrix}
	\]
Since $\alpha^2 > 4$ then we have that $|tr([T_C][T_D])| = |2 - \alpha^2| > 2$. So $T_CT_D$ is a pseudo-Anosov map with stretch factor
	\[
			\lambda = \displaystyle\frac{(\alpha^2 - 2) + \alpha\sqrt{\alpha^2 - 4}}{2}
	\]
Hence, $\lambda + \lambda^{-1} = \alpha^2 - 2$, and so $\mathbb{Q}(\lambda + \lambda^{-1}) = \mathbb{Q}(\alpha^2 - 2) = \mathbb{Q}(\alpha^2) = K$.
\end{proof}
\bibliographystyle{amsalpha}