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:

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

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

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

$$n;$$ $$2n-1;$$ $$3n-2; \dots ;$$$$\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

$$t-n;$$$$\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

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

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

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

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

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

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

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

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

$$d=q, r=k+d$$    és $$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

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

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

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