Explicit values of multi-dimensional Kloosterman sums for prime powers, II

For any integer fix , and let denote the group of reduced residues modulo . Let , a power of a prime . The hyper-Kloosterman sums of dimension are defined for by

where denotes the multiplicative inverse of modulo .

Salie evaluated in the classical setting for even , and for odd with . Later, Smith provided formulas that simplified the computation of in these cases for . Recently, Cochrane, Liu and Zheng computed upper bounds for in the general case , stopping short of their explicit evaluation. Here I complete the computation they initiated to obtain explicit values for the Kloosterman sums for , relying on basic properties of some simple specialized exponential sums. The treatment here is more elementary than the author's previous determination of these Kloosterman sums using character theory and -adic methods. At the least, it provides an alternative, independent evaluation of the Kloosterman sums.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

Convergence of classes of high-order semi-Lagrangian schemes for the Vlasov-Poisson system

In this paper we present some classes of high-order semi-Lagran- gian schemes for solving the periodic one-dimensional Vlasov-Poisson system in phase-space on uniform grids. We prove that the distribution function and the electric field converge in the norm with a rate of

where is the degree of the polynomial reconstruction, and and are respectively the time and the phase-space discretization parameters.

     

On Meinardus' examples for the conjugate gradient method

The conjugate gradient (CG) method is widely used to solve a positive definite linear system of order . It is well known that the relative residual of the th approximate solution by CG (with the initial approximation ) is bounded above by

   with

where is 's spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for but without saying anything about all other . This very example can be used to show that the bound is sharp for any given by constructing examples to attain the bound, but such examples depend on and for them the th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all . There are two contributions in this paper:

1. A closed formula for the CG residuals for all on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of of the actual residuals;
2. A complete characterization of extreme positive linear systems for which the th CG residual achieves the bound is also presented.

     

The Lucas-Pratt primality tree

In 1876, E. Lucas showed that a quick proof of primality for a prime could be attained through the prime factorization of and a primitive root for . V. Pratt's proof that PRIMES is in NP, done via Lucas's theorem, showed that a certificate of primality for a prime could be obtained in modular multiplications with integers at most . We show that for all constants , the number of modular multiplications necessary to obtain this certificate is greater than for a set of primes with relative asymptotic density 1.

     

Divisors in residue classes, constructively

Let be integers satisfying , , , and let . Lenstra showed that the number of integer divisors of equivalent to is upper bounded by . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to .

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

The generalized triangular decomposition

Given a complex matrix , we consider the decomposition , where is upper triangular and and have orthonormal columns. Special instances of this decomposition include the singular value decomposition (SVD) and the Schur decomposition where is an upper triangular matrix with the eigenvalues of on the diagonal. We show that any diagonal for can be achieved that satisfies Weyl's multiplicative majorization conditions:

where is the rank of , is the -th largest singular value of , and is the -th largest (in magnitude) diagonal element of . Given a vector which satisfies Weyl's conditions, we call the decomposition , where is upper triangular with prescribed diagonal , the generalized triangular decomposition (GTD). A direct (nonrecursive) algorithm is developed for computing the GTD. This algorithm starts with the SVD and applies a series of permutations and Givens rotations to obtain the GTD. The numerical stability of the GTD update step is established. The GTD can be used to optimize the power utilization of a communication channel, while taking into account quality of service requirements for subchannels. Another application of the GTD is to inverse eigenvalue problems where the goal is to construct matrices with prescribed eigenvalues and singular values.

     

On the polynomial representation for the number of partitions with fixed length

In this paper, it is shown that the number of partitions of a nonnegative integer with parts can be described by a set of polynomials of degree in , where denotes the least common multiple of the integers and denotes the quotient of when divided by . In addition, the sets of the polynomials are obtained and shown explicitly for and .

     

Construction of hyperelliptic function fields of high three-rank

We present several explicit constructions of hyperelliptic function fields whose Jacobian or ideal class group has large -rank. Our focus is on finding examples for which the genus and the base field are as small as possible. Most of our methods are adapted from analogous techniques used for generating quadratic number fields whose ideal class groups have high -rank, but one method, applicable to finding large -ranks for odd primes is new and unique to function fields. Algorithms, examples, and numerical data are included.

     

An interpolation error estimate in based on the anisotropic measures of higher order derivatives

