Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions
Abstract
For every N≥36, we realise any prescribed monic irreducible binary polynomial of degree N as the characteristic polynomial of a linear hybrid cellular automaton on a near-square region of exactly N cells. The transition matrix is Moore-local with a null boundary and has at most 3N−1 directed nonself dependencies. The dependency graph retains a bidirectional Hamilton path; its indegree, outdegree and underlying undirected degree are at most six. The underlying graph contains an explicit square grid minor of side proportional to √N. The deterministic synthesis takes O(N3) bit operations. The construction combines a local similarity transformation with a transport potential and joint routing across consecutive row gaps. Exact verification of finite certificates, followed by induction, proves the required routing inequalities for every admissible width. We also give an entirely analytic construction with fewer than 7N/2 dependencies and prove a lower bound of 5N/2−O(√N) for the retained path and full rectangular grid minor. This lower bound is sharp when the characteristic polynomial is unrestricted.
Related
- Counting irreducible skew polynomials x2n+axn+1
- Monogenity of the irreducible factors of (k,t)-Fibonacci and (k,t)-Lucas polynomials
- Superpolynomially Large Support in Every Irreducible Factor of Lacunary Polynomials
- Cyclotomic polynomials with trinomial irreducible factors over finite fields
- Kazhdan--Lusztig Polynomials for permutations with Pid,w(1)=3 and Irreducible Singular Locus
BibTeX
@misc{chen2026sparse,
title = {{Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions}},
author = {Lizhong Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06983},
eprint = {2610.06983},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06983},
}
RIS
TY - UNPB
TI - Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions
AU - Lizhong Chen
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.06983
UR - https://arxiv.org/abs/2610.06983
AB - For every N≥36, we realise any prescribed monic irreducible binary polynomial of degree N as the characteristic polynomial of a linear hybrid cellular automaton on a near-square region of exactly N cells. The transition matrix is Moore-local with a null boundary and has at most 3N−1 directed nonself dependencies. The dependency graph retains a bidirectional Hamilton path; its indegree, outdegree and underlying undirected degree are at most six. The underlying graph contains an explicit square grid minor of side proportional to √N. The deterministic synthesis takes O(N^3) bit operations. The construction combines a local similarity transformation with a transport potential and joint routing across consecutive row gaps. Exact verification of finite certificates, followed by induction, proves the required routing inequalities for every admissible width. We also give an entirely analytic construction with fewer than 7N/2 dependencies and prove a lower bound of 5N/2−O(√N) for the retained path and full rectangular grid minor. This lower bound is sharp when the characteristic polynomial is unrestricted.
ER -