Special functions arising from discrete Painlevé equations: A survey

This article is a survey on recent studies on special solutions of the discrete Painlevé equations, especially on hypergeometric solutions of the q-Painlevé equations. The main part of this survey is based on the joint work [K. Kajiwara, T. Masuda, M. Noumi, Y. Ohta, Y. Yamada, Hypergeometric solutions to the q-Painlevé equations, IMRN 2004 47 (2004) 2497–2521, K. Kajiwara, T. Masuda, M. Noumi, Y. Ohta, Y. Yamada, Construction of hypergeometric solutions to the q-Painlevé equations, IMRN 2005 24 (2005) 1439–1463] with Kajiwara, Masuda, Ohta and Yamada. After recalling some basic facts concerning Painlevé equations for comparison, we give an overview of the present status of studies on difference (discrete) Painlevé equations as a source of special functions.     

Decompositions of positive self-dual boolean functions

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f_c such that f_c(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a non-dominated (ND) coterie if and only if f_c is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f₁,f₂,…, f_k. In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f₁, and f₂, and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.     

Monotonic analysis: convergence of sequences of monotone functions

In this article we examine various kinds of convergence of sequences of increasing positively homogeneous (IPH) functions and nonnegative decreasing functions defined on the interior of a pointed closed solid convex cone K. We show that five different types of convergency (including pointwise and epi-convergence) coincide for IPH functions. If the space under consideration is finite dimensional then the sixth type can be added: uniform convergence on bounded subsets of itn K. Using IPH functions, we study epi-convergence of sequences of lower semi-continuous (lsc) nonnegative decreasing functions.     

On the Fourier tails of bounded functions over the discrete cube

In this paper we consider bounded real-valued functions over the discrete cube, f: {−1, 1}ⁿ → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the theory of social choice. It is often interesting to understand when these functions essentially depend on few coordinates. Our main result is a dichotomy that includes a lower bound on how fast the Fourier coefficients of such functions can decay: we show that

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 the probability of a rational outcome for generalized social welfare functions on three alternatives

In Kalai (2002) [10], Kalai investigated the probability of a rational outcome for a generalized social welfare function (GSWF) on three alternatives, when the individual preferences are uniform and independent. In this paper we generalize Kalai's results to a broader class of distributions of the individual preferences, and obtain new lower bounds on the probability of a rational outcome in several classes of GSWFs. In particular, we show that if the GSWF is monotone and balanced and the distribution of the preferences is uniform, then the probability of a rational outcome is at least 3/4, proving a conjecture raised by Kalai. The tools used in the paper are analytic: the Fourier-Walsh expansion of Boolean functions on the discrete cube, properties of the Bonamie-Beckner noise operator, and the FKG inequality.     

Recurrence relations for discrete hypergeometric functions

We present a general procedure for finding linear recurrence relations for the solutions of the second order difference equation of hypergeometric type. Applications to wave functions of certain discrete system are also given.     

Proof of a conjecture about rotation symmetric functions

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. We prove the conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed in Cusick and St?nic? (2002) [2] and its generalization, thus the nonlinearity of such functions is determined.     

Approximation of discrete functions and Chebyshev polynomials orthogonal on the uniform grid

Let _N+2m ={−m, −m+1, …, −1, 0, 1, …,N−1,N, …,N−1+m}. The present paper is devoted to the approximation of discrete functions of the formf : _N+2m → ℝ by algebraic polynomials on the grid Ω _N ={0, 1, …,N−1}. On the basis of two systems of Chebyshev polynomials orthogonal on the sets Ω _N+m and Ω _N , respectively, we construct a linear operatorY _{n+2m, N} =Y _{n+2m, N} (f), acting in the space of discrete functions as an algebraic polynomial of degree at mostn+2m for which the following estimate holds (x ε Ω _N ):

Constructions of strict Lyapunov functions for discrete time and hybrid time-varying systems

We provide explicit closed form expressions for strict Lyapunov functions for time-varying discrete time systems. Our Lyapunov functions are expressed in terms of known nonstrict Lyapunov functions for the dynamics and finite sums of persistency of excitation parameters. This provides a discrete time analog of our previous continuous time Lyapunov function constructions. We also construct explicit strict Lyapunov functions for systems satisfying nonstrict discrete time analogs of the conditions from Matrosov’s Theorem. We use our methods to build strict Lyapunov functions for time-varying hybrid systems that contain mixtures of continuous and discrete time evolutions.     

Decomposition and approximation of multivariate functions on the cube

In this paper, we present a decomposition method of multivariate functions. This method shows that any multivariate function f on [0, 1]d is a finite sum of the form ∑jφjψj , where each φj can be extended to a smooth periodic function, each ψj is an algebraic polynomial, and each φjψj is a product of separated variable type and its smoothness is same as f . Since any smooth periodic function can be approximated well by trigonometric polynomials, using our decomposition method, we find that any smooth multivariate function on [0, 1]d can be approximated well by a combination of algebraic polynomials and trigonometric polynomials. Meanwhile, we give a precise estimate of the approximation error.     

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.     

Completely monotone functions and the Wallis ratio

The aim of the paper is to improve known estimates of the Wallis ratio. Moreover, we show that these improvements are valid, because certain functions involving the continuous version of the Wallis ratio are completely monotone.     

Isometries on and monotone functions

We study necessary and sufficient conditions on a bounded operator T defined on the Hilbert space to be an isometry and show that, under suitable hypotheses, it suffices to restrict T to a smaller class of functions (e.g., if , to the cone of positive and decreasing functions). We also consider the problem of characterizing the sets for which the orthogonal projection of the operator T on is also an isometry. Finally, we illustrate our results with several examples involving classical operators on different settings.     

Double piling structure of matrix monotone functions and of matrix convex functions

There are basic equivalent assertions known for operator monotone functions and operator convex functions in two papers by Hansen and Pedersen. In this note we consider their results as correlation problem between two sequences of matrix n-monotone functions and matrix n-convex functions, and we focus the following three assertions at each label n among them:

(i) f(0)0 and f is n-convex in [0,α),

(ii) For each matrix a with its spectrum in [0,α) and a contraction c in the matrix algebra M_n,

f(cac)cf(a)c,