In this paper, we introduce the magnitude, orientation, and anisotropic ratio for the higher order derivative (with ) of a function to characterize its anisotropic behavior. The magnitude is equivalent to its usual Euclidean norm. The orientation is the direction along which the absolute value of the -th directional derivative is about the smallest, while along its perpendicular direction it is about the largest. The anisotropic ratio measures the strength of the anisotropic behavior of . These quantities are invariant under translation and rotation of the independent variables. They correspond to the area, orientation, and aspect ratio for triangular elements. Based on these measures, we derive an anisotropic error estimate for the piecewise polynomial interpolation over a family of triangulations that are quasi-uniform under a given Riemannian metric. Among the meshes of a fixed number of elements it is identified that the interpolation error is nearly the minimum on the one in which all the elements are aligned with the orientation of , their aspect ratios are about the anisotropic ratio of , and their areas make the error evenly distributed over every element.

     

The hyperdeterminant and triangulations of the 4-cube

The hyperdeterminant of format is a polynomial of degree in unknowns which has terms. We compute the Newton polytope of this polynomial and the secondary polytope of the -cube. The regular triangulations of the -cube are classified into -equivalence classes, one for each vertex of the Newton polytope. The -cube has coarsest regular subdivisions, one for each facet of the secondary polytope, but only of them come from the hyperdeterminant.

     

Two kinds of strong pseudoprimes up to

Let be an odd composite integer. Write with odd. If either mod or mod for some , then we say that is a strong pseudoprime to base , or spsp() for short. Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Conjectured values of were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of for ; to give a lower bound of : ; and to give reasons and numerical evidence of K2- and -spsp's to support the following conjecture: for any , where (resp. ) is the smallest K2- (resp. -) strong pseudoprime to all the first prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: with primes and ; and that a -spsp is an spsp and a Carmichael number of the form: with each prime factor mod .)

     

Prime decomposition in the anti-cyclotomic extension

For an imaginary quadratic number field and an odd prime number , the anti-cyclotomic -extension of is defined. For primes of , decomposition laws for in the anti-cyclotomic extension are given. We show how these laws can be applied to determine if the Hilbert class field (or part of it) of is -embeddable. For some and , we find explicit polynomials whose roots generate the first step of the anti-cyclotomic extension and show how the prime decomposition laws give nice results on the splitting of these polyniomials modulo . The article contains many numerical examples.

     

On the embedding problem for representations

Let denote the double cover of corresponding to the element in where transpositions lift to elements of order and the product of two disjoint transpositions to elements of order . Given an elliptic curve , let denote its -torsion points. Under some conditions on elements in correspond to Galois extensions of with Galois group (isomorphic to) . In this work we give an interpretation of the addition law on such fields, and prove that the obstruction for having a Galois extension with gives a homomorphism . As a corollary we can prove (if has conductor divisible by few primes and high rank) the existence of -dimensional representations of the absolute Galois group of attached to and use them in some examples to construct modular forms mapping via the Shimura map to (the modular form of weight attached to) .

     

The completion of locally refined simplicial partitions created by bisection

Recently, in [Found. Comput. Math., 7(2) (2007), 245-269], we proved that an adaptive finite element method based on newest vertex bisection in two space dimensions for solving elliptic equations, which is essentially the method from [SINUM, 38 (2000), 466-488] by Morin, Nochetto, and Siebert, converges with the optimal rate.The number of triangles in the output partition of such a method is generally larger than the number of triangles that in all intermediate partitions have been marked for bisection, because additional bisections are needed to retain conforming meshes.A key ingredient to our proof was a result from [Numer. Math., 97(2004), 219-268] by Binev, Dahmen and DeVore saying that for some absolute constant , where is the number of triangles from the initial partition that have never been bisected. In this paper, we extend this result to bisection algorithms of -simplices, with that generalizing the result concerning optimality of the adaptive finite element method to general space dimensions.

     

Weak coupling of solutions of first-order least-squares method

A theoretical analysis of a first-order least-squares finite element method for second-order self-adjoint elliptic problems is presented. We investigate the coupling effect of the approximate solutions for the primary function and for the flux . We prove that the accuracy of the approximate solution for the primary function is weakly affected by the flux . That is, the bound for is dependent on , but only through the best approximation for multiplied by a factor of meshsize . Similarly, we provide that the bound for is dependent on , but only through the best approximation for multiplied by a factor of the meshsize . This weak coupling is not true for the non-selfadjoint case. We provide the numerical experiment supporting the theorems in this paper.

     

Efficient CM-constructions of elliptic curves over finite fields

We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order and nextprime.

     

Parity-regular Steinhaus graphs

Steinhaus graphs on vertices are certain simple graphs in bijective correspondence with binary -sequences of length . A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic binary sequences of any length . By an exhaustive search the conjecture was known to hold up to 25 vertices. We report here that it remains true up to 117 vertices. This is achieved by considering the weaker notion of parity-regular Steinhaus graphs, where all vertex degrees have the same parity. We show that these graphs can be parametrized by an -vector space of dimension approximately and thus constitute an efficiently describable domain where true regular Steinhaus graphs can be searched by computer.

     

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.