Search

We study the classical \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\varOmega (\sqrt{\log n})}}$$\end{document}2Ω(logn), assuming \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}\not \subseteq \mathsf {DTIME}(n^{\mathcal {O}(\log n)})}$$\end{document}NP⊈DTIME(nO(logn)). This constitutes a significant gap to the best known approximation upper bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al. (Theory Comput 2:137–146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365–374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(1)}$$\end{document}O(1)-approximation when edges (or nodes) may be used by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}\left( \log n/\log \log n\right) }$$\end{document}Ologn/loglogn paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MaxEDP, we give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{r} \log ({k}r))}$$\end{document}O(rlog(kr))-approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al., as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r\le n}$$\end{document}r≤n.Further, we show how to route \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varOmega ({\text {OPT}}^{*})}$$\end{document}Ω(OPT∗) pairs with congestion bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\log (kr)/\log \log (kr))}$$\end{document}O(log(kr)/loglog(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MaxNDP, we give an algorithm that gives the optimal answer in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(k+r)^{\mathcal {O}(r)}\cdot n}$$\end{document}(k+r)O(r)·n. This is a substantial improvement on the run time of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^kr^{\mathcal {O}(r)}\cdot n}$$\end{document}2krO(r)·n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard even for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r=1}$$\end{document}r=1, and MaxNDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {W}[1]}$$\end{document}W[1]-hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {FPT}= \mathsf {W}[1]}$$\end{document}FPT=W[1] and that our approximability results are relevant even for very small constant values of r.

In our Novi Sad conference paper (1999) we described Dehn type surgeries of the famous Gieseking (1912) hyperbolic ideal simplex manifold $\mathcal{S}$, leading to compact fundamental domain $\mathcal{S}(k)$, $k = 2, 3, \dots$ with singularity geodesics of rotation order $k$, but as later turned out with cone angle $2(k-1)/k$. We computed also the volume of $S(k)$, tending to zero if $k$ goes to infinity. That time we naively thought that we obtained orbifolds with the above surprising property. As the reviewer of Math. Rev., Kevin P. Scannell (MR1770996 (2001g:57030)) rightly remarked, "this is in conflict with the well-known theorem of D. A. Kazhdan and G. A. Margulis (1968) and with the work of Thurston, describing the geometric convergence of orbifolds under large Dehn fillings". In this paper we refresh our previous publication. Correctly, we obtained cone manifolds (for $k > 2$), as A. D. Mednykh and V. S. Petrov (2006) kindly pointed out. We complete our discussion and derive the above cone manifold series (Gies.1 and Gies.2) in two geometrically equivalent form, by the half turn symmetry of any ideal simplex. Moreover we obtain a second orbifold series (Gies.3 and 4), tending to the regular ideal simplex as the original Gieseking manifold., 19 pages, 9 figures

In 1900, at the international congress of mathematicians, Hilbert claimed that the Riemann zeta function $\zeta(s)$ is not the solution of any algebraic ordinary differential equations on its region of analyticity. In 2015, Van Gorder considered the question of whether $\zeta(s)$ satisfies a non-algebraic differential equation and showed that it formally satisfies an infinite order linear differential equation. Recently, Prado and Klinger-Logan extended Van Gorder's result to show that the Hurwitz zeta function $\zeta(s,a)$ is also formally satisfies a similar differential equation \begin{equation*}\label{HurDE} T\left[\zeta (s,a) - \frac{1}{a^s}\right] = \frac{1}{(s-1)a^{s-1}}. \end{equation*} But unfortunately in the same paper they proved that the operator $T$ applied to Hurwitz zeta function $\zeta(s,a)$ does not converge at any point in the complex plane $\mathbb{C}$. In this paper, by defining $T_{p}^{a}$, a $p$-adic analogue of Van Gorder's operator $T,$ we establish an analogue of Prado and Klinger-Logan's differential equation satisfied by $\zeta_{p,E}(s,a)$ which is the $p$-adic analogue of the Hurwitz-type Euler zeta functions \begin{equation*}\label{HEZ} \zeta_E(s,a)=\sum_{n=0}^\infty\frac{(-1)^n}{(n+a)^s}. \end{equation*} In contrast with the complex case, due to the non-archimedean property, the operator $T_{p}^{a}$ applied to the $p$-adic Hurwitz-type Euler zeta function $\zeta_{p,E}(s,a)$ is convergent $p$-adically in the area of $s\in\mathbb{Z}_{p}$ with $s\neq 1$ and $a\in K$ with $|a|_{p}>1,$ where $K$ is any finite extension of $\mathbb{Q}_{p}$ with ramification index over $\mathbb{Q}_{p}$ less than $p-1.$, Comment: 18 pages. Final version. Dedicated to the memory of Prof. David Goss (1952-2017)

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollob\'as independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered' complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered' analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Kor\'andi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Kor\'andi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$., Comment: Reflected minor suggestions from reviewers

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) $A = (A_{\alpha \beta} x_{\alpha \beta})$, where $A_{\alpha \beta}$ is a $2 \times 2$ matrix over a field $\mathbf{F}$ and $x_{\alpha \beta}$ is an indeterminate for $\alpha = 1,2,\dots, \mu$ and $\beta = 1,2, \dots, \nu$. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos, Qiao, and Subrahamanyam (2018) and Garg, Gurvits, Oliveiva, and Wigderson (2019), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial $O((\mu \nu)^2 \min \{ \mu, \nu \})$-time algorithm for computing the symbolic rank of a $(2 \times 2)$-type generic partitioned matrix of size $2\mu \times 2\nu$. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of $A$ for an arbitrary field $\mathbf{F}$., Comment: This is a post-peer-review, pre-copyedit version of an article published in Mathematical Programming. The final authenticated version is available online at: https://doi.org/10.1007/s10107-021-01676-5

