Limits on code length from algebraic geometry over large fields
Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus
Information Theory
Summary
Some special kinds of error-correcting codes come from shapes called algebraic curves. These codes can correct many mistakes, but the authors found limits on how long these codes can be compared to the size of the system they work over. Specifically, when certain size measures get large, the code length can’t be more than half the size of the underlying setting. The authors provide mathematical bounds that apply broadly to these codes regardless of details.
What this means in practice
- •For error correction engineers: Design error-correcting codes knowing that length cannot exceed half the field size under certain dimension growth conditions.
- •For cryptography system designers: Account for upper limits on code lengths when using algebraic geometry codes in secure communication protocols.
A theory result. No direct application yet.
Authors
Haojie Chen, Chuangqiang Hu, Guorui Ma
Abstract
We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.