Gode rank 1 latticereglar av høg dimensjon

Masteroppgåve iAnvendtog Rekneorientert matematikk

Vegard Topphol

Matematisk institutt

UniversitetetiBergen

1. juni2011

Denne masteroppgåva vart gjennomført og skriven ved matematisk institutt, avdeling

for anvendt og rekneorientert matematikk 2010 til 2011. Denomhandlar numeriske in-

tegrasjonsreglarforintegrering overmangedimensjonar,og særskildlatticereglaravgitt

trigonometrisk grad. Ein god del av arbeidet her er dedikert særskild til utvikling og

testing av algoritmer for å nne gode rank 1 latticereglar avutvida grad

δ = 5

^{for høg}

dimensjon.

Fyrst vil eg takke vegleiar Tor Sørevik for å føreslå temaet for masteroppgåva, som

dethar vorebådeinteressant ogutfordrandeåarbeide med.Takk ogsåfor samtalar,råd

om oppgåva og svar på spørsmål når eg stod fast, og for at du stilte alle dei spørsmåla

somgjordeat eg sjølvmåtte tenkje godt gjennomdetaljane iarbeidet.

Vidare vil eg takke alle medstudentane på matematisk institutt for avbrekk frå ar-

beidet og selskap i kaepausane. Takk for eit godt og sosialt arbeidsmiljø og for at de

viserat detframleis nnastlivderute.

Til slutt vil eg takke mine kjære foreldre Kjersti og ArneKåre Topphol for alltid å

vere derfor meg og for å vise interesse i oppgåva eg har skrive. Takk for at akkurat de

ermine foreldre.

1 Innleiing 1

1.1 Integrering imangedimensjonar . . . 1

2 Introduksjon til latticereglar 3 2.1 Lattice . . . 3

2.2 Latticereglar . . . 4

2.3 Trigonometrisk grad . . . 5

2.4 Tilnærmingsfeilfor latticereglar . . . 6

2.5 Ekvivalens mellom latticereglar . . . 8

3 Konstruksjon av gode latticereglar 11 3.1 Gode latticereglar. . . 11

3.2 Utrekning avtrigonometrisk grad . . . 11

3.3 Deltasekvensar . . . 12

3.4 Krav fordeltasekvensar . . . 14

3.5 Golomblinjalar og kopling tildeltasekvensar . . . 16

4 Algoritmer ogkompleksitet 19 4.1 Algoritmer. . . 19

4.2 Utrekning avtrigonometrisk grad . . . 19

4.3 Algoritmerfor konstruksjon avdeltasekvensar . . . 22

4.4 Algoritmefor søk etter latticeregel . . . 25

4.5 Kompleksitet . . . 27

5 Eksperimentelle resultat 30 5.1 Resultat . . . 30

5.2 Diskusjon . . . 35

6 Konklusjon 39

1 Grenser for

N

^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36}

2 Testkøyretid for

O(s ⁹ )

^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37}

3 Testkøyretid for

O(s ⁷ )

^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38}

Tabellar

1 Tabell overlatticereglar . . . 31

2 Fordelingavgode latticereglar. . . 37

1.1 Integrering i mange dimensjonar

Innanfor eireulikefagfelt,mellom anna statistiskmekanikk,atomfysikk, nansmatem-

atikk,og andre stader, har einbruk for å kunne integrere over mange dimensjonar.For

eit lågt tal på dimensjonar er dette relativt greit og krev ikkje for stor reknekraft. For

enkleintegralkanein tilog medgjeredetanalytisk utan altfor store problem.

Men det store eirtal av funksjonar er dessverre ikkje slik. Dei kan ha for mange

dimensjonar, og derfor vere for uoversiktlige til å kunne integrerast analytisk. I tillegg

kandeihasingularitetarellerverediskontinuerlege, deikanhahurtigeoscillasjonar,eller

generellt sett vere for komplekse til å kunne forståast analytisk. Ofte har ein også med

integrandar å gjere somerantenheiltellerdelvis ukjend. Integrasjonsområdet kanogså

vereaveinslikart,medomsynbådepå formog avgrensing,ateinikkjeharnokonenkel

måte åintegrere deipå. Idesse tilfellavert detkravdmeirspesialiserte integrasjonsme-

todar.

Det nnast allereie einheil delmetodar for numerisk integrasjon, der deieindimen-

sjonaleintegrasjonsreglanenaturlegnokerbestutforska.Viharhertointegrasjonsreglar

som er verdt å nemne her. Den fyrste av desse er Gaussisk kvadratur som integrerer

polynomiske funksjonar eksakt opp til gitt orden. Den andre som her peikar seg ut er

trapesregelen, somgir godevaluering av integral avperiodiske funksjonar. Ein naturleg

tankeeråutvidekonseptaviharieindimensjonalereglartilåogsågjeldeforeiredimen-

sjonar.Denenklaste måten å gjere dettepå erå nytte produktintegrasjonsreglar. Dette

gårheiltenkeltutpååredusereeits-dimensjonaltintegraltileitsettavseindimensjonale

integral. For få dimensjonar går dette heilt greit, og ein får brukbare resultat utan for

storekravtilutrekningskraft.Mennåreinkjemoppiikkjesåaltformangedimensjonar

vertdettesnarteinutilstrekkjelegstrategi.Med dimensjonanevekstalet påutrekningar

eksponensiellt,og allereiefor femdimensjonarvileinmedenkelproduktintegrasjonvere

heiltpå randa avdetsom erpraktiskmogleg.

Vi treng derfor meir sostikerte integrasjonsmetodar. Dei metodane vi har tilgjen-

gelege deler seg hovudsaklegi to kategoriar, der hovudproblemet ialle tilfelle reduserer

til å velje evalueringspunkt på smarte måtar så feilen blir så liten som mogleg, med så

få utrekningar som mogleg. Den fyrste av desse kategoriane er Monte Carlo metodane

[17 ],somgårut pååvelgeevalueringspunkt tilfeldigogtagjennomsnittetavdesse.Ire-

alitetenvildetvereeitsettavpsevdotilfeldige punkteinbrukar,ogintegrasjonsmetoden

kan aldri vere betre enn dei beste generatorane av psevdotilfeldige punkt. Ein utnyttar

at ved tilfeldig utveljing så vilein, omein har eit stort nok utval, nærmeseg den reelle

middelverdien,ogdermeddeneksakteevalueringaavintegralet.Fordelenmeddetteerat

detgårrelativtfortåfårelativtgoderesultat.Ulempener at detereintilfeldigprosess,

og einkanderfor aldri garanterefor gode resultat.

Eitalternativ tilMonteCarlometodane erdenstore gruppaavintegrasjonsmetodar

som passande nok vert kalla kvasi Monte Carlo metodar[19 ]. I motsetnad til Monte

Carlo metodane fungerer desse ved at ein vel sample punkt ut i frå system konstruert

spesiktfor åminske integrasjonsfeilen.Dessemetodaneeroftetilpassa enkeltegrupper

integranden kan derforeitgodt valav einkvasiMonteCarlometode verebetreenn rein

MonteCarlointegrering.Itillegg,iogmedat MonteCarlointegreringirealitetennyttar

psevdotilfeldigepunkt,vildeihaeinvissregularitetsomeinikkjealltidharkontrollover

eekten av. Ved å nytte kvasi Monte Carlo metodar kan ein seiast å ta kontroll ovevr

denne regulariteten oghelder utnytte den for høgarepresisjon.

Itilleggtildesse togrunnleggjandegruppeneavmetodarkandetvereverdtånemne

adaptive metoder[23 ]. Dette er meir måtar å implementere numerisk integrering enn

sjølvstendigeintegrasjonsmetodar,dereinsøkjeråforbetreresultata tileinavdeigrunn-

leggjande metodane, typisk ved å nytte feilestimat til å nne endå betre tilnærmingar.

