Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3

We prove a complexity dichotomy theorem for ${\mathrm{H}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{t}}^{\ast }$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then ${\mathrm{H}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{t}}^{\ast }(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{S}\mathrm{L}(2,\mathbb{C})$ in $\mathrm{S}\mathrm{O}(3,\mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\mathit{\text{frames}}$ and $\mathit{\text{shells}}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\mathit{\text{annihilators}}$, which makes it possible to analyze $\mathit{\text{essentially}}\mathit{\text{Boolean}}\mathit{\text{domain}}$ functions in domain size $3$.