In this paper, using computations done through the LiE software, we compare the tensor product of irreducible selfdual representations of the special linear group with those of classical groups to formulate some conjectures relating the two. In the process a few other phenomenon present themselves which we record as questions. More precisely, under the natural correspondence of irreducible finite dimensional selfdual representations of ${\rm SL}_{2n}({\mathbb C})$ with those of ${\rm Spin}_{2n+1}({\mathbb C})$, it is easy to see that if the tensor product of three irreducible representations of ${\rm Spin}_{2n+1}({\rm C})$ contains the trivial representation, then so does the tensor product of the corresponding representations of ${\rm SL}_{2n}({\rm C})$. The paper formulates a conjecture in the reverse direction. We also deal with the pair $({\rm SL}_{2n+1}({\rm C}), {\rm Sp}_{2n}({\rm C}))$., Comment: Revised version!

This paper considers random processes of the form $$X_{n+1}=a_nX_n+b_n\pmod p$$ where p is odd, $$X_0=0$$ , $$(a_0,b_0), (a_1,b_1), (a_2,b_2),\ldots $$ are i.i.d., and $$a_n$$ and $$b_n$$ are independent with $$P(a_n=2)=P(a_n=(p+1)/2)=1/2$$ and $$P(b_n=1)=P(b_n=0)=P(b_n=-1)=1/3$$ . This can be viewed as a multiplicatively symmetrized version of a random process of Chung, Diaconis, and Graham. This paper shows that order $$(\log p)^2$$ steps suffice for $$X_n$$ to be close to uniformly distributed on the integers mod p for all odd p while order $$(\log p)^2$$ steps are necessary for $$X_n$$ to be close to uniformly distributed on the integers mod p.

Chen et al. (2004) strongly conjectured that R(Tn,Wm)=2n-1 if the maximum degree of Tn is small and m is even. Related to the conjecture, it is interesting to know for which tree Tn, we have R(Tn,Wm) > 2n-1 for even m. In this paper, we find the Ramsey number R(Tn,W8) for tree Tn with the maximum degree of Tn is at least n-3, namely R(Tn,W8) > 2n-1 for almost all such tree Tn. We also prove that if the maximum degree of Tn is large, then R(Tn,Wm) is a function of both m and n. In the end, we refine the conjecture of Chen et al. by giving the condition of small maximum degree. For a tree Tn with large maximum degree and even m, the R(Tn,Wm) is also unknown in general. In this paper, we shall determine the Ramsey number R(Tn,W8) for all trees Tn of order n with the maximum degree of Tn is at least n-3., 7 pages

In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial weakly polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in $O(m \log(nCD)\mathrm{SF}(kn, m, k))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $C$ is the maximum node capacity, $D$ is the maximum edge cost, and $\mathrm{SF}(n', m', \eta)$ is the time complexity of solving the submodular flow problem in a network of $n'$ nodes, $m'$ edges, and a submodular function with $\eta$-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows., Comment: A preliminary version of this paper was presented in at the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2019

Let $$\sigma $$ be an operator mean in the sense of Kubo and Ando. If the representation function $$f_\sigma $$ of $$\sigma $$ satisfies $$\begin{aligned} f_\sigma (t)^p\le f_\sigma (t^p) \text { for all } p>1, \end{aligned}$$then $$\sigma $$ is called a pmi mean. Our main interest is the class of pmi means (denoted by PMI). To study PMI, the operator means $$\sigma $$ satisfying $$\begin{aligned} f_\sigma (\sqrt{xy})\le \sqrt{f_\sigma (x)f_\sigma (y)}\quad (x,y>0) \end{aligned}$$are considered in this paper. The set of such means (denoted by GCV) includes certain significant examples and is included in PMI. The main result presented in this paper is that GCV is a proper subset of PMI. In addition, we investigate certain operator-mean classes including PMI.

Nielsen realization problem for the mapping class group $\text{Mod}(S_g)$ asks whether the natural projection $p_g: \text{Homeo}_+(S_g)\to \text{Mod}(S_g)$ has a section. While all the previous results use torsion elements in an essential way, in this paper, we focus on the much more difficult problem of realization of torsion-free subgroups of $\text{Mod}(S_g)$. The main result of this paper is that the Torelli group has no realization inside the area-preserving homeomorphisms., Comment: 22 pages, 5 figures

It is known that it is a very restrictive condition for a frame $\{f_k\}_{k=1}^\infty$ to have a representation $ \{T^n \varphi\}_{n=0}^\infty$ as the orbit of a bounded operator $T$ under a single generator $\varphi\in\mathcal{H}.$ In this paper we prove that, on the other hand, any frame can be approximated arbitrarily well by a suborbit $\{T^{\alpha(k)} \varphi\}_{k=1}^\infty$ of a bounded operator $T$. An important new aspect is that for certain important classes of frames, e.g., frames consisting of finitely supported vectors in $\ell^2(\mathbb{N}),$ we can be completely explicit about possible choices of the operator $T$ and the powers $\alpha(k),k\in \mathbb{N}.$ A similar approach carried out in $L^2(\mathbb{R})$ leads to an approximation of a frame using suborbits of two bounded operators. The results are illustrated with an application to Gabor frames generated by a compactly supported function. The paper is concluded with an appendix which collects general results about frame representations using multiple orbits of bounded operators.

This paper counts the number of reduced quasigroup words of a particular length in a certain number of generators. Taking account of the relationship with the Catalan numbers, counting words in a free magma, we introduce the term peri-Catalan number for the free quasigroup word counts. The main result of this paper is an exact recursive formula for the peri-Catalan numbers, structured by the Euclidean Algorithm. The Euclidean Algorithm structure does not readily lend itself to standard techniques of asymptotic analysis. However, conjectures for the asymptotic behavior of the peri-Catalan numbers, substantiated by numerical data, are presented. A remarkable aspect of the observed asymptotic behavior is the so-called asymptotic irrelevance of quasigroup identities, whereby cancelation resulting from quasigroup identities has a negligible effect on the asymptotic behavior of the peri-Catalan numbers for long words in a large number of generators.

