Varieties with few subalgebras of powers

Authors:
Joel Berman, Paweł Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote and Ross Willard

Journal:
Trans. Amer. Math. Soc. **362** (2010), 1445-1473

MSC (2000):
Primary 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30

DOI:
https://doi.org/10.1090/S0002-9947-09-04874-0

Published electronically:
October 19, 2009

MathSciNet review:
2563736

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 of subalgebras of finite Cartesian powers of a finite universal algebra . One particular strategy, advanced by Dalmau in his doctoral thesis (2000), has confirmed the conjecture for a certain class of finite algebras which, among other things, have the property that the number of subalgebras of is bounded by an exponential polynomial. In this paper we characterize the finite algebras 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 and some related functions on the one hand, and some standard algebraic properties of on the other hand. The theory developed here was applied to the Constraint Satisfaction Problem Dichotomy Conjecture, completing Dalmau's strategy.

**1.**Kirby A. Baker and Alden F. Pixley.

Polynomial interpolation and the Chinese remainder theorem for algebraic systems.*Math. Z.*, 143(2):165-174, 1975. MR**0371782 (51:7999)****2.**Joel Berman and Paweł M. Idziak.

Generative complexity in algebra.*Mem. Amer. Math. Soc.*, 175(828):viii+159 pp., 2005. MR**2130585 (2006a:08001)****3.**Andrei Bulatov, Hubie Chen, and Vıctor Dalmau.

Learning intersection-closed classes with signatures.*Theor. Comput. Sci.*, 382(3):209-220, 2007. MR**2348225 (2008h:68057)****4.**Andrei Bulatov and Vıctor Dalmau.

A simple algorithm for Mal'tsev constraints.*SIAM J. Comput.*, 36(1):16-27 (electronic), 2006. MR**2231638 (2007f:68073)****5.**Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.

Classifying the complexity of constraints using finite algebras.*SIAM J. Comput.*, 34(3):720-742 (electronic), 2005. MR**2137072 (2005k:68181)****6.**Stanley Burris and H. P. Sankappanavar.*A course in universal algebra*, volume 78 of*Graduate Texts in Mathematics*.

Springer-Verlag, New York, 1981. MR**648287 (83k:08001)****7.**Hubie Chen.

The expressive rate of constraints.*Ann. Math. Artif. Intell.*, 44(4):341-352, 2005. MR**2185700 (2006g:68239)****8.**Víctor Dalmau.*Computational complexity of problems over generalized formulas*.

Ph.D. thesis, Universitat Politécnica de Catalunya, 2000.**9.**Vıctor Dalmau.

Generalized majority-minority operations are tractable.

In*LICS '05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)*, pages 438-447, Washington, DC, USA, 2005. IEEE Computer Society.**10.**Vıctor Dalmau and Peter Jeavons.

Learnability of quantified formulas.*Theoret. Comput. Sci.*, 306(1-3):485-511, 2003. MR**2000189 (2004i:68092)****11.**Alan Day.

A characterization of modularity for congruence lattices of algebras.*Canad. Math. Bull.*, 12:167-173, 1969. MR**0248063 (40:1317)****12.**Tomás Feder and Moshe Y. Vardi.

The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.*SIAM J. Comput.*, 28(1):57-104 (electronic), 1999. MR**1630445 (2000e:68063)****13.**R. Freese and R. McKenzie.*Commutator Theory for Congruence Modular Varieties*, volume 125 of*London Mathematical Society Lecture Note Series*.

Cambridge University Press, 1987. MR**909290 (89c:08006)****14.**O. C. Garcıa and W. Taylor.

The lattice of interpretability types of varieties.*Mem. Amer. Math. Soc.*, 50(305):v+125, 1984. MR**749524 (86e:08006a)****15.**H. Peter Gumm.

Geometrical methods in congruence modular algebras.*Mem. Amer. Math. Soc.*, 45(286):viii+79, 1983. MR**714648 (85e:08012)****16.**Bradd Hart, Sergei Starchenko, and Matthew Valeriote.

Vaught's conjecture for varieties.*Trans. Amer. Math. Soc.*, 342(1):173-196, 1994. MR**1191612 (94e:03036)****17.**David Hobby and Ralph McKenzie.*The structure of finite algebras*, volume 76 of*Contemporary Mathematics*.

American Mathematical Society, Providence, RI, 1988.

Revised edition: 1996. MR**958685 (89m:08001)****18.**Paweł Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard.

Tractability and learnability arising from algebras with few subpowers.

In*LICS '07: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science*, pages 213-224, Washington, DC, USA, 2007. IEEE Computer Society.**19.**Paweł Idziak, Ralph McKenzie, and Matthew Valeriote.

The structure of locally finite varieties with polynomially many models.*Journal of the American Mathematical Society*32(1):119-165, 2009. MR**2449056****20.**Peter Jeavons.

On the algebraic structure of combinatorial problems.*Theoret. Comput. Sci.*, 200(1-2):185-204, 1998. MR**1625523 (99d:68085)****21.**Keith Kearnes and Ágnes Szendrei.

Clones of parallelogram algebras.

preprint, 2007.**22.**Petar Marković and Ralph McKenzie.

Few subpowers, congruence distributivity and near-unanimity terms.*Algebra Universalis*, 58(2):119-128, 2008. MR**2386525 (2009b:08008)****23.**Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor.*Algebras, lattices, varieties. Vol. I*.

The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987. MR**883644 (88e:08001)****24.**Michael Morley.

Categoricity in power.*Trans. Amer. Math. Soc.*, 114:514-538, 1965. MR**0175782 (31:58)****25.**Luıs Sequeira.

Near-unanimity is decomposable.*Algebra Universalis*, 50(2):157-164, 2003. MR**2037523 (2004i:08011)****26.**S. Shelah.*Classification theory and the number of nonisomorphic models*, volume 92 of*Studies in Logic and the Foundations of Mathematics*.

North-Holland Publishing Co., Amsterdam, second edition, 1990. MR**1083551 (91k:03085)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
08B05,
08B10,
08A30,
08A70,
68Q25,
68Q32,
68W30

Retrieve articles in all journals with MSC (2000): 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30

Additional Information

**Joel Berman**

Affiliation:
Department of Mathematics, University of Illinois at Chicago, Chicago, Illinois 60607

Email:
jberman@uic.edu

**Paweł Idziak**

Affiliation:
Department of Theoretical Computer Science, Jagiellonian University, Kraków, Poland

Email:
idziak@tcs.uj.edu.pl

**Petar Markovic**

Affiliation:
Department of Mathematics and Informatics, University of Novi Sad, Serbia

Email:
pera@im.ns.ac.yu

**Ralph McKenzie**

Affiliation:
Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240

Email:
mckenzie@math.vanderbilt.edu

**Matthew Valeriote**

Affiliation:
Department of Mathematics, McMaster University, Hamilton, Ontario, Canada L8S 4K1

Email:
matt@math.mcmaster.ca

**Ross Willard**

Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 2G1

Email:
rdwillar@uwaterloo.ca

DOI:
https://doi.org/10.1090/S0002-9947-09-04874-0

Keywords:
Maltsev condition,
variety,
constraint satisfaction problem

Received by editor(s):
February 5, 2008

Published electronically:
October 19, 2009

Additional Notes:
The second author was supported by grant no. N206 2106 33 of the Polish Ministry of Science, the third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia, the fourth author was supported by a grant from the US National Science Foundation, no. DMS-0245622, and the last two authors were supported by the NSERC of Canada.

Article copyright:
© Copyright 2009
American Mathematical Society