On the Almost Sure Location of the Singular Values of Certain Gaussian Block-Hankel Large Random Matrices

This paper studies the almost sure location of the eigenvalues of matrices \({\mathbf{W}}_N {\mathbf{W}}_N^{*}\), where \({\mathbf{W}}_N = ({\mathbf{W}}_N^{(1)T}, \ldots , {\mathbf{W}}_N^{(M)T})^{T}\) is a \({\textit{ML}} \times N\) block-line matrix whose block-lines \(({\mathbf{W}}_N^{(m)})_{m=1, \ldots , M}\) are independent identically distributed \(L \times N\) Hankel matrices built from i.i.d. standard complex Gaussian sequences. It is shown that if \(M \rightarrow +\infty \) and \(\frac{{\textit{ML}}}{N} \rightarrow c_* (c_* \in (0, \infty ))\), then the empirical eigenvalue distribution of \({\mathbf{W}}_N {\mathbf{W}}_N^{*}\) converges almost surely towards the Marcenko–Pastur distribution. More importantly, it is established using the Haagerup–Schultz–Thorbjornsen ideas that if \(L = O(N^{\alpha })\) with \(\alpha < 2/3\), then, almost surely, for \(N\) large enough, the eigenvalues of \({\mathbf{W}}_N {\mathbf{W}}_N^{*}\) are located in the neighbourhood of the Marcenko–Pastur distribution. It is conjectured that the condition \(\alpha < 2/3\) is optimal.     

Central Limit Theorem for Linear Eigenvalue Statistics for a Tensor Product Version of Sample Covariance Matrices

For \(k,m,n\in {\mathbb {N}}\), we consider \(n^k\times n^k\) random matrices of the form

$$\begin{aligned} {\mathcal {M}}_{n,m,k}({\mathbf {y}})=\sum _{\alpha =1}^m\tau _\alpha {Y_\alpha }Y_\alpha ^T,\quad {Y}_\alpha ={\mathbf {y}}_\alpha ^{(1)}\otimes \cdots \otimes {\mathbf {y}}_\alpha ^{(k)}, \end{aligned}$$

where \(\tau _{\alpha }\), \(\alpha \in [m]\), are real numbers and \({\mathbf {y}}_\alpha ^{(j)}\), \(\alpha \in [m]\), \(j\in [k]\), are i.i.d. copies of a normalized isotropic random vector \({\mathbf {y}}\in {\mathbb {R}}^n\). For every fixed \(k\ge 1\), if the Normalized Counting Measures of \(\{\tau _{\alpha }\}_{\alpha }\) converge weakly as \(m,n\rightarrow \infty \), \(m/n^k\rightarrow c\in [0,\infty )\) and \({\mathbf {y}}\) is a good vector in the sense of Definition 1.1, then the Normalized Counting Measures of eigenvalues of \({\mathcal {M}}_{n,m,k}({\mathbf {y}})\) converge weakly in probability to a nonrandom limit found in Marchenko and Pastur (Math USSR Sb 1:457–483, 1967). For \(k=2\), we define a subclass of good vectors \({\mathbf {y}}\) for which the centered linear eigenvalue statistics \(n^{-1/2}{{\mathrm{Tr}}}\varphi ({\mathcal {M}}_{n,m,2}({\mathbf {y}}))^\circ \) converge in distribution to a Gaussian random variable, i.e., the Central Limit Theorem is valid.

     

A Tight Upper Bound on Acquaintance Time of Graphs

In this note we confirm a conjecture raised by Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) on the acquaintance time of graphs, proving that for all graphs G with n vertices it holds that \(\mathcal {AC}(G) = O(n^{3/2})\). This is done by proving that for all graphs G with n vertices and maximum degree \(\varDelta \) it holds that \(\mathcal {AC}(G) \le 20 \varDelta n\). Combining this with the bound \(\mathcal {AC}(G) \le O(n^2/\varDelta )\) from Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) gives the uniform upper bound of \(O(n^{3/2})\) for all n-vertex graphs. This bound is tight up to a multiplicative constant. We also prove that for the n-vertex path \(P_n\) it holds that \(\mathcal {AC}(P_n)=n-2\). In addition we show that the barbell graph \(B_n\) consisting of two cliques of sizes \({\lceil n/2\rceil }\) and \({\lfloor n/2\rfloor }\) connected by a single edge also has \(\mathcal {AC}(B_n) = n-2\). This shows that it is possible to add \(\varOmega (n^2\)) edges a graph without changing its \(\mathcal {AC}\) value.     

