Characterizations of Bent and Almost Bent Function on {\mathbb{Z}_p^2}

Bent and almost-bent functions on \mathbbZ_p²{\mathbb{Z}_p^2} are studied in this paper. By calculating certain exponential sum and using a technique due to Hou (Finite Fields Appl 10:566–582, 2004), we obtain a degree bound for quasi-bent functions, and prove that almost-bent functions on \mathbbZ_p²{\mathbb{Z}_p^2} are equivalent to a degenerate quadratic form. From the viewpoint of relative difference sets, we also characterize bent functions on \mathbbZ_p²{\mathbb{Z}_p^2} in two classes of M{\mathcal{M}} ’s and PS{\mathcal{PS}} ’s, and show that the graph set corresponding to a bent function on \mathbbZ_p²{\mathbb{Z}_p^2} can be written as the sum of a graph set of M{\mathcal{M}} ’s type bent function and another group ring element. By using our characterization and some technique of permutation polynomial, we obtain the result: a bent function must be of M{\mathcal{M}} ’s type if its corresponding set contains more than (p − 3)/2 flats. A problem proposed by Ma and Pott (J Algebra 175:505–525, 1995) is therefore partially answered.     

Continuous piecewise linear finite elements for the Kirchhoff–Love plate equation

A family of continuous piecewise linear finite elements for thin plate problems is presented. We use standard linear interpolation of the deflection field to reconstruct a discontinuous piecewise quadratic deflection field. This allows us to use discontinuous Galerkin methods for the Kirchhoff–Love plate equation. Three example reconstructions of quadratic functions from linear interpolation triangles are presented: a reconstruction using Morley basis functions, a fully quadratic reconstruction, and a more general least squares approach to a fully quadratic reconstruction. The Morley reconstruction is shown to be equivalent to the basic plate triangle (BPT). Given a condition on the reconstruction operator, a priori error estimates are proved in energy norm and L ² norm. Numerical results indicate that the Morley reconstruction/BPT does not converge on unstructured meshes while the fully quadratic reconstruction show optimal convergence.     

Strongly regular graphs constructed from <Emphasis Type="Italic">p</Emphasis>-ary bent functions

In this paper, we generalize the construction of strongly regular graphs in Tan et al. (J. Comb. Theory, Ser. A 117:668–682, 2010) from ternary bent functions to p-ary bent functions, where p is an odd prime. We obtain strongly regular graphs with three types of parameters. Using certain non-quadratic p-ary bent functions, our constructions can give rise to new strongly regular graphs for small parameters.     

Maximum distance holey packings and related codes

The notion of a maximum distance holey packing is introduced and used to construct optimal ternary (n, 3, 3) codes for all lengthsn=2 (mod 3) andn≥8. Combining this with Etzion’s result, the existence problem for an optimal ternary (n,3,3) code is solved completely. Project supported by the National Natural Science Foundation of China (Grant No. 19671064).     

Convex Underestimation of Twice Continuously Differentiable Functions by Piecewise Quadratic Perturbation: Spline αBB Underestimators

This paper describes the construction of convex underestimators for twice continuously differentiable functions over box domains through piecewise quadratic perturbation functions. A refinement of the classical α BB convex underestimator, the underestimators derived through this approach may be significantly tighter than the classical αBB underestimator. The convex underestimator is the difference of the nonconvex function f and a smooth, piecewise quadratic, perturbation function, q. The convexity of the underestimator is guaranteed through an analysis of the eigenvalues of the Hessian of f over all subdomains of a partition of the original box domain. Smoothness properties of the piecewise quadratic perturbation function are derived in a manner analogous to that of spline construction.     

On superpositions of continuous functions defined on the baire space

For continuous functions specified on the Baire space, conditions for the representability of a function of several variables as a superposition of functions of a smaller number of variables are considered. With the use of linear functions of the form (1+α)t, a boundary value of the modulus of continuity separating the positive from the negative solution of the problem is found. For the case in which the problem has a negative solution, a constructive method for obtaining (n+1)-variable continuous functions with modulus of continuity ϕ(t) that are not representable as superposition ofn-variable continuous functions with the same modulus of continuity ϕ(t) is suggested. Translated fromMatermaticheskie Zametki, Vol. 66, No. 5, pp. 696–705, November, 1999.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.      

A simpler and tighter redundant Klee–Minty construction

