Characteristic Sturmian word Created 2026-10-20 Updated 2026-11-05
For an irrational number , the characteristic Sturmian word of slope is the binary sequenceEach term is zero or one because the arguments differ by less than one. This fixes an intercept convention: it is the lower mechanical word with intercept .
For , the beginning is , the Fibonacci word. Like every Sturmian word, it has exactly distinct factors of length . Its relation to continued fractions makes its recursive block structure reflect the partial quotients of its slope.
Claude Brezinski Created 2026-10-18 Updated 2026-11-05
Claude Brezinski works in numerical analysis, particularly extrapolation, Padé approximation, continued fractions, orthogonal polynomials and numerical linear algebra. His research also treats systems of nonlinear equations. These subjects connect different representations of an approximation with ways to accelerate or stabilize a numerical computation.[ref]
Identity source: claude-brezinski.fr/
Portrait of Claude Brezinski
. Complete quotient 2026-10-05
For a simple continued fraction, the complete quotients satisfy , and whenever the denominator is nonzero. Thus .
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 of the square root of nineteen Created 2026-10-14 Updated 2026-10-20
For a quadratic irrational , write its complete quotient as . The recurrence , , computes its continued fraction. For , the successive pairs after the initial quotient are , and then the cycle repeats. They give the displayed period of length six.
A polynomial-time algorithm for integer linear feasibility gives exact rational linear programming optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality localizes the finite optimum to an interval containing a unique rational of bounded denominator; continued fractions recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.
Gauss continued-fraction map Created 2026-10-05 Updated 2026-10-06
Modular symbol Created 2026-10-14 Updated 2026-11-05
A modular symbol is the relative homology class of a path between two modular cusps. Oriented paths satisfy . Continued fractions subdivide rational-endpoint paths into unimodular edges, giving a finite presentation through Manin symbols. The Hecke operators act by finite sums of transformed paths, so their matrices can be computed by rational linear algebra.
Negative continued fraction Created 2026-10-14 Updated 2026-11-05
The finite negative continued fraction isFor , it describes a negative-framed chain of unknots: the diagonal framings are and adjacent linking numbers are one. Repeated slam-dunk moves give rational surgery coefficient . The corresponding chain matrix is negative definite. To check this, the successive determinants of its negative have recurrence , starting with , ; they are positive and increasing, so Sylvester's criterion applies.
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 2001 iii Paper 20 7 Solution Created 2026-10-03 Updated 2026-10-14
A logarithmic form is in fixed choices of logarithms of nonzero algebraic numbers, with integer coefficients. The indispensable condition is . Put and take for a number field of degree containing the arguments. A typical effective estimate iswith an explicitly computable constant. For fixed arguments this is a power-type lower bound . It is fundamentally stronger for applications than a crude norm estimate exponential in .
The basic estimates follow the auxiliary-function pattern already used here, in a multivariable form. Choose a polynomial or an interpolation determinant in powers of the algebraic arguments; impose many derivative or interpolation conditions by Siegel lemma. Analytic extrapolation near the chosen logarithms makes the determinant tiny. Arithmetic denominator and norm estimates prevent a nonzero algebraic determinant from being so small, while a multiplicity or zero estimate ensures the necessary determinant does not vanish identically. Balancing the degree, multiplicity and arithmetic height parameters produces dependence on the individual and only logarithmic dependence on . The nonvanishing argument and the arithmetic arithmetic height control are both necessary parts of this outline.
For practical equations the output is a finite, certified computation. Factor the equation in a number field, record the finitely many ideal and torsion possibilities, and express its factors in fundamental units. At a place where the original equation gives an exponentially small remainder, choose the principal logarithm and include a multiple of for the branch. Compare that upper bound with the effective lower bound to obtain an initial exponent bound. Question 5 shows this for a unit equation, and Question 6 shows why a rational argument of variable arithmetic height can still bound a common power exponent. Zero forms and degenerate families are separated before any estimate is applied.
A concrete two-logarithm example is , with positive exponents. HereThe lower bound and give an effective upper bound for . The exponents are coprime: a common divisor greater than one would factor a difference of two positive integer powers equal to , which is impossible. For large the same upper estimate makes a continued-fraction convergent of , since its error is smaller than . One checks only the finitely many convergents up to the proven bound, with small cases checked directly. Higher-dimensional problems use the LLL algorithm to obtain analogous improvements from the first large bound.
Every numerical logarithm must be evaluated with a certified error interval, so that a proposed reduction really is an inequality and an exact integer check can certify each surviving candidate. Continued fractions or lattice reduction accelerate the search; the prior effective upper bound is what makes the search complete. This explains how linear forms in logarithms of algebraic numbers turn qualitative finiteness into practical Diophantine algorithms, while also outlining the auxiliary machinery behind the estimates.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 40 2 Solution Created 2026-10-03 Updated 2026-10-14
Assume and the integer coefficient bound . There are integers to record. Each signed integer in can be encoded in bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is . This is the bit-input model used for polynomial time; an arithmetic-operation count alone would not suffice.
We first construct a rational feasibility certificate for integer inequalities. Choose a feasible point and an orthant containing it, adding coordinate inequalities of the form or . The intersection is nonempty. Starting at a point of , if the active constraint normals have rank less than , choose a nonzero direction annihilating them. A sufficiently short move in either direction remains feasible, since every inactive constraint has positive slack. At least one direction has a finite endpoint: a nonzero coordinate of can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate , so it is independent of the previously active normals. Their rank strictly increases. In at most moves we obtain a point with independent active constraints.
At that point for an invertible integer matrix . Its rows are original constraint rows or signed coordinate rows, and has entries from or zero. All entries have absolute value at most . By Cramer's rule,where replaces column by . The Hadamard determinant inequality bounds both determinants by . The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by . The orthant argument is needed because itself may contain lines and have no vertex. If is allowed literally, all coefficients and right sides vanish, and is feasible; the printed fraction bound then needs replaced by , since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.
Recording such fractions takes bits. A verifier checks that denominators are nonzero, changes their signs if needed, and verifies all inequalities by exact integer arithmetic after multiplying by positive denominators. The intermediate integers still have polynomial bit length. Thus a yes-instance has a polynomial-size, polynomial-time verifiable witness, and .
For optimization, let be rational with a finite binary encoding; clear its denominators to make it integer, which multiplies the objective by a positive constant and preserves its minimizers. All bit bounds below include the encoding length of . Let and .
A useful refinement of the preceding vertex argument is that if an objective is bounded below, a feasible point can be moved to an orthant vertex without increasing its objective. Choose the annihilating direction to have . If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If , choose either finite endpoint supplied by the orthant. Rank increases as before. There are only finitely many such vertices across the finitely many orthants. Every feasible point therefore has one of these vertices with no larger objective; taking the least vertex value proves that a finite optimum is attained at one of them.
The Cramer representations at this optimum have one common denominator , of magnitude at most . Therefore its objective value has a representation with denominator at most and numerator at most . In particular . No enumeration of orthants or vertices is part of the algorithm; they provide only polynomial-bit bounds.
Here is an exact linear optimization from a feasibility oracle. First call the assumed ellipsoid method feasibility routine on ; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality . A yes answer proves unboundedness below, because any finite optimum would be at least ; an unbounded objective necessarily gives a yes answer. Thus the infeasible, unbounded and finite-optimum cases are distinguished using two feasibility calls.
In the finite case, maintain an infeasible lower threshold and a feasible upper threshold . Bisect the interval, querying each time. After polynomially many calls its length is less than , and lies in the resulting interval. Distinct reduced fractions with positive denominators at most differ by at least , so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint , , where is the denominator of . Thus occurs among the continued-fraction convergents of . Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most in the interval. If , use the final exact convergent. The Euclidean algorithm and all thresholds have polynomial bit length.
Even if the feasibility routine returns only a decision, an optimal point can be recovered without assuming a witness-producing oracle. Add and for all . This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of and setAll vertex coordinates of this fixed convex polytope have denominators at most by the same determinant argument. Minimize , recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for , and so on. Each restriction is an optimal face of the same original bounded convex polytope, so its vertices are original vertices. The single denominator bound therefore works at every step; repeated new precision bounds do not grow exponentially. After steps all coordinates are fixed to a feasible optimizer. There are polynomially many calls on polynomial-length rational instances, converted to integer inequalities by clearing denominators. Consequently linear optimization has a polynomial-time algorithm whenever linear feasibility does, with exact optimal value and optimizer, and correct reports of infeasibility or unboundedness.
Past exam of the mathematics course of the University of Cambridge 2005 ii Paper 4 11H a Solution Created 2026-09-24 Updated 2026-10-14
For the continued-fraction assertion, take the standard Pell equation hypothesis nonsquare. If is a solution with , thenThe convergent criterion for continued fractions therefore makes a convergent to . Write its periodic expansion as , and index convergents by with . The norm-one convergents occur at with even. In particular the fundamental positive solution comes at if is even, and at if it is odd. If is this least norm-one unit, all integer solutions are represented by , .
The abelian group law comes from multiplication of the norm-one expressions:Their field norms multiply, so the result remains a solution. Multiplication also proves associativity and commutativity; the identity is and the inverse of is . Cubing givesThe last form uses .
For completeness, the assertion about all powers follows by dividing any positive unit by the largest power of not exceeding it: the remainder is a norm-one unit in , and minimality forces it to be . Sign changes and inverses give the remaining solutions. If the phrase “nonsquare integer” includes negative , real continued fractions do not apply: has only except for , when also occur. The same multiplication law still works in those finite groups.
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 12F ii Solution Created 2026-09-24 Updated 2026-10-14
Let be the complete quotient. Iterating the fractional-linear formula for a continued fraction givesThe supplied determinant identity and therefore implyThe positive partial quotients ensure increasing denominators tending to infinity; the same determinant identity makes the even and odd convergents nested, giving their common limit . The displayed formula follows by passing to the limit in the finite-tail identity.
An explicit choice is for every . The recurrence gives . For , , so . Consequently andFirst is irrational: if , the nonzero difference from a convergent is at least , contradicting the error bound once . If were algebraic of any fixed degree , the last displayed upper bound would eventually be smaller than for the positive constant in part (i), since . This contradicts the Liouville approximation theorem. Thus this explicit continued fraction is transcendental.
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 2008 ii Paper 4 11H Solution Created 2026-09-24 Updated 2026-10-14
Put and use conventional convergent indexing starting at zero; the same argument covers all the printed positive indices. The continued fraction complete quotients satisfy , . After the first step they exceed one, while their algebraic conjugates lie in . Indeed , and if with , then .
Write , where are integers and . This form follows by rationalization at each step: and , starting from . The two conjugate inequalities giveso . The standard convergent recursions also giveSubstitute the displayed form of and compare rational and irrational coefficients. This yields and . Therefore the small norm residues from square-root continued fractions obeyThe initial convergent satisfies the same relation with the usual . This avoids the insufficient estimate obtained by merely replacing the convergent error with .
For integer factorization, choose a factor base of small primes for which is a quadratic residue, together with to record negative residues; a prime dividing already supplies a factor. Test the small nonzero integers for being B-numbers. Complete factorization over the base records each prime exponent modulo two. Once enough relations are collected, linear algebra over can choose a nonempty subcollection whose exponent sum is even, including the sign. ThenIf , one of or can yield a nontrivial factor. Relations with a noninvertible may already give a factor through its gcd. The small-residue bound makes smoothness more likely; it does not guarantee that any one dependency gives a nontrivial factor.
