The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

L’Enseignement Mathématique

Full-Text PDF (341 KB) | Metadata | Table of Contents | LEM summary
Volume 63, Issue 3/4, 2017, pp. 305–332
DOI: 10.4171/LEM/63-3/4-4

Published online: 2018-09-03

Good cyclic codes and the uncertainty principle

Shai Evra[1], Emmanuel Kowalski[2] and Alexander Lubotzky[3]

(1) Hebrew University, Jerusalem, Israel
(2) ETH Zürich, Switzerland
(3) Hebrew University, Jerusalem, Israel

A long standing problem in the area of error correcting codes asks whether there exist good cyclic codes. Most of the known results point in the direction of a negative answer.

e uncertainty principle is a classical result of harmonic analysis asserting that given a non-zero function $f$ on some abelian group, either $f$ or its Fourier transform $\hat{f}$ has large support.

In this note, we observe a connection between these two subjects. We point out that even a weak version of the uncertainty principle for elds of positive characteristic would imply that good cyclic codes do exist. We also provide some heuristic arguments supporting that this is indeed the case.

Keywords: Cyclic codes, uncertainty principles, finite abelian groups, primitive roots, Artin conjecture

Evra Shai, Kowalski Emmanuel, Lubotzky Alexander: Good cyclic codes and the uncertainty principle. Enseign. Math. 63 (2017), 305-332. doi: 10.4171/LEM/63-3/4-4