Sieve methods and their applications in number theory

Abstract

What is a sieve? One possible answer is: a technique to extract information from a sequence A, for instance an interval of integers, to get properties of a smaller sequence, for instance the number of primes within this interval, or the number of prime twins. But what kind of information are we talking about? Well, usually information on how this sequence is distributed in some special arithmetic progressions. The fact is that these processes are usually very general, which implies that we can use them even in some tricky situations. As only to be expected, these processes also have limitations. With that being said, sieve methods have had a long history and it has been, practically, over a century since the birth of the so called Modern Sieve Theory. The Sieve Theory has had an extraordinary development and it has greatly evolved, to the point that it is now a powerful tool in Number Theory and in other branches of Mathematics, such as the Theory of Automorphic Forms (essentially after the great work of H. Iwaniec). Also, in applied fields of Number Theory, such as Cryptography and Algorithmic Number Theory, sieve methods are extremely important and there are many applications. We have direct applications, like finding all the prime numbers within certain boundaries or the construction of numbers free of large prime factors; as well as some indirect applications, like the fact that sieve methods and sieve techniques can yield valuable information about the distribution of “smooth numbers” in short intervals, and hence allows us to bound the running time of some factoring algorithms. To summarize, in this thesis some sieve methods are studied and some examples of their applications in Number Theory are also presented.

O que é esta noção de crivo? Uma resposta possível seria: uma técnica para extrair informações acerca de uma sequência A, por exemplo um intervalo entre dois números inteiros, para estabelecer propriedades de uma sequência mais pequena, por exemplo o número de primos dentro deste intervalo. Mas de que tipo de informações é que estamos a falar? Bem, normalmente trata-se de informação relativa à distribuição da sequência em algumas progressões aritméticas especiais. A verdade é que estes processos são bastantes genéricos e abrangentes, pelo que podemos usálos mesmo em algumas situações mais delicadas. Como seria de esperar, eles também têm as suas limitações. Podemos dizer que os métodos associados à Teoria de Crivos têm uma longa história e já vai, practicamente, uma centena de anos desde o nascimento da chamada Teoria de Crivos Moderna. A Teoria de Crivos desenvolveu-se de forma notável e evoluiu bastante, ao ponto a que é actualmente uma ferramente poderosa para a Teoria de Números e para outros ramos da Matemática, tais como a Teoria das Formas Automórficas (principalmente após o trabalho extraordinário de H. Iwaniec). Além disso, em certas áreas de aplicação de Teoria de Números, tais como Criptografia e Teoria de Números Algorítmica, os métodos associados à Teoria de Crivos desempenham um papel fundamental, havendo mesmo bastantes e variadas aplicações. Temos as aplicações mais directas, tais como encontrar todos os primos dentro de certos limites ou a construção de números cuja factorização está livre de grandes primos; bem como aplicações mais indirectas, tais como o facto de que estes métodos nos dão informações relevantes acerca da distribuição de “números suaves” em intervalos de amplitude reduzida, o que nos permite limitar o tempo de execução de alguns algoritmos de factorização. Em suma, nesta tese são estudados alguns destes métodos associados à Teoria de Crivos, bem como alguns exemplos das suas aplicações em Teoria de Números.