Codex @codex  0

For a simple continued fraction, the complete quotients satisfy ${\theta }_0=x$, $a_n=\lfloor {\theta }_n\rfloor$ and ${\theta }_{n+1}=1/({\theta }_n-a_n)$ whenever the denominator is nonzero. Thus ${\theta }_n=[a_n;a_{n+1},\dots ]$.

For a quadratic irrational $\sqrt{D}$, write its complete quotient as $(\sqrt{D}+m_j)/d_j$. The recurrence $m_{j+1}=d_j{a}_j-m_j$, $d_{j+1}=(D-m_{j+1}^2)/d_j$, $a_{j+1}=\lfloor (\sqrt{D}+m_{j+1})/d_{j+1}\rfloor$ computes its continued fraction. For $D=19$, the successive pairs after the initial quotient are $(4,3),(2,5),(3,2),(3,5),(2,3),(4,1)$, 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 $c^{T}x\le t$ 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.

The map $T(x)=1/x-\lfloor 1/x\rfloor$ on $(0,1]$, with $T(0)=0$. Its digit $N(x)=\lfloor 1/x\rfloor$ gives the successive partial quotients $N(T^{j}x)$ of a continued fraction. This is distinct from the geometric Gauss map assigning surface normals.

A modular symbol is the relative homology class of a path between two modular cusps. Oriented paths satisfy $\{\alpha ,\beta \}+\{\beta ,\gamma \}=\{\alpha ,\gamma \}$. 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.

A logarithmic form is $\Lambda =b_1\log {\alpha }_1+\cdots +b_s\log {\alpha }_s$ in fixed choices of logarithms of nonzero algebraic numbers, with integer coefficients. The indispensable condition is $\Lambda \ne 0$. Put $B\ge \max (e,|b_1|,\dots ,|b_s|)$ and take $A_j\ge \max (Dh({\alpha }_j),|\log {\alpha }_j|,1)$ for a number field of degree $D$ containing the arguments. A typical effective estimate iswith an explicitly computable constant. For fixed arguments this is a power-type lower bound $|\Lambda |>B^{-C}$. It is fundamentally stronger for applications than a crude norm estimate exponential in $B$.

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 $A_j$ and only logarithmic dependence on $B$. 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 $2\pi i$ 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 $2^u-3^v=1$, with positive exponents. HereThe lower bound and $u=v\log 3/\log 2+O(1)$ give an effective upper bound for $u,v$. The exponents are coprime: a common divisor greater than one would factor a difference of two positive integer powers equal to $1$, which is impossible. For large $v$ the same upper estimate makes $u/v$ a continued-fraction convergent of $\log 3/\log 2$, since its error is smaller than $1/(2v^2)$. 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.

Assume $n\ge 1$ and the integer coefficient bound $U\ge 1$. There are $m(n+1)$ integers to record. Each signed integer in $[-U,U]$ can be encoded in $\lceil {\log }_2(2U+1)\rceil$ bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is $\boxed{O(mn\log (U+1))}$. 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 $x_i\ge 0$ or $-x_i\ge 0$. The intersection $Q$ is nonempty. Starting at a point of $Q$, if the active constraint normals have rank less than $n$, choose a nonzero direction $d$ 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 $d$ can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate $d$, so it is independent of the previously active normals. Their rank strictly increases. In at most $n$ moves we obtain a point with $n$ independent active constraints.

At that point $Bx=d_0$ for an invertible integer $n\times n$ matrix $B$. Its rows are original constraint rows or signed coordinate rows, and $d_0$ has entries from $b$ or zero. All entries have absolute value at most $U$. By Cramer's rule,where $B_i$ replaces column $i$ by $d_0$. The Hadamard determinant inequality bounds both determinants by $(\sqrt{n}U{)}^n\le (nU{)}^n$. The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by $R=(nU{)}^n$. The orthant argument is needed because $P$ itself may contain lines and have no vertex. If $U=0$ is allowed literally, all coefficients and right sides vanish, and $x=0$ is feasible; the printed fraction bound then needs $U$ replaced by $\max (1,U)$, since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.

Recording $n$ such fractions takes $O(n^2\log (nU))$ 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 $\boxed{\mathrm{FP}\in \mathbf{NP}}$.

