A feasible theory of truth over combinatory algebra

We define an applicative theory of truth _TPT${\mathsf{T}}_{\mathsf{PT}}$ which proves totality exactly for the polynomial time computable functions. _TPT${\mathsf{T}}_{\mathsf{PT}}$ has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system _TPT${\mathsf{T}}_{\mathsf{PT}}$ has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.     

On palindromic factorization of words

Given a finite word u, we define its palindromic length  _|u|pal${|u|}_{\mathrm{pal}}$ to be the least number n   such that u=_v1v2…_vn$u=v_1{v}_2\dots v_n$ with each _vi$v_i$ a palindrome. We address the following open question: let P be a positive integer and w   an infinite word such that _|u|pal?P${|u|}_{\mathrm{pal}}?P$ for every factor u of w. Must w be ultimately periodic? We give a partial answer to this question by proving that for each positive integer k, the word w must contain a k  -power, i.e., a factor of the form u^k$u^k$. In particular, w cannot be a fixed point of a primitive morphism. We also prove more: for each pair of positive integers k and l, the word w must contain a position covered by at least l distinct k-powers. In particular, w cannot be a Sierpinski-like word.     

Completely positive interpolations of compact,trace-class and Schatten-p class operators

Extending Li and Poon's results on interpolation problems for matrices, we give characterizations of the existence of a completely positive linear map _Φcp${\Phi }_{\mathrm{cp}}$ between compact (or Schatten-p class) operators sending a particular operator A to another B. It is shown that such a map exists if a multiple of the numerical range of A contains the numerical range of B. Given two commutative families of compact (or Schatten-p   class) operators {_Aα}$\{A_{\alpha }\}$ and {_Bα}$\{B_{\alpha }\}$, we provide sufficient and necessary conditions to ensure that we can choose a completely positive interpolation _Φcp${\Phi }_{\mathrm{cp}}$ to preserve trace and/or approximate units such that _Φcp(_Aα)=_Bα${\Phi }_{\mathrm{cp}}(A_{\alpha })=B_{\alpha }$ for all α.     

Exceptional collections of line bundles on projective homogeneous varieties

We construct new examples of exceptional collections of line bundles on the variety of Borel subgroups of a split semisimple linear algebraic group G$G$ of rank 2 over a field. We exhibit exceptional collections of the expected length for types _A2$A_2$ and _B2=_C2$B_2=C_2$ and prove that no such collection exists for type _G2$G_2$. This settles the question of the existence of full exceptional collections of line bundles on projective homogeneous G$G$-varieties for split linear algebraic groups G$G$ of rank at most 2.     

Polynomial numerical hulls of some normal matrices

In this note, polynomial numerical hulls of matrices of the form _A1⊕i_A2$A_1\oplus i{A}_2$, where _A1$A_1$ and _A2$A_2$ are Hermitian, are characterized.     

On additive-nilpotency of Jacobian matrices of polynomial maps

Let H:Cⁿ→Cⁿ$H:{\mathbb{C}}^n\to {\mathbb{C}}^n$ be a polynomial map, JH the Jacobian matrix of H  , and _VH$V_H$ the linear subspace of _Mn(C)$M_n(\mathbb{C})$ spanned by {JH(α)|α∈Cⁿ}$\{JH(\alpha )|\alpha \in {\mathbb{C}}^n\}$, the set of evaluated Jacobian matrices of H  . We describe the dimension of _VH$V_H$ through a power-linear Gorni–Zampieri mate of H, and give a numerical algorithm for computing this dimension and determining whether JH   is additive-nilpotent, i.e., whether _VH$V_H$ is a nilpotent subspace.     

On Mann iteration in Hilbert spaces

Let K$K$ be a compact convex subset of a real Hilbert space H$H$; T:K→K$T:K\to K$ a hemicontractive map. Let {_αn}$\left\{{\alpha }_n\right\}$ be a real sequence in [0,1] satisfying appropriate conditions; then for arbitrary _x0∈K$x_0\in K$, the sequence {_xn}$\left\{x_n\right\}$ defined iteratively by _xn=_αnxn−1+(1−_αn)T_xn$x_n={\alpha }_n{x}_{n-1}+(1-{\alpha }_n)T{x}_n$, n≥1$n\ge 1$ converges strongly to a fixed point of T$T$.     

