Lengths of words in transformation semigroups generated by digraphs

Given a simple digraph D on n vertices (with \(n\ge 2\)), there is a natural construction of a semigroup of transformations \(\langle D\rangle \). For any edge (a, b) of D, let \(a\rightarrow b\) be the idempotent of rank \(n-1\) mapping a to b and fixing all vertices other than a; then, define \(\langle D\rangle \) to be the semigroup generated by \(a \rightarrow b\) for all \((a,b) \in E(D)\). For \(\alpha \in \langle D\rangle \), let \(\ell (D,\alpha )\) be the minimal length of a word in E(D) expressing \(\alpha \). It is well known that the semigroup \(\mathrm {Sing}_n\) of all transformations of rank at most \(n-1\) is generated by its idempotents of rank \(n-1\). When \(D=K_n\) is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate \(\ell (K_n,\alpha )\), for any \(\alpha \in \langle K_n\rangle = \mathrm {Sing}_n\); however, no analogous non-trivial results are known when \(D \ne K_n\). In this paper, we characterise all simple digraphs D such that either \(\ell (D,\alpha )\) is equal to Howie–Iwahori’s formula for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )\) for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )\) for all \(\alpha \in \langle D\rangle \). We also obtain bounds for \(\ell (D,\alpha )\) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank \(n-1\) of \(\mathrm {Sing}_n\)). We finish the paper with a list of conjectures and open problems.     

Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

Mapping prefer-opposite to prefer-one de Bruijn sequences

We present a mapping of the binary prefer-opposite de Bruijn sequence of order n onto the binary prefer-one de Bruijn sequence of order \(n-1\). The mapping is based on the differentiation operator \(D(\langle {b_1,\ldots ,b_l}\rangle ) = \langle b_2-b_1, b_3-b_2,\ldots , b_{l}-b_{l-1} \rangle \) where bit subtraction is modulo two. We show that if we take the prefer-opposite sequence \(\langle {b_1,b_2,\ldots ,b_{2^n}}\rangle \), apply D to get the sequence \(\langle {\hat{b}_1, \ldots , \hat{b}_{2^n-1}}\rangle \) and drop all the bits \(\hat{b}_i\) such that \(\langle {\hat{b}_i,\ldots ,\hat{b}_{i+n-1}}\rangle \) is a substring of \(\langle {\hat{b}_1,\ldots ,\hat{b}_{i+n-2}}\rangle \), we get the prefer-one de Bruijn sequence of order \(n-1\).     

Green’s function for elliptic systems: existence and Delmotte–Deuschel bounds

This paper is divided into two parts: In the main deterministic part, we prove that for an open domain \(D \subset \mathbb {R}^d\) with \(d \ge 2\), for every (measurable) uniformly elliptic tensor field a and for almost every point \(y \in D\), there exists a unique Green’s function centred in y associated to the vectorial operator \(-\nabla \cdot a\nabla \) in D. This result implies the existence of the fundamental solution for elliptic systems when \(d>2\), i.e. the Green function for \(-\nabla \cdot a\nabla \) in \(\mathbb {R}^d\). In the second part, we introduce a shift-invariant ensemble \(\langle \cdot \rangle \) over the set of uniformly elliptic tensor fields, and infer for the fundamental solution G some pointwise bounds for \(\langle |G(\cdot ; x,y)|\rangle \), \(\langle |\nabla _x G(\cdot ; x,y)|\rangle \) and \(\langle |\nabla _x\nabla _y G(\cdot ; x,y)|\rangle \). These estimates scale optimally in space and provide a generalisation to systems of the bounds obtained by Delmotte and Deuschel for the scalar case.     

Lower order eigenvalues of a system of equations of the drifting Laplacian on the metric measure spaces

