The uncertainty principle over finite fields

DOI10.1016/J.DISC.2021.112670MaRDI QIDQ2237244zbMATH OpenOpenAlexFDO

Authors Martino Borello, Patrick Solé

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

asymptotically good codesBCH boundcyclic codesMattson-Solomon polynomialuncertainty principle

Mathematics Subject Classification ID

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

Abstract: In this paper we study the uncertainty principle (UP) connecting a function over a finite field and its Mattson-Solomon polynomial, which is a kind of Fourier transform in positive characteristic. Three versions of the UP over finite fields are studied, in connection with the asymptotic theory of cyclic codes. We first show that no finite field satisfies the strong version of UP, introduced recently by Evra, Kowalsky, Lubotzky, 2017. A refinement of the weak version is given, by using the asymptotic Plotkin bound. A naive version, which is the direct analogue over finite fields of the Donoho-Stark bound over the complex numbers, is proved by using the BCH bound. It is strong enough to show that there exist sequences of cyclic codes of length $n$, arbitrary rate, and minimum distance $Omega(n^{a}lpha)$ for all $0<alpha<1/2$. Finally, a connection with Ramsey Theory is pointed out.

Recommendations

• Good cyclic codes and the uncertainty principle
• An uncertainty principle for function fields
• On uncertainty principles in the finite dimensional setting
• Some remarks on the discrete uncertainty principle
• Uncertainty in finite planes

Cites work

• Additive combinatorics
• An uncertainty principle for cyclic groups of prime order
• Fundamentals of Error-Correcting Codes
• Good cyclic codes and the uncertainty principle
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Inequalities for finite group permutation modules
• Is the class of cyclic codes asymptotically good?
• On sets of vectors of a finite vector space in which every subset of basis size is a basis
• On sets of vectors of a finite vector space in which every subset of basis size is a basis. II
• On the minimum distance of cyclic codes
• The Shift Bound for Abelian Codes and Generalizations of the Donoho-Stark Uncertainty Principle
• The uncertainty principle: Variations on a theme
• Uncertainty Principles and Signal Recovery

Cited in

(6)

• Good cyclic codes and the uncertainty principle
• On ideals in group algebras: an uncertainty principle and the Schur product
• Uncertainty principles and sum complexes
• High-entropy dual functions over finite fields and locally decodable codes
• Sign uncertainty principles and low-degree polynomials
• On an uncertainty principle for small index subgroups of finite fields

This page was built for publication: The uncertainty principle over finite fields

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