Eitenkelteksempelpådettevilvereåtaendåeiresampleiproblemområdeforåkunne

jamneut feilen her.

Idenne oppgåvavileg konsentrere megomeinsærskildtype integrasjonsreglarkalla

latticereglar[16][23].Detteereinformforkvadraturreglar,ellerogsåkallakubaturreglar,

og dei kan sjåast på som ein generalisering av den eindimensjonale trapesregelen. Lat-

ticereglar er særskild eigna for ein-periodiske funksjonar, men med høve til å tilpas-

sastandre, ikkje-periodiskefunksjonar. Forenklare åhandtere denisjonarog konstruk-

sjonar av latticereglar vil integrasjonsområdet for alle latticereglane vi ser på vere den

s-dimensjonaleeiningskuba

C ^s

^{.Sidanvikanskalere eitkvart}rektangulært område tilei kube vildessekvadraturreglaneogsåkunne tilpassast slike integrasjonsområder.

Mitt mål med denne oppgåva er å studere eit sett av latticereglar konstruert på

ein spesiell måte ved hjelp av golomblinjalar. Vi vil utvikle algoritmer for å eektivt

kunnekonstruere rank-1latticereglar avgitt trigonometrisk gradmed lågastmoglegtal

på evalueringspunkt. Dette vil bli forklart seinare iteksten.Det har vist segat ein kan

forutsjå gradatillatticereglar konstruertved hjelpavgolomblinjalar. Dessealgoritmene

vileg sånytte for å nnelatticereglar avhøggrad og høg dimensjon.

Eg vil her presentere denisjonar og bakgrunnsteori om lattice og latticereglar som er

nødvendig for denne oppgåva. Ei gjennomgåande skildring av latticereglar kan nnast

hos Sloan og Joe [23 ], og meir kompakt hos Lyness [16]. Teorien bak latticereglar har

vore studert lenge, og kan seiast å ha starta med 'metoden for gode lattice punkt' hos

Korobov[12]ogHlawka[11 ],ogseinareogsåhosConroy[4].Eingeneralisertdenisjonav

latticereglar dukka fyrstopp hosFrolov [10] og gjenoppdaga og utvikla vidareavSloan

og Kachoyan [24 ][25 ] og av Sloan [22]. Min gjennomgong av bakgrunnsteorien vilstort

sett fylgje Sloanog Joe [23].

2.1 Lattice

Basisenforeinkvarlatticeregel,somogsåhargittdeinamnet,ereitlattice.Deterlatticet

som denerer korleis ein for ein spesik latticeregel vil velje integrasjonspunkta. For å

forstå latticereglanemåvi derfor denerekvaeit lattice er.Enkelt forklart ereit lattice

eitperiodiskgridavpunktieinellereiredimensjonar. Formeltsett kan videneredet

slik.

Denisjon 2.1 (Lattice). Eit

s

-dimensjonalt lattice

Λ

^{er ei diskret mengde}

{ x } ∈ R ^s

somerlukka underaddisjon ogsubtraksjon.

Vi kan umiddelbart ut i frå denne denisjonen nne nokon av eigenskapane til eit

lattice. For det fyrste ser vi at punktet

0 = (0, 0, . . . , 0)

^{altid er med i eitkvart lattice.}

Dette ser vi ut i frå at dersom

x ∈ Λ

^{må vi også ha at}

x − x ∈ Λ

^{. I tillegg er eitkvart}

punkt

y = kx

^der

k ∈ Z

^{også med i latticet. Latticet som består av alle punkt med}

heiltalskomponentar vert kalla einingslatticet og vi skrivdet som

Λ ^s ₀

^{. Eit minimalt sett}

av lineært uavhengige punkt

{ x i }

^{, der alle punkt i latticet}

Λ

^kan uttrykkjast som

y = P

i c _i x _i ; c _i ∈ Z

^vertkalla generatorarfor latticet.

Vidare, på grunn av additivitetskravet til latticepunkta, er alle lattice utanom

0

uavgrensa.

Til eitkvartlattice kandetdenerasteit dualtlattice.

Denisjon 2.2 (Dualtlattice). Eitkvartlattice

Λ

^{har eitdualt lattice}

Λ ^⊥

^{denert som}

settet

{ h ∈ R : h · x ∈ Z ∀ x ∈ Λ }

For einingslatticet får vi at detdualelatticet blir einingslatticet sjølv.

Ei spesiell gruppe av lattice er kalla integrasjonslattice. Desse lattice er viktige i

samanhang medlatticereglar,og vikan deneredeisomlattice innehaldandeeiningslat-

ticet

Λ ₀

^.

Denisjon 2.3 (integrasjonslattice). Eit

s

-dimensjonalt integrasjonslattice

Λ

^{ereit lat-}

tice denertaveimengde

{ n i , z i : i = 1, . . . , t } ,

der

t

^og

n _i

^{erpositiveheiltal og}

z _i ∈ Z ^s

^,og

Λ ^s ₀ ∈ Λ

^.

Λ

^{inneheld alle punkt påforma}

p =

t

X

i=1

ν i z i

n _i

⁽¹⁾

der

ν i

^{ereitvilkårleg heiltal.}

Ein konsekvens av at

Λ ^s ₀

^{er element i} integrasjonslatticet er at alle element i det tilsvarande duale latticet er heiltalsvektorar. Sidan einkvar kanonisk einingsvektor

e _i ∈ Λ ^s ₀ ∈ Λ

^og

h ∈ Λ ^⊥

^{får vi at}

h · e i = h i

^{, somut ifrå denisjonenmå vereheiltal. Vidare}

vil vi også ha at integrasjonslatticet må vere 1-periodisk, og i tillegg vil alle punkt av

typen

p mod 1

^{liggande i}einingskuba vereelement ilatticet.

I resten av oppgåva vil alle lattice

Λ

^vere integrasjonslattice og

Λ ^⊥

^det tilsvarande dualelattice.

2.2 Latticereglar

Latticereglar ermedlemer avden store familien av numeriske integrasjonsmetodar som

vert kalla kvasi-Monte Carlo metodar, og den er spesielt eigna for å integrere kontin-

uerlege, periodiske integrandar. Standard integrasjonsområde er

C ^s

^,den

s

-dimensjonale einingskuba. Integralet vivilevaluere vert då

If = Z

C ^s

f dx.

⁽²⁾

Ein latticeregel kan denerast på eire ulike måtar, noko avhengig av korleis ein

denerer eitlattice.

Denisjon 2.4 (Latticeregel). Ein latticeregel ereinintegrasjonsregel på forma

Qf = 1 N

X

x _j ∈Λ∩[0,1) ^s

f (x _j )

⁽³⁾

der

Λ

^ereitintegrasjonslattice.

Alternativt, dersomeintek utgangspunkt ilikning (1), kaneinskrive dette som

Qf = 1

n ₁ n ₂ . . . n _t

n 1 −1

X

j 1 =0 n 2 −1

X

j 2 =0

· · ·

n t −1

X

j t =0

f (j ₁ z ¹

n ₁ + j ₂ z ²

n ₂ + · · · + j _t z ^t

n _t )

⁽⁴⁾

der

z i

^er

s

-dimensjonaleheiltalsvektorar,og

n _i

^og

t

^{erpositiveheiltal.Dersomalle}

n _i > 1

vertdettekallaeint-syklus form[26 ],oglatticet vertsagtå vereavrankt.Denneforma

ernyttigipraktiskbruk. Legg merketil atomintegranden er1-periodisk, trengviikkje

åkrevje at

x _j

^ligginnanfor einingskuba.

Idette arbeidetkonsentrereregmeg omreglar avrank1,og likning(4)reduserer til

Qf = 1 N

N−1

X

j=0

f (j z

N ).

⁽⁵⁾

Sidan(3)ogsåskalgjeldeforrank1reglar har viat alle

z _i

^der

