Continued Fractions and Probability Estimations in Shor’s Algorithm: A Detailed and Self-Contained Treatise

Abstract

Shor’s algorithm for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books), filling the gap to allow a complete comprehension of Shor’s algorithm. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.

1. Introduction

Shor’s algorithm [1] for prime factorization is generally considered as a major milestone and a breakthrough in quantum computing: it solves a practically very relevant problem (which is, e.g., an underpinning of cryptography) with an exponential speedup compared to classical methods.

The algorithm is based on the fact that determining a divisor and finally a prime factor of a natural number $n\in \mathbb{N}$ can be reduced to finding the period p of the modular exponentiation function $f\left(x\right)=a^{x}modn$ for an a with $0<a<n$ (see Section 3.2.1).

The overall algorithm is hybrid, consisting of classical computations and a quantum computation. The classical computations are computing greatest common divisors with the Euclidian algorithm, and perform a continuous fraction analysis. A detailed discussion of the latter is one of the two foci of this contribution (see Section 2).

The quantum part mainly consists of: (i) creating an entangled state based on an oracle computing the modular exponentiation function f above, (ii) performing a quantum Fourier transform (QFT) on this state, and (iii) measuring it. The oracle produces the following state:

$$\left|a⟩\right|b⟩=\frac{1}{\sqrt{N}}\stackrel{N-1}{\sum _{x=0}}\left|x⟩\right|f\left(x\right)⟩$$

(1)

After applying the quantum Fourier transform and a measurement, the first part (i.e., the |a⟩-part) of the quantum register is in state

$$\frac{1}{\sqrt{NA}}\stackrel{A-1}{\sum _{j=0}}{\omega }_N^{jpy}|y⟩$$

(2)

In this state, the searched period p already appears in its amplitude. The measured value y can then be used with high probability (see Section 3.4, Theorem 16) to compute the period p of the modular exponentiation function f by analyzing the convergents of a continued fraction (see Section 3.4.1) and finally, based on the period, a prime factor (see Section 3.2.1). A detailed discussion on how this is achieved is the second focus of this contribution (see Section 3).

Structure of the Article

The article is structured as follows: in Section 2 we cover all details about continued fractions that are required to comprehend the corresponding aspect of Shor’s algorithm.

Section 2.1 defines the notion of a continued fraction, gives examples of how to compute the continued fraction representation of a rational number, and demonstrates how to compute the number that a continued fraction (and thus convergents) represents.

Convergents as the fundamental tool in the theory of continued fractions are detailed in Section 2.2: after defining the term, basic theorems about convergents such as the recursion theorem, two sign theorems, monotony properties, convergent comparison, nesting of a number by its convergents, and several distance estimations are proven.

Next, the brief Section 2.3 presents infinite regular continued fractions to represent non-rational numbers. A corresponding algorithm is provided to compute such continued fractions.

Section 2.4 gives several upper bounds and lower bounds for the difference between a number and its convergents. Exploiting one of these bounds, the convergence of the convergents of an infinite regular continued fraction of a number to this number is proven. Semiconvergents are defined and corresponding monotony properties are given.

Best approximations of a real number are introduced in Section 2.5. It is proven that best approximations of the second kind are convergents and vice versa (Lagrange’s theorem). Best approximations of the first kind are proven to be convergents or semiconvergents (another theorem by Lagrange). Finally, Legendre’s theorem is presented, which is the main result about continued fractions required by Shor’s algorithm: it allows the implication that a given fraction is a convergent of another number.

Section 3 is devoted to estimating the probability that convergents can be used to compute periods, i.e., that Legendre’s theorem can be applied.

At the beginning of Section 3, Section 3.1 proves a lower bound and an upper bound for the secant lengths of the unit circle. This estimation is central for estimating the aforementioned probability.

Section 3.2 contains many different estimations of parameters that appear in the measurement result of Shor’s algorithm. In Section 3.2.1, we recall the very basics of modular arithmetic, relate this to group theory, and use Lagrange’s theorem from group theory to prove that the period of the modular exponentiation function in Shor’s algorithm is less than the number to be factorized (Lemma 8). Intervals of consecutive multiples of the period are studied in Section 3.2.2: it is shown that multiples of N are sparsely scattered across these intervals (Note 12). This implies that measurement results are somehow centered around multiples of $N/p$ (Corollary 9). The cardinality of arguments in the superposition that build the pre-image of a certain $f\left(x\right)$ is estimated in Section 3.2.3. Section 3.2.4 proves bounds of phases of amplitudes relevant for computing the probability of measurement results as a geometric sum.

Finally, Section 3.3 computes this probability: it is proven that a measurement result is close to a multiple of $N/p$ with probability of approximately $4/{\pi }^2$ (Lemma 10).

Section 3.4 shows that this measurement result fulfills the assumption of Legendre’s theorem (Theorem 15). Thus, by computing convergents, the period can be determined (Theorem 16 and Section 3.4.1).

Section 3.5 sketches how the main results contribute to the proof of Shor’s algorithm. Its purpose is to avoid getting lost in the huge amount of low-level details.

A brief conclusion and discussion of related work ends this contribution with Section 4.

2. Continued Fractions

2.1. Definition of Continued Fractions and Their Computation

We define the notion of continued fractions and give an example of how to compute them.

Definition 1.

An expression of the form

$$a_0+\frac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{\ddots }}}$$

(3)

with $a_i,b_i\in ℂ$ is called an infinite continued fraction.

If, in this expression, it is $b_i=1$ for all i, $a_0\in \mathbb{Z}$, and $a_i\in \mathbb{N}$ for i≥1, the expression is called a regular continued fraction.

A finite regular continued fraction (simply called a continued fraction) satisfies, in addition, the condition $\exists N\in \mathbb{N}\forall k\in \mathbb{N}:a_{N+k}=0$ (convention: “1/0 = 0”).

A continued fraction is, thus, the following expression:

$$\left[a_0;a_1,\cdots ,a_N\right]\stackrel{\underset{def}{}}{=}{a}_0+\frac{1}{a_1+\frac{1}{\ddots +\frac{1}{a_{N-1}+\frac{1}{a_N}}}}$$

(4)

A continued fraction of a rational number a/b is computed as follows: the integer part $\lfloor a/b\rfloor$ becomes $a_0\in \mathbb{Z}$, leaving the non-negative rational remainder $x_1/y_1\in \mathbb{Q}$. The latter is now written as $1/\left(y_1/x_1\right)$, resulting in

$$a_0+\frac{1}{\left(\frac{y_1}{x_1}\right)}$$

Next, the integer part $\lfloor y_1/x_1\rfloor$ becomes $a_1$, leaving a rational remainder that is treated as before. This processing stops until the rational remainder is zero. Figure 1 gives an example of the processing.

Beside this straightforward proceeding to compute continued fractions, the well-known Euclidian algorithm can be used for this purpose too. Figure 2 gives a corresponding example; it should be self-descriptive.

Formally, a continued fraction can always be reduced such that its last element is greater than or equal to 2.

Note 1.

Let $\left[a_0;a_1,\dots ,a_N\right]$ be a continued fraction. Then:

$$\left[a_0;a_1,\dots ,a_N\right]=\left[a_0;a_1,\dots ,a_{N-1}+\frac{1}{a_N}\right]$$

(5)

Especially, it can always be achieved that a continued fraction $\left[a_0;a_1,\dots ,a_N\right]$ satisfies $a_N\ge 2$.

Proof. 

The following simple computation proves the first claim:

$$\begin{array}{cc}\left[a_0;a_1,\dots ,a_N\right]& =a_0+\frac{1}{a_1+\frac{1}{\ddots +\frac{1}{a_{N-1}+\frac{1}{a_N}}}}\\ & =a_0+\frac{1}{a_1+\frac{1}{\ddots +\frac{1}{\left(a_{N-1}+\frac{1}{a_N}\right)}}}\\ & =\left[a_0;a_1,\dots ,a_{N-1}+\frac{1}{a_N}\right]\end{array}$$

Furthermore, if $a_N=1$ in $\left[a_0;a_1,\dots ,a_N\right]$ then $a_{N-1}+1/a_N$ ≥ 2. This is because, by definition, $a_k\ge 1$ for 1 ≤ k ≤ N. □

Equation (5) implies a straightforward way to compute the value represented by a continued fraction $\left[a_0;a_1,\dots ,a_N\right]$: see Figure 3.

2.2. Convergents

Next, we define the “workhorses” of the theory of continued fractions.

Definition 2.

$\left[a_0;a_1,\dots ,a_m\right]$ is called m-th convergent of the continued fraction $\left[a_0;a_1,\dots ,a_N\right]$ for 0 ≤ m ≤ N, or m-th convergent of the infinite regular continued fraction $\left[a_0;a_1,\dots \right]$.

Convergents can be computed recursively based on the following theorem:

Theorem 1.

(Recursion Theorem)

Define:

• $p_0=a_0$;
• $p_1=a_1{a}_0+1$;
• $p_n=a_n{p}_{n-1}+p_{n-2}$ for n ≥ 2;

and define:

• $q_0=1$;
• $q_1=a_1$;
• $q_n=a_n{q}_{n-1}+q_{n-2}$ for n ≥ 2.

Then, for every convergent $\left[a_0;a_1,\dots ,a_n\right]$, it is:

$$\left[a_0;a_1,\dots ,a_n\right]=\frac{p_n}{q_n}$$

(6)

Proof (by induction).

Let n = 0, 1: Then, $\left[{\mathrm{a}}_0\right]={\mathrm{a}}_0=\frac{{\mathrm{p}}_0}{{\mathrm{q}}_0}$ and $\left[{\mathrm{a}}_0;{\mathrm{a}}_1\right]={\mathrm{a}}_0+\frac{1}{{\mathrm{a}}_1}=\frac{{\mathrm{a}}_0{\mathrm{a}}_1+1}{{\mathrm{a}}_1}=\frac{{\mathrm{p}}_1}{{\mathrm{q}}_1}$.

Induction hypothesis: $\left[a_0;a_1,\dots ,a_n\right]=\frac{p_n}{q_n}=\frac{a_n{p}_{n-1}+p_{n-2}}{a_n{q}_{n-1}+q_{n-2}}$.

Induction step n → n + 1: According to Note 1, it is

$$\left[a_0;a_1,\dots ,a_n,a_{n+1}\right]=\left[a_0;a_1,\dots ,a_n+\frac{1}{a_{n+1}}\right]$$

and the last continued fraction has n elements, i.e., the induction hypothesis applies:

$$\begin{array}{c}{a}_0;a_1,\dots ,a_n+\frac{1}{a_{n+1}}]=\frac{\left(a_n+\frac{1}{a_{n+1}}\right)p_{n-1}+p_{n-2}}{\left(a_n+\frac{1}{a_{n+1}}\right)q_{n-1}+q_{n-2}}=\frac{\frac{a_n{a}_{n+1}+1}{a_{n+1}}{p}_{n-1}+p_{n-2}}{\frac{a_n{a}_{n+1}+1}{a_{n+1}}{q}_{n-1}+q_{n-2}}\\ =\frac{\left(a_n{a}_{n+1}+1\right)p_{n-1}+a_{n+1}{p}_{n-2}}{\left(a_n{a}_{n+1}+1\right)q_{n-1}+a_{n+1}{q}_{n-2}}\\ =\frac{a_{n+1}\left(a_n{p}_{n-1}+p_{n-2}\right)+p_{n-1}}{a_{n+1}\left(a_n{q}_{n-1}+q_{n-2}\right)+q_{n-1}}\stackrel{\left(A\right)}{=}\frac{a_{n+1}{p}_n+p_{n-1}}{a_{n+1}{q}_n+q_{n-1}}\\ \stackrel{\left(B\right)}{=}\frac{p_{n+1}}{q_{n+1}}\end{array}$$

Here, (A) is valid because of the induction hypothesis, and (B) is the definition of $p_{n+1}$ and $q_{n+1}$. □

The recursion theorem implies the often used.

Corollary 1.

Numerators and denominators of convergents of a continued fraction $\left[a_0;a_1,\dots ,a_N\right]$ with $a_0\ge 0$ are strictly monotonically increasing:

$$p_n>p_{n-1} \mathrm{and} q_n>q_{n-1} \mathrm{for} \mathrm{all} n\in \mathbb{N}.$$

Proof (by induction).

Let n = 1: By definition, $p_0=a_0$, $p_1=a_1{a}_0+1$. Because $a_i\ge 1$ for i ≥ 1, and $a_0\ge 0$, it is $p_1>p_0\ge 0$. Similarly, $q_1>q_0>0$

Now, $p_n=a_n{p}_{n-1}+p_{n-2}$ and $q_n=a_n{q}_{n-1}+q_{n-2}$ for n ≥ 2. With $a_n\ge 1$ by definition, and $p_{n-1}>p_{n-2}$ (≥1) as well as $q_{n-1}>q_{n-2}$ (≥1) by induction hypothesis, the claim follows. □

The next theorem is about the sign of a combination of the numerators and denominators of consecutive convergents of a continued fraction.

Theorem 2.

(Sign Theorem)

For $\left[a_0;a_1,\dots ,a_n\right]=\frac{p_n}{q_n}$, the following holds:

$$p_n{q}_{n-1}-p_{n-1}{q}_n={\left(-1\right)}^{n-1}$$

(7)

Proof (by induction).

For n = 1, it is

$$p_1{q}_0-p_0{q}_1=\left(a_1{a}_0+1\right)\cdot 1-a_0\cdot a_1=1={(-1)}^0$$

Induction step n → n + 1:

$$\begin{array}{cc}{p}_{n+1}{q}_n-p_n{q}_{n+1}& =\left(a_{n+1}{p}_n+p_{n-1}\right)q_n-p_n\left(a_{n+1}{q}_n+q_{n-1}\right)\\ & =a_{n+1}{p}_n{q}_n+p_{n-1}{q}_n-p_n{a}_{n+1}{q}_n-p_n{q}_{n-1}\\ & =p_{n-1}{q}_n-p_n{q}_{n-1}=-\left(p_n{q}_{n-1}-p_{n-1}{q}_n\right)\\ & \stackrel{\left(A\right)}{=}-{\left(-1\right)}^{n-1}={\left(-1\right)}^n\end{array}$$

(A) uses the induction hypothesis. □

In case the numerators and denominators stem from the n-th convergent and the (n − 2)-nd convergent, the last n-th element of the convergent becomes part of the equation.

Theorem 3.

(Second Sign Theorem)

For $\left[a_0;a_1,\dots ,a_n\right]=\frac{p_n}{q_n}$, the following holds:

$$p_n{q}_{n-2}-p_{n-2}{q}_n={\left(-1\right)}^n{a}_n$$

(8)

Proof. 

It is ${\mathrm{p}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{n}}{\mathrm{p}}_{\mathrm{n}-1}+{\mathrm{p}}_{\mathrm{n}-2}$ and ${\mathrm{q}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{n}}{\mathrm{q}}_{\mathrm{n}-1}+{\mathrm{q}}_{\mathrm{n}-2}$.

Multiplying the first equation by $q_{n-2}$ and the second equation by $p_{n-2}$ results in $q_{n-2}{p}_n=q_{n-2}{a}_n{p}_{n-1}+q_{n-2}{p}_{n-2}$ and $p_{n-2}{q}_n=p_{n-2}{a}_n{q}_{n-1}+p_{n-2}{q}_{n-2}$. Next, both equations are subtracted:

$$\begin{array}{cc}{p}_n{q}_{n-2}-p_{n-2}{q}_n& =q_{n-2}{a}_n{p}_{n-1}+q_{n-2}{p}_{n-2}-p_{n-2}{a}_n{q}_{n-1}-p_{n-2}{q}_{n-2}\\ & =q_{n-2}{a}_n{p}_{n-1}-p_{n-2}{a}_n{q}_{n-1}\\ & =a_n\left(p_{n-1}{q}_{n-2}-p_{n-2}{q}_{n-1}\right)\\ & \stackrel{\left(A\right)}{=}{\left(-1\right)}^n{a}_n\end{array}$$

where (A) is implied by the sign theorem (Theorem 2) and considering ${(-1)}^{n-2}={(-1)}^n$. □

The sign theorem immediately yields the important.

Corollary 2.

Numerator and denominator of a convergent are co-prime.

Proof. 

Let t be a divisor of ${\mathrm{p}}_{\mathrm{n}}$ and ${\mathrm{q}}_{\mathrm{n}}$, i.e., $t|p_n$ and $t|q_n$. Then, $t|\left(p_n{q}_{n-1}-p_{n-1}{q}_n\right)$, but $\left(p_n{q}_{n-1}-p_{n-1}{q}_n\right)={\left(-1\right)}^{n-1}$ according to the sign theorem. Thus, t = ±1. □

