Generalized fibonacci gates correspond to algebra structures on all domains
Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture
Computational Complexity
Summary
This paper solves a math and computer science puzzle about special gadgets called generalized Fibonacci gates, which help solve certain counting problems efficiently. The authors show that these gates on any domain size can be understood exactly as a kind of algebra called a commutative Frobenius algebra. This insight matches previous guesses and gives a method that works efficiently for all sizes. They also classify different families of these gates and explain which ones affect the counting in different cases.
What this means in practice
- •For algorithm designers: Design polynomial-time algorithms for counting problems by modeling constraints using generalized Fibonacci gates linked to Frobenius algebras.
- •For computational complexity analysts: Use the algebraic framework to identify which Holant problems built from these gates are tractable or hard based on underlying algebra structure.
A theory result. No direct application yet.
Authors
Aaron Sterling
Abstract
Liu introduced generalized Fibonacci gates on domains of size 3 and 4, proved that Holant problems built from them are tractable by a cut-and-merge algorithm, and conjectured that Fibonacci gates with matching polynomial-time algorithms exist on all higher domains. We extend the definition uniformly to every domain size $k$ and show that a family of domain-$k$ generalized Fibonacci gates is the same thing as a $k$-dimensional commutative Frobenius (equivalently, Artinian Gorenstein) algebra $A$ equipped with an orthonormal basis containing $1$. Under this dictionary Liu's parameter constraints are exactly associativity of $A$, a gate is an element $w\in A$, merging two gates is multiplication in $A$, and the Holant value of a connected graph $G$ is $τ\bigl(h^{\,|E|-|V|+1}\prod_v w_v\bigr)$ for a fixed ``handle'' element $h\in A$. This proves Liu's conjecture for every $k$, with an algorithm whose cost is polynomial in $k$ as well as in the graph. We also give a closure criterion for linear recurrences of any depth (a balance condition implies closure, and is necessary when the unit is a combination of the colours), and we map the landscape: semisimple algebras are exactly Liu's orthogonal frames, smoothable algebras with nilpotents are collided frames, and families whose algebra is not smoothable (``frameless'' families) exist exactly when $k\ge 14$. Finally we show that every non-semisimple part of a family is invisible to the Holant on connected graphs with two or more independent cycles. This note states the results and sketches the proofs; the proofs of the main theorems are short and are given essentially in full.