Back to Search
Start Over
Shifted varieties and discrete neighborhoods around varieties.
- Source :
-
Journal of Symbolic Computation . Mar2022, Vol. 109, p31-49. 19p. - Publication Year :
- 2022
-
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 R or C 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 07477171
- Volume :
- 109
- Database :
- Academic Search Index
- Journal :
- Journal of Symbolic Computation
- Publication Type :
- Academic Journal
- Accession number :
- 152557018
- Full Text :
- https://doi.org/10.1016/j.jsc.2021.07.001