z _i /N ∈ Λ ∩ [0, 1) ^s

^må

kunneskrivastsom

z _i = iz(

^mod

N ).

⁽⁶⁾

Vi ser ut i frå dette at talet på evalueringspunkt er nært knytt til storleikne på

N

^.

For denne oppgåva har vi i tillegg at alle latticereglane kan denerast ut i frå ein

z = (1, z 2 , . . . , z s )

^{, og vi vil derfor ha at for ein gitt}

N

^{vil alle} latticereglar ha nøyaktig

N

evalueringspunkt.

Umiddelbart vilein kanskje seieat ved å konsentrere seg omrank 1 latticereglarvil

einutelukke mange gode reglaravhøgare rank.Men ved søk har det vistseg at mange

av dei beste reglane er nettop rank 1 reglar, og for dei tilfella derein har høgare rank

beste reglarliggtilsvaranderank1reglarikkjelangtetter[27 ].Fordelen medrank1vert

då openbar ved at dei er mindre komplekse og dermed lettare både å nne fram til og

implementere.Ved åkonsentrere segomrank 1kanein reduseresøkjerometbetydeleg.

Sidan eit integrasjonslattice måvere1-periodisk, vildet duale latticet til einrank 1

regel vere

N

-periodisk,og detvilreduseretil

{ h ∈ Z ^s : h · z ≡ 0(

^mod

N ) } .

Dette kanvi sjåved åla

h ⁰ = h + cN e _i ∈ Λ ^⊥ ; 1 ≤ i ≤ s, c ∈ Z

der

e _i

^{ereinkanonisk}einingsvektor. Vifår då at

h ⁰ · x = h ₁ x ₁ + · · · + h _i x _i + cN x _i + . . . h _s x _s

= h · x + cN x _i .

På grunn av(1)får viat

cN x _i ∈ Z

^og

h ⁰ · x ∈ Z

^{,som førertil at}

Λ ^⊥

^er

N

-periodisk.

2.3 Trigonometrisk grad

Eg har allereienemnd at latticereglar erspesiellt tilpassa periodiske funksjonar, og det

erderfor naturlegåville framstille integranden som einsum avtrigonometriskemonom

i

s

dimensjonar,analogt medFourierrekkjerieindimensjon.

Denisjon 2.5 (Trigonometrisk monom). Eit

s

-dimensjonalt trigonometrisk monomer einfunksjon påforma

f (x) = e ^{2πi h · x}

⁽⁷⁾

der

h ∈ Z ^s

Eittrigonometriskpolynomvertdåeinlineærkombinasjonavtrigonometriskemonom.

Vikallarrometavalletrigonometriskepolynomi

s

dimensjonar

T ^s

^.Gradatileittrigonometrisk monomvert

d = || h || 1

^ogtileittrigonometriskpolynomvertdenlikgradatildetmonom- leddet medhøgastgrad. Rometavalletrigonometriske polynomi

s

dimensjonarog opp til grad

d

^vertkalla

T ^s _d

^.

Trigonometrisk grader eit slikt mål som nettop baserer seg på at ein kan tilnærme ein

funksjon medeitendeleg trigonometrisk polynom.

Denisjon 2.6 (Trigonometrisk gradfor integrasjonsreglar). Ein integrasjonsregel har

trigonometrisk grad

d(Q)

^dersom

Qf = If

^{for alle}

f ∈ T ^s _d

^{og det eksisterer minst ein}

g ∈ T ^s _d+1

^{slik at}

Qg 6 = Ig

^.

I ein del samanhangar har det vist seg nyttig å denere eit nytt mål, kalla utvida

trigonometrisk grad. Dette erdenert som

δ = d(Q) + 1

^{.Reint matematiskhar detlite}

åseie, meneindel relasjonarblir enklare ogryddigare omvi brukar dettemålet.

Slektskapentil eit anna mål,kalla algebraisk grad,eropenbar.

Denisjon 2.7 (Algebraiskgradfor integrasjonsreglar). Ein integrasjonsregel har alge-

braiskgrad

g(Q)

^dersom

Qf = If

^{for alle}

f ∈ X

j ₁ +···+j s ≤g

a _{j 1 ...j s} x ^j ₁ ^s . . . x ^j _s ^s

Herereiinnsiktfrå lågaredimensjonarnyttig.Allesomhar forsøktsegmedinterpo-

lasjon med algebraiske polynom veit at einfor høgare gradspolynom får store problem

med artifaktar irandområda. Dette erein eekt som ikkje vil forsvinne ved høgare di-

mensjonarogeinkanderfortenkjesegattrigonometriskgrad imangetilfelleerbetreog

meirpresist ennalgebraisk grad.

2.4 Tilnærmingsfeil for latticereglar

Motivasjonen for å nytte trigonometrisk grad nn vi i den underliggande teorien for

Fourieranalyse. Denseierat einkvar kontinuerleg og periodiskfunksjon i

s

dimensjonar kanuttrykkjastved hjelpaveinuendeleg sum avtrigonometriske monom.

f (x) = X

h ∈Z ^s

f ˆ (h)e ^{2πi h · x} .

⁽⁸⁾

Ved å nytte latticeregelen på denne likninga kan vi nne integrasjonsfeilen for lat-

ticeregelen. Resultatet vertdå som iteoremet under.

Teorem2.1(Tilnærmingsfeilforlatticereglar). La

Q

^{vere ein}

s

-dimensjonallatticeregel, og

Λ

tilhøyrande integrasjonslattice. Antavidare atfunksjonen

f

^{har absolutt konvergent}

Fourierrekkje. Dåhar vi at

Qf − If = X

h ∈Λ ^⊥ \{0}

f(h). ˆ

⁽⁹⁾

Herer

f(h) ˆ

fourierkoessienteni

h

^og

Λ ^⊥

^{erdetduale latticet til}

Λ

^.

Prov For å sjåat dette stemmer brukar vi likning (8) saman med denisjonen av

Λ ^⊥

^.

Vimåviseat

Q[e ^{2πi h · x} ] =

1

^for

h ∈ Λ ^⊥

0

^elles

For fyrstedelenavprovetserviatnår

h ∈ Λ ^⊥

^{harviutifrådenisjonenat}

h · x ∈ Z

^,

somgir ossvidareat

Q[e ^{2πi h · x} ] = 1

^.

For siste delen av dette provet må vi bruke at integranden er 1-periodisk. Vi kan

denere einoperator

T _j

^for 1-periodiske funksjonar.

T j f (x) = f (x + x _j ); x _j ∈ Λ ∩ [0, 1) ^s .

Vi får for eit gitt lattice eksakt

N

^ulike translasjonar tilsvarande latticepunkta i ein- ingskuba. Dette girvidareat

T _k T j f (x) = f(x + x _j + x _k ) = f (x + x _l )

der

x _l

^{er den unike vektoren i}

Λ

^og

[0, 1) ^s

^{som har ein avstandtil}

x _j + x _k

^{på ein heil-}

talsvektor. På grunn avdenne unikskapenfår vi dåsom resultatat

{ T _k T 0 , . . . , T _k T N−1 }

berre gir translasjonane ei ny rekkjefylgje. Gjennomsnittet av alle translasjonane

T _j f

vert

f ¯ = 1 N

N−1

X

i=0

T _j f

Vikanvidare sjåat

f ¯

^{erinvariant under}translasjonaneiog medat

T _k f ¯ = 1 N

N−1

X

j=0

T _k T _j f = 1 N

N −1

X

l=0

T _l f = ¯ f .

Vi denerer ein ny funksjon

g h (x) = e ^{2πi h · x}

^med

h ∈ Z ^s

^,

x ∈ R ^s

^{. Ved å nytte}

translasjonenpå denne får viat

T _k g h = e ^{2πi h · x k} g h .

Vi ser her at dersom

h ∈ / Λ ^⊥

^{, så må}

