Global injectivity conditions for planar maps

We prove that a planar $C^1$ -smooth map $f:D\longrightarrow \mathbb{R }^{2n}$ , where $D\subseteq \mathbb{R }^{2n}$ is a convex open set, is injective if $\mathbb{R }\cap \mathrm{Spec}(df)_z=\emptyset $ for all $z\in D$ . We continue by showing that the triangulability of the differentials $(df)_z$ , $z\in D$ , ensure the global injectivity as well.     

The convex hull of the lattice points inside a curve

Let $C$ be a smooth convex closed plane curve. The $C$ -ovals $C(R,u,v)$ are formed by expanding by a factor  $R$ , then translating by  $(u,v)$ . The number of vertices $V(R,u,v)$ of the convex hull of the integer points within or on  $C(R,u,v)$ has order  $R^{2/3}$ (Balog and Bárány) and has average size $BR^{2/3}$ as $R$ varies (Balog and Deshouillers). We find the space average of  $V(R,u,v)$ over vectors  $(u,v)$ to be  $BR^{2/3}$ with an explicit coefficient  $B$ , and show that the average over  $R$ has the same  $B$ . The proof involves counting edges and finding the domain $D(q,a)$ of an integer vector, the set of  $(u,v)$ for which the convex hull has a directed edge parallel to  $(q,a)$ . The resulting sum over bases of the integer lattice is approximated by a triple integral.     

Optimal Reconstruction Might be Hard

Given as input a point set $\mathcal S $ that samples a shape $\mathcal A $ , the condition required for inferring Betti numbers of $\mathcal A $ from $\mathcal S $ in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of $\mathcal A $ from $\mathcal S $ . Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given 2 two-dimensional simplicial complexes $L \subset K$ , does there exist a simplicial complex containing $L$ and contained in $K$ which realizes the persistent homology of $L$ into $K$ ? We call this problem the homological simplification of the pair $(K,L)$ and prove that this problem is NP-complete, using a reduction from 3SAT.     

A unified approach for minimizing composite norms

We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem $$\begin{aligned} \begin{array}{ll} \min \limits _{X\in \mathbb{R }^{m\times n}}&\mu _1\Vert \sigma (\mathcal{F }(X)-G)\Vert _\alpha +\mu _2\Vert \mathcal{C }(X)-d\Vert _\beta ,\\ \text{ subject} \text{ to}&\mathcal{A }(X)-b\in \mathcal{Q }, \end{array} \end{aligned}$$ where $\sigma (X)$ denotes the vector of singular values of $X \in \mathbb{R }^{m\times n}$ , the matrix norm $\Vert \sigma (X)\Vert _{\alpha }$ denotes either the Frobenius, the nuclear, or the $\ell _2$ -operator norm of $X$ , the vector norm $\Vert .\Vert _{\beta }$ denotes either the $\ell _1$ -norm, $\ell _2$ -norm or the $\ell _{\infty }$ -norm; $\mathcal{Q }$ is a closed convex set and $\mathcal{A }(.)$ , $\mathcal{C }(.)$ , $\mathcal{F }(.)$ are linear operators from $\mathbb{R }^{m\times n}$ to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), and stable PCP problems are all special cases of the composite norm minimization problem. Thus, FALC is able to solve all these problems in a unified manner. We show that any limit point of FALC iterate sequence is an optimal solution of the composite norm minimization problem. We also show that for all $\epsilon >0$ , the FALC iterates are $\epsilon $ -feasible and $\epsilon $ -optimal after $\mathcal{O }(\log (\epsilon ^{-1}))$ iterations, which require $\mathcal{O }(\epsilon ^{-1})$ constrained shrinkage operations and Euclidean projection onto the set $\mathcal{Q }$ . Surprisingly, on the problem sets we tested, FALC required only $\mathcal{O }(\log (\epsilon ^{-1}))$ constrained shrinkage, instead of the $\mathcal{O }(\epsilon ^{-1})$ worst case bound, to compute an $\epsilon $ -feasible and $\epsilon $ -optimal solution. To best of our knowledge, FALC is the first algorithm with a known complexity bound that solves the stable PCP problem.     

