Normat 55:2, 59–77 (2007) 59
Lineære avbildninger og Lineær rekursjon
Dan Laksov
Matematiska Institutionen, KTH
SE-100 44 Stockholm
laksov@math.kth.se
I forbindelse med semiariet holdt til minne om E.S. Selmer den 16/2-07 på Mate-
matisk Institutt ved Universitetet i Bergen hadde jeg den selvpåtatte oppgaven å
si noen ord om lineær rekursjon over endelig kropper slik området fortonet seg i
Bergen på 1960’tallet. Mens jeg forebredte mitt foredrag slo det meg at man kan
betrakte løsningene til lineære rekursjonsrelasjoner som spesielle lineære avbildnin-
ger på polynomringer i en variabel. Dette er på en måte det duale synspunktet til
det som finnes i litteraturen, og gir en naturlig innfallsport til teorien for lineær re-
kursjon. Resultatene kommer på denne måten i et klarere lys, bevisene blir lettere,
og man bli på en naturlig måte ledet til generaliseringer av teorien. Spesielt blir
det klart at begrensningene til endelige kropper, eller mer generelt, til periodiske
sekvenser, er unødvendig for de fleste betraktningene. Dette illustrerer vi nedenfor
ved å gi en detaljert fremtilling av teorien for multigrammer. Jeg mistenker at jeg
ikke er den første som har oppdaget det duale perspektivet, men ettersom jeg ikke
kan finne det i litteraturen, og ettersom Selmer så godt som egenhendig drev Nor-
mat i 25 år vil jeg med disse notatene gjøre synspuktet tilgjengelig for Normats
lesere.
Jeg har ikke gjort noe forsøk på å skrive en komplett fremstilling av teorien for
lineære rekursjoner, men har illustrert den duale metoden ved å velge ut karakte-
ristiske deler av [L1], [L2], [P], [S] og [Z].
Som leseren vil oppdage er språket utpreget matematisk, med termer som ringer,
kropper, grupper, moduler og idealer. Ingen bør imidlertid blir avskrekket av dette.
Nå man ser ringer behøver man bare tenke på de hele tallene eller de hele tallene
modulo et helt tall, og når man ser kropper skal man tenke på de rasjonale tallene
eller de hele tallene modulo primtall. Moduler, grupper og idealer er eksplisitt gitt,
og regnerelgene i hvert konkret tilfelle er lette å verifisere. Grunnen til at vi bruker
en mer høytravende terminologi er at dette er praktisk, og antyder at materialet
er en del av en mer generell forestillingsverden.
Innledning
De aller fleste har noen gang kommet i kontakt med lineære rekursjoner. I det
minste har de hørt om Fibonacci sekvensen
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . ,
60 Dan Laksov Normat 2/2007
der hvert tall efter de to første er summen av de to foregående. Fibonacci sekvensen
forekommer overalt i matematikken og i naturen, og den har masser av interessante
egenskaper ([V], [VS]). Den har blitt studert fra en rekke ulike synspunkter og det
er skrevet titusentalls artikler om den.
En annen velkjent og flittig studert løsning til den samme lineære relasjonen er
Lucas sekvensen
1, 3, 4, 7, 11, 18, 29, 47, 76, . . . ,
der også hvert tall etter de to første er summen av de to foregående.
De to første tallene 1, 1, og 1, 3, i Fibonacci sekvensen, respektive i Lucas sekven-
sen, kalles begynnelsesverdiene til sekvensene. Det er klart at begynnelsesverdiene,
sammen med regelen om at hvert tall etter de to første er summen av de to fore-
gående, bestemmer resten av sekvensen. For eksempel gir begynnelsesverdien 3, 1
sekvensen
3, 1, 4, 5, 9, 14, 23, 37, 60, . . . .
Et viktig problem for slike sekvenser er å bestemme, for et gitt primtall, hvilke av
medlemmene i sekvensen som er delbare med dette primtallet. Vil vi, for eksempel,
bestemme hvilke av tallene i sekvensene ovenfor som er delbare med to, kan vi regne
i tallkroppen {0, 1} med to elementer der 1 + 1 = 0. Vi får at alle tre sekvensene
ovenfor gir sekvensen
1, 1, 0, 1, 1, 0, 1, 1, 0, . . .
i denne kroppen, det vil si, en periodisk sekvens med periode 3. Ettersom termene
nummer 3, 6, 9, . . . er 0 vil det være termene med disse nummerene, og bare disse,
som er delbare med 2. Er vi interesserte i hvilke av medlemmene i de tre sekvensene
som er delbare med 3 kan vi regne i tallkroppen {0, 1, 2} med tre elementer, der
1 + 2 = 0, 2 + 2 = 1 = 2 · 2. Vi får da de tre sekvensene
1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, . . .
1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, . . .
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, . . .
alle med periode 8. Vi ser at de tre sekvensene er forskyvninger av hverandre. I den
første sekvensen hara vi nuller på plassene 4, 8, 12, 16, . . . , så tallene i Fibonacci
sekvensen er delbare med 3 nøyaktig på disse plassene. Den andre sekvensen har
nuller på plassene 2, 6, 10, 14, . . . så tallene i Lucas sekvensen er delbare med 3
nøyaltig på disse plassene.
Delbarhet med primtall er bare en side av lineære rekursjoner. Slike rekursjoner
forekommer i mange forkledninger i matematikken. De har også store anvendelser,
spesielt ved elektronisk overføring av informasjon, der de er nær forbundet med
skift registre. De spiller en stor rolle i feilkorrigerende koder og ved krypering av
meddelelser, og brukes til å generere pseudoslumptall.
I det følgende skal vi konsentrere oss om egenskaper som er felles for sekvensene
vi får for en gitt lineær rekursjon når vi varierer begynnelsesverdiene. For eksempel,
i kroppen med to elementer vil den lineære rekursjonen der hvert tall etter de to
Normat 2/2007 Dan Laksov 61
første er summen av de to foregående ha fire løsninger svarende til de fire mulige
begynnelsesverdiene 0, 0, og 0, 1 og 1, 0 og 1, 1. Disse er
0, 0, 0, 0, 0, 0, 0, 0, 0, . . .
0, 1, 1, 0, 1, 1, 0, 1, 1, . . .
1, 0, 1, 1, 0, 1, 1, 0, 1, . . .
1, 1, 0, 1, 1, 0, 1, 1, 0, . . .
der de tre siste har periode 3 og er samme sekvens forskjøvet et eller to steg. Det
er for slike samlinger av løsninger vårt perspektiv på lineære rekursjonsrelasjoner
er mest fruktbar.
1 Lineære avbildninger og sekvenser
Som nevnt i innledningen danner lineære avbildninger fundamentet for vår innfalls-
vinkel til lineære sekvenser. I denne sekjonen innfører vi den nødvendige notasjonen
og gir noen av de grunnleggende resultatene. Vi viser også sammenhengen mellom
lineære avbildninger og løsningene til lineære rekursjonsrelasjoner.
1.1 Lineære avbildninger og idealer. Vi skal betrakte lineære rekursjoner
over en vilkårlig kommutativ ring A med enhet. En sentral rolle spiller gruppen
Hom
A
(A[T ], A) av A-lineære avbildninger, eller som vi nøyer oss med å si, lineære
avbildninger
x : A[T ] → A
fra polynomringen A[T ] i den variable T til A. For hvert polynom g i A[T ] betegner
vi med L
A
(g) de lineære avbildningene x : A[T ] → A som er null på elementene
T
i
g for i = 0, 1, . . . , eller ekvivalent, de lineære avbildningene som er null på idealet
(g) = {hg : h ∈ A[T ]}
generert av g, Det vil si
(1.1.1) L
A
(g) = {x ∈ L
A
(0) : x(hg) = 0 for alle h ∈ A[T ]}.
Vi ser at L
A
(0) = Hom
A
(A[T ], A) og av (1.1.1) ser vi at om g deler h i A[T ] vil
L
A
(g) ⊆ L
A
(h).
Det er klart at L
A
(g) er en gruppe. Videre er L
A
(g), på en naturlig måte, en A[T ]-
modul ved at produktet av et polynom h i A[T ] med et element x i L
A
(g) er definert
av
(hx)(k) = x(hk) for alle k ∈ A[T ].
For å se at hx er i L
A
(g) rekker det å observere at (hx)(gk) = x(hkg) = 0. Det er
klart av definisjonen av modulstrukturen at L
A
(g) er en undermodul av L
A
(0).
En fordel ved å betrakte L
A
(0) som en A[T ]-modul er at vi får den smidige
skrivemåten
L
A
(g) = {x ∈ L
A
(0) : gx = 0}.
62 Dan Laksov Normat 2/2007
Vi betegner med L
A
unionen av alle modulene L
A
(g) for g et monisk polynom i
A[T ], det vil si, polynomene g slik at koeffisienten for den høyeste potensen av T
i g er 1. Da er L
A
en undermodul av L
A
(0) fordi for x ∈ L
A
finnes det et monisk
polynom f i A[T ] slik at x ∈ L
A
(f) og derfor vil hx være i L
A
(f) for alle h ∈ A[T ].
Videre finnes det for y ∈ L
A
et monisk polynom g slik at y ∈ L
A
(g), og da vil
x + y ∈ L
A
(fg).
1.2 Lineære avbildninger, sekvenser og lineær rekursjon. Til hver sekvens
x
0
, x
1
, . . . av elementer i A svarer det nøyaktig en lineær avbildning x : A[T ] → A
bestemt av
x(T
i
) = x
i
for i = 0, 1, . . . .
Med andre ord har vi en bijeksjon
(1.2.1) L
A
(0) ←→ {sekvenser av elementer i A}
som avbilder den lineære avbildningen x til sekvensen x(1), x(T ), x(T
2
), . . . .
La
f(T ) = T
n
− c
1
T
n−1
+ ··· + (−1)
n
c
n
være et polynom i A[T ]. En lineær avbildning x ∈ L
A
(0) ligger i L
A
(f) hvis og
bare hvis x(T
i
f) = x(T
n+i
− c
1
T
n+i−1
+ ··· + ( −1)
n
c
n
T
i
) = 0 for i = 0, 1, . . . .
Setter vi x
i
= x(T
i
) for i = 0, 1, . . . kan dette skrives
(1.2.2) x
n+i
− c
1
x
n+i−1
+ ··· + (−1)
n
c
n
x
i
= 0 for i = 0, 1, . . . .
Vi sier at sekvensen x
0
, x
1
, . . . tilfredsstiller den lineære rekursjonen (1.2.2) med
karakteristisk polynom f(T ). Bijeksjonen (1.2.1) induserer følgelig en bijeksjon
L
A
(f) ←→ {sekvenser i A som tilfredsstiller den lineære rekursjonen (1.2.2)}.
For å fordype forståelsen av sammenhengen mellom lineære avbildninger og sekven-
ser merker vi at i bijeksjonen (1.2.1) svarer T x til den translaterte sekvensen
x
1
, x
2
, . . . .
Eksempel I. Vi gir et eksempel som illustrerer hvordan sekvenser som tilfreds-
stiller en lineær relasjon kan oppstå, og hvordan sekvensene er knyttet til lineære
avbildninger. La K = {0, 1} være kroppen med to elementer, så 1 + 1 = 0. Vi
definerer en lineær avbildning x : K[T ] → K ved
x(T
i
) =
(
0 når i eller i − 1 er delbar med 4
0 når i − 2 eller i − 3 er delbar med 4,
det vil si, sekvensen x(T
0
), x(T
1
), x(T
2
), . . . er 0, 0, 1, 1, 0, 0, 1, 1, . . . , som er perio-
disk med periode 4. Vi verifiserer lett at
x(T
i+3
− T
i+2
+ T
i+1
− T
i
) = x(T
i+3
) − x(T
i+2
) + x(T
i+1
) − x(T
i
) = 0,
Normat 2/2007 Dan Laksov 63
så x er null på alle elementer på formen T
i
(T
3
− T
2
+ T − 1), det vil si, på alle
elementer i idealet (f), der
f = T
3
− T
2
+ T − 1.
Den lineære avbildningen x er følgelig i L
K
(f), eller ekvivalent, sekvensen
0, 0, 1, 1, 0, 0, 1, 1, . . .
tilfredsstiller den lineære rekursjonen
x
3+i
− x
2+i
+ x
1+i
− x
i
= 0.
Det er instruktivt å bestemme flere liknende eksempler der man definerer verdiene
x(T
i
) ved egenskaper som kommer fra delbarhet med et av tallene 3, 4, 5, . . . .
2 Modulen av lineære avbildninger
I forrige seksjon viste vi sammenhengen mellom lineære avbildninger og løsninger
av linære rekursjonsrelasjoner. Her viser vi hvordan hovedsatsene for løsningene av
lineære rekursjonsrelasjoner ser ut når de formuleres og vises for lineære avbildnin-
ger. Spesielt merker vi hvor lett, naturlig og generell teorien blir.
2.1 Lemma. La f i A[T ] være et monisk polynom av grad n og la x
0
, . . . , x
n−1
være elementer i A. Da finnes det nøyaktig en lineær avbildning x i L
A
(f) slik at
x(T
i
) = x
i
for i = 0, . . . , n − 1.
Mer presist, A-modulen L
A
(f) er fri med basis e
0
, . . . , e
n−1
bestemt av
e
i
(T
j
) =
(
1 i = j
0 i 6= j
for i, j = 0, . . . , n −1.
Bevis. Som vi så i Seksjon 1.1 gir hver sekvens x
0
, x
1
, . . . i A en entydig lineær
avbildning x i L
A
(0) slik at x(T
i
) = x
i
for i = 0, 1, . . . . Videre så vi at x er i L
A
(f)
hvis og bare hvis x
0
, x
1
, . . . tilfredsstiller den lineære rekursjonen (1.2.2). Vi ser
umiddelbart, ved induksjon etter i, at (1.2.2) entydig bestemmer x
n
, x
n+1
, . . . når
x
0
, . . . , x
n−1
er gitt. Dette viser første delen av lemmaet.
For å vise den andre delen av lemmaet observerer vi at de lineære avbildningene
x og x
0
e
0
+ ··· + x
n−1
e
n−1
begge ligger i L
A
(f), og de tar samme verdier på
1, T, . . . , T
n−1
. Det følger da av den første delen av lemmaet at x = x
0
e
0
+ ··· +
x
n−1
e
n−1
, så e
0
, . . . , e
n−1
genererer A-modulen L
A
(f). At e
0
, . . . , e
n−1
er lineært
uavhengige over A er opplagt.
64 Dan Laksov Normat 2/2007
2.2 En fundamental lineær avbildning. La f være et monisk polynom av grad
n som ligger i A[T ]. Vi betegner med u = u
f
elementet i L
A
(f) bestemt av
u(T
i
) =
(
0 i = 0, . . . , n − 2
1 i = n −1
.
Eksempel II. Vi forsetter Eksempel I. I dette eksempelet er n = 3 og vi kan velge
begynnelsesverdiene x
0
, x
1
, x
2
på 2
3
= 8 måter. Dette gir sekvensene
I: 0, 0, 0, 0, 0, 0, 0, 0, . . .
II: 0, 1, 0, 1, 0, 1, 0, 1, . . .
III: 0, 0, 1, 1, 0, 0, 1, 1, . . .
IV: 0, 1, 1, 0, 0, 1, 1, 0, . . .
V: 1, 0, 0, 1, 1, 0, 0, 1, . . .
VI: 1, 1, 0, 0, 1, 1, 0, 0, . . .
VII: 1, 0, 1, 0, 1, 0, 1, 0, . . .
VIII: 1, 1, 1, 1, 1, 1, 1, 1, . . .
Sekvensene I og VIII har periode 1, sekvensene II og VII har periode 2, og resten
periode 4. Vi ser at sekvensen tilsvarende u i 2.2 er III, og at III, IV, VI, V er
u, T u, T
2
u, T
3
u respektive.
2.3 Setning. La f i A[T ] være et monisk polynom av grad n. Da er L
A
(f) en fri
A-modul med basis u, T u, . . . , T
n−1
u.
Bevis. Det følger av Lemma 2.1 at vi må vise at det, for hver sekvens x
0
, x . . . , x
n−1
av elementer i A, finnes nøyaktig et polynom g = a
n−1
+ a
n−2
T + ··· + a
0
T
n−1
i A[T ] slik at (gu)(T
i
) = x
i
for i = 0, . . . , n − 1, det vil si, slik at a
n−1
u(T
i
) +
a
n−2
u(T
i+1
) + ···+ a
0
u(T
i+n−1
) = x
i
for i = 0, . . . , n −1. Av definisjonen på u er
dette det samme som ligningssystemet
a
i
u(T
n−1
) + a
i−1
u(T
n
) + ··· + a
0
u(T
i+n−1
) = x
i
for i = 0, . . . , n − 1,
eller
1 0 0 . . . 0 0
u(T
n
) 1 0 . . . 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
u(T
2n−2
) u(T
2n−3
) u(T
2n−4
) . . . u(T
n
) 1
a
0
a
1
.
.
.
a
n−1
=
x
0
x
1
.
.
.
x
n−1
.
Det er opplagt at dette ligningssystemet har en entydig løsning i a
0
, . . . , a
n−1
når
x
0
, . . . , x
n−1
er gitt.
2.4 Korollar. La f og g være polynomer i A[T ] med f monisk. Da vil f dele g
hvis og bare hvis L
A
(f) ⊆ L
A
(g).
Normat 2/2007 Dan Laksov 65
Bevis. Vi observerte i Seksjon 1 at om f deler g så vil L
A
(f) ⊆ L
A
(g).
Ettersom f er monisk kan vi bruke Euklids algoritme i A[T ]. Vi får at g = qf +r
med q og r i A[T ], og der graden til r er strikt mindre enn graden til f.
Anta at L
A
(f) ⊆ L
A
(g). Da vil u
f
∈ L
A
(g) så 0 = gu
f
= (qf)u
f
+ ru
f
= ru
f
.
Men av setningen følger det at ru
f
= 0 medfører at r = 0, det vil si, f deler g.
2.5 Bemerkning. Korollar 2.4 er en vesentlig generalisering av et resultat av N.
Zierler [Z].
Eksempel III. Vi bruker Eksemplene I og II til å illustrere Korollar 2.4. Merk at
f = T
3
− T
2
+ T −1 = (T − 1)(T
2
+ 1).
Vi har at L
K
(T
2
+ 1) består av de fire lineære avbildningene som tilsvarer sekven-
sene
I: 0, 0, 0, 0, 0, 0, 0, 0, . . .
II: 0, 1, 0, 1, 0, 1, 0, 1, . . .
VII: 1, 0, 1, 0, 1, 0, 1, 0, . . .
VIII: 1, 1, 1, 1, 1, 1, 1, 1, . . .
og at L
K
(T − 1) består av to lineære avbildninger som tilsvarer sekvensene
I: 0, 0, 0, 0, 0, 0, 0, 0, . . .
VIII: 1, 1, 1, 1, 1, 1, 1, 1, . . . .
Som påstått i Korollar 2.4 ser vi at L
K
(T
2
+ 1) og L
K
(T −1) begger er inneholdt
i L
K
(f). Tar vi et polynom som ikke deler f, for eksempel T
2
− T + 1 får vi for
eksempel at
0, 1, 1, 0, 1, 1, 0, 1, . . .
tilsvarende en lineær avbildning som ligger i L
K
(T
2
− T + 1), men ikke i L
K
(f).
2.6 Bemerkning. La f være et monisk polynom i A[T ] og la (f) = {gf : g ∈ A[T ]}
være idealet genert av f . Restklasseringen til A[T ] modulo f betegner vi med
A[T ]/(f). Vi har en isomorfi av A[T ]-moduler
(2.6.1) A[T ]/(f) −→ L
A
(f)
entydig bestemt av at klassen til et polynom g i A[T ] modulo f avbildes til gu =
gu
f
.
Dette følger av Setning 2.3, for vi har en avbildning av A[T ]-moduler A[T ] →
L
A
(f) som avbilder g til gu. Denne avbildningen er surjektiv ved Setning 2.3 og
kjernen inneholder (f) ved definisjonen av L
A
(f). Derfor får vi indusert en av-
bildning A[T ]/(f) → L
A
(f) som påstått. Men denne avbilder A-modul basisen
i A[T ]/(f) som består av restlassene til 1, T, . . . , T
n−1
modulo f, til elemente-
ne u, T u, . . . , T
n−1
u. Men disse elementene i L
A
(f) danner en A-modul basis for
66 Dan Laksov Normat 2/2007
L
A
(f) ved Setning 2.3. Avbildningen 2.6.1 er derfor en isomorfi av A-moduler, og
derfor en isomorfi av A[T]-moduler.
Bruker vi isomorfien 2.6.1 kan vi vise at Korollaret 2.4 følger av Setning 2.3 uten
å bruke Euklids algoritme. Dette er en mer naturlig måte å vise Korollar 2.4 på.
Grunnen til at vi velger en annen vei er at vi vil unngå bruken av restklassringen.
På den andre siden er dette litt av en illusjon ettersom Euklids algoritme oftest
brukes til å vise A[T ]/(f) er en fri A-modul.
3 Lineære rekursjoner over kropper
Det vesentlige skillet mellom teorien for lineære rekursjonsrelasjoner over ringer og
kropper er at vi over kropper har tilgang til minimalpolynomer. I denne seksjo-
nen definerer vi minimalpolynomer for samlinger av lineære avbildninger og gir de
viktigste resultatene om minimalpolynomer.
3.1 Idealer. La K være en kropp. Da vil polynomringen K[T ] være et prinsipal-
idealområde. Det vil si, for hver undergruppe I 6= 0 av K[T ] slik at hg ∈ I for alle
g ∈ I og h ∈ K[T ], finnes det et entydig monisk polynom f i K[T ] slik at I = (f ).
En undergruppe I med egenskapen ovenfor kalles et ideal i K[T ].
3.2 Minimalpolynom. For hver undermengde S av L
K
skriver vi
I
S
= {g ∈ K[T ] : gx = 0 for alle x ∈ S},
eller ekvivalent
(3.2.1) I
S
= {g ∈ K[T ] : S ⊆ L
K
(g)}.
Det er klart at I
S
er et ideal i K[T ].
Om I
S
6= 0 betegner vi med f
S
det entydige moniske polynomet slik at I
S
= (f
S
)
og vi kaller f
S
for minimalpolynomet for S. Det er klart at
(3.2.2) S ⊆ L
K
(f
S
).
Om S = {x} har S alltid et minimalpolynom siden x ∈ L
K
(f) for et monisk
polynom f . Vi skriver da f
S
= f
x
og kaller f
x
for minimalpolynomet for x.
3.3 Lemma. La S være en undermengde av L
K
.
1. S har et minimalpolynom hvis og bare hvis det finnes et monisk polynom
f ∈ K[T ] slik at S ⊆ L
K
(f). Når dette holder vil f
S
dele f.
2. Om S = L
K
(f) vil f
S
= f.
Bevis. Første delen av (1) følger umiddelbart av uttrykket (3.2.1) for I
S
og defi-
nisjonen av minimalpolynom. At f
S
deler f følger da av definisjonen på minimal-
polynomet f
S
.
Av (3.2.2) har vi at når S = L
K
(f) vil L
K
(f) ⊆ L
K
(f
S
). Men av Korollar 2.4
har vi at L
K
(f) ⊆ L
K
(f
S
) medfører at f deler f
S
, så vi har f
S
= f, det vil si,
utsagnet (2) holder.
Normat 2/2007 Dan Laksov 67
Eksempel IV. Vi viser hvordan vi kan bruke Lemma 3.3 til å bestemme mini-
malpolynomene til de lineære avbildningene i Eksemplene I, II og III. La f
i
være
minimalpolynomet for den lineære avbildningen som tilsvarer sekvens nummer i.
Av Lemma 3.3 følger at minimalpolynomet til en lineæravbildning x i L
K
(f) deler
f. Av f = (T −1)(T
2
+ 1) = (T −1)(T + 1)
2
ser vi derfor med det samme at f
I
= 1,
f
VIII
= T − 1, f
II
= T
2
+ 1 = f
VII
, og at f
III
, f
IV
, f
V
og f
VI
alle er f.
Følgende resultat er klassisk og ryktet sier at det var kjent for L. Kronecker.
3.4 Proposisjon. La x ∈ L
K
og la f være et monisk polynom i K[T ]. Da vil
L
K
(f) = K[T ]x
hvis og bare hvis f = f
x
.
Bevis. Ved definisjonen av I
{x}
= (f
x
) vil I
{x}
være kjernen i den surjektive
avbildningen K[T ] → K[T ]x som avbilder g til gx. Derfor har vi en isomorfi
K[T ]/(f
x
) → K[T ]x fra restklasseringen av K[T ] modulo f
x
til K[T ]x. Spesielt
har vektorrommet K[T ]x dimensjon lik graden til f
x
. Av Lemma 2.1 følger det at
dimensjonen til L
K
(f
x
) også er graden til f
x
. Ettersom K[T ]x ⊆ L
K
(f
x
) vil derfor
K[T ]x = L
K
(f
x
). Vi har dermed vist at om f = f
x
så vil L
K
(f) = K[T ]x.
Omvendt, anta at L
K
(f) = K[T ]x. Da vil spesielt fx = 0 så det følger av Lemma
3.3 (1) at f
x
deler f . Vi har alltid at K[T ]x ⊆ L
K
(f
x
), så vi får at L
K
(f) ⊆ L
K
(f
x
).
Derfor følger det av Korollar 2.4 at f deler f
x
. Derfor er f = f
x
, som vi ville vise.
Eksempel V. Vi bruker Eksemplene I-IV for å illustrere Proposisjon 3.4. La u
i L
K
(f) tilsvare sekvensen 0, 0, 1, 1, 0, 0, 1, 1, . . . , så f
u
= f
III
= f. Vi har at de
lineære avbildningene u, T u, T
2
u, T
3
u tilsvarer sekvensene III, IV, VI og V respek-
tive, og at u + T u og T u + T
2
u tilsvarer sekvensene II, respektive VII. Til slutt
svarer u + T
2
u til sekvensen VIII. Vi har derfor at L
K
(f) = K[T ]u som påstått i
Proposisjon 3.4.
La x i L
K
(f) tilsvare sekvensen II: 0, 1, 0, 1, 0, 1, 0, 1, . . . så f
x
= f
II
= T
2
+ 1.
Da vil T
i
x = x for i = 0, 2, 4, . . . og T
i
x = y for i = 1, 3, 5, . . . , der y er den
lineære avbildningen som tilsvarer VII: 1, 0, 1, 0, 1, 0, 1, 0, . . . . Derfor vil K[T ]x =
L
K
(T
2
+ 1) og ikke L
K
(f), som også er påstått i Proposisjon 3.4.
Følgende resultat ble brukt av M. Ward i ulike former og vist over endelige kropper
av N. Zierler [Z].
3.5 Lemma. La f
1
, . . . , f
m
i K[T ] være moniske polynomer.
1. Om f er minste felles multiplum av f
1
, . . . , f
m
vil
L
K
(f) = L
K
(f
1
) + ··· + L
K
(f
m
).
2. Om g er største felles divisor i f
1
, . . . , f
m
vil
L
K
(g) = L
K
(f
1
) ∩ ··· ∩ L
K
(f
m
).
68 Dan Laksov Normat 2/2007
Bevis. (1) Vi har at f
i
deler f så vi får av Korollar 2.4 at L
K
(f
i
) ⊆ L
K
(f) og
derfor en inklusjon L
K
(f
1
) + ··· + L
K
(f
m
) ⊆ L
K
(f).
For å vise den omvendte inklusjonen bruker vi at polynomene f/f
1
, . . . , f/f
m
i
K[T ] er innbyrdes primiske. Det finnes derfor polynomer g
1
, . . . , g
m
i K[T ] slik at
g
1
f/f
1
+···+g
m
f/f
m
= 1. La x ∈ L
K
(f). For hvert i har vi f
i
(g
i
f/f
i
)x = g
i
fx = 0
så (g
i
f/f
i
)x ∈ L
K
(f
i
). Av x = (g
1
f/f
1
)x + ··· + (g
m
f/f
m
)x følger det derfor at
x ∈ L
K
(f
1
) + ··· + L
K
(f
m
), så vi har vist at L
K
(f) ⊆ L
K
(f
1
) + ··· + L
K
(f
m
).
(2) Vi har at g deler f
i
så vi får av Korollar 2.4 at L
K
(g) ⊆ L
K
(f
i
). Derfor har
vi en inklusjon L
K
(g) ⊆ L
K
(f
1
) ∩ ··· ∩ L
K
(f
m
).
For å vise den omvendt inklusjonen bruker vi at polynomene f
1
/g, . . . , f
m
/g er
innbyrdes primiske i K[T ]. Det finnes derfor polynomer h
1
, . . . , h
m
i K[T ] slik at 1 =
h
1
f
1
/g+···+h
m
f
m
/g. La x ∈ L
K
(f
1
)∩···∩L
K
(f
m
). For hvert i har vi g(h
i
f
i
/g)x =
h
i
f
i
x = 0 så (h
i
f
i
/g)x ∈ L
K
(g). Av x = (h
1
f
1
/g)x + ··· + (h
m
f
m
/g)x = 0 ser vi
at x ∈ L
K
(f) så vi har vist at L
K
(f
1
) ∩ ··· ∩ L
K
(f
m
) ⊆ L
K
(g).
Følgende resultat ble vist og brukt av Zierler [Z] over endelige kropper. Spesielt er
da S endelig.
3.6 Setning. La S ⊆ L
K
. Da er S = L
K
(f) for noe monisk polynom f i K[T ]
hvis og bare hvis S er en endelig generert K[T ]-modul.
Bevis. Vi har sett i Lemma 2.1 at om S = L
K
(f) så er S en K[T ]-modul som er
endelig generert som K-modul, og derfor en endelig generert K[T ]-modul.
Omvendt, om S er en endelig generert K[T ]-modul vil S = K[T ]y
1
+···+K[T ]y
m
for noen y
1
, . . . , y
m
i L
K
. La f
i
= f
y
i
. Av Proposisjon 3.4 vil K[T ]y
i
= L
K
(f
i
) for
i = 1, . . . , m. Derfor er S = L
K
(f
1
) + ··· + L
K
(f
m
). Det følger av Lemma 3.5 at
S = L
K
(f) der f er minste felles multiplum av f
1
, . . . , f
m
.
4 Multigrammer
For å illustrere hvordan det duale synspunktet på lineære avbildninger gjør det mu-
lig, og naturlig, å generalisere teorien for løsningene til linære rekursjonsrelasjoner
behandler vi i denne seksjonen multigrammer ganske detaljert.
4.1 Notasjon. La K være en kropp og la f(T ) = T
n
− c
1
T
n−1
+ ··· + (−1)
n
c
n
være i K[T ]. For alle x i L
K
(f) skriver vi
x
i
= x(T
i
) for i = 0, 1, . . . .
4.2 Definisjon. La 0 ≤ l
1
< ··· < l
m
være heltall. Multigrammet
M
f
= M
f
(l
1
, . . . , l
m
)
til L
K
(f) tilsvarende l
1
, . . . , l
m
består av m’tuplene (x
l
1
, . . . , x
l
m
) for alle x i L
K
(f).
Eksempel VI. For å forstå multigrammer er det viktig å se på eksempler. Her
bruker vi de lineære avbildningene i Eksemplene I-V til å gi noen multigrammer
Normat 2/2007 Dan Laksov 69
for ulike m og l
1
, . . . , l
m
. Vi har
M
f
(0, 1, 2) = {(0, 0, 0), (0, 1, 0), (0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (1, 1, 1)}
M
f
(0, 2, 3) = {(0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 0), (1, 0, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1)}
M
f
(0, 2, 4) = {(0, 0, 0), (0, 0, 0), (0, 1, 0), (0, 1, 0), (1, 0, 1), (1, 0, 1), (1, 1, 1), (1, 1, 1)}
M
f
(0, 1) = {(0, 0), (0, 1), (0, 0), (0, 1), (1, 0), (1, 1), (1, 0), (1, 1)}
M
f
(0, 4) = {(0, 0), (0, 0), (0, 0), (0, 0), (1, 1), (1, 1, ), (1, 1, ), (1, 1)}.
4.3 Bemerkning. Vi regner m’tuplene i M
f
med multiplisitet. Det følger av Set-
ning 2.3 at vektorene u, T u, . . . , T
n−1
u genererer L
K
(f). Derfor vil den underlig-
gende mengden til M
f
bestå av rekkerommet til matrisen
(4.3.1)
u
l
1
u
l
2
. . . u
l
m
u
l
1
+1
u
l
2
+1
. . . u
l
m
+1
.
.
.
.
.
.
.
.
.
.
.
.
u
l
1
+n−1
u
l
2
+n−1
. . . u
l
m
+n−1
.
Om vi for hvert m’tuppel (a
1
, . . . , a
m
) i rekkerommet til (4.3.1) skriver
L
f
(a
1
, . . . , a
m
) = {x ∈ L
K
(f) : (x
l
1
, . . . , x
l
m
) = (a
1
, . . . , a
m
)}
så vil det følgelig være en bijeksjon mellom elementene i L
K
(a
1
, . . . , a
m
) og fore-
komsten av m’tuplet (a
1
, . . . , a
m
) i M
f
.
Eksempel VII. Vi gir her matrisene (4.3.1) tilsvarende multigrammene i Eksempel
VI. Betegn matrisen (4.3.1) med U
f
(l
1
, . . . , l
m
). Vi har
U
f
(0, 1, 2) =
0 0 1
0 1 1
1 1 0
U
f
(0, 2, 3) =
0 1 1
0 1 0
1 0 0
U
f
(0, 2, 4) =
0 1 0
0 1 0
1 0 1
U
f
(0, 1) =
0 0
0 1
1 1
U
f
(0, 4) =
0 0
0 0
1 1
4.4 Proposisjon. Vi har at L
f
(0, . . . , 0) er et underrom av L
K
av dimensjon n−r,
der n er graden til f og r er rangen til matrisen (4.3.1). Videre har vi, for hver
lineær avbildning x i L
f
(a
1
, . . . , a
m
), at
L
f
(a
1
, . . . , a
m
) = x + L
f
(0, . . . , 0).
Bevis. La V være rekkerommet til matrisen (4.3.1). Vi har en surjektiv homomorfi
L
K
(f) → V som avbilder x til (x
l
1
, . . . , x
l
m
). Den første delen av proposisjonen
følger av at L
f
(0, . . . , 0) er kjernen i denne avbildningen.
Påstanden i den andre delen er at L
f
(a
1
, . . . , a
m
) er restklassen til x modulo
L
f
(0, . . . , 0) når (x
l
1
, . . . , x
l
m
) = (a
1
, . . . , a
m
). Det er klart at denne påstanden
holder.
70 Dan Laksov Normat 2/2007
4.5 Bemerkning. Av Proposition 4.4 følger det at multiplisiteten til hvert ele-
ment i M
f
er lik antallet elementer i L
f
(0, . . . , 0). Mer presist, for hvert m’tuppel
(a
1
, . . . , a
m
) i rekkerommet til matrisen (4.3.1) er det en bijeksjon mellom medlem-
mene i M
f
som er lik (a
1
, . . . , a
m
) og L
f
(0, . . . , 0).
Ettersom dimensjonen til L
f
(0, . . . , 0) er n−r vil multiplisiteten til hvert element
i M
f
være minimal når r er maksimal, det vil si når r = m.
4.6 Definisjon. Vi sier at multigrammet M
f
= M
f
(l
1
, . . . , l
m
) er skjevt om ran-
gen r til matrisen (4.3.1) er strikt mindre enn m.
Eksempel VIII. Vi bruker Eksemplene I-VII til å illustrere Proposisjon 4.4 og
Bemerkning 4.5, og for å motivere Definisjon 4.6. La m
f
(l
1
, . . . , l
m
) være multipli-
siteten til elementene i M
f
(l
1
, . . . , l
m
) og la r
f
(l
1
, . . . , l
m
) være rangen til matrisen
U
f
(l
1
, . . . , l
m
). Vi får
m (l
1
, l
2
, l
3
) r
f
(l
1
, l
2
, l
3
) n − r
f
(l
1
, l
2
, l
3
) m
f
(l
1
, l
2
, l
3
) m − r
3 (0, 1, 2) 3 0 1 0
3 (0, 2, 3) 3 0 1 0
3 (0, 2, 4) 2 1 2 1
2 (0, 1) 2 1 2 0
2 (0, 4) 1 2 4 1
4.7 Setning. Multigrammet M
f
= M
f
(l
1
, . . . , l
m
) er skjevt hvis og bare hvis det
finnes elementer a
1
, . . . , a
m
i K slik at f deler polynomet g = a
1
T
l
1
+ ···+ a
m
T
l
m
.
Bevis. Ettersom rekkerangen og søylerangen til en matrise sammenfaller er M
f
skjevt hvis og bare hvis søylene i (4.3.1) er lineært avhengige, det vil si, hvis og
bare hvis det finnes elementer a
1
, . . . , a
m
i K slik at
a
1
u
l
1
u
l
1
+1
.
.
.
u
l
1
+n−1
+ ··· + a
m
u
l
m
u
l
m
+1
.
.
.
u
l
m
+n−1
= 0,
eller ekvivalent, a
1
u
l
1
+i
+ ··· + a
m
u
l
m
+i
= 0 for i = 0, . . . , n − 1. Det følger av
Setning 2.3 at de lineære avbildningene u, T u, . . . , T
n−1
u genererer L
K
(f). Derfor
vil
a
1
x
l
1
+i
+ ··· + a
m
x
l
m
+i
= 0 for i = 0, 1, . . . for alle x ∈ L
K
(f).
Dette betyr at x er i L
K
(g) for alle x ∈ L
K
(f), det vil si, L
K
(f) ⊆ L
K
(g). Men
ved Korollar 2.4 er L
K
(f) ⊆ L
K
(g) ekvivalent med at f deler g. Vi har derfor vist
at M
f
er skjevt hvis og bare hvis det finnes a
1
, . . . , a
m
slik at L
K
(f) ⊆ L
K
(g) med
g = a
1
T
l
1
+ ··· + a
m
T
l
m
.
Normat 2/2007 Dan Laksov 71
4.8 Bemerkning. Ordet multigram ble innført av Selmer i tilfellet da K er en
endelig kropp. Om K har q elementer består da multigrammet M
f
av q
n
vektorer,
innregnet multiplisiteten. Rekkerommet til matrisen (4.3.1) består av q
r
vektorer
der r er rangen til matrisen, så multiplisiteten til hver vektor er q
n−r
. Når M
f
ikke
er skjev vil multiplisiteten derfor være q
n−m
.
Setningen 4.7 ble funnet eksperimentelt av Selmer og bevist i [L1] og [L2] (se
også [S]).
Eksempel IX. Vi viser at Eksempel VIII er en utmerket illustrasjon på Setning
4.7. Polynomet f = T
3
− T
2
+ T − 1 deler opplagt ikke polynomene på formen
a
1
+a
2
T +a
3
T
3
, eller b
1
+b
2
T . Dette betyr av Setning 4.7 at M
f
(0, 2, 3), respektive
M
f
(0, 1) ikke er skjeve, hvilket vi også ser av tabellen i Eksempel VII.
På den annen side er T
4
− 1 = (T − 1)(T
3
− T
2
+ T − 1) så f deler T
4
− 1. Av
Setning 4.7 betyr dette at M
f
(0, 2, 4) og M
f
(0, 4) er skjeve, hvilket bekreftes av
tabellen i Eksempel VII.
5 Periodiske sekvenser
I de arbeidene vi refererer til er de lineære sekvensene gitt over den endelige kroppen
GF(q) med q elementer. Alle sekvensene som tilfredsstiller en lineær rekursjon blir
da periodisk fra et visst punkt av. Dette spiller en stor rolle for teknikkene og
teorien i disse arbeidene. Som vi har observert spiller dette ikke noen rolle i vår
teori. Det kan imidlertid være vært å nevne periodisitet for å se relasjonen mellom
presentasjonen av lineære rekursjonsrelasjoner her og den i tidligere arbeider. I det
følgende setter vi for hver x i L
A
(0),
x
i
= x(T
i
) for i = 0, 1, . . . .
5.1 Definisjon. Et element x ∈ L
A
(0) er har preperiode m og en periode q om
x
i+q
= x
i
for i ≥ m.
Det minste positive tallet q som er en periode kalles perioden for x, og om m = 0
sier vi at x er periodisk.
5.2 Lemma. Om q er en periode for en sekvens x i L
A
(0) med periode p vil p dele
q.
Bevis. Vi har x
i+p
= x
i
for i ≥ m
p
og x
i+q
= x
i
for i ≥ m
q
for noen preperioder
m
p
og m
q
, og q ≥ p. Skriv q = sp + r med q og r heltall og 0 ≤ r < p. Vi får for
i ≥ maks(m
p
, m
q
) at x
i+r
= x
i+r+sp
= x
i+q
= x
i
. Derfor er r enten lik 0 eller r er
en periode. Men p var den minste perioden så r = 0. Det vil si, p deler q.
5.3 Lemma. Sekvensen x i L
A
(0) har preperiode m og en periode q hvis og bare
hvis x ∈ L
A
(T
m
(T
q
− 1)). Spesielt er x ∈ L
A
.
Bevis. Betingelsen x
i+q
= x
i
for i ≥ m kan klart skrives som T
m
(T
q
−1)x = 0 fordi
dette betyr at T
m+q
x(T
i
) = T
m
x(T
i
), eller x
m+q +i
= x
m+i
for i = 0, 1, . . . .
72 Dan Laksov Normat 2/2007
5.4 Proposisjon. Om u i L
A
(f) har preperiode m og periode q så har alle sekven-
sene i L
A
(f) preperiode m og periode q.
Bevis. Proposisjonen følger av at elementene u, T u, . . . , T
n−1
u ifølge Setning 2.3
genererer A-moduler L
A
(f), og alle disse elementene har en preperiode m og en
periode q.
5.5 Proposisjon. La f = T
n
−c
1
T
n−1
+ ···+ (−1)
n
c
n
og anta at alle sekvensene
x i L
A
(f) har en preperiode m
x
og en periode q
x
. Da er alle sekvensene i L
A
(f)
periodiske hvis og bare hvis c
n
ikke er en null divisor, det vil si ac
n
= 0 medfører
at a = 0.
Bevis. La x være en lineær avbildning i L
A
(f) og la m = m
x
være den minste
preperioden for x og la q = q
x
være en periode. Vi skal vise at m = 0. Anta at m >
0. Ettersom x
i+q
= x
i
for i = m, m + 1, . . . får vi av x
n+m−1+q
−c
1
x
n+m−1+q −1
+
··· + (−1)
n−1
c
n−1
x
m+q
+ (−1)
n
c
n
x
m−1+q
= 0 at x
n+m−1
− c
1
x
n+m−2
+ ··· +
(−1)
n−1
c
n−1
x
m
+ (−1)
n
c
n
x
m−1+q
= 0.
På den annen side har vi
x
n+m−1
− c
1
x
n+m−2
+ ··· + (−1)
n−1
c
n−1
x
m
+ (−1)
n
c
n
x
m−1
= 0.
Det følger at c
n
x
m−1+q
= c
n
x
m−1
. Antar vi derfor at c
n
ikke er en nulldivisor får
vi at x
m−1+q
= x
m−1
. Derfor er x
i+q
= x
i
for i = m − 1, m, . . . så m − 1 er en
preperiode. Men dette motsier antagelsen at m = m
x
er den minste preperioden
for x. Derfor er m
x
= 0 som vi ville vise.
Omvendt, anta at c
n
er en nulldivisor, og la a 6= 0 i A være slik at ac
n
= 0.
Da vil a, 0, 0, . . . være en sekvens som svarer til en linearavbildning x i L
A
(f), og
denne lineæravbildningen har minste preperiode 1 og periode 1.
Eksempel X. I alle Eksemplene I-V har vi en kropp K med to elementer og c
n
= 1.
Derfor er alle lineære avbildningene i disse eksemplene periodiske.
6 Relasjon til andre metoder
Det duale synspuktet på lineære rekursjonsrelasjoner passer vel inn med tidligere
metoder. Her gir vi de eksakte relasjonene mellom metodene.
6.1 Potensrekker. Vi betegner med A[[T ]] de formelle potensrekkene a
0
+ a
1
T +
··· i den variable T med koeffisienter i den kommutative ringen A med enhet.
Potensrekkene adderes komponentvis og multiplikasjonen er den vanlige
(a
0
+a
1
T +···)(b
0
+b
1
T +···) = a
0
b
0
+(a
1
b
0
+a
0
b
1
)T +(a
2
b
0
+a
1
b
1
+a
0
b
2
)T
2
+··· .
Det er vært å merke seg at vi kan dividere med alle potensrekker a
0
+ a
1
T + ···
der a
0
er invertibel i A. Dette sees ved ren utregning, det vil si, vi prøver
(a
0
+ a
1
T + ···)(x
0
+ x
1
T + ···) = 1
Normat 2/2007 Dan Laksov 73
og får ligninger a
0
x
0
= 1 og
x
i
a
0
+ x
i−1
a
1
+ ··· + x
0
a
i
= 0 for i = 1, 2, . . . ,
for x
0
, x
1
, . . . . Disse har klart en entydig løsning for x
0
, x
1
, . . . når a
0
, a
1
, . . . er gitt
og a
0
er invertibel. For eksempel vil
x
0
= a
−1
0
, x
1
= −a
−2
0
a
1
, x
2
= a
−3
0
(a
2
1
− a
0
a
2
), x
3
= −a
−4
0
(a
3
1
− 2a
0
a
1
a
2
+ a
2
0
a
3
).
6.2 Potensrekker og sekvenser. De fleste metodene for å behandle lineære re-
kursjoner bruker at det er en entydig korrespondanse mellom sekvenser av elemen-
ter i A og formelle potensrekker med koeffisienter i A, ved at sekvensen x
0
, x
1
, . . .
svarer til den formelle potensrekken x
0
+ x
1
T + ···. Tilsvarende har vi en bijeksjon
L
K
(0) ←→ A[[T ]]
som avbilder x til x
T
= x(1) + x(T )T + x(T
2
)T
2
+ ···. I det følgende skal vi, for
hver x ∈ L
K
(0), skrive
x(T
i
) = x
i
for i = 0, 1, . . . .
6.3 Bemerkning. Med notasjonen i Seksjon 2.2 setter vi
u
f
= u = (u
0
, u
1
, . . . ) = (0, . . . , 0, 1, s
1
, s
2
, . . . )
med n − 1 nuller i begynnelsen. Da kan relasjonen fu = 0 skrives som
(1 − c
1
T + ··· + (−1)
n
c
n
T
n
)(1 + s
1
T + s
2
T
2
+ ···) = 1.
Dette er samme relasjon som gir sammenhengen mellom Chern klasser og Segre
klasser i geometrien. Dette forklarer vår lett bisarre notasjon for lineære rekursjoner
med alternerende fortegn.
6.4 Potensrekker og lineær rekursjon. La
f(T ) = T
n
− c
1
T
n−1
+ ··· + (−1)
n
c
n
være i A[T ]. Vi har
(1 − c
1
T + ··· + (−1)
n
c
n
T
n
)(x
0
+ x
1
T + x
2
T
2
+ ···)
= x
0
+ (x
1
− c
1
x
0
)T + (x
2
− c
1
x
1
+ c
2
x
0
)T
2
+ ···
+ (x
n−1
− c
1
x
n−2
+ ··· + (−1)
n−1
c
n−1
x
0
)T
n−1
+ (x
n
− c
1
x
n−1
+ ··· + (−1)
n
c
n
x
0
)T
n
+ ··· .
Gitt a
0
+ a
1
T + ··· i A[[T ]]. Ligningene
x
0
= a
0
, x
1
− c
1
x
0
= a
1
, x
2
− c
1
x
1
+ c
2
x
0
= a
2
, . . . ,
x
n−1
− c
1
x
n−2
+ ··· + (−1)
n−1
c
n−1
x
0
= a
n−1
,
x
n
− c
1
x
n−1
+ ··· + (−1)
n
c
n
x
0
= a
n
, . . .
74 Dan Laksov Normat 2/2007
har klart en entydig løsning i x
0
, x
1
, . . . . Derfor vil avbildningen
(6.4.1) L
K
(0) → A[[T ]]
som avbilder x til (1 − c
1
T + ··· + (−1)
n
c
n
T
n
)x
T
være en bijeksjon. Videre ser vi
at denne bijeksjonen induserer en bijeksjon
L
K
(f) ←→ {polynomer av grad høyst n − 1 i A[T ]}.
6.5 Ward and Halls metoder. Den metoden som ofte ble anvendt av M. Hall
[H1]–[H2] og Ward [W1]–[W4] bruker isomorfien
A[T ]/(f) → L
A
(f)
som avbilder restklassen til a
0
T
n−1
+ ···+ a
n−1
til den lineære avbildningen x som
tilfredsstiller
(6.5.1) (1 + c
1
T + ··· + (−1)
n
c
n
T
n
)x
T
= a
0
+ a
1
T + ··· + a
n−1
T
n−1
.
6.6 Zierlers metode. Metoden som Zierler bruker [Z] bygger direkte på korre-
spondansen (6.4.1) mellom sekvenser og potensrekker. Det viktigste verktøyet er
relasjonen
(a
0
+ a
1
T + ··· + a
n−1
T
n−1
)/(1 − c
1
T + ··· + (−1)
n
c
n
T
n
) = x
0
+ x
1
T + x
2
T
2
···
i 6.4 mellom polynomer av grad høyst n − 1 og potensrekker.
6.7 Petersons metode. Denne metoden ble brukt av Peterson i [P] og danner
også det teoretiske grunnlaget for arbeidene [L1] og [L2]. Metoden fungerer best
for periodiske sekvenser. Vi antar derfor at alle sekvensene i L
K
(f) er periodiske
med en periode p, det vil si, x
i+p
= x
i
for i = 0, 1, . . . . For x ∈ L
K
(f) har vi da
x
T
= (x
0
+ x
1
T + ··· + x
p−1
T
p−1
)/(1 − T
p
).
Substituerer vi dette i (6.5.1) får vi
(6.7.1) (a
0
+ a
1
T + ··· + a
n−1
T
n−1
)(1 − T
p
)
= (1 − c
1
T + ··· + (−1)
n
c
n
T
n
)(x
0
+ x
1
T + ··· + x
p−1
T
p−1
).
Substituerer vi 1/T for T i (6.7.1) og tar bort overflødige nevnere får vi
(6.7.2) (T
p
− 1)(a
0
T
n−1
+ a
1
T
n−2
+ ··· + a
n−1
)
= f(T )(x
0
T
p−1
+ x
1
T
p−2
+ ··· + x
p−1
).
Ettersom vi har antatt at alle elementene i L
K
(f) er periodiske med periode p vil
f dele polynomet T
p
−1, så vi får T
p
−1 = fg med g i A[T ]. Substituerer vi dette
i (6.7.2) og forkorter med f får vi
g(T )(a
0
T
n−1
+ a
1
T
n−2
+ ··· + a
n−1
) = x
0
T
p−1
+ x
1
T
p−2
+ ··· + x
p−1
.
Normat 2/2007 Dan Laksov 75
Det er klart at denne relasjonen gir en bijeksjon
(g)/(T
p
− 1) → L
A
(f)
mellom elementene i idealet i A[T]/(T
p
−1) generert av restklassen til g og L
A
(f)
ved at klassen til g(a
0
T
n−1
+ a
1
T
n−2
+ ···+ a
n−1
) avbildes til elementet x i L
A
(f)
bestemt av x
T
= (x
0
+ x
1
T + ··· + x
p−1
T
p−1
)/(1 − T
p
).
6.8 Klassisk metode. Denne metoden bygger på partialbrøkoppspaltning. Etter-
som denne er velkjent og notasjonsmessig litt komplisert skal vi bare skisse meto-
den. Vi antar at f(T) = (T − b
1
)
m
1
···(T − b
r
)
m
r
er en oppspalting av polynomet
f og at vi har en partialbrøkoppspaltning
1/f(T ) = g
1
(T )/(T − b
1
)
m
1
+ ··· + g
r
(T )/(T − b
r
)
m
r
.
En slik oppspaltning finnes alltid når A er en kropp, eventuelt efter å ha utvi-
det kroppen så f(T ) splitter fullstendig. Ved å substituere 1/T for T og ta bort
overflødige nevnere i T får vi
1/(1 − c
1
T + ···+ (−1)
n
c
n
T
n
) = h
1
(T )/(1 − b
1
T )
m
1
+ ··· + h
r
(T )/(1 − b
r
T )
m
r
= h
1
(T )(1 + b
1
T + b
2
1
T
2
+ ···)
m
1
+ ··· + h
r
(T )(1 + b
r
T + b
2
r
T
2
+ ···)
m
r
for noen polynomer h
1
, . . . , h
r
. Multiplisert med polynomet a
0
+a
1
T +···+a
n−1
T
n−1
gir dette x
T
uttykt som potenssummer i røttene b
1
, . . . , b
r
. Vi gir ingen detaljer,
men påminner om Fibonacci tallene 1, 1, 2, 3, 5, 8, . . . , gitt av den lineære rekursjo-
nen med karakteristisk polynom T
2
− T −1. Vi har
f(T ) = T
2
− T −1 = (T −
1 +
√
5
2
)(T −
1 −
√
5
2
) = (T −α)(T − β).
Dette gir
1/(1 − T −T
2
) = (1/(α − β)) (α/(1 − T α) − β/(1 − T β))
=
∞
X
i=0
(α
i+1
− β
i+1
)/(α − β)
T
i
.
6.9 Kompanjongmatrisen. Vi kaller n × n-matrisen
C =
0 0 . . . 0 (−1)
n+1
c
n
1 0 . . . 0 (−1)
n
c
n−1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 . . . 0 −c
2
0 0 . . . 1 c
1
for kompanjongmatrisen til polynomet f (T ) = T
n
−c
1
T
n−1
+···+ (−1)
n
c
n
. Denne
matrisen har karakteristisk polynom f(T ) og vi ser at
(6.9.1) (x
i
, x
i+1
, . . . , x
n+i−1
)C
= (x
i+1
, x
i+2
, . . . , x
n+i−1
, x
n+i−1
c
1
− x
n+i−2
c
2
+ ··· + (−1)
n+1
x
i
c
n
)
76 Dan Laksov Normat 2/2007
slik at vi får de suksessive verdiene i sekvensen x
0
, x
1
, . . . ved multiplikasjon med
kompanjongmatrisen.
6.10 Matrisemetoden. Cayley-Hamilton’s sats sier at hver n ×n-matrise A med
karakteristisk polynom f(T ) tilfredsstiller ligningen
A
n
− c
1
A
n−1
+ ··· + (−1)
n
c
n
I
n
= 0
slik at
A
n+i
− c
1
A
n+i−1
+ ··· + (−1)
n
c
n
A
i
= 0.
Ettersom sporet tr(A) = tr(a
ij
) = a
11
+ ··· + a
nn
av en matrise er additiv, det vil
si tr( A + B) = tr(A) + tr(B), har vi at
tr(A
n+i
) − c
1
tr(A
n+i−1
) + ··· + (−1)
n
c
n
tr(A
i
) = 0.
Det vil si,
(6.10.1) tr(A
0
), tr(A), tr(A
2
), . . .
er en løsning til den lineære rekursjonen med karakteristisk polynom f(T ).
Vi merker at når A har koeffisienter i en kropp K og f(T ) splitter fullstendig i en
overkropp som f(T ) = (T −b
1
) ···(T −b
n
) så er løsningen (6.10.1) nær beslektet til
den klassiske metoden i 6.8. Dette er fordi det følger av Spektralavbildningssatsen
[LST] at det karakteristiske polynomet for A
i
er (T −b
i
1
) ···(T −b
i
n
), slik at tr(A
i
) =
b
i
1
+ ··· + b
i
n
. Sekvensen (6.10.1) blir altså
b
0
1
+ ··· + b
0
n
, b
1
+ ··· + b
n
, b
2
1
+ ··· + b
2
n
, . . . .
Et spesialtilfelle av matrisemetoden får vi når vi har en kropp K, en overkropp L, og
en basis med n elementer for L betraktet som et vektorrom over K. Multiplikasjon
med et element b i L gir da, relativt til denne basen, en matrise A
b
. Sporet til A
b
er, per definisjon, sporet tr(b) til b. Sekvensen (6.10.1) blir
tr(b
0
), tr(b
1
), tr(b
2
), . . .
som er en løsning til den lineære rekursjonen med karakteristisk polynom lik mini-
malpolynomet for b over K. Arnfinn Laudal forteller at denne løsningen, for endelige
kroppsutvidelser, var kjent for gruppen rundt ham i Forsvarsstaben i Norge på 60-
tallet, og så vidt han kan huske, skyldes John Johnsen.
6.11 Bemerkning. Sekvensen (6.10.1) gir ikke nødvendigvis interessante løsnin-
ger til den lineære rekursjonen med karakteristisk polynom lik det karakteristiske
polynomet til A.
La K = {0, 1} være kroppen med to elementer og la C =
0 −1
1 0
være kom-
panjongmatrisen til polynomet T
2
+ 1. Vi har C
2
=
−1 0
0 −1
så tr(C
i
) = 0 for
i = 0, 1, . . . , og sekvensen (6.10.1) bli null sekvensen 0, 0, 0, . . . .
Normat 2/2007 Dan Laksov 77
Referanser
[H1] Marshall Hall. An isomorphism between linear recurring sequences and al-
gebraic rings, Trans. Amer. Math. Soc. 44 (1938). 196–218.
[H2] Marshall Hall. A survey of difference sets. Proc. Amer. Math. Soc.7 (1956).
975–986.
[L1] Dan Laksov. Lineær rekursjon Master Thesis. University of Bergen 1964.
[L2] Dan Laksov. Linear recurring sequences over finite fields. Math. Scand. 16
(1965). 181–196.
[LST] Dan Laksov, Lars Svensson & Anders Thorup The Spectral Mapping
Theorem, norms on rings, and resultants. L’Enseignement Mathématique
46 (2000) 349-358.
[P] Peterson, W. Wesley. Error-correcting codes The M.I.T. Press, Cambridge,
Mass. John Wiley & Sons, Inc. New York-London 1961.
[S] Ernst S. Selmer. Linear recurrence relations over finite fields. Mimeograph-
ed notes. Department of Mathematics, Bergen 1966.
[V] N.N. Vorobyov. The Fibonacci numbers. Translated and adapted from the
first Russian edition (1951) by Norman D. Whaland, Jr., and Olga A. Titel-
baum. Survey of Recent East European Mathematical Literature, a project
conducted by Alfred L. Putnam and Izaak Wirszup. Topics in Mathematics
D. C. Heath and Co. Boston, Mass. 1963.
[VS] Välj specialarbete i matematik. Institut Mittag-Leffler. Djursholm, Sweden
1960.
[W1] Morgan Ward. The algebra of recurring series. Ann. of Math.32 (1931). 1–9.
[W2] Morgan Ward. The characteristic number of a sequence of integers satisfying
a linear recursion relation. Trans. Amer. Math. Soc. 33 (1931). 153–165.
[W3] Morgan Ward. Some arithmetical properties of sequences satisfying a linear
recursion relation. Ann. of Math. 32 (1931).734–738.
[W4] Morgan Ward. The arithmetical theory of linear recurring series. Trans.
Amer. Math. Soc. 35 (1933). 600–628.
[Z] Zierler, Neal. Linear recurring sequences. J. Soc. Indust. Appl. Math. 7
(1959). 31–48.