For graphs $G$ and $H$, a \emph{homomorphism} from $G$ to $H$ is an edge-preserving mapping from the vertex set of $G$ to the vertex set of $H$. For a fixed graph $H$, by \textsc{Hom($H$)} we denote the computational problem which asks whether a given graph $G$ admits a homomorphism to $H$. If $H$ is a complete graph with $k$ vertices, then \textsc{Hom($H$)} is equivalent to the $k$-\textsc{Coloring} problem, so graph homomorphisms can be seen as generalizations of colorings. It is known that \textsc{Hom($H$)} is polynomial-time solvable if $H$ is bipartite or has a vertex with a loop, and NP-complete otherwise [Hell and Ne\v{s}et\v{r}il, JCTB 1990]. In this paper we are interested in the complexity of the problem, parameterized by the treewidth of the input graph $G$. If $G$ has $n$ vertices and is given along with its tree decomposition of width $\mathrm{tw}(G)$, then the problem can be solved in time $|V(H)|^{\mathrm{tw}(G)} \cdot n^{\mathcal{O}(1)}$, using a straightforward dynamic programming. We explore whether this bound can be improved. We show that if $H$ is a \emph{projective core}, then the existence of such a faster algorithm is unlikely: assuming the Strong Exponential Time Hypothesis (SETH), the \textsc{Hom($H$)} problem cannot be solved in time $(|V(H)|-\epsilon)^{\mathrm{tw}(G)} \cdot n^{\mathcal{O}(1)}$, for any $\epsilon > 0$. This result provides a full complexity characterization for a large class of graphs $H$, as almost all graphs are projective cores. We also notice that the naive algorithm can be improved for some graphs $H$, and show a complexity classification for all graphs $H$, assuming two conjectures from algebraic graph theory. In particular, there are no known graphs $H$ which are not covered by our result. In order to prove our results, we bring together some tools and techniques from algebra and from fine-grained complexity., Comment: An extended abstract of this paper appeared on SODA 2020

In this work we prove general bounds for the diameter of random graphs generated by a preferential attachment model whose parameter is a function $f:\mathbb{N}\to[0,1]$ that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when $f$ is a \textit{regularly varying function at infinity} with strictly negative index of regular variation~$-\gamma$. For this particular class, we prove a characterization for the diameter that depends only on~$-\gamma$. More specifically, we prove that the diameter of such graphs is of order $1/\gamma$ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of \textit{slowly varying functions} are also obtained., Comment: After referee recommendation, all results not concerning the diameter have been removed to obtain a more streamlined paper. The paper has been published at Random Structures and Algorithms under the new title

Let $\mathscr{C}$ be a 2-Calabi-Yau triangulated category, and let $\mathscr{T}$ be a cluster tilting subcategory of $\mathscr{C}$. An important result from Dehy and Keller tells us that a rigid object $c \in \mathscr{C}$ is uniquely defined by its index with respect to $\mathscr{T}$. The notion of triangulated categories extends to the notion of $(d+2)$-angulated categories. Thanks to a paper by Oppermann and Thomas, we now have a definition for cluster tilting subcategories in higher dimensions. This paper proves that under a technical assumption, an indecomposable object in a $(d+2)$-angulated category is uniquely defined by its index with respect to a higher dimensional cluster tilting subcategory. We also demonstrate an application of this result in higher dimensional cluster categories., Comment: Revising the article based on advice from a referee received upon submitting to a journal. This serves to make the results slightly more general

The standard quadratic optimization problem (StQP), i.e. the problem of minimizing a quadratic form $$\mathbf{x}^TQ\mathbf{x}$$ on the standard simplex $$\{\mathbf{x}\ge \mathbf{0}: \mathbf{x}^T\mathbf{e}=1\}$$ , is studied. The StQP arises in numerous applications, and it is known to be NP-hard. Chen, Peng and Zhang showed that almost certainly the StQP with a large random matrix $$Q=Q^T$$ , $$Q_{i,j},\, (i\le j)$$ being independent and identically concave-distributed, attains its minimum at a point $$\mathbf{x}$$ with support size $$|\{j: x_j>0\}|$$ bounded in probability. Later Chen and Peng proved that for $$Q=(M+M^T)/2$$ , with $$M_{i,j}$$ i.i.d. normal, the likely support size is at most 2. In this paper we show that the likely support size is poly-logarithmic in n, the problem size, for a considerably broader class of the distributions. Unlike the cited papers, the mild constraints are put on the asymptotic behavior of the distribution at a single left endpoint of its support, rather than on the distribution’s shape elsewhere. It also covers the distributions with the left endpoint $$-\infty $$ , provided that the distribution of $$Q_{i,j},\, (i\le j)$$ (of $$M_{i,j}$$ , if $$Q=(M+M^T)/2$$ resp.) has a (super/sub) exponentially narrow left tail.

In the present paper, which is a direct sequel of our paper [12] joint with Roozbeh Hazrat, we prove unrelativised version of the standard commutator formula in the setting of Chevalley groups. Namely, let $\Phi$ be a reduced irreducible root system of rank $\ge 2$, let $R$ be a commutative ring and let $I,J$ be two ideals of $R$. We consider subgroups of the Chevalley group $G(\Phi,R)$ of type $\Phi$ over $R$. The unrelativised elementary subgroup $E(\Phi,I)$ of level $I$ is generated (as a group) by the elementary unipotents $x_{\alpha}(\xi)$, $\alpha\in\Phi$, $\xi\in I$, of level $I$. Obviously, in general $E(\Phi,I)$ has no chances to be normal in $E(\Phi,R)$, its normal closure in the absolute elementary subgroup $E(\Phi,R)$ is denoted by $E(\Phi,R,I)$. The main results of [12] implied that the commutator $\big[E(\Phi,I),E(\Phi,J)]$ is in fact normal in $E(\Phi,R)$. In the present paper we prove an unexpected result that in fact $\big[E(\Phi,I),E(\Phi,J)]=\big[E(\Phi,R,I),E(\Phi,R,J)\big]$. It follows that the standard commutator formula also holds in the unrelativised form, namely $\big[E(\Phi,I),C(\Phi,R,J)]=\big[E(\Phi,I),E(\Phi,J)\big]$, where $C(\Phi,R,I)$ is the full congruence subgroup of level $I$. In particular, $E(\Phi,I)$ is normal in $C(\Phi,R,I)$., Comment: 14 Pages

