% This paper comes in two versions.
% To compile the long version, you need these two lines:
% \includecomment{verlong}
% \excludecomment{vershort}
% For the short version, they need to be the instead:
% \excludecomment{verlong}
% \includecomment{vershort}
% This feature is not currently used (the two versions don't differ), but you
% can use it yourself:
% Everything between \begin{verlong} and \end{verlong} only appears in the long
% version.
% Everything between \begin{vershort} and \end{vershort} only appears in the
% short version.
% Everything else is compiled either way.
% The next line makes the paper appear in a certain style; you can
% change it if you want. "12pt" means that the text appears in 12pt font.
% "numbers=enddot" makes theorem numbers appear like "Theorem 12.2."
% (with dot at the end) rather than just "Theorem 12.2" (which I find ugly).
% "notitlepage" and "onecolumn" are the obvious thing.
% The next line imports a package for drawing diagrams (useful mostly for
% commutative diagrams in algebra, but not only.)
% Some standard packages follow. See
% http://tex.stackexchange.com/questions/32100/what-does-each-ams-package-do .
% Normally you want to import them all.
% "framed" is something I use for the vertical bars on my theorems.
% You probably don't want it.
% "comment" is what makes the vershort-verlong trick work.
% "color" does the obvious thing.
% "tabu" is a package for tables which are more complicated than the
% usual matrix/array environments of LaTeX (e.g. containing delimiters
% between certain cells but not others). I use it to draw cylindric
% tableaux in this file.
% "hyperref" allows hyperlinks (in the bibliography, but also from text
% to footnotes or to formulas). Almost every paper nowadays should import
% this package.
% The following two imports make the paper appear in the nonstandard font
% I want it to appear in.
% The following boilerplate code is not something you want to keep
% around for your paper; it defines Theorems, Definitions,
% Conditions etc. in a way that makes them appear with vertical
% bars in front of them.
% Vertical and horizontal offset. These determine the left and
% right margins. I am not sure that this is the best way to set them.
% The other two margins. Again, I am not sure if this is how you
% *should* set them, but hey, it works.
% This is for those vershort and verlong environments to switch
% between different versions of the document.
% Newcommands. For instance, the first of these defines \id to be a
% mathematical symbol "id". 
% Now the actual document. Be aware that it is generated by Scientific
% WorkPlace, so much of the code is ugly and/or bad. For instance, the
% \newcommands are almost never used, because Scientific WorkPlace
% always automatically extracts them. Also, most of the %'s at the end
% of lines are useless; I don't know why SWP keeps inserting them.

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{tabu}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, May 15, 2019 10:42:21}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\Par}{\operatorname{Par}}
\ihead{PRIMES 2015 reading project: Problem set \#3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
{\Huge \textbf{PRIMES 2015 reading project: Problem set \#3}}

(posted 31 May 2015, to be submitted around 15 June 2015)

Darij Grinberg
\end{center}

The purpose of this problem set is to replace an argument in \cite[proof of
Proposition 1.8]{BFZ-CA3} with a more elementary argument (which does not use
Newton polytopes).\footnote{This is not the only place where \cite{BFZ-CA3}
uses Newton polytopes; but the other place -- in the proof of Lemma 7.3 -- is
really tangential to what we are doing (it proves the \textquotedblleft only
if\textquotedblright\ part of Theorem 1.20, which I would not call
particularly interesting).}

\subsection{Some linear algebra basics}

Let us start by doing some linear algebra over the ring of integers. You are
probably most used to doing linear algebra over fields, since this is the case
most suited to doing linear algebra: For example, solving a system of linear
equations using Gaussian elimination works over fields but not (say) over
$\mathbb{Z}$ or over a polynomial ring.\footnote{This is not to say that the
situation over $\mathbb{Z}$ and over polynomial rings is hopeless. Some more
complicated versions of Gaussian elimination do their job over some of these
rings, and lead to certain weaker and more complicated (but also more
interesting!) versions of row-reduced matrices.} We shall do linear algebra
over the ring of integers here, because we will want to use the entries of our
vectors as exponents in monomials, and exponents in monomials should be
integers (we don't want to work with non-integer powers here). Fortunately,
the linear algebra that we will do will be simple enough that it can be made
to work over the integers.

If $F$ is a commutative ring\footnote{Recall that a commutative ring is
(roughly speaking) a set $S$ whose elements can be added, subtracted and
multiplied, and all of these operations give results inside $S$ and satisfy
the usual laws (commutativity, associativity, distributivity, existence of $0$
and $1$).} and if $n$ and $m$ are two nonnegative integers, then $F^{n\times
m}$ denotes the set of all $n\times m$-matrices over $F$. (These are the
matrices whose entries are in $F$ and which have $n$ rows and $m$ columns.) We
regard $\mathbb{Z}^{n\times m}$ as a subset of $\mathbb{Q}^{n\times m}$ for
all $n$ and $m$, because a matrix with integer entries can always be regarded
as a matrix with rational entries.

If $F$ is a commutative ring and if $n\in\mathbb{N}$, then $\operatorname*{GL}%
\nolimits_{n}\left(  F\right)  $ denotes the group of all invertible $n\times
n$-matrices $A\in F^{n\times n}$. Here, \textquotedblleft
invertible\textquotedblright\ means \textquotedblleft invertible in
$F^{n\times n}$\textquotedblright; that is, a matrix $A$ is said to be
invertible if there exists a matrix $B\in F^{n\times n}$ such that
$AB=BA=I_{n}$ (where $I_{n}$ is the $n\times n$ identity matrix). The meaning
of \textquotedblleft invertible\textquotedblright\ thus depends on $F$ (so we
will clarify it by saying \textquotedblleft invertible in $F^{n\times n}%
$\textquotedblright\ unless $F$ is clear from the context). For example, the
five matrices%
\[
\left(
\begin{array}
[c]{cc}%
1 & 3\\
1 & 2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & -1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cc}%
1 & 2\\
1 & 4
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cc}%
2 & 0\\
0 & -3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{cc}%
\dfrac{1}{2} & \dfrac{3}{2}\\
1 & 1
\end{array}
\right)
\]
are invertible in $\mathbb{Q}^{n\times n}$, but only the first two of them are
invertible in $\mathbb{Z}^{n\times n}$. (The fifth one, of course, does not
lie in $\mathbb{Z}^{n\times n}$ to begin with.)

We shall study $\operatorname*{GL}\nolimits_{n}\left(  \mathbb{Z}\right)  $ in
particular. Recall that a matrix $A\in\mathbb{Q}^{n\times n}$ is invertible if
and only if its determinant $\det A$ is nonzero. The analogous criterion for
$\mathbb{Z}$ is a lot more restrictive: A matrix $A\in\mathbb{Z}^{n\times n}$
is invertible if and only if its determinant $\det A$ has an inverse in
$\mathbb{Z}$. (The only integers which have an inverse in $\mathbb{Z}$ are $1$
and $-1$, so this leaves only two possibilities for the determinant.) We will
not use this fact, however, but it is important.\footnote{We might get to
explore it later.}

We start with some simpler things.

For any $n\in\mathbb{N}$, the sets $\mathbb{Z}^{n}$ and $\mathbb{Q}^{n}$
consist of column vectors of length $n$ (at least according to my convention),
and we consider $\mathbb{Z}^{n}$ as a subset of $\mathbb{Q}^{n}$. I will
usually write a column vector $\left(
\begin{array}
[c]{c}%
v_{1}\\
v_{2}\\
\vdots\\
v_{n}%
\end{array}
\right)  $ in the form $\left(  v_{1},v_{2},\ldots,v_{n}\right)  ^{T}$,
because the former (vertical) notation takes too much space. Of course, the
notation $\left(  v_{1},v_{2},\ldots,v_{n}\right)  ^{T}$ is just a particular
case of the general notation $A^{T}$ for the transpose of a matrix $A$ (at
least if we follow the usual convention to think of column vectors as
$n\times1$-matrices and of row vectors as $1\times n$-matrices).

The column vector of length $n$ whose all entries are $0$ will be denoted by
$0$, or (when $n$ is not clear from the context) by $0_{n}$. It is called the
\textit{zero vector}.

For every $n\in\mathbb{N}$ and $i\in\left\{  1,2,\ldots,n\right\}  $, we let
$e_{i}$ be the column vector
\[
\left(  0,0,\ldots,0,1,0,0,\ldots,0\right)  ^{T}\in\mathbb{Z}^{n},
\]
where the $1$ is the $i$-th entry of the vector. (This vector depends on both
$i$ and $n$; we just leave the $n$ out of the notation $e_{i}$ because it will
always be clear from the context.)

\begin{exercise}
\label{exe.GL.group}Let $n\in\mathbb{N}$, and let $F$ be a commutative ring.
(Feel free to take $F=\mathbb{Z}$ or $F=\mathbb{Q}$ here.) Show that
$\operatorname*{GL}\nolimits_{n}\left(  F\right)  $ is a group (where the
binary operation is multiplication of matrices).
\end{exercise}

\subsection{Gcds of integer vectors}

The \textit{greatest common divisor} $\gcd\mathbf{v}$ of a vector
$\mathbf{v}\in\mathbb{Z}^{n}$ is defined as the gcd of all the $n$ entries of
$\mathbf{v}$. When $\mathbf{v}=0$, this is understood to be $0$; otherwise, it
is a positive integer.

\begin{exercise}
\label{exe.GL.gcd}Let $n\in\mathbb{N}$, let $A\in\mathbb{Z}^{n\times n}$ and
$\mathbf{v}\in\mathbb{Z}^{n}$.

\textbf{(a)} Prove that $\gcd\mathbf{v}\mid\gcd\left(  A\mathbf{v}\right)  $.

\textbf{(b)} If $A\in\operatorname*{GL}\nolimits_{n}\left(  \mathbb{Z}\right)
$, then prove that $\gcd\left(  A\mathbf{v}\right)  =\gcd\mathbf{v}$.
\end{exercise}

\begin{exercise}
\label{exe.GL.vec-to-gcd}Let $n$ be a positive integer, and let $\mathbf{v}%
\in\mathbb{Z}^{n}$. Let $g=\gcd\mathbf{v}$. Then, there exists a matrix
$A\in\operatorname*{GL}\nolimits_{n}\left(  \mathbb{Z}\right)  $ such that%
\[
\mathbf{v}=gAe_{1}.
\]

\end{exercise}

This exercise is crucial, so let me comment on it a bit more. First of all,
$e_{1}$ is the column vector $\left(  1,0,0,0,\ldots\right)  \in\mathbb{Z}%
^{n}$ (which has $1$ as its first entry and $0$'s everywhere else). Thus,
$Ae_{1}$ is the first column of the matrix $A$ (check this if you don't know
why it holds), and so $gAe_{1}$ is the result of multiplying this first column
by $g=\gcd\mathbf{v}$. So Exercise \ref{exe.GL.vec-to-gcd} says that if $n$ is
a positive integer and if $\mathbf{v}\in\mathbb{Z}^{n}$, then there exists an
invertible matrix $A\in\operatorname*{GL}\nolimits_{n}\left(  \mathbb{Z}%
\right)  $ whose first column, multiplied by $\gcd\mathbf{v}$, is the vector
$\mathbf{v}$. In particular, if $\gcd\mathbf{v}=1$, then $\mathbf{v}$ itself
is the first column of an invertible matrix $A\in\operatorname*{GL}%
\nolimits_{n}\left(  \mathbb{Z}\right)  $. For instance, the vector $\left(
6,15,10\right)  ^{T}\in\mathbb{Z}^{3}$ is the first column of the invertible
matrix $\left(
\begin{array}
[c]{ccc}%
6 & 0 & 1\\
15 & 1 & 1\\
10 & 1 & 0
\end{array}
\right)  $ (and, of course, of many other such matrices).

Let me give a few hints for Exercise \ref{exe.GL.vec-to-gcd}. We want to prove
the existence of an invertible matrix $A\in\operatorname*{GL}\nolimits_{n}%
\left(  \mathbb{Z}\right)  $ such that $\mathbf{v}=gAe_{1}$. This is
tantamount to constructing an invertible matrix $B\in\operatorname*{GL}%
\nolimits_{n}\left(  \mathbb{Z}\right)  $ such that $B\mathbf{v}=ge_{1}$ (the
relation between $A$ and $B$ is that of being mutually inverse). A way to do
this is to find a sequence of invertible matrices which, when multiplied onto
$\mathbf{v}$ from the left (one after the other), will make the vector
$\mathbf{v}$ \textquotedblleft simpler\textquotedblright\ step by step, until
$\mathbf{v}$ becomes a vector with only one nonzero entry\footnote{unless
$\mathbf{v}=0$, in which case there is no nonzero entry at all and we are
done}. Then, the entry will have to be either $g$ or $-g$ (why?). A further
invertible matrix (namely, $-I_{n}$) will get rid of the minus if it is a
$-g$; a further multiplication with a permutation matrix (permutation matrices
are invertible) will push the nonzero entry into the first spot, and we will
have the vector $ge_{1}$ in front of us. So the main difficulty is to find
that sequence of invertible matrices which \textquotedblleft
simplify\textquotedblright\ $\mathbf{v}$. To do so, keep in mind that if
$\mathbf{v}\in\mathbb{Z}^{n}$ is a vector and $i$ and $j$ are two distinct
elements of $\left\{  1,2,\ldots,n\right\}  $, then the matrix $F_{i,j}$ which
has $1$'s on the main diagonal, a $-1$ in cell $\left(  i,j\right)  $, and
$0$'s everywhere else is invertible (what is its inverse?), and the vector
$F_{i,j}\mathbf{v}$ is obtained from $\mathbf{v}$ by subtracting the $j$-th
entry from the $i$-th entry. How can you \textquotedblleft
simplify\textquotedblright\ $\mathbf{v}$ using such subtraction operations?

\subsection{Reminders on polynomials}

Fix $n\in\mathbb{N}$ from now on. Let $\mathbf{x}$ denote the $n$-tuple
$\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ of distinct indeterminates. We can
use this $n$-tuple to define the polynomial ring $\mathbb{Z}\left[
\mathbf{x}\right]  =\mathbb{Z}\left[  x_{1},x_{2},\ldots,x_{n}\right]  $, as
well as the Laurent polynomial ring $\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  =\mathbb{Z}\left[  x_{1}^{\pm1},x_{2}^{\pm1},\ldots,x_{n}^{\pm
1}\right]  $. The elements of the polynomial ring $\mathbb{Z}\left[
\mathbf{x}\right]  $ are polynomials, i.e., $\mathbb{Z}$-linear combinations
of \textit{monomials} (which are expressions of the form $x_{1}^{v_{1}}%
x_{2}^{v_{2}}\cdots x_{n}^{v_{n}}$ where $v_{1},v_{2},\ldots,v_{n}%
\in\mathbb{N}$). The elements of the Laurent polynomial ring $\mathbb{Z}%
\left[  \mathbf{x}^{\pm1}\right]  $ are Laurent polynomials, i.e.,
$\mathbb{Z}$-linear combinations of \textit{Laurent monomials} (which are
expressions of the form $x_{1}^{v_{1}}x_{2}^{v_{2}}\cdots x_{n}^{v_{n}}$ where
$v_{1},v_{2},\ldots,v_{n}\in\mathbb{Z}$). We can view $\mathbb{Z}\left[
\mathbf{x}\right]  $ as a subring of $\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  $.

Let us recall how the notion of an \textit{irreducible element} of a
commutative ring is defined: If $R$ is a commutative ring, then an element
$a\in R$ is said to be \textit{irreducible} if and only if

\begin{itemize}
\item the element $a$ is not invertible (in $R$), and

\item there are no two elements $b$ and $c$ of $R$ which are not invertible
(in $R$) and satisfy $bc=a$.
\end{itemize}

For example, the irreducible elements of $\mathbb{Z}$ are the prime numbers
and the negatives of the prime numbers. The elements $1$ and $-1$ are not
irreducible (they fail the first condition, as they are invertible), and the
composite positive integers are not irreducible either (they fail the second
condition). On the other hand, $\mathbb{Q}$ has no irreducible elements
(indeed, $0\in\mathbb{Q}$ fails the second condition, while all other elements
fail the first one).

The irreducible elements of $\mathbb{Z}\left[  \mathbf{x}\right]  $ are the
irreducible polynomials, in the appropriate sense. For example, $2$, $x_{1}$,
$x_{2}^{2}+x_{3}^{2}$ and $x_{1}^{2}-2$ are irreducible, whereas $6$,
$x_{1}x_{2}$, $x_{2}^{2}-x_{3}^{2}$ and $x_{1}^{2}-4$ are not.

The irreducible elements of $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ are
\textquotedblleft more or less\textquotedblright\ the same, but only more or
less. The situation is slightly different because all Laurent monomials have
become invertible in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $. Thus, for
example, $x_{1}$, although irreducible in $\mathbb{Z}\left[  \mathbf{x}%
\right]  $, is not irreducible in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]
$, because it is invertible in the latter ring. Exercise \ref{exe.invertible}
\textbf{(c)} below shows that \textquotedblleft
almost-monomials\textquotedblright\ ($\pm x_{1},\pm x_{2},\ldots,\pm x_{n}$)
are essentially the only exceptions.

\begin{exercise}
\label{exe.invertible}\textbf{(a)} Show that a polynomial $P\in\mathbb{Z}%
\left[  \mathbf{x}\right]  $ is invertible in $\mathbb{Z}\left[
\mathbf{x}\right]  $ if and only if it equals $1$ or $-1$.

\textbf{(b)} Show that a Laurent polynomial $P\in\mathbb{Z}\left[
\mathbf{x}^{\pm1}\right]  $ is invertible in $\mathbb{Z}\left[  \mathbf{x}%
^{\pm1}\right]  $ if and only if either $P$ or $-P$ is a (single) Laurent monomial.

\textbf{(c)} Let $P\in\mathbb{Z}\left[  \mathbf{x}\right]  $ be a polynomial
such that none of the variables $x_{1},x_{2},\ldots,x_{n}$ divides $P$ (in
$\mathbb{Z}\left[  \mathbf{x}\right]  $). Then, show that $P$ is irreducible
as an element of $\mathbb{Z}\left[  \mathbf{x}\right]  $ if and only if $P$ is
irreducible as an element of $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $.
\end{exercise}

We say that two elements $a$ and $b$ of a commutative ring $R$ are
\textit{coprime} if every common divisor of $a$ and $b$ is invertible. When
$R=\mathbb{Z}$, this notion of coprimality is exactly the classical notion of
coprimality for integers.

\subsection{Monomial substitutions}

\begin{definition}
Let $A\in\mathbb{Z}^{n\times n}$. If $\mathbf{u}=\left(  u_{1},u_{2}%
,\ldots,u_{n}\right)  $ is an $n$-tuple of invertible elements of a
commutative ring $R$, then we let $A_{\ast}\mathbf{u}$ denote the $n$-tuple
defined as follows: Write $A$ in the form $A=\left(  a_{i,j}\right)  _{1\leq
i,j\leq n}=\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\
a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n,1} & a_{n,2} & \cdots & a_{n,n}%
\end{array}
\right)  $. Then, set%
\[
A_{\ast}\mathbf{u}=\left(  u_{1}^{a_{1,1}}u_{2}^{a_{1,2}}\cdots u_{n}%
^{a_{1,n}},u_{1}^{a_{2,1}}u_{2}^{a_{2,2}}\cdots u_{n}^{a_{2,n}},\ldots
,u_{1}^{a_{n,1}}u_{2}^{a_{n,2}}\cdots u_{n}^{a_{n,n}}\right)  .
\]
(This is the $n$-tuple whose $j$-th entry is $\prod_{i=1}^{n}u_{i}^{a_{j,i}}%
$.) Notice that $A_{\ast}\mathbf{u}$ is again an $n$-tuple of invertible
elements of $R$.
\end{definition}

