Construction of bent functions from near-bent functions

We give a construction of bent functions in dimension 2m from near-bent functions in dimension 2m−1. In particular, we give the first ever examples of non-weakly-normal bent functions in dimensions 10 and 12, which demonstrates the significance of our construction.     

Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

CCZ-equivalence of bent vectorial functions and related constructions

We observe that the CCZ-equivalence of bent vectorial functions over ${{\bf F}_2^n}$ (n even) reduces to their EA-equivalence. Then we show that in spite of this fact, CCZ-equivalence can be used for constructing bent functions which are new up to EA-equivalence and therefore to CCZ-equivalence: applying CCZ-equivalence to a non-bent vectorial function F which has some bent components, we get a function F?? which also has some bent components and whose bent components are CCZ-inequivalent to the components of the original function F. Using this approach we construct classes of nonquadratic bent Boolean and bent vectorial functions.     

Laced Boolean functions and subset sum problems in finite fields

In this paper, we investigate some algebraic and combinatorial properties of a special Boolean function on n variables, defined using weighted sums in the residue ring modulo the least prime p≥n. We also give further evidence relating to a question raised by Shparlinski regarding this function, by computing accurately the Boolean sensitivity, thus settling the question for prime number values p=n. Finally, we propose a generalization of these functions, which we call laced functions, and compute the weight of one such, for every value of n.     

Duality between bent functions and affine functions

A Boolean function in an even number of variables is called bent if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We prove that there is a duality between bent functions and affine functions. Namely, we show that affine function can be defined as a Boolean function that is at the maximal possible distance from the set of all bent functions.     

n-point sets and graphs of functions

We prove that, for every n?2, there exists an n-point set (a plane set which hits every line in exactly n points) that is homeomorphic to the graph of a function from R to R; for n?4, there exist both 0-dimensional and 1-dimensional examples. This raises the question (which we do not answer) of whether n-point sets for different n's could be homeomorphic.     

Construction of bent functions via Niho power functions

A Boolean function with an even number n=2k of variables is called bent if it is maximally nonlinear. We present here a new construction of bent functions. Boolean functions of the form f(x)=tr(α₁x^d₁+α₂x^d₂), α₁,α₂,x∈F_2ⁿ, are considered, where the exponents d_i (i=1,2) are of Niho type, i.e. the restriction of x^d_i on F_2^k is linear. We prove for several pairs of (d₁,d₂) that f is a bent function, when α₁ and α₂ fulfill certain conditions. To derive these results we develop a new method to prove that certain rational mappings on F_2ⁿ are bijective.     

On Chebyshev functions and Klee functions

Associated to a lower semicontinuous function, one can define its proximal mapping and farthest mapping. The function is called Chebyshev (Klee) if its proximal mapping (farthest mapping) is single-valued everywhere. We show that the function f is 1/λ-hypoconvex if its proximal mapping Pλf is single-valued. When the function f is bounded below, and Pλf is single-valued for every λ>0, the function must be convex. Similarly, we show that the function f is 1/μ-strongly convex if the farthest mapping Qμf is single-valued. When the function is the indicator function of a set, this recovers the well-known Chebyshev problem and Klee problem in Rn. We also give an example illustrating that a continuous proximal mapping (farthest mapping) needs not be locally Lipschitz, which answers one open question by Hare and Poliquin.     

New integral representations of nth order convex functions

In this paper we give an integral representation of an n-convex function f in general case without additional assumptions on function f. We prove that any n-convex function can be represented as a sum of two (n+1)-times monotone functions and a polynomial of degree at most n. We obtain a decomposition of n-Wright-convex functions which generalizes and complements results of Maksa and Páles (2009) [13]. We define and study relative n-convexity of n-convex functions. We introduce a measure of n-convexity of f. We give a characterization of relative n-convexity in terms of this measure, as well as in terms of nth order distributional derivatives and Radon-Nikodym derivatives. We define, study and give a characterization of strong n-convexity of an n-convex function f in terms of its derivative f(n+1)(x) (which exists a.e.) without additional assumptions on differentiability of f. We prove that for any two n-convex functions f and g, such that f is n-convex with respect to g, the function g is the support for the function f in the sense introduced by W?sowicz (2007) [29], up to polynomial of degree at most n.     

New explicit solutions to the p-Laplace equation based on isoparametric foliations

