Double-exponential growth of the number of vectors of solutions of polynomial systems
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 47-52
Voir la notice de l'article provenant de la source Math-Net.Ru
In [4] it was proved an upper bound $d^{O\left(\left(\smallmatrix n+d\\n\endsmallmatrix\right)\right)}$ on the number of vectors of multiplicities of the solutions of systems of the form $g_1=\ldots=g_n=0$ (provided, it has a finite number of solutions) of polynomials $g_1,\dots,g_n\in F[X_1,\dots,X_n]$ with degrees $\deg g_i\le d$ (the field $F$ is algebraically closed). In the present paper it is shown that this bound is close in order to the exact one. In particular, in case $d=n$ the construction provides a double-exponential (in $n$) number of vectors of multiplicities.
@article{ZNSL_2001_277_a2,
author = {D. Yu. Grigor'ev},
title = {Double-exponential growth of the number of vectors of solutions of polynomial systems},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {47--52},
publisher = {mathdoc},
volume = {277},
year = {2001},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a2/}
}
D. Yu. Grigor'ev. Double-exponential growth of the number of vectors of solutions of polynomial systems. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 47-52. http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a2/