Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich Theorem
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917219480371200 |
|---|---|
| author | Riis, Søren |
| author_facet | Riis, Søren |
| contents | Term Coding asks: given a finite system of term identities $Γ$ in $v$ variables, how large can its solution set be on an $n$--element alphabet, when we are free to choose the interpretations of the function symbols? This turns familiar existence problems for quasigroups, designs, and related objects into quantitative extremal questions.
We prove a guessing-number sandwich theorem that connects term coding to graph guessing numbers (graph entropy). After explicit normalisation and diversification reductions, every instance yields a canonical directed dependency structure with guessing number $α$ such that the maximum code size satisfies $\log_n \Sn(Γ)=α+o(1)$ (equivalently, $\Sn(Γ)=n^{α+o(1)}$), and $α$ can be bounded or computed using entropy and polymatroid methods.
We illustrate the framework with examples from extremal combinatorics (Steiner-type identities, self-orthogonal Latin squares) and from information-flow / network-coding style constraints (including a five-cycle instance with fractional exponent and small storage/relay maps). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16614 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich Theorem Riis, Søren Information Theory 94A17, 05C57, 05B15, 08B05 H.1.1; G.2.1; G.2.2 Term Coding asks: given a finite system of term identities $Γ$ in $v$ variables, how large can its solution set be on an $n$--element alphabet, when we are free to choose the interpretations of the function symbols? This turns familiar existence problems for quasigroups, designs, and related objects into quantitative extremal questions. We prove a guessing-number sandwich theorem that connects term coding to graph guessing numbers (graph entropy). After explicit normalisation and diversification reductions, every instance yields a canonical directed dependency structure with guessing number $α$ such that the maximum code size satisfies $\log_n \Sn(Γ)=α+o(1)$ (equivalently, $\Sn(Γ)=n^{α+o(1)}$), and $α$ can be bounded or computed using entropy and polymatroid methods. We illustrate the framework with examples from extremal combinatorics (Steiner-type identities, self-orthogonal Latin squares) and from information-flow / network-coding style constraints (including a five-cycle instance with fractional exponent and small storage/relay maps). |
| title | Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich Theorem |
| topic | Information Theory 94A17, 05C57, 05B15, 08B05 H.1.1; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2601.16614 |