Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914314683678720 |
|---|---|
| author | Riis, Søren |
| author_facet | Riis, Søren |
| contents | We introduce a new framework term coding for extremal problems in discrete mathematics and information flow, where one chooses interpretations of function symbols so as to maximise the number of satisfying assignments of a finite system of term equations.
We then focus on dispersion, the special case in which the system defines a term map $Θ^\mathcal I:\A^k\to\A^r$ and the objective is the size of its image. Writing $n:=|\A|$, we show that the maximum dispersion is $Θ(n^D)$ for an integer exponent $D$ equal to the guessing number of an associated directed graph, and we give a polynomial-time algorithm to compute $D$. In contrast, deciding whether \emph{perfect dispersion} ever occurs (i.e.\ whether $\Disp_n(\mathbf t)=n^r$ for some finite $n\ge 2$) is undecidable once $r\ge 3$, even though the corresponding asymptotic rate-threshold questions are polynomial-time decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08110 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow Riis, Søren Information Theory 94A15, 68Q17, 05C57 E.4; F.1.3; G.2.2 We introduce a new framework term coding for extremal problems in discrete mathematics and information flow, where one chooses interpretations of function symbols so as to maximise the number of satisfying assignments of a finite system of term equations. We then focus on dispersion, the special case in which the system defines a term map $Θ^\mathcal I:\A^k\to\A^r$ and the objective is the size of its image. Writing $n:=|\A|$, we show that the maximum dispersion is $Θ(n^D)$ for an integer exponent $D$ equal to the guessing number of an associated directed graph, and we give a polynomial-time algorithm to compute $D$. In contrast, deciding whether \emph{perfect dispersion} ever occurs (i.e.\ whether $\Disp_n(\mathbf t)=n^r$ for some finite $n\ge 2$) is undecidable once $r\ge 3$, even though the corresponding asymptotic rate-threshold questions are polynomial-time decidable. |
| title | Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow |
| topic | Information Theory 94A15, 68Q17, 05C57 E.4; F.1.3; G.2.2 |
| url | https://arxiv.org/abs/2602.08110 |