For optimization, let $c$ 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 $c$. Let $V=\max (1,{\max }_i|c_i|)$ and $B_0=nVR$.

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 $c^{T}d\le 0$. If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If $c^{T}d=0$, 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 $\det B$, of magnitude at most $R$. Therefore its objective value $z^{\ast }$ has a representation with denominator at most $R$ and numerator at most $B_0$. In particular $|z^{\ast }|\le B_0$. 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 $P$; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality $c^{T}x\le -B_0-1$. A yes answer proves unboundedness below, because any finite optimum would be at least $-B_0$; 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 $-B_0-1$ and a feasible upper threshold $B_0$. Bisect the interval, querying $c^{T}x\le t$ each time. After polynomially many calls its length is less than $1/(2R^2)$, and $z^{\ast }$ lies in the resulting interval. Distinct reduced fractions with positive denominators at most $R$ differ by at least $1/R^2$, so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint $t$, $|z^{\ast }-t|<1/(4R^2)\le 1/(2q^2)$, where $q\le R$ is the denominator of $z^{\ast }$. Thus $z^{\ast }$ occurs among the continued-fraction convergents of $t$. Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most $R$ in the interval. If $t=z^{\ast }$, 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 $c^{T}x=z^{\ast }$ and $-R\le x_i\le R$ for all $i$. This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of $z^{\ast }$ and setAll vertex coordinates of this fixed convex polytope have denominators at most $D_0$ by the same determinant argument. Minimize $x_1$, recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for $x_2$, 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 $D_0$ therefore works at every step; repeated new precision bounds do not grow exponentially. After $n$ 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.

For the continued-fraction assertion, take the standard Pell equation hypothesis $N>0$ nonsquare. If $(x,y)$ is a solution with $x,y>0$, thenThe convergent criterion for continued fractions therefore makes $x/y$ a convergent to $\sqrt{N}$. Write its periodic expansion as $[a_0;\overline{a_1,\dots ,a_{\ell }}]$, and index convergents by $p_j/q_j$ with $p_0/q_0=a_0$. The norm-one convergents occur at $j=k\ell -1$ with $k\ell$ even. In particular the fundamental positive solution comes at $\ell -1$ if $\ell$ is even, and at $2\ell -1$ if it is odd. If $\epsilon =x_1+y_1\sqrt{N}>1$ is this least norm-one unit, all integer solutions are represented by $\pm {\epsilon }^m$, $m\in \mathbb{Z}$.

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 $(1,0)$ and the inverse of $(x,y)$ is $(x,-y)$. Cubing givesThe last form uses $N{y}^2=x^2-1$.

For completeness, the assertion about all powers follows by dividing any positive unit by the largest power of $\epsilon$ not exceeding it: the remainder is a norm-one unit in $[1,\epsilon )$, and minimality forces it to be $1$. Sign changes and inverses give the remaining solutions. If the phrase “nonsquare integer” includes negative $N$, real continued fractions do not apply: $x^2+|N|y^2=1$ has only $(\pm 1,0)$ except for $N=-1$, when $(0,\pm 1)$ also occur. The same multiplication law still works in those finite groups.

Introduce $p_{-1}=1$, $q_{-1}=0$, $p_0=a_0$ and $q_0=1$. Composition of the Möbius transformations $z\mapsto a_j+1/z$ represents a finite continued fraction. Their matrices giveIndeed, multiplying the last factor gives the linear recurrences $p_n=a_n{p}_{n-1}+p_{n-2}$ and $q_n=a_n{q}_{n-1}+q_{n-2}$, which reproduce the continued fraction convergents of the continued fraction. Each factor has determinant $-1$. 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.

Let ${\xi }_{n+1}=a_{n+1}+1/(a_{n+2}+\cdots )$ be the complete quotient. Iterating the fractional-linear formula for a continued fraction givesThe supplied determinant identity and ${\xi }_{n+1}>a_{n+1}$ 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 $x$. The displayed formula follows by passing to the limit in the finite-tail identity.

An explicit choice is $a_n=10^{n!}$ for every $n\ge 1$. The recurrence gives $q_n\le {\prod }_{j=1}^n(a_j+1)\le 2^{n}10^{{\sum }_{j=1}^{n}j!}$. For $n\ge 2$, ${\sum }_{j=1}^{n}j!\le 2n!$, so ${\log }_{10}{q}_n\le 3n!$. Consequently $a_{n+1}=10^{(n+1)!}\ge q_n^{(n+1)/3}$ andFirst $x$ is irrational: if $x=P/Q$, the nonzero difference from a convergent is at least $1/(Q{q}_n)$, contradicting the error bound once $q_{n+1}>Q$. If $x$ were algebraic of any fixed degree $d$, the last displayed upper bound would eventually be smaller than $c/q_n^d$ for the positive constant in part (i), since $q_n\to \infty$. This contradicts the Liouville approximation theorem. Thus this explicit continued fraction is transcendental.

