Sandwich semigroups in locally small categories I: foundations

Fix (not necessarily distinct) objects i and j of a locally small category S, and write \(S_{ij}\) for the set of all morphisms \(i\rightarrow j\). Fix a morphism \(a\in S_{ji}\), and define an operation \(\star _a\) on \(S_{ij}\) by \(x\star _ay=xay\) for all \(x,y\in S_{ij}\). Then \((S_{ij},\star _a)\) is a semigroup, known as a sandwich semigroup, and denoted by \(S_{ij}^a\). This article develops a general theory of sandwich semigroups in locally small categories. We begin with structural issues such as regularity, Green’s relations and stability, focusing on the relationships between these properties on \(S_{ij}^a\) and the whole category S. We then identify a natural condition on a, called sandwich regularity, under which the set \({\text {Reg}}(S_{ij}^a)\) of all regular elements of \(S_{ij}^a\) is a subsemigroup of \(S_{ij}^a\). Under this condition, we carefully analyse the structure of the semigroup \({\text {Reg}}(S_{ij}^a)\), relating it via pullback products to certain regular subsemigroups of \(S_{ii}\) and \(S_{jj}\), and to a certain regular sandwich monoid defined on a subset of \(S_{ji}\); among other things, this allows us to also describe the idempotent-generated subsemigroup \(\mathbb E(S_{ij}^a)\) of \(S_{ij}^a\). We also study combinatorial invariants such as the rank (minimal size of a generating set) of the semigroups \(S_{ij}^a\), \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\); we give lower bounds for these ranks, and in the case of \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\) show that the bounds are sharp under a certain condition we call MI-domination. Applications to concrete categories of transformations and partial transformations are given in Part II.     

Convergence and Precise Asymptotics for Series Involving Self-normalized Sums

Let \(X, X_{1}, X_{2}, \ldots \) be i.i.d. random variables, and set \(S_{n}=X_{1}+\cdots +X_{n}\) and \( V_{n}^{2}=X_{1}^{2}+\cdots +X_{n}^{2}.\) Without any moment conditions on \(X\), assuming that \(\{S_{n}/V_{n}\}\) is tight, we establish convergence of series of the type (*) \(\sum \nolimits _{n}w_{n}P(\left| S_{n}\right| /V_{n}\ge \varepsilon b_{n}),\) \(\varepsilon >0.\) Then, assuming that \(X\) is symmetric and belongs to the domain of attraction of a stable law, and choosing \(w_{n}\) and \(b_{n}\) suitably\(,\) we derive the precise asymptotic behavior of the series (*) as \(\varepsilon \searrow 0. \)     

Sampling and Cubature on Sparse Grids Based on a B-spline Quasi-Interpolation

Let \(X_n = \{x^j\}_{j=1}^n\) be a set of n points in the d-cube \({\mathbb {I}}^d:=[0,1]^d\), and \(\Phi _n = \{\varphi _j\}_{j =1}^n\) a family of n functions on \({\mathbb {I}}^d\). We consider the approximate recovery of functions f on \({{\mathbb {I}}}^d\) from the sampled values \(f(x^1), \ldots , f(x^n)\), by the linear sampling algorithm \( L_n(X_n,\Phi _n,f) := \sum _{j=1}^n f(x^j)\varphi _j. \) The error of sampling recovery is measured in the norm of the space \(L_q({\mathbb {I}}^d)\)-norm or the energy quasi-norm of the isotropic Sobolev space \(W^\gamma _q({\mathbb {I}}^d)\) for \(1 < q < \infty \) and \(\gamma > 0\). Functions f to be recovered are from the unit ball in Besov-type spaces of an anisotropic smoothness, in particular, spaces \(B^{\alpha ,\beta }_{p,\theta }\) of a “hybrid” of mixed smoothness \(\alpha > 0\) and isotropic smoothness \(\beta \in {\mathbb {R}}\), and spaces \(B^a_{p,\theta }\) of a nonuniform mixed smoothness \(a \in {\mathbb {R}}^d_+\). We constructed asymptotically optimal linear sampling algorithms \(L_n(X_n^*,\Phi _n^*,\cdot )\) on special sparse grids \(X_n^*\) and a family \(\Phi _n^*\) of linear combinations of integer or half integer translated dilations of tensor products of B-splines. We computed the asymptotic order of the error of the optimal recovery. This construction is based on B-spline quasi-interpolation representations of functions in \(B^{\alpha ,\beta }_{p,\theta }\) and \(B^a_{p,\theta }\). As consequences, we obtained the asymptotic order of optimal cubature formulas for numerical integration of functions from the unit ball of these Besov-type spaces.     