Let \(\Omega \) be a bounded domain with smooth boundary in an n-dimensional metric measure space \((\mathbb {R}^n, \langle ,\rangle , e^{-\phi }dv)\) and let \(\mathbf {u}=(u^1, \ldots , u^n)\) be a vector-valued function from \(\Omega \) to \(\mathbb {R}^n\). In this paper, we investigate the Dirichlet eigenvalue problem of a system of equations of the drifting Laplacian: \(\mathbb {L}_{\phi } \mathbf {u} + \alpha [ \nabla (\mathrm {div}\mathbf { u}) -\nabla \phi \mathrm {div} \mathbf {u}]= - \widetilde{\sigma } \mathbf {u}\), in \( \Omega \), and \(u|_{\partial \Omega }=0,\) where \(\mathbb {L}_{\phi } = \Delta - \nabla \phi \cdot \nabla \) is the drifting Laplacian and \(\alpha \) is a nonnegative constant. We establish some universal inequalities for lower order eigenvalues of this problem on the metric measure space \((\mathbb {R}^n, \langle ,\rangle , e^{-\phi }dv)\) and the Gaussian shrinking soliton \((\mathbb {R}^n, \langle ,\rangle _{\mathrm {can}}, e^{-\frac{|x|^2}{4}}dv, \frac{1}{2})\). Moreover, we give an estimate for the upper bound of the second eigenvalue of this problem in terms of its first eigenvalue on the gradient product Ricci soliton \((\Sigma \times \mathbb {R}, \langle ,\rangle , e^{-\frac{\kappa t^2}{2}}dv, \kappa )\), where \( \Sigma \) is an Einstein manifold with constant Ricci curvature \(\kappa \).     

Representation of normal bands as semigroups of <Emphasis Type="Italic">k</Emphasis>-bi-ideals of a semiring

Here we show that every normal band N can be embedded into the normal band \(\mathcal {B(S)}\) of all k-bi-ideals, the left part \(N/ \mathcal {R}\) of N into the left normal band \(\mathcal {R(S)}\) of all right k-ideals, the right part \(N/ \mathcal {L}\) of N into the right normal band \(\mathcal {L(S)}\) of all left k-ideals, and the greatest semilattice homomorphic image \(N/ \mathcal {J}\) of N into the semilattice of all k-ideals of a same k-regular and intra k-regular semiring S.     

Large Deviations for Sums of Random Vectors Attracted to Operator Semi-Stable Laws

Let \(\{X_i, i\ge 1\}\) be i.i.d. \(\mathbb {R}^d\)-valued random vectors attracted to operator semi-stable laws and write \(S_n=\sum _{i=1}^{n}X_i\). This paper investigates precise large deviations for both the partial sums \(S_n\) and the random sums \(S_{N(t)}\), where N(t) is a counting process independent of the sequence \(\{X_i, i\ge 1\}\). In particular, we show for all unit vectors \(\theta \) the asymptotics

$$\begin{aligned} {\mathbb P}(|\langle S_n,\theta \rangle |>x)\sim n{\mathbb P}(|\langle X,\theta \rangle |>x) \end{aligned}$$

which holds uniformly for x-region \([\gamma _n, \infty )\), where \(\langle \cdot , \cdot \rangle \) is the standard inner product on \(\mathbb {R}^d\) and \(\{\gamma _n\}\) is some monotone sequence of positive numbers. As applications, the precise large deviations for random sums of real-valued random variables with regularly varying tails and \(\mathbb {R}^d\)-valued random vectors with weakly negatively associated occurrences are proposed. The obtained results improve some related classical ones.

     

Reducibility of operator semigroups and values of vector states

Let \(\mathcal S\) be a multiplicative semigroup of bounded linear operators on a complex Hilbert space \(\mathcal H\), and let \(\Omega \) be the range of a vector state on \(\mathcal S\) so that \(\Omega = \{ \langle S \xi , \xi \rangle \,{:}\,S \in \mathcal S\}\) for some fixed unit vector \(\xi \in \mathcal H\). We study the structure of sets \(\Omega \) of cardinality two coming from irreducible semigroups \(\mathcal S\). This leads us to sufficient conditions for reducibility and, in some cases, for the existence of common fixed points for \(\mathcal S\). This is made possible by a thorough investigation of the structure of maximal families \(\mathcal F\) of unit vectors in \(\mathcal H\) with the property that there exists a fixed constant \(\rho \in \mathbb C\) for which \(\langle x, y \rangle = \rho \) for all distinct pairs x and y in \(\mathcal F\).     

Eichler’s commutation relation and some other invariant subspaces of Hecke operators

