The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of characteristic other than $2$, and the latter to be VNP-complete over every field. Since its introduction, $HC$ has been studied from the perspective of circuit lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its connection with the Permanent and the Determinant polynomials by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). It has been the most prominent choice for generalising results to all fields, such as in Malod (CCC 2007) and Grochow-Mulmuley-Qiao (ICALP 2016), owing to its VNP-completeness over every field. Hrubes (ToCT, 2016) showed the VNP-completeness of many graph-based polynomial families over every field by using $HC$.

In Kayal (STOC 2012), a randomised polynomial time algorithm was given for the following problem: Given an $n^2$-variate degree-$n$ polynomial $f(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{n^2}(\mathbb{F})$ such that $f(\mathbf{x}) = Perm_n(A\mathbf{x})$. Here, the Permanent polynomial $Perm_n$ computes the permanent of the $n \times n$ symbolic matrix $(x_{i,j})$. This problem is known as testing equivalence to the Permanent, or alternatively, ET for Permanent.

In this work, we study ET for $HC$. While both families are VNP-complete, the efficient ET algorithm for Permanent does not imply the same for $HC$. Besides, there are crucial differences between the two polynomials that make studying the complexity of ET for $HC$ interesting: The underlying decision problem corresponding to the Permanent is in P (detecting perfect matchings in a bipartite graph), but that for $HC$ (detecting Hamiltonian cycles in a digraph) is NP-complete. The Permanent polynomial is known to be characterised by its symmetries as shown by Mulmuley-Sohoni (SIAM J. Computing, 2001). This property yields an efficient algorithm for the circuit-testing problem for the Permanent, a special case of ET for the Permanent, in which we check whether a given circuit computes the Permanent. In contrast, we show $HC_n$ is not characterised by its symmetries.

In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the underlying field. The algorithm is obtained by studying and completely characterising the Lie algebra and the symmetries of $HC_n$. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. However, we also show that, unlike the Permanent polynomial, $HC_n$ is not characterised by its symmetries. Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, as shown in Zhang-Bai (TCS 2011), which implies $HC_n$ is characterised by circuit identities and that we can efficiently test whether a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.