Sharp MSE Bounds for Proximal Denoising

Denoising has to do with estimating a signal \(\mathbf {x}_0\) from its noisy observations \(\mathbf {y}=\mathbf {x}_0+\mathbf {z}\). In this paper, we focus on the “structured denoising problem,” where the signal \(\mathbf {x}_0\) possesses a certain structure and \(\mathbf {z}\) has independent normally distributed entries with mean zero and variance \(\sigma ^2\). We employ a structure-inducing convex function \(f(\cdot )\) and solve \(\min _\mathbf {x}\{\frac{1}{2}\Vert \mathbf {y}-\mathbf {x}\Vert _2^2+\sigma {\lambda }f(\mathbf {x})\}\) to estimate \(\mathbf {x}_0\), for some \(\lambda >0\). Common choices for \(f(\cdot )\) include the \(\ell _1\) norm for sparse vectors, the \(\ell _1-\ell _2\) norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate \(\mathbf {x}^*\) is the normalized mean-squared error \(\text {NMSE}(\sigma )=\frac{{\mathbb {E}}\Vert \mathbf {x}^*-\mathbf {x}_0\Vert _2^2}{\sigma ^2}\). We show that NMSE is maximized as \(\sigma \rightarrow 0\) and we find the exact worst-case NMSE, which has a simple geometric interpretation: the mean-squared distance of a standard normal vector to the \({\lambda }\)-scaled subdifferential \({\lambda }\partial f(\mathbf {x}_0)\). When \({\lambda }\) is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-\mathbf {x}\Vert _2\}\). The paper also connects these results to the generalized LASSO problem, in which one solves \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-{\mathbf {A}}\mathbf {x}\Vert _2\}\) to estimate \(\mathbf {x}_0\) from noisy linear observations \(\mathbf {y}={\mathbf {A}}\mathbf {x}_0+\mathbf {z}\). We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a “phase transition” as a function of number of observations. We also provide an order-optimal bound for the LASSO error in terms of the mean-squared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems.     

Decorated marked surfaces: spherical twists versus braid twists

We are interested in the 3-Calabi-Yau categories \({\mathcal {D}}\) arising from quivers with potential associated to a triangulated marked surface \(\mathbf {S}\) (without punctures). We prove that the spherical twist group \(\mathrm{ST}\) of \({\mathcal {D}}\) is isomorphic to a subgroup (generated by braid twists) of the mapping class group of the decorated marked surface \({\mathbf {S}}_\bigtriangleup \). Here \({\mathbf {S}}_\bigtriangleup \) is the surface obtained from \(\mathbf {S}\) by decorating with a set of points, where the number of points equals the number of triangles in any triangulations of \(\mathbf {S}\). For instance, when \(\mathbf {S}\) is an annulus, the result implies that the corresponding spaces of stability conditions on \({\mathcal {D}}\) are contractible.     

Optimal bounds for convergence of expected spectral distributions to the semi-circular law

Let \(\mathbf {X}=(X_{jk})_{j,k=1}^n\) denote a Hermitian random matrix with entries \(X_{jk}\), which are independent for \(1\le j\le k\le n\). We consider the rate of convergence of the empirical spectral distribution function of the matrix \(\mathbf {X}\) to the semi-circular law assuming that \(\mathbf{E}X_{jk}=0\), \(\mathbf{E}X_{jk}^2=1\) and that

$$\begin{aligned} \sup _{n\ge 1}\sup _{1\le j,k\le n}\mathbf{E}|X_{jk}|^4=:\mu _4<\infty , \end{aligned}$$

and

$$\begin{aligned} \sup _{1\le j,k\le n}|X_{jk}|\le D_0n^{\frac{1}{4}}. \end{aligned}$$

By means of a recursion argument it is shown that the Kolmogorov distance between the expected spectral distribution of the Wigner matrix \(\mathbf {W}=\frac{1}{\sqrt{n}}\mathbf {X}\) and the semicircular law is of order \(O(n^{-1})\).

     

Towards a Comprehensive Stability Theory for Feynman’s Operational Calculus: The Time-Dependent Setting

