Zastosowania metod kombinatoryki addytywnej do wybranych zagadnień multiplikatywnych
Loading...
Date
2019
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Applications of additive combinatorics methods to some multiplicative problems
Abstract
Głównym celem pracy jest badanie różnych sposobów, w jakie kombinatoryka addytywna może być wykorzystana do radzenia sobie z pewnymi zagadnieniami pojawiającymi się w multiplikatywnej teorii liczb. Najważniejsza część pracy dotyczy następującego problemu: dla pewnej liczby naturalnej n i pewnej liczby pierwszej p jest nam dany zbiór reszt modulo p wszystkich dzielników liczby n i chcielibyśmy stwierdzić, które z nich odpowiadają jej czynnikom pierwszym. Przedstawiony jest algorytm rozwiązujący ten problem dla p i n spełniających pewne naturalne warunki i zostaje pokazane, że jest wiele takich liczb. Interesującą cechą przedstawionego dowodu jest to, że wymaga on użycia kombinatoryki addytywnej. W kolejnej części pracy rozważana jest suma wyrażeń exp(a2r/q ) dla wszystkich r należących do podgrupy multiplikatywnej reszt modulo q generowanej przez element 2. Podajemy górne oszacowanie wartości bezwzględnej z lepszą stałą niż dotychczas znana. W ostatniej części pracy rozważane są oszacowania na wielkość zbioru wszystkich sum postaci c1a1+c2a2+…+ckak, gdzie ci są ustalonymi współczynnikami, zaś ai są elementami zbioru A. Seria oszacowań górnych wielkości tego zbioru jest udowodniona dla A spełniającego |A+A| < K |A|. Najlepsze oszacowania dostajemy w przypadkach, gdy K jest znacznie mniejsze niż h oraz gdy zbiór współczynników ci ma pewną strukturę addytywną.
The main aim of this dissertation is the study of different ways in which additive combinatorics may be used to tackle some problems arising in multiplicative number theory. The main part of the thesis deals with the following problem: Suppose that for some natural number n and some prime number p we are given the set of residues mod p of all its divisors and we would like to know which of those residues correspond to prime factors of n. An algorithm which approximately solves this problem for p and n satisfying some natural conditions is presented and it is proved that there are plenty of such numbers. One interesting feature of the proof is that it relies on additive combinatorics. In the next part of the thesis the sum of expressions exp(a2r/q ) over r belonging to multiplicative subgroup of residues modulo q generated by element 2. absolute value of this sum is estimated. The result we obtained in this line of research is the following. We give an upper-bound of absolute value of this sum with a better constant than previously known. In the last part of the thesis bounds for the size of sets of all the sums of the form c1a1+c2a2+…+ckak, where ci are coefficients and ai are elements of the set A. Series of results giving upper-bounds on the size of this set is proved for A satisfying |A+A|<K|A|. The best bounds are obtained in cases when K is much smaller than h and when the set of ci coefficients has some additive structure.
The main aim of this dissertation is the study of different ways in which additive combinatorics may be used to tackle some problems arising in multiplicative number theory. The main part of the thesis deals with the following problem: Suppose that for some natural number n and some prime number p we are given the set of residues mod p of all its divisors and we would like to know which of those residues correspond to prime factors of n. An algorithm which approximately solves this problem for p and n satisfying some natural conditions is presented and it is proved that there are plenty of such numbers. One interesting feature of the proof is that it relies on additive combinatorics. In the next part of the thesis the sum of expressions exp(a2r/q ) over r belonging to multiplicative subgroup of residues modulo q generated by element 2. absolute value of this sum is estimated. The result we obtained in this line of research is the following. We give an upper-bound of absolute value of this sum with a better constant than previously known. In the last part of the thesis bounds for the size of sets of all the sums of the form c1a1+c2a2+…+ckak, where ci are coefficients and ai are elements of the set A. Series of results giving upper-bounds on the size of this set is proved for A satisfying |A+A|<K|A|. The best bounds are obtained in cases when K is much smaller than h and when the set of ci coefficients has some additive structure.
Description
Wydział Matematyki i Informatyki
Sponsor
Keywords
kombinatoryka addytywna, liczba pierwsza, współczynnik Fouriera, zbiór sum, algorytmiczna teoria liczb, additive combinatorics, prime numer, Fourier coefficient, sumset, algorithmic number theory