The Converse of the Real Orthogonal Holant Theorem
<|reference_start|>The Converse of the Real Orthogonal Holant Theorem: The Holant theorem is a powerful tool for studying the computational complexity of counting problems in the Holant framework. Due to the great expressiveness of the Holant framework, a converse to the Holant theorem would itself be a very powerful counting indistinguishability theorem. The most general converse does not hold, but we prove the following, still highly general, version: if any two sets of real-valued signatures are Holant-indistinguishable, then they are equivalent up to an orthogonal transformation. This resolves a partially open conjecture of Xia (2010). Consequences of this theorem include the well-known result that homomorphism counts from all graphs determine a graph up to isomorphism, the classical sufficient condition for simultaneous orthogonal similarity of sets of real matrices, and a combinatorial characterization of simultaneosly orthogonally decomposable (odeco) sets of tensors.<|reference_end|>
@article{young2024the,
    title={The Converse of the Real Orthogonal Holant Theorem},
    author={Ben Young},
    journal={arXiv preprint arXiv:2409.06911},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06911},
    primaryClass={cs.DM math.CO}
}