Complexity of Algebraic Structures

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

The project introduces an approach to the study of theoretical aspects of certain classes of algebraic structures from the perspective of complexity. The main objective is the study of algebraic structures--a ring, an ideal, or even a module--as they undergo smoothing processes. These transformations enable them to support new constructions, including analytic ones. In the case of algebras, divisors acquire a group structure, cohomology tends to slim down, and it is an essential step in the desingularization of singular varieties. At its core is the inherent interest in those processes that add to the structure the solutions of collections of equations of integral dependence. Finding these equations, determining the properties of the assemblage of solutions and understanding the complexity costs of these tasks is a central region of research for commutative algebra. The assignments of measures of size, via multiplicity theories recently discovered by the proposer and his students, to the algebras and to the construction itself are key aspects of the project. As applications, the proposer seeks to predict how delicate techniques associated to smoothing processes will perform when applied to the solution of several problems of interest, and thereby suggest which mix of methods offer higher performance. They will also be employed to derive ordinary complexity counts for several of these problems without previously known classical counts. Commutative algebra, the subject area of the proposal, is foremost the study of systems of polynomial equations, and of its generalizations. It has elucidated several structures that occur among such systems, particularly those tagged as of Cohen-Macaulay type. These encode theoretical efficiencies in the derivation/prediction of its properties and offer superb computational economies. Often the full natural set of equations is not known at the outset so that methods and processes must be developed to find and analyze it. This proposal is focused on one central process, that of smoothing transformation. It will develop methods, grounded on the Cohen-Macaulay case, to predict properties of the closure, devise algorithms to find it and examine the limits of the behavior of arbitrary (even unknown) algorithms. The results and methods developed will be used for interaction where the subject meets algebraic geometry, combinatorics, geometric modeling, number theory and robotics.