KOMBINATORIƒNI IZREK O NIƒLAH DIPLOMSKO DELO

UNIVERZA V LJUBLJANI PEDAGO’KA FAKULTETA

IZA HANšEK ’U’TER’Iƒ

KOMBINATORIƒNI IZREK O NIƒLAH DIPLOMSKO DELO

LJUBLJANA, 2018

UNIVERZA V LJUBLJANI PEDAGO’KA FAKULTETA

DVOPREDMETNI UƒITELJ

IZA HANšEK ’U’TER’Iƒ

Mentor: DOC. DR. BO’TJAN KUZMAN

KOMBINATORIƒNI IZREK O NIƒLAH DIPLOMSKO DELO

LJUBLJANA, 2018

Zahvala

Zahvalila bi se svojemu mentorju, doc. dr. Bo²tjanu Kuzmanu, za njegovo vztrajnost in potrpeºljivost, predvsem za konkretno naloºeno delo, ki mi je vlilo notranjo moti- vacijo za dokon£anje diplomskega dela.

Zahvalila bi se tudi Ani za vso njeno pomo£ in podporo, Ur²ki in Vesni za njuno mo- ralno podporo in Luki, brez katerega bi obstajali le kisli obrazi.

Najve£ja zahvala pa gre star²em, skoraj sestri Tja²i in partnerju Luki, brez katerih si ºivljenja ne predstavljam.

Povzetek

V diplomski nalogi najprej obravnavamo Hilbertov izrek o ni£lah (Nullstellensatz) in ga predstavimo z nekaj primeri. Bistvo naloge je Alonov kombinatori£ni izrek o ni£lah, za katerega zahtevamo nekoliko stroºje pogoje in dobimo tudi mo£nej²i zaklju-

£ek. Ogledamo si tudi njegovo posledico, ki se izkaºe za mo£no orodje pri dokazova- nju nekaterih znanih izrekov. Tako kombinatori£ni izrek o ni£lah kot njegova posle- dica sta v nalogi v celoti dokazana. V nadaljevanju si ogledamo nekaj primerov upo- rabe kombinatori£nega izreka pri dokazovanju ºe znanih izrekov iz razli£nih podro£ij matematike, kot sta izrek Chevalleya in Warninga o skupnih ni£lah kon£ne druºine polinomov, izrek Cauchyja in Davenporta o velikosti vsote podmnoºic Zp ter ²e nekaj drugih zgledov iz geometrije in teorije grafov.

Klju£ne besede: Kombinatori£ni izrek o ni£lah, polinomi, kombinatorika.

Abstract

In this diploma thesis we rst look at Hilbert Nullstellensatz, along with some exam- ples. The main focus of this work, however, is combinatorial nullstellensatz by Alon, which requires stricter conditions and provides a stronger result. We also look at its corollary, which turns out to be a powerful tool when proving some already known theorems. We present detailed proof of both the Combinatorial Nullstellensatz and its corollary in this work. Afterwards, we look at some cases where we can use the combinatorial nullstellensatz to prove already known theorems from dierent elds of mathematics, such as the Chevalley-Warning theorem of common zeros of a family of polynomials, the Cauchy-Davenport theorem of cardinality of two nonempty subsets of Zp, and some other examples from geometry and graph theory.

Key words: Combinatorial Nullstellensatz, polynomials, combinatorics.

Kazalo

1 Uvod 1

2 Osnovni pojmi 2

3 Hilbertov izrek o ni£lah 6

4 Kombinatori£ni izrek o ni£lah 8

5 Primeri uporabe 12

5.1 Seznamsko barvanje ciklov . . . 12

5.2 Pokritje kocke z druºino hiperravnin . . . 13

5.3 Chevalley-Warningov izrek . . . 15

5.4 Cauchy-Davenportov izrek . . . 17

5.5 Omejene vsote . . . 18

5.6 Dokaz domneve Erdös-Heilbronn . . . 21

6 Sklep 23

Literatura 24

1 Uvod

Polinomska metoda v kombinatoriki je v sodobni matemati£ni literaturi opisana kot mnoºica tehnik, kjer z uporabo orodij iz algebrai£ne geometrije re²ujemo kombina- tori£ne probleme, ki vsebujejo bodisi aritmeti£ne strukture, kot so vsote in produkti, bodisi geometrijske strukture, kot so povezave med to£kami in premicami.

Raztreseni primeri uporabe te metode se ºe desetletja pojavljajo v teoriji ²tevil in aritmeti£ni kombinatoriki. Eno najbolj znanih orodij polinomske metode je kombi- natori£ni izrek o ni£lah (ang. combinatorial nullstellensatz), ki je osrednja tema di- plomskega dela. Izraelski matematik Noga Alon je skupaj s ²e dvema avtorjema izrek razvil leta 1996, tri leta kasneje pa ga je preoblikoval in objavil pod [5] skupaj s pri- meri uporabe pri dokazovanju, sicer ºe znanih izrekov, kot sta Chevalley-Warningov in Cauchy-Davenportov izrek. Kombinatori£ni izrek o ni£lah je kombinatori£na ver- zija klasi£nega Hilbertovega izreka o ni£lah, kjer slednjemu dodamo stroºje predpo- stavke, a s tem dobimo tudi mo£nej²i izrek.

V diplomskem delu si bomo pogledali formulacijo Hilbertovega izreka o ni£lah in ga ilustrirali s primeri. V naslednjem razdelku bosta sledila kombinatori£ni izrek o ni£lah in njegova posledica, prav tako ilustrirana z nekaj primeri, in njuna dokaza. Nasle- dnja poglavja so namenjena prikazu uporabnosti kombinatori£nega izreka o ni£lah pri dokazovanju izrekov iz razli£nih podro£ij matematike, med drugim tudi domneve Er- dös in Heilbronna, pokazali pa bomo tudi primera re²itve dveh nalog z matemati£nih tekmovanj.

1

2 Osnovni pojmi

Za za£etek si bomo ogledali nekaj denicij in izrekov pojmov, s katerimi se bomo sre-

£evali, najve£ji poudarek bo na poljih in polinomih nad polji. Dokaze tega razdelka najdemo na primer v Vidav pod [4].

Denicija 2.1. Grupa je mnoºica G z dvo£leno operacijo ∗, ponavadi jo ozna£imo kot (G,∗), za katero velja naslednje:

• Zaprtost za operacijo: ∀x, y ∈G:x∗y∈G.

• Asociativnost: ∀x, y, z ∈G: (x∗y)∗z =x∗(y∗z).

• Premore nevtralni element: ∃!e∈G ∀x∈G:e∗x=x∗e=x.

• Vsi elementi imajo inverz: ∀x∈G ∃x⁰ ∈G:x∗x⁰ =x⁰∗x=e.

ƒe za operacijo v grupi Gvelja tudi komutativnost, torej ∀x, y ∈ G : x∗y = y∗x, pravimo, da je grupa G komutativna ali abelova grupa.

Denicija 2.2. Kolobar je mnoºica K z dvema dvo£lenima operacijama. Prvo ope- racijo imenujemo se²tevanje, kompozitum dveh elementov x, y ∈ K pa vsoto, ki jo pi²emo x +y. Drugo operacijo imenujemo mnoºenje, kompozitum dveh elementov x, y ∈K pa zaznamujemo z x·y ali kraj²e xy. Pri tem morajo biti izpolnjeni naslednji pogoji:

• Za se²tevanje je (K,+) abelova grupa.

• Za mnoºenje mora biti K zaprta in veljati mora asociativnost.

• Distributivnost: ∀x, y, z ∈K : (x+y)·z =x·z+y·z in x·(y+z) =x·y+x·z. Enoti za se²tevanje v kolobarju navadno pravimo ni£ ali ni£la in jo ozna£imo kar z 0.

ƒe kolobar premore tudi enoto za mnoºenje, ji pravimo enica in jo ozna£imo z 1. ƒe je moºenje v kolobarju komutativno, pravimo, da je kolobar komutativen.

Denicija 2.3. Komutativen kolobar je polje, £e so vsi neni£elni elementi obrnljivi za mnoºenje.

2