For a trivial example, $\left(  I_{n}\right)  _{\ast}\mathbf{u}=\mathbf{u}$
for every $n$-tuple $\mathbf{u}$. Other examples are%
\begin{align*}
\left(
\begin{array}
[c]{cc}%
1 & 0\\
2 & 3
\end{array}
\right)  _{\ast}\left(  u_{1},u_{2}\right)   &  =\left(  u_{1}^{1}u_{2}%
^{0},u_{1}^{2}u_{2}^{3}\right)  =\left(  u_{1},u_{1}^{2}u_{2}^{3}\right)  ;\\
\left(
\begin{array}
[c]{cc}%
1 & 2\\
0 & 3
\end{array}
\right)  _{\ast}\left(  u_{1},u_{2}\right)   &  =\left(  u_{1}^{1}u_{2}%
^{2},u_{1}^{0}u_{2}^{3}\right)  =\left(  u_{1}u_{2}^{2},u_{2}^{3}\right)  .
\end{align*}


\begin{exercise}
\label{exe.AB*}Let $A\in\mathbb{Z}^{n\times n}$ and $B\in\mathbb{Z}^{n\times
n}$. Prove that $A_{\ast}\left(  B_{\ast}\mathbf{u}\right)  =\left(
AB\right)  _{\ast}\mathbf{u}$ whenever $\mathbf{u}$ is an $n$-tuple of
invertible elements of a commutative ring $R$.
\end{exercise}

