Independent Squares and Average-Radius Obstructions for Linear Codes

Overview

Abstract

We study binary-input average-radius list recovery using a configuration formed by independent affine squares sharing their origin. If an F_q-linear code in (F_q^s)^n has dimension k, then, for t≥1, c≥0, d=2t+c, and M=1+3t+c, it contains M distinct words and input lists of size at most two with mean relative error at most 1-2/M-min{2n,n+2tu,(4t+c)u}/(Mn), where k≥ d and u=⌊(k-d)/s⌋. Allocating unequal shortening groups can strengthen the equal-group bound; the asymptotic improvement occurs when coloop directions are present. For sixteen words this gives the asymptotic converse 7/8-(5/4)min{R,1/10}, uniformly in the folding parameter and field. We also prove that the associated all-field two-fiber intersection-dimension certificate has exact cost 4t+c. Finally, standard full-length folded Reed–Solomon codes realize the sixteen-word profile with mean error exactly 3/4, including families at the fixed rate 5/48 and arbitrarily large folding and length. These results rule out the average-radius extrapolation of the Boolean-cube curve for output cap fifteen, and analogous extrapolations for larger power-of-two lists. They do not refute the ordinary list-recovery conjecture of Chen and Zhang. The increment is the sparse independent-square profile and its sharp certificate calculation; shortening, independent kernel representatives, and local-profile methods have established predecessors.

Keywords average-radius list recovery · linear codes · folded Reed–Solomon codes · independent affine squares · two-fiber certificates