Good cyclic codes and the uncertainty principle

DOI10.4171/LEM/63-3/4-4zbMATH Open1436.94116arXiv1703.01080OpenAlexW2963700193WikidataQ129299697 ScholiaQ129299697MaRDI QIDQ1624913FDOQ1624913

Alexander Lubotzky, Shai Evra, E. Kowalski

Publication date: 16 November 2018

Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)

Abstract: 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. The 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 $hatf$ 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 fields of positive characteristic would imply that good cyclic codes do exist. We also provide some heuristic arguments supporting that this is indeed the case.

Full work available at URL: https://arxiv.org/abs/1703.01080

zbMATH Keywords

cyclic codesprimitive rootsuncertainty principlesfinite abelian groupsArtin conjecture

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cyclic codes (94B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The uncertainty principle: A mathematical survey
• Quelques applications du théorème de densité de Chebotarev
• An uncertainty principle for cyclic groups of prime order
• Locally testable codes and PCPs of almost-linear length
• Uncertainty Principles and Signal Recovery
• Locally Testable Cyclic Codes
• Introduction to Coding Theory
• Artin's Primitive Root Conjecture – A Survey
• An uncertainty inequality for finite Abelian groups.
• ARTIN'S CONJECTURE FOR PRIMITIVE ROOTS
• On Artin's conjecture.
• Chebotarëv and his density theorem
• Is the class of cyclic codes asymptotically good?
• Long BCH codes are bad
• Generalized Vandermonde Determinants and Roots of Unity of Prime Order
• Inequalities for finite group permutation modules
• An uncertainty inequality for groups of order \(pq\)

Cited In (4)

• A modified Gilbert-Varshamov bound for self-dual quasi-twisted codes of index four
• Several classes of asymptotically good quasi-twisted codes with a low index
• On ideals in group algebras: an uncertainty principle and the Schur product
• The uncertainty principle over finite fields

This page was built for publication: Good cyclic codes and the uncertainty principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1624913)