Convergents can be represented as a sum of fractions with alternating sign and whose denominators consist of products of two consecutive denominators from the recursion theorem.

Theorem 4.

(Representation as a Sum)

Each convergent can be represented as a sum:

$$\left[a_0;a_1,\dots ,a_n\right]=a_0+\frac{1}{q_1{q}_0}-\frac{1}{q_2{q}_1}+\cdots +{\left(-1\right)}^{n-1}\frac{1}{q_n{q}_{n-1}}$$

(9)

Proof. 

Let $\left[{\mathrm{a}}_0;{\mathrm{a}}_1,\dots ,{\mathrm{a}}_{\mathrm{n}}\right]=\frac{{\mathrm{p}}_{\mathrm{n}}}{{\mathrm{q}}_{\mathrm{n}}}$. Since $-\frac{p_i}{q_i}+\frac{p_i}{q_i}=0$, we can write

$$\left[a_0;a_1,\dots ,a_n\right]=\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}+\frac{p_{n-1}}{q_{n-1}}-\frac{p_{n-2}}{q_{n-2}}+\frac{p_{n-2}}{q_{n-2}}-\cdots +\frac{p_1}{q_1}-\frac{p_0}{q_0}+\frac{p_0}{q_0}$$

Computing the differences results in

$$\begin{array}{cc}\left[a_0;a_1,\dots ,a_n\right]& =\frac{p_n{q}_{n-1}-q_n{p}_{n-1}}{q_n{q}_{n-1}}+\frac{p_{n-1}{q}_{n-2}-q_{n-1}{p}_{n-2}}{q_{n-1}{q}_{n-2}}+\cdots +\frac{p_1{q}_0-q_1{p}_0}{q_1{q}_0}+\frac{p_0}{q_0}\\ & \stackrel{\left(A\right)}{=}\frac{{\left(-1\right)}^{n-1}}{q_n{q}_{n-1}}+\frac{{\left(-1\right)}^{n-2}}{q_{n-1}{q}_{n-2}}+\cdots +\frac{{\left(-1\right)}^0}{q_1{q}_0}+a_0\end{array}$$

where the sign theorem is applied in (A) and the last term $a_0=p_0/q_0$ is the recursion theorem. □

The next theorem is key for many estimations in the domain of continued fractions.

Theorem 5.

(Monotony Theorem)

Let $x_n\stackrel{\underset{def}{}}{=}\frac{p_n}{q_n}=\left[a_0;a_1,\dots ,a_n\right]$ denote the n-th convergent. Then:

$$x_{2n}<x_{2n+2}$$

and

$$x_{2n+1}>x_{2n+3}$$

I.e., even convergents are strictly monotonically increasing, and odd convergents are strictly monotonically decreasing.

Proof. 

We compute the following difference, where (A) again uses $-\frac{p_i}{q_i}+\frac{p_i}{q_i}=0$:

$$\begin{array}{cc}{x}_n-x_{n-2}& =\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}\stackrel{\left(A\right)}{=}\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}+\frac{p_{n-1}}{q_{n-1}}-\frac{p_{n-2}}{q_{n-2}}\\ & =\frac{p_n{q}_{n-1}-q_n{p}_{n-1}}{q_n{q}_{n-1}}+\frac{p_{n-1}{q}_{n-2}-q_{n-1}{p}_{n-2}}{q_{n-1}{q}_{n-1}}\\ & \stackrel{\left(B\right)}{=}\frac{{(-1)}^{n-1}}{q_n{q}_{n-1}}+\frac{{(-1)}^{n-2}}{q_{n-1}{q}_{n-2}}=\frac{{(-1)}^{n-1}{q}_{n-2}+{(-1)}^{n-2}{q}_n}{q_n{q}_{n-1}{q}_{n-2}}\\ & =\frac{{(-1)}^{n-2}{q}_n-{(-1)}^{n-2}{q}_{n-2}}{q_n{q}_{n-1}{q}_{n-2}}=\frac{{(-1)}^{n-2}\left(q_n-q_{n-2}\right)}{q_n{q}_{n-1}{q}_{n-2}}\\ & =\frac{{(-1)}^n\left(q_n-q_{n-2}\right)}{q_n{q}_{n-1}{q}_{n-2}}\stackrel{\left(C\right)}{=}\frac{{(-1)}^n{a}_n{q}_{n-1}}{q_n{q}_{n-1}{q}_{n-2}}=\frac{{(-1)}^n{a}_n}{q_n{q}_{n-2}}\end{array}$$

(B) is because of the sign theorem, and (C) follows from $q_n=a_n{q}_{n-1}+q_{n-2}$, i.e., the recursion theorem.

Now, because of $a_n,q_n,q_{n-2}>0$, it is $\frac{a_n}{q_n{q}_{n-2}}>0$. Thus, $\frac{{(-1)}^n{a}_n}{q_n{q}_{n-2}}>0$ for n even and $\frac{{(-1)}^n{a}_n}{q_n{q}_{n-2}}<0$ for n odd. This implies $x_n=\frac{{(-1)}^n{a}_n}{q_n{q}_{n-2}}+x_{n-2}>x_{n-2}$ for n even as well as $x_n=\frac{{(-1)}^n{a}_n}{q_n{q}_{n-2}}+x_{n-2}<x_{n-2}$ for n odd. □

While even convergents are increasing and odd convergence are decreasing, all even convergents are smaller than all odd convergents. This is the content of the next very important theorem.

Theorem 6.

(Convergents Comparison Theorem)

For $0\le 2n,2m+1\le N$, it is $x_{2n}<x_{2m+1}$

Proof. 

As before, using the sign theorem in (A), we obtain

$$x_n-x_{n-1}=\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{p_n{q}_{n-1}-q_n{p}_{n-1}}{q_n{q}_{n-1}}\stackrel{\left(A\right)}{=}\frac{{(-1)}^{n-1}}{q_n{q}_{n-1}}=\frac{{(-1)}^{n-1}}{{\beta }_n}$$

with ${\beta }_n:=q_n{q}_{n-1}$. Because $q_n,q_{n-1}>0$, it is β_n > 0, i.e., the sign of $\frac{{(-1)}^{n-1}}{{\beta }_n}$ is in fact ${(-1)}^{n-1}$.

Thus, $x_{2n+1}-x_{2n}=\frac{{(-1)}^{2n}}{{\beta }_{2n+1}}>0$, and we get $x_{2n+1}=\frac{{(-1)}^{2n}}{{\beta }_{2n+1}}+x_{2n}>x_{2n}$. This shows that an even convergent $x_{2n}$ is strictly smaller than its immediate succeeding odd convergent $x_{2n+1}$.

But what about an arbitrary odd convergent $x_{2m+1}$? For n < m, the monotony theorem (Theorem 6) yields $x_{2n}<x_{2m}$ and we showed before that $x_{2m}<x_{2m+1}$; thus, $x_{2n}<x_{2m+1}$.

For n > m, the monotony theorem yields $x_{2m+1}>x_{2n+1}$ and with $x_{2n+1}>x_{2n}$ we see $x_{2n}<x_{2m+1}$. □

The following often-used corollary computes the difference of two immediately succeeding convergents by mean of the denominators of the convergents, while the difference of the n-th convergent and the (n − 2)-nd convergent adds the n-th element of the n-th convergent as a factor.

Corollary 3.

$$\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{{(-1)}^{n-1}}{q_n{q}_{n-1}}$$

(10)

and

$$\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{{\left(-1\right)}^n{a}_n}{q_n{q}_{n-2}}$$

(11)

Proof. 

Equation (10) is the first equation from the proof of Theorem 6. The second equation follows because of

$$\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{p_n{q}_{n-2}-p_{n-2}{q}_n}{q_n{q}_{n-2}}\stackrel{\left(A\right)}{=}\frac{{\left(-1\right)}^n{a}_n}{q_n{q}_{n-2}}$$

where (A) is because of the second sign theorem (Theorem 3). □

We already saw that the even convergents are strictly monotonically increasing, that the odd convergents are strictly monotonically decreasing, and that each even convergent is less than all odd convergents. According to the next theorem, the value of a continued fraction lies between the even convergents and the odd convergents, i.e., this value is larger than all even convergents and smaller than all odd convergents. The situation is depicted in Figure 4.

Note that the notion of the value of a continued fraction is defined for finite continued fractions. In Section 4, this notion will also be defined for regular infinite continued fractions.

Theorem 7.

(Nesting Theorem)

Let x be the value of the continued fraction $\left[a_0;a_1,\dots ,a_N\right]$ and let $x_k$ be its convergents. Then:

$$\forall m,n<N:x_{2m}<x<x_{2n+1}$$

(12)

Proof. 

The value of x is the convergent with the highest index N, i.e., $x=x_N=\left[a_0;a_1,\dots ,a_N\right]$.

Let N = 2k be even. Since even convergents are strictly monotonically increasing, we know that $\forall 2m<N:x_{2m}<x_{2k}=x_N=x$, and according to the convergent comparison theorem (Theorem 6), we know $\forall 2n+1:x=x_N=x_{2k}<x_{2n+1}$.

Let N = 2k + 1 be odd. Since odd convergents are strictly monotonically decreasing, we know that $\forall 2n+1<N:x_{2n+1}>x_{2k+1}=x_N=x$, and according to the convergent comparison theorem (Theorem 6), we know $\forall 2m:x=x_N=x_{2k+1}>x_{2m}$. □

Because the value of a continued fraction is nested within its even convergents and odd convergents, the distance of this value from any of its convergents can be estimated by the distance of two consecutive convergents:

Theorem 8.

(Distance Theorem)

Let $x=\left[a_0;a_1,\dots ,a_N\right]$ and let $x_k$ be its convergents. Then:

$$\forall n:\left|x-x_n\right|<\left|x_{n-1}-x_n\right|$$

(13)

and

$$\forall n:\left|x-x_n\right|<\left|x_{n+1}-x_n\right|$$

(14)

Proof. 

Let n be even. Then, $x_n<x<x_{n-1}$, i.e., $x-x_n<x_{n-1}-x_n$. Additionally, it is $x-x_n>0$ and $x_{n-1}-x_n>0$. Thus, $\left|x-x_n\right|<\left|x_{n-1}-x_n\right|$ for n even.

Now, let n be odd. It is $x_{n-1}<x<x_n$, which implies $x-x_n>x_{n-1}-x_n\iff -\left(x_n-x\right)>-\left(x_n-x_{n-1}\right)$ $\iff x_n-x<x_n-x_{n-1}$. Because of $x_n-x>0$ and $x_n-x_{n-1}>0$, it is $\left|x_n-x\right|<\left|x_n-x_{n-1}\right|$ ⇔ $\left|x-x_n\right|<\left|x_{n-1}-x_n\right|$ for n odd.

Together, this proves Equation (13). Equation (14) is proven similarly. □

Figure 5 shows the corresponding geometric situation for an even n.

Similarly, the difference between any two arbitrary convergents can be estimated by the difference of the convergent with the smaller index and its immediate predecessor:

Theorem 9.

(Difference Theorem)

Let $x=\left[a_0;a_1,\dots ,a_N\right]$ and let $x_k$ be its convergents. Then:

$$\forall m>n:\left|x_m-x_n\right|<\left|x_{n-1}-x_n\right|$$

(15)

Proof. 

Let n be even, e.g., n = 2k.

Let m = 2t be even. By Theorem 6, even convergents are smaller than all odd convergents, i.e., $x_{2t}<x_{2k-1}$ for any $t\in \mathbb{N}$. Thus, $x_m-x_n=x_{2t}-x_{2k}<<x_{2k-1}-x_{2k}=x_{n-1}-x_n$.

Let m = 2t − 1 be odd. By the monotony theorem (Theorem 5), odd convergents are strictly monotonically decreasing, i.e., $x_{2t-1}<x_{2k-1}$ for each t > k. Thus, $x_m-x_n=x_{2t-1}-x_{2k}<x_{2k-1}-x_{2k}=x_{n-1}-x_n$.

For n odd, the proof is analogous. □

The geometry of the last theorem is depicted in Figure 6.

In several calculations, the size of the denominator of a convergent must be estimated:

Lemma 1.

(Size of Denominators)

For the denominator $q_n$ of a convergent $\frac{p_n}{q_n}=\left[a_0;a_1,\dots ,a_n\right]$, the following holds:

$$\forall n:q_n\ge n$$

(16)

and

$$\forall n>3:q_n>n$$

(17)

Proof. 

By definition, $q_0=1>0$, and $q_1=a_1\ge 1$ because $a_i\in \mathbb{N}$, and finally,

$$q_2\stackrel{\left(A\right)}{=}{a}_2{q}_1+q_0\stackrel{\left(B\right)}{=}{a}_2{q}_1+1\stackrel{\left(C\right)}{\ge }{q}_1+1\stackrel{\left(D\right)}{\ge }2$$

(A) holds because of the recursion theorem (Theorem 1), (B) is by definition of $q_0$, (C) is because $a_2\in \mathbb{N}$, and (D) has been seen just before (i.e., $q_1\ge 1$). This proves the lemma for $n\le 2$.

The proof for n ≥ 3 is by induction. It is

$$q_n\stackrel{\left(A\right)}{=}{a}_n{q}_{n-1}+q_{n-2}\stackrel{\left(B\right)}{\ge }{q}_{n-1}+q_{n-2}\stackrel{\left(C\right)}{\ge }{q}_{n-1}+\left(n-2\right)\stackrel{\left(D\right)}{\ge }{q}_{n-1}+1\stackrel{\left(E\right)}{\ge }n$$

where (A) is the recursion theorem, (B) is because of $a_n\in \mathbb{N}$, (C) is by induction hypothesis applied to $q_{n-2}$, (D) is because n ≥ 3, and (E) is by induction hypothesis applied to $q_{n-1}$. This proves Equation (16).

Equation (17) is proven by induction again. Let n > 3. The argumentation is exactly as before, with the exception of (D):

$$q_n\stackrel{\left(A\right)}{=}{a}_n{q}_{n-1}+q_{n-2}\stackrel{\left(B\right)}{\ge }{q}_{n-1}+q_{n-2}\stackrel{\left(C\right)}{\ge }{q}_{n-1}+\left(n-2\right)\stackrel{\left(D\right)}{>}{q}_{n-1}+1\stackrel{\left(E\right)}{\ge }n$$

(D) holds because n > 3, i.e., $n-2>1$. □

In fact, denominators of a convergent grow much faster than the inequation $q_n>n$ may indicate:

Lemma 2.

(Geometric Growth of Denominators)

Let $q_n$ ($n\ge 2$) be the denominator of the convergent $\frac{p_n}{q_n}=\left[a_0;a_1,\dots ,a_n\right]$. Then:

$$q_n\ge 2^{\frac{n-1}{2}}$$

(18)

Proof. 

It is ${\mathrm{q}}_{\mathrm{k}}={\mathrm{a}}_{\mathrm{k}}{\mathrm{q}}_{\mathrm{k}-1}+{\mathrm{q}}_{\mathrm{k}-2}>{\mathrm{q}}_{\mathrm{k}-1}+{\mathrm{q}}_{\mathrm{k}-2}\stackrel{\left(\mathrm{A}\right)}{>}2{\mathrm{q}}_{\mathrm{k}-2}$, with (A) because, according to corollary 1, denominators are strictly monotonically increasing, i.e., $q_{k-1}>q_{k-2}$.

By induction, it is $q_{2k}\ge 2^k{q}_0$, and then $2^k{q}_0\stackrel{\left(A\right)}{=}{2}^k\stackrel{\left(B\right)}{\ge }{2}^{\frac{\left(2k\right)-1}{2}}$ with (A) because $q_0=1$, and (B) follows from

$$2^k=2^{\frac{2k}{2}}\ge \frac{1}{\sqrt{2}}{2}^{\frac{2k}{2}}=2^{\frac{2k}{2}-\frac{1}{2}}=2^{\frac{2k-1}{2}}$$

Similarly, by induction, it is $q_{2k+1}\ge 2^k{q}_1$ and then $2^k{q}_1\stackrel{\left(A\right)}{\ge }{2}^k=2^{\frac{\left(2k+1\right)-1}{2}}$ with (A) because of $q_1\in \mathbb{N}$.

With $n=2k$ and $n=2k+1$, respectively, Equation (18) is implied. □

2.3. Convergence of Infinite Regular Continuous Fractions

In Section 2.1, we presented an algorithm to compute the continued fraction representation of a rational number. Next, we show how to compute such a representation for a non-rational number (Algorithm 1).

Algorithm 1 Continued Fraction Representation of Non-Rational Number

