Abstract:Classical existence problems in extremal combinatorics ask whether finite operations can satisfy prescribed identities universally. Term Coding replaces this yes-or-no question by a graded one: for a finite system $\Gamma$, the maximum code size $S_n(\Gamma)$ is the largest number of satisfying assignments attainable on an $n$-element alphabet. We prove that normalisation and diversification associate $\Gamma$ with a labelled guessing game of guessing number $\alpha$ and give finite-alphabet sandwich bounds. Consequently, $\log_n S_n(\Gamma)=\alpha+o(1)$. Entropy and polymatroid inequalities provide systematic upper bounds. Examples include a five-cycle with exponent $5/2$, self-orthogonal Latin squares, and presentation-dependent exponents for universally equivalent identity systems. All theorems, lemmas and propositions in this paper have been machine-checked in the Lean 4 proof assistant; the development is available at this https URL.
From: Soren Riis [view email]
[v1]
Fri, 23 Jan 2026 10:14:05 UTC (31 KB)
[v2]
Sun, 30 Aug 2026 13:27:44 UTC (30 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。