On sesquilinear forms over fields with involution

Let k be a field of characteristic ≠2 with an involution σ. A matrix A is split if there is a change of variables Q such that (Q^σ)^TAQ consists of two complementary diagonal blocks. We classify all matrices that do not split. As a consequence we obtain a new proof for the following result. Given a square matrix A there is a matrix S such that (S^σ)^TAS=A^T and S^σS=I.     

Rank one perturbations at infinite coupling in Pontryagin spaces

In this paper we relate the operators in the operator representations of a generalized Nevanlinna function N(z) and of the function −N(z)⁻¹ under the assumption that z=∞ is the only (generalized) pole of nonpositive type. The results are applied to the Q-function for S and H and the Q-function for S and H^∞, where H is a self-adjoint operator in a Pontryagin space with a cyclic element w, H^∞ is the self-adjoint relation obtained from H and w via a rank one perturbation at infinite coupling, and S is the symmetric operator given by S=H∩H^∞.     

Hyperbolicity of arborescent tangles and arborescent links

In this paper, we study the hyperbolicity of arborescent tangles and arborescent links. We will explicitly determine all essential surfaces in arborescent tangle complements with non-negative Euler characteristic, and show that given an arborescent tangle T, the complement X(T) is non-hyperbolic if and only if T is a rational tangle, T=Qm*T^′ for some m?1, or T contains Qn for some n?2. We use these results to prove a theorem of Bonahon and Siebenmann which says that a large arborescent link L is non-hyperbolic if and only if it contains Q₂.     

Toroidal and Klein bottle boundary slopes

Let M be a compact, connected, orientable, irreducible 3-manifold and T₀ an incompressible torus boundary component of M such that the pair (M,T₀) is not cabled. By a result of C. Gordon, if (S,∂S),(T,∂T)⊂(M,T₀) are incompressible punctured tori with boundary slopes at distance Δ=Δ(∂S,∂T), then Δ?8, and the cases where Δ=6,7,8 are very few and classified. We give a simplified proof of this result (or rather, of its reduction process), using an improved estimate for the maximum possible number of mutually parallel negative edges in the graphs of intersection of S and T. We also extend Gordon's result by allowing either S or T to be an essential Klein bottle.     

A structured rank-revealing method for Sylvester matrix

We propose a fast algorithm for computing the numeric ranks of Sylvester matrices. Let S denote the Sylvester matrix and H   denote the Hankel-like-Sylvester matrix. The algorithm is based on a fast Cholesky factorization of S^TS$S^{\mathrm{T}}S$ or H^TH$H^{\mathrm{T}}H$ and relies on a stabilized version of the generalized Schur algorithm for matrices with displacement structure. All computations can be done in O(r(n+m))$\mathrm{O}(r(n+m))$, where n+m$n+m$ and r denote the size and the numerical rank of the Sylvester matrix, respectively.     

Lie algebras generated by bounded linear operators on Hilbert spaces

It is proved that the operator Lie algebra ε(T,T^∗) generated by a bounded linear operator T on Hilbert space H is finite-dimensional if and only if T=N+Q, N is a normal operator, [N,Q]=0, and dimA(Q,Q^∗)<+∞, where ε(T,T^∗) denotes the smallest Lie algebra containing T,T^∗, and A(Q,Q^∗) denotes the associative subalgebra of B(H) generated by Q,Q^∗. Moreover, we also give a sufficient and necessary condition for operators to generate finite-dimensional semi-simple Lie algebras. Finally, we prove that if ε(T,T^∗) is an ad-compact E-solvable Lie algebra, then T is a normal operator.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

On Generalized Friedrichs and Krein‐von Neumann Extensions and Canonical Systems

Let S be a densely defined and closed symmetric relation in a Hilbert space ℋ︁ with defect numbers (1,1), and let A be some of its canonical selfadjoint extensions. According to Krein's formula, to S and A corresponds a so‐called Q‐function from the Nevanlinna class N . In this note we show to which subclasses N _γ of N the Q‐functions corresponding to S and its canonical selfadjoint extensions belong and specify the Q‐functions of the generalized Friedrichs and Krein‐von Neumann extensions. A result of L. de Branges implies that to each function Q ∈ N there corresponds a unique Hamiltonian H such that Q is the Titchmarsh‐Weyl coefficient of the two‐dimensional canonical system J_y′ = —zHy on [0, ∞) where Weyl's limit point case prevails at ∞. Then the boundary condition y(0) = 0 corresponds to a symmetric relation T_min with defect numbers (1,1) in the Hilbert space L²_H, and Q is equal to the Q‐function with respect to the extension corresponding to the boundary condition y₁(0) = 0. If H satisfies some growth conditions at 0 or ∞, wepresent results on the corresponding Q‐functions and show under which conditions the generalized Friedrichs or Krein‐von Neumann extension exists.     

Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity

If S?{0,1};^* and S′ = {0,1}^*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A_n→A′_n with unique interpolants I_n that define S∩{0,1}ⁿ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T^p for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.     

A game semantics for disjunctive logic programming

Denotational semantics of logic programming and its extensions (by allowing negation, disjunctions, or both) have been studied thoroughly for many years. In 1998, a game semantics was given to definite logic programs by Di Cosmo, Loddo, and Nicolet, and a few years later it was extended to deal with negation by Rondogiannis and Wadge. Both approaches were proven equivalent to the traditional semantics. In this paper we define a game semantics for disjunctive logic programs and prove soundness and completeness with respect to the minimal model semantics of Minker. The overall development has been influenced by the games studied for PCF and functional programming in general, in the styles of Abramsky–Jagadeesan–Malacaria and Hyland–Ong–Nickau.     

A complete many-valued logic with product-conjunction

