Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio
Abstract
K users each observe a fixed linear function of common data over a finite field of characteristic p, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe a, b and a+b and the server wants a+λb. The four functions span four lines in a plane with cross-ratio λ, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every λ, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, λ=−1, λ=2 or 2λ=1, it is $2$: every zero-error code reveals (a,b) to the server, so no code beats having two users send their observations. For λ outside the prime subfield it is the cut-set bound 3/2, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other λ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for λ outside the prime subfield. The four-line instance is also exact repair of one node of a [4,2] MDS storage code, and the results translate to that setting.
Related
- Privacy-Constrained Function Computation in Distributed Databases
- Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes
- An information-geometric formulation of distributed computation
- A negative solution to the complemented subspace problem for Banach spaces with unconditional bases
- Seshadri slope K-semistability for the blow-up of projective space along a linear subspace
BibTeX
@misc{sun2026capacity,
title = {{Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio}},
author = {Hua Sun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42023},
eprint = {2610.42023},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42023},
}
RIS
TY - UNPB
TI - Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio
AU - Hua Sun
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42023
UR - https://arxiv.org/abs/2610.42023
AB - K users each observe a fixed linear function of common data over a finite field of characteristic p, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe a, b and a+b and the server wants a+λb. The four functions span four lines in a plane with cross-ratio λ, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every λ, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, λ=−1, λ=2 or 2λ=1, it is $2$: every zero-error code reveals (a,b) to the server, so no code beats having two users send their observations. For λ outside the prime subfield it is the cut-set bound 3/2, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other λ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for λ outside the prime subfield. The four-line instance is also exact repair of one node of a [4,2] MDS storage code, and the results translate to that setting.
ER -