Correlations for numeration systems

Abstract

Die vorliegende Dissertation behandelt Ziffernsummenfunktionen und die verwandten q-additiven und q-multiplikativen Funktionen. In den Arbeiten von C. Mauduit und J. Rivat zu dem sogenannten Gelfond-Problemen, die Ziffernsummenfunktionen betreffen, hat sich die diskrete Fouriertransformation als wertvolles Hilfsmittel erwiesen. Im ersten Kapitel wenden wir diese Technik im allgemeineren Rahmen von q-multiplikativen Funktionen an, was uns auf einen alternativen Beweis eines Resultates von J. Coquet, welches den Zusammenhang zwischen pseudozufälligen q-multiplikativen Funktionen und dem Fourier-Bohr-Spektrum betrifft, führt. Außerdem erhalten wir auf ähnliche Weise ein analoges Resultat für die Zeckendorf-Ziffernsumme. In den nächsten beiden Kapiteln beschäftigen wir uns mit der Ziffernsumme von n und von n+t und der Beziehung dieser Werte zueinander. Zunächst beweisen wir ein überraschendes Resultat über die Ziffernsumme von n+t und n+t R (wobei t R durch Umkehrung der Reihenfolge der Ziffern aus t hervorgeht). Danach erarbeiten wir eine partielle Antwort auf die folgende einfach zu formulierende Frage von T.W. Cusick: "Sei t eine natürliche Zahl. Ist es wahr, dass die binäre Ziffernsumme von n+t für mehr als der Hälfte der natürlichen Zahlen mindestens so groß ist wie die binäre Ziffernsumme von n?" Mit Hilfe von multivariaten erzeugenden Funktionen zeigen wir, dass die Antwort auf diese Frage für t in einer Teilmenge mit asymptotischer Dichte 1 positiv ist. Das vierte Kapitel behandelt Teilfolgen natürlicher Zahlen von der Form [n c]. Wir approximieren solche Folgen lokal durch Folgen von der einfacheren Gestalt ([nalpha+beta])_n, so genannte Beatty-Folgen. Dieser Ansatz führt uns auf ein allgemeines Kriterium dafür, dass sich eine arithmetische Funktion auf [n c]} so verhält, wie man es erwartet. Wir wenden dieses Theorem auf einige Probleme rund um Ziffernsummenfunktionen an. Schließlich adaptieren wir die diskrete Fouriertransformation, um sie auf die Zeckendorf-Ziffernsumme anwenden zu können. Damit beweisen wir, dass sich diese Funktion und die gewöhnliche Ziffernsummenfunktion in Basis q (unter einer zusätzlichen Hypothese) unabhängig voneinander in Restklassen verteilen.

This thesis is concerned with the well-known sum-of-digits function and the related notions of q-additive and q-multiplicative functions. In the work of C. Mauduit and J. Rivat on the so-called Gelfond problems, which deal with the sum-of-digits function, the discrete Fourier transform has proven to be a valuable tool. In the first chapter we apply this technique to the more general context of q-multiplicative functions, thereby reproving a result of J. Coquet concerning the relation of pseudorandom q-multiplicative functions to the Fourier-Bohr spectrum. Moreover, in this vein we establish an analogous result for the Zeckendorf sum-of-digits function. In the next two chapters we are concerned with the relation of the sum of digits of n and n+t to each other. We first prove a surprising digit reflection property and a related result on certain 2-regular sequences. After that, we establish a partial answer to the following simple-to-state question by T. W. Cusick:"for each positive integer t, is it true that the binary sum of digits n+t is at least as large as the binary sum of digits of n for more than half of all positive integers n?" Using multivariate generating functions, we show that the answer to this question is positive for t in a set of asymptotic density 1. The fourth chapter deals with subsequences of the integers of the form [n c]. We locally approximate this kind of sequence by sequences of the simpler form [nalpha+beta](so-called Beatty sequences). This leads us to a general criterion for an arithmetic function evaluated on integers of the form [n c] to behave as expected. We apply this theorem to certain problems related to sum-of-digits functions. Finally, we adapt the discrete Fourier transform technique to the Zeckendorf sum-of-digits function in order to prove that this function and the sum-of-digits function in base q are (under some mild assumption) distributed independently in residue classes.