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), 14451473
MSC (2000):
Primary 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30
Published electronically:
October 19, 2009
MathSciNet review:
2563736
Fulltext 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 (1975),
no. 2, 165–174. MR 0371782
(51 #7999)
 2.
Joel
Berman and PawełM.
Idziak, Generative complexity in algebra, Mem. Amer. Math.
Soc. 175 (2005), no. 828, viii+159. MR 2130585
(2006a:08001), http://dx.doi.org/10.1090/memo/0828
 3.
Andrei
Bulatov, Hubie
Chen, and Víctor
Dalmau, Learning intersectionclosed classes with signatures,
Theoret. Comput. Sci. 382 (2007), no. 3,
209–220. MR 2348225
(2008h:68057), http://dx.doi.org/10.1016/j.tcs.2007.03.039
 4.
Andrei
Bulatov and Víctor
Dalmau, A simple algorithm for Mal′tsev constraints,
SIAM J. Comput. 36 (2006), no. 1, 16–27
(electronic). MR
2231638 (2007f:68073), http://dx.doi.org/10.1137/050628957
 5.
Andrei
Bulatov, Peter
Jeavons, and Andrei
Krokhin, Classifying the complexity of constraints using finite
algebras, SIAM J. Comput. 34 (2005), no. 3,
720–742. MR 2137072
(2005k:68181), http://dx.doi.org/10.1137/S0097539700376676
 6.
Stanley
Burris and H.
P. Sankappanavar, A course in universal algebra, Graduate
Texts in Mathematics, vol. 78, SpringerVerlag, New York, 1981. MR 648287
(83k:08001)
 7.
Hubie
Chen, The expressive rate of constraints, Ann. Math. Artif.
Intell. 44 (2005), no. 4, 341–352. MR 2185700
(2006g:68239), http://dx.doi.org/10.1007/s1047200570314
 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 majorityminority operations are tractable. In LICS '05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), pages 438447, Washington, DC, USA, 2005. IEEE Computer Society.
 10.
Víctor
Dalmau and Peter
Jeavons, Learnability of quantified formulas, Theoret. Comput.
Sci. 306 (2003), no. 13, 485–511. MR 2000189
(2004i:68092), http://dx.doi.org/10.1016/S03043975(03)003426
 11.
Alan
Day, A characterization of modularity for congruence lattices of
algebras., Canad. Math. Bull. 12 (1969),
167–173. 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 (1999), no. 1, 57–104
(electronic). MR
1630445 (2000e:68063), http://dx.doi.org/10.1137/S0097539794266766
 13.
Ralph
Freese and Ralph
McKenzie, Commutator theory for congruence modular varieties,
London Mathematical Society Lecture Note Series, vol. 125, Cambridge
University Press, Cambridge, 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 (1984), no. 305, v+125. MR 749524
(86e:08006a), http://dx.doi.org/10.1090/memo/0305
 15.
H.
Peter Gumm, Geometrical methods in congruence modular
algebras, Mem. Amer. Math. Soc. 45 (1983),
no. 286, viii+79. MR 714648
(85e:08012), http://dx.doi.org/10.1090/memo/0286
 16.
Bradd
Hart, Sergei
Starchenko, and Matthew
Valeriote, Vaught’s conjecture for
varieties, Trans. Amer. Math. Soc.
342 (1994), no. 1,
173–196. MR 1191612
(94e:03036), http://dx.doi.org/10.1090/S00029947199411916120
 17.
David
Hobby and Ralph
McKenzie, The structure of finite algebras, Contemporary
Mathematics, vol. 76, American Mathematical Society, Providence, RI,
1988. 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 213224, 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, J.
Amer. Math. Soc. 22 (2009), no. 1, 119–165. MR 2449056
(2009j:08001), http://dx.doi.org/10.1090/S0894034708006140
 20.
Peter
Jeavons, On the algebraic structure of combinatorial problems,
Theoret. Comput. Sci. 200 (1998), no. 12,
185–204. MR 1625523
(99d:68085), http://dx.doi.org/10.1016/S03043975(97)002302
 21.
Keith Kearnes and Ágnes Szendrei.
Clones of parallelogram algebras. preprint, 2007.
 22.
Petar
Marković and Ralph
McKenzie, Few subpowers, congruence distributivity and
nearunanimity terms, Algebra Universalis 58 (2008),
no. 2, 119–128. MR 2386525
(2009b:08008), http://dx.doi.org/10.1007/s0001200820491
 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 (1965), 514–538. MR 0175782
(31 #58), http://dx.doi.org/10.1090/S00029947196501757820
 25.
Luís
Sequeira, Nearunanimity is decomposable, Algebra Universalis
50 (2003), no. 2, 157–164. MR 2037523
(2004i:08011), http://dx.doi.org/10.1007/s0001200318304
 26.
S.
Shelah, Classification theory and the number of nonisomorphic
models, 2nd ed., Studies in Logic and the Foundations of Mathematics,
vol. 92, NorthHolland Publishing Co., Amsterdam, 1990. MR 1083551
(91k:03085)
 1.
 Kirby A. Baker and Alden F. Pixley.
Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z., 143(2):165174, 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 intersectionclosed classes with signatures. Theor. Comput. Sci., 382(3):209220, 2007. MR 2348225 (2008h:68057)
 4.
 Andrei Bulatov and Vıctor Dalmau.
A simple algorithm for Mal'tsev constraints. SIAM J. Comput., 36(1):1627 (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):720742 (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. SpringerVerlag, New York, 1981. MR 648287 (83k:08001)
 7.
 Hubie Chen.
The expressive rate of constraints. Ann. Math. Artif. Intell., 44(4):341352, 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 majorityminority operations are tractable. In LICS '05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), pages 438447, Washington, DC, USA, 2005. IEEE Computer Society.
 10.
 Vıctor Dalmau and Peter Jeavons.
Learnability of quantified formulas. Theoret. Comput. Sci., 306(13):485511, 2003. MR 2000189 (2004i:68092)
 11.
 Alan Day.
A characterization of modularity for congruence lattices of algebras. Canad. Math. Bull., 12:167173, 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):57104 (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):173196, 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 213224, 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):119165, 2009. MR 2449056
 20.
 Peter Jeavons.
On the algebraic structure of combinatorial problems. Theoret. Comput. Sci., 200(12):185204, 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 nearunanimity terms. Algebra Universalis, 58(2):119128, 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:514538, 1965. MR 0175782 (31:58)
 25.
 Luıs Sequeira.
Nearunanimity is decomposable. Algebra Universalis, 50(2):157164, 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. NorthHolland 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
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:
http://dx.doi.org/10.1090/S0002994709048740
PII:
S 00029947(09)048740
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. DMS0245622, and the last two authors were supported by the NSERC of Canada.
Article copyright:
© Copyright 2009 American Mathematical Society
