Research Contribution DOI:10.56994/ARMJ.012.00?.00?
Received: 2025; Accepted: 2025


Arithmetic and Geometry of Markov polynomials

S.J. Evans Department of Mathematical Sciences, Loughborough University, Loughborough LE11 3TU, UK S.J.Evans@lboro.ac.uk ,  A.P. Veselov Department of Mathematical Sciences, Loughborough University, Loughborough LE11 3TU, UK A.P.Veselov@lboro.ac.uk  and  B. Winn Department of Mathematical Sciences, Loughborough University, Loughborough LE11 3TU, UK B.Winn@lboro.ac.uk
Abstact.
Markov polynomials are the Laurent-polynomial solutions of the generalised Markov equation

X2+Y2+Z2=k⁢X⁢Y⁢Z,k=x2+y2+z2x⁢y⁢z

which are the results of cluster mutations applied to the initial triple (x,y,z). They were first introduced and studied by Itsara, Musiker, Propp and Viana, who proved, in particular, that their coefficients are non-negative integers. We study the coefficients of Markov polynomials as functions on the corresponding Newton polygons, proposing several new conjectures. Some of these conjectures are proved for the special cases of Markov polynomials corresponding to Fibonacci and Pell numbers.

1 Introduction

One of the most remarkable Diophantine equations is the celebrated Markov equation

X2+Y2+Z2=3⁢X⁢Y⁢Z.

Markov showed [23] that all its solutions in positive integers can be found recursively from (1,1,1) using the Vieta involution

(1) (X,Y,Z)↦(X,Y,Z′),Z′=X2+Y2Z,

and permutation of variables.

Following Itsara, Musiker, Propp and Viana [17, 28], who were inspired by the earlier work of Fomin and Zelevinsky [15], we consider the following generalisation of the Markov equation

(2) X2+Y2+Z2=k⁢(x,y,z)⁢X⁢Y⁢Z,k⁢(x,y,z)=x2+y2+z2x⁢y⁢z.

with the solutions being rational functions of the parameters x,y,z. Starting with the initial solution (X,Y,Z)=(x,y,z) we can apply the Vieta involutions (1) and permutations to arrive at solutions

X=X⁢(x,y,z),Y=Y⁢(x,y,z),Z=Z⁢(x,y,z)

of the equation (2), certain Laurent polynomials of x,y,z, which we call Markov polynomials. They correspond to the cluster algebra related to the Markov quiver (see below).

The Laurent property follows from general cluster algebra framework of Fomin and Zelevinsky [15], but in this case also from the alternative form of the Vieta involution

(3) Z′=k⁢(x,y,z)⁢X⁢Y−Z.

In [28] it was shown that the coefficients of Markov polynomials are non-negative. When we specialise all the parameters x,y,z to 1, we get the celebrated Markov numbers, playing seminal role in many areas of mathematics [1]. In this sense Markov polynomials can be viewed as a 3-parameter quantisation of Markov numbers.

The aim of this paper is to study these polynomials in more detail. We will view their coefficients as the functions on the corresponding Newton polygons, which we will describe explicitly. We prove some new results and state several conjectures about the coefficients of Markov polynomials, some of which are proved for the Markov polynomials corresponding to Fibonacci and Pell numbers. We discuss the continuum limit, introducing the corresponding entropy function, which is conjectured to be concave. We also provide a description of the Markov polynomials via a suitable generalisation of Cohn matrices.

2 Markov polynomials on the Conway Topograph

To represent Markov numbers it is now customary (see e.g. [30]) to use the Conway topograph introduced by J.H. Conway [7] to vizualise the values of quadratic forms.

The Conway topograph consists of the planar domains which are connected components of the complement to the trivalent tree imbedded in the plane. These domains were originally labelled by superbases in the integer lattice ℤ2, but can be also labelled by the rational numbers using the Farey mediant p1q1⊕p2q2=p1+p2q1+q2. We will only be interested in the rationals in [0,1], leading to the rational Conway topograph given in Figure 1. Neighbouring regions are occupied by Farey neighbours, i.e. ab,cd where \abs⁢a⁢d−b⁢c=1.

p1q1p2q2p1+p2q1+q2 1101122335344758574513251437382715
Figure 1. Rationals in [0,1] represented on the Conway topograph.

To represent Markov numbers on the Conway topograph we iterate via the Vieta formula from the Markov equation, as shown on the left of Figure 2, starting with the initial state X=Y=Z=1. Markov triples can then be seen by looking at the three domains adjacent to a vertex. The first few iterations of this process can also be seen in Figure 2.

Juxtaposition with the rational Conway topograph establishes the parametrization of the Markov numbers by rational numbers ρ∈[0,1], a way of parametrizing Markov numbers which goes back to Frobenius [16].

ZXYZ′=X2+Y2Z 2152943316964663766614701985131943428977561132589
Figure 2. Markov numbers represented on the Conway topograph.

If instead of (1,1,1) on the Conway topograph we start with the triple (x,y,z) and apply the same Vieta formula we get Laurent polynomial solutions of the equation (2).

M1/1=x2+y2zM0/1=xM1/2=x4+2⁢x2⁢y2+y4+x2⁢z2y⁢z2M2/3M3/5M3/4M4/7M5/8M5/7M4/5M1/3M2/5M1/4M3/7M3/8M2/7M1/5
Figure 3. Markov polynomials on the Conway topograph.

We will use the notation Mρ=Mρ⁢(x,y,z) to represent the Markov polynomial occupying the same region as the rational ρ on their respective Conway topographs. Formally, this Frobenius parametrization is a mapping

(4) F:ρ∈[0,1]∩ℚ↦Mρ⁢(x,y,z).

Setting x=y=z=1 in Markov polynomials gives the corresponding Markov number: Mρ⁢(1,1,1)=mρ.

We have the correspondence between Markov triples of numbers and the triples of Markov polynomials Mρ with ρ∈[0,1]∩ℚ. In particular, the first Markov triples (1,1,1),(1,1,2),(1,2,5) correspond to the triples

(x,y,z),(x,y,x2+y2z),(x,x2+y2z,x4+2⁢x2⁢y2+y4+x2⁢z2y⁢z2)

respectively. Thus we have the first few Markov polynomials

(5) M0/1=x,M1/1=x2+y2z,M1/2=(x2+y2)2+x2⁢z2y⁢z2,…

Many of our proofs will proceed by induction on the Conway topograph, and the solutions (5) will provide the base cases for the induction.

To extend the Frobenius correspondence (4) to all rationals we can use the action of the symmetric group S3≅SL2⁢(ℤ2):

(6) Mρ⁢(x,y,z)=M1ρ⁢(y,x,z),Mρ⁢(x,y,z)=M−11+ρ⁢(z,x,y).

We believe that in this way we get all such solutions. More precisely, we have the following

Conjecture 2.1.

All the solutions X,Y,Z∈ℤ⁢[x±1,y±1,z±1] of equation (2) in integer Laurent polynomials, up to a change of sign of any two of them, are given by triples of Markov polynomials.

From now on we will focus only on the Markov polynomials corresponding to rationals in [0,1] as all others can be obtained by the above symmetries.

From the point of view of the theory of cluster algebras Markov polynomials correspond to the special quiver (called the Markov quiver) shown in Figure 4.

x1x2x3
Figure 4. Markov quiver

By the general procedure of Fomin and Zelevinsky [14] the mutation of a quiver Q with vertices labelled by 1,2,…,N at a vertex k consists of three steps:-

  1. (1)

    For each instance of a path j→k→l introduce a new edge j→l;

  2. (2)

    Reverse the direction of all of the edges incident to k;

  3. (3)

    Remove oriented 2-cycles.

The Markov quiver is special since it remains invariant (up to orientation) under all possible mutations.

Let x1,…,xN be the initial (seed) variables assigned to the corresponding vertices. The seed mutation at a vertex k changes the cluster (x1,…,xN) to (x1′,…,xN′) with xj′=xj for all j≠k and xk, xk′ related by the exchange relation

xk⁢xk′=∏j→kxj+∏k→lxl.

In the case of the Markov quiver the mutation at vertex 3 leads to the exchange relation

x3⁢x3′=x12+x22,

corresponding to the Vieta involution (1). Starting with the seeds x1=x,x2=y,x3=z and performing mutations we come to the Markov polynomials.

3 Structure of Markov Polynomials

The general structure of the Markov polynomial Ma/b⁢(x,y,z) can be described as follows.

Theorem 3.1.