Primeri kolobarjev so mnoºica celih ²tevil Z, mnoºica racionalnih ²tevil Q, mnoºica realnih ²tevil R, mnoºica kompleksnih ²tevilC, ki so opremljene s klasi£nim se²teva- njem in mnoºenjem ter mnoºica ostankov pri deljenju z n, Zn = {0,1, . . . , n−1} z operacijama po modulu n. Med na²tetimi kolobarji so poljaQ,R,Cin Zp, kjer je p pra²tevilo. Obrnljivost neni£elnih elementov v Z^p je posledica naslednjega izreka.

Izrek 2.1 (Mali Fermatov izrek). Naj bo p pra²tevilo in a neko nenegativno celo ²te- vilo. Potem je a^p ≡a(mod p). ƒe p ne deli a, potem velja a^p−1 ≡1(mod p).

Poznamo ²e druga kon£na polja, ki so vedno redapⁿ zap pra²tevilo,n ∈ N, in so enoli£no dolo£ena.

SK[x]ozna£imo kolobar polinomov ene spremenljivke s koecienti iz kolobarja K, ker pa bomo imeli ve£ opravka s polinomi s koecient iz polja, bo oznaka kar F[x]. Na primer polinomf(x) = 3x² −27 je eden izmed polinomov izQ[x]. Stopnja polinoma ene spremenljivke je kar najve£ji eksponent spremenljivke z neni£elnim koecientom, ki v njem nastopa. Zgornji polinomf je tako stopnje 2, to ozna£imo zdeg(f) = 2. Ni£le polinoma ene spremenljivke so elementi polja, v katerih je vrednost polinoma enaka ni£. Prej²nji polinom f ima dve ni£li3 in −3, ki sta obe iz Q. Seveda se lahko zgodi, da ni£la ni element polja iz katerega so koecienti polinoma.

Trditev 2.2. Naj bosta p, q ∈F[x] polinoma ene spremenljivke s koecienti iz polja F.

Velja naslednje:

• deg(p+q)≤max{deg(p),deg(q)},

• deg(p·q) = deg(p) + deg(q).

Zgled 2.1. Naj bosta p(x) = x² + 1 in q(x) = x² +x + 1 polinoma iz Z2. Oba polinoma sta stopnje dve. Ogledamo si njuno vsoto (p+q)(x) = 2x²+x+ 2 = x, ki pa je stopnje 1, kar je manj od 2. Oglejmo si ²e produkt danih polinomov (p·q)(x) = x⁴+x³+ 2x²+x+ 1 =x⁴+x³+x+ 1, katere stopnja je 4, kar je vsota stopenj danih dveh polinomov.

Bralca opozorimo, da je govora o polinomih s koecienti iz polja, torej ne iz kolo- barja, kjer lahko imamo delitelje ni£a. V primeru, da bi delitelji ni£a obstajali, bi stopnjo produkta lahko ocenili navzgor, kakor pri vsoti.

V nadaljevanju brez dokazov navajamo ²e nekaj osnovnih izrekov o polinomih.

3

Izrek 2.3 (Lema o deljenju). Naj bosta f(x) in g(x) izF[x] poljubna polinoma in naj bo g(x) 6= 0 stopnje n. Potem obstajata taka polinoma q(x) in r(x) iz F[x], pri £emer je stopnja r(x) kve£jemu n−1, da je

f(x) = q(x)g(x) +r(x).

Polinoma q(x) in r(x) sta enoli£no dolo£ena.

Izrek 2.4. Naj bo f ∈ F[x] polinom stopnjen in α ∈ F. ƒe je f(α) = 0, potem obstaja g ∈F[x] stopnje n−1, da velja

f(x) = (x−α)g(x).

Izrek 2.5. Naj bo f ∈F polinom stopnje n. Potem ima f najve£n ni£el v polju F.

Denicija 2.4. Polje F je algebrai£no zaprto, £e ima vsak nekonstanten polinom s koecienti iz F ni£lo v F.

Zgled 2.2. Mnoºica realnih ²tevil R je polje, ni pa algebrai£no zaprto, saj ni£li poli- noma p(x) = x² + 1 nista realni ²tevili. Primer algebrai£no zaprtega polja je mnoºica kompleksnih ²tevil C. Nobeno kon£no polje ni algebrai£no zaprto.

Izrek 2.6. Naj bo F algebrai£no zaprto polje in naj bo p polinom s koecienti iz polja F, ki je stopnje n. Potem ima polinom p v F natankon ni£el, £e vsako k-kratno ni£lo

²tejemo k-krat.

Zgornji izrek je ena izmed formulacij tako imenovanega osnovnega izreka algebre v primeru, ko za polje vzamemoC.

Za klasi£no algebrai£no geometrijo so pomembna predvsem algebrai£no zaprta polja, pri katerih lahko polinome identiciramo kar z njihovimi ni£lami. Pri kombinatoriki pa se pogosto uporablja kon£na polja. V obeh primerih pa nastopajo polinomi ve£

spremenljivk.

V primeru, da imamo polinome ve£ spremenljivk, recimon, ozna£imo kolobar po- linomov s koecienti iz polja z F[x₁, x₂, . . . , x_n]. Polinom lahko zapi²emo kot vsoto

£lenov, stopnja polinoma je v tem primeru najve£ja vsota eksponentov spremenljivk istega £lena. Za bolj²o predstavo si oglejmo naslednji zgled.

Zgled 2.3. Naj bo p(x, y) = x² +y² − 1 polinom dveh spremenljivk, ki je stopnje 2. Opazimo, da ima dva £lena najvi²je stopnje, njegove ni£le pa so vse to£ke enotske kroºnice, torej jih je neskon£no mnogo.

4

Polinom ve£ spremenljivk ima lahko ve£ £lenov iste stopnje, saj vsaka spremenljivka nastopa v razli£nih stopnjah, v posameznem £lenu pa je lahko ve£ razli£nih spremen- ljivk. Prej²nji polinom (f(x) = 3x²−27) ene spremenljivke je bil ravno tako stopnje 2, pa je imel le 2ni£li, medtem ko jih je imel ta polinom dveh spremenljivk iz prej²njega zgleda neskon£no.

5

3 Hilbertov izrek o ni£lah

Angle²ki matematik David Hilbert je na za£etku 20. stoletja dokazal ve£ izrekov, ki predstavljajo temelj sodobne algebrai£ne geometrije. Med temi izreki je tudi znani Hilbertov izrek o ni£lah, znan pod nem²kim imenom Nullstellensatz. Kombinato- ri£na verzija tega izreka predstavlja glavno temo te naloge in jo bomo spoznali v na- slednjem poglavju. Za za£etek pa si oglejmo eno izmed moºnih formulacij izvirnega Hilbertovega izreka o ni£lah in ga ilustrirajmo z nekaj primeri.

Izrek 3.1 (Hilbertov nullstellensatz [5]). Naj bo F poljubno algebrai£no zaprto polje in f, g₁, . . . , g_m polinomi v kolobarju polinomov F[x₁, x₂, . . . , x_n]. ƒe je f(α) = 0 za vsako skupno ni£lo α ∈ Fⁿ polinomov g₁, g₂, . . . , g_m, potem obstaja ²tevilo k ∈ N in polinomi h₁, h₂, . . . , h_m izF[x₁, x₂, . . . , x_n], da velja

f^k=

n

X

i=1

h_ig_i.

Izreka v tej nalogi ne bomo dokazali, zainteresirani bralec pa lahko najde dokaz v ²te- vilnih visoko²olskih u£benikih abstraktne algebre, na primer pod [8]. Za nadaljne ra- zumevanje je potrebno opozoriti, da dokaz ni konstruktiven. Zagotavlja zgolj obstoj polinomov, ne pa tudi kako te polinome v konkretnem primeru dolo£imo. Iz njega ne izvemo ni£esar o vrednosti ²tevilak niti o stopnjah polinomov h_i. Oglejmo si to na nekaj zgledih.

Zgled 3.1. Najprej si ogledamo primer s polinomi ene spremenljivke nad poljem C.

Naj bo f(x) = x+ 1 in naj bosta g₁(x) = x² −1 in g₂(x) = x² +x. O£itno imata polinoma g₁ in g₂ le eno skupno ni£lo α =−1, za katero velja tudi f(α) = 0. Torej so predpostavke izpolnjene, zato nam Hilbertov izrek zagotavlja, da obstajajo ²tevilo k in polinoma h₁, h₂, da velja

