The SFB - QMC Methods: Theory and Applications
Project Part Leaders
Project Parts
SFB Activities
Advisory Board
Land Oberösterreich

Project Parts

The SFB consists of 11 project parts. Below are listed short descriptions of each project part.

Project Part 01 (G. Larcher): Coordination Project

Project Part 02 (M. Drmota): Subsequences of Automatic Sequences and Uniform Distribution

Automatic sequences are sequences $t(n)$ on a finite alphabet that are the output of a finite automaton. These kind of sequences have got a lot of attention during the last 10 or 15 year. There are very close relations to dynamical systems, to digital expansions, to uniformly distributed sequences and also to number theory.

The underlying idea of this project part is to study certain subsequences of automatic sequences and to describe their distributional behavior. For example it has been already shown by Deshoulliers, Drmota and Morgenbesser that $t(\lfloor n^c \rfloor)$ has the same distribution as $t(n)$ for all $c\in (1,7/5)$. Furthermore Drmota and Morgenbesser have characterized the distribution behavior of $t(n^2)$ for so-called invertible automatic sequences. This line of research is mainly motivated by the recent developments on the so-called Gelfond problems on the prime values $s_q(p)$ and on   polynomial values $s_q(P(n))$ of the sum-of-digits function modulo $m$.

The concrete goals of this project part are to characterize -- as far as   possible -- the distributional behavior of subsequences of automatic sequences $t(n)$ of the form $t(\lfloor n^c \rfloor)$ (for $c> 1$), $t(P(n))$ for polynomials $P$ of degree greater than $1$, and $t(p)$ for primes $p$ and to study similar questions for more general digital expansions like   the Zeckendorff expansion (that is based on Fibonacci numbers).

Project Part 03 (P. Grabner): Distributing Points on Spheres and Manifolds: Minimal Energy and Designs

This project part is concerned with constructions of well-distributed point sets on compact manifolds, especially the $d$-sphere $\mathbb{S}^d\subset\mathbb{R}^{d+1}$.

Minimal energy point sets

For a given compact manifold $M\subset\mathbb{R}^{d+1}$ and a set of $N$ distinct points $X_N=\{x_1,\ldots,x_N\}\subset M$, the Riesz $s$-energy is defined as
$E_s(X_N)=\sum_{i\neq j}\|x_i-x_j\|^{-s}.$
A configuration $X_N^*$, which minimizes $E_s$ amongst all $N$-point configurations, is called a minimal energy configuration. The motivation for studying such configurations comes from Chemistry and Physics, where self-organization of mutually repelling particles under inverse power laws occur. For fixed $s$ and $N\to\infty$ the distribution
approaches a continuous limiting measure, which can be described by classical potential theory, if $s<\dim(M)$, and which is normalized Hausdorff measure, if $s\geq\dim(M)$ by a recent result of D.~P.~Hardin and E.~B.~Saff.

Spherical designs

A spherical $t$-design is a finite set of points $X\subset\mathbb{S}^d$ such that
$\frac1{\# X}\sum_{x\in X}p(x)=\int_{S^d} f(x)\,d\sigma(x)$
for all polynomials $p$ of degree $\leq t$, where $\sigma$ denotes the normalized surface measure on $\mathbb{S}^d$. Only recently A.~V.~Bondarenko et al. could show that $t$-designs with $\mathcal{O}(t^d)$ exist. This is the same order of magnitude as previously known lower bounds.

The discrepancy, integration error, and separation properties of minimal energy point sets and designs shall be analyzed. Furthermore, number-theoretic constructions for well-distributed point sets on the sphere shall be investigated further.

Project Part 04 (P. Hellekalek): Arithmetic Primitives for Uniform Distribution Modulo 1

This project is about techniques relevant to the theory of uniform distribution modulo 1 (u.d.mod 1) of sequences and its applications in the field of random number generation and QMC methods. There is also a tie of this project to applied cryptography.

We will contribute (i) to the question how well a given (finite) sequence is u.d.mod 1, by studying and developing appropriate figures of merit and investigating their relation (keywords: discrepancy, diaphony, spectral test,

inequality of Erdös-Turán-Koksma, inequality of Le Veque), (ii) to new construction methods for so-called low discrepancy sequences (keyword: $b$-adic arithmetics, lattice methods), and (iii) to applied cryptography (keywords: nonlinearity of Boolean functions, bit diffusion).

Project Part 05 (R. Hofer): Digital Sequences and Related Hybrid Sequences

Many of the most famous low-discrepancy sequences are contained in the class of digital sequences. Digital sequences are constructed via operating on the $q$-adic digits of the natural numbers by using so-called generating matrices. In this project we focus on the generating matrices. We study the constructions of Niederreiter, Xing & Niederreiter, Hofer, and Hofer & Niederreiter with respect to designing specific properties of the matrices. Particularly, properties which are related to matrix densities as well as multiplicative properties between the generating matrices.

Furthermore we study the distribution properties of hybrid sequences which are built by combining a digital sequence generated by specific matrices with different other types of sequences; as Kronecker sequences, pseudorandom sequences, lattice point sets or again a digital sequence generated by specific matrices.

We also continue recent investigations on the distribution of subsequences of digital sequences.

Project Part 06 (P. Kritzer): Approximation of Integrals and Functions by New Types of Quasi-Monte Carlo Algorithms

In this project part, we will consider recent developments in QMC theory. One topic is hybrid point sets, obtained by concatenating the components of conventional QMC points, applications of which are, e.g., to be found in computer graphics and high-dimensional simulation. By using hybrid point sets, one has increased flexibility in integrating functions with different properties regarding different components.
There has been much work on the analysis of hybrid point sets as such, but only few results on the functions that we can efficiently integrate by QMC algorithms based on these. Therefore, we will study ``hybrid'' function spaces and the corresponding algorithms. As pointed out in many papers, one can employ QMC methods also for function approximation, so studying hybrid point sets also for approximating functions is near at hand. Another new approach is obtaining exponential error convergence for QMC algorithms when dealing with analytic functions. In this vein, multivariate algorithms have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. Considerable progress has been made on these questions during the last years, and we will continue research in this context, with a particular focus on function approximation. The previous analysis of algorithms for analytic functions gave rise to new definitions of tractability, and we will analyze our new methods with respect to these concepts and compare the findings to those for classical tractability notions.

Project Part 07 (G. Larcher): Improved Discrepancy Estimates for Various Classes of Sequences

It is the main aim of this project to give improved discrepancy estimates for several types of point sequences and point sets in an $s$-dimensional unit-cube. In most cases we will concentrate on the star-discrepancy $D^*_N$.

In the proposal of this project part we will state 16 concrete research problems in three groups:

A) ``Metrical'' lower bounds for the discrepancy of good lattice point sets and of digital $(t, m, s)$-nets.

