Brendon Rhoades
email: brhoades@math.mit.edu

The cluster and dual canonical bases of Z[x 11 , . . . , x 33 ] are equal

Keywords: quantum group, cluster algebra, canonical basis

The polynomial ring Z[x11, . . . , x33] has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group Uq(sl3(C)). On the other hand, Z[x11, . . . , x33] inherits a basis from the cluster monomial basis of a geometric model of the type D4 cluster algebra. We prove that these two bases are equal. This extends work of Skandera and proves a conjecture of Fomin and Zelevinsky.

Introduction

For n ≥ 0, let A n denote the polynomial ring Z[x 11 , . . . , x nn ] in the n 2 commuting variables (x ij ) 1≤i,j≤n . The algebra A n has an obvious Z-basis of monomials in the variables x ij , which we call the natural basis. In addition to the natural basis, the ring A n has many other interesting bases. Examples include a bitableau basis defined by Mead and popularized by Désarménien, Kung, and Rota [START_REF] Énien | Invariant theory, Young bitableaux and combinatorics[END_REF] having applications in invariant theory and the dual canonical basis of Lusztig [START_REF] Lusztig | Canonical bases arising from quantized enveloping algebras[END_REF] and Kashiwara [START_REF] Kashiwara | On crystal bases of the Q-analog of universal enveloping algebras[END_REF] whose quantization facilitates the study of representations of the quantum group U q (sl n (C)). Given two bases of A n , it is natural to compare them by examining the corresponding transition matrix. For example, in [START_REF] Rhoades | Bitableaux and zero sets of dual canonical basis elements[END_REF] it is shown that these latter two bases are related via a transition matrix which may be taken to be unitriangular (i.e., upper triangular with 1's on the main diagonal) with respect to an appropriate ordering of basis elements.

Cluster algebras are a certain class of commutative rings introduced by Fomin and Zelevinsky [START_REF] Fomin | Cluster algebras I: Foundations[END_REF] to study total positivity and dual canonical bases. Any cluster algebra comes equipped with a distinguished set of generators called cluster variables which are grouped into finite overlapping subsets called clusters, all of which have the same cardinality. The cluster algebras with a finite number of clusters have a classification similar to the Cartan-Killing classification of finite-dimensional simple complex Lie algebras [START_REF] Fomin | Cluster algebras II: finite type classification[END_REF]. In this classification, it turns out that the cluster algebra of type D 4 is a localization of the ring A 3 (see for example [START_REF] Skandera | The Cluster Basis of Z[END_REF]) and the ring A 3 inherits a Z-basis consisting of cluster monomials. We call this basis the cluster basis. Fomin and Zelevinsky conjectured that the cluster basis and the dual canonical basis of A 3 are equal, and Skandera showed that any two of the natural, cluster, and dual canonical bases of A 3 are x 11

x 12

x 21 x 22 x 23

x 32 x 33 ∆ 23,23 (x) ∆ 23,13

∆ 13,23 (x) ∆ 13,13 (x) ∆ 13,12 related via a unitriangular transition matrix when basis elements are ordered appropriately [START_REF] Skandera | The Cluster Basis of Z[END_REF]. In this paper we strengthen Skandera's result and prove Fomin and Zelevinsky's conjecture with the following result (definitions will be postponed until Sections 2 and 3).

Theorem 1 The dual canonical and cluster bases of A 3 are equal.

Since each of the cluster and frozen variables of A 3 are irreducible polynomials, this result can be viewed as giving a complete factorization of the dual canonical basis elements of A 3 into irreducibles. Because the natural GL 3 (C) action on C ⊗ Z A 3 is multiplicative, this could aid in constructing representing matrices for this action with respect to the dual canonical basis.

Theorem 1 will turn out to be the classical q = 1 specialization of a result (Theorem 33) comparing two bases of a noncommutative quantization A (q) 3 of the polynomial ring A 3 . The remainder of this paper is devoted to the proof of this basis equality. In Section 2 we define the cluster basis of the classical ring A 3 . In Section 3 we introduce the quantum polynomial ring A (q) n together with its dual canonical basis and a quantum analogue of the cluster basis of A 3 . In Section 4 we use a result of Zhang [START_REF] Zhang | On dual canonical bases[END_REF] and some rather involved computations to show that the quantum analogues of the cluster and dual canonical bases coincide up to a factor q (which may depend on the basis element in question) and deduce Theorem 1. In Section 5 we comment on possible extensions of the results in this paper.

For any two subsets I, J ⊆ [START_REF] Du | IC bases and quantum linear groups[END_REF] of equal size, define the (I, J)-minor ∆ I,J (x) of x = (x i,j ) 1≤i,j≤3 to be the determinant of the submatrix of x with row set I and column set J. Define additionally two more polynomials, the 132-and 213-Kazhdan-Lusztig immanants of x, by Imm 132 (x) = x 11 x 23 x 32 -x 12 x 23 x 31 -x 13 x 21 x 32 + x 13 x 22 x 31 and

Imm 213 (x) = x 12 x 21 x 33 -x 12 x 23 x 31 -x 13 x 21 x 32 + x 13 x 22 x 31 .

The cluster variables are the 16 elements of A 3 shown in Figure 1 [12, p. 3], with the associated decorated octagons. Every octagon is decorated with either a pair of parallel nonintersecting nondiameters or a diameter colored one of two colors, red/dashed or blue/solid. Using the terminology in [START_REF] Fomin | Y-systems and generalized associahedra[END_REF], a centrally symmetric colored triangulation of the octagon is a maximal collection of the above octagon decorations without intersections except that distinct diameters of the same color can intersect and identical diameters of different colors can coincide. Every centrally symmetric colored triangulation of the octagon consists of four decorations, and a cluster is the associated four element set of polynomials corresponding to the decorations in such a triangulation. There are 50 centrally symmetric colored triangulations of the octagon, and hence 50 clusters. Four examples of centrally symmetric colored triangulations are shown in Figure 2. The corresponding clusters are, from left to right, {x 21 , x 23 , ∆ 23,13 (x), ∆ 23,23 (x)}, {x 23 , x 33 , ∆ 12,13 (x), Imm 132 (x)}, {x 12 , x 21 , x 22 , ∆ 23,23 (x)}, and {x 11 , x 12 , x 21 , ∆ 12,12 (x)}. Elements in F are called frozen variables and the union of F with any cluster is an extended cluster. A cluster monomial is a product of the form z b1 1 • • • z b9 9 , where {z 1 , . . . , z 9 } is an extended cluster and the b i are nonnegative integers.

For any n ≥ 0, the set Mat n (N) is equipped with a partial order ≤ lex called lex order defined as follows. Endow the set [n] × [n] with lexicograpihcal order. Given a matrix A ∈ Mat n (N), the word w(A) of A is defined to be the unique nondecreasing word in [n] × [n] where the multiplicity of the letter (i, j) is equal to the (i, j)-entry of A. Given two matrices A, B ∈ Mat n (N), we say that A ≤ lex B if and only if the words w(A) and w(B) of A and B have the same length and w(A) ≥ w(B) in the lexicographical order in sequences in

[n] × [n] induced from the lexicographical order on [n] × [n]. Example 2 Let A = 1 1 1 1 and B = 1 2 1 0
. The words w(A) and w(B) are given by w

(A) = (1, 1)(1, 2)(2, 1)(2, 2) and w(B) = (1, 1)(1, 2)(1, 2)(2, 1) and therefore A < lex B.
Skandera [START_REF] Skandera | The Cluster Basis of Z[END_REF] develops a map φ from the set of cluster monomials to the set Mat 3 (N) as follows. For any cluster or frozen variable z, let φ(z) be the unique lex least matrix A for which the monomial x

(A)1,1 11 • • • x (A)n,n nn
appears in the expansion of z in the natural basis, where (-) i,j denotes taking the (i, j)entry of a matrix. In particular, if E ij ∈ Mat 3 (N) denotes the 3 × 3 matrix with a 1 in the (i, j)-position and zeroes elsewhere, we have that for any minor ∆ I,J (x) with I, J ⊆ [START_REF] Du | IC bases and quantum linear groups[END_REF] and

I = {i 1 < • • • < i r } and J = {j 1 < • • • < j r }, the value of φ on ∆ I,J (x) is φ(∆ I,J (x)) = E i1j1 + • • • + E irjr . In addition, we have that φ(Imm 132 (x)) = E 11 + E 23 + E 32 and φ(Imm 213 (x)) = E 12 + E 21 + E 33 . Given an arbitrary cluster monomial z b1 1 • • • z b9 9 , extend the definition of φ via φ(z b1 1 • • • z b9 9 ) := b 1 φ(z 1 ) + • • • + b 9 φ(z 9 ).

Proposition 3 ([12])

The map φ is a bijection from the set of cluster monomials to Mat 3 (N).

The fact that φ is a bijection is used in [START_REF] Skandera | The Cluster Basis of Z[END_REF] to show that the set of cluster monomials is related to the natural basis of A 3 via a unitriangular, integer transition matrix, and thus is actually a Z-basis for A 3 (the fact that the cluster monomials form a basis is also a consequence of more general cluster algebra theory). This basis is called the cluster basis of A 3 .

Example 4 Consider the cluster corresponding to the leftmost centrally symmetric colored triangulation in Figure 2, i.e. {x 21 , x 23 , ∆ 23,13 (x), ∆ 23,23 (x)}. An example of a cluster monomial drawn from the corresponding extended cluster is

z := x 7 21 x 0 23 ∆ 23,13 (x) 2 ∆ 23,23 (x) 1 x 0 13 ∆ 12,23 (x) 2 ∆ 123,123 (x) 0 ∆ 23,12 (x) 0 x 7 31 .
We have that

φ(z) = 7   0 0 0 1 0 0 0 0 0   + 0   0 0 0 0 0 1 0 0 0   + 2   0 0 0 1 0 0 0 0 1   + • • • =   0 2 0 9 1 2 7 0 3   .
3 The Quantum Polynomial Ring

For n ≥ 0, define the quantum polynomial ring A (q)

n to be the unital noncommutative Z[q ±1/2 ]-algebra generated by the n 2 variables x = (x ij ) 1≤i,j≤n and subject to the relations

x ik x il = qx il x ik (1) x ik x jk = qx jk x ik (2) x il x jk = x jk x il (3)
x ik x jl = x jl x ik + (q -q -1 )x il x jk , (4)
where i < j and k < l. It follows from these relations that the specialization of A (q)

n to q = 1 recovers the classical polynomial ring A n . The center of A (q) n is generated by the quantum determinant det q (x) := w∈Sn (-q) (w) x 1,w(1) • • • x n,w(n) . Here (w) denotes the Coxeter length of a permutation w. Factoring the extension C ⊗ Z A (q) n by the ideal (det q (x) -1) yields the quantum coordinate ring O q (SL n (C)) of the special linear group. Given two ring elements f, g ∈ A (q) n , we say that f is a q-shift of g if there exists a ∈ 1 2 Z so that f = q a g.

The natural basis of A n lifts to a Z[q ±1/2 ]-basis of the quantum polynomial ring A (q) n given by {X

A := x w(A)1 • • • x w(A) N | A ∈ Mat n (N)}, where w(A) = w(A) 1 • • • w(A) N is the word of A. A monomial m in the generators x ij of A (q)
n will be said to be in lex order if it is of the form m = X A for some (necessarily unique) matrix A. We call this basis the quantum natural basis (QNB). We will find it convenient to work with a Z[q ±1/2 ]-basis of A (q) n whose elements are q-shifts of QNB elements. Following [START_REF] Zhang | On dual canonical bases[END_REF], for any matrix A = (a ij ) ∈ Mat n (N), define the number e(A) := -1 2 i j<k (a ij a ik + a ji a ki ) and the quantum polynomial X(A) := q e(A) X A ∈ A (q) n . We have that e(A) = 0 whenever A ∈ Mat n (N) has at most one nonzero entry in every row and column and, in particular, we have e(φ(z)) = 0 for any quantum cluster or frozen variable z. The set

{X(A) | A ∈ Mat n (N)} is also a Z[q ±1/2 ]-basis of A (q)
n , called the modified quantum natural basis (MQNB).

As with the classical polynomial ring A n , the quantum ring

A (q)
n admits a natural N-grading by degree. Finer than this grading is an N n × N n -grading, where the (r 1 , . . . , r n ) × (c 1 , . . . , c n )-graded piece is the Z[q ±1/2 ]-linear span of all MQNB elements X(A) for matrices A ∈ Mat n (N) with row sum vector row(A) = (r 1 , . . . , r n ) and column sum vector col(A) = (c 1 , . . . , c n ). It is routine to check from Relations 1-4 that this grading is well-defined.

Example 5 Let n = 2 and let A = 1 2 1 0 . We have that

X A = x 11 x 2 12 x 21 ∈ A (q) 2 , e(A) = -3 2 ,
and therefore

X(A) = q -3 2 x 11 x 2 12 x 21 ∈ A (q) 2 . Both X A and X(A) lie in the (3, 1) × (2, 2)-graded component of A (q)
2 with respect to its N 2 × N 2 -grading.

The ring A (q)

n is equipped with an involutive bar antiautomorphism defined by the Z-linear extension of q 1/2 = q -1/2 and x ij = x ij . It follows readily from Relations 1-4 that • is well-defined. Observe that the bar involution specializes to the identity map at q = 1. The dual canonical basis (DCB) of A (q) n arises naturally when attempting to find bases of A (q) n consisting of bar invariant polynomials. Define a partial order ≤ Br on Mat n (N) called Bruhat order by letting A ≤ Br B if B can be obtained from A by a sequence of 2 × 2 submatrix transformations of the form

a ik a il a jk a jl → a ik -1 a il + 1 a jk + 1 a jl -1 ,
for i < j and k < l with a ik , a ji > 0. Observe that the restriction of ≤ Br to the set of permutation matrices is isomorphic to the ordinary (strong) Bruhat order on the symmetric group S n . Observe also that matrix transposition and antitransposition are automorphisms of the poset (Mat n (N), ≤ Br ). (Matrix antitransposition acts on square matrices x = (x ij ) 1≤i,j≤n by reflection across the main antidiagonal {x i,n-i+1 | 1 ≤ i ≤ n}.) Bruhat order and lex order on Mat n (N) are related by the implication (A ≤ Br B) ⇒ (A ≤ lex B) which can be easily checked on the generating relation ≺ Br . Given a free Z[q ±1/2 ]-module M equipped with a Z-involution D : M → M satisfying certain conditions, Du [START_REF] Du | IC bases and quantum linear groups[END_REF] introduced the notion of an IC basis, which is a certain normalized basis of a Z[q 1/2 ]submodule of M which is fixed pointwise by the action of D. Zhang [14, Theorem 3.2] applied Du's result to the case where M = A (q) n and D is the bar involution to get an IC basis for a Z[q 1/2 ]-submodule of A (q) n . The following is a slight modification of Zhang's result.

Theorem 6 There exists a unique Z[q ±1/2 ]-basis

{b(A) | A ∈ Mat n (N)} of A (q)
n where b(A) is homogeneous with respect to the N n × N n -grading of A

(A) = X(A) + B> Br A β A,B (q 1/2 )X(B),
where the β A,B are polynomials in

q 1/2 Z[q 1/2 ].
This basis is called the dual canonical basis.

Proof: We first prove the weaker assertion that there exists a unique bar invariant

Z[q ±1/2 ]-basis {b(A) | A ∈ Mat n (N)} of A (q)
n such that b(A) is homogeneous with respect to the

N n × N n -grading of A (q) n and the MQNB expansion of b(A) is of the form b(A) = X(A) + B> lex A β A,B (q 1/2 )X(B),
where the β A,B are polynomials in q 1/2 Z[q 1/2 ]. Let L ⊆ A (q)
n denote the free Z[q 1/2 ]-module with basis {X(A) | A ∈ Mat n (N)}. By [14, Theorem 3.2], there exists a unique bar invariant Z[q 1/2 ]-basis

{b(A) | A ∈ Mat n (N)} of L such that the MQNB expansion of b(A) has the form b(A) = X(A) + B> lex A β A,B (q 1/2 )X(B),
for some polynomials β A,B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ] and b(A) is homogeneous with respect to the N n × N ngrading of A (q) n of degree row(A) × col(A). This Z[q 1/2 ]-basis of L is also a Z[q ±1/2 ]-basis of A (q) n . On the other hand, any

