On The Theory of Partial Difference Equations: From Numerical Methods to the Language of Complexity

On he Theo y o Pa ial Di e ence Equa ions:
F om Nume ical Me hods o he Language o
Complexi y
Bik Kuang Min
Depa men o Ma hema ical Sciences, Facul y o Science and Technology,
Uni e si i Kebangsaan Malaysia (UKM), Bangi, Selango , Malaysia
Email: [email p o ec ed]
ORCID: 0009-0009-8368-3858
12 Sep embe 2025
Abs ac
This monog aph de elops a comp ehensi e and uni ied heo y o linea
and nonlinea pa ial di e ence equa ions (P∆E), ex ending hem a be-
yond hei adi ional ole in nume ical analysis. We es ablish a igo ous
ma hema ical amewo k ha connec s disc e e analysis, combina o ics,
ope a o heo y, Fou ie me hods, unc ional analysis, and he heo y o
dynamical sys ems.
We begin by in oducing he ounda ions o P∆Es: disc e e unc ions
and shi s, he classi ica ion o equa ions (linea , semilinea , quasilinea ,
ully nonlinea ), and he basic egula i y p ope ies o disc e e solu ions.
A ull ope a o – heo e ic se ing is de eloped h ough disc e e unc ion
spaces (Banach, Hilbe , Lp, Schwa z, and ini e–suppo spaces), ad-
join heo y, and spec al p ope ies o disc e e Laplacians—including he
Moo e Laplacian in highe dimensions. Fundamen al ools o unc ional
analysis such as he Hahn–Banach heo em, he Riesz ep esen a ion he-
o em, compac ness p inciples, and Banach ixed poin heo y a e es ab-
lished in he disc e e se ing.
G een’s unc ions a e cons uc ed sys ema ically, showing how classi-
cal combina o ial s uc u es—binomial, mul inomial, and S i ling num-
be s—a ise na u ally as undamen al solu ions o P∆Es. Disc e e Fou ie
se ies and ans o ms a e de eloped in de ail, including Pa se al’s iden-
i y and he use o disc e e symbols (Lau en polynomials) o analyze
well–posedness and classi y second–o de equa ions.
Explici classes o equa ions a e sol ed using disc e e analogues o
sepa a ion o a iables, Fou ie in eg als, and semig oup me hods. These
include i s –o de e olu ion equa ions, disc e e hea and wa e equa ions,
and a wide amily o highe –dimensional linea models whose solu ions
a e exp essed h ough mul inomial e olu ion ke nels.
1
Nonlinea P∆Es a e hen in oduced, wi h pa icula a en ion o
mod-nnonlinea i ies. These equa ions p oduce exac ac al solu ions
such as he Sie pinski iangle, ca pe , and py amid, and lead o he con-
cep ual p oposal ha ac als can be ega ded as solu ions o e olu ion
equa ions.
The heo y is comple ed wi h a sys ema ic ea men o sys ems o
P∆Es, w i en in e olu ion o m , and wi h an a las o nonlinea models in-
cluding cellula au oma a, sandpile dynamics, disc e e di usion– eac ion
sys ems, and disc e e analogues o luid equa ions.
O e all, his monog aph e ames pa ial di e ence equa ions as a un-
damen al language o disc e e dynamics, complex sys ems, and ac al
e olu ion, ad ancing hem om hei nume ical o igins o a b oad ma h-
ema ical heo y capable o desc ibing sel –o ganiza ion and complexi y.
Keywo ds: pa ial di e ence equa ions; di e ence equa ions; G een’s unc-
ion; unc ional analysis; disc e e dynamical sys ems; Fou ie ans o m; com-
bina o ics; ac als
2
Con en s
P e ace 6
1 In oduc ion o Pa ial Di e ence Equa ions 7
1.1 Mo i a ion and Backg ound . . . . . . . . . . . . . . . . . . . . . 7
1.2 Disc e eFunc ion........................... 8
1.3 Ope a o s............................... 8
1.4 O dina y Di e ence Equa ions . . . . . . . . . . . . . . . . . . . 9
1.5 Pa ial Di e ence Equa ions . . . . . . . . . . . . . . . . . . . . . 10
1.6 The O de o a Pa ial Di e ence Equa ion . . . . . . . . . . . . 10
1.7 Classi ica ion and Examples . . . . . . . . . . . . . . . . . . . . . 12
1.8 No a ions ............................... 13
1.9 No a ion E olu ion . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 In oduc ion o Linea Pa ial Di e ence Equa ions 15
2.1 De ini ion ............................... 15
2.2 Disc e e 1D T anspo Equa ion . . . . . . . . . . . . . . . . . . 16
2.3 3D Disc e e T anspo Equa ion . . . . . . . . . . . . . . . . . . 18
2.4 Exis ence and Uniqueness o Solu ions o P∆E . . . . . . . . . . 19
3 Disc e e Func ion Spaces and Ope a o s 20
3.1 In oduc ion.............................. 20
3.2 Disc e e Func ion Spaces . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Typeso Ope a o s.......................... 25
3.4 Ope a o Theo y ........................... 30
4 Disc e e Func ionals and Con e gence 39
4.1 In oduc ion.............................. 39
4.2 Disc e e Func ionals . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Compac ness o he Uni Ball in Disc e e Func ion Spaces . . . . 40
4.4 Hahn–Banach Theo em . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Riesz Rep esen a ion Theo em . . . . . . . . . . . . . . . . . . . 42
4.6 Banach Fixed Poin Theo em . . . . . . . . . . . . . . . . . . . . 43
4.7 Types o Con e gence . . . . . . . . . . . . . . . . . . . . . . . . 43
5 The Disc e e G een’s Func ion 45
5.1 The K onecke Del a Func ion . . . . . . . . . . . . . . . . . . . 45
5.2 Fundamen al Solu ion . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3 The Disc e e G een’s Func ion . . . . . . . . . . . . . . . . . . . 47
6 Disc e e Fou ie T ans o m 49
6.1 Mo i a ion and Backg ound . . . . . . . . . . . . . . . . . . . . . 49
6.2 Disc e e Fou ie Se ies . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Inne P oduc and O hogonali y . . . . . . . . . . . . . . . . . . 49
6.4 Disc e e Fou ie T ans o m . . . . . . . . . . . . . . . . . . . . . 50
6.5 Pa se al’s Iden i y . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3
6.6 Jus i ica ion o he Fou ie Ansa z o Linea P∆E . . . . . . . . 52
6.7 Classi ica ion o Second O de Linea P∆E . . . . . . . . . . . . 52
6.8 Disc e e Fou ie Analysis and Hadama d’s Well-posedness . . . . 55
7 Fi s O de Equa ions in Time 57
7.1 In oduc ion.............................. 57
7.2 1D Pascal E olu ion Equa ion . . . . . . . . . . . . . . . . . . . . 57
7.3 1D Disc e e Hea Equa ion . . . . . . . . . . . . . . . . . . . . . 60
7.4 S i ling Second Equa ion . . . . . . . . . . . . . . . . . . . . . . . 63
8 Second O de Equa ions in Time 65
8.1 In oduc ion.............................. 65
8.2 Second–O de Pascal E olu ion Equa ion . . . . . . . . . . . . . 65
8.3 Disc e e 1D Wa e Equa ion . . . . . . . . . . . . . . . . . . . . . 68
9 S eady S a e P oblems 71
9.1 In oduc ion.............................. 71
9.2 2D Disc e e Laplace Equa ion . . . . . . . . . . . . . . . . . . . . 72
9.3 2D Disc e e Poisson Equa ion . . . . . . . . . . . . . . . . . . . . 74
9.4 Two-Dimensional Moo e Laplace Equa ion . . . . . . . . . . . . . 76
9.5 Lis o Disc e e E olu ion Equa ions . . . . . . . . . . . . . . . . 79
9.6 Lis o S eady S a e P oblems . . . . . . . . . . . . . . . . . . . . 81
10 Disc e e E olu ion Equa ions 83
10.1In oduc ion.............................. 83
10.2De ini ions............................... 83
10.3Semig oupTheo y .......................... 88
10.4 Ini ial Value P oblems . . . . . . . . . . . . . . . . . . . . . . . . 89
10.5 Bounda y Value P oblems . . . . . . . . . . . . . . . . . . . . . . 90
10.6 Ini ial-Bounda y Value P oblems . . . . . . . . . . . . . . . . . . 92
10.7 Au onomous and Non–Au onomous Sys ems . . . . . . . . . . . . 93
11 Highe Dimensional P oblems 95
11.1In oduc ion.............................. 95
11.2 2D Pascal E olu ion Equa ion . . . . . . . . . . . . . . . . . . . . 95
11.3 3D Pascal E olu ion Equa ion . . . . . . . . . . . . . . . . . . . . 96
11.4 n-Dimensional Pascal E olu ion Equa ion . . . . . . . . . . . . . 98
12 Nonlinea Equa ions wi h mod n Nonlinea i y 100
12.1In oduc ion..............................100
12.2 Righ –Side Sie pinski T iangle Equa ion . . . . . . . . . . . . . . 100
12.3 Sie pinski Ca pe Equa ion . . . . . . . . . . . . . . . . . . . . . 104
12.4 Sie pinski Py amid Equa ion . . . . . . . . . . . . . . . . . . . . 105
12.5 Sie pinski Fan Equa ion . . . . . . . . . . . . . . . . . . . . . . . 110
12.6 Mod 5 Sie pi´nski Equa ion . . . . . . . . . . . . . . . . . . . . . . 111
12.7 Mod 4 Sie pinski F ac al Equa ion . . . . . . . . . . . . . . . . . 112
4
12.8 F ac als as Solu ions o E olu ion Equa ions . . . . . . . . . . . 114
13 Sys em o Pa ial Di e ence Equa ions 115
13.1In oduc ion..............................115
13.2 Classi ica ion o P∆E Sys ems . . . . . . . . . . . . . . . . . . . 115
13.3Linea Sys ems ............................119
13.4 Cons an Coe icien Linea P∆E Sys em . . . . . . . . . . . . . 122
13.5 Non-homogeneous Linea Sys em . . . . . . . . . . . . . . . . . . 125
13.6 Semilinea Sys ems . . . . . . . . . . . . . . . . . . . . . . . . . . 126
14 A las o Nonlinea Pa ial Di e ence Equa ions 128
14.1In oduc ion..............................128
14.2 Elemen a y Cellula Au oma a . . . . . . . . . . . . . . . . . . . 131
14.3 Abelian Sandpile Model . . . . . . . . . . . . . . . . . . . . . . . 140
14.4 Ku amo o Fi e ly Model . . . . . . . . . . . . . . . . . . . . . . . 143
14.5IsingModel..............................145
14.6 Disc e e Logis ic Di usion Equa ion . . . . . . . . . . . . . . . . 146
14.7 Bac e ial Colony Model . . . . . . . . . . . . . . . . . . . . . . . 155
14.8 Disc e e Na ie –S okes Equa ions . . . . . . . . . . . . . . . . . . 161
15 Summa y 165
15.1 F om Nume ical Me hods o he Language o Complexi y . . . . 165
15.2 Limi a ions and Fu u e Wo k . . . . . . . . . . . . . . . . . . . . 166
Acknowledgemen s 167
Re e ences 168
5

P e ace
Since en e ing uni e si y, I ha e been deeply in e es ed in modeling biological
e olu ion h ough ma hema ics. My ini ial a emp s ocused on g aph heo y,
bu I soon encoun e ed limi a ions— o ins ance, classical g aph- heo e ic ap-
p oaches could no adequa ely cap u e phenomena such as ing species. I hen
u ned o pa ial di e en ial equa ions (PDE), hoping o desc ibe con inuous
p ocesses such as cellula di ision, bu again ound ha PDEs we e insu icien
o model disc e e s uc u al ans o ma ions such as su ace spli ing.
These ailu es g adually led me o a new pe spec i e. Biological sys ems a e,
a hei co e, disc e e in bo h space and ime: molecules, cells, and indi iduals
a e disc e e en i ies, and ep oduc ion occu s ac oss gene a ions. This sugges ed
ha di e en ial equa ions migh no be he mos na u al amewo k o such
sys ems. Ins ead, one should u n o di e ence equa ions.
A i s , I was unsu e how o o mula e pa ial di e ence equa ions in a
sys ema ic way. The b eak h ough came when I ecognized ha classical mod-
els om complex sys ems science—such as he Game o Li e and he Sand-
pile Model—can, in ac , be na u ally exp essed as pa ial di e ence equa ions.
These models sha e he same essen ial s uc u e: dynamics de ined on disc e e
space and disc e e ime. F om his pe spec i e, jus as PDEs desc ibe he e olu-
ion o con inuous ields, pa ial di e ence equa ions can be iewed as desc ibing
he e olu ion o disc e e ields.
This ealiza ion mo i a ed me o sys ema ically ein e p e a wide a ie y
o disc e e models—including cellula au oma a, combina o ial ecu sions, and
e olu iona y dynamics—wi hin a single analy ic amewo k ha I call Disc e e
Field Theo y. The aim o his amewo k is no me ely o p o ide ano he
modeling echnique, bu o uni y di e se phenomena unde a language inspi ed
by he analysis o PDE, en iched by ools om unc ional analysis, ope a o
heo y, and spec al heo y.
This wo k ep esen s only a i s s ep. The heo y is a om comple e, and
much emains o be de eloped and e ined. I hope ha by p esen ing hese ideas,
I can in i e u he explo a ion and collabo a ion. My goal is o p o ide no a
inished solu ion, bu a he a s a ing poin o a b oade esea ch p og am in
he analysis o disc e e dynamical sys ems.
6
1 In oduc ion o Pa ial Di e ence Equa ions
1.1 Mo i a ion and Backg ound
O e he pas yea , he au ho has eleased se e al p ep in s [4–6] aiming o
desc ibe a wide ange o complex sys ems, including cellula au oma a, sandpile
models, and o he disc e e dynamical p ocesses, wi hin a single uni ied ame-
wo k based on pa ial di e ence equa ions (P∆Es). These wo ks demons a ed
ha many classical models o complexi y, o en s udied independen ly in com-
pu e science, combina o ics, physics, o nonlinea dynamics, may in ac be
exp essed as explici e olu ion equa ions buil om shi and di e ence ope a-
o s.
Howe e , despi e hese applica ions, a comple e and igo ous ma hema ical
ounda ion o such equa ions was s ill missing. The p esen monog aph is
he e o e de o ed o es ablishing a comp ehensi e heo y o pa ial di e ence
equa ions: including hei analy ic amewo k, unc ion spaces, ope a o heo y,
Fou ie analysis, G een’s unc ions, classi ica ion, well-posedness, and me hods
o solu ion. Ou goal is o c ea e a sys ema ic and sel -con ained ea men
compa able in scope and s uc u e o he classical heo y o pa ial di e en ial
equa ions.
The au ho ini ially a i ed a his subjec independen ly. By analyzing well-
known cellula au oma a such as Conway’s Game o Li e, he Abelian Sandpile
Model, and a ious coupled-map la ice sys ems, i became e iden ha each
could be w i en na u ally as a pa ial di e ence equa ion in space and ime.
Sea ching he li e a u e o “Pa ial Di e ence Equa ions” sugges ed ha he
e m exis ed, bu almos exclusi ely in he nume ical analysis communi y, whe e
i e e ed o ini e-di e ence schemes o app oxima ing PDEs. This was en-
i ely di e en om he highe -dimensional in insic di e ence equa ions con-
side ed he e.
Fo a pe iod o ime he au ho belie ed ha his iewpoin — ea ing di e -
ence equa ions as genuine mul i a iable analy ic objec s, a he han as nume i-
cal disc e iza ions, migh be en i ely new. I was only la e , a e ecei ing co e-
spondence om P o esso Alexande Lyapin (Sibe ian Fede al Uni e si y), ha
he au ho lea ned o an exis ing, hough ex emely small, esea ch communi y
wo king on wha hey call mul idimensional di e ence equa ions. The app oach
de eloped by Lyapin, Leina as, Apano ich and o he s is oo ed in combina-
o ics and complex-analy ic me hods [1,22,24], equen ly in ol ing gene a ing
unc ions and unc ional equa ions.
Al hough hese wo ks sha e simila mo i a ions, hey di e subs an ially in
no a ion, e minology, and me hodology. In his monog aph we con inue o
employ he au ho ’s e minology:
•O dina y Di e ence Equa ions (O∆E) e e o one-dimensional disc e e
equa ions.
•Pa ial Di e ence Equa ions (P∆E) e e o genuinely mul i a iable dis-
c e e equa ions, de ined on Zn.
7
Ou no a ion, ope a o calculus, and analy ical s yle ollow mo e closely
he adi ion o pa ial di e en ial equa ions: we wo k ex ensi ely wi h shi
ope a o s, adjoin ope a o s, disc e e analogues o di e gence and Laplacian,
spec al heo y, eigen unc ion expansions, Fou ie ans o ms, G een’s unc ions,
and semig oup me hods. Thus, while ela ed o he combina o ial li e a u e, he
p esen monog aph de elops a undamen ally di e en and mo e PDE-o ien ed
iewpoin .
The pu pose o his olume is o p esen , o he i s ime, a uni ied and
sys ema ically de eloped heo y o pa ial di e ence equa ions as an indepen-
den ma hema ical discipline, s anding alongside he classical heo y o pa ial
di e en ial equa ions and disc e e dynamical sys ems.
1.2 Disc e e Func ion
In his sec ion, we in oduce he concep o a disc e e unc ion, which se es as
he undamen al objec in ou amewo k o disc e e dynamical sys ems.
De ini ion 1.1 (Disc e e Func ion).Adisc e e unc ion is a mapping
: Ω ⊆Zn→C,
whe e Znis he disc e e n-dimensional in ege la ice, and Cis he codomain o
he unc ion ( eal, in ege , o complex alues depending on con ex ).
In his pape , we p ima ily ocus on he case whe e :Zn→R, i.e., eal-
alued disc e e unc ions.
Example 1.1 (Disc e e Single- a iable Func ion).Le :Z→Rbe de ined as
(x) = sin(x).
This is a eal- alued unc ion de ined on he in ege la ice Z.
Example 1.2 (Disc e e Mul i a iable Func ion).Le u:Z2→Zbe de ined as
u( , x) = ⌊x+ sin( )⌋.
He e, umaps disc e e space ime coo dina es ( , x) o an in ege alue ia he
loo unc ion applied o a eal exp ession.
De ini ion 1.2 (Disc e e Vec o Field).Adisc e e ec o ield on a disc e e
domain Ω⊆Znis a mapping
F: Ω →Rm,
ha assigns o each disc e e poin x∈Ωa ec o F(x) = (F1(x), F2(x), . . . , Fm(x)).
1.3 Ope a o s
De ini ion 1.3 (Shi Ope a o ).Le x:Z→C. We de ine he shi ope a o
Ekac ing on a disc e e unc ion x( )by
Ekx:= x( +k)
o any in ege k∈Z.
8
Examples.
Ex =x( + 1)
E2x=x( + 2)
E−1x=x( −1)
[12]
De ini ion 1.4 (Pa ial Shi Ope a o ).Gi en a disc e e scala ield u(x1, x2, . . . , xn),
he pa ial shi ope a o Eki
xiac s on uby shi ing he i- h coo dina e:
Eki
xiu:= u(x1, . . . , xi+ki, . . . , xn)
o any in ege ki∈Z.
Examples.
E u=u( + 1, x, y, z)
E2
xu=u( , x + 2, y, z)
De ini ion 1.5 (Di e ence Ope a o ).Le x:Z→C. We de ine he ( o wa d)
di e ence ope a o ∆by
∆x:= x( + 1) −x( )
We may de ine he shi ope a o Eas Ex := x( + 1), so ha he di e ence
ope a o can be w i en compac ly as
∆x=Ex −x
De ini ion 1.6 (Pa ial Di e ence Ope a o ).Le u:Zn→C, and deno e
u=u(x1, x2, . . . , xn). The pa ial di e ence ope a o wi h espec o he
a iable xiis de ined as:
∆xiu:= Exiu−u
whe e Exiis he pa ial shi ope a o ac ing on he i- h coo dina e:
Exiu:= u(x1, . . . , xi+ 1, . . . , xn)
1.4 O dina y Di e ence Equa ions
De ini ion 1.7 (O dina y Di e ence Equa ion o O de k).An o dina y di -
e ence equa ion o o de kis an equa ion in ol ing a single- a iable unc ion
x:Z→C, exp essed in e ms o shi ope a o s:
F(Enx, En−1x, . . . , Ex, x, E−1x, . . . , E−mx, )=0,
whe e Eix:= x( +i),n, m ∈Z+,k=m+nis he o al o de , and Fis a
(possibly nonlinea ) unc ion.
9
2.2 Disc e e 1D T anspo Equa ion
We conside he Disc e e T anspo Equa ion:
E u=Ek
xu
whe e u:Z2→Ris de ined on disc e e space ime.
Ini ial condi ion:
u(0, x) = (x)
We impose no bounda y condi ion.
In e p e a ion: Each alue is anspo ed igidly along a disc e e pa h. The
e ec i e eloci y is −k, since da a mo es om x+k o x.
Cha ac e is ic cu e:
x( ) = x0+k
Solu ion
We conside he pa ial di e ence equa ion
E u=Ek
xu, k ∈Z,
wi h no bounda y condi ions.
Le us de ine a new a iable:
ξ=x+k ,
and de ine a new unc ion
( , ξ) := u( , x).
Then we compu e he ime-shi o :
E = ( +1, ξ) = ( +1, x+k( +1)) = ( +1, x+k +k) = ( +1, ξ+k) = E Ek
ξ =E Ek
xu
E =E Ek
xu
=Ek
xu
On he o he hand, om he o iginal equa ion:
E u=u( + 1, x) = Ek
xu( , x) = u( , x +k).
Subs i u e u( , x) = ( , ξ), we ge :
E u=u( + 1, x) = ( + 1, ξ) = E .
16

