chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2016-17-3-18-27cheb-255Research ArticleСтатьиArticleТЕОРЕМА О ПЛОЩАДИ ДИСКОВОЙ ДИАГРАММЫ НАД С(3)-Т(6)-ГРУППОЙTHE AREA THEOREM FOR THE DISC DIAGRAM OVER С(3)-Т(6)-GROUPБезверхнийН. В.BezverkhniyN. V.

доктор физико-математических наук, профессор, профессор

doctor of physical and mathematical sciences, professor, professor

Vnbezv@rambler.ruТульский государственный педагогический университета им. Л. Н. ТолстогоРоссияTula State L.N. Tolstoy Pedagogical UniversityRussian Federation2016111220161731827Copyright © Безверхний Н.В., 20162016Безверхний Н.В.Bezverkhniy N.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/255

Геометрические методы широко используются в комбинаторной теории групп. Теория групп с малыми сокращениями эффективно использует метод групповых диаграмм. Это позволяет решать, в частности, различные алгоритмические проблемы. Одной из таких проблем является проблема степенной сопряжённости. Будучи решённой в классе групп с условиями малого сокращения C(6)-T(3), она остаётся открытой в близком классе C(3)-T(6)-групп.

В данной статье исследуется структура односвязных диаграмм над C(3)-T(6)-группами и указывается, как это исследование может быть использовано при решении проблемы степенной сопряжённости.

Основным результатом данной статьи является доказательство теоремы о нижней оценке площади дисковой диаграммы на группой с условиями C(3)-T(6). Известно, что для групп с условиями C(p)-T(q) при \((p,q)\in \{(3,6), (4,4), (6,3)\}\), являющихся автоматными, изопериметрическое неравенство является квадратичным. То же самое утверждается в известной в теории групп с малыми сокращениями теореме о площади. Оба утверждения ограничивают сверху площадь односвязной приведённой диаграммы в рассматриваемом классе групп квадратичной функцией длины границы.

В данной статье доказано, что нижняя граница для площади диаграммы указанного типа тоже является квадратичной функцией длины границы. Важность этого результата видна с точки зрения оценки сложности алгоритма, решающего проблему равенства слов. Он оказывается не менее, чем квадратичной сложности от длины сравниваемых слов.

Geometric methods are widely used in combinatorial group theory. The theory of small cancellation groups use the diagram method. In particular, it allows to approach various algorithmic problems. One of them is the power conjugacy problem. It is already solved for groups with a presentation satisfying the small cancellation conditions C(3) and T(6). However, it remains open for a similar class of groups, having a presentation satisfying the small cancellation conditions C(3) and T(3).

In this paper we investigate the structure of connected diagrams over presentations satisfying the small cancellation conditions C(3) and T(3) and we indicate how our results may be possible used in the power conjugacy problem.

The main result of this article is the proof of the theorem about lower bound on square of the reduced diagram on the group with small cancellation conditions C(3)-T(6). It is known that for groups with conditions C(p)-T(q) with \((p,q)\in \{(3,6), (4,4), (6,3)\}\), being automatic, isoperimetric inequality is quadratic. The same stated in well-known in small cancellation theory theorem of the square. Both statements restrict the area of the simply connected diagrams in the considered class of groups by the quadratic function of the length of the boundary.

In this article it is proved that the lower bound for the area of the diagram of the specified type also is a quadratic function of the length of the border. The importance of this result is visible from the point of view of evaluation of complexity of the algorithm solves the word problem. It is not less than quadratic complexity of the length of the compared words.

