Теория исключения в алгебраической геометрии

Введение

Часть алгебраической геометрии, посвященная исключению переменных из многочленов. В коммутативной алгебре и алгебраической геометрии теория исключения – это классическое название алгоритмических методов, предназначенных для исключения одних переменных из многочленов многих переменных с целью решения систем полиномиальных уравнений. Классическая теория исключения достигла своего пика в работах Фрэнсиса Маколея о многомерных результирующих функциях, как описано в главе, посвященной теории исключения, в первых изданиях (1930) «Современной алгебры» Бартеля ван дер Вардена. После этого теория исключения оставалась без внимания большинства алгебраических геометров почти тридцать лет, пока не появились новые методы решения полиномиальных уравнений, такие как базисы Грёбнера, необходимые для компьютерной алгебры.

История и связь с современными теориями

Область теории исключения была мотивирована необходимостью методов решения систем полиномиальных уравнений. Одним из первых результатов стала теорема Безу, которая ограничивает число решений (в случае двух многочленов от двух переменных в безуовский момент времени). За исключением теоремы Безу, общий подход заключался в исключении переменных для сведения задачи к одному уравнению с одной переменной. Случай линейных уравнений был полностью решен методом Гаусса, в то время как более старый метод правила Крамера не основан на исключении и работает только тогда, когда число уравнений равно числу переменных. В XIX веке это было расширено на линейные диофантовы уравнения и абелевы группы с нормальной формой Эрмита и нормальной формой Смита. До XX века были введены различные типы исключителей, включая результирующие функции и различные виды дискриминантов. В целом, эти исключители также инвариантны относительно различных преобразований переменных и являются фундаментальными в теории инвариантов. Все эти понятия являются конструктивными, в том смысле, что их определения включают в себя метод вычисления. Около 1890 года Давид Гильберт ввел неконструктивные методы, что было воспринято как революция, побудившая большинство алгебраических геометров первой половины XX века попытаться «избавиться от исключения». Тем не менее, теорема Гильберта о нулях (Nullstellensatz) может считаться относящейся к теории исключения, поскольку она утверждает, что система полиномиальных уравнений не имеет решений тогда и только тогда, когда можно исключить все неизвестные, чтобы получить противоречие 1 = 0. Теория исключения достигла своего апогея в работах Леопольда Кронекера, а затем Маколея, который ввел многомерные и U-результирующие функции, предоставив полные методы исключения для систем полиномиальных уравнений, которые описаны в главе о теории исключения в первых изданиях (1930) «Современной алгебры» ван дер Вардена. Позднее теория исключения была признана устаревшей и исключена из последующих изданий «Современной алгебры». Она оставалась в значительной степени игнорируемой до появления компьютеров и, в частности, компьютерной алгебры, которая вновь сделала актуальной разработку эффективных алгоритмов исключения, а не только доказательство существования и структурных результатов. Основными методами для возрождения теории исключения стали базисы Грёбнера и цилиндрическое алгебраическое разложение, представленные около 1970 года.

The field of elimination theory was motivated by the need of methods for solving systems of polynomial equations. One of the first results was Bézout's theorem, which bounds the number of solutions (in the case of two polynomials in two variables at Bézout time). Except for Bézout's theorem, the general approach was to eliminate variables for reducing the problem to a single equation in one variable. The case of linear equations was completely solved by Gaussian elimination, where the older method of Cramer's rule does not proceed by elimination, and works only when the number of equations equals the number of variables. In the 19th century, this was extended to linear Diophantine equations and abelian group with Hermite normal form and Smith normal form. Before the 20th century, different types of eliminants were introduced, including resultants, and various kinds of discriminants. In general, these eliminants are also invariant under various changes of variables, and are also fundamental in invariant theory. All these concepts are effective, in the sense that their definitions include a method of computation. Around 1890, David Hilbert introduced non effective methods, and this was seen as a revolution, which led most algebraic geometers of the first half of the 20th century to try to "eliminate elimination". Nevertheless Hilbert's Nullstellensatz, may be considered to belong to elimination theory, as it asserts that a system of polynomial equations does not have any solution if and only if one may eliminate all unknowns to obtain the constant equation 1 = 0. Elimination theory culminated with the work of Leopold Kronecker, and finally Macaulay, who introduced multivariate resultants and U resultants, providing complete elimination methods for systems of polynomial equations, which are described in the chapter on Elimination theory in the first editions (1930) of van der Waerden's Moderne Algebra. Later, elimination theory was considered old fashioned and removed from subsequent editions of Moderne Algebra. It was generally ignored until the introduction of computers, and more specifically of computer algebra, which again made relevant the design of efficient elimination algorithms, rather than merely existence and structural results. The main methods for this renewal of elimination theory are Gröbner bases and cylindrical algebraic decomposition, introduced around 1970.

Подключение к логике

Существует также логический аспект теории исключения, что проявляется в задаче булевой выполнимости. В худшем случае, предположительно, вычислительно сложно исключать переменные. Исключение кванторов – термин, используемый в математической логике для описания того, что в некоторых теориях каждая формула эквивалентна формуле без кванторов. Это справедливо для теории многочленов над алгебраически замкнутым полем, где теория исключения может рассматриваться как теория методов, позволяющих сделать исключение кванторов алгоритмически эффективным. Исключение кванторов над вещественными числами – еще один пример, который является фундаментальным в вычислительной алгебраической геометрии.