Eötvös Loránd Tudományegyetem Matematikai Intézet
Nagy Zoltán Lóránt
A Kombinatorikus Nullhelytétel alkalmazásai című PhD disszertációjának tézisei
Mathematikai Doktori Iskola Igazgató: Laczkovich Miklós, D.Sc. egyetemi tanár, a Magyar Tudományos Akadémia rendes tagja
Elméleti matematika doktori program Vezető: Szűcs András, D.Sc. egyetemi tanár, a Magyar Tudományos Akadémia levelező tagja
Témavezetők: Gács András, PhD Károlyi Gyula, D.Sc. Szőnyi Tamás, D.Sc. Számítógéptudományi Tanszék Természettudományi kar Budapest, 2014
1 Az úgynevezett polinommódszerhez kötődő bizonyítási eljárások a kombinatorika számos területén bizonyultak alapvető és hatékony eszköznek a kombinatorikus struktúrák feltárására. Ezen területek közé tartozik például az additív kombinatorika, a kombinatorikus geometria, a véges geometria, a gráfelmélet, vagy az extremális halmazrendszerek elmélete [1, 8, 12, 25, 27, 28]. Munkánkban Noga Alon nevezetes Kombinatorikus Nullhelytételének (Combinatorial Nullstellensatz) két változatával, illetve alkalmazásaival foglalkozunk. A Nullhelytétel alkalmazásaiban jellemzően azt használják ki, hogy egy bizonyos (többváltozós) polinom nem tűnhet el valamely nagy kiértékelési halmazon. Eme megközelítés lényegében az említett tétel egy következményeként, vagy gyengébb változataként is felfogható. Első eredményeink a tétel olyan alkalmazásához kapcsolódnak, amely kihasználja a tétel állításának teljes mélységét, és így nyújt bizonyítást véges test feletti polinomok értékkészletének és fokszámának összefüggésére. Az állítás az additív kombinatorika és a véges geometria nyelvén is megfogalmazható [13]. Kapcsolódó problémát old meg [24]. További eredményeink a Nullhelytétel egy új változatának alkalmazásához kapcsolódnak, ami Lasoń [22] és Karasev–Petrov [18] cikkein alapul. A szerzők egy kvantitatív változatát dolgozták ki a Kombinatorikus Nullhelytételnek, amely hatékony eszköznek bizonyult új eredmények elérésében, és egy nevezetes sejtés igazolásában a konstans együttható-azonosságok elméletének területén [19, 21]. Most térjünk rá a dolgozat főbb eredményeinek bemutatására. GF(q) vagy Fq a q elemű véges testet jelöli (ahol q egy prímhatvány). Jelölje továbbá CT P (x) a P (x) Laurent-polinom konstans tagját. Korábbi eredményeket követően (mint például [3]) Noga Alon az [1] nagyhatású áttekintő cikkben mutatta be az úgynevezett Kombinatorikus Nullhelytétel számos lehetséges alkalmazását. Általános alakban a tétel a következőképpen fogalmazható meg, Hilbert Nullhelytételéhez (lásd [17]) hasonló formában: Tétel. 2.1.1 [Combinatorial Nullstellensatz, általános alak] Legyen F tetszőleges test, és legyen P = P (x1 , . . . , xk ) egy k változós F feletti polinom. Legyenek továbbá A1 , A2 , . . . , Ak F elemeinek nemüres halmazai, és definiáljuk segítségükkel a Y (xi − s) gi (xi ) = s∈Ai
polinomokat. Ha P (s1 , s2 , . . . sk ) = 0 teljesül minden (s1 , s2 , . . . , sk ) ∈ A1 × . . . × Ak helyettesítésre a szorzathalmazból, akkor P a gi polinomok által generált ideálban van, vagyis P =
k X
hi gi ,
i=1
ahol hi = hi (x1 , x2 , . . . , xk ) többváltozós polinomok F felett. Azt is megkövetelhetjük, hogy deg(hi ) ≤ deg(P ) − deg(gi ) teljesüljön.
2 A legismertebb változata a 2.1.1 Tételnek azt állítja, hogy egy P (x1 , . . . , xk ) k-változós polinom nullhelyeinek halmaza nem tartalmazhatnak nagyméretű A1 ×. . .×Ak szorzathalmazt, amennyiben a P polinom bizonyos monomjának együtthatója nem nulla. Tétel. 2.1.2 [Combinatorial Nullstellensatz, el nem tűnési változat] Legyen F tetszőleges test, és legyen P = P (x1 , . . . , xk ) egy k változós F feletti polinom. Tegyük fel hogy létezik egy olyan Qk Pk Qk di di i=1 xi együtthatója i=1 di kitevőösszeg megegyezik P fokával, és i=1 xi monom, melyre a P -ben nem nulla. Ekkor bármely A1 , . . . , Ak ∈ F halmazok esetén, melyeknek számosságára |Ai | > di teljesül, létezik egy (s1 , s2 , . . . sk ) ∈ ×Ai amelyre P (s1 , s2 , . . . sk ) 6= 0. További egyszerű és jól használható speciális esete a 2.1.1 Tételnek az alábbi Következmény. 2.1.5 Ha az Fq feletti P = P (Y1 , . . . , Yk ) polinom eltűnik minden behelyettesítés esetén, akkor P felírható P (Y1 , . . . , Yk ) = h1 (Y1q − Y1 ) + · · · + hk (Ykq − Yk ) alakban, ahol a hi -k Y1 , . . . , Yk változójú, legfeljebb deg(P ) − q fokú polinomok. A Kombinatorikus Nullhelytétel általános alakja kevésbé elterjedten alkalmazott, először Károlyi Gyula cikkében tűnt fel [20]. A fenti következményt alkalmaztuk a disszertáció 3. fejezetében, a következő tételnek és kiterjesztésének bizonyításában. Tétel. 3.1.1 Tegyük fel, hogy {a1 , a2 , . . . , ap } egy GF(p) feletti multihalmaz, és p prímszám. P Ekkor az elemek indexeinek egy megfelelő permutációját véve, i iai = 0 teljesül, kivéve, ha az elemek között p − 2 darab a, és egy-egy a + b, a − b van valamely a és b, b 6= 0 testelemekre. Tétel. 3.1.2 Tegyük fel, hogy {a1 , a2 , . . . , aq } egy GF(q) feletti multihalmaz. Pontosan akkor P nincs a különböző b1 , b2 , . . . , bq ∈ GF(q) testelemeknek egy i ai bi = 0-t teljesítő permutációja, ha az ai elemek közül q − 2 darab a, és egy-egy a + b, illetve a − b van, ahol a és b, b 6= 0 testelemek. Idézzük fel Snevily sejtését, mely szerint minden G páratlan rendű (additív) Abel-csoportra, és minden pozitív egész n ≤ |G|-re teljesül, hogy ha {a1 , . . . , an } és {b1 , . . . , bn } G elemeinek két részhalmaza, akkor létezik az indexeknek egy π permutációja, melyre az a1 bπ(1) , a2 bπ(2) , . . . , an bπ(n) különböző elemek lesznek. A Snevily-sejtéssel való kapcsolata mellett – melyet a ciklikus csoport esetének igazolását követően nemrég általánosan is beláttak – a 3.1.2 Tételnek fontos következményei – pontosabban fogalmazva, ekvivalens megfogalmazásai – vannak a véges geometria és a véges testek feletti polinomok elméletében. Legyen GF(q) egy véges test. Ha M egy q elemű multihalmaz, akkor azt mondjuk, hogy M az f polinom értékkészlete, ha M = {f (x) : x ∈ GF(q)}, vagyis M -ben a megfelelő multiplicitásokkal fel vannak sorolva az f által felvett értékek. Adott M -re kereshetjük azt a minimális fokú polinomot, aminek éppen M az értékkészlete. Jól ismert, hogy minden polinom, sőt minden GF(q) → GF(q) leképezés függvényként azonosítható egy legfeljebb q − 1
3 fokú polinommal. A megfelelő polinomot a függvény redukált fokú polinomjának nevezzük, és a fokszáma az úgynevezett redukált fok. Ha M -ben az elemek összege nem nulla, akkor minden M értékkészletű redukált fokú polinom foka q − 1 lesz, és megfordítva, ha az elemek összege 0, akkor minden M értékkészletű redukált fokú polinom foka legfeljebb q − 2 lesz. Az előbb bemutatott tétellel ekvivalens állítást fogalmaz meg a Tétel. 3.2.1 Tegyük fel, hogy {a1 , a2 , . . . , ap } egy GF(q) feletti multihalmaz, melyre a1 + · · · + aq = 0. Pontosan akkor nincs legfeljebb q − 3 redukált fokú, M értékkészletű polinom, ha az ai elemek közül q − 2 darab a, és egy-egy a + b, illetve a − b van, ahol a és b, b 6= 0 testelemek. Foglalkozzunk most a véges geometriai változattal. Legyen q egy prímhatvány és V jelöljön egy n dimenziós GF(q) feletti vektorteret, amelynek pontjai (x1 , x2 , . . . , xn ) alakúak. Legyen Hij az xi = xj (i 6= j) egyenlettel definiált hipersík. Keressük meg azokat a hipersíkokat a vektortérben, melyeket az ∪i6=j Hij halmaz teljesen magába foglal. Vegyük észre, hogy ha n > q, akkor a halmaz minden pontot tartalmaz a skatulyaelv szerint, így a probléma csak akkor nemtriviális, ha n ≤ q. Eredményünket az alábbi tétel mondja ki: Tétel. 3.3.1 Legyen n ≤ q és H ⊆ ∪i6=j Hij egy V -beli hipersík, melyre H 6= Hij egyetlen i 6= j-re sem. Ez esetben a következők egyike teljesül: P (i) n = q, H = {(x1 , . . . , xn ) : c(xj − xk ) + i xi = 0} valamely c 6= 0 elemre és j 6= k indexre; P (ii) n = q − 1, H = {(x1 , . . . , xn ) : xj + i xi = 0} valamely j 6= k index esetén. Könnyű látni, hogy a (i) és (ii) pontokban megmutatott hipersíkok valóban benne vannak az unióban. A 4. fejezetben a 3.1.1 Tétel egy más irányú, kombinatorikusabb jellegű általánosítását tárgyaljuk. Előző tételünkben kihasználtuk, hogy algebrai értelemben az alaphalmaz egy test volt (ami lehetővé tette a Nullhelytétel alkalmazását ), ám valójában a probléma megfogalmazásában lényegében csak a additív csoport struktúrára van szükség. Ez adja a motivációt a prímeset ciklikus csoportokra való általánosítására. Megkülönböztetjük a páratlan és páros rendű ciklikus csoportok esetét.
Tétel. 4.1.1 Legyen M = {a1 , a2 , . . . , am } egy Zm = Z/mZ-beli multihalmaz, ahol m páratlan. P Ekkor az elemek indexeinek egy megfelelő permutációját véve i iai = 0 teljesül, kivéve ha az elemek között p − 2 darab a és egy-egy a + b, a − b van, ahol a és b csoportelemek és (b, m) = 1 . A páros rendű esetben két típusú kivételes multihalmaz-struktúrát kell megkülönböztetnünk. Az alábbi állítást könnyű ellenőrízni. Állítás. 4.1.2 Legyen m páros, m = 2k n alakú szám, ahol n páratlan. (i) Ha a Zm -beli M = {a1 , a2 , . . . , am } multihalmaz elemei ugyanazt a páratlan c maradékot adják mod 2k , akkor az M -beli elemek indexeinek nincsen olyan permutációja, melyre P i iai = 0 teljesül.
4 (ii) Ha M = {a, a, . . . , a + b, a − b} mod m, ahol a páros és (b, m) = 1 teljesül, akkor az P M -beli elemek indexeinek nincsen olyan permutációja, melyre i iai = 0 teljesül.
E két kivételes multihalmaz-struktúrát rendre homogén multihalmaznak nevezzük.
illetve
inhomogén
kivételes
Tétel. 4.1.3 Legyen M = {a1 , a2 , . . . , am } egy Zm -beli multihalmaz, ahol m páros. Ekkor az P elemek indexeinek egy megfelelő permutációját véve i iai = 0 teljesül, kivéve ha M homogén vagy inhomogén kivételes multihalmaz. A bizonyított eredmények szoros kapcsolatban állnak az additív kombinatorika ú.n. nullösszegeket vizsgáló ágával. Ennek alátámasztására Caro korábbi sejtését említjük meg, melyet Grynkiewicz igazolt [15]. Ez tekinthető a nevezetes Erdős-Ginzburg-Ziv tétel jelentős általánosításának. Tétel. 4.6.4 [Grynkiewicz, súlyozott Erdős-Ginzburg-Ziv] Legyenek b1 , . . . , bn olyan Zn -beli P elemek, melyekre ni=1 bi = 0 teljesül. Ha M egy Zn -beli 2n−1 elemű multihalmaz, akkor annak Pn létezik olyan M ′ = {a1 , . . . , an } ⊂ M n-elemű rész-multihalmaza amelyre i=1 ai bα(i) = 0 alkalmas α permutációt választva. Bialostocki egyik sejtéséből [7] szintén következne az előbbi tétel. Sejtés. 4.6.3 Tegyük fel, hogy a1 , . . . , an és b1 , . . . , bn két Zn -beli multihalmaz, melyre Pn Pn i=1 bi = 0 teljesül. Amennyiben n páros, akkor létezik olyan α permutáció, melyre i=1 ai = Pn a b = 0. i=1 i α(i)
Világos, hogy az n paritására vonatkozó feltétel szükséges, hiszen a 4.1.1 Tétel szerint ha P n páratlan és a bi elemek mind különbözők, akkor ni=1 bi = 0 teljesül, miközben a 4.1.1 Tétel szerinti kivételes struktúrájú multihalmazt választva az ai -k halmazának, nem létezik a keresett 0 összeget adó permutáció. A páros n esetben ugyanakkor nem kapunk ellenpéldát különböző P bi elemek választásával, ugyanis ekkor ni=1 bi = 0 nem teljesül. Grynkiewicz, Philipp és Ponomarenko 2014-ben megjelent cikkükben [16] egyfajta kiterjesztését igazolják a 4.1.1 és 4.1.3 tételeknek. Tetszőleges véges G Abel-csoportot tekintve szükséges és elégséges feltételt adnak arra, hogy egy M = {a1 , . . . a|G| } G-beli multihalmaz esetén minden g ∈ G elem felvétetik mint a |G| X
wi · aπ(i)
(W = {w1 , . . . , w|G| }, π ∈ Sym|G| )
i=1
súlyozott összeg értéke, ahol W = {0, 1, . . . |G| − 1}. Tétel. 4.6.5 [Grynkiewicz, Philipp, Ponomarenko, [16]] Ha valamely g ∈ G érték nem vétetik fel, mint az M multihalmaz W = {0, 1, . . . |G| − 1} súlyokkal vett összege, akkor • M elemei mind G egy részcsoportjának mellékosztályából származnak, vagy • G a Klein-csoport és M a csoport összes elemét tartalmazza, vagy
5 • G ciklikus csoport és M {a, a, . . . , a, a + b, a − b} alakú, ahol b a G csoport egy generátora. Visszatérünk a Kombinatorikus Nullhelytétel további alkalmazásaihoz. Az 5. fejezetben a Kombinatorikus Nullhelytétel egy olyan változatát mutatjuk be, amely többváltozós polinomok maximális fokú monomjainak együtthatóját egyszerű formulával képes kifejezni, ha a polinomot ki tudjuk értékelni elegendően nagy halmazok Descartes-szorzatán. Ez a gondolat nemrégiben Lasoń [22] illetve Karasev és Petrov [18] cikkeiben jelent meg, később a [21] cikkben általánosabb formában is megfogalmaztuk. Az állítás a következő. Tétel. 5.1.1 [Kvantitatív Nullstellensatz] Legyen F egy test, P ∈ F[x1 , x2 , . . . , xm ] pedig a test feletti többváltozós polinom, melynek foka, deg(P ) ≤ d1 + d2 + . . . + dm . Tekintsünk egy tetszőleges A1 , A2 , . . . , Am halmazrendszert Ai ⊆ F és |Ai | = di + 1 feltételek mellett. Ekkor a Q di xi P -beli monom együtthatója kifejezhető mint X X
X
z1 ∈A1 z2 ∈A2 zm ∈Am
ahol φi (x) =
Q
a∈Ai (x
P (z1 , z2 , . . . zm ) , φ′1 (z1 )φ′2 (z2 ) · · · φ′m (zm )
− a).
Mi a tétel fenti alakját használjuk, de megjegyezzük, hogy hasonló tétel mondható ki P Q Q minden maximális xdi i monom együtthatójáról. Olyan xdi i monomokról tehát, melyekhez Q nem létezik P -ben nem nulla együtthatójú ki=1 xδi i monom, melyre δi ≥ di minden i esetén, Q eltekintve magától xdi i -től. A 5.1.1 Tétel hatékony használatának kulcsa az, hogy az együtthatónak megfelelő bonyolult összeget leegyszerűsítjük, élve azzal a lehetőséggel, hogy az Ai halmazok megválasztásában nagy a szabadságunk. Amennyiben a vizsgált polinomunk elég szimmetriával rendelkezik, akkor elérhető, hogy az összegzésben a tagok többsége nullává váljon. Bizonyos polinomcsaládokra még az is elérhető, hogy az Ai halmazok optimális választásával mindösszesen egy tag nem tűnik el az összegből. A jelenség illusztrálására röviden bemutatjuk a (q-analóg) konstans együtthatós azonosságok elméletének alapjait, és Andrews már korábban belátott [29] sejtésére [4] egy igen rövid bizonyítást adunk. Ezt követően számos korábban már ismert, komplexebb konstans együttható-azonosságot vezetünk le, egyúttal igazolunk egy, a statisztikus mechanikában felmerült régi sejtést is. Legyenek x1 , . . . , xn független változók, és minden xi -hez rendeljünk egy ai nemnegatív egészet. 1962-ben Dyson — egy új statisztikus fizikai modellt vizsgálva — a Y xi ai 1− xj 1≤i6=j≤n
Laurent-polinom konstans együtthatójáról azt a sejtést fogalmazta meg, hogy egy egyszerű multinomiális együtthatóval fejezhető ki: Tétel. 5.2.1 [Dyson-azonosság [9]] A PD (x, a) :=
Y
1≤i6=j≤n
xi 1− xj
ai
6 Laurent-polinom konstans tagja (a1 + a2 + · · · + an )! . a1 ! · a2 ! · · · an ! Legyen q egy további független valós változó. 1975-ben Andrews [4] a Dyson-azonosság alábbi q-analóg változatát fogalmazta meg: Tétel. 5.2.2 [q-Dyson-azonosság] A Y QD (x, a) :=
1≤i<j≤n
xi xj
ai
qxj xi
∈ Q(q)[x, x−1 ]
aj
q-Laurent polinom konstans tagja (q)a1 +a2 +···+an . (q)a1 (q)a2 . . . (q)an Itt (t)k az úgynevezett q-Pochhammer-szimbólumot jelöli, tehát (t)k = (1 − t)(1 − tq) . . . (1 − tq k−1 ), azzal a kiegészítéssel hogy (t)0 definíció szerint 1. A q = 1 értéket rögzítve Andrews sejtése visszaadja a Dyson-sejtés állítását. Ez a sejtés egészen 1985-ig megoldatlan maradt, amikor Zeilberger és Bressoud [29] igazolták cikkükben elemi úton, de igen összetett bizonyítással. Karasev és Petrov [18] tételére alapozva röviden bemutatjuk a q-Dyson azonosság bizonyításán [19] keresztül a kvantitatív Nullstellensatz alkalmazását. Jegyezzük meg, hogy ha valamely i esetén ai = 0, akkor elhagyhatjuk az összes xi -t tartalmazó faktort, mivel ezek nem befolyásolják a QD konstans tagját. Így feltehetjük, hogy minden ai pozitív egész. P Jelölje σ az ai számok összegét, σ = ni=1 ai . Tekintsük a következő homogén polinomot! ! aj aY i −1 Y Y (xi − xj q t ) ∈ Q(q)[x]. (xj − xi q t ) · F (x1 , x2 , . . . , xn ) = 1≤i<j≤n
t=1
t=0
Q Világos hogy a QD (x) konstans tagja megegyezik F (x)-ben a i xiσ−ai monom együtthatójával. Mivel F homogén, ezért ez a monom maximális fokú. Szeretnénk a 5.1.1 Tételt erre a polinomra és a jelzett monomjára alkalmazni. Ehhez tekintsük F ∈ F = Q(q)-t olyan Ai halmazokon kiértékelve, ahol F eltűnik az A1 × · · · × An szorzathalmaz minden elemén, egyet kivéve. Válasszuk meg az Ai halmazokat úgy, hogy eleget tegyenek az |Ai | = σ − ai + 1 feltételnek, továbbá az ! aj aY i −1 Y Y t t (xi − xj q ) (xj − xi q ) · 1≤i<j≤n
t=0
t=1
szorzat tűnjön el a lehetséges legtöbb
(x1 , x2 , . . . xn ) = (c1 , c2 , . . . , cn ) ∈ A1 × · · · × An esetén. Ez motiválja az Ai = {1, q, . . . , q σ−ai } választást. Pi−1 Vezessük be a σi := j=1 aj jelölést, így tehát σ1 = 0 és σn+1 = σ. A következő kombinatorikusan igazolható állítás a bizonyítás kulcsa.
7 Állítás. 5.2.3 Minden c ∈ A1 × · · · × An esetén F (c) = 0, kivéve ha ci = q σi teljesül az összes i-re. Ezzel a QD konstans tagjának meghatározását visszavezettük a F (q σ1 , q σ2 , . . . , q σn ) φ′1 (q σ1 )φ′2 (q σ2 ) . . . φ′n (q σn ) érték kiszámolásához, ahol φi (z) = (z − 1)(z − q) . . . (z − q σ−ai ). Egyszerűen kiszámolható, hogy a kifejezés éppen megegyezik azzal, amit a 5.2.2 Tétel állít. Az imént bemutatott Dyson-azonosságra konstans együtthatós azonosságok nagy családjának egy képviselőjeként is tekinthetünk. Legyenek x0 , x1 , . . . , xn független változók. Tekintsük a következő alakú Laurentpolinomokat: P (x0 , x1 , . . . , xn ) :=
Y
0≤i6=j≤n
xi βij 1− , xj
βij ∈ N.
Célunk, hogy egyszerű képlettel ki tudjuk fejezni ilyen típusú polinomok konstans tagjait. Erre teljes általánosságban nincsen remény, ugyanakkor módszerünk számos részcsaládban gyümölcsözőnek bizonyul. A jelöléseink egyszerűsítése és átláthatósága kedvéért bevezetjük az (n + 1) × (n + 1)es B mátrixot - sorait és oszlopait 0-tól n-ig indexelve - és megfeleltetjük a P polinom szorzatalakjában a kitevőknek. Jelölés. 5.3.1 Az x := (x1 , . . . , xn ) és B = ((βij )) jelölést használva P (x0 , x, B) :=
Y
0≤i6=j≤n
xi βij . 1− xj
Számos hasonló alakú polinomhoz tartozó konstans együtthatós azonosság szorosan összefügg a Selberg-féle integrálformulával [26], melyet a következőképpen fogalmazhatunk meg.
Sn (α, β, γ) :=
=
Z
1
... 0
n−1 Y j=0
Z
n 1Y 0 i=1
tα−1 (1 − ti )β−1 i
Y
|ti − tj |2γ dt1 . . . dtn
1≤i<j≤n
Γ(α + jγ)Γ(β + jγ)Γ(1 + (j + 1)γ) , Γ(α + β + (n + j − 1)γ)Γ(1 + γ)
ahol az α, β, γ olyan komplex paraméterek, melyeknek valós része pozitív. Tekintsük először Morris [23] konstans együtthatós azonosságát, amely közismerten ekvivalens a Selberg-integrálforumulával. Értelmezhető a Morris-azonosság a Dyson-azonosság speciális esetének másfajta általánosításaként is, melyben egy új x0 változó is szerepel, míg ai = k ha i ∈ [1, n]. Az azonosság szerint a nemnegatív egész a, b, k paraméterű
8
n Y xj a x0 b 1− PM (x0 , x; a, b, k) := 1− · PD (x; k · 1) x0 xj j=1 n Y xj a xi k x0 b Y 1− = 1− 1− x0 xj xj 1≤i6=j≤n
j=1
Laurent polinom konstans tagja CT [PM (x0 , x; a, b, k)] =
n−1 Y j=0
(a + b + kj)!(kj + k)! . (a + kj)!(b + kj)!k!
1987-ben Aomoto a Selberg integrálformula általánosítását is belátta, miután egy további t1 · · · tm faktorral bővítette az integrandust (m ≤ n). Aomoto integrálformulájának megfelelő azonosság szerint Y n xj a+χ(j≤m) x0 b · PD (x; k · 1) 1− 1− CT x0 xj j=1
=
n−1 Y j=0
(a + b + kj + χ(j ≥ n − m))!(kj + k)! , (a + kj + χ(j ≥ n − m))!(b + kj)!k!
ahol χ(S) értéke 1 ha S teljesül, és 0 egyébként. Tétel. 5.3.3 [Aomoto-azonosság, [5]] CT [P (x0 , x; B A )] =
n−1 Y j=0
(a + b + kj + χ(j ≥ n − m))!(kj + k)! . (a + kj + χ(j ≥ n − m))!(b + kj)!k!
Forrester az általánosított Calogero-Moser-Sutherland (statisztikus fizikai) modellt elemezve a Morris-azonosság egy újabb fajta általánosítását vizsgálta. Tekintsük a Y xi PF (x0 , x; n0 ; a, b, k) = PM (x0 , x; a, b, k) · 1− xj n0
Laurent-polinomot. Sejtés. 5.3.4 [Forrester-sejtés, [11]]
CT [PF (x0 , x; n0 ; a, b, k)] = = M (n0 ; a, b, k) ×
n−n 0 −1 Y j=0
(j + 1)(a + b + kn0 + (k + 1)j)!(kn0 + (k + 1)j + k)! . (a + kn0 + (k + 1)j)!(b + kn0 + (k + 1)j)!k!
A kvantitatív Nullstellensatz állítását alkalmazva az 5. fejezetben belátjuk az Aomotoazonosságnak és a Forrester által sejtett azonosságnak egy közös q-analóg általánosítását,
9 amelyből következik az eredeti sejtés állítása is. Ezen eredmények az Aomotohoz és Forresterhez kötődő polinomok B A illetve B F mátrixait a m ≥ n − n0 esetben egyszerre tartalmazó 0 0 b ... b b ... b b ... b a 0 ... k k ... k k ... k 1 .. .. . . .. .. . . .. .. .. .. .. . . . . . . . . . . . a k . . . 0 k . . . k k . . . k n − m a + 1 k ... k 0 ... k k ... k n−m+1 B AF = . . . . . . . .. .. . .. .. . . . .. .. . . . .. .. . . . a + 1 k ... k k ... 0 n0 k ... k 0 ... k + 1 n0 + 1 a + 1 k ... k k ... k . .. . . . . . . . . . . .. . . .. .. . . .. .. .. .. . . a + 1 k ... k k ... k k + 1 ...
0
n
mátrix, illetve hozzá tartozó P (x0 , x; B AF ) Laurent polinom vizsgálatából következnek, ezen általános polinomnak határozzuk meg a konstans tagját. Jelölés. 5.4.1 Használva a x := (x1 , . . . , xn ), B = ((βij )) jelölést, Q(x0 , x, B) jelölje a Y xi βij P (x0 , x, B) = 1− xj 0≤i6=j≤n
-hez tartozó Laurent polinom q-analóg változatát, vagyis Y xi qxj . Q(x0 , x, B) := xj βij xi βji 0≤i<j≤n
Fő eredményünk tehát a következőképpen fogalmazható meg. Tétel. 5.4.2 Legyen n pozitív egész. Tetszőleges a, b, k nemnegatív egészek esetén, és m, n0 ≤ n ≤ m + n0 feltétel mellett, CT[Q(x0 , x; B AF )] = =
n−1 Y j=0
n−n Y0 1 − q (k+1)j (q)a+b+kj+χ(j>n0 )(j−n0 )+χ(j≥n−m) (q)kj+χ(j>n0 )(j−n0 )+k × . (q)a+kj+χ(j>n0 )(j−n0 )+χ(j≥n−m) (q)b+kj+χ(j>n0 )(j−n0 ) (q)k 1 − q k+1 j=1
Az m = 0 eset igazolja Baker és Forrester (q-analóg) sejtését [6, Conjecture 2.1], valamint q = 1-re specializálva, Forrester eredeti sejtését is. Az n0 = n eset adja az Aomoto-azonosság q-analóg változatát. Következmény. 5.4.3 [q-Aomoto azonosság] Legyen n pozitív egész. Tetszőleges a, b, k illetve m ≤ n nemnegatív egészek esetén CT[Q(x0 , x; B A )] =
n−1 Y j=0
(q)a+b+kj+χ(j≥n−m) (q)kj+k . (q)a+kj+χ(j≥n−m) (q)b+kj (q)k
10 A főtétel bizonyításának gondolata nagy vonalakban a 5.2.2 Tétel bizonyítását követi. Miután bevezetjük a Laurent-polinomhoz tartozó homogén polinomot, és vesszük annak a konstansnak megfelelő monomját, alkalmas Ai halmazokat kell találnunk az xi változókhoz. A homogén polinom szerkezete ezúttal jóval bonyolultabb, mint a q-Dyson esetében, emiatt lényegesen összetettebb a kulcslépés igazolása, hogy az így választott ×Ai szorzathalmazon a polinom egy kiértékelési hely kivételével eltűnik. Valójában először még élnünk kell a technikai k > a feltétellel is, hogy az Ai -k valóban halmazok legyenek és ne tartalmazzanak többszörös multiplicitással elemeket. Az így kapott egyetlen összeadandó meghatározása kiadja a 5.4.2 Tételt k > a esetben. Végül a teljes tétel igazolásához egy további lemmára van szükségünk, amely szélesebb körben is alkalmazható. Újra felidézve, hogy QD (x, k · 1) jelöli a PD (x; k · a) Dyson-azonosság (vagy a Morrisazonosság) Laurent polinomjának q-analógját az ai ≡ k esetben, a lemma így fogalmazható meg. P P Lemma. 5.4.9 Legyenek ri , si rögzített nemnegatív egészek (1 ≤ i ≤ n), amelyekre ri = si teljesül. Ekkor létezik olyan R = R(z) ∈ Q(q)(z) racionális törtfüggvény, amely csak az n illetve az ri , si számoktól függ, és segítségével kifejezhető a QD -ben egy másik együttható is, nevezetesen r1 x1 . . . xrnn k (q)nk CT s1 . sn QD (x; k · 1) = R(q ) x1 . . . xn (q)nk A lemmát a [14, Proposition 2.4] eredmény inspirálta. Ezt alkalmazzuk az általunk vizsgált Laurent polinomra, Q(x0 , x; B AF ) =
n Y
j=1
(qxj )a+χ(j≤m) (1/xj )b
Y
(1 − q k xi /xj )(1 − q k+1 xj /xi ) · QD (x; k · 1)
n0
-ra, és segítségével a kiterjesztést könnyen megmutathatjuk a k ≤ a esetre is. A kvantitatív Nullstellensatz az additív kombinatorikában is jól használhatónak bizonyult. Ehelyütt csupán a Hamidoune–Silva tételt említjük meg, amely Erdős és Heilbronn sejtését [10] igazolta, majd ennek lehetséges kiterjesztését [21]. A tétel tehát alkalmas halmazválasztások mellett egyszerűbb bizonyításokhoz és új eredményekhez vezetett és vezethet el.
Irodalomjegyzék [1] N. Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing 8 (1999) 7-29. [2] N. Alon, Additive Latin transversals. Israel J. Math. 117 (2000) 125-130. [3] N. Alon, M.B. Nathanson, I.Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Th. 56 (1996) 404-417. [4] G. E. Andrews, Problems and prospects for basic hypergeometric functions, Theory and Application of Special Functions, R. A. Askey, ed., Academic Press, New York (1975) 191-224. [5] K. Aomoto, Jacobi polynomials associated with Selberg integrals, SIAM J. Math. Anal., 18 (1987) 545-549. [6] T. H. Baker and P. J. Forrester, Generalizations of the q-Morris constant term identity, J. Combin. Th. A 81 (1998) 69-87. [7] A. Bialostocki, Some problems in view of recent developments of the Erdős Ginzburg Ziv theorem, INTEGERS: Electron. J. Comb. Num. Th. 7 (2007) A07. [8] A. Blokhuis, On the size of a blocking set in PG(2,p), Combinatorica 14 (1994) 273-276. [9] F. J. Dyson, Statistical theory of energy levels of complex systems, J. Math. Phys. 3 (1962) 140-156. [10] P. Erdős, H. Heilbronn, On the addition of residue classes modulo p, Acta Arith. 9 (1964) 149-159. [11] P. J. Forrester, Normalization of the wavefunction for the Calogero–Sutherland model with internal degrees of freedom, Int. J. Mod. Phys. B 9 (1995) 1243-1261. [12] P. Frankl, R. M. Wilson, Intersection theorems with geometric consequences. Combinatorica 1 (1981) 357-368. [13] A. Gács, T. Héger, Z. L. Nagy and D. Pálvölgyi, Permutations, hyperplanes and polynomials over finite fields, Finite Fields Appl., 16 (2010) 301-314. [14] I. Gessel, L. Lv, G. Xin, Y. Zhou, A unified elementary approach to the Dyson, Morris, Aomoto and Forrester constant term identities, J. Combin. Th. A 115 (2008) 1417-1435. [15] D. J. Grynkiewicz, A weighted Erdős Ginzburg Ziv theorem, Combinatorica 26 (2006) 445-453. [16] D. J. Grynkiewicz, A. Philipp, V. Ponomarenko, Aritmethic-progression-weighted subsequence sums, Israel J. Math. 193 (2013) 359-398. [17] D. Hilbert, Über die vollen Invariantensysteme, Math. Ann. 42 (1893) 313-373. [18] R. N. Karasev and F. V. Petrov, Partitions of nonzero elements of a finite field into pairs, Israel J. Math. 192 (2012) 143-156. [19] Gy. Károlyi, Z. L. Nagy, A simple proof of the Zeilberger - Bressoud q-Dyson theorem, Proc. Amer. Math. Soc. 142 (2014) 3007-3011. [20] Gy. Károlyi, An inverse theorem for the restricted est addition in abelian groups, J. Algebra 290 (2005) 557-593. [21] Gy. Károlyi, Z. L. Nagy, F. Petrov, V. Volkov, A new approach to constant term identities and Selberg-type integrals, Adv. Math. submitted. [22] M. Lasoń, A generalization of Combinatorial Nullstellensatz, Electron. J. Combin. 17 (2010) #N32. [23] W. G. Morris, Constant Term Identities for Finite and Affine Root Systems, Ph.D. Thesis, University of Wisconsin, Madison, 1982. [24] Z. L. Nagy, Permutations over cyclic groups, Europ. J. Comb. 41C (2014) 68-78. [25] L. Rédei, Lacunary polynomials over finite fields, North-Holland , 1973. [26] A. Selberg, Bemerkninger om et multipelt integral, Norsk Mat. Tidsskr. 26 (1944) 71-78. [27] T. Szőnyi, Blocking sets in Desarguesian affine and projective planes, Finite Fields Appl. 3 (1997) 187-202. [28] T. Tao, V. H. Vu, Additive Combinatorics, Cambridge University Press, 2006. [29] D. Zeilberger, D. M. Bressoud, A proof of Andrews’ q-Dyson conjecture, Discrete Math. 54 (1985) 201-224.
11