In contrast to an infinite family of explicit examples of two-dimensional p-harmonic functions obtained by G. Aronsson in the late 80s, there is very little known about the higher-dimensional case. In this paper, we show how to use isoparametric polynomials to produce diverse examples of p-harmonic and biharmonic functions. Remarkably, for some distinguished values of p and the ambient dimension n this yields first examples of rational and algebraic p-harmonic functions. Moreover, we show that there are no p-harmonic polynomials of the isoparametric type. This supports a negative answer to a question proposed in 1980 by J. Lewis.     

Hyper-bent functions and cyclic codes

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2^n-1-2^n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PS_ap class, introduced by Dillon, up to the linear transformations x?δx, . Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code H_n with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of H_n and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PS_ap are some codewords of weight 2^n-1-2^n/2-1 of a subcode of H_n and we deduce that for some n, depending on the factorization of 2ⁿ-1, the only hyper-bent functions on n variables are the elements of the class , obtained from PS_ap by composing the functions by the transformations x?δx, δ≠0, and by adding constant functions. We prove that non- hyper-bent functions exist for n=4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n=12.     

A new construction of bent functions based on {\mathbb{Z}} -bent functions

Dobbertin has embedded the problem of construction of bent functions in a recursive framework by using a generalization of bent functions called ${\mathbb{Z}}$ -bent functions. Following his ideas, we generalize the construction of partial spreads bent functions to partial spreads ${\mathbb{Z}}$ -bent functions of arbitrary level. Furthermore, we show how these partial spreads ${\mathbb{Z}}$ -bent functions give rise to a new construction of (classical) bent functions. Further, we construct a bent function on 8 variables which is inequivalent to all Maiorana–McFarland as well as PS _ap type bents. It is also shown that all bent functions on 6 variables, up to equivalence, can be obtained by our construction.     

Restricted domains,arrow-social welfare functions and noncorruptible and non-manipulable social choice correspondences: The case of private alternatives

An n-person social choice problem is considered in which the alternatives are n dimensional vectors, with the ith component of such a vector being the part of the alternatives affecting individual i alone. Assuming that individuals are selfish (individual i must be indifferent between any two alternatives with the same components), that they may be indifferent among alternatives and that each individual may choose his preferences out of a different set of permissible preferences, we prove that any set of restricted domains of preferences admits an n person non-dictatorial Arrow-type social welfare function if and only if it admits a two-person Arrow-type social welfare function: we characterize all the sets of restricted domains of preferences which admit two-person Arrow-type social welfare functions (and therefore also admit n-person Arrow-type social welfare functions) and then we prove that we also characterized all the sets of restricted domains of preferences which admit nondictatorial, nonmanipulable, noncorruptible and rational social choice correspondences.     

The circle as an attractor of an iterated function system on the plane

We give an iterated function system (IFS) on the plane with the circle as attractor. In doing this, we also give a sufficient condition for radially contracting functions on the plane (or on Rn) to be a contraction. A counterexample shows that radial contractiveness is not enough to be a contraction.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

On the dual of a Coulter–Matthews bent function

Coulter–Matthews (CM) bent functions are from to defined by , where and (α,2n)=1. It is not known if these bent functions are weakly regular in general. In this paper, we show that when n is even and α=n+1 (or n−1), the CM bent function is weakly regular. Moreover, we explicitly determine the dual of the CM bent function in this case. The dual is a bent function not reported previously.     

Comparison of volumes of convex bodies in real, complex, and quaternionic spaces

The classical Busemann-Petty problem (1956) asks, whether origin-symmetric convex bodies in Rn with smaller hyperplane central sections necessarily have smaller volumes. It is known, that the answer is affirmative if n?4 and negative if n>4. The same question can be asked when volumes of hyperplane sections are replaced by other comparison functions having geometric meaning. We give unified analysis of this circle of problems in real, complex, and quaternionic n-dimensional spaces. All cases are treated simultaneously. In particular, we show that the Busemann-Petty problem in the quaternionic n-dimensional space has an affirmative answer if and only if n=2. The method relies on the properties of cosine transforms on the unit sphere. We discuss possible generalizations.     

On the univalence of derivatives of functions which are univalent in angular domains

We consider functions f that are univalent in a plane angular domain of angle απ, 0 < α ≤ 2. It is proved that there exists a natural number k depending only on α such that the kth derivatives f ^(k) of these functions cannot be univalent in this angle. We find the least of the possible values of for k. As a consequence, we obtain an answer to the question posed by Kir’yatskii: if f is univalent in the half-plane, then its fourth derivative cannot be univalent in this half-plane.