Sylvester-expansie

De Sylvester-expansie van een positieve breuk $a/b$ is de stijgende rij van positieve gehele getallen $(x_{1},x_{2},\ldots ,x_{n})$ waarmee de breuk geschreven kan worden als Egyptische breuk zodanig dat steeds $x_{i}$ zo klein mogelijk is. Een Egyptische breuk is een som van stambreuken met natuurlijke getallen als noemers:

${\frac {a}{b}}={\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\ldots +{\frac {1}{x_{n}}}$

Voor de Sylvester-expansie geldt nog:

${\frac {1}{x_{i}}}\leq {\frac {a}{b}}-\left({\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\ldots +{\frac {1}{x_{i-1}}}\right)<{\frac {1}{x_{i}-1}}$

De expansie is genoemd naar de wiskundige James Joseph Sylvester, die ze in 1880 beschreef.

Berekening

Het algoritme om de Sylvester-expansie van een echte breuk $q={\frac {a}{b}}$, dus met $0<a<b$, te vinden is een greedy of gretig algoritme, wat inhoudt dat in elke stap de grootst mogelijke stambreuk wordt gezocht die nog kan opgeteld worden bij het voorlopige resultaat. Dit betekent dat de getallen $x_{1},x_{2},\ldots ,x_{n}$ een stijgende rij vormen, en dat verder $x_{1}$ het kleinste natuurlijke getal is waarvoor ${\frac {1}{x_{1}}}$ zo dicht mogelijk ligt bij $q$, dus:

${\frac {1}{x_{1}}}\leq q<{\frac {1}{x_{1}-1}}$

of:

$x_{1}-1<{\frac {1}{q}}\leq x_{1}$

Dan is:

$x_{1}=\left\lceil {\frac {b}{a}}\right\rceil$

Bereken nu de restterm $q-{\frac {1}{x_{1}}}={\frac {a\cdot x_{1}-b}{b\cdot x_{1}}}$

en herhaal het voorgaande met deze nieuwe breuk om $x_{2}$ te vinden, enzovoort. Stop wanneer de teller van de restterm nul wordt (het algoritme stopt gegarandeerd omdat de teller verkleint in elke stap).

Voorbeeld

De Sylvester-expansie van de breuk 115/137 wordt berekend als:

• Stap 1:

$x_{1}=\left\lceil {\frac {137}{115}}\right\rceil =2$

$\mathrm {rest} ={\frac {137}{115}}-{\frac {1}{2}}={\frac {93}{274}}$

• Stap 2:

$x_{2}=\left\lceil {\frac {274}{93}}\right\rceil =3$

$\mathrm {rest} ={\frac {93}{274}}-{\frac {1}{3}}={\frac {5}{822}}$

• Stap 3:

$x_{3}=\left\lceil {\frac {822}{5}}\right\rceil =165$

$\mathrm {rest} ={\frac {5}{822}}-{\frac {1}{165}}={\frac {3}{135630}}={\frac {1}{45210}}$

De Sylvester-expansie van 115/137 is dus {2, 3, 165, 45210}

Verband tussen de elementen in een Sylvester-expansie

Uit de berekeningswijze van de Sylvester-expansie volgt het volgende verband tussen twee opeenvolgende getallen uit de expansie:

$x_{i+1}\geq {x_{i}}^{2}-x_{i}+1$

voor alle waarden van i.

Dit is de noodzakelijke en voldoende voorwaarde opdat een gegeven rij $x_{1},x_{2},\dots$ de Sylvester-expansie van een breuk zij.

Sylvester noemde een expansie waarvoor steeds de gelijkheid geldt:

$x_{i+1}={x_{i}}^{2}-x_{i}+1$

voor alle i, een "limiterende" expansie (limiting). De rij {2, 3, 7, 43, 1807, 3263443} is een voorbeeld van een limiterende expansie. Alle getallen in een limiterende expansie zijn onderling ondeelbaar.

Andere expansies

De Sylvester-expansie is niet de enige manier om een rationaal getal te schrijven als een som van stambreuken; andere zijn bijvoorbeeld de Lüroth-expansie of de Engel-expansie. In de Engel-expansie zijn de noemers van de stambreuken opeenvolgende producten van gehele getallen:

$x={\frac {1}{a_{1}}}+{\frac {1}{a_{1}a_{2}}}+{\frac {1}{a_{1}a_{2}a_{3}}}+\cdots .\;$

De Engel-expansie bestaat voor elk positief reëel getal, dus ook voor breuken tussen 0 en 1. Jun Wu heeft in 2003 bewezen dat de verzameling van punten tussen 0 en 1 met dezelfde Engel- en Sylvester-expansie Hausdorff-dimensie 1/2 heeft.

Bronnen, noten en/of referenties