Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-069 | 8th April 2024 01:28

Character sums over AG codes


Authors: Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch
Publication: 10th April 2024 08:13
Downloads: 120


The Stepanov-Bombieri proof of the Hasse-Weil bound also gives non-trivial bounds on the bias of character sums over curves with small genus, for any low-degree function $f$ that is not completely biased. For high genus curves, and in particular for curves used in AG codes over constant size fields, the technique fails to prove any non-trivial result.

We significantly strengthen the Stepanov-Bombieri approach and obtain strong bounds on the bias of character sums over high genus curves. For example, we show that the bias of the quadratic character over the Hermitian function field is small, for any low-degree function $f$ with odd degree. Our results also give non-trivial results for the first levels of the Hermitian tower.

Technique-wise we analyze multiplicity in function fields in a better way, using a new 'universal derivative-fix' lemma we prove, building on the connection between derivatives and differentials in function fields.

ISSN 1433-8092 | Imprint