Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

   Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

Weighted compound integration rules with higher order convergence for all N

Quasi-Monte Carlo integration rules, which are equal-weight sample averages of function values, have been popular for approximating multivariate integrals due to their superior convergence rate of order close to 1/N or better, compared to the order 1/?N1/\sqrt{N} of simple Monte Carlo algorithms. For practical applications, it is desirable to be able to increase the total number of sampling points N one or several at a time until a desired accuracy is met, while keeping all existing evaluations. We show that although a convergence rate of order close to 1/N can be achieved for all values of N (e.g., by using a good lattice sequence), it is impossible to get better than order 1/N convergence for all values of N by adding equally-weighted sampling points in this manner. We then prove that a convergence of order N ^− α for α > 1 can be achieved by weighting the sampling points, that is, by using a weighted compound integration rule. We apply our theory to lattice sequences and present some numerical results. The same theory also applies to digital sequences.     

Scrambling non-uniform nets

In this paper, we consider Owen’s scrambling of an (m−1, m, d)-net in base b which consists of d copies of a (0, m, 1)-net in base b, and derive an exact formula for the gain coefficients of these nets. This formula leads us to a necessary and sufficient condition for scrambled (m − 1, m, d)-nets to have smaller variance than simple Monte Carlo methods for the class of L ₂ functions on [0, 1] ^d . Secondly, from the viewpoint of the Latin hypercube scrambling, we compare scrambled non-uniform nets with scrambled uniform nets. An important consequence is that in the case of base two, many more gain coefficients are equal to zero in scrambled (m − 1, m, d)-nets than in scrambled Sobol’ points for practical size of samples and dimensions.      

Variations on polynomial subgroup growth

A groupG hasweak polynomial subgroup growth (wPSG) of degree ≤α if each finite quotient Ḡ ofG contains at most │Ḡ│ ^a subgroups. The main result is that wPSG of degree α implies polynomial subgroup growth (PSG) of degree at mostf(α). It follows that wPSG is equivalent to PSG. A corollary is that if, in a profinite groupG, thek-generator subgroups have positive “density” δ, thenG is finitely generated (the number of generators being bounded by a function ofk and δ).     

Computation of connection coefficients and measure modifications for orthogonal polynomials

We observe that polynomial measure modifications for families of univariate orthogonal polynomials imply sparse connection coefficient relations. We therefore propose connecting L ² expansion coefficients between a polynomial family and a modified family by a sparse transformation. Accuracy and conditioning of the connection and its inverse are explored. The connection and recurrence coefficients can simultaneously be obtained as the Cholesky decomposition of a matrix polynomial involving the Jacobi matrix; this property extends to continuous, non-polynomial measure modifications on finite intervals. We conclude with an example of a useful application to families of Jacobi polynomials with parameters (γ,δ) where the fast Fourier transform may be applied in order to obtain expansion coefficients whenever 2γ and 2δ are odd integers.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base 2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.     

Asymptotics and weighted estimates of meixner polynomials orthogonal on the gird {0, δ, 2δ, ...}

Suppose that 0<δ≤1,N=1/δ, and α, ga≥0, is an integer. For the classical Meixner polynomials orthonormal on the gird {0, δ, 2δ, ...} with weight ρ(x)=(1-e ^−δ)^αг(Nx+α+ 1)/г(Nx+1), the following asymptotic formula is obtained: . The remainderv _n,N ^α (z) forn≤λN satisfies the estimate

Construction of scrambled polynomial lattice rules over \mathbb{F}_{2} with small mean square weighted \mathcal{L}_{2} discrepancy

The \(\mathcal{L}_{2}\) discrepancy is one of several well-known quantitative measures for the equidistribution properties of point sets in the high-dimensional unit cube. The concept of weights was introduced by Sloan and Wo?niakowski to take into account the relative importance of the discrepancy of lower dimensional projections. As known under the name of quasi-Monte Carlo methods, point sets with small weighted \(\mathcal{L}_{2}\) discrepancy are useful in numerical integration. This study investigates the component-by-component construction of polynomial lattice rules over the finite field \(\mathbb{F}_{2}\) whose scrambled point sets have small mean square weighted \(\mathcal{L}_{2}\) discrepancy. An upper bound on this discrepancy is proved, which converges at almost the best possible rate of N ^?2+δ for all δ>0, where N denotes the number of points. Numerical experiments confirm that the performance of our constructed polynomial lattice point sets is comparable or even superior to that of Sobol’ sequences.     

A larger GL2 large sieve in the level aspect

In this paper we study the orthogonality of Fourier coefficients of holomorphic cusp forms in the sense of large sieve inequality. We investigate the family of GL ₂ cusp forms modular with respect to the congruence subgroups Γ₁(q), with additional averaging over the levels q ∼ Q. We obtain the orthogonality in the range N ≪ Q ^2−δ for any δ > 0, where N is the length of linear forms in the large sieve.     

