Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

Abstract

We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings $(a,b,c)$, there exists a string $z$ such that each conditional Kolmogorov complexity $C(a|z),C(b|z),C(c|z)$ is approximately half of the corresponding unconditional Kolmogorov complexity. We give a negative answer to this question by constructing a triple $(a,b,c)$ for which no such string $z$ exists. Moreover, we construct a fully explicit example of such a tuple. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on bounds for point-line incidences over prime fields. As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields.

26 pages, 3 figures. v4: revised and extended version. A short version of the paper has been accepted to appear at the MFCS 2025