A bound for the degree of a system of equations determining the variety of reducible polynomials
Author:
A. L. Chistov
Translated by:
the author
Original publication:
Algebra i Analiz, tom 24 (2012), nomer 3.
Journal:
St. Petersburg Math. J. 24 (2013), 513528
MSC (2010):
Primary 14Q15; Secondary 14M99, 12Y05, 12E05, 13P05
Published electronically:
March 21, 2013
MathSciNet review:
3014133
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let denote the affine space of homogeneous polynomials of degree in variables with coefficients from the algebraic closure of a field of arbitrary characteristic; so . It is proved that the variety of all reducible polynomials in this affine space can be given by a system of polynomial equations of degree less than in variables. This result makes it possible to formulate an efficient version of the first Bertini theorem for the case of a hypersurface.
 1.
Nicolas
Bourbaki, Commutative algebra. Chapters 1–7, Elements of
Mathematics (Berlin), SpringerVerlag, Berlin, 1998. Translated from the
French; Reprint of the 1989 English translation. MR 1727221
(2001g:13001)
 2.
A.
L. Chistov, An algorithm of polynomial complexity for factoring
polynomials, and determination of the components of a variety in a
subexponential time, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst.
Steklov. (LOMI) 137 (1984), 124–188 (Russian, with
English summary). Theory of the complexity of computations, II. MR 762101
(86g:11077b)
 3.
A.
L. Chistov, A doubly exponential lower bound for
the degree of a system of generators of a polynomial prime ideal,
Algebra i Analiz 20 (2008), no. 6, 186–213
(Russian, with Russian summary); English transl., St.
Petersburg Math. J. 20 (2009), no. 6, 983–1001. MR 2530898
(2010e:13015), 10.1090/S1061002209010814
 4.
, A deterministic polynomialtime algorithm for the first Bertini theorem, Preprint of St. Petersburg Math. Soc., 2004, http://www.mathsoc.spb.ru/preprint/2004/index.html
 5.
Alexander
Chistov, Hervé
Fournier, Leonid
Gurvits, and Pascal
Koiran, Vandermonde matrices, NPcompleteness, and transversal
subspaces, Found. Comput. Math. 3 (2003), no. 4,
421–427. MR 2009684
(2004h:15026), 10.1007/s1020800200764
 6.
A.
K. Lenstra, H.
W. Lenstra Jr., and L.
Lovász, Factoring polynomials with rational
coefficients, Math. Ann. 261 (1982), no. 4,
515–534. MR
682664 (84a:12002), 10.1007/BF01457454
 7.
Oscar
Zariski, Pencils on an algebraic variety and a
new proof of a theorem of Bertini, Trans. Amer.
Math. Soc. 50
(1941), 48–70. MR 0004241
(2,345a), 10.1090/S00029947194100042414
 1.
 N. Bourbaki, Commutative algebra. Ch. 17, SpringerVerlag, Berlin, 1998. MR 1727221 (2001g:13001)
 2.
 A. L. Chistov, An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 124188; English transl. in J. Soviet Math. 34 (1986), no. 4. MR 762101 (86g:11077b)
 3.
 , Doubleexponential lower bound for the degree of any system of generators of a polynomial prime ideal, Algebra i Analiz 20 (2008), no. 6, 186213; English transl., St. Petersburg Math. J. 20 (2009), no. 6, 9831001. MR 2530898 (2010e:13015)
 4.
 , A deterministic polynomialtime algorithm for the first Bertini theorem, Preprint of St. Petersburg Math. Soc., 2004, http://www.mathsoc.spb.ru/preprint/2004/index.html
 5.
 A. L. Chistov, H. Fournier, L. Gurvits, and P. Koiran, Vandermonde matrices, NPcompleteness, and transversal subspaces, Found. Comput. Math. 3 (2003), no. 4, 421427. MR 2009684 (2004h:15026)
 6.
 A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515534. MR 682664 (84a:12002)
 7.
 O. Zariski, Pencils on an algebraic variety and a new proof of a theorem of Bertini, Trans. Amer. Math. Soc. 50 (1941), 4870. MR 0004241 (2:345a)
Similar Articles
Retrieve articles in St. Petersburg Mathematical Journal
with MSC (2010):
14Q15,
14M99,
12Y05,
12E05,
13P05
Retrieve articles in all journals
with MSC (2010):
14Q15,
14M99,
12Y05,
12E05,
13P05
Additional Information
A. L. Chistov
Affiliation:
St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, Saint Petersburg 191023, Russia
Email:
alch@pdmi.ras.ru
DOI:
http://dx.doi.org/10.1090/S106100222013012519
Keywords:
Absolute irreducibility,
lattices,
Bertini theorem
Received by editor(s):
November 1, 2011
Published electronically:
March 21, 2013
Article copyright:
© Copyright 2013
American Mathematical Society