A simple complete axiomatic system is presented for the many-valued propositional logic based on the conjunction interpreted as product, the coresponding implication (Goguen's implication) and the corresponding negation (Gödel's negation). Algebraic proof methods are used. The meaning for fuzzy logic (in the narrow sense) is shortly discussed.This article was processed by the author using the LATEX style filepljorlm from Springer-Verlag.     

On the essential commutant of analytic Toeplitz operators associated with spherical isometries

Let T∈Bn(H) be an essentially normal spherical isometry with empty point spectrum on a separable complex Hilbert space H, and let AT⊂B(H) be the unital dual operator algebra generated by T. In this note we show that every operator S∈B(H) in the essential commutant of AT has the form S=X+K with a T-Toeplitz operator X and a compact operator K. Our proof actually covers a larger class of subnormal operator tuples, called A-isometries, which includes for example the tuple T=(Mz₁,…,Mzn)∈B(H²n(σ)) consisting of the multiplication operators with the coordinate functions on the Hardy space H²(σ) associated with the normalized surface measure σ on the boundary ∂D of a strictly pseudoconvex domain D⊂Cn. As an application we determine the essential commutant of the set of all analytic Toeplitz operators on H²(σ) and thus extend results proved by Davidson (1977) [6] for the unit disc and Ding and Sun (1997) [11] for the unit ball.     

Sémantique de type Kripke d'un système logique basé sur un ensemble ordonné fini

In order to modelize the reasoning of intelligent agents represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems the use of a set of constants constitutes a fundamental tool. We have introduced in [8] a logic system called without this kind of constants but limited to the case that T is a finite poset. We have proved a completeness result for this system w.r.t. an algebraic semantics. We introduce in this paper a Kripke‐style semantics for a subsystem of for which there existes a deduction theorem. The set of “possible worldsr is enriched by a family of functions indexed by the elements of T and satisfying some conditions. We prove a completeness result for system with respect to this Kripke semantics and define a finite Kripke structure that characterizes the propositional fragment of logic . We introduce a reational semantics (found by E. Orlowska) which has the advantage to allow an interpretation of the propositionnal logic using only binary relations. We treat also the computational complexity of the satisfiability problem of the propositional fragment of logic .     

Semidefinite descriptions of low-dimensional separable matrix cones

Let K⊂E, K^′⊂E^′ be convex cones residing in finite-dimensional real vector spaces. An element y in the tensor product E⊗E^′ is K⊗K^′-separable if it can be represented as finite sum , where x_l∈K and for all l. Let S(n), H(n), Q(n) be the spaces of n×n real symmetric, complex Hermitian and quaternionic Hermitian matrices, respectively. Let further S₊(n), H₊(n), Q₊(n) be the cones of positive semidefinite matrices in these spaces. If a matrix A∈H(mn)=H(m)⊗H(n) is H₊(m)⊗H₊(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m)⊗S(n), H(m)⊗S(n), and for m?2 in the space Q(m)⊗S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n)⊗S(2) is Q₊(n)⊗S₊(2)- separable if and only if it is positive semidefinite.     

A logic of implications in algebra and coalgebra

Implications in a category can be presented as epimorphisms: an object satisfies the implication iff it is injective with respect to that epimorphism. G. Ro?u formulated a logic for deriving an implication from other implications. We present two versions of implicational logics: a general one and a finitary one (for epimorphisms with finitely presentable domains and codomains). In categories Alg Σ of algebras on a given signature our logic specializes to the implicational logic of R. Quackenbush. In categories Coalg H of coalgebras for a given accessible endofunctor H of sets we derive a logic for implications in the sense of P. Gumm.     

Periods of principal homogeneous spaces of algebraic tori

A generic torsor of an algebraic torus S over a field F is the generic fiber of a S-torsor P → T, where P is a quasi-trivial torus containing S as a subgroup and T = P/S. The period of a generic S-torsor over a field extension K/F, i.e., the order of the class of the torsor in the group H ^p1(K, S) does not depend on the choice of a generic torsor. In the paper we compute the period of a generic torsor of S in terms of the character lattice of the torus S.     

Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

Asymptotic <Emphasis Type="Italic">T</Emphasis><Subscript><Emphasis Type="Italic">u</Emphasis></Subscript>-Toeplitzness of weighted composition operators on <Emphasis Type="Italic">H</Emphasis><Superscript>2</Superscript>

Given a unilateral forward shift S acting on a complex, separable, innite dimensional Hilbert space H, an asymptotically S-Toeplitz operator is a bounded linear operator T on H satisfying that {S* ⁿ TS ⁿ } is convergent with respect to one of the topologies commonly used in the algebra of bounded linear operators on H. In this paper, we study the asymptotic T _u -Toeplitzness of weighted composition operators on the Hardy space H², where u is a nonconstant inner function.     

Homogeneous tri-additive forms and derivations

Gleason [A.M. Gleason, The definition of a quadratic form, Amer. Math. Monthly 73 (1966) 1049-1066] determined all functionals Q on K-vector spaces satisfying the parallelogram law Q(x+y)+Q(x-y)=2Q(x)+2Q(y) and the homogeneity Q(λx)=λ²Q(x). Associated with Q is a unique symmetric bi-additive form S such that Q(x)=S(x,x) and 4S(x,y)=Q(x+y)-Q(x-y). Homogeneity of Q corresponds to that of S: S(λx,λy)=λ²S(x,y). The associated S is not necessarily bi-linear.Let V be a vector space over a field K, char(K)≠2,3. A tri-additive form T on V is a map of V³ into K that is additive in each of its three variables. T is homogeneous of degree 3 if T(λx,λy,λz)=λ³T(x,y,z) for all .We determine the structure of tri-additive forms that are homogeneous of degree 3. One of the keys to this investigation is to find the general solution of the functional equation

F(t)+t³G(1/t)=0,