Anillo de giges

UNIVERSIDAD DE CONCEPCIÓN FACULTAD DE CIENCIAS FÍSICAS Y MATEMÁTICAS PROGRAMA DE MAGISTER EN MATEMATICA - ACADÉMICO

Extensiones del problema de Büchi a distintas estructuras y potencias más altas

Profesor Guía: Xavier Vidaux Negre Codirector: Antonio Laface Dpto. de Matemáticas Facultad de Ciencias Físicas y Matemáticas Universidad de Concepción

Tesis para ser presentada a la Direcciónde Postgrado de la Universidad de Concepción

HÉCTOR HARDY PASTÉN VÁSQUEZ CONCEPCIÓN-CHILE 2010

2

Agradezco a mi familia, amigos, y profesores del Departamento de Matemática quienes hicieron posible la elaboración de esta Tesis.

Título:

Extensiones del problema de Büchi a distintas estructuras y potencias más altas
Héctor Pastén Vásquez

Tesis de Magister

Índice general1. Presentación
1.1. 1.2. 1.3. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problemática y Objetivos Resultados principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3 4 6

2. A survey on Büchi's problem : new presentations and open problems 8
2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 2.9. Preamble . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 9 10 12 14 16 18 20 21 22 24 27 30 32 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Denitions and notation . . . . . . . . . . . . . . . . . . . . . . . The origin of Büchi's problem . . . . . . . . . . . . . . . . . . . . Other rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . Hensley's problem

Optimal bounds for the length of sequences Büchi's problem with constant

=2

. . . . . . . . . . . . . . . . .

Number elds . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.10. Rings of functions in characteristic 0 . . . . . . . . . . . . . . . . 2.11. Higher powers . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 2.12. Positive characteristic 2.13. To be done . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. An Extension of Büchi's Problem for Polynomial Rings in Zero Characteristic 33
3.1. 3.2. 3.3. 3.4. 3.5. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Main Result and Corollaries . . . . . . . . .. . . . . . . . . . . . Intermediate Results . . . . . . . . . . . . . . . . . . . . . . . . . Proof of Theorem 11 . . . . . . . . . . . . . . . . . . . . . . . . . Equivalence of Büchi's Problem and Hensley's Formulation . . . 33 35 36 39 42

4. Büchi's problem in any Power for Finite Fields
4.1. 4.2. 4.3. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Representationof

43
43 46 49

k -th

powers by a polynomial of degree

k.

. . .

The case of squares . . . . . . . . . . . . . . . . . . . . . . . . . .

1

5. Büchi's problem for the ring of p-adic entire functions and consequences in Logic 51
5.1. 5.2. 5.3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Representation of squares by a polynomial of degree two inBüchi's Problem and consequences in Logic 51 53 57

Ap [X].

. . . . . . . . . . . .

2

Capítulo 1
Presentación

1.1. Introducción
En 1900 Hilbert propuso el problema de encontrar un algoritmo para decidir si dada una ecuación polinomial con coecientes enteros, ella posee o no soluciones enteras. Este problema, conocido como el Décimo Problema de Hilbert (el cual denotamos

H10),fue resuelto por Matiyasevich 70 años más tarde [16]

concluyendo un trabajo desarrollado principalmente por M. Davis, H. Putnam y J. Robinson. El resultado obtenido fue que en realidad no existe tal algoritmo. En realidad se demostró algo mucho más fuerte: los conjuntos recursivamente enumerables (i.e. listables por una máquina de Turing) de En consecuencia, la teoría positiva existencial de...