Sidonova sekvence - Sidon sequence

V teorii čísel je Sidonova sekvence posloupností přirozených čísel, ve kterých jsou všechny párové součty (pro ) odlišné. Sidonské sekvence se také nazývají Sidonovy sady ; jsou pojmenovány po maďarském matematikovi Simonovi Sidonovi , který tento koncept představil ve svém výzkumu Fourierových řad . ${\ displaystyle A = \ {a_ {0}, a_ {1}, a_ {2}, \ tečky \}}$${\ displaystyle a_ {i} + a_ {j}}$${\ Displaystyle i \ leq j}$

Hlavním problémem při studiu Sidonových sekvencí, které Sidon představuje, je najít maximální počet prvků, které může Sidonova sekvence obsahovat, a to až do určité míry . Navzdory rozsáhlému výzkumu zůstala otázka nevyřešená. ${\ displaystyle x}$

Časné výsledky

Paul Erdős a Pál Turán dokázali, že u každého je nejvýše počet prvků menší než v Sidonově sekvenci . Pomocí konstrukce J. Singera ukázali, že existují Sidonovy sekvence, které obsahují členy menší než x . ${\ displaystyle x> 0}$${\ displaystyle x}$${\ displaystyle {\ sqrt {x}} + O ({\ sqrt [{4}] {x}})}$${\ displaystyle {\ sqrt {x}} (1-o (1))}$

Nekonečné Sidonovy sekvence

Erdős dále zjištěno, že pro jakýkoli konkrétní nekonečné Sidon sekvence s označující počet svých prvků, až do , ${\ displaystyle A}$${\ displaystyle A (x)}$${\ displaystyle x}$

To znamená, že nekonečné Sidonovy sekvence jsou tenčí než nejhustší konečné Sidonovy sekvence.

Pro druhý směr Chowla a Mian poznamenali, že chamtivý algoritmus dává nekonečnou Sidonovu sekvenci pro každého . Ajtai , Komlós a Szemerédi to vylepšili konstrukcí Sidonovy sekvence s ${\ displaystyle A (x)> c {\ sqrt [{3}] {x}}}$${\ displaystyle x}$

Nejlepší dolní mez doposud dal Imre Z. Ruzsa , který dokázal, že sidonská sekvence s

existuje. Erdős se domníval, že existuje nekonečná sada Sidonů, která platí. On a Rényi ukázali existenci posloupnosti s dohadovou hustotou, ale uspokojili pouze slabší vlastnost, že existuje konstanta taková, že pro každé přirozené číslo existuje nanejvýš řešení rovnice . (Být Sidonovou sekvencí by to vyžadovalo .) ${\ displaystyle A}$${\ displaystyle A (x)> x ^ {1/2-o (1)}}$${\ displaystyle \ {a_ {0}, a_ {1}, \ tečky \}}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle a_ {i} + a_ {j} = n}$${\ displaystyle k = 1}$

Erdős dále se domníval, že existuje nekonstantní celé číslo - koeficient polynomu , jehož hodnoty v přirozených čísel tvoří sekvence Sidonu. Konkrétně se zeptal, zda sada pátých sil je sada Sidon. Ruzsa se k tomu přiblížil tím, že ukázal, že existuje reálné číslo s takovým, že rozsah funkce je Sidonova sekvence, kde označuje

celočíselnou část . Jak je iracionální, tato funkce není polynomem. Tvrzení, že množina pátých sil je Sidonova množina, je zvláštním případem pozdějšího domněnky Landera, Parkina a Selfridgea . ${\ displaystyle c}$${\ displaystyle 0 <c <1}$${\ displaystyle f (x) = x ^ {5} + \ lfloor cx ^ {4} \ rfloor}$${\ displaystyle \ lfloor \ \ rfloor}$${\ displaystyle c}$${\ displaystyle f (x)}$

Vztah k vládcům Golombů

Všechny konečné Sidonovy sady jsou vládci Golombů a naopak.

Chcete-li to vidět, předpokládejte rozpor, který je Sidonova množina a ne vládce Golomb. Jelikož to není golombský vládce, musí existovat takoví čtyři členové . Z toho vyplývá, že to je v rozporu s tvrzením, kterým je Sidonova množina. Proto všechny Sidonovy sady musí být vládci Golombů. Podobným argumentem musí být všichni golombští vládci Sidonovými sadami. ${\ displaystyle S}$${\ displaystyle a_ {i} -a_ {j} = a_ {k} -a_ {l}}$${\ displaystyle a_ {i} + a_ {l} = a_ {k} + a_ {j}}$${\ displaystyle S}$

Viz také

• Moser – De Bruijnova sekvence
• Sumset

Reference