f^k =h₁g₁+g₂h₂.

Poskusimo poiskati kak²na ustrezna polinoma h₁, h₂ z ugibanjem. Denimo, da bi ob- stajala taka polinoma prve stopnje ºe za vrednost k = 1. Pi²emo h₁(x) = ax +b in h₂(x) =cx+d, kjer so a, b, c, d∈C ter poskusimo re²iti ena£bo

x+ 1 = (ax+b)(x²−1) + (cx+d)(x²+x)

= (a+c)x³+ (b+c+d)x²+ (−a+d)x−b.

Iz primerjave koecientov dobimo sistem ena£b z enoparametri£no re²itvijo a ∈ C, b = −1, c = −a in d = 1 +a. ƒe izberemo recimo a = 1, dobimo primer ustreznih

6

polinomov h₁(x) = x−1 in h₂(x) =−x+ 2. Imeli smo torej sre£o, da smo ºe za k= 1 ob predpostavki, da sta polinoma h₁, h₂ prve stopnje, na²li neko re²itev. V splo²nem pa bi se lahko zgodilo, da bi bili k in stopnje polinomov bistveno vi²je.

Zgled 3.2. Naj bo f(x) = x+ 1 in naj bosta g₁(x) = x² + 2x+ 1 in g₂(x) = x³ + 2x²+x. O£itno imata polinoma g₁ in g₂ le eno skupno ni£lo α =−1, za katero velja tudi f(α) = 0. Torej so pogoji izreka izpolnjeni in zato velja f^k = g1h1 +g2h2 za neka polinoma h₁, h₂. Denimo, da obstajata taka polinomoma prve stopnje in pi²emo h₁(x) =ax+b ter h₂(x) = cx+d, kjer so a, b, c, d∈C. Z nekaj ra£unanja ugotovimo, da za k = 1 sistem nima re²itve, zato poskusimo za k = 2 re²iti ena£bo

(x+ 1)² = (ax+b)(x²+ 2x+ 1) + (cx+d)(x³+ 2x²+x)

=cx⁴+ (a+ 2c+d)x³+ (2a+b+c+ 2d)x²+ (a+ 2b+d)x+b.

Iz primerjave koecientov dobimo sistem ena£b z enoparametri£no re²itvijo a ∈ C, b= 1, c= 0 in d=−a.

Zgled 3.3. Poglejmo si ²e primer s tremi spremenljivkami. Naj bo f(x, y, z) = x+ y+ z² −z −3 in g₁(x, y, z) = x− 1, g₂(x, y, z) = y −2, g₃(x, y, z) = z(z −1). Ni£le polinoma g1 so trojice oblike (1, y, z) za katerakoli y, z. Podobno velja za g2, da so ni£le oblike (x,2, z) in za g₃ so ni£le (x, y,0) ali (x, y,1). Skupni ni£li sta torej le (1,2,0) in (1,2,1). Zlahka preverimo, da velja f(1,2,0) = 0 in f(1,2,1) = 0. Torej f izpolnjuje predpostavko izreka, zato velja f^k = P3

i=1g_ih_i za neke polinome h_i in neko

²tevilo k. Tudi v tem primeru se izkaºe, da re²itev obstaja ºe za k = 1, tedaj ena£bo re²ijo kar konstantni polinomi h₁ =h₂ =h₃ = 1.

Zadnji zgled je imel enostavno re²itev, saj so bili polinomigi v resnici polinomi ene spremenljivke x_i. To je osnovna ideja kombinatori£ne verzije izreka o ni£lah, ki ga bomo spoznali v naslednjem poglavju.

7

4 Kombinatori£ni izrek o ni£lah

V primeru, ko pri Hilbertovem izreku zahtevamo nekoliko stroºje predpostavke, do- bimo tudi mo£nej²o razli£ico izreka o ni£lah, ki se je uveljavila pod imenom kombi- natori£ni nullstellensatz (ang. combinatorial nullstellensatz). Ta izrek je formuliral in dokazal izraelski matematik Noga Alon leta 1999 in ºe v izvirni objavi pokazal nje- govo uporabnost pri dokazovanju nekaterih, sicer ºe znanih, izrekov iz razli£nih po- dro£ij matematike.

Denimo, da v predpostavkah Hilbertovega izreka zahtevamo, da je m = n, torej, da je ²tevilo polinomovg_i enako ²tevilu spremenljivk x_i, in da so polinomig_i v resnici polinomi ene spremenljivke brez ve£kratnih ni£el, torej jih lahko zapi²emo kot

gi(xi) = Y

s∈S_i

(xi −s),

kjer je Si ⊂ F mnoºica ni£el polinoma gi. V tem primeru lahko dokaºemo naslednji izrek.

Izrek 4.1 (Kombinatori£ni izrek o ni£lah, prvi£). Naj bo F poljubno polje,

f ∈ F[x1, x2, . . . , xn] polinom in S1, S2, . . . , Sn kon£ne, neprazne podmnoºice mno- ºice F. Naj bodo g_i(x_i) = Q

s∈S_i(x_i − s) polinomi v eni spremenljivki, ki so stopnje deg(g_i) =|S_i|. ƒe je

f(s₁, s₂, . . . , s_n) = 0

za vse s₁ ∈S₁, s₂ ∈S₂, . . . , s_n∈S_n, potem obstajajo polinomi

h₁, h₂, . . . , h_n∈F[x₁, x₂, . . . , x_n], katerih stopnje so deg(h_i)≤deg(f)−deg(g_i), da je f =

n

X

i=1

h_ig_i.

Dodatno, £e so polinomi f, g1, . . . , gn iz R[x1, x2, . . . , xn], kjer je R nek podkolobar F, potem bodo polinomi h₁, h₂, . . . , h_n prav tako iz R[x₁, x₂, . . . , x_n].

Dokaz bo sledil kasneje. Ta izrek je od Hilbertovega mo£nej²i v tem smislu, da je po- lje F v tem primeru poljubno, izrek pa nam zagotavlja obstoj re²itve za k = 1 in navzgor omeji stopnje iskanih polinomov h_i. Oglejmo si to na naslednjem zgledu.

Zgled 4.1. še v prej²njem razdelku smo videli, da za polinom f(x, y, z) =x+y+z²− z−3 in polinome v eni spremenljivkig1(x) = x−1, g2(y) = y−2, g3(z) = z(z −1) velja

f¹ =

3

X

i=1

g_ih_i,

8

kjer so h_i konstantni polinomi h₁ = h₂ = h₃ = 1. Mnoºice S_i iz Kombinatori£nega izreka so v tem primeru S₁ = {1}, S₂ = {2} in S₃ = {0,1}, izrek pa nam zagotavlja, da bodo iskani polinomi stopenj deg(h₁) ≤ 1, deg(h₂) ≤ 1 in deg(h₃) ≤ 0. To se sklada z na²o re²itvijo.

Naslednja verzija kombinatori£nega izreka o ni£lah pa je neposredna posledica prej-

²nje in se v tej obliki najve£krat uporablja pri dokazovanju konkretnih trditev.

Posledica 4.2 (Kombinatori£ni izrek o ni£lah, drugi£). Naj bo F poljubno polje, f = f(x₁, x₂, . . . , x_n) polinom stopnje t = Pn

i=1t_i, kjer je t_i ∈ N, in S₁, S₂, . . . , S_n kon£ne, neprazne podmnoºice F mo£i |S_i| > t_i za vse i. ƒe je koecient pri £lenu maksimalne stopnje Qn

i=1x^t_iⁱ v polinomu f neni£eln, potem obstajajo elementi s₁ ∈ S₁, s₂ ∈S₂, . . . , s_n ∈S_n, da je

f(s₁, s₂, . . . , s_n)6= 0.

Tudi dokaz posledice sledi v nadaljevanju, bralca pa opozorimo, da lahko v polinomu f obstaja ve£ monomov najve£je stopnje in posledica velja za vsakega od njih, £e je le ustrezni koecient neni£eln.

