Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zapiski Nauchnykh Seminarov LOMI, 1984, Volume 137, Pages 7–19 (Mi znsl4785)  

Bounds of real roots of a system of algebraic equations

N. N. Vorobjov (Jr.)
Abstract: Let $V\subset\mathbb R^n$ be real algebraic variety defined by the system of equations $f_1=\dots=f_m=0$, where $f_i\in\mathbb Q[x_1,\dots,x_n]$ $(i=1,2,\dots,n)$. Denote by $L$ the maximum of bitwise lengths of descriptions of coefficients of the system and propose $d=\sum_{i=1}^n\operatorname{deg}f_i$, $r=\binom{n+2d}n$. It is proved, that for any compound $V'$ of the variety $V$ there exists such a point $x=(x_1,\dots,x_n)\in V'$, that $|x_i|<2^{H(r,L)}(i=1,\dots,n)$, where $H$ – is a polynomial independent on the input system. If $V$ is compact, then any point $x\in V$ has the metnioned property. Such kind of bounds may appear useful for creating subexponential-time algorithm for finding the real roots of algebraic systems.
The idea of the proof is the approximation of the input system real roots by corresponding complex roots of a certain sequence of systems which have finite number of roots each. The constraction of this sequence in the case of a compact $V$ uses the technic from [б] and can be realized as follows. It is sufficient to consider real varieties defined by one equation $f=0$ (replacing $f$ by $\sum_{i=1}^mf_i^2$). If null is critical value of the function $f$, then consider the sequence of polynomials $\tilde f^{(l)}=f-\nu_l$, where $\nu_l\in\mathbb R$ $(l=1,2,\dots)$ are regular values of $f$ and $\lim_{l\to\infty}\nu_l=0$. If points $(0,\dots,0,\pm1)\in S^{n-1}$ are critical values of Gauss mappings of varieties $\{\tilde f^{(l)}=0\}$ then trasform the sequence proposing $f^{(l)}(x)=\tilde f^{(l)}(\tilde M^{(l)}x)$, where $M^{(l)} (l=1,2,\dots)$ are appropriativ rotation matrices and $(0,\dots,0,\pm1)$ – regular values of Gauss mappings of varieties $\{f^{(l)}=0\}$. Approximate polynomials $\partial f^{(l)}/\partial x_1,\dots,\partial f^{(l)}/\partial x_{n-1}, f$ by polynomials $g_1^{(l)},\dots,g_n^{(l)}$ of the same degrees with real algebraically independent coefficients. As a result we have the sought sequence of the systems: $g_1^{(l)}=\dots=g_n^{(l)}=0$ $(l=1,2,\dots)$. The case, when $V$ is not compact is treated analogously, with the help of induction on $n$. Bounds for limit roots of a sequence of systems are obtained in lemma 1 with the help of one theorem due to Lazard ([5]).
In §3 some lower bounds for coordinates of real roots are obtained as corollaries.
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: N. N. Vorobjov (Jr.), “Bounds of real roots of a system of algebraic equations”, Computational complexity theory. Part II, Zap. Nauchn. Sem. LOMI, 137, "Nauka", Leningrad. Otdel., Leningrad, 1984, 7–19
Citation in format AMSBIB
\Bibitem{Vor84}
\by N.~N.~Vorobjov (Jr.)
\paper Bounds of real roots of a~system of algebraic equations
\inbook Computational complexity theory. Part~II
\serial Zap. Nauchn. Sem. LOMI
\yr 1984
\vol 137
\pages 7--19
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl4785}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=762095}
Linking options:
  • https://www.mathnet.ru/eng/znsl4785
  • https://www.mathnet.ru/eng/znsl/v137/p7
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024