Let k be an odd positive integer, L a lattice on a regular positive definite k-dimensional quadratic space over \(\mathbb {Q}\), \(N_L\) the level of L, and \(\mathscr {M}(L)\)  be the linear space of \(\theta \)-series attached to the distinct classes in the genus of L. We prove that, for an odd prime \(p|N_L\), if \(L_p=L_{p,1}\,\bot \, L_{p,2}\), where \(L_{p,1}\) is unimodular, \(L_{p,2}\) is (p)-modular, and \(\mathbb {Q}_pL_{p,2}\) is anisotropic, then \(\mathscr {M}(L;p):=\) \(\mathscr {M}(L)\) \(+T_{p^2}.\) \(\mathscr {M}(L)\)  is stable under the Hecke operator \(T_{p^2}\). If \(L_2\) is isometric to \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle 2\varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}1\\ 1&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) with \(\varepsilon \in \mathbb {Z}_2^{\times }\) and \(\kappa :=\frac{k-1}{2}\), then \(\mathscr {M}(L;2):=T_{2^2}.\mathscr {M}(L)+T_{2^2}^2.\,\mathscr {M}(L)\) is stable under the Hecke operator \(T_{2^2}\). Furthermore, we determine some invariant subspaces of the cusp forms for the Hecke operators.     

Torsion and divisibility in finitely generated commutative semirings

It is conjectured that (additive) divisibility is equivalent to (additive) idempotency in a finitely generated commutative semiring S. In this paper we extend this conjecture to weaker forms of these properties—torsion and almost-divisibility (an element \(a\in S\) is called almost-divisible in S if there is \(b\in \mathbb {N}\cdot a\) such that b is divisible in S by infinitely many primes). We show that a one-generated semiring is almost-divisible if and only if it is torsion. In the case of a free commutative semiring F(X) we characterize those elements \(f\in F(X)\) such that for every epimorphism \(\pi \) of F(X) torsion and almost-divisibility of \(\pi (f)\) are equivalent in \(\pi (F(X))\).     

A note on Weyl groups and root lattices

We follow the dual approach to Coxeter systems and show for Weyl groups that a set of reflections generates the group if and only if the related sets of roots and coroots generate the root and the coroot lattices, respectively. Previously, we have proven if (W, S) is a Coxeter system of finite rank n with set of reflections T and if \(t_1, \ldots t_n \in T\) are reflections in W that generate W, then \(P:= \langle t_1, \ldots t_{n-1}\rangle \) is a parabolic subgroup of (W, S) of rank \(n-1\) (Baumeister et al. in J Group Theory 20:103–131, 2017, Theorem 1.5). Here we show if (W, S) is crystallographic as well, then all the reflections \(t \in T\) such that \(\langle P, t\rangle = W\) form a single orbit under conjugation by P.     

The primitive idempotents and weight distributions of irreducible constacyclic codes

Let \({\mathbb {F}}_q\) be a finite field with q elements such that \(l^v||(q^t-1)\) and \(\gcd (l,q(q-1))=1\), where l, t are primes and v is a positive integer. In this paper, we give all primitive idempotents in a ring \(\mathbb F_q[x]/\langle x^{l^m}-a\rangle \) for \(a\in {\mathbb {F}}_q^*\). Specially for \(t=2\), we give the weight distributions of all irreducible constacyclic codes and their dual codes of length \(l^m\) over \({\mathbb {F}}_q\).     

Line complexity asymptotics of polynomial cellular automata

Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence \(a_T(k)\), which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial \(T(x)=c_0+c_1x+\dots +c_nx^n\) with \(c_0,c_n\ne ~0\), we construct odd and even parts of the polynomial from the strings \(0c_1c_3c_5\cdots c_{1+2\lfloor (n-1)/2\rfloor }\) and \(c_0c_2c_4\cdots c_{2\lfloor n/2\rfloor }\), respectively. We prove that \(a_T(k)\) satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function \(\phi (z)=\sum _{k=1}^\infty \alpha (k)z^k\) which satisfies a functional equation relating \(\phi (z)\) and \(\phi (z^p)\). We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which \(\lim _{k\rightarrow \infty }(\alpha (k)/k^2-~f(p^{-\langle \log _p k\rangle })) = 0\) (here \(\langle y\rangle =y-\lfloor y\rfloor \)). We use this result to show that for certain positive integer sequences \(s_k(x)\rightarrow \infty \) with a parameter \(x\in [1/p,1]\), the ratio \(\alpha (s_k(x))/s_k(x)^2\) tends to f(x), and that the limit superior and inferior of \(\alpha (k)/k^2\) are given by the extremal values of f.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