An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).     

Combinatorial invariance of Kazhdan–Lusztig–Vogan polynomials for fixed point free involutions

When \(\mathrm {Sp}(2n,\mathbb {C})\) acts on the flag variety of \(\mathrm {SL}(2n,\mathbb {C})\), the orbits are in bijection with fixed point free involutions in the symmetric group \(S_{2n}\). In this case, the associated Kazhdan–Lusztig–Vogan polynomials \(P_{v,u}\) can be indexed by pairs of fixed point free involutions \(v\ge u\), where \(\ge \) denotes the Bruhat order on \(S_{2n}\). We prove that these polynomials are combinatorial invariants in the sense that if \(f:[u,w_0]\rightarrow [u',w_0]\) is a poset isomorphism of upper intervals in the Bruhat order on fixed point free involutions, then \(P_{v,u} = P_{f(v),u'}\) for all \(v\ge u\).     

On the Dilation of Truncated Toeplitz Operators

An operator \(S_{\varphi ,\psi }^{u}\in \mathcal {L}(L^2)\) is called the dilation of a truncated Toeplitz operator if for two symbols \(\varphi ,\psi \in L^{\infty }\) and an inner function u,

$$\begin{aligned} S_{\varphi ,\psi }^{u}f=\varphi P_uf+\psi Q_uf \end{aligned}$$

holds for \(f\in {L}^{2}\) where \(P_{u}\) denotes the orthogonal projection of \(L^2\) onto the model space \(\mathcal { K}_{u}^2=H^2{\ominus }{{u}H^2}\) and \(Q_u=I-P_u.\) In this paper, we study properties of the dilation of truncated Toeplitz operators on \(L^{2}\). In particular, we provide conditions for the dilation of truncated Toeplitz operators to be normal. As some applications, we give several examples of such operators.

     

Homotopy type of neighborhood complexes of Kneser graphs, $$\varvec{KG_{2,k}}$$

Schrijver (Nieuw Archief voor Wiskunde, 26(3) (1978) 454–461) identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). Björner and de Longueville (Combinatorica 23(1) (2003) 23–34) proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a k-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension k. We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).     

Fluctuation Theory for Markov Random Walks

Two fundamental theorems by Spitzer–Erickson and Kesten–Maller on the fluctuation-type (positive divergence, negative divergence or oscillation) of a real-valued random walk \((S_{n})_{n\ge 0}\) with iid increments \(X_{1},X_{2},\ldots \) and the existence of moments of various related quantities like the first passage into \((x,\infty )\) and the last exit time from \((-\infty ,x]\) for arbitrary \(x\ge 0\) are studied in the Markov-modulated situation when the \(X_{n}\) are governed by a positive recurrent Markov chain \(M=(M_{n})_{n\ge 0}\) on a countable state space \(\mathcal {S}\); thus, for a Markov random walk \((M_{n},S_{n})_{n\ge 0}\). Our approach is based on the natural strategy to draw on the results in the iid case for the embedded ordinary random walks \((S_{\tau _{n}(i)})_{n\ge 0}\), where \(\tau _{1}(i),\tau _{2}(i),\ldots \) denote the successive return times of M to state i, and an analysis of the excursions of the walk between these epochs. However, due to these excursions, generalizations of the aforementioned theorems are surprisingly more complicated and require the introduction of various excursion measures so as to characterize the existence of moments of different quantities.     