картадиаграммадуальная картадэновская областьполосакольцевая диаграммаусловия малого сокращенияопределяющее соотношениеобразующиеmapdiagramdual mapdehn regionbandring diagramsmall cancellation conditiondefining relationgeneratorsReferencesLindon R., Schupp P., 1980, "Kombinatorial group theory". М.: Мir.Lindon R., Schupp P., 1980, "Kombinatorial group theory". М.: Мir.Gersten S. M., Short H., 1990, "Small cancellation theory and automatic groups". Inventiones mathematicae 102, pp. 305–334.Gersten S. M., Short H., 1990, "Small cancellation theory and automatic groups". Inventiones mathematicae 102, pp. 305–334.Bezverkhniy N. V., 1999, "The solvability of the membership problem into the cyclic subgroup of C(6)-group". Fundamentalnaya i prikladnaya matematika, v. 5, N 1, pp. 39–46.Bezverkhniy N. V., 1999, "The solvability of the membership problem into the cyclic subgroup of C(6)-group". Fundamentalnaya i prikladnaya matematika, v. 5, N 1, pp. 39–46.Parshikova E. V., 2001, "The solvability of the weak power conjugacy problem inParshikova E. V., 2001, "The solvability of the weak power conjugacy problem in С(4)-Т(4)-group". Algoritmicheskie problemi teorii grupp i polugrupp. Publishing house of the Tula state pedagogical University, pp. 179–185.Bezverkhniy V. N., 1994, "The normalizers of elements of C(p)-T(q)-group". Algoritmicheskie problemi teorii grupp i polugrupp. Publishing house of the Tula state pedagogical University, с.4–58.Bezverkhniy V. N., 1994, "The normalizers of elements of C(p)-T(q)-group". Algoritmicheskie problemi teorii grupp i polugrupp. Publishing house of the Tula state pedagogical University, с.4–58.Bezverkhniy N. V., 2012, "The solvability of the weak power conjugacy problem in C(3)-T(6)-group". Diskretnaya matematika., v. 24, issue 4, pp. 27–46.Bezverkhniy N. V., 2012, "The solvability of the weak power conjugacy problem in C(3)-T(6)-group". Diskretnaya matematika., v. 24, issue 4, pp. 27–46.Bezverkhniy N. V., 2010, "Normal forms for the elements of infinite order in C(3)-T(6)-groups". Izvestiya Tulskogo gosudarstvennogo universiteta, issue 1, pp. 6-25.Bezverkhniy N. V., 2010, "Normal forms for the elements of infinite order in C(3)-T(6)-groups". Izvestiya Tulskogo gosudarstvennogo universiteta, issue 1, pp. 6-25.Magnus W., Karrass A., Solitar D., 1965, "Combinatorial group theory". Springer-Verlag Berlin Heidelberg New York.Magnus W., Karrass A., Solitar D., 1965, "Combinatorial group theory". Springer-Verlag Berlin Heidelberg New York.Ol’shanskii, A. Yu., 1991, "Geometry of Defining Relations in Groups". Kluwer Academic Publishers Group, Dordrecht.Ol’shanskii, A. Yu., 1991, "Geometry of Defining Relations in Groups". Kluwer Academic Publishers Group, Dordrecht.Novikov P. S., 1955, "On algorithmic unsolvability of the word problem in the group theory". Trudi Matematicheskogo instituta AN SSSR, v. 44. pp. 1–444.Novikov P. S., 1955, "On algorithmic unsolvability of the word problem in the group theory". Trudi Matematicheskogo instituta AN SSSR, v. 44. pp. 1–444.Kapovich I., may 1997, "Small cancellation groups and translation numbers". Transactions of the American Mathematical Society, V. 349, N 5, pp. 1851 — 1875.Kapovich I., may 1997, "Small cancellation groups and translation numbers". Transactions of the American Mathematical Society, V. 349, N 5, pp. 1851 — 1875.Gluhov М. М., 2010, "The analysis of some publickey criptosistems using nonabelian groups". Matematicheskie voprosi kriptografii., v.1, № 4, pp. 5–22.Gluhov М. М., 2010, "The analysis of some publickey criptosistems using nonabelian groups". Matematicheskie voprosi kriptografii., v.1, № 4, pp. 5–22.Koo K. H., Lee S. J., Cheon J. H., Han J.W., Kang J., Park C., 2000, "New publickey criptosistem using braide groups". CRIPTO 2000, Lect. Notes Comput Sci., v. 1880, pp. 166–183.Koo K. H., Lee S. J., Cheon J. H., Han J.W., Kang J., Park C., 2000, "New publickey criptosistem using braide groups". CRIPTO 2000, Lect. Notes Comput Sci., v. 1880, pp. 166–183.Paeng S. H., Ha K. C., Kim J. H., Chee S., Park C., 2001, "New public key criptosistem using finite nonabelian groups". CRIPTO 2001, Lect. Notes Comput. Sci., v. 2139, pp. 470–485.Paeng S. H., Ha K. C., Kim J. H., Chee S., Park C., 2001, "New public key criptosistem using finite nonabelian groups". CRIPTO 2001, Lect. Notes Comput. Sci., v. 2139, pp. 470–485.Bogley W. A., Pride S. J., 1992, "Aspherical relative presentations". Pros. of the Edinburg Mathematical Society, v. 35, pp. 1–39.Bogley W. A., Pride S. J., 1992, "Aspherical relative presentations". Pros. of the Edinburg Mathematical Society, v. 35, pp. 1–39.

The authors declare that there are no conflicts of interest present.