next up previous contents
Next: A nem felírható számok Up: A nem felírható számok Previous: Az eddigi eredmények vázlatos   Tartalomjegyzék

Az ERDŐS-GRAHAM-sejtés

ERDOS és GRAHAM [7, 86.old.] tették fel a következő kérdést: ,,Hogyan kell megválasztani $ n$ darab pozitív egész számot $ 1 < a_1 < a_2 < \dots <a_n \le t$, hogy azoknak a számoknak a száma, amelyek nem írhatók fel $ \sum \limits_{i}^{ } c_ia_i$ alakban maximális legyen? Itt a $ c_i$-k szokásosan mind nemnegatív egész számok. Vajon a szomszédos egész számok, $ a_1=t-n+1, a_2=t-n+2, \ldots , a_n=t$ választása adja-e minden esetben a legtöbb nem felírható számot?''

Ebben a fejezetben egy egyszerű bizonyítást adunk erre a sejtésre. Ezenkívül végtelen sok más esetben tudunk példát adni további, a maximumot szintén biztosító $ A=\{a_1, a_2, \ldots ,a_n\}$ konstrukcióra is.

Jelentse továbbra is $ N(a_1,a_2, \dots,a_n)$ azoknak a pozitív egészeknek a számát, amelyek nem írhatók fel az $ a_1,a_2, \dots, a_n$ nemnegatív lineáris kombinációjaként. A $ g(n, t)$ mintájára definiáljuk a $ \nu(n,t)$ függvényt:

$\displaystyle \nu(n,t)=\max N(a_1,a_2, \dots,a_n),
$

ahol a maximumot az összes olyan $ a_i$-kre tekintjük, amelyek kielégítik az $ 1 < a_1 < a_2 < \dots <a_n \le t$ és $ (a_1, a_2, \dots , a_n)=1$ feltételeket. ERDŐS és GRAHAM állítását a következő formában írhatjuk fel az új jelölésünkkel:


TÉTEL 4.2.1   Legyenek $ n$ és $ t$ egész számok, $ 1 < n \le t.$ Ekkor

$\displaystyle \nu(n,t)=N(t-n+1,t-n+2, \dots , t).
$


A tétel bizonyításához felhasználjuk DIXMIER következő eredményét [4]:

TÉTEL 4.2.2   Ha $ a_n \le t$ akkor tetszőleges $ k$ esetén legalább
$ \min(t,kn-k+1)$ darab egész szám reprezentálható az $ a_1,a_2, \dots, a_n$ egészek segítségével az $ I_k=[(k-1)t+1, kt]$ intervallumban.

Tulajdonképpen ezen a tételen alapul DIXMIER korábban idézett két becslése, a 3.1.3. és 3.2.5. Tétel is, amelyek segítségével az ext-remális Frobenius-problémában is eredményesen dolgozhattunk.

A sejtés bizonyítása előtt kimondjuk a következő segédtételt:

LEMMA 4.2.3   Legyenek $ n$ és $ t$ egészek, $ 1 < n \le t.$ Legyenek továbbá a $ q$ és $ r$ egészek a $ t=q(n-1)+r$ maradékos osztás szerint definiálva, ahol $ 1 \le r \le n-1.$ Ekkor

$\displaystyle N(t-n+1,t-n+2, \dots , t)=\frac {(t-n+r-1)q} {2}.$

Az állítás pontosan megegyezik a 2. fejezet 15. feladatával. A bizonyítást ott részleteztük. (Megjegyezzük, hogy a lemma a 2. fejezet 9. feladatából és SELMER számtani sorozatokkal kapcsolatos 4.1.3. Tételéből is levezethető.)


Most rátérünk a 4.2.1. Tétel igazolására.


BIZONYÍTÁS: A fentebbi 4.2.2. Tételben az egyes $ I_k$ intervallumok rendre legalább

$\displaystyle n;$ $\displaystyle 2n-1;$ $\displaystyle 3n-2; \dots ;$$\displaystyle \text { } k(n-1)+1;
\text { } \dots $

felírható elemet tartalmaznak. Így azoknak a száma, amelyek nem írhatók fel az $ I_k$ intervallumból, rendre legfeljebb

$\displaystyle t-n;$$\displaystyle \text { } t-2n+1;\text { } t-3n+2;\dots ;
\text { } t-k(n-1)-1;\dots; \text { } t-q(n-1)-1=r-1.$

Ez egy számtani sorozat, amelyet összegezve

$\displaystyle N(a_1,a_2, \dots, a_n) \le \sum _{k=1}^q (t-k(n-1)-1).$

Láthatóan ez a szám megegyezik a 15. feladat bizonyításában a második $ \sum$-val (21. oldal).

Tehát $ \nu(n,t)=N(t-n+1, t-n+2, \dots, t),$ ahogyan állítottuk. $ \blacksquare $


A fejezet hátralévő részében további optimális halmazokat adunk meg.