Properties of singular integral operators $$\varvec{S}_{\varvec{\alpha ,\beta }}$$

For \(\alpha , \beta \in L^{\infty } (S^1),\) the singular integral operator \(S_{\alpha ,\beta }\) on \(L^2 (S^1)\) is defined by \(S_{\alpha ,\beta }f:= \alpha Pf+\beta Qf\), where P denotes the orthogonal projection of \(L^2(S^1)\) onto the Hardy space \(H^2(S^1),\) and Q denotes the orthogonal projection onto \(H^2(S^1)^{\perp }\). In a recent paper, Nakazi and Yamamoto have studied the normality and self-adjointness of \(S_{\alpha ,\beta }\). This work has shown that \(S_{\alpha ,\beta }\) may have analogous properties to that of the Toeplitz operator. In this paper, we study several other properties of \(S_{\alpha ,\beta }\).     

On the snake-in-the-box codes for rank modulation under Kendall’s $$\tau $$-metric

For exactly and efficiently representing and storing data in flash memories, the rank modulation scheme has been presented. In this scheme, Gray codes over the permutations are important, which are used to represent information in flash memories. For a Gray code, two consecutive codewords are obtained using one “push-to-the-top” operation. Specially, a snake-in-the-box code under the Kendall’s \(\tau \)-metric is a Gray code, which is capable of detecting one Kendall’s \(\tau \)-error. In this paper, we consider only the Kendall’s \(\tau \)-metric on the permutations. And we answer one open problem proposed by Horovitz and Etzion. That is, we prove that the length of the longest snake in \(S_{2n+2}\) is longer than the length of the longest snake in \(S_{2n+1}\).     

On a Generalization for Tribonacci Quaternions

Let \(V_{n}\) denote the third order linear recursive sequence defined by the initial values \(V_{0}\), \(V_{1}\) and \(V_{2}\) and the recursion \(V_{n}=rV_{n-1}+sV_{n-2}+tV_{n-3}\) if \(n\ge 3\), where r, s, and t are real constants. The \(\{V_{n}\}_{n\ge 0}\) are generalized Tribonacci numbers and reduce to the usual Tribonacci numbers when \(r=s=t=1\) and to the 3-bonacci numbers when \(r=s=1\) and \(t=0\). In this study, we introduced a quaternion sequence which has not been introduced before. We show that the new quaternion sequence that we introduced includes the previously introduced Tribonacci, Padovan, Narayana and third order Jacobsthal quaternion sequences. We obtained the Binet formula, summation formula and the norm value for this new quaternion sequence.     

Sharp Bounds for the Ratio of Modified Bessel Functions

Let \(I_{\nu }( x) \) be the modified Bessel functions of the first kind of order \(\nu \), and \(S_{p,\nu }( x) =W_{\nu }( x) ^{2}-2pW_{\nu }( x) -x^{2}\) with \(W_{\nu }( x) =xI_{\nu }( x) /I_{\nu +1}( x) \). We achieve necessary and sufficient conditions for the inequality \(S_{p,\nu }( x) <u\) or \(S_{p,\nu }( x) >l\) to hold for \(x>0\) by establishing the monotonicity of \(S_{p,\nu }(x)\) in \(x\in ( 0,\infty ) \) with \(\nu >-3/2\). In addition, the best parameters p and q are obtained to the inequality \(W_{\nu }( x) <( >) p+\sqrt{ x^{2}+q^{2}}\) for \(x>0\). Our main achievements improve some known results, and it seems to answer an open problem recently posed by Hornik and Grün (J Math Anal Appl 408:91–101, 2013).     

On counting subring-submodules of free modules over finite commutative frobenius rings

