Positive definite symmetric functions on linear spaces

If Φ is a positive definite function on a real linear space E of infinite dimension and Φ enjoys certain symmetry conditions we are able to show that Φ is expressible as a certain Laplace-Stieltjes transform. Conversely, if Φ is given by such a transform we can often show that Φ is positive definite on E. In particular, our results apply to the L^p spaces, 0 < p < ∞, as well as to other Orlicz spaces. We also are able to show that the only positive definite continuous sup-norm symmetric functions on C(T), the space of bounded real continuous functions on T, are constants whenever C(T) contains a sequence of functions with sup-norm one and disjoint support. Finally, we apply these ideas to obtain a result on radial exponentially convex functions on a Hilbert space.     

On approximation of a function and its derivatives by a polynomial and its derivatives

Let g∈C~q[-1, 1] be such that g~((k))(±1)=0 for k=0,…,q. Let P_n be an algebraic polynomialof degree at most n, such that P_n~((k))(±1)=0 for k=0,…,[_2~ (q+1)]. Then P_n and its derivativesP_n~((k)) for k≤q well approximate g and its respective derivatives, provided only that P_n well approxi-mates g itself in the weighted norm ‖g(x)-P_n(x) (1-x~2)~(1/2)~q‖This result is easily extended to an arbitrary f∈C~q[-1, 1], by subtracting from f the polynomial ofminnimal degree which interpolates f~((0))…,f~((q)) at±1. As well as providing easy criteria for judging the simultaneous approximation properties of a givenPolynomial to a given function, our results further explain the similarities and differences betweenalgebraic polynomial approximation in C~q[-1, 1] and trigonometric polynomial approximation in thespace of q times differentiable 2π-periodic functions. Our proofs are elementary and basic in character,permitting the construction of actual error estimates for simultaneous approximation proedures for smallvalues of q.     

Representing positive definiteB-invariant functions of[FC] B − groups

The [FC]^? groups are characterized as those groups having “sufficiently many” continuous positive definite central functions with compact support.     

Convergence Rates of Padé and Padé-Type Approximants

A comparison is made between Padé and Padé-type approximants. LetQ_nbe thenth orthonormal polynomial with respect to a positive measureμwith compact support inC. We show that for functions of the form[formula]wherewis an analytic function on the support ofμ, Padé-type approximants with denominatorQ_ngive a successful and, in general, better approximation procedure than Padé approximation.     

Detection of positive roots of a polynomial with five parameters

We give a complete set of discriminatory criteria for a polynomial with five parameters to have a positive root. This polynomial arises from the characteristic equation of a difference equation Δⁿ(x_k+px_k−τ)+qx_k−σ=0, which is used to model population dynamics. Our investigations are self-contained and based on the theory of envelopes.     

LELONG-DEMAILLY NUMBERS IN TERMS OF CAPACITY AND WEAK CONVERGENCE FOR CLOSED POSITIVE CURRENTS

In this paper we give a new definition of the Lelong-Demailly number in terms of the CT-capacity, where T is a closed positive current and CT is the capacity associated to T. This derived from some esimate on the growth of the CT-capacity of the sublevel sets of a weighted plurisubharmonic （psh for short） function. These estimates enable us to give another proof of the Demailly＇s comparaison theorem as well as a generalization of some results due to Xing concerning the characterization of bounded psh functions. Another problem that we consider here is related to the existence of a psh function v that satisfies the equality CT（K） ： fK T ∧ （dd^cu）^p, where K is a compact subset. Finally, we give some conditions on the capacity CT that guarantees the weak convergence ukTk → uT, for positive closed currents T, Tk and psh functions uk, u.     

Reduction of variance for Gaussian densities via restriction to convex sets

Let X be a random vector with values in $\text{R}$ⁿ and a Gaussian density f. Let Y be a random vector whose density can be factored as k · f, where k is a logarithmically concave function on $\text{R}$ⁿ. We prove that the covariance matrix of X dominates the covariance matrix of Y by a positive semidefinite matrix. When k is the indicator function of a compact convex set A of positive measure the difference is positive definite. If A and X are both symmetric Var(a · X) is bounded above by an expression which is always strictly less than Var(a · X) for every a ∈ $\text{R}$ⁿ. Finally some counterexamples are given to show that these results cannot be extended to the general case where f is any logarithmically concave density.     

Read-Once Functions Revisited and the Readability Number of a Boolean Function

In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is 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-occurrance graph is P₄-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2^k function and a read 2^k formula for F for f can be obtained in polynomial time.     

Cardinal ECT-splines

