Comptes Rendus
On cogrowth function of algebras and its logarithmical gap
Comptes Rendus. Mathématique, Volume 359 (2021) no. 3, pp. 297-303.

Let AkX/I be an associative algebra. A finite word over alphabet X is I-reducible if its image in A is a k-linear combination of length-lexicographically lesser words. An obstruction is a subword-minimal I-reducible word. If the number of obstructions is finite then I has a finite Gröbner basis, and the word problem for the algebra is decidable. A cogrowth function is the number of obstructions of length n. We show that the cogrowth function of a finitely presented algebra is either bounded or at least logarithmical. We also show that an uniformly recurrent word has at least logarithmical cogrowth.

Soit AkX/I une algèbre associative. Un mot fini sur l’alphabet X est I-réductible si son image dans A est une combinaison linéaire k de mots de longueur lexicographiquement moindre. Une obstruction dans un mot minimal I -réductible. Si le nombre d’obstructions est fini, alors I a une base finie Gröbner, et le mot problème pour l’algèbre est décidable. Une fonction co-croissance est le nombre d’obstructions de longueur n. Nous montrons que la fonction de co-croissance d’une algèbre finement présentée est soit bornée, soit au moins logarithmique. Nous montrons également qu’un mot uniformément récurrent a au moins une co-croissance logarithmique.

Published online:
DOI: 10.5802/crmath.170

Alexei Ya. Kanel-Belov 1; Igor Melnikov 2; Ivan Mitrofanov 3

1 Bar Ilan University, Ramat-Gan, Israel
2 Moscow Institute of Physics and Technology, Dolgoprudny, Russia
3 C.N.R.S., École Normale Superieur, PSL Research University, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     author = {Alexei Ya. Kanel-Belov and Igor Melnikov and Ivan Mitrofanov},
     title = {On cogrowth function of algebras and its logarithmical gap},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {297--303},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {359},
     number = {3},
     year = {2021},
     doi = {10.5802/crmath.170},
     language = {en},
AU  - Alexei Ya. Kanel-Belov
AU  - Igor Melnikov
AU  - Ivan Mitrofanov
TI  - On cogrowth function of algebras and its logarithmical gap
JO  - Comptes Rendus. Mathématique
PY  - 2021
SP  - 297
EP  - 303
VL  - 359
IS  - 3
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.170
LA  - en
ID  - CRMATH_2021__359_3_297_0
ER  - 
%0 Journal Article
%A Alexei Ya. Kanel-Belov
%A Igor Melnikov
%A Ivan Mitrofanov
%T On cogrowth function of algebras and its logarithmical gap
%J Comptes Rendus. Mathématique
%D 2021
%P 297-303
%V 359
%N 3
%I Académie des sciences, Paris
%R 10.5802/crmath.170
%G en
%F CRMATH_2021__359_3_297_0
Alexei Ya. Kanel-Belov; Igor Melnikov; Ivan Mitrofanov. On cogrowth function of algebras and its logarithmical gap. Comptes Rendus. Mathématique, Volume 359 (2021) no. 3, pp. 297-303. doi : 10.5802/crmath.170.

[1] Marie-Pierre Béal; Filippo Mignosi; Antonio Restivo; Marinella Sciortino Forbidden Words in Symbolic Dynamics, Adv. Appl. Math., Volume 25 (2020) no. 2, pp. 163-193 | DOI | MR | Zbl

[2] Alekseĭ Ya. Belov; Vladimir V. Borisenko; Viktor N. Latyshev Monomial algebras, J. Math. Sci., New York, Volume 87 (1997) no. 3, pp. 3463-3575 | DOI | MR | Zbl

[3] George M. Bergman The diamond lemma for ring theory, Adv. Math., Volume 29 (1978) no. 2, pp. 178-218 | DOI | MR | Zbl

[4] Ilya I. Bogdanov; Grigory R. Chelnokov The maximal length of the period of a periodic word defined by restrictions (2013) ( | Zbl

[5] Grigory R. Chelnokov On the number of restrictions defining a periodic sequence, Model and Analysis of Inform. Systems, Volume 14 (2007) no. 2, pp. 12-16 (in Russian)

[6] Ilya Ivanov-Pogodaev; Sergey Malev Finite Gröbner basis algebras with unsolvable nilpotency problem and zero divisors problem, J. Algebra, Volume 508 (2018), pp. 575-588 | DOI | Zbl

[7] Petr A. Lavrov Number of restrictions required for periodic word in the finite alphabet (2012) (

[8] Petr A. Lavrov Minimal number of restrictions defining a periodic word (2014) (

[9] Andrej A. Muchnik; Yu. L. Pritykin; Alexei L. Semenov Sequences close to periodic, Russ. Math. Surv., Volume 64 (2009) no. 5, pp. 805-871 | DOI | Zbl

Cited by Sources:

Comments - Policy