Search

Planar functions are mappings from a finite field F q to itself with an extremal differential property. Such functions give rise to finite projective planes and other combinatorial objects. There is a subtle difference between the definitions of these functions depending on the parity of q and we consider the case that q is even. We classify polynomials of degree at most q 1 / 4 that induce planar functions on F q , by showing that such polynomials are precisely those in which the degree of every monomial is a power of two. As a corollary we obtain a complete classification of exceptional planar polynomials, namely polynomials over F q that induce planar functions on infinitely many extensions of F q. The proof strategy is to study the number of F q -rational points of an algebraic curve attached to a putative planar function. Our methods also give a simple proof of a new partial result for the classification of almost perfect nonlinear functions. [ABSTRACT FROM AUTHOR]

Abstract The largest Hamming distance between a Boolean function in n variables and the set of all affine Boolean functions in n variables is known as the covering radius ρ n of the [ 2 n , n + 1 ] Reed–Muller code. This number determines how well Boolean functions can be approximated by linear Boolean functions. We prove that lim n → ∞ ⁡ 2 n / 2 − ρ n / 2 n / 2 − 1 = 1 , which resolves a conjecture due to Patterson and Wiedemann from 1983. [ABSTRACT FROM AUTHOR]

The problem of constructing polynomials with all coefficients 1 or −1 and large merit factor (equivalently with small L 4 norm on the unit circle) arises naturally in complex analysis, condensed matter physics, and digital communications engineering. Most known constructions arise (sometimes in a subtle way) from difference sets, in particular from Paley and Singer difference sets. We consider the asymptotic merit factor of polynomials constructed from other difference sets, providing the first essentially new examples since 1991. In particular we prove a general theorem on the asymptotic merit factor of polynomials arising from cyclotomy, which includes results on Hall and Paley difference sets as special cases. In addition, we establish the asymptotic merit factor of polynomials derived from Gordon–Mills–Welch difference sets and Sidelnikov almost difference sets, proving two recent conjectures. [ABSTRACT FROM AUTHOR]

A hyperoval in the projective plane P 2 ( F q ) is a set of q + 2 points no three of which are collinear. Hyperovals have been studied extensively since the 1950s with the ultimate goal of establishing a complete classification. It is well known that hyperovals in P 2 ( F q ) are in one-to-one correspondence to polynomials with certain properties, called o-polynomials of F q . We classify o-polynomials of F q of degree less than 1 2 q 1 / 4 . As a corollary we obtain a complete classification of exceptional o-polynomials, namely polynomials over F q that are o-polynomials of infinitely many extensions of F q . [ABSTRACT FROM AUTHOR]

Abstract: Let be the set of symmetric bilinear forms on an m-dimensional vector space over , where q is a power of two. A subset Y of is called an -set if the difference of every two distinct elements in Y has rank at least d. Such objects are closely related to certain families of codes over Galois rings of characteristic four. An upper bound on the size of -sets is derived, and in certain cases, the rank distance distribution of an -set is explicitly given. Constructions of -sets are provided for all possible values of m and d. [ABSTRACT FROM AUTHOR]

We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from F q n to F q to the set of affine functions from F q n to F q. We prove the conjecture for each q such that the characteristic of 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 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. [ABSTRACT FROM AUTHOR]

Abstract: Littlewood asked how small the ratio (where denotes the norm on the unit circle) can be for polynomials having all coefficients in , as the degree tends to infinity. Since 1988, the least known asymptotic value of this ratio has been , which was conjectured to be minimum. We disprove this conjecture by showing that there is a sequence of such polynomials, derived from the Fekete polynomials, for which the limit of this ratio is less than . [Copyright &y& Elsevier]

Abstract: The identification of binary sequences with large merit factor (small mean-squared aperiodic autocorrelation) is an old problem of complex analysis and combinatorial optimization, with practical importance in digital communications engineering and condensed matter physics. We establish the asymptotic merit factor of several families of binary sequences and thereby prove various conjectures, explain numerical evidence presented by other authors, and bring together within a single framework results previously appearing in scattered form. We exhibit, for the first time, families of skew-symmetric sequences whose asymptotic merit factor is as large as the best known value (an algebraic number greater than 6.34) for all binary sequences; this is interesting in light of Golayʼs conjecture that the subclass of skew-symmetric sequences has asymptotically optimal merit factor. Our methods combine Fourier analysis, estimation of character sums, and estimation of the number of lattice points in polyhedra. [Copyright &y& Elsevier]