Markov polynomials Ma/b⁢(x,y,z) with coprime a,b>0 have the following general form

(7) Ma/b⁢(x,y,z)=Pa/b⁢(x2,y2,z2)xa−1⁢yb−1⁢za+b−1,

where Pa/b⁢(u,v,w) is a homogeneous polynomial of degree a+b−1 with non-negative integer coefficients, indivisible by x, y or z.

We set here P0/1≡1 to have the correct formula for M0/1⁢(x,y,z)=x.

Proof.

The proof is by induction using the Vieta formula in the form (3).

MρZ,ρZ=abMρX,ρX=cdMρY,ρY=a+cb+dMρZ′,ρZ′=a+2⁢cb+2⁢d
Figure 5. Section of the Conway topograph showing correspondence.

Consider the part of the Conway topograph shown in Figure 5. We assume that the statement holds for MρX, MρY and MρZ. Then, according to (3),

MρZ′ =k⁢(x,y,z)⁢MρX⁢MρY−MρZ
=(x2+y2+z2)⁢Pc/d⁢(x2,y2,z2)⁢P(a+c)/(b+d)⁢(x2,y2,z2)−x2⁢c⁢y2⁢d⁢z2⁢c+2⁢d⁢Pa/b⁢(x2,y2,z2)xa+2⁢c−1⁢yb+2⁢d−1⁢za+b+2⁢c+2⁢d−1,

where the denominator is of the required form. We need only to be sure that there is no cancellation of factors from the denominator, but for that to happen, one of Pc/d or P(a+b)/(c+d) would have to be divisible by x, y or z, which cannot happen. We further see that the numerator satisfies the required homogeneity property. The base cases (5) satisfy (7) so the proof is complete.

The non-negativity of the coefficients of Markov polynomials was known before [28], but we will provide an independent proof based on quantised Cohn matrices (see Corollary 10.2 below). ∎

As a consequence of the proof, we obtain a formula for the evolution of the numerators along the Conway topograph:

(8) Pa+2⁢cb+2⁢d=(u+v+w)⁢Pcd⁢(u,v,w)⁢Pa+cb+d⁢(u,v,w)−uc⁢vd⁢wc+d⁢Pab⁢(u,v,w).

3.1 Newton polygon of the numerator

To study the numerator Pρ⁢(u,v,w) of the Markov polynomial Mρ⁢(x,y,z), ρ=a/b, it is natural to look first at the corresponding Newton polygon Δρ, which can be considered as tropicalization of Pρ⁢(u,v,w).

Whilst our polynomials consist of three variables u,v,w, by noting homogeneity of terms—each term has total order in the numerator of a+b−1—we can simplify the problem (see Theorem 3.1). Indeed we can write Pρ as the following sum

(9) Pρ⁢(u,v,w)=∑Ai⁢j⁢ui⁢vj⁢wa+b−1−i−j.

As a result of this homogeneity we can consider the plane projections w=1, looking at the Newton polygon in the two variables u,v, and losing no additional information in the process. Note that this is now precisely the affine version (w=1) of the Newton polygon for the polynomial Pρ⁢(u,v,w).

For example, when ρ=23,mρ=29 we have

Pρ⁢(u,v,w)=u4+4⁢u3⁢v+6⁢u2⁢v2+4⁢u⁢v3+v4+2⁢u3⁢w+5⁢u2⁢v⁢w+4⁢u⁢v2⁢w+v3⁢w+u2⁢w2,

and setting w=1 we obtain

Pρ⁢(u,v,w)=u4+4⁢u3⁢v+6⁢u2⁢v2+4⁢u⁢v3+v4+2⁢u3+5⁢u2⁢v+4⁢u⁢v2+v3+u2.

We define the Newton polygon of Mρ⁢(x,y,z) as the convex hull

(10) Δρ=Δ⁢(Pρ):=Conv⁡{(i,j):Ai⁢j≠0}⊂ℤ2.
4321043210ji
Figure 6. Newton polygon Δρ, of the Markov polynomial Mρ,ρ=23.

We have the following explicit description111We are very grateful to Alexey Ustinov for the stimulating discussions of the Newton polygons for Markov polynomials, which led to formula (11). of the Newton polygons of the numerators of Markov polynomials in general case.222As we were informed by Ralf Schiffler, this result can be derived from the general description of Newton polygons for rank 3 cluster algebras [22].

Theorem 3.2.

Given a rational ρ=ab, the Newton polygon Δa/b of the numerator of Markov polynomial Mρ⁢(x,y,z) is the area on the i⁢j-plane with i,j≥0 satisfying the conditions