In this paper, we study the derivatives of an integer-valued polynomial of a given degree. Denoting by $E_n$ the set of the integer-valued polynomials with degree $\leq n$, we show that the smallest positive integer $c_n$ satisfying the property: $\forall P \in E_n, c_n P' \in E_n$ is $c_n = \mathrm{lcm}(1 , 2 , \dots , n)$. As an application, we deduce an easy proof of the well-known inequality $\mathrm{lcm}(1 , 2 , \dots , n) \geq 2^{n - 1}$ ($\forall n \geq 1$). In the second part of the paper, we generalize our result for the derivative of a given order $k$ and then we give two divisibility properties for the obtained numbers $c_{n , k}$ (generalizing the $c_n$'s). Leaning on this study, we conclude the paper by determining, for a given natural number $n$, the smallest positive integer $\lambda_n$ satisfying the property: $\forall P \in E_n$, $\forall k \in \mathbb{N}$: $\lambda_n P^{(k)} \in E_n$. In particular, we show that: $\lambda_n = \prod_{p \text{ prime}} p^{\lfloor\frac{n}{p}\rfloor}$ ($\forall n \in \mathbb{N}$)., Comment: 17 pages

Let $n$ be an integer$\geqq0$. Let $S^{n+2}_1$ (respectively, $S^{n+2}_2$) be the $(n+2)$-sphere embedded in the $(n+4)$-sphere $S^{n+4}$. Let $S^{n+2}_1$ and $S^{n+2}_2$ intersect transversely. Suppose that the smooth submanifold, $S^{n+2}_1 \cap S^{n+2}_2$ in $S^{n+2}_i$ is PL homeomophic to the $n$-sphere. Then $S^{n+2}_1$ and $S^{n+2}_2$ in $S^{n+2}_i$ is an $n$-knot $K_i$. We say that the pair $(K_1,K_2)$ of n-knots is realizable. We consider the following problem in this paper. Let $A_1$ and $A_2$ be n-knots. Is the pair $(A_1,A_2)$ of $n$-knots realizable? We give a complete characterization., Comment: 22 pages, 1 figure,Chapter I: Mathematical Research Letters, 1998, 5, 577-582. Chapter II: University of Tokyo preprint series UTMS 95-50. This paper is beased on the author's master thesis 1994, and his PhD thesis 1996

Suppose that $n\geq 1$ and that, for all $i$ and $j$ with $1\leq i,j\leq n$ and $i\neq j$, $z_{ij}\in{\mathbb T}$ are given such that $z_{ji}=\overline{z}_{ij}$ for all $i\neq j$. If $V_1,\dotsc, V_n$ are isometries on a Hilbert space such that $V_i^\ast V_j^{\phantom{\ast}}\!=\overline{z}_{ij} V_j^{\phantom{\ast}}\!V_i^\ast$ for all $i\neq j$, then $(V_1,\dotsc,V_n)$ is called an $n$-tuple of doubly non-commuting isometries. The generators of non-commutative tori are well-known examples. In this paper, we establish a simultaneous Wold decomposition for $(V_1,\dotsc,V_n)$. This decomposition enables us to classify such $n$-tuples up to unitary equivalence. We show that the joint listing of a unitary equivalence class of a representation of each of the $2^n$ non-commutative tori that are naturally associated with the structure constants is a classifying invariant. A dilation theorem is also established, showing that an $n$-tuple of doubly non-commuting isometries can be extended to an $n$-tuple of doubly non-commuting unitary operators on an enveloping Hilbert space., Comment: A remark on the relation between the dilation theorem in this paper and other dilation theorems for multiple operators in the literature has been added. Otherwise, there are only a few minor editorial changes compared to the first version; some typos have also been corrected. Final version, to appear in Advances in Mathematics

The main object in this paper is a certain rational convex polytope whose lattice points give a polyhedral realization of a highest weight crystal basis. This is also identical to a Newton-Okounkov body of a flag variety, and it gives a toric degeneration. In this paper, we prove that a specific class of this polytope is given by Kiritchenko's Demazure operators on polytopes. This implies that polytopes in this class are all lattice polytopes. As an application, we give a sufficient condition for the corresponding toric variety to be Gorenstein Fano., Comment: 21 pages

In a number of papers by Edge, and in a related paper by Fano, several properties are discussed of the family of scrolls of degree 8, in the complex projective space, whose plane sections are projected bicanonical models of a genus 3 curve C. This beautiful subject is implicitely related to the moduli of semistable rank two vector bundles on C with bicanonical determinant. We revisit and reconstruct this matter in modern terms with a modular point of view. This paper is the refereed version of a contribution to a volume in honor of W.L Edge, to be published by European Journal of Mathematics., Comment: 13 pages

Jim Propp recently introduced a variant of chip-firing on a line where the chips are given distinct integer labels. Hopkins, McConville, and Propp showed that this process is confluent from some (but not all) initial configurations of chips. We recast their set-up in terms of root systems: labeled chip-firing can be seen as a root-firing process which allows the moves $\lambda \to \lambda + \alpha$ for $\alpha\in \Phi^{+}$ whenever $\langle\lambda,\alpha^\vee\rangle = 0$, where $\Phi^{+}$ is the set of positive roots of a root system of Type A and $\lambda$ is a weight of this root system. We are thus motivated to study the exact same root-firing process for an arbitrary root system. Actually, this central root-firing process is the subject of a sequel to this paper. In the present paper, we instead study the interval root-firing processes determined by $\lambda \to \lambda + \alpha$ for $\alpha\in \Phi^{+}$ whenever $\langle\lambda,\alpha^\vee\rangle \in [-k-1,k-1]$ or $\langle\lambda,\alpha^\vee\rangle \in [-k,k-1]$, for any $k \geq 0$. We prove that these interval-firing processes are always confluent, from any initial weight. We also show that there is a natural way to consistently label the stable points of these interval-firing processes across all values of $k$ so that the number of weights with given stabilization is a polynomial in $k$. We conjecture that these Ehrhart-like polynomials have nonnegative integer coefficients., Comment: 54 pages, 12 figures, 2 tables; v2: major revisions to improve exposition; v3: to appear in Mathematische Zeitschrift (Math. Z.)

