Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow

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 ${\mathrm{\Theta }}^{\mathcal{I}}:{\text{A}}^k\to {\text{A}}^r$ and the objective is the size of its image. Writing $n:=\mathrm{\mid }\text{A}\mathrm{\mid }$, we show that the maximum dispersion is $\mathrm{\Theta }(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 ${\text{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.