Monotone additive functions on shifted primes

Generalising a sixty year old result of Erdös, it is proved that an additive arithmetic function that is non-decreasing on the shifted primes is essentially a logarithm.     

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.     

Monotone insertion of lattice-valued functions

Insertion of lattice-valued functions in a monotone manner is investigated. For L a ⊲-separable completely distributive lattice (i.e. L admits a countable base which is free of supercompact elements), a monotone version of the Katětov-Tong insertion theorem for L-valued functions is established. We also provide a monotone lattice-valued version of Urysohn’s lemma. Both results yield new characterizations of monotonically normal spaces. Moreover, extension of lattice-valued functions under additional assumptions is shown to characterize also monotone normality. This research was supported by the MEyC and FEDER under grant MTM2006-14925-C02-02/ and by UPV05/101     

Influences of monotone Boolean functions

Recently, Keller and Pilpel conjectured that the influence of a monotone Boolean function does not decrease if we apply to it an invertible linear transformation. Our aim in this short note is to prove this conjecture.     

Compositional complexity of Boolean functions

We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations.     

Monotone matrix functions of successive orders

This paper extends a result obtained by Wigner and von Neumann. We prove that a non-constant real-valued function, , in where is an interval of the real line, is a monotone matrix function of order on if and only if a related, modified function is a monotone matrix function of order for every value of in , assuming that is strictly positive on .

     

On generalized Boolean functions i

In this paper we introduce the concept of generalized Boolean function. Such a function has its arguments and values in a Boolean algebra and can be written in a manner similar to the canonical disjunctive form, but instead of the product of simple or complemented variables, the product of values of certain functions is used. Every Boolean function is a generalized Boolean one but the converse is not true. The set of all generalized Boolean function “generated” by some fixed function is a Boolean algebra.     

On generalized Boolean functions II

This cycle of papers is based on the concept of generalized Bolean functions introduced by the author in the first article of the series. Every generalized Boolean function f:Bⁿ→B can be written in a manner similar to the canonical disjunctive form using some function defined on A×B, where A is a finite subset of B containing 0 and 1. The set of those functions f is denoted by GBF_n[A]. In this paper the following questions are presented: (1) What is the relationship between GBF_n[A₁] and GBF_n[A₂] when A₁A₂. (2) What can be said about GBF_n[A₁∩A₂] and GBF_n[A₁A₂] in comparison with GBF_n[A₁]∩GBF_n[A₂] and GBF_n[A₁]GBF_n[A₂], respectively.     

Exclusion sensitivity of Boolean functions

Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study “exclusion sensitivity” of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d. dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.     

Dualization of regular Boolean functions

A monotonic Boolean function is regular if its variables are naturally ordered by decreasing ‘strength’, so that shifting to the right the non-zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.     

Approximating Boolean functions by OBDDs

In learning theory and genetic programming, OBDDs are used to represent approximations of Boolean functions. This motivates the investigation of the OBDD complexity of approximating Boolean functions with respect to given distributions on the inputs. We present a new type of reduction for one-round communication problems that is suitable for approximations. Using this new type of reduction, we improve a known lower bound on the size of OBDD approximations of the hidden weighted bit function for uniformly distributed inputs to an asymptotically tight bound and prove new results about OBDD approximations of integer multiplication and squaring for uniformly distributed inputs.     

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.     

Monotone thematic factorizations of matrix functions

We continue the study of the so-called thematic factorizations of admissible very badly approximable matrix functions. These factorizations were introduced by V.V. Peller and N.J. Young for studying superoptimal approximation by bounded analytic matrix functions. Even though thematic indices associated with a thematic factorization of an admissible very badly approximable matrix function are not uniquely determined by the function itself, R.B. Alexeev and V.V. Peller showed that the thematic indices of any monotone non-increasing thematic factorization of an admissible very badly approximable matrix function are uniquely determined. In this paper, we prove the existence of monotone non-decreasing thematic factorizations for admissible very badly approximable matrix functions. It is also shown that the thematic indices appearing in a monotone non-decreasing thematic factorization are not uniquely determined by the matrix function itself. Furthermore, we show that the monotone non-increasing thematic factorization gives rise to a great number of other thematic factorizations.     

Interior and exterior functions of positive Boolean functions

The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems -INTERIOR and -EXTERIOR, introduced therein. We first answer the question about the complexity of -INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231); it has no polynomial total time algorithm even if is bounded by a constant, unless P=NP. However, for positive h-term DNF functions with h bounded by a constant, problems -INTERIOR and -EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, -INTERIOR for two cases in which k=1, and and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.     

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.     

Explicit estimates of some functions over primes

New results have been found about the Riemann hypothesis. In particular, we noticed an extension of zero-free region and a more accurate location of zeros in the critical strip. The Riemann hypothesis implies results about the distribution of prime numbers. We get better effective estimates of common number theoretical functions which are closely linked to \(\zeta \) zeros like \(\psi (x),\vartheta (x),\pi (x)\), or the \(k\mathrm{{th}}\) prime number \(p_k\).     

Monotone transformations and differential properties of functions

The class of all real functions of a single variable which become everywhere differentiable after a certain homeomorphic transformation of coordinate axis is described. Moreover, various examples about differential properties of functions are given (in particular, an elementary construction of a nonconstant continuously differentiable real function of two variables, every value of which is critical-the example of Whitney, is given).Translated from Matematicheskie Zametki, Vol. 22, No. 6, pp. 859–871, December, 1977.The authors express gratitude to A. L. Brudno, P. L. Ul'yanov, and V. A. Skvortsov for discussion of the results given here.