Good cyclic codes and the uncertainty principle

  • Shai Evra

    Hebrew University, Jerusalem, Israel
  • Emmanuel Kowalski

    ETH Zürich, Switzerland
  • Alexander Lubotzky

    Hebrew University, Jerusalem, Israel
Good cyclic codes and the uncertainty principle cover
Download PDF

A subscription is required to access this article.


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 on some abelian group, either or its Fourier transform 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.

Cite this article

Shai Evra, Emmanuel Kowalski, Alexander Lubotzky, Good cyclic codes and the uncertainty principle. Enseign. Math. 63 (2017), no. 3/4, pp. 305–332

DOI 10.4171/LEM/63-3/4-4