Publication:820939

DOI10.1016/J.JSC.2021.07.001zbMATH Open1489.14087arXiv1812.07020OpenAlexW3197512519MaRDI QIDQ820939FDOQ820939

Joachim von zur Gathen, Guillermo Matera

Publication date: 29 September 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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, like 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. 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 (size of the variety) x (size of a neighborhood of a point). It turns out that this bound is usually asymptotically tight, including for the singular matrices, polynomials with multiple roots, and pairs of non-coprime polynomials. The interesting question then is: for which varieties does this bound not hold? We show that these are precisely those that admit a shift, that is, where one absolutely irreducible component 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.

Full work available at URL: https://arxiv.org/abs/1812.07020

zbMATH Keywords

finite fieldspolynomial systemsneighborhoods around varietiesneighborhoods of varieties

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Finite ground fields in algebraic geometry (14G15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Solving polynomial systems; resultants (13P15) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Geometric aspects of numerical algebraic geometry (14Q65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Handbook of finite fields
• Eigenvalues and Condition Numbers of Random Matrices
• Quasi-gcd computations
• The fundamental theorem of algebra and complexity theory
• The Probability That a Numerical Analysis Problem is Difficult
• Determinantal rings
• Definability and fast quantifier elimination in algebraically closed fields
• Estimates on the distribution of the condition number of singular matrices
• Uniform Distribution of Polynomials Over Finite Fields
• Detection and validation of clusters of polynomial zeros
• Homogeneity degrees of the set of singular complete intersections
• On the equal-subset-sum problem
• Improved explicit estimates on the number of solutions of equations over a finite field
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• On the Distribution of a Scaled Condition Number
• Distribution of polynomial discriminants modulo a prime
• Density of real and complex decomposable univariate polynomials

This page was built for publication: Shifted varieties and discrete neighborhoods around varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820939)