A new theorem on the prime-counting function

For \(x>0\), let \(\pi (x)\) denote the number of primes not exceeding x. For integers a and \(m>0\), we determine when there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). In particular, we show that, for any integers \(m>2\) and \(a\leqslant \lceil e^{m-1}/(m-1)\rceil \), there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). Consequently, for any integer \(m>4\), there is a positive integer n with \(\pi (mn)=m+n\). We also pose several conjectures for further research; for example, we conjecture that, for each \(m=1,2,3,\ldots \), there is a positive integer n such that \(m+n\) divides \(p_m+p_n\), where \(p_k\) denotes the k-th prime.     

Newly appointed editors

Let k be a field and \(k(x_0,\ldots ,x_{p-1})\) be the rational function field of p variables over k where p is a prime number. Suppose that \(G=\langle \sigma \rangle \simeq C_p\) acts on \(k(x_0,\ldots ,x_{p-1})\) by k-automorphisms defined as \(\sigma :x_0\mapsto x_1\mapsto \cdots \mapsto x_{p-1}\mapsto x_0\). Denote by P the set of all prime numbers and define \(P_0=\{p\in P:\mathbb {Q}(\zeta _{p-1})\) is of class number one\(\}\) where \(\zeta _n\) a primitive n-th root of unity in \(\mathbb {C}\) for a positive integer n; \(P_0\) is a finite set by Masley and Montgomery (J Reine Angew Math 286/287:248–256, 1976). Theorem. Let k be an algebraic number field and \(P_k=\{p\in P: p\) is ramified in \(k\}\). Then \(k(x_0,\ldots ,x_{p-1})^G\) is not stably rational over k for all \(p\in P\backslash (P_0\cup P_k)\).     

Complete classification of pseudo <Emphasis Type="Italic">H</Emphasis>-type Lie algebras: I

Let \({\mathscr {N}}\) be a 2-step nilpotent Lie algebra endowed with a non-degenerate scalar product \(\langle .\,,.\rangle \), and let \({\mathscr {N}}=V\oplus _{\perp }Z\), where Z is the centre of the Lie algebra and V its orthogonal complement. We study classification of the Lie algebras for which the space V arises as a representation space of the Clifford algebra \({{\mathrm{{\mathrm{Cl}}}}}({\mathbb {R}}^{r,s})\), and the representation map \(J:{{\mathrm{{\mathrm{Cl}}}}}({\mathbb {R}}^{r,s})\rightarrow {{\mathrm{End}}}(V)\) is related to the Lie algebra structure by \(\langle J_zv,w\rangle =\langle z,[v,w]\rangle \) for all \(z\in {\mathbb {R}}^{r,s}\) and \(v,w\in V\). The classification depends on parameters r and s and is completed for the Clifford modules V having minimal possible dimension, that are not necessary irreducible. We find necessary conditions for the existence of a Lie algebra isomorphism according to the range of the integer parameters \(0\le r,s<\infty \). We present a constructive proof for the isomorphism maps for isomorphic Lie algebras and determine the class of non-isomorphic Lie algebras.     

Integral Cayley graphs over dihedral groups

In this paper, we give a necessary and sufficient condition for the integrality of Cayley graphs over the dihedral group \(D_n=\langle a,b\mid a^n=b^2=1,bab=a^{-1}\rangle \). Moreover, we also obtain some simple sufficient conditions for the integrality of Cayley graphs over \(D_n\) in terms of the Boolean algebra of \(\langle a\rangle \), from which we find infinite classes of integral Cayley graphs over \(D_n\). In particular, we completely determine all integral Cayley graphs over the dihedral group \(D_p\) for a prime p.