And
Ek
xu=
Thus,
E = ,
o equi alen ly,
E = .
This is jus an O dina y Di e ence Equa ion.
Now we de ine a new unc ion o ξonly:
( , ξ) = (ξ),
which sol es he equa ion since
E = .
The e o e, he gene al solu ion is
( , ξ) = (ξ) = (x+k ),
so ha
u( , x) = (x+k ),
whe e (x) = u(0, x) is he ini ial condi ion.
Conclusion: The solu ion o he pa ial di e ence equa ion
E u=Ek
xu
is gi en by
u( , x) = (x+k ),
whe e is he ini ial p o ile o ua ime = 0.
17
2.3 3D Disc e e T anspo Equa ion
We conside he h ee-dimensional disc e e anspo equa ion
E u=Ea
xEb
yEc
zu, a, b, c ∈Z,
o a unc ion
u:N0×Z3→R, u =u( , x, y, z),
oge he wi h he ini ial condi ion
u(0, x, y, z) = (x, y, z),
and no bounda y condi ions.
Solu ion
In oduce he new coo dina es
ξ=x+a , η =y+b , ω =z+c ,
and de ine he ans o med unc ion
( , ξ, η, ω) := u( , x, y, z).
We compu e he ime-shi o :
E = ( + 1, ξ, η, ω)
=  + 1, x +a , y +b , z +c 
=  + 1, x +a +a, y +b +b, z +c +c
= ( + 1, ξ +a, η +b, ω +c)
=E Ea
ξEb
ηEc
ω
=E Ea
xEb
yEc
zu
Thus,
E =E Ea
xEb
yEc
zu,
=Ea
xEb
yEc
zu,
and subs i u ing u( , x, y, z) = ( , ξ, η, ω) gi es
E = .
Thus sa is ies he o dina y di e ence equa ion
E = ,
whose gene al solu ion is
( , ξ, η, ω) = (ξ, η, ω).
Re u ning o he o iginal a iables, we ob ain he solu ion o he 3D disc e e
anspo equa ion:
u( , x, y, z) = (x+a , y +b , z +c ).
18
2.4 Exis ence and Uniqueness o Solu ions o P∆E
Fo linea pa ial di e ence equa ions, he ques ion o exis ence and uniqueness
o solu ions is conside ably simple han in he con inuous case. Since he equa-
ions a e algeb aic ecu sions on a disc e e la ice, solu ions can be cons uc ed
s ep by s ep as long as he ecu sion is well-de ined.
In pa icula , a solu ion exis s and is unique p o ided he ollowing condi-
ions hold:
•The equa ion is well-de ined, i.e. he shi ope a o s in ol ed do no lead
o unde ined alues.
•Su icien ini ial condi ions a e gi en: i he equa ion has s uc u al o de
kin he ime di ec ion, hen one mus p esc ibe u(0,·), u(1,·), . . . , u(k−
1,·) on he spa ial domain.
•Bounda y condi ions a e speci ied so ha whene e a shi ed poin alls
ou side he compu a ional domain, he alue o uis s ill uniquely de e -
mined.
Unde hese assump ions, he solu ion can be cons uc ed induc i ely in
ime, and a each s ep he new laye o alues is uniquely de e mined by p e i-
ously known laye s and he p esc ibed bounda y da a. The e o e, unlike he case
o pa ial di e en ial equa ions, no addi ional egula i y condi ions a e equi ed
o gua an ee exis ence and uniqueness.
19
3 Disc e e Func ion Spaces and Ope a o s
3.1 In oduc ion
In his sec ion, we in oduce and igo ously de ine se e al disc e e unc ion
spaces, such as he disc e e Lpspaces, disc e e Hilbe spaces, and he dis-
c e e Schwa z space. We hen p oceed o de ine a a ie y o ope a o s in he
disc e e se ing, including he shi ope a o , he di e ence ope a o , and he
disc e e Laplacian. A e wa d, we discuss ope a o heo y in his con ex , co -
e ing undamen al no ions such as bounded linea ope a o s and adjoin s. In
his wo k, we adap a numbe o classical heo ems om unc ional analysis
(such as he Hahn–Banach heo em, he Riesz ep esen a ion heo em, and he
Banach–Alaoglu heo em) o he disc e e amewo k o e Zn. We hen illus-
a e hese esul s h ough explici cons uc ions in disc e e unc ion spaces
and ope a o heo y, he eby es ablishing an analy ic ounda ion o he s udy
o pa ial di e ence equa ions. Mos o hese concep s a e na u al adap a ions
o exis ing amewo ks om he li e a u e, d awing inspi a ion om classical
e e ences in di e ence equa ions, pa ial di e en ial equa ions, and unc ional
analysis [8,12,21,28].
3.2 Disc e e Func ion Spaces
De ini ion 3.1 (Disc e e Func ion Space).Le Ω⊆Znbe a disc e e domain.
We de ine he disc e e unc ion space o e Ωas
F(Ω) := { : Ω →C},
i.e., he se o all unc ions om Ω o he complex numbe s.
De ini ion 3.2 (Topological Vec o Space).A opological ec o space (TVS)
o e a ield K(whe e K=Ro C) is a ec o space X oge he wi h a opology
τon Xsuch ha :
1. (X, τ)is a opological space.
2. The ec o addi ion map
+ : X×X→X, (x, y)7→ x+y
is con inuous wi h espec o he p oduc opology on X×X.
3. The scala mul iplica ion map
·:K×X→X, (λ, x)7→ λx
is con inuous wi h espec o he p oduc opology on K×X.
De ini ion 3.3 (No med Vec o Space).Le Vbe a ec o space o e he ield
Ro C. A no m on Vis a mapping
∥·∥:V→[0,∞)
sa is ying, o all u, ∈Vand all scala s α:
20
1. Posi i e de ini eness: ∥u∥= 0 ⇐⇒ u= 0.
2. Homogenei y: ∥αu∥=|α|∥u∥.
3. T iangle inequali y: ∥u+ ∥ ≤ ∥u∥+∥ ∥.
A ec o space Vequipped wi h a no m ∥·∥is called a no med ec o space,
deno ed (V, ∥·∥).
De ini ion 3.4 (Banach Space).Le (X, ∥·∥)be a no med ec o space o e R
o C. We say ha (X, ∥·∥)is a Banach space i Xis comple e wi h espec o
he me ic induced by he no m, i.e.
d(x, y) = ∥x−y∥, x, y ∈X,
meaning ha e e y Cauchy sequence {xn}in Xcon e ges o some limi x∈X.
De ini ion 3.5 (Measu e Space).Ameasu e space is a iple (X, A, µ)whe e
1. Xis a nonemp y se (called he unde lying se ).
2. Ais a σ-algeb a o subse s o X; ha is:
(a) ∅∈ A,
(b) I A∈ A, hen X A∈ A,
(c) I {Ai}∞
i=1 ⊆ A, hen S∞
i=1 Ai∈ A.
3. µ:A → [0,∞]is a measu e, i.e.
(a) µ(∅)=0,
(b) (Coun able addi i i y) Fo any coun able collec ion o pai wise dis-
join se s {Ai}∞
i=1 ⊆ A,
µ ∞
[
i=1
Ai!=
∞
X
i=1
µ(Ai).
Example 3.1 (Coun ing Measu e).Le Xbe any se and le A= 2Xbe he
collec ion o all subse s o X. The coun ing measu e µc:A → [0,∞]is de ined
by
µc(A) = (|A|,i Ais ini e,
∞,i Ais in ini e.
Then (X, A, µc)is a measu e space.
[20]
21

De ini ion 3.6 (Disc e e LpSpace).Le Ω⊆Zn. We de ine he disc e e Lp
space o 1≤p < ∞as
Lp(Ω) := ( : Ω →CX
x∈Ω| (x)|p<∞),
wi h he co esponding Lpno m de ined by
∥ ∥p:= X
x∈Ω| (x)|p!1/p
.
Fo p=∞, we de ine
L∞(Ω) :=  : Ω →Csup
x∈Ω| (x)|<∞,
wi h he co esponding L∞no m gi en by
∥ ∥∞:= sup
x∈Ω| (x)|.
[16]
De ini ion 3.7 (Disc e e Hilbe Space).Le Ω⊆Zn. The disc e e Hilbe
space is he space L2(Ω) de ined as
L2(Ω) := ( : Ω →CX
x∈Ω| (x)|2<∞),
equipped wi h he inne p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x), o all , g ∈ L2(Ω).
This inne p oduc sa is ies he ollowing p ope ies o all , g, h ∈ L2(Ω)
and all scala s α∈C:
1. Conjuga e Symme y:
⟨ , g⟩=⟨g, ⟩.
2. Linea i y in he Fi s A gumen :
⟨α +h, g⟩=α⟨ , g⟩+⟨h, g⟩.
3. Posi i e De ini eness:
⟨ , ⟩ ≥ 0,and ⟨ , ⟩= 0 ⇐⇒ = 0.
22
The no m induced by his inne p oduc is
∥ ∥2:= p⟨ , ⟩= X
x∈Ω| (x)|2!1/2
.
Mo eo e , L2(Ω) is comple e wi h espec o his no m, and hence o ms a
Hilbe space.
De ini ion 3.8 (Suppo o a Func ion).Le Xbe a se and :X→Ca
unc ion. The suppo o , deno ed by supp( ), is de ined as
supp( ) = {x∈X| (x)= 0}.
In wo ds, he suppo o is he se o all poin s whe e does no anish.
De ini ion 3.9 (Fini e Suppo Func ion Space).The Fini e Suppo Func ion
Space on Znis de ined as
F0(Zn) := { :Zn→C|supp( )is ini e}.
Tha is, ∈F0(Zn)i and only i he e exis s a ini e se A⊂Znsuch ha
(x) = 0 o all x /∈A.
De ini ion 3.10 (Disc e e Schwa z Space).Le α= (α1, . . . , αn)∈Nnbe a
mul i-index and, o x= (x1, . . . , xn)∈Zn, w i e
xα:=
n
Y
i=1 |xi|αi.
De ine he semino ms
pα( ) := sup
x∈Znxα (x)∈[0,∞].
The disc e e Schwa z space on Znis
S(Zn) :=  :Zn→C:pα( )<∞ o all α∈Nn.
Equi alen ly, le ing |x|:= px2
1+···+x2
n,
S(Zn) = n :Zn→C: sup
x∈Zn
(1 + |x|)k| (x)|<∞ o all k∈No.
Example 3.2.
(1) I has ini e suppo , hen ∈ S(Zn).
(2) The Gaussian es ic ion (x) = e−|x|2,x∈Zn, sa is ies
sup
x∈Zn
(1 + |x|)ke−|x|2<∞ o all k,
hence ∈ S(Zn).
(3) The polynomially decaying sequence (x) = (1 + |x|)−mbelongs o S(Zn) i
mcan be aken a bi a ily la ge; o ixed mi is no in S(Zn).
23
P oposi ion 3.11. The disc e e unc ion space
F0(Z) := { :Z→R|supp( )is ini e}
is no comple e wi h espec o he L1no m.
P oo . De ine a sequence { n}∞
n=1 ⊂F0(Z) by
n(x) := (e−x2,−n≤x≤n,
0,o he wise,x∈Z.
Clea ly each nhas ini e suppo , hence n∈F0(Z).
Conside he me ic induced by he L1no m:
d( , g) = ∥ −g∥L1=X
x∈Z| (x)−g(x)|.
Fo m>n, we compu e
∥ m− n∥L1=X
x∈Z| m(x)− n(x)|=X
n<|x|≤m
e−x2.
Since Px∈Ze−x2<∞, he ail sum Pn<|x|≤me−x2→0 as n→ ∞. Thus { n}
is a Cauchy sequence in (F0(Z),∥·∥L1).
I s poin wise and L1limi is he unc ion
(x) = e−x2, x ∈Z,
which belongs o L1(Z) since Px∈Ze−x2<∞, bu /∈F0(Z) because supp( ) =
Zis in ini e.
The e o e, F0(Z) is no comple e. I s comple ion is L1(Z).
P oposi ion 3.12. The space o ini ely suppo ed unc ions
F0(Z) = { :Z→R|supp( )is ini e}
is dense in L1(Z).
P oo . Le ∈ L1(Z), i.e. X
x∈Z| (x)|<∞.
Fo each N∈N, de ine he unca ed unc ion
N(x) := ( (x),|x| ≤ N,
0,|x|> N.
Clea ly N∈F0(Z), since i s suppo is con ained in {−N, −N+ 1, . . . , N}.
24
Now es ima e he app oxima ion e o :
∥ − N∥L1=X
x∈Z| (x)− N(x)|=X
|x|>N | (x)|.
Since ∈ L1(Z), he se ies Px∈Z| (x)|con e ges, hence he ail sum P|x|>N | (x)| →
0 as N→ ∞.
The e o e,
lim
N→∞ ∥ − N∥L1= 0,
which p o es ha F0(Z) is dense in L1(Z).
De ini ion 3.13 (In ege Valued Func ion Space).Le Ω⊆Zn. We de ine he
in ege alued unc ion space as
Q(Ω) = { : Ω →Z}.
Rema k 3.14. The in ege alued unc ion space Q(Ω) is no a ec o space,
since scala mul iplica ion o e R(o C) is no de ined. Ins ead, i o ms a
module o e he in ege ing Z, whe e he scala s come om Z.
De ini ion 3.15 (Mod nIn ege Valued Func ion Space).Le Ω⊆Zn. We
de ine he Mod nIn ege Valued Func ion Space as
Qn(Ω) = { : Ω →Zn},
whe e Zn={0,1,2, ..., n −1}, n ∈Z}deno es he ing o in ege s modulo n.
De ini ion 3.16 (Boolean Func ion Space).Le Ω⊆Zn. We de ine he
Boolean Func ion Space as
B(Ω) = Q2(Ω) = { : Ω →Z2},
whe e Z2={0,1}deno es he Boolean ing wi h wo elemen s. Any ∈B(Ω)
is called a Boolean unc ion.
3.3 Types o Ope a o s
De ini ion 3.17 (Disc e e Ope a o ).Le V, W be disc e e unc ion spaces, i.e.,
subspaces o F(Ω), whe e Ω⊆Zn.
Adisc e e ope a o is a map
T:V→W,
which assigns o each unc ion ∈Va unc ion T ∈W.
De ini ion 3.18 (Shi Ope a o ).Le x:Z→C. We de ine he shi ope -
a o Ekac ing on a disc e e unc ion x( )by
Ekx:= x( +k)
o any in ege k∈Z.
25
Theo em 3.40 (Abelian G oup o Pa ial Shi Ope a o s).Le u:Zn→Cbe
a disc e e unc ion. Fo k= (k1, . . . , kn)∈Zn, de ine he pa ial shi ope a o
Ek:= Ek1
x1Ek2
x2···Ekn
xn,(Eki
xiu)(x1, . . . , xn) = u(x1, . . . , xi+ki, . . . , xn).
Then he se
E={Ek:k∈Zn}
o ms an abelian g oup unde composi ion. Mo eo e ,
EkEm=Ek+m,(Ek)−1=E−k,
and he e o e
E∼
=(Zn,+).
P oo . Closu e. Fo any k,m∈Zn,
EkEm=Ek1
x1Em1
x1···Ekn
xnEmn
xn=Ek1+m1
x1···Ekn+mn
xn=Ek+m,
hence Eis closed unde composi ion.
Iden i y. The neu al elemen is he ze o shi
E0=I.
In e se. Fo any k∈Zn,
EkE−k=E0=I.
Associa i i y. This ollows om associa i i y o ope a o composi ion.
Commu a i i y. Since pa ial shi s in di e en coo dina es commu e,
Eki
xiEmj
xj=Emj
xjEki
xi, i =j,
we ob ain
EkEm=EmEk.
Thus he g oup is abelian.
All g oup axioms a e sa is ied, and he mapping k7→ Ekis a g oup isomo -
phism om (Zn,+) o E.
P oposi ion 3.41 (Lie G oup o he Con inuous Pa ial Shi Ope a o s).Le
:Rn→Rbe any unc ion, and o each k∈Rnde ine he con inuous pa ial
shi ope a o
(Ek )(x) := (x+k), x ∈Rn.
Then he amily o ope a o s
G:= {Ek:k∈Rn}
o ms an n-dimensional abelian Lie g oup unde composi ion. Mo eo e , his
Lie g oup is smoo hly isomo phic o (Rn,+).
32

P oo . (1) G oup s uc u e. Fo any k, h ∈Rnand any unc ion ,
(EkEh )(x) = Eh (x+k) = (x+k+h)=(Ek+h )(x).
Thus
EkEh=Ek+h,
which shows closu e and de ines he g oup law. The iden i y elemen is E0,
since E0 (x) = (x).
Fo each k∈Rn, he in e se is
(Ek)−1=E−k,
since EkE−k=E0. Hence Gis a g oup.
(2) Smoo h mani old s uc u e. De ine he map
Φ : Rn→ G, k 7→ Ek.
This map is bijec i e, wi h in e se gi en by
Φ−1(Ek) = k.
Thus Ginhe i s a smoo h mani old s uc u e om Rn ia Φ. In pa icula , Gis
an n-dimensional smoo h mani old.
(3) Smoo hness o g oup ope a ions. Unde he iden i ica ion Φ, he
g oup law becomes
k·h=k+h,
which is smoo h on Rn. Simila ly, in e sion co esponds o
k−1=−k,
which is also smoo h. Hence bo h mul iplica ion and in e sion on Ga e smoo h
wi h espec o he inhe i ed mani old s uc u e.
(4) Conclusion. The se o con inuous pa ial shi ope a o s Gis he e o e
an n-dimensional abelian Lie g oup, smoo hly isomo phic (indeed isomo phic as
Lie g oups) o (Rn,+).
De ini ion 3.42 (Adjoin Ope a o ).Le L2(Ω) be a disc e e Hilbe space wi h
inne p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x).
Le T:D(T)⊆ L2(Ω) → L2(Ω) be a linea ope a o .
We say ha a linea ope a o T∗:D(T∗)⊆ L2(Ω) → L2(Ω) is he adjoin
o Ti :
⟨T , g⟩=⟨ , T∗g⟩ o all ∈ D(T), g ∈ D(T∗).
He e, D(T∗)consis s o all g∈ L2(Ω) such ha he map
7→ ⟨T , g⟩
is con inuous (i.e., bounded) on D(T).
33
Example 3.7. Le Ω⊆Znbe shi -in a ian unde α∈Zn(e.g. Ω = Zn, o Ω
wi h pe iodic bounda y condi ions), and conside he Hilbe space L2(Ω) wi h
inne p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x).
Fo α∈Zn, de ine he (mul i-dimensional) shi
(Eαu)(x) := u(x+α),
whe e
Eα=Eα1
x1···Eαn
xn, α = (α1, . . . , αn)∈Zn
is he ec o ep esen ing he di ec ion (and magni ude) o he shi .
Then o all u, ∈ L2(Ω),
⟨Eαu, ⟩=X
x∈Ω
u(x+α) (x) = X
y∈Ω
u(y) (y−α)
=⟨u, E−α ⟩.
Hence he adjoin o he shi is he opposi e shi :
(Eα)∗=E−α.
De ini ion 3.43 (Uni a y Ope a o ).Le Ω⊆Znand le
U:D(U)⊆ L2(Ω) → L2(Ω)
be a linea ope a o wi h domain D(U). We say ha Uis uni a y i :
U∗U=UU∗=I,
ha is,
U∗=U−1,
whe e U∗is he adjoin o Uand U−1is he in e se ope a o o U. Equi alen ly,
Uis uni a y i i p ese es he inne p oduc :
⟨U , Ug⟩=⟨ , g⟩ o all , g ∈ L2(Ω).
P oposi ion 3.44. Le Ω⊆Znbe shi -in a ian unde ±α∈Zn(e.g. Ω = Zn
o Ωwi h pe iodic bounda y condi ions). Conside he Hilbe space L2(Ω) wi h
inne p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x).
Fo α∈Zn, de ine he shi ope a o
Eαu(x) := u(x+α).
Then Eαis a uni a y ope a o on L2(Ω).
34
P oo . F om he calcula ion in he p e ious example, we ha e
⟨Eαu, ⟩=⟨u, E−α ⟩,
which shows (Eα)∗=E−α. Since EαE−α=E−αEα=I, i ollows ha
(Eα)∗= (Eα)−1.
Thus Eαis uni a y by de ini ion. Equi alen ly, o all u∈ L2(Ω),
∥Eαu∥2
2=X
x∈Ω|u(x+α)|2=X
y∈Ω|u(y)|2=∥u∥2
2,
so Eαp ese es he no m and is su jec i e.
De ini ion 3.45 (Sel -adjoin Ope a o ).Le Ω⊆Zn, and le
T:D(T)⊆ L2(Ω) → L2(Ω)
be a linea ope a o wi h domain D(T). We say ha Tis sel -adjoin i i
sa is ies:
T=T∗and D(T) = D(T∗),
whe e T∗deno es he adjoin ope a o o T, de ined by
⟨Tu, ⟩=⟨u, T ∗ ⟩ o all u∈ D(T), ∈ D(T∗).
Theo em 3.46 (Sel -adjoin ness o sums and p oduc s o commu ing ope a-
o s).Le Ω⊆Zn, and le
L1, L2, . . . , Lm:L2(Ω) → L2(Ω)
be linea ope a o s sa is ying:
(1) Sel -adjoin ness:
L∗
i=Li, i = 1, . . . , m.
(2) Pai wise commu a i i y:
LiLj=LjLi,∀i, j.
Then:
(a) The sum
L=
m
X
i=1
Li
is sel -adjoin .
35
(b) The p oduc
P=
m
Y
i=1
Li
is also sel -adjoin .
P oo . (a) Sum o sel -adjoin ope a o s. Using linea i y o he adjoin ,
m
X
i=1
Li!∗
=
m
X
i=1
L∗
i=
m
X
i=1
Li,
so he sum is sel -adjoin .
(b) P oduc o commu ing sel -adjoin ope a o s. Le
P=L1L2···Lm.
Using he adjoin ule (AB)∗=B∗A∗,
P∗= (L1L2···Lm)∗=L∗
mL∗
m−1···L∗
1.
Since each Liis sel -adjoin ,
P∗=LmLm−1···L1.
Commu a i i y gi es
LmLm−1···L1=L1L2···Lm=P.
Thus P∗=P, so Pis sel -adjoin .
Example 3.8 (Disc e e Laplacian is sel -adjoin ).Le Ω⊆Zbe shi -in a ian
unde ±1(e.g. Ω = Zo pe iodic bounda y condi ions on a ini e la ice), and
conside he Hilbe space L2(Ω) wi h inne p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x).
De ine he 1D disc e e Laplacian by
∇2u:= Eu +E−1u−2u, i.e. ∇2=E+E−1−2I,
whe e Eku=u(x+k).
Since E∗=E−1(and hence (E−1)∗=E), we ha e
(∇2)∗= (E+E−1−2I)∗=E∗+ (E−1)∗−2I=E−1+E−2I=∇2.
Equi alen ly, o all u, ∈ L2(Ω),
⟨∇2u, ⟩=⟨Eu, ⟩+⟨E−1u, ⟩−2⟨u, ⟩
=⟨u, E−1 ⟩+⟨u, E ⟩−2⟨u, ⟩=⟨u, (E−1+E−2I) ⟩=⟨u, ∇2 ⟩.
Hence ∇2is sel -adjoin on L2(Ω).
36
Example 3.9 (Disc e e n-Dimensional Laplacian is sel -adjoin ).Le Ω⊆Zn
be shi -in a ian unde ±ei o i= 1, . . . , n (e.g. Ω = Zno pe iodic bounda y
condi ions on a ini e la ice), and conside he Hilbe space L2(Ω) wi h inne
p oduc
⟨ , g⟩:= X
x∈Ω
(x)g(x).
Fo each coo dina e i, le Exideno e he uni shi in he i- h di ec ion:
Exiu:= u(x+ei), E−1
xiu:= u(x−ei).
De ine he disc e e Laplacian by
∇2u:=
n
X
i=1 Exiu+E−1
xiu−2u⇐⇒ ∇2=
n
X
i=1 Exi+E−1
xi−2I.
Using (Exi)∗=E−1
xi(hence (E−1
xi)∗=Exi), we ha e
(∇2)∗=
n
X
i=1 (Exi)∗+ (E−1
xi)∗−2I=
n
X
i=1 E−1
xi+Exi−2I=∇2.
Equi alen ly, o all u, ∈ L2(Ω),
⟨∇2u, ⟩=
n
X
i=1 ⟨Exiu, ⟩+⟨E−1
xiu, ⟩−2⟨u, ⟩=
n
X
i=1 ⟨u, E−1
xi ⟩+⟨u, Exi ⟩−2⟨u, ⟩=⟨u, ∇2 ⟩.
Hence ∇2is sel -adjoin on L2(Ω).
Example 3.10 (Spec um o he Disc e e Laplacian).Conside he disc e e
Laplacian de ined on a uni o m g id
(∇2u)(x) = u(x+ 1) + u(x−1) −2u(x).
We s udy he eigen alue p oblem
−∇2u=λu, u(0) = u(L) = 0.
The solu ions a e gi en by he disc e e sine unc ions
uk(j) = sinkπj
L, j = 0,1, . . . , L,
wi h co esponding eigen alues
λk= 4 sin2kπ
2L, k = 1,2, . . . , L −1.
The e o e, he spec um o he disc e e Laplacian wi h Di ichle bounda y con-
di ions is
σ(−∇2) = n4 sin2kπ
2L:k= 1,2, . . . , L −1o.
37

