Restricted partial quotients

Last updated September 05, 2024

In mathematics, and more particularly in the analytic theory of regular continued fractions, an infinite regular continued fraction x is said to be restricted, or composed of restricted partial quotients, if the sequence of denominators of its partial quotients is bounded; that is

Periodic continued fractions

A regular periodic continued fraction consists of a finite initial block of partial denominators followed by a repeating block; if

\zeta =[a_{0};a_{1},a_{2},\dots ,a_{k},{\overline {a_{k+1},a_{k+2},\dots ,a_{k+m}}}],\,

then ζ is a quadratic irrational number, and its representation as a regular continued fraction is periodic. Clearly any regular periodic continued fraction consists of restricted partial quotients, since none of the partial denominators can be greater than the largest of a₀ through a_k+m. Historically, mathematicians studied periodic continued fractions before considering the more general concept of restricted partial quotients.

Restricted CFs and the Cantor set

The Cantor set is a set C of measure zero from which a complete interval of real numbers can be constructed by simple addition – that is, any real number from the interval can be expressed as the sum of exactly two elements of the set C. The usual proof of the existence of the Cantor set is based on the idea of punching a "hole" in the middle of an interval, then punching holes in the remaining sub-intervals, and repeating this process ad infinitum.

The process of adding one more partial quotient to a finite continued fraction is in many ways analogous to this process of "punching a hole" in an interval of real numbers. The size of the "hole" is inversely proportional to the next partial denominator chosen – if the next partial denominator is 1, the gap between successive convergents is maximized. To make the following theorems precise we will consider CF(M), the set of restricted continued fractions whose values lie in the open interval (0, 1) and whose partial denominators are bounded by a positive integer M– that is,

\mathrm {CF} (M)=\{[0;a_{1},a_{2},a_{3},\dots ]:1\leq a_{i}\leq M\}.\,

By making an argument parallel to the one used to construct the Cantor set two interesting results can be obtained.

If M ≥ 4, then any real number in an interval can be constructed as the sum of two elements from CF(M), where the interval is given by

(2\times [0;{\overline {M,1}}],2\times [0;{\overline {1,M}}])=\left({\frac {1}{M}}\left[{\sqrt {M^{2}+4M}}-M\right],{\sqrt {M^{2}+4M}}-M\right).

A simple argument shows that ${\scriptstyle [0;{\overline {1,M}}]-[0;{\overline {M,1}}]\geq {\frac {1}{2}}}$ holds when M ≥ 4, and this in turn implies that if M ≥ 4, every real number can be represented in the form n + CF₁ + CF₂, where n is an integer, and CF₁ and CF₂ are elements of CF(M).^[3]

Zaremba's conjecture

Zaremba has conjectured the existence of an absolute constant A, such that the rationals with partial quotients restricted by A contain at least one for every (positive integer) denominator. The choice A = 5 is compatible with the numerical evidence.^[4] Further conjectures reduce that value, in the case of all sufficiently large denominators.^[5] Jean Bourgain and Alex Kontorovich have shown that A can be chosen so that the conclusion holds for a set of denominators of density 1.^[6]

Related Research Articles

In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and mentioned by German mathematician Georg Cantor in 1883.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, a square root of a number $x$ is a number $y$ such that $; in other words, a number y whose square is x . For example, 4 and -4 are square roots of 16 because .$

In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on. In a finite continued fraction, the iteration/recursion is terminated after finitely many steps by using an integer in lieu of another continued fraction. In contrast, an infinite continued fraction is an infinite expression. In either case, all integers in the sequence, other than the first, must be positive. The integers $are called the coefficients or terms of the continued fraction.$

<span class="mw-page-title-main">Division (mathematics)</span> Arithmetic operation

Division is one of the four basic operations of arithmetic. The other operations are addition, subtraction, and multiplication. What is being divided is called the dividend, which is divided by the divisor, and the result is called the quotient.

In mathematics, a quadratic irrational number is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducible over the rational numbers. Since fractions in the coefficients of a quadratic equation can be cleared by multiplying both sides by their least common denominator, a quadratic irrational is an irrational root of some quadratic equation with integer coefficients. The quadratic irrational numbers, a subset of the complex numbers, are algebraic numbers of degree 2, and can therefore be expressed as

In complex analysis, a branch of mathematics, a generalized continued fraction is a generalization of regular continued fractions in canonical form, in which the partial numerators and partial denominators can assume arbitrary complex values.

<span class="mw-page-title-main">Stern–Brocot tree</span> Ordered binary tree of rational numbers

