Mostrar el registro sencillo del ítem
dc.contributor.author
Von zur Gathen, Joachim
dc.contributor.author
Matera, Guillermo
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2024-08-28T14:43:19Z
dc.date.issued
2022-03
dc.identifier.citation
Von zur Gathen, Joachim; Matera, Guillermo; Shifted varieties and discrete neighborhoods around varieties; Academic Press Ltd - Elsevier Science Ltd; Journal Of Symbolic Computation; 109; 3-2022; 31-49
dc.identifier.issn
0747-7171
dc.identifier.uri
http://hdl.handle.net/11336/243262
dc.description.abstract
In the area of symbolic-numerical computation within computer algebra, an interesting question is how “close” a random input is to the “critical” ones. Examples are the singular matrices in linear algebra or the polynomials with multiple roots for Newton's root-finding method. Bounds, sometimes very precise, are known for the volumes over or of such neighborhoods of the varieties of “critical” inputs; see the references below. This paper deals with the discrete version of this question: over a finite field, how many points lie in a certain type of neighborhood around a given variety? A trivial upper bound on this number is given by the product (size of the variety) ⋅ (size of a neighborhood of a point). It turns out that this bound is usually asymptotically tight, in particular for the singular matrices, polynomials with multiple roots, and pairs of non-coprime polynomials. The interesting question then is: for which varieties is this bound not asymptotically tight? We show that these are precisely those that admit a shift, that is, where one absolutely irreducible component of maximal dimension is a shift (translation by a fixed nonzero point) of another such component. Furthermore, the shift-invariant absolutely irreducible varieties are characterized as being cylinders over some base variety. Computationally, determining whether a given variety is shift-invariant turns out to be intractable, namely NP-hard even in simple cases.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Academic Press Ltd - Elsevier Science Ltd
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
FINITE FIELDS
dc.subject
NEIGHBORHOODS AROUND VARIETIES
dc.subject
NEIGHBORHOODS OF VARIETIES
dc.subject
POLYNOMIAL SYSTEMS
dc.subject.classification
Matemática Pura
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Shifted varieties and discrete neighborhoods around varieties
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2024-08-28T09:57:51Z
dc.journal.volume
109
dc.journal.pagination
31-49
dc.journal.pais
Estados Unidos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.description.fil
Fil: Von zur Gathen, Joachim. Universitat Bonn; Alemania
dc.description.fil
Fil: Matera, Guillermo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina
dc.journal.title
Journal Of Symbolic Computation
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.jsc.2021.07.001
Archivos asociados