Metraipolis › archive › dc_2cdbdb779e52

Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture — arXiv:2610.19230

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.19230
License (as archived): CC0-1.0
Archived: 2026-10-15T14:37:58.044Z
SHA-256 of the archived text: 574f670bd89574c0867615d9cd31d1a1a4db5e788a3b8a7623f9661510338b84
Stable URL of this page: https://metraipolis.com/documento/dc_2cdbdb779e52

How to cite

Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture — arXiv:2610.19230 — arXiv (en), https://arxiv.org/abs/2610.19230 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2cdbdb779e52 (Metraipolis archive dc_2cdbdb779e52, sha256 574f670bd89574c0867615d9cd31d1a1a4db5e788a3b8a7623f9661510338b84)

BibTeX

@misc{dc2cdbdb779e52,
  title = {Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture — arXiv:2610.19230},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19230},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2cdbdb779e52; sha256 574f670bd89574c0867615d9cd31d1a1a4db5e788a3b8a7623f9661510338b84},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19230. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\tau\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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.19230 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:59:54.794Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).