Differential operators associated with zonal polynomials. I

Summary Associated with each zonal polynomial,C _k(S), of a symmetric matrixS, we define a differential operator ∂_k, having the basic property that ∂_kC_λδ_kλ, δ being Kronecker's delta, whenever κ and λ are partitions of the non-negative integerk. Using these operators, we solve the problems of determining the coefficients in the expansion of (i) the product of two zonal polynomials as a series of zonal polynomials, and (ii) the zonal polynomial of the direct sum,S⊕T, of two symmetric matricesS andT, in terms of the zonal polynomials ofS andT. We also consider the problem of expanding an arbitrary homogeneous symmetric polynomial,P(S) in a series of zonal polynomials. Further, these operators are used to derive identities expressing the doubly generalised binomial coefficients ( _P ^λ ),P(S) being a monomial in the power sums of the latent roots ofS, in terms of the coefficients of the zonal polynomials, and from these, various results are obtained.     

Herman’s theory revisited

We prove that a C ^2+α -smooth orientation-preserving circle diffeomorphism with rotation number in Diophantine class D _δ , 0≤δ<α≤1, α−δ≠1, is C ^1+α−δ -smoothly conjugate to a rigid rotation. This is the first sharp result on the smoothness of the conjugacy. We also derive the most precise version of Denjoy’s inequality for such diffeomorphisms.     

An overview of fast component-by-component constructions of lattice rules and lattice sequences

Since the initial work by I. H. Sloan and his collaborators on the component-by-component construction of good lattice rules for the approximation of multivariate integrals, a lot of variations on this theme have been published. These include various function spaces, prime and composite number of points, intermediate-rank rules, polynomial lattice rules and extensible rules. We sketch the different variations and discuss the properties needed to have a fast component-by-component construction. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Eigenfunctions for singular fully nonlinear equations in unbounded domains

In this paper, we prove the existence of a generalized eigenvalue and a corresponding eigenfunction for fully nonlinear elliptic operators singular or degenerate, homogeneous of degree 1+α, α > −1 in unbounded domains of IR ^N . The main tool will be Harnack’s inequality.     

Wave atoms and time upscaling of wave equations

We present a new geometric strategy for the numerical solution of hyperbolic wave equations in smoothly varying, two-dimensional time-independent periodic media. The method consists in representing the time-dependent Green’s function in wave atoms, a tight frame of multiscale, directional wave packets obeying a precise parabolic balance between oscillations and support size, namely wavelength ~(diameter).² Wave atoms offer a uniquely structured representation of the Green’s function in the sense that

A Note on the Distribution of the Distance from a Lattice

Let ℒ be an n-dimensional lattice, and let x be a point chosen uniformly from a large ball in ℝ ⁿ . In this note we consider the distribution of the distance from x to ℒ, normalized by the largest possible such distance (i.e., the covering radius of ℒ). By definition, the support of this distribution is [0,1]. We show that there exists a universal constant α ₂ that provides a natural “threshold” for this distribution in the following sense. For any ε>0, there exists a δ>0 such that for any lattice, this distribution has mass at least δ on [α ₂−ε,1]; moreover, there exist lattices for which the distribution is tightly concentrated around α ₂ (and so the mass on [α ₂+ε,1] can be arbitrarily small). We also provide several bounds on α ₂ and its extension to other ℓ _p norms. We end with an application from the area of computational complexity. Namely, we show that α ₂ is exactly the approximation factor of a certain natural protocol for the Covering Radius Problem. I. Haviv’s research was supported by the Binational Science Foundation and by the Israel Science Foundation. V. Lyubashevsky’s research was supported by NSF ITR 0313241. O. Regev’s research was supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848.     

The centralizer of an element in a Lie algebra of type <Emphasis Type="Italic">L</Emphasis>

In this paper, we investigate the Lie algebra L(A,α,δ) of type L and obtain the respective sufficient conditions for L(A,α,δ δ to be semisimple, and for Z(ω) = Fω as well, where 0 ≠ ω Є L(A, α, δ, δ) and Z(ω) is the centralizer of ω.     

Generalizations of coatomic modules

For a ring R and a right R-module M, a submodule N of M is said to be δ-small in M if, whenever N+X=M with M/X singular, we have X=M. Let ℘ be the class of all singular simple modules. Then δ(M)=Σ{ L≤ M| L is a δ-small submodule of M} = Re _jm(℘)=∩{ N⊂ M: M/N∈℘. We call M δ-coatomic module whenever N≤ M and M/N=δ(M/N) then M/N=0. And R is called right (left) δ-coatomic ring if the right (left) R-module R _R(_RR) is δ-coatomic. In this note, we study δ-coatomic modules and ring. We prove M=⊕ _i=1 ⁿ M_i is δ-coatomic if and only if each M _i (i=1,…, n) is δ-coatomic.