MacWilliams duality and a Gleason-type theorem on self-dual bent functions

We prove that the MacWilliams duality holds for bent functions. It enables us to derive the concept of formally self-dual Boolean functions with respect to their near weight enumerators. By using this concept, we prove the Gleason-type theorem on self-dual bent functions. As an application, we provide the total number of (self-dual) bent functions in two and four variables obtaining from formally self-dual Boolean functions.     

On the degree of homogeneous bent functions

In this paper, the degree of homogeneous bent functions is discussed. We prove that for any nonnegative integer k, there exists a positive integer N such that for n?N there exist no 2n- variable homogeneous bent functions having degree n-k or more, where N is the least integer satisfying .     

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.     

Normal Boolean functions

Dobbertin (Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, Berlin, 1994, pp. 61–74) introduced the normality of bent functions. His work strengthened the interest for the study of the restrictions of Boolean functions on k-dimensional flats providing the concept of k-normality. Using recent results on the decomposition of any Boolean functions with respect to some subspace, we present several formulations of k-normality. We later focus on some highly linear functions, bent functions and almost optimal functions. We point out that normality is a property for which these two classes are strongly connected. We propose several improvements for checking normality, again based on specific decompositions introduced in Canteaut et al. (IEEE Trans. Inform. Theory, 47(4) (2001) 1494), Canteaut and Charpin (IEEE Trans. Inform. Theory). As an illustration, we show that cubic bent functions of 8 variables are normal.     

A refinement of Cusick-Cheon bound for the second order binary Reed-Muller code

We prove a stronger form of the conjectured Cusick-Cheon lower bound for the number of quadratic balanced Boolean functions. We also prove various asymptotic results involving B(k,m), the number of balanced Boolean functions of degree ≤k in m variables, in the case k=2. Finally, we connect our results for k=2 with the (still unproved) conjectures of Cusick-Cheon for the functions B(k,m) with k>2.     

Bent and generalized bent Boolean functions

In this paper, we investigate the properties of generalized bent functions defined on ${\mathbb{Z}_2^n}$ with values in ${\mathbb{Z}_q}$ , where q ≥ 2 is any positive integer. We characterize the class of generalized bent functions symmetric with respect to two variables, provide analogues of Maiorana–McFarland type bent functions and Dillon’s functions in the generalized set up. A class of bent functions called generalized spreads is introduced and we show that it contains all Dillon type generalized bent functions and Maiorana–McFarland type generalized bent functions. Thus, unification of two different types of generalized bent functions is achieved. The crosscorrelation spectrum of generalized Dillon type bent functions is also characterized. We further characterize generalized bent Boolean functions defined on ${\mathbb{Z}_2^n}$ with values in ${\mathbb{Z}_4}$ and ${\mathbb{Z}_8}$ . Moreover, we propose several constructions of such generalized bent functions for both n even and n odd.     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

The expressive power of voting polynomials

We consider the problem of approximating a Boolean functionf∶{0,1} ⁿ →{0,1} by the sign of an integer polynomialp of degreek. For us, a polynomialp(x) predicts the value off(x) if, wheneverp(x)≥0,f(x)=1, and wheneverp(x)<0,f(x)=0. A low-degree polynomialp is a good approximator forf if it predictsf at almost all points. Given a positive integerk, and a Boolean functionf, we ask, “how good is the best degreek approximation tof?” We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the casef is parity. Minsky and Papert [10] proved that a perceptron cannot compute parity; our bounds indicate exactly how well a perceptron canapproximate it. As a consequence, we are able to give the first correct proof that, for a random oracleA, PP ^A is properly contained in PSPACE ^A . We are also able to prove the old AC⁰ exponential-size lower bounds in a new way. This allows us to prove the new result that an AC⁰ circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

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.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Finding nonnormal bent functions

The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension n/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

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.     

On the Existence of Absolutely Simple Abelian Varieties of a Given Dimension over an Arbitrary Field

We prove that for every field k and every positive integer n there exists an absolutely simple n-dimensional abelian variety over k. We also prove an asymptotic result for finite fields: For every finite field k and positive integer n, we let S(k, n) denote the fraction of the isogeny classes of n-dimensional abelian varieties over k that consist of absolutely simple ordinary abelian varieties. Then for every n we have S(F_q, n)→1 as q→∞ over the prime powers.     

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.     

Orbits of rational n-sets of projective spaces under the action of the linear group

Let k=Fq be a finite field. We enumerate k-rational n-sets of (unordered) points in a projective space PN over k, and we compute the generating function for the numbers of PGLN+1(k)-orbits of these n-sets. For N=1,2 we obtain a formula for these numbers of orbits as a polynomial in q with integer coefficients.     

Latroids and their representation by codes over modules

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases.

In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these.

We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

On digit sums of multiples of an integer

Let g>1 be an integer and sg(m) be the sum of digits in base g of the positive integer m. In this paper, we study the positive integers n such that sg(n) and sg(kn) satisfy certain relations for a fixed, or arbitrary positive integer k. In the first part of the paper, we prove that if n is not a power of g, then there exists a nontrivial multiple of n say kn such that sg(n)=sg(kn). In the second part of the paper, we show that for any K>0 the set of the integers n satisfying sg(n)?Ksg(kn) for all k∈N is of asymptotic density 0. This gives an affirmative answer to a question of W.M. Schmidt.