\documentclass[ALCO,ThmDefs,Unicode,epreuves,published]{cedram}
\OneNumberAllTheorems
\numberwithin{equation}{section}
%\usepackage{longtable}
\usepackage{xy,amscd}
%\usepackage{comment}
%\usepackage{epsfig}
%\usepackage{rotating}
%\usepackage{xspace}
%\usepackage{dashbox}
%\usepackage{float}
\xyoption{all}
\usepackage{tikz}
\usetikzlibrary{arrows,decorations.pathmorphing,decorations.pathreplacing,%
positioning,shapes.geometric,shapes.misc,decorations.markings,decorations.fractals,calc,patterns}
\newcommand{\CC }{\mathbb{C}}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\md}{mod}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%1
\author{\firstname{Michael} \lastname{Cuntz}}
\address{Leibniz Universit{\"a}t Hannover,
Institut f{\"u}r Algebra, Zahlentheorie und Diskrete Mathematik,
Fakult{\"a}t f{\"u}r Mathematik und Physik,
Welfengarten 1, D-30167 Hannover, Germany}
\email{cuntz@math.uni-hannover.de}
\urladdr{https://www.iazd.uni-hannover.de/cuntz}
%%%2
\author{\firstname{Thorsten} \lastname{Holm}}
\address{Leibniz Universit{\"a}t Hannover,
Institut f{\"u}r Algebra, Zahlentheorie und Diskrete Mathematik,
Fakult{\"a}t f{\"u}r Mathematik und Physik,
Welfengarten 1, D-30167 Hannover, Germany}
\email{holm@math.uni-hannover.de}
\urladdr{https://www.iazd.uni-hannover.de/tholm}
%%%%% Sujet
\keywords{Frieze pattern, tame frieze pattern, quiddity cycle, cluster algebra, polygon, triangulation.}
\subjclass{05E15, 05E99, 13F60, 51M20}
%%%%% Gestion
\DOI{10.5802/alco.180}
\datereceived{2020-04-06}
\daterevised{2021-03-04}
\dateaccepted{2021-04-23}
%%%%% Titre et résumé
\title[Subpolygons in Conway--Coxeter frieze patterns]
{Subpolygons in Conway--Coxeter frieze patterns}
\begin{abstract}
Friezes with coefficients are maps assigning numbers to the edges and diagonals of a regular polygon such that all Ptolemy relations for crossing diagonals are satisfied. Among these, the classic Conway--Coxeter friezes are the ones where all values are positive integers and all edges have value 1. Every subpolygon of a Conway--Coxeter frieze yields a frieze with coefficients over the positive integers. In this paper we give a complete arithmetic criterion for which friezes with coefficients appear as subpolygons of Conway--Coxeter friezes. This generalizes a result of our earlier paper with Peter J{\o}rgensen from triangles to subpolygons of arbitrary size.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\datepublished{2021-08-17}
\begin{document}
\maketitle
\section{Introduction}
Frieze patterns are infinite configurations of numbers introduced by
Coxeter~\cite{Cox71} in the 1970s, the shape of which is reminiscent of
friezes which appeared in architecture and decorative art for centuries.
The entries in a frieze pattern have to satisfy a specific rule for each
neighbouring $2\times 2$-determinant. This frieze pattern rule is for example implicitly contained in the structure of smooth toric varieties~\cite[1.6]{Oda} and has been essential in the study of continued fractions more than a century earlier~\cite[\S~51]{b-Perron29}.
It also reappeared some 30 years after Coxeter's definition as the exchange condition in Fomin and Zelevinsky's
cluster algebras, mathematical structures
which became highly influential in many areas of modern
mathematics. This connection to cluster algebras initiated an intensive
renewed interest in frieze patterns in recent years, see~\cite{MG15}. Whereas classic frieze
patterns are bounded by rows of 1's, to capture cluster algebras with
coefficients more general boundary rows and a modified rule for
$2\times 2$-determinants are needed. The resulting frieze patterns with coefficients
have been suggested by Propp~\cite{Propp} and recently their fundamental
properties have been studied in~\cite{CHJ}. Among other things, it is proven in
\cite{CHJ} that a frieze pattern with coefficients can be viewed as a map on
edges and diagonals of a regular polygon (with values in a suitable number
system) satisfying the Ptolemy relations for any pair of crossing diagonals;
we then speak of a frieze with coefficients to distinguish these viewpoints.
For classic frieze patterns this viewpoint was well-known, not least for
classic frieze patterns over positive integers, where a beautiful result of
Conway and Coxeter~\cite{CC73} shows that such frieze patterns are in
bijection with triangulations of regular polygons.
Any subpolygon of a Conway--Coxeter frieze yields a
frieze with coefficients over the positive integers. The natural question
arises which friezes with coefficients actually appear as subpolygons of
Conway--Coxeter friezes. A solution would give new insight into the subtle
arithmetic relations of entries in Conway--Coxeter friezes, and hence
triangulations of polygons.
It is a special property of a frieze with coefficients to appear in a Conway--Coxeter
frieze. For instance, we observed in~\cite{CHJ} that for every triangle in
a Conway--Coxeter frieze the greatest common divisors of any two of the three
numbers must be equal. This already rules out many friezes with coefficients.
Still, there are many friezes with coefficients where the condition on the greatest
common divisors holds for all triangles and then it is a priori difficult to
determine whether such a frieze with coefficients appears in a Conway--Coxeter
frieze, or not. As one main result of~\cite{CHJ} we have shown that for triangles
this happens if and only if the three numbers are all odd or do not have the
same 2-valuation.
\looseness-1
Recall that for a prime number $p$ and a positive integer $m$, the $p$-valuation
$\nu_p(m)$ is the maximal non-negative integer $\ell$ such that $p^{\ell}$ divides $m$
but $p^{\ell+1}$ does not divide $m$.
%\smallskip
The aim of this paper is to give a complete solution to this problem for polygons of
arbitrary size, that is, we present a
characterization of those friezes with coefficients which appear as subpolygons
in Conway--Coxeter friezes.
\begin{theo*}
Let $\mathcal{C}$ be a frieze with coefficients
on an $n$-gon over the positive integers. Then $\mathcal{C}$ appears as a subpolygon
of some Conway--Coxeter frieze if and only if the following conditions are
satisfied:
\begin{enumerate}
\item \label{cond0:gcd}
For any triangle $(a,b,c)$ in $\mathcal{C}$ we have
$\gcd(a,b)=\gcd(b,c)=\gcd(a,c)$.
\item \label{cond0:p+1}
Let $p 0}$.
A fundamental result of Conway and Coxeter states that these frieze patterns are in bijection with triangulations of regular polygons, see~\cite{CC73}.
\item There is a close connection between frieze patterns and Fomin and
Zelevinsky's cluster algebras. Namely,
starting with a set of indeterminates on a row in the frieze pattern,
the frieze conditions ($E_{i,j}$) produce the cluster variables of the
cluster algebra of Dynkin type $A$. Whereas the classic Conway--Coxeter frieze
patterns correspond to cluster algebras without coefficients, the more general
frieze patterns with coefficients correspond to the cluster algebras of
Dynkin type A with boundary edges acting as frozen variables.
From the cluster algebras perspective this is the main motivation to study
frieze patterns with coefficients.
\end{enumerate}
\end{rema}
In general, there are too many frieze patterns
with coefficients to expect a satisfactory theory, even in the case of classic frieze
patterns,
see~\cite[Section~3]{Cuntz-wild} for an illustration of the case of wild $\SL_3$-frieze patterns. Therefore, it is very common in the literature to
restrict to tame frieze patterns. Many interesting frieze patterns
are tame, \eg all frieze patterns without zero entries, see
\cite[Proposition~2.4]{CHJ} for a proof.
\begin{defi} \label{def:tame}
Let $\mathcal{C}$ be a frieze pattern with coefficients as in Definition~\ref{def:frieze}.
Then $\mathcal{C}$ is called {\em tame} if every complete adjacent $3\times 3$-submatrix of
$\mathcal{C}$ has determinant 0.
\end{defi}
The entries of a tame frieze pattern with coefficients are closely linked
by many remarkable equations (in addition to the defining equations ($E_{i,j}$)
in Definition~\ref{def:frieze}). We restate some results from~\cite{CHJ}
which are relevant for the present paper.
First, the entries in a tame frieze pattern are invariant under a glide symmetry.
\begin{prop}[{\cite[Theorem~2.4]{CHJ}}] \label{thm:glide}
Let $R\subseteq \mathbb{C}$ be a subset.
Let $\mathcal{C}=(c_{i,j})$ be a tame frieze pattern with coefficients over $R$ of height
$n$. Then for all entries of $\mathcal{C}$ we have
$c_{i,j} = c_{j,n+i+3}.
$
\end{prop}
This implies that
the triangular region shown
in Figure~\ref{fig:glide} yields
a fundamental domain for the action of the glide symmetry.
Note that the indices of the entries
are in bijection with the edges and diagonals of a regular $(n+3)$-gon (viewed as pairs of vertices). This means that we can view every tame
frieze pattern with coefficients of height $n$ over $R$ as a map on the edges and
diagonals of a regular $(n+3)$-gon with values in $R$.
In the case of Conway--Coxeter frieze patterns the diagonals
which are mapped to $1$ give a triangulation of the $(n+3)$-gon.
\begin{figure}[htb]\centering
$
\begin{array}{ccccccccc}
& ~~ & ~\ddots~ & ~ & ~~ & ~~ & ~ & \ddots~ & ~\\
& ~0~ & ~c_{1,2}~ & ~c_{1,3}~ & ~\ldots~ & ~\ldots~ & ~\ldots~ & ~c_{1,n+3}~ & ~0~ \\
& & ~0~ & ~c_{2,3}~ & ~c_{2,4}~ & ~\ldots~ & ~\ldots~ & ~c_{2,n+3}~ & ~\ddots~ \\
& & & ~\ddots~ & ~\ddots~ & ~\ddots~ & ~~ & ~\vdots~ & ~ \\
& & & ~~ & ~\ddots~ & ~\ddots~ & ~\ddots~ & ~\vdots~ & ~\\
& & & ~~ & ~~ & ~0~ & ~c_{n+1,n+2}~ & ~c_{n+1,n+3}~ & ~\\
& & & ~~ & ~~ & ~~ & ~0~ & ~c_{n+2,n+3}~ & ~ \ddots \\
& & & ~~ & ~~ & ~~ & ~~ & ~0~ & ~\ddots \\
& & & ~~ & ~~ & ~~ & ~~ & ~~ & ~0~ \\
\end{array}
$
\caption{Fundamental domain for the glide symmetry of a frieze pattern
with coefficients.\label{fig:glide}}
\end{figure}
%\noindent
\begin{enonce*}[remark]{Convention}
We use the notion (tame) {\em frieze pattern with coefficients} for an infinite array
as in Definition~\ref{def:frieze} and the notion (tame) {\em frieze with coefficients}
for a corresponding map from edges and diagonals of a regular polygon.
\end{enonce*}
%\bigskip
Secondly,
the entries in a frieze (pattern) with coefficients satisfy Ptolemy relations,
as visualized in Figure~\ref{fig:Ptolemy}.
\begin{defi} \label{def:ptolemy}
Let $\mathcal{C}=(c_{i,j})$ be a tame frieze with coefficients over $R\subseteq \mathbb{C}$
on a regular $m$-gon. We say that $\mathcal{C}$ satisfies the Ptolemy relation for
the indices $1\le i\le j\le k\le \ell\le m$ if the following equation holds:
\begin{equation*}\tag{$E_{i,j,k,\ell}$}\label{eq:ptolemy}
c_{i,k} c_{j,\ell} = c_{i,\ell} c_{j,k} + c_{i,j} c_{k,\ell}.
\end{equation*}
\end{defi}
\begin{figure}[htb]\centering
\begin{tikzpicture}[auto]
\node[name=s, draw, shape=regular polygon, regular polygon sides=500, minimum size=4cm] {};
\draw[thick] (s.corner 60) to (s.corner 180);
\draw[thick] (s.corner 180) to (s.corner 300);
\draw[thick] (s.corner 300) to (s.corner 400);
\draw[thick] (s.corner 400) to (s.corner 60);
\draw[thick] (s.corner 60) to (s.corner 300);
\draw[thick] (s.corner 180) to (s.corner 400);
\draw[shift=(s.corner 60)] node[above] {{\small $i$}};
\draw[shift=(s.corner 180)] node[left] {{\small $j$}};
\draw[shift=(s.corner 300)] node[below] {{\small $k$}};
\draw[shift=(s.corner 400)] node[right] {{\small $\ell$}};
\end{tikzpicture}
\caption{The Ptolemy relation~\eqref{eq:ptolemy}.
\label{fig:Ptolemy}}
\end{figure}
An old result by Coxeter (see~\cite[Equation~(5.7)]{Cox71})
states that classic friezes satisfy all Ptolemy relations and this can be extended
to friezes with coefficients.
\begin{prop}[{\cite[Theorem~2.6]{CHJ}}] \label{thm:ptolemy}
Every tame frieze with coefficients
over some subset $R\subseteq \mathbb{C}$
satisfies all Ptolemy relations.
\end{prop}
\section{\texorpdfstring{$n$}{n}-gons in Conway--Coxeter friezes}
\label{sec:ngons}
From now on we consider frieze patterns with coefficients over positive integers.
Let us take any classic Conway--Coxeter
frieze $\mathcal{C}$ on an $n$-gon, that is, a map
from edges and diagonals of a regular
polygon to the positive integers such that all edges of the $n$-gon are mapped to 1.
Restricting this map to any subpolygon of the
$n$-gon yields a frieze with coefficients. In fact,
the restricted
map still satisfies all Ptolemy relations of the subpolygon. See Figure~\ref{fig:cut}
for an example.
\begin{figure}[htb]\centering
\begin{tikzpicture}[auto]
\node[name=s, draw, shape=regular polygon, regular polygon sides=6, minimum size=3cm] {};
\draw[thick] (s.corner 2) to (s.corner 4);
\draw[thick] (s.corner 2) to (s.corner 5);
\draw[thick] (s.corner 2) to (s.corner 6);
\end{tikzpicture}
\mbox{\hskip2cm}
\begin{tikzpicture}[auto]
\node[name=s, draw, shape=regular polygon, regular polygon sides=6, minimum size=3cm] {};
\draw[ultra thick] (s.corner 1) to (s.corner 3);
\draw[ultra thick] (s.corner 3) to (s.corner 5);
\draw[ultra thick] (s.corner 2) to (s.corner 5);
\draw[ultra thick] (s.corner 1) to (s.corner 5);
\draw[ultra thick] (s.corner 1) to (s.corner 2);
\draw[ultra thick] (s.corner 2) to (s.corner 3);
\draw[shift=(s.side 1)] node[above] {{\small 1}};
\draw[shift=(s.corner 2)] node[below left=12pt] {{\small 1}};
\draw[shift=(s.corner 4)] node[above right=5pt] {{\small 2}};
\draw[shift=(s.corner 6)] node[left=10pt] {{\small 2}};
\draw[shift=(s.corner 6)] node[left=42pt] {{\small 1}};
\draw[shift=(s.corner 1)] node[below left=15pt] {{\small 4}};
\end{tikzpicture}
\caption{A frieze with coefficients cut out of a Conway--Coxeter frieze.
\label{fig:cut}}
\end{figure}
In~\cite{CHJ} we addressed the fundamental question which friezes with coefficients
actually appear as subpolygons of Conway--Coxeter friezes and obtained the
following complete answer for the special case of triangles.
\begin{theo}[{\cite[Theorem~5.12]{CHJ}}] \label{thm:triangle}
Let $a,b,c\in \mathbb{N}$. The triple $(a,b,c)$ appears as labels of a triangle
in some Conway--Coxeter frieze if and only if the following two conditions are
satisfied:
\begin{enumerate}
\item $\gcd(a,b)=\gcd(b,c)=\gcd(a,c)$.
\item $\nu_2(a)=\nu_2(b)=\nu_2(c)=0$ or $|\{\nu_2(a),\nu_2(b),\nu_2(c)\}|>1$ where
$\nu_2(\cdot )$ denotes the 2-valuation, that is, the numbers $a,b,c$ are either all odd or
do not all have the same 2-valuation.
\end{enumerate}
\end{theo}
The main aim of this paper is a generalization of the previous theorem
to arbitrary subpolygons in Conway--Coxeter friezes. That is, we give
arithmetic conditions on the entries of a frieze with coefficients
which characterize whether
or not the frieze with coefficients appears as a subpolygon in some
Conway--Coxeter frieze.
The following theorem is the main result of this paper.
\begin{theo} \label{thm:mgon}
Let $\mathcal{C}$ be a frieze with coefficients
on an $n$-gon over the positive integers. Then $\mathcal{C}$ appears as a
subpolygon
of some Conway--Coxeter frieze if and only if the following conditions are
satisfied:
\begin{enumerate}
\item \label{cond:gcd}
For any triangle $(a,b,c)$ in $\mathcal{C}$ we have
$\gcd(a,b)=\gcd(b,c)=\gcd(a,c)$.
\item \label{cond:p+1}
Let $p0$.
Assume first that every diagonal $(i,v)$ for $i=0,\ldots,p$ and $v$ not a vertex of $\mathcal{D}$ is divisible by $p$.
Then if $v,w$ are vertices of $\mathcal{C}$ not in $\mathcal{D}$, then the
label of the diagonal $(v,w)$ is divisible by $p$ as well by assumption~\eqref{cgcd} since $(c_{0,v},c_{v,w},c_{0,w})$ is a triangle.
Dividing the labels of all edges and diagonals of $\mathcal{C}$ by $p$ we obtain a frieze with coefficients $\mathcal{C'}$ satisfying the assumption of the proposition with $m-1$ instead of $m$, thus we are finished by induction.
We may thus now assume without loss of generality that there exists a vertex $v$ such that the label
of the diagonal $(v,p)$ is not divisible by $p$, see Figure~\ref{fig:p+1}.
For $j=0,1,\ldots,p$ we set $c_j:=c_{p,j}$ and $y_j:=c_{v,j}$ for abbreviation.
For $j=1,\ldots,p-1$
the Ptolemy relation for the crossing diagonals $(0,p)$ and $(v,j)$ of
$\mathcal{C}$ gives
\[
c_0y_j = y_0c_j + c_{0,j}y_p.
\]
Dividing this equation by $p^m$ leads to
\begin{equation} \label{eq1}
c'_0y_j = y_0c'_j + c'_{0,j}y_p
\end{equation}
where $c'_0=\frac{c_0}{p^m}$, $c'_j=\frac{c_j}{p^m}$ and
$c'_{0,j}=\frac{c_{0,j}}{p^m}$. By assumption on $\mathcal{D}$, none of
these three positive integers is divisible by $p$.
In addition, note that $y_j$ is not divisible by $p$ by assumption~\eqref{cgcd}, since
$(y_p,y_j,c_j)$ are the labels of a triangle in $\mathcal{C}$ and
$y_p=c_{v,p}$ is not divisible by $p$.
Then Equation~\eqref{eq1} implies
\begin{equation} \label{eq:residue}
y_0\not\equiv -(c'_j)^{-1} c'_{0,j} y_p\,\,(\md p)
\mbox{\hskip1cm
for all $j=1,\ldots,p-1$}.
\end{equation}
On the other hand, for any $1\le i< j\le p-1$, dividing the Ptolemy relation for the crossing diagonals
$(0,j)$ and $(p,i)$ by $p^{2m}$ yields
\[
c'_{0,j} c'_i - c'_{0,i}c'_j = c'_0c'_{i,j} \not\equiv 0
\,\,(\md p).
\]
That is, the residue classes modulo $p$
appearing on the right of~\eqref{eq:residue}
are pairwise different for $j=1,\ldots,p-1$. Hence the conditions in
\eqref{eq:residue} rule out all nonzero residue classes modulo $p$
for $y_0$, but
since $y_0$ is not divisible by $p$, this leaves no choice for $y_0$.
This is a contradiction and thus this case cannot occur.
\end{proof}
We now show that Conditions~\eqref{cond:gcd} and~\eqref{cond:p+1} are necessary for a frieze with
coefficients to appear as a subpolygon of a Conway--Coxeter frieze.
So assume that $\mathcal{C}$ is a frieze with coefficients that appears as a subpolygon of a Conway--Coxeter frieze $\mathcal{E}$.
By Lemma~\ref{lem:gcd}, Condition~\eqref{cond:gcd} is satisfied in $\mathcal{E}$, thus satisfied in $\mathcal{C}$ as well.
\looseness-1
Now assume that $\mathcal{C}$ contains a $(p+1)$-subpolygon $\mathcal{D}$ for a prime number $p$
such that the labels of all edges and diagonals of $\mathcal{D}$ have the same $p$-valuation $m$.
Proposition~\ref{prop:pm} tells us that then the labels of all edges and
diagonals of $\mathcal{E}$ are divisible by $p^m$. Since the edges of the
Conway--Coxeter frieze $\mathcal{E}$ are labelled by $1$, we obtain $m=0$,
that is, the labels of all edges and diagonals of $\mathcal{D}$ are
not divisible by $p$, and Condition~\eqref{cond:p+1} holds.
\subsection{Sufficiency}
It remains to prove the sufficiency statement of Theorem~\ref{thm:mgon}. Let~$\mathcal{C}$ be a frieze with coefficients over $\mathbb{Z}_{>0}$ on an
$n$-gon satisfying Conditions \eqref{cond:gcd} and~\eqref{cond:p+1}. We have to show
that $\mathcal{C}$ can be extended to a Conway--Coxeter frieze.
If all boundary edges have label 1 then $\mathcal{C}$ is itself a Conway--Coxeter
frieze and we are done. So assume that $\mathcal{C}$ has a boundary edge with
label $c_0>1$.
The idea of the proof is to proceed inductively. That is, we aim to construct
a frieze with coefficients $\widetilde{\mathcal{C}}$ over $\mathbb{Z}_{>0}$
on an $(n+1)$-gon with the following properties:
\begin{enumerate}[label=(\roman*)]
\item %[{(i)}]
$\widetilde{\mathcal{C}}$
contains $\mathcal{C}$ as a subpolygon.
\item %[{(ii)}]
The edges attached to the new vertex have labels $1$ and $y_0$ where
$0< y_0 < c_0$.
\item %[{(iii)}]
$\widetilde{\mathcal{C}}$ still satisfies Conditions~\eqref{cond:gcd} and~\eqref{cond:p+1}.
\end{enumerate}
Carrying out this procedure inductively for each boundary edge of $\mathcal{C}$
eventually produces
a frieze with coefficients with all boundary edges having label 1, that is, a
Conway--Coxeter frieze containing $\mathcal{C}$ as a subpolygon. We will give an
explicit algorithm to determine such a frieze with coefficients $\widetilde{\mathcal{C}}$,
that is, the proof of this direction is constructive.
%\smallskip
We label the vertices of the $n$-gon by $0,1,\ldots,n-1$ in counterclockwise order,
such that the edge with label $c_0$ has vertices $0$ and $n-1$, see Figure~\ref{fig:ext}.
\begin{figure}[htb]\centering
\begin{tikzpicture}[auto]
\node[name=s, draw, shape=regular polygon, regular polygon sides=11, minimum size=7cm] {};
\draw[dashed] (s.corner 1) to (s.corner 3);
\draw[dashed] (s.corner 1) to (s.corner 5);
\draw[dashed] (s.corner 1) to (s.corner 7);
\draw[ultra thick] (s.corner 2) to (s.corner 11);
\draw[ultra thick] (s.corner 3) to (s.corner 11);
\draw[ultra thick] (s.corner 5) to (s.corner 11);
\draw[ultra thick] (s.corner 7) to (s.corner 11);
\draw[shift=(s.side 3)] node[right=40pt] {{$y_j$}};
\draw[shift=(s.side 3)] node[right=70pt] {{$c_j$}};
\draw[shift=(s.side 9)] node[left=30pt] {{$c_{i_p}$}};
\draw[shift=(s.side 11)] node[above right] {{$1$}};
\draw[shift=(s.side 1)] node[above left] {{$y_0$}};
\draw[shift=(s.corner 9)] node[left=79pt] {{$y_{i_p}$}};
\draw[shift=(s.corner 2)] node[left] {{$0$}};
\draw[shift=(s.corner 3)] node[left] {{$1$}};
\draw[shift=(s.corner 11)] node[right] {{$n-1$}};
\draw[shift=(s.corner 1)] node[above] {{$n$}};
\draw[shift=(s.corner 4)] node[above right=20pt] {{$\ddots$}};
\draw[shift=(s.side 5)] node[above right=20pt] {{$\ddots$}};
\draw[shift=(s.corner 5)] node[left] {{$j$}};
\draw[shift=(s.corner 7)] node[below right] {{$i_p$}};
\end{tikzpicture}
\caption{Extending a frieze with coefficients.
\label{fig:ext}}
\end{figure}
We set $c_j:= c_{j,n-1}$ for $0\le j\le n-2$, see the ultra thick lines in
Figure~\ref{fig:ext}. We aim to find suitable labels $y_j:=c_{j,n}$ for the
new edges and diagonals in the larger frieze with coefficients $\widetilde{\mathcal{C}}$
(the dashed lines in Figure~\ref{fig:ext})
such that all Ptolemy relations in $\widetilde{\mathcal{C}}$ are satisfied.
For computing suitable positive integers $y_j$,
we consider each prime power divisor of $c_0$ separately and eventually use the
Chinese Remainder Theorem.
Let $p$ be a prime divisor of $c_0$ and $\ell:=\nu_p(c_0)$ be the $p$-valuation
(that is, $p^{\ell}$ divides $c_0$ but $p^{\ell+1}$ does not divide $c_0$).
We set
\[
m:= \min \{\nu_p(c_i)\mid 0\le i\le n-2\},
\]
and we choose a vertex $i_p$ with $\nu_p(c_{i_p})=m$. Note that for every vertex $j$
in $\mathcal{C}$ we have $p^m\mid c_j$ (by minimality of $m$) and
also $p^m\mid c_{i,j}$ for $i\ne j$ (by Condition~\eqref{cond:gcd} for $\mathcal{C}$).
For any positive integer $u$ we define $u'$ by $u=p^{\nu_p(u)} u'$.
%\medskip
We first want to determine a suitable label $y_{i_p}\Mk$.
\begin{lemm} \label{lem:yip}
With the above notation there are positive integers $y_{i_p}$ such that the following
conditions are satisfied.
\begin{enumerate}[label=(\roman*)]
\item\label{lemma4.3_i} %[{(i)}]
$y_{i_p} \not \equiv 0\,\,(\md p)$.
\item\label{lemma4.3_ii} %[{(ii)}]
If $m>0$, then for every vertex $j$ such that $p\nmid \frac{c_{i_p,j}}{p^m}$ and $p\nmid \frac{c_{j}}{p^m}$ we have
\begin{equation} \label{eq:ruleout}
\begin{cases}
c'_j y_{i_p} - c'_{i_p,j}\not \equiv 0\,\,(\md p) & \mbox{if $j0$.
We consider the nonzero residue classes modulo $p$ and show that for the elements in at least one
residue class the conditions of the lemma hold. Let $j$ be a vertex such that
$p\nmid \frac{c_{i_p,j}}{p^m}$ and $p\nmid \frac{c_{j}}{p^m}$. Then the second condition
in the lemma rules out the residue class
$\pm (c'_j)^{-1} c'_{i_p,j}\,\,(\md p)$ to be chosen for $y_{i_p}$.
%\smallskip
\begin{enonce*}{Claim} Let vertices $i$ and $j$ both satisfy the assumptions in the second
condition of the lemma. Then
\eqref{eq:ruleout} rules out the same residue class modulo $p$
if
$p\mid \frac{c_{i,j}}{p^m}$ and different residue classes modulo $p$ otherwise.
%\smallskip
\end{enonce*}
\begin{proof}[Proof of the claim] We can assume $i0$, contradicting Condition~\eqref{cond:p+1}).
Using the above claim this implies that not all residue
classes modulo $p$ are ruled out by Condition~\eqref{eq:ruleout}
and hence we can choose positive integers $y_{i_p}$
as claimed.
\end{proof}
Using a suitable value for $y_{i_p}$ as in Lemma~\ref{lem:yip} we now want to
look for suitable values for the other new diagonals $y_j$, such that
the Ptolemy relations in the larger polygon $\widetilde{\mathcal{C}}$ can
be satisfied. Recall that above we have defined
$\ell=\nu_p(c_0)$.
\begin{lemm} \label{lem:yj}
We keep the above notation and fix a positive integer $y_{i_p}$ satisfying the conditions
in Lemma~\ref{lem:yip}.
Then for every integer $y_j$ in the residue class
\[
\begin{cases}
(c'_{i_p})^{-1} \left( \frac{c_j}{p^m} y_{i_p} - \frac{c_{i_p,j}}{p^m}\right)\quad
(\md p^{\ell}) & \text{ if } j0$ then
according to the choice of $y_{i_p}$ in
Lemma~\ref{lem:yip}, the right hand side of~\eqref{eq:modpl} is
invertible modulo $p^{\ell}$. Hence the left hand side is invertible as well.
Thus, $p\nmid y_j$ and in particular $p\nmid \gcd(y_j,c_j)$.
\end{enonce*}
\ref{lemma4.4_b}~Due to the signs in the definition of $y_j$,
there are separate cases. We present the argument for the case $i0}$.
\item\label{prop4.5_b} %[{(b)}]
$\widetilde{\mathcal{C}}$ satisfies Conditions~\eqref{cond:gcd} and~\eqref{cond:p+1} of Theorem~\ref{thm:mgon}.
\end{enumerate}
\end{prop}
\begin{proof}
\ref{prop4.5_a} The Ptolemy relations not involving any of the new diagonals with
label $y_j$ are Ptolemy relations of $\mathcal{C}$ and hold by assumption
since $\mathcal{C}$ is a frieze with coefficients.
For crossings of diagonals labelled $y_j$ with the diagonal with label $c_0$
the Ptolemy relation holds by definition of $y_j$ in~\eqref{eq:yj}.
Let $(i,k)$ be a diagonal in $\mathcal{C}$ crossing the new diagonal with label
$y_j$. Using the formula in~\eqref{eq:yj} and Ptolemy relations in $\mathcal{C}$
we get
\begin{align*}
y_kc_{i,j} + y_i c_{j,k} & = \frac{c_ky_0+c_{0,k}}{c_0} c_{i,j}
+ \frac{c_iy_0+c_{0,i}}{c_0} c_{j,k} \\
& = \frac{1}{c_0} ( y_0 (c_kc_{i,j} + c_ic_{j,k}) +
c_{0,k} c_{i,j} + c_{0,i} c_{j,k}) \\
& = \frac{1}{c_0} ( y_0 c_jc_{i,k} + c_{0,j}c_{i,k})
= \frac{c_j y_0+c_{0,j}}{c_0} c_{i,k} = y_j c_{i,k}.
\end{align*}
Note that in particular we also obtain $c_i y_j = c_j y_i + c_{i,j}$ for all $i,j$.
\ref{prop4.5_b}~For Condition~\eqref{cond:gcd} we have to consider the triangles in
$\widetilde{\mathcal{C}}$ which are not already in $\mathcal{C}$.
There are different types of triangles to consider.
The triangle $(1,y_0,c_0)$ satisfies Condition~\eqref{cond:gcd} by Lemma
\ref{lem:yj}\,\ref{lemma4.4_a}. For a triangle $(1,y_j,c_j)$ with $j\neq 0$ we know again
by Lemma~\ref{lem:yj}\,\ref{lemma4.4_a} that $p\nmid \gcd(y_j,c_j)$ for all prime divisors
$p$ of $c_0$. Suppose $q$ is a prime number dividing $y_j$ and $c_j$ but
$q\nmid c_0$. Then $q\mid c_{0,j}$ by~\eqref{eq:yj}. Thus $q$ is a common divisor
of $c_{0,j}$ and $c_j$. But the triangle $(c_0,c_{0,j},c_j)$ in $\mathcal{C}$
satisfies Condition~\eqref{cond:gcd}, so $q\mid c_0$, a contradiction. Thus
we have shown that $\gcd(y_j,c_j)=1$ and the triangle $(1,y_j,c_j)$ satisfies
Condition~\eqref{cond:gcd}.
The other new triangles in $\widetilde{\mathcal{C}}$ are of the form
$(y_i,c_{i,j},y_j)$. We use the Ptolemy relation $c_i y_j = c_j y_i + c_{i,j}$.
Let $d$ be a common divisor of $y_i$ and $c_{i,j}$. Then $d$ divides $c_iy_j$.
But $y_i$ and $c_i$ are coprime as shown in the previous paragraph, so $d$ divides $y_j$, as desired. Similarly, if $d$ is a common divisor of $c_{i,j}$ and $y_j$, then $d$ divides $y_i$. Finally, if $d$ is a common divisor
of $y_i$ and $y_j$ then $d$ divides $c_{i,j}$.
So Condition~\eqref{cond:gcd} holds for all triangles in
$\widetilde{\mathcal{C}}$.
%\smallskip
\looseness-1
For Condition~\eqref{cond:p+1} we have to consider all possible $(q+1)$-gons
in $\widetilde{\mathcal{C}}$ for all prime numbers $q