A consequence of Exercise \ref{exe.AB*} is that every $A\in\operatorname*{GL}%
\nolimits_{n}\left(  \mathbb{Z}\right)  $ and every $n$-tuple $\mathbf{u}$ of
invertible elements of a commutative ring $R$ satisfy%
\begin{equation}
\left(  A^{-1}\right)  _{\ast}\left(  A_{\ast}\mathbf{u}\right)  =\left(
\underbrace{A^{-1}A}_{=I_{n}}\right)  _{\ast}\mathbf{u}=\left(  I_{n}\right)
_{\ast}\mathbf{u}=\mathbf{u.} \label{eq.AA-1*}%
\end{equation}


Now, if $\mathbf{u}$ is an $n$-tuple of invertible elements of a commutative
ring $R$, and if $P\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ is a
Laurent polynomial, then we can substitute the entries of $\mathbf{u}$ for the
variables $x_{1},x_{2},\ldots,x_{n}$ in $P$, and obtain an element of $R$,
which we denote by $P\left[  \mathbf{u}\right]  $. (It is more commonly
denoted by $P\left(  \mathbf{u}\right)  $, but we prefer to write $P\left[
\mathbf{u}\right]  $ due to a lesser chance of confusing it with a product
when $\mathbf{u}$ is a $1$-tuple.) For instance, if $n=2$, $R=\mathbb{Q}$,
$\mathbf{u}=\left(  1,3\right)  $ and $P=\dfrac{x_{1}}{x_{2}}-\dfrac{x_{2}%
}{x_{1}}$, then $P\left[  \mathbf{u}\right]  =\dfrac{1}{3}-\dfrac{3}%
{1}=-\dfrac{8}{3}$. Of course, every $P\in\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  $ satisfies $P\left[  \mathbf{x}\right]  =P$, because substituting
the variables $x_{1},x_{2},\ldots,x_{n}$ for themselves does not change $P$.

