Pseudo- and quasi-random sequences: measures, constructions

Quasi- and pseudorandom numbers are algorithmically produced numbers or vectors that are constructed to fulfill certain, well-defined requirements on randomness. Pseudorandom numbers, on the one hand, are supposed to resemble `true` random numbers as much as possible, whereas quasi-random numbers are optimized for specific aspects required in applications. The usage of both types extends over many areas; quasi-random numbers are commonly employed in numerical integration or optimization, pseudorandom numbers in cryptography and data transmission and both in simulation. This results in applications in financial mathematics, image processing, entertainment (as in games, e.g.) and many more. The project is concerned with the above-mentioned requirements (expressed in certain measures) in various ways. First, for `digital point sets`, an important subclass of quasi-random numbers, the crucial quantity called the `t-parameter` shall be developed as naturally evolving from a more abstracted view, similarly as is the case for the Euler characteristic with respect to manifolds. It may be expected that such an abstracted point-of-view would lead to constructions optimizing the t-value in a more targeted way. Another aim of the project is to try to classify the numerous constructions of digital point sets developed in recent years, particularly those based on global function fields. Many of them yield the same asymptotically optimal t-value but are apparently constructed in very different ways. By investigating possible common special cases, common generalizations or inclusions, a clearer picture of the relations between all those different constructions would be formed. Furthermore a database of generator matrices for digital point sets shall be provided; simultaneously their quality in terms of the t-value shall be determined accurately. Such a validation would enable users of the respective quasi-Monte Carlo methods to better estimate the quality of their application as well as the time expenditure needed (better quality of the point sets results in a reduction in the number of points needed, thus reducing time expenditure). For this task, the web database `MinT` shall be employed for publication. It was developed by Schmid and Schürer at the University of Salzburg and is a resource widely renowned in the community. Within the project it is also an aim to work at the update, maintenance and expansion of this web site. Subsequently, the applicant would eventually fully take over the responsibility for the site. Finally, in the realm of pseudorandom numbers, relations between different pseudorandomness measures shall be investigated, with a focus on nonlinear and vector (`multi-sequence`) measures. In addition, some nonlinear generators shall be implemented efficiently and provided to the community.

The project had the goals to investigate algorithmic randomness in various aspects, and to transfer, maintain and expand a scientific database, called "MinT". Algorithmically constructed randomness can roughly be divided in pseudo-randomness, which has applications, e.g., in data transfer, as in that of radio networks used for mobile phones, but also encryption of data, and, quasi-randomness, which is particularly suited for methods of numerical integraion, as is used in various areas, such as financial mathematics, computer graphics, etc. Concerning pseudo-randomness, fundamental insight could be gained on the relations between several criteria for pseudo-randomness. Specifically, the focus was on `bent functions', which exhibit a high degree of non-linearity and thus cryptographics security. As for the second area, quasi-randomness, new constructions of point sets could be devised, that are also of high theoretic interest, as they reveal novel connections between the uniform randomness (defined in a specific sense) of sequences of integers and the uniform randomness of points distributed in (a finite) space. Yet another criteria of randomness is the `Poissonian pair correlation'. This takes a rather `local' view on point sets: it considers, whether differences between pairs of points occur with the appropriate frequency. -- In the project it could be shown that a classical sequence exhibiting uniform distribution does not fulfill this other criterium. Previously it had been known that the pair correlation implies uniform distribution; so this counter example gives another small contribution to the better understanding of these concepts and their relations. Finally, the database "MinT": originally developed at the University Salzburg, it provides the knowledge on the optimal attainable, and, if known, constructable quasi-random point sets. Technically, this means giving the `t-parameter of a digital net'. This is supposed to be as small as possible, hence the name "min t". These values haven been gathered and processed within this database. They happen to have relevance also for a row of other objects of discrete mathematics or combinatorics, for which reason the database is quite renowned in the international scientific community. At its location in Salzburg, however, it could be tended to only intermittently. This why it was decided to transfer both the database and the responsibility for it to Linz within this project. Furthermore, some extensions of its functionality were drafted to be implemented. This could not be achieved during the runtime of the project but may well be done at a later time. Nevertheless, the continued service of the database is currently secured.