1. $\mathrm{Let} \alpha \in ℝ\setminus \mathbb{Q}$. Define: ${\alpha }_0:=\alpha$$\mathrm{and} b_0:=\lfloor {\alpha }_0\rfloor$; ${\alpha }_i:=\frac{1}{{\alpha }_{i-1}-b_{i-1}}$$\mathrm{and} b_i:=\lfloor {\alpha }_i\rfloor$ for i ≥ 1. 2. Then, $\left[b_0;b_1,b_2,\dots \right]$ is the continued fraction representation of$\mathsf{\alpha }. \mathrm{Each} {\alpha }_i$ is called the i-th complete quotient of α.

The above algorithm does not terminate, i.e., the continued fraction representation of a non-rational number is infinite. This is the content of the following note:

Note 2.

 

In Algorithm 1, it is ${\alpha }_i\notin \mathbb{Z}$.

Proof (by induction).

 

n = 0: Then, by definition, ${\alpha }_0=\alpha \notin \mathbb{Z}$.

Induction hypothesis: ${\alpha }_n\notin \mathbb{Z}$.

n → n + 1: Assume ${\alpha }_n-b_n\in \mathbb{Z}$ ⇒ $\left({\alpha }_n-b_n\right)=k\in \mathbb{Z}$ ⇒ ${\alpha }_n=k+b_n\in \mathbb{Z}$, which is a contradiction to the hypothesis! Thus, ${\alpha }_n-b_n\notin \mathbb{Z}$ ⇒ ${\alpha }_{n+1}:=\frac{1}{{\alpha }_n-b_n}\notin \mathbb{Z}$. □

Figure 7 gives the computation of the continued fraction representation of $\sqrt{2}$:

2.4. Bounds Expressed by Denominators of Convergents

In the following, we give upper bounds and lower bounds of the approximations of a number by the convergents of its continued fraction representation by means of the denominators of the convergents.

First, we start with estimations of upper bounds:

Lemma 3.

(Upper Bounds)

Let $p_n/q_n$ be a convergent of the continued fraction representation of x. Then:

$$\left|x-\frac{p_n}{q_n}\right|<\frac{1}{q_n{q}_{n+1}}<\frac{1}{q_n^2}\le \frac{1}{n^2}$$

(19)

Proof. 

With $x_n=p_n/q_n$, it is $\left|x-x_n\right|<\left|x_{n+1}-x_n\right|$ (see Theorem 8, Equation (14)). According to Corollary 3 (Equation (10)), it is

$$x_{n+1}-x_n=\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}=\frac{{(-1)}^n}{q_n{q}_{n+1}}$$

Thus,

$$\left|x-x_n\right|<\left|x_{n+1}-x_n\right|=\left|\frac{{(-1)}^n}{q_n{q}_{n+1}}\right|=\frac{1}{q_n{q}_{n+1}}\stackrel{\left(A\right)}{<}\frac{1}{q_n^2}\stackrel{\left(B\right)}{\le }\frac{1}{n^2}$$

where (A) holds because of $q_{n+1}>q_n$ (Corollary 1), and (B) is true because of $q_n\ge n$ (Lemma 1). □

An immediate consequence of this theorem is the convergence of the sequence of the convergents of a continued fraction to the value of the continued fraction. This, by the way, is the origin of the name “convergents”.

Corollary 4.

The series $\left(p_n/q_n\right)$ of the convergents of the continued fraction representation of $x\in ℝ\setminus \mathbb{Q}$ converges to x:

$$lim\frac{p_n}{q_n}=x$$

Proof. 

The claim follows immediately from $\left|x-\frac{p_n}{q_n}\right|<\frac{1}{n^2}$. □

Often, two fractions are compared by means of their mediant (“mediant” means “somewhere in between”).

Definition 3.

For $\mathrm{a}/\mathrm{b},\mathrm{c}/\mathrm{d}\in \mathbb{Q}$ and b, d > 0, the term $\frac{\mathrm{a}+\mathrm{c}}{\mathrm{b}+\mathrm{d}}$ is called the mediant of the two fractions.

The following simple inequation is often used.

Note 3.

(Mediant Property)

Let $a/b,c/d\in \mathbb{Q}$ and b, d > 0 and $\frac{a}{b}<\frac{c}{d}$.

Then:

$$\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$$

(20)

Proof. 

It is $\frac{a}{b}<\frac{c}{d}\Rightarrow ad<bc\Rightarrow bc-ad>0$ and $b,d>0\Rightarrow b\left(b+d\right)>0$. This implies $\frac{a+c}{b+d}-\frac{a}{b}=\frac{b\left(a+c\right)-a\left(b+d\right)}{b\left(b+d\right)}=\frac{bc-ad}{b\left(b+d\right)}>0$ and thus $\frac{a}{b}<\frac{a+c}{b+d}$. The inequation $\frac{a+c}{b+d}<\frac{c}{d}$ follows similarly. □

Mediants of convergents that are weighted in a certain way are another important concept for computing bounds:

Definition 4.

The term $x_{n,t}=\frac{t{p}_{n+1}+p_n}{t{q}_{n+1}+q_n}$ with $1\le t\le a_{n+2}$ is called the (n,t)-th semiconvergent.

Semiconvergents of an even n are strictly monotonically increasing, and semiconvergents of an odd n are strictly monotonically decreasing. This is the content of the following lemma.

Lemma 4.

(Monotony of Semiconvergents)

Let n be even. Then, $x_{n,t}<x_{n,t+1}$.

Let n be odd. Then, $x_{n,t}>x_{n,t+1}$.

Proof. 

A simple calculation and the use of the sign theorem (Theorem 2) results in

$$\begin{array}{cc}\hfill x_{n,t+1}-x_{n,t}=& \frac{\left(t+1\right)p_{n+1}+p_n}{\left(t+1\right)q_{n+1}+q_n}-\frac{t{p}_{n+1}+p_n}{t{q}_{n+1}+q_n}\hfill \\ \hfill & =\frac{{\left(-1\right)}^n}{\left(\left(t+1\right)q_{n+1}+q_n\right)\left(t{q}_{n+1}+q_n\right)}\hfill \end{array}$$

The denominator of the last fraction is always positive. Thus, the last term is positive iff n is even (i.e., $x_{n,t+1}-x_{n,t}>0$), and it is negative iff n is odd (i.e., $x_{n,t+1}-x_{n,t}<0$). □

In order to simplify proofs in what follows, the following conventions are used:

$$p_{-1}\stackrel{\underset{def}{}}{=}1 \mathrm{and} q_{-1}\stackrel{\underset{def}{}}{=}0$$

(21)

With this, $x_{-1,1}=\frac{p_0+p_{-1}}{q_0+q_{-1}}=\frac{a_0+1}{1+0}=a_0+1$ becomes a semiconvergent. Now, $x_1=\frac{p_1}{q_1}\stackrel{\left(A\right)}{=}\frac{a_1{a}_0+1}{a_1}=a_0+\frac{1}{a_1}\stackrel{\left(B\right)}{\le }{a}_0+1=x_{-1,1}$ where (A) is the recursion theorem and (B) follows because $a_1\ge 1$; thus, $x_1\le x_{-1,1}$.

Furthermore, it is $x_{-1,t}=\frac{t{p}_0+p_{-1}}{t{q}_0+q_{-1}}=\frac{t{a}_0+1}{t\cdot 1+0}=\frac{t{a}_0+1}{t}=a_0+\frac{1}{t}$ for $1\le t\le a_1$.

Putting things together, it is

$$x_{-1,1}=a_0+1>a_0+\frac{1}{2}>\cdots >a_0+\frac{1}{a_1}=x_1$$

(22)

Based on this, we can refine Figure 4, which depicts the nesting and ordering of convergents by including semiconvergents: Between two succeeding convergents (e.g., $x_n$ and $x_{n+2}$ in Figure 8, the corresponding semiconvergents ordered according to Lemma 4 are nested (in increasing order as shown for an even n in Figure 8). Furthermore, beyond $x_1=a_0+\frac{1}{a_1}$, the semiconvergents $x_{-1,t}$ are added.

Now, we are prepared to prove a lower bound of the approximation of a number by the convergents of its continued fraction representation by means of the denominators of the convergents.

Lemma 5.

(Lower Bounds)

Let $p_n/q_n$ be a convergent of the continued fraction representation of x. Then:

$$\left|x-\frac{p_n}{q_n}\right|>\frac{1}{\left(q_n+q_{n+1}\right)q_n}$$

(23)

Proof. 

The proof is based on the following claims:

Claim 1.

n even ⇒ $\frac{p_n}{q_n}<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<x<\frac{p_{n+1}}{q_{n+1}}$.

Proof. 

$\frac{p_{n+1}+p_n}{q_{n+1}+q_n}$ is the mediant of $\frac{p_{n+1}}{q_{n+1}}$ and $\frac{p_n}{q_n}$. Thus, the mediant property (Note 3) shows that $\frac{p_n}{q_n}<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<\frac{p_{n+1}}{q_{n+1}}$. Then:

$$\frac{p_n}{q_n}<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}\stackrel{\left(A\right)}{<}\frac{2p_{n+1}+p_n}{2q_{n+1}+q_n}<\cdots <\frac{a_{n+2}{p}_{n+1}+p_n}{a_{n+2}{q}_{n+1}+q_n}\stackrel{\left(B\right)}{=}\frac{p_{n+2}}{q_{n+2}}$$

where (A) follows by the monotony of even semiconvergents (Lemma 4), and (B) is the recursion theorem. Because of Theorem 7 (note that n + 2 is even and n + 1 is odd), it is $\frac{p_{n+2}}{q_{n+2}}<x<\frac{p_{n+1}}{q_{n+1}}$. This proves Claim 1.${\square }_{\left(claim1\right)}$

Claim 2.

n odd ⇒ $\frac{p_{n-1}}{q_{n-1}}<x<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<\frac{p_n}{q_n}$.

Proof. 

As before, $\frac{p_{n+1}+p_n}{q_{n+1}+q_n}$ is the mediant of $\frac{p_{n+1}}{q_{n+1}}$ and $\frac{p_n}{q_n}$. Because n is odd, it is $\frac{p_{n+1}}{q_{n+1}}<\frac{p_n}{q_n}$ (Theorem 7). Thus, $\frac{p_{n+1}}{q_{n+1}}<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<\frac{p_n}{q_n}$ because of the mediant property (Note 3). Then:

$$\frac{p_n}{q_n}>\frac{p_{n+1}+p_n}{q_{n+1}+q_n}\stackrel{\left(A\right)}{>}\frac{2p_{n+1}+p_n}{2q_{n+1}+q_n}>\cdots >\frac{a_{n+2}{p}_{n+1}+p_n}{a_{n+2}{q}_{n+1}+q_n}\stackrel{\left(B\right)}{=}\frac{p_{n+2}}{q_{n+2}}$$

where (A) follows by the monotony of odd semiconvergents (Lemma 4), and (B) is the recursion theorem. Because of Theorem 7 (note that n − 1 is even and n + 2 is odd), it is $\frac{p_{n-1}}{q_{n-1}}<x<\frac{p_{n+2}}{q_{n+2}}$, and because n is odd, it is $\frac{p_{n+2}}{q_{n+2}}<\frac{p_n}{q_n}$. This proves Claim 2. ${\square }_{\left(claim2\right)}$

With Claim 1, for even n, it is $\frac{p_n}{q_n}<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<x$ ⇒ $x-\frac{p_n}{q_n}>\frac{p_n+p_{n+1}}{q_n+q_{n+1}}-\frac{p_n}{q_n}$.

With Claim 2, for n odd, it is $x<\frac{p_{n+1}+p_n}{q_{n+1}+q_n}<\frac{p_n}{q_n}$ ⇒ $\frac{p_n}{q_n}-x>\frac{p_n}{q_n}-\frac{p_n+p_{n+1}}{q_n+q_{n+1}}$ ⇔ $-\left(x-\frac{p_n}{q_n}\right)>-\left(\frac{p_n+p_{n+1}}{q_n+q_{n+1}}-\frac{p_n}{q_n}\right)$.

Thus, for any k ∈ ℕ:$\left|x-\frac{p_k}{q_k}\right|>\left|\frac{p_{k+1}+p_k}{q_{k+1}+q_k}-\frac{p_k}{q_k}\right|$. Next, we compute

$$\begin{array}{cc}\frac{p_k+p_{k+1}}{q_k+q_{k+1}}-\frac{p_k}{q_k}& =\frac{\left(p_k+p_{k+1}\right)q_k-\left(q_k+q_{k+1}\right)p_k}{\left(q_k+q_{k+1}\right)q_k}=\frac{p_{k+1}{q}_k-p_k{q}_{k+1}}{\left(q_k+q_{k+1}\right)q_k}\\ & \stackrel{\left(A\right)}{=}\frac{{\left(-1\right)}^k}{\left(q_k+q_{k+1}\right)q_k}\end{array}$$

where (A) is the sign theorem (Theorem 2).

This implies $\left|x-\frac{p_k}{q_k}\right|>\left|\frac{{\left(-1\right)}^k}{\left(q_k+q_{k+1}\right)q_k}\right|=\frac{1}{\left(q_k+q_{k+1}\right)q_k}$. □

Because of $q_{k+1}>q_k$ (Corollary 1), it is

$$q_k+q_{k+1}<2q_{k+1}\iff \frac{1}{2q_{k+1}}<\frac{1}{q_k+q_{k+1}}\iff \frac{1}{2q_k{q}_{k+1}}<\frac{1}{\left(q_k+q_{k+1}\right)q_k}$$

Using the last inequality in Lemma 5 (Lower Bounds) and using Lemma 3 (Upper Bounds), we obtain the concluding theorem of this section:

In summary, we have proved the following:

Theorem 10.

(Bounds of Approximations by Convergents)

Let$p_k/q_k$ be a convergent of the continued fraction representation of x. Then:

$$\frac{1}{2q_k{q}_{k+1}}<\frac{1}{\left(q_k+q_{k+1}\right)q_k}<\left|x-\frac{p_k}{q_k}\right|<\frac{1}{q_k{q}_{k+1}}<\frac{1}{q_k^2}$$

(24)

 □

2.5. Best Approximations

Our goal is to approximate a real number by a rational number as good as possible while keeping the denominator of the rational number “small”. Keeping the denominator small is important because in practice, every real number can only be given up to a certain degree of precision, and this is achieved by means of a huge denominator and corresponding numerator. i.e., approximating a real number by a rational number with a huge denominator is canonical, but finding a small denominator is a problem.

This is captured by the following:

Definition 5.

A fraction $p/q\in \mathbb{Q}$ is called a best approximation (of the first kind) of $\alpha \in ℝ$:⇔ $\forall c/d\in \mathbb{Q}:d\le q\Rightarrow \left|\alpha -\frac{c}{d}\right|>\left|\alpha -\frac{p}{q}\right|$ (assuming c/d ≠ p/q).

Often, the addition “of the first kind” is omitted. By definition, a best approximation of a real number can only be improved if the denominator of the given approximation is increased.

If p/q is a best approximation of α, then $\left|\alpha -\frac{p}{q}\right|=\frac{1}{q}\left|q\alpha -p\right|$ is small and, thus, $\left|q\alpha -p\right|$ is small. Measuring the goodness of an approximation this way results in the following:

Definition 6.

A fraction $p/q\in \mathbb{Q}$ is called a best approximation of the second kind of $\alpha \in ℝ$:⇔ $\forall c/d\in \mathbb{Q}:d\le q\Rightarrow \left|d\alpha -c\right|>\left|q\alpha -p\right|$ (assuming c/d ≠ p/q).

The question is whether every best approximation is also a best approximation of the second kind. Now, 1/3 is a best approximation of 1/5 because the only possible fractions for c/d, with d ≤ 3 = q, are 0, 1/2, 2/3, and 1, and these numbers satisfy $\left|\frac{1}{5}-\frac{c}{d}\right|>\left|\frac{1}{5}-\frac{1}{3}\right|$.

Next, we observe that $\left|1\cdot \frac{1}{5}-0\right|<\left|3\cdot \frac{1}{5}-1\right|$ with 1 < 3. Thus, with $d=1$ and $q=3$ (i.e., $d<q$) and $\alpha =1/5$, we found a fraction $c/d=0/1$ with $\left|d\alpha -c\right|<\left|q\alpha -p\right|$! As a consequence, although 1/3 is a best approximation of the first kind of 1/5, it is not a best approximation of the second kind.

Thus, not all best approximations of the first kind are best approximations of the second kind. But the reverse holds true:

Lemma 6.

(Every 2nd Kind Best Approximation is a 1st Kind Best Approximation)

If $p/q\in \mathbb{Q}$ is a best approximation of the second kind of $\alpha \in ℝ$, then $p/q$ is also a best approximation of the first kind of α.

Proof (by contradiction).

Assume p/q is not a best approximation of the first kind. Then, $\left|\alpha -\frac{c}{d}\right|\le \left|\alpha -\frac{p}{q}\right|$ for a fraction c/d with d < q. Multiplying both inequations results in $d\left|\alpha -\frac{c}{d}\right|\le q\left|\alpha -\frac{p}{q}\right|$ ⇔ $\left|d\alpha -c\right|\le \left|q\alpha -p\right|$, which is a contradiction because p/q is a best approximation of the second kind. □