How large dimension guarantees a given angle?

We study the following two problems: (1) Given $n\ge 2$ and $0\le \alpha \le 180^\circ $ , how large Hausdorff dimension can a compact set $A\subset \mathbb{R }^n$ have if $A$ does not contain three points that form an angle $\alpha $ ? (2) Given $\alpha $ and $\delta $ , how large Hausdorff dimension can a subset $A$ of a Euclidean space have if $A$ does not contain three points that form an angle in the $\delta $ -neighborhood of $\alpha $ ? An interesting phenomenon is that different angles show different behaviour in the above problems. Apart from the clearly special extreme angles $0$ and $180^\circ $ , the angles $60^\circ , 90^\circ $ and $120^\circ $ also play special role in problem (2): the maximal dimension is smaller for these angles than for the other angles. In problem (1) the angle $90^\circ $ seems to behave differently from other angles.     

Spectral self-affine measures with prime determinant

The self-affine measure $\mu _{M,D}$ relating to an expanding matrix $M\in M_{n}(\mathbb Z )$ and a finite digit set $D\subset \mathbb Z ^n$ is a unique probability measure satisfying the self-affine identity with equal weight. In the present paper, we shall study the spectrality of $\mu _{M,D}$ in the case when $|\det (M)|=p$ is a prime. The main result shows that under certain mild conditions, if there are two points $s_{1}, s_{2}\in \mathbb R ^{n}, s_{1}-s_{2}\in \mathbb Z ^{n}$ such that the exponential functions $e_{s_{1}}(x), e_{s_{2}}(x)$ are orthogonal in $L^{2}(\mu _{M,D})$ , then the self-affine measure $\mu _{M,D}$ is a spectral measure with lattice spectrum. This gives some sufficient conditions for a self-affine measure to be a lattice spectral measure.     

Characterization of some simple groups by the multiplicity pattern

Let $G$ be a finite group and let ${\mathrm{Irr}}(G)$ denote the set of all complex irreducible characters of $G.$ Let ${\mathrm{cd}}(G)$ be the set of all character degrees of $G.$ For each positive integer $d,$ the multiplicity of $d$ in $G$ is defined to be the number of irreducible characters of $G$ having the same degree $d.$ The multiplicity pattern ${\mathrm{mp}}(G)$ is the vector whose first coordinate is $|G:G^{\prime }|$ and for $i\ge 1,$ the $(i+1)$ th-coordinate of ${\mathrm{mp}}(G)$ is the multiplicity of the $i$ th-smallest nontrivial character degree of $G.$ In this paper, we show that every nonabelian simple group with at most $7$ distinct character degrees is uniquely determined by the multiplicity pattern.     

Linear complementarity as absolute value equation solution

We consider the linear complementarity problem (LCP): $Mz+q\ge 0, z\ge 0, z^{\prime }(Mz+q)=0$ as an absolute value equation (AVE): $(M+I)z+q=|(M-I)z+q|$ , where $M$ is an $n\times n$ square matrix and $I$ is the identity matrix. We propose a concave minimization algorithm for solving (AVE) that consists of solving a few linear programs, typically two. The algorithm was tested on 500 consecutively generated random solvable instances of the LCP with $n=10, 50, 100, 500$ and 1,000. The algorithm solved $100\,\%$ of the test problems to an accuracy of $10^{-8}$ by solving 2 or less linear programs per LCP problem.     

A unified algorithm for mixed l_{2,p}-minimizations and its application in feature selection

