Word Equations, Fibonacci Numbers, and Hilbert`s Tenth Problem

Transcrição

Word Equations, Fibonacci Numbers, and
Hilbert’s Tenth Problem
Yuri Matiyasevich
Steklov Institute of Mathematics at St.Petersburg, Russia
http://logic.pdmi.ras.ru/~yumat
David Hilbert, Mathematical Problems [1900]
10. Entscheidung der Lösbarkeit einer diophantischen
Gleichung. Eine diophantische
Gleichung mit irgendwelchen
Unbekannten und mit ganzen
rationalen Zahlkoefficienten sei
vorgelegt: man soll ein Verfahren angeben, nach welchen
sich mittels einer endlichen Anzahl von Operationen entscheiden lässt, ob die Gleichung in
ganzen rationalen Zahlen lösbar
ist.
10. Determination of the
Solvability of a Diophantine
Equation. Given a diophantine equation with any number
of unknown quantities and with
rational integral numerical coefficients: To devise a process
according to which it can be
determined by a finite number
of operations whether the equation is solvable in rational integers.
Word Equations
Main alphabet: An = {α1 , . . . , αn }
Word Equations
Alphabet of unknowns: U = {υ1 , . . . , υm }
Word Equations
Alphabet of unknowns: U = {υ1 , . . . , υm }, An ∩ U = ∅
Word Equations
Word equation: P = Q where P, Q ∈ (An ∪ U)∗
Word Equations
Word equation: P = Q where P, Q ∈ (An ∪ U)∗
Solution: words V1 , . . . , Vm ∈ A∗n such that
υ1 ,...,υm
m
PVυ11 ,...,υ
,...,Vm ≡ QV1 ,...,Vm
From Words to Numbers
(First Numbering: Matrices)
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
Lemma. Every 2 × 2 matrix ca db with natural number elements
and the determinant equal to 1 can be represented in aunique way
as the product of matrices M1 = 11 01 and M2 = 10 11 .
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
”αi1 . . . αik ” ∼ Mi1 × · · · × Mik
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
”αi1 . . . αik ” ∼ Mi1 × · · · × Mik
υ1 , . . . , υm ∼ a1 , b1 , c1 , d1 , . . . , am , bm , cm , dm
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
”αi1 . . . αik ” ∼ Mi1 × · · · × Mik
P=Q ∼
P11 (. . . , ai , bi , ci , di , . . . , ) = Q11 (. . . , ai , bi , ci , di , . . . , )
W.o.l.g n = 2, i.e., A2 = {α1 , α2 }
”αi1 . . . αik ” ∼ Mi1 × · · · × Mik
P=Q ∼
a1 d1 − b1 c1 = · · · = am dm − bm cm = 1
(Second Numbering: Fibonacci weights)
Every word X = ”βim βim−1 . . . βi1 ” in the binary alphabet
B = {β0 , β1 } = {0, 1} can be viewed as the number
x = im um + im−1 um−1 + · · · + i1 u1
written in positional system with weights of digits being the
Fibonacci numbers u1 = 1, u2 = 1, u3 = 2, u4 = 3, . . . (rather than
traditional 1, 2, 4, 8, 16, . . . ).
x = im um + im−1 um−1 + · · · + i1 u1
traditional 1, 2, 4, 8, 16, . . . ).
”0”∼0
”1”∼1
”00”∼0
”01”∼1
”10”∼1
”11”∼2
”000”∼0
”001”∼1
”010”∼1
”011”∼2
”100”∼2
”101”∼3
”110”∼3
”111”∼4
”0000”∼0
”0001”∼1
”0010”∼1
”0011”∼2
”0100”∼2
”0101”∼3
”0110”∼3
”0111”∼4
”00000”∼0
”00001”∼1
”00010”∼1
”00011”∼2
”00100”∼2
”00101”∼3
”00110”∼3
”00111”∼4
x = im um + im−1 um−1 + · · · + i1 u1
traditional 1, 2, 4, 8, 16, . . . ).
”1”∼1
”10”∼1
”11”∼2
”100”∼2
”101”∼3
”110”∼3
”111”∼4
”1000”∼3
”1001”∼4
”1010”∼4
”1011”∼5
”1100”∼5
”1101”∼6
”1110”∼6
”1111”∼7
”10000”∼5
”10001”∼6
”10010”∼6
”10011”∼7
”11100”∼8
”11101”∼9
”11110”∼9
”11111”∼10
x = im um + im−1 um−1 + · · · + i1 u1
traditional 1, 2, 4, 8, 16, . . . ).
”10”∼1
”100”∼2
”110”∼3
”1000”∼3
”1010”∼4
”1100”∼5
”1110”∼6
”10000”∼5
”10010”∼6
”10100”∼7
”10110”∼8
”11000”∼8
”11010”∼9
”11100”∼10
”11110”∼11
(Second Numbering: Zeckendorf’s words)
””∼0
”10”∼1
”100”∼2
”1000”∼3
”1010”∼4
”10000”∼5
”10010”∼6
”10100”∼7
”100000”∼8
”100010”∼9
”100100”∼10
”101000”∼11
”101010”∼12
”1000000”∼13
”1000010”∼14
”1000100”∼15
””∼0
”10”∼1
”100”∼2
”1000”∼3
”1010”∼4
”10000”∼5
”10010”∼6
”10100”∼7
”100000”∼8
”100010”∼9
”100100”∼10
”101000”∼11
”101010”∼12
”1000000”∼13
”1000010”∼14
”1000100”∼15
Zeckendorf’s Theorem. Every positive integer x can be
represented in the form
x = im um + im−1 um−1 + · · · + i1 u1
with additional restrictions im = 1, i1 = 0, ik+1 ik = 0, and and in
unique way.
””∼0
”10”∼1
”100”∼2
”1000”∼3
”1010”∼4
”10000”∼5
”10010”∼6
”10100”∼7
”100000”∼8
”100010”∼9
”100100”∼10
”101000”∼11
”101010”∼12
”1000000”∼13
”1000010”∼14
”1000100”∼15
Zeckendorf’s Theorem. Every positive integer x can be
represented in the form
x = im um + im−1 um−1 + · · · + i1 u1
with additional restrictions im = 1, i1 = 0, ik+1 ik = 0, and and in
unique way.
Zeckendorf’s words: they do not begin with ”0”, do not end with
”1”, and do not contain ”11”.
(Third Numbering: Infinite Alphabet)
Every word ”αik αik−1 . . . αi1 ” in the infinite alphabet
A∞ = {α1 , α2 , . . . } can be presented by the Zeckendorf word
”10ik 10ik−1 . . . 10i1 ”.
We get, via Fibonacci numbers, a natural one-to-one
correspondence between words in the infinite alphabet A∞ and
natural numbers.
””∼0
”10”∼1
”100”∼2
”1000”∼3
””∼0
”α1 ”∼1
”α2 ”∼2
”α3 ”∼3
”1010”∼4
”10000”∼5
”10010”∼6
”10100”∼7
”α1 α1 ”∼4
”α4 ”∼5
”α2 α1 ”∼6
”α1 α2 ”∼7
”100000”∼8
”100010”∼9
”100100”∼10
”101000”∼11
”α5 ”∼8
”α3 α1 ”∼9
”α2 α2 ”∼10
”α1 α3 ”∼11
”101010”∼12
”1000000”∼13
”1000010”∼14
”1000100”∼15
”α1 α1 α1 ”∼12
”α6 ”∼13
”α4 α1 ”∼14
”α3 α2 ”∼15
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
=
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
uk+n = uk un+1 + uk−1 un
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
= im (um un+1 + um−1 un ) + · · · + i1 (u1 un+1 + u0 un ) + y
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
= (im um + · · · + i1 u1 )un+1 + (im um−1 + · · · + i1 u0 )un + y
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
|
{z
}
x
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
|
{z
}
|
{z
}
x
x1
( Concatenation)
X
x
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
Y
y
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
Z = XY = ”βim . . . βi1 βjn . . . βj1 ”
z
= im um+n + · · · + i1 u1+n + jn un + · · · + j1 u1
|
{z
}
|
{z
}
x
x1
= xy3 + x1 y2 + y
where
y2 = un ,
y3 = un+1
( Concatenation cont.)
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Z = XY
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
= ”βim . . . βi1 βjn . . . βj1 ”
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Z = XY
z
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
= ”βim . . . βi1 βjn . . . βj1 ”
= x1 y2 + xy3 + y
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Z = XY
z
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
= ”βim . . . βi1 βjn . . . βj1 ”
= x1 y2 + xy3 + y
z1 = x1 (y3 − y2 ) + xy2 + y1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Z = XY
z
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
= ”βim . . . βi1 βjn . . . βj1 ”
= x1 y2 + xy3 + y
z1 = x1 (y3 − y2 ) + xy2 + y1
z2 = (x3 − x2 )y2 + x2 y3
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Z = XY
z
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
= ”βim . . . βi1 βjn . . . βj1 ”
= x1 y2 + xy3 + y
z1 = x1 (y3 − y2 ) + xy2 + y1
z2 = (x3 − x2 )y2 + x2 y3
z3 = x2 y2 + x3 y3
Fibonacci Numbers and Diophantine Equations
Theorem (G. D. Cassini [1680]).
2
2
um+1
− um+1 um − um
= (−1)m
Fibonacci Numbers and Diophantine Equations
Theorem (G. D. Cassini [1680]).
2
2
um+1
− um+1 um − um
= (−1)m
Theorem (M. J. Wasteels [1902]). If
w 2 − wv − v 2 = ±1
then
w = um+1 ,
for some m.
v = um
(Second Numbering cont.)
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
(x32 − x3 x2 − x22 )2 = 1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
(x32 − x3 x2 − x22 )2 = 1
x2 ≤ x < x3
uk−1
X
x
x1
x2
x3
uk
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
(x32 − x3 x2 − x22 )2 = 1
x2 ≤ x < x3
≈φ=
√
1+ 5
2
uk−1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
(x32 − x3 x2 − x22 )2 = 1
x2 ≤ x < x3
x
x1
≈φ
uk
≈φ=
√
1+ 5
2
uk−1
X
x
x1
x2
x3
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
(x32 − x3 x2 − x22 )2 = 1
x2 ≤ x < x3
x
x1
≈φ
uk
φ − 2 < x1 − x/φ < φ − 1
≈φ=
√
1+ 5
2
Concatenation
X
x
x1
x2
x3
GCD(um , un ) = uGCD(m,n)
=
”βim . . . βi1 ”
= im um + · · · + i1 u1
= im um−1 + · · · + i1 u0
=
um
=
um+1
Y
y
y1
y2
y3
=
”βjn . . . βj1 ”
= jn un + · · · + j1 u1
= jn un−1 + · · · + j1 u0
=
un
=
un+1
length(X ) = length(Y ) ⇔ x2 = y2
length(X )length(Y ) ⇔ x2 (x2 + x3 )y2 (y2 + y3 )
GCD(length(X ), length(Y )) = 1 ⇔ GCD(x2 (x2 + x3 ), y2 (y2 + y3 )) =
”10ik 10ik−1 . . . 10i1 ”
length(”10ik 10ik−1 . . . 10i1 ”) = k + ik + ik−1 + · · · + i1
Concatenation
X
=
x
x1
x2
x3
=
=
=
=
uk
uk−1
≈φ=
”βim βim−1 . . . βi1 ”
”βim 0βim−1 0 . . . βi1 0”
im u2m + im−1 u2(m−1) + · · · + i1 u2
im u2m−1 + im−1 u2(m−1)−1 + · · · + i1 u1
u2m
u2m+1
√
1+ 5
2
”1” 7→ ”10”, ”0” 7→ ”
x32 − x3 x2 − x22 = 1
x < x3
φ − 2 < x1 − x/φ < φ − 1
”10” 7→ ”1”, ”00” 7→ ”0”, ”01” 7→ ”1”

Word Equations, Fibonacci Numbers, and Hilbert`s Tenth Problem

Transcrição

Documentos relacionados

Alphabet story gen

Non Settlement Term

Error Orthogonal Models and Commutative Orthogonal Block Structure

- Open Research Online

Alphabet Books in the Brown Station Media Center

Graffitti von a z

Guidelines for writing an academic

Tipografia cursiva tattoo word

Graffiti buchstaben az

Technical Analysis and Nonlinear Dynamics