g h 6 = T _k g h

^{for ein eller annan}

0 ≤ k ≤ N − 1

^{. I}

tillegg har viat

¯ g ^h = 1

N

N−1

X

j=0

T j g ^h =



 1 N

X

j=0

e ^{2πi h · x j}



 g ^h .

Gjennomsnittet er invariant under transformasjonen

T _k

^{.Samstundes kan vi nne ein}

k

somgjerat

g ^h

^{ikkjeerinvariant underdensame} transformasjonen.Dette girossdermed at uttrykkjet iparentesen måverelik0.

Einkonsekvensavdettevertdå,somtidlegarenemnd,atlatticereglarpassarsærdeles

godt for funksjonar med raskt avtakande fourierkoesientar. Dette gjeld mellom anna

for funksjonarsom er1-periodiske.

Det naturlege neste steget vert då å nne ut korleis ein skal minske denne feilen.

Vi veit at når den 1-periodiske utvidinga av ein funksjon

f

^er

k

^gongar deriverbar, så vil fourierkoessientane ha ein konvergensrate

f ˆ (h) ∼ 1/h ^k

^{. Dersom utvidinga av}

periodiske, vil vi få at konvergensen bli

f ˆ (h) ∼ C ^−h ; | C | > 1

^{. I det}

s

-dimensjonale problemet får viat dersom

f

^er1-periodiskog deipartiellderiverte

∂ ^{q 1 +...q s} f

∂x ^q ₁ ¹ . . . ∂x ^q _s ^s , 0 ≤ q _k ≤ α, 1 ≤ k ≤ s

eksistererog erkontinuerlegepå

[0, 1) ^s

^er

f ˆ ∼ 1/(¯ h ₁ h ¯ ₂ . . . ¯ h _s ) ^α .

⁽¹⁰⁾

der

¯ h = max(1, | h | )

^{For uendeleg} deriverbare funksjonar i

s

dimensjonar får vi

f ˆ (h) ∼ C ₁ ^{−|h 1 |} C ₂ ^{−|h 2 |} . . . C s ^{−|h s |}

^.Dersom

C ₁ = C ₂ = · · · = C _s

^{får vi}

f ˆ (h) ∼ C ^{−|| h || 1} .

⁽¹¹⁾

Ut ifrå dette kan vi sjåat dei mest signikante koesientane høyrer til

|| h || 1 < d

^{. På}

grunn av (10)kanvi skrivefeilestimatet som

Qf − If = c X

h ∈Λ ^⊥ \{0}

1 (¯ h 1 ¯ h 2 . . . ¯ h s ) ^α .

For integrasjonsreglar vert konsekvensen av teorem (2.1) og argumentasjonen over,

at integralet av(8)må blilik

0

^{for alle} heiltalsvektorar

h

^der

0 < || h || 1 ≤ d

^.

Q[1] = I[1] = 1

Q[exp(2πih · x)] = I[exp(2πih · x)] = 0 ∀ 0 < || h || 1 ≤ d

⁽¹²⁾

2.5 Ekvivalens mellom latticereglar

Når vi studerer latticereglar er det nyttig å merke seg visse likskapar mellom beslekta

latticereglar.Detteernokovikanutnytte forågjeresøketterlatticereglarmeireektive.

Særskildnyttigerdetåsjåetterlikskaparsomgjeratlatticereglarharliktrigonometrisk

grad. For denne oppgåva er det nyttig å denere ekvivalensklasser ut i frå to transfor-

masjonar.

Denisjon 2.8 (Ekvivalensklasse). To vektorar

z

^og

z ⁰

^dannar latticereglar i same ek- vivalensklassedersom

1)

z ⁰

^{erdanna ved} permutasjonavkomponentane i

z

2) og

\

^eller

z ⁰

^{erdanna av}

z

^{ved å erstatte}

z _i

^med

N − z _i

^.

Latticereglar som erbeslekta pådenne måten har nokre felles eigenskapar. Det vik-

tigastefor denne oppgåva erat deivilhasame trigonometrisk grad.

Teorem2.2. Dersom

z

^og

z ⁰

^{høyrertilsame}ekvivalensklasse,og

z

^dannareinlatticeregel av utvidagrad

δ

^{, så vilogså}

z ⁰

^{danne ein} latticeregel avutvida grad

δ

Prov Vi vil fyrst vise at

z

^og

z ⁰

^er ekvivalente med omsyn til trigonometrisk grad under permutasjon. Vi denerer ein operator

P _i,j (z) = z ⁰

^der komponentane

z _i

^og

z _j

har byt plass.

P _i,j

^{ermatrisen somavvikfrå} identitetsmatrisen

I

^{,ved at} komponentane

(i, i) = (j, j) = 0

^,medan

(i, j) = (j, i) = 1

^{, ogvi har itillegg}

P _ij = P _ij ⁻¹ = P _ji

^og

P _ij (z)

erinvertibel. Viantarat deteksistererein

h ∈ Z ^s

^{slik at}

(h · z) mod N = 0,

= (h 1 z 1 + · · · + h i z i + · · · + h j z j + · · · + h s z s ) mod N.

⁽¹³⁾

For

z ⁰

^{får vidå vidaredersom}

h ⁰ = P _i,j (h)

^,at

(z ⁰ · h ⁰ ) mod N

= (h ₁ z ₁ + · · · + h _j z _j + · · · + h _i z _i + · · · + h _s z _s ) mod N = 0.

Sidan

P

^{er invertibel vil kvar}

h

^{ha, for gitte}

0 < { i, j } ≤ s

^{, ein unik}

h ⁰ = P _i,j (h)

^{, og}

fordi

P

^ereinreinpermutasjon av komponentanevil

|| h ⁰ || 1 = || h || 1

^.Dersom

z

^genererer

eit lattice av utvida grad

δ

^{har vi ein}

h

^der

|| h || 1 = δ

^{som gir (13). Dette fører til at}

latticet generertav

z ⁰

^{ogsåhar utvidagrad}

δ

^.

Vi gårvidaretil å viseat ved å erstatte

z i

^med

N − z i

^{vilvi ogsåfå to} latticereglar avlikgrad.Vilet

z = (z ₁ , . . . , z _i , . . . , z _s )

^og

z ⁰ = (z ₁ , . . . , N − z _i , . . . , z _s )

^{.Viantarvidare,}

somover, at vifor ein

h ∈ Z

^{har at}

(h · z) mod N

= (z 1 h 1 , . . . , z i h i , . . . , z s h s ) mod N = 0.

⁽¹⁴⁾

Vikanvidare setje

h ⁰ = (h ₁ , . . . , − h _i , . . . , h _s )

^{,og pågrunn av(14)får vi}

(h ⁰ · z ⁰ ) mod N

= [z ₁ h ₁ , . . . , (N − z _i )( − h), . . . , z _s h _s ] mod N

= [(z ₁ h ₁ ) + · · · − (N h _i ) + (z _i h _i ) + · · · + (z _s h _s )] mod N = 0.

Ved same argumentasjon som overfår vi då at dersom

z

^{genererer eit lattice avutvida}

grad

δ

^vilogså

z ⁰

^{generereeitlattice avutvidagrad}

δ

^.

Nokre medlemmer i desse ekvivalensklassene er i ulike samanhangar nyttigare enn

andre[28 ].

Teorem 2.3. Einkvar ekvivalensklasse av rank 1 latticereglar inneheld ein representant

som tilfredsstiller

0 < z ₁ < z ₂ < · · · < z _s < N/2,

og einrepresentant som tilfredsstiller

N/2 < z 1 < z 2 < · · · < z s < N.

Prov For ein vilkårleg

z

^der

z/N ∈ Λ

^vil

(z(

^mod

N ))/N ∈ Λ

^{. Dette gir oss at alle}

z _i < N