P oposi ion 3.47 (Sel -adjoin ness o he Moo e Laplacian).Le Ω⊆Znbe
shi -in a ian unde ±ei o i= 1, . . . , n. The Moo e Laplacian
∇2
Mu=X
∅=S⊆{1,...,n} Y
i∈S
δxi∆xi!u
is a sel -adjoin ope a o on L2(Ω).
P oo . F om he ea lie sec ions, each one-dimensional second-o de di e ence
ope a o δxi∆xisa is ies:
(δxi∆xi)∗=δxi∆xi, i = 1, . . . , n,
ha is, each is sel -adjoin on L2(Ω).
Mo eo e , hese ope a o s commu e pai wise:
δxi∆xiδxj∆xj=δxj∆xjδxi∆xi,∀i, j,
because all pa ial shi ope a o s commu e.
By he heo em on sums and p oduc s o commu ing sel -adjoin ope a o s,
any ini e p oduc
Y
i∈S
δxi∆xi,∅ =S⊆ {1, . . . , n},
is sel -adjoin .
Finally, he Moo e Laplacian is a ini e sum o such p oduc s:
∇2
M=X
∅=S⊆{1,...,n}Y
i∈S
δxi∆xi,
hence i is sel -adjoin .
This comple es he p oo .
38
4 Disc e e Func ionals and Con e gence
4.1 In oduc ion
In his sec ion, we in oduce he no ion o disc e e unc ionals, and s udy he
compac ness o he uni ball in disc e e unc ion spaces. We hen ecall some
undamen al heo ems om unc ional analysis, such as he Hahn–Banach he-
o em and he Riesz ep esen a ion heo em, and explain how hese ideas ex end
na u ally o he disc e e se ing. Finally, we p esen se e al di e en no ions
o con e gence o disc e e unc ions, including poin wise con e gence, uni o m
con e gence, and weak con e gence. [8,21]
4.2 Disc e e Func ionals
De ini ion 4.1 (Disc e e Func ional).Le Ω⊆Znand le Vbe a ec o space
o unc ions u: Ω →C(o R). A disc e e unc ional on Vis a mapping
F:V→C,
ha assigns o each unc ion u∈Va scala F(u).
Example 4.1.
1. Di ac unc ional: Fo a ixed x0∈Ω, de ine
F(u) = u(x0).
This unc ional simply e alua es he unc ion ua he poin x0.
2. Summa ion unc ional: De ine
F(u) = X
x∈Ω
u(x),
whene e he sum con e ges. Mo e gene ally, wi h weigh s w: Ω →C,
F(u) = X
x∈Ω
w(x)u(x).
De ini ion 4.2 (Bounded Linea Func ional).Le (X, ∥·∥)be a no med ec o
space o e Ro C. A mapping F:X→R(o C) is called a linea unc ional
i
F(αx +βy) = αF(x) + βF(y),∀x, y ∈X, ∀α, β ∈R(o C).
The unc ional Fis said o be bounded (o con inuous) i he e exis s a cons an
C≥0such ha
|F(x)| ≤ C∥x∥,∀x∈X.
The smalles such cons an Cis called he ope a o no m o F, deno ed
∥F∥:= sup
x∈X, x=0
|F(x)|
∥x∥.
39
De ini ion 4.3 (Dual Space).Le (X, ∥·∥)be a no med ec o space o e Ro
C. The dual space o X, deno ed by X∗, is he collec ion o all linea unc ionals
F:X→R(o C) ha a e bounded, i.e., he e exis s a cons an C≥0such
ha
|F(x)| ≤ C∥x∥,∀x∈X.
The ope a o no m o F∈X∗is de ined by
∥F∥:= sup
x∈X, x=0
|F(x)|
∥x∥.
Equipped wi h his no m, he dual space (X∗,∥·∥)is i sel a Banach space, e en
i Xis no comple e.
4.3 Compac ness o he Uni Ball in Disc e e Func ion
Spaces
We illus a e he phenomenon using he disc e e Hilbe space L2(Ω).
Theo em 4.4 (Compac ness o he Uni Ball).Le Ω⊆Zn. Conside he uni
ball
B:= { ∈ L2(Ω) : ∥ ∥L2≤1}.
Then:
1. I Ωis ini e (say |Ω|=N < ∞), hen L2(Ω) ∼
=RN(o CN). By he
Heine–Bo el heo em, e e y closed and bounded se in RNis compac .
Hence Bis compac .
2. I Ωis in ini e, hen L2(Ω) is in ini e-dimensional. In his case, Bis no
compac in he no m opology.
Coun e example in he in ini e case. Le Ω = Zand conside he s anda d o -
hono mal basis {en}n∈Z⊂ L2(Z), whe e
en(m) := (1, m =n,
0, m =n.
Clea ly, ∥en∥L2= 1 o all n, so each en∈B. Howe e , o n=m, we ha e
∥en−em∥L2=√2.
Thus, he sequence {en}has no Cauchy subsequence, and he e o e no con e -
gen subsequence in no m. Hence, Bis no compac .
Theo em 4.5 (Banach–Alaoglu Theo em).Le Xbe a no med ec o space
o e Ro C, and le X∗deno e i s dual space. Conside he closed uni ball in
he dual space,
B∗:= { ∈X∗:∥ ∥ ≤ 1}.
Then B∗is compac in he weak-* opology on X∗, i.e. he opology o poin wise
con e gence on X.
40
4.4 Hahn–Banach Theo em
De ini ion 4.6 (Sublinea unc ional).Le Xbe a eal ec o space. A mapping
p:X→Ris called a sublinea unc ional i i sa is ies:
1. Posi i e homogenei y: p(λx) = λp(x) o all x∈Xand λ > 0.
2. Subaddi i i y: p(x+y)≤p(x) + p(y) o all x, y ∈X.
Theo em 4.7 (Hahn–Banach Theo em).Le Xbe a eal ec o space, p:
X→Ra sublinea unc ional, and le Y⊂Xbe a linea subspace. Suppose
:Y→Ris a linea unc ional such ha
(y)≤p(y),∀y∈Y.
Then he e exis s a linea unc ional F:X→Rex ending (i.e. F|Y= )
such ha
F(x)≤p(x),∀x∈X.
Example 4.2 (Hahn–Banach Ex ension on Z).Conside he Banach space
X=L1(Z) = n :Z→RX
x∈Z| (x)|<∞o.
Subspace. Le
F0(Z) = { :Z→R|supp( )is ini e}
be he space o ini ely suppo ed unc ions.
Func ional on he subspace. De ine
g( ) = (0), ∈F0(Z),
ha is, e alua ion a he o igin.
Boundedness. Fo any ∈F0(Z),
|g( )|=| (0)| ≤ X
x∈Z| (x)|=∥ ∥L1.
Hence gis a bounded linea unc ional.
Hahn–Banach ex ension. By he Hahn–Banach heo em:
1. The unc ional gde ined on F0(Z)can be ex ended o a bounded linea
unc ional Gon all o L1(Z).
2. The ex ension sa is ies
|G( )|≤∥ ∥L1,∀ ∈ L1(Z).
Conclusion. In ac , e e y such ex ension has he o m
G( ) = X
x∈Z
w(x) (x), w ∈ L∞(Z),
41
P oo o “Solu ion as Con olu ion o he G een’s Func ion”. Fix Ω ⊆Zn. Le
Lbe a linea , causal e olu ion ope a o ha is shi –in a ian in space and ime,
and le G( , x) deno e he disc e e G een’s unc ion, i.e. he esponse o a uni
space– ime impulse a he o igin:
inpu δ( )δ(x)7→ ou pu G( , x), ≥0.
S ep 1 (del a expansion o he o cing). Fo any o cing :Z≥0×Ω→Cwe
ha e he (space– ime) del a ep esen a ion
( , x) =
∞
X
τ=0 X
s∈Ω
(τ, s)δ( −τ)δ(x−s),
wi h con e gence in L2(Ω) o each ixed (o in a sui able unc ion space
depending on he p oblem).
S ep 2 ( esponses o elemen a y impulses). Le eτ,s( , x) := δ( −τ)δ(x−s).
By ime- and space-shi in a iance o L, he esponse o eτ,sis he shi ed
G een’s unc ion
uτ,s( , x) = G( −τ, x−s) (unde s ood as 0 o <τ).
S ep 3 (linea supe posi ion). By linea i y o L, he solu ion o L(u) = wi h
ze o ini ial condi ion is he supe posi ion o he elemen a y esponses weigh ed
by he coe icien s (τ, s) om S ep 1:
u( , x) =
X
τ=0 X
s∈Ω
(τ, s)G( −τ, x−s).
(The uppe limi e lec s causali y; e ms wi h τ > anish.)
Thus u=G∗ is he disc e e space– ime con olu ion o he G een’s unc ion
wi h he o cing, which p o es he s a ed o mula.
48

6 Disc e e Fou ie T ans o m
6.1 Mo i a ion and Backg ound
In his sec ion we de elop he Fou ie analy ic amewo k necessa y o he
s udy o pa ial di e ence equa ions. The disc e e Fou ie se ies (DFS) and he
disc e e Fou ie ans o m (DFT) p o ide na u al ools o ep esen ing pe iodic
disc e e unc ions in e ms o o hogonal exponen ial bases. These ep esen a-
ions no only yield compac o mulas o he coe icien s and econs uc ion o
disc e e unc ions, bu also es ablish powe ul heo ems such as o hogonali y e-
la ions, Pa se al’s iden i y, and con e gence esul s. Mo eo e , Fou ie me hods
play a c ucial ole in sol ing linea pa ial di e ence equa ions by diagonaliz-
ing shi ope a o s and cons uc ing explici solu ions o ini ial–bounda y alue
p oblems. The exposi ion he e is inspi ed by classical esul s in Fou ie analysis
and adap ed o he disc e e unc ion se ing (c . [15,27,28]).
6.2 Disc e e Fou ie Se ies
We now in oduce he disc e e Fou ie se ies (DFS), which p o ides an expansion
o pe iodic disc e e unc ions in e ms o exponen ial basis unc ions. Le :
Z→Cbe a disc e e unc ion o pe iod N, i.e. (x+N) = (x) o all x∈Z.
Then admi s he ep esen a ion
(x) =
N−1
X
k=0
F(k)ei2π
Nkx,
whe e he Fou ie coe icien s a e gi en explici ly by
F(k) = 1
N
N−1
X
x=0
(x)e−i2π
Nkx, k = 0,1, . . . , N −1.
This o mula shows ha e e y N-pe iodic disc e e unc ion can be decomposed
in o a ini e linea combina ion o o hogonal exponen ial unc ions. In he
ollowing, we shall es ablish he o hogonali y ela ions o he exponen ial basis,
de i e Pa se al’s iden i y, and discuss he con e gence p ope ies o he disc e e
Fou ie se ies.
6.3 Inne P oduc and O hogonali y
We equip he space o N-pe iodic disc e e unc ions wi h he no malized inne
p oduc
⟨ , g⟩:= 1
N
N−1
X
x=0
(x)g(x).
This s uc u e makes he unc ion space a ini e-dimensional Hilbe space, na -
u ally iden i ied wi h CN.
49
P oposi ion 6.1 (O hono mali y o he exponen ial basis).Le
ϕk(x) := ei2π
Nkx, k = 0,1, . . . , N −1, x ∈Z.
Then {ϕk}N−1
k=0 o ms an o hono mal basis o L2(Ω) wi h Ω = {0,1, . . . , N −1}.
In pa icula ,
⟨ϕk, ϕm⟩=δkm,0≤k, m ≤N−1.
P oposi ion 6.2 (O hono mali y o he exponen ial basis).Le
ϕk(x) := ei2π
Nkx, k = 0,1, . . . , N −1, x ∈Z.
Then {ϕk}N−1
k=0 o ms an o hono mal basis o L2(Ω) wi h Ω = {0,1, . . . , N −1}.
In pa icula ,
⟨ϕk, ϕm⟩=δkm,0≤k, m ≤N−1.
P oo . By de ini ion o he inne p oduc ,
⟨ϕk, ϕm⟩=1
N
N−1
X
x=0
ei2π
N(k−m)x.
I k=m, each e m equals 1 and hence he sum equals 1. I k=m, he
summand is a ini e geome ic p og ession wi h a io ei2π
N(k−m)= 1, and he
sum anishes. Thus ⟨ϕk, ϕm⟩=δkm.
6.4 Disc e e Fou ie T ans o m
We now u n o he disc e e Fou ie ans o m (DFT), which is he na u al
Fou ie analy ic ool o unc ions de ined on he en i e in ege la ice.
De ini ion 6.3 (DFT and i s in e se).Le :Z→Cbe an in ini e disc e e
unc ion. The disc e e Fou ie ans o m o is de ined by
F(ω) = X
x∈Z
(x)e−iωx, ω ∈[−π, π].
The co esponding in e se ans o m is gi en by
(x) = 1
2πZπ
−π
F(ω)eiωx dω, x ∈Z.
Rema k 6.4 (Key p ope ies).
•The equency a iable ωis con inuous and a ies o e he undamen al
in e al [−π, π].
•The spec um F(ω)is pe iodic wi h pe iod 2π, i.e.
F(ω+ 2π) = F(ω).
•This ans o m (commonly e e ed o as DTFT in enginee ing) is pa ic-
ula ly use ul in analyzing in ini e disc e e sequences, e.g. in digi al signal
p ocessing, s abili y analysis, and disc e e- ime dynamical sys ems.
50
Con en ion. In his pape we e e o he Fou ie ans o m o sequences
de ined on he ull in ege la ice Zas he Disc e e Fou ie T ans o m (DFT).
This di e s om he enginee ing con en ion, whe e “DFT” usually deno es he
ans o m o ini e sequences. The pe iodic ini e case will be e e ed o he e
as he Disc e e Fou ie Se ies (DFS).
6.5 Pa se al’s Iden i y
Theo em 6.5 (Pa se al’s iden i y: pe iodic disc e e case).Le :{0,1, . . . , N−
1} → Cand de ine he inne p oduc
⟨ , g⟩:= 1
N
N−1
X
x=0
(x)g(x).
Le he exponen ial basis ϕk(x) = ei2π
Nkx,k= 0, . . . , N −1, which is o hono mal
unde ⟨·,·⟩. De ine Fou ie coe icien s
F(k) = ⟨ , ϕk⟩=1
N
N−1
X
x=0
(x)e−i2π
Nkx.
Then
1
N
N−1
X
x=0 | (x)|2=
N−1
X
k=0 |F(k)|2.
Equi alen ly,
N−1
X
x=0 | (x)|2=N
N−1
X
k=0 |F(k)|2.
P oo . Since {ϕk}is an o hono mal basis o he N-dimensional Hilbe space,
he o hogonal expansion holds: =PN−1
k=0 F(k)ϕkwi h F(k) = ⟨ , ϕk⟩. Ap-
plying ∥ ∥2=⟨ , ⟩and o hono mali y,
⟨ , ⟩=DX
k
F(k)ϕk,X
m
F(m)ϕmE=X
k,m
F(k)F(m)⟨ϕk, ϕm⟩=X
k|F(k)|2,
i.e. 1
NPx| (x)|2=Pk|F(k)|2.
Theo em 6.6 (Pa se al/Planche el: in ini e la ice (DFT in his pape )).Le
∈ L2(Z)and de ine i s disc e e Fou ie ans o m ( equency con inuous on
[−π, π])
F(ω) = X
x∈Z
(x)e−iωx, ω ∈[−π, π],
wi h in e se
(x) = 1
2πZπ
−π
F(ω)eiωx dω.
Then he Planche el iden i y holds:
X
x∈Z| (x)|2=1
2πZπ
−π|F(ω)|2dω.
51
P oo ske ch. Conside he isome ic isomo phism F:L2(Z)→L2([−π, π])
gi en by 7→ Fabo e. Using he o hogonali y 1
2πRπ
−πei(ω)(x−y)dω =δxy and
Fubini/Tonelli, compu e
1
2πZπ
−π|F(ω)|2dω =1
2πZX
x,y
(x) (y)e−iω(x−y)dω =X
x,y
(x) (y)δxy =X
x| (x)|2.
6.6 Jus i ica ion o he Fou ie Ansa z o Linea P∆E
The use o he Fou ie ansa z in sol ing linea pa ial di e ence equa ions is no
an ad hoc guess, bu a he a di ec consequence o he spec al p ope ies o
shi and di e ence ope a o s.
Conside i s he spa ial shi ope a o
(Exu)(x) = u(x+ 1).
I s eigen unc ions a e exponen ial unc ions o he o m eikx, since
Exeikx=eik(x+1) =eik eikx.
Thus eikx is an eigen unc ion o Exwi h eigen alue eik.
Simila ly, in he empo al di ec ion, he o wa d di e ence ope a o
∆ u( ) = u( + 1) −u( )
ac s on exponen ial unc ions eλ by
∆ eλ =eλ( +1) −eλ = (eλ−1) eλ .
Hence eλ is also an eigen unc ion, wi h eigen alue eλ−1.
Mo e gene ally, any linea di e ence ope a o cons uc ed om shi s and
ini e linea combina ions he eo has exponen ial unc ions as i s eigen unc ions.
Since linea P∆Es a e buil om such ope a o s, solu ions may be ep esen ed
as supe posi ions o sepa able modes o he o m
u( , x) = eλ eikx.
This explains he s anda d Fou ie ansa z: each exponen ial mode diagonalizes
he ope a o s in ol ed, educing he pa ial di e ence equa ion o an algeb aic
ela ion be ween λand k. By he p inciple o supe posi ion, he gene al solu ion
is hen ob ained by combining hese modes acco ding o he Fou ie expansion
o he ini ial da a.
6.7 Classi ica ion o Second O de Linea P∆E
Fo simplici y, le us conside a linea e olu ion equa ion wi h wo independen
a iables ( , x), o s uc u al o de 2, and wi hou mixed shi ope a o s:
aE u+bE−1
u+cExu+dE−1
xu+e u = 0, u =u( , x).
52
Fou ie –Laplace Ansa z. We employ he Fou ie –Laplace ansa z
u( , x) = eλ eikx,
whe e λ∈Cand k∈Rdeno e he empo al g ow h a e and spa ial equency,
espec i ely. Subs i u ing in o he equa ion yields
aeλ+be−λ+ceik +de−ik +e= 0.
Le
z=eλ, w =eik,
so ha he ela ion becomes he Lau en polynomial
Q(z, w) = az +bz−1+cw +dw−1+e= 0.
Classi ica ion. Sol ing o zin e ms o wgi es he dispe sion ela ion
z=eλ= (k).
The quali a i e beha iou o he solu ion is hen de e mined by he modulus o
z:
•I |z|<1, he solu ion decays in ime, co esponding o a di usi e/pa abolic
ype.
•I |z|= 1, he solu ion oscilla es wi hou g ow h o decay, co esponding
o a wa e/hype bolic ype.
•I |z|>1, he solu ion exhibi s exponen ial g ow h in ime, leading o
ins abili y o blow-up.
S eady-s a e p oblems. Fo pu ely s eady-s a e p oblems o he o m
aExu+bE−1
xu+cEyu+dE−1
yu+e u = 0, u =u(x, y),
we ins ead use he Fou ie ansa z
u(x, y) = eikxeimy,(k, m)∈R2,
which leads o he symbol
Q(w, ) = aw +bw−1+c +d −1+e= 0,
wi h w=eik, =eim. The s uc u e o he ze o se {(w, )∈C2:Q(w, )=0}
cha ac e izes he admissible s eady-s a e solu ions.
Example 6.1 (Disc e e Di usion Equa ion).Conside he disc e e di usion
equa ion
E u=1
2Exu+E−1
xu.
53

Fou ie –Laplace Ansa z. Take
u( , x) = eλ eikx, k ∈R.
Subs i u ing in o he equa ion gi es
eλ=1
2eik +e−ik= cos(k).
Dispe sion ela ion. Thus
z=eλ= cos(k).
Since |cos(k)|<1 o almos all k∈(0, π), he empo al g ow h a e sa is ies
ℜ(λ)<0in gene al.
Classi ica ion. The e o e he solu ion decays in ime and smoo hs ou oscil-
la ions. This beha iou co esponds o he pa abolic/di usi e ype, whe e he
solu ion ends o la en as → ∞.
Example 6.2 (Disc e e Laplace Equa ion).Conside he wo–dimensional dis-
c e e Laplace equa ion
∇2u= 0,
which in shi –ope a o o m eads
Exu+E−1
xu+Eyu+E−1
yu−4u= 0.
Fou ie Ansa z. Take
u(x, y) = eikxeimy,(k, m)∈R2.
Subs i u ing in o he equa ion yields
eik +e−ik +eim +e−im −4=0,
o equi alen ly
2 cos(k) + 2 cos(m)−4=0.
F equency condi ion. This educes o
cos(k) + cos(m)=2.
Since cos(θ)≤1, he only solu ion is
k≡0 (mod 2π), m ≡0 (mod 2π).
Conclusion. Hence he only admissible Fou ie modes a e cons an equen-
cies. The disc e e Laplace equa ion hus admi s only cons an solu ions (up o
bounda y condi ions), consis en wi h he con inuous case whe e ∆u= 0 admi s
only ha monic unc ions wi h i ial oscilla o y modes.
54
6.8 Disc e e Fou ie Analysis and Hadama d’s Well-posedness
Conside he wo-dimensional disc e e Laplace equa ion
Exu+E−1
xu+Eyu+E−1
yu−4u= 0.
Suppose we p esc ibe he ini ial condi ions
u(0, y) = (y), u(1, y) = g(y),
wi h no bounda y condi ions in he y-di ec ion.
Fou ie Ansa z. We ake
u(x, y) = ekxeimy, m ∈[−π, π],
and subs i u e in o he equa ion. The esul ing dispe sion ela ion is
cosh(k)=2−cos(m).
Hence
ek=e±cosh−1(2−cos m).
Obse a ion. Fo almos all equencies m, we ha e 2 −cos(m)>1, so ha
cosh−1(2 −cos m)>0. The e o e |ek|>1 o gene ic m, wi h he only neu al
case being m= 0 (mod 2π), whe e k= 0. This means ha mos Fou ie modes
lead o exponen ial g ow h in he x-di ec ion.
Gene al Solu ion. By Fou ie in e sion, he ull solu ion can be w i en as
u(x, y) = 1
2πZπ
−πA(m)excosh−1(2−cos m)+B(m)e−xcosh−1(2−cos m)eimy dm,
whe e he coe icien s A(m), B(m) a e de e mined by he ini ial da a (y), g(y).
Conclusion. Fo gene ic ini ial condi ions, unless all coe icien s A(m) anish,
he solu ion con ains g owing modes o he o m excosh−1(2−cos m)and he e o e
exhibi s unbounded g ow h (“blow-up”). This demons a es ha in e p e ing
he disc e e Laplace equa ion as an e olu ion equa ion leads o an ill-posed
p oblem in he sense o Hadama d: he solu ion is uns able wi h espec o he
ini ial da a.
Rema k 6.7. The Fou ie analysis shows ha he only s able mode is he i -
ial ze o- equency mode (m= 0), while almos all o he equencies p oduce
exponen ial g ow h. Thus he disc e e Laplace equa ion, i ein e p e ed as an
e olu ion law, is undamen ally uns able and ill-posed.
55
Hadama d’s Well-posedness in Pa ial Di e ence Equa ions
In analogy wi h he classical heo y o pa ial di e en ial equa ions (PDEs), we
ex end he concep o Hadama d well-posedness o pa ial di e ence equa ions
(P∆Es). A p oblem is said o be well-posed i i sa is ies he ollowing h ee
c i e ia:
1. Exis ence: Fo e e y admissible se o ini ial o bounda y da a, a solu ion
exis s.
2. Uniqueness: The solu ion is unique wi hin he p esc ibed unc ion space.
3. S abili y (Con inuous Dependence): The solu ion depends con inu-
ously on he ini ial and bounda y da a; in pa icula , small pe u ba ions
in he da a lead o only small changes in he solu ion.
I any o hese h ee condi ions ails, he p oblem is e e ed o as an ill-posed
p oblem. This amewo k allows us o analyze he s abili y p ope ies o P∆Es
in di ec analogy wi h PDEs.
56
7 Fi s O de Equa ions in Time
7.1 In oduc ion
In his sec ion, we s udy linea pa ial di e ence equa ions whose s uc u al
o de in he ime di ec ion is one. Such sys ems e ol e s ep by s ep in a manne
whe e he nex s a e depends only on he p esen s a e, and he e o e hey
may na u ally be e e ed o as Ma ko sys ems. These equa ions se e as
he disc e e- ime analogue o i s -o de e olu ion equa ions in he con inuous
se ing, and hey p o ide a undamen al amewo k o analyzing p opaga ion,
anspo , and p obabilis ic models in disc e e space- ime la ices.
De ini ion 7.1 (Ma ko Sys em).Le u:Z1+n→R(o C) be a unc ion o
disc e e ime ∈Zand spa ial a iables (x1, . . . , xn)∈Zn. A Ma ko sys em
is a i s –o de ime e olu ion equa ion o he o m
E u( , x) = F{Ek1
x1···Ekn
xnu( , x)}(k1,...,kn)∈S, , x,
whe e S⊂Znis a ini e index se . This means ha he s a e a ime + 1
depends only on he con igu a ion a ime , bu no on any ea lie imes.
7.2 1D Pascal E olu ion Equa ion
We now conside he linea pa ial di e ence equa ion inspi ed by he ecu ence
ela ion in combina o ics [23]
E u=u+E−1
xu, u :Z2→R,
wi h ini ial condi ion
u(0, x) = (x)∈ L2(Z),
and no bounda y condi ions.
Fou ie Ansa z. We apply he Fou ie ansa z
u( , x) = eλ eikx.
Subs i u ion in o he equa ion gi es he dispe sion ela ion
eλ= 1 + e−ik.
In eg al Rep esen a ion o he Solu ion. The gene al solu ion can be
w i en as
u( , x) = Zπ
−π
A(k) (1 + e−ik) eikx dk.
Using he ini ial condi ion = 0, we ob ain
u(0, x) = (x) = Zπ
−π
A(k)eikx dk.
57
In gene al, by induc ion,
X(x) = X(0)
(λ−1)(λ−2) ···(λ−x), x ≥1.
In alling ac o ial no a ion,
X(x) = X(0)
(λ−1)x
.
Cha ac e is ic Solu ion. Thus he sepa a ed solu ion is
uλ( , x) = λ
(λ−1)x
.
Gene al Solu ion. By linea supe posi ion, he gene al solu ion can be ex-
p essed as
u( , x) = X
λ
A(λ)λ
(λ−1)x
.
Ini ial Condi ion. The ini ial condi ion u(0, x) = δ(x) imposes he cons ain
u(0, x) = X
λ
A(λ)
(λ−1)x
.
- Fo x= 0:
u(0,0) = 1 = X
λ
A(λ).
- Fo x≥1:
u(0, x) = 0 = X
λ
A(λ)
(λ−1)x
.
This is p ecisely he s uc u e o a binomial in e sion o mula. Sol ing o
A(λ) gi es
A(λ) = (−1)x−λ
x!x
λ,0≤λ≤x.
Subs i u ing back, we ob ain
u( , x) = 1
x!
x
X
λ=0
(−1)x−λx
λλ .
Conclusion. The closed- o m exp ession o u( , x) is exac ly he S i ling num-
be o he second kind S( , x). Hence we conclude ha he S i ling numbe s
a ise na u ally as he G een’s unc ion o he non-au onomous pa ial di e ence
equa ion
E u=E−1
xu+xu.
64

8 Second O de Equa ions in Time
8.1 In oduc ion
In his sec ion, we s udy linea pa ial di e ence equa ions wi h s uc u al o de
2 in he ime di ec ion. Such sys ems depend no only on he p esen s a e bu
also on he p e ious ime s ep, analogous o second-o de e olu ion equa ions
in he con inuous se ing. They na u ally cap u e wa e-like and oscilla o y
beha iou in disc e e space- ime la ices.
Examples.
•One-dimensional equa ion:
E u=aE−1
xu+bu +cExu+pE−1
E−1
xu+qE−1
u+ E−1
Exu.
•Two-dimensional equa ion:
E u=u+E−1
xu+E−1
yu+E−1
u.
8.2 Second–O de Pascal E olu ion Equa ion
We conside he second–o de linea pa ial di e ence equa ion
E u=E−1
xu+Exu+E−1
u, u :Z2→R.
This equa ion ex ends he classical Pascal E olu ion Equa ion by including
a memo y e m h ough E−1
u. Consequen ly, he G een’s unc ion no longe
p oduces he s anda d Pascal iangle, bu ins ead gene a es a no el combina-
o ial s uc u e ha exhibi s duplica ion and oscilla o y pa e ns. We e e o
his sys em as he Second–O de Pascal E olu ion Equa ion.
Ini ial Condi ion.
u(0, x) = (x), u(1, x) = g(x)
, g ∈ L2(Z)
Fou ie Ansa z. We seek solu ions o he o m
u( , x) = eλ eikx.
Subs i u ion yields
eλ=e−ik +eik +e−λ.
Equi alen ly, wi h z=eλ, his gi es he quad a ic
z2−2 cos(k)z−1=0,
65
whose oo s a e
z±=z±(k) = cos(k)±p1 + cos2(k).
Gene al Solu ion. By supe posi ion, he solu ion admi s he Fou ie in eg al
ep esen a ion
u( , x) = 1
2πZπ
−πA(k)z
++B(k)z
−eikx dk,
whe e A(k), B(k) a e de e mined om he ini ial condi ions.
De e mina ion o Coe icien s. A = 0,
u(0, x) = (x) = 1
2πZπ
−πA(k) + B(k)eikx dk,
so ha
A(k) + B(k) = b
(k),b
(k) = X
x∈Z
(x)e−ikx.
A = 1,
u(1, x) = g(x) = 1
2πZπ
−πA(k)z+(k) + B(k)z−(k)eikx dk,
so ha
A(k)z+(k) + B(k)z−(k) = bg(k),bg(k) = X
x∈Z
g(x)e−ikx.
Thus,
A(k) = bg(k)−b
(k)z−(k)
z+(k)−z−(k), B(k) = b
(k)z+(k)−bg(k)
z+(k)−z−(k).
Final Rep esen a ion. The gene al solu ion is he e o e
u( , x) = 1
2πZπ
−π"bg(k)−b
(k)z−(k)
z+(k)−z−(k)z+(k) +b
(k)z+(k)−bg(k)
z+(k)−z−(k)z−(k) #eikx dk.
Special Case: Del a Ini ial Da a. Fo he choice
(x) = δ(x), g(x) = δ(x),
he Fou ie ans o ms a e b
(k) = bg(k) = 1. Thus,
u( , x) = 1
2πZπ
−π
(1 −z−)z
++ (z+−1)z
−
z+−z−
eikx dk.
This Fou ie in eg al ep esen s a special solu ion associa ed wi h he second–
o de Pascal E olu ion Equa ion and gene a es he no el combina o ial s uc-
u e obse ed in he nume ical pa e n.
66
Figu e 1: In ege a ay gene a ed by he Second–O de Pascal E olu ion Equa-
ion wi h wo–del a ini ial condi ion. No ice he duplica ed alues along he
diagonals and oscilla o y s uc u es eme ging inside he iangle.
67
8.3 Disc e e 1D Wa e Equa ion
We de ine he disc e e 1D wa e equa ion as
δ ∆ u=c2∇2u
whe e u=u( , x), wi h u:Z2→R, and he ope a o s a e de ined ia shi
ope a o s:
δ ∆ u=E u+E−1
u−2u,
δ u=u−E−1
u(backwa d di e ence),
∇2u=Exu+E−1
xu−2u(disc e e Laplacian).
Physical In e p e a ion. This equa ion models a sys em o coupled oscilla-
o s a anged on a one-dimensional la ice. Each oscilla o in e ac s wi h i s
nea es neighbou s, and he e m ∇2u ep esen s he ne es o ing o ce. The
pa ame e cis a cons an ha go e ns he wa e p opaga ion speed in he dis-
c e e medium.
Solu ion
We conside he disc e e wa e equa ion
δ ∆ u=c2∇2u,
which in shi –ope a o o m eads
E u+E−1
u−2u=c2Exu+E−1
xu−2u, u :Z2→R.
Ini ial and bounda y condi ions.
u(0, x) = (x), u(1, x) = g(x)
, g ∈ L2(Ω),Ω = {x∈Z: 1 ≤x≤L−1}
u( , 0) = u( , L)=0.
Sepa a ion o a iables. We assume
u( , x) = T( )X(x).
Subs i u ion gi es
E T−2T+E−1
T
T=c2ExX−2X+E−1
xX
X=−λ,
o some sepa a ion cons an λ.
68
Spa ial p oblem (Disc e e S u m–Liou ille).
ExX−2X+E−1
xX=−λ
c2X, X(0) = X(L) = 0.
The eigen unc ions and eigen alues a e
Xn(x) = sinnπ
Lx, λn= 4c2sin2nπ
2L, n = 1,2, . . . , L −1.
Tempo al p oblem.
E T−2T+E−1
T=−λT.
I s cha ac e is ic polynomial is
z2−(2 −λ)z+ 1 = 0,
wi h oo s
z±(λ) = 2−λ±p(2 −λ)2−4
2.
Hence
Tn( ) = Anz+(λn) +Bnz−(λn) .
Mode solu ions. The n- h mode is
un( , x) = Anz+(λn) +Bnz−(λn) sinnπ
Lx.
Gene al solu ion.
u( , x) =
L−1
X
n=1 Anz+(λn) +Bnz−(λn) sinnπ
Lx.
De e mina ion o coe icien s. F om u(0, x) = (x) and u(1, x) = g(x), we
expand:
(x) =
L−1
X
n=1
(An+Bn) sinnπ
Lx,
g(x) =
L−1
X
n=1
(Anz+(λn) + Bnz−(λn)) sinnπ
Lx.
By o hogonali y o he sine basis,
An+Bn=2
L
L−1
X
x=1
(x) sinnπ
Lx,
69

Anz+(λn) + Bnz−(λn) = 2
L
L−1
X
x=1
g(x) sinnπ
Lx.
Explici o mulas. Sol ing his 2 ×2 linea sys em gi es
An=1
z+(λn)−z−(λn) 2
L
L−1
X
x=1 g(x)−z−(λn) (x)sinnπ
Lx!,
Bn=1
z−(λn)−z+(λn) 2
L
L−1
X
x=1 g(x)−z+(λn) (x)sinnπ
Lx!.
Thus he ull solu ion is comple ely de e mined.
Rema k 8.1. The empo al pa o he solu ion is exp essed in e ms o he
cha ac e is ic oo s
Tn( ) = Anz
n,++Bnz
n,−, zn,±=2−λn±p(2 −λn)2−4
2.
When he disc iminan is nega i e, he oo s zn,±a e complex conjuga es and
he solu ion can be ew i en in igonome ic o m using cos(ωn )and sin(ωn ).
O he wise, when he oo s a e eal, i is mo e na u al o keep he exponen ial
ep esen a ion. Bo h o ms a e ma hema ically equi alen and depend only on
he spec al pa ame e λn.
70
9 S eady S a e P oblems
9.1 In oduc ion
In his chap e , we s udy he s a iona y o s eady-s a e p oblem o disc e e
ield equa ions. Ou goal is o de elop a disc e e analogue o he classical ellip ic
heo y a ising in con inuous pa ial di e en ial equa ions.
We begin by in oducing he disc e e coun e pa s o he Laplace and Pois-
son equa ions, de ined on in ege la ices Zno on ini e disc e e domains wi h
p esc ibed bounda y condi ions. In addi ion o he s anda d nea es -neighbou
Laplacian, we also p opose he Moo e Laplacian and he co esponding Moo e
Poisson equa ion, ob ained by ex ending he s encil o he ull Moo e neigh-
bou hood. These ope a o s e ain many o he s uc u al p ope ies o hei
con inuous ellip ic coun e pa s, such as sel -adjoin ness, posi i i y, and dis-
c e e maximum p inciples, while encoding iche geome ic o combina o ial
in e ac ions.
The disc e e ellip ic equa ions conside ed he e ake he gene al o m
Lu= ,
whe e Lis one o he Laplace- ype ope a o s in oduced abo e. We will examine
he sol abili y, p ope ies o solu ions, and he ela ionship be ween hese dis-
c e e o mula ions and he classical ellip ic PDEs. In pa icula , we show ha
he disc e e equa ions exhibi beha io closely analogous o con inuous ellip ic
p oblems, including smoo hing e ec s, uniqueness o solu ions, and ha monici y
on disc e e domains.
71
9.2 2D Disc e e Laplace Equa ion
We now conside he wo-dimensional disc e e Laplace equa ion
δx∆xu+δy∆yu= 0, u =u(x, y),
subjec o he Di ichle bounda y condi ions
u(0, y) = u(L, y) = u(x, M)=0, u(x, 0) = (x), (0) = (L) = 0.
Sepa a ion o Va iables. We seek a sepa able solu ion o he o m
u(x, y) = X(x)Y(y).
Subs i u ing in o he equa ion gi es
Y(y)δx∆xX+X(x)δy∆yY= 0,
which can be ea anged as
δx∆xX
X(x)+δy∆yY
Y(y)= 0.
Thus, each e m mus equal a cons an −λ, gi ing wo o dina y di e ence equa-
ions:
δx∆xX=−λX, δy∆yY=λY.
Shi Ope a o Fo m. Using he shi ope a o s Exand Ey, hese can be
w i en as
ExX+E−1
xX−2X=−λX, (1)
EyY+E−1
yY−2Y=λY. (2)
Solu ion o X(x).Expanding Eq. (1) gi es
ExX+E−1
xX= (2 −λ)X.
Assume a ial solu ion X(x) = x, leading o he cha ac e is ic equa ion
+1
= 2 −λ, o equi alen ly, 2−(2 −λ) + 1 = 0.
The oo s a e
±=e±iθ,wi h cos θ= 1 −λ
2.
Hence he gene al solu ion o X(x) is
X(x) = Acos(θx) + Bsin(θx).
Applying he Di ichle condi ions X(0) = X(L) = 0 yields
A= 0, θn=nπ
L, n = 1,2, . . . , L −1,
so ha
Xn(x) = sinnπx
L, λn= 4 sin2nπ
2L.
72
Solu ion o Y(y).Subs i u ing λnin o Eq. (2) gi es
EyY+E−1
yY= (2 + λn)Y.
Assume Y(y) = y, gi ing
+1
= 2 + λn, ±=e±µn,whe e cosh µn= 1 + λn
2.
Thus he gene al solu ion is
Yn(y) = Cneµny+Dne−µny.
Applying he bounda y condi ion Y(M) = 0 gi es
Yn(y) = sinhµn(M−y),
up o no maliza ion, and we se Yn(0) = 1 o con enience:
Yn(y) = sinhµn(M−y)
sinh(µnM).
Comple e Solu ion. By he supe posi ion p inciple, he ull solu ion sa is-
ying u(x, 0) = (x) is
u(x, y) =
L−1
X
n=1
Ansinnπx
Lsinhµn(M−y)
sinh(µnM),whe e cosh µn= 1+2 sin2nπ
2L.
The coe icien s Ana e de e mined om he bounda y da a:
(x) =
L−1
X
n=1
Ansinnπx
L.
Hence,
An=2
L
L−1
X
x=1
(x) sinnπx
L.
Final Fo m. The disc e e Laplace equa ion wi h Di ichle bounda y condi-
ions admi s he o mal solu ion
u(x, y) =
L−1
X
n=1 "2
L
L−1
X
x′=1
(x′) sinnπx′
L#sinnπx
Lsinhµn(M−y)
sinh(µnM),
whe e
λn= 4 sin2nπ
2L,cosh µn= 1 + λn
2.
73
2D case.
δ ∆ u=c2δx∆xu+δy∆yu.
3D case.
δ ∆ u=c2δx∆xu+δy∆yu+δz∆zu.
4. Moo e Hea Equa ion
The Moo e Laplacian in wo dimensions is de ined as
∇2
Mu:= δx∆xu+δy∆yu+δx∆xδy∆yu.
The Moo e hea equa ion is hen
∆ u=α∇2
Mu.
2D case.
∆ u=αδx∆xu+δy∆yu+δx∆xδy∆yu.
3D case. The na u al 3D Moo e Laplacian includes all wo–coo dina e cou-
plings:
∇2
Mu=∇2u+δx∆xδy∆yu+δy∆yδz∆zu+δz∆zδx∆xu
+δx∆xδy∆yδz∆zu.
Hence he 3D Moo e hea equa ion becomes
∆ u=α∇2
Mu.
5. Moo e Wa e Equa ion
The Moo e wa e equa ion is de ined as
δ ∆ u=c2∇2
Mu.
2D case.
δ ∆ u=c2δx∆xu+δy∆yu+δx∆xδy∆yu.
3D case.
δ ∆ u=c2∇2
Mu,
wi h ∇2
Mgi en by he ull Moo e coupling s uc u e abo e.
80

9.6 Lis o S eady S a e P oblems
S eady s a e p oblems a ise na u ally om disc e e e olu ion equa ions by im-
posing he condi ion
∆ u= 0.
In his sec ion we summa ize se e al undamen al s eady s a e equa ions in he
heo y o pa ial di e ence equa ions.
1. Disc e e Laplace Equa ion
The disc e e Laplace equa ion is de ined by
∇2u= 0.
Explici ly:
•1D:
δx∆xu= 0.
•2D:
δx∆xu+δy∆yu= 0.
•3D:
δx∆xu+δy∆yu+δz∆zu= 0.
2. Disc e e Poisson Equa ion
The disc e e Poisson equa ion is he disc e e analogue o ∇2u=− :
∇2u=− .
Explici o ms:
•1D:
δx∆xu=− (x).
•2D:
δx∆xu+δy∆yu=− (x, y).
•3D:
δx∆xu+δy∆yu+δz∆zu=− (x, y, z).
81
3. Moo e Laplace Equa ion
Using he Moo e neighbou hood, he Moo e Laplacian sa is ies
∇2
Mu= 0.
Explici ly:
•2D:
δx∆xu+δy∆yu+δx∆xδy∆yu= 0.
•3D:
∇2u+δx∆xδy∆yu+δy∆yδz∆zu+δz∆zδx∆xu+δx∆xδy∆yδz∆zu= 0.
4. Moo e Poisson Equa ion
The Moo e Poisson equa ion is de ined by
∇2
Mu=− .
Explici o ms:
•2D:
δx∆xu+δy∆yu+δx∆xδy∆yu=− (x, y).
•3D:
∇2u+δx∆xδy∆yu+δy∆yδz∆zu+δz∆zδx∆xu+δx∆xδy∆yδz∆zu=− (x, y, z).
5. Disc e e Biha monic Equa ion
The disc e e biha monic equa ion is de ined by
∇4u= 0,∇4:= (∇2)2.
Explici ly:
•1D:
∇4u= (∇2)2u=δ2
x∆2
xu= 0.
•2D:
δ2
x∆2
xu+δ2
y∆2
yu+ 2 δx∆xδy∆yu= 0.
•3D:
∇4u= (δx∆x+δy∆y+δz∆z)2u= 0.
These s eady s a e p oblems may be sol ed using sepa a ion o a iables,
eigen alue me hods, and disc e e Fou ie se ies expansions.
82
10 Disc e e E olu ion Equa ions
10.1 In oduc ion
In his chap e , we de elop he heo e ical amewo k o disc e e spa io empo-
al dynamical sys ems and in oduce he concep o disc e e e olu ion equa ions.
Ou aim is o es ablish a igo ous pa allel be ween con inuous e olu ion equa-
ions, which a ise in he s udy o pa ial di e en ial equa ions (PDEs), and hei
ully disc e e coun e pa s de ined on he la ice Zn.
We begin by de ining disc e e dynamical sys ems and o mula ing disc e e
e olu ion equa ions in ope a o o m. The connec ion o semig oup heo y is
hen discussed, p o iding he algeb aic ounda ion o he ime e olu ion o such
sys ems.
Subsequen ly, we classi y well-posed p oblems in o h ee main ypes: ini ial
alue p oblems,bounda y alue p oblems, and ini ial-bounda y alue p oblems.
These se ings se e as he na u al disc e e analogues o he classical PDE he-
o y.
Finally, we in oduce he dis inc ion be ween au onomous and non-au onomous
sys ems, depending on whe he he upda e ope a o depends explici ly on he
independen a iables. Toge he , hese elemen s o m a comp ehensi e heo y
o disc e e e olu ion equa ions, laying he g oundwo k o subsequen analysis
and applica ions.
10.2 De ini ions
De ini ion 10.1 (Disc e e Dynamical Sys em).Le Xbe a se ( ypically a me -
ic space, opological space, o Banach space). A disc e e dynamical sys em
is a pai (X, φ)whe e
φ:X→X
is a mapping (o en con inuous i Xhas a opology).
The dynamics is de ined by i e a ion:
un+1 =φ(un), n ∈Z≥0, u0∈X.
Equi alen ly, o each n∈Z≥0, we de ine he n- h i e a e
φn(x) := φ◦φ◦···◦φ
| {z }
n imes
(x),
so ha he ajec o y o x∈Xis gi en by
{φn(x) : n∈Z≥0}.
[9]
De ini ion 10.2 (Disc e e Spa io empo al Dynamical Sys em).Le
u:N0×Zn→C
deno e he s a e o he sys em, whe e
83
• ∈N0is he disc e e ime,
•x∈Znis he disc e e spa ial coo dina e.
Adisc e e spa io empo al dynamical sys em is go e ned by an equa ion
o he o m
E u( , x) = F{Em
Ek
xu( , x)}(m,k)∈S, , x,
whe e
•Em
u( , x) = u( +m, x)is he ime–shi ope a o ,
•Ek
xu( , x) = u( , x+k)is he spa ial shi ope a o ,
•S⊂Zn+1 is a ini e index se speci ying which ime–space shi s appea ,
•Fis a p esc ibed unc ion, possibly nonlinea .
De ini ion 10.3 (Disc e e E olu ion Equa ion).Le Xbe a Banach space, and
le A:X→Xbe a linea ope a o . A disc e e e olu ion equa ion is an
i e a i e ela ion o he o m
E u=Au +F(u, ),
ha is,
u( + 1) = Au( ) + F(u( ), ), ∈Z≥0,
whe e
•u:Z≥0→Xis he unknown sequence (o disc e e ajec o y),
•A:X→Xis a linea ope a o , ep esen ing he linea pa o he dy-
namics,
•F:X×Z≥0→Xis a linea o nonlinea mapping, ep esen ing he
o cing o nonlinea in e ac ion e m.
An ini ial condi ion
u(0) = u0∈X
is p esc ibed, and he disc e e e olu ion equa ion de e mines he ajec o y {u( )} ≥0.
Example 10.1 (Linea E olu ion Equa ion: Fibonacci Equa ion).Conside
he ecu ence ela ion
E x=x+E−1
x,
whe e x=x( )and x:Z→R. This is a linea o dina y di e ence equa-
ion o o de 2, commonly known as he Fibonacci equa ion.
Example 10.2 (Nonlinea E olu ion Equa ion: Logis ic Map).Conside he
nonlinea ecu ence
E x= x(1 −x),
whe e x=x( )and x:Z→R.
This is a nonlinea o dina y di e ence equa ion, amously known as
he logis ic map, which plays a cen al ole in he s udy o chaos heo y.
84
[26]
Example 10.3 (Disc e e E olu ion Equa ion: Vec o Equa ion).Conside he
disc e e scala ield u=u( , x)wi h ∈N0,x∈Z. The e olu ion is go e ned
by he equa ion
E u=u+E−1
xu+Exu+E−1
u+E−2
u.
De ine auxilia y a iables
( , x) := E−1
u( , x) = u( −1, x), w( , x) := E−2
u( , x) = u( −2, x).
Then he sys em can be ew i en as
E u=u+E−1
xu+Exu+ +w,
E =u,
E w= .
In oducing he ec o - alued unc ion
u=u( , x) := 

u( , x)
( , x)
w( , x)
,
he sys em akes he compac ope a o o m
E u=Au,
whe e Ais a linea ope a o ac ing on ude ined by
A

u
w
=

u+E−1
xu+Exu+ +w
u

.
Example 10.4 (Nonlinea E olu ion Equa ion: Rule 110).Conside he one-
dimensional cellula au oma on Rule 110, which can be exp essed as a nonlin-
ea pa ial di e ence equa ion:
E u= mod2u+Exu+u Exu+u Exu E−1
xu,
whe e
u:N0×Z→Z2, u =u( , x).
This sys em is well-known o i s Tu ing comple eness. I can be ega ded
as a nonlinea e olu ion equa ion o he o m
E u=Au +F(u, ),
wi h
A= 0, F(u, ) = mod2u+Exu+u Exu+u Exu E−1
xu.
85

[33]
Example 10.5 (Lang on’s An as a Sys em o Coupled Di e ence Equa ions).
Conside he ollowing sys em:
E u=u+ (1 −2u)·δ(x−X)δ(y−Y),
E d= mod4d+ (1 −2u( , X, Y )),
E X=X+ cosπ
2·E d,
E Y=Y−sinπ
2·E d,
whe e:
•u=u( , x, y)∈ {0,1}is he s a e o he la ice a ime and posi ion
(x, y), i.e. u:Z3→ {0,1}.
•d=d( )∈ {0,1,2,3}is he an ’s di ec ion a ime , i.e. d:Z→Z4.
•(X( ), Y ( )) ∈Z2is he posi ion o he an , wi h X, Y :Z→Z.
•The modulo ope a o is de ined as
mod4(x) = x−4·x
4.
This yields a coupled nonlinea e olu ion sys em consis ing o :
•One pa ial di e ence equa ion o he la ice s a e u( , x, y).
•Th ee o dina y di e ence equa ions o he an ’s in e nal s a e: he di ec-
ion d( ), and he posi ion (X( ), Y ( )).
[7]
Obse a ions and Phenomena
The ollowing igu e illus a es he e olu ion o Lang on’s An o e disc e e
ime s eps.
86
Figu e 2: The e olu ion o Lang on’s An o e ime. The black squa es ep esen
lipped cells (s a e 1), he whi e backg ound deno es un isi ed cells (s a e 0),
and he ed do indica es he cu en posi ion o he an a he inal ime s ep.
The sys em exhibi s ansien chaos, ollowed by he eme gence o a epea ing
s uc u e called he highway, which ac s as a pe iodic a ac o in he phase
space.
87
10.3 Semig oup Theo y
De ini ion 10.4 (Semig oup).Le Xbe a se . A semig oup is a pai (X, ·)
whe e ·:X×X→Xis a bina y ope a ion sa is ying he associa i i y p ope y:
(x·y)·z=x·(y·z),∀x, y, z ∈X.
I he e exis s an elemen e∈Xsuch ha
e·x=x·e=x, ∀x∈X,
hen (X, ·)is called a monoid, and eis called he iden i y elemen .
[30]
De ini ion 10.5 (Disc e e Ope a o Semig oup).Le Xbe a Banach space and
T:X→Xa bounded linea ope a o . The amily {Tn}n∈N0de ined by
Tn:= T◦T◦···◦T
| {z }
n imes
, T0:= I,
is called a disc e e ope a o semig oup gene a ed by T.
Theo em 10.6 (Solu ion o Linea Disc e e E olu ion Equa ion).Le Xbe a
Banach space, T:X→Xa bounded linea ope a o , and u0∈X. Then he
solu ion o
E u=u( + 1) = Tu( ), u(0) = u0,
is gi en explici ly by
u( ) = T u0, ∈N0.
Example 10.6 (S abili y o he Disc e e Hea Equa ion Semig oup).Conside
he disc e e hea equa ion
E u=u+α∇2u, u(0, x) = (x)∈ L2(Z),
whe e ∇2u=u( , x + 1) −2u( , x) + u( , x −1) is he disc e e Laplacian. De ine
he e olu ion ope a o
T=I+α∇2:L2(Z)→ L2(Z).
Then:
1. Tis a bounded linea ope a o . The e o e {T } ∈N0 o ms a disc e e op-
e a o semig oup, and he solu ion always exis s, gi en by
u( ) = T , ∈N0.
2. The Fou ie symbol o Tis
b
T(k)=1−4αsin2k
2, k ∈[−π, π].
3. The sys em is s able (i.e. ∥T ∥L2≤ ∥ ∥L2 o all ) i and only i
0< α ≤1
2.
I α > 1
2, hen he e exis modes ha g ow exponen ially, and he solu ion
explodes.
88
10.4 Ini ial Value P oblems
De ini ion 10.7 (Ini ial Value P oblem o Disc e e E olu ion Equa ions).Le
u=u( , x)deno e he s a e o he sys em, whe e
( , x)∈N0×Zn,
wi h ∈N0 ep esen ing disc e e ime and x∈Zn ep esen ing disc e e space.
Adisc e e ini ial alue p oblem is gi en by
E u=Au+F(u, , x),
subjec o he ini ial condi ion
u(0,x) = (x),x∈Zn,
wi h no bounda y condi ions imposed. He e Ais a linea ope a o and Fis a
(possibly nonlinea ) unc ion.
Example 10.7 (Ini ial Value P oblem: Rule 90 Cellula Au oma on).Conside
he Rule 90 cellula au oma on, exp essed as a pa ial di e ence equa ion:
E u= mod2E−1
xu+Exu,
whe e
u:Z2→Z2.
The ini ial condi ion is gi en by
u(0, x) = (x)∈B(Z),
wi h no bounda y condi ion imposed.
I we ake
(x) = δ(x),
whe e δ(x)is he K onecke del a, hen he explici solu ion is
u( , x) = mod2C(2 , x + ),
whe e
C(n, k) = 


n!
k!(n−k)!,0≤k≤n,
0,o he wise.
This solu ion gene a es he well-known Sie pinski iangle.
[33]
89
Expanding he inomial yields
(1 + e−ik +e−im) =X
a+b+c=
a,b,c≥0
!
a!b!c!e−ikae−imb,
so ha
G( , x, y) = 
−x−y, x, y.
Con olu ion Fo m o he Solu ion. The e o e, he gene al solu ion can be
w i en in con olu ion o m:
u( , x, y) = X
(s,p)∈Z2
(s, p)C( , x −s, y −p),
whe e
C( , x, y) = 




!
( −x−y)! x!y!,i 0 ≤x, y ≤ and x+y≤ ,
0,o he wise.
Fou ie –Combina o ial Iden i y. This es ablishes he iden i y
1
(2π)2Zπ
−πZπ
−π1 + e−ik +e−im ei(kx+my)dk dm =
−x−y, x, y,
which shows ha he inomial coe icien a ises na u ally as he G een’s unc-
ion o he 2D Pascal E olu ion Equa ion.
11.3 3D Pascal E olu ion Equa ion
We now conside a simple linea pa ial di e ence equa ion in h ee spa ial
dimensions:
E u=u+E−1
xu+E−1
yu+E−1
zu, u :Z4→R.
The ini ial condi ion is p esc ibed as
u(0, x, y, z) = (x, y, z)∈ L2(Z3),
wi h no bounda y condi ions.
Fou ie Ansa z. We apply he Fou ie ansa z
u( , x, y, z) = eλ ei(kx+my+nz).
Subs i u ion in o he equa ion gi es he dispe sion ela ion
eλ= 1 + e−ik +e−im +e−in.
96

In eg al Rep esen a ion o he Solu ion. Hence he gene al solu ion can
be exp essed in Fou ie o m as
u( , x, y, z) = 1
(2π)3Zπ
−πZπ
−πZπ
−πb
(k, m, n) (1+e−ik+e−im+e−in) ei(kx+my+nz)dk dm dn,
whe e b
(k, m, n) deno es he disc e e Fou ie ans o m o he ini ial da a:
b
(k, m, n) = X
x,y,z∈Z
(x, y, z)e−i(kx+my+nz).
G een’s Func ion. Fo he del a ini ial condi ion (x, y, z) = δ(x)δ(y)δ(z),
we ob ain he G een’s unc ion
G( , x, y, z) = 1
(2π)3Zπ
−πZπ
−πZπ
−π
(1+e−ik+e−im+e−in) ei(kx+my+nz)dk dm dn.
Expanding he mul inomial e m and e alua ing he in eg al, we ind
G( , x, y, z) = C( , x, y, z)
whe e
C( , x, y, z) = 




!
( −x−y−z)! x!y!z!,i 0 ≤x, y, z ≤ and x+y+z≤ ,
0,o he wise.
which is he mul inomial coe icien , p o ided all en ies a e nonnega i e,
and 0 o he wise.
Con olu ion Fo m o he Solu ion. The e o e, he solu ion can also be
w i en in con olu ion o m:
u( , x, y, z) = X
s,p,q∈Z
(s, p, q)C , x −s, y −p, z −q.
Fou ie –Mul inomial Iden i y. This yields he iden i y
1
(2π)3Zπ
−πZπ
−πZπ
−π
(1+e−ik+e−im+e−in) ei(kx+my+nz)dk dm dn =
−x−y−z, x, y, z .
In o he wo ds, he G een’s unc ion o he 3D Pascal E olu ion Equa ion is
exac ly gi en by mul inomial coe icien s.
97
11.4 n-Dimensional Pascal E olu ion Equa ion
We now p opose a gene al linea pa ial di e ence equa ion in nspa ial dimen-
sions, ex ending he binomial and inomial cases.
Equa ion.
E u=u+E−1
x1u+E−1
x2u+···+E−1
xnu, u :Zn+1 →R.
Ini ial condi ion:
u(0,x) = (x)∈ L2(Zn),
wi h no bounda y condi ions.
Fou ie Ansa z. We apply he Fou ie ansa z
u( , x) = eλ ei(k1x1+···+knxn).
Subs i u ion gi es he dispe sion ela ion
eλ= 1 + e−ik1+e−ik2+···+e−ikn.
In eg al Rep esen a ion. Thus he gene al solu ion has he Fou ie in eg al
o m
u( , x) = 1
(2π)nZ[−π,π]nb
(k)1 + e−ik1+···+e−ikn ei(k1x1+···+knxn)dk,
whe e b
(k) is he disc e e Fou ie ans o m o .
G een’s Func ion. Fo he del a ini ial condi ion (x) = δ(x), we ob ain
G( , x) = 1
(2π)nZ[−π,π]n1 + e−ik1+···+e−ikn ei(k1x1+···+knxn)dk.
This in eg al can be iden i ied wi h he mul inomial coe icien in disc e e
o m:
G( , x) = C( , x) = 




!
( −Pn
j=1 xj)! x1!···xn!,i Pn
j=1 xj≤ and xj≥0,
0,o he wise.
Con olu ion Fo m o he Solu ion. The e o e he gene al solu ion can also
be w i en in con olu ion o m:
u( , x) = X
s∈Zn
(s)C , x−s.
This es ablishes he n-dimensional Pascal E olu ion Equa ion, whe e he G een’s
unc ion is gi en by he mul inomial coe icien , gene alizing he binomial and
inomial cases.
98
Theo em 11.1 (Fou ie –Mul inomial Iden i y).Le k= (k1, . . . , kn)∈[−π, π]n
and x= (x1, . . . , xn)∈Zn. Fo ∈Nwe ha e
1
(2π)nZ[−π,π]n
1 +
n
X
j=1
e−ikj

ei(k·x)dk=C( , x),
whe e C( , x)is he mul inomial coe icien
C( , x) = 




!
( −Pn
j=1 xj)! x1!···xn!,i Pn
j=1 xj≤ and xj≥0,
0,o he wise.
99
12 Nonlinea Equa ions wi h mod n Nonlinea -
i y
12.1 In oduc ion
In his sec ion, we ocus exclusi ely on nonlinea pa ial di e ence equa ions
wi h mod nnonlinea i y. In pa icula , we demons a e ha se e al classical
sel –simila ac als can be ealized as exac solu ions o such e olu iona y sys-
ems.
We p opose and analyze pa ial di e ence equa ions co esponding o h ee
well–known ac als:
• he Sie pinski iangle,
• he Sie pinski ca pe ,
• he Sie pinski py amid.
Fo each case, we de i e he analy ic o m o he solu ion by applying he
linea G een’s unc ion ep esen a ion, ollowed by educ ion modulo n. This
app oach e eals ha hese ac als a e no me ely geome ic cons uc s de ined
by i e a ed unc ion sys ems (IFS), bu can also be unde s ood as solu ions o
explici ly de ined nonlinea e olu ion equa ions.
12.2 Righ –Side Sie pinski T iangle Equa ion
We now conside he nonlinea pa ial di e ence equa ion
E u= mod2u+E−1
xu, u :Z2→R.
Ini ial Condi ion. We impose
u(0, x) = (x)∈ L2(Z)
wi h no bounda y condi ions.
Rela ion o he Linea Case. F om he p e ious sec ion, he linea equa ion
E u=u+E−1
xu
admi s he con olu ion solu ion
u( , x) = X
s∈Z
(s)C( , x −s),
whe e
C( , y) = 


y,0≤y≤ ,
0,o he wise.
100
Nonlinea Modula Sys em. Fo he modula sys em, he solu ion becomes
u( , x) = mod2 X
s∈Z
(s)C( , x −s)!.
Del a Ini ial Condi ion. I (x) = δ(x), hen
u( , x) = mod2C( , x).
This e olu ion p oduces a il ed Sie pinski iangle pa e n.
Spa io empo al Pa e ns.
•Fo (x) = δ(x), he e olu ion yields a pe ec sel –simila ac al s uc u e
(Sie pinski iangle).
•Fo andom ini ial condi ions wi h (x)∈ {0,1}, he dynamics s ill exhibi
ac al–like iangula pa e ns.
•Fo eal– alued andom ini ial condi ions (x)∈R, he sys em displays
spa io empo al chaos.
101

Figu e 3: Spa io empo al plo o δini ial condi ion.
102
Figu e 4: Random ini ial condi ion wi h (x)∈ {0,1}.
103
Figu e 5: Random ini ial condi ion wi h (x)∈R.
12.3 Sie pinski Ca pe Equa ion
A collabo a o o mine, Wu Han (China), p oposed he ollowing nonlinea
pa ial di e ence equa ion wi h modula educ ion:
E u= mod3E−1
xu+Exu+E−1
u, u :Z2→R.
Ini ial Condi ion. We impose wo del a ini ial condi ions
u(0, x) = u(1, x) = δ(x),
wi h no bounda y condi ions.
Nume ical Obse a ion.
104
Figu e 6: The spa io empo al plo o his sys em e eals a s iking ac al pa -
e n: he e olu ion gene a es a Sie pinski ca pe . The p ecise ma hema ical
eason o his eme gence is no ye unde s ood, bu he nume ical e idence is
compelling.
Rela ion o he Linea Case. F om he p e ious sec ion, he co esponding
linea sys em wi hou he modula educ ion has he G een’s unc ion
K( , x) = 1
2πZπ
−π
(1 −z−)z
++ (z+−1) z
−
z+−z−
eikx dk,
wi h cha ac e is ic oo s
z±=z±(k) = cos(k)±p1 + cos2(k).
Modula Reduc ion. Fo he nonlinea modula sys em, he solu ion wi h
del a ini ial condi ions is gi en by
u( , x) = mod3K( , x).
F ac al Eme gence. Rema kably, his modula educ ion ans o ms he os-
cilla o y in ege s uc u e o K( , x) in o a pe ec sel –simila ac al, he Sie -
pinski ca pe .
12.4 Sie pinski Py amid Equa ion
We p opose he nonlinea pa ial di e ence equa ion
E u= mod2u+E−1
xu+E−1
yu, u :Z3→R.
Ini ial Condi ion.
u(0, x, y) = (x, y)∈ L2(Z2),
105
Figu e 11: Spa io empo al e olu ion o he Mod 5 Sie pi´nski Equa ion
12.7 Mod 4 Sie pinski F ac al Equa ion
We conside he ollowing nonlinea pa ial di e ence equa ion:
E u= mod4E−1
xu+u+Exu+δ(x)
wi h ini ial condi ion:
u(0, x) = δ(x)
and no bounda y condi ion.
u=u( , x)∈ {0,1,2,3}
He e, δ(x) is he disc e e del a unc ion de ined by:
δ(x) = (1,i x= 0
0,o he wise
The alues o u( , x) a e es ic ed o {0,1,2,3}, and we isualize hem using
he ollowing colou scheme:
Value Colou
0 Whi e
1 G een
2 Pu ple
3 Yellow
The spa io empo al plo o his equa ion is shown below:
112

We obse e ha his sys em gene a es a s ikingly complica ed ac al s uc-
u e, eminiscen o a Sie pinski iangle, bu wi h iche pe iodic colou laye s.
Despi e i s simplici y, he sys em exhibi s highly non i ial dynamics ha may
e lec deep combina o ial o algeb aic pa e ns.
113
12.8 F ac als as Solu ions o E olu ion Equa ions
T adi ionally, many well–known ac als such as he Sie pinski iangle, he Sie -
pinski ca pe , and he Sie pinski py amid a e gene a ed ia I e a ed Func ion
Sys ems (IFS) [13, 14] o pu ely geome ic cons uc ions. In his wo k, how-
e e , we ha e obse ed ha hese ac als can also eme ge as exac solu ions o
sui able e olu ion equa ions. This p o ides a no el pe spec i e, e ealing deep
connec ions be ween di e ence equa ions and ac al geome y.
In pa icula , we no ed ha he G een’s unc ions o se e al linea pa ial di -
e ence equa ions coincide wi h classical combina o ial numbe s (e.g. binomial,
inomial, and mul inomial coe icien s). When hese coe icien s a e educed
modulo a small in ege , he esul ing solu ions display exac ac al pa e ns.
Hence, pa ial di e ence equa ions na u ally uni y Fou ie analysis, combina-
o ics, ac al geome y, and chaos heo y.
Fu he mo e, he linea equa ions wi hou modula educ ion p oduce solu ions
ha g ow inde ini ely, co esponding o a “s e ching” mechanism. The modula
educ ion ac s as a “ olding” s ep ha o ces he solu ion alues back in o a
bounded ange. This in e play o s e ching and olding is p ecisely he cen al
mechanism esponsible o chao ic dynamics. [2]
We also obse ed ha o many nonlinea o chao ic sys ems, when he ini ial
condi ion o o cing e m is a del a unc ion, he solu ion is a pe ec sel –simila
ac al. On he o he hand, i he ini ial condi ion is andom, he solu ion e ol es
in o spa io empo al chaos. F om he con olu ion ep esen a ions, i ollows ha
he nonlinea solu ions can be exp essed as supe posi ions o e olu ion ke nels,
and we conjec u e ha some spa io empo al chaos can be unde s ood as he
nonlinea supe posi ion o many ac al ke nels.
114
13 Sys em o Pa ial Di e ence Equa ions
13.1 In oduc ion
In he p eceding chap e s, we ocused p ima ily on scala pa ial di e ence
equa ions, ha is, equa ions go e ning a single disc e e ield
u:N0×Zn→R.
Such equa ions su ice o modeling isola ed di usion p ocesses, simple anspo
dynamics, o single–species popula ion models.
Howe e , many na u al and physical sys ems canno be desc ibed by a single
scala equa ion. Phenomena in luid mechanics, elec omagne ism, eac ion–
di usion sys ems, popula ion in e ac ions, and complex sys ems o en equi e
he simul aneous e olu ion o mul iple in e ac ing componen s. These in e ac-
ions na u ally lead o coupled equa ions, o equi alen ly, o he e olu ion o a
ec o – alued disc e e ield
u= (u1, . . . , us) : N0×Zn→Rs.
This chap e is de o ed o he sys ema ic o mula ion and analysis o sys-
ems o pa ial di e ence equa ions (P∆E sys ems). We in oduce he gene al
ope a o amewo k, de ine linea , semilinea , quasilinea , and ully nonlinea
sys ems, and es ablish a uni ied no a ion o disc e e ec o ields and disc e e
di e en ial ope a o s. These sys ems o m he na u al disc e e analogue o ec-
o PDEs in he con inuous se ing and p o ide a gene al language o desc ibing
a wide ange o coupled dynamical phenomena.
13.2 Classi ica ion o P∆E Sys ems
In his sec ion we in oduce a sys ema ic classi ica ion scheme o sys ems o
pa ial di e ence equa ions (P∆E). Le
x= (x1, x2, . . . , xn)∈Zn, k = (k1, k2, . . . , kn)∈Zn,
and de ine he mul i-indexed shi ope a o
Ek:= Ek1
x1Ek2
x2···Ekn
xn,
oge he wi h he L1–no m
|k|1:= |k1|+|k2|+···+|kn|.
We conside ec o - alued disc e e ields
u= (u1, u2, . . . , us) wi h u:N0×Zn→Rs,
and w i e all sys ems in e olu ion o m,
E u=Au +F(u, , x).
115
De ini ion 13.1 (Linea Sys em).A sys em is called linea i i is o he o m
E u=A( , x)u+F( , x),
whe e A( , x)is an s×sma ix o shi ope a o s wi h en ies
Aij( , x) = X
|k|1≤m
aijk( , x)Ek,1≤i, j ≤s.
No nonlinea dependence on uoccu s.
De ini ion 13.2 (Semilinea Sys em).A sys em is called semilinea i
E u=A( , x)u+F(u, , x),
whe e A( , x)is as in he linea case, and he nonlinea e m F(u, , x)sa is ies:
no shi ope a o s may appea in F.
Thus Fmay be nonlinea in u, bu mus depend only on he poin wise alue
u( , x)and no on i s shi ed e sions.
De ini ion 13.3 (Quasilinea Sys em).A sys em is called quasilinea i
E u=A( , x, u)u+F(u, , x),
whe e he en ies o Aa e gi en by
Aij( , x, u) = X
|k|1≤m
aijk( , x, u)Ek,
wi h he es ic ion:
A( , x, u)may depend nonlinea ly on u, bu no shi ope a o s may appea inside A.
Equi alen ly, he only admissible nonlinea anspo - ype e ms a e o he o m
(u)Exu.
De ini ion 13.4 (Fully Nonlinea Sys em).A sys em is called ully nonlinea
i
E u=F(Au, u, , x),
whe e Fmay depend nonlinea ly on shi ed e sions o u. Typical examples
include
Exu Eyu, (Exu)2,pu+Exu, e c.
In his case, shi ope a o s appea inside he nonlinea e m in genuinely non-
linea combina ions.
116
Rema k. This classi ica ion is ully pa allel o he classical PDE classi ica ion.
Indeed, eplacing each shi ope a o Ekwi h he di e en ial ope a o
∂k=∂k1
x1∂k2
x2···∂kn
xn,
yields he co esponding no ions o linea , semilinea , quasilinea , and ully
nonlinea pa ial di e en ial equa ion sys ems.
Example 13.1 (Re o mula ion o a Second-O de P∆E in o a Fi s -O de Sys-
em).Conside he h ee-dimensional disc e e wa e equa ion
δ ∆ u=c2∇2u, u :N0×Z3→R.
Recall ha
δ ∆ u=E u+E−1
u−2u.
The e o e he equa ion can be ew i en in pu e shi -ope a o o m as
E u=c2∇2u+ 2u−E−1
u.
In oduce a new auxilia y a iable
:= E−1
u.
Then he second-o de equa ion becomes he coupled i s -o de sys em
(E u=c2∇2u+ 2u− ,
E =u.
This shows ha any second-o de P∆E in ime can be equi alen ly o mula ed
as a i s -o de sys em in an ex ended s a e ec o .
Example 13.2 (Quasilinea Sys em: Disc e e Na ie –S okes Equa ions).Con-
side he disc e e analogue o he Na ie –S okes equa ions, which we e e o as
he Disc e e Na ie –S okes Equa ions (DNSE):
ρ∆ u+u·∇cu=−∇cp+µ∇2u+ ,∇c·u= 0,
whe e he disc e e ec o ield
u= (u, , w) = u( , x, y, z),u:N0×Z3→R3,
and he ope a o s ∆ ,∇c, and ∇2deno e espec i ely he o wa d ime di e -
ence, he cen al disc e e g adien , and he disc e e Laplacian on he cubic la ice
Z3.
Rew i ing he equa ion in e olu ion o m using E u=u+ ∆ u, we ob ain
E u=u−1
ρ∇cp+µ
ρ∇2u−u·∇cu+1
ρ .
117

This sys em is quasilinea because he disc e e g adien ∇cuappea ing in he
con ec i e e m is mul iplied by he solu ion ui sel :
u·∇cu=u∆c
xu+ ∆c
yu+w∆c
zu,
which is linea in he disc e e de i a i es o ubu nonlinea in u. Thus he
DNSE i s p ecisely in o he amewo k o quasilinea pa ial di e ence equa ion
sys ems.
Example 13.3 (Fully Nonlinea Sys em: Fo es Fi e Model).Conside he
wo-dimensional Fo es Fi e Model, which can be w i en as
E u= mod3(2 δ(u−1) θ(S−1) + G( , x, y)) ,
whe e he neighbou hood in e ac ion e m is
S=X
(i,j)∈M
δEi
xEj
yu−2,
and
u:N0×Z2→Z3,Z3={0,1,2}.
The s a es a e in e p e ed as:
0 = emp y,1 = ee,2 = bu ning ee.
The o cing e m
G:N0×Z2→ {0,1}
models ex e nal phenomena such as spon aneous ee g ow h o ligh ning s ikes.
This sys em is ully nonlinea because he highes -o de spa ial ope a o
δEi
xEj
yu−2
depends nonlinea ly on he shi ed alues o u, and he e o e he nonlinea i y
appea s inside he ope a o i sel .
118
13.3 Linea Sys ems
In his sec ion, we s udy he class o linea pa ial di e ence equa ion sys ems
o he o m
E u=A( , x)u+F( , x),
whe e u:N0×Zn→Rsis a ec o - alued unc ion, and A( , x) is an s×s
ma ix whose en ies a e ini e linea combina ions o shi ope a o s:
Aij( , x) = X
∥k∥1≤m
aijk( , x)Ek, k = (k1, . . . , kn)∈Zn.
He e
Ek:= Ek1
x1Ek2
x2···Ekn
xn,∥k∥1=|k1|+···+|kn|,
and
u= (u1, u2, . . . , us)T
is a disc e e ec o ield.
Reduc ion o O dina y Di e ence Equa ions. I each en y Aij( , x) con-
ains no shi ope a o , i.e.
Aij( , x) = aij( , x),
hen he sys em educes o a sys em o o dina y di e ence equa ions (ODEs).
Cons an -Coe icien Linea Sys ems
Conside he au onomous sys em
E u=Au, A ∈Rs×scons an .
The solu ion is well known and can be exp essed using he disc e e semig oup
{A } ≥0:
u( ) = A u0, u0=u(0).
Case 1: Ais diagonalizable. Suppose
A=PΛP−1,
whe e Λ = diag(λ1, . . . , λs). Then
A =PΛ P−1,
and hence he solu ion is
u( ) = P


λ
1...
λ
s


P−1u0.
119
Case 2: Ais no diagonalizable. Le Aha e Jo dan o m
A=PJP−1, J = diag (J1, J2, . . . , J ),
whe e each Jo dan block is o he o m
Jℓ=






λℓ1 0 ··· 0
0λℓ1··· 0
.
.
........
.
.
0··· 0λℓ1
0··· 0 0 λℓ







.
Then
A =PJ P−1,
whe e each block sa is ies
J
ℓ=λ
ℓ







1 
2··· 
kℓ−1
0 1 ··· 
kℓ−2
.
.
........
.
.
0··· 0 1
0··· 0 0 1







.
Thus he ull solu ion is
u( ) = PJ P−1u0,
wi h polynomial p e ac o s 
ja ising om he nilpo en pa o each Jo dan
block.
Sys em o Independen Equa ions
I he coe icien ma ix Ais diagonal, hen he sys em
E u=Au
con ains no coupling be ween he componen s o u. In o he wo ds, each com-
ponen e ol es independen ly, and he sys em may be sol ed by ea ing he
equa ions one by one.
Example 13.4 (Disc e e Vec o Hea Equa ion).Conside he disc e e ec o
hea equa ion
∆ u=α∇2u,u= (u, , w),
whe e
u:N0×Z3→R3.
Using he iden i y ∆ =E −I, he sys em can be ew i en in e olu ion
o m:
E u=u+α∇2u, E = +α∇2 , E w=w+α∇2w.
120
Hence he ma ix Ais diagonal:
A= diag I+α∇2, I +α∇2, I +α∇2.
I is now clea ha he sys em decouples in o h ee scala equa ions, each
o which may be sol ed independen ly. Thus he ec o hea equa ion is simply
h ee copies o he scala disc e e hea equa ion.
121
14 A las o Nonlinea Pa ial Di e ence Equa-
ions
14.1 In oduc ion
This chap e p esen s an a las o nonlinea pa ial di e ence equa ions (P∆Es)
ha exhibi ich dynamical beha io , including pa e n o ma ion, spa io em-
po al chaos, and a wide a ie y o ac al s uc u es. The pu pose o his chap e
is wo old:
1. o illus a e how classical disc e e models—such as cellula au oma a,
sandpile dynamics, and la ice-based e olu ion ules— i na u ally in o
he uni ied amewo k o nonlinea P∆Es; and
2. o showcase se e al no el models in oduced by he au ho , demons a -
ing he exp essi e powe o P∆Es in gene a ing complex and eme gen
beha io om simple algeb aic ules.
The examples in his a las ange om elemen a y one-dimensional e olu ion
ules o high-dimensional sys ems wi h nonlinea couplings and mod-nin e ac-
ions. Despi e hei di e si y, all models can be w i en compac ly in he gene al
o m
E u=F(u, x, ),
whe e Fmay in ol e nonlinea combina ions o shi ope a o s, local in e ac-
ions, h eshold o mod-nnonlinea i ies, o disc e e app oxima ions o classical
di e en ial ope a o s.
Many o he sys ems p esen ed he e p oduce s iking phenomena: sel -simila
pa e ns, ecu si ely gene a ed ac als, in e mi ency, spa io empo al u bu-
lence, and long- ange co ela ions. Th ough hese examples, we highligh he
cen al heme o his monog aph: nonlinea pa ial di e ence equa ions p o ide
a na u al language o desc ibing complexi y in disc e e space ime.
This a las se es bo h as a e e ence and as a sou ce o inspi a ion o u u e
esea ch on nonlinea disc e e dynamics, o e ing a b oad iew o how simple
algeb aic ules can gi e ise o highly non i ial eme gen s uc u es.
128

Coupled Map La ice
1D Coupled Map La ice
The one-dimensional Coupled Map La ice (CML), o iginally p oposed by Kaneko [34],
is a p o o ypical model o spa io empo al chaos. I is de ined by he ollowing
ecu ence ela ion:
u +1
s= (1 −ε) (u
s) + ε
2 (u
s+1) + (u
s−1),
whe e u
s∈R, :R→Ris a nonlinea local map (e.g., logis ic map), and
ε∈[0,1] is he coupling s eng h.
We e o mula e his equa ion using shi ope a o s o ob ain a compac
ope a o -based ep esen a ion:
E u= (1 −ε) (u) + ε
2 (Exu) + (E−1
xu),
whe e
u=u( , x), u :Z2→R.
This equa ion is usually nonlinea au onomous Pa ial Di e ence Equa ion
ha cap u es spa io empo al dynamics and is equen ly used o model chao ic
beha iou on disc e e la ices.
2D Coupled Map La ice
The wo-dimensional Coupled Map La ice (2D CML) ex ends he 1D case o
a squa e la ice, whe e each si e in e ac s wi h i s ou nea es neighbou s. The
classical o m is gi en by:
u +1
i,j = (1 −ε) (u
i,j) + ε
4 (u
i+1,j) + (u
i−1,j) + (u
i,j+1) + (u
i,j−1),
whe e u
i,j ∈R, :R→R, and ε∈[0,1] as be o e.
Using shi ope a o s, he sys em can be ew i en in a compac ope a o -
based o m:
E u= (1 −ε) (u) + ε
4 (Exu) + (E−1
xu) + (Eyu) + (E−1
yu),
whe e
u=u( , x, y), u :Z3→R.
This ope a o ep esen a ion highligh s he spa ial symme y and acili-
a es gene aliza ion o highe dimensions, aniso opic coupling, o g aph-based
opologies.
129
Explana ion
Acoupled map la ice (CML) is a disc e e- ime, disc e e-space dynamical sys-
em in which each la ice si e e ol es acco ding o a p esc ibed local map and
in e ac s wi h o he si es ia a coupling ule. The local map encodes he non-
linea dynamics a each si e, while he coupling ep esen s spa ial in e ac ions
such as di usion, anspo , o synch oniza ion.
CMLs a e capable o p oducing spa io empo al chaos, whe e complex, i eg-
ula pa e ns eme ge and e ol e ac oss bo h space and ime. They occupy an
in e media e posi ion be ween con inuous pa ial di e en ial equa ions and ully
disc e e cellula au oma a: like PDE, hey desc ibe he e olu ion o a ield; like
CA, hey a e inhe en ly disc e e in space and ime.
In he con ex o his wo k, CMLs can be ega ded as a pa icula subclass
o pa ial di e ence equa ions in which he upda e ope a o con ains a nonlinea
local componen oge he wi h a disc e e coupling e m. This pe spec i e allows
he ma hema ical machine y o disc e e unc ional analysis o be applied di ec ly
o he s udy o CML dynamics.
130
14.2 Elemen a y Cellula Au oma a
The s udy o one-dimensional cellula au oma a (1D CA) was signi ican ly ad-
anced by S ephen Wol am [33], who sys ema ically explo ed he beha iou o
all 256 elemen a y ules. These models, despi e hei simplici y, can gene a e a
wide ange o complex spa io empo al pa e ns, including pe iodic s uc u es,
nes ed ac als, localized s uc u es, and e en chao ic beha iou .
All 1D cellula au oma a can be exp essed as au onomous pa ial di e -
ence equa ions, meaning ha he upda e ule does no include any ex e nal
o cing e m. Mo eo e , mos o hese equa ions a e inhe en ly nonlinea , due
o he logical (Boolean) na u e o he local in e ac ions.
In his sec ion, we o mula e se e al 1D cellula au oma a as pa ial di -
e ence equa ions. Some o hese o mula ions a e based on known Boolean
algeb a ans o ma ions, con e ing logical ules in o Boolean polynomials, and
hen in o pa ial di e ence equa ions. O he s a e de i ed heu is ically by ob-
se ing he pa e n o e olu ion.
This e o mula ion has se e al impo an ad an ages:
•I p o ides a uni ied ma hema ical amewo k o s udy disc e e sys ems.
•I allows he applica ion o analy ical ools such as ope a o heo y, s a-
bili y analysis, and e en G een’s unc ions.
•I enables he explo a ion o di e en ypes o ini ial and bounda y con-
di ions in a mo e o malized way.
•I makes i possible o in oduce non-au onomous e ms and s udy how
ex e nal o cing in luences he e olu ion.
This app oach ans o ms cellula au oma a om me e compu a ional oys
in o objec s o igo ous ma hema ical in es iga ion wi hin he b oade con ex
o disc e e dynamical sys ems.
The Rule 90
The Rule 90 cellula au oma on can be w i en as a nonlinea pa ial di e ence
equa ion o he o m:
E u= mod2E−1
xu+Exu
whe e mod2(x) is de ined as:
mod2(x) := (1,i xis odd
0,i xis e en
This unc ion is clea ly non-linea , making he equa ion i sel non-linea .
We e e o his equa ion as he Sie pi´nski Equa ion, due o i s deep
connec ion wi h he Sie pi´nski iangle.
131
De ine a disc e e del a unc ion as:
δ(x−a) := (1,i x=a
0,o he wise
Gi en he ini ial condi ion u(0, x) = δ(x) and no bounda y condi ion, he
exac solu ion o he equa ion is:
u( , x) = mod2(C(2 , x + ))
whe e C(x, y) is he binomial coe icien , de ined as:
C(x, y) := (x!
(x−y)! y!,i 0 ≤y≤x
0,o he wise
Fo a gene al ini ial condi ion u(0, x) = (x), he solu ion becomes:
u( , x) = mod2 X
s∈Z
(s)·C(2 , x + −s)!
This sys em exhibi s chao ic beha iou in a disc e e bina y ield. Re-
ma kably, despi e i s chao ic dynamics, we ha e ound a closed- o m analy ical
solu ion. This p o ides a ounda ion o de ine and analyze concep s like chao ic
unc ions and quasichao ic unc ions wi hin he amewo k o disc e e unc-
ional analysis.
132
Example 1
This is he spa io empo al plo o Rule 90 wi h he ini ial condi ion u(0, x) =
δ(x) and no bounda y condi ions.
Figu e 12: Spa io empo al plo o Rule 90 wi h u(0, x) = δ(x) and no bounda y
condi ions.
I clea ly o ms a Sie pi´nski iangle. No e ha each cell’s s a e depends
only on i s le and igh neighbou s. Thus, his ac al is no globally planned,
bu eme ges om local in e ac ions.
133

Example 2
This is he spa io empo al plo o Rule 90 wi h he ini ial condi ion u(0, x) =
δ(x) and bounda y condi ions u( , −100) = u( , 100) = 0.
Figu e 13: Spa io empo al plo o Rule 90 wi h u(0, x) = δ(x) and bounda y
condi ions u( , −100) = u( , 100) = 0.
Ini ially, we obse e a pe ec Sie pi´nski iangle. Howe e , once he pa e n
eaches he bounda y, i b eaks down in o spa io empo al chaos and becomes
unp edic able.
134
Example 3
This is he spa io empo al plo o Rule 90 wi h andom ini ial condi ion and
bounda y condi ions u( , −200) = u( , 200) = 0.
Figu e 14: Spa io empo al plo o Rule 90 wi h andom ini ial condi ion and
bounda y condi ions.
As shown, he sys em exhibi s spa io empo al chaos.
135
Rule 30
The e olu ion equa ion o Rule 30, de i ed using Boolean algeb a, is gi en by:
E u= mod2E−1
xu+Exu+u+u·Exu,
whe e E is he ime shi ope a o , Exis he spa ial igh shi ope a o .
Example
We conside he ollowing simula ion se up:
•Ini ial condi ion: u(0, x) is chosen andomly wi h alues in {0,1}.
•Bounda y condi ion: u( , −200) = u( , 200) = 0 o all .
The igu e below shows he spa io empo al e olu ion o he sys em unde
Rule 30:
I is e iden ha he sys em exhibi s spa io empo al chaos, cha ac e ized by
ape iodic and unp edic able pa e ns ac oss bo h space and ime.
136
The Rule 153
We de ine he e olu ion equa ion as ollows:
E u= mod21−E−1
xu
1 + Exu+Exu·E−1
xu+3E−1
xu−4Exu+u
Example
•Ini ial condi ion: u(0, x) is assigned a andom bina y alue (0 o 1) a
each spa ial poin .
•Bounda y condi ion: u( , −200) = u( , 200) = 0 o all .
•Colou scheme: 0 is shown as whi e, and 1 is shown as black.
The ollowing image illus a es he space- ime e olu ion om = 0 o =
400, and x∈[−200,200], wi h a andom ini ial condi ion:
This sys em exhibi s spa io empo al chaos.
137
This model shows in e es ing connec ions o:
•Phase synch oniza ion phenomena
•Topological o ex dynamics
•Pa e n o ma ion and sel -o ganiza ion
Figu e 19: Spa io empo al e olu ion o he Ku amo o model. Topological de-
ec s ( o ices) eme ge and mo e, and hei annihila ion leads o la ge-scale
synch oniza ion.
144

14.5 Ising Model
Go e ning Equa ion
We p opose he ollowing disc e e e olu ion equa ion o he well-known Ising
Model [29]:
E u= (1 −δ(sign(JS u)−sign(u))) θ(F−ε) sign(JS u)
+δ(sign(JS u)−sign(u)) θ(F−F0) (−sign(JS u)) (3)
whe e
S u=X
(i,j)∈V
Ei
xEj
yu,
•Vis he on Neumann neighbou hood.
•u=u( , x, y)∈ {−1,+1}is he bina y s a e a disc e e ime and spa ial
coo dina e (x, y).
•E u:= u( + 1, x, y) is he nex ime s ep alue.
•F=F( , x, y)∼ N(µ, c2) is a andom d i ing ield a si e (x, y), d awn
om a no mal dis ibu ion cen e ed a µ=kT, whe e Tis he empe a u e
and kis a cons an .
•εis a small posi i e numbe (baseline ac i a ion h eshold).
•F0is a la ge h eshold equi ed o lipping a s able si e.
•Jis he coupling cons an de e mining in e ac ion s eng h be ween neigh-
bou ing si es.
Physical In e p e a ion
The unc ion u( , x, y) ep esen s he spin (o s a e) o a pa icle o si e a
posi ion (x, y) and ime . The a iable E udeno es he upda ed s a e a ime
+1. The upda e is go e ned by local in e ac ions and s ochas ic en i onmen al
d i e F.
•The i s e m ac i a es when he si e’s cu en s a e is di e en om
he local neighbou hood majo i y (sign(JS u)= sign(u)), allowing i o
lip easily when F > ε.
•The second e m ac i a es when he si e’s cu en s a e ma ches he
neighbou hood majo i y, bu may s ill lip i he d i ing o ce exceeds a
highe h eshold F0, modeling he mal noise o ins abili y.
This model exp esses he Ising-like beha iou in he language o pa ial di -
e ence equa ions (P∆E), linking local de e minis ic upda e ules wi h s ochas ic
d i ing o ce unde he mal con ol.
145
14.6 Disc e e Logis ic Di usion Equa ion
In his sec ion, we p opose a disc e e- ime, disc e e-space popula ion model
called he Disc e e Logis ic Di usion Equa ion, designed o cap u e he
expansion and g ow h o a popula ion o e a spa ial domain. This equa ion is
a disc e e analogue o he Fishe -KPP Equa ion.
∆ u=jα∇2u+ u 1−u
Kk (4)
whe e he disc e e Laplacian is de ined as
∇2u:= 
X
(i,j)∈V
Ei
xEj
yu
−4u
wi h he on Neumann neighbou hood
V={(1,0),(−1,0),(0,1),(0,−1)}
He e, he s a e a iable u=u( , x, y)∈Z≥0 ep esen s he numbe o indi-
iduals a si e (x, y) a ime , and ∆ u=u( + 1, x, y)−u( , x, y).
This is a Nonlinea Au onomous Pa ial Di e ence Equa ion
Biological In e p e a ion
We conside a wo-dimensional disc e e la ice whe e each si e (x, y) co esponds
o a uni habi a a ea. Time is disc e e and may ep esen one minu e, one
hou , o one day depending on he modeling scale. The a iable u( , x, y)∈Z≥0
deno es he popula ion size a loca ion (x, y) and ime .
The e olu ion equa ion consis s o he ollowing componen s:
•u: cu en popula ion size a each si e.
•α∇2u: disc e e di usion e m. Indi iduals mo e o neighbo ing si es in
he on Neumann neighbo hood. The coe icien αcon ols how s ongly
he popula ion sp eads in space.
• u 1−u
K: logis ic g ow h e m. Popula ion inc eases locally a g ow h
a e , bu he g ow h slows as uapp oaches he ca ying capaci y K.K
is he maximum numbe o indi iduals allowed in each uni a ea.K∈Z
•⌊·⌋: he loo unc ion ensu es ha he upda ed popula ion emains an
in ege , e lec ing he disc e eness o indi iduals in biological popula ions.
•E u=u( + 1, x, y): o wa d ime e olu ion ope a o , ep esen ing he
s a e o he sys em a he nex ime s ep.
This model cap u es he compe i ion be ween local g ow h and spa ial dis-
pe sal in a biologically plausible manne . I also espec s he ac ha popula-
ion coun s a e disc e e and limi ed by spa ial cons ain s.
146
Simula ion Resul s
Del a Ini ial Condi ion
We conside he ollowing pa ame e se up o he simula ion:
•Di usion coe icien : α= 0.05
•Ca ying capaci y: K= 1000
•Ini ial condi ion: u(0, x, y) = δ(x)δ(y), meaning a single indi idual is
placed a he cen e o he g id.
•Bounda y condi ion:
(u( , −100, y) = u( , 100, y) = 0,
u( , x, −100) = u( , x, 100) = 0,
ep esen ing a bounded domain wi h ze o popula ion on he edges.
We simula e he e olu ion o he sys em unde he Disc e e Logis ic Di usion
Equa ion o a ious alues o he g ow h a e . Below a e he popula ion
dis ibu ions u( , x, y) a ime = 250, co esponding o di e en alues o :
147
Random Ini ial Condi ion
In his simula ion, we keep all pa ame e s and bounda y condi ions unchanged:
•α= 0.05
•K= 1000
148
•Bounda y condi ions:
u( , −100, y) = u( , 100, y)=0, u( , x, −100) = u( , x, 100) = 0
Howe e , we change he ini ial condi ion o a andom con igu a ion:
u(0, x, y) = andom in ege s (e.g., uni o mly sampled om {0,1,2, ...})
Below a e he e olu ion plo s o di e en alues o :
149

F om he simula ion esul s unde he del a ini ial condi ion, whe e he
sys em is ini ialized wi h
u(0, x, y) = δ(x)δ(y),
we obse e a nea ly ci cula ou wa d expansion due o he localized s a ing
poin . As he g ow h a e inc eases, he esul ing spa ial pa e ns exhibi a
ich sequence o ansi ions:
•Fo small alues o , he solu ion eaches a spa ially homogeneous s eady
s a e.
•As inc eases, he sys em begins o o m checke boa d-like s uc u es.
•Wi h u he inc ease in , he pa e ns e ol e in o concen ic wa e-like
ipples.
•A highe alues o , he symme y b eaks down and complex, i egula
s uc u es eme ge.
Unde he andom ini ial condi ion, whe e he sys em is ini ialized wi h
spa ially he e ogeneous andom alues, a simila p og ession is obse ed. The
sys em ansi ions om a s eady s a e o inc easingly diso de ed and chao ic
spa ial pa e ns as inc eases.
These obse a ions sugges ha he model exhibi s a ype o in ini e-
dimensional bi u ca ion beha io , whe e complex pa e n dynamics eme ge
h ough successi e ins abili ies d i en by he con ol pa ame e .
Simple Model wi h In ini e Complexi y
I we emo e he loo unc ion, se he ca ying capaci y K= 1, and es ic
he model o one spa ial dimension, he disc e e equa ion simpli ies o:
∆ u=α∇2u+ u(1 −u),(5)
150
whe e u=u( , x)∈R≥0 ep esen s he popula ion densi y a si e xand ime ,
and he disc e e Laplacian is gi en by:
∇2u:= Exu+E−1
xu−2u.
We call his Logis ic Di usion Equa ion.
We ix he di usion coe icien a :
α= 0.05,
and use he ollowing se ings:
•Ini ial condi ion: u(0, x) is a andomly gene a ed eal- alued unc ion
on he spa ial domain.
•Bounda y condi ion: u( , −100) = u( , 100) = 0 o all .
Below we p esen he spa io empo al e olu ion o u( , x) o di e en alues
o he g ow h a e :
151
152
These simula ions illus a e a ich spec um o beha iou s, including s eady
s a es, pe ec pe iodici y, quasipe iodici y, spa io empo al in e mi ency, and
ull spa io empo al chaos, depending on he alue o .
As he pa ame e inc eases, he sys em exhibi s a wide a ie y o dynamical
beha iou s:
• ∈[0,1.8]: he sys em con e ges o a s eady s a e, esembling a ixed
poin .
• ≈1.9: he solu ion begins o bi u ca e.
• ≈2.0: he sys em o ms pe ec checke boa d-like pa e ns.
• ∈[2.2,2.3]: he sys em exhibi s spa ially pe iodic s uc u es.
• ≈2.4: he solu ion appea s almos pe ec ly pe iodic, bu upon close
inspec ion e eals quasipe iodic beha iou .
• ≈2.5: he sys em begins o show localized i egula i ies — pa quasipe i-
odic, pa diso de ed — sugges ing he onse o chao ic ea u es.
153