B) Discrepancy estimates for hybrid sequences and applications of hybrid sequences.

C) Concrete (non-metric) discrepancy estimates.

Concerning estimation of a metrical type or for concrete types of sequences, we especially concentrate ourselves to low-discrepancy sequences which are essential for QMC methods. By working and (at least partly) solving these problems we will give new impulses for various directions of research on discrepancy theory and on low-discrepancy sequences.

Project Part 08 (G. Leobacher): Adapting QMC Algorithms to the Simulation Problem

The project is located at the interface between quasi-Monte Carlo methods (QMC) and applications in finance and natural sciences. Hereby the main questions are how to reformulate a given high-dimensional integration problem to make it more suitable for QMC, which used to be recommended as a method for problems of low to moderate dimensions.

One of the most fruitful approaches known is to express the problem as an expectation of a function depending on independent standard normal variables and concatenate the function with a carefully chosen orthogonal transform. For very high-dimensional problems another important requirement is that the transform can be computed sufficiently fast. Examples of such transforms are the Brownian bridge construction and the principal component analysis construction.

In the present project we aim to further strengthen the theoretical basis for the use of orthogonal transforms with QMC and to find algorithms for constructing fast transforms for different types of problems from mathematical finance.

Project Part 09 (F. Pillichshammer): Digital Nets and Lattice Based Integration Rules

In QMC integration, point sets with good distribution properties are required. There are two main ways to choose these point sets. The first class of quadrature points are lattice point sets, which were introduced independently by Hlawka and Korobov in the 1950s and the second main class are digital nets, comprising the important sub-class of polynomial lattice point sets, and digital sequences, as introduced by Niederreiter in the 1980s. It is the primal aim of this project part to push the research on these point sets and sequences. The problems considered can be grouped into three overall topics: 1. the explicit construction of point sets for QMC, 2. the analysis of problems with higher and even infinite smoothness and 3. the analysis of new concepts of sequences such as hybrid sequences or hyperplane sequences. In all three topics, digital nets and sequences as well as lattice point sets play an important role. In 1. we aim at giving explicit constructions of polynomial lattice point sets with low star discrepancy and digital sequences with low mean square discrepancy. In 2. we study integration and approximation of smooth functions based on tent-transformed lattice point sets and integration of analytic functions based on regular lattices. In 3. we analyze distribution properties of hyperplane sequences and of hybrid sequences made of lattice point sets and digital sequences with respect to the star discrepancy.

Project Part 10 (R. Tichy): Diophantine Equations, Discrepancy and Finance

QMC methods are frequently used in applied mathematics, in particular for the evaluation of multivariate integrals and for simulations in mathematical physics and finance. In the last decade probabilistic methods have been fruitfully used to achieve QMC error bounds which depend linearly in the dimension. Furthermore, a combination of such probabilistic tools with deep machinery from Diophantine analysis can be used to obtain precise limit laws for discrepancy functions and related objects of QMC theory. This project part consists of five parts: 1) Lacunarity, symmetry and Diophantine equations with a focus on permutation invariant limit laws. 2) Geometric discrepancy. 3) Pseudorandomness and discrepancy. 4) Uniform distribution and dynamical systems. 5) QMC methods, copulas and finance.

We will use a great variety of tools from the theory of diophantine equations and approximations such as Schmidt's subspace theorem as well as martingale inequalities, harmonic analysis, ergodic theory and combinatorial methods.

Project Part 11 (A. Winterhof): On the Hierarchy of Measures of Pseudorandomness

Pseudorandom numbers are generated by deterministic algorithms and are not random at all. However, in contrast to truly random numbers they guarantee certain randomness properties.
Their desirable features depend on the application area. For example, uniformly distributed sequences of pseudorandom numbers are needed for Monte Carlo methods, unpredictable sequences for cryptography, and uncorrelated sequences for wireless communication or radar. Corresponding quality measures are discrepancy for uniform distribution, linear complexity for unpredictability, and correlation.

The main goal of this project is to find relations between different measures of pseudorandomness. For example, Dorfer, Niederreiter and Winterhof showed that the linear complexity provides essentially the same quality measure as certain lattice tests coming from the area of Monte Carlo methods. Moreover, Mauduit, Niederreiter and Sarközy studied links between uniformly distributed pseudorandom sequences of real numbers in $[0, 1)$ and the correlation of pseudorandom binary sequences derived from them.

Brandstätter and Winterhof proved a relation between the linear complexity and the higher order correlation of binary sequences.

Roughly speaking, the discrepancy is a stronger measure than correlation which is a stronger measure than linear complexity.

There are many other related measures of pseudorandomness for sequences and we want to analyze their hierarchy.