Z[q ±1/2 ]-basis {b(A) | A ∈ Mat n (N)} of A (q) n such that the MQNB expansion of b(A) has the form b(A) = X(A) + B> lex A β A,B (q 1/2 )X(B),
for some polynomials β A,B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ] is also a Z[q 1/2 ]-basis of L. This implies our weaker assertion.

Let

{b(A) | A ∈ Mat n (N)} be the unique Z[q ±1/2 ]-basis of A (q)
n guaranteed by our weaker assertion. We claim that the coefficient β A,B (q

1/2 ) in the MQNB expansion b(A) = X(A) + B> lex A β A,B (q 1/2 )X(B),
is equal to zero unless B > Br A. Indeed, the first paragraph of the proof of [START_REF] Zhang | On dual canonical bases[END_REF]Corollary 3.4] asserts that the matrix B corresponding to any nonzero term in this expansion may be obtained from A by a sequence of 2 × 2 submatrix transformations of the type

a ik a il a jk a jl → a ik -1 a il + 1 a jk + 1 a jl -1 .
This comes from the fact that when one uses Relations 1-4 to express D(X(A)) in terms of the MQNB, only the application of 4 leads to nonzero terms X(B) for potentially new matrices B and each application of 4 may be interpreted as a submatrix transformation of this form. One deduces that only matrices B arising from A by a sequence of such transformations can have terms X(B) appearing with nonzero coefficient in the corresponding basis element b(A). 2

While the DCB is important in the study of the representation theory of the quantum group U q (sl n (C)) [START_REF] Kashiwara | On crystal bases of the Q-analog of universal enveloping algebras[END_REF][START_REF] Lusztig | Canonical bases arising from quantized enveloping algebras[END_REF] , the lack of an elementary formula for the expansion of the b(A) in the MQNB can make computations involving the DCB difficult. Due to the triangularity condition (2) in Theorem 6, we will often need to study quantum ring elements f ∈ A (q) n which have a q-shift (necessarily unique) whose MQNB expansion is of the form X(A) + B> Br A β A,B (q 1/2 )X(B), where the β A,B are polynomials in q 1/2 Z[q 1/2 ]. For short, we will call such ring elements q-triangular. We remark that the restriction of the DCB of the quantum ring A (q) n to q = 1 yields a basis of the classical polynomial ring A n , also called the dual canonical basis.

In studying q-triangularity, we will frequently need to analyze expansions of quantum ring elements in the (M)QNB. To find these expansions, we use relations 1-4 to express arbitrary ring elements as a linear combination of monomials which are in lex order. While the somewhat exotic Relation 4 can make for complicated expansions, this straightening procedure is somewhat well behaved with respect to the unique Bruhat minimal term, when it exists.

More precisely, given any product m ∈ A (q) n of the generators x ij and a ground ring element β ∈ Z[q ±1/2 ], define the content C(βm) of βm to be the n × n matrix whose (i, j)-entry is equal to the number of occurrences of x ij in m. Also, if a ring element f ∈ A (q) n has a QNB expansion of the form

f = B≥ Br A β A,B X B with β A,B ∈ Z[q ±1/2 ] and β A,A = 0, set σ(f ) := β A,A X A ∈ A (q)
n . If f does not have a QNB expansion of this form, leave σ(f ) undefined. The following lemma states a couple facts about the function σ which will be used in Section 4 to analyze Bruhat minimal terms of ring elements in

A (q) n . Lemma 7 (Leading Lemma) (1) Let f = βm + β 1 m 1 + • • • + β r m r ∈ A (q) n be an element of A (q) n such that β k ∈ Z[q ±1/2 ]
for all k, the m k are monomials in the x ij , and C(m) < Br C(m k ) for all k. Then, σ(f ) is defined and has content C(m).

(

) Suppose that f, g ∈ A (q) 2
n are ring elements such that σ(f ) and σ(g) are both defined. Then, we have that σ(f g) = σ(σ(f )σ(g)), where both sides of this equation are defined.

Proof: (1) To expand f in the QNB, we apply the Relations 1-4 to express the summands m, m 1 , . . . , m r as a linear combination of monomials in lex order. The application of Relations 1-3 to a monomial in the generators x ij does not change the content of this monomial. Moreover, the application of Relation 4 to any monomial m 0 in A (q) n yields a sum m 0 -(q -q -1 )m 0 , where m 0 has the same content as m 0 and m 0 has content which is greater in Bruhat order than the content of m 0 .

(2) There exist matrices A, A ∈ Mat n (N) and ground ring elements

β A,B , β A ,B ∈ Z[q ±1/2 ] with β A,A , β A ,A = 0 such that f = B≥ Br A β A,B X B and g = B ≥ Br A β A ,B X B .
Multiplying these expressions together and expanding, we see that

f g = B≥ Br A,B ≥ Br A β A,B β A ,B X B X B .
For any term in the above sum, we have the associated content matrix

C(β A,B β A ,B X B X B ) = B + B ∈ Mat n (N).
It can be checked that matrix addition (B, B ) → B + B gives an order preserving map

(Mat n (N) × Mat n (N), ≤ Br × ≤ Br ) → (Mat n (N), ≤ Br ). Therefore, by Part 1, σ(f g) is well defined and has content C(σ(f g)) = A + A . By the same reasoning as in the proof of Part 1, if B ≥ Br A and B ≥ Br A with (B, B ) = (A, A ), the coefficient of X A+A in the expansion of X B X B in the QNB is zero. It follows that σ(f g) = σ( B≥ Br A,B ≥ Br A β A,B β A ,B X B X B ) = σ(β A,A β A ,A X A X A ) = σ(σ(f )σ(g)).

2

In the classical setting q = 1, Skandera [START_REF] Skandera | On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations[END_REF] discovered an explicit formula for dual canonical basis elements of A n which involves certain polynomials called immanants. Given a permutation w ∈ S m and an m × m matrix y = (y ij ) 1≤i,j≤m with entries drawn from the set

{x ij | 1 ≤ i, j ≤ n}, define the w-KL immanant of y to be Imm w (y) := v∈Sm Q v,w (1)y 1,v(1) • • • y m,v(m) .
Here Q v,w (q) is the inverse Kazhdan-Lusztig polynomial corresponding to the permutations v and w (see [START_REF] Lusztig | Representations of Coxeter groups and Hecke algebras[END_REF] or [START_REF] Bj | Combinatorics of Coxeter groups[END_REF]). It can be shown that the KL immanant Imm 1 (y) corresponding to the identity permutation 1 ∈ S m is equal to the determinant det(y).

Any (weak) composition α |= m with n parts induces a function [m] → [n], also denoted α, which maps the interval (α 1 + • • • + α i-1 , α 1 + • • • α i ] onto i for all i. We also have the associated parabolic subgroup S α ∼ = S α1 × • • • × S αn of S m
which stabilizes all of the above intervals. Given a pair α, β |= m of compositions of m both having n parts, we define the generalized submatrix x α,β of x to be the m × m matrix satisfying (x α,β ) ij := x α(i),β(j) for all 1 ≤ i, j ≤ m. Let Λ m (α, β) denote the set of Bruhat maximal permutations in the set of double cosets S α \S m /S β . Skandera's work [START_REF] Skandera | On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations[END_REF]Section 2] implies that the dual canonical basis of A n is equal to the set

m≥0 α,β {Imm w (x α,β ) | w ∈ Λ m (α, β)}. (5)
The lack of an elementary description of the inverse KL polynomials is the most difficult part in using Skandera's formula to write down DCB elements.

Returning to the quantum setting,for two subsets

I, J ⊆ [n] with |I| = |J|, the quantum minor ∆ (q) I,J (x) ∈ A (q)
n is the quantum determinant of the submatrix of x with row set I and column set J.

Restricting to the case n = 3, we define the quantum 132-and 213-KL immanants, denoted Imm (q) 132 (x) and Imm (q) 213 (x), to be the elements of A (q) 3 given by Imm (q) 132 (x) = x 11 x 23 x 32 -qx 12 x 23 x 31 -qx 13 x 21 x 32 + q 2 x 13 x 22 x 31 and Imm (q) 213 (x) = x 12 x 21 x 33 -qx 12 x 23 x 31 -qx 13 x 21 x 32 + q 2 x 13 x 22 x 31 . Define quantum cluster and quantum frozen variables to be the polynomials obtained by replacing every minor in the classical quantum or frozen variable definition by its corresponding quantum minor and the classical polynomials Imm 132 (x) and Imm 213 (x) by their quantum counterparts. Define a quantum (extended) cluster to be the set of quantum (frozen and) cluster variables corresponding to polynomials in a classical (extended) cluster.

To define the quantum cluster monomials, fix a total order {z 1 < z 2 < • • • < z 21 } on the union of the quantum cluster and frozen variables. A quantum cluster monomial is any product of the form

z b1 1 • • • z b9 9 ∈ A (q)
3 , where {z 1 < • • • < z 9 } is an ordered quantum extended cluster and the b i are nonnegative integers. It will turn out (Corollary 16) that the choice of total order < only affects the quantum cluster monomials up to a q-shift. Skandera's map φ yields a bijection (also denoted φ) between the set of quantum cluster monomials and Mat 3 (N).

While it is not obvious at this point, the set Z of all quantum cluster monomials will be shown in Corollary 20 to be a Z[q ±1/2 ]-basis for the ring A (q) 3 . This basis will be called the quantum cluster basis (QCB). The main result of this paper (Theorem 33) states that every dual canonical basis element in A (q) 3 is a q-shift of a unique quantum cluster basis element. Setting q = 1, we have that Theorem 33 implies Theorem 1.

Main Results

Let Z be the set of quantum cluster monomials (with respect to some fixed total order < on the set of quantum cluster and frozen variables). In order to prove that every dual canonical basis element of A (q) 3 is a q-shift of a unique element of Z, we will show that Z satisfies the Du-Zhang characterization of the dual canonical basis in Theorem 6 up to q-shift. To do this, we will show that (1) Z is a Z[q ±1/2 ]-basis of the ring A (q) 3 (Corollary 20), (2) given z ∈ Z, z is homogeneous with respect to the N 3 × N 3 -grading of A (q) 3 of homogeneous degree row(φ(z)) × col(φ(z), where the N 3 × N 3 -grading of A (q) 3 was presented before Example 5 and the map φ is as in Section 2 (Observation 9), (3) z is a q-shift of a unique bar invariant element of A (q) 3 (Corollary 18), and (4) the same q-shift of z as in (3) expands in the MQNB as

X(φ(z)) + φ(z)< Br B β φ(z),B (q 1/2 )X(B),
where < Br is Bruhat order and β φ(z),B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ] for all B (Lemma 32).

We begin with a rather benign observation about the expansion of quantum frozen or cluster variables in the MQNB.

Observation 8 Let z ∈ A (q)
3 be a quantum cluster variable or frozen variable and let A = φ(z). The ring element z is homogeneous with respect to the N 3 × N 3 -grading of A (q) 3 and has homogeneous degree row(A)× col(A). Moreover, the expansion of z in the MQNB is of the form

z = X(A) + B> Br A β A,B (q 1/2 )X(B),
where the β A,B are polynomials in q 1/2 Z[q 1/2 ].

Next, we observe that quantum cluster monomials are homogeneous.

Observation 9 Let z ∈ A (q)
3 be a quantum cluster monomial and let A = φ(z). The ring element z is homogeneous with respect to the N 3 × N 3 -grading of A (q) 3 with homogeneous degree row(A)× col(A).

Proof: This is immediate from Observation 8 and the definition of a grading.

2

Our computational work with the ring A (q)

n will be economized by means of a collection of algebra maps. Define maps τ and α on the generators of A (q) n by the formulas τ (x ij ) = x ji and α(x ij ) = x (n-j+1)(n-i+1) . It is routine to check from the Relations 1-4 that τ extends to an involutive Z[q ±1/2 ]-

algebra automorphism τ : A (q) n → A (q)
n and that α extends to an involutive Z[q ±1/2 ]-algebra antiautomorphism α :

A (q) n → A (q)
n . The maps τ and α will be called the transposition and antitransposition maps, respectively, because they act on the matrix x = (x ij ) of generators by transposition and antitransposition. In addition, for any two subsets I, J ⊆ [n], we can form the subalgebra

A (q) n (I, J) of A (q) n generated by {x ij | i ∈ I, j ∈ J}. Writing I = {i 1 < • • • < i r } and J = {j 1 < • • • < j s }, we have a Z[q ±1/2 ]-algebra isomorphism c I,J : A (q) n (I, J) → A (q)
n ([r], [s]) given by c I,J : x ia,j b → x a,b . The map c I,J will be called the compression map corresponding to I and J because it acts on the matrix x of generators by compression into the northwest corner. We first write down how these maps act on the MQNB.

Observation 10 Let A ∈ Mat n (N). We have the following formulas involving the MQNB:

