On the intrinsic complexity of the arithmetic Nullstellensatz

We show several arithmetic estimates for Hilbert's Nullstellensatz. This includes an algorithmic procedure computing the polynomials and constants occurring in a Bézout identity, whose complexity is polynomial in the geometric degree of the system. Moreover, we show for the first time height es...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Hägele, K., Morais, J. E., Pardo, L. M., Sombra, Martín
Formato: Articulo
Lenguaje:Inglés
Publicado: 2000
Materias:
Matemática
Hilbert’s Nullstellensatz
estimaciones aritméticas
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/83447
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-83447
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Hilbert’s Nullstellensatz
estimaciones aritméticas
spellingShingle Matemática
Hilbert’s Nullstellensatz
estimaciones aritméticas
Hägele, K.
Morais, J. E.
Pardo, L. M.
Sombra, Martín
On the intrinsic complexity of the arithmetic Nullstellensatz
topic_facet Matemática
Hilbert’s Nullstellensatz
estimaciones aritméticas
description We show several arithmetic estimates for Hilbert's Nullstellensatz. This includes an algorithmic procedure computing the polynomials and constants occurring in a Bézout identity, whose complexity is polynomial in the geometric degree of the system. Moreover, we show for the first time height estimates of intrinsic type for the polynomials and constants appearing, again polynomial in the geometric degree and linear in the height of the system. These results are based on a suitable representation of polynomials by straight-line programs and duality techniques using the Trace Formula for Gorenstein algebras. As an application we show more precise upper bounds for the function πS(x) counting the number of primes yielding an inconsistent modular polynomial equation system. We also give a computationally interesting lower bound for the density of small prime numbers of controlled bit length for the reduction to positive characteristic of inconsistent systems. Again, this bound is given in terms of intrinsic parameters.
format Articulo
Articulo
author Hägele, K.
Morais, J. E.
Pardo, L. M.
Sombra, Martín
author_facet Hägele, K.
Morais, J. E.
Pardo, L. M.
Sombra, Martín
author_sort Hägele, K.
title On the intrinsic complexity of the arithmetic Nullstellensatz
title_short On the intrinsic complexity of the arithmetic Nullstellensatz
title_full On the intrinsic complexity of the arithmetic Nullstellensatz
title_fullStr On the intrinsic complexity of the arithmetic Nullstellensatz
title_full_unstemmed On the intrinsic complexity of the arithmetic Nullstellensatz
title_sort on the intrinsic complexity of the arithmetic nullstellensatz
publishDate 2000
url http://sedici.unlp.edu.ar/handle/10915/83447
work_keys_str_mv AT hagelek ontheintrinsiccomplexityofthearithmeticnullstellensatz
AT moraisje ontheintrinsiccomplexityofthearithmeticnullstellensatz
AT pardolm ontheintrinsiccomplexityofthearithmeticnullstellensatz
AT sombramartin ontheintrinsiccomplexityofthearithmeticnullstellensatz
bdutipo_str Repositorios
_version_ 1764820488625848323

Ejemplares similares