We can combine the notations we have now introduced to describe certain
substitutions in Laurent polynomials. Namely, if $A\in\mathbb{Z}^{n\times n}$
is a matrix, then $A_{\ast}\mathbf{x}$ is an $n$-tuple of Laurent monomials
(recall that $\mathbf{x}=\left(  x_{1},x_{2},\ldots,x_{n}\right)  $), and thus
$P\left[  A_{\ast}\mathbf{x}\right]  $ is defined for every Laurent polynomial
$P\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $. For instance,%
\[
P\left[  \left(
\begin{array}
[c]{cc}%
1 & 0\\
2 & 3
\end{array}
\right)  _{\ast}\mathbf{x}\right]  =P\left[  x_{1},x_{1}^{2}x_{2}^{3}\right]
.
\]


\begin{exercise}
\label{exe.subst.irred-coprime}Let $A\in\operatorname*{GL}\nolimits_{n}\left(
\mathbb{Z}\right)  $.

\textbf{(a)} If $P\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ is a
Laurent polynomial, then show that $P$ is irreducible if and only if $P\left[
A_{\ast}\mathbf{x}\right]  $ is irreducible.

\textbf{(b)} If $P\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ and
$Q\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ are two Laurent
polynomials, then show that $P$ and $Q$ are coprime if and only if $P\left[
A_{\ast}\mathbf{x}\right]  $ and $Q\left[  A_{\ast}\mathbf{x}\right]  $ are coprime.
\end{exercise}

