Varieties with few subalgebras of powers
Varieties with few subalgebras of powers
复制标题
幂子代数很少的簇
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Willard
中科院分区：
文献类型：
--
作者：
J. Berman;P. Idziak;P. Marković;R. McKenzie;M. Valeriote;R. Willard
Feder和Vardi（1999）的约束满足问题二分法猜想在过去的10年中被有效地重新表述为关于有限泛代数A的有限笛卡尔幂的子代数的集合SP fin（A）的猜想。一个特别的战略，先进的Dalmau在他的博士论文（2000年），证实了猜想的某一类有限代数A，其中，除其他外，有财产的数量子代数的A n是有界的指数多项式。本文刻画了具有这一性质的有限代数A，我们称之为具有较少子幂的代数，并发展了具有较少子幂的代数的子幂的表示理论。我们的表征表明，代数有几个次幂的有限成员的一个新发现的和令人惊讶的强大的Maltsev类定义的存在一个特殊的术语，我们称之为边项。一方面，我们证明了An的子代数数的渐近性态与相关函数的渐近性态之间的紧密联系，另一方面，我们证明了A的一些标准代数性质.这里开发的理论被应用到约束满足问题二分法猜想，完成Dalmau的战略。
The Constraint Satisfaction Problem Dichotomy Conjecture of Feder and Vardi (1999) has in the last 10 years been profitably reformulated as a conjecture about the set SP fin (A) of subalgebras of finite Cartesian powers of a finite universal algebra A. One particular strategy, advanced by Dalmau in his doctoral thesis (2000), has confirmed the conjecture for a certain class of finite algebras A which, among other things, have the property that the number of subalgebras of A n is bounded by an exponential polynomial. In this paper we characterize the finite algebras A with this property, which we call having few subpowers, and develop a representation theory for the subpowers of algebras having few subpowers. Our characterization shows that algebras having few subpowers are the finite members of a newly discovered and surprisingly robust Maltsev class defined by the existence of a special term we call an edge term. We also prove some tight connections between the asymptotic behavior of the number of subalgebras of A n and some related functions on the one hand, and some standard algebraic properties of A on the other hand. The theory developed here was applied to the Constraint Satisfaction Problem Dichotomy Conjecture, completing Dalmau's strategy.