(1) τ (X(A)) = X(A T ) (2) α(X(A)) = X(A T ).
Here (-) T denotes matrix transposition and (-) T denotes matrix antitransposition. Moreover, if the row support of A is contained in I and the column support of A is contained in J for subsets

I, J ⊆ [n], then (3) c I,J (X(A)) = X(C I,J (A)).
Here C I,J (A) is the matrix obtained by compressing the rows I and columns J of A into the northwest corner.

Proof: (3) is trivial. To verify (1) and ( 2), one applies the maps τ and α to X(A) and uses Relations 1-4 to get the desired result.

2

Next, we show that the transposition, antitransposition, and compression maps preserve the triangularity property (2) of Theorem 6. n be a homogeneous element with respect to the N n × N n -grading whose MQNB expansion satisfies the triangularity condition (2) of Theorem 6. The images τ (f ) and α(f ) satisfy this triangularity condition, as well. Moreover, if the row support and column support of the matrices A where X(A) appears in f are contained in subsets I and J of [n], respectively, then c I,J (f ) satisfies this triangularity condition too.

Proof: Apply Observation 10 together with the fact that the maps A → A T , A → A T , and A → C I,J (A) all preserve Bruhat order.

2

We observe that the transposition, antitransposition, and compression maps act in a nice way on the set of quantum cluster and frozen variables.

Observation 12 Let z be a quantum cluster or frozen variable. Retaining notation from Observation 10, α(z) and τ (z) are quantum cluster or frozen variables with φ(α(z)) = φ(z) T and φ(τ (z)) = φ(z) T . Moreover, if the row support of φ(z) is contained in I ⊆ [START_REF] Du | IC bases and quantum linear groups[END_REF] and the column support of φ(z) is contained in J ⊆ [START_REF] Du | IC bases and quantum linear groups[END_REF], then the image of z under the compression map c I,J corresponding to I and J is a quantum cluster or frozen variable whose image under φ is C I,J (φ(z)).

Proof: The proof of this observation is a direct computation. For example, the quantum cluster variable z = ∆

2

The 7 equivalence classes of quantum cluster variables under the maps τ and α are shown in Figure 4. Visually, the map τ swaps diameter colors and the map α reflects across the y-axis and swaps diameter colors. The actions of τ , α, and the compression maps remain well-defined on the level of quantum clusters.

To help us show that the transposition, antitransposition, and compression maps act nicely on the dual canonical basis of A (q) n (Lemma 25), we observe that these maps commute with the bar involution, and therefore preserve the property of bar invariance.

Observation 13

The transposition map τ , the antitransposition map α, and the compression maps c I,J all commute with the bar involution.

Proof: Regarding A (q)
n as a Z-algebra, this can be verified trivially on the generators x ij , q 1/2 , and q -1/2 . 2

Our first step in showing that quantum cluster monomials are q-shifts of bar invariant elements in A (q) 3 is to observe that their constituent quantum cluster or frozen variables are themselves bar invariant.

Observation 14 Every quantum cluster variable or quantum frozen variable is bar invariant.

Proof: The bar invariance of the elements det q (x), ∆

12,12 (x), x 11 , Imm

(q) 132 (x) ∈ A (q)
3 can be verified by direct computation. Use of the maps τ, α :

A (q) 3 → A (q)
3 as well as inverses of the compression maps implies the truth of Observation 14 for all quantum cluster variables and quantum frozen variables by Observation 13.

2

Two ring elements f, g ∈ A (q)

n are said to quasicommute if f g = q a gf for some a ∈ Z. We observe that quantum cluster or frozen variables which appear in the same quantum extended cluster quasicommute with eachother. For example, the quantum cluster variables x 11 and x 22 do not quasicommute, but by inspection never appear in the same quantum extended cluster. This next observation implies that changing the order < on the quantum cluster and frozen variables only affects quantum cluster monomials up to a q-shift (Corollary 16) and will be used together with Lemma 17 to show that quantum cluster monomials are q-shifts of bar invariant elements of A (q) 3 .

Observation 15 Let z and z be a pair of elements of A (q) 3 which appear in the same quantum extended cluster. Then, z and z quasicommute.

Proof: A straightforward, albeit tedious calculation shows that we have the following equalities in the ring A (q) 3 . To prove each equality, we expand both sides and use the relations 1-4 to express these expansions as a linear combination of MQNB elements.

∆ (q) 12,12 (x)∆ (q) 13,23 (x) = q∆ (q) 13,23 (x)∆ (q) 12,12 (x) Imm (q) 132 (x)∆ (q) 13,12 (x) = ∆ (q) 13,12 (x)Imm (q) 132 (x) ∆ (q) 12,12 (x)Imm (q) 132 (x) = q 2 Imm (q) 132 (x)∆ (q) 12,12 (x) ∆ (q) 13,12 (x)∆ (q) 12,13 (x) = ∆ (q)
12,13 (x)∆ (q) 13,12 (x) ∆ (q) 13,12 (x)∆ (q) 13,23 (x) = q∆ (q) 13,23 (x)∆ (q) 13,12 (x)

x 11 x 12 = qx 12 x 11 x 12 x 21 = x 21 x 12 Applying the transposition map τ , the antitransposition map α, and inverses of the compression maps c I,J to both sides of these equalities, we see that any two quantum cluster variables which appear in the same quantum cluster quasicommute. It follows from [14, Lemma 5.1] and Observation 8 that if z is a quantum frozen variable and z is a quantum frozen or cluster variable, then zz = q a z z for some a ∈ Z. 2

The next corollary is immediate from Observation 15 and the fact that A 3 is a unique factorization domain.

Corollary 16 Let < and < be two total orders on the set of quantum cluster and frozen variables. Let Z and Z be the sets of quantum cluster monomials obtained from the orders < and < , respectively. Then, for any element z ∈ Z there exists a unique element z ∈ Z and a unique number a z ∈ Z so that z = q az z .

Proof:

The existence of such an element z ∈ Z comes from rearranging the quantum cluster and frozen factors of z according to the order < and applying Observation 15. Uniqueness comes from setting q = 1 and using the fact that the commutative ring A 3 is a unique factorization domain.

2

Corollary 16 implies that when proving a quantum cluster monomial z is q-triangular, we may write the quantum cluster factors of z in any order we wish. We will make repeated implicit use of this fact in the proofs of Lemmas 27, 29, and 30. Observation 15 is also useful in showing that quantum cluster monomials are q-shifts of bar invariant elements of A (q) 3 . Lemma 17 Let f 1 , . . . , f k be a collection of bar invariant elements of A (q) n . Suppose that for every i < j there is a number c(i, j) ∈ Z so that f i f j = q c(i,j) f j f i . Then, the product

q c f 1 • • • f k is bar invariant, where c = - 1 2 i<j c(i, j).
Proof: Since the bar map is an antiautomorphism, we get that

q c f 1 • • • f k = q -c f k • • • f 1 = q -c f k • • • f 1 = q -c q 2c f 1 • • • f k = q c f 1 • • • f k , as desired. 2
Corollary 18 Every quantum cluster monomial is a q-shift of a unique bar invariant element of A (q)

3 .

Proof: Let z = z b1 1 • • • z b9 9 be a quantum cluster monomial. By Observation 14, we have that z i = z i for 1 ≤ i ≤ 9. By Lemma 17 and Observation 15, we have that z is a q-shift of a bar invariant element of A (q) 3 . If q a z and q b z are bar invariant, it follows that q a z = q a z = q -a z = q -a+b q b z = q -a+2b z, so that a = -a + 2b and a = b.

2

We turn to the verification that the set Z of quantum cluster monomials forms a Z[q ±1/2 ]-basis of the ring A (q) 3 . Our strategy is to show that the transition matrix between Z and the quantum natural basis is upper triangular with unital diagonal elements, with respect to an appropriate ordering of basis elements. (9) . Then, the expansion of z in the quantum natural basis

Lemma 19 Let z = z b1 1 • • • z b9 9 be a quantum cluster monomial. For 1 ≤ r ≤ 9, let A (i) = φ(z i ) ∈ Mat 3 (N) and let A = φ(z), so that A = b 1 A (1) + • • • + b 9 A
{X B | B ∈ Mat 3 (N)} of A (q)
3 has the form

z = q y X A + B> Br A β A,B X B ,
where β A,B ∈ Z[q ±1/2 ] for all B and y = -

3 i=1 1≤k< ≤3 1≤r<s≤9 b r b s ((A (r) ) i (A (s) ) ik + (A (r) ) i (A (s) ) ki ).
Here (-) ij denotes taking the (i, j)-entry of a matrix.

Proof: We adopt the notation of Lemma 7. Observation 8 implies that for 1 ≤ r ≤ 9, the ring element σ(z r ) is defined and is given by σ(z r ) = X A (r) . By Part 2 of Lemma 7, we have that σ(z) is defined and σ(z) = σ(σ(z 1 ) b1 • • • σ(z r ) br ). By Part 1 of Theorem 6 and the fact that matrix addition preserves Bruhat order, we have that the content

C(σ(z)) of σ(z) = σ(σ(z 1 ) b1 • • • σ(z r ) br ) is C(σ(z)) = b 1 A (1) + • • • + b r A (r) = A.
Aside from the coefficient of X A in the QNB expansion of z, this verifies Lemma 19.

We claim that the coefficient of X A in the QNB expansion of z is equal to q y , where y is the number given in the statement of the lemma. Since σ(z) = σ(σ(z 1 ) b1 • • • σ(z r ) br ) = βX A for some β ∈ Z[q ±1/2 ], we have that the coefficient of X A in the QNB expansion of z is equal to the coefficient of X A in the QNB expansion of σ(z 1 ) b1 • • • σ(z r ) br = (X A (1) ) b1 • • • (X A (r) ) br . In order to find the coefficient of X A in the QNB expansion of (X A (1) ) b1 • • • (X A (r) ) br , we apply the relations 1-4 to express (X A (1) ) b1 • • • (X A (r) ) br as a linear combination of QNB elements. An application of the relation 4 to a monomial m in the generators x ij results in m -(q -q -1 )m , where m has the same content as m and m has content which is greater in Bruhat order than the content of m. Since we are only interested in the coefficient of the Bruhat minimal term X A in the QNB expansion of (X A (1) ) b1 • • • (X A (r) ) br , we can replace relation 4 with the relation 6:

x ik x jl = x jl x ik (i < j, k < l) (6)
for the purposes of this straightening. Each application of relations 1 or 2 introduces a factor of q -1 to the coefficient of X A in the QNB expansion of (X A (1) ) b1 • • • (X A (r) ) br . Each application of relations 3 or 6 leaves the coefficient of X A in the QNB expansion of (X A (1) ) b1 • • • (X A (r) ) br unchanged. For any r, we have that the matrix A (r) = φ(z r ) has at most one nonzero entry in any row or column. Therefore, no application of relations 1 or 2 is necessary when expanding (X A (r) ) br in the QNB. Counting the number of times 1 or 2 must be applied to put the terms of (X A (1) ) b1 • • • (X A (r) ) br in lex order using the relations 1, 2, 3, and 6, we get that the coefficient of X A in the QNB expansion of (X A (1) ) b1 • • • (X A (r) ) br is equal to q y , where y is given in the statement of the lemma. 2

While the exact form of the exponent y is not necessary for the proof of the next corollary, it will be used later in the proof of q-triangularity.

Corollary 20 The set of quantum cluster monomials is a Z[q ±1/2 ]-basis of A (q) 3 .

Proof: Index a quantum cluster monomial z with the matrix φ(z) ∈ Mat 3 (N). Consider the transition matrix between the set of quantum cluster monomials and the quantum natural basis, where basis elements are ordered by an arbitrary linear extension of Bruhat order on Mat 3 (N). By Lemma 19, this matrix is upper triangular with diagonal entries which are units in Z[q ±1/2 ].

2

Our next task is to prove that every quantum cluster monomial is q-triangular. This result will be proven in Lemma 31 and we build up to it with a sequence of weaker results. We start by writing down the expansion det q (x)X(A) in the MQNB for an arbitrary matrix A ∈ Mat 3 (N).

Observation 21 Let A =   a b c d e f g h i   ∈ Mat 3 (N). In the quantum ring A (q) 3 we have the MQNB expansion det q (x)X(A) = β 1 X   a + 1 b c d e + 1 f g h i + 1   +β 2 X   a b + 1 c d + 1 e f g h i + 1   + β 3 X   a + 1 b c d e f + 1 g h + 1 i   +β 4 X   a b + 1 c d e f + 1 g + 1 h i   + β 5 X   a b c + 1 d + 1 e f g h + 1 i   +β 6 X   a b c + 1 d e + 1 f g + 1 h i   + β 7 X   a b + 1 c d + 1 e -1 f + 1 g h + 1 i   ,
where the coefficients β 1 , . . . , β 7 are given by

β 1 = 1 β 2 = -q a+e+1 β 3 = -q e+i+1 β 4 = q a+d+h+i+2 β 5 = q a+b+f +i+2 β 6 = -q a+b+d+f +h+i+3 β 7 = q a+2e+i+1 (1 -q -2e )
This observation is proven by direct computation in the quantum ring A (q) 3 using Relations 1-4. Since the quantum determinant is central in A (q) 3 , we would have obtained the same expansion if we had multiplied X(A) on the right by det q (x). Except for the powers of q that appear, the first six terms in this expansion are expected from the classical ring computation in A 3 of multiplying the determinant by a monomial. Since the coefficient β 7 vanishes at q = 1, the more exotic seventh term in this expansion vanishes in the classical setting. It may be interesting to compute the expansion of det q (x)X(A) in the MQNB for arbitrary n > 0, where A ∈ Mat n (N). Observation 21 implies the following about the expansion of det q (x) k in the MQNB.

Lemma 22 For k ≥ 0, let A be the matrix

  k 0 0 0 0 k 0 k 0   . If B ∈ Mat 3 (N)
is any matrix with row and column vector given by row(B) = col(B) = (k, k, k), then B ≥ Br A if and only if the (3,3)-entry of B is equal to zero. The coefficient of X(A) in the MQNB expansion of det q (x) k is equal to

(-q) k . If B > Br A, the coefficient of X(B) in the MQNB expansion of det q (x) k is a polynomial in q k+1 Z[q].
Proof: The statement regarding Bruhat order comparability follows directly from the definition of the Bruhat order on Mat 3 (N). The facts about the coefficients of the MQNB expansion of (det q (x)) k can be proven using Observation 21 and induction on k together with the fact that B ≥ Br A if and only if

