h-analogue of Fibonacci numbers

We introduce the \(h\) -analogue of Fibonacci numbers for non-commutative \(h\) -plane. For \(h h'= 1\) and \(h = 0\) , these are just the usual Fibonacci numbers as it should be. We show that the Laplace integral transforms for both the Fibonacci and Chebyshev polynomials are the \(h\) -Fibonacci numbers. We also derive a collection of identities for these numbers.     

Approximation faible et principe de Hasse pour des espaces homogènes à stabilisateur fini résoluble

Let \(K\) be a global field and \(G\) a finite solvable \(K\) -group. Under certain hypotheses concerning the extension splitting \(G\) , we show that the homogeneous space \(V=G'/G\) with \(G'\) a semi-simple simply connected \(K\) -group has the weak approximation property. We use a more precise version of this result to prove the Hasse principle for homogeneous spaces \(X\) under a semi-simple simply connected \(K\) -group \(G'\) with finite solvable geometric stabilizer \({\bar{G}}\) , under certain hypotheses concerning the \(K\) -kernel (or \(K\) -lien) \(({\bar{G}},\kappa )\) defined by \(X\) .     

Isomorphisms between Jacobson graphs

Let \(R\) be a commutative ring with a non-zero identity and \(\mathfrak {J}_R\) be its Jacobson graph. We show that if \(R\) and \(R'\) are finite commutative rings, then \(\mathfrak {J}_R\cong \mathfrak {J}_{R'}\) if and only if \(|J(R)|=|J(R')|\) and \(R/J(R)\cong R'/J(R')\) . Also, for a Jacobson graph \(\mathfrak {J}_R\) , we obtain the structure of group \(\mathrm {Aut}(\mathfrak {J}_R)\) of all automorphisms of \(\mathfrak {J}_R\) and prove that under some conditions two semi-simple rings \(R\) and \(R'\) are isomorphic if and only if \(\mathrm {Aut}(\mathfrak {J}_R)\cong \mathrm {Aut}(\mathfrak {J}_{R'})\) .     

Isomorphic Steiner symmetrization of p-convex sets

In this paper we show that given a \(p\) -convex set \(K \subset \mathbb{R }^n\) , there exist \(5n\) Steiner symmetrizations that transform it into an isomorphic Euclidean ball. That is, if \(|K| = |D_n| = \kappa _n\) , we may symmetrize it, using \(5n\) Steiner symmetrizations, into a set \(K'\) such that \(c_p D_n \subset K' \subset C_p D_n\) , where \(c_p\) and \(C_p\) are constants dependent on \(p\) only.     

L^2-properties of the \overline{\partial } and the \overline{\partial }-Neumann operator on spaces with isolated singularities

Let \(X\) be a Hermitian complex space of pure dimension with only isolated singularities and \(\pi : M\rightarrow X\) a resolution of singularities. Let \(\Omega \subset \subset X\) be a domain with no singularities in the boundary, \(\Omega ^*=\Omega {\setminus }\!{{\mathrm{Sing}}}X\) and \(\Omega '=\pi ^{-1}(\Omega )\) . We relate \(L^2\) -properties of the \(\overline{\partial }\) and the \(\overline{\partial }\) -Neumann operator on \(\Omega ^*\) to properties of the corresponding operators on \(\Omega '\) (where the situation is classically well understood). Outside some middle degrees, there are compact solution operators for the \(\overline{\partial }\) -equation on \(\Omega ^*\) exactly if there are such operators on the resolution \(\Omega '\) , and the \(\overline{\partial }\) -Neumann operator is compact on \(\Omega ^*\) exactly if it is compact on \(\Omega '\) .     

Note on prehomogeneous vector spaces

Let \(V\) be a complex prehomogeneous vector space under the action of a linear algebraic group \(G\) . Assume the poset of orbit closures in the Zariski topology \(\{\overline{Gx}:x\in V\}\) coincides with a (partial) flag \(V_0=0<V_1<\dots <V_k=V\) in \(V\) . Then for any Borel subgroup \(B\) of \(G\) , the poset \(\{\overline{B x}:x\in V\}\) coincides with a full flag in \(V\) .     

A Note on the Homotopy Type of the Alexander Dual

We investigate the homotopy type of the Alexander dual of a simplicial complex. It is known that in general the homotopy type of \(K\) does not determine the homotopy type of its dual \(K^*\) . We construct for each finitely presented group \(G\) , a simply connected simplicial complex \(K\) such that \(\pi _1(K^*)=G\) and study sufficient conditions on \(K\) for \(K^*\) to have the homotopy type of a sphere. We extend the simplicial Alexander duality to the more general context of reduced lattices and relate this construction with Bier spheres using deleted joins of lattices. Finally we introduce an alternative dual, in the context of reduced lattices, with the same homotopy type as the Alexander dual but smaller and simpler to compute.     

Tree metrics and edge-disjoint S-paths

Given an undirected graph \(G=(V,E)\) with a terminal set \(S \subseteq V\) , a weight function on terminal pairs, and an edge-cost \(a: E \rightarrow \mathbf{Z}_+\) , the \(\mu \) -weighted minimum-cost edge-disjoint \(S\) -paths problem ( \(\mu \) -CEDP) is to maximize \(\sum \nolimits _{P \in \mathcal{P}} \mu (s_P,t_P) - a(P)\) over all edge-disjoint sets \(\mathcal{P}\) of \(S\) -paths, where \(s_P,t_P\) denote the ends of \(P\) and \(a(P)\) is the sum of edge-cost \(a(e)\) over edges \(e\) in \(P\) . Our main result is a complete characterization of terminal weights \(\mu \) for which \(\mu \) -CEDP is tractable and admits a combinatorial min–max theorem. We prove that if \(\mu \) is a tree metric, then \(\mu \) -CEDP is solvable in polynomial time and has a combinatorial min–max formula, which extends Mader’s edge-disjoint \(S\) -paths theorem and its minimum-cost generalization by Karzanov. Our min–max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that \(\mu \) -EDP, which is \(\mu \) -CEDP with \(a = 0\) , is NP-hard if \(\mu \) is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, \(\mu \) -CEDP for a truncated tree metric \(\mu \) reduces to \(\mu '\) -CEDP for a tree metric \(\mu '\) . Thus our result is best possible unless P = NP. As an application, we obtain a good approximation algorithm for \(\mu \) -EDP with “near” tree metric \(\mu \) by utilizing results from the theory of low-distortion embedding.     

Generalization of Sabitov’s Theorem to Polyhedra of Arbitrary Dimensions

In 1996 Sabitov proved that the volume \(V\) of an arbitrary simplicial polyhedron \(P\) in the \(3\) -dimensional Euclidean space \(\mathbb {R}^3\) satisfies a monic (with respect to \(V\) ) polynomial relation \(F(V,\ell )=0\) , where \(\ell \) denotes the set of the squares of edge lengths of \(P\) . In 2011 the author proved the same assertion for polyhedra in \(\mathbb {R}^4\) . In this paper, we prove that the same result is true in arbitrary dimension \(n\ge 3\) . Moreover, we show that this is true not only for simplicial polyhedra, but for all polyhedra with triangular \(2\) -faces. As a corollary, we obtain the proof in arbitrary dimension of the well-known Bellows Conjecture posed by Connelly in 1978. This conjecture claims that the volume of any flexible polyhedron is constant. Moreover, we obtain the following stronger result. If \(P_t, t\in [0,1]\) , is a continuous deformation of a polyhedron such that the combinatorial type of \(P_t\) does not change and every \(2\) -face of \(P_t\) remains congruent to the corresponding face of \(P_0\) , then the volume of \(P_t\) is constant. We also obtain non-trivial estimates for the oriented volumes of complex simplicial polyhedra in \(\mathbb {C}^n\) from their orthogonal edge lengths.     

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

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.     

On lower bounds for cohomology growth in p-adic analytic towers

Let \(p\) and \(\ell \) be two distinct prime numbers and let \(\Gamma \) be a group. We study the asymptotic behaviour of the mod- \(\ell \) Betti numbers in \(p\) -adic analytic towers of finite index subgroups. If \(\Theta \) is a finite \(\ell \) -group of automorphisms of \(\Gamma \) , our main theorem allows to lift lower bounds for the mod- \(\ell \) cohomology growth in the fixed point group \(\Gamma ^\Theta \) to lower bounds for the growth in \(\Gamma \) . We give applications to \(S\) -arithmetic groups and we also obtain a similar result for cohomology with rational coefficients.     

Truncated Quillen complexes of p-groups

Let \(p\) be an odd prime and let \(P\) be a \(p\) -group. We examine the order complex of the poset of elementary abelian subgroups of \(P\) having order at least \(p^2\) . Bouc and Thévenaz showed that this complex has the homotopy type of a wedge of spheres. We show that, for each nonnegative integer \(l\) , the number of spheres of dimension \(l\) in this wedge is controlled by the number of extraspecial subgroups \(X\) of \(P\) having order \(p^{2l+3}\) and satisfying \(\Omega _1(C_P(X))=Z(X)\) . We go on to provide a negative answer to a question raised by Bouc and Thévenaz concerning restrictions on the homology groups of the given complex.     

Frequent Hypercyclicity of Random Entire Functions for the Differentiation Operator

We study the random entire functions defined as power series \(f(z) = \sum _{n=0}^\infty (X_n/n!) z^n\) with independent and identically distributed coefficients \((X_n)\) and show that, under very weak assumptions, they are frequently hypercyclic for the differentiation operator \(D: H({\mathbb {C}}) \rightarrow H({\mathbb {C}}),\,f \mapsto Df = f'\) . This gives a very simple probabilistic construction of \(D\) -frequently hypercyclic functions in \(H({\mathbb {C}})\) . Moreover we show that, under more restrictive assumptions on the distribution of the \((X_n)\) , these random entire functions have a growth rate that differs from the slowest growth rate possible for \(D\) -frequently hypercyclic entire functions at most by a factor of a power of a logarithm.     

A construction for strength-3 covering arrays from linear feedback shift register sequences

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252–260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial \(f\) of degree \(m\) over \(\mathbb F _q\) , by taking all unique subintervals of length \(\frac{q^m-1}{q-1}\) from the LFSR generated by \(f\) , we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For \(m=3\) , by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over \(q^2+q+1\) factors, each with \(q\) levels that has size only \(2q^3-1\) , i.e. a \(\text {CA}(2q^3-1; 3, q^2+q+1, q)\) whenever \(q\) is a prime power. When \(q\) is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all \(2 \le q \le 25\) . Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all \(q\) except \(q = 2,3,6\) . By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.     

Shellability of the higher pinched Veronese posets

The pinched Veronese poset \({\mathcal {V}}^{\bullet }_n\) is the poset with ground set consisting of all nonnegative integer vectors of length \(n\) such that the sum of their coordinates is divisible by \(n\) with exception of the vector \((1,\ldots ,1)\) . For two vectors \(\mathbf {a}\) and \(\mathbf {b}\) in \({\mathcal {V}}^{\bullet }_n\) , we have \(\mathbf {a}\preceq \mathbf {b}\) if and only if \(\mathbf {b}- \mathbf {a}\) belongs to the ground set of \({\mathcal {V}}^{\bullet }_n\) . We show that every interval in \({\mathcal {V}}^{\bullet }_n\) is shellable for \(n \ge 4\) . In order to obtain the result, we develop a new method for showing that a poset is shellable. This method differs from classical lexicographic shellability. Shellability of intervals in \({\mathcal {V}}^{\bullet }_n\) has consequences in commutative algebra. As a corollary, we obtain a combinatorial proof of the fact that the pinched Veronese ring is Koszul for \(n \ge 4\) . (This also follows from a result by Conca, Herzog, Trung, and Valla.)     

The ring of evenly weighted points on the line

Let \(M_w = ({\mathbb {P}}^1)^n /\!/\hbox {SL}_2\) denote the geometric invariant theory quotient of \(({\mathbb {P}}^1)^n\) by the diagonal action of \(\hbox {SL}_2\) using the line bundle \(\mathcal {O}(w_1,w_2,\ldots ,w_n)\) on \(({\mathbb {P}}^1)^n\) . Let \(R_w\) be the coordinate ring of \(M_w\) . We give a closed formula for the Hilbert function of \(R_w\) , which allows us to compute the degree of \(M_w\) . The graded parts of \(R_w\) are certain Kostka numbers, so this Hilbert function computes stretched Kostka numbers. If all the weights \(w_i\) are even, we find a presentation of \(R_w\) so that the ideal \(I_w\) of this presentation has a quadratic Gröbner basis. In particular, \(R_w\) is Koszul. We obtain this result by studying the homogeneous coordinate ring of a projective toric variety arising as a degeneration of \(M_w\) .     

Laplacian ideals,arrangements, and resolutions

The Laplacian matrix of a graph \(G\) describes the combinatorial dynamics of the Abelian Sandpile Model and the more general Riemann–Roch theory of \(G\) . The lattice ideal associated to the lattice generated by the columns of the Laplacian provides an algebraic perspective on this recently (re)emerging field. This binomial ideal \(I_G\) has a distinguished monomial initial ideal \(M_G\) , characterized by the property that the standard monomials are in bijection with the \(G\) -parking functions of the graph \(G\) . The ideal \(M_G\) was also considered by Postnikov and Shapiro (Trans Am Math Soc 356:3109–3142, 2004) in the context of monotone monomial ideals. We study resolutions of \(M_G\) and show that a minimal-free cellular resolution is supported on the bounded subcomplex of a section of the graphical arrangement of \(G\) . This generalizes constructions from Postnikov and Shapiro (for the case of the complete graph) and connects to work of Manjunath and Sturmfels, and of Perkinson et al. on the commutative algebra of Sandpiles. As a corollary, we verify a conjecture of Perkinson et al. regarding the Betti numbers of \(M_G\) and in the process provide a combinatorial characterization in terms of acyclic orientations.     

The range of holomorphic maps at boundary points

We prove a boundary version of the open mapping theorem for holomorphic maps between strongly pseudoconvex domains. That is, we prove that the local image of a holomorphic map \(f{:\,}D\rightarrow D'\) close to a boundary regular contact point \(p\in \partial D\) where the Jacobian is bounded away from zero along normal non-tangential directions has to eventually contain every cone (and more generally every region which is Kobayashi asymptotic to a cone) with vertex at \(f(p)\) .     

On an extension of the Frobenius^{\prime } theorem about p-nilpotency of a finite group

Suppose that \(G\) is a finite group and \(H\) is a subgroup of \(G\) . \(H\) is said to be \(s\) -quasinormally embedded in \(G\) if for each prime \(p\) dividing the order of \(H\) , a Sylow \(p\) -subgroup of \(H\) is also a Sylow \(p\) -subgroup of some \(s\) -quasinormal subgroup of \(G\) . We fix in every non-cyclic Sylow subgroup \(P\) of \(G\) some subgroup \(D\) satisfying \(1<|D|<|P|\) and study the \(p\) -nilpotency of \(G\) under the assumption that every subgroup \(H\) of \(P\) with \(|H|=|D|\) is \(s\) -quasinormally embedded in \(G\) . Some recent results and the Frobenius \(^{\prime }\) theorem are generalized.