On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus,II

One of the alternatives to linear congruential pseudorandom number generators with their known deficiencies is the inversive congruential method with prime power modulus. Recently, it was proved that pairs of inversive congruential pseudorandom numbers have nice statistical independence properties. In the present paper it is shown that a similar result cannot be obtained fork-tuples withk≥3 since their discrepancy is too large. The method of proof relies on the evaluation of certain exponential sums. In view of the present result the inversive congruential method with prime power modulus seems to be not absolutely suitable for generating uniform pseudorandom numbers.     

On the correlation of pseudorandom numbers generated by inversive methods

We introduce two new types of inversive generators for pseudorandom numbers. These new methods offer several advantages over the conventional inversive generator. For instance, we establish good correlation properties of our generators that cannot be obtained for the conventional inversive generator with current methods. A new bound on character sums for finite fields is the essential technical tool for this work. Authors’ addresses: Harald Niederreiter, Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543, Republic of Singapore; Jo?l Rivat, Institut de Mathématiques de Luminy, Université de la Méditerranée, CNRS-UMR 6206, 163 avenue de Luminy, Case 907, 13288 Marseille Cedex 9, France     

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)     

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)     

Similarities and conformal transformations

Summary In ordinary Euclidean space, every isometry that leaves no point invariaut is either a screw displacement (including a translation as a special case) or a glide reflection. Every other kind of similarity is a spiral similarity: the product of a rotation about a line and a dilatation whose center lies on this line. In real inversive space (i.e., Euclidean space plus a single point at infinity), every conformal transformation is either a similarity or the product of an inversion and an isometry. This last remark remains valid when the number of dimensions is increased. In fact, every conformal transformation of inversive n-space (n/2) is expressible as the proddct of r reflections and s inversions, where r≤n+1, s≤2, r+s≤n+2. To Enrico Bompiani on his scientific Jubilce     

Inversive congruential generator over a Galois ring of dimension <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">l</Emphasis></Superscript>

We consider the construction of of an inversive congruential generator over a Galois ring of odd dimension p ^l , whichwas proposed by Solé and Zinoviev for p = 2. Using the estimates of trigonometric sums on the sequences of pseudorandom numbers, we obtain the estimates of a discrepant function, a generated sequence of pseudorandom numbers, and the associated sequence of two-dimensional “overlapping” points.     

Circle geometry in affine Cayley-Klein planes

Some theorems from inversive and Euclidean circle geometry are extended to all affine Cayley-Klein planes. In particular, we obtain an analogue to the first step of Clifford’s chain of theorems, a statement related to Napoleon’s theorem, extensions of Wood’s theorem on similar-perspective triangles and of the known fact that the three radical axes of three given circles are parallel or have a point in common. For proving these statements, we use generalized complex numbers. Supported by a grant D01-761/24.10.06 from the Ministry of Education and Sciences, and by a grant 108/2007 from Sofia University.     

Construction of inversive congruential pseudorandom number generators with maximal period length

The inversive congruential method for generating uniform pseudorandom numbers is a particularly attractive alternative to linear congruential generators with their well-known inherent deficiencies like the unfavourable coarse lattice structure in higher dimensions. In the present paper the modulus in the inversive congruential method is chosen as a power of an arbitrary odd prime. The existence of inversive congruential generators with maximal period length is proved by a new constructive characterization of these generators.     

On the 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 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.

     

Inversive localization at semiprlme goldie ideals

P. M. Cohn [6] introduced a method of localizing at a semiprime ideal of a noncommutative Noetherian ring by inverting certain matrices. This paper continues the study of the technique of inversive localization, in a more general setting. The inversive localization is characterized by its structure modulo its Jacobson radical. This is in marked contrast to the torsion theoretic localization, and the two constructions coincide only when the localization can actually be obtained by inverting elements rather than matrices. The inversive localization is computed for the class of left Artinian rings, and it is then shown that at a minimal prime ideal of an order in a left Artinian ring the inversive localization must be left Artinian. On the other hand, the inversive localization at a semiprime ideal of a left Noetherian ring need not be left Noetherian.     

