Dari kemacetan Jakarta ke Dirichlet Divisor Function
Kemarin saya menemukan dua mobil didepan saya yang nomor plat-nya menarik. Saya lupa angka-angka persisnya, tapi untuk cerita ini sebut saja lah plat nya adalah B 1856 ESE dan B 9280 ATE. Ini menarik, setelah sekian lama saya melakukan kerjaan iseng ini, ini adalah pertama kali nya saya menemukan dua mobil didepan saya dimana angka plat nya 4 digit dan memenuhi $x \lvert y$, contoh disini $9280 = 5 \times 1856$.
Dari sini saya berpikir, seberapa langka sih sebenarnya hal ini?
Jadi apabila ada sepasang bilangan bulat $(a,b)$ diambil secara random, berapa sering kah mereka memenuhi $a \lvert b$ atau $b \lvert a$ ?
Perhatikan bahwa saya menggunakan kata "seberapa sering", untuk hal ini saya akan menggunakan alat yang biasa dipakai di Teori Bilangan Analitik yaitu Natural Density (Sebenarnya ada bentuk Density yang lain seperti Logarithmic Density dan Analytic Density, tapi dikasus ini Natural Density -nya ternyata sudah ada, sehingga Logartihmic/Analytic Density nya juga ada dan sama.)
Hal ini dengan melihat kembali suatu hasil dari Cesaro yang mengatakan bahwa apabila dua bilangan diambil secara random maka probabilitas bahwa mereka relatif prima adalah $\frac{1}{\zeta(2)} = \frac{6}{\pi^2}$, disini sebenarnya yang digunakan bukanlah probability yang biasa kita kenal ( yang dengan Borel Algebra dll). Angka $\frac{1}{\zeta(2)}$ tersebut adalah natural density dari $\{(a,b) : gcd(a,b)=1\}$.
Pada bukti dari hasil $\frac{1}{\zeta(2)}$ diatas, biasanya digunakan estimasi \[\sum_{n\leq x} \varphi(n) = \frac{3x^2}{\pi^2} + O(x \log x)\],
ini disebut estimasi Mertens.
Perhitungan natural density nomor plat membagi diatas dapat dikerjakan dengan cara serupa menggunakan Dirichlet Divisor Estimation
\[\sum_{n \leq x} d(n) = x \log x + (2 \gamma -1 )x + \Delta(x)\]
Dimana $\Delta(x)= O(\sqrt{x})$, sampai saat ini masih merupakan famous open problem tentang bilangan terkecil $\alpha$ sehingga $\Delta(x) = O(x^{\alpha+\epsilon})$ untuk setiap $\epsilon>0$.
(Aproksimasi untuk $\Delta(x)$ merupakan sebuah topik riset, ini disebut Dirichlet Divisor Problem).
Tapi menurut saya itu agak overkill, jadi saya coba cara yang lebih elementer dibawah ini.
Saya akan menghitung
\[d(\mathcal{A}) = \lim_{N \rightarrow \infty} \frac{\# \{ (x,y) : 1\leq x, y \leq N, x| y \text{ atau } y| x \} }{\#\{(x,y) : 1\leq x, y \leq N \} } \]
dimana $\mathcal{A} = \{(x,y) \in \mathbb{N}^2 : x| y \text{ atau } y|x \}$.
Perhatikan juga bahwa Natural Density itu bukan Probability Measure, karena tidak memenuhi sifat countably additive ( $d\left(\bigcup_{i=1}^{\infty} \mathcal{A}_i\right) \neq \sum_{i=1}^{\infty} d(\mathcal{A}_i) $ ) tapi memang dibangun untuk membuat make-sense beberapa prinsip probabilitas terhadap Arithmetic Function (dalam ranah ilmu Teori Bilangan). Kita sebut ekspresi pada limit diatas sebagai $p_N$, dan kita ingin mengetahui $\lim_{N \rightarrow \infty} p_N$.
Untuk bilangan-bilangan kecil, sebenarnya cukup banyak, contoh pada interval $[1,5]$, yang mempunyai $25$ buah pasangan, terdapat pasangan $(1, j)$ dan $(j,1)$, dimana $j= 1, 2, 3, 4, 5$ yang totalnya adalah $10-1=9$ buah, lalu pasangan $(j,j)$ untuk $j=2,3,4,5$ ada $4$ pasangan, dan $(2,4)$ dan $(4,2)$ , jadi ada $9+4+2=15$ pasangan, dan rasio nya $p_5 = \frac{15}{25} = \frac{3}{5}$.
Kita akan representasikan $\{ (x,y) : 1\leq x, y \leq N, x| y \text{ atau } y| x \}$ sebagai titik lattice pada kuadran pertama.
Banyak titik bagus yang berada pada garis $y=x$ adalah $N$.
Kita akan menghitung banyak titik bagus pada tiap-tiap ruas garis yang berwarna biru diatas, ruas garis biru diatas adalah ruas garis $y=k$ iris $k < x \leq N$, dimana $k=1,2, \cdots, N-1$. Untuk sebarang $k$, banyak bilangan pada ruas garis biru yang merupakan kelipatan $k$ adalah $\left\lfloor \frac{N}{k} \right\rfloor - 1$. Jadi total titik bagus adalah
\[2 \sum_{k=1}^{N}\left( \left\lfloor \frac{N}{k} \right\rfloor - 1\right) +N = \sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N \]
Sebenarnya dari sini kita bisa menggunakan Teorema Dirichlet yang saya sebutkan diatas.
Tapi mari kita gunakan cara yang lebih elementer (bukti Teorema Dirichlet diatas sebenarnya juga elementer dan menggunakan titik lattice).
Perhatikan bahwa $x-\lfloor x \rfloor < 1$ sehingga $ x-\lfloor x \rfloor = O(1)$ ini berarti
\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N = \sum_{k=1}^{N}2\left( \frac{N}{k} - O(1) \right)- N =2N \left( \sum_{k=1}^{N} \frac{1}{k}\right) - O(N)-N = 2N \left(H_N\right) + O(N) \]
dimana $H_N = \sum_{k=1}^{N} \frac{1}{k}$. Untuk menggaproksimasi $H_n$, pandang fungsi $f(x) = \frac{1}{x}$ pada interval $[k, k+1]$ dimana $k \in [1, N]$, fungsi ini monoton turun sehingga
\[ f(k+1) \leq f(x) \leq f(k) \Rightarrow \int_k^{k+1} f(k+1) \, dx \leq \int_k^{k+1} f(x) \, dx \leq \int_k^{k+1}f(k) \, dx \]
Diperoleh
\[f(k+1) \leq \int_k^{k+1}f(x) \, dx \leq f(k)\]
Jumlahkan dari $k=1$ sampai $k=N-1$ diperoleh
\[H_N -1 \leq \int_1^{N} \frac{1}{x} \, dx \leq H_{N-1} \Rightarrow \frac{1}{N} +\log N \leq H_N \leq 1+\log N \]
Sehingga kita peroleh estimasi (tidak kuat tapi cukup) $H_N = O(\log N)$. Jadi
\[ \lim_{N\rightarrow \infty} p_N = \lim_{N\rightarrow \infty} \frac{2NO(\log N) + O(N)}{N^2} = \lim_{N\rightarrow \infty} 2 O\left(\frac{\log N}{ N}\right) + O\left(\frac{1}{N}\right) =0 \]
Jadi natural density $d(\mathcal{A})=0$, ini menjelaskan cerita awal saya, yaitu mengapa pasangan-pasangan yang demikian sangat jarang ditemukan pada bilangan-bilangan yang besar. Karena semakin besar bilangannya, pertumbuhan pasangan-pasangan tersebut kalah telak dengan pertumbuhan $N \times N$.
Estimasi lengkap nya sebenarnya sebagai berikut, banyak pasangan $(a,b)$ dengan $1 \leq a,b \leq N$ dan $a | b$ atau $b|a$ adalah seperti yang telah dihitung diatas
\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N \]
dapat dibuktikan $\sum_{k=1}^{N}\left( \left\lfloor \frac{N}{k} \right\rfloor\right) = \sum_{k=1}^n d(k)$ dimana $d(n)$ adalah banyak divisor positif dari $n$. Lalu dengan estimasi Dirichlet kita peroleh
\[\sum_{k=1}^{N}2\left( \left\lfloor \frac{N}{k} \right\rfloor\right)- N = 2 N \log N + (4\gamma - 2)N + \Delta(N)\]
dimana $\gamma$ adalah Euler-Mascheroni Constant. Jadi apabila dibagi $N^2$ dan di limit diperoleh
\[\lim_{N \rightarrow \infty} 2 \frac{\log N}{N} + \frac{4 \gamma -2}{N} + \frac{\Delta(N)}{N} = 0.\]
No wonder, It is indeed rare :D