Engel expansion

From HandWiki

The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers [math]\displaystyle{ (a_1,a_2,a_3,\dots) }[/math] such that

[math]\displaystyle{ x=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\cdots = \frac{1}{a_1}\!\left(1 + \frac{1}{a_2}\!\left(1 + \frac{1}{a_3}\left(1+\cdots\right)\right)\right) }[/math]

For instance, Euler's number e has the Engel expansion[1]

1, 1, 2, 3, 4, 5, 6, 7, 8, ...

corresponding to the infinite series

[math]\displaystyle{ e=\frac{1}{1}+\frac{1}{1}+\frac{1}{1\cdot 2}+\frac{1}{1\cdot 2\cdot 3}+\frac{1}{1\cdot 2\cdot 3\cdot 4}+\cdots }[/math]

Rational numbers have a finite Engel expansion, while irrational numbers have an infinite Engel expansion. If x is rational, its Engel expansion provides a representation of x as an Egyptian fraction. Engel expansions are named after Friedrich Engel, who studied them in 1913.

An expansion analogous to an Engel expansion, in which alternating terms are negative, is called a Pierce expansion.

Engel expansions, continued fractions, and Fibonacci

(Kraaikamp Wu) observe that an Engel expansion can also be written as an ascending variant of a continued fraction:

[math]\displaystyle{ x = \cfrac{1+\cfrac{1+\cfrac{1+\cdots}{a_3}}{a_2}}{a_1}. }[/math]

They claim that ascending continued fractions such as this have been studied as early as Fibonacci's Liber Abaci (1202). This claim appears to refer to Fibonacci's compound fraction notation in which a sequence of numerators and denominators sharing the same fraction bar represents an ascending continued fraction:

[math]\displaystyle{ \frac{a\ b\ c\ d}{e\ f\ g\ h} = \dfrac{d+\cfrac{c+\cfrac{b+\cfrac{a}{e}}{f}}{g}}{h}. }[/math]

If such a notation has all numerators 0 or 1, as occurs in several instances in Liber Abaci, the result is an Engel expansion. However, Engel expansion as a general technique does not seem to be described by Fibonacci.

Algorithm for computing Engel expansions

To find the Engel expansion of x, let

[math]\displaystyle{ u_1 = x, }[/math]
[math]\displaystyle{ a_k = \left \lceil \frac{1}{u_k} \right \rceil\!, }[/math]

and

[math]\displaystyle{ u_{k+1} = u_k a_k - 1 }[/math]

where [math]\displaystyle{ \left \lceil r \right \rceil }[/math] is the ceiling function (the smallest integer not less than r).

If [math]\displaystyle{ u_i=0 }[/math] for any i, halt the algorithm.

Iterated functions for computing Engel expansions

Another equivalent method is to consider the map[2]

[math]\displaystyle{ g(x) = x\!\left( 1 + \left\lfloor x^{-1}\right\rfloor \right) - 1 }[/math]

and set

[math]\displaystyle{ u_k = 1 + \left\lfloor \frac{1}{g^{(n-1)} (x)} \right\rfloor }[/math]

where

[math]\displaystyle{ g^{(n)}(x) = g(g^{(n-1)}(x)) }[/math] and [math]\displaystyle{ g^{(0)}(x) = x. }[/math]

Yet another equivalent method, called the modified Engel expansion calculated by

[math]\displaystyle{ h (x) = \left\lfloor \frac{1}{x} \right\rfloor g(x) = \left\lfloor \frac{1}{x} \right\rfloor\!\left( x \left\lfloor \frac{1}{x} \right\rfloor + x - 1 \right) }[/math]

and

[math]\displaystyle{ u_k = \begin{cases} 1 + \left\lfloor \frac{1}{x} \right\rfloor & n = 1\\ \left\lfloor \frac{1}{h^{(k-2)}(x)} \right\rfloor\!\left( 1 + \left\lfloor \frac{1}{h^{(k-1)}(x)} \right\rfloor \right) & n \geq 2 \end{cases} }[/math]

The transfer operator of the Engel map

The Frobenius–Perron transfer operator of the Engel map [math]\displaystyle{ g(x) }[/math] acts on functions [math]\displaystyle{ f(x) }[/math] with

[math]\displaystyle{ [\mathcal{L}_g f] (x) = \sum_{y : g (y) = x} \frac{f (y)}{\left| \frac{d}{d z} g (z) \right|_{z = y}} = \sum_{n = 1}^{\infty} \frac{f \left( \frac{x + 1}{n + 1} \right)}{n + 1} }[/math]

since

[math]\displaystyle{ \frac{d}{dx} [x(n+1) - 1] = n + 1 }[/math] and the inverse of the n-th component is [math]\displaystyle{ \frac{x + 1}{n + 1} }[/math] which is found by solving [math]\displaystyle{ x (n + 1)- 1 = y }[/math] for [math]\displaystyle{ x }[/math].

Relation to the Riemann ζ function

The Mellin transform of the map [math]\displaystyle{ g(x) }[/math] is related to the Riemann zeta function by the formula

[math]\displaystyle{ \begin{align} \int_0^1 g(x) x^{s-1} \,dx & = \sum_{n=1}^\infty \int_{\frac{1}{n + 1}}^{\frac{1}{n}} (x(n+1) - 1) x^{s-1} \,dx \\[5pt] & = \sum_{n=1}^\infty \frac{n^{-s} (s-1) + (n + 1)^{- s - 1} (n^2 + 2n + 1) + n^{-s-1} s - n^{1-s}}{(s+1)s(n+1)} \\[5pt] & = \frac{\zeta(s+1)}{s+1} - \frac{1}{s(s+1)} \end{align}. }[/math]