^{. Ved å nytte} transformasjonane i denisjon 2.8 kan vi vise begge påstandane i teoremet.Vi permuterer komponentane i

z

^{og får}

z ₁ < z ₂ < · · · < z _s

^.Dersom

z _i > N/2

for eineller annan

0 < i ≤ s

^{let vi}

z _i ⁰ = N − z _i < N/2

^{.Elleskan vi setje}

z _i ⁰ = z _i

^.Vihar

meddetein

z ⁰

^{ekvivalent med}

z

^der

0 < z ₁ < z ₂ < · · · < z _s < N/2

^.

Sidanalle

0 < z _i ⁰ < N/2

^{kanviigjenvidaresetje}

z _i ⁰⁰ = N − z _i ⁰

^{ogfår ein}

z ⁰⁰

^ekvivalent

med

z ⁰

^og

z

^der

N/2 < z ₁ < z ₂ < · · · < z _s < N

^.

3.1 Gode latticereglar

Måletmed denneoppgåva ersomnemndå søkjeetter gode latticereglar. Menfor åvite

kva somergode latticereglarmåeg presiserekvaeinoptimal latticeregel er.

Denisjon3.1(Optimallatticeregelavgrad

d

^ogdimensjon

s

^{). Einoptimal}latticeregel av grad

d

ⁱ

s

dimensjonar er ein latticeregel som tilfredsstiller

min N (Λ)

^{for alle}

Λ

^slik

at

d(Λ) = d

^.

Dersomintegrandeneruendelegderiverbarvildetverefornuftig,utifrå(11),åbruke

1-normentil

h

^somkvalitetsmål,derein vilmaksimere storleiken

δ(Q) = min

h ∈Λ ^⊥ /{0} ( || h || 1 )

for at

C ^{−| h | 1}

^{skal bli så liten som mogleg. I denne oppgåva har vi valt å anta at at}

integrandenerglattog 1-periodisk,vildetderforverenaturleg åbruke dettemålet,som

tilsvarar trigonometrisk gradnemndtidlegare.

Basertpådessekriteriannastdeteireulikeangrepsvinklarnåreinvilleiteetterog

konstrueregodelatticereglar.Omeinkonsentrerersegomrank1reglarharviihovudsak

tre måtar. Denfyrste gårpå at einkan la

N

^{vere konstant og såvariere}

z

^{vektoren for}

å nne den latticeregelen somav desse har høgast grad. Alternativt kanein for ein gitt

z

^variere

N

^{for å} optimalisere grada. Begge desse framgongsmåtane har sine fordelar.

For begge gjeld det at ein må ha ein eektiv måte å rekne ut trigonometrisk grad på.

Den fyrste metoden har den fordelen at ein alltid kan nne reglar med eit lågt tal på

evalueringspunkt. Ulempa er at dersom ein vil ha høg grad kan det krevje at ein må

auke

N

^{, og} optimaliseringsproblemet vert då eit grensesetjingsproblem. Fordelen med den siste metoden er at når ein fyrst har funne ein god

z

^{kan ein enkelt auke}

N

^fram

til einhar ynska grad. Problemet her vert då å nne reglar for korleis

z

^{skalsjå ut for}

å garantere gitt grad. Den tredje måten vil vere å fastsetje grad først, for så å variere

både

z

^og

N

^.Denneframgongsmåten kompenserertil eiviss gradfor problemameddei to andremetodane,menhan vilisi reinasteformrisikereåkunne krevjeeitnoksåstort

søkjeområde. Eg vili denne oppgåva konsentrere megom den siste metoden, men for å

unngå alt for store søk vil eg konstruere alle

z

^{ut ifrå gitte reglar skildraunder. Desse}

konstruksjonanevilogså ginaturlegeavgrensingarfor søkjeområdet til

N

^.

3.2 Utrekning av trigonometrisk grad

Motivertavuttrykketilikningane(12)kaneinnneeinmetodeforårekneuttrigonometrisk

gradeektivt. Argumentasjonen her ereiforenkling avden gitt avRonald Cools [5 ] for

latticereglar av vilkårleg rank, og vil her gjelde berre for reglar av rank 1. Den fyrste

likninga

Q(1) = I(1) = 1

^{er triviellt} tilfredsstilt. Kvadraturet reduserer her til å ta

0 = Q(e ^{2πi h · x} ) = 1 N

N−1

X

j=0

exp(j 2πih · z

N )

m

0 =

N−1

X

j=0

exp(j 2πih · z

N )

Ein latticeregel hardå perdenisjon utvidagrad

δ

^dersom

∀ h : 0 < || h || 1 < δ, 0 =

N−1

X

j=0

exp(j 2πih · z

N )

som,ut ifrå Teorem 2.1og denisjonen2.2avdetdualelatticet

Λ ^T

^{,er ekvivalentmed}

∀ h : 0 < || h || 1 < δ, h · z mod N 6 = 0

⁽¹⁵⁾

Dersom ein varierer

h

systematisk ieit område for

|| h || 1 = δ ⁰ > 0

^for

δ ⁰

^{aukande og}

testarfor kraveti (15), nnein

δ = δ ⁰ − 1

^{fyrstestaden testen feilar. Algoritmen vilbli}

skildradetaljert i kapittelet om koding og implementering, og er basert på ei algoritme

gitt avRonald Cools[5].

3.3 Deltasekvensar

Alt eg har presentert no er standard sto for latticereglar og nnast i litteratur. For

å kunne gå vidare med å nne gode

z

^{vektorar treng vi noko meir teori. Teorien eg}

no vil presentere er tidlegare upublisert materiale frå eit sett av notat skrive av James

Lyness [28 ] [15 ]. Dessenotatane inneheld mellom anna nokre svært nyttige teorem som

ertil hjelpialgoritmer for konstruksjon avgode latticeregla,og fortel korleis

z

^måvere

oppbygd for ågenerere latticereglarav gitttrigonometrisk grad.

Vektorane

z

^{kansjåastpåsom}talfylgjer,ogut ifrå teorem2.2kaneinutanproblem sortere komponentane i stigande rekkjefylgje.Dette vil berre korrespondere til eirenu-

merering avdimensjonane og fører ikkjetil noko tap avgeneralitet. For ein latticeregel

medutvidagrad

δ

^{kan einviseat omvi krevat}

z = (z ₁ , . . . , z _i , . . . , z _s ); z _i = 1, 1 ≤ i ≤ s

⁽¹⁶⁾

må den kunne konstruerastut i frå ein deltasekvens. Vi kan også vise ut i frå dette at

for ein kvar

δ

^{må detnnast ein}latticeregel avutvidagrad

δ

^{generertut i frå ein}

z

^på

denne forma.

Denisjon 3.2 (Deltasekvens). Ein vektor

a = (a ₁ , . . . , a _σ ) ^T

^{vert kalla} deltasekvens dersom

0 < a ₁ < · · · < a _σ

⁽¹⁷⁾

|

σ

X

j=1

λ j a j | +

σ

X

j=1

| λ j | ≥ δ

^{for alle}

λ ∈ Z ^σ .

⁽¹⁸⁾

Dersomeinhar ein

λ

^{somgjer(18)tileinlikskapvert}

a

^{kallaeinstrikt}deltasekvens.

Vikan nokome medeit viktigteoremfor denne oppgåva.

Teorem3.1(Deltasekvens). Eitkvartrank1lattice

Λ

^avutvidagrad

δ

^generertav

z ∈ Z ^s

og

N

^{, der}

z = (z ₁ , . . . , z _i−1 , 1, z _i+1 , . . . , z _s ) ^T ; 1 ≤ i ≤ s

^{, må vere i same} ekvivalensklasse som eit lattice

Λ ⁰

^{generert av}

z ⁰

^og

N

^der

z ⁰

^{er danna av ein}deltasekvens av grad

δ

^.

Prov For ein

z ⁰ = (z ₁ ⁰ , . . . , z _i ⁰ , . . . , z _s ⁰ ) ^T

