{"id":"arxiv/2606.09045","url":"https://arxiv.org/abs/2606.09045","tags":["math.CO"],"score":0,"title":"Embedding Finite Functions into Low-Degree Polynomial Functions over Commutative Rings","domain":"math.CO","source":"arxiv","authors":["Roman Bacik"],"reviews":0,"subject":"math.CO","summary":"A function $f \\colon X^k \\to X$ on a finite set embeds into a polynomial of total degree $d$ over a commutative ring $R$ if there is an injection $j \\colon X \\to R$ and a polynomial $g$ of total degree at most $d$ with $j \\circ f = g \\circ j^k$, where $j^k$ applies $j$ in each coordinate. These are the transition functions of $k$-neighbour cellular automata, and the injection $j$ is an enlargement of the alphabet that preserves the transitions. We prove three results, all verified in Lean~4 with Mathlib~\\cite{bacik2026finbin}. Every unary function $f \\colon X \\to X$ embeds into a polynomial…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-08","reactions":{}}