In this paper we study group-based Markov models of evolution and their mixtures. In the algebreo-geometric setting, group-based phylogenetic tree models correspond to toric varieties, while their mixtures correspond to secant and join varieties. Determining properties of these secant and join varieties can aid both in model selection and establishing parameter identifiability. Here we explore the first natural geometric property of these varieties: their dimension. The expected projective dimension of the join variety of a set of varieties is one more than the sum of their dimensions. A join variety that realizes the expected dimension is nondefective. Nondefectiveness is not only interesting from a geometric point-of-view, but has been used to establish combinatorial identifiability for several classes of phylogenetic mixture models. In this paper, we focus on group-based models where the equivalence classes of identified parameters are orbits of a subgroup of the automorphism group of the group defining the model. In particular, we show that, for these group-based models, the variety corresponding to the mixture of $r$ trees with $n$ leaves is nondefective when $n \geq 2r+5$. We also give improved bounds for claw trees and give computational evidence that 2-tree and 3-tree mixtures are nondefective for small~$n$., Comment: 24 pages, 4 figures

The second author introduced with I. T\"orm\"a a two-player word-building game [Playing with Subshifts, Fund. Inform. 132 (2014), 131--152]. The game has a predetermined (possibly finite) choice sequence $\alpha_1$, $\alpha_2$, $\ldots$ of integers such that on round $n$ the player $A$ chooses a subset $S_n$ of size $\alpha_n$ of some fixed finite alphabet and the player $B$ picks a letter from the set $S_n$. The outcome is determined by whether the word obtained by concatenating the letters $B$ picked lies in a prescribed target set $X$ (a win for player $A$) or not (a win for player $B$). Typically, we consider $X$ to be a subshift. The winning shift $W(X)$ of a subshift $X$ is defined as the set of choice sequences for which $A$ has a winning strategy when the target set is the language of $X$. The winning shift $W(X)$ mirrors some properties of $X$. For instance, $W(X)$ and $X$ have the same entropy. Virtually nothing is known about the structure of the winning shifts of subshifts common in combinatorics on words. In this paper, we study the winning shifts of subshifts generated by marked uniform substitutions, and show that these winning shifts, viewed as subshifts, also have a substitutive structure. Particularly, we give an explicit description of the winning shift for the generalized Thue-Morse substitutions. It is known that $W(X)$ and $X$ have the same factor complexity. As an example application, we exploit this connection to give a simple derivation of the first difference and factor complexity functions of subshifts generated by marked substitutions. We describe these functions in particular detail for the generalized Thue-Morse substitutions., Comment: Extended version of a paper presented at RuFiDiM IV