By introducing redundant Klee–Minty examples, we have previously shown that the central path can be bent along the edges of the Klee–Minty cubes, thus having 2 ⁿ −2 sharp turns in dimension n. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and N, the total number of the redundant hyperplanes is reduced by a factor of n ², further tightening the gap between iteration-complexity upper and lower bounds.     

Classification of self dual quadratic bent functions

We classify all self dual and anti self dual quadratic bent functions in 2n variables under the action of the orthogonal group O(2n,\mathbb F₂){{O}(2n,\mathbb F_2)} . This is done through a classification of all 2n × 2n involutory alternating matrices over \mathbb F₂{\mathbb F_2} under the action of the orthogonal group. The sizes of the O(2n,\mathbb F₂){{O}(2n,\mathbb F_2)} -orbits of self dual and anti self dual quadratic bent functions are determined explicitly.     

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.     

On the equivalence of quadratic APN functions

Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to the APN Gold function x^2r+1{x^{2^r+1}} if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2 ⁿ where n ≡ 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function.     

Association Schemes Related to Kasami Codes and Kerdock Sets

Two new infinite series of imprimitive 5-class association schemes are constructed. The first series of schemes arises from forming, in a special manner, two edge-disjoint copies of the coset graph of a binary Kasami code (double error-correcting BCH code). The second series of schemes is formally dual to the first. The construction applies vector space duality to obtain a fission scheme of a subscheme of the Cameron-Seidel 3-class scheme of linked symmetric designs derived from Kerdock sets and quadratic forms over GF(2).     

One Approach to synthesizing predicate circuits on the basis of generalized variables

The asymptotic behavior of the Shannon’s function L _B(n) is studied for complexity of n-variable predicate implementation with the use of predicate circuits over arbitrary complete basis B. A new definition of the reduced weight of the predicate is introduced, regarding it as a solution of a specific linear programming problem based on a system of predicate’s generalized variables. New, more exact upper elements for L _B(n) in a number of bases are acquired by the means of special decompositions of initial predicates using universal sets of predicates constructed for circuits consisting of bases elements with minimal reduced weight.     

On Boolean functions with the sum of every two of them being bent

A set of Boolean functions is called a bent set if the sum of any two distinct members is a bent function. We show that any bent set yields a homogeneous system of linked symmetric designs with the same design parameters as those systems derived from Kerdock sets. Further we observe that there are bent sets of size equal to the square root of the Kerdock set size which consist of Boolean functions with arbitrary degrees.     

Construction of deletion correcting codes using generalized Reed–Solomon codes and their subcodes

A code is n-deletion correcting if it is possible to correct any n deletion of symbols having occurred in transmission of codewords. In this paper, we present explicit constructions of n-deletion correcting codes for arbitrary values of n using generalized Reed–Solomon codes and their subcodes.      

Gowers $$U_3$$ norm of some classes of bent Boolean functions

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Constant Weight Codes and Group Divisible Designs

The study of a class of optimal constant weight codes over arbitrary alphabets was initiated by Etzion, who showed that such codes are equivalent to special GDDs known as generalized Steiner systems GS(t,k,n,g) Etzion. This paper presents new constructions for these systems in the case t=2, k=3. In particular, these constructions imply that the obvious necessary conditions on the length n of the code for the existence of an optimal weight 3, distance 3 code over an alphabet of arbitrary size are asymptotically sufficient.     

A Generalization of the Classical <Emphasis Type="Italic">α</Emphasis>BB Convex Underestimation via Diagonal and Nondiagonal Quadratic Terms

The classical αBB method determines univariate quadratic perturbations that convexify twice continuously differentiable functions. This paper generalizes αBB to additionally consider nondiagonal elements in the perturbation Hessian matrix. These correspond to bilinear terms in the underestimators, where previously all nonlinear terms were separable quadratic terms. An interval extension of Gerschgorin’s circle theorem guarantees convexity of the underestimator. It is shown that underestimation parameters which are optimal, in the sense that the maximal underestimation error is minimized, can be obtained by solving a linear optimization model.     

Convergence theorems for the Birkhoff integral

We give sufficient conditions for the interchange of the operations of limit and the Birkhoff integral for a sequence (f _n ) of functions from a measure space to a Banach space. In one result the equi-integrability of f _n ’s is involved and we assume f _n → f almost everywhere. The other result resembles the Lebesgue dominated convergence theorem where the almost uniform convergence of (f _n ) to f is assumed.