We obtain lower bounds on blow-up of solutions for the 3D magneto-micropolar equations. More precisely, we establish some estimates for the solution \((\mathbf{u},\mathbf{w},\mathbf{b}) (t)\) in its maximal interval \([0,T^{*})\) provided that \(T^{*}<\infty\), which show for \(\delta\in(0,1)\) that \(\|(\mathbf{u},\mathbf{w},\mathbf{b})(t)\|_{\dot{H}^{s}}\) is at least of the order \((T^{*}-t)^{-(\delta s)/(1+2\delta)}\) for \(s\geq1/2+\delta\). In particular, by choosing a suitable \(\delta\), one concludes that \(\|(\mathbf{u},\mathbf{w},\mathbf{b})(t)\|_{\dot{H}^{s}}\) is at least of the order \((T^{*}-t)^{-s/4}\), and \((T^{*}-t)^{1/4-s/2}\) for \(s\geq1\), and \(1/2< s<3/2\), respectively. We also show that \((T^{*}-t)^{-s/3}\) is a lower rate for \(\|(\mathbf{u},\mathbf{w},\mathbf{b})(t)\|_{\dot{H}^{s}}\) if \(s>3/2\).     

Epireflective subcategories of TOP,T$$_$$UNIF,UNIF, closed under epimorphic images,or being algebraic

The epireflective subcategories of \(\mathbf{Top}\), that are closed under epimorphic (or bimorphic) images, are \(\{ X \mid |X| \le 1 \} \), \(\{ X \mid X\) is indiscrete\(\} \) and \(\mathbf{Top}\). The epireflective subcategories of \(\mathbf{T_2Unif}\), closed under epimorphic images, are: \(\{ X \mid |X| \le 1 \} \), \(\{ X \mid X\) is compact \(T_2 \} \), \(\{ X \mid \) covering character of X is \( \le \lambda _0 \} \) (where \(\lambda _0\) is an infinite cardinal), and \(\mathbf{T_2Unif}\). The epireflective subcategories of \(\mathbf{Unif}\), closed under epimorphic (or bimorphic) images, are: \(\{ X \mid |X| \le 1 \} \), \(\{ X \mid X\) is indiscrete\(\} \), \(\{ X \mid \) covering character of X is \( \le \lambda _0 \} \) (where \(\lambda _0\) is an infinite cardinal), and \(\mathbf{Unif}\). The epireflective subcategories of \(\mathbf{Top}\), that are algebraic categories, are \(\{ X \mid |X| \le 1 \} \), and \(\{ X \mid X\) is indiscrete\(\} \). The subcategories of \(\mathbf{Unif}\), closed under products and closed subspaces and being varietal, are \(\{ X \mid |X| \le 1 \} \), \(\{ X \mid X\) is indiscrete\(\} \), \(\{ X \mid X\) is compact \(T_2 \} \). The subcategories of \(\mathbf{Unif}\), closed under products and closed subspaces and being algebraic, are \(\{ X \mid X\) is indiscrete\( \} \), and all epireflective subcategories of \(\{ X \mid X\) is compact \(T_2 \} \). Also we give a sharpened form of a theorem of Kannan-Soundararajan about classes of \(T_3\) spaces, closed for products, closed subspaces and surjective images.     

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

Why there is no an existence theorem for a convex polytope with prescribed directions and perimeters of the faces?

We choose some special unit vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) in \({\mathbb {R}}^3\) and denote by \({\mathscr {L}}\subset {\mathbb {R}}^5\) the set of all points \((L_1,\ldots ,L_5)\in {\mathbb {R}}^5\) with the following property: there exists a compact convex polytope \(P\subset {\mathbb {R}}^3\) such that the vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) (and no other vector) are unit outward normals to the faces of P and the perimeter of the face with the outward normal \({\mathbf {n}}_k\) is equal to \(L_k\) for all \(k=1,\ldots ,5\). Our main result reads that \({\mathscr {L}}\) is not a locally-analytic set, i.e., we prove that, for some point \((L_1,\ldots ,L_5)\in {\mathscr {L}}\), it is not possible to find a neighborhood \(U\subset {\mathbb {R}}^5\) and an analytic set \(A\subset {\mathbb {R}}^5\) such that \({\mathscr {L}}\cap U=A\cap U\). We interpret this result as an obstacle for finding an existence theorem for a compact convex polytope with prescribed directions and perimeters of the faces.     

Bilinear dual hyperovals in the largest ambient spaces

The following facts are shown for a bilinear dual hyperoval \({\mathcal {S}}\) of rank n. The ambient space \({\mathbf {A}}({\mathcal {S}})\) has vector dimension at most \(n(n+1)/2\). The dimension of \({\mathbf {A}}({\mathcal {S}})\) is \(n(n+1)/2\) if and only if \({\mathcal {S}}\) is isomorphic to the Huybrechts or the Buratti–Del Fra dual hyperoval.     

