This dissertation explores an analogue of the prime number theorem for polynomials over finite fields as well as its connection to the necklace factorization algorithm T-transform and the string complexity measure T-complexity. Specifically, a precise asymptotic expansion for the prime polynomial counting function is derived. The approximation given is more accurate than previous results in the literature while requiring very little computational effort. In this context asymptotic series expansions for Lerch transcendent, Eulerian polynomials, truncated polylogarithm, and polylogarithms of negative integer order are also provided. The expansion formulas developed are general and have applications in numerous areas other than the enumeration of prime polynomials. A bijection between the equivalence classes of aperiodic necklaces and monic prime polynomials is utilized to derive an asymptotic bound on the maximal T-complexity value of a string. Furthermore, the statistical behaviour of uniform random sequences that are factored via the T-transform are investigated, and an accurate probabilistic model for short necklace factors is presented. Finally, a T-complexity based conditional string complexity measure is proposed and used to define the normalized T-complexity distance that measures similarity between strings. The T-complexity distance is proven to not be a metric. However, the measure can be computed in linear time and space making it a suitable choice for large data sets. / Graduate / 0544 0984 0405 / nrebenich@gmail.com

Le sujet principal de cette thèse est la distribution des nombres premiers dans les progressions arithmétiques, c'est-à-dire des nombres premiers de la forme $qn+a$, avec $a$ et $q$ des entiers fixés et $n=1,2,3,\dots$ La thèse porte aussi sur la comparaison de différentes suites arithmétiques par rapport à leur comportement dans les progressions arithmétiques. Elle est divisée en quatre chapitres et contient trois articles. Le premier chapitre est une invitation à la théorie analytique des nombres, suivie d'une revue des outils qui seront utilisés plus tard. Cette introduction comporte aussi certains résultats de recherche, que nous avons cru bon d'inclure au fil du texte. Le deuxième chapitre contient l'article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, qui est le fruit de recherche conjointe avec le professeur Greg Martin. Le but de cet article est d'étudier un phénomène appelé le <<Biais de Chebyshev>>, qui s'observe dans les <<courses de nombres premiers>>. Chebyshev a observé qu'il semble y avoir plus de premiers de la forme $4n+3$ que de la forme $4n+1$. De manière plus générale, Rubinstein et Sarnak ont montré l'existence d'une quantité $\delta(q;a,b)$, qui désigne la probabilité d'avoir plus de premiers de la forme $qn+a$ que de la forme $qn+b$. Dans cet article nous prouvons une formule asymptotique pour $\delta(q;a,b)$ qui peut être d'un ordre de précision arbitraire (en terme de puissance négative de $q$). Nous présentons aussi des résultats numériques qui supportent nos formules. Le troisième chapitre contient l'article \emph{Residue classes containing an unexpected number of primes}. Le but est de fixer un entier $a\neq 0$ et ensuite d'étudier la répartition des premiers de la forme $qn+a$, en moyenne sur $q$. Nous montrons que l'entier $a$ fixé au départ a une grande influence sur cette répartition, et qu'il existe en fait certaines progressions arithmétiques contenant moins de premiers que d'autres. Ce phénomène est plutôt surprenant, compte tenu du théorème des premiers dans les progressions arithmétiques qui stipule que les premiers sont équidistribués dans les classes d'équivalence $\bmod q$. Le quatrième chapitre contient l'article \emph{The influence of the first term of an arithmetic progression}. Dans cet article on s'intéresse à des irrégularités similaires à celles observées au troisième chapitre, mais pour des suites arithmétiques plus générales. En effet, nous étudions des suites telles que les entiers s'exprimant comme la somme de deux carrés, les valeurs d'une forme quadratique binaire, les $k$-tuplets de premiers et les entiers sans petit facteur premier. Nous démontrons que dans chacun de ces exemples, ainsi que dans une grande classe de suites arithmétiques, il existe des irrégularités dans les progressions arithmétiques $a\bmod q$, avec $a$ fixé et en moyenne sur $q$. / The main subject of this thesis is the distribution of primes in arithmetic progressions, that is of primes of the form $qn+a$, with $a$ and $q$ fixed, and $n=1,2,3,\dots$ The thesis also compares different arithmetic sequences, according to their behaviour over arithmetic progressions. It is divided in four chapters and contains three articles. The first chapter is an invitation to the subject of analytic number theory, which is followed by a review of the various number-theoretic tools to be used in the following chapters. This introduction also contains some research results, which we found adequate to include. The second chapter consists of the article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, which is joint work with Professor Greg Martin. The goal of this article is to study <<Chebyshev's Bias>>, a phenomenon appearing in <<prime number races>>. Chebyshev was the first to observe that there tends to be more primes of the form $4n+3$ than of the form $4n+1$. More generally, Rubinstein and Sarnak showed the existence of the quantity $\delta(q;a,b)$, which stands for the probability of having more primes of the form $qn+a$ than of the form $qn+b$. In this paper, we establish an asymptotic series for $\delta(q;a,b)$ which is precise to an arbitrary order of precision (in terms of negative powers of $q$). %(it can be instantiated with an error term smaller than any negative power of $q$). We also provide many numerical results supporting our formulas. The third chapter consists of the article \emph{Residue classes containing an unexpected number of primes}. We fix an integer $a \neq 0$ and study the distribution of the primes of the form $qn+a$, on average over $q$. We show that the choice of $a$ has a significant influence on this distribution, and that some arithmetic progressions contain, on average over q, fewer primes than typical arithmetic progressions. This phenomenon is quite surprising since in light of the prime number theorem for arithmetic progressions, the primes are equidistributed in the residue classes $\bmod q$. The fourth chapter consists of the article \emph{The influence of the first term of an arithmetic progression}. In this article we are interested in studying more general arithmetic sequences and finding irregularities similar to those observed in chapter three. Examples of such sequences are the integers which can be written as the sum of two squares, values of binary quadratic forms, prime $k$-tuples and integers free of small prime factors. We show that a broad class of arithmetic sequences exhibits such irregularities over the arithmetic progressions $a\bmod q$, with $a$ fixed and on average over $q$.

