Algorithms for integral solutions of a class of diophantine equations

• Autorzy: Polak A.
• Języki publikacji: EN

Abstrakty

EN

In 1970 a negative solution to the tenth Hilbert problem, concerning the determination of integral solutions of diophantine equations, has been published by Y. W. Matiyasevich (see Matiyasevich, 1970). Despite this result, we can present algorithms to compute integral solutions (roots) for a wide class of quadratic diophantine equations of the form q(x) = d, where q : Zⁿ → Z is a homogeneous quadratic form. We will focus on the roots of one (i.e., d = 1) of quadratic Euler forms of selected posets from Loupias list (see Loupias, 1975). In particular, we will describe the roots of positive definite quadratic forms and the roots of quadratic forms that are principal (see Simson, 2010a). The algorithms and results we present here are successfully used in the representation theory of finite groups and algebras.

Słowa kluczowe

EN

integral quadratic form; unit form; diophantine equations; roots; Euler bilinear form; Euclidean diagrams; mesh quiver; algorithm; Maple

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 2
• Strony: 491--514
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Polak A.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University ul. Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• Adleman, L. and Manders, K. (1976) Diophantine complexity, Proc. 17th IEEE Symposium on Foundations of Computer Science, Proc. IEEE, New York, 81-88.
• Barot, M. and de la Pena, J.A. (1999) The Dynkin type of a non-negative unit form, Expo. Math., 17, 339-348
• Buchmann, J. and Vollmer, U. (2007) Binary Quadratic Forms: An Algorithmic Approach (Algorithms and Computation in Mathematics). Springer, Berlin-Heidelberg.
• Drozdowski, G. and Simson, D. (1978) Remarks on posets of finite representation type, http : //www −users.mat.umk.pl/ simson/Drozdowski-Simson1978.pdf. Wydział Matematyki i Informatyki UMK, Toruń.
• Loupias, M. (1975) Indecomposable representations of finite partially ordered sets. Lecture Notes in Math., 488, Springer-Verlag, Berlin-Heidelberg-New York, 201-209.
• Marczak,M., Polak,A. and Simson,D. (2010) P-critical integral quadratic forms and positive unit forms: An algorithmic approach. Linear Algebra and its Applications, 433, 1873-1888.
• Matiyasevich, Y. (1970) Enumerable sets are Diophantine. Doklady Akademii Nauk SSSR, 191, English translation in Soviet Mathematics Doklady, 11 (2), 279-282.
• Polak, A. and Simson, D. (2010) Peak P-critical Tits forms of one-peak posets, preprint.
• Ringel, C.M. (1984) Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math., 1099, Springer-Verlag, Berlin-Heidelberg-New York-Tokyo.
• Simson, D. (1992) Linear Representations of Partially Ordered Sets and Vectors Space Categories. Algebra, Logic and Applications, 4. Gordon & Breach Science Publishers, Switzerland.
• Simson, D. (1992) Diagramy Coxetera-Dynkina i problemy macierzowe (Coxeter-Dynkin diagrams and matrix problems; in Polish). Instytut Matematyki UMK, Toruń.
• Simson, D. (2004-2009) Pierwiastki funkcjonałów kwadratowych, diagramy Dynkina i zbiory częściowo uporządkowane (Roots of square functionals, Dynkin diagrams and partially ordered sets; in Polish). Wyklad monograficzny, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń.
• Simson, D. (2010a) Mesh geometries of root orbits of integraf quadratic forms. J. Pure Appl. Algebra, 215, 13-34 .
• Simson, D. (2010b) Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets. Linear Algebra and Appl., 433, 699-717.
• Simson, D. (2011) Mesh algorithms for solving principal diophantine equations, Sand-glass tubes and tori of roots. Fundamenta Informaticae, 109, 425-462.
• Zavadskij, A.G. and Shkabara, A.S. (1976) Commutative quivers and matrix algebras of finite type. Preprint IM-76-3, Institute of Mathematics AN USSR, Kiev (in Russian).