Let \(\texttt {R}\) be a finite commutative Frobenius ring and \(\texttt {S}\) a Galois extension of \(\texttt {R}\) of degree m. For positive integers k and \(k'\), we determine the number of free \(\texttt {S}\)-submodules \(\mathcal {B}\) of \(\texttt {S}^\ell \) with the property \(k=\texttt {rank}_\texttt {S}(\mathcal {B})\) and \(k'=\texttt {rank}_\texttt {R}(\mathcal {B}\cap \texttt {R}^\ell )\). This corrects the wrong result (Bill in Linear Algebr Appl 22:223–233, 1978, Theorem 6) which was given in the language of codes over finite fields.     

The Gray images of $$$$ constacyclic codes over $$F_{2^m}[u]/\langle u^{k} \rangle $$F2m[u]/⟨uk⟩

Let \(R_{k}\) denote the polynomial residue ring \(F_{2^m}[u]/\langle u^{k} \rangle \), where \(2^{j-1}+1\le k\le 2^{j}\) for some positive integer \(j\). Motivated by the work in [1], we introduce a new Gray map from \(R_{k}\) to \(F_{2^m}^{2^{j}}\). It is proved that the Gray image of a linear \((1+u)\) constacyclic code of an arbitrary length \(N\) over \(R_{k}\) is a distance invariant linear cyclic code of length \(2^{j}N\) over \(F_{2^m}\). Moreover, the generator polynomial of the Gray image of such a constacyclic code is determined, and some optimal linear cyclic codes over \(F_{2}\) and \(F_{4}\) are constructed under this Gray map.     

Random Walks in the Hyperbolic Plane and the Minkowski Question Mark Function

