This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share



2016 (EN)
Ένα ανάλογο του 10ο προβλήματος του Χίλμπερτ για το δακτύλιο των εκθετικών αθροισμάτων
An analogue of Hilbert's tenth problem for the ring of exponential sums

Χομπιτάκη, Δήμητρα

Vidaux, Xavier
Kolountzakis, Mihalis
Φειδάς, Αθανάσιος

Το κεντρικό θέμα της διπλωματικής είναι το αν ο δακτύλιος των εκθετικών αθροισμάτων έχει αποφασίσιμη θετική υπαρξιακή θεωρία. Αυτό είναι ένα πρόβλημα ανάλογο του 10ou προβλήματος του Hilbert για το δακτύλιο των εκθετικών αθροισμάτων μίας μεταβλητής υπεράνω του σώματος των μιγαδικών αριθμών (παρακάτω θα δοθούν ακριβείς ορισμοί). Το πρόβλημα αυτό μπορεί να θεω¬ρηθεί ως ένα πρώτο βήμα για να δοθεί μία απάντηση στην ακόλουθη ερώτηση: Έστω H ο δακτύλιος των αναλυτικών συναρτήσεων πάνω στους μιγαδικούς της ανεξάρτητης μεταβλητής z και Lz η γλώσσα της αριθμητικής προσαυξημένη κατά ένα σταθερό - σύμβολο για τη z : Lz = {+, •, 0,1,z} Ερώτηση: Είναι η θετική υπαρξιακή θεωρία του H στην Lz αποφασίσιμη; Αυτό το πρόβλημα έχει ουσιαστική σημασία και είναι ακόμα ανοιχτό. Για περισσότερες λεπτομέρειες ο αναγνώστης μπορεί να διαβάσει τη σχετική βιβλι-ογραφία που αναφέρεται στο Introduction. Μέρος της διπλωματικής είναι επίσης η σύντομη παρουσίαση άλλων τριών προβλημάτων αποφασισιμότητας των οποίων τεχνικές και αποτελέσματα χρησι-μοποιήθηκαν στην απόδειξη του ανάλογου του 10ou Προβλήματος του Hilbert για το δακτύλιο των εκθετικών αθροισμάτων. Εισαγωγικά Το 10o Πρόβλημα του Hilbert Το 10ο Πρόβλημα του Hilbert (θα το συμβολίζουμε ΗΤΡ) ρωτάει αν υπάρχει ένας αλγόριθμος που να απαντάει πάντα σωστά στην ερώτηση αν μία πολυων-υμική εξίσωση πολλών μεταβλητών με ακέραιους συντελεστές έχει ή δεν έχει ακέραιες λύσεις. Το πρόβλημα ανακοινώθηκε από τον ίδιο τον Hilbert το 1900. Ο Yuri Matjiasevich έδωσε αρνητική απάντηση στο πρόβλημα το 1970. Ο Matjiasevich για να καταλήξει στο συμπέρασμα ότι δεν υπάρχει τέτοιος αλγόρι¬θμος βασίστηκε στην ερευνητική δουλειά των Martin Davis , Hilary Putmnan και Julia Robinson. Έπειτα ήταν λογικό να αναρωτηθούν αν θα μπορούσε να υπάρξει ένας τέτοιος αλγόριθμος αν θεωρήσουμε έναν άλλον δακτύλιο πέρα από τους ακεραίους. Για παράδειγμα, είναι ήδη γνωστή η απάντηση για τους δακτυλίους των φυσικών, πραγματικών και μιγαδικών αριθμών όπως επίσης και για το σώμα των ρητών συναρτήσεων. Ωστόσο, το ανάλογο του ΗΤΡ για το σώμα των ρητών αριθμών είναι ανοιχτό και μάλιστα θεωρείται ως το κύριο ανοιχτό πρόβλημα της περιοχής. Στο κεφάλαιο Introduction παρουσιάζουμε κάποια ανάλογα του ΗΤΡ υπεράνω δακτυλίων των οποίων η δομή τους χρησι¬μοποιείται συχνά στα μαθηματικά. Διοφαντικό Πρόβλημα - Θετική Υπαρξιακή Θεωρία - Ορισμοί Θεωρία μίας δομής: είναι το σύνολο των προτάσεων που είναι αληθείς στη δομή. (Θετική) υπαρξιακή θεωρία μίας δομής: είναι το σύνολο των (θετικών) υπαρξιακών προτάσεων που είναι αληθείς στη δομή. Γλώσσα L: είναι μία ακολουθία συμβόλων η οποία εν γένει περιλαμβάνει τα σύμβολα + (για την πρόσθεση) , • (για τον πολλαπλασιασμό) , 0 (για το ουδέτερο στοιχείο της πρόσθεσης στον R) και 1 (για το ουδέτερο στοιχείο του πολλαπλασιασμού στον R). Επίσης, στην L μπορεί να περιλαμβάνονται σύμ¬βολα για ειδικά στοιχεία του δακτυλίου R. Λέμε ότι το Διοφαντικό πρόβλημα για το δακτύλιο R με συντελεστές στον R' είναι μη επιλύσιμο αν υπάρχει ένας αλγόριθμος που να αποφασίζει αν μία πολυωνυμική εξίσωση πολλών μεταβλητών με συντελεστές στον R' έχει λύση στον R. Η Εξίσωση του Pell Η διοφαντική εξίσωση x2 - dy2 = 1 (0.0.1) όπου d είναι θετικός ακέραιος ελεύθερος τετραγώνου, είναι γνωστή ως η εξίσωση του Pell. Οι J.Robinson, M.Davis και ο Y.Matjiasevich χρησιμοποίησαν εξισώσεις της παραπάνω μορφής και εισήγαγαν νέους μεθόδους για την επίλυση προβλημάτων της περιοχής. Μία σημαντική και ιδιαίτερα χρήσιμη παρατήρηση για τις λύσεις της εξίσωσης του Pell είναι η ακόλουθη: Παρατήρηση: Έστω (αι,&ι) και (α2,b2) λύσεις της παραπάνω εξίσωσης. Τότε το ζευγάρι (ai,bi) Θ (a2,b2) = (αια2 + db1b2,a1b2 + a2bi) είναι επίσης λύση της εξίσωσης. (EL)
At a glance: We prove that the positive existential theory of the ring of exponential sums is undecidable. Define the set of exponential sums, EXP(C), to be the the set of expres¬sions a = αο + α1βμιζ + + aw βμΝ z where α^,μ.,• G C. We ask whether the positive existential first order theory of EXP(C), as a structure of the language L = {+, •, 0,1,ez} is decidable or undecidable. Our result may be considered as an analogue of Hilbert's Tenth Problem for this structure and as a step to answering the similar problem for the ring of exponential polynomials, which is still open. We prove: Theorem 1 The ring of gaussian integers Z[i] is positive existentially defin¬able over EXP(C), as an L-structure. Hence the positive existential theory of this structure is undecidable. In order to prove Theorem 1 we adapt techniques of [8] and we show Theorem 2: (0.0.16) We consider the equation (e2z - 1)y2 = x2 - 1 where x,y Ε EXP(C). Let (a,b) and (a2,b2) be solutions of (0.0.16). We define the law Θ by bi) Θ (a2, b2) = (aia2 + (e2z - 1)bib2, aib2 + a2bi) The pair (a,b) = (ai,bi) Θ (a2,b2) is also a solution of (0.0.16). We denote by κ Θ (a, b) = (a, b) Θ • • • Θ (a, b). ((a, b) added to itself by Θ κ times.) Theorem 2 The solutions of the equation (0.0.16) are given by (x, y) = κ Θ (±ez, 1) Θ λ Θ (±e-z, ie-z). The proof uses techniques of [38], [28] and [23]. Important points of the proof We would like to characterise all the solutions of Equation (0.0.16) over EXP(C). Observe that, by the definition of EXP(C), x and y lay in some ring of the form R = C[ewz, β~μιΖ,... , eMfcZ,e_MfcZ], where k is a natural number and each μ Ε C. In [28] it is shown that one can choose the μ in such a way that μ1 = , for some natural number N, and the set {1,μ2, • • • , μ^;} is linearly indepen¬dent over the field Q. By results of [38] it follows that the set {βμιΖ,..., eMfcz} is algebraically independent over C. So the question about solutions of (0.0.16) becomes Given a natural number N, find the solutions of (Z2-v - 1)y2 = x2 - 1 (0.0.17) over the ring C[Z,Z 1 ,t2,t21, ■ ■ ■ ,ίί,ίρ1], where Z = eJ1 and the elements t2, ■ ■ ■ te are variables over may be consid¬ered as variables over C[Z, ZAt a first stage we show that any solu¬tion of (0.0.17) does not depend on the varables tj, i.e. is over C[Z, Z Then, extending techniques of [23] we show that any solution is over the ring C[ZN, Z-N]. Finally we give the characterization of solutions as in Theorem 2. Subsequently the set of integers is positive existentially definable, by tech¬niques of [8] and [7]. The results of Theorem 2 may be stated as The set of solutions of (T2 - 1)y2 = x2 - 1 over the tower of rings uN C[T Μ ,T - Μ ] stabilizes at the level of C[T, T (EN)

text

Εξίσωση του Πελλ
Pell's equation
Διοφαντικό πρόβλημα
Positive existential theory
Diophantine problem
Εκθετικά αθροίσματα
Θετική υπαρξιακή θεωρία

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

2016-11-18




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)