Az eddigiekben azt találtuk, hogy az $ A=\{t-n+1,t-n+2, \dots ,t\}$ halmaz optimális abban az értelemben, hogy $ \nu(n,t)=N(A).$

Vajon léteznek-e más ilyen optimális halmazok is?

A következő tételben belátjuk, hogy nagyon sok esetben igen.


TÉTEL 4.2.4   Legyenek $ d, n, k$ egészek,  $ 2 \le d < n,$ $ 0 \le k < n-d.$ Ha $ n-k \equiv 0 \pmod {d+1}$ vagy $ n-k\ \equiv -1 \pmod {d+1}$, akkor $ t=dn+k$-ra létezik legalább két optimális $ A$ halmaz, azaz amelyre

$\displaystyle N(A)=\nu(n,dn+k).$


BIZONYÍTÁS: Azt fogjuk belátni, hogy van a $ \{t-n+1,t-n+2, \dots ,t\}$ halmaztól különböző optimális halmaz. Ugyanazokat a halmazokat használjuk fel, amelyek a 3.3.1. Tétel bizonyításában, $ g(n, dn+k)$ pontos értékének meghatározásánál szerepeltek. Természetesen ezért azonosak a $ d, k$ és $ n$ számokra megadott feltételek az ottaniakkal.


I. eset. Legyen $ n-k \equiv 0 \pmod {d+1}.$ Ekkor $ n=l(d+1)+k$, tehát

$\displaystyle dn+k=ld(d+1)+dk+k=(d+1)(ld+k).
$

Az $ A=\{a_1, a_2, \dots, a_n\}$ álljon a $ (d+1)$ összes többszöröseiből és a $ -1$ $ \mod {d+1}$ maradékosztály $ l$ darab legnagyobb eleméből $ t$-ig:

$\displaystyle A=\{d+1, 2(d+1), \dots , (ld+k-1)(d+1), (ld+k)(d+1),$

$\displaystyle dn+k-1, dn+k-1-(d+1), dn+k-1-2(d+1), \dots ,
$

$\displaystyle dn+k-1-(l-1)(d+1)\}.
$

Legyen $ z=dn+k-1-(l-1)(d+1)$ a legkisebb olyan eleme $ A$-nak, amely nem többszöröse a $ (d+1)$-nek.

Ismert tény (ld. pl. Sylvester [30]) és ebben a dolgozatban is tárgyaltuk a 2. fejezet 8. feladatában, illetve a 4.1.1. Tételben, hogy $ N(b,c)=(b-1)(c-1)/2 ,$ így

$\displaystyle N(A)=N(d+1,z)=(z-1)\frac {d}{2}=[dn+k-l(d+1)+d-1]\frac{d}{2}=
$

$\displaystyle =(dn+k-n+k+d-1)\frac{d}{2}.
$

Ez egyenlő $ \nu(n,t)=N(t-n+1,t-n+2, \dots ,t)$-vel, mivel a jelöléseinkkel és a 4.2.3. Lemma alapján $ t=dn+k=d(n-1)+k+d,$ így

$\displaystyle d=q, r=k+d$    és $\displaystyle dn+k-n+k+d-1=t-n+r-1.$


II. eset. Tegyük fel most, hogy $ n-k \equiv -1 \pmod {d+1}.$ Ekkor $ n=l(d+1)+k-1$ és

$\displaystyle dn+k=(d+1)dl+dk-d+k=(d+1)(dl+k)-d.
$

Ebben az esetben $ dn+k-1=(d+1)(dl+k-1)$ többszöröse
$ (d+1)$-nek. Az $ A=\{a_1, a_2, \dots, a_n\}$ halmaz tartalmazza ismét a $ (d+1)$ többszöröseit, továbbá az $ 1$ $ \mod {d+1}$ maradékosztály $ l$ darab legnagyobb elemét $ t$-ig:

$\displaystyle A=\{d+1, 2(d+1), \dots , (ld+k-1)(d+1),
$

$\displaystyle dn+k, dn+k-(d+1), dn+k-2(d+1), \dots , dn+k-(l-1)(d+1)\}.
$

A II. esetben az I. esethez hasonló számolással kapjuk, hogy
$ N(A)=\nu(n,t).$ $ \blacksquare $

Érdekes kettősség, hogy a 3.3.1., ill. 4.2.4.Tételben megadott kons-trukció mind $ g(n, dn+k)$, mind pedig $ \nu(n, dn+k)$ szempontjából az extremális konstrukciót adja, miközben a szomszédos $ a_i$-k választása csak $ \nu$-re vonatkozóan optimális.

Továbbra sem ismerjük a választ arra a kérdésre, hogy minden $ t$-re megadható-e a szomszédos elemek konstrukcióján kívül még legalább egy optimális halmaz, illetve vannak-e további, az említettektől eltérő optimális halmazok is a $ \nu(n,t)$ vizsgálatánál.



next up previous contents
Next: A nem felírható számok Up: A nem felírható számok Previous: Az eddigi eredmények vázlatos   Tartalomjegyzék
root 2004-12-04