Highly nonlinear functions over finite fields

We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from Fqn to Fq to the set of affine functions from Fqn to Fq. We prove the conjecture for each q such that the characteristic of Fq lies in a subset of the primes with density 1 an...

Full description

Saved in:
Bibliographic Details
Published in:Finite fields and their applications 2020-03, Vol.63, p.101640, Article 101640
Main Author: Schmidt, Kai-Uwe
Format: Article
Language:English
Subjects:
Covering radius
Finite fields
Nonlinearity
Reed-Muller codes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from Fqn to Fq to the set of affine functions from Fqn to Fq. We prove the conjecture for each q such that the characteristic of Fq 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 [qn,n+1] Reed-Muller code over Fq 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.
ISSN:1071-5797
1090-2465
DOI:10.1016/j.ffa.2020.101640