On the Distribution of Compound Inversive Congruential Pseudorandom Numbers

 Inversive methods are interesting alternatives to linear methods for pseudorandom number generation. A particularly attractive method is the compound inversive congruential method introduced and analyzed by Huber and Eichenauer-Herrmann. We present the first nontrivial worst-case results on the distribution of sequences of compound inversive congruential pseudorandom numbers in parts of the period. The proofs are based on new bounds for certain exponential sums. (Received 2 March 2000; in revised form 22 November 2000)     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse. Authors’ addresses: Christian Mauduit, Institut de Mathématiques de Luminy, CNRS, UMR 6206, 163 avenue de Luminy, Case 907, F-13288 Marseille Cedex 9, France; András Sárk?zy, Department of Algebra and Number Theory, E?tv?s Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary     

Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

This paper deals with the inversive congruential method with power of two modulusm for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that there exist parameters in the inversive congruential method such that the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude at leastm ^–1/3. The method of proof relies on a detailed analysis of certain rational exponential sums.     

Compound nonlinear congruential pseudorandom numbers

The nonlinear congruential method for generating uniform pseudorandom numbers has several very promising properties. However, an implementation in multiprecision of these pseudorandom number generators is usually necessary. In the present paper a compound version of the nonlinear congruential method is introduced, which overcomes this disadvantage. It is shown that the generated sequences have very attractive statistical independence properties. The results that are established are essentially best possible and show that the generated pseudorandom numbers model true random numbers very closely. The method of proof relies heavily on a thorough analysis of exponential sums.     

On the Multidimensional Distribution of Inversive Congruential Pseudorandom Numbers in Parts of the Period

 The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present the first nontrivial bounds on the multidimensional discrepancy of individual sequences of inversive congruential pseudorandom numbers in parts of the period. The proof is based on a new bound for certain incomplete exponential sums. (Received 3 December 1998)     

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

Mean-Value Theorems for Multiplicative Functions on Additive Arithmetic Semigroups via Halász’s Method

 We extend the mean-value theorems for multiplicative functions f on additive arithmetic semigroups, which satisfy the condition ∣f(a)∣≤1, to a wider class of multiplicative functions f for which ∣f(a)∣ is bounded in some average sense, via Halász’s method in classical probabilistic number theory. Received October 18, 2001; in final form April 11, 2002     

The Existence of Good Extensible Polynomial Lattice Rules

Extensible (polynomial) lattice rules have been introduced recently and they are convenient tools for quasi-Monte Carlo integration. It is shown in this paper that for suitable infinite families of polynomial moduli there exist generating parameters for extensible rank-1 polynomial lattice rules such that for all these infinitely many moduli and all dimensions s the quantity R ^(s) and the star discrepancy are small. The case of Korobov-type polynomial lattice rules is also considered.Received April 30, 2002; in revised form August 21, 2002 Published online April 4, 2003     

Nonoverlapping pairs of explicit inversive congruential pseudorandom numbers

Recently, the explicit inversive congruential method with power of two modulus for generating uniform pseudorandom numbers was introduced. Statistical independence properties of the generated sequences have been studied by estimating the discrepancy of all overlapping pairs of successive pseudorandom numbers. In the present paper a similar analysis is performed for the subsets of nonoverlapping pairs. The method of proof relies on a detailed discussion of the properties of certain exponential sums.     

Discrepancy and the Error in Integration

 This paper is devoted to an estimation of the error of integration with respect to arbitrary unit measures μ and ν on only in terms of continuity or smoothness properties of the function f and the discrepancy . Here, stands for certain classes of (Borel-) test sets. The proofs are in part based on a continuous wavelet analysis of the integrated function by means of Haar-type wavelets. Received 26 January 2001; in revised form 23 September 2001     

On the -Discrepancy of the Hammersley Point Set

 We give a formula for the -discrepancy of the 2-dimensional Hammersley point set in base 2 for all integers p, . Received 18 May 2001; in revised form 18 December 2001     

Elliptic curve analogue of Legendre sequences

The Legendre symbol is applied to the rational points over an elliptic curve to output a family of binary sequences with strong pseudorandom properties. That is, both the well-distribution measure and the correlation measure of order k, which are evaluated by using estimation of certain character sums along elliptic curves, of the resulting binary sequences are “small”. A lower bound on the linear complexity profile of these sequences is also presented. Our results indicate that the behavior of such sequences is very similar to that of the Legendre sequences. Research partially supported by the Science and Technology Foundation of Putian City (No. 2005S04), the Open Funds of Key Lab of Fujian Province University Network Security and Cryptology (No. 07B005) and the Foundation of the Education Department of Fujian Province (No. JA07164). Author’s addresses: Department of Mathematics, Putian University, Putian, Fujian 351100, China; and Key Lab of Network Security and Cryptology, Fujian Normal University, Fuzhou, Fujian 350007, China     