Zgled 4.2. Naj bo f(x, y) = xy + 2y = xy + 2y + 0x², potem je polinom stopnje deg(f) = 2. Ker je xy monom maksimalne stopnje s potencama t₁ = 1 in t₂ = 1, po- sledica trdi, da lahko za poljubni mnoºici S₁, S₂ mo£i vsaj 2 vselej izberemo elementa s₁ ∈ S₁ in s₂ ∈ S₂, da bo f(s₁, s₂) 6= 0. Po drugi strani pa to ne velja nujno za mno- ºici S₁⁰ mo£i vsaj 3 in mnoºico S₂⁰ mo£i vsaj 1, ki bi ustrezali monomu x², ki ima v resnici ni£elni koecient. V tem primeru za S₁⁰ ={1,2,3} in S₂ ={0} ustreznega para ni mogo£e najti.

Zanimivej²i zgledi uporabe sledijo v naslednjem poglavju. Da dokaºemo izrek, pa naj- prej dokaºemo naslednjo pomoºno trditev.

Lema 4.3. Naj bo P(x₁, x₂, . . . , x_n) polinom nad poljem F, stopnja polinoma P v spremenljivki x_i najve£ t_i za vsak i in naj bodo S_i kon£ne podmnoºice F mo£i vsaj t_i+ 1. ƒe je P(s₁, s₂, . . . , s_n) = 0 za vse (s₁, s₂, . . . , s_n)∈S₁ ×S₂×. . .×S_n, potem je P ≡0.

Dokaz. Dokazujemo z indukcijo nan. Za n = 1 imamo P(x₁) polinom ene spremen- ljivke stopnje deg(P(x₁)) ≤ t₁ in kon£no mnoºico S₁ ⊆ F mo£i vsajt₁ + 1. Poli- nom stopnje t₁ ima najve£ t₁ ni£el v danem polju. Po na²i predpostavki ima polinom P(x₁) ve£ ni£el, zato je P(x₁)≡0.

9

Denimo, da trditev velja za n−1 in dokazujemo za n, kjer je n≥2. Zapi²emo

P(x₁, x₂, . . . , x_n) =

tn

X

i=0

P_i(x₁, x₂, . . . , x_n−1)xⁱ_n

kot polinom spremenljivke x_n, torej so koecienti pri xⁱ_n polinomi v ostalih spremen- ljivkah. Po predpostavki izreka jeP(s₁, s₂, . . . , s_n) = 0, torej je P_i(s₁, s₂, . . . , sn−1) = 0 za vse (s₁, s₂, . . . , sn−1)∈S₁×S₂ ×. . .×S_n. Ker v P_i nastopax_j v stopnji najve£ t_j, po indukcijski predpostavki veljaP_i(x₁, x₂, . . . , x_n−1)≡0. Sledi P ≡0.

Dokaz izreka 4.1. Naj bot_i =|S_i| −1 za vsaki. Po predpostavki je

f(s1, s2, . . . , sn) = 0za vse n-terice(s1, s2, . . . , sn)∈S1×S2 × · · · ×Sn. (1) Za vsak1≤i≤n je polinom

g_i(x_i) = Y

s∈S_i

(x_i−s) = x^t_iⁱ⁺¹−

ti

X

j=0

g_ijx^j_i. (2)

Polinomi g_i imajo po konstrukciji vodilni koecient enak 1 in so stopnje t_i + 1, zato jih lahko zapi²emo v zgornji obliki, pri £emer je gij koecient pripadajo£ega £lena.

V nadaljevanju bomo konstruirali polinom f tako, da bomo vsako pojavitev posame- zne spremenljivkex_i stopnje k_i > t_i v f, zapisanem kot linearno kombinacijo mono- mov, zamenjali z x_i manj²e stopnje z uporabo zveze pod (2).

Za bolj²o predstavo, kaj natanko storimo, si poglejmo primer, ko v f nastopa £len s spremenljivko x₁ v stopnji k₁ > t₁. Ker je k₁ > t₁, lahko zapi²emok₁ = t₁ + 1 +r₁, kjer je r1 ∈N⁰. Potem lahko izrazimo

f = (. . .) +ax^k₁¹x^r₂²· · ·x^r_nⁿ

= (. . .) + (ax^r₁¹x^r₂²· · ·x^r_nⁿ)x^t₁¹⁺¹ in za k₁(x₁, x₂, . . . , x_n) =ax^r₁¹x^r₂²· · ·x^r_nⁿ o£itno velja

deg(k₁)≤deg(f)−(t₁+ 1) = deg(f)−deg(g₁).

Sedaj od²tejemo

f −k₁g₁ = (. . .) +k₁x^t₁¹⁺¹−k₁(x^t₁¹⁺¹−

t1

X

j=0

g_ijx^j₁)

= (. . .) +k₁

t1

X

j=0

g_ijx^j₁

10

in dobimo polinom, v katerem smo izbranemu £lenu za 1zmanj²ali stopnjo spremen- ljivke x₁. To ponavljamo z vsemi £leni, v katerih spremenljivka x₁ nastopa v stopnji ve£ji od t₁, dokler ne pridemo do stopnje najve£ t₁ pri vseh spremenljivkahx₁ in do- bimo polinom

f −k₁g₁ −k₂g₁−. . .−k_mg₁.

Zah1(x1, x2, . . . , xn) =k1+k2 +. . .+km o£itno velja deg(h1)≤deg(f)−deg(g1). (V primeru, ko so koecienti polinomov f, g₁, . . . , g_n iz nekega podkolobarja, je glede na konstrukcijo polinoma h_i o£itno, da bodo njegovi koecienti prav tako iz istega podkolobarja.) Enako storimo za vse preostale spremenljivkex₂, x₃, . . . , x_n in na koncu dobimo polinom

f =f −h₁g₁−h₂g₂−. . .−h_ng_n,

kjer je deg(h_i) ≤ deg(f)−deg(g_i) za vse i. Za vse (s₁, s₂, . . . , s_n) ∈ S₁ × · · · ×S_n je f(s1, s2, . . . , sn) = f −h1g1 −h2g2−. . .−hngn = 0, saj velja (1) in vsak si ∈ Si je ni£la polinomag_i. Po lemi 4.3 je f ≡ 0, od koder sledi, da je f = Pn

i=1h_ig_i, kar smo ºeleli pokazati.

Dokaz posledice 4.2. Brez teºav lahko privzamemo, da je|S_i| = t_i + 1 za vsaki. De- nimo, da izrek ne drºi, torej za vse s1 ∈S1, s2 ∈S2, . . . , sn ∈Sn je

f(s₁, s₂, . . . , s_n) = 0.

Deniramog_i(x_i) = Q

s∈S_i(x_i − s), ki je stopnje deg(g_i) = t_i + 1. Po izreku 4.1 obstajajo polinomi h₁, h₂, . . . , h_n ∈F[x₁, x₂, . . . , x_n], ki zado²£ajo neenakosti deg(h_i)≤deg(f)−deg(g_i), da velja

f =

n

X

i=1

h_ig_i.

Po predpostavki izreka je koecient pri £lenu maksimalne stopnjeQn

i=1x^t_iⁱ na levi ne- ni£eln, zato mora to veljati tudi za desno stran.

Na desni strani je vsota £lenov oblike higi =hi

Y

s∈S_i

(xi−s) = hi(x^t_iⁱ⁺¹−

ti

X

j=0

gijx^j_i),

ki so stopnje najve£ deg(f). Monom najve£je stopnje na desni je h_ix^t_iⁱ⁺¹, saj so pre- ostali £leni vsote niºjih stopenj. Vsak £len najve£je stopnje v higi mora biti deljiv z x^t_iⁱ⁺¹, zato £len Qn

i=1x^t_iⁱ ni najve£je stopnje v h_ig_i, kar pa je protislovje.

11

5 Primeri uporabe

V tem razdelku se bomo pobliºje spoznali z ve£ zgledi uporabe izreka, ki prihajajo iz razli£nih podro£ij matematike.

5.1 Seznamsko barvanje ciklov

Prvi zgled prihaja iz teorije grafov, lahko pa ga zastavimo tudi kot uganko. Re²itev je povzeta po [1].

