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.

     

The 192 solutions of the Heun equation

A machine-generated list of local solutions of the Heun equation is given. They are analogous to Kummer's  solutions of the Gauss hypergeometric equation, since the two equations are canonical Fuchsian differential equations on the Riemann sphere with four and three singular points, respectively. Tabulation is facilitated by the identification of the automorphism group of the equation with  singular points as the Coxeter group  . Each of the expressions is labeled by an element of  . Of the ,  are equivalent expressions for the local Heun function  , and it is shown that the resulting order- group of transformations of  is isomorphic to the symmetric group . The isomorphism encodes each transformation as a permutation of an abstract four-element set, not identical to the set of singular points.

     

On the smallest value of the maximal modulus of an algebraic integer

The house of an algebraic integer of degree is the largest modulus of its conjugates. For , we compute the smallest house of degree , say m. As a consequence we improve Matveev's theorem on the lower bound of m We show that, in this range, the conjecture of Schinzel-Zassenhaus is satisfied. The minimal polynomial of any algebraic integer whose house is equal to m is a factor of a bi-, tri- or quadrinomial. The computations use a family of explicit auxiliary functions. These functions depend on generalizations of the integer transfinite diameter of some compact sets in They give better bounds than the classical ones for the coefficients of the minimal polynomial of an algebraic integer whose house is small.

     

Heuristics for class numbers and lambda invariants

Let be an imaginary quadratic field and let be the associated real quadratic field. Starting from the Cohen-Lenstra heuristics and Scholz's theorem, we make predictions for the behaviors of the 3-parts of the class groups of these two fields as varies. We deduce heuristic predictions for the behavior of the Iwasawa -invariant for the cyclotomic -extension of and test them computationally.

     

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.

     

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 .

     

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 distribution of zeros of the Hurwitz zeta-function

Assuming the Riemann hypothesis, we prove asymptotics for the sum of values of the Hurwitz zeta-function taken at the nontrivial zeros of the Riemann zeta-function when the parameter either tends to and , respectively, or is fixed; the case is of special interest since . If is fixed, we improve an older result of Fujii. Besides, we present several computer plots which reflect the dependence of zeros of on the parameter . Inspired by these plots, we call a zero of stable if its trajectory starts and ends on the critical line as varies from to , and we conjecture an asymptotic formula for these zeros.

     

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.

     

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 .

     

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.

     

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 .

     

Univariate splines: Equivalence of moduli of smoothness and applications

Several results on equivalence of moduli of smoothness of univariate splines are obtained. For example, it is shown that, for any , , and , the inequality , , is satisfied, where is a piecewise polynomial of degree on a quasi-uniform (i.e., the ratio of lengths of the largest and the smallest intervals is bounded by a constant) partition of an interval. Similar results for Chebyshev partitions and weighted Ditzian-Totik moduli of smoothness are also obtained. These results yield simple new constructions and allow considerable simplification of various known proofs in the area of constrained approximation by polynomials and splines.

     

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.

     

Complexity of inverting the Euler function

Given an integer , how hard is it to find the set of all integers such that , where is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of , in polynomial time ``on average' (that is, ), finds the set of all such solutions . In fact, in the worst case this set of solutions is exponential in , and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the PARTITION PROBLEM, an NP-complete problem, can be reduced in polynomial (in the input size) time to the problem of deciding whether has a solution, for polynomially (in the input size of the PARTITION PROBLEM) many values of (where the prime factorizations of these are given). What this means is that the problem of deciding whether there even exists a solution to , let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.

     

Computing the arithmetic genus of Hilbert modular fourfolds

The Hilbert modular fourfold determined by the totally real quartic number field is a desingularization of a natural compactification of the quotient space , where PSL acts on by fractional linear transformations via the four embeddings of into . The arithmetic genus, equal to one plus the dimension of the space of Hilbert modular cusp forms of weight , is a birational invariant useful in the classification of these varieties. In this work, we describe an algorithm allowing for the automated computation of the arithmetic genus and give sample results.

     

The monic integer transfinite diameter

We study the problem of finding nonconstant monic integer polynomials, normalized by their degree, with small supremum on an interval . The monic integer transfinite diameter is defined as the infimum of all such supremums. We show that if has length , then .

We make three general conjectures relating to the value of for intervals of length less than . We also conjecture a value for where . We give some partial results, as well as computational evidence, to support these conjectures.

We define functions and , which measure properties of the lengths of intervals with on either side of . Upper and lower bounds are given for these functions.

We also consider the problem of determining when is a Farey interval. We prove that a conjecture of Borwein, Pinner and Pritsker concerning this value is true for an infinite family of Farey intervals.

     

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.

     

Families of irreducible polynomials of Gaussian periods and matrices of cyclotomic numbers

Given an odd prime we show a way to construct large families of polynomials , , where is a set of primes of the form mod and is the irreducible polynomial of the Gaussian periods of degree in . Examples of these families when are worked in detail. We also show, given an integer and a prime mod , how to represent by matrices the Gaussian periods of degree in , and how to calculate in a simple way, with the help of a computer, irreducible polynomials for elements of .

     

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 .