Few associative triples,isotopisms and groups

Let Q be a quasigroup. For \(\alpha ,\beta \in S_Q\) let \(Q_{\alpha ,\beta }\) be the principal isotope \(x*y = \alpha (x)\beta (y)\). Put \(\mathbf a(Q)= |\{(x,y,z)\in Q^3;\) \(x(yz)) = (xy)z\}|\) and assume that \(|Q|=n\). Then \(\sum _{\alpha ,\beta }\mathbf a(Q_{\alpha ,\beta })/(n!)^2 = n^2(1+(n-1)^{-1})\), and for every \(\alpha \in S_Q\) there is \(\sum _\beta \mathbf a(Q_{\alpha ,\beta })/n! = n(n-1)^{-1}\sum _x(f_x^2-2f_x+n)\ge n^2\), where \(f_x=|\{y\in Q;\) \( y = \alpha (y)x\}|\). If G is a group and \(\alpha \) is an orthomorphism, then \(\mathbf a(G_{\alpha ,\beta })=n^2\) for every \(\beta \in S_Q\). A detailed case study of \(\mathbf a(G_{\alpha ,\beta })\) is made for the situation when \(G = \mathbb Z_{2d}\), and both \(\alpha \) and \(\beta \) are “natural” near-orthomorphisms. Asymptotically, \(\mathbf a(G_{\alpha ,\beta })>3n\) if G is an abelian group of order n. Computational results: \(\mathbf a(7) = 17\) and \(\mathbf a(8) \le 21\), where \(\mathbf a(n) = \min \{\mathbf a(Q);\) \( |Q|=n\}\). There are also determined minimum values for \(\mathbf a(G_{\alpha ,\beta })\), G a group of order \(\le 8\).     

Tannakian formalism for fiber functors over tensor categories

It is well known that the pseudovariety \(\mathbf {J}\) of all \(\mathscr {J}\)-trivial monoids is not local, which means that the pseudovariety \(g\mathbf {J}\) of categories generated by \(\mathbf {J}\) is a proper subpseudovariety of the pseudovariety \(\ell \mathbf {J}\) of categories all of whose local monoids belong to \(\mathbf {J}\). In this paper, it is proved that the pseudovariety \(\mathbf {J}\) enjoys the following weaker property. For every prime number p, the pseudovariety \(\ell \mathbf {J}\) is a subpseudovariety of the pseudovariety \(g(\mathbf {J}*\mathbf {Ab}_p)\), where \(\mathbf {Ab}_p\) is the pseudovariety of all elementary abelian p-groups and \(\mathbf {J}*\mathbf {Ab}_p\) is the pseudovariety of monoids generated by the class of all semidirect products of monoids from \(\mathbf {J}\) by groups from \(\mathbf {Ab}_p\). As an application, a new proof of the celebrated equality of pseudovarieties \(\mathbf {PG}=\mathbf {BG}\) is obtained, where \(\mathbf {PG}\) is the pseudovariety of monoids generated by the class of all power monoids of groups and \(\mathbf {BG}\) is the pseudovariety of all block groups.     

There is exactly one $${\mathbb {Z}}_2{\mathbb {Z}}_4$$-cyclic 1-perfect code

Let \(\mathcal{C}\) be a \({\mathbb {Z}}_2{\mathbb {Z}}_4\)-additive code of length \(n > 3\). We prove that if the binary Gray image of \(\mathcal{C}\) is a 1-perfect nonlinear code, then \(\mathcal{C}\) cannot be a \({\mathbb {Z}}_2{\mathbb {Z}}_4\)-cyclic code except for one case of length \(n=15\). Moreover, we give a parity check matrix for this cyclic code. Adding an even parity check coordinate to a \({\mathbb {Z}}_2{\mathbb {Z}}_4\)-additive 1-perfect code gives a \({\mathbb {Z}}_2{\mathbb {Z}}_4\)-additive extended 1-perfect code. We also prove that such a code cannot be \({\mathbb {Z}}_2{\mathbb {Z}}_4\)-cyclic.     

On homogeneous hypersurfaces in $${\mathbb {C}}^3$$

