Continuous-time Kreiss resolvent condition on infinite-dimensional spaces

Given the infinitesimal generator of a -semigroup on the Banach space which satisfies the Kreiss resolvent condition, i.e., there exists an such that for all complex with positive real part, we show that for general Banach spaces this condition does not give any information on the growth of the associated -semigroup. For Hilbert spaces the situation is less dramatic. In particular, we show that the semigroup can grow at most like . Furthermore, we show that for every there exists an infinitesimal generator satisfying the Kreiss resolvent condition, but whose semigroup grows at least like . As a consequence, we find that for with the standard Euclidian norm the estimate cannot be replaced by a lower power of or .

     

Iterated function systems, Ruelle operators, and invariant projective measures

We introduce a Fourier-based harmonic analysis for a class of discrete dynamical systems which arise from Iterated Function Systems. Our starting point is the following pair of special features of these systems. (1) We assume that a measurable space comes with a finite-to-one endomorphism which is onto but not one-to-one. (2) In the case of affine Iterated Function Systems (IFSs) in , this harmonic analysis arises naturally as a spectral duality defined from a given pair of finite subsets in of the same cardinality which generate complex Hadamard matrices.

Our harmonic analysis for these iterated function systems (IFS) is based on a Markov process on certain paths. The probabilities are determined by a weight function on . From we define a transition operator acting on functions on , and a corresponding class of continuous -harmonic functions. The properties of the functions in are analyzed, and they determine the spectral theory of . For affine IFSs we establish orthogonal bases in . These bases are generated by paths with infinite repetition of finite words. We use this in the last section to analyze tiles in .

     

Littlewood polynomials with high order zeros

Let be the minimal length of a polynomial with coefficients divisible by . Byrnes noted that for each , and asked whether in fact . Boyd showed that for all , but . He further showed that , and that is one of the 5 numbers , or . Here we prove that . Similarly, let be the maximal power of dividing some polynomial of degree with coefficients. Boyd was able to find for . In this paper we determine for .

     

On the minimal polynomial of Gauss periods for prime powers

For a positive integer , set and let denote the group of reduced residues modulo . Fix a congruence group of conductor and of order . Choose integers to represent the cosets of in . The Gauss periods

corresponding to are conjugate and distinct over with minimal polynomial

To determine the coefficients of the period polynomial (or equivalently, its reciprocal polynomial is a classical problem dating back to Gauss. Previous work of the author, and Gupta and Zagier, primarily treated the case , an odd prime, with fixed. In this setting, it is known for certain integral power series and , that for any positive integer

holds in for all primes except those in an effectively determinable finite set. Here we describe an analogous result for the case , a prime power ( ). The methods extend for odd prime powers to give a similar result for certain twisted Gauss periods of the form

where denotes the usual Legendre symbol and .

     

Lower bounds for the condition number of a real confluent Vandermonde matrix

Lower bounds on the condition number of a real confluent Vandermonde matrix are established in terms of the dimension , or and the largest absolute value among all nodes that define the confluent Vandermonde matrix and the interval that contains the nodes. In particular, it is proved that for any modest (the largest multiplicity of distinct nodes), behaves no smaller than , or than if all nodes are nonnegative. It is not clear whether those bounds are asymptotically sharp for modest .

     

Order of convergence of second order schemes based on the minmod limiter

Many second order accurate nonoscillatory schemes are based on the minmod limiter, e.g., the Nessyahu-Tadmor scheme. It is well known that the -error of monotone finite difference methods for the linear advection equation is of order for initial data in , . For second or higher order nonoscillatory schemes very little is known because they are nonlinear even for the simple advection equation. In this paper, in the case of a linear advection equation with monotone initial data, it is shown that the order of the -error for a class of second order schemes based on the minmod limiter is of order at least in contrast to the order for any formally first order scheme.

     

On the convergence of certain Gauss-type quadrature formulas for unbounded intervals

We consider the convergence of Gauss-type quadrature formulas for the integral , where is a weight function on the half line . The -point Gauss-type quadrature formulas are constructed such that they are exact in the set of Laurent polynomials }, where is a sequence of integers satisfying and . It is proved that under certain Carleman-type conditions for the weight and when or goes to , then convergence holds for all functions for which is integrable on . Some numerical experiments compare the convergence of these quadrature formulas with the convergence of the classical Gauss quadrature formulas for the half line.

     

