{"id":"arxiv/2610.06983","url":"https://arxiv.org/abs/2610.06983","tags":["math.CO","math.RA"],"score":0,"title":"Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions","domain":"math.CO","source":"arxiv","authors":["Lizhong Chen"],"reviews":0,"subject":"math.CO","summary":"For every $N\\ge36$, 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 $\\sqrt N$. The deterministic synthesis takes $O(N^3)$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}