Recently, matrix norm $l_{2,1}$ has been widely applied to feature selection in many areas such as computer vision, pattern recognition, biological study and etc. As an extension of $l_1$ norm, $l_{2,1}$ matrix norm is often used to find jointly sparse solution. Actually, computational studies have showed that the solution of $l_p$ -minimization ( $0<p<1$ ) is sparser than that of $l_1$ -minimization. The generalized $l_{2,p}$ -minimization ( $p\in (0,1]$ ) is naturally expected to have better sparsity than $l_{2,1}$ -minimization. This paper presents a type of models based on $l_{2,p}\ (p\in (0, 1])$ matrix norm which is non-convex and non-Lipschitz continuous optimization problem when $p$ is fractional ( $0<p<1$ ). For all $p$ in $(0, 1]$ , a unified algorithm is proposed to solve the $l_{2,p}$ -minimization and the convergence is also uniformly demonstrated. In the practical implementation of algorithm, a gradient projection technique is utilized to reduce the computational cost. Typically different $l_{2,p}\ (p\in (0,1])$ are applied to select features in computational biology.     

Stability results for the N-dimensional Schiffer conjecture via a perturbation method

Given a eigenvalue $\mu _{0m}^2$ of $-\Delta $ in the unit ball $B_1$ , with Neumann boundary conditions, we prove that there exists a class $\mathcal{D}$ of $C^{0,1}$ -domains, depending on $\mu _{0m} $ , such that if $u$ is a no trivial solution to the following problem $ \Delta u+\mu u=0$ in $\Omega , u=0$ on $\partial \Omega $ , and $ \int \nolimits _{\partial \Omega }\partial _{\mathbf{n}}u=0$ , with $\Omega \in \mathcal{D}$ , and $\mu =\mu _{0m}^2+o(1)$ , then $\Omega $ is a ball. Here $\mu $ is a eigenvalue of $-\Delta $ in $\Omega $ , with Neumann boundary conditions.     

Compression-based distance between string data and its application to literary work classification based on authorship

There are many well-known document classification/clustering algorithms. In this paper, compression-based distances between documents are focused on, in particular, the normalized compression distance (NCD). The NCD is a popular and powerful metric between strings. A new distance $D_\alpha $ with one parameter $\alpha $ between strings is designed on the basis of the NCD, and several properties of $D_\alpha $ are studied. It is also proved that every pair of strings $(x,y)$ can be plotted on the contour graphs of NCD and $D_\alpha $ (and some other compression-based distances) in a 2-dimensional plane. The distance $D_\alpha (x,y)$ is defined to take a relatively small value if a string $x$ is a portion of a string $y.$ Literary works $x$ and $y$ are usually assumed to be written by the same author(s) if $x$ is a portion of $y.$ Therefore, it may be appropriate to consider the performance of $D_\alpha $ for literary work classification based on authorship, as a benchmark. An algorithm to determine an appropriate value of $\alpha $ is presented using the contour graphs, and this algorithm does not require the knowledge of the names of the authors of each work. According to experimental results of the area under receiver operating characteristics curves and clustering, $D_\alpha $ with such an appropriate value of $\alpha $ performs somewhat better in literary work classification based on authorship.     

Some properties of a hypergeometric function which appear in an approximation problem

In this paper we consider properties and power expressions of the functions $f:(-1,1)\rightarrow \mathbb{R }$ and $f_L:(-1,1)\rightarrow \mathbb{R }$ , defined by $$\begin{aligned} f(x;\gamma )=\frac{1}{\pi }\int \limits _{-1}^1 \frac{(1+xt)^\gamma }{\sqrt{1-t^2}}\,\mathrm{d}t \quad \text{ and}\quad f_L(x;\gamma )=\frac{1}{\pi }\int \limits _{-1}^1 \frac{(1+xt)^\gamma \log (1+x t)}{\sqrt{1-t^2}}\,\mathrm{d}t, \end{aligned}$$ respectively, where $\gamma $ is a real parameter, as well as some properties of a two parametric real-valued function $D(\,\cdot \,;\alpha ,\beta ) :(-1,1) \rightarrow \mathbb{R }$ , defined by $$\begin{aligned} D(x;\alpha ,\beta )= f(x;\beta )f(x;-\alpha -1)- f(x;-\alpha )f(x;\beta -1),\quad \alpha ,\beta \in \mathbb{R }. \end{aligned}$$ The inequality of Turán type $$\begin{aligned} D(x;\alpha ,\beta )>0,\quad -1<x<1, \end{aligned}$$ for $\alpha +\beta >0$ is proved, as well as an opposite inequality if $\alpha +\beta <0$ . Finally, for the partial derivatives of $D(x;\alpha ,\beta )$ with respect to $\alpha $ or $\beta $ , respectively $A(x;\alpha ,\beta )$ and $B(x;\alpha ,\beta )$ , for which $A(x;\alpha ,\beta )=B(x;-\beta ,-\alpha )$ , some results are obtained. We mention also that some results of this paper have been successfully applied in various problems in the theory of polynomial approximation and some “truncated” quadrature formulas of Gaussian type with an exponential weight on the real semiaxis, especially in a computation of Mhaskar–Rahmanov–Saff numbers.     