Example

To find the Engel expansion of 1.175, we perform the following steps.

[math]\displaystyle{ u_1 = 1.175, a_1 = \left\lceil \frac{1}{1.175} \right\rceil = 1; }[/math]
[math]\displaystyle{ u_2 = u_1a_1 - 1 = 1.175\cdot 1 - 1 = 0.175, a_2 = \left\lceil\frac{1}{0.175}\right\rceil = 6 }[/math]
[math]\displaystyle{ u_3 = u_2a_2 - 1 = 0.175\cdot 6 - 1 = 0.05, a_3 = \left\lceil\frac{1}{0.05}\right\rceil = 20 }[/math]
[math]\displaystyle{ u_4 = u_3a_3 - 1 = 0.05\cdot 20 - 1 = 0 }[/math]

The series ends here. Thus,

[math]\displaystyle{ 1.175=\frac{1}{1}+\frac{1}{1\cdot6}+\frac{1}{1\cdot6\cdot20} }[/math]

and the Engel expansion of 1.175 is (1, 6, 20).

Engel expansions of rational numbers

Every positive rational number has a unique finite Engel expansion. In the algorithm for Engel expansion, if ui is a rational number x/y, then ui + 1 = (−y mod x)/y. Therefore, at each step, the numerator in the remaining fraction ui decreases and the process of constructing the Engel expansion must terminate in a finite number of steps. Every rational number also has a unique infinite Engel expansion: using the identity

[math]\displaystyle{ \frac{1}{n}=\sum_{r=1}^{\infty}\frac{1}{(n+1)^r}. }[/math]

the final digit n in a finite Engel expansion can be replaced by an infinite sequence of (n + 1)s without changing its value. For example,

[math]\displaystyle{ 1.175 = (1,6,20) = (1,6,21,21,21,\dots). }[/math]

This is analogous to the fact that any rational number with a finite decimal representation also has an infinite decimal representation (see 0.999...). An infinite Engel expansion in which all terms are equal is a geometric series.

Erdős, Rényi, and Szüsz asked for nontrivial bounds on the length of the finite Engel expansion of a rational number x/y ; this question was answered by Erdős and Shallit, who proved that the number of terms in the expansion is O(y1/3 + ε) for any ε > 0.[3]

Engel expansions for some well-known constants

[math]\displaystyle{ \pi }[/math] = (1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492, ...) (sequence A006784 in the OEIS)
[math]\displaystyle{ \sqrt{2} }[/math] = (1, 3, 5, 5, 16, 18, 78, 102, 120, 144, ...) (sequence A028254 in the OEIS)
[math]\displaystyle{ e }[/math] = (1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...) (sequence A028310 in the OEIS)

The Engel expansion for arithmetic progressions can be represented as

[math]\displaystyle{ \sum_{k = 1}^{\infty} \frac{1}{ \prod_{i = 0}^{k - 1} (\alpha + i\beta)}= \frac{1}{\alpha} + \frac{1}{\alpha(\alpha+\beta)} + \frac{1}{\alpha(\alpha+\beta)(\alpha+2\beta)} + \cdots. }[/math]

where [math]\displaystyle{ \alpha, \beta \in \mathbb{N} }[/math] and [math]\displaystyle{ 0 \lt \alpha \leq \beta }[/math]. Thus, in general

[math]\displaystyle{ \left(\frac{1}{\beta}\right)^{1 - \frac{\alpha}{\beta}} e^{\frac{1}{\beta}} \gamma\left(\frac{\alpha}{\beta}, \frac{1}{\beta}\right)=\{{\alpha}, \alpha(\alpha+\beta), \alpha(\alpha+\beta)(\alpha+2\beta), \dots\}\; }[/math] where [math]\displaystyle{ \gamma }[/math] represents the lower Incomplete gamma function.

Specifically, if [math]\displaystyle{ \alpha=\beta }[/math],

[math]\displaystyle{ e^{1/\beta}-1=\{1\beta, 2\beta, 3\beta, 4\beta, 5\beta, 6\beta, \dots\}\; }[/math]


More Engel expansions for constants can be found here.

Growth rate of the expansion terms

The coefficients ai of the Engel expansion typically exhibit exponential growth; more precisely, for almost all numbers in the interval (0,1], the limit [math]\displaystyle{ \lim_{n\to\infty} a_n^{1/n} }[/math] exists and is equal to e. However, the subset of the interval for which this is not the case is still large enough that its Hausdorff dimension is one.[4]

The same typical growth rate applies to the terms in expansion generated by the greedy algorithm for Egyptian fractions. However, the set of real numbers in the interval (0,1] whose Engel expansions coincide with their greedy expansions has measure zero, and Hausdorff dimension 1/2.[5]

See also

Notes

  1. ↑ Sloane, N. J. A., ed. "Sequence A028310". OEIS Foundation. https://oeis.org/A028310. 
  2. ↑ Sloane, N. J. A., ed. "Sequence A220335". OEIS Foundation. https://oeis.org/A220335. 
  3. ↑ (Erdős Rényi); (Erdős Shallit).
  4. ↑ (Wu 2000). Wu credits the result that the limit is almost always e to Janos Galambos.
  5. ↑ (Wu 2003).

References

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Engel_expansion&oldid=3373695"