RESEARCH IN RESIDENCE
Asymptotic methods: pseudorandomness, partitions and prime numbers
Méthodes asymptotiques : pseudo-aléatoire, partitions et nombres premiers
17 – 21 April, 2023
Participants
Joël Rivat (Aix-Marseille Université)
Manfred Madritsch (Université de Lorraine)
Robert Tichy (Graz University of Technology)
The objective of the present project is to connect uniform distribution theory with pseudorandomness as well as partitions. Let us first briefly describe the three areas.
Uniform distribution theory investigates the distribution of sequences in the unit interval. In particular we call a sequence uniformly distributed if for each interval the frequency of elements of the sequence lying in this interval asymptotically tends to the size of the interval. Otherwise said there is no area (interval) that is hit more or less often than the average.
Pseudorandomness provides tools in order to measure how random a given binary sequence behaves. Two main tools consider the distribution along arithmetic progressions as well as the correlation with a given shift vector. If both are small, then we suppose that the sequence behaves randomly.
Partitions of an integer are representations of this integer as sum of integers from a given infinite set. In this area one is interested in the length (number of summands) of a partition, the average size of a summand, the largest or the smallest summand on average etc.
The measures and methods that are introduced in order to describe the pseudorandom behaviour of a sequence have their counterparts in uniform distribution theory. In the present project we want to enlighten this link and to use it for transferring other concepts.
In order to obtain an asymptotic formula for the number of partitions we need that the infinite set does not prefer certain residue classes or other additive structures. This seems equivalent to showing that a certain connected sequence is indeed uniformly distributed. In the present project we want to generalise this connection in order to obtain results for arbitrary infinite sets.
Finally we want to use the connections between uniform distribution and pseudorandomness as well as partitions to generalise known results to subsequences such as the primes or square-free numbers.
L’objectif du présent projet est de connecter la théorie des distributions uniformes avec le pseudo-aléatoire ainsi que les partitions. Décrivons d’abord brièvement ces trois domaines.
La théorie de l’équirépartition étudie la distribution des suites dans l’intervalle unitaire. En particulier, nous appelons une suite équirépartie si pour chaque intervalle, la fréquence des éléments de la suite se situant dans cet intervalle tend asymptotiquement vers la taille de l’intervalle. Autrement dit, il n’y a pas de zone (intervalle) qui est atteinte plus ou moins souvent que la moyenne.
Le pseudo-aléatoire fournit des outils pour mesurer le caractère aléatoire d’une suite binaire donnée. Deux outils principaux considèrent la distribution le long des progressions arithmétiques ainsi que la corrélation avec un vecteur de décalage donné. Si les deux sont petites, nous supposons que la suite se comporte de manière aléatoire.
Les partitions d’un entier sont des représentations de cet entier comme somme d’entiers d’un ensemble infini donné. Dans ce domaine, on s’intéresse à la longueur (nombre de sommets) d’une partition, à la taille moyenne d’un sommet, au plus grand ou au plus petit sommet en moyenne, etc.
Les mesures et les méthodes qui sont introduites pour décrire le comportement pseudo-aléatoire d’une suite ont leurs équivalents dans la théorie de l’équirépartition. Dans le présent projet, nous voulons éclairer ce lien et l’utiliser pour transférer d’autres concepts.
Afin d’obtenir une formule asymptotique pour le nombre de partitions, nous avons besoin que l’ensemble infini ne préfère pas certaines classes de résidus ou d’autres structures additives. Cela semble équivalent à montrer qu’une certaine suite connectée est effectivement uniformément distribuée. Dans le présent projet, nous voulons généraliser ce lien afin d’obtenir des résultats pour des ensembles infinis arbitraires.
Enfin, nous voulons utiliser les liens entre la distribution uniforme et le pseudo-aléatoire ainsi que les partitions pour généraliser les résultats connus aux sous-suites telles que les nombres premiers ou les nombres sans facteur carré.
SPONSOR