Pfaffian representations of cubic surfaces

Let $\mathbb{K }$ be a field of characteristic zero. We describe an algorithm which requires a homogeneous polynomial $F$ of degree three in $\mathbb{K }[x_{0},x_1,x_{2},x_{3}]$ and a zero ${\mathbf{a }}$ of $F$ in $\mathbb{P }^{3}_{\mathbb{K }}$ and ensures a linear Pfaffian representation of $\text{ V}(F)$ with entries in $\mathbb{K }[x_{0},x_{1},x_{2},x_{3}]$ , under mild assumptions on $F$ and ${\mathbf{a }}$ . We use this result to give an explicit construction of (and to prove the existence of) a linear Pfaffian representation of $\text{ V}(F)$ , with entries in $\mathbb{K }^{\prime }[x_{0},x_{1},x_{2},x_{3}]$ , being $\mathbb{K }^{\prime }$ an algebraic extension of $\mathbb{K }$ of degree at most six. An explicit example of such a construction is given.     

Complexity of unconstrained L_2-L_p minimization

We consider the unconstrained $L_q$ - $L_p$ minimization: find a minimizer of $\Vert Ax-b\Vert ^q_q+\lambda \Vert x\Vert ^p_p$ for given $A \in R^{m\times n}$ , $b\in R^m$ and parameters $\lambda >0$ , $p\in [0, 1)$ and $q\ge 1$ . This problem has been studied extensively in many areas. Especially, for the case when $q=2$ , this problem is known as the $L_2-L_p$ minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the $L_q$ - $L_p$ problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function $\Vert \cdot \Vert ^p_p$ . In this paper, we show that the $L_q$ - $L_p$ minimization problem is strongly NP-hard for any $p\in [0,1)$ and $q\ge 1$ , including its smoothed version. On the other hand, we show that, by choosing parameters $(p,\lambda )$ carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.     

Hypercentralizing generalized skew derivations on left ideals in prime rings

Let $\mathcal{R }$ be a prime ring of characteristic different from $2, \mathcal{Q }_r$ the right Martindale quotient ring of $\mathcal{R }, \mathcal{C }$ the extended centroid of $\mathcal{R }, \mathcal{I }$ a nonzero left ideal of $\mathcal{R }, F$ a nonzero generalized skew derivation of $\mathcal{R }$ with associated automorphism $\alpha $ , and $n,k \ge 1$ be fixed integers. If $[F(r^n),r^n]_k=0$ for all $r \in \mathcal{I }$ , then there exists $\lambda \in \mathcal{C }$ such that $F(x)=\lambda x$ , for all $x\in \mathcal{I }$ . More precisely one of the following holds: (1) $\alpha $ is an $X$ -inner automorphism of $\mathcal{R }$ and there exist $b,c \in \mathcal{Q }_r$ and $q$ invertible element of $\mathcal{Q }_r$ , such that $F(x)=bx-qxq^{-1}c$ , for all $x\in \mathcal{Q }_r$ . Moreover there exists $\gamma \in \mathcal{C }$ such that $\mathcal{I }(q^{-1}c-\gamma )=(0)$ and $b-\gamma q \in \mathcal{C }$ ; (2) $\alpha $ is an $X$ -outer automorphism of $\mathcal{R }$ and there exist $c \in \mathcal{Q }_r, \lambda \in \mathcal{C }$ , such that $F(x)=\lambda x-\alpha (x)c$ , for all $x\in \mathcal{Q }_r$ , with $\alpha (\mathcal{I })c=0$ .     

