Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915612731637760 |
|---|---|
| author | Cohen, Gil Doron, Dean Goldgraber, Noam Manket, Tomer |
| author_facet | Cohen, Gil Doron, Dean Goldgraber, Noam Manket, Tomer |
| contents | One of the oldest problems in coding theory is to match the Gilbert-Varshamov bound with explicit binary codes. Over larger-yet still constant-sized-fields, algebraic-geometry codes are known to beat the GV bound. In this work, we leverage this phenomenon by taking traces of AG codes. Our hope is that the margin by which AG codes exceed the GV bound will withstand the parameter loss incurred by taking the trace from a constant field extension to the binary field. In contrast to concatenation, the usual alphabet-reduction method, our analysis of trace-of-AG (TAG) codes uses the AG codes' algebraic structure throughout - including in the alphabet-reduction step.
Our main technical contribution is a Hasse-Weil-type theorem that is well-suited for the analysis of TAG codes. The classical theorem (and its Grothendieck trace-formula extension) are inadequate in this setting. Although we do not obtain improved constructions, we show that a constant-factor strengthening of our bound would suffice. We also analyze the limitations of TAG codes under our bound and prove that, in the high-distance regime, they are inferior to code concatenation. Our Hasse-Weil-type theorem holds in far greater generality than is needed for analyzing TAG codes. In particular, we derive new estimates for exponential sums. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08788 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound Cohen, Gil Doron, Dean Goldgraber, Noam Manket, Tomer Information Theory Computational Complexity Algebraic Geometry 11T71, 14H05, 14Q05, 11R58, 14H05 One of the oldest problems in coding theory is to match the Gilbert-Varshamov bound with explicit binary codes. Over larger-yet still constant-sized-fields, algebraic-geometry codes are known to beat the GV bound. In this work, we leverage this phenomenon by taking traces of AG codes. Our hope is that the margin by which AG codes exceed the GV bound will withstand the parameter loss incurred by taking the trace from a constant field extension to the binary field. In contrast to concatenation, the usual alphabet-reduction method, our analysis of trace-of-AG (TAG) codes uses the AG codes' algebraic structure throughout - including in the alphabet-reduction step. Our main technical contribution is a Hasse-Weil-type theorem that is well-suited for the analysis of TAG codes. The classical theorem (and its Grothendieck trace-formula extension) are inadequate in this setting. Although we do not obtain improved constructions, we show that a constant-factor strengthening of our bound would suffice. We also analyze the limitations of TAG codes under our bound and prove that, in the high-distance regime, they are inferior to code concatenation. Our Hasse-Weil-type theorem holds in far greater generality than is needed for analyzing TAG codes. In particular, we derive new estimates for exponential sums. |
| title | Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound |
| topic | Information Theory Computational Complexity Algebraic Geometry 11T71, 14H05, 14Q05, 11R58, 14H05 |
| url | https://arxiv.org/abs/2511.08788 |