Wybrane zagadnienia addytywne kombinatorycznej teorii liczb
Loading...
Date
2012-12-08
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Selected additive problems of combinatorial number theory
Abstract
Praca ma na celu przedstawienie kilku wyników dotyczących zagadnień addytywnych kombinatorycznej teorii liczb. Każdy z rozdziałów dotyczy innej tematyki. Rozdział pierwszy zawiera wykaz stosowanych oznaczeń oraz definicje.
W rozdziale drugim omawiane są pewne własności minimalnych baz asymptotycznych.
Erdős i Nathanson pokazali, że dla każdej liczby naturalnej h≥ 2 istnieje minimalna baza asymptotyczna A rzędu h o gęstości równej 1/h.
Erdős i Nathanson pytają w swej pracy, czy jest możliwe wzmocnienie tego wyniku, tj. czy istnieje minimalna baza asymptotyczna rzędu h≥ 2 taka, że A(k)=k/h+O(1). Innym postawionym przez Erdősa i Nathansona problemem jest stwierdzenie istnienia minimalnej bazy asymptotycznej A={a0, a1, a2,…}, dla której limsup (ai+1-ai)=3.
W tej części pracy odpowiemy twierdząco na oba postawione pytania. Przedstawiona zostanie konstrukcja minimalnej bazy asymptotycznej rzędu dwa, której funkcja licząca spełnia warunek k/2 ≤ A(k) ≤ k/2+1 dla k⊆N oraz taka, że kolejne dwa elementy bazy różnią się od siebie o co najwyżej trzy. Pokazane zostanie także, że nie istnieje minimalna baza asymptotyczna rzędu dwa, dla której funkcja licząca spełniałaby warunek k/2+1/2 ≤ A(k) ≤ k/2+Cdla wszystkich dostatecznie dużych k ⊆ N, gdzie C jest dodatnią stałą.
Rozdział trzeci dotyczy addytywnych własności ciągu Fibonacciego. Erdős, Sarközy i Sós udowodnili, że dla dowolnego dwukolorowania zbioru liczb naturalnych E(n)=|E⊆ [n]| ≤ (log n)/(log ((1+51/2)/2)) dla każdego n ⊆ N, gdzie E oznacza zbiór tych dodatnich parzystych liczb całkowitych, których nie można przedstawić w postaci sumy dwóch różnych elementów jednego ze zbiorów dwupodziału. W tym rozdziale wykażemy, że nierówności podanej przez Erdős'a, Sarközy'ego i Sós nie można poprawić. Wskażemy mianowicie konstrukcję takiego dwupodziału zbioru liczb naturalnych, że żadna liczba Gn=2Fn (gdzie (Fn)n⊆N jest ciągiem Fibonacciego) nie posiada monochromatycznej reprezentacji. Pokażemy też, że każdy podzbiór A zbioru liczb naturalnych taki, że do zbioru różnic A-A nie należy żadna liczba Fibonacciego ma gęstość dolną mniejszą niż 7/36 oraz że istnieje zbiór o podanej własności mający gęstość równą 19/110. Stosując tę samą ideę dowodu uzyskany rezultat można poprawić rozważając dokładniej warunki początkowe. Metoda ta nie daje jednak możliwości uzyskania optymalnego wyniku.
W rozdziale czwartym omawiamy problem oszacowania wielkości zbioru A⊆Zp (gdzie Zp=Z/pZ) na podstawie znajomości minimalnej liczby reprezentacji elementów zbioru sum A+A.
Udowodnimy mianowicie dwa nowe oszacowania dolne największej liczby naturalnej n takiej, że dla dowolnego zbioru A⊆Zp o co najwyżej n elementach istnieje co najmniej jeden element w zbiorze A+A, który można przedstawić w postaci sumy elementów z A na mniej niż K sposobów (liczbę tę oznaczamy fK(p)). W oparciu o lemat Shkredov'a pokażemy, że
dla K ≥ 2 mamy fK(p) ≥ c1(K log p)/((log K + log log p)log log p).
Stosując natomiast lemat Chang w miejsce lematu Shkredov'a dostajemy, że dla K ≥ 2 mamy fK(p) ≥ (K log p)/(2(log K + 2log log p)(4+ log log K + log log log p))-1. Wynik drugi poprawia pierwszy rezultat.
Szczególnie ciekawy jest przypadek K=clog p. Wówczas otrzymujemy fK(p) ≥ (c2(log p)2)/((log log p)(log log log p)), co poprawia oszacowanie podane przez Łuczaka i Schoena.
Oba dowody wykorzystują ponadto klasyczne twierdzenie Dirichleta.
The thesis contains several results concerning combinatorial problems in additive number theory. The first chapter consists of the Basic definitions and notation used throughout. In chapter two we study some properties of asymptotic bases. Erd{\H o}s and Nathanson showed that for every $h\geq 2$ there exist minimal asymptotic basis $A$ of order $h$ with ${\rm d}(A)=1/h,$ where ${\rm d}(A)$ denotes the density of $A.$ Erd{\H o}s and Nathanson asked whether it is possible to strengthen their result by deciding on the existence of a minima asymptotic bases of order $h\ge 2$ such that $A(k)=k/h+O(1).$ Moreover Erd{\H o}s and Nathanson asked if there exists a minimal asymptotic basis with $\limsup (a_{i+1}-a_{i})=3.$ In this chapter we answer these questions in the affirmative and we construct a minimal asymptotic basis $A$ of order $2$ fulfilling a very restrictive condition $$\frac{1}{2}k\leq A(k)\leq \frac{1}{2}k+1.$$ In chapter three we study some additive properties of the Fibonacci sequence $F$. In particular, we prove a lower and an upper bound for the quantity $\sup_{A\sbeq \N}\{\overline{\rm d}(A): (A-A)\cap F=\emptyset\}.$ Let $f_{K}(p)$ be the largest $n$ such that for every set $A\subseteq\Z/p\Z$ with at most $n$ elements there exists at least one element in $A+A$ with less than $K$ representations. In chapter four we show a new lower bound for $f_K(p)$: $$ f_K(p)\ge\frac{K\log p}{2\left( \log K + 2\log\log p \right)\left( 4+\log\log K + \log\log\log p \right)}-1. $$
The thesis contains several results concerning combinatorial problems in additive number theory. The first chapter consists of the Basic definitions and notation used throughout. In chapter two we study some properties of asymptotic bases. Erd{\H o}s and Nathanson showed that for every $h\geq 2$ there exist minimal asymptotic basis $A$ of order $h$ with ${\rm d}(A)=1/h,$ where ${\rm d}(A)$ denotes the density of $A.$ Erd{\H o}s and Nathanson asked whether it is possible to strengthen their result by deciding on the existence of a minima asymptotic bases of order $h\ge 2$ such that $A(k)=k/h+O(1).$ Moreover Erd{\H o}s and Nathanson asked if there exists a minimal asymptotic basis with $\limsup (a_{i+1}-a_{i})=3.$ In this chapter we answer these questions in the affirmative and we construct a minimal asymptotic basis $A$ of order $2$ fulfilling a very restrictive condition $$\frac{1}{2}k\leq A(k)\leq \frac{1}{2}k+1.$$ In chapter three we study some additive properties of the Fibonacci sequence $F$. In particular, we prove a lower and an upper bound for the quantity $\sup_{A\sbeq \N}\{\overline{\rm d}(A): (A-A)\cap F=\emptyset\}.$ Let $f_{K}(p)$ be the largest $n$ such that for every set $A\subseteq\Z/p\Z$ with at most $n$ elements there exists at least one element in $A+A$ with less than $K$ representations. In chapter four we show a new lower bound for $f_K(p)$: $$ f_K(p)\ge\frac{K\log p}{2\left( \log K + 2\log\log p \right)\left( 4+\log\log K + \log\log\log p \right)}-1. $$
Description
Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
Sponsor
Keywords
minimalna baza asymptotyczna, minimal asymptotic basis, podziały, partitions, Ciąg Fibonacciego, Fibonacci sequence, zbiór sum, sumset, minimalna liczba reprezentacji, minimal number of representations