Best approximation of the second kind Created 2026-09-29 Updated 2026-11-05
A reduced fraction is a best approximation of the second kind to a real number if for every competing fraction with . It minimizes the error after multiplication by the denominator; this differs from best rational approximation of the first kind, which minimizes .
For the simple continued fraction of an irrational number, the continued fraction convergents with have this property. The initial convergent needs an exception when the fractional part of exceeds , since then is closer. For example, if , the initial convergent is beaten by . The next convergent is , and the subsequent continued fraction convergents have the usual best-approximation property.
The inverse branch of the th iterate of the Gauss continued-fraction map on a fixed digit cylinder has the displayed form, with continued fraction convergents . Its derivative has absolute value . Since , the maximum-to-minimum derivative ratio is at most four. The density of the Gauss measure changes this ratio by at most a further factor two. The cylinders shrink to irrational points, so this uniform distortion bound and the Lebesgue density theorem prove ergodicity of the map.
Continued fraction Created 2026-09-24 Updated 2026-11-05
A simple continued fraction writes a real number as , with integral and positive integral for . Repeatedly taking the integer part and inverting the remainder constructs the expansion.
For example, . Rational inputs terminate; irrational inputs give infinite expansions. Truncations are continued fraction convergents, whose numerator and denominator satisfy short recurrences and provide particularly effective best rational approximations. The expansion of a quadratic irrational number is eventually periodic, linking these approximations with Pell equations.
Continued fraction convergent Created 2026-09-24 Updated 2026-11-05
The th continued fraction convergent of is its truncation , written in lowest terms with positive denominator. The recurrences are and , initialized by and .
For , the convergents begin . For an infinite simple continued fraction, . Thus the successive convergent denominators quantify the improving accuracy rather than merely recording a symbolic truncation.
Continued-fraction matrix Created 2026-09-24 Updated 2026-11-05
A continued-fraction matrix packages the recurrences for continued fraction convergents into matrix multiplication. Put
If , with , , and , then
For the identity is immediate. Right multiplication by replaces the first column by times the old first column plus the old second column, proving the convergent recurrences by mathematical induction.
Each factor has determinant , so . Any common divisor of and must therefore divide . Thus each continued fraction convergent is a fraction with coprime numerator and denominator.
Convergent denominator Created 2026-10-20 Updated 2026-11-05
For the continued fraction convergent in lowest terms, is its convergent denominator. With and , it satisfies .
For , the first denominators are . Their growth measures the increasing cost of representing a better best rational approximation. The determinant identity proves that neighboring continued fraction convergents are reduced and tightly linked; in particular, their difference has absolute value .
Diophantine approximation Created 2026-09-24 Updated 2026-11-05
Diophantine approximation asks how closely a real or complex quantity can be approximated by rational numbers or algebraic numbers of bounded arithmetic complexity. For a real , one compares with functions of the denominator .
For example, continued fraction convergents to give approximations . A nonzero integer norm of also supplies a lower bound, preventing arbitrarily exceptional accuracy. The Liouville approximation theorem extends this idea to algebraic numbers, while Roth's theorem sharpens the exponent for algebraic irrational inputs. Approximation quality can therefore distinguish algebraic from transcendental behavior, not merely give convenient decimal values.
For with nonsquare positive integer , the solution with , and smallest is the fundamental solution. It generates other positive solutions through powers of and can be found using continued fraction convergents of .
Between consecutive continued fraction convergents, intermediate convergents have the form for . The final value is the next convergent.
Partial quotient of a continued fraction Created 2026-10-20 Updated 2026-11-05
The partial quotients of a simple continued fraction are its integer coefficients: and for . Repeatedly subtract the integer part and invert the positive remainder to obtain the next coefficient.
For , this gives , since . For , it gives . Truncation after gives a continued fraction convergent. A large next partial quotient makes the current convergent particularly accurate because the next reciprocal tail is small.
Introduce , , and . Composition of the Möbius transformations represents a finite continued fraction. Their matrices give
Indeed, multiplying the last factor gives the linear recurrences and , which reproduce the continued fraction convergents of the continued fraction. Each factor has determinant . Taking determinants therefore yields
This identity also proves that the numerator and denominator in the first column are coprime, so no unnoticed cancellation changes the displayed matrix.
Apply the reciprocal-and-integer-part algorithm for the continued fraction. The successive complete quotients after the integer part two are , , , and . Their integer parts are , and taking the next reciprocal repeats the first complete quotient. Therefore
The first four continued fraction convergents are . The last gives . Squaring its unit gives , whose norm is again one. Thus two positive solutions of the Pell equation are
Direct verification gives .
For a probability measure-preserving system, ergodicity means that every measurable set satisfying modulo null sets has measure zero or one. Equivalently, the only invariant functions are almost everywhere constant. The pointwise ergodic theorem states that, for ,
where is the invariant sigma-algebra; on a probability space the convergence also holds in . For an ergodic transformation, the limit is the constant .
For the Gauss continued-fraction map, the Gauss measure is the probability measure
Its density integrates to one and is bounded above and below by positive constants, so it has the same null sets as Lebesgue measure. Apart from countably many endpoints, the inverse branches are , . For a bounded measurable test function , substitution on each branch gives
Thus is a measure-preserving transformation. Its definition at zero and the rational branch endpoints does not affect these identities.
For ergodicity, we give the full shrinking-cylinder argument. A digit cylinder with first partial quotients is an interval , where and is the identity. The continued fraction convergents give
Here after the initial step, and the recurrence makes tend to infinity at least at the Fibonacci rate. Hence the nested cylinders of every irrational point shrink to that point. The bounded distortion of continued-fraction cylinders is uniform: the ratio of the largest to the smallest value of is at most four. Since ranges between and , the density
has maximum-to-minimum ratio at most eight. Consequently every measurable satisfies
The last inequality uses .
Now suppose modulo null sets and . Choose an irrational density point , and let be its successive digit cylinders. The Lebesgue density theorem applies to these intervals even though they need not be centered: an interval of length containing lies in the centered interval of radius , so its relative complement tends to zero. Comparability of the two densities then gives
But invariance gives almost everywhere for each inverse branch of . Pulling the exceptional null sets through is legitimate since has a positive smooth Jacobian on this fixed branch. Thus the distortion estimate with gives
Letting forces . Therefore the Gauss continued-fraction map is ergodic for the Gauss measure.
For an irrational , the successive continued fraction digits satisfy . The event that a digit equals two is the interval , up to null endpoints. Apply the pointwise ergodic theorem to its indicator:
This holds for almost every with respect to both the Gauss measure and Lebesgue measure, since they have the same null sets.
The matrix recurrence gives and . Successive continued fraction convergents bracket , hence
The infinite continued fraction is irrational: if were rational, a distinct convergent would be at distance at least , contradicting the first bound once . If were rational, this irrational would have degree two. The Liouville approximation theorem would then give . Comparing with the displayed bound would force for every , contrary to the unbounded coefficients. Thus is irrational, by the unbounded continued-fraction coefficients exclude quadratic irrationality argument.
The continued fraction starts , since has integer part . Its next continued fraction convergent is . Direct substitution gives
Put . Every positive solution satisfies
After reducing , we still have . Here is the continued fraction convergent criterion with its proof. If is reduced and obeys this inequality, it is a strict best approximation of the second kind: for any different with , the assumption would give
a contradiction. Choose consecutive continued fraction convergents with . Their determinant is , their errors alternate in sign, and every integer pair is uniquely . For , either , or have opposite signs: positive would make , negative make , and is impossible. Opposite signs make and have the same sign, so . If , reduction gives the th convergent itself. Thus a strict best approximation must be a convergent. The determinant and alternating-error facts follow immediately from the recurrence , and the positive continued-fraction tail formula. Therefore the reduced ratio is a convergent of . Without assuming , the unreduced pair may be a common multiple of the convergent's numerator and denominator; for example for reduces to .
For a simple continued fraction, define
Multiplying the matrices gives
Their determinants also give . If the infinite tail is , the same formula implies
The denominators of these continued fraction convergents tend to infinity, since . Hence they converge to .
The square-root algorithm for the periodic continued fraction of a quadratic irrational, using , and , gives
The first four continued fraction convergents are . Direct substitution gives positive solutions to the requested Pell-type equations:
Let . In the Shor algorithm, first use classical arithmetic to deal with even and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power , with , already gives a nontrivial factor . We may therefore consider an odd composite with at least two distinct prime factors.
Choose uniformly from and compute its greatest common divisor with using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise is a unit, and the remaining task is quantum order finding. Set
Prepare a uniform quantum superposition in a -qubit register and use quantum modular exponentiation in a second register to obtain
Repeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in . Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining . Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of .
Here is a quantitative quantum Fourier sampling bound for order finding. If , multiplication by cycles its orbit states. The Fourier eigenstates of that cycle have eigenvalues , and the initial state has squared overlap with each, for . Therefore
Conditioned on a particular eigenphase , its nearest integer outcome obeys and has probability at least . Indeed the absolute amplitude is , where . For , the numerator is at least and the denominator at most ; the limiting value at is one.
If , the fraction is reduced, and gives
Use continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying are continued fraction convergents of . For an input rational of digits, their candidates can be enumerated classically in time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding . A zero measurement is treated as a failed order-finding sample.
For each remaining even candidate denominator , compute by repeated squaring, and try and . Return only a divisor with ; otherwise repeat the quantum sample or choose another . This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).
Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least : its true multiplicative order is even and . To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is , the probability of the largest possible value of is , and the probability of any specified smaller value is at most . Failure requires all components to have the same : either all zero, making odd, or all the same positive value, making the halfway power in every component. Conditioning on one component, the chance another component matches it is at most , so total failure is at most .
Second, the fraction of phase numerators coprime to is , where is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are , then and . The totient product formula therefore gives
Thus for a good , the probability of sampling a coprime phase numerator with the required accuracy is at least . This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in .
The reduction is therefore polynomial in the bit length:
A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.
Set and define the continued fraction convergents by
The recurrence reverses the sign of , whose initial value at is . Hence . Every common divisor of divides this number, proving .
The continued fraction convergents of begin . The last one yields
Changing either sign gives another valid integer solution.