多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

Fully Optimal Bases and the Active Bijection in Graphs,Hyperplane Arrangements,and Oriented Matroids

In this note, we present the main results of a series of forthcoming papers, dealing with bi-jective generalizations of some counting formulas. New intrinsic constructions in oriented matroids on a linearly ordered set of elements establish notably structural links between counting regions and linear programming. We introduce fully optimal bases, which have a simple combinatorial characterization, and strengthen the well-known optimal bases of linear programming. Our main result is that every bounded region of an ordered hyperplane arrangement, or ordered oriented matroid, has a unique fully optimal basis, providing the active bijection between bounded regions and uniactive internal bases. The active bijec-tion is extended to an activity preserving mapping between all reorientations and all bases of an ordered oriented matroid. It gives a bijective interpretation of the equality of two expressions for the Tutte polynomial, as well as a new expression of this polynomial in terms of beta invariants of minors. There are several refinements, such as an activity preserving bijection between regions (acyclic reorientations) and no-broken-circuit subsets, and others in terms of hyperplane arrangements, graphs, and permutations.     

Graph products of spheres, associative graded algebras and Hilbert series

Given a finite, simple, vertex-weighted graph, we construct a graded associative (noncommutative) algebra, whose generators correspond to vertices and whose ideal of relations has generators that are graded commutators corresponding to edges. We show that the Hilbert series of this algebra is the inverse of the clique polynomial of the graph. Using this result it easy to recognize if the ideal is inert, from which strong results on the algebra follow. Noncommutative Gr?bner bases play an important role in our proof. There is an interesting application to toric topology. This algebra arises naturally from a partial product of spheres, which is a special case of a generalized moment?Cangle complex. We apply our result to the loop-space homology of this space.     

Grobner基的一个应用

固定一个项序,利用Buchberger算法求多项式环S=C[x1,x2,…,xn]上的理想I的Grbner基.根据S上任意多项式f（x1,x2,…,xn）用Grobner基表示时其余项唯一的特点,将其应用到求解多项式方程组问题.实例展示用Grobner基可证明一个联立方程式是无解的.     

分区参数Grbner基的计算

对于含参数的多项式理想,提出了分区参数Grbner基的概念,并且给出了一个计算分区参数Grbner基的算法,证明了该算法的正确性和终止性.     

On an asymptotic analysis of polynomial approximation to halfband filters

In this paper we provide information about the asymptotic properties of polynomial filters which approximate the ideal filter. In particular, we study this problem in the special case of polynomial halfband filters. Specifically we estimate the error between a polynomial filter and an ideal filter and show that the error decays exponentially fast. For the special case of polynomial halfband filters, our n-th root asymptotic error estimates are sharp.     

分区参数Gr\

对于含参数的多项式理想,提出了分区参数Gröbner基的概念,并且给出了一个计算分区参数Gröbner基的算法,证明了该算法的正确性和终止性.     

On constructing bases for ideals in polynomial rings over the integers

The author defines canonical bases for ideals in polynomial rings over Z and develops an algorithm for constructing such a basis for a given ideal. Results of previous authors are discussed and a comparison between those and the results obtained here is included.     

Computing Gröbner fans

This paper presents algorithms for computing the Gröbner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Gröbner bases of the ideal. Our algorithms are based on a uniform definition of the Gröbner fan that applies to both homogeneous and non-homogeneous ideals and a proof that this object is a polyhedral complex. We show that the cells of a Gröbner fan can easily be oriented acyclically and with a unique sink, allowing their enumeration by the memory-less reverse search procedure. The significance of this follows from the fact that Gröbner fans are not always normal fans of polyhedra, in which case reverse search applies automatically. Computational results using our implementation of these algorithms in the software package Gfan are included.

     

Flat modules and the behavior of a standard basis relative to an extension of the ground ring

The property of a generating set of a polynomial ideal or of an ideal of a free associative algebra over a commutative ring to be its Gr?bner basis is kept by a flat (but not any) extension of the ground ring. The converse is proved in the broader context of standard bases for filtered modules.     

Reduced Gröbner Bases in Polynomial Rings over a Polynomial Ring

We propose a new notion of reduced Gr?bner bases in polynomial rings over a polynomial ring and we show that every ideal has a unique reduced Gr?bner basis. We introduce an algorithm for computing them.     

Extremality with respect to the estimates of Dubreil-Campanella: Splitting theorems