Le sujet principal de cette thèse est la distribution des nombres premiers dans les progressions arithmétiques, c'est-à-dire des nombres premiers de la forme $qn+a$, avec $a$ et $q$ des entiers fixés et $n=1,2,3,\dots$ La thèse porte aussi sur la comparaison de différentes suites arithmétiques par rapport à leur comportement dans les progressions arithmétiques. Elle est divisée en quatre chapitres et contient trois articles. Le premier chapitre est une invitation à la théorie analytique des nombres, suivie d'une revue des outils qui seront utilisés plus tard. Cette introduction comporte aussi certains résultats de recherche, que nous avons cru bon d'inclure au fil du texte. Le deuxième chapitre contient l'article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, qui est le fruit de recherche conjointe avec le professeur Greg Martin. Le but de cet article est d'étudier un phénomène appelé le <<Biais de Chebyshev>>, qui s'observe dans les <<courses de nombres premiers>>. Chebyshev a observé qu'il semble y avoir plus de premiers de la forme $4n+3$ que de la forme $4n+1$. De manière plus générale, Rubinstein et Sarnak ont montré l'existence d'une quantité $\delta(q;a,b)$, qui désigne la probabilité d'avoir plus de premiers de la forme $qn+a$ que de la forme $qn+b$. Dans cet article nous prouvons une formule asymptotique pour $\delta(q;a,b)$ qui peut être d'un ordre de précision arbitraire (en terme de puissance négative de $q$). Nous présentons aussi des résultats numériques qui supportent nos formules. Le troisième chapitre contient l'article \emph{Residue classes containing an unexpected number of primes}. Le but est de fixer un entier $a\neq 0$ et ensuite d'étudier la répartition des premiers de la forme $qn+a$, en moyenne sur $q$. Nous montrons que l'entier $a$ fixé au départ a une grande influence sur cette répartition, et qu'il existe en fait certaines progressions arithmétiques contenant moins de premiers que d'autres. Ce phénomène est plutôt surprenant, compte tenu du théorème des premiers dans les progressions arithmétiques qui stipule que les premiers sont équidistribués dans les classes d'équivalence $\bmod q$. Le quatrième chapitre contient l'article \emph{The influence of the first term of an arithmetic progression}. Dans cet article on s'intéresse à des irrégularités similaires à celles observées au troisième chapitre, mais pour des suites arithmétiques plus générales. En effet, nous étudions des suites telles que les entiers s'exprimant comme la somme de deux carrés, les valeurs d'une forme quadratique binaire, les $k$-tuplets de premiers et les entiers sans petit facteur premier. Nous démontrons que dans chacun de ces exemples, ainsi que dans une grande classe de suites arithmétiques, il existe des irrégularités dans les progressions arithmétiques $a\bmod q$, avec $a$ fixé et en moyenne sur $q$. / The main subject of this thesis is the distribution of primes in arithmetic progressions, that is of primes of the form $qn+a$, with $a$ and $q$ fixed, and $n=1,2,3,\dots$ The thesis also compares different arithmetic sequences, according to their behaviour over arithmetic progressions. It is divided in four chapters and contains three articles. The first chapter is an invitation to the subject of analytic number theory, which is followed by a review of the various number-theoretic tools to be used in the following chapters. This introduction also contains some research results, which we found adequate to include. The second chapter consists of the article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, which is joint work with Professor Greg Martin. The goal of this article is to study <<Chebyshev's Bias>>, a phenomenon appearing in <<prime number races>>. Chebyshev was the first to observe that there tends to be more primes of the form $4n+3$ than of the form $4n+1$. More generally, Rubinstein and Sarnak showed the existence of the quantity $\delta(q;a,b)$, which stands for the probability of having more primes of the form $qn+a$ than of the form $qn+b$. In this paper, we establish an asymptotic series for $\delta(q;a,b)$ which is precise to an arbitrary order of precision (in terms of negative powers of $q$). %(it can be instantiated with an error term smaller than any negative power of $q$). We also provide many numerical results supporting our formulas. The third chapter consists of the article \emph{Residue classes containing an unexpected number of primes}. We fix an integer $a \neq 0$ and study the distribution of the primes of the form $qn+a$, on average over $q$. We show that the choice of $a$ has a significant influence on this distribution, and that some arithmetic progressions contain, on average over q, fewer primes than typical arithmetic progressions. This phenomenon is quite surprising since in light of the prime number theorem for arithmetic progressions, the primes are equidistributed in the residue classes $\bmod q$. The fourth chapter consists of the article \emph{The influence of the first term of an arithmetic progression}. In this article we are interested in studying more general arithmetic sequences and finding irregularities similar to those observed in chapter three. Examples of such sequences are the integers which can be written as the sum of two squares, values of binary quadratic forms, prime $k$-tuples and integers free of small prime factors. We show that a broad class of arithmetic sequences exhibits such irregularities over the arithmetic progressions $a\bmod q$, with $a$ fixed and on average over $q$.

