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. PutIf , with , , and , thenFor 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.
Fundamental solution of a Pell equation 2026-10-20
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 .
Intermediate continued fraction convergent 2026-10-20
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.
Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 3 2G Solution Created 2026-09-24 Updated 2026-10-14
Introduce , , and . Composition of the Möbius transformations represents a finite continued fraction. Their matrices giveIndeed, 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 yieldsThis identity also proves that the numerator and denominator in the first column are coprime, so no unnoticed cancellation changes the displayed matrix.
Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 3 1F Solution Created 2026-09-24 Updated 2026-10-14
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. ThereforeThe 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 areDirect verification gives .
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 30 2 Solution Created 2026-10-03 Updated 2026-10-14
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 measureIts 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 givesThus 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 giveHere 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 densityhas maximum-to-minimum ratio at most eight. Consequently every measurable satisfiesThe 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 givesBut 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 givesLetting 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.
Past exam of the mathematics course of the University of Cambridge 2008 ii Paper 3 12F b Solution Created 2026-09-24 Updated 2026-10-14
The matrix recurrence gives and . Successive continued fraction convergents bracket , henceThe 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.
Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 3 1G ii Solution Created 2026-09-24 Updated 2026-10-14
The continued fraction starts , since has integer part . Its next continued fraction convergent is . Direct substitution gives
Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 3 1G i Solution 2026-10-14
Put . Every positive solution satisfiesAfter 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 givea 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 .
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 3 9H Solution Created 2026-09-24 Updated 2026-10-06
For a simple continued fraction, defineMultiplying the matrices givesTheir determinants also give . If the infinite tail is , the same formula impliesThe 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 , givesThe first four continued fraction convergents are . Direct substitution gives positive solutions to the requested Pell-type equations:
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 1 ii Solution Created 2026-10-03 Updated 2026-10-06
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. SetPrepare a uniform quantum superposition in a -qubit register and use quantum modular exponentiation in a second register to obtainRepeated 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 . ThereforeConditioned 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 givesUse 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 givesThus 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.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 10G a Solution Created 2026-09-24 Updated 2026-10-05
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 10G d Solution Created 2026-09-24 Updated 2026-10-05
The continued fraction convergents of begin . The last one yieldsChanging either sign gives another valid integer solution.