(11) {ia+jb≥1i+j≤a+b−1.

The proof is by induction. The first few cases are easily verifiable by direct computations. For the inductive step, we use the Vieta formula Z⁢Z′=X2+Y2 and verify that the Minkowski sum of the Newton polygons on the LHS coincides with the convex hull of the union of the scaled (due to squared terms) polygons on the RHS, taking care with the effect of the denominators on the subsequent numerator during the addition on the RHS. This is straightforward but a bit technical, so we omit the details.

We know due to [28] that Markov polynomials have non-negative coefficients, but some of the terms corresponding to the lattice points in the Newton polygon Δρ, in principle, could be zero. We conjecture that this is not the case and all the corresponding coefficients are positive.

Conjecture 3.3.

(Saturation conjecture) The terms that appear in the numerator of a Markov polynomial Mρ are precisely those corresponding to the integer lattice points in the Newton polygon Δρ.

Note that in the original (x,y,z) variables the Newton polygon is twice larger and saturation does not hold.

We will prove Conjecture 3.3 in certain special cases of Markov polynomials (see Section 5).

We should also mention in this relation an important result by Fei [11], who proved saturation for the F-polynomials of a rigid representation of any finite-dimensional basic algebra.

4 Coefficients of Markov polynomials

We can view the coefficients Ai⁢j of Markov polynomial

Ma/b⁢(x,y,z)=1xa−1⁢yb−1⁢za+b−1⁢∑i+j≤a+b−1,ia+jb≥1Ai⁢j⁢x2⁢i⁢y2⁢j⁢z2⁢(a+b−1−i−j)

as the weights on the lattice points of Newton polygon.

For example, for ρ=23 the ‘weighted’ polygon, Δρ is given in Figure 7.

14641254114321043210ji
Figure 7. ‘Weighted’ Newton polygon of the Markov polynomial M2/3.

Looking at the coefficients that appear on the lines i=0,j=0 and i+j=a+b−1=4, we notice that they are binomial coefficients. This is no coincidence as we prove below.

Expanding the Markov polynomials as Laurent series in z,y,x leads respectively to

Ma/b⁢(x,y,z)=1xa−1⁢yb−1⁢[T0⁢(x2,y2)za+b−1+T1⁢(x2,y2)za+b−3+⋯+Tk⁢(x2,y2)za+b−1−2⁢k+⋯]
=1xa−1⁢za+b−1⁢[R0⁢(x2,z2)yb−1+R1⁢(x2,z2)zb−3+⋯+Rk⁢(x2,z2)yb−1−2⁢k+⋯]
=1yb−1⁢za+b−1⁢[S0⁢(y2,z2)xa−1+S1⁢(y2,z2)xa−3+⋯+Sk⁢(y2,z2)xa−1−2⁢k+⋯]

for certain polynomials Ti,Ri,Si. These polynomials with i=0 contain information about the coefficients on the boundary of the Newton polygon (S0 on the vertical, R0 on the horizontal and T0 on the upper diagonal line), while i=1,2,… correspond to the neighbouring parallel lines.

Theorem 4.1.

In the following cases the polynomials Si,Ri,Ti can be written explicitly as:

  • •

    S0⁢(v,w)=vb⁢(v+w)a−1

  • •

    R0⁢(u,w)=ua⁢(u+w)b−1

  • •

    R1⁢(u,w)=ua⁢(3⁢a−1)⁢(u+w)b−2+ua+1⁢(b−2⁢a)⁢(u+w)b−3

  • •

    T0⁢(u,v)=(u+v)a+b−1

  • •

    T1⁢(u,v)=(a−1)⁢(u+v)a+b−2+u⁢(b−a)⁢(u+v)a+b−3

  • •

    T2⁢(u,v)=(a−1)⁢(a−2)2⁢(u+v)a+b−3+u⁢[a⁢(b−a)−a]⁢(u+v)a+b−4+12⁢u2⁢[(b−a)2+5⁢a−3⁢b]⁢(u+v)a+b−5.

Proof.

We will prove only the formula for T0; all other cases are similar.

It is clear from (5) that P0/1,P1/1,P1/2 all have the required form, so let us consider again the section of the Conway topograph in Figure 5, and suppose that

PρX⁢(u,v,w)=T0,X⁢(u,v)+O⁢(w) =(u+v)c+d−1+O⁢(w)
PρY⁢(u,v,w)=T0,Y⁢(u,v)+O⁢(w) =(u+v)a+b+c+d−1+O⁢(w)
PρZ⁢(u,v,w)=T0,Z⁢(u,v)+O⁢(w) =(u+v)a+b−1+O⁢(w),

where O⁢(w) denotes a polynomial function of u,v,w with w as a factor.

From (8) we have

PρZ′⁢(u,v,w) =(u+v+w)⁢PρX⁢(u,v,w)⁢PρY⁢(u,v,w)−uc⁢vd⁢wc+d⁢PρZ⁢(u,v,w)
=(u+v)⁢(u+v)c+d−1⁢(u+v)a+b+c+d−1+O⁢(w)
=(u+v)a+b+2⁢c+2⁢d−1+O⁢(w),

giving us the expected form for PρZ′⁢(u,v,w) with ρZ′=(a+2⁢c)/(b+2⁢d). ∎

As a corollary we have an explicit form of the following coefficients (see Figure 8).

Theorem 4.2.

For the Markov polynomial Ma/b⁢(x,y,z) we know the coefficients Ai⁢j in the following cases:

  • •

    A0,j=(a−1j−b)

  • •

    Ai,0=(b−1i−a)

  • •

    Ai,1=(3⁢a−1)⁢(b−2i−a)+(b−2)⁢(b−3i−a−1)

  • •

    If i+j=a+b−1 then Ai,j=(a+b−1i),

  • •

    If i+j=a+b−2 then

    Ai,j=(a−1)⁢(a+b−2i)+(b−a)⁢(a+b−3i−1)
  • •

    If i+j=a+b−3 then

    Ai,j =(a−1)⁢(a−2)2⁢(a+b−3i)+[a⁢(b−a)−a]⁢(a+b−4i−1)
    +12⁢[(b−a)2+5⁢a−3⁢b]⁢(a+b−5i−2)

In particular, the boundary coefficients are binomials and we have an explicit expression for some of the interior coefficients as sums of binomial coefficients.

Figure 8. Lines on the Newton polygon where the coefficients are explicitly known.

For the rationals of the form ρ=1n and ρ=22⁢n−1 we can add also the coefficients on one more vertical line with i=1.

Theorem 4.3.

For the Markov polynomials M1/n and M2/(2⁢n−1) we have respectively

S1⁢(y2,z2)=∑k=1nk⁢y2⁢(k−1)⁢z2⁢(n−k)

and

S1⁢(y2,z2)=2⁢n⁢y4⁢n−2+∑k=1n−14⁢k⁢y2⁢(n+k−1)⁢z2⁢(n−k).

The proof of these results is similar to that of Theorems 3.1 and 4.1 and is based on relation (8).

In particular, on the line i=1 the Markov polynomial M1/n⁢(x,y,z) has the coefficients 1,2,…,n (see Figure 9 for the example with n=5, corresponding to the Markov number 89).

15101051412124693421543210543210ji
Figure 9. Weighted Newton polygon of M1/5 with the highlighted coefficients on the line i=1.

In the next two sections we consider in more detail two special series of Markov polynomials Mρ with ρ=1/n and ρ=n/(n+1).

5 Markov polynomials corresponding to Fibonacci and Pell numbers

5.1 Markov-Fibonacci polynomials

Fibonacci numbers satisfy the following recurrence

(12) Fn+1=Fn+Fn−1,

subject to the intial conditions F0=0,F1=1 (sequence A000045 of [26]). The first few terms are:

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,….

It is known that the odd-indexed Fibonacci numbers F2⁢k+1 are also Markov numbers [1]. Indeed, the odd-indexed Fibonacci numbers satisfy

F2⁢k+1=3⁢F2⁢k−1−F2⁢k−3,

which means that Yk=F2⁢k−1 satisfy the Vieta recursion Yk+1=3⁢Yk−Yk−1 for the Markov triples (1,Yk−1,Yk).

We will call the Markov polynomials M1/n⁢(x,y,z) corresponding to the Fibonacci numbers F2⁢n−1 the Markov-Fibonacci polynomials. They can be viewed as 3-parameter quantisations of the odd-indexed Fibonacci numbers.

We should note that a closely related notion was introduced by Caldero and Zelevinsky [4] as cluster variables of the A1(1) cluster algebra via the recurrence relation

(13) fm+1=fm2+1fm−1.

The Caldero-Zelevinsky Fibonacci polynomial fm is defined as the corresponding fm⁢(x1,x2) considered as the function of the two initial cluster variables f1=x1,f2=x2.

Theorem 5.1 ([4], [33]).

For every n≥0 there are the explicit formulæ

f2⁢n =1x1n⁢x2n⁢∑q+r≤n(n−rq)⁢(n−qr)⁢x12⁢q⁢x22⁢r,
f2⁢n+1 =1x1n+1⁢x2n⁢(x22⁢(n+1)+∑q+r≤n(n−rq)⁢(n+1−qr)⁢x12⁢q⁢x22⁢r).

In particular fm are Laurent polynomials in x1,x2 with positive coefficients.

Comparing Eqs. (13) with the Vieta recurrence for Markov polynomials

(14) M1/(k+1)=M1/k+x2M1/(k−1)

we see that M1/k’s are a homogeneous version of the cluster variables fm:

(15) fm⁢(x1,x2)=M1/m⁢(1,x2,x1).

Using Theorem 5.1, we have

Theorem 5.2.

The Markov-Fibonacci polynomials M1/(n+1)⁢(x,y,z) have coefficients

(16) Ai⁢j=(n−jn+1−i−j)⁢(i+jj),

where Ai⁢j is the coefficient of the numerator monomial x2⁢i⁢y2⁢j⁢z2⁢(n+1−i−j).

Corollary 5.3.

Markov-Fibonacci polynomials satisfy the Saturation Conjecture 3.3.

Another simple consequence of this result is the first part of Theorem 4.3 since setting i=1 leads to

A1⁢j=(n−jn−j)⁢(1+jj)=j+1.

It is interesting to note333This was observed by Sam Evans after discussions with Valentin Ovsienko. that our Markov-Fibonacci polynomials M1/n⁢(u,v,w) are related to Fibonacci polynomials ℱn⁢(q) from the theory of q-rational numbers developed by Morier-Genoud and Ovsienko [24].

The Fibonacci polynomials ℱn⁢(q) are the denominators of the q-deformed rationals [Fn+1Fn]q, where Fn are the Fibonacci numbers [21]. They can be determined by the recurrence relation

(17) ℱn+2⁢(q)=[3]q⁢ℱn⁢(q)−q2⁢ℱn−2⁢(q),

where [3]q=1+q+q2, and the initial conditions

ℱ0⁢(q)=1,ℱ2⁢(q)=1+qandℱ1⁢(q)=1,ℱ3⁢(q)=1+q+q2.
Proposition 5.4.

The Fibonacci polynomials ℱn⁢(q) are the following specialisations

(18) ℱ2⁢n⁢(q)=P1/n⁢(q,1,q2)

of the numerators P1/n⁢(u,v,w) of the Markov polynomials M1/n⁢(u,v,w).

Proof.

This follows from the comparison of the recurrence relations (8) and (17), and P1/0⁢(u,v,w)=1, P1/1⁢(u,v,w)=u+v. ∎

5.2 Markov-Pell Polynomials

We now turn to the Markov polynomials corresponding to Pell numbers, satisfying the recurrence

(19) Pn+1=2⁢Pn+Pn−1,

subject to the intial conditions P0=0,P1=1 (sequence A000129 of [26]). The first few Pell numbers are 0,1,2,5,12,29,70,169,….

It is known [1] that the odd-indexed Pell numbers P2⁢k+1 are also Markov numbers, since they satisfy the recurrence

P2⁢k+1=6⁢P2⁢k−1−P2⁢k−3,

equivalent to Vieta recursion for Markov triples (2,Yk−1,Yk),Yk=P2⁢k−1.

The Markov polynomials Mk/(k+1) can be viewed as a quantization of the Pell numbers P2⁢k+1.

We introduce now the Markov-Pell polynomials via the following recurrences, (which are quantized versions of (19))

(20) R2⁢k+1 =(x2+y2)⁢R2⁢k+x2⁢z2⁢R2⁢k−1,
R2⁢k =(x2+y2)⁢R2⁢k−1+y2⁢z2⁢R2⁢k−2,

with R0=0,R1=1,R2=x2+y2,R3=x4+2⁢x2⁢y2+y4+x2⁢z2.

The odd-indexed Markov-Pell polynomials satisfy the recurrence

(21) R2⁢k+1=(x2+y2)⁢(x2+y2+z2)⁢R2⁢k−1−x2⁢y2⁢z4⁢R2⁢k−3,

which is precisely the recurrence for the numerators of the Markov polynomials Mk/(k+1) (and because of the special initial data they coincide with these numerators).

From the equations (20) we can deduce

Corollary 5.5.

Markov-Pell polynomials satisfy the Saturation Conjecture 3.3.

The equations  (21) imply the recurrence for the corresponding coefficient Ai,j(2⁢k+1) at the monomial x2⁢i⁢y2⁢j⁢z2⁢(k−i−j) in R2⁢k+1:

(22) Ai,j(2⁢k+1)=Ai−2,j(2⁢k−1)+2⁢Ai−1,j−1(2⁢k−1)+Ai,j−2(2⁢k−1)+Ai−1,j(2⁢k−1)+Ai,j−1(2⁢k−1)−Ai−1,j−1(2⁢k−3).

We can also produce the Binet-type formula for the corresponding Markov-Pell polynomials, similar to the classical Binet formula for the Fibonacci numbers

Fn=15⁢((1+52)n−(1−52)n).

Indeed, we can rewrite Eqs. (20) in matrix form as

(R2⁢k+1R2⁢k)=((x2+y2)2+x2⁢z2(x2+y2)⁢x2⁢z2(x2+y2)y2⁢z2)⁢(R2⁢k−1R2⁢k−2)

The characteristic equation of the corresponding matrix is

(23) λ2−(x2+y2)⁢(x2+y2+z2)⁢λ+x2⁢y2⁢z4=0

giving the eigenvalues

λ±⁢(x,y,z)=12⁢[(x2+y2)⁢(x2+y2+z2)±𝒟]

where

𝒟=(x2+y2)4+2⁢z2⁢(x2+y2)3+z4⁢(x2−y2)2

is the discriminant of (23).

The standard procedure leads now to the following Binet-type formula for the Markov-Pell polynomials:

(24) R2⁢k+1=1𝒟⁢((λ+−y2⁢z2)⁢λ+k−(λ−−y2⁢z2)⁢λ−k).

6 Log-Concavity

A large number of naturally-occurring combinatorial sequences exhibit the logarithmically concave (log-concave) property [31]. Further to saturation, experimental data that we have looked-at so far has shown that coefficients of the Markov polynomials are log-concave in all directions.

Definition 6.1.

A sequence x=(x0,x1,…,xn) is said to be log-concave if it satisfies the property

(25) xk2≥xk−1⁢xk+1,

for k∈{1,2,…,n−1}.

A well-known example is the binomial sequence xk=(nk),k=0,…,n:

xk2xk−1⁢xk+1=(nk)2/(nk−1)⁢(nk+1)=k+1k⁢n−k+1n−k>1.
Definition 6.2.

We say that the weights on the Newton polygon satisfy the weak log-concavity property if their sequences in all principal directions (horizontal, vertical and diagonal with i+j=constant) are log-concave.

Conjecture 6.3.

(Log-concavity conjecture) The coefficients of Markov polynomials are weakly log-concave on the corresponding Newton polygon.

Note that the Conjecture 6.3 implies the Saturation Conjecture 3.3, claiming the positivity of all the coefficients inside the Newton polygon. Indeed, we know that the coefficients on the boundary are positive, so the appearance of internal zero coefficients will contradict the log-concavity property (25).

Theorem 6.4.

Conjecture 6.3 holds for the Markov-Fibonacci polynomials.

Proof.

We need to check the log-concavity condition in all three principal directions. Using (16), in the horizontal direction we have

Ai,j2=(n−jn+1−i−j)2⁢(i+jj)2=((n−j)!2(n+1−i−j)!2⁢(i−1)!2)⁢((i+j)!2i!2⁢j!2),
Ai−1,j⁢Ai+1,j =(n−jn+2−i−j)⁢(n−jn−i−j)⁢(i+j−1j)⁢(i+j+1j)
=((n−j)!2(n+2−i−j)!⁢(i−2)!⁢(n−i−j)!⁢i!)⁢((i−1+j)!⁢(i+1+j)!j!2⁢(i−1)!⁢(i+1)!).

This implies that

Ai,j2Ai−1,j⁢Ai+1,j =(n+2−i−jn+1−i−j)⁢(ii−1)⁢(i+ji+j+1)⁢(i+1i)
=(n+2−i−jn+1−i−j)⁢(ii−1)⁢(i⁢(i+1)+j⁢(i+1)i⁢(i+1)+j⁢i).

We see that all three terms here are greater than 1 and so we have the required inequality Ai,j2>Ai−1,j⁢Ai+1,j.

Similarly in the vertical case we have

Ai,j2Ai,j−1⁢Ai,j+1=[(n−jn+1−j)⁢(n+2−i−jn+1−i−j)]⁢[(i+ji+j+1)⁢(j+1j)]
=[(n+1−i−j)⁢(n−j)+(n−j)(n+1−i−j)⁢(n−j)+(n+1−i−j)]⁢[j⁢(i+j)+(i+j)j⁢(i+j)+j],

with both of the final fractions being greater than 1 (the first requires that i≥1 but the vertical line for i=0 consists of only a single point, so can be ignored).

In the diagonal case the second binomials in Ai−1,j+1,Ai,j,Ai+1,j−1 are respectively (i+jj+1),(i+jj),(i+jj−1), which are consecutive binomial coefficients satisfying the log-concavity property. As a result we have

Ai,j2Ai−1,j+1⁢Ai+1,j−1≥((n−j)!2(n−j+1)!⁢(n−j−1)!)⁢((n−i−j)!⁢(n+2−i−j)!(n+1−i−j)!2)
=(n−jn−j+1)⁢(n+2−i−jn+1−i−j)=(n−j)⁢(n+1−i−j)+(n−j)(n−j)⁢(n+1−i−j)+(n+1−i−j),

which is greater than or equal to 1 as required. ∎

The Conjecture 6.3 holds along the boundaries of the polygon, since these coefficients are precisely binomial coefficients, which are known to be log-concave. We will show now that this holds also on the 2nd horizontal line and upper diagonal of the Newton polygon.

Lemma 6.5.

Sequences of the form

xk=A⁢(ck)+B⁢(ck−1),k=0,1,…,c

for positive A,B,c are always log-concave.

Proof.

We have

xk2=A2⁢(ck)2+2⁢A⁢B⁢(ck)⁢(ck−1)+B2⁢(ck−1)2,
xk−1⁢xk+1=A2⁢(ck−1)⁢(ck+1)+A⁢B⁢[(ck−1)⁢(ck)+(ck−2)⁢(ck+1)]+B2⁢(ck−2)⁢(ck).

It is clear that the coefficients of A2 and B2 are greater in the case of xk2 due to the log-concavity of the binomial coefficients. So if we can show that

(ck−1)⁢(ck)≥(ck−2)⁢(ck+1),

then the result will follow. Since

(ck−1)⁢(ck)(ck−2)⁢(ck+1)=k+1k−1⁢c−k+2c−k>1,

this completes the proof. ∎

Theorem 6.6.

The coefficients of Markov polynomial Mρ that appear on the lines with j=1 and i+j=a+b−2 of its Newton polygon are strictly log-concave.

Proof.

The proof follows from Theorem 4.2 and the previous lemma. ∎

As for the 3rd diagonal we are only able to prove the log-concavity in the case where ρ≤3/5.

Theorem 6.7.

The coefficients of Markov polynomials Mρ that appear on the line with i+j=a+b−3 of its Newton polygon are log-concave for ab≤35.

Proof.

We will use the following result quoted by Stanley [31] (but which dates back to Newton [25]).

Theorem 6.8 (Stanley [31]).

Let p⁢(X)=∑k=0nαk⁢Xk. If the polynomial p⁢(X) has only real zeros, then the sequence αk is log-concave.

Let αk be the coefficients on the diagonal i+j−3 stated in Theorem 4.2:

αk=E⁢(a+b−3k)+F⁢(a+b−4k−1)+G⁢(a+b−5k−2),
E=(a−1)⁢(a−2)2,F=a⁢(b−a−1),G=12⁢[(b−a)2+5⁢a−3⁢b].

Let

p⁢(X)=∑k=0a+b−3αk⁢Xk,

then we have

p⁢(X) =E⁢(1+X)a+b−3+F⁢X⁢(1+X)a+b−4+G⁢X2⁢(1+X)a+b−5
=(1+X)a+b−5⁢[E⁢(1+X)2+F⁢X⁢(1+X)+G⁢X2]=(1+X)a+b−5⁢q⁢(X),

where

q⁢(X) :=(E+F+G)⁢X2+(2⁢E+F)⁢X+E
=(b−1)⁢(b−2)2⁢X2+(a⁢b−4⁢a+2)⁢X+(a−1)⁢(a−2)2

Since (1+X)a+b−5 has clearly real roots, to apply Theorem 6.8 we need to show that q⁢(X) has only real roots. The discriminant Δ of q⁢(X) is

Δ =(a⁢b−4⁢a+2)2−4⁢(b−1)⁢(b−2)2⁢(a−1)⁢(a−2)2
=(a⁢b−4⁢a+2)2−(a⁢b−2⁢a−b+2)⁢(a⁢b−a−2⁢b+2).

If a/b≤3/5 then a+2⁢b≥4⁢a+a3 and 2⁢a+b≥4⁢a−a3, so

Δ ≥(a⁢b−4⁢a+2)2−(a⁢b−4⁢a+2+a3)⁢(a⁢b−4⁢a+2−a3)=a29≥0.

∎

7 Continuum limit and entropy function

Consider the sequence of fractions ρn=an/bn tending to some α∈[0,1] when n→∞. Let (in,jn) be the sequence of points in the Newton polygons

(26) Δρn={i,j∈ℤ≥0:i/an+j/bn≥1,i+j≤an+bn−1}

such that the corresponding points (ξn=in/bn,ηn=jn/bn)→(ξ,η)∈𝒩α as n→∞, where 𝒩α is the scaled Newton polygon

(27) 𝒩α:={ξ,η∈ℝ:ξ,η>0,ξ+αη>α,ξ+η<α+1.}

Define the entropy function of this sequence as

(28) ℋ=lim supn→∞1bn⁢ln⁡Ain,jn⁢(ρn),

where Ai,j⁢(ρn) are the coefficients of the Markov polynomial Mρn.

Proposition 7.1.

The corresponding limit superior does exist for any such sequences.

The proof follows from the estimate Ai,j⁢(ρn)<mρn, where mρn is the corresponding Markov number, and the results of Fock [13] (see also [29]).

We have two natural questions:

Q.1 Does the entropy ℋ depend only on ξ,η and α, but not on the choice of the sequences?

We conjecture that at least for irrational α this is the case.

Q.2 What are the analytic properties of the entropy function ℋα⁢(ξ,η) on the corresponding Newton polygon 𝒩α?

We conjecture that the entropy function ℋα⁢(ξ,η) is strictly concave on the Newton polygon 𝒩α (and, in particular, it is continuous there).

We prove this now for the sequence ρn=1/n corresponding to Fibonacci polynomials. In that case the scaled Newton polygon is the triangle with vertices at (0,0),(1,0),(0,1).

Let us start with a well-known fact about binomial coefficients.

Let mn be a sequence of positive integers such that mn/n→p∈[0,1] when n→∞.

Proposition 7.2 (Entropy Function for Binomial).

For any such sequence

limn→∞1n⁢ln⁡(nmn)=H⁢(p),
(29) H⁢(p):=−p⁢ln⁡p−(1−p)⁢ln⁡(1−p).
Proof.

Recall the Stirling formula

n!∼2⁢π⁢n⁢(n/e)n,

implying that

(30) ln⁡n!=n⁢ln⁡n−n+O⁢(ln⁡n).

Using this we have

1n⁢ln⁡(nmn)=1n⁢[−mn⁢ln⁡mnn−(n−mn)⁢ln⁡n−mnn+O⁢(ln⁡n)],

which turns to H⁢(p) when n goes to infinity. ∎

To compute the entropy of the Fibonacci polynomials M1/n we can use the explicit formula  (16) for the corresponding coefficients Ai,j⁢(1/n).

Proposition 7.3 (Entropy Function for Fibonacci Polynomials).
limn→∞1n⁢ln⁡Ain,jn⁢(1/n)=(1−η)⁢H⁢(ξ1−η)+(ξ+η)⁢H⁢(ξξ+η),

where ξ=limn→∞inn,η=limn→∞jnn and H is given by (29).

Proof.

Substituting in=n⁢ξn,jn=n⁢ηn into Eq. (16) we have

Ain,jn=(n⁢(1−ηn)n⁢(1−ξn−ηn))⁢(n⁢(ξn+ηn)n⁢ηn)

and therefore

1n⁢ln⁡Ain,jn=1n⁢ln⁡(n⁢(1−ηn)n⁢(1−ξn−ηn))+1n⁢ln⁡(n⁢(ξn+ηn)n⁢ηn).

Applying again formula (30) and using the fact that ξn→ξ,ηn→η we have

limn→∞1n⁢ln⁡Ain,jn=(1−η)⁢H⁢(ξ1−η)+(ξ+η)⁢H⁢(ξξ+η),

with H⁢(p)=−p⁢ln⁡p−(1−p)⁢ln⁡(1−p)=H⁢(1−p). ∎

Theorem 7.4.

The entropy function of Markov-Fibonacci polynomials

(31) ℱ⁢(ξ,η):=(1−η)⁢H⁢(ξ1−η)+(ξ+η)⁢H⁢(ξξ+η)

with H given by (29), is strictly concave on the region ξ,η>0,ξ+η<1. It is invariant under the change (ξ,η)→(ξ,1−ξ−η).

Proof.

We will prove that the Hessian matrix

Hess⁡(ℱ)=(ℱξ⁢ξℱξ⁢ηℱη⁢ξℱη⁢η)

is negative definite. By Sylvester’s criterion it is enough to show that ℱξ⁢ξ<0 and detHess⁡(ℱ)>0. Straightforward calculations lead to

Hess⁡(ℱ)=(1ξ+η−1−2ξ+1ξ+η1ξ+η−1+1ξ+η1ξ+η−1+1ξ+η1ξ+η−1+11−η−1η+1ξ+η).

Clearly ℱξ⁢ξ<0 since 1ξ+η−1<0 and 1ξ>1ξ+η>0. Computing the determinant and simplifying we find

detHess⁡(ℱ)=1η⁢(ξ+η)⁢(1−η)⁢(1−ξ−η),

where all terms in the denominator are positive in the specified region and hence the determinant is positive as required. Therefore the function is strictly concave.

The symmetry (ξ,η)→(ξ,1−ξ−η) is evident from formula (31). ∎

The graph of the corresponding function ℱ⁢(ξ,η) is shown in Figure 10. The maximum value is 2⁢ln⁡1+52 achieved at ξ=15,η=5−510.

Refer to captionξη
Figure 10. Graph of the entropy for Fibonacci polynomials.

8 Critical triangle and Markov sails

We can split up the Newton polygon by drawing ‘critical lines’ i=a,j=b as shown in Figure 11. The set of lattice points with

i<a,j<b,ia+jb>1

we will refer to as the critical triangle.

14641254114321043210ji
Figure 11. Critical triangle of the weighted Newton polygon Δ29. Notice that per our definition, the lines i=2 and j=3 themselves are not considered as part of the critical triangle.

In this section we will look at Markov coefficients inside the critical triangle in more detail. We begin with the following conjecture based on the analysis of experimental data.

Conjecture 8.1.

(Factor 4 Conjecture) The coefficients of Markov polynomials strictly within the critical triangle are divisible by 4.

We are going to be more specific about the coefficients on the lower boundary of the critical triangle, using the following geometric interpretation of continued fractions proposed by Felix Klein.

Take the region [0,a]×[0,b] for some positive integers a,b and divide it into two parts with the line y=ba⁢x. Then consider the convex hull of integer points in each of the two parts, the boundary either side of the line y=ba⁢x will be a broken line that is called, following Arnold, the sail (see [2, 18]). More precisely,

  • •

    The vertices on the sail containing the point (1,0) are defined to be A0,A1,…,An (where A0=(1,0)). This is the lower sail (i.e., below the line).

  • •

    The vertices on the sail containing the point (0,1) are defined to be B0,B1,…,Bn (where B0=(0,1)). This is the upper sail (i.e., above the line).

One can prove that these vertices on the sails can be found as the convergents of the continued fraction for ba (see for example [18]).

In particular, we have the following procedure to find the Klein diagram. Plot points (qk,pk) to represent the continuants Ck alongside the line y=ba⁢x, then connect with straight lines the the points (qk,pk) and (qk+2,pk+2). Note that the points representing even-indexed continuants will all lie above the line y=ba⁢x whilst the odd-indexed ones will lie below.

Example 8.2.

Consider the rational 53=[1,1,2], its continuants are given in the following table.

1 1 2
pk 0 1 1 2 5
qk 1 0 1 1 3

(C−1=01,C0=10,C1=11,C2=21,C3=53).

A0A1A2B0B13210543210
Figure 12. Klein Diagram for the rational 53

More formally we can define Ai’s and Bi’s as follows,

(32) Ai=(q2⁢i−1,p2⁢i−1),Bi=(q2⁢i,p2⁢i),

where pkqk=[a1,a2,…,ak] is the kth convergent. Note that for rationals we always consider the final continuant (i.e., the point (a,b)) to be part of both sails.

There may be more integer points lying on the sail, indeed in the Example 8.2 the point (2,3) lies on the line between A1 and A2. These additional integer points can actually be found immediately if we instead look at the convergents of the Hirzebruch (negative) continued fraction instead, as it was shown by Ustinov in [32].

From the theory of continued fractions, we know

pk=ak⁢pk−1+pk−2,qk=ak⁢qk−1+pk−2.

This means that the line joining the second-last convergent’s coordinates (pk−2,qk−2) to the corner will have gradient equal to the penultimate convergent. This means that if we flip one of the sails, so that they are both on the same side of the diagonal, they will intersect at the point corresponding to the final convergent. In this way we can combine the sails onto one side. More explicitly, if we consider the coordinate system of the lower sail (blue) to have origin at (a,b) and directions reversed from normal then we can connect the sails. In practise, continuing on from Example 8.2 this is shown on the left in Figure 13.

A0A1B0B13210543210B0B1A1A03210543210
Figure 13. (Left) Combined sail for the rational 53; (Right) the reflection in the line x=a/2.

This is precisely the convex hull of the integer lattice above the line y=ba⁢x (with endpoints (0,0),(3,5) omitted).

From Eq. (11) it is clear to see that the critical triangle of the Newton polygon consists of a region [0,a]×[0,b] split via a central diagonal, which is comparable to that of the Klein diagram. Furthermore, we are again only interested in integral points.

Indeed, reflecting the leftmost picture in Figure 13 in the line x=a2 we obtain the critical triangle, where coordinate frames have been shown in their corresponding colours.

The integer points on this combined sail all refer to a monomial in the Markov polynomial and as such they each have their own coefficient. We will refer to this combined sail, together with the coefficients at each point as the Markov sail.

With our change of coordinate frames, we reformulate the definition of points from Eq. (32) to

Ai~=(q2⁢i−1,b−p2⁢i−1),Bi~=(a−q2⁢i,p2⁢i),

but going forward we will omit the tilde’s for simplicity.

8.1 Markov Sail Duality

There is an important Edge-Angle duality between the two sails, saying that the length of a unbroken line on one sail is equal to the ‘index’ at a vertex/rational angle on the opposite sail, see Karpenkov [18].

Here the integer length (denoted l⁢ℓ⁢(A⁢B)) of a line segment A⁢B is defined to be the number of integer points on the its interior plus 1, and the index (denoted l⁢α⁢(∠⁢B⁢A⁢C)) of a rational angle ∠⁢B⁢A⁢C is defined to be the index of the sublattice generated by the integer vectors of the lines A⁢B and A⁢C in the integer lattice, see [18].

Formally, Karpenkov stated this duality as follows

l⁢α⁢(∠⁢Ai⁢Ai+1⁢Ai+2)=l⁢ℓ⁢(Bi⁢Bi+1) =a2⁢i+2,
l⁢α⁢(∠⁢Bi⁢Bi+1⁢Bi+2)=l⁢ℓ⁢(Ai+1⁢Ai+2) =a2⁢i+3,

where ai’s are the partial quotients of the continued fraction ba=[a1,a2,…].

We conjecture that in our case (for the so called Markov sails) we have a sort of duality between the ‘weights’ of these vertices/lines on the sail. Denote ℳ⁢(C) to be the coefficient of the monomial represented at the point C on the Newton polygon, we will refer to these as ℳ-values and define this only for integer points in the interior of the critical triangle (i.e., not on the boundary).

It appears as though, on unbroken lines of the sail, the coefficients differ according to an arithmetic progression. Denote d⁢(Ci⁢Ci+1) to be the common difference of ℳ-values of integer points along an unbroken line segment of the Markov sail between vertices Ci and Ci+1. We conjecture the following extended duality.

Conjecture 8.3.

(Markov Sail Duality) The coefficients of Markov polynomials satisfy Markov sail duality

d⁢(Bi⁢Bi+1) =−ℳ⁢(Ai+1)
d⁢(Ai+1⁢Ai+2) =−ℳ⁢(Bi+1)

This conjecture will provide us with a method for determining almost all ℳ-values on the sail if we having some starting value of which to work from. This is because we known how many integer points lie on each unbroken line from the duality, Corollary 3.1 in [18], so can compute ℳ-values using the equations from this conjecture from some initial condition.

With regard to this initial starting value, we claim that the ℳ-value corresponding to the point of the penultimate continuant is always 4.

Conjecture 8.4.

(Location of 4) Consider the continued fraction ba=[a1,a2,…,an]. If n=2⁢m+1 (odd) then ℳ⁢(Bm)=4. If n=2⁢m (even) then ℳ⁢(Am)=4.

From this value we would then be able to work backwards (alternating between each side of the sail) to recover the ℳ-values on most of the sail (all but on line A0⁢A1 if there are any integer points on its interior). To see this, consider the following example.

Example 8.5.

ba=1813=[1,2,1,1,2]

1 2 1 1 2
pk 0 1 1 3 4 7 18
qk 1 0 1 2 3 5 13

According to Eq. (8) we therefore have A0=(1,18),A1=(1,17),A2=(3,14) and B0=(13,1),B1=(11,3),B2=(8,7).

B0B1B2A0A1A2131211831018171473210
Figure 14. Markov sail for Example 8.5.

According to Conjecture 8.4, since the continued fraction has odd length (n=5,m=2) we should have m⁢(B2)=4. Now using Conjecture 8.3, we should have

d⁢(A2⁢A3) =−ℳ⁢(B2)
d⁢(B1⁢B2) =−ℳ⁢(A2)
d⁢(A1⁢A2) =−ℳ⁢(B1)
d⁢(B0⁢B1) =−ℳ⁢(A1).

Note the integer lengths

l⁢ℓ⁢(A2⁢A3) =a5=2
l⁢ℓ⁢(B1⁢B2) =a4=1,
l⁢ℓ⁢(A1⁢A2) =a3=1,
l⁢ℓ⁢(B0⁢B1) =a2=2.

Noting that Bm is the penultimate integer point before Am+1 on the line Am⁢Am+1 for n odd (this will always be the case), we have

ℳ⁢(A2) =ℳ⁢(B2)+(a5−1)⁢ℳ⁢(B2)=8,
ℳ⁢(B1) =ℳ⁢(B2)+a4⁢ℳ⁢(A2)=12,
ℳ⁢(A1) =ℳ⁢(A2)+a3⁢ℳ⁢(B1)=20.

Since B0 is not in the interior of the critical triangle we cannot apply to conjecture to find its ℳ-value. However, since the integer length of B0⁢B1 is 2 there will be an integer point on the interior of this line (which will lie in the interior of the critical triangle). This interior point however can be found from the conjecture and should have ℳ-value equal to

ℳ⁢(B1)+ℳ⁢(A1)=32.

Checking numerically, all of the ℳ-values calculated in this example agree with the actual ℳ-values, supporting the conjectures in this case.

9 Sails of Pell polynomials

Returning to our ‘simplest’ cases of Markov polynomials, we observe that the critical triangle (and hence sail) is empty for Fibonacci Markov polynomials (as a=1). However, in the case of Markov polynomials corresponding to Pell numbers we can prove some of our earlier conjectures using Eq. (22).

The first of which is the presence and location of the coefficient 4. According to our conjecture the coefficient 4 should lie at coordinates corresponding to the penultimate convergent of ba. Here

ba=n+1n=[1,n]

So the penultimate convergent is [1]=11 and we expect the location of the 4 to be at (1,n) (1 in each direction from corner (0,n+1) since continued fraction is even length).

Theorem 9.1.

For Markov polynomials Mρ, where ρ=nn+1, the coefficient at the coordinate (1,n) in the Newton polygon is 4.

Proof.

Looking at i=1,j=n in Eq. (22), we find

(33) A1,n(2⁢n+1)=[A−1,n(2⁢n−1)+2⁢A0,n−1(2⁢n−1)+A1,n−2(2⁢n−1)]+[A0,n(2⁢n−1)+A1,n−1(2⁢n−1)]−A0,n−1(2⁢n−3).

Clearly if i or j is negative the coefficient will be 0 however this is not the only case where the coefficient is 0. The lower vertices of the Newton polygon for R2⁢n−1 are at (0,n) and (n−1,0) therefore A0,n−1(2⁢n−1),A1,n−2(2⁢n−1) will also be 0 (they are outside the boundaries of the Newton polygon - can be seen rigorously by showing in−1+jn≤1). This leaves the final 3 terms; A0,n(2⁢n−1) and A0,n−1(2⁢n−3) are vertices of their respective Newton polygons and are known to be 1 (and cancel each other out) so we are left with A1,n(2⁢n+1)=A1,n−1(2⁢n−1). So all we need to do is prove that it holds in the base case (n=2, since critical triangle is empty in n=1 case). Direct computation of M2/3 (corresponding to the Markov number 29) shows that this is indeed the case (see Figure 11). ∎

Combining our conjectures regarding coefficients on the sail, in the case Mn/n+1 the integer points on the sail should have coefficients following an arithmetic progression with common difference 4.

Theorem 9.2.

For Markov polynomials Mρ where ρ=nn+1, the coefficients at the coordinates (m,n+1−m) in the Newton polygon are 4⁢m, for m=1,2,…,n−1.

Proof.

For m=1 the result is proven - it is precisely Theorem 9.1.

To complete the proof we need to consider two seperate cases; m=2,…,n−2 and m=n−1. In both cases, Eq. (22) becomes

Am,n+1−m(2⁢k+1)=[Am−2,n+1−m(2⁢k−1)+2⁢Am−1,n−m(2⁢k−1)+Am,n−m−1(2⁢k−1)]+[Am−1,n+1−m(2⁢k−1)+Am,n−m(2⁢k−1)]−Am−1,n−m(2⁢k−3).

For m=1,2,…,n−1, the first 3 terms on the RHS are 0 (outside the Newton polygon), leaving

Am,n+1−m(2⁢k+1)=[Am−1,n+1−m(2⁢k−1)+Am,n−m(2⁢k−1)]−Am−1,n−m(2⁢k−3).

By induction this becomes Am,n+1−m(2⁢k+1)=[4⁢(m−1)+4⁢m]−4⁢(m−1)=4⁢m, where we can check the first two (relevant) cases directly k=2,3.

For m=n−1, the term Am,n−m−1(2⁢k−1)=An−1,0(2⁢k−1) does not disappear, in fact it corresponds to a lower boundary point and equals 1 and also the coefficients Am,n−m(2⁢k−1)=An−1,1(2⁢k−1) and Am−1,n−m(2⁢k−3)=An−2,1(2⁢k−3) lie on the boundary of the critical triangle (not in the interior so we can use the same inductive argument).

However, Theorem 4.2 tells us that the first point on the first horizontal (j=1) has coefficient An−1,1(2⁢k−1)=3⁢(n−1)−1 and An−2,1(2⁢k−3)=3⁢(n−2)−1 and so Eq. (22) becomes

An−1,2(2⁢k+1) =An−1,0(2⁢k−1)+[An−2,2(2⁢k−1)+An−1,1(2⁢k−1)]−An−2,1(2⁢k−3)
=1+[4⁢(m−1)+(3⁢(n−1)−1)]−(3⁢(n−2)−1)=4⁢m

as required. ∎

So now we have proven the coefficients on the whole of the interior of the sail. As mentioned we also know one of the boundary coefficients of the sail, namely An,1(2⁢k+1)=3⁢n−1. If we can determine the other boundary A1,n+1(2⁢k+1) then we will know the sail coefficients in their entirety.

Again using Eq. (22),

A1,n+1(2⁢k+1)=[A−1,n+1(2⁢k−1)+2⁢A0,n(2⁢k−1)+A1,n−1(2⁢k−1)]+[A0,n+1(2⁢k−1)+A1,n(2⁢k−1)]−A0,n(2⁢k−3).

Since

A−1,n+1(2⁢k−1)=0,A0,n(2⁢k−1)=1,A1,n−1(2⁢k−1)=4,A0,n+1(2⁢k−1)=n−2,A0,n(2⁢k−3)=n−3,

we have

A1,n+1(2⁢k+1)=[0+2⁢(1)+4]+[n−2+A1,n(2⁢k−1)]−(n−3)=A1,n(2⁢k−1)+7.

Computing A1,3(3)=4, the solution to this recursion is A1,n+1(2⁢k+1)=7⁢n−10, so now we have the weights on the sail in its entirety: from top to bottom (7⁢n−10, 4, 8,…, 4⁢n−4, 3⁢n−1).

10 Markov polynomials via generalised Cohn matrices

Harvey Cohn [6] proposed the following remarkable way to compute Markov numbers. He suggested to replace the addition of integer numbers in u+v=w in the Euclid tree by multiplication of 2×2 matrices, starting from a special pair.

More precisely, using the Conway topograph we define the Cohn tree as in Figure 15,

BAA⁢BA⁢B2A⁢B⁢A⁢B2A⁢B3⋯A⁢B⁢A⁢B2⁢A⁢B2⋯⋯A2⁢BA2⁢B⁢A⁢BA3⁢B⋯⋯A3⁢B⁢A2⁢BA4⁢B
Figure 15. The Cohn tree.

starting with the Cohn matrices

(34) A=(1112),B=(3243).

The relation between Cohn and Markov trees is given by the trace map (see [1, 30]):

C↦m=13⁢tr⁡C,

or, by taking the off-diagonal element m=C12 (see Fig. 16).

2152913(1112)(3243)(75118)(41296546)(18132921)
Figure 16. Cohn and Markov trees related by trace map

Define now the following generalised Cohn matrices as

(35) A=C0/1:=(y2xx⁢y2x2+z2),B=C1/1:=(x2⁢y2+y4+y2⁢z2x3+x⁢y2x3⁢y2+x⁢y4+2⁢x⁢y2⁢z2x4+x2⁢y2+x2⁢z2),

and consider the corresponding generalisation of Cohn tree (15). We claim that the analogue of Cohn’s construction leads to the Markov polynomials.

Theorem 10.1.

The numerator Pa/b⁢(x2,y2,z2) of the corresponding Markov polynomial (7) can be found from Cohn matrices as

(36) Pa/b⁢(x2,y2,z2)=tr⁡Ca/bx2+y2+z2,

or, as the upper right entry of Ca/b divided by x.

The proof is a modification of the arguments from Chapter 4 of Aigner’s book—see [9] for the details.

Note in the special case u=q,v=1,w=q2 our Cohn matrices are conjugated to Cohn matrices introduced in [20]. Deformations of Cohn matrices from [10, 19] lead to different modifications of the Markov equation.

Since all the coefficients of the entries of the Cohn matrices are positive, as a corollary we have an independent proof of the non-negativity of Markov coefficients [28].

Corollary 10.2.

All the coefficients of the Markov polynomials are non-negative.

It would be interesting to extend this to the proof of the saturation conjecture.

The usual Cohn matrices A and B are known to generate the commutator subgroup of the modular group PSL⁢(2,ℤ) (see [1]).

A natural question is if the same is true for the Laurent analogue of the modular group ΓL=PSL⁢(2,ℤ⁢[x±1,y±1,z±1]), which is the quotient of the group SL⁢(2,ℤ⁢[x±1,y±1,z±1]) consisting of the matrices

g=(A11A12A21A22),Ai⁢j∈ℤ⁢[x±1,y±1,z±1],detg=xi⁢yj⁢zk,i,j,k∈ℤ

by the monomial subgroup consisting of ±xi⁢yj⁢zk⁢I,i,j,k∈ℤ.

Consider the following deformation of the standard generators of the modular group

L=(1011),R=(1101),S=(01−10),

defined by

(37) L~=(y0x⁢yz),R~=(z10x),S~=(01−y20).

Their choice is motivated by the desire to keep the commutator relations between the Cohn matrices and the generators L,R,S of the modular group:

A=[L,S],B=[L,S]⁢[R,S],

where [x,y]:=x⁢y⁢x−1⁢y−1 is the group commutator. Note that L~,R~,S~ have determinants y⁢z,x⁢z,y2 respectively and thus do not generate the whole group ΓL. It would be interesting to find a good set of generators of ΓL.

Proposition 10.3.

Generalised Cohn matrices (36) belong to the commutator of the Laurent modular group ΓL and satisfy the same relations as in the classical case:

A=[L~,S~],B=[L~,S~]⁢[R~,S~],

The proof follows from the matrix equalities

[L~,S~]=y−1⁢z−1⁢(y2xx⁢y2x2+z2),[R~,S~]=x−1⁢z−1⁢(y2+z2xx⁢y2x2),
[L~,S~]⁢[R~,S~]=x−1⁢y−1⁢z−2⁢(x2⁢y2+y4+y2⁢z2x3+x⁢y2x3⁢y2+x⁢y4+2⁢x⁢y2⁢z2x4+x2⁢y2+x2⁢z2).

Note that we can start the Cohn tree with the matrices

A=(y2xx⁢y2x2+z2),B′=(y2+z2xx⁢y2x2),

which are certain quantisations of Arnold’s cat-matrices. They generate a subgroup in the commutator of ΓL, which could be of special interest.

11 Concluding remarks

As we have seen, there are many questions about Markov polynomials, which are still to be answered. Already the question if they provide (up to change of sign of any two of them) all integer Laurent-polynomial solutions to the generalised Markov equation (2) is still open. This can be considered as a Laurent-polynomial analogue of the strong approximation conjecture by Bourgain, Gamburd and Sarnak [3] about connectivity of the Markov graph of the mod-p solutions of the Markov equation (see recent progress in this direction in [8]).

Note that from Theorem 3.1 it follows that all Markov polynomials are distinct, which implies that for a generic choice of the hyperbolic structure on a once-punctured torus, no two simple closed geodesics have the same length [28]. On the relation with hyperbolic geometry and the Teichmüller theory we refer to [12, 13, 27].

We have shown also that there are very plausible conjectures about the coefficients of Markov polynomials. They can be reformulated combinatorially using the weighted perfect matching interpretation of these coefficients proposed in [17, 28, 5]. It would be interesting to explore if this combinatorial interpretation can help to prove some of them (in particular, the Factor-4 conjecture).

Finally, the Laurent version ΓL of the modular group seems to be interesting in its own right and deserves a more detailed study (generators, relations, commutator, etc.).

Acknowledgements.

We would like to thank Jonah Gaster, Oleg Karpenkov, Dylan Thurston, Li Li and especially Ralf Schiffler and Alexey Ustinov for very helpful discussions.

One of us (Sam Evans) is grateful to the Higher Education, Research and Innovation Department of the French Embassy in the UK for the support of his visit to Laboratoire de Mathématiques de Reims UMR 9008 in June 2025.

References

  • [1] M. Aigner Markov’s Theorem and 100 Years of the Uniqueness Conjecture: A Mathematical Journey from Irrational Numbers to Perfect Matchings. Springer, 2013.
  • [2] V.I. Arnold Continued fractions. Moscow Center of Continuous Mathematical Education, Moscow, 2002 (in Russian).
  • [3] J. Bourgain, A. Gamburd and P. Sarnak. Markoff surfaces and strong approximation. Comptes Rendus de l’Acad. Sci. 354:2 (2016), 131–135.
  • [4] Ph. Caldero, A.V. Zelevinsky Laurent expansions in cluster algebras via quiver representations. Moscow Mathematical Journal, 2006, 6:3 (2006), 411–429.
  • [5] İ. Çanakçı, R. Schiffler Snake graphs and continued fractions. European J. of Combinatorics 86 (2020), article 103081.
  • [6] H. Cohn Approach to Markoff’s minimal forms through modular functions. Annals of Math. 61 (1955), 1–12.
  • [7] J.H. Conway The Sensual (Quadratic) Form, Carus Mathematical Monographs, Vol.26. Mathematical Association of America, 1997.
  • [8] J. Eddy, E. Fuchs, M. Litman, D. Martin, N. Tripeny Connectivity of Markoff mod-p graphs and maximal divisors. Proc. London Math. Soc. 130 (2025) article e70027.
  • [9] S.J. Evans Quantum Numbers and Markov Polynomials. PhD Thesis, Loughborough University, September 2025.
  • [10] S. Evans, P. Jouteur, S. Morier-Genoud, V. Ovsienko On q-deformed Markov numbers. Cohn matrices and perfect matchings with weighted edges, arXiv:2507.19080.
  • [11] J. Fei Combinatorics of F-polynomials. International Mathematics Research Notices, Vol. 2023, No. 9, 7578–-7615.
  • [12] A. Felikson, M. Shapiro, P. Tumarkin Skew-symmetric cluster algebras of finite mutation type. J. Eur. Math. Soc. 14:4 (2012), 1135–1180.
  • [13] V. V. Fock Dual Teichmüller spaces. Preprint 1997, arXiv:dg-ga/9702018v3.
  • [14] S. Fomin and A. Zelevinsky Cluster algebras. I. Foundations. J. Amer. Math. Soc. 15 (2002), no. 2, 497–529.
  • [15] S. Fomin and A. Zelevinsky The Laurent phenomenon. Advances in Applied Mathematics 28:2 (2002),119–144.
  • [16] G. Frobenius Über die Markoffschen Zahlen. Sitzungsberichte der Preußischen Akademie der Wissenschaften zu Berlin, 1913.
  • [17] A. Itsara, G. Musiker, J. Propp, and R. Viana Combinatorial interpretations for the Markoff numbers. Memo dated May 1, 2003; https://www-users.cse.umn.edu/~musiker/Markoff2003.pdf
  • [18] O. Karpenkov Geometry of Continued Fractions. Springer, 2022.
  • [19] T. Kogiso q-deformations and t-deformations of the Markov triples, arXiv:2008.12913.
  • [20] L. Leclere and S. Morier-Genoud q-deformations in the modular group and of the real quadratic irrational numbers. Adv. Appl. Math. 130 (2021).
  • [21] L. Leclere, S. Morier-Genoud, V. Ovsienko and A. Veselov On radius of convergence of q-deformed real numbers. Mosc. Math. J. 24 (2024), 1–9.
  • [22] K. Lee, L. Li, R. Schiffler Newton polytopes of rank 3 cluster variables. Algebraic Combinatorics 3:6 (2020), 1293–1330.
  • [23] A.A. Markoff Sur les formes quadratiques binaires indéfinies. Mathematische Annalen, 15 (1879), 381–406; 17 (1880), 379–399.
  • [24] S. Morier-Genoud and V. Ovsienko q-deformed rationals and q-continued fractions. Forum Math. Sigma 8 (2020), e13, 55pp.
  • [25] I. Newton Arithmetica Universalis: Sive De Compositione Et Resolutione Arithmetica Liber. London 1707.
  • [26] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org.
  • [27] R.C. Penner The decorated Teichmüller space of punctured surfaces. Comm. Math. Phys. 113 (1987), 299-339.
  • [28] J. Propp The combinatorics of frieze patterns and Markoff numbers. Integers 20 (2020), article A12.
  • [29] A. Sorrentino and A.P. Veselov Markov numbers, Mather’s beta-function and stable norm. Nonlinearity 32, Number 6 (2019), 2147–2156.
  • [30] K. Spalding, A.P. Veselov Lyapunov spectrum of Markov and Euclid trees. Nonlinearity 30 (2017), 4428–4453.
  • [31] R.P. Stanley Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Ann. New York Acad. Sci, 576(1), 500–535 (1989).
  • [32] A.V. Ustinov Geometric proof of Rødseth’s formula for Frobenius numbers. Proceedings of the Steklov Institute of Math. 76, 275–282 (2012).
  • [33] A. Zelevinsky Semicanonical basis generators of the cluster algebra of type A1(1). The Electronic Journal of Combinatorics 14.1 (2007): Research paper N4, 5 p.