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  

$$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  

$$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

$$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  

$$\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  

$$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  

$$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  

$$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  

$$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  

$$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.