Search

In this paper we investigate quasi-Monte Carlo (QMC) integration using digital nets over Z b in reproducing kernel Hilbert spaces. The tent transformation (previously called baker’s transform) was originally used for lattice rules by Hickernell (2002) to achieve higher order convergence of the integration error for smooth non-periodic integrands, and later, has been successfully applied to digital nets over Z 2 by Cristea et al. (2007) and Goda (2015). The aim of this paper is to generalize the latter two results to digital nets over Z b for an arbitrary prime b . For this purpose, we introduce the b -adic tent transformation for an arbitrary positive integer b greater than 1, which is a generalization of the original (dyadic) tent transformation. Further, again for an arbitrary positive integer b greater than 1, we analyze the mean square worst-case error of QMC rules using digital nets over Z b which are randomly digitally shifted and then folded using the b -adic tent transformation in reproducing kernel Hilbert spaces. Using this result, for a prime b , we prove the existence of good higher order polynomial lattice rules over Z b among a smaller number of candidates as compared to the result by Dick and Pillichshammer (2007), which achieve almost the optimal convergence rate of the mean square worst-case error in unanchored Sobolev spaces of smoothness of arbitrary high order.

We say that the polynomial sequence $(Q^{(\lambda)}_n)$ is a semiclassical Sobolev polynomial sequence when it is orthogonal with respect to the inner product $$ _S= +\lambda , $$ where ${\bf u}$ is a semiclassical linear functional, ${\mathscr D}$ is the differential, the difference or the $q$--difference operator, and $\lambda$ is a positive constant. In this paper we get algebraic and differential/difference properties for such polynomials as well as algebraic relations between them and the polynomial sequence orthogonal with respect to the semiclassical functional $\bf u$. The main goal of this article is to give a general approach to the study of the polynomials orthogonal with respect to the above nonstandard inner product regardless of the type of operator ${\mathscr D}$ considered. Finally, we illustrate our results by applying them to some known families of Sobolev orthogonal polynomials as well as to some new ones introduced in this paper for the first time., Comment: 23 pages, special issue dedicated to Professor Guillermo Lopez lagomasino on the occasion of his 60th birthday, accepted in Journal of Approximation Theory

Let (\Pi,\Sigma) be a Coxeter system. An ordered list of elements in \Sigma and an element in \Pi determine a {\em subword complex}, as introduced in our paper on Gr\"obner geometry of Schubert polynomials (math.AG/0110058). Subword complexes are demonstrated here to be homeomorphic to balls or spheres, and their Hilbert series are shown to reflect combinatorial properties of reduced expressions in Coxeter groups. Two formulae for double Grothendieck polynomials, one of which is due to Fomin and Kirillov, are recovered in the context of simplicial topology for subword complexes. Some open questions related to subword complexes are presented., Comment: 14 pages. Final version, to appear in Advances in Mathematics. This paper was split off from math.AG/0110058v2, whose version 3 is now shorter

Let g be a symmetrisable Kac-Moody algebra, and U_h(g) the corresponding quantum group. We showed in arXiv:1610.09744 and arXiv:1610.09741 that the braided quasi-Coxeter structure on integrable, category O representations of U_h(g) which underlies the R-matrix actions arising from the Levi subalgebras of U_h(g) and the quantum Weyl group action of the generalised braid group B_g can be transferred to integrable, category O representations of g. We prove in this paper that, up to unique equivalence, there is a unique such structure on the latter category with prescribed restriction functors, R--matrices, and local monodromies. This extends, simplifies and strengthens a similar result of the second author valid when g is semisimple, and is used in arXiv:1512.03041 to describe the monodromy of the rational Casimir connection of g in terms of the quantum Weyl group operators of U_h(g). Our main tool is a refinement of Enriquez's universal algebras, which is adapted to the PROP describing a Lie bialgebra graded by the non-negative roots of g., Expanded Introduction and Sec. 5 to discuss convolution product (5.11), cosimplicial structure on basis elements (5.13) and module structure on coinvariants (5.15). Minor revisions in Sec. 7.1 (gradings), 7.4 (deformation DY modules), 9.7 (exposition), 15.7 (Drinfeld double) and 15.15 (rigidity for diagrammatic KM algebras). Final version, to appear in Adv. Math. 81 pages