Exercise \ref{exe.subst.irred-coprime} \textbf{(a)} shows that, for example,
if $n=2$, then a Laurent polynomial $P=P\left[  x_{1},x_{2}\right]
\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ is irreducible if and only if
$P\left[  x_{1},x_{1}x_{2}\right]  \in\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  $ is irreducible (because $\left(  x_{1},x_{1}x_{2}\right)
=\left(
\begin{array}
[c]{cc}%
1 & 0\\
1 & 1
\end{array}
\right)  _{\ast}\mathbf{x}$).

If $\mathbf{v}=\left(  v_{1},v_{2},\ldots,v_{n}\right)  ^{T}\in\mathbb{Z}^{n}$
is any vector, then we define a Laurent monomial $\mathbf{x}^{\mathbf{v}}%
\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ by $\mathbf{x}^{\mathbf{v}%
}=x_{1}^{v_{1}}x_{2}^{v_{2}}\cdots x_{n}^{v_{n}}$. This is a monomial in
$\mathbb{Z}\left[  \mathbf{x}\right]  $ when all entries of $\mathbf{v}$ are nonnegative.

\begin{exercise}
\label{exe.subst.monomial-simpl}Let $n$ be a positive integer. Let
$\mathbf{v}\in\mathbb{Z}^{n}$ and let $g=\gcd\mathbf{v}$. Prove that there
exists an $A\in\operatorname*{GL}\nolimits_{n}\left(  \mathbb{Z}\right)  $
such that $\mathbf{x}^{\mathbf{v}}=x_{1}^{g}\left[  A_{\ast}\mathbf{x}\right]
$. (To make sense of the notation $x_{1}^{g}\left[  A_{\ast}\mathbf{x}\right]
$, recall that $x_{1}^{g}$ is a Laurent monomial and thus a Laurent
polynomial, and that $A_{\ast}\mathbf{x}$ is an $n$-tuple of Laurent
monomials; thus $x_{1}^{g}\left[  A_{\ast}\mathbf{x}\right]  $ means the
result of substituting $A_{\ast}\mathbf{x}$ for $\mathbf{x}$ in $x_{1}^{g}$.
\end{exercise}

This exercise is useful: It shows that every monomial $\mathbf{x}^{\mathbf{v}%
}$ can be obtained from the monomial $x_{1}^{g}$ (for $g=\gcd\mathbf{v}$) by
an invertible substitution of Laurent monomials for its variables. (Why
invertible? Because (\ref{eq.AA-1*}) shows that it is undone by a similar
substitution using the matrix $A^{-1}$.) Let us get some mileage out of this:

\begin{exercise}
\label{exe.binomial.irred}Let $\mathbf{v}\in\mathbb{Z}^{n}$ be such that
$\gcd\mathbf{v}=1$. Prove that the Laurent polynomial $\mathbf{x}^{\mathbf{v}%
}+1$ is irreducible in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $.
\end{exercise}

Here are some examples for Exercise \ref{exe.binomial.irred}:

\begin{itemize}
\item For $n=4$ and $\mathbf{v}=\left(  2,3,0,-4\right)  ^{T}$, we have
$\mathbf{x}^{\mathbf{v}}=x_{1}^{2}x_{2}^{3}x_{4}^{-4}$, and thus Exercise
\ref{exe.binomial.irred} yields that the Laurent polynomial $x_{1}^{2}%
x_{2}^{3}x_{4}^{-4}+1$ is irreducible in $\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  $.

\item For $n=2$ and $\mathbf{v}=\left(  6,9\right)  ^{T}$, we have
$\mathbf{x}^{\mathbf{v}}=x_{1}^{6}x_{2}^{9}$, and Exercise
\ref{exe.binomial.irred} cannot be applied (because $\gcd\mathbf{v}=3\neq1$).
Nor does its consequent hold: The Laurent polynomial $x_{1}^{6}x_{2}^{9}+1$
factors as $x_{1}^{6}x_{2}^{9}+1=\left(  x_{1}^{2}x_{2}^{3}+1\right)  \left(
x_{1}^{4}x_{2}^{6}-x_{1}^{2}x_{2}^{3}+1\right)  $, and thus is not irreducible.

\item For $n=2$ and $\mathbf{v}=\left(  2,4\right)  ^{T}$, we have
$\mathbf{x}^{\mathbf{v}}=x_{1}^{2}x_{2}^{4}$. Here, Exercise
\ref{exe.binomial.irred} cannot be applied either, but the Laurent polynomial
$x_{1}^{2}x_{2}^{4}+1$ is nevertheless irreducible. So the converse of
Exercise \ref{exe.binomial.irred} does not hold!
\end{itemize}

The following exercise might help solving Exercise \ref{exe.binomial.irred}:

\begin{exercise}
\label{exe.binomial.irred.1}Let $n$ be a positive integer. Let $h$ be a
positive integer. Let $P\in\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ be a
Laurent polynomial which divides $x_{1}^{h}+1$. Show that $P$ has the form
$\mathbf{x}^{\mathbf{v}}\cdot Q\left(  x_{1}\right)  $, where $\mathbf{x}%
^{\mathbf{v}}$ is a Laurent monomial and $Q\in\mathbb{Z}\left[  t\right]  $ is
a polynomial in a single variable $t$.
\end{exercise}

Exercise \ref{exe.binomial.irred} discussed irreducibility. Let us now study coprimality:

\begin{exercise}
\label{exe.binomial.coprime}Let $\mathbf{v}\in\mathbb{Z}^{n}$ and
$\mathbf{w}\in\mathbb{Z}^{n}$. Prove that if the Laurent polynomials
$\mathbf{x}^{\mathbf{v}}+1$ and $\mathbf{x}^{\mathbf{w}}+1$ are not coprime in
$\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $, then the vectors $\mathbf{v}$
and $\mathbf{w}$ are proportional (i.e., there exists some integers $b$ and
$c$ which are not both $0$ and which satisfy $b\mathbf{v}=c\mathbf{w}$).
\end{exercise}

Note that more can be said: Namely, the Laurent polynomials $\mathbf{x}%
^{\mathbf{v}}+1$ and $\mathbf{x}^{\mathbf{w}}+1$ are coprime in $\mathbb{Z}%
\left[  \mathbf{x}^{\pm1}\right]  $ if and only if there exist no odd coprime
integers $b$ and $c$ such that $b\mathbf{v}=c\mathbf{w}$. This is what Fomin
and Zelevinsky need to prove \cite[Lemma 3.1]{BFZ-CA3}; but it is not needed
for proving \cite[Proposition 1.8]{BFZ-CA3}, and it is harder to show, so you
can just as well ignore it.

\subsection{Replacing \cite[Lemma 3.1]{BFZ-CA3}}

Now, let us show how to use Exercise \ref{exe.binomial.coprime} in place of
\cite[Lemma 3.1]{BFZ-CA3} in the proof of \cite[Proposition 1.8]{BFZ-CA3}.

We use the notations of \cite{BFZ-CA3}. Let $\Sigma=\left(  \mathbf{x}%
,\widetilde{B}\right)  $ be a seed of geometric type. Assume that the matrix
$\widetilde{B}$ has full rank. We need to check that all seeds mutation
equivalent to $\Sigma$ are coprime.

We shall prove that
\begin{equation}
\text{the seed }\Sigma\text{ is coprime.} \label{pf.prop.1.18.goal1}%
\end{equation}


Why is this sufficient for proving \cite[Proposition 1.8]{BFZ-CA3}? Well,
assume that we have proven (\ref{pf.prop.1.18.goal1}). Now, \cite[Lemma
3.2]{BFZ-CA3}\footnote{which, by the way, is a generalization of
\cite[Exercise 2.4 \textbf{(a)}]{Lampe}} yields that every seed mutation
equivalent to $\Sigma$ has full rank. Then, this seed must be coprime (by
(\ref{pf.prop.1.18.goal1}), applied to this seed instead of $\Sigma
$)\ \ \ \ \footnote{Here, we are using the fact that coprimality of a seed is
defined in terms of the seed alone. Thus, if $\left(  \mathbf{y}%
,\widetilde{C}\right)  $ is a seed in $\mathcal{F}$ obtained by some mutations
from an original seed $\left(  \mathbf{x},\widetilde{B}\right)  $, then
coprimality of the seed $\left(  \mathbf{y},\widetilde{C}\right)  $ means that
the polynomials appearing in its exchange relations are pairwise coprime in
$\mathbb{ZP}\left[  \mathbf{y}\right]  $, not in $\mathbb{ZP}\left[
\mathbf{x}\right]  $.}. Therefore, \cite[Proposition 1.8]{BFZ-CA3} is proven
under the assumption that (\ref{pf.prop.1.18.goal1}) holds.

So it remains to prove (\ref{pf.prop.1.18.goal1}). Indeed, recall what it
means for the seed $\Sigma$ to be coprime: It means that the polynomials
$P_{1},P_{2},\ldots,P_{n}$ appearing in the exchange relations \cite[(1.3)]%
{BFZ-CA3} are coprime in $\mathbb{ZP}\left[  \mathbf{x}\right]  $%
.\ \ \ \ \footnote{Recall that $\mathbb{ZP}$ is the Laurent polynomial ring
$\mathbb{Z}\left[  x_{n+1}^{\pm1},x_{n+2}^{\pm1},\ldots,x_{m}^{\pm1}\right]  $
here.} Since our seed is of geometric type, we have%
\[
p_{j}^{+}=\prod_{\substack{n<i\leq m;\\b_{i,j}>0}}x_{i}^{b_{i,j}%
}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ p_{j}^{-}=\prod
_{\substack{n<i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}%
\]
for all $j$. This allows us to simplify the formula \cite[(1.3)]{BFZ-CA3} for
$P_{j}\left(  \mathbf{x}\right)  $ as follows:%
\begin{align}
P_{j}\left(  \mathbf{x}\right)   &  =\underbrace{p_{j}^{+}}_{=\prod
_{\substack{n<i\leq m;\\b_{i,j}>0}}x_{i}^{b_{i,j}}}\prod_{\substack{1\leq
i\leq n;\\b_{i,j}>0}}x_{i}^{b_{i,j}}+\underbrace{p_{j}^{-}}_{=\prod
_{\substack{n<i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}}\prod_{\substack{1\leq
i\leq n;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}\nonumber\\
&  =\underbrace{\left(  \prod_{\substack{n<i\leq m;\\b_{i,j}>0}}x_{i}%
^{b_{i,j}}\right)  \left(  \prod_{\substack{1\leq i\leq n;\\b_{i,j}>0}%
}x_{i}^{b_{i,j}}\right)  }_{=\prod_{\substack{1\leq i\leq m;\\b_{i,j}>0}%
}x_{i}^{b_{i,j}}}+\underbrace{\left(  \prod_{\substack{n<i\leq m;\\b_{i,j}%
<0}}x_{i}^{-b_{i,j}}\right)  \left(  \prod_{\substack{1\leq i\leq
n;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}\right)  }_{\substack{=\prod_{\substack{1\leq
i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}}}\nonumber\\
&  =\prod_{\substack{1\leq i\leq m;\\b_{i,j}>0}}x_{i}^{b_{i,j}}+\prod
_{\substack{1\leq i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}.
\label{pf.prop.1.18.4}%
\end{align}
We can further transform the right hand side by noticing that%
\begin{align*}
\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}  &  =\left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}\right)  \left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}=0}}\underbrace{x_{i}^{-b_{i,j}}%
}_{=x_{i}^{-0}=x_{i}^{0}=1}\right) \\
&  =\left(  \prod_{\substack{1\leq i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}%
}\right)  \underbrace{\left(  \prod_{\substack{1\leq i\leq m;\\b_{i,j}%
=0}}1\right)  }_{=1}=\prod_{\substack{1\leq i\leq m;\\b_{i,j}<0}%
}x_{i}^{-b_{i,j}}.
\end{align*}
Thus, (\ref{pf.prop.1.18.4}) becomes%
\begin{equation}
P_{j}\left(  \mathbf{x}\right)  =\prod_{\substack{1\leq i\leq m;\\b_{i,j}%
>0}}x_{i}^{b_{i,j}}+\underbrace{\prod_{\substack{1\leq i\leq m;\\b_{i,j}%
<0}}x_{i}^{-b_{i,j}}}_{=\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}%
}x_{i}^{-b_{i,j}}}=\prod_{\substack{1\leq i\leq m;\\b_{i,j}>0}}x_{i}^{b_{i,j}%
}+\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}.
\label{pf.prop.1.18.5}%
\end{equation}
So far we have been working in $\mathbb{Z}\left[  \mathbf{x}\right]  $.
(Indeed, all exponents on the right hand side of (\ref{pf.prop.1.18.5}) are
nonnegative.) Let us now work in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]
$; this allows us to get an even simpler form for $P_{j}\left(  \mathbf{x}%
\right)  $: Namely,%
\begin{align}
P_{j}\left(  \mathbf{x}\right)   &  =\underbrace{\prod_{\substack{1\leq i\leq
m;\\b_{i,j}>0}}x_{i}^{b_{i,j}}}_{\substack{=\left(  \prod_{1\leq i\leq m}%
x_{i}^{b_{i,j}}\right)  /\left(  \prod_{\substack{1\leq i\leq m;\\b_{i,j}%
\leq0}}x_{i}^{b_{i,j}}\right)  \\\text{(since the }i\text{'s which satisfy
}b_{i,j}>0\text{ are exactly}\\\text{the }i\text{'s which do not satisfy
}b_{i,j}\leq0\text{)}}}+\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}%
}x_{i}^{-b_{i,j}}\nonumber\\
&  =\left(  \prod_{1\leq i\leq m}x_{i}^{b_{i,j}}\right)  /\left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{b_{i,j}}\right)
+\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\nonumber\\
&  =\left(  \prod_{1\leq i\leq m}x_{i}^{b_{i,j}}\right)  \left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\right)
+\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\nonumber\\
&  =\left(  \prod_{1\leq i\leq m}x_{i}^{b_{i,j}}+1\right)  \left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\right)  .
\label{pf.prop.1.18.6}%
\end{align}