A core-free semicovering of the Hawaiian Earring

The connected covering spaces of a connected and locally path-connected topological space X   can be classified by the conjugacy classes of those subgroups of _π1(X,x)${\pi }_1(X,x)$ which contain an open normal subgroup of _π1(X,x)${\pi }_1(X,x)$, when endowed with the natural quotient topology of the compact-open topology on based loops. There are known examples of semicoverings (in the sense of Brazas) that correspond to open subgroups which do not contain an open normal subgroup. We present an example of a semicovering of the Hawaiian Earring H$\mathbb{H}$ with corresponding open subgroup of _π1(H)${\pi }_1(\mathbb{H})$ which does not contain any   nontrivial normal subgroup of _π1(H)${\pi }_1(\mathbb{H})$.     

Global well-posedness and exponential decay rates for a KdV–Burgers equation with indefinite damping

We consider the KdV–Burgers equation _ut+_uxxx−_uxx+λu+u_ux=0$u_t+u_{xxx}-u_{xx}+\lambda u+u{u}_x=0$ and its linearized version _ut+_uxxx−_uxx+λu=0$u_t+u_{xxx}-u_{xx}+\lambda u=0$ on the whole real line. We investigate their well-posedness their exponential stability when λ is an indefinite damping.     

Non-homogeneous random walks on a semi-infinite strip

We study the asymptotic behaviour of Markov chains (_Xn,_ηn)$(X_n,{\eta }_n)$ on _Z+×S${\mathbb{Z}}_{+}\times S$, where _Z+${\mathbb{Z}}_{+}$ is the non-negative integers and S$S$ is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of _Xn$X_n$, and that, roughly speaking, _ηn${\eta }_n$ is close to being Markov when _Xn$X_n$ is large. This departure from much of the literature, which assumes that _ηn${\eta }_n$ is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for _Xn$X_n$ given _ηn${\eta }_n$. We give a recurrence classification in terms of increment moment parameters for _Xn$X_n$ and the stationary distribution for the large- X$X$ limit of _ηn${\eta }_n$. In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between _Xn$X_n$ (rescaled) and _ηn${\eta }_n$. Our results can be seen as generalizations of Lamperti’s results for non-homogeneous random walks on _Z+${\mathbb{Z}}_{+}$ (the case where S$S$ is a singleton). Motivation arises from modulated queues or processes with hidden variables where _ηn${\eta }_n$ tracks an internal state of the system.     

Relativization makes contradictions harder for Resolution

We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d)$\mathrm{Res}(d)$, as well as their tree-like versions, Res^?(d)${\mathrm{Res}}^{?}(d)$. The contradictions we use are natural combinatorial principles: the Least number principle  , _LNPn${\mathrm{LNP}}_n$ and an ordered variant thereof, the Induction principle  , _IPn${\mathrm{IP}}_n$.     

Effective Pólya semi-positivity for non-negative polynomials on the simplex

We consider homogeneous polynomials f∈R[_x1,…,_xn]$f\in \mathbb{R}[x_1,\dots ,x_n]$ which are non-negative on the standard simplex in Rⁿ${\mathbb{R}}^n$, and we obtain sufficient conditions for such an f   to be Pólya semi-positive, that is, all the coefficients of (_x1+?+_xn)^Nf$(x_1+?+x_n{)}^{N}f$ are non-negative for all sufficiently large positive integers N. Such sufficient conditions are expressed in terms of the vanishing orders of the monomial terms of f along the faces of the simplex. Our result also gives effective estimates on N   under such conditions. Moreover, we also show that any Pólya semi-positive polynomial necessarily satisfies a slightly weaker condition. In particular, our results lead to a simple characterization of the Pólya semi-positive polynomials in the low dimensional case when n?3$n?3$ as well as the case (in any dimension) when the zero set of the polynomial in the simplex consists of a finite number of points. We also discuss an application to the representations of non-homogeneous polynomials which are non-negative on a general simplex.     

