The Odd Shift is not sofic in dimensions $d \ge 3$
In this paper, we prove that the Odd Shift $S_{odd}$ is not sofic for dimensions $d \ge 3$. Our proof uses lower bounds from communication complexity, specifically the result of Raz and Spieker on the nondeterministic communication complexity for the connectivity problem. We also prove that $S_{odd}$ is not sofic for dimension $d=2$ under the assumption we call Mute Ocean.
Authors
- Ivan Mitrofanov (ORCID: https://orcid.org/0000-0001-6844-6357)
- Nikita Gladkov (ORCID: https://orcid.org/0000-0001-8671-7229)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.21008
- Primary Topic
- semigroups and automata theory
- Type
- preprint