Az extremális problémára vonatkozó
eredmények összefoglalása

A becslések után ismerkedjünk meg az extremális Frobenius prob-lémakör eddigi eredményeivel. Ezeket részben az előző fejezetben is ismertettük. Ott az oktatási vonatkozások hangsúlyozása, itt az eddigi eredmények teljesebb megismertetése a célunk. A $g(n, t)$-vel kapcsolatban több fontos részeredmény is ismert.

Első lépésnek tekinthetjük két japán szerző, NAGATA és MATSUMURA [21] 1961-ben megfogalmazott tételét:

TÉTEL 3.2.1   Legyenek $n$ és $k$ pozitív egészek, $k \le n-1.$ Ekkor

$$g(n, n+k)= 2k-1.$$

Erre az öszefüggésre több eltérő bizonyítás is adható, amelyek közül egyre utaltunk a 2. fejezetben. Ezt az eredményt felhasználva ERDŐS 1971-ben folyóiratban kitűzött problémaként jelentette meg a $g(n, 2n)$-re és a $g(n, 2n+1)$-re vonatkozó tételt [5]. A kitűzött feladatra később az általa adott megoldást ismertették.

TÉTEL 3.2.2   Ha $n > 1$ pozitív egész, akkor

$$g(n, 2n)=2n+1, \qquad g(n,2n+1)=\left\{ \begin{gathered}2n+5, \te... ...od{3};\\ 2n+3, \text{ ha } n \equiv 2 \mod{3}. \end{gathered} \text{ } \right.$$

Az ötletes kombinatorikus bizonyítást GRAHAMmel közösen kiterjesztették és 1972-ben megszületett az az általánosabb tétel, amelyet közel húsz évig nem sikerült egyetlen matematikusnak sem tovább javítania [6].

TÉTEL 3.2.3   Ha $n$ és $k$ pozitív egészek, $n \ge 9k^2+15k+2,$ akkor

$$g(n, 2n+k)= \left\{ \begin{gathered}2n+4k+1,\text{ } \text{ ha } ... ...;\\ 2n+4k-1, \text{ }\text{ ha } n-k \equiv 1 \pmod{3}. \end{gathered} \right.$$

Lényegében ezzel párhuzamosan kis $n$-ekre is többen vizsgálták nemcsak $G(A)$-t, hanem a minél pontosabb felső becslések keresésével közvetve $g(n, t)$-t is. A $G(a, b)$ kiszámítása alapján szinte nyilvánvaló, hogy

$$g(2,t)= \max [(a-1)(b-1)-1]=(t-2)(t-1)-1=t^2-3t+1.$$

Az $n=3$ esetet LEWIN [20] tisztázta szintén az 1970-es évek elején:

TÉTEL 3.2.4  

$$g(3, t)=\left \lfloor \frac {(t-2)^2}{2} \right \rfloor -1.$$

Mind LEWIN, mind ERDŐS és GRAHAM bizonyításaiban azzal válik teljessé a $g(n, t)$ meghatározása, hogy megadnak olyan konkrét $a_i$-ket, amelyekre

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

Ezek a konstrukciók mindegyik esetben vagy szomszédos számokból, vagy két azonos differenciájú számtani sorozat egyesítéséből épülnek fel.

Ezután több mint másfél évtizedig, a menet közben egyre jobban kiterjedő Frobenius problémakörnek ebben a szegmensében nem történt semmiféle előrelépés. A következő áttörés DIXMIER 1990-ben megjelent [4] cikke nyomán indult el és napjainkig is tart. DIXMIER francia matematikus csoportelméleti interpretációval és a Kneser-tételt is felhasználva, a fentebb említett 3.1.3. Tétel becslését élesítve nagyon pontos felső becslést adott $g(n, t)$-re.

TÉTEL 3.2.5  

$$g(n, t) \le (v-1)(t-r-1)-1, t-1=v(n-1)-r 0 \le r < n-1.$$ (3.2.1)

DIXMIER ezzel bizonyította ERDŐS és GRAHAM [7] egy 1980-ban publikált sejtését, mely szerint

TÉTEL 3.2.6  

$$g(n, t) \thicksim \frac {t^2}{n-1}.$$

A 3.2.5. Tétel becslése több fontos esetben a lehető legjobbnak bizonyult, azaz megadható olyan $A=\{a_1, a_2, \ldots ,a_n\}$ halmaz, amelyre $G(A)$ megegyezik (3.2.1) jobb oldalával. Ezeket az eseteket DIXMIER két tételben rögzítette.

TÉTEL 3.2.7   Ha $n-1\mid t$ vagy $n-1 \mid t-2$, akkor

$$g(n, t)=\frac{t(t-2)}{n-1}-t+1.$$

TÉTEL 3.2.8   Amennyiben $n-1 \mid t-1,$ úgy

$$g(n, t)=\frac {(t-1)^2}{n-1}-t.$$

Amikor az $n-1$ a $t-2$-nek osztója, a maximális értéket a legnagyobb szomszédos címletek választásával érhetjük el. A másik két esetben esetben $\lfloor t/(n-1) \rfloor$ differenciájú számtani sorozat lesz a konstrukció alapja. Ezek a tételek azonnal adják az $n=3$-ra és az $n=4$-re vonatkozó explicit formulákat. Ezekre DIXMIER csak utal publikációjában [4].

Legyen először $n=3.$ Ekkor két esetet vizsgálunk aszerint, hogy a $t$ páros vagy páratlan. A páros esetben a 3.2.7. Tétel alapján

$$g(3,t)=\frac{t(t-2)}{2}-t+1=\frac {t(t-2)}{2}-(t-2)-1=\frac {(t-2)^2}{2}-1.$$

Amennyiben a $t$ páratlan, tekintsük a 3.2.8. Tételt. Itt $t-1$ páros, így

$$g(3,t)=\frac {(t-1)^2}{2}-t=\frac {(t-1)(t-3)}{2}-1= \left \lfloor \frac {(t-2)^2}{2} \right \rfloor -1.$$

Ez pontosan megegyezik a LEWIN-féle 3.2.4.Tétellel.

Hasonlóan kaphatjuk meg a pontos formulát az $n=4$ esetben is. Legyen először $t=3k$, vagy $t=3k+2$. Alkalmazhatjuk a 3.2.7. Tételt, és kapjuk, hogy

$$g(4, t)=\frac {t(t-2)}{3}-t+1=\frac{t^2-2t+3}{3}-t=\frac {(t-1)^2+2}{3}-t.$$

Legyen most $t=3k+1,$ ekkor

$$g(4, t)=\frac {(t-1)^2}{3}-t.$$

A két képlet az oszthatósági viszonyok ismeretében egységes alakban is felírható:

TÉTEL 3.2.9  

$$g(4, t)=\left\lfloor \frac{(t-1)^2+2}{3}\right\rfloor -t.$$

Az $n=5$ esetben a $t=4k+3$-ra már nem kapunk pontos értéket a két DIXMIER-tétel alapján. Az $n$ további növelésével egyre ritkábban fordul elő, hogy a két tétel oszthatósági feltételei teljesülnek, így ezen az úton további általánosabb eredmények nem nyerhetők. Azt, hogy mégsem érdektelen a két tétel későbbi használata, például a $t=3n-1$ eset pontos számolásával is indokolhatjuk.

Más úton V. LEVnek [19] sikerült kiterjesztenie az ERDŐS-GRA-HAM-tétel érvényességi körét. Belátta, hogy a $g(n, 2n+k)$-ra vonatkozó formula egészen $k=n-2$-ig teljesül az eredetileg megfogalmazott formában. Bizonyításában FREIMAN két erős tételére támaszkodik. Itt lényeges, hogy ,,majdnem sűrű'' halmazok szerepeljenek, tehát ezen az úton sem nyerhetünk új formulákat. Az előbb említett 3.2.7. DIXMIER-tétellel azonban pontosan meghatározzuk $g(n, 3n-1)$-et:

$$g(n, 3n-1)=\frac{t(t-2)}{n-1}-t+1=\frac{(3n-1)(3n-3)}{n-1}-3n+2=6n-1.$$

Itt elfogynak a szakirodalomban az általánosan igaz formulák. Ez természetesen nem jelenti azt, hogy nem tudunk meghatározni bizonyos feltételek teljesülése esetén további $g(n, t)$-ket, pl. $g(5, t)$, ha $t\not=4k+3$, illetve $g(n, 4n-4);$ $g(n, 4n-3);$ $g(n, 4n-2)$ is azonnal adódik a DIXMIER-tételekből.