On the zeros of Meixner polynomials

We investigate the zeros of a family of hypergeometric polynomials $M_n(x;\beta ,c)=(\beta )_n\,{}_2F_1(-n,-x;\beta ;1-\frac{1}{c})$ , $n\in \mathbb N ,$ known as Meixner polynomials, that are orthogonal on $(0,\infty )$ with respect to a discrete measure for $\beta >0$ and $0<c<1.$ When $\beta =-N$ , $N\in \mathbb N $ and $c=\frac{p}{p-1}$ , the polynomials $K_n(x;p,N)=(-N)_n\,{}_2F_1(-n,-x;-N;\frac{1}{p})$ , $n=0,1,\ldots , N$ , $0<p<1$ are referred to as Krawtchouk polynomials. We prove results for the zero location of the orthogonal polynomials $M_n(x;\beta ,c)$ , $c<0$ and $n<1-\beta $ , the quasi-orthogonal polynomials $M_n(x;\beta ,c)$ , $-k<\beta <-k+1$ , $k=1,\ldots ,n-1$ and $0<c<1$ or $c>1,$ as well as the polynomials $K_{n}(x;p,N)$ with non-Hermitian orthogonality for $0<p<1$ and $n=N+1,N+2,\ldots $ . We also show that the polynomials $M_n(x;\beta ,c)$ , $\beta \in \mathbb R $ are real-rooted when $c\rightarrow 0$ .     

Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes

Let $\Delta _{n-1}$ denote the $(n-1)$ -dimensional simplex. Let $Y$ be a random $d$ -dimensional subcomplex of $\Delta _{n-1}$ obtained by starting with the full $(d-1)$ -dimensional skeleton of $\Delta _{n-1}$ and then adding each $d$ -simplex independently with probability $p=\frac{c}{n}$ . We compute an explicit constant $\gamma _d$ , with $\gamma _2 \simeq 2.45$ , $\gamma _3 \simeq 3.5$ , and $\gamma _d=\Theta (\log d)$ as $d \rightarrow \infty $ , so that for $c < \gamma _d$ such a random simplicial complex either collapses to a $(d-1)$ -dimensional subcomplex or it contains $\partial \Delta _{d+1}$ , the boundary of a $(d+1)$ -dimensional simplex. We conjecture this bound to be sharp. In addition, we show that there exists a constant $\gamma _d< c_d <d+1$ such that for any $c>c_d$ and a fixed field $\mathbb{F }$ , asymptotically almost surely $H_d(Y;\mathbb{F }) \ne 0$ .     

Growth estimates for orbits of self-adjoint groups