Zgled 5.1 (Rusko matemati£no tekmovanje 2007, naloga 5). Na ogli²£a pravilnega stokotnika zapi²emo po dve razli£ni ²tevili na vsako ogli²£e. Dokaºi, da lahko po eno

²tevilo na vsakem ogli²£u odstranimo, da bodo ²tevila na sosednjih ogli²£ih razli£na.

Nalogo s pomo£jo kombinatori£nega izreka o ni£lah re²imo tako. Zapi²emo polinom f(x1, x2, . . . , x100) = (x1−x2)(x2−x3)· · ·(x99−x100)(x100−x1).

Gre za polinom stopnje 100, koecient pri £lenu maksimalne stopnje x1x2· · ·x100 pa je enak 2, torej neni£eln. Za poljubne mnoºice S_i z lastnostjo |S_i| = 2, velja da lahko izberemo po en element v vsaki tako, da bo f(s₁, s₂, . . . , x₁₀₀) 6= 0. Elementi mnoºice S_i predstavljajo ²tevila na ogli²£ih, polinom f pa o£itno zavzame vrednost 0 natanko tedaj, ko sta neki ²tevili na sosednjih ogli²£ih enaki. S tem je trditev dokazana.

Navedeni zgled predstavlja tipi£en primer uporabe kombinatori£nega izreka o ni£lah oziroma njegove posledice. Izrek lahko uporabimo takrat, ko je mogo£e zapisati po- goje problema v obliki polinoma in smiselno uporabiti rezultat izreka.

Zgornji dokaz lahko v resnici uporabimo za poljubni cikel sode dolºine in ustrezni iz- rek zapi²emo v jeziku teorije grafov. Naj bo Γ = (V, E) graf, kjer mnoºica V(Γ)pred- stavlja njegova vozli²£a, mnoºica E(Γ)pa povezave.

Ozna£imo s C razred vseh barv. Naj bo L : V(Γ) → P(C) preslikava, ki vsakemu vozli²£uv grafa Γpriredi mnoºico barv L(v) ⊂ C. Preslikavi Lpravimo izbira barv za vozli²£a grafa Γ, mnoºico L(v) pa imenujemo seznam dopustnih barv za vozli²£e v. Preslikava c:V(Γ)→C je L−barvanje (vozli²£) grafa Γ, £e veljata naslednja pogoja.

• c(v)∈L(v) za vsako vozli²£e v grafuΓ,

• za poljubni dve sosednji vozli²£iu inv grafa Γ je c(u)6=c(v).

12

Naj graf Γdopu²£a L−barvanje za vsako izbiro barv L, za katero velja, da je |L(v)| ≥ k za vsako vozli²£e v ∈ V(Γ). Potem pravimo, da jeΓ k−izbirljiv. Najmanj²e ²tevilo k, za katero je Γ k−izbirljiv, imenujemo ²tevilo izbire (choice number) ali seznamsko kromati£no ²tevilo grafa Γin ga ozna£imo z ch(Γ).

Izrek 5.1. Za cikel sode dolºine velja ch(C_2n) = 2. Dokaz. Vstavi 2n namesto 100 v prej²nji zgled.

5.2 Pokritje kocke z druºino hiperravnin

Kot ²e en primer uporabe kombinatori£nega si poglejmo nalogo 6 iz mednarodne ma- temati£ne olimpijade (MMO) leta 2007, ki se je odvijala v Vietnamu, in je ena naj- slab²e re²evanih nalog v vsej zgodovini matemati£nih olimpijad.

Zgled 5.2 (MMO 2007, naloga 6). Naj bo n ∈N in

S ={(x, y, z) :x, y, z ∈ {0,1, . . . , n}, x+y+z >0}

mnoºica (n+ 1)³ −1 to£k v 3-razseºnem prostoru. Dolo£i najmanj²e ²tevilo ravnin, katerih unija vsebujejo S, in nobena ne poteka skozi to£ko (0,0,0).

Ta naloga ima elementarno re²itev, ki je razmeroma dolga in komplicirana, z uporabo kombinatori£nega izreka o ni£lah, pa je dokaz kratek, povzemamo ga po [1].

Re²itev: Hitro ugotovimo, da 3n ravnin zado²£a, saj lahko vzamemo ravnine x+y+ z = k za k ∈ {1,2, . . . ,3n}. Nobena od njih ne poteka skozi to£ko (0,0,0), hkrati pa pokrijejo S, saj vsaka to£ka (x, y, z) ∈ S ustreza eni od ena£b. Sedaj ºelimo pokazati, da z manj ravninami tega ni mogo£e storiti.

Denimo, da lahko to storimo z manj ravninami, denimo s k < 3n. Naj bodo to rav- nine a_ix+b_iy+c_iz+d_i = 0. Deniramo naslednja polinoma:

A(x, y, z) =

k

Y

i=1

(a_ix+b_iy+c_iz+d_i),

B(x, y, z) =

n

Y

i=1

(x−i)(y−i)(z−i).

Prvi je stopnje k, stopnja drugega pa je 3n. Zato sta koecienta pri £lenu xⁿyⁿzⁿ v polinomu A enak 0, v polinomu B pa 1. Sedaj si poglejmo polinom

P(x, y, z) =A(x, y, z)− A(0,0,0)

B(0,0,0)B(x, y, z).

13

Opazimo, da je stopnje 3n in velja

P(x, y, z) = 0za vse(x, y, z)∈ {0,1, . . . , n}³. (3) Koecient pri £lenu xⁿyⁿzⁿ je enak

A(0,0,0)

B(0,0,0) = d₁d₂· · ·d_k (−1)³(−2)³· · ·(−n)³,

kar je razli£no od ni£. Po izreku 4.2 za mnoºice S = S₁ = S₂ = S₃ = {0,1, . . . , n}

velikosti n+ 1 obstaja (x₀, y₀, z₀)∈S³, da je P(x₀, y₀, z₀)6= 0, kar pa je v protislovju s (3). Torej je ²tevilo ravnin, ki ustrezajo pogojem, najmanj 3n.

Ta zgled je v resnici samo poseben primer izreka o druºini hiperravnin v Rⁿ, ki sta ga dokazala Alon in Füredi ºe leta 1993 pod [5].

Izrek 5.2. Naj bodo H₁, H₂, . . . , H_m razli£ne hiperravnine v Rⁿ, ki pokrijejo vse celo-

²tevilske to£ke v enotski kocki {0,1}ⁿ razen ene. Potem je m≥n.

Dokaz. Brez ²kode za splo²nost lahko privzamemo, da je nepokrito ogli²£e kar izhodi-

²£e. Naj bo (a_i, x) =b_i ena£ba za H_i, kjer je x= (x₁, x₂, . . . , x_n), a_i = (a_i1, a_i2, . . . , a_in) vektor (normale hiperravnine) in vsakbi skalar, ki ga dobimo kot produkt normale ai

in neke to£ke (vektorja) na hiperravnini, z (a, b) pa ozna£imo skalarni produkt vektor- jev a in b v Rⁿ. Za vsak ije b_i 6= 0, saj H_i ne pokriva izhodi²£a. Denimo, da izrek ne velja, torej je m < n. Oglejmo si polinom

P(x) = (−1)^m+n

m

Y

j=1

b_j

n

Y

i=1

(x_i−1)−

m

Y

i=1

[(a_i, x)−b_i].

Polinom je o£itno stopnje n in koecient pri £lenu maksimalne stopnje Qn i=1x_i je enak(−1)^m+nQm

j=1bi 6= 0. Zato po izreku 4.2 obstaja to£ka x ∈ {0,1}ⁿ, da je P(x)6= 0. Ta to£ka ni izhodi²£e, saj je

P(0,0, . . . ,0) = (−1)^mb₁b₂· · ·b_m−(−1)^mb₁b₂· · ·b_m = 0.

Torej velja za neko drugo to£ko (s₁, s₂, . . . , s_n), da je P(s₁, s₂, . . . , s_n) = 0. To po- meni, da je levi del izraza enak ni£, saj je vsaj en x_i = 1, od tod sledi, da je tudi levi del enak ni£. Torej je (a_i, x)−b_i = 0, kar pa pomeni, da ta to£ka leºi na hiperravnini, torej smo pri²li do protislovja.