Consider \(G=SL_2(\mathbb {Z})/\{\pm I\}\) acting on the complex upper half plane H by \(h_M(z)=\frac{az\,+\,b}{cz\,+\,d}\) for \(M \in G\). Let \(D=\{z \in H: |z|\ge 1, |\mathfrak {R}(z)|\le 1/2\}\). We consider the set \({\mathcal {E}} \subset G\) with the nine elements M, different from the identity, such that \(\mathrm{tr\,}(MM^T)\le 3\). We equip the tiling of H defined by \(\mathbb {D}=\{h_M(D){:}\, M \in G\}\) with a graph structure where the neighbours are defined by \(h_M(D) \cap h_{M'}(D) \ne \emptyset \), equivalently \(M^{-1}M' \in {\mathcal {E}}\). The present paper studies several Markov chains related to the above structure. We show that the simple random walk on the above graph converges a.s. to a point X of the real line with the same distribution of \(S_2 W^{S_1}\), where \(S_1,S_2,W\) are independent with \(\Pr (S_i=\pm 1)=1/2\) and where W is valued in (0, 1) with distribution \(\Pr (W<w)=\mathbf ? (w)\). Here \(\mathbf ? \) is the Minkowski function. If \(K_1, K_2, \ldots \) are i.i.d with distribution \(\Pr (K_i=n)= 1/2^n\) for \(n=1,2,\ldots \), then \(W= \frac{1}{K_1+\frac{1}{K_2+\ldots }}\): this known result (Isola in Appl Math 5:1067–1090, 2014) is derived again here.     

The First Passage Time of a Stable Process Conditioned to Not Overshoot

Consider a stable Lévy process \(X=(X_t,t\ge 0)\) and let \(T_{x}\), for \(x>0\), denote the first passage time of \(X\) above the level \(x\). In this work, we give an alternative proof of the absolute continuity of the law of \(T_{x}\) and we obtain a new expression for its density function. Our constructive approach provides a new insight into the study of the law of \(T_{x}\). The random variable \(T_{x}^{0}\), defined as the limit of \(T_{x}\) when the corresponding overshoot tends to \(0\), plays an important role in obtaining these results. Moreover, we establish a relation between the random variable \(T_{x}^{0}\) and the dual process conditioned to die at \(0\). This relation allows us to link the expression of the density function of the law of \(T_{x}\) presented in this paper to the already known results on this topic.     

Korovkin-Type Approximation Theory in Riesz Spaces

In this paper, we prove the following Riesz spaces’ version of the Korovkin theorem. Let E and F be two Archimedean Riesz spaces with F uniformly complete, let W be a nonempty subset of \(E^{+}\), and let \((T_{n})\) be a given sequence of (r-u)-continuous elements of \(\mathcal {L(}E,F)\), such that \(\left| T_{n}-T_{m}\right| x=\left| (T_{n}-T_{m})x\right| \mathcal {\ }\)for all \(x\in E^{+},\) \(m,n\ge n_{0}\) (for a given \(n_{0}\in \mathbb {N} )\). If the sequence \((T_{n}x)_{n}\) \((r-u)\)-converges for every \(x\in W\), then \((T_{n})\) \((r-u)\)-converges also pointwise on the ideal \(E_{W}\), generated by W, to a linear operator \(S_{0}:E_{W}\rightarrow F\). We also prove a similar Korovkin-type theorem for nets of operators. Some applications for f-algebras and orthomorphisms are presented.     

Harmonic <Emphasis Type="Italic">p</Emphasis>-forms on Hadamard manifolds with finite total curvature

In the present note, the geometric structures and topological properties of harmonic p-forms on a complete noncompact submanifold \(M^{n}(n\ge 4)\) immersed in Hadamard manifold \(N^{n+m}\) are discussed, where \(M^{n}\) and \(N^{n+m}\) are assumed to have flat normal bundle and pure curvature tensor, respectively. Firstly, under the assumption that \(M^{n}\) satisfies the \((\mathcal {P}_\rho )\) property (i.e., the weighted Poincaré inequality holds on \(M^{n}\)) and the \((p,n-p)\)-curvature of \(N^{n+m}\) is not less than a given negative constant, using Moser iteration, the space of all \(L^{2}\) harmonic p-forms on \(M^{n}\) is proven to have finite dimensions if \(M^{n}\) has finite total curvature. Furthermore, if the total curvature is small enough or \(M^{n}\) has at most Euclidean volume growth, two vanishing theorems are, respectively, established for harmonic p-forms. Note that the two vanishing theorems extend several previous results obtained by H. Z. Lin.     

A note on generalized skew derivations on Lie ideals

Let \(\mathcal {R}\) be a prime ring, \(\mathcal {Z(R)}\) its center, \(\mathcal {C}\) its extended centroid, \(\mathcal {L}\) a Lie ideal of \(\mathcal {R}, \mathcal {F}\) a generalized skew derivation associated with a skew derivation d and automorphism \(\alpha \). Assume that there exist \(t\ge 1\) and \(m,n\ge 0\) fixed integers such that \( vu = u^m\mathcal {F}(uv)^tu^n\) for all \(u,v \in \mathcal {L}\). Then it is shown that either \(\mathcal {L}\) is central or \(\mathrm{char}(\mathcal {R})=2, \mathcal {R}\subseteq \mathcal {M}_2(\mathcal {C})\), the ring of \(2\times 2\) matrices over \(\mathcal {C}, \mathcal {L}\) is commutative and \(u^2\in \mathcal {Z(R)}\), for all \(u\in \mathcal {L}\). In particular, if \(\mathcal {L}=[\mathcal {R,R}]\), then \(\mathcal {R}\) is commutative.     

Pointwise convergence in probability of general smoothing splines

Establishing the convergence of splines can be cast as a variational problem which is amenable to a \(\Gamma \)-convergence approach. We consider the case in which the regularization coefficient scales with the number of observations, n, as \(\lambda _n=n^{-p}\). Using standard theorems from the \(\Gamma \)-convergence literature, we prove that the general spline model is consistent in that estimators converge in a sense slightly weaker than weak convergence in probability for \(p\le \frac{1}{2}\). Without further assumptions, we show this rate is sharp. This differs from rates for strong convergence using Hilbert scales where one can often choose \(p>\frac{1}{2}\).