Let $G$ be a finite connected graph, and let $\rho$ be the spectral radius of its universal cover. For example, if $G$ is $k$-regular then $\rho=2\sqrt{k-1}$. We show that for every $r$, there is an $r$-covering (a.k.a. an $r$-lift) of $G$ where all the new eigenvalues are bounded from above by $\rho$. It follows that a bipartite Ramanujan graph has a Ramanujan $r$-covering for every $r$. This generalizes the $r=2$ case due to Marcus, Spielman and Srivastava (2013). Every $r$-covering of $G$ corresponds to a labeling of the edges of $G$ by elements of the symmetric group $S_{r}$. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist. In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by Marcus-Spielman-Srivastava, a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from a recent paper of them (2015). Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the $r$-th matching polynomial of $G$ to be the average matching polynomial of all $r$-coverings of $G$. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside $\left[-\rho,\rho\right]$., Comment: 38 pages, 4 figures, journal version (minor changes from previous arXiv version). Shortened version appeared in STOC 2016

In this paper we find the optimal error bound (smallest possible estimate, independent of the starting point) for the linear convergence rate of the simultaneous projection method applied to closed linear subspaces in a real Hilbert space. We achieve this by computing the norm of an error operator which we also express in terms of the Friedrichs number. We compare our estimate with the optimal one provided for the alternating projection method by Kayalar and Weinert (1988). Moreover, we relate our result to the alternating projection formalization of Pierra (1984) in a product space. Finally, we adjust our results to closed affine subspaces and put them in context with recent dichotomy theorems., Accepted for publication in the Journal of Approximation Theory

Macaulay's Inverse System gives an effective method to construct Artinian Gorenstein k-algebras. To date a general structure for Gorenstein k-algebras of any dimension (and codimension) is not understood. In this paper we extend Macaulay's correspondence characterizing the submodules of the divided power ring in one-to-one correspondence with Gorenstein d-dimensional k-algebras. We discuss effective methods for constructing Gorenstein graded rings. Several examples illustrating our results are given., 19 pages, to appear in Advances in Mathematics

We prove novel results on interpolation of Fredholm operators including an abstract factorization theorem. The main result of this paper provides sufficient conditions on the parameters $\theta \in (0,1)$ and $q\in \lbrack 1,\infty ]$ under which an operator $A$ is a Fredholm operator from the real interpolation space $(X_{0},X_{1})_{\theta ,q}$ to $(Y_{0},Y_{1})_{\theta ,q} $ for a given operator $A\colon (X_{0},X_{1})\rightarrow (Y_{0},Y_{1})$ between compatible pairs of Banach spaces such that its restrictions to the endpoint spaces are Fredholm operators. These conditions are expressed in terms of the corresponding indices generated by the $K$-functional of elements from the kernel of the operator $A$ in the interpolation sum $X_{0}+X_{1}$. If in addition $q\in \lbrack 1,\infty )$ and $A$ is invertible operator on endpoint spaces, then these conditions are also necessary. We apply these results to obtain and present an affirmative solution of the famous Lions-Magenes problem on the real interpolation of closed subspaces. We also discuss some applications to the spectral theory of operators as well as to perturbation of the Hardy operator by identity on weighted $L_{p}$-spaces.

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over $\mathbb{Z}_{b}$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such \emph{folded digital nets} as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with "infinite digit expansions," which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good \emph{folded higher order polynomial lattice rules} that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.

We prove a few interesting inequalities for Lorentz polynomials. A highlight of this paper states that the Markov-type inequality max x ? - 1 , 1 ] | f ' ( x ) | ? n max x ? - 1 , 1 ] | f ( x ) | holds for all polynomials f of degree at most n with real coefficients for which f ' has all its zeros outside the open unit disk. Equality holds only for f ( x ) : = c ( ( 1 ? x ) n - 2 n - 1 ) with a constant 0 ? c ? R . This should be compared with Erd?s's classical result stating that max x ? - 1 , 1 ] | f ' ( x ) | ? n 2 ( n n - 1 ) n - 1 max x ? - 1 , 1 ] | f ( x ) | for all polynomials f of degree at most n having all their zeros in R ? ( - 1 , 1 ) .