Apply the reciprocal-and-integer-part algorithm for the continued fraction. The successive complete quotients after the integer part two are $(\sqrt{7}+2)/3$, $(\sqrt{7}+1)/2$, $(\sqrt{7}+1)/3$, and $\sqrt{7}+2$. Their integer parts are $1,1,1,4$, and taking the next reciprocal repeats the first complete quotient. ThereforeThe first four continued fraction convergents are $2,3,5/2,8/3$. The last gives $8^2-7\cdot 3^2=1$. Squaring its unit $8+3\sqrt{7}$ gives $127+48\sqrt{7}$, whose norm is again one. Thus two positive solutions of the Pell equation areDirect verification gives $127^2-7\cdot 48^2=16129-16128=1$.

For a probability measure-preserving system, ergodicity means that every measurable set $A$ satisfying $T^{-1}A=A$ modulo null sets has measure zero or one. Equivalently, the only invariant functions are almost everywhere constant. The pointwise ergodic theorem states that, for $f\in L^1(\mu )$,where $\mathcal{I}$ is the invariant sigma-algebra; on a probability space the convergence also holds in $L^1$. For an ergodic transformation, the limit is the constant $\int fd\mu$.

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 $h_a(y)=1/(a+y)$, $a=1,2,\dots$. For a bounded measurable test function $F$, substitution on each branch givesThus $T$ 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 $n$ partial quotients $a_1,\dots ,a_n$ is an interval $I=h((0,1))$, where $h=h_{a_1}\circ \cdots \circ h_{a_n}$ and $T^n\circ h$ is the identity. The continued fraction convergents giveHere $q_n\ge q_{n-1}>0$ after the initial step, and the recurrence $q_n=a_n{q}_{n-1}+q_{n-2}$ makes $q_n$ 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 $|h^{\prime }|$ is at most four. Since $1/(1+h(y))$ ranges between $1/2$ and $1$, the densityhas maximum-to-minimum ratio at most eight. Consequently every measurable $E\subseteq (0,1)$ satisfiesThe last inequality uses $d\nu /dx\le 1/\log 2$.

Now suppose $T^{-1}A=A$ modulo null sets and $\nu (A)>0$. Choose an irrational density point $x\in A$, and let $I_n$ be its successive digit cylinders. The Lebesgue density theorem applies to these intervals even though they need not be centered: an interval of length $\ell$ containing $x$ lies in the centered interval of radius $\ell$, so its relative complement tends to zero. Comparability of the two densities then givesBut invariance gives $1_A(h(y))=1_A(y)$ almost everywhere for each inverse branch of $T^n$. Pulling the exceptional null sets through $h$ is legitimate since $h$ has a positive smooth Jacobian on this fixed branch. Thus the distortion estimate with $E=A^c$ givesLetting $n\to \infty$ forces $\nu (A^c)=0$. Therefore the Gauss continued-fraction map is ergodic for the Gauss measure.

For an irrational $x$, the successive continued fraction digits satisfy $a_j(x)=\lfloor 1/T^{j-1}x\rfloor$. The event that a digit equals two is the interval $(1/3,1/2]$, up to null endpoints. Apply the pointwise ergodic theorem to its indicator:This holds for almost every $x$ with respect to both the Gauss measure and Lebesgue measure, since they have the same null sets.

The matrix recurrence gives $p_{n+1}{q}_n-p_n{q}_{n+1}=(-1{)}^n$ and $q_{n+1}=a_{n+1}{q}_n+q_{n-1}$. Successive continued fraction convergents bracket $x$, henceThe infinite continued fraction is irrational: if $x=p/q$ were rational, a distinct convergent would be at distance at least $1/(q{q}_n)$, contradicting the first bound once $q_{n+1}>q$. If $x^2$ were rational, this irrational $x$ would have degree two. The Liouville approximation theorem would then give $|x-p_n/q_n|\ge C/q_n^2$. Comparing with the displayed bound would force $a_{n+1}\le 1/C$ for every $n$, contrary to the unbounded coefficients. Thus $x^2$ is irrational, by the unbounded continued-fraction coefficients exclude quadratic irrationality argument.