Sous l’hypothèse de Riemann généralisée et l’hypothèse d’indépendance linéaire, Rubinstein et Sarnak ont prouvé que les valeurs de x > 1 pour lesquelles nous avons plus de nombres premiers de la forme 4n + 3 que de nombres premiers de la forme 4n + 1 en dessous de x ont une densité logarithmique d’environ 99,59%. En général, l’étude de la différence #{p < x : p dans A} − #{p < x : p dans B} pour deux sous-ensembles de nombres premiers A et B s’appelle la course entre les nombres premiers de A et de B. Dans ce mémoire, nous cherchons ultimement à analyser d’un point de vue numérique et statistique la course entre les nombres premiers p tels que 2p + 1 est aussi premier (aussi appelés nombres premiers de Sophie Germain) et les nombres premiers p tels que 2p − 1 est aussi premier. Pour ce faire, nous présentons au préalable l’analyse de Rubinstein et Sarnak pour pouvoir repérer d’où vient le biais dans la course entre les nombres premiers 1 (mod 4) et les nombres premiers 3 (mod 4) et émettons une conjecture sur la distribution des nombres premiers de Sophie Germain. / Under the Generalized Riemann Hypothesis and the Linear Independence Hypothesis, Rubinstein and Sarnak proved that the values of x which have more prime numbers less than or equal to x of the form 4n + 3 than primes of the form 4n + 1 have a logarithmic density of approximately 99.59%. In general, the study of the difference #{p < x : p in A} − #{p < x : p in B} for two subsets of the primes A and B is called the prime number race between A and B. In this thesis, we will analyze the prime number race between the primes p such that 2p + 1 is also prime (these primes are called the Sophie Germain primes) and the primes p such that 2p − 1 is also prime. To understand this, we first present Rubinstein and Sarnak’s analysis to understand where the bias between primes that are 1 (mod 4) and the ones that are 3 (mod 4) comes from and give a conjecture on the distribution of Sophie Germain primes.