For every $j\in\left\{  1,2,\ldots,n\right\}  $, let $\mathbf{b}_{j}$ be the
$j$-th column of the matrix $\widetilde{B}$. Then, $\mathbf{b}_{j}=\left(
b_{1,j},b_{2,j},\ldots,b_{m,j}\right)  ^{T}\in\mathbb{Z}^{m}$, and%
\[
\mathbf{x}^{\mathbf{b}_{j}}=\prod_{1\leq i\leq m}x_{i}^{b_{i,j}}.
\]
Hence, (\ref{pf.prop.1.18.6}) simplifies as follows:%
\begin{equation}
P_{j}\left(  \mathbf{x}\right)  =\left(  \underbrace{\prod_{1\leq i\leq
m}x_{i}^{b_{i,j}}}_{=\mathbf{x}^{\mathbf{b}_{j}}}+1\right)  \left(
\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\right)
=\left(  \mathbf{x}^{\mathbf{b}_{j}}+1\right)  \left(  \prod_{\substack{1\leq
i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}\right)  . \label{pf.prop.1.18.7}%
\end{equation}
Hence,%
\begin{equation}
P_{j}\left(  \mathbf{x}\right)  \mid\mathbf{x}^{\mathbf{b}_{j}}+1\text{ in
}\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  \label{pf.prop.1.18.8}%
\end{equation}
(because $\prod_{\substack{1\leq i\leq m;\\b_{i,j}\leq0}}x_{i}^{-b_{i,j}}$ is
just a Laurent monomial, and thus is invertible in $\mathbb{Z}\left[
\mathbf{x}^{\pm1}\right]  $).

Now, let us finally prove that the seed $\Sigma$ is coprime. To do so, we need
to show that the polynomials $P_{1},P_{2},\ldots,P_{n}$ are pairwise coprime
in $\mathbb{ZP}\left[  \mathbf{x}\right]  $. Indeed, let $i$ and $j$ be two
distinct elements of $\left\{  1,2,\ldots,n\right\}  $. We need to show that
$P_{i}$ and $P_{j}$ are coprime in $\mathbb{ZP}\left[  \mathbf{x}\right]  $.

Assume the contrary. Then, there exists a non-invertible polynomial
$g\in\mathbb{ZP}\left[  \mathbf{x}\right]  $ which divides each of $P_{i}$ and
$P_{j}$ in $\mathbb{ZP}\left[  \mathbf{x}\right]  $. Consider this $g$. (We
call $g$ a \textquotedblleft polynomial\textquotedblright, but in truth it is
a polynomial over $\mathbb{ZP}$, so it can have inverses of the frozen
variables $x_{n+1},x_{n+2},\ldots,x_{m}$ (but not of $x_{1},x_{2},\ldots
,x_{n}$).)

We have $g\mid P_{j}=P_{j}\left(  \mathbf{x}\right)  \mid\mathbf{x}%
^{\mathbf{b}_{j}}+1$ in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $
(because of (\ref{pf.prop.1.18.8})). Similarly, $g\mid\mathbf{x}%
^{\mathbf{b}_{i}}+1$ in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $.

The matrix $\widetilde{B}$ has full rank. Thus, its columns are linearly
independent. In particular, no two of its columns are proportional. Thus, the
vectors $\mathbf{b}_{i}$ and $\mathbf{b}_{j}$ (being two distinct columns of
$\widetilde{B}$) are not proportional. Thus, the Laurent polynomials
$\mathbf{x}^{\mathbf{b}_{i}}+1$ and $\mathbf{x}^{\mathbf{b}_{j}}+1$ must be
coprime in $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  $ (because otherwise,
Exercise \ref{exe.binomial.coprime} (applied to $m$, $\mathbf{b}_{i}$ and
$\mathbf{b}_{j}$ instead of $n$, $\mathbf{v}$ and $\mathbf{w}$) would yield
that the vectors $\mathbf{b}_{i}$ and $\mathbf{b}_{j}$ are proportional). In
other words, every Laurent polynomial $h\in\mathbb{Z}\left[  \mathbf{x}^{\pm
1}\right]  $ which divides both $\mathbf{x}^{\mathbf{b}_{i}}+1$ and
$\mathbf{x}^{\mathbf{b}_{j}}+1$ must be invertible in $\mathbb{Z}\left[
\mathbf{x}^{\pm1}\right]  $. Thus, $g$ is invertible in $\mathbb{Z}\left[
\mathbf{x}^{\pm1}\right]  $ (since $g$ is a Laurent polynomial which divides
both $\mathbf{x}^{\mathbf{b}_{i}}+1$ and $\mathbf{x}^{\mathbf{b}_{j}}+1$).

We are almost done: We know that $g$ is invertible in $\mathbb{Z}\left[
\mathbf{x}^{\pm1}\right]  $ but non-invertible in $\mathbb{ZP}\left[
\mathbf{x}\right]  $. These two facts almost make a contradiction, but not
quite, because $\mathbb{Z}\left[  \mathbf{x}^{\pm1}\right]  \neq
\mathbb{ZP}\left[  \mathbf{x}\right]  $ in general. But Exercise
\ref{exe.invertible} \textbf{(b)} (applied to $P=g$) yields that either $g$ or
$-g$ is a (single) Laurent monomial. We WLOG assume that $g$ is a Laurent
monomial (because otherwise, we can just replace $g$ by $-g$ and get back into
this case). In other words, $g=x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}$
for some $k_{1},k_{2},\ldots,k_{m}\in\mathbb{Z}$. Consider these $k_{1}%
,k_{2},\ldots,k_{m}$.