Partial Densities on Locally Compact Abelian Groups and Uniformly Distributed Sequences

 We investigate conditions under which a partial density on a locally compact abelian group can be extended to a density. The results allow applications to the theory of uniform distribution of sequences in locally compact abelian groups. Received August 27, 2001 Published online July 12, 2002     

Walsh Series Analysis of the L 2-Discrepancyof Symmetrisized Point Sets

 We present a method to estimate the L ₂-discrepancy of symmetrisized point sets from above and from below with the help of Walsh series analysis. We apply the method to a class of two-dimensional net-type point sets, thereby generalizing results of Halton and Zaremba and of Proinov. (Received 14 September 2000)     

On a Problem of D. H. Lehmer and Kloosterman Sums

Let q3 be an odd number, a be any fixed positive integer with (a, q)=1. For each integer b with 1b<q and (b, q)=1, it is clear that there exists one and only one c with 0<c<q such that bca (mod q). Let N(a, q) denote the number of all solutions of the congruent equation bca (mod q) for 1b, c<q in which b and c are of opposite parity, and let . The main purpose of this paper is to study the distribution properties of E(a, q), and to give a sharper hybrid mean value formula involving E(a, q) and Kloosterman sums.Received January 24, 2002; in revised form August 12, 2002 Published online February 28, 2003     

Construction of Pseudorandom Binary Sequences Using Additive Characters

In earlier papers the authors studied finite pseudorandom binary sequences, and they constructed sequences with strong pseudorandom properties. In these earlier constructions multiplicative characters were used. In this paper a new construction is presented which utilizes properties of additive characters. These new sequences can be computed fast, they are well-distributed relative to arithmetic progressions and their correlations of small order are small, but the price paid for the fast computation is that the correlations of large order can be large.     

On the Independence of Hartman Sequences

 Given and , we define by setting if and only if , where denotes the fractional part of α, i.e. α is considered as an element of the torus . If the topological boundary of A has Haar measure 0, then is called a Hartman sequence, which is a generalisation of Kronecker and Beatty sequences. In this article we answer a question of Winkler by showing explicitly for which sets , and vectors , we have . The main tool of the proof is Weyl’s theorem on uniform distribution. Received 3 November 2000; in final form 24 April 2001     

Large-Time Behaviour of Solutions of the Exterior-Domain Cauchy–Dirichlet Problem for the Porous Media Equation with Homogeneous Boundary Data

The title of this paper states precisely what the subject is. The first part of the paper concerns the radially-symmetric problem in the exterior of the unit ball. It is shown that in time the solution of the problem converges to one of two specific self-similar solutions of the porous media equation, dependent upon the dimensionality of the problem. Moreover, the free boundary of the solution converges to that of the self-similar solution. The critical space dimension is two, for which there is no distinction between the self-similar solutions, and the form of the convergence is exceptional. The technique used is a comparison principle involving a variable that is a weighted integral of the solution. The second part of the paper is devoted to the problem in an arbitrary spatial domain with no conditions of symmetry. A special invariance principle and the results obtained for the radially-symmetric case are used to determine the large-time behaviour of solutions and their free boundaries. This behaviour is decidedly different from when the boundary data are fixed and not homogeneous.     

On the numerical analysis of non-convex variational problems

Summary. We discuss a numerical method for finding Young-measure-valued minimizers of non-convex variational problems. To have any hope of a convergence theorem, one must work in a setting where the minimizer is unique and minimizing sequences converge strongly. This paper has two main goals: (i) we specify a method for producing strongly-convergent minimizing sequences, despite the failure of strict convexity; and (ii) we show how uniqueness of the Young measure can be parlayed into a numerical convergence theorem. The treatment of (ii) is done in the setting of two model problems, one involving scalar valued functions and a multiwell energy, the other from micromagnetics. Received July 29, 1995     

Metric properties and exceptional sets of β-expansions over formal Laurent series

This paper is concerned with the metric properties of β-expansions over the field of formal Laurent series. We will see that there are essential differences between β-expansions of the formal Laurent series case and the classical real case. Also the Hausdorff dimensions of some exceptional sets, with respect to the Haar measure, are determined. Authors’ addresses: Bing Li and Jian Xu, School of Mathematics and Statistics, Wuhan University, Wuhan, Hubei 430072, P.R. China; Jun Wu, Department of Mathematics, Huazhong University of Science and Technology, Wuhan, Hubei 430074, P.R. China