Sekwencja Sydonu

W teorii liczb sekwencja Sidon jest sekwencją ${\ Displaystyle A = \ {a_ {0}, a_ {1}, a_ {2}, \ kropki \}}$ liczb naturalnych, w których wszystkie sumy parami $a_ {j}$ $}$ { \ Sekwencje Sidon nazywane są również zbiorami Sidon ; zostały nazwane na cześć węgierskiego matematyka Simona Sidona , który wprowadził to pojęcie do swoich badań nad szeregami Fouriera .

Głównym problemem w badaniu sekwencji Sidon, postawionym przez Sidona, jest znalezienie maksymalnej liczby elementów, które może zawierać sekwencja Sidon, aż do $pewnego$ . Pomimo dużej liczby badań, pytanie pozostało nierozwiązane.

Wczesne wyniki

Paul Erdős i Pál Turán $\ Displaystyle { \sqrt {x}}+O({\sqrt[{4}]{x}})}$ , że dla każdego $wynosi$ elementów mniejszych niż w sekwencji $Sydonu$ co najwyżej . Kilka lat wcześniej James Singer skonstruował sekwencje Sidon z ${\ Displaystyle {\ sqrt {x}} (1-o (1))}$ wyrażenia mniejsze niż x .

Nieskończone sekwencje Sidon

Erdős wykazał również, że dla dowolnej określonej nieskończonej sekwencji Sidon $z$ liczbę jej elementów do , ZA ( $)$ $}$

{\ Displaystyle \ liminf _ {x \ do \ infty}} {\ Frac {A (x) {\ sqrt {\ log x}}} {\ sqrt {x}}}\równik 1.}

Oznacza to, że nieskończone sekwencje Sidon są cieńsze niż najgęstsze skończone sekwencje Sidon.

W drugim kierunku Chowla i Mian zauważyli , że algorytm zachłanny daje nieskończoną sekwencję Sidon z ${\ Displaystyle A (x)> c {\ sqrt [{3}] {x}}}$ co ${\ displaystyle x}$ . Ajtai , Komlós i Szemerédi udoskonalili to, konstruując sekwencję Sydonu z

{\ Displaystyle A (x)> {\ sqrt [{3}] {x \ log x}}.}

Najlepszą dolną granicę do tej pory podał Imre Z. Ruzsa , który udowodnił, że sekwencja Sidon z

{\ Displaystyle A (x)> x ^ {{\ sqrt {2}} -1-o (1)}}

istnieje. Erdős przypuszczał, że istnieje nieskończony zbiór Sydonu

,

którego

{\ Displaystyle A (x)> x ^ {1/2-o (1)} }

trzyma. On i Rényi wykazali istnienie sekwencji

{\ Displaystyle \ {a_ {0}, a_ {1}, \ kropki \}}

z hipotetyczną gęstością, ale spełniającą tylko słabszą właściwość, że istnieje taka stała,

{\ Displaystyle a_ {i} + a_ {j} = n}

​​dla każdej

displaystyle

naturalnej istnieją co najwyżej rozwiązania równania

k}

. (Aby być sekwencją Sydonu, wymagałoby to

{\ displaystyle k = 1}

).

Erdős dalej przypuszczał, że istnieje niestały wielomian całkowity - współczynnik , którego wartości przy liczbach naturalnych tworzą ciąg Sidon. W szczególności zapytał, czy zbiór piątych potęg jest zbiorem Sydonu. $,$ istnieje liczba rzeczywista $z$ taką zakres ${\ Displaystyle f (x) = x ^ {5} + \ lfloor cx ^ {4} \ rfloor}$ to $sekwencja$ Sidon, gdzie część całkowitą Ponieważ $irracjonalny$ , $nie$ funkcja Stwierdzenie, że zbiór piątych potęg jest zbiorem Sydonu, jest szczególnym przypadkiem późniejszej hipotezy Landera, Parkina i Selfridge'a .

Stosunek do władców Golomba

Wszystkie skończone zbiory Sydonu są władcami Golomba i odwrotnie.

Aby to zobaczyć, załóżmy dla sprzeczności , że jest $zbiorem$ , a nie władcą Golomba. Ponieważ nie jest to władca Golomba, musi być czterech takich członków, że $\ Displaystyle a_ {i} -a_ {j} = a_ {k} -a_ {l}}$ . Wynika z tego, że $l} = a_ {k} + a_ {j}}$ , co jest sprzeczne z twierdzeniem, że jest $zbiorem$ . Dlatego wszystkie zestawy Sydonu muszą być władcami Golomba. Stosując podobny argument, wszyscy władcy Golomba muszą być zbiorami Sydonu.

Zobacz też