Since $x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}=g\in\mathbb{ZP}\left[
\mathbf{x}\right]  $, we must have $k_{\ell}\geq0$ for all $\ell\leq n$
(because the only indeterminates which are invertible in $\mathbb{ZP}\left[
\mathbf{x}\right]  $ are $x_{n+1},x_{n+2},\ldots,x_{m}$). But if we have
$k_{\ell}=0$ for all $\ell\leq n$, then the monomial $g$ is invertible in
$\mathbb{ZP}\left[  \mathbf{x}\right]  $ (because it is a Laurent monomial in
the indeterminates $x_{n+1},x_{n+2},\ldots,x_{m}$ only, and such monomials are
already invertible in $\mathbb{ZP}$), which is impossible (because $g$ is
non-invertible in $\mathbb{ZP}\left[  \mathbf{x}\right]  $ by definition).
Therefore, there exists some $\ell\leq n$ such that $k_{\ell}>0$. Consider
this $\ell$. Clearly, $k_{\ell}>0$ shows that $x_{\ell}\mid g$ in
$\mathbb{ZP}\left[  \mathbf{x}\right]  $. Thus,%
\[
x_{\ell}\mid g\mid P_{j}=P_{j}\left(  \mathbf{x}\right)  =\prod
_{\substack{1\leq i\leq m;\\b_{i,j}>0}}x_{i}^{b_{i,j}}+\prod_{\substack{1\leq
i\leq m;\\b_{i,j}<0}}x_{i}^{-b_{i,j}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.1.18.4})}\right)
\]
in $\mathbb{ZP}\left[  \mathbf{x}\right]  $. Hence, the term $x_{\ell}$ must
appear in both monomials $\prod_{\substack{1\leq i\leq m;\\b_{i,j}>0}%
}x_{i}^{b_{i,j}}$ and $\prod_{\substack{1\leq i\leq m;\\b_{i,j}<0}%
}x_{i}^{-b_{i,j}}$ (because these two monomials surely cannot cancel each
other, and because $x_{\ell}$ is not invertible in $\mathbb{ZP}\left[
\mathbf{x}\right]  $). Therefore, $\ell$ must both satisfy $b_{i,\ell}>0$ (so
that it can appear in the first monomial) and satisfy $b_{i,\ell}<0$ (so that
it can appear in the second monomial). But this is clearly absurd. This gives
us the contradiction we wanted, and thus (\ref{pf.prop.1.18.goal1}) is proven.
Hence, \cite[Proposition 1.8]{BFZ-CA3} is proven.

\begin{thebibliography}{9999999}                                                                                          %


\bibitem[BFZ-CA3]{BFZ-CA3}Arkady Berenstein, Sergey Fomin, Andrei Zelevinsky,
\textit{Cluster algebras III: Upper bounds and double Bruhat cells},
\href{http://arxiv.org/abs/math/0305434v3}{arXiv preprint
arXiv:math/0305434v3}. (This was later published in: Duke Mathematical
Journal, Vol. 126, No. 1, 2005.)

\bibitem[Lampe]{Lampe}Philipp Lampe, \textit{Cluster algebras},\newline%
\texttt{\href{http://www.math.uni-bielefeld.de/~lampe/teaching/cluster/cluster.pdf}{http://www.math.uni-bielefeld.de/\symbol{126}%
lampe/teaching/cluster/cluster.pdf}} .

A version with my corrections:\newline%
\texttt{\href{https://www.dropbox.com/s/aush67ecrx6twlf/cluster - version 4 dec 2013 EV.pdf?dl=0}{https://www.dropbox.com/s/aush67ecrx6twlf/cluster
- version 4 dec 2013 EV.pdf?dl=0}}
\end{thebibliography}


\end{document}