next up previous contents
Next: Az extremális problémára vonatkozó Up: Az extremális Frobenius-probléma Previous: Az extremális Frobenius-probléma   Tartalomjegyzék

Néhány becslés $ G(A)$-ra

Az előző fejezetben vázlatosan megismertük az eredeti Frobenius-problémát. Eszerint, ha $ 0<a_1< \ldots <a_n$ és $ (a_1, a_2, \ldots , a_n)=1$, akkor a $ K=\sum_{i=1}^{n}x_ia_i$ diofantoszi egyenlet megoldható elég nagy $ K$-ra, ahol az $ x_i$-k nemnegatív egészek. Nevezzük a következőkben is $ G(a_1, a_2, \ldots ,a_n)$-nek a legnagyobb olyan $ K$-t, amelyre az egyenlet nem oldható meg. Az eddig ismertetett eredmények is mutatják a nehézségeket. A legnagyobb nem felírható szám erősen függ az együtthatók, a ,,címletek'' egymás közötti nagyságrendi és oszthatósági viszonyaitól. Talán éppen a probléma általános megoldhatóságának reménytelensége miatt az 1970-es évek elejétől egyre több felső becslés jelent meg a szakirodalomban. A teljesség igénye nélkül felsorolunk néhány ilyen felső becslést. Ezek közül többet azóta is rendszeresen idéznek, illetve ezek mentén alakult ki az azóta extremális Frobenius-problémának nevezett általánosítás. A becslések között szerepel olyan is, amely a további vizsgálatainknak az alapját képezi.

SELMER függetlennek tekintette az $ a_i$-ket, ha egyik sem volt kifejezhető a többi lineáris kombinációjaként. Az ilyen független halmazok vizsgálatánál nyerte a következő becslést [28]:

TÉTEL 3.1.1  

$\displaystyle G(a_1, a_2, \ldots, a_n) \le 2a_n\left \lfloor \frac {a_1}{n} \right \rfloor -a_1. $

ERDŐS és GRAHAM 1972-ben adott a Kneser-tétel segítségével felső becslést a legnagyobb nem felírható számra [6]:

TÉTEL 3.1.2  

$\displaystyle G(a_1, a_2, \ldots , a_n) \le 2a_{n-1}
\left\lfloor \frac {a_n}{n}\right\rfloor-a_n.$

Az extremális problémára jellemző $ g(n, t)$ jelölés ERDŐS 1971-es kitűzött feladatában szerepel először [5]. Legyen ennek megfelelően a továbbiakban

$\displaystyle g(n,t)=\max G(a_1, a_2, \ldots, a_n), $

ahol a maximumot az összes olyan $ a_i$-kre képezzük, amelyekre teljesül, hogy $ 1<a_1<a_2< \ldots <a_n \le t$ és $ (a_1, a_2, \ldots , a_n)=1.$

DIXMIER 1990-ben tette közzé becslését, amelyben az alsó becsléshez a $ t, t-1, t-2, \dots ,t-n+1$ szomszédos elemek alapján jutott el [4].

TÉTEL 3.1.3  

$\displaystyle \left\lfloor\frac{t-2}{n-1}\right\rfloor(t-n+1)-1 \le g(n, t) \le
\left(\left\lceil\frac{t-1}{n-1}\right\rceil-1\right)t-1.
$

Egészen új M. BECK, R. DIAZ és S. ROBINS becslése [1]:

TÉTEL 3.1.4  

$\displaystyle G(a_1, a_2, \ldots, a_n) \le \frac{1}{2}\left(\sqrt{a_1a_2a_3(a_1+a_2+a_3)}-a_1-a_2-a_3\right).
$

Jelenlegi tárgyalásunkkal nem mutatnak kapcsolatot, de mindenképpen meg kell említeni, hogy a $ G(a_1, a_2, \ldots ,a_n)$-re alsó becslések is ismertek. Ezek általában aszimptotikus jellegűek és gráfelméleti, algoritmuselméleti valamint vektoros interpretációk eredményeiként adódtak. J. L. DAVISONtól származik egy az előbbi felső becsléshez hasonló szerkezetű becslés $ n=3$-ra [3]:

TÉTEL 3.1.5  

$\displaystyle G(a_1, a_2, a_3)\ge \sqrt{3}\sqrt{a_1a_2a_3} - a_1-a_2-a_3.
$

HUJTER MIHÁLYtól, 1982-ből származik a következő általános eredmény [11]:

TÉTEL 3.1.6  

$\displaystyle G(a_1, a_2, \ldots, a_n) \ge
\left(\frac{n-1}{n}\right)\left((n-1)!a_1a_2 \ldots a_n\right)^{\frac{1}{n-1}}-\sum_{i=1}^{n}a_i.
$

KILLINGBERGTRO ezt, az egynél kisebb szorzó egyre növelésével 2000-ben továbbjavította [15]:

TÉTEL 3.1.7  

$\displaystyle G(a_1, a_2, \ldots, a_n) \ge
\left((n-1)!a_1a_2 \ldots a_n\right)^{\frac{1}{n-1}}-\sum_{i=1}^{n}a_i.
$


Végezetül JANZ [13] egy különleges megfogalmazású becslését említjük meg. Az $ A=\{a_1, a_2, \ldots ,a_n\}$ pozitív egészekből álló véges halmazt telítettnek nevezi, ha bármely két elemének összege vagy szintén az $ A$-hoz tartozik, vagy már nagyobb az $ A$ maximális eleménél. Ezután veszi az összes olyan telített halmazokat, amelyek két azonos differenciájú számtani sorozat uniójaként állíthatók elő. Ha a $ g(n, t)$ függvényt csak ilyen halmazokra vizsgálja, továbbá a $ t$ elegendően nagy az $ n$-hez képest $ (t \ge (9n^3-30n^2+4n-22)/4),$ és azt is felteszi, hogy a $ t$ nem kongruens 0 vagy $ 1$ modulo $ (n-1)$, akkor

TÉTEL 3.1.8  

$\displaystyle g(n, t) = G(t-n+1, t-n+2, \ldots, t-1, t).
$

Ez a korlátozások ellenére egy igen éles eredmény, amely később az általános megoldás(ok)nak is része lehet.



next up previous contents
Next: Az extremális problémára vonatkozó Up: Az extremális Frobenius-probléma Previous: Az extremális Frobenius-probléma   Tartalomjegyzék
root 2004-12-04