row(B) = col(B) = (k, k, k) and (B) 3,3 = 0. 2
We use Observation 21 to show that powers of the quantum ring elements Imm (q) 132 (x) and Imm (q) 213 (x) are q-triangular.

Lemma 23 For any k ≥ 0, the quantum ring elements Imm (q) 132 (x) k and Imm (q) 213 (x) k are q-triangular.

Proof: Let us first check that Imm (q) 132 (x) k is q-triangular. By Lemma 19, the expansion of Imm (q) 132 (x) k in the MQNB has unique Bruhat minimal term X(A), where A = φ(Imm

(q) 132 (x) k ) =   k 0 0 0 0 k 0 k 0   .
We have the quantum ring identity

Imm (q) 132 (x) = q -1 (∆ (q) 12,12 (x)x 33 -det q (x)).
From the centrality of the quantum determinant and the binomial formula we get that for k > 0

Imm (q) 132 (x) k = q -k k m=0 k m (-1) m det q (x) m (∆ (q) 12,12 (x)x 33 ) k-m . ( 7
)
We consider the expansion of the left and right hand sides of Equation 7 in the MQNB. Since Imm (q) 132 (x) contains no terms involving x 33 , it is easy to see from the relations 1-4 that the expansion of the left hand side of Equation 7 in the MQNB contains no terms involving x 33 .

Consider now the right hand side of Equation 7. We expand each term in the alternating sum in the MQNB separately. If m < k, the term det q (x) m (∆ (q) 12,12 (x)x 33 ) k-m ends in x 33 . The relations 1-4 imply that every term in the expansion of det q (x) m (∆ (q) 12,12 (x)x 33 ) k-m in the MQNB contains at least one power of x 33 , as well. Since no term involving x 33 appears on the left hand side of Equation 7, we conclude that the terms in the sum on the right hand side of Equation 7 corresponding to m < k must all be cancelled in the alternating sum. Therefore, the only surviving terms in the MQNB expansion of the sum on the right hand side of Equation 7arise from the summand (-det q (x)) k .

Finally, consider the expansion of det q (x) k in the MQNB. By Lemma 22, the coefficient of X(A) in this expansion is (-q) k and the coefficient of X(B) in this expansion for any matrix B with (3, 3)-entry equal to zero involves only powers q of q with > k. Since the MQNB expansion of the left hand side of Equation 7 contains no terms involving x 33 , any terms X(B) appearing in the MQNB expansion of det q (x) k with the (3, 3)-entry of B not equal to zero must be cancelled in the alternating sum on the right hand side. By the Bruhat comparability statement in Lemma 22, we conclude that there are polynomials β A,B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ] so that

Imm (q) 132 (x) k = X(A) + B> Br A β A,B (q 1/2 )X(B).
Therefore, Imm (q) 132 (x) k is q-triangular. We have that α(Imm

(q) 132 (x) k ) = Imm (q)
213 (x) k . By Observation 11, the q-triangularity of Imm (q) 132 (x) k implies the q-triangularity of Imm

(q) 213 (x) k . 2
The next result is due to Zhang and implies that the dual canonical basis of A (q)

3 is closed under multiplication by quantum frozen variables, up to q-shift. This is helpful because by Theorem 6, any q-shift of a dual canonical basis element is q-triangular. Zhang's proof uses the characterization of the dual canonical basis given of A (q) n given in Theorem 6. Theorem 24 ([14, Theorem 5.2]) For -n < k < n, let E k be the n × n matrix whose (i, j)-entry is the Kronecker delta δ i+k,j . Let I k and J k be the row and column support of the matrix E k , respectively. We have that the dual canonical basis element b(E k ) ∈ A (q) n is given by ∆ (q)

I k ,J k (x). If A ∈ Mat n (N), we have that b(A)∆ (q) I k ,J k (x) ∈ A (q)
n is a q-shift of the dual canonical basis element b(A + E k ). Our work in proving the q-triangularity of quantum cluster monomials will be reduced by noticing that transposition, antitransposition, and compression maps are well-behaved with respect to the dual canonical basis.

Lemma 25 Let A ∈ Mat n (N). In the notation of Observation 10, the following identities involving dual canonical basis elements hold.

(1) τ (b(A)) = b(A T ) (2) α(b(A)) = b(A T ). Moreover, if the row support of the matrix A is contained in I ⊆ [n] and the column support of A is contained in J ⊆ [n], we have that (3) c I,J (b(A)) = b(C I,J (A)).
Finally, if the row support of the matrix A is contained in [r] and the column support of A is contained in

, and (4) follow the same line of reasoning as in Zhang's proof of [START_REF] Bj | Combinatorics of Coxeter groups[END_REF].

Let B = {b(A) | A ∈ Mat n (N)} denote the dual canonical basis of A (q) n . Since α : A (q) n → A (q) n is a Z[q ±1/2 ]-linear involution, the set α(B) := {α(b(A)) | A ∈ Mat n (N)} is a Z[q ±1/2 ]-linear basis of A (q)
n . By Observation 13 and Theorem 6, the ring element α(b(A)) ∈ A (q) n is bar invariant for any matrix A ∈ Mat n (N). Since b(A) is homogeneous with respect to the N n × N n -grading of A (q) n with homogeneous degree row(A) × col(A), we have that α(b(A)) is homogeneous with respect to this grading with degree row(A T ) × col(A T ). By Observations 10 and 11 as well as Theorem 6, we have that α(b(A)) satisfies the triangularity condition (2) of Theorem 6 with σ(α(b(A))) = X(A T ). The uniqueness statement of Theorem 6 implies that B = α(B). Since σ(α(b(A))) = X(A T ) we also have that α(b(A)) = b(A T ). This proves [START_REF] Énien | Invariant theory, Young bitableaux and combinatorics[END_REF].

For the proof of (3), for any two subsets

K, L ⊆ [n], let Mat n (N, K, L) denote the set of matrices A ∈ Mat n (N) such that (A) ij = 0 unless i ∈ K and j ∈ L. Suppose that |I| = r and |J| = s. Define a subset B ⊂ A (q) n by B = (B {b(A) | A ∈ Mat n (N, [r], [s])}) ∪ {c I,J (b(A)) | A ∈ Mat n (N, I, J)}.
For any matrix A ∈ Mat n (N, I, J), by Observations 10 and 11 and Theorem 6 we have that the MQNB expansion of c I,J (b(A)) satisfies the triangularity condition (2) of Theorem 6 with σ(c I,J (b(A))) = X(C I,J (A)). It follows that the transition matrix from B to the MQNB is unitriangular whenever basis elements are ordered in a linear extension of Bruhat order, and therefore B is a Z[q ±1/2 ]-basis of A (q) n . By Observation 13 and Theorem 6, every element of B is bar invariant. The uniqueness statement of Theorem 6 implies that B = B . The fact that σ(c I,J (b(A))) = X(C I,J (A)) implies that c I,J (b(A)) = b(C I,J (A)), which proves (3). The proof of ( 4) is similar to the proof of (3) and is left to the reader. 2

We note also that the inclusion of the dual canonical basis of

A (q) m into A (q) n for m < n is a subset of the dual canonical basis of A (q) n .
Lemma 26 Suppose m < n and A ∈ Mat m (N) is a matrix with associated dual canonical basis element b(A) ∈ A (q) m . Let A ∈ Mat n (N) be the matrix obtained by embedding A in the northwest corner of an n × n matrix of zeroes. Then, considered as an element of A (q) n , the ring element b(A) is in the dual canonical basis of A

(q) n . Define a subset B ⊂ A (q) n by B = (B {b(A) | A ∈ ι (Mat m (N))}) ∪ ι(B).
(ι (A)). It follows that B is a Z[q ±1/2 ]-basis of A (q)
n . The bar invariance of every element of B together with the uniqueness statement of Theorem 6 implies that

B = B . The equation σ(ι(b(A)) = X(ι (A)) implies that ι(b(A)) = b(ι (A)), as desired. 2
We show next that any power of a quantum matrix minor is in the dual canonical basis of A

3 , and hence q-triangular. Combined with Lemma 23, this shows that any power of a single quantum frozen or cluster variable is q-triangular.

Lemma 27 Let I, J ⊆ [START_REF] Du | IC bases and quantum linear groups[END_REF] with |I| = |J| and let k ≥ 0. The quantum ring element (∆ (q) IJ (x)) k is a q-shift of a dual canonical basis element of A (q) 3 , and hence q-triangular by Theorem 6.

Proof: Let n = |I| = |J|. By Theorem 24, we have that ∆ (q)

[n],[n] (x) k is a q-shift of a dual canonical basis element of A (q) n . By Lemma 25, ∆

[n],[n] (x) k remains a q-shift of a dual canonical basis element of A (q) 3 . By Part 4 of Lemma 25, we have that ∆ (q) I,J (x) k is a q-shift of a dual canonical basis element of A (q) 3 . 2 Our next result will be our first showing that certain quantum cluster monomials which are not powers of a single quantum cluster or frozen variable are q-triangular. We will find it convenient to consider quantum cluster monomials containing only factors arising from a proper subset of the quantum cluster variables. Define a reduced cluster to be a subset of A (q) 3 of the form C {x 11 , ∆ (q) 12,12 (x), ∆ (q) 23,23 (x), x 33 }, where C is a quantum cluster. A glance at Figure 4 shows that a reduced cluster is obtained from a quantum cluster by deleting quantum cluster variables belonging to a four-element set stabilized by the action of α and τ . On the level of decorated octagons, reduced clusters are obtained from clusters by deleting pairs of centrally symmetric nondiameters which cut out triangles on the boundary of the octagon. The action of the Klein 4-group generated by τ and α breaks the set of reduced clusters up into ten equivalence classes.

A decorated octagon corresponding to a representative from each equivalence class is shown in Figure 4. Any cluster could be obtained from an equivalence class in Figure 4 by applying the maps α and τ and by adding pairs of centrally symmetric nondiameters which cut out triangles on the boundary of the octagon.

Define a reduced cluster monomial to be a product of the form

z b1 1 • • • z b ∈ A (q)
3 , where {z 1 < • • • < z } is a reduced cluster with total order induced from the order on quantum cluster and frozen variables. Observe that in particular reduced cluster monomials do not contain any frozen factors.

Lemma 28 Every reduced cluster monomial is q-triangular.

Proof: We will show first that a reduced cluster monomial arising from any of the ten reduced clusters whose decorated octagons are shown in Figure 4 is q-triangular. While there are ten reduced clusters to consider, observe that the decorations in the bottom two decorated octagons in Figure 4 occur as subsets of the decorations in the decorated octagon in the top row, second from the left. We therefore show that a reduced cluster monomial arising from any of the eight reduced clusters whose decorated octagons are shown in the first two rows of Figure 4 are q-triangular. This gives rise to eight cases, each labeled by a reduced cluster.

Case 1. {x 12 , x 21 , x 22 }, The monomials x j 12 x k 21 x 22 are obviously q-triangular.

Case 2. {∆ (q) 13,12 (x), ∆

13,23 (x), x 12 , x 32 } We must show that form any j, k, , m ≥ 0, the polynomial x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 is q-triangular. We build up to this statement in several steps.

By Lemma 27, we have that ∆ (q) 12,12 (x) k is a q-shift of a dual canonical basis element of A (q)

3 . By Theorem 24, we have that ∆ (q) 12,12 (x) k ∆ (q) 12,23 (x) is a q-shift of a dual canonical basis element of A (q) 3 . By Part 4 of Lemma 25, we have that ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) is a q-shift of a dual canonical basis element of A (q) 3 , and hence q-triangular by Theorem 6. Our next claim is that the set of ring elements of the form x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 which are q-triangular is closed under left multiplication by x 12 . A direct calculation yields the formula:

x 12 X   a b c d e f g h i   = q 1 2 (-a+c+e+h) X   a b + 1 c d e f g h i   , (8)
By Lemma 19, the matrix φ(x j 12 ∆ (q) 13,12 (x

) k ∆ (q) 13,23 (x) x m 32 ) =   k j + 0 0 0 m 0 k   ∈ Mat 3 (N)
is the unique Bruhat minimal matrix in the set of matrices A ∈ Mat 3 (N) such that X(A) appears with nonzero coefficient in the MQNB expansion of x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 . By Observation 9, the ring element