Let $G$ denote a closed, connected, self-adjoint, noncompact subgroup of $GL(n,\mathbb R )$ , and let $d_{R}$ and $d_{L}$ denote respectively the right and left invariant Riemannian metrics defined by the canonical inner product on $M(n,\mathbb R ) = T_{I} GL(n,\mathbb R )$ . Let $v$ be a nonzero vector of $\mathbb R ^{n}$ such that the orbit $G(v)$ is unbounded in $\mathbb R ^{n}$ . Then the function $g \rightarrow d_{R}(g, G_{v})$ is unbounded, where $G_{v} = \{g \in G : g(v) = v \}$ , and we obtain algebraically defined upper and lower bounds $\lambda ^{+}(v)$ and $\lambda ^{-}(v)$ for the asymptotic behavior of the function $\frac{log|g(v)|}{d_{R}(g, G_{v})}$ as $d_{R}(g, G_{v}) \rightarrow \infty $ . The upper bound $\lambda ^{+}(v)$ is at most 1. The orbit $G(v)$ is closed in $\mathbb R ^{n} \Leftrightarrow \lambda ^{-}(w)$ is positive for some w $\in G(v)$ . If $G_{v}$ is compact, then $g \rightarrow |d_{R}(g,I) - d_{L}(g,I)|$ is uniformly bounded in $G$ , and the exponents $\lambda ^{+}(v)$ and $\lambda ^{-}(v)$ are sharp upper and lower asymptotic bounds for the functions $\frac{log|g(v)|}{d_{R}(g,I)}$ and $\frac{log|g(v)|}{d_{L}(g,I)}$ as $d_{R}(g,I) \rightarrow \infty $ or as $d_{L}(g,I) \rightarrow \infty $ . However, we show by example that if $G_{v}$ is noncompact, then there need not exist asymptotic upper and lower bounds for the function $\frac{log|g(v)|}{d_{L}(g, G_{v})}$ as $d_{L}(g, G_{v}) \rightarrow \infty $ . The results apply to representations of noncompact semisimple Lie groups $G$ on finite dimensional real vector spaces. We compute $\lambda ^{+}$ and $\lambda ^{-}$ for the irreducible, real representations of $SL(2,\mathbb R )$ , and we show that if the dimension of the $SL(2,\mathbb R )$ -module $V$ is odd, then $\lambda ^{+} = \lambda ^{-}$ on a nonempty open subset of $V$ . We show that the function $\lambda ^{-}$ is $K$ -invariant, where $K = O(n,\mathbb R ) \cap G$ . We do not know if $\lambda ^{-}$ is $G$ -invariant.     

An Index Formula in Connection with Meromorphic Approximation

Let $\Phi $ be a continuous $n\times n$ matrix-valued function on the unit circle $\mathbb T $ such that the $(k-1)$ st singular value of the Hankel operator with symbol $\Phi $ is greater than the $k$ th singular value. In this case, it is well-known that $\Phi $ has a unique superoptimal meromorphic approximant $Q$ in $H^{\infty }_{(k)}$ ; that is, $Q$ has at most $k$ poles in the unit disc $\mathbb D $ (in the sense that the McMillan degree of $Q$ in $\mathbb D $ is at most $k$ ) and $Q$ minimizes the essential suprema of singular values $s_{j}\left((\Phi -Q)(\zeta )\right)\!, j\ge 0$ , with respect to the lexicographic ordering. For each $j\ge 0$ , the essential supremum of $s_{j}\left((\Phi -Q)(\zeta )\right)$ is called the $j$ th superoptimal singular value of degree $k$ of $\Phi $ . We prove that if $\Phi $ has $n$ non-zero superoptimal singular values of degree $k$ , then the Toeplitz operator $T_{\Phi -Q}$ with symbol $\Phi -Q$ is Fredholm and has index $$ \mathrm{ind}T_{\Phi -Q}=\dim \ker T_{\Phi -Q}=2k+\dim \mathcal E , $$ where $\mathcal E =\{ \xi \in \ker H_{Q}: \Vert H_{\Phi }\xi \Vert _{2}=\Vert (\Phi -Q)\xi \Vert _{2}\}$ and $H_{\Phi }$ denotes the Hankel operator with symbol $\Phi $ . This result can in fact be extended from continuous matrix-valued functions to the wider class of $k$ -admissible matrix-valued functions, i.e. essentially bounded $n\times n$ matrix-valued functions $\Phi $ on $\mathbb T $ for which the essential norm of the Hankel operator $H_{\Phi }$ is strictly less than the smallest non-zero superoptimal singular value of degree $k$ of $\Phi $ .     

p-Groups with few conjugacy classes of normalizers

For a group $G$ , denote by $\omega (G)$ the number of conjugacy classes of normalizers of subgroups of $G$ . Clearly, $\omega (G)=1$ if and only if $G$ is a Dedekind group. Hence if $G$ is a 2-group, then $G$ is nilpotent of class $\le 2$ and if $G$ is a $p$ -group, $p>2$ , then $G$ is abelian. We prove a generalization of this. Let $G$ be a finite $p$ -group with $\omega (G)\le p+1$ . If $p=2$ , then $G$ is of class $\le 3$ ; if $p>2$ , then $G$ is of class $\le 2$ .