14

5.3 Chevalley-Warningov izrek

Naslednji izrek je kot domnevo postavil Artin leta 1934, imenuje pa se po Chevalleyu in Warningu, ki sta vsak svojo verzijo dokazala naslednjega leta. Dokaz, ki ga bomo predstavili v tem razdelku, temelji na kombinatori£nem izreku o ni£lah.

Izrek 5.3 (Chevalley - Warning). Naj bo p pra²tevilo in P₁ =P₁(x₁, x₂, . . . , x_n), P₂ = P2(x1, x2, . . . , xn), . . . , Pm =Pm(x1, x2, . . . , xn) polinomi nad Z^p. ƒe je n >Pm

i=1deg(Pi) in (c₁, c₂, . . . , c_n) skupna ni£la polinomov P_i, potem imajo polinomi ²e eno skupno ni-

£lo.

’e preden se posvetimo dokazu, si bomo pogledali naslednji zgled. Izrek nam sicer ne pove, kako za izpolnjene predpostavke ni£lo poiskati, zagotovi nam le njen obstoj.

Zgled 5.3. Naj bosta P₁(x, y, z) = x +y + 2z in P₂(x, y, z) = 2x + 2y+z poli- noma s koecienti iz Z3. V danem primeru imamo polinoma treh spremenljivk, torej je n = 3, ki sta oba prve stopnje, torej je deg(P₁) + deg(P₂) = 2, kar je manj od 3. O£itno imata polinoma skupno ni£lo (0,0,0), torej so pogoji izreka izpolnjeni in vemo, da imata polinoma ²e eno skupno ni£lo. Bralec se brez teºav lahko prepri£a, da je to (1,2,0). Vpra²amo se lahko, ali sta to edini skupni ni£li za ta polinoma. Odgovor je ne, tudi (2,1,0) je ni£la obeh polinomov.

Sedaj si bomo pogledali ²e dokaz prej²njega izreka.

Dokaz. Denimo, da izrek ne velja, torej, da je za dane predpostavke (c₁, c₂, . . . , c_n) edina skupna ni£la polinomov P_i. Deniramo naslednji polinom

f =f(x₁, x₂, . . . , x_n) =

m

Y

i=1

(1−P_i(x₁, x₂, . . . , x_n)^p−1)−α

n

Y

j=1

Y

c∈Zp,c6=c_j

(x_j −c),

kjer je α dolo£en tako, da velja

f(c₁, c₂, . . . , c_n) = 0. (4)

S tem pogojem je α natanko dolo£en in neni£eln, saj je (c₁, c₂, . . . , c_n) skupna ni£la polinomov P_i od koder sledi, da je

m

Y

i=1

(1−P_i(c₁, c₂, . . . , c_n)^p−1) =

m

Y

i=1

(1−0^p−1) =

m

Y

i=1

1 = 1^m = 1, (5) in drugi del polinoma f

n

Y

j=1

Y

c∈Zp,c6=c_j

(c_j −c) = β 6= 0, (6)

15

saj je produkt kon£en in so vsic ∈ Zp v produktu razli£ni od c_j za vse 1 ≤ j ≤ n. Sedaj ena£be (4), (5) in (6) ena£imo in dobimo

0 = 1−αβ ⇒α= 1 β. Opazimo, da je

f(s₁, s₂, . . . , s_n) = 0za vses_i ∈Zp. (7) Res je tako v primeru, da je (s₁, s₂, . . . , s_n) = (c₁, c₂, . . . , c_n), saj to sledi iz (4). V primeru, ko je(s₁, s₂, . . . , s_n) 6= (c₁, c₂, . . . , c_n), pa po predpostavki obstaja polinom P_j, katerega(s₁, s₂, . . . , s_n)ni ni£la. Torej je (P_j(s₁, s₂, . . . , s_n))^p−1 = 1po Malem Fermatovem izreku in je zato

1−P_j(s₁, s₂, . . . , s_n)^p−1 = 0. (8) Za uporabo Malega Fermatovega izreka smo upo²tevali, da so vsi neni£elni elementi Z^p tuji pra²tevilu p. Ker (s1, s2, . . . , sn) ni enak (c1, c2, . . . , cn), obstaja vsaj en i, da je s_i 6=c_i. Torej bo vsaj en x_i =s_i in prav tako c=s_i. Vsaj en £len produkta je torej ni£, od koder sledi

n

Y

j=1

Y

c∈Zp,c6=cj

(x_j−c) = 0. (9)

Po (8) in (9) res sledi (7). Deniramo t_i = p−1 za vse i. Zanima nas koecient pred

£lenom, ki dolo£a stopnjo polinoma f, torej koecient pri Qn

i=1x^t_iⁱ. Prvi £len v f je

m

Y

i=1

(1−Pi(x1, x2, . . . , xn)^p−1), (10) ki je stopnje (p−1)Pm

i=1deg(P_i), kar je po predpostavki manj od (p−1)n. Drugi £len v f je

−α

n

Y

j=1

Y

c∈Zp,c6=cj

(x_j −c), (11)

ki pa je stopnje natanko (p−1)n. To velja, saj je x_j−jev natanko n, za ksen x_j pa je c−jev iz Zp, ki so razli£ni od c_j natanko p−1, torej je £lenov v (11) (p−1)n. Stopnja pri (11) je ve£ja kot stopnja pri (10), zato je koecient pri £lenu Qn

i=1x^t_iⁱ v (11) in po- sledi£no vf enak−α 6= 0. Zato po izreku 4.2 zaSi = Z^p za vse i obstajajo elementi s₁, s₂, . . . , s_n ∈ Zp, da je f(s₁, s₂, . . . , s_n) 6= 0, kar je v protislovju s (7) in s tem je dokaz zaklju£en.

16

5.4 Cauchy-Davenportov izrek

Najpomembnej²i izrek v tem poglavju se imenuje po francoskem matematiku Cau- chyju in angle²kem matematiku Davenportu. Prvi je ta izrek dokazal leta 1813 in ga uporabil pri novem dokazu Lagrangeve leme v njegovi znani objavi iz leta 1770, kjer je pokazal, da se vsako celo ²tevilo lahko zapi²e kot vsoto ²tirih kvadratov. V tem razdelku pa ga bomo predstavili kot posledico kombinatori£nega izreka o ni£lah. ’e prej si bomo ogledali naslednjo pomoºno trditev, ki jo bomo prav tako potrebovail.

Lema 5.4. Naj bo p pra²tevilo in A, B neprazni podmnoºici Z^p. ƒe je |A|+|B| > p, potem je A+B =Zp, kjer je A+B ={(a+b)(mod p) :a ∈A, b∈B}.

Preden se lotimo dokaza, si poglejmo ²e ustrezen zgled.

Zgled 5.4. Naj bosta A = {0,1,2} in B = {2,3,4} podmnoºici Z5. Za podmnoºici A = {0,1,2} in B = {2,3,4} v Z5 velja pogoj izreka |A| +|B| > 5 in tudi sklep A+B ={0,1,2,3,4}.

Poudarimo, da je pogoj leme zadosten, a ni potreben. Lahko se nam zgodi, da za vsoto mo£i podmnoºic manj oziroma kar p za nujno vsoto vseeno dobimo celotnoZ^p. To se zgodi, ko na primer vzamemo podmnoºici A={1,2} inB ={1,3,4} v Z5. Dokaz. ƒe je |A|+|B| > p, potem je za vsakg ∈ Zp presek mnoºic A ing −B = {g−b:b ∈B, g ∈Z^p}prazen.

Denimo, da to ne velja, torej zag ∈ Z^p je A∩ (g − B) = ∅. ƒe je presek mnoºic prazen, je mo£ unije enaka vsoti mo£i posameznih mnoºic. Torej je |A∪(g −B)| =

|A|+|g −B|. Ker je g −B = {g −b : b ∈ B}je mo£ |g −B| enaka |B|. Od tod sledi |A∪(g −B)|= |A|+|g−B|= |A|+|B|, kar je po predpostavki ve£ od p, mo£

|A∪(g−B)| pa je najve£p in tako smo pri²li do protislovja.