Operator norm attainment and inner product spaces

In this paper we prove that a finite dimensional real normed linear space X$\mathbb{X}$ is an inner product space iff for any linear operator T   on X$\mathbb{X}$, T   attains its norm at _e1,_e2∈_SX$e_1,e_2\in S_{\mathbb{X}}$ implies T   attains its norm at span{_e1,_e2}∩_SX$\mathit{span}\{e_1,e_2\}\cap S_{\mathbb{X}}$.     

Permanents,Doty coalgebras and dominant dimension of Schur algebras

A (hidden) multiplication on _AZ(n,r)$A_{\mathbb{Z}}(n,r)$, the Z$\mathbb{Z}$-dual of the integral Schur algebra _SZ(n,r)$S_{\mathbb{Z}}(n,r)$ is explicitly constructed, possibly without a unit. The image of the multiplication map is shown to be spanned by bipermanents. Let k   be any field of characteristic p>0$p>0$. The image of the induced multiplication on _Ak(n,r)=_AZ(n,r)_⊗Zk$A_k(n,r)=A_{\mathbb{Z}}(n,r){\otimes }_{\mathbb{Z}}k$ turns out to coincide with the Doty coalgebra _Dn,r,p$D_{n,r,p}$ of truncated symmetric powers. Combined with a new straightening formula for bipermanents, it is proved that such a multiplication induces an isomorphism _Ak(n,r)_⊗Sk(n,r)Ak(n,r)≅_Ak(n,r)$A_k(n,r){\otimes }_{S_k(n,r)}{A}_k(n,r)\cong A_k(n,r)$ as _Sk(n,r)$S_k(n,r)$-bimodules if and only if r≤n(p−1)$r\le n(p-1)$, if and only if _Dn,r,p=_Ak(n,r)$D_{n,r,p}=A_k(n,r)$. As a result, _Sk(n,r)$S_k(n,r)$ is a gendo-symmetric algebra, and its dominant dimension is at least two and admits a combinatorial characterization as long as r≤n(p−1)$r\le n(p-1)$.     

On convergence of the inexact Rayleigh quotient iteration with MINRES

For the Hermitian inexact Rayleigh quotient iteration (RQI), we present a new general theory, independent of iterative solvers for shifted inner linear systems. The theory shows that the method converges at least quadratically under a new condition, called the uniform positiveness condition, that may allow the residual norm _ξk≥1${\xi }_k\ge 1$ of the inner linear system at outer iteration k+1$k+1$ and can be considerably weaker than the condition _ξk≤ξ<1${\xi }_k\le \xi <1$ with ξ$\xi$ a constant not near one commonly used in the literature. We consider the convergence of the inexact RQI with the unpreconditioned and tuned preconditioned MINRES methods for the linear systems. Some attractive properties are derived for the residuals obtained by MINRES. Based on them and the new general theory, we make a refined analysis and establish a number of new convergence results. Let ‖_rk‖$\Vert r_k\Vert$ be the residual norm of approximating eigenpair at outer iteration k$k$. Then all the available cubic and quadratic convergence results require _ξk=O(‖_rk‖)${\xi }_k=O\left(\Vert r_k\Vert \right)$ and _ξk≤ξ${\xi }_k\le \xi$ with a fixed ξ$\xi$ not near one, respectively. Fundamentally different from these, we prove that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that _ξk≤ξ${\xi }_k\le \xi$ with a constant ξ<1$\xi <1$ not near one, _ξk=1−O(‖_rk‖)${\xi }_k=1-O\left(\Vert r_k\Vert \right)$ and _ξk=1−O(‖_rk‖²)${\xi }_k=1-O\left({\Vert r_k\Vert }^2\right)$, respectively. The new convergence conditions are much more relaxed than ever before. The theory can be used to design practical stopping criteria to implement the method more effectively. Numerical experiments confirm our results.