x j 12 ∆ (q) 13,12 (x) k ∆ (q)
13,23 (x) x m 32 is homogeneous with respect to the N 3 × N 3 -grading on A (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 is q-triangular. To show that x (j+1) 12

∆ (q) 13,12 (x) k ∆ (q)
13,23 (x) x m 32 is also q-triangular, by Equation 8 it is enough to show that By homogeneity we have the chain of (in)equalities:

1 2 (-a + c + e + h) - 1 2 (-k + k) = 1 2 (-a + c + j + + k -b) = c ≥ 0.
Therefore, the set of q-triangular cluster monomials of the form x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 is closed under left multiplication by x 12 .

The argument that the set of cluster monomials of the form x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 is closed under right multiplication by x 32 is similar. A direct calculation shows that

X   a b c d e f g h i   x 32 = q 1 2 (b+e+g-i) X   a b c d e f g h + 1 i   . (9)
Suppose that x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x m 32 is q-triangular and assume that X

  a b c d e f g h i   appears with nonzero coefficient in the MQNB expansion of x j 12 ∆ (q) 13,12 (x) k ∆ (q)
13,23 (x) x m 32 . By Equation 9, to show that

x j 12 ∆ (q) 13,12 (x) k ∆ (q) 13,23 (x) x (m+1) 32
is q-triangular it is enough to show that 1 2 (b+e+g-i)-1 2 (j+ -) ≥ 0. A similar homogeneity argument yields the equalities b + e + h = j + + k and k + = g + h + i, which gives rise to the chain of (in)equalities:

1 2 (b + e + g -i) - 1 2 (j + -) = 1 2 (j + + k -h + g -i) - 1 2 j = g ≥ 0.
Case 3. {∆ (q) 13,13 (x), ∆

13,23 (x), ∆

13,12 (x)} We must show that for any j, k, ≥ 0, the ring element ∆ (q) 13,13 (x) j ∆ (q) 13,23 (x) k ∆ (q) 13,12 (x) is q-triangular. We build up to this statement in several steps.

By Lemma 27, the quantum minor power ∆ (q) 12,13 (x) j is a q-shift of a dual canonical basis element. By Theorem 24, we can right multiply this q-shift of a dual canonical basis element by powers of the quantum frozen variable ∆ (q) 12,23 (x) to get that ∆ (q) 12,13 (x) j ∆ (q) 12,23 (x) k is a q-shift of a dual canonical basis element. Next, observe that ∆ (q) 12,13 (x) j ∆ (q) 12,23 (x) k is the image of ∆ (q) 23,13 (x) j ∆ (q) 23,23 (x) k under the compression map c 23,123 . Part 4 of Lemma 25 implies that ∆ (q) 23,13 (x) j ∆ (q) 23,23 (x) k is a q-shift of a dual canonical basis element. Again applying Theorem 24, we can right multiply by powers of the quantum froxen variable ∆ (q) 23,12 (x) to get that ∆ (q) 23,13 (x) j ∆ (q) 23,23 (x) j ∆ (q) 23,12 (x) is a q-shift of a dual canonical basis element. Since ∆ (q) 13,13 (x) j ∆ (q) 13,23 (x) k ∆ (q) 13,12 (x) is the image of ∆ 13,13 (x) j ∆ (q) 13,23 (x) k ∆ (q) 13,12 (x) is a q-shift of a dual canonical basis element and therefore q-triangular by Theorem 6. Case 4. {Imm (q) 132 (x), ∆ (q) 13,12 (x), x 32 } We must show that for any j, k, ≥ 0, the polynomial ∆ (q) 13,12 (x) j Imm (q) 132 (x) k x 32 is q-triangular. By Lemma 23, Imm (q) 132 (x) k is q-triangular. We claim that the set of ring elements of the form ∆ (q) 13,12 (x) j Imm (q) 132 (x) k x 32 which are q-triangular is closed under left multiplication by ∆ (q) 13,12 (x). A direct calculation yields the following MQNB expansion:

∆ (q) 13,12 (x)X   a b c d e f g h i   = q 1 2 (c+d-e+i) X   a + 1 b c d e f g h + 1 i   -q 1 2 (2a+c-d+e+2h+i+2) X   a b + 1 c d e f g + 1 h i   (10)
-(1 -q -2d )q 1 2 (c+3d-e+2h+i) X   a + 1 b c d -1 e + 1 f g + 1 h i   .
By Lemma 19, the matrix φ(∆

(q) 13,12 (x) j Imm (q) 132 (x) k x 32 ) =   j + k 0 0 0 0 k 0 j + k + 0   ∈ Mat 3 (N)
is the unique Bruhat minimal matrix in the set of matrices A ∈ Mat 3 (N) such that X(A) appears with nonzero coefficient in the MQNB expansion of ∆ (q) 13,12 (x) j Imm 13,12 (x) j Imm (q) 132 (x) k x 32 . Assume that ∆ (q) 13,12 (x) j Imm (q) 132 (x) k x 32 is q-triangular. As in Case 2, Observation 9 implies that we have the equalities c + f + i = k and d + e + f = k. Therefore, we have the (in)equalities:

1 2 (c + d -e + i) = 1 2 (d -e -f + k) = d ≥ 0, 1 2 (2a + c -d + e + 2h + i + 2) = 1 2 (2a -d + e -f + 2h + k + 2) = a + e + h + 1 > 0, 1 2 (c -d -e + 2h + i) = 1 2 (-d -e -f + 2h + k) = h ≥ 0.
Examining the exponents in Equation 10, it follows that ∆ (q) 13,12 (x) (j+1) Imm (q) 132 (x) k x 32 is q-triangular. It follows that the set of quantum cluster monomials of the form ∆ (q) 13,12 (x) j Imm (q) 132 (x) k x 32 which are q-triangular is closed under left multiplication by ∆ (q) 13,12 (x). The argument that this set is also closed under right multiplication by x 32 is similar and is left to the reader. The relevant MQNB expansion for this argument which plays the role of Equations 8-10 can be obtained by applying τ to both sides of Equation 9. Case 5. {Imm (q) 132 (x), x 32 , x 23 } We must show that all ring elements of the form Imm (q) 132 (x) j x k 32 x 23 are q-triangular. It follows from Case 4 that all ring elements of the form Imm (q) 132 (x) j x k 32 are q-triangular. The argument that all ring elements of the form Imm (q) 132 (x) j x k 32 x 23 are q-triangular is left to the reader. The relevant MQNB expansion for this argument can be obtained by applying τ to both sides of Equation 9.

Case 6. {Imm

(q) 132 (x), ∆ (q)
13,12 (x), ∆

12,13 (x)} We must show that for any j, k, ≥ 0, the polynomial ∆ (q) 12,13 (x) j ∆ (q) 13,12 (x) k Imm (q) 132 (x) is q-triangular. By Case 4 and Observation 15, the ring element ∆ (q) 13,12 (x) k Imm (q) 132 (x) is q-triangular for all ≥ 0. The argument that the set of q-triangular ring elements of the form ∆ (q) 12,13 (x) j ∆ (q) 13,12 (x) k Imm (q) 132 (x) is closed under left multiplication by ∆ (q) 12,13 (x) is similar to the argument in Case 4 and is left to the reader. The relevant MQNB expansion for this argument can be obtained by applying τ to both sides of Equation 10.

Case 7. {x 12 , x 22 , x 32 } The monomials x j 12 x k 22 x 32 are clearly q-triangular.

Case 8. {∆ (q) 13,12 (x), ∆

12,13 (x), ∆ (q) 13,13 (x)} We must show that all ring elements of the form ∆ (q) 13,12 (x) j ∆ (q) 12,13 (x) k ∆ (q) 13,13 (x) are q-triangular. By Lemma 27, the ring element ∆ (q) 13,23 (x) is a q-shift of a dual canonical basis element for all ≥ 0. By Theorem 24, we can multiply by the quantum frozen variable ∆ (q) 12,23 (x) k to get that ∆ (q) 12,23 (x) k ∆ (q) 13,23 (x) is a q-shift of a dual canonical basis element. Observe that this latter ring element is the image of ∆ (q) 12,13 (x) k ∆ (q) 13,13 (x) under the composition c -1 123,13 • c 123,23 , so Parts 3 and 4 of Lemma 25 imply that ∆ (q) 12,13 (x) k ∆ (q) 13,13 (x) is a q-shift of a dual canonical basis element and q-triangular by Theorem 6. To complete the proof of Case 8, we must show that the set of q-triangular ring elements of the form ∆ (q) 13,12 (x) j ∆ (q) 12,13 (x) k ∆ (q) 13,13 (x) is closed under left multiplication by the quantum cluster variable ∆ (q) 13,12 (x). The argument for this case uses the MQNB expansion of ∆ (q) 13,12 (x)X(A) for A ∈ Mat 3 (N) found in the proof of Case 4 and a similar argument involving homogeneity and the φ function to show that the required exponents are nonnegative. We leave details of this verificaiton to the reader. Completion of the proof of Lemma 28. By Cases 1-8, we have that any reduced cluster monomial arising from one of the reduced clusters in Figure 4 is q-triangular. Since the reduced clusters in Figure 4 are a compete set of representatives from the equivalence classes of reduced clusters under the action of α and τ , by Observations 11 and 15 we conclude that every reduced cluster monomial is q-triangular. 2

The next result shows that the property of being q-triangular is preserved under multiplication on the appropriate side by the elements which are removed from quantum clusters in the definition of reduced clusters.

Lemma 29 Let f ∈ A (q) 3 be q-triangular. Then, the four ring elements x 11 f, ∆ (q) 12,12 (x)f, f ∆ (q) 23,23 (x), and f x 33 are q-triangular.

Proof: Assume that f ∈ A (q) 3 is q-triangular. We begin by showing that x 11 f is also q-triangular. A direct computation shows that we have the following MQNB expansion in the ring A We now show that ∆ (q) 12,12 (x)f is q-triangular. A direct computation shows that we have the following equation involving the MQNB of A 12,12 (x)f is q-triangular, it is enough to show that c + f + g + h ≤ c + f + g + h and that c + f + g + h < 2a + c + 2e + f + g + h + 2. The first inequality follows from the definition of Bruhat order and the fact that A ≤ Br B. The second inequality follows from the first inequality.

We have that α(x 11 f ) = α(f )x 33 and α(∆ (q) 12,12 (x)f ) = α(f )∆ (q) 23,23 (x). Therefore, by applying Observation 11 and replacing f with α(f ), we get that the expressions f x 33 and f ∆ (q) 23,23 (x) are qtriangular.

2

We prove that the conclusion of Lemma 28 holds for quantum cluster monomials with no frozen factors.

Lemma 30 Every quantum cluster monomial z b1 1 • • • z b4 4 which contains no frozen factors is q-triangular.

Proof: By Observation 15 and the definition of a reduced cluster monomial, any quantum cluster monomial with no frozen factors can be obtained up to q-shift by multiplying a reduced cluster monomial by powers of x 11 or ∆

Fig. 1 :

 1 Fig. 1: Cluster variables in Z[x11, . . . , x33]

Fig. 2 :

 2 Fig. 2: Four centrally symmetric colored triangulations corresponding to clusters

n

  with degree row(A) × col(A) and the b(A) satisfy (1) (bar invariance) b(A) = b(A) for all A ∈ Mat n (N), and (2) (q-triangularity) for all A ∈ Mat n (N), the basis element b(A) expands in the MQNB as b

Fig. 3 :

 3 Fig. 3: Equivalence classes of cluster variables under α and τ



  , which has row support {2, 3} and column support {1, 3}.The image of z under the compression map c 23,13 is y = ∆ (q) 12,12 (x), which satisfies φ(y)

  [s] for r, s ≤ n and if |I| = r and |J| = s for I, J ⊆ [n], we have that (4) c -1 I,J (b(A)) = b(C -1 I,J (A)), where c -1 I,J is the inverse of the compression map c I,J and C -1 I,J (A) is the matrix obtained by writing the first r rows and the first s columns of A in rows I and columns of J, preserving the relative position of entries in these rows and columns. Proof: The fact that τ (b(A)) = b(A T ) is due to Zhang [14, Corollary 3.4]. The proofs of statements (2),

nn

  and we have b(A) = b(A ). Proof: We use the line of reasoning of the proof of Lemma 25. Let ι : A be the inclusion map and let ι : Mat m (N) → Mat n (N) denote the map A → A obtained by embedding in the northwest corner of a matrix of zeroes. Let B = {b(A) | A ∈ Mat m (N)} denote the dual canonical basis of A (q) m and let B = {b(A) | A ∈ Mat n (N)} denote the dual canonical basis of A

Fig. 4 :

 4 Fig. 4: The ten equivalence classes of reduced clusters



  appears with nonzero coefficient in the MQNB expansion of x j 12 ∆ (x) x m we have the row and column sum equalities a + b + c = j + k + and b + e + h = j + k + . Suppose that x j 12 ∆

1 2 (

 2 -a + c + e + h) -1 2 (-k + k) ≥ 0 whenever X appears with nonzero coefficient in the MQNB expansion of x j 12 ∆

  • c 23,123 , Parts 3 and 4 of Lemma 25 imply that ∆ (q)

  coefficient in the MQNB expansion of ∆ (q)



  unique Bruhat minimal matrix A ∈ Mat 3 (N) such that X(A) appears in the MQNB expansion of f is A = the definition of the Bruhat order and Equation11, we have that is the unique Bruhat minimal matrix such that X(A) appears in the MQNB expansion of x 11 f . appears in the MQNB expansion of f . To show that x 11 f is qtriangular, by Equation11it is enough to show that b + c + d + g ≤ b + c + d + g. This inequality follows from the definition of Bruhat order and the fact that A ≤ Br B.



  By the definition of the Bruhat order and Equation12, we have that such that X(A) appears in the MQNB expansion of ∆ appears in the MQNB expansion of f . To show that ∆ (q)

  (x) on the left or by powers of x 33 or ∆ (q) 23,23 (x) on the right. Lemma 29 states

Acknowledgments

The author is grateful to Sergey Fomin, Gregg Musiker, Vic Reiner, and Mark Skandera for helpful conversations. The author would also like to thank an anonymous referee of their helpful comments.

that the set of q-triangular elements of A (q) 3 is closed under left multiplication by x 11 or ∆ (q) 12,12 (x) and right multiplication by x 33 or ∆ (q) 23,23 (x). By Lemma 28, any reduced cluster monomial is q-triangular. We conclude that every quantum cluster monomial which contains no frozen factors is q-triangular.

2

Finally, we prove that every quantum cluster monomial is q-triangular.

Lemma 31 Every quantum cluster monomial z b1 1 • • • z b9 9 is q-triangular.

By Lemma 19 we know that z b1 1 • • • z b9 9 has, up to q-shift, a MQNB expansion of the form

where the β A,B are in the Laurent polynomial ring Z[q ±1/2 ]. We need only show that the β A,B in fact lie in the subset q 1/2 Z[q 1/2 ] of this ring.

In the proof of Theorem 5.2 in [START_REF] Zhang | On dual canonical bases[END_REF], it is shown that if

3 is a quantum frozen variable, we have that

where c is a constant that depends only on row(A) and col(A) and not on z and < lex is lex order on matrices and β A ,B (q Let z be a quantum cluster monomial. By Corollary 18, a unique q-shift of z is bar invariant. By Lemma 30, an a priori different q-shift of z has a MQNB expansion which satisfies the triangularity condition (2) of Theorem 6. We show that these two q-shifts are in fact the same.

Lemma 32 Let z be a quantum cluster monomial with A = φ(z) ∈ Mat 3 (N) and suppose that q d z is bar invariant. Then, the ring element q d z has a MQNB expansion of the form (9) . Let (-) ij denote taking the (i, j)-entry of a matrix. Additionally, for any 1 ≤ r, s ≤ 4, define a number Γ(r, s) by

By Observation 15, for all 1 ≤ r < s ≤ n, there exists an integer c(r, s) such that z r z s = q c(r,s) z s z r . By Observation 14 and Lemma 17, we have that

By the uniqueness statement in Corollary 18, we have that

To see this, we start with the relation z r z s = q c(r,s) z s z r . By Lemma 19, the matrix A (r) + A (s) is the unique Bruhat minimal matrix among the set of matrices B such that X(B) appears with nonzero coefficient in the MQNB expansion of z r z s or z s z r . By Part 2 of Lemma 7, we have that σ(z r z s ) = σ(σ(z r )σ(z s )) and σ(z s z r ) = σ(σ(z s )σ(z r )). Therefore, we have that the coefficient of

. Equation 17follows from a counting argument similar to the counting argument used to prove the value of y in Lemma 19. Combining Equations 16 and 17 with the fact that d = d yields

Lemma 19 implies that the quantum natural basis expansion of z has the form

where

Recall that for any B ∈ Mat 3 (N), the quantum natural basis element X B and the MQNB element X(B) are related by X(B) = q e(B) X B , where the number e(B) is given by e(B) = - (9) , where

By Lemma 31, we have that q d z = X(A)+ A< Br B β A,B (q 1/2 )X(B), where β A,B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ].

To complete the proof we need only show that d = d . This is routine to check using Equations 18-21. 2

The cluster and dual canonical bases of Z[x 11 , . . . , x 33 ] are equal 123 Theorem 33 Every dual canonical basis element of A (q)

3 is a q-shift of a unique quantum cluster basis element of A (q) 3 .

Proof: Let Z be the set of quantum cluster monomials in A (q) 3 . We show that Z satisfies the conditions of the Du-Zhang characterization of the dual canonical basis in Theorem 6, up to q-shift.

By Corollary 20, the set Z is a Z[q ±1/2 ]-basis of the ring A (q)

3 . By Corollary 18, given z ∈ Z there exists a unique number c z so that q cz z is bar invariant. By Lemma 32, the ring element q cz z also has MQNB expansion

where β A,B (q 1/2 ) ∈ q 1/2 Z[q 1/2 ]. The fact that q cz z has this MQNB expansion implies that q cz z is homogeneous with respect to the N 3 × N 3 -grading with homogeneous degree row(A) × col(A). This latter fact is also a consequence of Observation 9. By Theorem 6 we conclude that the set {q cz z | z ∈ Z} is equal to the dual canonical basis of A (q)

3 . 2

Future Directions

In this paper we have proven that the dual canonical basis and the cluster monomial basis of the classical polynomial ring A 3 are equal by showing that they have quantizations which differ by a q-shift. In doing so, we discovered how DCB elements for A 3 and A

3 decompose into irreducibles and found an easy way to write down any DCB element of these rings up to a q-shift: choose a decorated octagon and write down some monomial in the elements of the related extended (quantum) cluster. It is natural to ask how much of this can be extended to rings A n and A (q) n for n > 3. It turns out that there are obstructions to finding such results from both the theory of cluster monomial bases and dual canonical bases.

For n > 3 there is a known cluster algebra structure on a subalgebra of A n which gives rise to a linearly independent set of cluster monomials. Unfortunately, these cluster monomials do not span A n for n > 3. Moreover, for n > 3 this cluster algebra is of infinite type, i.e., it has infinitely many clusters. Since these clusters are not given at the outset but rather are determined by a 'mutation' procedure starting with some initial cluster and 'mutation matrix' (see [START_REF] Fomin | Cluster algebras I: Foundations[END_REF]), this would seem to make the cluster monomials in these algebras difficult to work with.

Leaving aside the present lack of a cluster algebra structure on A n , one can still ask how dual canonical basis elements of A n and its quantization A (q) n factor. By Theorem 33 and the fact that quantum cluster monomials are arbitrary products of the ring elements in some quantum extended cluster, we have the following result in A (q) 3 .

Corollary 34 Let b be any element in the dual canonical basis of A (q) 3 . Then, a q-shift of b k is in the dual canonical basis of A (q) 3 for any k ≥ 0. For n > 5, Leclerc [START_REF] Leclerc | Imaginary vectors in the dual canonical basis of u q (n)[END_REF] has shown that there exist elements b of the DCB of A (q) n such that b 2 is not a q-shift of a DCB element of A (q) n (so-called imaginary vectors). The author does not know whether imaginary vectors exist in the DCB of A (q) n for n = 4, 5. In light of the construction of cluster monomials, Leclerc's result is troubling if one wants to find a cluster-style interpretation of the factorization of all of the DCB elements of A (q) n for n > 5.


Milan Bradonjić

Tobias Müller
email: tobias@cwi.nl.

Allon G Percus
email: allon.percus@cgu.edu.

Coloring Geographical Threshold Graphs

Keywords: Geographical threshold graphs, random geometric graphs, chromatic number, coloring algorithm

We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e.g., wireless networks, the Internet, etc.) need to be studied by using a "richer" stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: 𝜒 = ln 𝑛 ln ln 𝑛 (1 + 𝑜(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within 𝐶 ln 𝑛/(ln ln 𝑛) 2 , and specify the constant 𝐶.

Introduction

Numerous approaches have been proposed in recent years to study the structure of large real-world technological and social networks, and to optimize processes on these networks. A particularly fertile approach has been to consider the network as an instance of an ensemble, arising from a suitable random generative model. One straightforward example is the random geometric graph (RGG) model, where nodes are placed at random in a Euclidean space and edges are placed between any two nodes within a threshold distance. This has the advantage of describing many aspects of systems such as sensor networks, while avoiding unnecessary detail. Even though geometric correlations in RGGs complicate the probabilistic analysis of the model, recent work has clarified many of its structural properties including threshold behavior [START_REF] Penrose | Random Geometric Graphs[END_REF]; [START_REF] Gupta | Critical power for asymptotic connectivity[END_REF]; [START_REF] Goel | Sharp thresholds for monotone properties in random geometric graphs[END_REF], random walk behavior [START_REF] Avin | On the cover time and mixing time of random geometric graphs[END_REF] and chromatic number [START_REF] Mcdiarmid | On the chromatic number of random geometric graphs[END_REF][START_REF] Mcdiarmid | On the chromatic number of random geometric graphs[END_REF]; [START_REF] Penrose | Random Geometric Graphs[END_REF].

RGGs fail, however, to capture heterogeneity in the network. Geographical threshold graphs (GTG) aim at generalizing RGGs, providing this heterogeneity via a richer stochastic model that nevertheless preserves much of the simplicity of the RGG model. GTGs assign to nodes both a location and a weight, which may represent a quantity such as transmission power in a wireless network or influence in a social network. Edges are placed between two nodes if a symmetric function of their weights and the distance between them exceeds a certain threshold [START_REF] Bradonjić | Wireless ad hoc networks with tunable topology[END_REF].

Recent work has analyzed structural properties of GTGs, such as connectivity, clustering coefficient, degree distribution, diameter, existence and absence of the giant component Bradonjić et al. (2007[START_REF] Bradonjić | The structure of geographical threshold graphs[END_REF]. These properties are not merely of theoretical importance, but also play an important role in applications. In communication networks, connectivity implies the ability to reach all parts of the network. In packet routing, the diameter gives the minimal number of hops needed for transmission between two arbitrary nodes. And in the case of epidemics, the existence or absence of the giant component controls whether the epidemic spreads or is contained.

When considering wireless networks, a natural quantity to study is the chromatic number. This is the minimum number of colors needed to color vertices, such that no two adjacent vertices in the graph receive the same color. Treating the colors as the different radio channels or frequencies, the chromatic number gives the minimal number of channels needed so that neighboring radios do not interfere with each other. In this paper we study the asymptotic behavior of the chromatic number for GTGs with constant mean degree. We propose a greedy coloring algorithm, and analyze the behavior of this algorithm along with the graph's clique number. This leads to upper and lower bounds on the chromatic number.

The paper is organized as follows. Section 2 defines the GTG model. Section 3 presents our main asymptotic result, based on our analysis of the coloring algorithm. We show that for graphs 𝐺 of constant mean degree, both the clique number 𝜔(𝐺) and chromatic number 𝜒(𝐺) are with high probability ln 𝑛 ln ln 𝑛 (1 + 𝑜(1)). Section 4 analyzes the gap between lower and upper bounds on the chromatic number, given respectively by the clique number and the greedy coloring algorithm. We show that this gap is at most 𝐶 ln 𝑛/(ln ln 𝑛) 2 , and bound the constant 𝐶. Finally, Section 5 concludes with open questions regarding the chromatic number for sparser and denser GTGs.

Geographical Threshold Graph Model

Given random points 𝑋 1 , 𝑋 2 , • • • ∈ [0, 1] 2 that are i.i.d., uniformly at random, and i.i.d. nonnegative weights 𝑊 1 , 𝑊 2 , . . . , we construct a random geographical threshold graph 𝐺 𝑛 as follows. Let 𝑁 = 𝑑 Po(𝑛) be the number of nodes, independent of the 𝑋 𝑖 and 𝑊 𝑖 . Let 𝜃 𝑛 be a given threshold parameter that depends on 𝑛. Then 𝐺 𝑛 has vertex set 𝑉 (𝐺 𝑛 ) = {1, . . . , 𝑁 }, and for 𝑖, 𝑗 ∈ 𝑉 (𝐺 𝑛 ), 𝐺 𝑛 has edge 𝑖𝑗 ∈ 𝐸(𝐺 𝑛 ) iff

𝑊 𝑖 + 𝑊 𝑗 ‖𝑋 𝑖 -𝑋 𝑗 ‖ 2 ≥ 𝜃 𝑛 .
(1)

For technical convenience we identify opposite edges of [0, 1] 2 , making it into a torus. We will specifically analyze the regime of constant expected degree. If E(𝑊 𝑖 ) is a constant, then this occurs when the threshold parameter is linear in the expected number of nodes, 𝜃 𝑛 = Θ(𝑛). For simplicity we take 𝜃 𝑛 = 𝑛, since if 𝜃 𝑛 = 𝑐𝑛 for some constant 𝑐 > 0, the weights can always be rescaled to 𝑊 𝑖 := 𝑊 𝑖 /𝑐.

Asymptotic Results

If 𝐺 is a graph then 𝜔(𝐺) denotes its clique number and 𝜒(𝐺) its chromatic number. We will show formally that the clique number and chromatic number of the geographical threshold graph are essentially the same as those for a random geometric graph with the same (constant) average degree.

Note that, since coloring a clique of size 𝜔(𝐺) requires 𝜔(𝐺) different colors, 𝜔(𝐺) ≤ 𝜒(𝐺). The rest of this section is devoted to proving the theorem.

Lower bound

Let ŵ ∈ R be such that Pr(𝑊 𝑖 > ŵ) ≥ 1/2. Then the probability that 𝐺 𝑛 contains fewer than 𝑛/3 vertices with weight more than ŵ is exponentially small. In fact, this probability is bounded above by the probability that a Po(𝑛/2)-variable is less than 𝑛/3, which is exp(-Ω(𝑛)), as can be seen by the Chernoff bound. Let 𝐺 ′ 𝑛 be the subgraph of 𝐺 𝑛 induced by 𝑛/3 of the points with weight at least ŵ. Note that if 𝑖, 𝑗 ∈ 𝑉 (𝐺 ′ 𝑛 ) and ‖𝑋 𝑖 -𝑋 𝑗 ‖ 2 < 2 ŵ/𝑛 then certainly 𝑖𝑗 ∈ 𝐸(𝐺 ′ 𝑛 ). Thus 𝐺 ′ 𝑛 (and hence also 𝐺 𝑛 ) contains the ordinary random geometric graph RGG(𝑛/3, √ 2 ŵ/𝑛) as a subgraph, with probability 1 -exp(-Ω(𝑛)). By Lemma 5.3 of [START_REF] Mcdiarmid | Random channel assignment in the plane[END_REF],

Pr(𝜔(𝐺 𝑛 ) < (1 -𝜀) ln 𝑛/ ln ln 𝑛) = 𝑜(1).

Upper bound

Let us define a "level" 𝐿 𝑘 as follows:

𝐿 𝑘 := { {𝑖 ≤ 𝑁 : 𝑊 𝑖 < 1}, 𝑘 = -1 {𝑖 ≤ 𝑁 : 4 𝑘 ≤ 𝑊 𝑖 < 4 𝑘+1 }, 𝑘 ≥ 0.
Note that the set {𝑋 𝑖 : 𝑖 ∈ 𝐿 𝑘 } of the points of the Poisson process corresponding to level 𝑘 (for

𝑘 ≥ 0) is in fact a Poisson process itself with intensity 𝑛 ( 𝐹 (4 𝑘+1 ) -𝐹 (4 𝑘 ) )
on the unit square and intensity 0 elsewhere, where 𝐹 denotes the cdf of 𝑊 1 . Moreover, these Poisson processes corresponding to the levels 𝐿 -1 , 𝐿 0 , 𝐿 1 , . . . are independent.

For 𝑥 ∈ [0, 1] 2 let us denote

𝑀 𝑥 := ∞ ∑ 𝑘=-1 |{𝑖 ∈ 𝐿 𝑘 : ‖𝑋 𝑖 -𝑥‖ ≤ 6 √ 2 • 2 𝑘 / √ 𝑛}|,
and let us set 𝑀 := max 𝑥∈[0,1] 2 𝑀 𝑥 . Very roughly, 𝑀 represents the greatest number of neighbors that a sufficiently high-weight node can have. Then we have the following lemma.

Lemma 3.2 The chromatic number satisfies 𝜒(𝐺 𝑛 ) ≤ 𝑀 .

Proof: Let us order the vertices by nondecreasing weight and greedily color them. That is, we first color the vertex with smallest weight, then the vertex with second smallest weight and so on; and when we choose a color for a vertex we always pick the smallest available color (i.e., the smallest color that does not occur among the neighbors of the vertex that have already been colored). We claim that in this way we will never need more than 𝑀 colors.

For ease of notation let us assume (w.l.o.g.) that

𝑊 1 ≤ 𝑊 2 ≤ • • • ≤ 𝑊 𝑁 . Let 𝑁 < (𝑖)
represent all neighbors of node 𝑖 with lower weight than 𝑖:

𝑁 < (𝑖) := {𝑗 < 𝑖 : 𝑖𝑗 ∈ 𝐸(𝐺 𝑛 )}. Note that if 𝑖 ∈ 𝐿 𝑘 and 𝑗 ∈ 𝑁 < (𝑖) then ‖𝑋 𝑖 -𝑋 𝑗 ‖ ≤ 2 𝑘+3/2 / √ 𝑛. For 1 ≤ 𝑖 ≤ 𝑁 let 𝑐(𝑖)
denote the color that the algorithm has assigned to vertex 𝑖. Observe that for each 1 ≤ 𝑖 ≤ 𝑁 we have

{1, . . . , 𝑐(𝑖) -1} ⊆ {𝑐(𝑗) : 𝑗 ∈ 𝑁 < (𝑖)}, (2)
because otherwise the algorithm would not have used color 𝑐(𝑖) for 𝑖. Now let 𝑖 be an arbitrary vertex. For notational convenience let us write 𝑗 0 := 𝑖 and let 𝑘 0 denote the level of 𝑖. Let 𝑚 be the maximal number for which there exist strictly decreasing sequences

𝑗 0 > 𝑗 1 > • • • > 𝑗 𝑚 and 𝑘 0 > 𝑘 1 > • • • > 𝑘 𝑚
with the following properties. For each 𝑝 = 0, . . . , 𝑚 -1 we have

1. 𝑐(𝑗 𝑝+1 ) = max ( {1, . . . , 𝑐(𝑗 𝑝 ) -1} ∖ {𝑐(𝑗) : 𝑗 ∈ 𝑁 < (𝑗 𝑝 ) ∩ 𝐿 𝑘𝑝 } ) ; 2. 𝑗 𝑝+1 ∈ 𝐿 𝑘𝑝+1 ∩ 𝑁 < (𝑗 𝑝 ).
(Observe that, for each color 𝑐 ∈ {1, . . . , 𝑐(𝑗 𝑝 ) -1} ∖ {𝑐(𝑗) : 𝑗 ∈ 𝑁 < (𝑗 𝑝 ) ∩ 𝐿 𝑘𝑝 } -provided this set is non-empty -there is a 𝑗 ∈ 𝑁 < (𝑗 𝑝 ) with 𝑐(𝑗) = 𝑐 by (2) and the level of 𝑗 is necessarily strictly less than 𝑘 𝑝 .) It is possible that 𝑚 = 0. In that case {1, . . . , 𝑐(𝑗 0 ) -1} ⊆ {𝑐(𝑗) : 𝐿 𝑘0 ∩ 𝑁 < (𝑗 0 )}. This gives

𝑐(𝑖) ≤ |𝐿 𝑘0 ∩ 𝑁 < (𝑖)| + 1 ≤ |{𝑗 ∈ 𝐿 𝑘0 : ‖𝑋 𝑗 -𝑋 𝑖 ‖ ≤ 2 𝑘0+3/2 / √ 𝑛}| ≤ 𝑀 𝑋𝑖 ≤ 𝑀. Now suppose that 𝑚 > 0. By maximality of 𝑚 we have {1, . . . , 𝑐(𝑗 𝑚 ) -1} ⊆ {𝑐(𝑗) : 𝐿 𝑘𝑚 ∩ 𝑁 < (𝑗 𝑚 )}.
(3) Also note that, by definition of 𝑗 𝑝 we have

{𝑐(𝑗 𝑝+1 ) + 1, . . . , 𝑐(𝑗 𝑝 ) -1} ⊆ {𝑐(𝑗) : 𝑗 ∈ 𝐿 𝑘𝑝 ∩ 𝑁 < (𝑗 𝑝 )} for 𝑝 = 0, . . . , 𝑚 -1. (4)
Combining ( 3) and ( 4) we find

𝑐(𝑖) = |{1, . . . , 𝑐(𝑗 𝑚 ) -1}| + 1 + ∑ 𝑚-1 𝑝=0 |{𝑐(𝑗 𝑝+1 ) + 1, . . . , 𝑐(𝑗 𝑝 ) -1}| + 1 ≤ ∑ 𝑚 𝑝=0 |𝐿 𝑘𝑝 ∩ 𝑁 < (𝑗 𝑝 )| + 𝑚 + 1 ≤ ∑ 𝑚 𝑝=0 |{𝑗 ∈ 𝐿 𝑘𝑝 : ‖𝑋 𝑗 -𝑋 𝑗𝑝 ‖ ≤ 2 𝑘𝑝+ 3 2 / √ 𝑛}|.
(5)

Let us observe that:

‖𝑋 𝑗𝑝 -𝑋 𝑗𝑚 ‖ ≤ ∑ 𝑚-1 𝑞=𝑝 ‖𝑋 𝑗𝑞 -𝑋 𝑗𝑞+1 ‖ ≤ ∑ 𝑚-1 𝑞=𝑝 2 𝑘𝑞+3/2 / √ 𝑛 < 2 𝑘𝑝+5/2 / √ 𝑛, for all 1 ≤ 𝑝 ≤ 𝑚. Thus, if ‖𝑋 𝑗 -𝑋 𝑗𝑝 ‖ < 2 𝑘𝑝+ 3 2 / √ 𝑛 then ‖𝑋 𝑗 -𝑋 𝑗𝑚 ‖ ≤ ‖𝑋 𝑗𝑝 -𝑋 𝑗𝑚 ‖ + ‖𝑋 𝑗 -𝑋 𝑗𝑝 ‖ ≤ (2 𝑘𝑝+5/2 + 2 𝑘𝑝+3/2 )/ √ 𝑛 = 6 √ 2 • 2 𝑘𝑝 / √ 𝑛. (6)
Combining ( 6) with ( 5) we get:

𝑐(𝑖) ≤ ∑ 𝑚 𝑝=0 |{𝑗 ∈ 𝐿 𝑘𝑝 : ‖𝑋 𝑗 -𝑋 𝑗𝑚 ‖ ≤ 6 √ 2 • 2 𝑘𝑝 / √ 𝑛}|. ≤ 𝑀 𝑋𝑗 𝑚 ≤ 𝑀.
Since the vertex 𝑖 was arbitrary, the claim follows.

2

Remark: Note that Lemma 3.2 does not depend on the fact that the points and weights are random, but rather it will hold for any "deterministic" threshold graph if we replace 𝑛 by its threshold 𝜃 𝑛 in the definition of 𝑀 𝑥 above.

To finish the proof of the theorem it now suffices to prove the following lemma.

Lemma 3.3 Suppose that weights are distributed such that Pr(𝑊 𝑖 > 𝑥) = 𝑂(𝑥 -𝛾 ) for some 𝛾 > 1.

Then, for any 𝜀 > 0:

Pr

( 𝑀 ≥ (1 + 𝜀) ln 𝑛 ln ln 𝑛 ) → 0, as 𝑛 → ∞. Proof: Let us set 2 • 2 𝑘 / √
𝑛 for all 𝑘 ≥ -1, and thus

𝑀 ≤ max 𝑥∈𝐴 𝑀 ′ 𝑥 . (7)
Let 𝑥 ∈ R 2 be arbitrary and note that 𝑀 ′ 𝑥 = 𝑑 ∑ ∞ 𝑘=-1 𝑍 𝑘 , where the 𝑍 𝑘 are independent Poisson random variables, and

E(𝑍 𝑘 ) = { 𝜋(12 √ 2) 2 4 -1 𝐹 (1), 𝑘 = -1 𝜋(12 √ 2) 2 4 𝑘 ( 𝐹 (4 𝑘+1 ) -𝐹 (4 𝑘 ) ) , 𝑘 ≥ 0. = 𝑂(4 𝑘(1-𝛾) ).

So in particular 𝑀 ′

𝑥 is itself Poisson with a mean that is bounded above by some constant, say 𝜇. Using a well known bound, see for instance the Lemma 4.4 of [START_REF] Mcdiarmid | Random channel assignment in the plane[END_REF], we obtain that

Pr(𝑀 ′ 𝑥 > (1 + 𝜀) ln 𝑛/ ln ln 𝑛) ≤ ( 𝑒𝜇 (1 + 𝜀) ln 𝑛/ ln ln 𝑛 ) (1+𝜀) ln 𝑛/ ln ln 𝑛 (8) = exp ( -(1 + 𝜀 + 𝑜(1)) ln 𝑛 ) .
Hence, by Eq. ( 7), applying the union bound,

Pr ( 𝑀 > (1 + 𝜀) ln 𝑛/ ln ln 𝑛 ) ≤ 𝑛𝑒 -(1+𝜀+𝑜(1)) ln 𝑛 ≤ 𝑛 -𝜀 2 . ( 9
)
The last inequality holds for 𝑛 sufficiently large. This shows that 𝑀/(ln 𝑛/ ln ln 𝑛) is upper bounded by 1 + 𝜀, with high probability. 2

Remark: It is possible to adapt a subsequence trick from [START_REF] Penrose | Random Geometric Graphs[END_REF] (page 123) to strengthen the type of convergence in Theorem 3.1 from convergence in probability to almost sure convergence. We now briefly sketch the main ideas.

The probability that the clique number of the RGG is less than (1 -𝜀) ln 𝑛/ ln ln 𝑛 has been upper bounded by exp(-𝑛 𝜀+𝑜(1) ) in [START_REF] Mcdiarmid | Random channel assignment in the plane[END_REF] (page 201). These computations combined with the Borel-Cantelli Lemma give that lim inf 𝑀/(ln 𝑛/ ln ln 𝑛) ≥ 1 a.s.

To prove that lim sup 𝑀/(ln 𝑛/ ln ln 𝑛) ≤ 1 a.s. let us define a sequence (𝑚 𝑘 ) 𝑘 by setting 𝑚 𝑘 := 𝑘 3/𝜀 . Then the upper bound (9) together with the Borel-Cantelli lemma give that Pr ( 𝑀 (𝑚 𝑘 ) ln 𝑚 𝑘 / ln ln 𝑚 𝑘 ≤ 1 + 𝜀 for all but finitely many 𝑘

) = 1. (10)
If instead of 𝜃 𝑛 = √ 𝑛 we had taken 𝜃 (𝜀)

𝑛 := (1 -𝜀)
√ 𝑛 then all computations leading up to (10) would have held. For 𝑛 ∈ N, let 𝑚(𝑛) := ⌈𝑛 𝜀/3 ⌉ 3/𝜀 be the least element of (𝑚 𝑘 ) 𝑘 with 𝑛 ≤ 𝑚 𝑘 . Observe that lim 𝑛→∞ 𝑚(𝑛)/𝑛 = 1, so that in particular 𝜃 (𝜀) 𝑚(𝑛) ≤ 𝜃 𝑛 for all sufficiently large 𝑛. Now, let 𝑀 (𝜀) denote the analogue of 𝑀 , which we obtain if we use the same points 𝑋 1 , 𝑋 1 , . . . and weights 𝑊 1 , 𝑊 2 , . . . , with the threshold 𝜃 (𝜀) 𝑛 instead. Let us assume that the random variables 𝑁 (1), 𝑁 (2), . . . , which determine the number of points used in the construction of the GTG and definition of 𝑀 , have been coupled in such a way that 𝑁 (𝑘) ≤ 𝑁 (𝑘 + 1) for all 𝑘. (This can be achieved by setting 𝑁 (𝑘) = 𝑌 1 + • • • + 𝑌 𝑘 with the 𝑌 𝑖 's i.i.d. Po(1)-variables). Then we obtain

𝑀 (𝑛) ≤ 𝑀 (𝜀) (𝑚(𝑛)), (11)
for all sufficiently large 𝑛 (using that 𝜃 (𝜀) 𝑚(𝑛) ≤ 𝜃 𝑛 for all sufficiently large 𝑛). Combining ( 11) with (10) proves that lim sup 𝑀/(ln 𝑛/ ln ln 𝑛) ≤ 1 a.s.

Mind the Gap!

In this section we analyze the gap between lower and upper bounds on the chromatic number, given respectively by the clique number (Subsection 4.1) and the greedy coloring algorithm (Subsection 4.2). In Subsection 4.3 we show that this gap is at most 𝐶 ln 𝑛/(ln ln 𝑛) 2 , and bound the constant 𝐶.

Lower Bound

Informally: we tile the space [0, 1] 2 and inscribe a ball in each tile. Then the number of nodes within a clique in an arbitrarily chosen ball will give us a lower bound on the chromatic number of the entire geographical threshold graph within [0, 1] 2 . The number of the balls, or how we tile the space [0, 1] 2 , is a parameter that we discuss later. Formally, the argument is the following.

For some threshold weight 𝑤 0 , let 𝛼 be defined by Pr(𝑊 ≤ 𝑤 0 ) = 𝛼. We will appropriately choose the constant 𝑤 0 (and hence 𝛼) later. Let us define a radius 𝑟 0 = √ 𝑤 0 /(2𝜃 𝑛 ). We consider 𝑏 = 1/(2𝑟 0 ) 2 disjoint balls with radii 𝑟 0 (see Figure 1) and call these balls 𝐵 𝑖 . For convenience, tile the square [0, 1] 2 with 𝑏 = 1/(2𝑟 0 ) 2 sub-squares of the size 2𝑟 0 × 2𝑟 0 , and within each of the squares inscribe a ball of radius 𝑟 0 . The number of nodes within 𝐵 𝑖 is given by Poisson distribution Po(𝑛𝑟 2 0 𝜋), while the number of nodes with weights ≥ 𝑤 0 within 𝐵 𝑖 is given by Po((1 -𝛼)𝑛𝑟 2 0 𝜋). For convenience we let 𝜆 = (1 -𝛼)𝑛𝑟 2 0 𝜋. Let us note that for

𝜃 𝑛 = 𝑛 it follows 𝑏 = 1/(4𝑟 2 0 ) = 𝜃 𝑛 /(2𝑤 0 ) = 𝑛/(2𝑤 0 ) (this is Θ(𝑛)) and 𝜆 = 𝜋 2 (1 -𝛼)𝑤 0 (this is Θ(1)
). Let us now consider only those nodes with weights 𝑊 ≥ 𝑤 0 within a given ball 𝐵 𝑖 . All such nodes form a clique, since by construction, each pair of nodes within 𝐵 𝑖 satisfies the connectivity relation Eq. (1). Let 𝑘 be a positive integer to be specified later. Since the number of nodes 𝑛 𝑖 within 𝐵 𝑖 is a Poisson random variable with mean 𝜆,

Pr(𝑛 𝑖 ≥ 𝑘) ≥ 𝑒 -𝜆 𝜆 𝑘 𝑘! . ( 12
)
Denote 𝑝 := 𝑒 -𝜆 𝜆 𝑘 /𝑘!, and let 𝐼 𝑖 be an indicator of the event {𝑛 𝑖 ≥ 𝑘}, so that Pr(𝐼 𝑖 = 1) ≥ 𝑝. Let us define 𝐽 = ∑ 𝑏 𝑖=1 𝐼 𝑖 . We will show that for sufficiently large 𝑘, Pr(𝐽 = 0) → 0. First, 𝐽 = 0 iff all 𝐼 𝑖 are 0. Second, the indicators 𝐼 𝑖 are mutually independent, since the balls 𝐵 𝑖 are mutually disjoint. Thus, Pr(∩𝐼 𝑐 𝑖 ) = Pr(𝐼 𝑐 𝑖 ) 𝑏 ≤ (1 -𝑝) 𝑏 = exp(ln(1 -𝑝)𝑏). We have seen that 𝑏 = Θ(𝑛). Now choose 𝑘 so that 𝑝 = ln 𝑛/𝑛. In that case, Pr(𝐽 > 0) ≥ 1 -exp(ln(1 -𝑝)𝑏) = 1 -exp(-Θ(ln 𝑛)) = 1 -𝑛 -Θ(1) . Thus, we must solve the following equation in 𝑘 𝑒 -𝜆 𝜆 𝑘 𝑘! = ln 𝑛 𝑛 .

(13) Taking the logarithm, 𝜆 -𝑘 ln 𝜆 + ln 𝑘! = ln 𝑛 -ln ln 𝑛.

According to Stirling's formula 𝑘! = √ 2𝜋𝑘 𝑘 𝑘 𝑒 -𝑘+𝛽/12𝑘 for some 𝛽 ∈ (0, 1), and applying the logarithm, ln 𝑘! = 1 2 ln 2𝜋𝑘 + 𝑘(ln 𝑘 -1) + 𝛽/12𝑘. Now, Eq.( 14) is equivalent to

𝑘(ln 𝑘 -1 -ln 𝜆) = ln 𝑛 -ln ln 𝑛 -𝜆 - 1 2 ln 2𝜋 - 1 2 ln 𝑘 - 𝛽 12𝑘 . (15)
Let 𝜂 = 1 + ln 𝜆 (this is Θ(1)), and introduce the (rescaled) variables 𝑦 = 𝑒 -𝜂 𝑘 and 𝑥 = 𝑒 -𝜂 (ln 𝑛ln ln 𝑛 -𝜆 -1 2 ln 2𝜋 -𝛽/12𝑘 -𝜂/2). Then, Eq. ( 15) may be recast as

𝑦 = 𝑥 ln 𝑦 - 𝑒 -𝜂 2 . (16)
For given 𝑥 and 𝜂, Eq. ( 16) has a unique solution in 𝑦. Noting that 𝑥 = Θ(ln 𝑛), it is not hard to verify that 𝑦 satisfies

𝑦 = 𝑥 ln 𝑥 ( 1 + ln ln 𝑥 ln 𝑥 (1 + 𝑜(1)) ) . (17)
From the precise definition of 𝑥,

𝑥 = 𝑒 -𝜂 ln 𝑛 ( 1 -𝑂 ( ln ln 𝑛 ln 𝑛 )) , (18)
so ln 𝑥 = ln ( 𝑒 -𝜂 ln 𝑛 (1 -𝑜(1)) ) = ln ln 𝑛 -𝜂 -𝑜(1)
and

ln ln 𝑥 = ln ( ln ln 𝑛 (1 -𝑜(1)) )
= ln ln ln 𝑛 -𝑜(1).

Therefore from Eq. ( 17),

ln 𝑦 = ln 𝑥 -ln ln 𝑥 + 𝑜(1)
= ln ln 𝑛 -ln ln ln 𝑛 -𝜂 -𝑜(1)

= ln ln 𝑛 ( 1 - ln ln ln 𝑛 + 𝜂 + 𝑜(1) ln ln 𝑛 ) . (19)
Plugging Eq. ( 18) and Eq. ( 19) into the right-hand side of Eq. ( 16) gives

𝑦 = 𝑒 -𝜂 ln 𝑛 ( 1 -𝑂 ( ln ln 𝑛 ln 𝑛 )) ln ln 𝑛 ( 1 -ln ln ln 𝑛+𝜂+𝑜(1) ln ln 𝑛 ) - 𝑒 -𝜂 2 = 𝑒 -𝜂 ln 𝑛 ln ln 𝑛 ( 1 + ln ln ln 𝑛 + 𝜂 + 𝑜(1) ln ln 𝑛 ) - 𝑒 -𝜂 2 , so 𝑘 = 𝑒 𝜂 𝑦 = ln 𝑛 ln ln 𝑛 ( 1 + ln ln ln 𝑛 + 𝜂 + 𝑜(1) ln ln 𝑛 ) .
We know that there is a clique of size at least 𝑘 within some ball 𝐵 𝑖 , with probability ≥ 1 -𝑛 -Θ(1) . Since 𝑘 ≤ 𝜔(𝐺 𝑛 ) ≤ 𝜒(𝐺 𝑛 ), it follows that with probability ≥ 1 -𝑛

Upper Bound

In this subsection we derive an upper bound on the chromatic number, given by the greedy coloring algorithm in Section 3. Consider the inequality (8). Letting 𝐵 = 1 + ln 𝜇,

Pr ( 𝑀 ′ 𝑥 > (1 + 𝜀) ln 𝑛/ ln ln 𝑛 ) ≤ ( 𝑒𝜇 (1 + 𝜀) ln 𝑛/ ln ln 𝑛 ) (1+𝜀)

Comparison of Bounds

Let us now optimize the constants 𝜂 = 1 + ln 𝜆 and 𝐵 = 1 + ln 𝜇 to minimize the gap between lower and upper bounds on 𝜒(𝐺 𝑛 ). We define 𝑠 1 = sup 𝛼∈[0,1] 𝜂 and 𝑠 2 = inf 𝛼∈[0,1] 𝐵. By using the definition of 𝛼 = Pr(𝑊 ≤ 𝑤 0 ), we obtain

𝑠 1 = 1 + sup 𝛼∈[0,1] ln 𝜆 = 1 + sup 𝛼∈[0,1] ln ( (1 -𝛼)𝑛𝑟 2 0 𝜋 ) = 1 + sup 𝛼∈[0,1] ln ( 𝜋 2 𝑛 𝜃 𝑛 (1 -𝛼)𝑤 0 ) = 1 + ln 𝜋 2 + sup 𝑤0≥0 ln ( (1 -𝐹 (𝑤 0 ))𝑤 0 ) = 1 + ln 𝜋 2 + ln ( sup 𝑤0≥0 𝑤 0 (1 -𝐹 (𝑤 0 )) ) . (20)
For the other bound, 𝑠 2 = 1 + inf 𝛼∈[0,1] ln 𝜇, and 𝜇 is bounded by

𝜇 ≤ ∞ ∑ 𝑗=-1 E(𝑍 𝑗 ) = 𝜋(12 √ 2) 2 ( 4 -1 𝐹 (1) + ∞ ∑ 𝑗=0 4 𝑗 ( 𝐹 (4 𝑗+1 ) -𝐹 (4 𝑗 ) ) ) = 𝜋(12 √ 2) 2 ( 1 4 + 3 4 ∞ ∑ 𝑗=0 4 𝑗 (1 -𝐹 (4 𝑗 )) ) , so 𝑠 2 ≤ 1 + ln ( 72𝜋 ( 1 + 3 ∞ ∑ 𝑗=0 4 𝑗 (1 -𝐹 (4 𝑗 )) )) . (21)
Note that the conditions imposed on the weight distribution in Lemma 3.3 are Pr(𝑊 𝑖 > 𝑥) = 𝑂(𝑥 -𝛾 ) for some 𝛾 > 1. Then it may be helpful to write 1 -𝐹 (4 𝑗 ) = 𝑂(4 -𝛾𝑗 ) ≤ 𝐷4 -𝛾𝑗 , with the constant 𝐷 given by 𝐷 = max 𝑗 4 𝛾𝑗 (1 -𝐹 (4 𝑗 )). In that case,

𝑠 2 ≤ 1 + ln ( 72𝜋 ( 1 + 3 ∞ ∑ 𝑗=0 4 𝑗 𝐷4 -𝛾𝑗 )) = 1 + ln ( 72𝜋 ( 1 + 3𝐷 ∞ ∑ 𝑗=0 4 (1-𝛾)𝑗 )) = 1 + ln ( 72𝜋 ( 1 + 3𝐷 1 -4 1-𝛾 )) . Now the

Examples of Bounds

Here we compare lower and upper bounds for the following two weight distributions: (i) exponential and (ii) power-law.

(i) Exponential weight distribution: 𝑓 (𝑤) = 𝑒 -𝑤 , for 𝑤 ≥ 0, and thus 𝐹 (𝑤) = 1 -𝑒 -𝑤 .

Since sup 𝑤0≥0 𝑤 0 (1 -𝐹 (𝑤 0 )) = 1/𝑒 is attained at 𝑤 0 = 1, Eq. ( 20) yields 𝑠 1 = ln(𝜋/2) ≈ 0.4516.

On the other hand, Eq. ( 21) yields

𝑠 2 ≤ 1 + ln ( 72𝜋 ( 1 + 3 ∞ ∑ 𝑗=0 4 𝑗 exp(-4 𝑗 ) )) ≈ 7.2644,
giving 𝐶 < 6.82.

(ii) Power-law weight distribution: 𝑓 (𝑤) = 𝑤 -𝛽 , for 𝑤 ≥ 1, and thus 𝐹 (𝑤) = 1 -1/𝑤 𝛽-1 .

Since sup 𝑤0≥1 𝑤 0 (1 -𝐹 (𝑤 0 )) = sup 𝑤0≥1 1/𝑤 𝛽-2 0 = 1, attained at 𝑤 0 = 1 and for 𝛽 ≥ 2, then Eq. (20) yields 𝑠 1 = 1 + ln(𝜋/2) ≈ 1.4516, while Eq. ( 21) becomes

𝑠 2 ≤ 1 + ln ( 72𝜋 ( 1 + 3 ∞ ∑ 𝑗=0 4 𝑗(2-𝛽) )) = 1 + ln ( 72𝜋 ( 1 + 3 1 -4 2-𝛽 )) ≈ 6.4214 + ln ( 1 + 3 1 -4 2-𝛽 )
.

If for instance 𝛽 = 3, this last bound is ≈ 8.0308, giving 𝐶 < 6.58.

Conclusion

In this work, we have derived the chromatic number and proposed a coloring algorithm on GTG, for the case of 𝜃 𝑛 = Θ(𝑛), that is, when the mean degree is constant. We are naturally interested into the values of the chromatic number for denser and sparser GTGs. A particularly interesting case would be to show the chromatic number around the connectivity regime. The connectivity threshold for GTGs has been derived to be 𝜃 𝑛 = Θ(𝑛/ ln 𝑛), Bradonjić et al. (2007). However, the methods that we have used in this work rely heavily on the techniques that apply for RGGs of equivalent degree and the analysis of the chromatic number of the RGG is much more involved in this range than in the range we have studied in this work. For instance, in McDiarmid and Müller it has been shown that if the expected degree of the RGG is 𝑡 ln 𝑛 for some constant 𝑡 > 0, then the ratio of the chromatic number to the clique number has a limit, which can be expressed as some complicated function of 𝑡. One of the surprising findings of McDiarmid and Müller has been the existence of a constant 𝑡 0 > 0 such that this ratio tends to 1 for expected degrees ≤ 𝑡 0 ln 𝑛 and it is strictly bigger than one if the expected degree is at least (𝑡 0 + 𝜀) ln 𝑛, for any 𝜀 > 0.

It is unlikely that the crude upper bound on the chromatic number, which we have used in this work (that is, our 𝑀 ), would be anywhere near sharp when the expected degree is logarithmic. Therefore, we expect that substantial new tools will be needed to tackle the chromatic number of the GTG in this regime.

Fig. 1 :

 1 Fig. 1: Tiling of the unit square, showing one ball 𝐵𝑖 and the high-weight nodes (𝑊 ≥ 𝑤0) within the ball.

  Theorem 3.1 Suppose that weights are distributed such that Pr(𝑊 𝑖 > 𝑥) = 𝑂(𝑥 -𝛾 ) for some 𝛾 > 1.

	Then	𝜔(𝐺 𝑛 ) ln 𝑛/ ln ln 𝑛	→ 1 in probability,
	and	𝜒(𝐺 𝑛 ) ln 𝑛/ ln ln 𝑛	→ 1 in probability,
	as 𝑛 → ∞.

  ln 𝑛/ ln ln 𝑛 Hence, by Eq. (7) and the union bound, Pr(𝑀 < (1 + 𝜀) ln 𝑛/ ln ln 𝑛) ≥ 1 -𝑒 -ln 𝑛 ln ln 𝑛 (𝛿-𝑜(1)) . Consequently, for any positive constant 𝛿, the chromatic number satisfies

			𝜒(𝐺 𝑛 ) ≤	ln 𝑛 ln ln 𝑛	(	1 +	ln ln 𝑛 ln ln ln 𝑛 + 𝐵 + 𝛿	)
	with probability ≥ 1 -exp(-Θ(ln 𝑛/ ln ln 𝑛)).
					= exp	{(	𝐵 -ln	(	(1 + 𝜀)	ln 𝑛 ln ln 𝑛	) )	(1 + 𝜀)	ln ln 𝑛 ln 𝑛	}
					= exp	{	ln 𝑛	( 𝐵(1 + 𝜀) ln ln 𝑛	-(1 + 𝜀)	ln ln 𝑛 ln(1 + 𝜀) + ln ln 𝑛 -ln ln ln 𝑛	)}
					= exp	{	ln 𝑛	( 𝐵(1 + 𝜀) ln ln 𝑛	-	(1 + 𝜀) ln(1 + 𝜀) ln ln 𝑛
												-(1 + 𝜀) + (1 + 𝜀)	ln ln 𝑛 ln ln ln 𝑛	)}
					= exp	{	ln 𝑛	( 𝐵 ln ln 𝑛	+	𝐵𝜀 ln ln 𝑛	-	𝜀 + 𝑂(𝜀 2 ) ln ln 𝑛
												-1 -𝜀 +	ln ln ln 𝑛 ln ln 𝑛	+ 𝜀	ln ln ln 𝑛 ln ln 𝑛	)}	.
	Let us choose 𝜀 to be			𝜀 =	ln ln ln 𝑛 + 𝐵 + 𝛿 ln ln 𝑛
	for some 𝛿. Then it follows that
	Pr	(	𝑀 ′ 𝑥 > (1 + 𝜀) ln 𝑛/ ln ln 𝑛	)	≤ exp	{	ln 𝑛	(	-1 -	𝛿 ln ln 𝑛	+ 𝜀	ln ln 𝑛 ln ln ln 𝑛 + 𝐵 -1 -𝑜(1)	)}
					= exp	{	ln 𝑛	(	-1 -	𝛿 -𝑜(1) ln ln 𝑛	)} .

  lower and upper bounds on 𝜒(𝐺 𝑛 ), respectively, give us the size of the gap 𝐶 ln 𝑛/(ln ln 𝑛) 2 .Finally, the constant 𝐶, specified in the abstract, is 𝐶 = 𝑠 2 -𝑠 1 , where 𝑠 1 and 𝑠 2 are as above.

		ln 𝑛 ln ln 𝑛	(	1 +	ln ln ln 𝑛 + 𝑠 1 ln ln 𝑛	)	≤ 𝜒(𝐺 𝑛 )
	and	𝜒(𝐺 𝑛 ) ≤	ln 𝑛 ln ln 𝑛	(	1 +	ln ln ln 𝑛 + 𝑠 2 ln ln 𝑛	)	,

Supported by the Department of Energy ASCR program at Los Alamos National Laboratory under contract DE-AC52-06NA25396. Partially supported through an ERC advanced grant. Supported by National Science Foundation grant CCF-0829945 and Office of Naval Research grant N000141010641. 1365-8050 c