A mesh algorithm for principal quadratic forms

• 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, was published by Y. W. Matiyasevich. Despite this result, we can present algorithms to compute integral solutions (roots) to a wide class of quadratic diophantine equations of the form q(x) = d, where q : Z is a homogeneous quadratic form. We will focus on the roots of one (i.e., d = 1) of quadratic unit forms (q11 = ... = qnn = 1). In particular, we will describe the set of roots Rq of positive definite quadratic forms and the set of roots of quadratic forms that are principal. The algorithms and results presented here are successfully used in the representation theory of finite groups and algebras. If q is principal (q is positive semi-definite and Ker q={v ∈ Zn; q(v) = 0}= Z · h) then |Rq| = ∞. For a given unit quadratic form q (or its bigraph), which is positive semi-definite or is principal, we present an algorithm which aligns roots Rq in a Φ-mesh. If q is principal (|Rq| is less than ∞), then our algorithm produces consecutive roots in Rq from finite subset of Rq, determined in an initial step of the algorithm.

Słowa kluczowe

EN

mesh algorithm; quadratic form; quadratic diophantine equation

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2011
• Tom: Vol. 11, no. 1
• Strony: 23--31
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Polak A.

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

Bibliografia

• [1] Matiyasevich Y., Enumerable sets are Diophantine, Doklady Akademii Nauk ZSSR (1970): 279.
• [2] Adleman L. and Manders K., Diophantine complexity (Proc. 17th IEEE Symposium on Foundations of Computer Science) Proc. IEEE (1976): 81.
• [3] Simson D., Linear Representations of Partially Ordered Sets and Vectors Space Categories, Algebra, Logic and Applications 4 (1992).
• [4] Simson D., Integral bilinear forms, Coxeter transformations and Coxeter polynomias of finite posets, Linear Algebra and its Applications (2010); doi:10.1016/j.laa.2010.03.041.
• [5] Simson D., Mesh algorithm for solving principal diophantine equations, preprint (2009).
• [6] Marczak G., Polak A., Simson D., P-critical integral quadratic forms and positive unit forms: An algorithmic approach, Linear Algebra and its Applications (2010); doi:10.1016/j.laa.2010.06.052.
• [7] Simson D., Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra (2010); doi:10.1016/j.jpaa.2010.02.029.