Dari kemacetan Jakarta ke Dirichlet Divisor Function

Dari kemacetan Jakarta ke Dirichlet Divisor Function

02:54:00   Analytic, Umum,

Ini sebenarnya cuma follow up dari kejadian beberapa hari lalu ketika saya sedang terjebak kemacetan. Saya melihat beberapa mobil yang ada didepan saya , dan biasa nya saya suka melakukan arithmetic kepada angka plat dari mobil-mobil tersebut (kurang kerjaan sih emang, cm klo udah kena macet, main ginian pun jadi).

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.

   

Terdapat tepat $N^2$ buah titik lattice pada kuadran pertama yang memenuhi $1 \leq x,y \leq N$. Kita sebut titik lattice $(a,b)$ dimana $1 \leq a,b \leq N$ yang memenuhi $a\lvert b$ dan $b \lvert a$ sebagai titik bagus, berdasarkan simetri, kita cukup mengitung banyak titik bagus yang berada dibawah garis $y=x$, kemudian mengkalikan hasilnya dengan $2$, dan menambahkan banyak titik bagus pada garis $y=x$

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

Continue Reading

[UnSA] Atsuji Space is Complete

[UnSA] Atsuji Space is Complete

09:00:00   Analytic, UnSA,

Today, we were looking at the abstract of a paper which says"It is well-known that Atsuji Space is a complete space" .... I was riddled with this statement, I found the proof, It was based from 1955 Paper by Norman Levine and William G. Saunders.

Recall that a metric space $(X,d)$ is called Atsuji Space iff  every real-valued continuous functions on $X$ are also uniformly continuous on $X$.

We want to prove that:

If $(X,d)$ is an Atsuji space then every Cauchy sequence $(x_n)$  in $X$ converges.

Equivalently, we want to prove that
If there exists a Cauchy sequence in $X$ which does not converge, then there exists a continuous function $f: X \rightarrow \mathbb{R}$  which is not uniformly continuous.

In proving the above assertion, we need a following Lemma
[Uryohn's Lemma]
Let $X$ be a normal space. If $A$ and $B$ are two disjoint closed subsets of X, then there exists a continuous function $f$ from $X$ to the real line $\mathbb{R}$ such that $f(x)=0$ for all $x\in A$ and $f(x)=1$ for all $x\in B$.

The proof of Uryohn's Lemma is rather long, I remembered that the nearly two pages proof is on James Munkers Book, Topology.  Recall also that from elementary topology course: all metric spaces are normal, so Uryohn's Lemma works also for metric space.

It is not hard to prove that: A Cauchy sequence which has at least one convergent subsequence, is a convergent sequence. Therefore a divergent Cauchy sequence would imply that all of its subsequences are also divergent.

Suppose that $\{x_i\}_{i=1}^{\infty}$ is a Cauchy sequence of $X$ which diverges. Consider the set $\{x_1,x_2,\cdots,x_{i},\cdots\}$, since $(x_n)$ diverges this set has no limit point on $X$. Define
\[A:=\{x_{2k} | k\in \mathbb{N}\} \qquad  B:=\{x_{2k-1} | k \in \mathbb{N}\}\]
The element of $A$ will form a subsequence of $(x_n)$ and by our remark on the previous paragraph this subsequence also diverges, thus $A$ also has no limit point. Similarly $B$ also has no limit point. Therefore $A$ and $B$ are disjoint closed subsets of $X$, thus by Uryohn Lemma since $X$ is normal space, there exists a continuous function $f:X\rightarrow \mathbb{R}$ such that  $f(x_{2k-1})=0$ and $f(x_{2k})=1$.  This function is not uniformly continuous, since there exists $\epsilon_0 = \frac{1}{2}$ and two sequences $u_k = x_{2k}$ and $v_k=x_{2k-1}$ with $\lim (u_n - v_n) =0$ (since $x_n$ is Cauchy) but $f(u_n)-f(v_n)=1> \frac{1}{2}=\epsilon_0$.

Continue Reading