Stern-Brocot Ağacı: Her Pozitif Rasyonel Sayının Doğal Adresi

Saat tamircisi ve matematikçi

1858: Alman matematikçi Moritz Abraham Stern (Göttingen Üniversitesi) bir makale yayımladı: rasyonel sayıları sistemli olarak listeleyen yeni bir yapı.

1861: Fransız saat ustası Achille Brocot bağımsız olarak aynı yapıyı keşfetti — saat mekanizması tasarlarken (dişli oranı hesaplamak için) doğal olarak ortaya çıkmıştı.

İki keşif birleşince Stern-Brocot ağacı adı verildi. Bugün matematiksel mücevherlerden biri sayılıyor — özellikle bilgisayar bilimi, sayılar teorisi ve hatta müzik kuramında.

Mediant işlemi

İki kesir $\frac{a}{b}$ ve $\frac{c}{d}$ verildiğinde mediant (medyan-benzeri) şudur:

$\frac{a}{b} \oplus \frac{c}{d} = \frac{a+c}{b+d}$

Dikkat — bu aritmetik bir toplama değil! Pay ve payda ayrı ayrı toplanır.

Örnek: $\frac{1}{3} \oplus \frac{2}{5} = \frac{3}{8}$.

İlginç özellik: mediant her zaman iki kesir arasında kalır:

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

(asıl kesirler $\frac{a}{b} < \frac{c}{d}$ ise).

Ağacın inşası

İki "sahte" başlangıç değerinden başlıyoruz:

• En sol: $\frac{0}{1} = 0$
• En sağ: $\frac{1}{0} = +\infty$ (sembolik)

Düzey 0: $\frac{0}{1}, \frac{1}{0}$.

Düzey 1: Aralarına mediant ekle: $\frac{0+1}{1+0} = \frac{1}{1}$.

Liste: $\frac{0}{1}, \frac{1}{1}, \frac{1}{0}$.

Düzey 2: Yeni komşu çiftlerine mediant ekle:

• $\frac{0}{1} \oplus \frac{1}{1} = \frac{1}{2}$
• $\frac{1}{1} \oplus \frac{1}{0} = \frac{2}{1}$

Liste: $\frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0}$.

Düzey 3: $\frac{1}{3}, \frac{2}{3}, \frac{3}{2}, \frac{3}{1}$ eklenir.

Düzey 4: $\frac{1}{4}, \frac{2}{5}, \frac{3}{5}, \frac{3}{4}, \frac{4}{3}, \frac{5}{3}, \frac{5}{2}, \frac{4}{1}$ eklenir.

İkili ağaç olarak çizilirse:

                  1/1
               /        \
            1/2          2/1
           /   \        /   \
         1/3   2/3    3/2   3/1
         / \   / \    / \   / \
       1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1

Temel teoremler

Stern-Brocot ağacının iki muhteşem özelliği vardır:

Teorem 1 (Tamlık). Her pozitif rasyonel sayı bu ağaçta tam olarak bir kez görünür.

Teorem 2 (En basit form). Ağaçta görünen her $\frac{p}{q}$ kesri otomatik olarak en basit şekildedir (yani $\gcd(p,q) = 1$). Tüm kesirler tam zaten sadeleşmiştir.

Bu, klasik aritmetiğin "EBOB hesapla, sadeleştir" adımını gereksiz kılan zarif bir yapı.

Teorem 3 (Komşuluk). Ağaçta komşu kesirler $\frac{a}{b}$ ve $\frac{c}{d}$ için çapraz çarpım farkı $\pm 1$'dir:

$ad - bc = \pm 1$

(determinant +1 veya -1). Bu, ağaçta komşu kesirlerin Farey komşuları olduğunu söyler.

Sürekli kesirlerle bağı

Stern-Brocot ağacı sürekli kesir açılımı ile derinden bağlıdır. Bir kesrin ağaçtaki konumunu bulmak için: kökten $\frac{1}{1}$'dan başlayın; sol-sağ yön sekansı bizi kesre götürür. Bu sol-sağ kelimeleri ile sürekli kesir terimleri arasında doğrudan bir karşılık vardır.

Örnek: $\frac{5}{8}$'i ararken kökten yola çıkıp sol, sağ, sol, sol giderseniz $\frac{5}{8}$'e ulaşırsınız. Bu da $\frac{5}{8} = [0; 1, 1, 1, 2]$ sürekli kesir açılımına karşılık gelir.

Brocot'un saat mekaniği uygulaması

Brocot bu ağacı dişli oranı seçimi için kullandı. Bir saat 100/137 oranında bir dönüşüm gerektiriyorsa, ama bu kadar uzun dişli mümkün değilse, yakın daha basit bir oran seçmek gerekir. Stern-Brocot ağacı, istediğiniz hata düzeyiyle en iyi yaklaşımı verir.

Örneğin $\pi \approx 3.14159$ için ağaçta gezerek:

• $\frac{3}{1}$
• $\frac{22}{7} \approx 3.142857$ (klasik)
• $\frac{333}{106} \approx 3.141509$
• $\frac{355}{113} \approx 3.1415929$ — inanılmaz iyi, 7 doğru basamak.

Bu rasyonel yaklaşım algoritması modern bilgisayar aritmetiğinde, FPGA tasarımında, görüntü ölçeklemede kullanılır.

Farey dizileri ile farkı

Farey dizisi $F_n$, paydası $\leq n$ olan tüm $[0, 1]$ aralığındaki kesirleri sıralı verir. Stern-Brocot ile yakın akrabadır ama farklı: Farey paydaya göre sıralanır, Stern-Brocot mediant-tabanlı ikili ağaçtır.

İkisi de mediant ve çapraz çarpım = ±1 özelliklerini paylaşır.

Modern uygulamalar

1. Bilgisayar grafiği: anti-aliasing, piksel oranı seçimi — Stern-Brocot rasyonel yaklaşım.
2. Müzik teorisi: doğal aralıklar (perfect fifth $\frac{3}{2}$, major third $\frac{5}{4}$) ağaçta erken seviyelerde — neden müziğin uyumlu olduğunun matematiksel bir izi.
3. Çalış zamanlama (cron): "her 7/3 günde bir" gibi düzensiz periyotları yaklaşıklayarak basit oranlara indirir.
4. Sürekli kesir tabanlı şifreleme: bazı kuantum-sonrası kriptografi yaklaşımları.
5. Bilgisayar aritmetik: GCD algoritması ve Bezout katsayıları doğrudan Stern-Brocot algoritmasıyla hesaplanabilir.

Sonuç

Stern-Brocot ağacı, sade bir aritmetik işlem (mediant) etrafında olağanüstü bir yapı: tüm pozitif rasyonel sayıları, her birini tam bir kez, otomatik sadeleştirilmiş şekilde sıralar.

Bir saat tamircisinin dişli problemiyle bir matematikçinin sayı listesinin aynı yapıya ulaşması: matematiğin işlevsel bir keşif olduğunun en güzel kanıtı.