^der

z _i ⁰ = 1, 1 ≤ i ≤ s

^{kanvi fyrst, utifrå Teorem}

2.2 sorterealle elementa i

z ⁰

^istigande rekkjefylgje slik at

z = (1, z ₂ , . . . , z _s ) ^T

^{Dette gir}

ossat for einkvar

µ ∈ Z ^s

^vilalle

h

^påforma

h = [(N µ ₁ −

s

X

i=2

µ _i z _i ), µ ₂ , . . . , µ _s ] ^T

verepunkt i

Λ ^⊥

^{.Vikan ogsåskrive dette som}

h = [(N µ ₁ +

s

X

i=2

µ _i z _i ), − µ ₂ , . . . , − µ _s ] ^T .

⁽¹⁹⁾

Ut i frå dette fyl det av (15) at

|| h || 1 ≥ δ

^{for ein} latticeregel av utvida grad

δ

^{. For}

einvilkårleg

µ

^{får vi då at}

|| h || 1 = || [(N µ ₁ +

s

X

i=2

µ _i z _i ), − µ ₂ , . . . , − µ _s ] ^T || 1

|| h || 1 = |

s

X

j=2

µ _j z _j + µ ₁ N | +

s

X

j=2

| µ _j | m

|

s

X

j=2

µ _j z _j + µ ₁ N | +

s

X

j=2

| µ _j | ≥ δ

⁽²⁰⁾

Dettemåsærskildgjeldenår

µ ₁ = 0

^{.Viserutifrådetteatomviset}

a = (z ₂ , . . . , z _s ) ^T

med

σ = s − 1

^{element og}

λ = (µ ₂ , . . . , µ _s ) ^T

^{, får vi at dersom}

z

^{skal generere ein}

latticeregel avutvidagrad

δ

^må

a

^vereein deltasekvensavgrad

δ

^.

EitresultatavdetteogTeorem2.3eratviforeinkvar

δ

^{alltidkannneein}latticeregel avrank1og utvidagrad

δ

^{generertavein}

z = (1, z ₂ , . . . , z _s )

^der

0 < z ₁ = 1 < z ₂ < · · · <

z _s < N/2

^.

Viserat forlatticereglar

Λ

^{avdenne typenog for}

h ∈ Λ ^⊥

^nnastdetein

µ ∈ Z ^σ

^slik

at

|| h || 1 = | N µ 1 + λ · a | + || λ || 1 .

Viser at

|| h || 1 ≥ || λ || 1

^{,såved å undersøkje alle}

h

^{generert av}

µ = (0, λ) ^t

^der

|| λ || 1 ≤ δ

harvigarantert fåttmedalle

h ∈ Λ ^⊥

^{somtrengstforåevaluere(15). Vilet}

m

^veretalet

på

h

^{vi måevaluere for kvartpar av}

z

^og

N

^.

Dette leier naturleg til ein 2-stegs strategi for søk etter latticereglar. Fyrste steg vil

vere å nne gode deltasekvensar,

a

^{, før ein i andre steg nn ein minst mogleg}

N

^slik

at

z

^og

N

^{genererer eit lattice av utvida grad}

δ

^{. Frå teorem 2.3 servi at}

z _s

^{erei nedre}

grense for

N/2

^{, og det vil derfor vere naturleg å nne} deltasekvensar medlåg verdi på

z s

^{.Iresten avdette kapittelet vileg}konsentrere megomteori for steg ein.

3.4 Krav for deltasekvensar

For å kunnesøkje etter deltasekvensar eektivt måvivite noko omeigenskapane deira.

Vimåsetje nokre kravtil

z

^{for atden skalvereein}deltasekvens.

Lemma 3.1. Nødvendige krav for at ein sekvens

z

^{skal vere ein} deltasekvens av utvida grad større eller lik

δ

^er

z ₁ ≥ δ − 1

z _j − z _j−1 ≥ δ − 2; 1 < j ≤ s

Prov Begge desse kan lett visast ved motseiing. Vi antar at

z ₁ ≤ δ − 2

^{. Dersom då}

λ = (1, 0, . . . , 0)

^{fårvi at uttrykketi(20)reduserer til}

z ₁ + 1 ≤ δ − 2 + 1

^somermindre

enn

δ

^{. Vimåderforha at}

z ₁ ≥ δ − 1

^.

Tilsvarande, dersomvi antarat detfor

z

^{nnast eitpar}

z j − z j−1 ≤ δ − 3

^{får vi då}

for

λ _j = − λ _j−1

^{og med}

0

^{ellesat (20)reduserer til}

λ _j z _j − λ _j−1 z _j−1 + 2 ≤ δ − 3 + 2 < δ

^.

Teorem3.2(Reduksjonogekspansjonavdeltasekvensar).Dersom

a = (a ₁ , a ₂ , . . . , a _i−1 , a _i , a _i+1 , . . . , a _s )

er eindeltasekvens så vilogså

˜ a = (a ₁ , a ₂ , . . . , a _i−1 , a _i+1 , . . . , a _s )

^{vere ein}deltasekvens.

Dersom

a = (a ₁ , a ₂ , . . . , a _s−1 , a _s )

^{er ein} deltasekvens så må det også nnast ein

a s+1 ≥ a s + δ − 2

^{som gjer at}

a ¯ = (a 1 , a 2 , . . . , a s , a s+1 )

^{blir ein} deltasekvens.

ProvDersom

a ˜

^ikkjeereindeltasekvensmådetnnastein

˜ λ = (λ ₁ , . . . , λ _i−1 , λ _i+1 , . . . , λ _s )

somgjeratkravet(18)ikkjeheld.For

a

^måogsådentilsvarande

λ = (λ ₁ , . . . , λ _i−1 , λ _i , λ _i+1 , . . . , λ _s )

med

λ _i = 0

^{gjereat (18)ikkje held.Dette førertil ei}sjølvmotseiing og

a ˜

^{måderforogså}

vereein deltasekvens.

Dersom

a

^ereindeltasekvenshar viat (18) vilgjeldefor alle

λ = (λ ₁ , λ ₂ , . . . , λ _s )

^og

dermed også for

a ¯

^og

λ ¯ = (λ, 0)

^{. For}

λ _s+1 6 = 0

^{treng vi kun å} konsentrere ossom

λ

^der

| λ | 1 < δ − 1

^{. Dåvil}

a _s+1 > (δ − 2)a _s

alltidgieinnydeltasekvens

a ¯

^{.Pågrunnav(3.1)kan}

a _s+1

^{ikkjeveremindreenn}

a _s +δ − 2

^.

Someghar nemndvilegidenne oppgåva konsentrere megom

δ = 5

^{,ogegvilderfor}

kome med ei teorem, Teorem 3.3, som er viktig for nettopp tilfellet

δ = 5

^{. Men før det}

måvi fåpå plassto lemma.

Lemma 3.2. La

0 < a 1 < a 2 < · · · < a s

^,

2a 1 − a s ≥ 0

^,

P _s

i=1 | λ i | ≤ 4

^og

P _s

i=1 λ i 6 = 0

^.

Dåvil

S = |

s

X

i=1

λ _i a _i | ≥ 2a ₁ − a _s .

Viviser detteved åsjåpå allemoglegheitene for åkonstruere

λ

^{ut ifrådesse krava.}

For

λ ₁ 6 = 0

^og

λ _i = 0 ∀ i 6 = 1

^harvi

S ≥ | λ ₁ | a ₁ ≥ 2a ₁ − a _s

^.

For

λ ₁ = { 2, 3 } ; λ _i = − 1 ∀ i > 1

^blir

S = | λ ₁ a ₁ − a _i | ≥ 2a ₁ − a _s

^.

For

λ ₁ = 2, λ _i = − λ _j = 1

^{får vi}

