On efficient approximation of quadratic irrationals

Technical Summary: Efficient Approximation of Quadratic Irrationals

Problem Statement
The paper addresses the computational challenge of efficiently calculating the convergents ($p_n/q_n$) of the simple continued fraction expansion for quadratic irrationals. While Lagrange's theorem guarantees that such expansions are eventually periodic, computing specific convergents for large indices $n$ using standard iterative methods requires $O(n)$ operations. The authors seek algorithms that reduce this complexity to $O(\log n)$, particularly in settings where Galois' refinement of Lagrange's theorem applies (specifically for square roots of rational numbers and certain complex numbers).

Methodology and Theoretical Framework
The authors establish a deep connection between the sequence of convergents of quadratic irrationals and various families of Chebyshev polynomials.

1. Polynomial Definitions: The paper introduces and relates several polynomial sequences:

   • Standard Chebyshev polynomials of the first ($T_k$) and second ($U_k$) kinds.
   • Dilation variants ($\tilde{T}_k, \tilde{U}_k$) satisfying $T_{k+2} = xT_{k+1} - T_k$.
   • Sign-changed variants ($\hat{T}_k, \hat{U}_k$) satisfying $T_{k+2} = xT_{k+1} + T_k$.
   • "Signed" Chebyshev polynomials ($T^l_k, U^l_k$) which depend on the parity of the period length $l$, satisfying recurrences of the form $T^l_{k+2} = 2xT^l_{k+1} - (-1)^l T^l_k$.

2. Matrix Representation: The authors utilize the matrix representation of continued fractions, where the product of matrices $\begin{pmatrix} c_i & 1 \\ 1 & 0 \end{pmatrix}$ yields the convergent matrix $\Psi_n$. They leverage the Cayley–Hamilton theorem to show that the trace of powers of these matrices corresponds to the defined Chebyshev polynomials.

3. Decimation and Periodicity: For quadratic irrationals with a purely periodic or symmetric period structure (specifically square roots of rationals, where the period is of the form $[c_0, c_1, \dots, c_1, 2c_0]$), the authors prove that specific decimations of the convergent sequence (indices $kl-1$) are generated by these signed Chebyshev polynomials.

Key Contributions and Algorithms
The paper provides four distinct algorithms to compute the convergent matrix $\Psi_m$ for large $m$, all achieving $O(\log m)$ complexity.

• Theoretical Result (Theorem 3.1): A linear recurrence relation is derived for the convergent matrices separated by multiples of the period $l$. This relation expresses $\Psi_{n+2ikl}$ in terms of $\Psi_{n+2ikl}$ and $\Psi_n$ using coefficients $t_{2ik}$ derived from signed Chebyshev polynomials.
• Algorithm 3.1 (Binary, Additive): Uses the binary representation of the period multiplier. It relies on the linear recurrence relation (3.1) and requires matrix multiplications plus linear combinations of matrices. The authors note that in the worst case, the number of linear combinations grows quadratically with $\log h$.
• Algorithm 3.2 (Nested Binary, Additive): Uses a nested binary representation (Horner's method style) to minimize the number of linear combinations. This is presented as the preferred additive method, as it reduces the computational cost of linear combinations compared to Algorithm 3.1.
• Algorithm 3.3: A supporting algorithm to efficiently compute the necessary Chebyshev coefficients ($t_k$) required by the additive methods.
• Algorithms 3.4 and 3.5 (Multiplicative): These methods rely solely on matrix squaring (multiplication) without computing intermediate coefficients. While they avoid coefficient determination, they require more matrix multiplications ($n_q + q + 3$) than the additive variants.

Results on Householder Methods
A significant theoretical contribution is the demonstration that these decimated sequences of convergents can be generated by iterating Householder's method.

• Theorem 5.1: Applying the Householder method of order $d$ to the $(l-1)$-th convergent of $\sqrt{N}$ yields the $(kl-1)$-th convergent, where $k = d+1$.
• Specific Cases:
  • $d=1$ (Newton's method/Babylonian method) yields the $2l-1$-th convergent.
  • $d=2$ (Halley's method) yields the $3l-1$-th convergent.
• This establishes that the Householder iteration, when applied to quadratic irrationals with the specific periodic structure, acts as a "jump" operator that skips directly to specific terms in the continued fraction sequence.

Significance and Claims
The paper claims to provide "efficient algorithms" for computing convergents of quadratic irrationals, specifically optimizing for settings where Galois' theorem holds.

• Efficiency: The primary significance is the reduction of computational complexity from linear to logarithmic with respect to the index of the convergent.
• Unification: The work unifies the theory of continued fractions, Chebyshev polynomials, and iterative root-finding methods (Householder). It demonstrates that the "signed Chebyshev sequences" are not merely mathematical curiosities but are intrinsic to the structure of quadratic irrational approximations.
• Generality: While focused on square roots of rational numbers (where the period is symmetric), the authors note that the algorithms (3.1–3.5) remain applicable to complex numbers and other quadratic irrationals even when the strict symmetric form of the period (1.4) does not hold, provided the period length $l$ is known.

The authors do not propose new experimental applications or future research directions beyond the mathematical framework presented, maintaining a focus on the theoretical derivation and algorithmic implementation of these efficient computation methods.