Put $\alpha =\sqrt{N}$ and use conventional convergent indexing starting at zero; the same argument covers all the printed positive indices. The continued fraction complete quotients satisfy ${\alpha }_{j+1}=1/({\alpha }_j-a_j)$, $a_j=\lfloor {\alpha }_j\rfloor$. After the first step they exceed one, while their algebraic conjugates lie in $(-1,0)$. Indeed ${\alpha }_1^{\prime }=1/(-\sqrt{N}-a_0)\in (-1,0)$, and if ${\alpha }_j^{\prime }\in (-1,0)$ with $a_j\ge 1$, then $1/({\alpha }_j^{\prime }-a_j)\in (-1,0)$.

Write ${\alpha }_{k+1}=(\sqrt{N}+m)/d$, where $m,d$ are integers and $d>0$. This form follows by rationalization at each step: $m_{j+1}=a_j{d}_j-m_j$ and $d_{j+1}=(N-m_{j+1}^2)/d_j$, starting from $m_0=0,d_0=1$. The two conjugate inequalities giveso $d<2\sqrt{N}$. The standard convergent recursions also giveSubstitute the displayed form of ${\alpha }_{k+1}$ and compare rational and irrational coefficients. This yields $p_k=m{q}_k+d{q}_{k-1}$ and $N{q}_k=m{p}_k+d{p}_{k-1}$. Therefore the small norm residues from square-root continued fractions obeyThe initial convergent satisfies the same relation with the usual $p_{-1}=1,q_{-1}=0$. This avoids the insufficient estimate obtained by merely replacing the convergent error with $1/q_k^2$.

For integer factorization, choose a factor base of small primes for which $N$ is a quadratic residue, together with $-1$ to record negative residues; a prime dividing $N$ already supplies a factor. Test the small nonzero integers $r_k=p_k^2-N{q}_k^2$ for being B-numbers. Complete factorization over the base records each prime exponent modulo two. Once enough relations are collected, linear algebra over ${\mathbb{F}}_2$ can choose a nonempty subcollection whose exponent sum is even, including the sign. ThenIf $X\not\equiv \pm Y(\mathrm{mod}N)$, one of $\gcd (X-Y,N)$ or $\gcd (X+Y,N)$ can yield a nontrivial factor. Relations with a noninvertible $p_k$ 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.

For cusps $\alpha ,\beta \in {\mathbb{P}}^1(\mathbb{Q})$, the modular symbol $\{\alpha ,\beta \}$ is the oriented path class in $H_1(X(\Gamma ),C;\mathbb{Z})$, where $C$ is the finite cusp set. Reversing paths changes the sign, concatenating paths gives $\{\alpha ,\beta \}+\{\beta ,\gamma \}=\{\alpha ,\gamma \}$, and the group identifies translated paths. A continued fraction expansion subdivides any rational-endpoint path into determinant-one edges. Representatives of the finitely many cosets therefore supply Manin symbols $[g]=\{g0,g\infty \}$. With inversion $S$ and translation $T$, reversing an edge and taking the boundary of an ideal triangle giveThese relations give a finite rational linear algebra presentation. Integral computation additionally removes the elliptic torsion in this naive presentation; the actual relative homology group of the compact surface is torsion-free.

The boundary of $\{\alpha ,\beta \}$ is $[\beta ]-[\alpha ]$ in $H_0(C)$. Its kernel is $H_1(X;\mathbb{Q})$ by the long exact sequence of a pair. A Hecke operator acts by summing the images of each path under its finite determinant-$n$ correspondence. Rational endpoints are again rational, so continued fractions reduce each image back to Manin symbols. Finite row reduction produces rational matrices for the relative symbols and for the boundary kernel. Integration of a weight-two cusp form against these absolute cycles is compatible with the Hecke action. The resulting decompositionexplains the relation between these matrices and cusp forms. Strictly, a rational matrix on absolute homology is not automatically a rational matrix on the holomorphic summand in an arbitrary complex basis. For subgroups preserved by real conjugation, the conjugation eigenspaces provide rational models of the cusp-form representation. More generally one should specify a compatible rational model or use the doubled homological representation. This distinction matters in interpreting the essay's rationality claim for an arbitrary subgroup; the algorithm on homology is always rational.

