On the arithmetic Walsh coefficients of Boolean functions

We generalize to the arithmetic Walsh transform (AWT) some results which were previously known for the Walsh–Hadamard transform of Boolean functions. We first generalize the classical Poisson summation formula to the AWT. We then define a generalized notion of resilience with respect to an arbitrary statistical measure of Boolean functions. We apply the Poisson summation formula to obtain a condition equivalent to resilience for one such statistical measure. Last, we show that the AWT of a large class of Boolean functions can be expressed in terms of the AWT of a Boolean function of algebraic degree at most three in a larger number of variables.     

Algorithmic aspects of the substitution decomposition in optimization over relations,set systems and Boolean functions

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.     

Complete Fault Detection Tests of Length 2 for Logic Networks under Stuck-at Faults of Gates

We consider the problem of the synthesis of the logic networks implementing Boolean functions of n variables and allowing short complete fault detection tests regarding arbitrary stuck-at faults at the outputs of gates. We prove that there exists a basis consisting of two Boolean functions of at most four variables in which we can implement each Boolean function by a network allowing such a test with length at most 2.     

A novel algorithm enumerating bent functions

Based on the relationship between the Walsh spectra of a Boolean function at partial points and the Walsh spectra of its subfunctions, and on the binary Möbius transform, a novel algorithm is developed, which can theoretically construct all bent functions. Practically we enumerate all bent functions in 6 variables. With the restriction on the algebraic normal form, the algorithm is also efficient in more variables case. For example, enumeration of all homogeneous bent functions of degree 3 in 8 variables can be done in one minute with a P4 1.7 GHz computer; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is computationally proved.     

-functionals and multivariate Bernstein polynomials

This paper estimates upper and lower bounds for the approximation rates of iterated Boolean sums of multivariate Bernstein polynomials. Both direct and inverse inequalities for the approximation rate are established in terms of a certain K-functional. From these estimates, one can also determine the class of functions yielding optimal approximations to the iterated Boolean sums.     

Binary linear codes from vectorial boolean functions and their weight distribution

Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Binary terms in polynomial representations of Boolean functions

Polynomial representations of Boolean functions by binary terms are considered. The construction of terms involves variables and residual functions. Special cases of such representations are the decomposition of a function with respect to variables, Zhegalkin polynomials, and representations of functions as sums of conjunctions of residual functions.     

Convolution integral equations involving a general class of polynomials and the multivariableH-function

In this paper we first solve a convolution integral equation involving product of the general class of polynomials and theH-function of several variables. Due to general nature of the general class of polynomials and theH-function of several variables which occur as kernels in our main convolution integral equation, we can obtain from it solutions of a large number of convolution integral equations involving products of several useful polynomials and special functions as its special cases. We record here only one such special case which involves the product of general class of polynomials and Appell's functionF ₃. We also give exact references of two results recently obtained by Srivastavaet al [10] and Rashmi Jain [3] which follow as special cases of our main result.     

On isotone functions with the Substitution Property in distributive lattices

A universal algebra isaffine complete if all functions satisfying the Substitution Property are polynomials (composed of the basic operations and the elements of the algebra). In 1962, the first author proved that a bounded distributive lattice is affine complete if and only if it does not contain a proper Boolean interval. Recently, M. Ploica generalized this result to arbitrary distributive lattices.In this paper, we introduce a class of functions on a latticeL, we call themID-polynomials, that derive from polynomials on the ideal lattice (resp., dual ideal lattice) ofL; they are isotone functions and satisfy the Substitution Property. We prove that for a distributive latticeL, all unary functions with the Substitution Property are ID-polynomials if and only ifL contains no proper Boolean interval.The research of the first author was supported by the NSERC of Canada. The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

Refined estimates of the number of repetition-free boolean functions in the full binary basis {&, ∨, ⊕, −

We consider repetition-free Boolean functions in the basis {&, ∨, ⊕, ?}, and prove a formula expressing the number of such functions of n variables as a product of Fibonacci numbers. These products are estimated; as a result, we obtain asymptotic estimates for the number of repetition-free Boolean functions. These estimates involve Euler numbers of second order and can be reduced by well-known methods to the form of an exponential-power series. These estimates can be used to construct the final asymptotics of the number of repetition-free Boolean functions in the full binary basis.     

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.     

On Binary Resilient Functions

Using a lifting formula for the coefficients of Boolean functions, we characterize binary resilient functions as binary matrices with certain row or column intersection properties. We give some new constructions of binary resilient functions based on this characterization. In particular, we show that the incidence matrix of a Steiner system can be used to construct binary resilient functions.     

On Partial Classes Containig All Monotone and Zero-Preserving Total Boolean Functions

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ??(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ??(A) can be finite or infinite. We state some general results on ??(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.     

任意三角形域上的一种C~2插值方法

1.引言 平面上任意给出一组离散的数据点,经三角剖分后构成以三角形为基本单位的平面域,然后在每个三角形上进行插值,使之在这一平面域上达到一定的光滑连续阶。这一插值方法已经应用于CAGD和有限元,以及生物、医学、考古学等。1973年Barnhill等首次提出标准三角形(以(0,0),(1,0),(0,1)为顶点的三角形)上的插值逼近,他们构造     

Linear codes from simplicial complexes

In this article we introduce a method of constructing binary linear codes and computing their weights by means of Boolean functions arising from mathematical objects called simplicial complexes. Inspired by Adamaszek (Am Math Mon 122:367–370, 2015) we introduce n-variable generating functions associated with simplicial complexes and derive explicit formulae. Applying the construction (Carlet in Finite Field Appl 13:121–135, 2007; Wadayama in Des Codes Cryptogr 23:23–33, 2001) of binary linear codes to Boolean functions arising from simplicial complexes, we obtain a class of optimal linear codes and a class of minimal linear codes.     

An analogue of the big <Emphasis Type="Italic">q</Emphasis>-Jacobi polynomials in the algebra of symmetric functions

It is well known how to construct a system of symmetric orthogonal polynomials in an arbitrary finite number of variables from an arbitrary system of orthogonal polynomials on the real line. In the special case of the big q-Jacobi polynomials, the number of variables can be made infinite. As a result, in the algebra of symmetric functions, there arises an inhomogeneous basis whose elements are orthogonal with respect to some probability measure. This measure is defined on a certain space of infinite point configurations and hence determines a random point process.     

Monotone Boolean functions capture their primes

It is shown that monotone Boolean functions on the Boolean cube capture the expected number of primes, under the usual identification by binary expansion. This answers a question posed by G. Kalai.     

Downward closure of depth in countable Boolean algebras

We study the set of depths of relative algebras of countable Boolean algebras, in particular the extent to which this set may not be downward closed within the countable ordinals for a fixed countable Boolean algebra. Doing so, we exhibit a structural difference between the class of arbitrary rank countable Boolean algebras and the class of rank one countable Boolean algebras.