We consider a family \(M_t^n\), with \(n\geqslant 2\), \(t>1\), of real hypersurfaces in a complex affine n-dimensional quadric arising in connection with the classification of homogeneous compact simply connected real-analytic hypersurfaces in  \({\mathbb {C}}^n\) due to Morimoto and Nagano. To finalize their classification, one needs to resolve the problem of the embeddability of \(M_t^n\) in  \({\mathbb {C}}^n\) for \(n=3,7\). In our earlier article we showed that \(M_t^7\) is not embeddable in  \({\mathbb {C}}^7\) for every t and that \(M_t^3\) is embeddable in  \({\mathbb {C}}^3\) for all \(1<t<1+10^{-6}\). In the present paper, we improve on the latter result by showing that the embeddability of \(M_t^3\) in fact takes place for \(1<t<\sqrt{(2+\sqrt{2})/3}\). This is achieved by analyzing the explicit totally real embedding of the sphere \(S^3\) in \({\mathbb {C}}^3\) constructed by Ahern and Rudin. For \(t\geqslant {\sqrt{(2+\sqrt{2})/3}}\), the problem of the embeddability of \(M_t^3\) remains open.     

The Transition Density of Brownian Motion Killed on a Bounded Set

We study the transition density of a standard two-dimensional Brownian motion killed when hitting a bounded Borel set A. We derive the asymptotic form of the density, say \(p^A_t(\mathbf{x},\mathbf{y})\), for large times t and for \(\mathbf{x}\) and \(\mathbf{y}\) in the exterior of A valid uniformly under the constraint \(|\mathbf{x}|\vee |\mathbf{y}| =O(t)\). Within the parabolic regime \(|\mathbf{x}|\vee |\mathbf{y}| = O(\sqrt{t})\) in particular \(p^A_t(\mathbf{x},\mathbf{y})\) is shown to behave like \(4e_A(\mathbf{x})e_A(\mathbf{y}) (\lg t)^{-2} p_t(\mathbf{y}-\mathbf{x})\) for large t, where \(p_t(\mathbf{y}-\mathbf{x})\) is the transition kernel of the Brownian motion (without killing) and \(e_A\) is the Green function for the ‘exterior of A’ with a pole at infinity normalized so that \(e_A(\mathbf{x}) \sim \lg |\mathbf{x}|\). We also provide fairly accurate upper and lower bounds of \(p^A_t(\mathbf{x},\mathbf{y})\) for the case \(|\mathbf{x}|\vee |\mathbf{y}|>t\) as well as corresponding results for the higher dimensions.     

Chebyshev polynomials of the second kind via raising operator preserving the orthogonality

It is well known that monic orthogonal polynomial sequences \(\{T_n\}_{n\ge 0}\) and \(\{U_n\}_{n\ge 0}\), the Chebyshev polynomials of the first and second kind, satisfy the relation \(DT_{n+1}=(n+1)U_n\) (\(n\ge 0\)). One can also easily check that the following “inverse” of the mentioned formula holds: \({\mathcal {U}}_{-1}(U_n)=(n+1)T_{n+1}\) (\(n\ge 0\)), where \({\mathcal {U}}_\xi =x(xD+{\mathbb {I}})+\xi D\) with \(\xi \) being an arbitrary nonzero parameter and \({\mathbb {I}}\) representing the identity operator. Note that whereas the first expression involves the operator D which lowers the degree by one, the second one involves \({\mathcal {U}}_\xi \) which raises the degree by one (i.e. it is a “raising operator”). In this paper it is shown that the scaled Chebyshev polynomial sequence \(\{a^{-n}U_n(ax)\}_{n\ge 0}\) where \(a^2=-\xi ^{-1}\), is actually the only monic orthogonal polynomial sequence which is \({\mathcal {U}}_\xi \)-classical (i.e. for which the application of the raising operator \({\mathcal {U}}_\xi \) turns the original sequence into another orthogonal one).     

Morrey–Sobolev Extension Domains

We show that every uniform domain of \({{{\mathbb {R}}}^n}\) with \(n\ge 2\) is a Morrey–Sobolev \({\mathscr {W}}^{1,\,p}\)-extension domain for all \(p\in [1,\,n)\), and moreover, that this result is essentially the best possible for each \(p\in [1,\,n)\) in the sense that, given a simply connected planar domain or a domain of \({{{\mathbb {R}}}^n}\) with \(n\ge 3\) that is quasiconformal equivalent to a uniform domain, if it is a \({\mathscr {W}}^{1,\,p} \)-extension domain, then it must be uniform.