Limiting set of second order spectra

Let be a self-adjoint operator acting on a Hilbert space . A complex number is in the second order spectrum of relative to a finite-dimensional subspace iff the truncation to of is not invertible. This definition was first introduced in Davies, 1998, and according to the results of Levin and Shargorodsky in 2004, these sets provide a method for estimating eigenvalues free from the problems of spectral pollution. In this paper we investigate various aspects related to the issue of approximation using second order spectra. Our main result shows that under fairly mild hypothesis on the uniform limit of these sets, as increases towards , contain the isolated eigenvalues of of finite multiplicity. Therefore, unlike the majority of the standard methods, second order spectra combine nonpollution and approximation at a very high level of generality.

     

A dual finite element complex on the barycentric refinement

Given a two dimensional oriented surface equipped with a simplicial mesh, the standard lowest order finite element spaces provide a complex centered on Raviart-Thomas divergence conforming vector fields. It can be seen as a realization of the simplicial cochain complex. We construct a new complex of finite element spaces on the barycentric refinement of the mesh which can be seen as a realization of the simplicial chain complex on the original (unrefined) mesh, such that the duality is non-degenerate on for each . In particular is a space of -conforming vector fields which is dual to Raviart-Thomas -conforming elements. When interpreted in terms of differential forms, these two complexes provide a finite-dimensional analogue of Hodge duality.

     

Jacobi's last geometric statement extends to a wider class of Liouville surfaces

Numerical evidence is presented which strongly suggests that ``Jacobi's last geometric statement"--that the conjugate locus from a point has exactly four cusps and the corresponding cut locus consists of only one topological segment--holds for compact real analytic Liouville surfaces diffeomorphic to if the Gaussian curvature is everywhere positive and has exactly six critical points, these being two saddles, two global minima, and two global maxima (as is the case for an ellipsoid). Our experiments suggest that this is a sufficient rather than a necessary condition. Furthermore, for compact real analytic Liouville surfaces diffeomorphic to upon which the Gaussian curvature can be negative but has exactly six critical points, these being two saddles, two global minima, and two global maxima, it appears that the cut locus is always a subarc of a line given by or , where are canonical coordinates with respect to which the metric has the form . In the case of an ellipsoid, these curves are lines of curvature.

     

Multigrid methods for the computation of singular solutions and stress intensity factors I: Corner singularities

We consider the Poisson equation with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain with re-entrant angles. A multigrid method for the computation of singular solutions and stress intensity factors using piecewise linear functions is analyzed. When , the rate of convergence to the singular solution in the energy norm is shown to be , and the rate of convergence to the stress intensity factors is shown to be , where is the largest re-entrant angle of the domain and can be arbitrarily small. The cost of the algorithm is . When , the algorithm can be modified so that the convergence rate to the stress intensity factors is . In this case the maximum error of the multigrid solution over the vertices of the triangulation is shown to be .

     

On irregular prime power divisors of the Bernoulli numbers

Let ( ) denote the usual th Bernoulli number. Let be a positive even integer where or . It is well known that the numerator of the reduced quotient is a product of powers of irregular primes. Let be an irregular pair with . We show that for every the congruence has a unique solution where and . The sequence defines a -adic integer which is a zero of a certain -adic zeta function originally defined by T. Kubota and H. W. Leopoldt. We show some properties of these functions and give some applications. Subsequently we give several computations of the (truncated) -adic expansion of for irregular pairs with below 1000.

     

Equal moments division of a set

Let be the minimal positive integer , for which there exists a splitting of the set into  subsets, , , ..., , whose first moments are equal. Similarly, let be the maximal positive integer , such that there exists a splitting of into subsets whose first moments are equal. For , these functions were investigated by several authors, and the values of and have been found for and , respectively. In this paper, we deal with the problem for any prime . We demonstrate our methods by finding for any and for .

     

On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation

We study the maximal rate of convergence (mrc) of algorithms for (multivariate) integration and approximation of -variate functions from reproducing kernel Hilbert spaces . Here is an arbitrary kernel all of whose partial derivatives up to order satisfy a Hölder-type condition with exponent . Algorithms use function values and we analyze their rate of convergence as tends to infinity. We focus on universal algorithms which depend on , , and but not on the specific kernel , and nonuniversal algorithms which may depend additionally on .

For universal algorithms the mrc is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. Hence, the mrc for universal algorithms suffers from the curse of dimensionality if is large relative to , whereas the mrc for nonuniversal algorithms does not since it is always at least for integration, and for approximation. This is the price we have to pay for using universal algorithms. On the other hand, if is large relative to , then the mrc for universal and nonuniversal algorithms is approximately the same.

We also consider the case when we have the additional knowledge that the kernel has product structure, . Here are some univariate kernels whose all derivatives up to order satisfy a Hölder-type condition with exponent . Then the mrc for universal algorithms is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. If or for all , then the mrc is at least , and the curse of dimensionality is not present. Hence, the product form of reproducing kernels breaks the curse of dimensionality even for universal algorithms.

     

Tractability of quasilinear problems II: Second-order elliptic problems

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation in the -dimensional unit cube, in which depends linearly on , but nonlinearly on . Here, both and  are -variate functions from a reproducing kernel Hilbert space with finite-order weights of order . This means that, although  can be arbitrarily large, and  can be decomposed as sums of functions of at most  variables, with independent of .

In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of and  needed to obtain an -approximation is polynomial in  and , with the degree of the polynomial depending linearly on . In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in  , independently of . We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in  and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criteria, the only exception being the Dirichlet boundary condition under the normalized error criterion.

     

Stabilized finite element method based on the Crank-Nicolson extrapolation scheme for the time-dependent Navier-Stokes equations

This paper provides an error analysis for the Crank-Nicolson extrapolation scheme of time discretization applied to the spatially discrete stabilized finite element approximation of the two-dimensional time-dependent Navier-Stokes problem, where the finite element space pair for the approximation of the velocity and the pressure is constructed by the low-order finite element: the quadrilateral element or the triangle element with mesh size . Error estimates of the numerical solution to the exact solution with are derived.

     

Integer transfinite diameter and polynomials with small Mahler measure

In this work, we show how suitable generalizations of the integer transfinite diameter of some compact sets in give very good bounds for coefficients of polynomials with small Mahler measure. By this way, we give the list of all monic irreducible primitive polynomials of of degree at most with Mahler measure less than and of degree and with Mahler measure less than .

     

Modular exponentiation via the explicit Chinese remainder theorem

Fix pairwise coprime positive integers . We propose representing integers modulo , where is any positive integer up to roughly , as vectors . We use this representation to obtain a new result on the parallel complexity of modular exponentiation: there is an algorithm for the Common CRCW PRAM that, given positive integers , , and in binary, of total bit length , computes in time using processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an expected time algorithm using processors; von zur Gathen gave an NC algorithm for the highly special case that is polynomially smooth.

     

A new bound for the smallest

Let denote the number of primes and let denote the usual integral logarithm of . We prove that there are at least integer values of in the vicinity of with . This improves earlier bounds of Skewes, Lehman, and te Riele. We also plot more than 10000 values of in four different regions, including the regions discovered by Lehman, te Riele, and the authors of this paper, and a more distant region in the vicinity of , where appears to exceed by more than . The plots strongly suggest, although upper bounds derived to date for are not sufficient for a proof, that exceeds for at least integers in the vicinity of . If it is possible to improve our bound for by finding a sign change before , our first plot clearly delineates the potential candidates. Finally, we compute the logarithmic density of and find that as departs from the region in the vicinity of , the density is , and that it varies from this by no more than over the next integers. This should be compared to Rubinstein and Sarnak.

     

Rationality problem of three-dimensional purely monomial group actions: the last case

A -automorphism of the rational function field is called purely monomial if sends every variable to a monic Laurent monomial in the variables . Let be a finite subgroup of purely monomial -automorphisms of . The rationality problem of the -action is the problem of whether the -fixed field is -rational, i.e., purely transcendental over , or not. In 1994, M. Hajja and M. Kang gave a positive answer for the rationality problem of the three-dimensional purely monomial group actions except one case. We show that the remaining case is also affirmative.