Analysis of PSLQ, an integer relation finding algorithm 论文

摘要

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper K"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbb {K}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be either the real, complex, or quaternion number system and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper O left-parenthesis double-struck upper K right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">O</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbb {O}}({\mathbb {K}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the corresponding integers. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x equals left-parenthesis x 1 comma ellipsis comma x Subscript n Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">x = (x_{1}, \dots , x_{n})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a vector in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper K Superscript n"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">{\mathbb {K}}^{n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The vector <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has an integer relation if there exists a vector <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m equals left-parenthesis m 1 comma ellipsis comma m Subscript n Baseline right-parenthesis element-of double-struck upper O left-parenthesis double-struck upper K right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ∈ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">O</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> </mml:mrow> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">m = (m_{1}, \dots , m_{n}) \in {\mathbb {O}}({\mathbb {K}})^{n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m not-equals 0"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo> ≠ </mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">m \ne 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m 1 x 1 plus m 2 x 2 plus ellipsis plus m Subscript n Baseline x Subscript n Baseline equals 0"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>m</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:msub> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>m</mml:mi>