Unitals and inversive planes

We show that if U is a Buekenhout-Metz unital (with respect to a point P) in any translation plane of order q ² with kernel containing GF(q), then U has an associated 2-(q²,q+1,q) design which is the point-residual of an inversive plane, generalizing results of Wilbrink, Baker and Ebert. Further, our proof gives a natural, geometric isomorphism between the resulting inversive plane and the (egglike) inversive plane arising from the ovoid involved in the construction of the Buekenhout-Metz unital. We apply our results to investigate some parallel classes and partitions of the set of blocks of any Buekenhout-Metz unital.     

Inversive planes satisfying the bundle theorem

It is proved that all infinite inversive planes which satisfy the bundle theorem are egglike (ovoidal). For finite inversive planes this was previously proved by the author.     

Harmonische Involutionen und Kreisspiegelungen in Möbiusebenen

An involutory automorphism of an inversive plane whose set of fixed points consists of exactly two points resp. of a circle is called a harmonic involution resp. an inversion. In this paper we study inversive planes with sufficiently many such involutions. Herrn Walter Benz zum 75. Geburtstag gewidmet     

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.     

Basic properties of e-inversive semigroups

Generalizing a property of regular resp. finite semigroups a semigroup S is called E-(0-) inversive if for every a ∈ S4(a ≠ 0) there exists x ∈ S such that ax (≠ 0) is an idempotent. Several characterizations are given allowing to identify the (completely, resp. eventually) regular semigroups in this class. The case that for every a ∈ S4(≠ 0) there exist x,y ∈ S such that ax = ya(≠ 0) is an idempotent, is dealt with also. Ideal extensions of E- (0-)inversive semigroups are studied discribing in particular retract extensions of completely simple semigroups. The structure of E- (0-)inversive semigroups satisfying different cancellativity conditions is elucidated. 1991 AMS classification number: 20M10.     

Construction of spirals with prescribed boundary conditions

Spirality, regarded as monotonicity of curvature, is preserved under inversions. This property is used for constructing a spiral transition curve with predefined curvature elements at the endpoints. These boundary conditions define two invariant values: Coxeter’s inversive distance and the width of the lens. In order to solve the problem, it suffices to realize the corresponding values on two curvature elements of any known spiral. The rest is achieved by inversion. In particular, any boundary conditions compatible with spirality can be satisfied by inverting an arc of the logarithmic spiral. Bibliography: 9 titles.     

On the automorphism group of inversive planes of odd order

The structure of the fix bundle free automorphism groups of inversive planes of odd order is determined. As a special case of our main result, the automorphism groups with a transitive action on the points of an inversive plane of odd order are essentially determined, and the plane is shown to be miquelian when these have no non-trivial normal subgroups of odd order.     

The affine planeAG(2,q),q odd,has a unique one point extension

Summary LetJ be a finite inversive plane of odd orderq. If for at least one pointp ofJ the internal affine planeJ _p is Desarguesian, thenJ is Miquelian. Other formulation: the finite Desarguesian affine plane of odd orderq has a unique one point extension; this extension is the Miquelian inversive plane of orderq. It follows that there is a unique inversive plane of orderq, withq{3, 5, 7}.Oblatum 23-X-1992 & 24-I-1994     

一般组合逆同余法的算法与偏差分析

本文研究了逆同余产生伪随机数的方法，给出了一般的组合逆同余法算法．将已有结果进行理论比较，得到了一个较好的伪随机数序列的产生方法．     

On the Average Distribution of Inversive Pseudorandom Numbers

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. The authors have recently introduced a new method for obtaining nontrivial upper bounds on the multidimensional discrepancy of inversive congruential pseudorandom numbers in parts of the period. This method has also been used to study the multidimensional distribution of several other similar families of pseudorandom numbers. Here we apply this method to show that, “on average” over all initial values, much stronger results than those known for “individual” sequences can be obtained.