Campanella's refinements of Dubreil's theorem are sharp upper and lower bounds, formulated in postulational terms, for the number of forms of any given degree in the standard bases of 2-codimensional perfect homogeneous polynomial ideals. This note considers the implications of upper-bound-extremality. Its principal discovery is that such extremality implies a splitting of the syzygy module of any standard basis of such an ideal into syzygy modules of the standard bases of ‘component’ ideals explicitly describable in terms of the standard basis in question.     

Cubic Spline Prewavelets on the Four-Directional Mesh

Dedicated to Professor M. J. D. Powell on the occasion of his sixty-fifth birthday and his retirement. In this paper, we design differentiable, two-dimensional, piecewise polynomial cubic prewavelets of particularly small compact support. They are given in closed form, and provide stable, orthogonal decompositions of L ² (R ² ) . In particular, the splines we use in our prewavelet constructions give rise to stable bases of spline spaces that contain all cubic polynomials, whereas the more familiar box spline constructions cannot reproduce all cubic polynomials, unless resorting to a box spline of higher polynomial degree.     

Effective Genericity, δ-Regularity and Strong Noether Position

We show that the concept of strong Noether position for a polynomial ideal ? ? left𝒫 is equivalent to δ-regularity and thus related to Pommaret bases. In particular, we provide explicit Pommaret bases for two of the ideal sequences used in Hashemi's definition of strong Noether position and alternative proofs for a number of his statements. Finally, we show that one consequence of δ-regularity is that any Pommaret basis contains a system of parameters and we present an algorithm for checking whether the factor ring 𝒫/? is Gorenstein via a socle computation.     

Degree bounds for Gröbner bases in algebras of solvable type

We establish doubly-exponential degree bounds for Gröbner bases in certain algebras of solvable type over a field (as introduced by Kandri-Rody and Weispfenning). The class of algebras considered here includes commutative polynomial rings, Weyl algebras, and universal enveloping algebras of finite-dimensional Lie algebras. For the computation of these bounds, we adapt a method due to Dubé based on a generalization of Stanley decompositions. Our bounds yield doubly-exponential degree bounds for ideal membership and syzygies, generalizing the classical results of Hermann and Seidenberg (in the commutative case) and Grigoriev (in the case of Weyl algebras).     

The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: The fully optimal basis of a bounded region

The present paper is the first in a series of four dealing with a mapping, introduced by the present authors, from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). This mapping is actually defined for ordered oriented matroids. We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions–one in terms of activities of reorientations, and the other in terms of activities of bases–of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial.We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.     

Rings whose singular ideals are nil

Abstract

It is well known that when a ring R satisfies ACC on right annihilators of elements, then the right singular ideal of R is nil, in this case, we say R is right nil-singular. Many classes of rings whose singular ideals are nil, but do not satisfy the ACC on right annihilators, are presented and the behavior of them is investigated with respect to various constructions, in particular skew polynomial rings and triangular matrix rings. The class of right nil-singular rings contains π-regular rings and is closed under direct sums. Examples are provided to explain and delimit our results.     

The ideal of separants in the ring of differential polynomials

We obtained the criterion of existence of a quasi-linear polynomial in a differential ideal in the ordinary ring of differential polynomials over a field of characteristic zero. We generalized the “going up” and “going down” theorems onto the case of Ritt algebras. In particular, new finiteness criteria for differential standard bases and estimates that characterize calculation complexity were obtained. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 1, pp. 215–227, 2007.     

The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier‐free case and in the case of purely existential or universal quantifiers, we show that Ω(n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao‐Håstad switching lemma (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Computing border bases using mutant strategies

Border bases, a generalization of Gröbner bases, have actively been addressed during recent years due to their applicability to industrial problems. In cryptography and coding theory a useful application of border based is to solve zero-dimensional systems of polynomial equations over finite fields, which motivates us for developing optimizations of the algorithms that compute border bases. In 2006, Kehrein and Kreuzer formulated the Border Basis Algorithm (BBA), an algorithm which allows the computation of border bases that relate to a degree compatible term ordering. In 2007, J. Ding et al. introduced mutant strategies bases on finding special lower degree polynomials in the ideal. The mutant strategies aim to distinguish special lower degree polynomials (mutants) from the other polynomials and give them priority in the process of generating new polynomials in the ideal. In this paper we develop hybrid algorithms that use the ideas of J. Ding et al. involving the concept of mutants to optimize the Border Basis Algorithm for solving systems of polynomial equations over finite fields. In particular, we recall a version of the Border Basis Algorithm which is actually called the Improved Border Basis Algorithm and propose two hybrid algorithms, called MBBA and IMBBA. The new mutants variants provide us space efficiency as well as time efficiency. The efficiency of these newly developed hybrid algorithms is discussed using standard cryptographic examples.