On cogrowth function of algebras and its logarithmical gap

Alexei Ya. Kanel-Belov; Igor Melnikov; Ivan Mitrofanov

doi:10.5802/crmath.170

Algebra

On cogrowth function of algebras and its logarithmical gap

Alexei Ya. Kanel-Belov ¹; Igor Melnikov ²; Ivan Mitrofanov ³

¹ Bar Ilan University, Ramat-Gan, Israel
² Moscow Institute of Physics and Technology, Dolgoprudny, Russia
³ C.N.R.S., École Normale Superieur, PSL Research University, France

Comptes Rendus. Mathématique, Volume 359 (2021) no. 3, pp. 297-303.

Abstract
Résumé

Let $A ≅ k 〈 X 〉 / 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 $\leq 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 $A ≅ k 〈 X 〉 / 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 $\leq 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.

Received: 2020-07-06
Revised: 2020-12-14
Accepted: 2020-12-14
Published online: 2021-04-20

DOI: 10.5802/crmath.170

Author's affiliations:

Alexei Ya. Kanel-Belov ¹; Igor Melnikov ²; Ivan Mitrofanov ³

¹ Bar Ilan University, Ramat-Gan, Israel
² Moscow Institute of Physics and Technology, Dolgoprudny, Russia
³ 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

@article{CRMATH_2021__359_3_297_0,
     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},
}

TY  - JOUR
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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.170/

References
Cited by

[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) (https://arxiv.org/abs/1305.0460) | 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) (https://arxiv.org/abs/1209.0220)

[8] Petr A. Lavrov Minimal number of restrictions defining a periodic word (2014) (https://arxiv.org/abs/1412.5201)

[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