In this paper, we prove that the weighted BMO space as follows $${\rm BMO}^{p}(\omega)=\Big\{f\in L^{1}_{\rm loc}:\sup_{Q}\|\chi_{Q}\|^{-1}_{L^{p}(\omega)}\big\|(f-f_{Q})\omega^{-1}\chi_{Q}\big\|_{L^{p}(\omega)}, Comment: Recently, Jarod Hart and Rodolfo H. Torres(arXiv:1707.01141) obtained some characterizations of weighted BMO space, Theorem 1.2 in my paper can be seem as a corollary of Theorem 5.9 in their paper. It should point out that our paper has submitted to Forum Mathematicum on 18-Apr-2017

It has been 40 years since Lawson and Osserman introduced the three minimal cones associated with Dirichlet problems in their 1977 Acta paper [13] . The first cone was shown area-minimizing by Harvey and Lawson in the celebrated paper [10] . In this paper, we confirm that the other two are also area-minimizing. In fact, we show that every Lawson–Osserman cone of type ( n , p , 2 ) constructed in [26] is area-minimizing.

Inspired by work of McMullen, we show that any orbit of the diagonal group in the space of lattices accumulates on the set of stable lattices. As consequences, we settle a conjecture of Ramharter concerning the asymptotic behaviour of the Mordell constant, and reduce Minkowski's conjecture on products of linear forms to a geometric question, yielding two new proofs of the conjecture in dimensions up to 7., Comment: This paper was part of the paper "On stable lattices and the diagonal group" (arXiv:1309.4025) which was split into three shorter papers (now all on arXiv) following the referee's request

A recent paper of Shekhar compares the ranks of elliptic curves $E_1$ and $E_2$ for which there is an isomorphism $E_1[p] \simeq E_2[p]$ as $\mathrm{Gal}(\bar{\mathbf{Q}}/\mathbf{Q})$-modules, where $p$ is a prime of good ordinary reduction for both curves. In this paper we prove an analogous result in the case where $p$ is a prime of good supersingular reduction., Comment: fixed a persistent typo in the results of Section 3. this typo led to the original example for p=3 being incorrect; it has been replaced with a correct example

This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $\lambda\left( G\right) $ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $k\geq1,$ $n\geq k^{3}/2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $\delta\left( G\right) \geq k.$ If \[ \lambda\left( G\right) \geq n-k-1, \] then $G$ has a Hamiltonian cycle, unless $G=K_{1}\vee(K_{n-k-1}+K_{k})$ or $G=K_{k}\vee(K_{n-2k}+\overline{K}_{k})$. (2) Let $k\geq1,$ $n\geq k^{3}/2+k^{2}/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $\delta\left( G\right) \geq k.$ If \[ \lambda\left( G\right) \geq n-k-2, \] then $G$ has a Hamiltonian path, unless $G=K_{k}\vee(K_{n-2k-1}+\overline {K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$., Comment: 18 pages. This version gives tighter bounds

We study the behavior of zero-divisors of the double zeta-function $\zeta_2(s_1,s_2)$. In our former paper \cite{MatSho14} we studied the case $s_1=s_2$, but in the present paper we consider the more general two variable situation. We carry out numerical computations in order to trace the behavior of zero-divisors. We observe that some divisors approach the points with $s_2=0$, while other divisors approach the points which are solutions of $\zeta(s_2)=1$., Comment: 14 pages, 16 figures

Let $R=K[[x_1,...,x_s]]$ be the ring of formal power series with maximal ideal $\mathfrak{m}$ over a field $K$ of arbitrary characteristic. On the ring $M_{m,n}$ of $m\times n$ matrices $A$ with entries in $R$ we consider several equivalence relations given by the action on $M_{m,n}$ of a group $G$. $G$ can be the group of automorphisms of $R$, combined with the multiplication of invertible matrices from the left, from the right, or from both sides, respectively. We call $A$ finitely $G$-determined if $A$ is $G$-equivalent to any matrix $B$ with ${A-B} \in {\mathfrak{m}^k M_{m,n}}$ for some finite integer $k$, which implies in particular that $A$ is $G$--equivalent to a matrix with polynomial entries. The classical criterion for analytic or differential map germs $f:(K^s,0) \to (K^m,0)$, $K = \mathbb{R}, \mathbb{C}$, says that $f \in M_{m,1}$ is finitely determined (with respect to various group actions) iff the tangent space to the orbit of $f$ has finite codimension in $M_{m,1}$. We extend this criterion to arbitrary matrices in $M_{m,n}$ if the characteristic of K is 0 or, more general, if the orbit map is separable. In positive characteristic however, the problem is more subtle since the orbit map is in general not separable, as we show by an example. This fact had been overlooked in previous papers. Our main result is a general sufficient criterion for finite $G$-determinacy in $M_{m,n}$ in arbitrary characteristic in terms of the tangent image of the orbit map, which we introduce in this paper. This criterion provides a computable bound for the $G$-determinacy of a matrix $A$ in $M_{m,n}$, which is new even in characteristic 0., Comment: 21 pages

In his 1990 Inventiones paper, P. Jones characterized subsets of rectifiable curves in the plane via a multiscale sum of $\beta$-numbers. These $\beta$-numbers are geometric quantities measuring how far a given set deviates from a best fitting line at each scale and location. Jones' result is a quantitative way of saying that a curve is rectifiable if and only if it has a tangent at almost every point. Moreover, computing this square sum for a curve returns the length of the curve up to multiplicative constant. K. Okikiolu extended his result from subsets of the plane to subsets of Euclidean space. G. David and S. Semmes extended the discussion to include sets of (integer) dimension larger than one, under the assumption of Ahlfors regularity and using a variant of Jones' $\beta$ numbers. In this paper we give a version of P. Jones' theorem for sets of arbitrary (integer) dimension lying in Euclidean space. We estimate the $d$-dimensional Hausdorff measure of a set in terms of an analogous sum of $\beta$-type numbers. There is no assumption of Ahlfors regularity, but rather, only of a lower bound on the Hausdorff content. We adapt David and Semmes' version of Jones' $\beta$-numbers by redefining them using a Choquet integral. A key tool in the proof is G. David and T. Toro's parametrization of Reifenberg flat sets (with holes)., Comment: Corrected more typos. There are still several typos and small mistakes in the published version of the paper, so the authors will maintain an up-to-date version on their webpages as we continue to correct them

The category of framed correspondences $Fr_*(k)$ and framed sheaves were invented by Voevodsky in his unpublished notes [V2]. Based on the theory, framed motives are introduced and studied in [GP1]. These are Nisnivich sheaves of $S^1$-spectra and the major computational tool of [GP1]. The aim of this paper is to show the following result which is essential in proving the main theorem of [GP1]: given an infinite perfect base field $k$, any $k$-smooth scheme $X$ and any $n\geq 1$, the map of simplicial pointed Nisnevich sheaves $(-,\mathbb{A}^1//\mathbb G_m)^{\wedge n}_+\to T^n$ induces a Nisnevich local level weak equivalence of $S^1$-spectra $$M_{fr}(X\times (\mathbb{A}^1// \mathbb G_m)^{\wedge n})\to M_{fr}(X\times T^n).$$ Moreover, it is proven that the sequence of $S^1$-spectra $$M_{fr}(X \times T^n \times \mathbb G_m) \to M_{fr}(X \times T^n \times\mathbb A^1) \to M_{fr}(X \times T^{n+1})$$ is locally a homotopy cofiber sequence in the Nisnevich topology. Another important result of this paper shows that homology of framed motives is computed as linear framed motives in the sense of [GP1]. This computation is crucial for the whole machinery of framed motives [GP1]., Comment: This is the final revised version

Let G be a reductive linear algebraic group, H a reductive subgroup of G and X an affine G-variety. Let Y denote the set of fixed points of H in X, and N(H) the normalizer of H in G. In this paper we study the natural map from the quotient of Y by N(H) to the quotient of X by G induced by the inclusion of Y in X. We show that, given G and H, this map is a finite morphism for all G-varieties X if and only if H is G-completely reducible (in the sense defined by J-P. Serre); this was proved in characteristic zero by Luna in the 1970s. We discuss some applications and give a criterion for the map of quotients to be an isomorphism. We show how to extend some other results in Luna's paper to positive characteristic and also prove the following theorem. Let H and K be reductive subgroups of G; then the double coset HgK is closed for generic g in G if and only if the intersection of generic conjugates of H and K is reductive., Comment: 29 pages; some changes in Section 5; to appear in Math. Z

The purpose of this paper is to modify the notion of the Nevanlinna constant $\operatorname{Nev}(D)$, recently introduced by the first author, for an effective Cartier divisor on a projective variety $X$. The modified notion is called the birational Nevanlinna constant and is denoted by $\operatorname{Nev}_{\text{bir}}(D)$. By computing $\operatorname{Nev}_{\text{bir}}(D)$ using the filtration constructed by Autissier in 2011, we establish a general result (see the General Theorem in the Introduction), in both the arithmetic and complex cases, which extends to general divisors the 2008 results of Evertse and Ferretti and the 2009 results of the first author. The notion $\operatorname{Nev}_{\text{bir}}(D)$ is originally defined in terms of Weil functions for use in applications, and it is proved later in this paper that it can be defined in terms of local effectivity of Cartier divisors after taking a proper birational lifting. In the last two sections, we use the notion $\operatorname{Nev}_{\text{bir}}(D)$ to recover the proof of an example of Faltings from his 2002 Baker's Garden article., Comment: 56 pages; latex

The Naruse hook-length formula is a recent general formula for the number of standard Young tableaux of skew shapes, given as a positive sum over excited diagrams of products of hook-lengths. In 2015 we gave two different $q$-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. In this paper we give an elementary proof of Naruse's formula based on the case of border strips. For special border strips, we obtain curious new formulas for the Euler and $q$-Euler numbers in terms of certain Dyck path summations., Comment: 33 pages, 10 figures. This is the second paper of the series "Hook formulas for skew shapes". Most of Sections 8 and 9 in this paper used to be part of arxiv:1512.08348 (v1,v2); v2 fixed several typos; v3 made precision in definition of flagged tableaux in Section 3.2 and fixed typo in Example 3.3; v4 fixed small typos in proof of Corollary 7.6

This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss-Seidel method and can be transformed to Kaczmarz method and projection onto convex sets (POCS). We observe that the known provable complexity of C-CD can be $O(n^2)$ times slower than randomized coordinate descent (R-CD), but no example was rigorously proven to exhibit such a large gap. In this paper we show that the gap indeed exists. We prove that there exists an example for which C-CD takes at least $O(n^4 \kappa_{\text{CD}} \log\frac{1}{\epsilon})$ operations, where $\kappa_{\text{CD}}$ is related to Demmel's condition number and it determines the convergence rate of R-CD. It implies that in the worst case C-CD can indeed be $O(n^2)$ times slower than R-CD, which has complexity $O( n^2 \kappa_{\text{CD}} \log\frac{1}{\epsilon})$. Note that for this example, the gap exists for any fixed update order, not just a particular order. Based on the example, we establish several almost tight complexity bounds of C-CD for quadratic problems. One difficulty with the analysis is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitute a \textit{lower bound} for the convergence rate. An immediate consequence is that for Gauss-Seidel method, Kaczmarz method and POCS, there is also an $O(n^2) $ gap between the cyclic versions and randomized versions (for solving linear systems). We also show that the classical convergence rate of POCS by Smith, Solmon and Wager [1] is always worse and sometimes can be infinitely times worse than our bound., Comment: 47 pages. Add a few tables to summarize the main convergence rates; add comparison with classical POCS bound; add discussions on another example

In this paper, we determine the bound of the valency of Cayley graphs of Frobenius groups with respect to normal Cayley subsets which guarantees to be Ramanujan. We see that if the ratio between the orders of the Frobenius kernel and complement is not so small, then this bound coincides with the trivial one coming from the trivial estimate of the largest non-trivial eigenvalue of the graphs. Moreover, in the cases of the dihedral groups of order twice odd primes, which are special cases of the Frobenius groups, we determine the same bound for the Cayley graphs of the groups with respect to not only normal but also all Cayley subsets. As is the case of abelian groups which we have treated in the previous papers, such a bound is equal to the trivial one in the above sense or, as exceptional cases, exceeds one from it. We then clarify that the latter occurs if and only if the corresponding prime is represented by a quadratic polynomial in a finite family., Comment: 12 pages

In this paper, we give a complete description of the associated primes of every power of the edge ideal in terms of generalized ear decompositions of the graph. This result establishes a surprising relationship between two seemingly unrelated notions of Commutative Algebra and Combinatorics. It covers all previous major results in this topic and has several interesting consequences., Comment: 28 pages, 7 figures. This revision contains more comments on the methods and the results of the paper. Important terminology and notations now appear in Definition environments for the convenience of the readers. That changes the numeration of the results considerably. This paper will appear in Trans. Amer. Math. Soc

We study representations of segment type of groups Sp(n) and SO(2n+1, F) over a local non-archimedean field, which play a fundamental role in the constructions of discrete series, and obtain a complete description of the Jacquet modules of these representations. Also, we provide an alternative way for determination of Jacquet modules of strongly positive discrete series and a description of top Jacquet modules of general discrete series. In this version are corrected few typographical errors which exist in the published version of this paper (see page 5 of the paper for more details)., Comment: 41 pages

The {Farey fractions} $F_n$ of order $n$ consist of all fractions $\frac{h}{k}$ in lowest terms lying in the closed unit interval and having denominator at most $n$. This paper considers the products $F_n$ of all nonzero Farey fractions of order $n$. It studies their growth measured by $\log(F_n)$ and their divisibility properties by powers of a fixed prime, given by $ord_p(F_n)$, as a function of $n$. The growth of $\log(F_n)$ is related to the Riemann hypothesis. This paper theoretically and empirically studies the functions $ord_p(F_n)$ and formulates several unproved properties (P1)-(P4) they may have. It presents evidence raising the possibility that the Riemann hypothesis may also be encoded in $ord_p(F_n)$ for a single prime $p$. This encoding makes use of a relation of these products to the products $G_n$ of all reduced and unreduced Farey fractions of order $n$, which are connected by M\"obius inversion. It involves new arithmetic functions which mix the M\"obius function with functions of radix expansions to a fixed prime base $p$., Comment: 32 pages, 10 figures

Let $(\xi_n)_{n=0}^\infty$ be a nonhomogeneous Markov chain taking values from finite state-space of $\mathbf{X}=\{1,2,\ldots,b\}$. In this paper, we will study the generalized entropy ergodic theorem with almost-everywhere and $\mathcal{L}_1$ convergence for nonhomogeneous Markov chains, which generalizes the corresponding classical results for the Markov chains., Comment: 13 pages,This paper has been accepted for publication in Journal of Theoretical Probability

For a pair $(M, I)$, where $M$ is finitely generated graded module over a standard graded ring $R$ of dimension $d$, and $I$ is a graded ideal with $\ell(R/I) < \infty$, we introduce a new invariant $HKd(M, I)$ called the {\em Hilbert-Kunz density function}. In Theorem 1.1, we relate this to the Hilbert-Kunz multiplicity $e_{HK}(M,I)$ by an integral formula. We prove that the Hilbert-Kunz density function is additive. Moreover it satisfies a multiplicative formula for a Segre product of rings. This gives a formula for $e_{HK}$ of the Segre product of rings in terms of the HKd of the rings involved. As a corollary, $e_{HK}$ of the Segre product of any finite number of Projective curves is a rational number. As an another application we see that $e_{HK}(R, {\bf m}^k) - e(R, {\bf m}^k)/d!$ grows at least as a fixed positive multiple of $k^{d-1}$ as $k\to \infty$., This paper is one part of the earlier submission, which has been split in two parts. This part will introduce and develop the theory of Hilbert-Kunz Density. This will appear in Transactions of AMS. The second part (which will be another paper) will involve the study of asymptotic behaviour of Hilbert-Kunz multiplicities of powers of an ideal

The birational classification of varieties inevitably leads to the study of singularities. The types of singularities that occur in this context have been studied by Mori, Kollar, Reid, and others, beginning in the 1980s with the introduction of the Minimal Model Program. Normal singularities that are terminal, canonical, log terminal, and log canonical, and their non-normal counterparts, are typically studied by using a resolution of singularities (or a semi-resolution), and finding numerical conditions that relate the canonical class of the variety to that of its resolution. In order to do this, it has been assumed that a variety X is has a $${\mathbb {Q}}$$ -Cartier canonical class: some multiple $$mK_X$$ of the canonical class is Cartier. In particular, this divisor can be pulled back under a resolution $$f: Y \rightarrow X$$ by pulling back its local sections. Then one has a relation $$K_Y \sim \frac{1}{m}f^*(mK_X) + \sum a_iE_i$$ . It is then the coefficients of the exceptional divisors $$E_i$$ that determine the type of singularities that belong to X. It might be asked whether this $${\mathbb {Q}}$$ -Cartier hypothesis is necessary in studying singularities in birational classification. de Fernex and Hacon (Compos Math 145:393–414, 2009) construct a boundary divisor $$\Delta $$ for arbitrary normal varieties, the resulting divisor $$K_X + \Delta $$ being $${\mathbb {Q}}$$ -Cartier even though $$K_X$$ itself is not. This they call (for reasons that will be made clear) an m-compatible boundary for X, and they proceed to show that the singularities defined in terms of the pair $$(X,\Delta )$$ are none other than the singularities just described, when $$K_X$$ happens to be $${\mathbb {Q}}$$ -Cartier. Thus, a wider context exists within which one can study singularities of the above types. In the present paper, we extend the results of de Fernex and Hacon (Compos Math 145:393–414, 2009) still further, to include demi-normal varieties without a $${\mathbb {Q}}$$ -Cartier canonical class. Our main result is that m-compatible boundaries exist for demi-normal varieties (Theorem 1.1). This theorem provides a link between the theory of singularities for arbitrary demi-normal varieites (whose canonical class may not $$\hbox {be } {\mathbb {Q}}$$ -Cartier), that theory being developed in the present paper, and the established theory of singularities of pairs.

The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combinatorica, 37 (2017), pp. 313--332] generalizes the famous Doignon--Bell--Scarf theorem on the existence of integer solutions to systems of linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly $k$ integer points in ${R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $\mathbb{R}^n$ that contains exactly $k$ integer points has a relaxation to at most $c(n,k)$ of its inequalities that will define a new polyhedron with the same integer points. They prove that $c(n,k) = O(k)2^n$. In this paper, we improve the bound asymptotically to be sublinear in $k$, that is, $c(n,k) = o(k) 2^n$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension n=2, our upper and lower bounds match to within a constant factor.

The spherical functions of the noncompact Grassmann manifolds $G_{p,q}(\mathbb F)=G/K$ over the (skew-)fields $\mathbb F=\mathbb R, \mathbb C, \mathbb H$ with rank $q\ge1$ and dimension parameter $p>q$ can be described as Heckman-Opdam hypergeometric functions of type BC, where the double coset space $G//K$ is identified with the Weyl chamber $ C_q^B\subset \mathbb R^q$ of type B. The corresponding product formulas and Harish-Chandra integral representations were recently written down by M. R��sler and the author in an explicit way such that both formulas can be extended analytically to all real parameters $p\in[2q-1,\infty[$, and that associated commutative convolution structures $*_p$ on $C_q^B$ exist. In this paper we introduce moment functions and the dispersion of probability measures on $C_q^B$ depending on $*_p$ and study these functions with the aid of this generalized integral representation. Moreover, we derive strong laws of large numbers and central limit theorems for associated time-homogeneous random walks on $(C_q^B, *_p)$ where the moment functions and the dispersion appear in order to determine drift vectors and covariance matrices of these limit laws explicitely. For integers $p$, all results have interpretations for $G$-invariant random walks on the Grassmannians $G/K$. Besides the BC-cases we also study the spaces $GL(q,\mathbb F)/U(q,\mathbb F)$, which are related to Weyl chambers of type A, and for which corresponding results hold. For the rank-one-case $q=1$, the results of this paper are well-known in the context of Jacobi-type hypergroups on $[0,\infty[$., Extended version of arXiv:1205.4866; some corrections to prior version. Accepted for publication in J. Theor. Probab

In the first part of this paper, we consider nonlinear extension of frame theory by introducing bi-Lipschitz maps F between Banach spaces. Our linear model of bi-Lipschitz maps is the analysis operator associated with Hilbert frames, p-frames, Banach frames, g-frames and fusion frames. In general Banach space setting, stable algorithms to reconstruct a signal x from its noisy measurement $$F(x)+\epsilon $$ may not exist. In this paper, we establish exponential convergence of two iterative reconstruction algorithms when F is not too far from some bounded below linear operator with bounded pseudo-inverse, and when F is a well-localized map between two Banach spaces with dense Hilbert subspaces. The crucial step to prove the latter conclusion is a novel fixed point theorem for a well-localized map on a Banach space. In the second part of this paper, we consider stable reconstruction of sparse signals in a union $$\mathbf{A}$$ of closed linear subspaces of a Hilbert space $$\mathbf{H}$$ from their nonlinear measurements. We introduce an optimization framework called a sparse approximation triple $$(\mathbf{A}, \mathbf{M}, \mathbf{H})$$ , and show that the minimizer $$\begin{aligned} x^*=\mathrm{argmin}_{\hat{x}\in {\mathbf M}\ \mathrm{with} \ \Vert F(\hat{x})-F(x^0)\Vert \le \epsilon } \Vert \hat{x}\Vert _{\mathbf M} \end{aligned}$$ provides a suboptimal approximation to the original sparse signal $$x^0\in \mathbf{A}$$ when the measurement map F has the sparse Riesz property and the almost linear property on $${\mathbf A}$$ . The above two new properties are shown to be satisfied when F is not far away from a linear measurement operator T having the restricted isometry property.

Let G be a finite group such that \(\mathop {{\text {SL}}}\nolimits (n,q)\subseteq G \subseteq \mathop {{\text {GL}}}\nolimits (n,q)\) and Z be a central subgroup of G. In this paper we determine the group T(G / Z) consisting of the equivalence classes of endotrivial k(G / Z)-modules where k is an algebraically closed field of characteristic p such that p does not divide q. The results in this paper complete the classification of endotrivial modules for all finite groups of (untwisted) Lie type A, initiated earlier by the authors.