Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

References [Enhancements On Off] (What's this?)

  • 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)

Similar Articles

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

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

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

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

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

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

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

American Mathematical Society