Hurwitz numbers count branched covers of the Riemann sphere with specified ramification, or equivalently, transitive permutation factorizations in the symmetric group with specified cycle types. Monotone Hurwitz numbers count a restricted subset of these branched covers, related to the expansion of complete symmetric functions in the Jucys-Murphy elements, and have arisen in recent work on the the asymptotic expansion of the Harish-Chandra-Itzykson-Zuber integral. In previous work we gave an explicit formula for monotone Hurwitz numbers in genus zero. In this paper we consider monotone Hurwitz numbers in higher genera, and prove a number of results that are reminiscent of those for classical Hurwitz numbers. These include an explicit formula for monotone Hurwitz numbers in genus one, and an explicit form for the generating function in arbitrary positive genus. From the form of the generating function we are able to prove that monotone Hurwitz numbers exhibit a polynomiality that is reminiscent of that for the classical Hurwitz numbers, i.e., up to a specified combinatorial factor, the monotone Hurwitz number in genus g with ramification specified by a given partition is a polynomial indexed by g in the parts of the partition., Comment: 23 pages

In two previous papers we have presented partition formulas for the Fibonacci numbers motivated by the appearance of the Fibonacci numbers in the representation theory of the 3-Kronecker quiver and its universal cover, the 3-regular tree. Here we show that the basic information can be rearranged in two triangles. They are quite similar to the Pascal triangle of the binomial coefficients, but in contrast to the additivity rule for the Pascal triangle, we now deal with additivity along "hooks", or, equivalently, with additive functions for valued translation quivers. As for the Pascal triangle, we see that the numbers in these Fibonacci partition triangles arc given by evaluating polynomials. We show that the two triangles can be obtained from each other by looking at differences of numbers, it is sufficient to take differences along arrows and knight's moves. (C) 2012 Elsevier Inc. All rights reserved.

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least e d n edges of G to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. In this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a constant number of queries. As a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. None of these properties was previously known to be testable even with o(n) queries. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.

A seminal technique of theoretical physics called Wick's theorem interprets the Gaussian matrix integral of the products of the trace of powers of Hermitian matrices as the number of labelled maps with a given degree sequence, sorted by their Euler characteristics. This leads to the map enumeration results analogous to those obtained by combinatorial methods. In this paper we show that the enumeration of the graphs embeddable on a given 2-dimensional surface (a main research topic of contemporary enumerative combinatorics) can also be formulated as the Gaussian matrix integral of an ice-type partition function. Some of the most puzzling conjectures of discrete mathematics are related to the notion of the cycle double cover. We express the number of the graphs with a fixed directed cycle double cover as the Gaussian matrix integral of an Ihara-Selberg-type function., Comment: 23 pages, 2 figures

Let K be a field of characteristic 0. We consider linear equations a1*x1+...+an*xn=1 in unknowns x1,...,xn from G, where a1,...,an are non-zero elements of K, and where G is a subgroup of the multiplicative group of non-zero elements of K. Two tuples (a1,...,an) and (b1,...,bn) of non-zero elements of K are called G-equivalent if there are u1,...,un in G such that b1=a1*u1,..., bn=an*un. Denote by m(a1,...,an,G) the smallest number m such that the set of solutions of a1*x1+...+an*xn=1 in x1,...,xn from G is contained in the union of m proper linear subspaces of K^n. It is known that m(a1,...,an,G) is finite; clearly, this quantity does not change if (a1,...,an) is replaced by a G-equivalent tuple. Gyory and the author proved in 1988 that there is a constant c(n) depending only on the number of variables n, such that for all but finitely many G-equivalence classes (a1,...,an), one has m(a1,...,an,G)< c(n). It is as yet not clear what is the best possible value of c(n). Gyory and the author showed that c(n)=2^{(n+1)!} can be taken. This was improved by the author in 1993 to c(n)=(n!)^{2n+2}. In the present paper we improve this further to c(n)=2^{n+1}, and give an example showing that c(n) can not be smaller than n., 12 pages, latex file

Complete Boolean algebras proved to be an important tool in topology and set theory. Two of the most prominent examples are B(kappa), the algebra of Borel sets modulo measure zero ideal in the generalized Cantor space {0,1}^kappa equipped with product measure, and C(kappa), the algebra of regular open sets in the space {0,1}^kappa, for kappa an infinite cardinal. C(kappa) is much easier to analyse than B(kappa) : C(kappa) has a dense subset of size kappa, while the density of B(kappa) depends on the cardinal characteristics of the real line; and the definition of C(kappa) is simpler. Indeed, C(kappa) seems to have the simplest definition among all algebras of its size. In the Main Theorem of this paper we show that in a certain precise sense, C(aleph_1) has the simplest structure among all algebras of its size, too. MAIN THEOREM: If ZFC is consistent then so is ZFC + 2^{aleph_0}= aleph_2 +``for every complete Boolean algebra B of uniform density aleph_1, C(aleph_1) is isomorphic to a complete subalgebra of B''.