Sedaj ºelimo pokazati, da jeA+B =Z^p. Vemo, da jeA∩(g_i−B)6=∅ za vsak element gi ∈ Z^p, takih elementov je natanko p. Za vsak gi ∈ Z^p zaradi A ∩(gi −B) = ∅ velja, da obstajata a_i ∈ A in b_i ∈ B taka, da je a_i = g_i − b_i oziroma a_i +b_i = g_i. Imamo S

1≤i≤p{a_i +b_i} = S

i{g_i}, S

i{a_i +b_i} ⊂ A+B in S

i{g_i} = Zp in zato je Zp = S

i{g_i} = S

1≤i≤p{a_i +b_i} ⊂ A+B. Zaradi p = |Zp| in iz Zp ⊆ A+B sledi

|Zp| ≤ |A+B|, dobimo p≤ |A+B|, torej je |A+B|=p in velja A+B =Zp. Izrek 5.5 (Cauchy - Davenport). Naj bo p pra²tevilo in A, B neprazni podmnoºici Z^p. Potem je |A+B| ≥min{p,|A|+|B| −1}.

17

Izrek nam oceni velikost vsote dveh podmnoºic cikli£ne grupe pra²tevilskega reda.

Preden pa se lotimo dokaza, si poglejmo ²e naslednji zgled.

Zgled 5.5. Naj bosta A ={0,1} in B ={1,3} podmnoºici Z7. Mnoºici sta neprazni, vsaka je mo£i 2. Ker je tudi 7 pra²tevilo, so predpostavke izreka izpolnjene. Oglejmo si njuno vsoto A +B = {0 + 1,0 + 3,1 + 1,1 + 3} = {1,2,3,4}, ki premore 4 elemente. Po izreku mora biti mo£ vsote ve£ja ali enaka min{7,2 + 2−1} = 3, kar drºi. Bralec lahko opazi, da je vsota mo£i mnoºic A, B manj²a od mo£i mnoºice Z7, enaka pa je mo£i njune vsote, kar nikakor ne velja v splo²nem. Na primer, ko je ena izmed mnoºic kar mnoºica {0}, bo o£itno mo£ vsote enaka mo£i druge mnoºice.

Sedaj se posvetimo ²e dokazu izreka.

Dokaz. ƒe je |A|+|B|> p, je sklep neposredna posledica leme 5.4. Ker je |A|+|B|>

p, sledi da je |A|+|B| −1≥p, minimum min{p,|A|+|B| −1} je enakp, torej izrek v tem primeru velja.

Poglejmo ²e primer, ko je |A|+|B| ≤ p. Denimo, da izrek ne velja, torej da je |A+ B|<min{p,|A|+|B| −1}. Potem je |A+B|< p in|A+B|<|A|+|B| −1. Da prvi pogoj ne velja, se zgodi le v primeru, ko jeA+B =Zp, zato se osredoto£imo zgolj na drugi pogoj. ƒe je |A+B|<|A|+|B| −1, potem je |A+B| ≤ |A|+|B| −2. Naj bo C ⊆ Zp podmnoºica, za katero veljaA+B ⊆ C in|C| = |A|+|B| −2. Deniramo polinom f(x, y) =Q

c∈C(x+y−c) in opazimo, da je

f(a, b) = 0za vsea∈Ainb ∈B (12)

po denicijiC. Naj bo t₁ = |A| −1 int₂ = |B| −1. Koecient pri £lenu x^t1y^t2 v f je binomski koecient ^|A|+|B|−2_|A|−1

6= 0, saj je|A|+|B| −2 < p. Zato po izreku 4.2 za n = 2, S₁ =A in S₂ =B obstajata elementa a ∈A in b ∈B, da je f(a, b)6= 0, kar pa je v protislovju z (12) in s tem je dokaz zaklju£en.

5.5 Omejene vsote

S pojmom omejene vsote opisujemo mnoºico vsot elementov danih mnoºic, za katere veljajo dolo£ene omejitve. V tem podrazdelku si bomo ogledali nekaj izrekov, ki ome- njajo kak²no tako vsoto in opi²ejo neko spodnjo mejo za njeno mo£.

Naslednji izrek je znan rezultat in je bil prvi£ dokazan v [6].

18

Izrek 5.6. Naj bo p pra²tevilo, h = h(x₀, x₁, . . . , x_k) polinom nad poljem Zp, naj bodo A₀, A₁, . . . , A_k neprazne podmnoºice Zp mo£i |A_i| = c_i + 1 in deniramo m = Pk

i=0c_i − deg(h). ƒe je koecient pri £lenu Qk

i=0x^c_iⁱ v polinomu (x₀ + x₁ + . . .+ x_k)^mh(x₀, x₁, . . . , x_k) neni£eln v Zp, potem je | ⊕_hPk

i=0A_i| ≥m+ 1, kjer je

⊕_h

k

X

i=0

A_i ={a₀+a₁+. . .+a_k:a_i ∈A_i, h(a₀, a₁, . . . , a_k)6= 0}.

Dokaz. Denimo, da izrek ne velja, torej da je pri danih predpostavkah | ⊕_hPk

i=0A_i|<

m+ 1. Naj boE (multi-) mnoºica m elementov iz Zp, ki vsebuje ⊕_hPk

i=0A_i. De- niramo naslednji polinom Q(x₀, x₁, . . . , x_k) = Q

e∈E(x₀ +. . .+x_k−e). Opazimo, da je

Q(x₀, x₁, . . . , x_k) = 0za vse(x₀, x₁, . . . , x_k)∈A₁×A₂×. . .×A_k. (13) To velja, ker je bodisi (x₀, x₁, . . . , x_k) ni£la polinomah, bodisi je (x₀+x₁+. . .+x_k)∈

⊕_hPk

i=0A_i ⊂ E in je zatoQ

e∈E(x₀ +. . .+x_k − e) = 0. Stopnja polinoma Q je deg(Q) = deg(h)+m=Pk

i=0ci, saj je|E|=m, torej je v produktu natanko m £lenov.

Koecient pri x^c₀⁰x^c₁¹· · ·x^c_k^k v polinomu Q in v (x₀+x₁ +. . .+x_k)^mh(x₀, x₁, . . . , x_k) je enak in po predpostavki neni£eln. Po izreku 4.2 obstajajo elementi x₀ ∈ A₀, x₁ ∈ A₁, . . . , x_k ∈ A_k, da je Q(x₀, x₁, . . . , x_k) 6= 0, kar pa je v protislovju z (13) in je izrek s tem dokazan.

Naslednji izrek izbolj²a spodnjo mejo iz Izreka Cauchyja in Davenporta.

Izrek 5.7. Naj bo p pra²tevilo in A, B neprazni podmnoºici Z^p. Potem velja

|{a+b:a ∈A, b∈B, ab6= 1}| ≥min{p,|A|+|B| −3}.

Dokaz bo sledil v nadaljevanju, ²e prej bralca opozorimo, da je dodatna zahteva tega izreka, da ne se²tevamo inverznih elementov za mnoºenje.

Zgled 5.6. Naj bosta A ={0,1} in B ={1,3} podmnoºici Z7. Obe mnoºica sta mo£i 2, torej neprazni, in 7 je pra²tevilo. Predpostavke izreka so torej izpolnjene. Oglejmo si mnoºico vsot iz izreka, v njej bodo vse kombinacije po enega elementa iz prve in enega iz druge mnoºice razen kombinacije obeh 1, saj je 1·1 = 1. Dobimo naslednjo mnoºico {1,3,4}, ki je mo£i 3. Minimum ²tevil 7 in 2 + 2−3 je o£itno 1, kar je manj od 3.

Dokaz. Uporabiti ºelimo izrek 5.6. Za k = 1 potrebujemo dve neprazni podmnoºici Zp, kar je po predpostavki izreka dano, in polinom dveh spremenljivk. Naj bo torej

19

A₀ =A inA₁ =B, torej je c₀ =|A| −1 inc₁ =|B| −1, in naj bo h(x₀, x₁) = x₀x₁−1 polinom stopnje 2. Opazimo, da je vsota

⊕_h

1

X

i=0

A_i ={a+b :a ∈A, b∈B, h(a, b)6= 0}={a+b :a ∈A, b∈B, ab6= 0},

