Enumeration of non-crossing pairings on bit strings

A non-crossing pairing on a bit string is a matching of 1s and 0s in the string with the property that the pairing diagram has no crossings. For an arbitrary bit-string w=p₁¹q₁⁰…pr¹qr⁰, let φ(w) be the number of such pairings. This enumeration problem arises when calculating moments in the theory of random matrices and free probability, and we are interested in determining useful formulas and asymptotic estimates for φ(w). Our main results include explicit formulas in the “symmetric” case where each pi=qi, as well as upper and lower bounds for φ(w) that are uniform across all words of fixed length and fixed r. In addition, we offer more refined conjectural expressions for the upper bounds. Our proofs follow from the construction of combinatorial mappings from the set of non-crossing pairings into certain generalized “Catalan” structures that include labeled trees and lattice paths.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Solving linear systems via Pfaffians

An explicit solution is given for the system of linear equations EφE^t=φ^′, where φ, φ^′ are alternating matrices of Pfaffian 1, which at most differ in their first row and column, and E is of the form . If v, v^′, w∈R^r+1 with 〈v,w〉=1=〈v^′,w〉 then a sequence of Cohn transforms with respect to (the fixed) w which takes (v,w) to (v^′,w) is prescribed.     

Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g noncommutative variables x=(x₁,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r for which there is an ?>0 such that if X=(X₁,…,Xg) is a g-tuple of n×n symmetric matrices satisfying

     

Extensions of convex and semiconvex functions and intervally thin sets

We call A⊂RNintervally thin if for all x,y∈RN and ε>0 there exist x^′∈B(x,ε), y^′∈B(y,ε) such that [x^′,y^′]∩A=∅. Closed intervally thin sets behave like sets with measure zero (for example such a set cannot “disconnect” an open connected set). Let us also mention that if the (N−1)-dimensional Hausdorff measure of A is zero, then A is intervally thin. A function f is preconvex if it is convex on every convex subset of its domain. The consequence of our main theorem is the following: Let U be an open subset ofRNand let A be a closed intervally thin subset of U. Then every preconvex functioncan be uniquely extended (with preservation of preconvexity) onto U. In fact we show that a more general version of this result holds for semiconvex functions.     

Polynomial sequences of bounded operators

The basic results of spectral theory are obtained using the sequence of powers of a bounded linear operator T,T²,…,Tⁿ,…. In this paper, we replace the powers Tⁿ by certain polynomials p_n(T), and make use of special properties of the polynomial sequence to derive some new results concerning operators. For example, using an arbitrary polynomial sequence , we obtain “binomial” spectral radii and semidistances, which reduce, in the case of the sequence of powers, to the usual spectral radius and semidistance.     

Good distance graphs and the geometry of matrices

Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V^′,∼^′) be two good distance graphs, and φ:V→V^′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩Z_D|?3 and D is not a field of characteristic 2 with D=F, where and Z_D is the center of D. Let H_n(n?2) be the set of n×n Hermitian matrices over D. It is proved that (H_n,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈H_n.     

Crossed-products by finite index endomorphisms and KMS states

Given a unital -algebra A, an injective endomorphism preserving the unit, and a conditional expectation E from A to the range of α we consider the crossed-product of A by α relative to the transfer operator L=α⁻¹E. When E is of index-finite type we show that there exists a conditional expectation G from the crossed-product to A which is unique under certain hypothesis. We define a “gauge action” on the crossed-product algebra in terms of a central positive element h and study its KMS states. The main result is: if h>1 and E(ab)=E(ba) for all a,b∈A (e.g. when A is commutative) then the KMS_β states are precisely those of the form ψ=φ°G, where φ is a trace on A satisfying the identity

     

Unboundedness of the large solutions of an asymmetric oscillator

In this paper, we consider the unboundedness problem of solutions for the following asymmetric oscillator:

(φp(x^′)^)′+(p−1)[αφp(x⁺)−βφp(x⁻)]=f(x,x^′,t),     

Nonlinear abstract differential equations with deviated argument

In this paper we consider the nonlinear differential equation with deviated argument u^′(t)=Au(t)+f(t,u(t),u[φ(u(t),t)]), t∈R₊, in a Banach space (X,‖⋅‖), where A is the infinitesimal generator of an analytic semigroup. Under suitable conditions on the functions f and φ, we prove a global existence and uniqueness result for the above equation.     

A new characterization of dual bases in finite fields and its applications

We propose a new characterization of dual bases in finite fields. Let A=(α₁,…,α_n) be a basis of F over F_q and its dual basis B=(β₁,…,β_n) with the transition matrix C∈GL_n(F_q) such that (β₁,…,β_n)=(α₁,…,α_n)C. We show that holds for all 1?k?n, where T_k∈M_n(F_q) satisfies α_k(α₁,…,α_n)=(α₁,…,α_n)T_k. Conversely, suppose F=F_q(α_k^′) and for some 1?k^′?n and G∈GL_n(F_q), then B is equivalent to (α₁,…,α_n)G. As applications, we can construct the dual basis of a given basis A or determine whether the dual basis of A satisfies the desired conditions from T_k. This generalizes the results obtained by Liao and Sun for normal bases. Furthermore, we give a simple proof of the theorem of Gollmann, Wang and Blake for polynomial bases.     

On the homology of elementary Abelian groups as modules over the Steenrod algebra

We examine the dual of the so-called “hit problem”, the latter being the problem of determining a minimal generating set for the cohomology of products of infinite projective spaces as a module over the Steenrod Algebra A at the prime 2. The dual problem is to determine the set of A-annihilated elements in homology. The set of A-annihilateds has been shown by David Anick to be a free associative algebra. In this note we prove that, for each k≥0, the set of kpartiallyA-annihilateds, the set of elements that are annihilated by Sqⁱ for each i≤2^k, itself forms a free associative algebra.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Interpretation of De Finetti coherence criterion in ?ukasiewicz Logic

De Finetti gave a natural definition of “coherent probability assessment” β:E→[0,1] of a set E={X₁,…,X_m} of “events” occurring in an arbitrary set W⊆[0,1]^E of “possible worlds”. In the particular case of yes-no events, (where W⊆{0,1}^E), Kolmogorov axioms can be derived from his criterion. While De Finetti’s approach to probability was logic-free, we construct a theory Θ in infinite-valued ?ukasiewicz propositional logic, and show: (i) a possible world of W is a valuation satisfying Θ, (ii) β is coherent iff it is a convex combination of valuations satisfying Θ, (iii) iff β agrees on E with a state of the Lindenbaum MV-algebra of Θ, (iv) iff for some Borel probability measure μ on W. Thus ?ukasiewicz semantics, MV-algebraic (finitely additive) states, and (countably additive) Borel probability measures provide a universal representation of coherent assessments of events occurring in any conceivable set of possible worlds.     

On an integral-type operator from iterated logarithmic Bloch spaces into Bloch-type spaces

Let H(B) denote the space of all holomorphic functions on the open unit ball B of Cⁿ. Let φ=(φ₁,…,φ_n) be a holomorphic self-map of B and g∈H(B) such that g(0)=0. In this paper we study the boundedness and compactness of the following integral-type operator, recently introduced by Xiangling Zhu and the second author

     

On the independence of Heegner points in the function field case

Let ∞ be a fixed place of a global function field k. Let E be an elliptic curve defined over k which has split multiplicative reduction at ∞ and fix a modular parametrization ΦE:X₀(N)→E. Let be Heegner points associated to the rings of integers of distinct quadratic “imaginary” fields K₁,…,Kr over (k,∞). We prove that if the “prime-to-2p” part of the ideal class numbers of ring of integers of K₁,…,Kr are larger than a constant C=C(E,ΦE) depending only on E and ΦE, then the points P₁,…,Pr are independent in . Moreover, when k is rational, we show that there are infinitely many imaginary quadratic fields for which the prime-to-2p part of the class numbers are larger than C.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.