On the fractional chromatic number of monotone self-dual Boolean functions

We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.     

Decompositions of functions and Dirichlet problems in the unit disc

In this paper, we establish a decomposition theorem for polyharmonic functions and consider its applications to some Dirichlet problems in the unit disc. By the decomposition, we get the unique solution of the Dirichlet problem for polyharmonic functions (PHD problem) and give a unified expression for a class of kernel functions associated with the solution in the case of the unit disc introduced by Begehr, Du and Wang. In addition, we also discuss some quasi-Dirichlet problems for homogeneous mixed-partial differential equations of higher order. It is worthy to note that the decomposition theorem in the present paper is a natural extension of the Goursat decomposition theorem for biharmonic functions.     

The nonexistence of near-extremal formally self-dual codes

A code is called formally self-dual if and have the same weight enumerators. There are four types of nontrivial divisible formally self-dual codes over , and . These codes are called extremal if their minimum distances achieve the Mallows-Sloane bound. S. Zhang gave possible lengths for which extremal self-dual codes do not exist. In this paper, we define near-extremal formally self-dual (f.s.d.) codes. With Zhang’s systematic approach, we determine possible lengths for which the four types of near-extremal formally self-dual codes as well as the two types of near-extremal formally self-dual additive codes cannot exist. In particular, our result on the nonexistence of near-extremal binary f.s.d. even codes of any even length n completes all the cases since only the case 8|n was dealt with by Han and Lee.      

On differentiability and analyticity of positive definite functions

We derive a set of differential inequalities for positive definite functions based on previous results derived for positive definite kernels by purely algebraic methods. Our main results show that the global behavior of a smooth positive definite function is, to a large extent, determined solely by the sequence of even-order derivatives at the origin: if a single one of these vanishes then the function is constant; if they are all non-zero and satisfy a natural growth condition, the function is real-analytic and consequently extends holomorphically to a maximal horizontal strip of the complex plane.     

Strictly positive definite functions on a compact group

We recognize a result of Schreiner, concerning strictly positive definite functions on a sphere in an Euclidean space, as a generalization of Bochner's theorem for compact groups.

     

Regular symmetric groups of boolean functions

We show that with the exception of four known cases: C₃, C₄, C₅, and , all regular permutation groups can be represented as symmetric groups of boolean functions. This solves the problem posed by A. Kisielewicz in the paper [A. Kisielewicz, Symmetry groups of boolean functions and constructions of permutation groups, J. Algebra 199 (1998) 379-403]. A slight extension of our proof yields the same result for semiregular groups.     

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 a new condition for strictly positive definite functions on spheres

Recently, Xu and Cheney (1992) have proved that if all the Legendre coefficients of a zonal function defined on a sphere are positive then the function is strictly positive definite. It will be shown in this paper that, even if finitely many of the Legendre coefficients are zero, the strict positive definiteness can be assured. The results are based on approximation properties of singular integrals, and provide also a completely different proof of the results of Xu and Cheney.

     

Self-duality of bounded monotone boolean functions and related problems

In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k literals can be determined in O(2^k2k²n) time. This implies an O(n²logn) algorithm for determining the self-duality of -DNF functions. We also consider the version where any two disjuncts have at most c literals in common. For this case we give an O(n^4(c+1)) algorithm for determining self-duality.     

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.     

New extremal binary self-dual codes of length 68 from generalized neighbors

In this work, we use the concept of distance between self-dual codes, which generalizes the concept of a neighbor for self-dual codes. Using the k-neighbors, we are able to construct extremal binary self-dual codes of length 68 with new weight enumerators. We construct 143 extremal binary self-dual codes of length 68 with new weight enumerators including 42 codes with $\gamma =8$ in their $W_{68,2}$ and 40 with $\gamma =9$ in their $W_{68,2}$. These examples are the first in the literature for these γ values. This completes the theoretical list of possible values for γ in $W_{68,2}$.     

Decompositions of the free additive convolution

We introduce and study a new type of convolution of probability measures, denoted μν and called the s-free additive convolution, which is defined by the subordination functions associated with the free additive convolution. We derive an alternating decomposition of μν for compactly supported μ and ν, using another convolution called orthogonal additive convolution. This decomposition leads to two types of ‘complete’ alternating decompositions of the free additive convolution μ?ν. More importantly, we develop an operatorial approach to the subordination property and introduce the associated notion of s-free independence. Moreover, we establish relations between convolutions associated with the main notions of noncommutative independence (free, monotone and boolean). Finally, our result leads to natural decompositions of the free product of rooted graphs.     

Interlacing of positive real zeros of Bessel functions

We unify the three distinct inequality sequences (Abramowitz and Stegun (1972) [1, 9.5.2]) of positive real zeros of Bessel functions into a single one.     

On common linear copositive Lyapunov functions for pairs of stable positive linear systems

We study the common linear copositive Lyapunov functions of positive linear systems. Firstly, we present a theorem on pairs of second order positive linear systems, and give another proof of this theorem by means of properties of geometry. Based on the process of the proof, we extended the results to a finite number of second order positive linear systems. Then we extend this result to third order systems. Finally, for higher order systems, we give some results on common linear copositive Lyapunov functions.     

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.     

On interpolation with products of positive definite functions

In this paper we consider the problem of scattered data interpolation for multivariate functions. In order to solve this problem, linear combinations of products of positive definite kernel functions are used. The theory of reproducing kernels is applied. In particular, it follows from this theory that the interpolating functions are solutions of some varational problems.     

The cone of positive harmonic functions for scale-invariant diffusions

Consider a scale invariant diffusion whose state space is a closed cone in R ^d , minus the vertex. Then the process is either recurrent, transient to ∞ or transient to the vertex of the cone. In the latter case, the diffusion has finite lifetime (a.s.) and converges to the vertex at the lifetime. The Martin boundary consists of two points, and the corresponding minimal harmonic functions are of the form 1 and |x| ^α ψ(x/|x|).     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

Decompositions of Besov–Morrey spaces and Triebel–Lizorkin–Morrey spaces

The aim of this paper is to define the Besov–Morrey spaces and the Triebel– Lizorkin–Morrey spaces and to present a decomposition of functions belonging to these spaces. Our results contain an answer to the conjecture proposed by Mazzucato. The first author is supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. The second author is supported by Fūjyukai foundation and the 21st century COE program at Graduate School of Mathematical Sciences, the University of Tokyo.