Inversion of circulant matrices over

In this paper we consider the problem of inverting an circulant matrix with entries over . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of and , and their costs range, roughly, from to operations over . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.

     

Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation

We develop efficient data-sparse representations to a class of high order tensors via a block many-fold Kronecker product decomposition. Such a decomposition is based on low separation-rank approximations of the corresponding multivariate generating function. We combine the interpolation and a quadrature-based approximation with hierarchically organised block tensor-product formats. Different matrix and tensor operations in the generalised Kronecker tensor-product format including the Hadamard-type product can be implemented with the low cost. An application to the collision integral from the deterministic Boltzmann equation leads to an asymptotical cost - in the one-dimensional problem size (depending on the model kernel function), which noticeably improves the complexity of the full matrix representation.

     

Involutions and characters of upper triangular matrix groups

We study the realizability over of representations of the group of upper-triangular matrices over . We prove that all the representations of are realizable over if , but that if , has representations not realizable over . This theorem is a variation on a result that can be obtained by combining work of J. Arregi and A. Vera-López and of the authors, but the proof of the theorem in this paper is much more natural.

     

On the total number of prime factors of an odd perfect number

We say is perfect if , where denotes the sum of the positive divisors of . No odd perfect numbers are known, but it is well known that if such a number exists, it must have prime factorization of the form , where , , ..., are distinct primes and . We prove that if or for all , , then . We also prove as our main result that , where . This improves a result of Sayers given in 1986.

     

Two efficient algorithms for the computation of ideal sums in quadratic orders

This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used to calculate the GCD in the quadratic order. We show that the calculation of an ideal sum in a fixed quadratic order can be done as fast as in up to a constant factor, i.e., in where bounds the size of the operands and denotes an upper bound for the multiplication time of -bit integers. Using Schönhage-Strassen's asymptotically fast multiplication for -bit integers, we achieve

     

On searching for solutions of the Diophantine equation

We propose an efficient search algorithm to solve the equation for a fixed value of 0$">. By parametrizing , this algorithm obtains and (if they exist) by solving a quadratic equation derived from divisors of . Thanks to the use of several efficient number-theoretic sieves, the new algorithm is much faster on average than previous straightforward algorithms. We performed a computer search for six values of below 1000 for which no solution had previously been found. We found three new integer solutions for and 931 in the range of .

     

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 .

     

Sharpening ``Primes is in P' for a large family of numbers

We present algorithms that are deterministic primality tests for a large family of integers, namely, integers for which an integer is given such that the Jacobi symbol , and integers for which an integer is given such that . The algorithms we present run in time, where is the exact power of dividing when and if . The complexity of our algorithms improves up to when . We also give tests for a more general family of numbers and study their complexity.

     

The construction of good extensible rank-1 lattices

It has been shown by Hickernell and Niederreiter that there exist generating vectors for integration lattices which yield small integration errors for for all integers . This paper provides algorithms for the construction of generating vectors which are finitely extensible for for all integers . The proofs which show that our algorithms yield good extensible rank-1 lattices are based on a sieve principle. Particularly fast algorithms are obtained by using the fast component-by-component construction of Nuyens and Cools. Analogous results are presented for generating vectors with small weighted star discrepancy.

     

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.

     

Satoh's algorithm in characteristic 2

We give an algorithm for counting points on arbitrary ordinary elliptic curves over finite fields of characteristic , extending the method given by Takakazu Satoh, giving the asymptotically fastest point counting algorithm known to date.

     

Short effective intervals containing primes in arithmetic progressions and the seven cubes problem

For any and any non-exceptional modulus , we prove that, for large enough ( ), the interval contains a prime in any of the arithmetic progressions modulo . We apply this result to establish that every integer larger than is a sum of seven cubes.

     

Maximum of the modulus of kernels in Gauss-Turán quadratures

We study the kernels in the remainder terms of the Gauss-Turán quadrature formulae for analytic functions on elliptical contours with foci at , when the weight is a generalized Chebyshev weight function. For the generalized Chebyshev weight of the first (third) kind, it is shown that the modulus of the kernel attains its maximum on the real axis (positive real semi-axis) for each . It was stated as a conjecture in [Math. Comp. 72 (2003), 1855-1872]. For the generalized Chebyshev weight of the second kind, in the case when the number of the nodes in the corresponding Gauss-Turán quadrature formula is even, it is shown that the modulus of the kernel attains its maximum on the imaginary axis for each . Numerical examples are included.

     

New techniques for bounds on the total number of prime factors of an odd perfect number

Let denote the sum of the positive divisors of . We say that is perfect if . Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form , where are distinct primes and . Define the total number of prime factors of as . Sayers showed that . This was later extended by Iannucci and Sorli to show that . This was extended by the author to show that . Using an idea of Carl Pomerance this paper extends these results. The current new bound is .

     

Analysis of recovery type a posteriori error estimators for mildly structured grids

Some recovery type error estimators for linear finite elements are analyzed under 0)$"> regular grids. Superconvergence of order is established for recovered gradients by three different methods. As a consequence, a posteriori error estimators based on those recovery methods are asymptotically exact.

     

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.

     

Solving quadratic equations using reduced unimodular quadratic forms

Let be an symmetric matrix with integral entries and with , but not necesarily positive definite. We describe a generalized LLL algorithm to reduce this quadratic form. This algorithm either reduces the quadratic form or stops with some isotropic vector. It is proved to run in polynomial time. We also describe an algorithm for the minimization of a ternary quadratic form: when a quadratic equation is solvable over , a solution can be deduced from another quadratic equation of determinant . The combination of these algorithms allows us to solve efficiently any general ternary quadratic equation over , and this gives a polynomial time algorithm (as soon as the factorization of the determinant of is known).

     

Prime sieves using binary quadratic forms

We introduce an algorithm that computes the prime numbers up to using additions and bits of memory. The algorithm enumerates representations of integers by certain binary quadratic forms. We present implementation results for this algorithm and one of the best previous algorithms.

     

Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the th cyclotomic polynomial, over , and distinct primes. Given the traces of the roots of we construct the coefficients of in time . We demonstrate a deterministic algorithm for factoring in time when has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of in time .