Comptes Rendus
Algèbre
On cogrowth function of algebras and its logarithmical gap
[Sur la fonction de co-croissance des algèbres et son écart logarithmique]
Comptes Rendus. Mathématique, Volume 359 (2021) no. 3, pp. 297-303.

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.

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@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/

[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

Cité par Sources :

Commentaires - Politique


Ces articles pourraient vous intéresser

Explicit left orders on free groups extending the lexicographic order on free monoids

Zoran Šunić

C. R. Math (2013)


The critical exponent functions

Dario Corona; Alessandro Della Corte

C. R. Math (2022)


On the triplex substitution – combinatorial properties

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

C. R. Math (2008)