The next simple estimation about the distance of two fractions by means of the product of their denominators is often used.

Note 4.

(Distance of Fractions)

Let $\frac{a}{b},\frac{p}{q}\in \mathbb{Q}$ with $\frac{a}{b}\ne \frac{p}{q}$. Then:

$$\left|\frac{p}{q}-\frac{a}{b}\right|\ge \frac{1}{qb}$$

(25)

Proof. 

With $a,p\in \mathbb{Z}$ and $b,q\in \mathbb{N}$, it is $pb-aq\in \mathbb{Z}$. Also, $pb-aq\ne 0$ because otherwise $pb=aq\iff \frac{p}{q}=\frac{a}{b}$ which contradicts the premise. Thus, $\left|pb-aq\right|\in \mathbb{N}$, i.e., $\left|pb-aq\right|\ge 1$. This implies

$$\left|\frac{p}{q}-\frac{a}{b}\right|=\left|\frac{pb-aq}{qb}\right|=\frac{\left|pb-aq\right|}{\left|qb\right|}\ge \frac{1}{qb}$$

where $\left|qb\right|=qb$ because $b,q\in \mathbb{N}$. □

Next, we prove that every best approximation of the second kind is a convergent.

Theorem 11.

(2nd Kind Best Approximations are Convergents)

Let $a/b$ be a best approximation of the second kind of $x\in ℝ$, and let $x=\left[a_0;a_1,\cdots \right]$ be the continued fraction representation of x.

Then $a/b$ is a convergent of x.

Proof. 

Being a best approximation of the second kind of x, $a/b$ satisfies, by definition, $\left|dx-c\right|>\left|bx-a\right|$ for d ≤ b.

Claim 1.

$\frac{a}{b}\ge a_0=x_0$.

Proof (by contradiction).

Assume $\frac{a}{b}<a_0\Rightarrow -a_0<-\frac{a}{b}\Rightarrow x-a_0<x-\frac{a}{b}$; thus, $\left|x-a_0\right|<\left|x-\frac{a}{b}\right|\stackrel{\left(A\right)}{\le }b\left|x-\frac{a}{b}\right|=\left|bx-a\right|$, where (A) holds because $b\in \mathbb{N}$, i.e., 1 ≤ b. This implies $\left|1\cdot x-a_0\right|\le \left|bx-a\right|$, which contradicts $\left|dx-c\right|>\left|bx-a\right|$ for d ≤ b (with $d=1\le b$ and $c=a_0$). This means that $\frac{a}{b}\ge a_0=\frac{a_0}{1}\stackrel{\left(B\right)}{=}\frac{q_0}{q_0}=x_0$, (B) is because of the recursion theorem. ${\square }_{\left(claim1\right)}$

Thus, the geometric situation is as depicted in Figure 9, i.e., $a/b$ is in the grey shaded area being greater than or equal to the convergent $x_0$. This will be refined in what follows.

Next, we proceed with a proof by contradiction assuming that $a/b$ is not a convergent of x.

Assumption. 

$\frac{a}{b}\ne \frac{q_k}{q_k}=x_k$ for $k\in \mathbb{N}$.

According to Claim 1, $\frac{a}{b}\ge a_0=x_0$. Thus, one of the following must hold:

$$(\mathrm{i}) \frac{a}{b}\in \left]\frac{p_{k-1}}{q_{k-1}},\frac{p_{k+1}}{q_{k+1}}\right[ \mathrm{for} \mathrm{k} \ge 1$$

or

$$(\mathrm{ii}) \frac{a}{b}>\frac{p_1}{q_1}=x_1$$

This situation is shown in Figure 10.

Case (1).

If (i) is true, then

$$\left|\frac{a}{b}-\frac{p_{k-1}}{q_{k-1}}\right|<\left|x-\frac{p_{k-1}}{q_{k-1}}\right|\stackrel{\left(Th8\right)}{<}\left|\frac{p_k}{q_k}-\frac{p_{k-1}}{q_{k-1}}\right|\stackrel{\left(C\right)}{=}\frac{1}{q_k{q}_{k-1}}$$

where (Th8) is Theorem 8, Equation (14), and (C) is from Corollary 3, Equation (10). Furthermore, $\left|\frac{a}{b}-\frac{p_{k-1}}{q_{k-1}}\right|\stackrel{\left(D\right)}{\ge }\frac{1}{b{q}_{k-1}}$, with (D) because of Note 4 (Distance of Fractions).

Together, $\frac{1}{b{q}_{k-1}}\le \left|\frac{a}{b}-\frac{p_{k-1}}{q_{k-1}}\right|<\frac{1}{q_k{q}_{k-1}}$ ⇒ $\frac{1}{b}<\frac{1}{q_k}$ ⇒ $b>q_k$ (iii).

Also, if (i) is true, then $\left|x-\frac{a}{b}\right|\ge \left|\frac{p_{k+1}}{q_{k+1}}-\frac{a}{b}\right|\stackrel{\left(E\right)}{\ge }\frac{1}{b{q}_{k+1}}$, where (E) is again using Note 4. This implies $b\left|x-\frac{a}{b}\right|\ge \frac{1}{q_{k+1}}$ ⇒ $\left|bx-a\right|\ge \frac{1}{q_{k+1}}$ (iv).

Lemma 3 (Upper Bounds) tells us that $\left|x-\frac{p_k}{q_k}\right|<\frac{1}{q_k{q}_{k+1}}$ which is equivalent to $q_k\left|x-\frac{p_k}{q_k}\right|<\frac{1}{q_{k+1}}$ ⇔ $\left|q_{k}x-p_k\right|<\frac{1}{q_{k+1}}$ ⇒ $\left|q_{k}x-p_k\right|<\left|bx-a\right|$ (see (iv) just before). Since $q_k<b$ (see (iii) above), this is a contradiction to $a/b$ being a best approximation of the second kind of x. Thus, Case (1) does not occur.

Case (2).

This case is shown in Figure 11. Then, $\left|x-\frac{a}{b}\right|>\left|\frac{p_1}{q_1}-\frac{a}{b}\right|\stackrel{\left(F\right)}{=}\frac{1}{b{q}_1}$, where (F) again uses Note 4. This implies $\left|bx-a\right|>\frac{1}{q_1}\stackrel{\left(G\right)}{=}\frac{1}{a_1}$ (v) with (G) using the recursion theorem.

Now, $x-a_0=\frac{1}{a_1+\frac{1}{a_2+\ddots }}\le \frac{1}{a_1}$, where the last inequality holds because of $\frac{1}{a_2+\ddots }>0$; thus, $\left|x-a_0\right|\le \frac{1}{a_1}\stackrel{\left(H\right)}{<}\left|bx-a\right|$, (H) based on (v) before. This means that $\left|1\cdot x-a_0\right|<\left|bx-a\right|$ with $1\le b$, i.e., $a/b$ is not a best approximation of the second kind of x, which is a contradiction. Thus, Case (2) does not occur either.

Consequently, the assumption is wrong and there is a $k\in \mathbb{N}$ with $\frac{a}{b}=\frac{q_k}{q_k}=x_k$, i.e., $a/b$ is a convergent. □

So, every best approximation of the second kind is a convergent. The next theorem proves the reverse, i.e., that every convergent is a best approximation of the second kind.

Theorem 12.

(Lagrange, 1798—Convergents are 2nd Kind Best Approximations)

Let $p_n/q_n$ be a convergent of $x=\left[a_0;a_1,\cdots ,a_N\right]$, $x\ne a_0+\frac{1}{2}$, and $n\ne 0$. Then, for $d\le q_n$ and $\frac{c}{d}\ne \frac{p_n}{q_n}$ it is $\left|dx-c\right|>\left|q_{n}x-p_n\right|$, i.e., the convergent is a best approximation of the second kind of x.

The cases $x=a_0+\frac{1}{2}$ and $n=0$ are excluded because the convergent $\frac{p_0}{q_0}=\frac{a_0}{1}$ is not a best approximation of the second kind of $x=a_0+\frac{1}{2}$: it is $\left|1\cdot x-\left(a_0+1\right)\right|=\left|a_0+\frac{1}{2}-a_0-1\right|=\frac{1}{2}$ and $\left|1\cdot x-a_0\right|=\left|a_0+\frac{1}{2}-a_0\right|=\frac{1}{2}$, which implies $\left|1\cdot x-\left(a_0+1\right)\right|=\left|1\cdot x-a_0\right|$. Setting $d:=1\le q_0$, $c:=a_0+1$ results in $\left|d\cdot x-c\right|$ = $\left|1\cdot x-\left(a_0+1\right)\right|=\left|1\cdot x-a_0\right|$ = $\left|q_0\cdot x-p_0\right|$. If $\frac{p_0}{q_0}$ would be a best approximation of the second kind of x, then $\left|1\cdot x-\left(a_0+1\right)\right|$ > $\left|1\cdot x-a_0\right|$ would hold.

The proof of Lagrange’s theorem is very technical. First, the expression $\left|y_{0}x-z_0\right|$ is analyzed to find the smallest integral numbers $y_0$ and $z_0$ such that the expression is minimized under the constraint $y_0\in \left\{q_0,\dots ,q_k\right\}$, i.e., $y_0$ is a denominator of a convergent. It is shown both that $z_0/y_0$ is a best approximation of the second kind of x, and that $z_0=p_k$ and $y_0=q_k$.

Proof. 

Let $k\in \mathbb{Z}$ and let $p_k/q_k$ be a convergent. First, we are looking for the smallest numbers $y_0,z_0\in \mathbb{Z}$ with $y_0\in \left\{q_0,\dots ,q_k\right\}$ such that $\left|y_{0}x-z_0\right|$ is minimal.

Step 1.

Pick an arbitrary $z\in \mathbb{Z}$, and based on this we determine $y_0\in \left\{q_0,\dots ,q_k\right\}$.

It is $\underset{y}{min}\left|yx-z\right|=0\iff y=\frac{z}{x}$, but in general $y\notin \mathbb{Z}$. Looking for a solution $y_0\in \left\{q_0,\dots ,q_k\right\}\subseteq \mathbb{Z}$ that minimizes $\left|y_{0}x-z\right|$ results in the following potential positions of $z/x$ with respect to the denominators $q_0,\dots ,q_k$ (see Figure 12):

• Case 1: $z/x>q_k$. Then, $y_0=q_k$ is the solution;
• Case 2: $z/x<q_0$. Then, $y_0=q_0$ is the solution;
  Let $q_i\le z/x\le q_{i+1}$ for 1 ≤ i ≤ k.
• Case 3: For $\left|q_{i+1}x-z\right|<\left|q_{i}x-z\right|$ (i.e., $z/x$ is closer to $q_{i+1}$ than to $q_i$), $y_0=q_{i+1}$ is the solution, and for $\left|q_{i+1}x-z\right|>\left|q_{i}x-z\right|$ (i.e., $z/x$ is closer to $q_i$ than to $q_{i+1}$), $y_0=q_i$ is the solution;
• Case 4: For $\left|q_{i+1}x-z\right|=\left|q_{i}x-z\right|$ (i.e., $z/x$ is exactly in the middle between $q_i$ and $q_{i+1}$), $y_0=q_i$ is the solution because $q_i<q_{i+1}$, and we are looking for the smallest $y_0$, especially $y_0\ge q_0=1$. ${\square }_{\left(step1\right)}$

Step 2.

Based on the $y_0$ found, we determine $z_0$ next. It is $\underset{z}{min}\left|y_{0}x-z\right|=0$ $\iff z=y_{0}x$, but in general, $z\notin \mathbb{Z}$. In solving the minimization problem within $\mathbb{Z}$ (i.e., $z_0:=\underset{z\in \mathbb{Z}}{argmin}\left|y_{0}x-z\right|$), the following cases can be distinguished (see Figure 13):

• Case 0: It may happen that $y_{0}x\in \mathbb{Z}$. Then, choose $z_0=y_{0}x$;
• Case 1: $y_{0}x$ is between two integral numbers s and t, i.e., $s<y_{0}x<t$. For $\left|y_{0}x-s\right|>\left|y_{0}x-t\right|$ (i.e., $y_{0}x$ is closer to t than to s), $z_0=t$ is the solution; and for $\left|y_{0}x-s\right|<\left|y_{0}x-t\right|$ (i.e., $y_{0}x$ is closer to s than to t), $z_0=s$ is the solution;
• Case 2: For $\left|y_{0}x-s\right|=\left|y_{0}x-t\right|$ (i.e., $y_{0}x$ is exactly in the middle between t and s), $z_0=s$ is the solution because $s<t$, and we are looking for the smallest $z_0$. ${\square }_{\left(step2\right)}$

Claim 1.

$z_0$ is uniquely determined.

Proof (by contradiction).

Assume there exists a ${\tilde{z}}_0\in \mathbb{Z}$ with ${\tilde{z}}_0\ne z_0$ and $\left|x-\frac{z_0}{y_0}\right|=\left|x-\frac{{\tilde{z}}_0}{y_0}\right|$. This can only happen iff one term is positive and the other is negative, i.e., for example, if $x-\frac{z_0}{y_0}>0$ and $x-\frac{{\tilde{z}}_0}{y_0}<0$, and then $x-\frac{z_0}{y_0}=\frac{{\tilde{z}}_0}{y_0}-x$, i.e., $x=\frac{z_0+{\tilde{z}}_0}{2y_0}$.

As an intermediate step we prove:

Claim 2.

$z_0+{\tilde{z}}_0$ and $2y_0$ are co-prime, i.e., $gcd\left(z_0+{\tilde{z}}_0,2y_0\right)=1$

Proof (by contradiction).

Let ${\tilde{z}}_0+z_0=Lp$ and $2y_0=Lq$ with $L>1$. Then, $x=\frac{z_0+{\tilde{z}}_0}{2y_0}=\frac{Lp}{Lq}\Rightarrow x=\frac{p}{q}$ and thus

$$(\mathrm{i}) \left|qx-p\right|=\left|q\frac{p}{q}-p\right|=0$$

Assume $L>2$. Then, with $2y_0=Lq$ and $L/2>1$, it follows:

$$(\mathrm{ii}) y_0=\frac{L}{2}q>q$$

Now, $y_0$ has been determined in Step 1 to satisfy $y_0=\underset{y}{argmin} \left|yx-z\right|$ for a given z, especially for $z=p$, i.e., $y_0=\underset{y}{argmin} \left|yx-p\right|$. Because $0=\underset{y}{min }\left|yx-p\right|$ and $\left|qx-p\right|=0$, it must be $q=y_0$. This is a contradiction because $q<y_0$ according to (ii) before. Thus, $1<L\le 2$, i.e., L = 2.

With $L=2$ and $2y_0=Lq$, we get $y_0=q$, which implies. By definition of $z_0$, $\left|qx-p\right|=\left|y_{0}x-p\right|>\left|y_{0}x-z_0\right|$. However, $\left|qx-p\right|=0$ (see (i) above); thus, $0>\left|y_{0}x-z_0\right|$, which is a contraction.${\square }_{\left(claim2\right)}$

We continue the proof of Claim 1: It is $\frac{z_0+{\tilde{z}}_0}{2y_0}=x$ and also $x=\frac{p_N}{q_N}$, i.e., $\frac{z_0+{\tilde{z}}_0}{2y_0}=\frac{p_N}{q_N}$. Because $gcd\left(z_0+{\tilde{z}}_0,2y_0\right)=1$ according to Claim 2, it follows that $p_N=z_0+{\tilde{z}}_0$ and $q_N=2y_0$.

Now, let $N\ge 2$. Then, it is $2y_0=q_N\stackrel{\left(A\right)}{=}{a}_N{q}_{N-1}+q_{N-2}$ ((A) uses the recursion theorem (Theorem 1)), and with Note 1, it is $a_N\ge 2$. Thus, $2y_0\ge 2q_{N-1}+q_{N-2}$ $\Rightarrow y_0\ge q_{N-1}+\frac{q_{N-2}}{2}$ $\Rightarrow q_{N-1}\le y_0-\frac{q_{N-2}}{2}\stackrel{\left(B\right)}{<}{y}_0$ ((B) is because $q_{N-2}>0$). Now:

$$\left|q_{N-1}x-p_{N-1}\right|=\left|q_{N-1}\frac{p_N}{q_N}-p_{N-1}\right|=\frac{1}{q_N}\left|q_{N-1}{p}_N-p_{N-1}{q}_N\right|\stackrel{\left(C\right)}{=}\frac{1}{q_N}=\frac{1}{2y_0}\stackrel{\left(D\right)}{\le }\frac{1}{2}$$

where (C) holds because of the sign theorem and (D) because $y_0\ge 1$ (see the end of the proof of Step 1).

Furthermore,

$$\begin{array}{cc}\left|y_{0}x-z_0\right|=\left|y_0\frac{z_0+{\tilde{z}}_0}{2y_0}-z_0\right|& =\left|\frac{z_0+{\tilde{z}}_0}{2}-z_0\right|=\frac{1}{2}\left|z_0+{\tilde{z}}_0-2z_0\right|\\ & =\frac{1}{2}\left|{\tilde{z}}_0-z_0\right|\stackrel{\left(E\right)}{\ge }\frac{1}{2}\left(iii\right)\end{array}$$

where (E) is true because ${\tilde{z}}_0\ne z_0$ and, thus, $\left|{\tilde{z}}_0-z_0\right|\ge 1$ for integral numbers ${\tilde{z}}_0$ and $z_0$. Together, we obtained $\left|y_{0}x-z_0\right|\ge \frac{1}{2}\ge \left|q_{N-1}x-p_{N-1}\right|$, which is a contradiction to the choice of $y_0$ and $z_0$! This proves Claim 1 for $N\ge 2$.

Now, let $N=1$ and choose $a_1=2$ (based on Note 1, the highest element of a continued fraction is always greater than or equal 2, thus $a_1\ge 2$). Then

$$x=\left[a_0;a_1\right]=\frac{p_1}{q_1}\stackrel{\left(F\right)}{=}\frac{a_1{a}_0+1}{a_1}=\frac{2a_0+1}{2}=a_0+\frac{1}{2}$$

((F) is the recursion theorem) which has been excluded from the theorem.

Thus, let $N=1$ and $a_1>2$. Then

$$\left|1\cdot x-a_0\right|\stackrel{\left(G\right)}{=}\left|q_{0}x-p_0\right|=\left|q_0\frac{p_1}{q_1}-p_0\right|=\frac{1}{q_1}\left|q_0{p}_1-q_1{p}_0\right|\stackrel{\left(H\right)}{=}\frac{1}{q_1}\stackrel{\left(G\right)}{=}\frac{1}{a_1}<\frac{1}{2}$$

where (G) applies the recursion theorem and (H) the sign theorem. Because of (iii), it is $\left|y_{0}x-z_0\right|\ge \frac{1}{2}$, i.e., together, $\left|q_{0}x-p_0\right|<\left|y_{0}x-z_0\right|$ which contradicts the definition of $y_0$ and $z_0$! This proves Claim 1 for $N=1$. ${\square }_{\left(claim1\right)}$

Next, we observe

Claim 3.

$\frac{z_0}{y_0}$ is a best approximation of the second kind of x.

Otherwise: $\left|bx-a\right|\le \left|y_{0}x-z_0\right|$ for an $\frac{a}{b}\ne \frac{z_0}{y_0}$ with $b\le y_0$, which contradicts the definition of $y_0$ and $z_0$!${\square }_{\left(claim3\right)}$

According to Theorem 11, $\frac{z_0}{y_0}$ is a convergent of x, i.e., $\frac{z_0}{y_0}=\frac{p_s}{q_s}$ for an $s\le k$. If $s=k$, the proof is done. Thus, we assume $s<k$.

Claim 4.

For $s<k$, it is $\frac{1}{q_s+q_{s+1}}\ge \frac{1}{q_k+q_{k-1}}$.

Proof. 

$s<k$ ⇒ $s\le k-1$ ⇒ $q_s\le q_{k-1}$ (Corollary 1: denominators are monotonically increasing). Similarly, $s<k$ ⇒ $s+1\le k$ ⇒ $q_{s+1}\le q_k$. Together, this implies $q_k+q_{k-1}\ge q_s+q_{s+1}$. ${\square }_{\left(claim4\right)}$

Next, we get

$$\left|q_{s}x-p_s\right|=q_s\left|x-\frac{p_s}{q_s}\right|\stackrel{\left(I\right)}{>}{q}_s\frac{1}{\left(q_s+q_{s+1}\right)q_s}=\frac{1}{q_s+q_{s+1}}\stackrel{\left(J\right)}{\ge }\frac{1}{q_k+q_{k-1}}$$

where (I) is Lemma 5 (Lower Bounds) and (J) is Claim 4.

Furthermore, $\left|q_{k}x-p_k\right|=q_k\left|x-\frac{p_k}{q_k}\right|\stackrel{\left(K\right)}{<}{q}_k\frac{1}{q_k{q}_{k+1}}=\frac{1}{q_{k+1}}$, where (K) holds because of Lemma 3 (Upper Bounds).

With $\frac{z_0}{y_0}=\frac{p_s}{q_s}$ and the definition of $y_0\left(=q_s\right)$ and $z_0\left(=p_s\right)$ (i.e., the minimizing property), it is $\left|q_{s}x-p_s\right|=\left|y_{0}x-z_0\right|\le \left|q_{k}x-p_k\right|$ ⇒ $\frac{1}{q_k+q_{k-1}}\le \frac{1}{q_{k+1}}$, which implies $q_{k+1}<q_k+q_{k-1}$. This is a contradiction; because of the recursion theorem, it is $q_{k+1}=a_{k+1}{q}_k+q_{k-1}\stackrel{\left(L\right)}{\ge }{q}_k+q_{k-1}$, where (L) holds with $a_k\ge 1$. Thus, $s=k$ which proves the overall theorem. □

Putting the last two theorems together yields:

Corollary 5.

$a/b$ is a best approximation of the second kind of x ⇔ x is a convergent of x. □

According to Theorem 12, every convergent is a best approximation of the second kind, and each best approximation of the second kind is also a best approximation of the first kind (Lemma 6). We keep this observation as:

Note 5.

Every convergent is a best approximation of the first kind. □

But are best approximations of the first kind also always convergents? Not quite: the next theorem proves that a best approximation of the first kind is a convergent or a semiconvergent.

Theorem 13.

(Lagrange, 1798—1st Kind Best Approximations are Convergents or Semiconvergents)

Let $a/b$ be a best approximation of the first kind of $x=\left[a_0;a_1,\cdots ,a_N\right]$. Then$a/b$ is a convergent or a semiconvergent of x.

Proof. 

By definition, it is $\left|x-\frac{c}{d}\right|>\left|x-\frac{a}{b}\right|$ for $\frac{c}{c}\ne \frac{a}{b}$ and $d\le b$.

Claim 1.

$a/b>a_0$.

Otherwise: $\frac{a}{b}\le a_0=\frac{a_0}{1}$; thus, $x-a_0\le x-\frac{a}{b}$. Now, $x-a_0=\frac{1}{a_1+\ddots }>0$; thus, $0<x-a_0\le x-\frac{a}{b}$ ⇒ $\left|x-\frac{a_0}{1}\right|\le \left|x-\frac{a}{b}\right|$. Because $1\le b$, we obtained a contradiction since $a/b$ is a best approximation of the first kind.${\square }_{\left(claim1\right)}$

Claim 2.

$a/b<a_0+1$.

Otherwise: $\frac{a}{b}\ge a_0+1$ and based on the geometric situation depicted in Figure 8, it follows that $\left|x-\frac{a_0+1}{1}\right|\le \left|x-\frac{a}{b}\right|$ with $1\le b$, which contradicts $a/b$ being a best approximation of the first kind.${\square }_{\left(claim2\right)}$

Consequently, $a/b$ lies between $x_0=a_0$ and $x_{-1,1}=a_0+1$ (see Equation (22)), i.e.,

$$x_0=a_0<\frac{a}{b}<a_0+1=x_{-1,1}$$

(26)

and is, thus, covered by the set of intervals defined by the convergents and semiconvergents of x (see Figure 8).

Assumption. 

$a/b$ is neither a convergent nor a semiconvergent.

This results in the following cases:

• Case 1: $a/b$ lies between two semiconvergents $x_{k-1,r}$ and $x_{k-1,r+1}$;
• Case 2: $a/b$ lies between two convergents $x_k$ and $x_{k+2}$;
• Case 3: $a/b$ lies between a convergent and a semiconvergent.

We will show that all three cases lead to a contradiction, i.e., the assumption must be false; thus, the theorem is proven.

Case 1.

$a/b$ lies between $x_{k-1,r}=\frac{r{p}_k+p_{k-1}}{r{q}_k+q_{k-1}}$ and $x_{k-1,r+1}=\frac{\left(r+1\right)p_k+p_{k-1}}{\left(r+1\right)q_k+q_{k-1}}$.

Then,

$$\begin{array}{cc}\hfill \left|\frac{a}{b}-\frac{r{p}_k+p_{k-1}}{r{q}_k+q_{k-1}}\right|<& \mid \frac{\left(r+1\right)p_k+p_{k-1}}{\left(r+1\right)q_k+q_{k-1}}\hfill \\ \hfill & -\frac{r{p}_k+p_{k-1}}{r{q}_k+q_{k-1}}\mid \stackrel{\left(A\right)}{=}\frac{1}{\left(\left(r+1\right)q_k+q_{k-1}\right)\left(r{q}_k+q_{k-1}\right)}\hfill \end{array}$$

where (A) results from the same computation performed in the proof of Lemma 4.

Furthermore, it is

$$(\mathrm{i}) \left|\frac{a}{b}-\frac{r{p}_k+p_{k-1}}{r{q}_k+q_{k-1}}\right|=\frac{\left|a\left(r{q}_k+q_{k-1}\right)-b\left(r{p}_k+p_{k-1}\right)\right|}{b\left(r{q}_k+q_{k-1}\right)}\stackrel{\left(B\right)}{\ge }\frac{1}{b\left(r{q}_k+q_{k-1}\right)}$$

where (B) is seen to be valid as follows: $a\left(r{q}_k+q_{k-1}\right)-b\left(r{p}_k+p_{k-1}\right)\in \mathbb{Z}$ and, thus, $\left|a\left(r{q}_k+q_{k-1}\right)-b\left(r{p}_k+p_{k-1}\right)\right|\in {\mathbb{N}}_0$; if it would be zero, the first modulus in (i) would be zero, i.e., $a/b=x_{k-1,r}$ which contradicts the assumption of the claim, which in turn implies $\left|a\left(r{q}_k+q_{k-1}\right)-b\left(r{p}_k+p_{k-1}\right)\right|\ge 1$.

Together,

$$\frac{1}{b\left(r{q}_k+q_{k-1}\right)}<\frac{1}{\left(\left(r+1\right)q_k+q_{k-1}\right)\left(r{q}_k+q_{k-1}\right)} \Rightarrow \frac{1}{b}<\frac{1}{\left(r+1\right)q_k+q_{k-1}},$$

thus,

$$(\mathrm{ii}) b>\left(r+1\right)q_k+q_{k-1}$$

Because of the monotony of the sequence of semiconvergents ${(x_{s,t})}_t$ (Lemma 4), it is for an odd $k$ (i.e., $k-1$ even) $x_{k-1,r}<x_{k-1,r+1}$ (see the geometric situation in Figure 14);

thus,

$$\left|x-\frac{a}{b}\right|>\left|x-\frac{\left(r+1\right)p_k+p_{k-1}}{\left(r+1\right)q_k+q_{k-1}}\right|$$

But with (ii), it is $\left(r+1\right)q_k+q_{k-1}<b$; thus, $a/b$ is not a best approximation of the first kind to x, which is a contradiction. $k$ even leads to a contradiction too, i.e., Case (1) is not possible ${\square }_{\left(case1\right)}$

Case 2.

$a/b$ lies between $x_k$ and $x_{k+2}$.

Then, $\left|\frac{a}{b}-\frac{p_k}{q_k}\right|<\left|\frac{p_k}{q_k}-\frac{p_{k+2}}{q_{k+2}}\right|\stackrel{\left(C\right)}{=}\frac{a_{k+2}}{q_k{q}_{k+2}}<\frac{1}{q_k{q}_{k+2}}$ where (C) is Equation (11) from Corollary 3, and with Note 4, it is $\left|\frac{a}{b}-\frac{p_k}{q_k}\right|\ge \frac{1}{b{q}_k}$.

Together, $\frac{1}{b{q}_k}<\frac{1}{q_k{q}_{k+2}}$ ⇒ $\frac{1}{b}<\frac{1}{q_{k+2}}$ ⇒ $b>q_{k+2}$. Because of the geometric situation shown in Figure 15, it is $\left|x-\frac{a}{b}\right|>\left|x-\frac{p_{k+2}}{q_{k+2}}\right|$, which is a contradiction to $a/b$ being a best approximation of the first kind to x and $b>q_{k+2}$.${\square }_{\left(case2\right)}$

Case 3.

$a/b$ lies between a convergent and a semiconvergent.

This implies that $a/b$ lies between $x_k$ and $x_{k,1}$ (see Figure 8), otherwise $a/b$ would lie between two semiconvergents, which has already been covered in Case 1.

Thus, $\left|\frac{a}{b}-\frac{p_k}{q_k}\right|<\left|x_k-x_{k,1}\right|$, but

$$\begin{array}{cc}\left|x_k-x_{k,1}\right|& =\left|\frac{p_k}{q_k}-\frac{p_{k+1}+p_k}{q_{k+1}+q_k}\right|=\left|\frac{p_k\left(q_{k+1}+q_k\right)-q_k\left(p_{k+1}+p_k\right)}{q_k\left(q_{k+1}+q_k\right)}\right|\\ & =\left|\frac{p_k{q}_{k+1}-q_k{p}_{k+1}}{q_k\left(q_{k+1}+q_k\right)}\right|\stackrel{\left(D\right)}{=}\frac{1}{q_k\left(q_{k+1}+q_k\right)}\end{array}$$

where (D) is the sign theorem. I.e., it is $\left|\frac{a}{b}-\frac{p_k}{q_k}\right|<\frac{1}{q_k\left(q_{k+1}+q_k\right)}$. As before, with Note 4, it is $\left|\frac{a}{b}-\frac{p_k}{q_k}\right|\ge \frac{1}{b{q}_k}$ ⇒ $\frac{1}{b{q}_k}<\frac{1}{q_k\left(q_{k+1}+q_k\right)}$ ⇒ $b>q_{k+1}+q_k$.

The geometric situation from Figure 16 reveals $\left|x-\frac{a}{b}\right|>\left|x-\frac{p_k+p_{k-1}}{q_k+q_{k-1}}\right|$, which is a contradiction to $a/b$ being a best approximation of the first kind to x and $b>q_{k+1}+q_k$.${\square }_{\left(case3\right)}$ □

Finally, we give a simple criterion that allows us to prove that a given fraction is a convergent of another real number. This theorem is a cornerstone of computing a prime factor with Shor’s algorithm.

Theorem 14.

(Legendre, 1798—Convergent Criterion)

Let $\left|x-\frac{a}{b}\right|<\frac{1}{2b^2}$ ⇒ $a/b$ is a convergent of x.

Proof. 

We show that $a/b$ is a best approximation of the second kind of x. Theorem 11 then proves the claim.

Let $\left|dx-c\right|\le \left|bx-a\right|$ for $\frac{a}{b}\ne \frac{c}{d}$ and $d>0$. We need to prove $d>b$.

Now, $\left|bx-a\right|=b\left|x-\frac{a}{b}\right|<b\frac{1}{2b^2}=\frac{1}{2b}$. This implies $\left|dx-c\right|<\frac{1}{2b}$ ⇔ $d\left|x-\frac{c}{d}\right|<\frac{1}{2b}$ ⇔ $\left|x-\frac{c}{d}\right|<\frac{1}{2db}$. Thus,

$\left|\frac{c}{d}-\frac{a}{b}\right|=\left|\frac{c}{d}-x+x-\frac{a}{b}\right|\le \left|\frac{c}{d}-x\right|+\left|x-\frac{a}{b}\right|<\frac{1}{2db}+\frac{1}{2b^2}=\frac{b+d}{2d{b}^2}$

With Note 4 (Distance of Fractions), it is also $\left|\frac{c}{d}-\frac{a}{b}\right|\ge \frac{1}{db}$. Together, it is

$$\frac{1}{db}<\frac{b+d}{2d{b}^2} \iff 1<\frac{b+d}{2b} \iff 2b<b+d \iff d>b.\hspace{1em}\square$$

3. Probability of the Occurrence of Convergents

3.1. Estimating Secant Lengths

In this part, we use the main arguments of [2].

In order to estimate the probability of the occurrence of a certain state after having performed the quantum Fourier transform, we need the following estimation of a lower bound and an upper bound of the length of a secant of the unit circle:

Lemma 7.

(Secant Length Estimation)

If $\phi \in \left[-\pi ,\pi \right]$ then $\frac{2\left|\phi \right|}{\pi }\le \left|1-e^{i\phi }\right|\le \left|\phi \right|$.

Proof. 

The upper bound follows from elementary geometry, namely that the length of a secant is less than or equal to the length of the corresponding arc of a circle (see Figure 17).

The length of the arc determined by the angle φ on a circle of radius r is $r\phi$, i.e., if the circle is a unit circle, the length of the arc (green in the Figure) is $\phi$.

A secant of the unit circle (red in the Figure 17) can be defined by the two complex numbers on the unit circle (black in the Figure 17) that are the endpoints of the secant. Thus, the length of this secant is the difference of these complex numbers. One of these points can always be 1 because a corresponding rotation is length-preserving; the other point is then $e^{i\phi }$, where $\phi$ is the angle of the arc cut by the secant. The length of this secant is then $\left|1-e^{i\phi }\right|$.

This proves the inequality $\left|1-e^{i\phi }\right|\le \left|\phi \right|$.${\square }_{\left(upperbound\right)}$

Next, we compute

$$\begin{array}{cc}\left|1-e^{i\phi }\right|& \stackrel{\left(A\right)}{=}\left|1-cos\phi -isin\phi \right|\stackrel{\left(B\right)}{=}\sqrt{{\left(1-cos\phi \right)}^2+si{n}^2\phi }\\ & =\sqrt{1-2cos\phi +co{s}^2\phi +si{n}^2\phi }=\sqrt{2-2cos\phi }\\ & =\sqrt{2}\sqrt{1-cos\phi }\stackrel{\left(C\right)}{=}\sqrt{2}\sqrt{2si{n}^2\frac{\phi }{2}}\\ & \stackrel{\left(D\right)}{=}2sin\frac{\phi }{2} \end{array}$$

where (A) uses Euler’s formula, (B) is the definition of the modulus of a complex number with $Re=1-cos \phi$ and $Im=-sin \phi$, (C) is the double-angle formula, and (D) assumes that $sin\frac{\phi }{2}\ge 0$.

To estimate a lower bound for $sin\frac{\phi }{2}$, we analyze the function $f\left(x\right)=sin x-\frac{2x}{\pi }$. From elementary calculus, it is known that a function $\psi$ is concave on $D\subseteq ℝ$ if and only if its second derivative is not positive on D, i.e., ${\psi }^{″}\le 0$ on D.

(Reminder: $\psi$ is concave on D:⇔ $\forall x,y\in D\forall t\in \left[0,1\right]:\psi \left(tx+\left(1-t\right)y\right)\ge t\psi \left(x\right)+\left(1-t\right)\psi \left(y\right)$,

I.e., for any two points on the graph of $\psi$, the secant between these points is below the graph, Figure 18).

With $d^{2}sin x/d{x}^2=-sin x\le 0$ especially for $x\in \left[0,\pi /2\right]$, i.e., $sin x$ is concave on $x\in \left[0,\pi /2\right]$. Thus, the secant between $sin 0=0$ and $sin\frac{\pi }{2}=1$ is below the graph of $sin x$ (orange in Figure 18). However, this secant is given by $g\left(x\right)=\frac{2}{\pi }x$ (green in Figure 18). Thus, it is $\frac{2}{\pi }x\le sinx$ for $x\in \left[0,\pi /2\right]$, i.e., with $\phi :=2x$ we get $\frac{\phi }{\pi }\le sin\frac{\phi }{2}$ for $\phi \in \left[0,\pi \right]$, and this implies $2\frac{\phi }{\pi }\le 2sin\frac{\phi }{2}$ for $\phi \in \left[0,\pi \right]$.

Now, $\left|1-e^{i\phi }\right|=2sin\frac{\phi }{2}$ (see the computation before) implies $\left|1-e^{i\phi }\right|\ge 2\frac{\phi }{\pi }$ for $\phi \in \left[0,\pi \right]$.

Furthermore, $sin x$ is convex on $x\in \left[-\pi /2,0\right]$; thus, an argument analogous to the above shows that $\left|1-e^{i\phi }\right|\ge 2\frac{\left|\phi \right|}{\pi }$ for $\phi \in \left[-\pi ,\pi \right]$.${\square }_{\left(lowerbound\right)}$ □

3.2. Estimating Amplitude Parameters

As stated in the introduction, the quantum part of Shor’s algorithm produces in its final step the following quantum state via a measurement:

$$\frac{1}{\sqrt{NA}}\stackrel{A-1}{\sum _{j=0}}{\omega }_N^{jpy}|y⟩$$

(27)

Thus, according to the Born rule, the probability $P\left(y\right)$ of this particular state |y⟩ is the square of the modulus of the amplitude of |y⟩, i.e.,

$$P\left(y\right)={\left|\frac{1}{\sqrt{NA}}\stackrel{A-1}{\sum _{j=0}}{\omega }_N^{jpy}\right|}^2=\frac{1}{NA}{\left|{\displaystyle \sum }_{j=0}^{A-1}{\omega }_N^{jpy}\right|}^2$$

(28)

The argument of the modulus is a geometric sum $\sum q^j$ with $q={\omega }_N^{py}=e^{\frac{2\pi i}{N}py}$; thus, in case $q\ne 1$,

$$P\left(y\right)=\frac{1}{NA}{\left|{\displaystyle \sum }_{j=0}^{A-1}{q}^j\right|}^2=\frac{1}{NA}{\left|\frac{1-q^A}{1-q}\right|}^2$$

(29)

With $q^A=e^{\frac{2\pi i}{N}Apy}$. In this section, in order to compute a lower bound for $P\left(y\right)$, we investigate some relations between the following parameters appearing in Equation (28):

• n: the number to be factorized;
• N: a power of 2 (e.g., $N=2^m$) with $n^2<N<2n^2$;
  • the choice of N effectively determines the domain of numbers that can be represented in the $|a⟩$-part of the quantum register (see Equation (1)).
• p: the period of the modular exponentiation function $f\left(x\right)=a^x mod n$;
• A: the number of arguments mapped to a given value of $f$.

We also estimate bounds of the argument $2\pi \frac{Apy}{N}$ of $q^A=e^{\frac{2\pi i}{N}Apy}$.

3.2.1. Basics from Number Theory

For convenience, we state the definition of the modulo function.

Definition 7.

The modulo function is the following map:

$$\begin{array}{cc}mod:{\mathbb{N}}_0\times \mathbb{N}& \to \mathbb{N}\\ \left(z,n\right)& \mapsto z-\lfloor \frac{z}{n}\rfloor n\stackrel{\underset{def}{}}{=}z mod n\end{array}$$

(30)

$z mod n$ is, thus, the residue left when dividing z by n. I.e., if $r=z mod n$, then there is a number $k\in {\mathbb{N}}_0$ such that $z=kn+r$ with $0\le r<n$.

If $z mod n=\tilde{z} mod n=r$, we find numbers $k_1$ and $k_2$ such that $z=k_{1}n+r$ and $\tilde{z}=k_{2}n+r$ with $0\le r<n$. This implies that $z-\tilde{z}=\left(k_1-k_2\right)n=:kn$, i.e., n is a divisor of $z-\tilde{z}$ (in symbols: $n|\left(z-\tilde{z}\right)$). We also obtain that $z mod n=\tilde{z} mod n$ implies that $\tilde{z}=z+kn$.

The equation $z mod n=\tilde{z} mod n$ is abbreviated as $z\equiv \tilde{z} \left(mod n\right)$; in words, $z$ is congruent $\tilde{z}$ modulo n. As shown just before, $z\equiv \tilde{z} \left(modn \right)$ is equivalent to $n|\left(z-\tilde{z}\right)$ and to $\tilde{z}=z+kn$. We keep this as

Note 6.

 

$z\equiv \tilde{z} \left(mod n\right)$ ⇔ $n|\left(z-\tilde{z}\right)$ ⇔ $\tilde{z}=z+kn$. □

Furthermore, we state the definition of modular exponentiation which turns out to play a key role in finding factors.

Definition 8.

 

For $0<a<n$, the modular exponentiation function is the following map:

$$\begin{array}{cc}f:{\mathbb{N}}_0& \to {\mathbb{N}}_0\\ x& \mapsto a^x mod n\end{array}$$

(31)

The smallest number p that satisfies $f\left(x\right)=f\left(x+p\right)$ for all x is called the period of f. Especially, with $x=0$, we get $f\left(0\right)=f\left(p\right)$ which means that $a^p mod n=a^0 modn=1 mod n$, i.e., $a^p\equiv 1 \left(mod n\right)$ which in turn is equivalent to $n|\left(a^p-1\right)$. Thus, we have proven:

Note 7.

 

$f\left(x\right)=a^{x}modn$ has period p ⇔ $a^p\equiv 1\left(modn\right)$ ⇔ $n|\left(a^p-1\right)$. □

Finding a factor of n can be achieved by finding the period p of the function $f\left(x\right)=a^{x}modn$. This is seen as follows: Let p be the period of $f$, then $n|\left(a^p-1\right)$, i.e., $\left(a^p-1\right)=kn$. Assume p is even (if p is odd, Shor’s algorithm is repeated with a different a, until an even p is found). With such an even p, it is $\left(a^p-1\right)=\left(a^{p/2}-1\right)\left(a^{p/2}+1\right)=kn$ which implies that $\left(a^{p/2}-1\right)$ and $\left(a^{p/2}+1\right)$ have a common divisor, which in turn means that $gcd\left(a^{p/2}-1,n\right)$ or $gcd\left(a^{p/2}+1,n\right)$ is a divisor of n. Thus, if an even period has been determined, classically efficient calculations can be used to compute a factor of n. If this factor is a prime number, we can finish. Otherwise, we continue determining a factor of the former factor, and so on, until we end up with a prime factor of n.

Next, we determine an upper bound of the period p of the modular exponentiation by using group theory. A simple calculation shows that “$\equiv$” is an equivalence relation on $\mathbb{Z}$. The equivalence class of $z\in \mathbb{Z}$ is denoted as $\left[z\right]$ and is referred to as the residue class of z modulo n. It is $\left[z\right]=\left\{\tilde{z}\in \mathbb{Z} |\widetilde{ z}\equiv z \left(mod n\right)\right\}=\left\{z+kn | k\in \mathbb{Z}\right\}$ (see Note 6), where the latter set is sometimes written as $z+n\mathbb{Z}$. The set of all residue classes modulo n is denoted as ${\mathbb{Z}}_n$, i.e., ${\mathbb{Z}}_n=\left\{\left[0\right],\left[1\right],\dots ,\left[n-1\right]\right\}$.

We can multiply two residue classes modulo n as follows: $\left[x\right]\cdot \left[y\right]=\left[x\cdot y\right]$. With this multiplication, ${\mathbb{Z}}_n^{*}=\left\{\left[z\right]\in {\mathbb{Z}}_n | gcd\left(z,n\right)=1\right\}$ becomes a group. Because ${\mathbb{Z}}_n^{*}\subseteq {\mathbb{Z}}_n$, it is $\phi \left(n\right):=card {\mathbb{Z}}_n^{*}\le card {\mathbb{Z}}_n=n$. Since every integer is a divisor of itself, it is $gcd\left(n,n\right)=n\ne 1$ (for $n\ge 2$), i.e., the cardinality of numbers co-prime to n is less than n: $n\ge 2\Rightarrow \phi \left(n\right)<n$.

The well-known Lagrange’s theorem from group theory states that for a group G with $card G=m<\infty$ and for each $x\in G$, it is $x^m=e$ (e is the unit element of G)—see Lemma 3.2.5 in [3], for example. Thus, for $x\in {\mathbb{Z}}_n^{*}$, it is $x^{\phi \left(n\right)}=1$, i.e., $x^{\phi \left(n\right)}\equiv 1 \left(mod n\right)$. Since the period p is the smallest number with $x^p\equiv 1 \left(mod n\right)$, it follows that $p\le \phi \left(n\right)$ and, thus, $p<n$.

Now, the assumption of Shor’s algorithm is that $0<a<n$ and that $gcd\left(a,n\right)=1$, which ensures that $\left[a\right]\in {\mathbb{Z}}_n^{*}$; thus, ${[a]}^p\equiv 1 \left(mod n\right)$ and $p<n$.

Lemma 8.

 

Let p be the period of $f\left(x\right)=a^x mod n$. Then, $p<n$. □

3.2.2. Intervals of Consecutive Multiples of the Period

The relation between N and p is depicted in Figure 19; multiples of N are always contained in closed intervals defined by consecutive multiples of p, i.e., it may happen that a multiple of N coincides with a multiple of p.

Note 8.

$$\forall k\in \mathbb{N}\exists t\in \mathbb{N}:\left(t-1\right)p\le kN\le tp.$$

Proof. 

Pick an arbitrary $k\in \mathbb{N}$, i.e., $kN\in \mathbb{N}$ is also given. Then, we find a $\tilde{t}\in \mathbb{N}$ such that $\tilde{t}p\ge kN$ (trivial because $p>0$). Let $t$ be the smallest of such $\tilde{t}$, i.e., $t\stackrel{\underset{def}{}}{=}min\left\{\tilde{t}|\tilde{t}p\ge kN\right\}$. Thus, $\left(t-1\right)p\le kN$ because otherwise $\left(t-1\right)p>kN$, which is a contradiction because t was chosen minimal.

Together, $\left(t-1\right)p\le kN\le tp$. The claim follows because k an arbitrary number. □

The situation we just discussed is shown in Figure 20.

Furthermore, two different multiples of N are in different intervals defined by succeeding multiples of p. Otherwise, the situation of Figure 21 would imply that $N\le p$, which is a contradiction as shown by the proof of Note 9 below.

We denote a $t$ with $\left(t-1\right)p\le kN\le tp$ by $t_k$. This is justified by the next Note 9 which proves that such a $t$ is uniquely determined by $k$. Especially, a multiple $kN$ is contained in “its” interval:

$$\forall k\in \mathbb{N}\exists t_k\in \mathbb{N}:kN\in \left[\left(t_k-1\right)p,t_{k}p\right]$$

(32)

Note 9.

 

Let $k\in \mathbb{N}$ and $t_k\in \mathbb{N}$ with $\left(t_k-1\right)p\le kN\le t_{k}p$.

Then, $r\ne s\in \left\{0,\dots ,p-1\right\}$ implies $t_r\ne t_s$.

Proof (by contradiction).

Assume $r\ne s$ but $t_r=t_s\stackrel{\underset{def}{}}{=}t$ with $\left(t-1\right)p\le rN\le tp$ and $\left(t-1\right)p\le sN\le tp$ (see Figure 20). W.l.o.g. $r<s$ ⇒ $r+1\le s$ ⇒ $sN-rN\ge \left(r+1\right)N-rN=N$. Further, $sN-rN\le tp-\left(t-1\right)p=p$. Together, it is $N\le sN-rN\le p$, i.e., $N<p$.

According to Lemma 8, we know $p<n$ ⇒ $N<p<n<n^2$. However, by selection of N (see the bullet list at the beginning of Section 8), it is $n^2<N$, which is a contradiction. □

The proof of Note 9 has shown especially:

Corollary 6.

$$\begin{gathered} r\ne s\in \left\{0,\dots ,p-1\right\} \Rightarrow rN\notin \left[\left(t_s-1\right)p,t_{s}p\right] \\ \square \end{gathered}$$

By Note 9, for $r\ne s\in \left\{0,\dots ,p-1\right\}$, the numbers $t_r,t_s$ are different, i.e., for each $k\in \left\{0,\dots ,p-1\right\}$, such a unique $t_k$ exists, i.e., the $p$ numbers $t_0,t_1,\dots ,t_{p-1}$ are different. Thus:

Corollary 7.

 

There exist p different numbers $t_k$, $0\le k\le p-1$, such that $\left(t_k-1\right)p\le kN\le t_{k}p$. □

These different numbers are strictly monotonically increasing.

Note 10.

 

Let $k\in \mathbb{N}$ and $t_k\in \mathbb{N}$ with $\left(t_k-1\right)p\le kN\le t_{k}p$. Then, $t_k<t_{k+1}$. Thus, $t_0<t_1<\dots <t_{p-1}$.

Proof (by contradiction).

Assume $t_{k+1}\le t_k$; thus, $t_{k+1}-1\le t_k-1$, which implies $t_{k+1}p\le t_{k}p$ and $\left(t_{k+1}-1\right)p\le \left(t_k-1\right)p$.

Now, $kN<\left(k+1\right)N$, $\left(t_k-1\right)p\le kN\le t_{k}p$, and $\left(t_{k+1}-1\right)p\le \left(k+1\right)N\le t_{k+1}p$. This implies $\left(k+1\right)N\le t_{k+1}p\le t_{k}p$ and $\left(t_k-1\right)p\le kN<\left(k+1\right)N$, which finally results in $\left(t_k-1\right)p<\left(k+1\right)N\le t_{k}p$—which is a contradiction to corollary 6 because this would imply that $\left(k+1\right)N\in \left[\left(t_k-1\right)p,t_{k}p\right]$. □

Each multiple $kN$ of N is “close” to a multiple $tp$ in the sense that $kN$ is at most $p/2$ apart from $\left(t_k-1\right)p$ or $t_{k}p$ (see Figure 22).

More precisely:

Note 11.

$$\forall k\in \mathbb{N}\exists t\in \mathbb{N}:\left|\left(t-1\right)p-kN\right|\le \frac{p}{2}\vee \left|tp-kN\right|\le \frac{p}{2}.$$

Proof. 

It is $\left(t-1\right)p\le kN\le tp$, i.e., by definition $kN\in \left[\left(t-1\right)p,tp\right]$. This implies $kN-\left(t-1\right)p\le \frac{p}{2}$ ∨ $tp-kN\le \frac{p}{2}$ (see Figure 22), otherwise:

$$kN-\left(t-1\right)p>\frac{p}{2}\wedge tp-kN>\frac{p}{2}\iff -\left(t-1\right)p>\frac{p}{2}-kN\wedge tp>\frac{p}{2}+kN$$

⇒ $tp-\left(t-1\right)p>\frac{p}{2}-kN+\frac{p}{2}+kN=p$, but $tp-\left(t-1\right)p=p$, i.e., $p>p$, which is a contradiction! This proves the claim $\left|\left(t-1\right)p-kN\right|\le \frac{p}{2}\vee \left|tp-kN\right|\le \frac{p}{2}$. □

As before, from Note 9, it follows that for $k\in \left\{0,\dots ,p-1\right\}$, these numbers t are all different. Precisely:

Corollary 8.

 

Let $0\le k\le p-1$ and $t_k\in \mathbb{N}$ such that $\left|\left(t_k-1\right)p-kN\right|\le \frac{p}{2}\vee \left|t_{k}p-kN\right|\le \frac{p}{2}$. If $r\ne s$, then $t_r\ne t_s$. □

The multiples of N are sparsely scattered across the intervals of consecutive multiples of p. More precisely, intervals of consecutive multiples of p, which contain a multiple of N, are not consecutive. This is the content of

Note 12.

 

Let $n>2$, $k\in \left\{0,\dots ,p-1\right\}$, and $t_k\in \mathbb{N}$ with $\left(t_k-1\right)p\le kN\le t_{k}p$.

Then $t_{k+1}>t_k+1$ as well as $t_{k-1}<t_k-1$.

Proof. 

Because of Note 10, it is $t_{k+1}>t_k$; thus, $t_{k+1}\ge t_k+1$.

Assumption. 

$t_{k+1}=t_k+1$.

By definition, $\left(k+1\right)N\in \left[\left(t_{k+1}-1\right)p,t_{k+1}p\right]$, and by assumption, $t_{k+1}=t_k+1$; thus, it is $\left(k+1\right)N\in \left[t_{k}p,\left(t_k+1\right)p\right]$. Furthermore, by definition, $kN\in \left[\left(t_k-1\right)p,t_{k}p\right]$ (see Figure 23).

Now, $\left[\left(t_k-1\right)p,t_{k}p\right],\left[t_{k}p,\left(t_k+1\right)p\right]\subseteq \left[\left(t_k-1\right)p,\left(t_k+1\right)p\right]$ which implies $kN,\left(k+1\right)N\in \left[\left(t_k-1\right)p,\left(t_k+1\right)p\right]$.

Thus, $N=\left(k+1\right)N-kN\le \left(t_k+1\right)p-\left(t_k-1\right)p=2p$, i.e., $N\le 2p$ (see Figure 23).

By Lemma 8, it is $p<n$ ⇒ $2p<2n$. With $n>2$ ⇒ $n^2>2n$ and by definition of N, it is $n^2<N$; thus, $N>n^2>2n>2p$: a contradiction!

Thus, the assumption is false, which implies $t_{k+1}>t_k+1$. The claim $t_{k-1}<t_k-1$ is proven similarly. □

The resulting geometric situation is depicted in Figure 24.

If $kN\in \left[\left(t_k-1\right)p,t_{k}p\right]$, it is $t_{k}p-kN\le p/2$ or $kN-\left(t_k-1\right)p\le p/2$ (see Figure 22 or Figure 24). In case $kN-\left(t_k-1\right)p\le p/2$, we define $\widehat{t}:=t_k-1$ and $kN-\hat{t}p\le p/2$ results, and in case of $t_{k}p-kN\le p/2$, we define $\widehat{t}:=t_k$ implying $\widehat{t}p-kN\le p/2$. According to Note 9, this $\widehat{t}$ is uniquely defined. This proves

Note 13.

 

$\forall k\in \mathbb{N} \exists !\widehat{t}\in \mathbb{N}:\left|\widehat{t}p-kN\right|\le \frac{p}{2}$, i.e., $\widehat{t}$ is uniquely determined by $k$. □

This is next rewritten into a format more useful for what follows.

Note 14.

 

Let $k\in \left\{0,\dots ,p-1\right\}$ and $t_k\in \mathbb{N}$ with $t_k\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$.

If $r\ne s\in \left\{0,\dots ,p-1\right\}$, then $t_r\ne t_s$.

Proof. 

It is $t_k\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ ⇔$k\frac{N}{p}-\frac{1}{2}\le t_k\le k\frac{N}{p}+\frac{1}{2}$⇔$kN-\frac{p}{2}\le p{t}_k\le kN+\frac{p}{2}$ ⇔$-\frac{p}{2}\le p{t}_k-kN\le \frac{p}{2}$ ⇔ $\left|p{t}_k-kN\right|\le \frac{p}{2}$. Note 13 shows that $t_k$ is uniquely determined by $k$. □

Finally, we can prove the following:

Corollary 9.

 

There exist p different numbers $t_k$, $0\le k\le p-1$, such that

$$t_k\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$$

Proof. 

There exist p different numbers $t_k$, $0\le k\le p-1$, such that $\left(t_k-1\right)p\le kN\le t_{k}p$ (Corollary 7). The proof of Note 11 shows that this implies $\left|\left(t_k-1\right)p-kN\right|\le \frac{p}{2}\vee \left|t_{k}p-kN\right|\le \frac{p}{2}$. The proof of Note 14 shows that this implies $t_k\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$. □

3.2.3. Cardinality of Pre-Images

First, we show that the parameter A is greater than 1, i.e., at least two numbers available in the $|a⟩$-part of the quantum register are mapped by f to the same value.

Note 15.

$$A>1.$$

Proof. 

As reminded in the introduction, the quantum Fourier transform of Shor’s algorithm produces the following state:

$$\left|a⟩\right|b⟩=\frac{1}{\sqrt{N}}\stackrel{N-1}{\sum _{x=0}}\left|x⟩\right|f\left(x\right)⟩$$

After measurement of the $|b⟩$-part of the register, the $|a⟩$-part is in the state

$$|a⟩=\frac{1}{\sqrt{A}}\left(\left|x⟩+\right|x+p⟩+\left|x+2p⟩+\cdots +\right|x+\left(A-1\right)p⟩\right)$$

(33)

i.e., $f^{-1}(|x⟩)=\left\{\left|x⟩,\right|x+p⟩,\left|x+2p⟩,\cdots ,\right|x+\left(A-1\right)p⟩\right\}$.

Choose $x<p$—such an x exists because otherwise it would be $p=0$, but a period p satisfies $p>0$. With $p<n$ (Lemma 8) and $n<n^2<N$ (by choice of N), it is $x+p<2p<N$ (see the proof of Note 12). Thus, $x+p$ is in the domain of f (in the sense that it is a value in the $|a⟩$-part of the quantum register available as an argument for f), i.e., $f\left(x+p\right)$ is available in the $|b⟩$-part of the register.

$A=1$ would imply that $f^{-1}(|x⟩)=\left\{|x⟩\right\}$ and, thus, $|x+p⟩\notin f^{-1}(|x⟩)$, i.e., $f(|x⟩)\ne f(|x+p⟩)$ for $p\ne 0$. Since $p>0$, the function $f$ would not be periodic. □

Next, we prove tighter bounds for the parameter A.

Note 16.

$$\left(A-1\right)p<N<\left(A+1\right)p.$$

Proof. 

As in the proof of Note 15, we choose $x<p$. With

$$\left|a\right.=\frac{1}{\sqrt{A}}\left(\left|x\right.+\left|x+p\right.+\left|x+2p\right.+\cdots +\left|x+\left(A-1\right)p\right.\right),$$

i.e., $\left\{\left|x⟩,\right|x+p⟩,\left|x+2p⟩,\cdots ,\right|x+\left(A-1\right)p⟩\right\}$ are all values in the $|a⟩$-part of the register being mapped to $f\left(x\right)$, i.e., $A$ is the largest number satisfying $x+\left(A-1\right)p<N$. With $x\ge 0$, this implies $\left(A-1\right)p<N$—which is the first part of the claim.

Thus, $\left(A+1\right)p>N$. Otherwise, $\left(A+1\right)p\le N$ and with $x<p$, it would be $x+Ap<p+Ap=\left(A+1\right)p\le N$, i.e., $|x+Ap⟩$ would also be in the $|a⟩$-part of the register being mapped to $f\left(x\right)$, which is a contradiction to the definition of A. This proves the second part of the claim. □

The next estimation gives an approximation of $N$ in terms of the product of $A$ and $p$.

Note 17.

$$N\approx Ap.$$

Proof. 

Because of $\left(A-1\right)p<N<\left(A+1\right)p$, the geometric situation is as depicted in Figure 25, i.e., $N\in \left[\left(A-1\right)p,Ap\right]$ or $N\in \left[Ap,\left(A+1\right)p\right]$. Thus, $\left|N-Ap\right|\le p$.

Now, $p<n$ (Lemma 8) and $n<n^2<N$ by choice of N. In practice, n is a large number, i.e., $n^2$ is huge compared to n: $n\ll n^2<N$. Together:

$$p\ll N$$

(34)

In this sense, $p$ is a small number, i.e., $\left|N-Ap\right|$ is small too: $N\approx Ap$. □

3.2.4. Estimating Arguments of Amplitudes of Potential Measurement Results

The next Lemma is the main result of this section for what follows.

Lemma 9.

 

Let $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ and $k\in \left\{0,\dots ,p-1\right\}$. Then:

$$2\pi \frac{y\left(A-1\right)p}{N},2\pi \frac{py}{N}\in \left[-\pi ,+\pi \right]$$

Proof. 

It is $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ ⇔ $k\frac{N}{p}-\frac{1}{2}\le y\le k\frac{N}{p}+\frac{1}{2}$ ⇔ (multiply with p) $kN-\frac{p}{2}\le py\le kN+\frac{p}{2}$ ⇔ $-\frac{p}{2}\le py-kN\le \frac{p}{2}$ ⇔

$$(\mathrm{i}) yp-kN\le \frac{p}{2}\wedge kN-yp\le \frac{p}{2}$$

By Note 16, it is

$$(\mathrm{ii}) \left(A-1\right)p<N \Rightarrow \frac{\left(A-1\right)p}{N}<1$$

Furthermore:

$$(\mathrm{iii}) \frac{\left(A-1\right)p}{N}=\frac{Ap}{N}-\frac{p}{N}\stackrel{\left(A\right)}{\approx }\frac{N}{N}-\frac{p}{N}=1-\frac{p}{N}\stackrel{\left(B\right)}{\approx }1$$

where (A) is because of Note 17 ($N\approx Ap$), and (B) is because of Equation (34) ($p\ll N$).

Next, we compute the lower bound for the first fraction of the claim:

$$\begin{array}{cc}2\pi \frac{y\left(A-1\right)p}{N}& =2\pi \frac{\left(A-1\right)}{N}yp\\ & \stackrel{\left(C\right)}{\ge }2\pi \frac{\left(A-1\right)}{N}\left(kN-\frac{p}{2}\right)\\ & =2\pi \left(A-1\right)k-\pi \frac{\left(A-1\right)p}{N}\\ & \stackrel{\left(D\right)}{\ge }-\pi \frac{\left(A-1\right)p}{N}\stackrel{\left(E\right)}{\approx }-\pi \end{array}$$

where (C) follows from the second inequation of (i) above, (D) is because of $2\pi \left(A-1\right)k\ge 0$, and (E) is implied by (iii) above.

The upper bound for the first fraction of the claim is computed next:

$$\begin{array}{cc}2\pi \frac{y\left(A-1\right)p}{N}& =2\pi \frac{\left(A-1\right)}{N}yp\stackrel{\left(F\right)}{\le }2\pi \frac{\left(A-1\right)}{N}\left(kN+\frac{p}{2}\right)\\ & =2\pi \left(A-1\right)k+\pi \frac{\left(A-1\right)p}{N}\stackrel{\left(G\right)}{<}2\pi \left(A-1\right)k+\pi \\ & \stackrel{\left(H\right)}{<}2\pi \left(A-1\right)p+\pi \stackrel{\left(I\right)}{<}2\pi N+\pi \stackrel{\left(J\right)}{\equiv }\pi \end{array}$$

where (F) is implied by the first inequation of (i) above, (G) is (ii) above, (H) follows from the prerequisite $k\in I\left\{0,\dots ,p-1\right\}$, i.e., $k<p$, and (I) is the first inequation of (ii) above. Finally, we will estimate $e^{i\phi }$, and because of $e^{i2\pi N}=1$, (J) is justified.

Together, $-\pi \le 2\pi \frac{y\left(A-1\right)p}{N}\le \pi$, which proves the first claim.${\square }_{\left(firstfraction\right)}$

Next,

$$\begin{array}{cc}2\pi \frac{py}{N}& =\frac{2\pi }{N}py\stackrel{\left(K\right)}{\le }\frac{2\pi }{N}\left(kN+\frac{p}{2}\right)\\ & =2\pi k+\pi \frac{p}{N}\stackrel{\left(L\right)}{<}2\pi k+\pi \stackrel{\left(M\right)}{\equiv }\pi \end{array}$$

with (K) from the first inequation of (i) before, (L) because $p<N$, and (M) because we will estimate $e^{i\phi }$. I.e., the upper bound of the second fraction is as claimed.

The correctness of the lower bound is seen as follows:

$$\begin{array}{cc}2\pi \frac{py}{N}& =\frac{2\pi }{N}py\stackrel{\left(N\right)}{\ge }\frac{2\pi }{N}\left(kN-\frac{p}{2}\right)\\ & =2\pi k-\pi \frac{p}{N}\stackrel{\left(O\right)}{>}-\pi \frac{p}{N}\stackrel{\left(Q\right)}{>}-\pi \end{array}$$

with the second inequation of (i) before giving (N), (O) is because of $2\pi k>0$, and (Q) is true because $0<p<N$; thus, $0<p/N<1$. ${\square }_{\left(secondfraction\right)}$ □

3.3. Estimating Probabilities

We are now ready to compute the probability $P\left(y\right)$ that the state |y⟩, which is prepared by the quantum part of Shor’s algorithm, is “close” (i.e., within a distance of $1/2$) to a multiple of $p/N$.

Lemma 10.

 

Assume $q=e^{i2\pi \frac{yp}{N}}\ne 1$ and let P be the probability that $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ for a $k\in \left\{0,\dots ,p-1\right\}$. Then, $P\approx \frac{4}{{\pi }^2}$.

Proof. 

According to Equation (29), the probability $P\left(y\right)$ to measure a particular $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ is

$$P\left(y\right)=\frac{1}{NA}{\left|\frac{1-q^A}{1-q}\right|}^2$$

(35)

In case $q\ne 1$ (which is the assumption) where $q=e^{i2\pi \frac{yp}{N}}$ (the case $q=1$ will be treated separately in Note 18). Thus, with $q^A=e^{i2\pi \frac{yAp}{N}}$, it is

$$\left|\frac{1-q^A}{1-q}\right|=\frac{\left|1-q^A\right|}{\left|1-q\right|}=\frac{\left|1-e^{i2\pi \frac{yAp}{N}}\right|}{\left|1-e^{i2\pi \frac{yp}{N}}\right|}$$

(36)

The structure of the numerator and denominator recommends the estimation of both by means of the Lemma 7 (Secant Length Estimation). However, applying Lemma 7 requires that $2\pi \frac{yAp}{N},2\pi \frac{yp}{N}\in \left[-\pi ,+\pi \right]$. By Lemma 9, we know that under the prerequisite $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$, it is $2\pi \frac{py}{N}\in \left[-\pi ,+\pi \right]$ as well as$2\pi \frac{y\left(A-1\right)p}{N}\in \left[-\pi ,+\pi \right]$, but Lemma 9 does not imply $2\pi \frac{yAp}{N}\in \left[-\pi ,+\pi \right]$.

Now, consider the following calculation:

$$\left|\frac{1-q^A}{1-q}\right|=\left|\frac{1-q^{A-1}}{1-q}+q^{A-1}\right|\stackrel{\left(A\right)}{\ge }\left|\frac{1-q^{A-1}}{1-q}\right|-\left|q^{A-1}\right|\stackrel{\left(B\right)}{=}\left|\frac{1-q^{A-1}}{1-q}\right|-1$$

(37)

where (A) holds because of $\left|a+b\right|\ge \left|a\right|-\left|b\right|$, and $\left|e^{i\phi }\right|=1$ implies (B): $\left|q^t\right|=\left|{\left(e^{i2\pi \frac{yp}{N}}\right)}^t\right|=\left|e^{i\left(2\pi \frac{ypt}{N}\right)}\right|=1$.

Equation (37) allows us to apply the secant length estimation (Lemma 7) because in

$$\left|\frac{1-q^{A-1}}{1-q}\right|=\frac{\left|1-q^{A-1}\right|}{\left|1-q\right|}=\frac{\left|1-e^{i2\pi \frac{y\left(A-1\right)p}{N}}\right|}{\left|1-e^{i2\pi \frac{yp}{N}}\right|}$$

(38)

it is now $2\pi \frac{y\left(A-1\right)p}{N},2\pi \frac{yp}{N}\in \left[-\pi ,+\pi \right]$ according to Lemma 9.

First, we use the second inequation of $\frac{2\left|\phi \right|}{\pi }\le \left|1-e^{i\phi }\right|\le \left|\phi \right|$ from Lemma 7 with $\phi =2\pi \frac{yp}{N}\in \left[-\pi ,+\pi \right]$ and obtain

$$\left|1-e^{i2\pi \frac{yp}{N}}\right|\le 2\pi \frac{yp}{N}$$

(39)

Then, we use the first inequation of $\frac{2\left|\phi \right|}{\pi }\le \left|1-e^{i\phi }\right|\le \left|\phi \right|$ from Lemma 7 with $\phi =2\pi \frac{y\left(A-1\right)p}{N}\in \left[-\pi ,+\pi \right]$ and obtain

$$\left|1-e^{i2\pi \frac{y\left(A-1\right)p}{N}}\right|\ge \frac{2}{\pi }\cdot 2\pi \frac{y\left(A-1\right)p}{N}$$

(40)

Using Equations (39) and (40) in Equation (38) results in

$$\left|\frac{1-q^{A-1}}{1-q}\right|=\frac{\left|1-e^{i2\pi \frac{y\left(A-1\right)p}{N}}\right|}{\left|1-e^{i2\pi \frac{yp}{N}}\right|}\ge \frac{2}{\pi }\cdot 2\pi y\frac{\left(A-1\right)p}{N}\cdot \frac{N}{2\pi yp}=\frac{2\left(A-1\right)}{\pi }$$

(41)

This result is now used in Equation (37) (step (C) below) and we obtain

$$\begin{array}{cc}\left|\frac{1-q^A}{1-q}\right|=\left|\frac{1-q^{A-1}}{1-q}\right|-1& \stackrel{\left(C\right)}{\ge }\frac{2\left(A-1\right)}{\pi }-1\\ & =\frac{2A}{\pi }-\frac{2}{\pi }-1=\frac{2A}{\pi }-\left(\frac{2}{\pi }+1\right)\end{array}$$

(42)

Using Equation (42) in Equation (35) (step (D) below) results in

$$P\left(y\right)=\frac{1}{NA}{\left|\frac{1-q^A}{1-q}\right|}^2\stackrel{\left(D\right)}{\ge }\frac{1}{NA}{\left(\frac{2A}{\pi }-\left(\frac{2}{\pi }+1\right)\right)}^2$$

$$=\frac{1}{NA}\left(\frac{4A^2}{{\pi }^2}-\frac{4A}{\pi }\left(\frac{2}{\pi }+1\right)+{\left(\frac{2}{\pi }+1\right)}^2\right)$$

$$=\frac{1}{NA}\left(\frac{4A^2}{{\pi }^2}-\frac{8A}{{\pi }^2}-\frac{4A}{\pi }+\frac{4}{{\pi }^2}+\frac{4}{\pi }+1\right)$$

$$=\frac{4A}{{\pi }^{2}N}-\frac{8}{{\pi }^{2}N}-\frac{4}{\pi N}+\frac{4}{{\pi }^{2}NA}+\frac{4}{\pi NA}+\frac{1}{NA}$$

$$\ge \frac{4A}{{\pi }^{2}N}-\frac{8}{{\pi }^{2}N}-\frac{4}{\pi N}=\frac{4A}{{\pi }^{2}N}-\frac{4}{\pi N}\left(1+\frac{2}{\pi }\right)$$

Thus,

$$P\left(y\right)\ge \frac{4A}{{\pi }^{2}N}-\frac{4}{\pi N}\left(1+\frac{2}{\pi }\right)$$

(43)

According to Note 17, we know $N\approx Ap$ ⇒ $\frac{A}{N}\approx \frac{1}{p}$, i.e.,

$$\frac{4A}{{\pi }^{2}N}\approx \frac{4}{{\pi }^{2}p}$$

(44)

Furthermore, since N is a “huge” number, we know that the following is “small”:

$$\frac{4}{\pi N}\left(1+\frac{2}{\pi }\right)\stackrel{\underset{def}{}}{=}\epsilon$$

(45)

Using Equations (44) and (45) in Equation (43) results in

$$P\left(y\right)\ge \frac{4}{{\pi }^2}\frac{1}{p}-\epsilon$$

(46)

for each $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$. According to Corollary 9, there exist p different numbers $y_k$ with $y_k\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ and for each of them $P\left(y_k\right)\ge \frac{4}{{\pi }^2}\frac{1}{p}-\epsilon$. Since we are not interested in a particular $y_k$, but in any of them, we need to sum up all probabilities $P\left(y_k\right)$ to obtain the overall probability $P$:

$$P=\stackrel{p-1}{\sum _{i=0}}P\left(y_i\right)\ge \frac{4}{{\pi }^2}-p\epsilon \approx \frac{4}{{\pi }^2}$$

This proves the claim. □

We still need to estimate the probability for the case $q=1$.

Note 18.

Let $q=1$. Then $P\left(y\right)=\frac{A}{N}$.

Proof. 

In case $q=1$, the probability is

$$P\left(y\right)=\frac{1}{NA}{\left|{\displaystyle {{\displaystyle \sum }}_{j=0}^{A-1}}{q}^A\right|}^2=\frac{1}{NA}{\left|{\displaystyle {{\displaystyle \sum }}_{j=0}^{A-1}}1\right|}^2=\frac{1}{NA}{A}^2=\frac{A}{N}\hspace{1em}\square$$

3.4. Computing the Period

Let y be the result of the measurement produced by Shor’s algorithm. Under the assumption that $q\ne 1$, the following holds:

Theorem 15.

 

With probability $P\approx \frac{4}{{\pi }^2}$, there exists a $k\in \left\{0,\dots ,p-1\right\}$, such that

$$\left|\frac{y}{N}-\frac{k}{p}\right|<\frac{1}{2p^2}$$

Proof. 

According to Lemma 10, the probability that $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ for a $k\in \left\{0,\dots ,p-1\right\}$ is $\approx 4/{\pi }^2$.

However, $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ ⇔ $-\frac{1}{2}\le y-\frac{kN}{p}\le +\frac{1}{2}$. Dividing the latter inequations by $N$ yields: $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ ⇔$-\frac{1}{2N}\le \frac{y}{N}-\frac{k}{p}\le +\frac{1}{2N}$.

Thus, $\left|\frac{y}{N}-\frac{k}{p}\right|\le \frac{1}{2N}$. By choice of $N$, it is $n^2<N$. Furthermore, $p<n$ ⇒ $p^2<n^2$ ⇒ $p^2<N$ ⇒ $\frac{1}{N}<\frac{1}{p^2}$. This results in $\left|\frac{y}{N}-\frac{k}{p}\right|\le \frac{1}{2N}<\frac{1}{2p^2}$. □

Legendre’s Theorem (Theorem 14) proves immediately:

Theorem 16.

 

With probability $\approx 4/{\pi }^2$, $k/p$ is a convergent of $y/N$. □

3.4.1. Determining the Period by Convergents: $\mathrm{q}\ne 1$

The Algorithm 2 determines with probability of approximately $4/{\pi }^2$ the period p we are looking for; is is applicable in the case $q\ne 1$:

Algorithm 2 Determining with probability of approximately $4/{\pi }^2$ the period p we are looking for

Compute $\frac{y}{N}\in {\mathbb{Q}}_{>0}$; The result of the measurement is $y\in \mathbb{N}$ and $N\in \mathbb{N}$ has been chosen ⇒ $\frac{y}{N}\in {\mathbb{Q}}_{>0}$ can be computed. Compute the continued fraction representation $\left[a_0;a_1,\dots ,a_m\right]$ of $\frac{y}{N}\in \mathbb{Q}$; Compute the convergents $\left[a_0;a_1,\dots ,a_u\right]=\frac{g_u}{h_u}$, $1\le u\le m$; Determine $h_{\omega }$ with $h_{\omega }\ge h_u$ for $1\le u\le m$ and $h_{\omega }<n$ ⇒ $\frac{g_{\omega }}{h_{\omega }}$ is a very good approximation of $\frac{k}{p}$ because $\frac{1}{2h_{\omega }^2}\le \frac{1}{2h_u^2}$; Thus, $h_{\omega }\approx p$ is a candidate for the period p; Check whether p is in fact the period.

3.4.2. Determining the Period by Convergents: $\mathrm{q}=1$

In case $q=1$, the above algorithm is not applicable. However, $q=1$ ⇔ $e^{\frac{2\pi i}{N}py}=1$ ⇔ $\frac{py}{N}\in \mathbb{Z}$ ⇔ $p=k\frac{N}{y}$ with $k\in \mathbb{Z}$. Thus, the Algorithm 3 can be used:

Algorithm 3$q=1$ ⇔ $e^{\frac{2\pi i}{N}py}=1$ ⇔ $\frac{py}{N}\in \mathbb{Z}$ ⇔ $p=k\frac{N}{y}$$\mathrm{with} k\in \mathbb{Z}$

Compute $\frac{N}{y}\in {\mathbb{Q}}_{>0}.$ The result of the measurement is $y\in \mathbb{N}$ and $N\in \mathbb{N}$ has been chosen ⇒ $\frac{N}{y}\in {\mathbb{Q}}_{>0}$ can be computed; Select $k\in \mathbb{N}$; Compute $k\frac{N}{y}$; If $k\frac{N}{y}\notin \mathbb{N}$, go back to step (2); If $k\frac{N}{y}\ge n$, go back to step (2); $p=k\frac{N}{y}$ is a candidate for the period p; Check whether p is in fact the period; If p is not the period: a. If some predefined termination criterion is met: stop; b. Go back to step (2).

This may yield the period p but does not guarantee it.

3.5. How the Presented Results Relate

The contribution contains several low-level details. In order to avoid getting lost in these details, this section sketches how the main details contribute to the proof of Shor’s algorithm. The Figure 26 at the end of this section is a cartoon of these relations.

3.5.1. Applying the Results about Continued Factions

Determining a divisor and finally a prime factor of a natural number $n\in \mathbb{N}$ can be reduced to finding the period p of the modular exponentiation function $f\left(x\right)=a^{x}modn$ for an a with $0<a<n$—see Section 3.2.1 and Note 7.

The quantum part of Shor’s algorithm produces the state $\frac{1}{\sqrt{NA}}{\displaystyle \sum _{j=0}^{A-1}}{\omega }_N^{jpy}|y⟩$ from Equation (2). Measuring this state results in a natural number $y\in \mathbb{N}$.

The natural number N in Equation (2) must be chosen in advance based on the number n to be factorized: it is chosen as $N=2^m$ with $n^2<N<2n^2$—see the introduction of Section 8. This ensures that the relevant arguments to compute the $f\left(x\right)$ by the quantum part of Shor’s algorithm can be captured as quantum states.

Theorem 15 guarantees with probability $P\approx 4/{\pi }^2$ the existence of a $k\in \left\{0,\dots ,p-1\right\}$ such that $\left|\frac{y}{N}-\frac{k}{p}\right|<\frac{1}{2p^2}$.

Thus, according to the convergent criterion of Legendre’s Theorem (Theorem 14), $k/p$ is a convergent of $y/N$.

The proof of Legendre’s convergent criterion (Theorem 14), in turn, is based on the fact that convergents are exactly the best approximations of the second kind (Theorem 11 and Lagrange’s theorem (Theorem 12)).

The proof of Lagrange’s theorem (Theorem 12—each convergent is a best approximation of the second kind) makes use of the recursion theorem (Theorem 1), the sign theorem (Theorem 2), the monotony property of denominators of convergents (Corollary 1), as well as the estimations of the upper bounds of convergents (Lemma 3) and their lower bounds (Lemma 5).

The proof of Theorem 11 (each best approximation of the second kind is a convergent) makes use of the recursion theorem (Theorem 1), the distance theorem (Theorem 8), the computation of the difference of convergents (Corollary 3), the distance of fractions (Note 4), and the estimation of the upper bounds of convergents (Lemma 3).

The estimations of the lower and upper bounds of convergents depend on the distance theorem (Theorem 8), the computation of the difference of convergents (Corollary 3), the monotony property of denominators of convergents (Corollary 1), and on estimations of the size of denominators of convergents (Lemma 1). The estimation of the lower bounds (Lemma 5) makes use of semiconvergents (Definition 4) and their monotony property (Lemma 4) as well as the nesting theorem (Theorem 7).

Remark: Theorem 13, which proves that best approximations of the first kind are convergents or semiconvergents, is not immediately relevant to Shor’s algorithm and may be ignored when focusing on Shor’s algorithm.

3.5.2. Applying Probability Estimations

According to Equation (29) (which is implied by the Born rule), the probability $P\left(y\right)$ to measure a particular y is $P\left(y\right)=\frac{1}{NA}{\left|\frac{1-q^A}{1-q}\right|}^2$ for $q=e^{i2\pi \frac{py}{N}}\ne 1$.

Equations (37) and (38) show that this probability can be estimated as $\left|\frac{1-q^A}{1-q}\right|\ge \left|\frac{1-q^{A-1}}{1-q}\right|-1=\frac{\left|1-e^{i2\pi \frac{y\left(A-1\right)p}{N}}\right|}{\left|1-e^{i2\pi \frac{yp}{N}}\right|}-1$. The latter fraction, in turn, can be estimated by means of Lemma 7 (Secant Length Estimation) in case $2\pi \frac{y\left(A-1\right)p}{N},2\pi \frac{py}{N}\in \left[-\pi ,+\pi \right]$.

Lemma 9 shows that the latter inclusion is satisfied in case of $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ and $k\in \left\{0,\dots ,p-1\right\}$.

Lemma 10 proves that with probability $P\left(y\right)\approx 4/{\pi }^2$ it is, in fact, $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ for $k\in \left\{0,\dots ,p-1\right\}$. The proof of this lemma is based on a proper estimation of N (Note 17) which in turn relies on Note 16. Further, it makes use of Corollary 9, which is the summary of the various results of Section 3.2.2.

A simple calculation in the proof of Theorem 15 finally shows that $y\in \left[k\frac{N}{p}-\frac{1}{2},k\frac{N}{p}+\frac{1}{2}\right]$ implies $\left|\frac{y}{N}-\frac{k}{p}\right|\le \frac{1}{2N}<\frac{1}{2p^2}$. Thus, with probability $P\left(y\right)\approx 4/{\pi }^2$, the convergent criterion of Legendre’s Theorem (Theorem 14) is satisfied.

4. Conclusions and Related Work

The literature analyzing, discussing, and refining Shor’s algorithm [1] is vast. Of course, most text books on quantaum computing explain the algorithm too (e.g., [4,5]). In doing so, all this literature puts a sharp focus on the quantum part of the algorithm and sketches its classical parts at various depths. However, the mathematical treatment of the classical aspects is sketchy, omitting most of the details and leaving them as an exercise for the reader with references to corresponding text books from mathematics such as [6] or [7]. The lecture notes by Preskill [2] go a bit deeper, especially on the estimation of probabilities, but still omit the low-level details; however, the authors of the contribution at hand benefited a lot by the treatment in [2]. It is noted that the genesis for the authors’ treatment of probability estimations was inspired by unpublished, non-public work to which the authors had access to several years ago.

In doing so, the contribution at hand is very detailed on the probability estimation of being able to use Legendre’s Theorem in Shor’s algorithm. The authors are not aware of any other publication providing these low-level details.

Furthermore, the contribution at hand is a self-contained treatment on continued fractions up to Legendre’s Theorem. All background that is needed to understand this theorem is presented, including all proofs with low-level details step by step.

The authors hope to foster the comprehension of the classical aspects of Shor’s algorithm even at the level of beginners in quantum computing.