Highly nonlinear functions over finite fields

DOI10.1016/J.FFA.2020.101640MaRDI QIDQ2302588zbMATH OpenOpenAlexFDO

Authors Kai-Uwe Schmidt

Publication date 26 February 2020

Published in Finite Fields and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

finite fieldsnonlinearitycovering radiusReed-Muller codes

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05) Combinatorial codes (94B25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from $mathbb{F}_q^n$ to $mathbb{F}_q$ to the set of affine functions from $mathbb{F}_q^n$ to $mathbb{F}_q$. We prove the conjecture for each $q$ such that the characteristic of $mathbb{F}_q$ lies in a subset of the primes with density $1$ and we prove the conjecture for all $q$ by assuming the generalised Riemann hypothesis. Roughly speaking, we show the existence of functions for which the distance to the affine functions is maximised when $n$ tends to infinity. This also determines the asymptotic behaviour of the covering radius of the $[q^n,n+1]$ Reed-Muller code over $mathbb{F}_q$ and so answers a question raised by Leducq in 2013. Our results extend the case $q=2$, which was recently proved by the author and which corresponds to the original conjecture by Patterson and Wiedemann. Our proof combines evaluations of Gauss sums in the semiprimitive case, probabilistic arguments, and methods from discrepancy theory.

Recommendations

• Asymptotically optimal Boolean functions
• Highly nonlinear functions
• Hamming distances from a function to all codewords of a generalized Reed-Muller code of order one
• Sur la non-linéarité des fonctions booléennes
• scientific article; zbMATH DE number 1866873

Cites work

• scientific article; zbMATH DE number 51347 (Why is no real title available?)
• scientific article; zbMATH DE number 3539225 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class
• Asymptotically optimal Boolean functions
• Calculation of certain Gauss sums
• Complete solving of explicit evaluation of Gauss sums in the index 2 case
• Flat Polynomials on the unit Circle-Note on a Problem of Littlewood
• Multicolour Discrepancies
• New generalizations of the Reed-Muller codes--I: Primitive codes
• On equationap—bP 2=m
• On primes in arithmetic progression having a prescribed primitive root. II
• On the Covering Radius of First-Order Generalized Reed–Muller Codes
• On the covering radius of binary codes (Corresp.)
• On the equation b1 p - b2P2 = b3
• Six Standard Deviations Suffice
• The covering radius of the (128,8) Reed-Muller code is 56 (Corresp.)
• The covering radius of the<tex>(2^{15}, 16)</tex>Reed-Muller code is at least 16276

Cited in

(6)

• Resilient functions over finite fields
• scientific article; zbMATH DE number 1866873 (Why is no real title available?)
• High-entropy dual functions over finite fields and locally decodable codes
• Asymptotically optimal Boolean functions
• Hamming distances from a function to all codewords of a generalized Reed-Muller code of order one
• Pure Gauss sums and skew Hadamard difference sets

This page was built for publication: Highly nonlinear functions over finite fields

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