Sylvester-expansie

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

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

Voor de Sylvester-expansie geldt nog:

${\displaystyle {\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.^[1]

Het algoritme om de Sylvester-expansie van een echte breuk ${\displaystyle q={\frac {a}{b}}}$, dus met ${\displaystyle 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 ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ een stijgende rij vormen, en dat verder ${\displaystyle x_{1}}$ het kleinste natuurlijke getal is waarvoor ${\displaystyle {\frac {1}{x_{1}}}}$ zo dicht mogelijk ligt bij ${\displaystyle q}$, dus:

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

of:

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

Dan is:

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

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

en herhaal het voorgaande met deze nieuwe breuk om ${\displaystyle 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).

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

• Stap 1:

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

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

• Stap 2:

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

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

• Stap 3:

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

${\displaystyle \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}

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

${\displaystyle 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 ${\displaystyle x_{1},x_{2},\dots }$ de Sylvester-expansie van een breuk zij.^[1]

Sylvester noemde een expansie waarvoor steeds de gelijkheid geldt:

${\displaystyle 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.

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:

${\displaystyle 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.^[2]