S = | 2a ₁ + a _i − a _j | ≥ 2a ₁ − a _s

For

λ ₁ = λ _i = − λ _j = 1

^fårvi

S = | a ₁ + a _i − a _j | ≥ 2a ₁ − a _s

For alle andremoglegheiter der

P s

i=1 λ _i 6 = 0

^{harvi atforteikna tilalle}

λ _i ∈ λ; λ _i 6 = 0

erlike.Dette gir

S ≥ a _i ≥ a ₁

^.

Lemma 3.3. Når

2a ₁ − a _s ≥ δ − 1

^{vert kravet for at}

a = (a ₁ , a ₂ , . . . , a _s )

^{skal vere ein}

deltasekvens at

0 <

s

X

i=1

| λ i | ≤ δ − 1

^og

s

X

i=1

λ i = 0

ProvDetteserviutifråatfor

P _s

i=1 λ _i 6 = 0

^fårvi

P _s

i=1 | λ _i | + | S | ≥ P _s

i=1 | λ _i | +2a ₁ − a _s ≥ 1 + δ − 1

^.

Teorem 3.3 (Tilstrekkjelege og nødvendige krav til deltasekvensar av utvida grad 5).

La

a _s < 2a ₁ − δ + 1

^og

_i,j = | a _i − a _j |

^{. Dåvil}

a = (a ₁ , a ₂ , · · · , a _s )

^{danne ein}deltasekvens med

δ ≥ 5

^{dersom,og kun dersom}

E = { i,j ; s ≥ i > j ≥ 1 }

inneheld distinkteelement og

_i,j ≥ 3

Prov Fyrst vilvi vise at dersom

a

^{skalvere ein} deltasekvens må

E

^{innehalde distinkte}

element.

Dersom

_i,j = _k,l

då er

a _i − a _j − a _k + a _l = 0.

Dersom visåvel

λ _i = − λ _j = − λ _k = λ _l = 1; λ _r = 0 ∀ r / ∈ i, j, k, l

får vi

s

X

m=1

| λ m | + |

s

X

m=1

λ m a m | = 4 < 5.

Dette viserat fyrste kraveternødvendigfor at

a

^skalvereein deltasekvens.

For å vise at dette er eit tilstrekkjeleg krav treng vi, ut i frå lemma 3.3, berre å

vurderedeitilfella der

P s

i=1 λ _i = 0

^.

For

λ _i = − λ _j

^{får vi}

S = | λ _i (a _i − a _j ) |

^{som gir}

P _s

k=1 | λ _k | + S ≥ 2 + _i,j ≥ δ

For

λ _i = − λ _j = λ _k = − λ _l

^{får vi}

S = | ± _i,j ± _k,l |

^{. Sidan alle}

^{er distinkte får vi}

P s

m=1 | λ m | + S ≥ 4 + S ≥ δ

For

λ _i = − 2λ _j = − 2λ _k

^blir

S = | 2a _i − a _j − a _k | = |± _i,j ± _j,k |

^.Dettegir

P _s

l=1 | λ _l | +S ≥ 4 + S ≥ δ

^.

3.5 Golomblinjalar og kopling til deltasekvensar

Kravet om distinkte avstandar kjenner vi att som det som denerer eit anna fenomen

kallagolomblinjalar.

Denisjon 3.3 (Golomblinjal). Ein vektor,

a = (a ₁ , a ₂ , . . . , a _σ ); a ₁ < a ₂ < · · · < a _σ

^,

deralletalaerheiltal,vertkallaeingolomblinjaldersomdetforeitheiltal,

x 6 = 0

^,nnast

høgstei løysingpå likninga

x = a _j − a _i

^,

a _i , a _j

^.

Eit enkelt tal ieinslik golomblinjal vert kalla eit merke. Lengda av eingolomblinjal

G(σ)

^{vert denert som}

G(σ) = a _σ

^der

a _σ

^{er det merke med høgast verdi. Ein optimal}

golomblinjalerden kortastmoglegefor eit gitt talpå merker.

Tooperasjonarsomernyttige,ogsomgjeratgolomblinjalaneframleisergolomblinjal,

erfjerning avmerker ogforskuvingavmerka medeinheiltalsverdi.

Teorem 3.4 (Forskuving og trunkering av golomblinjal). For einkvar golomblinjal

a = (a ₁ , . . . , a _σ−1 , a _σ )

^ogkonstant

c ∈ Z

^vilogså

a ⁰ = (a ₁ , . . . , a _σ−1 )

^og

a ⁰⁰ = (a ₁ +c, . . . , a _σ−1 + c, a _σ + c)

^vere golomblinjal.

Prov Dersomvi harein golomlbinjal

a = (a 1 , a 2 , . . . , a i−1 , a i , a i+1 , . . . , a σ )

^{kan vifjerne}

eit merke og får

a ⁰ = (a ₁ , a ₂ , . . . , a _i−1 , a _i+1 , . . . , a _σ )

^.Dersom

a ⁰

^{ikkje er} golomblinjalmå det nnast

j, k, l, m

^{slik at}

a _j − a _k = a _l − a _m

^{. Men sidan} operasjonen vi har utført er å fjerne eit merke, må desse merka framleis nnast i

a

^{, som impliserer at}

a

^{ikkje er}

golomblinjal. Vedmotseiing måderforogså

a ⁰

^veregolomblinjal.

For å viseat forskuving girein nygolomblinjalantar vi fyrstat

a = (a ₁ , a ₂ , . . . , a _σ )

ergolomblinjal. For ein

c ∈ Z

^{har vi}

a ⁰⁰ = (a ₁ + c, a ₂ + c, . . . , a _σ + c)

^.Dersom

a ⁰⁰

^ikkjeer

golomblinjalmådetnnast

i, j, k, l

^slikat

a _i + c − (a _j + c) = a _k + c − (a _l + c)

⇓

a _i − a _j = a _k − a _l .

Men dette impliserer at

a

^{ikkje er} golomblinjal og vi får ei motseiing. Vi får då at

a ⁰⁰

ogsåmåvere golomblinjal.

Golomblinjalar dukka fyrstopp i eitarbeid av Wallace C. Babcock frå 1953 [2 ] som

ei løysing på eit problem i samband med radioteknikk. Ein kunne redusere interferens

Golomblinjalen er oppkalla etter Solomon W. Golomb som var den fyrste til å studere

deisystematisk.

Ein ekvivalentdenisjonersidonsett,somdenerastutifråat detinnehelddistinkte

summar for kvart par av merker. Vi ser lett denne ekvivalensen ved at om

a _i − a _j 6 = a _k − a _l , ∀ { i, j, k, l } ∈ Z

^måogså

a i + a _l 6 = a _k + a j

^{.Sidonsetthar blittstudertsidan1930}

talet, ogvart fyrstskildraav Simon Sidon[21],saman med PálErd®s og Pál Turán [8].

Frå teori baksidonsett har vi einedregrense for lengdapå eingolomblinjal[14]

G(σ) ≥ σ ² − 2σ √ σ + √

σ − 2.

⁽²¹⁾

EkvivalensmedgolomblinjalarharblittdemonstrertavApostolosDimitriomanolakis[7].

Ingen lukka løysing på konstruksjon av optimale golomblinjalar nnast endå. Dei

vi kjenner er funne ved systematiske søk, fyrst manuellt og seinare med datamaskiner.

SærskildkaneinnemneprojectOGRdrivepåwww.distributet.net [9],somereitmassivt

kooperativt søk etter optimale golomblinjalar.

Det nnast likevel eire ulike konstruksjonar som gir nær optimale golomblinjalar.

Med nær optimale golomblinjalar meinar ein golomblinjalar med lengde

a _σ ≤ σ ²

^{, som}

erinærleikenavdennenedregrensa nemndover.Dette fylogsåeitframlegg, presentert

av Erd®s [8 ],som seierat alle optimale golomblinjalar med