Cardinal ECT-spline curves are generated from one ECT-system of order n which is shifted by integer translations via one connection matrix. If this matrix is nonsingular, lower triangular and totally positive, there exists an ECT-B-spline function N₀ⁿ(x) having minimal compact support [0,n] whose integer translates span the cardinal ECT-spline space. This B-spline is computed explicitly piece by piece. Involved is the characteristic polynomial of a certain matrix which is the product of a matrix related to the connection matrix and of the generalized Taylor matrix of the basic ECT-system. This approach extends results for polynomial cardinal splines via connection matrices [6] to the more general setting of cardinal ECT-splines. The method is illustrated by two examples based on ECT-systems of rational functions with prescribed poles. Also, a Greens function involved is expressed explicitly as an ECT-B-splines series. AMS subject classification 41A15, 41A05     

Independence roots and independence fractals of certain graphs

The independence polynomial of a graph G is the polynomial ∑i _k x ^k , where i _k denote the number of independent sets of cardinality k in G. In this paper, we obtain the relationships between the independence polynomial of path P _n and cycle C _n with Jacobsthal polynomial. We find all roots of Jacobsthal polynomial. As a consequence, the roots of independence polynomial of the family {P _n } and {C _n } are real and dense in $(-\infty,-\frac{1}{4}]$ . Also we investigate the independence fractals or independence attractors of paths, cycles, wheels and certain trees.     

Universal terms of complexity three

If there is a function g such that g ^m mapsX/C bijectively ontoX, wherem is a positive integer and whereC is a finite subset ofX, thenm is a factor of |C|. This fact serves to establish the necessary and sufficient conditions for the wordA ^kB^mAⁿ to represent the successor and the predecessor functions on ε. These conditions entail that there is no nontrivial point universal word of complexity three.     

A Family of Clique Divergent Graphs with Linear Growth

We present an infinite set A of finite graphs such that for any graph G e A the order | V(k ⁿ (G))| of the n-th iterated clique graph k ⁿ (G) is a linear function of n. We also give examples of graphs G such that | V(k ⁿ(G))| is a polynomial of any given positive degree.     

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.     

Satisfiability of mixed Horn formulas

In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time O(2^0.5284n). A strong argument showing that it is hard to improve a time bound of O(2^n/2) for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound O(∥C∥2^0.5284k). We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time O(2^0.5284n) if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas.     

Distance to Ck hypersurfaces

It is shown by elementary means that a C^k hypersurface M of positive reach in $\text{R}$^{n + 1} has the property that the signed distance function to it is C^k, k ? 1. This extends and complements work of Federer, Gilbarg and Trudinger, and Serrin.     

Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees

An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195-198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131-153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality.For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read 2^k function and a read 2^k formula for F can be obtained in polynomial time.     

Markov-Bernstein type inequalities of multivariate polynomials with positive coefficients and applications

The Cauchy’s formula of entire functions f:C^k→C is used to establish Markov-Bernstein type inequalities of multivariate polynomials with positive coeffeicients on the k-dimensional simplex T_k⊂R^k and on the cube [0,1]^k. The main results generalize and improve those of G.G. Lorentz, etc. Some applications of these inequalities are also considered in polynomial constrained approximation.     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Erratum to: “On the HSS iteration methods for positive definite Toeplitz linear systems” [J. Comput. Appl. Math. 224 (2009) 709-718]

In [1], Gu and Tian [Chuanqing Gu, Zhaolu Tian, On the HSS iteration methods for positive definite Toeplitz linear systems, J. Comput. Appl. Math. 224 (2009) 709-718] proposed the special HSS iteration methods for positive definite linear systems Ax=b with A∈C^n×n a complex Toeplitz matrix. But we find that the special HSS iteration methods are incorrect. Some examples are given in our paper.     

Topological vector spaces problems in homology and homotopy theories

Three data are interesting here: domains of integration, integrands and integration itself. There is a lack of symmetry between polyhedral chains as domains of integration and differential forms as integrands. The non-symmetric situation disappears after considering the topological spaces of the de Rham differential forms and forms with compact supports and their strong duals, i.e., currents with compact supports and currents, respectively. This idea goes back to Schwartz distributions and Schwartz distributions with compact supports, in other terminology, generalized functions and generalized functions with compact supports.Some problems are raised, e.g., whether every quasi-complete barreled nuclear space E, whose strongly dual E^′ is nuclear, is strongly hereditary reflexive. This concerns the above mentioned de Rham spaces. Problems on R- and Q-homotopy, proper R- and Q-homotopy and proper R- and Q-homotopy at infinity are also considered as well as the coalgebra structure on currents and currents with compact supports.The classical theorem concerning derivation of additive functions with respect to volumes in points is generalized to a theorem on derivation of continuous m-forms with compact supports ωm of an oriented n-dimensional C¹-manifold Mn with respect to its m-dimensional oriented submanifolds Vm in compact regular oriented submanifolds Lk of Mn, 0?k<m?n.