Good cyclic codes and the uncertainty principle

DOI10.4171/LEM/63-3/4-4MaRDI QIDQ1624913zbMATH OpenOpenAlexWikidataFDO

Authors Shai Evra, E. Kowalski, Alexander Lubotzky

Publication date 16 November 2018

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

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

zbMATH Keywords

Artin conjecturecyclic codesfinite abelian groupsprimitive rootsuncertainty principles

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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 \(\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 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.

Recommendations

• The uncertainty principle over finite fields
• Locally Testable Cyclic Codes
• Is the class of cyclic codes asymptotically good?
• The uncertainty principle and a generalization of a theorem of Tao
• Uncertainty principles and sum complexes

Cites work

• An uncertainty inequality for finite Abelian groups.
• An uncertainty inequality for groups of order \(pq\)
• An uncertainty principle for cyclic groups of prime order
• ARTIN'S CONJECTURE FOR PRIMITIVE ROOTS
• Artin's primitive root conjecture -- a survey
• Chebotarëv and his density theorem
• Generalized Vandermonde Determinants and Roots of Unity of Prime Order
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095850 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• scientific article; zbMATH DE number 7273775 (Why is no real title available?)
• Inequalities for finite group permutation modules
• Introduction to Coding Theory
• Is the class of cyclic codes asymptotically good?
• Locally testable codes and PCPs of almost-linear length
• Locally Testable Cyclic Codes
• Long BCH codes are bad
• On Artin's conjecture.
• Quelques applications du théorème de densité de Chebotarev
• The uncertainty principle: A mathematical survey
• Uncertainty Principles and Signal Recovery

Cited in

(8)

• 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
• A modified Gilbert-Varshamov bound for self-dual quasi-twisted codes of index four
• On an uncertainty principle for small index subgroups of finite fields
• Sequences of linear codes where the rate times distance grows rapidly
• Asymptotic performance of double circulant and four circulant codes with small hull dimension
• Product entropic uncertainty principle

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)