kar je natanko mnoºica iz predpostavke izreka. V danem primeru je m=|A|+|B| −4, v kar se ni teºko prepri£ati. Sedaj si pogledamo polinom(x₀ + x₁)^m(x₀x₁ − 1) = (x0+x1)^|A|+|B|−4(x0x1 −1), koecient pri £lenu x^c₀⁰x^c₁¹ =x^|A|−1₀ x^|B|−1₁ v njem je o£itno neni£eln, zato so pogoji izreka 5.6 izpolnjeni in velja

|{a+b :a ∈A, b∈B, ab6= 0}| ≥ |A|+|B| −4 + 1 =|A|+|B| −3.

Pokazali smo ºeljeno.

Naslednjo lemo bomo navedli brez dokaza, saj jo bomo potrebovali pri dokazu nasle- dnjega izreka. Zainteresirani bralec si njen dokaz lahko ogleda v objavi pod [6] iz leta 1996, katere eden izmed treh avtorjev je prav tako Noga Alon.

Lema 5.8. Naj bodo c₀, c₁, . . . , c_k ∈N0 in Pk

i=0c_i =m+ ^k+1₂

, kjer je m∈N0. Potem je koecient pri Qk

i=0x^c_iⁱ v polinomu (x₀ +x₁ +. . .+x_k)^mQ

k≥i>j≥0(x_i − x_j) enak

m!

c0!c1!···c_k!

Q

k≥i>j≥0(c_i−c_j).

Da si nekoliko poenostavimo zapis vpeljemo naslednjo oznako.

Denicija 5.1. Naj bo p pra²tevilo in A0, A1, . . . , Ak neprazne podmnoºice cikli£ne grupe Zp. Deniramo naslednjo vsoto

⊕^k_i=0A_i ={a₀+a₁+. . .+a_k:a_i ∈A_i, a_i 6=a_j za vsei6=j}.

Trditev 5.9. Naj bo p pra²tevilo in A₀, A₁, . . . , A_k neprazne podmnoºice grupe Zp. ƒe je |A_i| 6=|A_j| za vse 0≤i < j ≤k in je Pk

i=0A_i ≤p+ ^k+2₂

−1, potem je

| ⊕^k_i=0A_i| ≥

k

X

i=0

|A_i| −

k+ 2 2

+ 1.

Dokaz. Dane mnoºiceA0, A1, . . . , Ak ⊆ Z^p so po predpostavki neprazne in razli£nih mo£i, torej |A_i| 6=|A_j| za vse i6=j. Naj bo |A_i|=c_i+ 1 za vse i, potem o£itno velja

c_i < pza vsei. (14)

20

Naj bo

m =

k

X

i=0

c_i−

k+ 1 2

. (15)

Iz (15) sledi, da je m=

k

X

i=0

(|A_i| −1)−

k+ 1 2

=

k

X

i=0

|A_i| −(k+ 1)−

k+ 1 2

=

k

X

i=0

|A_i| −

k+ 2 2

,

ko upo²tevamo ²e predpostavko, da je Pk

i=0|A_i| ≤p+ ^k+2₂

−1 dobimo m=Pk

i=0|A_i| − ^k+2₂

≤p+ ^k+2₂

−1− ^k+2₂

=p−1, torej je

m < p. (16)

Deniramo polinom h(x₀, x₁, . . . , x_k) = Q

k≥i>j≥0(x_i −x_j). V tem produktu jek!

faktorjev, zato je stopnja polinomah kar deg(h) =

k

X

i=0

i= 1

2k(k+ 1) =

k+ 1 2

. (17)

Opazimo tudi, da je za dani polinom vsota ⊕^k_i=0A_i enaka vsoti ⊕_hPk

i=0A_i. Zaradi (15) po lemi 5.8 sledi, da je koecient pri £lenu Qk

i=0x^c_iⁱ v polinomu (x₀ +x₁ +. . .+ x_k)h(x₀, x₁, . . . , x_k) enak _c0!c^m!_1!···ck!Q

k≥i>j≥0(c_i −c_j). Koecient je razli£en od ni£, saj velja (14),c₀, c₁, . . . , c_k so paroma razli£na ²tevila in (16).

Ker je m = Pk

i=0ci − ^k+1₂

in (17), sledi m = Pk

i=0ci − deg(h), zato po izreku 5.6 velja | ⊕_h Pk

i=0A_i| ≥ m+ 1. Ker za polinom h velja⊕_hPk

i=0A_i = ⊕^k_i=0A_i in m=Pk

i=0|A_i| − ^k+2₂ sledi

| ⊕^k_i=0A_i|=| ⊕_h

k

X

i=0

A_i| ≥

k

X

i=0

|A_i| −

k+ 2 2

+ 1.

S tem je dokaz zaklju£en.

5.6 Dokaz domneve Erdös-Heilbronn

Alon je s pomo£jo posledice uspel dokazati 30 let staro domnevo Erdösa in Heilbronna.

Kot prvi pa je leta 1994 potrdil domnevo Dias Da Silva.

Izrek 5.10 (Domneva Erdös-Heilbronna). Naj bo p pra²tevilo in A neprazna podmno- ºica Zp. Potem je

|{a+a⁰ :a, a⁰ ∈A, a6=a⁰}| ≥min{p,2|A| −3}.

21

Pri dokazu si bomo pomagali s prej²njo trditvijo.

Dokaz. Naj bok = 1, A₀ = A inA₁ = A\{a}, kjer jea ∈ A poljuben. Ker je po predpostavkiA ⊆ Z^p, je A\{a} ⊂ Z^p. O£itno velja|A0| = |A| 6= |A1| = |A\{a}| =

|A| −1. ƒe velja|A₀|+|A₁| = 2|A| −1 ≤ p+ ³₂

−1 = p+ 2, potem po trditvi 5.9 sledi |{a+a⁰ :a, a⁰ ∈A, a 6=a⁰}| ≥(2|A| −1)− ³₂

+ 1 = 2|A| −3.

22

6 Sklep

V diplomski nalogi smo spoznali kombinatori£ni izrek o ni£lah in ve£ zgledov njegove uporabe na primerih iz teorije grafov, geometrije in aditivne teorije ²tevil. še v izvir- nem £lanku [5] je Alon podal ²e veliko drugih primerov, ki jih nismo uspeli obravna- vati, med njimi denimo izrek Eliahouja in Kervaireja o mo£i vsote podmnoºic v vek- torskem prostoru nad kon£nim poljem ter takoimenovano permanentno lemo in nekaj njenih posledic o vektorjih v Zⁿp. Dokazal je tudi ve£ ve£inoma ºe znanih izrekov iz podro£ja teorije grafov. Eden tak²nih primerov je recimo rezultat Alona, Friedlanda in Kalaija o p−regularnih podgrah v grafu brez zank s povpre£no stopnjo 2p−2 in maksimalno stopnjo najve£ 2p−1. Drugi primeri so izreki o seznamskem kromati£nem

²tevilu, denimo izrek Alona in Tarsija, da je to ²tevilo najve£ 3 za vsak ravninski dvo- delen graf. Sem spada ²e izrek Fleischnerja in Stiebitza, ki pravi, da je za vsak graf s 3n vozli²£i, katerega mnoºica povezav je disjunktna unija Hamiltonskega cikla in n paroma po vozli²£ih disjunktnih trikotnikov, njegovo seznamsko kromati£no ²tevilo enako kromati£nemu ²tevilu, ki je enako3.

Raznovrstne rezultate z uporabo Alonovega izreka so nato dobili tudi drugi, denimo Hefetz[2], ki je ²tudiral antimagi£no ozna£evanje grafov, pa Shirazi in Verstraëte [3], ki sta ²tudirala obstoj podgrafov v grah z vozli²£i ozna£enimi s seznami slabih ²tevil in podobno.

Nekateri avtorji so formulirali druga£ne razli£ice Alonovega izreka, denimo Lasonov kvantitativni nullstellensatz, ki podaja tudi formulo za izra£un koecienta pri £lenu maksimalne stopnje. S temi orodji so bili dokazani ²e ²tevilni drugi novi rezultati, glej na primer [9].

Zdi se, da je na tem podro£ju ²e veliko moºnosti za nova odkritja.

23