σ

^{merker erkortare enn}

σ ²

^.

Dette har ikkje blitt universellt prova, men det har blitt vist korrekt for

s < 65000

^[1]

[13 ] [7].

Ein spesiell måte å framstille golomblinjalar på, som eg har gjort nytte av i dette

arbeideterdetsomvertkallasykliskegolomblinjalar,ellerogsåmodulæregolomblinjalar.

Dei er kort fortald kjenneteikna ved at dei der ein vanleg golomblinjal er denert ut i

frå å ha unike dieransar mellom merka, har ein syklisk golomblinjal unike dieransar

moduloeit heiltal

b

^{.Meir persist vertdette denert slik.}

Denisjon 3.4 (Sysklisk golomblinjal). For to tal

a _i , a _j ∈ a; i 6 = j

^der

a

^{er einsyklisk}

golomblinjal, har viat

(a i − a j )(

^mod

b) 6 = (a j − a i )(

^mod

b)

Ein nyttig måte å illustrere einslik golomblinjal er å ta einsirkelmed omkrins

b

^og

plassereutdistansanerundtdennesirkelen.Deravharvinamnetsykliskegolomblinjalar.

Ein grunn til at sykliske golomblinjalar eravinteresse i denne oppgåva er at mange

av dei gode konstruksjonane som gir korte golomblinjalar er basert på modulære kon-

struksjonar og gir nettopp sykliske golomblinjalar. Dei beste av dei gir golomblinjalar

med lengde rundt

s ²

^{, som også er i nærleiken av denne nedre grensa for lengda av}

golomblinjalar nemnd over. Dette er praktisk for oppgåva i og med at vi er på jakt

etter golomblinjalar somersåkorte sommogleg.

Nårvifyrsthar funneeinsykliskgolomblinjalmed

s

^{merker, kanvikonstruere}

s − 1

nye golomblinjalarved forskuvingavgolomblinjalenmodulo

b

^{.Detvilseie,omviharein}

golomblinjal

a = a 1 , a 2 , . . . , a s

^{,kan vidanne einny}golomblinjalved transformasjonen

a ⁰ = S _c (a) = { a ₁ + c(

^mod

b), a ₂ + c(

^mod

b), . . . , a _s + c(

^mod

b) }

⁽²²⁾

der

c

^{er eit vilkårleg heiltal. Ved å velje}

c = b − a _s

^{får vi ein ny} golomblinjal der det øverste merkethar blitt detlågaste. Denneprosessen kanhalde framinntil vi ertilbake

tildenoriginale golomblinjalen,og vivilhaeitsettpå

s

^{ulikelinjalar.Alledesse vilvere}

deltasekvensar, mengenereltulikemed omsyntilgrad.

SomvisågiTeorem3.3måeindeltasekvens

δ ≥ 5

^{,itilleggtilåvere}golomblinjal,ha minsteavstand

min( i,j ) ≥ 3

^{.Dettegjeratomeinkankonstruere}golomblinjalarmeddei rette eigenskapane kan einogså, ialle fall ut ifrå teorien, konstruere godelatticereglar.

Problemet er at einikkje for tida har tilstrekkjeleggode kravtil desse golomblinjalane,

og ein kan berreeksperimentellt nne gode kandidatar mellom deimange mindregode.

Det er helder ikkje blitt vist at ein optimal golomblinjal automatisk vil gi ein optimal

latticeregel.SamanhangenhereratpågrunnavTeorem2.3vilvireknemedatdeibeste

z

^har

z _s

^{liten.Dessutan erdetikkje sålett å seiekvasomereingod}latticeregel når ein ikkjeallereiehar den optimale.

Framgongsmåteneghervilnyttevilvereåfyrstkonstruereeinnæroptimalgolomblin-

jal, for såå fjerne eit eller to merker slik at

min( _i,j ) ≥ 3

^{. Vi kan kalle mengda av alle}

golomblinjalarmedminsteavstand

i, j ≥ k

^for

GL _k

^{,ogvierderforuteetter}deltasekven- sar

a ∈ GL ₃

^. Implementeringa og algoritmene frå denne teorien vil eg skildre i neste kapittel.

4.1 Algoritmer

Fornoåkunnearbeidevidaremåvikunneimplementeredenne teorienirobustealgorit-

mer.Dei algoritmene vi treng for å gjennomføre vårt søketter gode latticereglar består

fyrst og fremst ein metode for å rekne ut trigonometrisk grad. Denne, som vi skal sjå,

kan delast i to mindre algoritmer. Vidare vil vi ha behov for å kunne konstruere

z

^{, og}

ut i frå førre kapittel, også metodar for å konstruere deltasekvensar. Dette er også ein

todeltprosess,dervi fyrstdannardeltasekvensar,for såå modiseredeipå ulike måtar

for ågi ein

z

^{av ynskagradfor gitt dimensjon. Tilslutttreng viei algoritmefor å setje}

saman dessetil eit eektivtsøk.

Programmet eg har nytta baserer seg på å konstruere latticereglar ved hjelp av

golomblinjalar, for så å teste latticereglane for trigonometrisk grad. Det er likevel in-

genting ivegenfor ånytte algoritmene for testing av trigonometrisk grad i eitprogram

somtekikkjeeksplisittsykliskegolomblinjalarsominput.Detatgolomblinjalaneersyk-

liskei mittprogram gjer detenklare å manipulere dei, slik at vi kanteste eire linjalar

utifrå densamekonstruksjonen.Dessutandannaralledeibesteavdeikjendekonstruk-

sjonane sykliske golomblinjalar. Vi vil derfor gjerne også utnytte denne eigenskapen i

programmet.

Andre ting vi vil utnytte i denne oppgåva er det faktum at det nnast eire ulike

metodarforågenereregolomblinjalar.Dettegirgrunnlagfor eindelheuristiskemetodar

for å forbetre søket etter latticereglar. Eg vil kommentere dette for deialgoritmene der

dette eraktuelt.

4.2 Utrekning av trigonometrisk grad

Før eg nogjernoko annavileg presenteremetoden egbrukar for å nnetrigonometrisk

grad. Standardmåten å rekne ut trigonometrisk grad er å variere

h

^med

|| h || 1 = d

^for

stigande

d

^{, for så å teste}

h · z(

^mod

N ) 6 = 0

^{inntil dette feilar} ?? h-norm<delta). For den

h

^{dertesten feilarhar vi}

δ = || h || 1

^{. For mine algoritmer har eg teke} utgangspunkt i eit program skildra av Ronald Cools [5], som nettopp er basert på denne opplagde

algoritmen. Dersom vi kun er ute etter å vite om ein gitt latticeregel har utvida grad

δ ≥ ˆ δ

^{,og ikkjetreng åviteden eksaktegradatil} latticeregelen, kanvi stoppe når alle

h

der

|| h || 1 < ˆ δ

^erevaluert.

Eit problem med denne metoden å gjere det på er at når vi vil undersøke eire

latticereglarharvibehovforågenereremange

h

^vektorar.Utfordringavertdåågenerere kundei

h

^{vektorane vihar behov for,og ikkjeeire.}

Det nye eg har her i mine algoritmer er ein observasjon som gjer at vi kan dele

prosessen medånne trigonometrisk grad innito trinn,og itillegg kuneta varepåein

delinformasjonutanåmåtte rekneutaltpånyttforkvarnye

N

^{.Dersomvivilevaluere}

h · h

^{for mange}

z

^{kan det vere nyttig å lagre alle}

h

^{i ei matrise}

H

^{. I tillegg, om vi så}

vil evaluere

Hz(

^mod

N )

^{for mange}

N

^{kan det vere lønsamt å lagre}

q = Hz

^{og helder}

evaluere

q(

^mod

N )

^.

Eg vilfyrstleggje framalgoritmen nn

q()

^{,som dannar kjernen for desse}utrekningane.