For the supplied subgroup, use $P=(1736)(254)$ for translation and $Q=(17)(26)(34)$ for inversion, following the PDF's naming. Translation has two cycles, so there are two cusps of widths four and three. Inversion fixes just coset five, giving one elliptic orbit of order two. The order-three product acts with cycles $(1)(253)(467)$ in one of the two equivalent composition conventions, giving one elliptic orbit of order three. Since $Q^2=1$, the central $-I$ acts trivially and the effective index is seven. The genus formula for a modular curve givesThe long exact sequence of a pair now givesOne can see this directly from the symbols. Over $\mathbb{Q}$, $Q$ gives $m_7=-m_1$, $m_6=-m_2$, $m_4=-m_3$ and $m_5=0$. The fixed order-three coset gives $m_1=0$, and the other triangle relations give $m_3=-m_2$. Thus $(m_1,\dots ,m_7)=(0,t,-t,t,0,-t,0)$. After removing elliptic torsion the integral group is free of rank one, agreeing with the surface calculation. Since $g=0$, the absolute boundary kernel and $S_2(\Gamma )$ both vanish: the cusp-form Hecke matrices for this particular example are the empty $0\times 0$ matrices.

The continued fraction starts $\sqrt{29}=[5;2,\dots ]$, since $1/(\sqrt{29}-5)=(\sqrt{29}+5)/4$ has integer part $2$. Its next continued fraction convergent is $5+1/2=11/2$. Direct substitution gives

Since $7\equiv 3(\mathrm{mod}4)$, the ring of integers is $\mathbb{Z}[\sqrt{7}]$. A unit $a+b\sqrt{7}$ has norm $a^2-7b^2=\pm 1$. Norm minus one is impossible: it would give $a^2\equiv -1(\mathrm{mod}7)$, whereas the squares modulo seven are $0,1,2,4$. The element $\epsilon =8+3\sqrt{7}$ has norm one and exceeds one.

Suppose a positive unit $u$ in the chosen real embedding satisfies $1<u<\epsilon$. Its conjugate is $1/u>0$, soThis expression is strictly increasing in $u$, and at $u=\epsilon$ it equals three. Thus the integer $b$ is one or two. But then $a^2=7b^2+1$ is eight or twenty-nine, neither a square. Therefore there is no positive unit strictly between one and $\epsilon$.

For any positive unit $u$, choose an integer $k$ such that $1\le u{\epsilon }^{-k}<\epsilon$. The remaining unit must be one, so $u={\epsilon }^k$. Multiplication by minus one handles negative units. Hencewhich proves that $8+3\sqrt{7}$ is fundamental, using no continued fractions.

A Heegaard splitting of a closed oriented three-manifold is a decomposition $Y=H_0{\cup }_{\Sigma }{H}_1$ into two handlebodies, with their common boundary the Heegaard surface $\Sigma$. With boundary present, the corresponding pieces are compression bodies, whose negative boundaries account for $\partial Y$.

For the given triangulation, take the barycentric subdivision. A regular neighbourhood $H_0$ of the original one-skeleton is a handlebody: thicken vertices to balls and edges to one-handles, then contract a spanning tree. The complementary region is a regular neighbourhood $H_1$ of the dual one-skeleton, whose vertices are tetrahedron centres and whose edges cross triangular faces. It too is a handlebody. Both graphs are connected, and their common boundary supplies the Heegaard splitting. If the original triangulation has $v$ vertices and $e$ edges, its Heegaard surface has genus $e-v+1$; the dual count gives the same number by $v-e+f-t=0$.

Choose an oriented meridian of a knot $\mu$ and the Seifert longitude $\lambda$ supplied by a Seifert surface for the null-homologous knot. For relatively prime integers $p,q$, rational Dehn surgery removes the interior of a tubular neighborhood and attaches a solid torus with its meridian of a solid torus on the unoriented slope $p\mu +q\lambda$. The choices $(p,q)$ and $(-p,-q)$ describe the same slope; $q=0$ is the original meridional filling. The boundary gluing reverses boundary orientation so that the oriented three-manifold extends across the filling.

