Decidability and Cluster algebras

Question

Recall the definition of a cluster algebra, which can be seen as a (possibly infinite) graph, where each vertex is a tuple of a quiver and Laurent expressions at some of the vertices of the quiver. The edges of this graph is given by mutations, and every vertex has the same degree.

Whenever the quiver is a Dynkin diagram, the graph is finite, and the Laurent polynomials have nice interpretations.

However, for a general seed quiver, the graph is infinite. Given a seed, and a Laurent polynomial, is there an algorithm to determine if the given Laurent polynomial appear as a cluster variable in the cluster algebra? Or might this be undecidable?

The reason it might be undecidable, is that a priori, the graph is infinite, so there is no upper bound on how many vertices we need to visit (by successive mutations), before concluding that the expression cannot be constructed, and the problem has "the same feel" as say the Collatz problem, or the problem of deciding if a set of matrices can produce the zero matrix by multiplication (the latter problem is undecidable).

Answer 1

For rank 2 it is decidable since there is a combinatorial formula for cluster variables. This case is certainly simpler than the general case, but some nice properties on the rank 2 case are conjectured to hold more generally. So, I'll write a bit about the rank 2 case and a bit about how we may hope to generalize. This does not answer the whole question, but hopefully it is still useful to someone.

See Theorem 1.11 of Greedy elements in rank 2 cluster algebras by Lee, Li, and Zelevinsky. For the rank 2 cluster algebra $\mathcal{A}(a,b)$ the theorem gives this formula $$x[a_1,a_2] = x_1^{-a_1} x_2^{-a_2} \sum_{(S_1, S_b)}x_1^{b|S_2|}x_2^{a|S_1|} $$ where $S_1$ and $S_2$ are defined in terms of certain Dyck paths (see the paper for details). For each $(a_1,a_2) \in \mathbb{Z} \times \mathbb{Z}$ the theorem describes corresponding the so call greedy element of the cluster algebra. It is known that each cluster variable is a greedy element, and it is known which pairs $(a_1,a_2)$ correspond to cluster variables (see Remark 1.9). As a result we can decide if a given Laurent polynomial is a cluster variable in any rank 2 cluster algebra.

The $(a_1,a_2)$ is known as the denominator vector, and such denominator vectors exists in other cluster algebras too. It is conjectured that different cluster variables have different denominator vectors (see this MO question). It seems like a hard problem, but perhaps it's possible to classifying denominator vectors corresponding to cluster variables then give a combinatorial formula for the remaining polynomial like the rank 2 case.