In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.

Methods of computing square roots are algorithms for approximating the non-negative square root $of a positive real number . Since all square roots of natural numbers, other than of perfect squares, are irrational, square roots can usually only be computed to some finite precision: these methods typically construct a series of increasingly accurate approximations.$

The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers $such that$

A decimal representation of a non-negative real number $r$ is its expression as a sequence of symbols consisting of decimal digits traditionally written with a single separator: $Here . is the decimal separator, k is a nonnegative integer, and are digits, which are symbols representing integers in the range 0, ..., 9.$

In mathematics, a quadratic equation is a polynomial equation of the second degree. The general form is

In the analytic theory of continued fractions, the convergence problem is the determination of conditions on the partial numeratorsa_i and partial denominatorsb_i that are sufficient to guarantee the convergence of the continued fraction

In the metrical theory of regular continued fractions, the kth complete quotient ζ_k is obtained by ignoring the first k partial denominators a_i. For example, if a regular continued fraction is given by

In mathematics, an infinite periodic continued fraction is a continued fraction that can be placed in the form

The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. It is more precisely called the principal square root of 5, to distinguish it from the negative number with the same property. This number appears in the fractional expression for the golden ratio. It can be denoted in surd form as:

A repeating decimal or recurring decimal is a decimal representation of a number whose digits are eventually periodic ; if this sequence consists only of zeros, the decimal is said to be terminating, and is not considered as repeating.

In arithmetic, short division is a division algorithm which breaks down a division problem into a series of easier steps. It is an abbreviated form of long division — whereby the products are omitted and the partial remainders are notated as superscripts.

In mathematics, a rational number is a number that can be expressed as the quotient or fraction ⁠ $⁠$ of two integers, a numerator $p$ and a non-zero denominator $q$ . For example, ⁠ $⁠$ is a rational number, as is every integer. The set of all rational numbers, also referred to as "the rationals", the field of rationals or the field of rational numbers is usually denoted by boldface $Q$ , or blackboard bold ⁠ $⁠$

The square root of 7 is the positive real number that, when multiplied by itself, gives the prime number 7. It is more precisely called the principal square root of 7, to distinguish it from the negative number with the same property. This number appears in various geometric and number-theoretic contexts. It can be denoted in surd form as:

References

↑ Rockett, Andrew M.; Szüsz, Peter (1992). Continued Fractions . World Scientific. ISBN 981-02-1052-3.
↑ For a fuller explanation of the K notation used here, please see this article.
↑ Hall, Marshall (October 1947). "On the Sum and Product of Continued Fractions". The Annals of Mathematics. 48 (4): 966–993. doi:10.2307/1969389. JSTOR 1969389.
↑ Cristian S. Calude; Elena Calude; M. J. Dinneen (29 November 2004). Developments in Language Theory: 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, Proceedings. Springer. p. 180. ISBN 978-3-540-24014-3.
↑ Hee Oh; Emmanuel Breuillard (17 February 2014). Thin Groups and Superstrong Approximation. Cambridge University Press. p. 15. ISBN 978-1-107-03685-7.
↑ Bourgain, Jean; Kontorovich, Alex (2014). "On Zaremba's conjecture". Annals of Mathematics . 180 (1): 137–196. arXiv: 1107.3776 . doi:10.4007/annals.2014.180.1.3. MR 3194813.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Rockett, Andrew M.; Szüsz, Peter (1992). Continued Fractions . World Scientific. ISBN 981-02-1052-3.

[2] For a fuller explanation of the K notation used here, please see this article.

[3] Hall, Marshall (October 1947). "On the Sum and Product of Continued Fractions". The Annals of Mathematics. 48 (4): 966–993. doi:10.2307/1969389. JSTOR 1969389.

[4] Cristian S. Calude; Elena Calude; M. J. Dinneen (29 November 2004). Developments in Language Theory: 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, Proceedings. Springer. p. 180. ISBN 978-3-540-24014-3.

[5] Hee Oh; Emmanuel Breuillard (17 February 2014). Thin Groups and Superstrong Approximation. Cambridge University Press. p. 15. ISBN 978-1-107-03685-7.

[6] Bourgain, Jean; Kontorovich, Alex (2014). "On Zaremba's conjecture". Annals of Mathematics . 180 (1): 137–196. arXiv: 1107.3776 . doi:10.4007/annals.2014.180.1.3. MR 3194813.

[1]

[2]

[3]

[4]

[5]

[6]