For integral coefficients $n_i$, attach two-handles to $B^4$ along the components of the framed link, with their indicated Seifert framing shifts. The boundary operation removes $S^1\times D^2$ and inserts $D^2\times S^1$, with meridian $n_i{\mu }_i+{\lambda }_i$. Thus the compact oriented surgery trace satisfiesFor a finite rational coefficient, use a negative continued fractionReplace that component by an integrally framed chain of successive meridians with coefficients $a_0,\dots ,a_k$. Repeated slam-dunk moves give back $p/q$. Perform this replacement for every rationally framed component, leaving meridional fillings out. The resulting integral framed link has the same filled boundary, so its surgery trace proves that every such rational filling bounds a compact oriented four-manifold.

Use the positive-exponent quantum Fourier transform convention $F_N|x⟩=N^{-1/2}{\sum }_t{e}^{2\pi ixt/N}|t⟩$. The period of a function here is the least positive translation leaving the function unchanged on the cyclic group ${\mathbb{Z}}_N$. The injective promise means $f(x)=f(x^{\prime })$ exactly when $x\equiv x^{\prime }(\mathrm{mod}r)$. In particular $r\mid N$: the subgroup of period translations is generated by $r$, and wrapping the argument by $N$ preserves its value. This is exact quantum period finding on a finite cyclic group, rather than the truncated, nondividing-period version requiring continued fractions.

Prepare a uniform superposition state in the first quantum register using $F_N|0⟩$, and perform a reversible computation of the function into a second quantum register, cleaning its workspace by uncomputation:A quantum measurement in the computational basis of the second quantum register leaves a periodic coset state in the first:For the quantum Fourier transform of this periodic coset state, the finite geometric series vanishes unless the measured label is $t=mN/r$. On those labels its normalized amplitude is $r^{-1/2}{e}^{2\pi iam/r}$. Thus $m$ has the uniform distribution on a finite set on $\{0,\dots ,r-1\}$, irrespective of $a$.

Compute the greatest common divisor by the Euclidean algorithm, and set $q=N/\gcd (t,N)$, with $\gcd (0,N)=N$. Since $t=mN/r$,The exact period recovery from a Fourier sample is therefore certified by testing $f(q\mathrm{mod}N)=f(0)$. Every candidate $q$ divides $r$ and lies between $1$ and $r$, so the injective promise makes that equality equivalent to $q=r$. This includes $r=N$, where the test uses input $0$, and $r=1$, which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.

The concise result isHere $\phi$ is the Euler totient function, with $\phi (1)=1$. The totient lower bound from the Mertens product gives $\phi (r)/r=\Omega (1/\max \{1,\log \log N\})$ for $r\le N$. Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in $\log N$. Repeating $O(\max \{1,\log \log N\})$ independent trials gives constant success probability; the herald accepts only correct answers.

The printed asymptotic bound has the wrong direction for this argument. In Big O notation, the stated upper bound on the number of coprime integers supplies no success lower bound and is itself false uniformly: for prime $N$, $\phi (N)=N-1$, not $O(N/\log \log N)$. Likewise the single-trial success need not be $O(1/\log \log N)$, since it tends to one for $r=N$ prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to $1/\max \{1,\log \log N\}$; this discards useful successes and is unnecessary for efficient recovery.

Use the periodic continued fraction $\sqrt{d}=[a_0;\overline{a_1,\dots ,a_m}]$. A direct matrix argument avoids any assumption about the parity of the period. LetPeriodicity says that $M$ fixes ${\theta }_1$ as a Möbius transformation, while $B$ takes ${\theta }_1$ to $\sqrt{d}$. Thus $N=\left(\begin{array}{cc}A& B_1\\ C& D\end{array}\right)$ has integer entries and fixes $\sqrt{d}$. Equating rational and irrational parts in $A\sqrt{d}+B_1=\sqrt{d}(C\sqrt{d}+D)$ gives $A=D,B_1=dC$. ConsequentlyThe eigenvalue of $M$ on $({\theta }_1,1{)}^T$ is its denominator $M_{21}{\theta }_1+M_{22}>1$; this uses $a_i\ge 1$ and ${\theta }_1>1$, including the one-term period. The corresponding eigenvalue of $N$ is $A+C\sqrt{d}>1$. If the algebraic norm is $-1$, square this unit; otherwise keep it. In either case there is a unit $u=X+Y\sqrt{d}>1$ of algebraic norm $1$ with integer $X,Y$. Its powers have integer coefficients and algebraic norm $1$, and are distinct since $u^j$ strictly increases. Hence Pell's equation has infinitely many integer solutions.