[Part I] How does the prime connect to Zeta Function?

[Part I] How does the prime connect to Zeta Function?

20:38:00   Analytic Number Theory,

I looked back to my previous post about Riemann Hypothesis, Defining The Zeta Function.. Well, even It was said there that the theorem plays an important role in Number Theory,  but all of the things I put there are likely a complex analysis rather than a Number Theory (of course Complex Number is also a number :D ). Now Let's connect it to the primes.

The connection was established  before Riemann consider $\zeta(s)$ in his memoirs. It was Euler who first suggested the following relation between Dirichlet Series and Prime numbers

\[\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p\text{ is prime}} \left(1+\frac{1}{p^s} + \frac{1}{p^{2s}} + \cdots + \frac{1}{p^{ks}} + \cdots\right)\qquad (1)\]

Where the product is understood to range over all prime numbers. The above identity holds for $\Re(s)>1$. Therefore, $\zeta(s)$ would never equals zero for $\Re(s)>1$.

Equation (1) can be thought as the analytic version of Fundamental Theorem of Arithmetic. The intuition is clear here, since whenever we multiply all the product from the Right-Hand Side, ranging over all prime numbers, it would produce any combination of the reciprocal  $\frac{1}{p^{2\alpha_1s}p^{2\alpha_2 s}\cdots\,p^{2\alpha_n s}}$, which is some representation of a natural number by fundamental theorem of arithmetic and hence summing to the Left-Hand side. To guarantee the convergence of the series and product, we need the condition $\Re (s) >1$.

I want to reprise Tchebychev exposure in his paper Sur la fonction qui détermine la totalité des nombres premiers inférieurs à une limite donnée, using the modernize notation. 
My purpose is to verified some missing details in the paper. The paper can be downloaded here,  which is in french.


Tchebychev use (1) to bound the prime counting function $\pi(x)$ (the cardinality of the set of all prime numbers less than $x$). His argument is quite elementary and classical,  he considered three expressions

\[\sum_{k=2}^{\infty}\frac{1}{k^{1+\rho}}-\frac{1}{\sigma}\qquad (2)\]

\[\ln \rho-\sum_{p \text{ is prime}}\ln\left(1-\frac{1}{p^{1+\sigma}}\right)\qquad (3)\]

\[\sum_{p \text{ is prime}}\ln\left(1-\frac{1}{p^{1+\sigma}}\right)+\sum_{p \text{ is prime}} \frac{1}{p^{1+\sigma}}\qquad (4)\]

Let $s=\sigma+1$, the above are valid for $\Re(\sigma)>0$, or $\Re(s)>1$.
The first expresssion (2) is equal to
\[T_1(s)=\zeta(s) - 1 - \frac{1}{s-1}\]
 and  by (1) the second (3) is equal to
\[T_2(s)=\ln(s-1)+\ln \zeta(s),\]
while the third (4) is
\[T_3(s)=\sum_{p \text{ is prime}}\frac{1}{p^s}-\ln\zeta(s).\]

Notice that for
\[\begin{align*}\int_0^{\infty}\frac{e^{-x}}{e^x-1} x^{s-1} \, dx &=\int_0^{\infty} \left(\frac{e^{-x}}{1-e^{-x}}\right) e^{-x} x^{s-1} \, dx \\ &= \int_0^{\infty} \left(\sum_{k=1}^{\infty}e^{-kx}\right)e^{-x} x^{s-1} \, dx\\&=\sum_{k=1}^{\infty} \int_0^{\infty}e^{-(k+1)x}x^{s-1}\, dx\end{align*}\]

Substitute $x=\frac{u}{k+1}$, we have $\int_0^{\infty}e^{-(k+1)x}x^{s-1}\, dx = \int_0^{\infty} e^{-u} \frac{u^{s-1}}{(k+1)^s} \, du = \Gamma(s) \frac{1}{(k+1)^s}$. So denoting integral Gamma, $\Gamma(s)=\int_0^{\infty} e^{-x} x^{s-1} \,dx$ we have
\[\int_0^{\infty}\frac{e^{-x}}{e^x-1} x^{s-1}\, dx=\sum_{k=1}^{\infty}\Gamma(s)\frac{1}{(k+1)^s}=\Gamma(s)\left(\zeta(s)-1\right)\]

Since $\frac{1}{s-1}=\frac{\Gamma(s-1)}{\Gamma(s)}$, therefore (2) is equal to
\[T_1(s)=\zeta(s) - 1 - \frac{1}{s-1} = \frac{\int_0^{\infty}\frac{e^{-x}}{e^x-1} x^{s-1}\, dx - \Gamma(s-1)}{\Gamma(s)} = \frac{\int_0^{\infty}\left(\frac{1}{e^x-1} - \frac{1}{x}\right)x^{s-1}\, dx}{\Gamma(s)}\]

Taking limit $s \rightarrow 1^+$, since $\lim_{x\rightarrow 0^+}\left(\frac{1}{e^x-1}-\frac{1}{x}\right)=-\frac{1}{2}$ then $\int_0^{\infty}\frac{1}{e^x-1}-\frac{1}{x}\, dx$ converges and also $\int_0^{\infty} e^{-x}\,dx=1$. Thus
\[\lim_{s\rightarrow 1^+}T_1(s)=\lim_{s\rightarrow 1^+}\frac{\int_0^{\infty}\left(\frac{1}{e^x-1} - \frac{1}{x}\right)x^{s-1}\, dx}{\Gamma(s)}\] exists.

If we differentiate $\frac{\int_0^{\infty}\left(\frac{1}{e^x-1} - \frac{1}{x}\right)x^{s-1}\, dx}{\Gamma(s)}$ with respect to $s$ multiple times, we would have some combination of $\int_0^{\infty}\left(\frac{1}{e^x-1} - \frac{1}{x}\right)x^{s-1} \ln^k x \, dx$ and $\Gamma^{(k)}(s)=\int_0^{\infty} e^{-x} x^{s-1}\ln^k x\,dx$, where for all $k$ these integrals are finite and these integrals also converges when $s \rightarrow 1^+$. So the function $T_1(s)$ along with its $n$-th derivative are defined at $s=1$.

Consider expression (3),  which is by (1) equal to $T_2(s)=\ln(s-1)+\ln \zeta(s)$, by our previous result $T_1(s)$ has finite limit for $s \rightarrow 1^+$, thus

\[(s-1)T_1(s)\]

approach zero for $s \rightarrow 1^+$. Notice that

\[(s-1)T_1(s)+s=(s-1)\left(\zeta(s)-1- \frac{1}{s-1}\right) + s = (s-1)\zeta(s)\]

Therefore $\ln((s-1)T_1(s)+s)=T_2(s)$  since $\lim_{s \rightarrow 1^+} (s-1)\zeta(s)=1$ we have $\lim_{s \rightarrow 1^+} T_2 =1$.
Next we prove that $T_2$ has derivative of order $n$, for any $n$. We conclude this from the fact that $(s-1)T_1(s)+s$ would never zero, also since we have proved that $T_1(s)$ has $n$-th derivative, the relation $T_2(s)=\ln ((s-1)T_1(s)+s)$ would implies that $T_2$ also assumes $n$-th derivative.

Now we consider expression (4), which is $T_3(s)$. By the mean value theorem for $x>2$ there exists $c \in [x-1,x]$ such that $\ln(x)-\ln(x-1) = \frac{1}{c} > \frac{1}{x}$, so that

\[\ln(x-1)-\ln x +\frac{1}{x}<0 \qquad \text{for all } x>2\]

Now consider the series

\[\sum_{k=2}^{\infty}\ln(k-1)-\ln k + \frac{1}{k}=\lim_{n \rightarrow \infty}\sum_{k=1}^n \frac{1}{k}-\ln n-1=\gamma -1 \]

where $\gamma$ is Euler-Mascheroni Constant therefore the series converges, and since the terms are always negative

\[\sum_{k=2}^{\infty}\left|\ln(k-1)-\ln k+\frac{1}{k}\right|=-\sum_{k=2}^{\infty}\ln(k-1)-\ln k+ \frac{1}{k}=1-\gamma\]

so the series is absolutely converges therefore some subseries of it let say for those $k$ is prime also converges, we have

\[\sum_{p \text{ is prime} }\ln(p-1)-\ln p + \frac{1}{p}=\sum_{p \text{ is prime}}\ln \left(1-\frac{1}{p}\right) + \frac{1}{p}= T_3(1)\]
converges.

Also note that

\[T_3^{(n)}(s) =\sum_{p \text{ is prime} } \frac{1}{p^{2s}} \left(\frac{\ln^i p }{1-\frac{1}{p^s}}\right) \frac{1}{p^j \left(1-\frac{1}{p^s}\right)^k}\]

where $i,j,k \geq 0$. We can compare $T_3^{(n)}(s)$ with the $p$-series $\sum \frac{1}{n^p}$ where $\Re(p)>1$, thus the series is converges.

we will use $T_1(s)$, $T_2(s)$, and $T_3(s)$ to approximate $|\pi(x) - Li(x)|$ where $Li(x)=\int_2^x \frac{1}{\ln x}\, dx$.  We will do this in the next post. Continue Reading

Mendefinisikan fungsi Zeta Riemann, dan Riemann Hypothesis.

Mendefinisikan fungsi Zeta Riemann, dan Riemann Hypothesis.

04:27:00   Analytic Number Theory,

Walaupun cabang ini berada pada area Teori Bilangan, namun post yang saya buat ini, lebih pekat ke analisa kompleks, pada kenyataannya, pada post ini kita tidak membicarakan hubungan zeta function dengan bilangan prima.


Definisi awal (bukan definisi yang sebenarnya) dari Fungsi Zeta Riemann diperoleh dari Deret Dirichlet

\[\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}\qquad\Re(s)>1\]

Fungsi ini bukan fungsi yang secara umum dimaksud pada Riemann Hypothesis. Fungsi Zeta Riemann yang sebenarnya akan didefinisikan melalui fungsi ini, dan akan dijelaskan pada post ini.

Fungsi ini analytic di $\Re(s)>1$ (Fungsi nya sendiri diperoleh dari proses analitik pada complex; limit, infinite series; tapi deret diatas bukan power series dari $\zeta(s)$ yang memberikan evidensi bahwa $\zeta(s)$ analytic)
Pernyataan dari Riemann Hypothesis adalah (Mungkin bukan formulasi yang paling sederhana, menurut opini saya, formulasi dengan Liouville's Lambda Function lebih sederhana )

[Riemann Hypothesis] Semua akar tak-trivial dari fungsi $\zeta(s)$ berada pada garis kritis $\Re(s)=\frac{1}{2}$.

Sebuah pertanyaan yang muncul disini adalah:

Bukannya deret tersebut divergen untuk $\Re(s) \leq 1$? Lalu mengapa disebutkan $\Re(s)=\frac{1}{2}$? Lalu akar tak-trivial itu apa?

Pertama-tama kita jawab pertanyaan yang pertama dengan mendefinisikan fungsi zeta yang sebenarnya,kita akan menggunakan argumen yang digunakan Riemann.

Karena fungsi diatas hanya terdefinisi ketika $\Re(s)>1$. Bagaimana caranya kita mencapai (baca:define) di $\Re(s)\leq 1$, yaitu mendefinisikannya untuk seluruh bidang kompleks? Lebih lanjut lagi, karena fungsi awal tersebut sudah analitik di $\Re(s) >1$, kita ingin mendefinisikan fungsi ini sedemikian sehingga fungsi nya juga analitik di $\Re(s) \leq 1$.


Salah satu alat yang bisa kita pakai disini adalah analytic continuation, dimana kita dapat mengisi nilai-nilai dari suatu fungsi analitik diluar natural domain nya sehingga menghasilkan fungsi analitik lain dengan domain yang lebih besar. Yakni, dengan menemukan fungsi lain katakanlah $F(z)$ sedemikian sehingga hasil restriksi dari $F(s)$ di $Re(s)>1$ adalah $\zeta(s)$. Sayangnya tidak ada harapan untuk $s=1$, akan kita liat hal ini nanti, sekarang kita fokus untuk menemukan $F$ sedemikian sehingga $F(s)=\zeta(s)$, untuk $\Re(s)>1$, dan fungsi ini harus analitik di sebuah domain yang lebih besar dari $\Re(s)>1$.

Untuk menemukan fungsi ini kita mulai dengan satu-satunya definisi yang kita punya, yaitu untuk $\Re(s)>1$ diperoleh
\[\begin{align*}\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}&=\sum_{n=0}^{\infty}\frac{1}{(n+1)^s} \\ &=\sum_{n=1}^{\infty} \frac{1}{(n+1)^s}+1\\ &=\sum_{n=1}^{\infty}\frac{1}{(n+1)^s} + \sum_{n=1}^{\infty} \left(\frac{1}{n^{s-1}} - \frac{1}{(n+1)^{s-1}}\right)\\ &=\sum_{n=1}^{\infty}\left(\frac{1}{(n+1)^s}-\frac{n+1}{(n+1)^s}+\frac{n}{n^{s}}\right)\\ &=\sum_{n=1}^{\infty}n\left(\frac{1}{n^s}-\frac{1}{(n+1)^s}\right)\\ &=\sum_{n=1}^{\infty} n s\int_{n}^{n+1} x^{-s-1}\,dx\end{align*}\]

Karena $\lfloor x \rfloor = n$ ketika $x \in [n,n+1)$, kita peroleh $\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx=n\int_{n}^{n+1} x^{-s-1}\,dx$. Kita peroleh

\[\begin{align*}\zeta(s)&=s\sum_{n=1}^{\infty} n \int_{n}^{n+1} x^{-s-1}\,dx\\ &=s\sum_{n=1}^{\infty}\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx\\ &=s\int_1^{\infty}\lfloor x \rfloor x^{-s-1}\,dx\end{align*}\]

Tulis $\lfloor x \rfloor = x - \{x\}$ dimana $\{x\}$ adalah bagian pecahan dari $x$. Jadi

\[\begin{align*}\zeta(s)&=s \int_1^{\infty} x^{-s-1}\lfloor x \rfloor \,dx\\ &=s \int_1^{\infty}(x-\{x\})x^{-s-1}\,dx\\ &=s \int_1^{\infty} x^{-s}\, dx - s\int_1^{\infty} x^{-s-1}\{x\}\, dx\end{align*}\]

Karena $s \int_1^{\infty} x^{-s} \,dx = s \frac{-x^{-s+1}}{-s+1}\mid_1^{\infty}=\frac{s}{s-1}$, kita dapatkan

\[\zeta(s)=\frac{s}{s-1} - \int_1^{\infty}\{x\}x^{-s-1}\,dx\]

Dengan representasi dari $\zeta(s)$ yang ini, dapat dilihat bahwa $\zeta(s)$ mempunyai simple pole di $s=1$, dan juga karena $\{x\} \in [0,1)$ integral $\int_1^{\infty}\{x\}x^{-s-1}\,dx$ konvergen untuk $\Re(s)>0$, berdasarkan uji banding dengan $\int_1^{\infty} x^{-\Re(s)-1} \, dx$. Jadi, dengan menggunakan representasi ini , $\zeta(s)$ terdefinisi untuk $\Re(s)>0$. Kita telah memperbesar domain dari $\zeta(s)$ (dengan menggunakan analytic continuation) dari $\Re(s)>1$ ke $\Re(s)>0$, dan memperoleh informasi tentang simple pole di $s=1$ dengan residue 1 (koefisien dari $(s-1)^{-1}$). Tetapi pekerjaan untuk mendefinsikan $\zeta(s)$ untuk (hampir) setiap bidang kompleks belum selesai.


Untuk melanjutkan, kita pinjam sebuah fungsi dari kuliah Kalkulus Tingkat Lanjut (di Universitas Indonesia kami menyebutnya Matematika Dasar IV), yaitu Fungsi Gamma (Gamma Function).
Fungsi Gamma, awalnya didefinisikan sebagai $\Gamma(s)=\int_0^{\infty}t^{s-1}e^{-t}\,dt$ untuk $s$ bilangan real positif, karena integral tersebut juga konvergen untuk $s$ bilangan kompleks dengan $\Re(s)>0$, maka fungsi Gamma juga terdinisi pada bilangan kompleks , fungsi gamma analitik juga untuk $\Re(s)>0$ (beberapa kali kita memakai fakta bahwa fungsi yang menggunakan integral atau deret dalam representasinya itu analitik). Bagaimanapun juga hanya dengan menggunakan hal ini, kita tidak bisa lanjut lebih jauh melebihi $\Re(s)>0$, tapi untungnya, dengan menggunakan analytic continuation, Fungsi Gamma juga bisa diperluas menjadi fungsi analitik di seluruh bidang kompleks kecuali untuk $s=0, -1,-2, \cdots, -n, \cdots$ (liat link, atau baca lagi buku Kalkulus Tingkat Lanjut)

Menggunakan hal diatas fungsi $\Gamma(s)$ dapat didefinsikan di $\mathbb{C}/\{0,-1,-2,\cdots\}$, dan terlebih lagi analitik disana. Hubungan antara $\zeta$ dan $\Gamma$ dapat diperoleh sebagai berikut
\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}t^{s/2-1}e^{-t}\, dt\]

Substitusikan $t=n^2\pi u$ kita dapatkan

\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}\pi^{\frac{s-2}{2}} n^{s-2} u^{\frac{s-2}{2}} e^{-n^2 \pi u} (n^2 \pi)\,du=n^s \pi^{\frac{s}{/2}}\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]

Setara dengan

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right)\left(\frac{1}{n^s}\right)=\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]

Jumlahkan dari $n=1$ ke $\infty$ dan karena integral di sisi kiri konvergen uniform, kita bisa menukar integral dan sumasi dan menghasilkan

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right) \zeta(s) = \int_0^{\infty} u^{\frac{s}{2}-1} \left(\sum_{n=1}^{\infty}e^{-n^2 \pi u}\right) \, du\]

Kita pinjam lagi fungsi dari kalkulus tingkat lanjut yaitu, Jacobi-Theta Function, yang didefinisikan sebagai $\theta(t)=\sum_{n=-\infty}^{\infty} e^{n^2 i\pi t}$. Oleh karena itu $\theta(it)=\sum_{n=-\infty}^{\infty} e^{-n^2 \pi t}$. Karena "$\sum_{n=-\infty}^{0} e^{-n^2 \pi t} = \sum_{n=0}^{\infty} e^{-n^2\pi t}$", jadi

\[\theta(it)=\sum_{n=0}^{\infty} e^{-n^2 \pi t}+ \sum_{n=1}^{\infty}e^{-n^2 \pi t}=2 \sum_{n=1}^{\infty} e^{-n^2 \pi t}+1.\]

sehingga $\sum_{n=1}^{\infty}e^{-n^2 \pi t} = \frac{\theta(it)-1}{2}$. Sehingga fungsi zeta dapat dinyatakan sebagai

\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\int_0^{\infty} u^{\frac{s}{2}-1} \left(\frac{\theta(ui)-1}{2}\right)\, du\]

Dari sini kita akan menggunakan persamaan fungsi dari $\theta$, yaitu $(-ix)^{\frac{1}{2}}\theta(x)=\theta\left(-\frac{1}{x}\right)$, yang buktinya cukup susah (liat di buku tentang Special Function), pesamaan ini dapat diperoleh melalui transformasi modular dari jacobi function, biasanya juga disebut Identitas Jacobi (Liat link diatas, tapi tidak ada buktinya). Substitusikan $x \mapsto ix$ ke persamaan fungsi diatas diperoleh $x^{\frac{1}{2}} \theta(ix)=\theta\left(\frac{-1}{ix}\right)=\theta\left(\frac{i}{x}\right)$.

\[\begin{align*}&\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx=\\ &\int_0^{1}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx+\int_1^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\end{align*}\]

Dengan substitusi $x \mapsto \frac{1}{x}$ ke Integral pertama diperoleh

\[\begin{align*}\int_0^1x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\, dx&= \int_{\infty}^{1}x^{-s/2+1}\left(\frac{\theta\left(\frac{i}{x}\right)-1}{2}\right)\left(\frac{-1}{x^2}\right)\, dx \\ &= \int_1^{\infty} x^{-s/2-1}\left(\frac{x^{1/2}\theta(ix)-1}{2}\right)\\ &= \int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}\\ &+ \int_1^{\infty} \frac{x^{-s/2-1/2}-x^{-s/2-1}}{2} \, dx\\ &=\int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}+\frac{1}{s(s-1)}\end{align*}\]

Jadi

\[\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\]
\[=\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\]

Dan Fungsi Zeta Riemann terdefinisi sebagai
\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\left(\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\right)\]

Perhatikan bahwa fungsi Gamma mempunyai simple pole di $s=0$, jadi $\frac{1}{\Gamma\left(\frac{s}{2}\right)}$ saling menghilangkan simple pole yang juga di $s=0$ yang diperoleh dari $\frac{1}{s(s-1)}$.
Karena $\theta(xi)$ tumbuh secara eksponensial (baca buku Persamaan Differensial, Pengantar transformasi Laplace), integrak diatas konvergen untuk $s\in \mathbb{C}$, jadi ekspresi yang berada di kanan merupakan fungsi analitik di $s \in \mathbb{C}$ kecuali untuk for $s=1$ (dimana penyebutnya nol) dan $s=-2,-4,-6, \cdots$ (dimana $\Gamma\left(\frac{s}{2}\right)$ tidak analitik, yaitu mempunyai pole) jadi kita telah memperluas fungsi zeta menjadi fungsi analitik pada domain $\mathbb{C}/\{1,-2,-4,\cdots,-2k,\cdots\}$. Pertanyaan pertama selesai.

Untuk pertanyaan kedua, apa itu akar tak-trivial dari $\zeta(s)$, singkatnya, kita sebut $s$ sebagai akar trivial jika dan hanya jika $s$ merupakan pole dari $\Gamma\left(\frac{s}{2}\right)$ yang tidak ter-cancel ($s\neq 0$), yaitu $s=-2,-4,\cdots$. Akar lain yang diketahui berada pada $0\leq \Re(z) \leq 1$, disebut akar tak-trivial. Yup, Riemann Hypothesis menanyakan apakah akar ini selalu berada pada garis $\Re(s)=\frac{1}{2}$, atau berbentuk $s=\frac{1}{2} + bi$

Telah diketahui bahwa beberapa milyar akar pertama dari akar tak-trivial dari $\zeta(s)$ memenuhi prediksi Riemann Hypothesis. Jadi pernyataan nya mungkin benar. Tapi pembuktiannya sangatlah susah, dan diketahui, teknik yang dipakai pada area ini sangat beragam, dan belum ada yang berani mengklaim teknik mana yang akan membawa ke bukti yang diinginkan (silahkan liat di arXiv.org)

Post selanjutnya (sedang di draft) membicarakan tentang hubungan nya dengan bilangan prima, dan Li function.

Continue Reading

Riemann Hypothesis for Dummies?

Riemann Hypothesis for Dummies?

05:23:00   Analytic Number Theory,

First, i'm sorry if the title is a little bit offensive. I just wonder if there's such a thing as "Riemann Hypothesis For Dummies", while the original statement of the conjecture itself would require at least advance undergraduate complex analysis, and (no math undergraduate is dummy right?).  I'm going to write down some analysis preliminary that will lead us to understand the statement of Riemann Hypothesis.

Recall that the Initial Riemann zeta function is defined via the Dirichlet series by

\[\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}\qquad\Re(s)>1\]

Note that the function is clearly analytic on $\Re(s)>1$.

The statement of Riemann Hypothesis is (it is not the most simple form, perhaps the most simple form i know is the thing related to Liouville's Lambda Function )

[Riemann Hypothesis] All nontrivial zeros of the Riemann Zeta Function  lie on the critical line $\Re(s)=\frac{1}{2}$.


The question immediately arises here, isn't the series diverges for $\Re(s) \leq 1$? Then why does it
mention $\Re(s)=\frac{1}{2}$? Also what is the nontrivial zero?

First we resolve the problem on defining the Riemann Zeta Function (without initial), we will use Riemann's Argument, since so far this function only defined for $\Re(s)>1$.  How could we reach (read:define) it on $\Re(s)\leq 1$, that is to define it for all complex plane? Moreover, since the function is already analytic on $\Re(s) >1$, we want the function to be also analytic on the other region $\Re(s) \leq 1$.
One tool we can use here is the analytic continuation, for which we can fill the the value of the function outside its analytic domain resulting the other analytic function with a larger domain,  this can be done if  we can find another analytic function $F(s)$ such that the restriction of $F$ on $Re(s)>1$ is $\zeta(s)$ itself.  Unfortunately, there is no hope for  $s=1$, we will see this later, now we focus on finding an analytic function $F$ such that $F(s)=\zeta(s)$, for $\Re(s)>1$, this function must be analytic on the domain larger than just $\Re(s)>1$.

To find the extended function, we start with what we only have, for $\Re(s)>1$ we have

\[\begin{align*}\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}&=\sum_{n=0}^{\infty}\frac{1}{(n+1)^s} \\ &=\sum_{n=1}^{\infty} \frac{1}{(n+1)^s}+1\\ &=\sum_{n=1}^{\infty}\frac{1}{(n+1)^s} + \sum_{n=1}^{\infty} \left(\frac{1}{n^{s-1}} - \frac{1}{(n+1)^{s-1}}\right)\\ &=\sum_{n=1}^{\infty}\left(\frac{1}{(n+1)^s}-\frac{n+1}{(n+1)^s}+\frac{n}{n^{s}}\right)\\ &=\sum_{n=1}^{\infty}n\left(\frac{1}{n^s}-\frac{1}{(n+1)^s}\right)\\ &=\sum_{n=1}^{\infty} n s\int_{n}^{n+1} x^{-s-1}\,dx\end{align*}\]

Since $\lfloor x \rfloor = n$ when $x \in [n,n+1)$, we have $\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx=n\int_{n}^{n+1} x^{-s-1}\,dx$. We have

\[\begin{align*}\zeta(s)&=s\sum_{n=1}^{\infty} n \int_{n}^{n+1} x^{-s-1}\,dx\\ &=s\sum_{n=1}^{\infty}\int_{n}^{n+1}\lfloor x \rfloor x^{-s-1}\,dx\\ &=s\int_1^{\infty}\lfloor x \rfloor x^{-s-1}\,dx\end{align*}\]

Write $\lfloor x \rfloor = x - \{x\}$ where $\{x\}$ is fractional part of $x$. We have

\[\begin{align*}\zeta(s)&=s \int_1^{\infty} x^{-s-1}\lfloor x \rfloor \,dx\\ &=s \int_1^{\infty}(x-\{x\})x^{-s-1}\,dx\\ &=s \int_1^{\infty} x^{-s}\, dx - s\int_1^{\infty} x^{-s-1}\{x\}\, dx\end{align*}\]

Since $s \int_1^{\infty} x^{-s} \,dx = s \frac{-x^{-s+1}}{-s+1}\mid_1^{\infty}=\frac{s}{s-1}$, we have

\[\zeta(s)=\frac{s}{s-1} - \int_1^{\infty}\{x\}x^{-s-1}\,dx\]

Via this representation of $\zeta(s)$,  we see that $\zeta(s)$ has simple pole for $s=1$, and also since $\{x\} \in [0,1)$ the integral $\int_1^{\infty}\{x\}x^{-s-1}\,dx$ converges for $\Re(s)>0$, by comparison test with $\int_1^{\infty} x^{-\Re(s)-1} \, dx$. Thus, on this representation, $\zeta(s)$ is defined for $\Re(s)>0$. We actually have extend the domain of $\zeta(s)$ (applying analytic continuation) from $\Re(s)>1$ to $\Re(s)>0$, and resulting the simple pole in $s=1$ with residue 1. Still, our works to define $\zeta(s)$ for the whole complex plane, not finish yet.

To continue, we borrow a function from Advanced Calculus Course (in Universitas Indonesia we call it Calculus IV), Gamma Function.

Gamma function, initially defined by $\Gamma(s)=\int_0^{\infty}t^{s-1}e^{-t}\,dt$ for $s$ is real positive, since the integral also converges whenever $s$ is a complex number with $\Re(s)>0$, therefore the Gamma function is defined as a complex function, this function is analytic on where it is defined that is $\Re(s)>0$. However using this definition, we can't go anywhere other than $\Re(s)>0$, but luckily, using also analytic continuation, the Gamma Function can also extendable to an analytic function in the whole complex plane except for $s=0, -1,-2, \cdots, -n, \cdots$ (see the link above)

Using it then, Gamma Function is extendable to $\mathbb{C}/\{0,-1,-2,\cdots\}$.  In the relation between $\zeta$ and $\Gamma$, consider

\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}t^{s/2-1}e^{-t}\, dt\]

Substitue $t=n^2\pi u$ we have

\[\Gamma\left(\frac{s}{2}\right)=\int_0^{\infty}\pi^{\frac{s-2}{2}} n^{s-2} u^{\frac{s-2}{2}} e^{-n^2 \pi u} (n^2 \pi)\,du=n^s \pi^{\frac{s}{/2}}\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]

Equivalent to

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right)\left(\frac{1}{n^s}\right)=\int_0^{\infty} u^{\frac{s}{2}-1} e^{-n^2 \pi u} \, du\]



Taking the summation from $n=1$ to $\infty$ and since the integral on the left converges uniformly, we can exchange the integral and summation thus resulting

\[\pi^{-\frac{s}{2}}\Gamma\left(\frac{s}{2}\right) \zeta(s) = \int_0^{\infty} u^{\frac{s}{2}-1} \left(\sum_{n=1}^{\infty}e^{-n^2 \pi u}\right) \, du\]

We borrow again a function from advanced calculus,  Jacobi-Theta Function, defined by $\theta(t)=\sum_{n=-\infty}^{\infty} e^{n^2 i\pi t}$. Therefore $\theta(it)=\sum_{n=-\infty}^{\infty} e^{-n^2 \pi t}$. Since "$\sum_{n=-\infty}^{0} e^{-n^2 \pi t} = \sum_{n=0}^{\infty} e^{-n^2\pi t}$", using this we have

\[\theta(it)=\sum_{n=0}^{\infty} e^{-n^2 \pi t}+ \sum_{n=1}^{\infty}e^{-n^2 \pi t}=2 \sum_{n=1}^{\infty} e^{-n^2 \pi t}+1.\]

Thus $\sum_{n=1}^{\infty}e^{-n^2 \pi t} = \frac{\theta(it)-1}{2}$. Therefore the zeta function is represented as

\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\int_0^{\infty} u^{\frac{s}{2}-1} \left(\frac{\theta(ui)-1}{2}\right)\, du\]

From this point we shall use the functional equation for $\theta$, that is $(-ix)^{\frac{1}{2}}\theta(x)=\theta\left(-\frac{1}{x}\right)$,  which is quite hard to prove, this functional equation can be obtained from modular transform of theta function. Usually given as Jacobi Identities for theta function (See the Link above, but no proof there).  Substituing $x \mapsto ix$ to the functional equation we have $x^{\frac{1}{2}} \theta(ix)=\theta\left(\frac{-1}{ix}\right)=\theta\left(\frac{i}{x}\right)$.

\[\begin{align*}&\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx=\\ &\int_0^{1}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx+\int_1^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\end{align*}\]

Using substitution $x \mapsto \frac{1}{x}$ on the first integral, we have

\[\begin{align*}\int_0^1x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\, dx&= \int_{\infty}^{1}x^{-s/2+1}\left(\frac{\theta\left(\frac{i}{x}\right)-1}{2}\right)\left(\frac{-1}{x^2}\right)\, dx \\ &= \int_1^{\infty} x^{-s/2-1}\left(\frac{x^{1/2}\theta(ix)-1}{2}\right)\\ &= \int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}\\ &+ \int_1^{\infty} \frac{x^{-s/2-1/2}-x^{-s/2-1}}{2} \, dx\\ &=\int_1^{\infty} \frac{x^{-s/2-1/2}\theta(ix)-x^{-s/2-1/2}}{2}+\frac{1}{s(s-1)}\end{align*}\]

Thus we have

\[\int_0^{\infty}x^{s/2-1}\left(\frac{\theta(xi)-1}{2}\right)\,dx\]
\[=\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\]

Hence the Riemann Zeta Function would takes form

\[\zeta(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma\left(\frac{s}{2}\right)}\left(\frac{1}{s(s-1)}+\int_1^{\infty}(x^{-s/2-1/2}+x^{s/2-1})\left(\frac{\theta(xi)-1}{2}\right)\,dx\right)\]

Note that Gamma function has simple pole on $s=0$, thus $\frac{1}{\Gamma\left(\frac{s}{2}\right)}$ cancel the simple pole also at $s=0$ obtained from $\frac{1}{s(s-1)}$.
Since $\theta(xi)$ has exponential order, the above integral converges for every $s\in \mathbb{C}$, therefore the expression on the right performs an analytic function for all $s \in \mathbb{C}$ except for $s=1$ (in which the denominator is zero) and $s=-2,-4,-6, \cdots$ (in which $\Gamma\left(\frac{s}{2}\right)$ is not analytic) thus we have extend the zeta function to an analytic function defined on $\mathbb{C}/\{1,-2,-4,\cdots,-2k,\cdots\}$.

We actually have any other question to resolve, that is a nontrivial zeros of $\zeta(s)$, to make it short, we call $s$ the zero is trivial zero iff $s$ is a pole from the $\Gamma\left(\frac{s}{2}\right)$, that is $s=0,-2,-4,\cdots$. The other zeros is known to be located on $0\leq \Re(z) \leq 1$, are called nontrivial zeros.  Therefore we have got the idea now, that the Riemann Hypothesis asks wether these nontrivial zeros always located on the $\Re(s)=\frac{1}{2}$.

It is known that more than billion of the first nontrivial zeros are all agree with the hypothesis, which seems likely the hypothesis to be true. But, as the problem is complicated enough to describe, the proof challenges many greatest minds in the world(s), as the most difficult problem in Number Theory.

Writing this post remind me with the quote from Albert Einstein, which is put on the wall of the seminar room in our university :D  , "If you can't explain it simply, you don't understand it well enough" ,  well maybe I don't really understand this very well,  because even to describe it, the miscellaneous properties of the other special functions are being used.

Continue Reading

[ALGAE IV] Rational Curve and Rational Function.

[ALGAE IV] Rational Curve and Rational Function.

22:41:00   Algebraic Geometry,

It has been months, and i actually has got quite far reading algebraic geometry, but i don't spare a time to share it here. Let's continue the previous posts (and to remind me more about what i have learned).

As we already learn that any irreducible rational curve $f(x,y)=0$ can be parameterized by $x=\varphi(t)$ and $y=\psi(t)$. Lets take a look this parameterization deeper,  Example in the [AlGAE II] is the place to look, the parameter $t$ help us to correspond a point in the curve to the point in the line $x=-1$, by a mapping (recall that $y=tx$)

\[(x,y) \mapsto (-1,-t) = \left(-1, -\frac{y}{x}\right)\]

For $x=0$ which also implies $y=0$, this map is undefined, and this is where the denominator of $\varphi(t)$ and $\psi(t)$ vanish. Ignoring these points, the map seems fine, and defines a bijection from the point in the curve to the line. In fact, there can be only finitely many points in the curve such that the parameter fails to represent (like our $(0,0)$ just know), those are actually the common roots of the denominator of $\varphi(t)$ and $\psi(t)$.

Let include the result obtained on [ALGAE III], where we can find the isomorphic map from $\mathbb{F}(X)$ to $\mathbb{F}(t)$, given that $X$ is a rational curve.
Let's see wether this result is vice versa, that is whenever $\mathbb{F}(X)\cong \mathbb{F}(t)$ then $X$ is rational.
Since $x, y \in \mathbb{F}(X)$,  they have a correspondence image in $\mathbb{F}(t)$, let say $x$ to $\varphi(t)$ and $y$ to $\psi(t)$. By isomorphism, the element $f(x,y)=0 \in \mathbb{F}(X)$ goes to the element $f(\varphi(t),\psi(t))=0$ (since $x$ and $y$ is related by an algebraic relation, note that this is not a mere substitution $x =\varphi(t)$ and $y =\psi(t)$). Therefore, such parametrization so that $f(\varphi(t),\psi(t))=0$ exists, and $X$ is rational.

Moreover, as for any $t_0 \in \mathbb{F}$ we should have $f(\varphi(t_0),\psi(t_0))=0$, but this can be failed for which $t_0$ is a common root of the denominator of $\varphi(t)$ and $\psi(t)$. Excluding these points  we can easily see that $x=\varphi(t)$ and $y=\psi(t)$ define a parameterization the point on a curve $X$.

Our goal is to represent any point $(x,y) \in X$ as $(x,y)=(\varphi(t),\psi(t))$ for some $t$, and conversely producing $(x,y) \in X$, for any given $t$ by using parametrization $x=\varphi(t)$ and $\psi(t)$. Unfortunately, this is so much a dream, as we can see our parametrization in [ALGAE II] failed to include/produce some points in $X$. We will resolve this as close as possible to our goal.

Let $\tau(x,y)$ is a function in $\mathbb{F}(x)$ which is mapped to the function $t \in \mathbb{F}(t)$ via the isomorphism $\mathbb{F}(X) \rightarrow \mathbb{F}(t)$.  Consider the map $s(t) \mapsto s(\tau(x,y))$, this map takes $t$ to $\tau(x,y)$,  also it is a isomorphism, thus the map defines an isomorphism $\mathbb{F}(t) \rightarrow \mathbb{F}(X)$.
Recall that $x\mapsto\varphi(t)$ and $y\mapsto\psi(t)$,  by using the field isomorphism properties we have $\tau(x,y) \mapsto \tau(\varphi(t),\psi(t))$, also by the same map $\tau(x,y) \mapsto t$, and we conclude that

\[t=\tau(\varphi(t),\psi(t))\]

Similarly, $t \mapsto \tau(x,y)$ implies $\varphi(t) \mapsto \varphi(\tau(x,y))$, and also by the same map $\varphi(t) \mapsto x$, thus we conclude that (with similar argument for $y \mapsto \psi(t)$ )

\[\varphi(\tau(x,y))=x \qquad \text{and} \qquad \psi(\tau(x,y))=y\]

for any points in the curve. But the thing is not so smooth here, suppose that $\tau(x,y)=\frac{p(x,y)}{q(x,y)}$, then for in any points $(x_0,y_0)$ such that $q(x_0,x_0)=0$, we can't find such $t_0$ we want.  Luckily, there is only finitely many points  $(x_0,y_0) \in X$, such that $q(x_0,y_0)=0$, since $q(x,y)$ is not divisible by $f(x,y)$. The value of $t$ for which the parametrization fails are all $t_0$ that is the common root of the denominator $\varphi(t)$ and $\psi(t)$ , thus when $t_0=\tau(x_0,y_0)$ is the common root  of the denominator of  $\varphi(t)$ and $\psi(t)$, we have $\frac{p(x_0,y_0)}{q(x_0,y_0)}=t_0$, we assert that there can be only finite points $(x_0,y_0)\in X$ such that this can happen. Suppose that $p(x,y)-t_0 q(x_y)=0$ for infinitely many points on $X$, thus $f(x,y) | p(x,y)-t_0 q(x,y)$, which implies $\tau(x,y)=t_0$ up to the equality on $\mathbb{F}(X)$, which is absurd.

Therefore we conclude that

Except for some finite points in $X$, any point $(x_0,y_0) \in X$ can be represented as parameterization $x_0 = \varphi(t_0)$ and $y_0=\psi(t_0)$ and also for any $t_0 \in\mathbb{F}$, but some finitely many points, we can produce the point  $(\varphi(t_0),\psi(t_0)) \in X$.


Actually we've got something more, from $t=\tau(\varphi(t),\psi(t))$ , we see that the point $t_0$ is uniquely determined by the point $(x_0,y_0) \in X$, therefore our representation is unique. Continue Reading

OSN 2010 hari kedua

OSN 2010 hari kedua

03:41:00   Olimpiade Matematika,

Soal hari kedua sedikit lebih susah dari hari pertama, ini adalah solusi untuk soal-soal hari kedua (keuali soal no 8, dengan alasan yang sama). Untuk solusi untuk soal no 5,  ide awal nya (invariant principle) bukan ide saya sepenuh nya (at the beginning I even didn't understand the problem ^^)


Soal 5. (Hendrata Darmawan) 
Sebanyak $m$ orang anak laki-laki dan $n$ orang anak perempuan $(m> n)$ duduk mengelilingi meja bundar diawasi oleh seorang guru, dan mereka melakukan sebuah permainan sebagai berikut. Mula-mula sang guru menunjuk seorang anak laki-laki untuk memulai permainan. Anak laki-laki tersebut meletakkan sekeping uang logam di atas meja. Kemudian bergiliran searah jarum jam, setiap anak melakukan gilirannya masing-masing. Jika anak tersebut laki-laki, ia menambahkan sekeping uang logam ke tumpukan di atas meja, dan jika anak tersebut perempuan, ia mengambil sekeping uang logam dari tumpukan tersebut. Jika tumpukan di atas meja habis, maka permainan berakhir saat itu juga. Perhatikan bahwa tergantung siapa yang ditunjuk oleh sang guru untuk memulai langkah pertama, maka permainan tersebut bisa  cepat berakhir, atau bisa saja berlangsung paling sedikit $1$ putaran penuh. Jika sang guru menginginkan agar permainan tersebut berlangsung paling sedikit $1$ putaran penuh, ada berapa pilihan anak laki-laki yang dapat beliau tunjuk untuk memulai?

Solusi:

Sebut anak laki-laki pada permainan tersebut jack jika dan hanya jika apabila permainan dimulai dari anak tersebut, maka permainan akan berlangsung setidaknya satu putaran. Anak laki-laki yang tidak demikian disebut non-jack.

Pertama-tama kita pahami maksud soal ini lebih baik, sebanyak $m+n$ orang anak sudah duduk di meja bundar, dan sang guru harus memilih satu orang jack, diantara $m$ orang anak laki-laki tersebut,  yang akan dicari adalah ada beberapa banyak pilihan jack dari $m$ orang anak laki-laki yang ada.

Ambil sebarang jack, kita tinjau apa yang terjadi apabila permainan sudah berlangsung satu putaran, misalkan pada saat putaran terjadi, terdapat $x$ koin di meja. Pada saat itu, $n$ orang anak perempuan telah ikut bermain. Untuk mencari berapa kemungkinan jack yang mungkin, kita lakukan langkah berikut:
Untuk tiap-tiap satu anak perempuan pada permainan, kita keluarkan dari permainan, diikuti dengan tepat satu pemain laki-laki, yang bukan jack  yang memulai permainan.
Hal ini tidak mengubah banyak koin yang ada di meja, dan karena ada $n$ anak perempuan dan $m>n$, maka prosedur ini dapat terus dilakukan hingga tersisa $m-n$ orang anak laki-laki.

Apabila permainan dimulai dari salah satu dari $m-n$ orang anak laki-laki ini, dengan memasukan kembali semua anak perempuan dan anak laki-laki yang telah di keluarkan pada prosedur sebelumnya ke tempatnya semula, kita peroleh bahwa $m-n$ orang anak laki-laki tersebut adalah jack.


Jadi jawaban nya adalah $m-n$.


Soal 6. (Raja Oktovin)
Cari semua bilangan asli $n>1$ demikian sehingga

\[\tau(n)+\varphi(n)=n+1.\]

Dalam hal ini, $\tau(n)$ menyatakan banyaknya bilangan asli yang habis membagi $n$ dan $\varphi(n)$ menyatakan banyaknya bilangan asli yang kurang dari $n$ dan relatif prima terhadap $n$.

Solusi:

Misalkan \[X_n:=\{d \in \mathbb{N} : d | n\}\qquad Y_n:=\{m \in \mathbb{N} : \text{FPB}(m,n)=1\}.\]
Maka $\tau(n)=|X_n|$ dan $\varphi(n)=|Y_n|$, dan kita harus mencari $n$ sehingga $|X_n|+|Y_n|=n+1$. Perhatikan juga bahwa $X_n \cap Y_n = \{1\}$, sehingga $|X_n \cup Y_n|=|X_n|+|Y_n|-1$, dan Jika $n$ adalah bilangan yang memenuhi syarat pada soal maka haruslah \[|X_n \cup Y_n| = n\]

Karena untuk setiap $x\in X_n$ berlaku $1\leq x \leq n$ dan $X_n \subset N_n$ dan $Y_n \subset N_n$ dimana $N_n=\{1,2,\cdots,n\}$. Jadi $X_n \cup Y_n \subset N_n$ dan karena $|X_n \cup Y_n|=n= |N_n|$ maka $X_n \cup Y_n = N_n$.

Misalkan $p$ adalah faktor prima terkecil dari $n$, dan $\alpha$ adalah bilangan asli sehingga $p^{\alpha} | n$ dan $p^{\alpha+1} \not | n$. Jika $p^{\alpha+1}\leq n$ maka $p^{\alpha+1} \in N_n$ sehingga $p^{\alpha+1} \in X_n \cup Y_n$, namun $\text{FPB}(p^{\alpha+1},n) \neq 1$ dan $p^{\alpha+1} \not | n$, jadi tidak mungkin $p^{\alpha+1} \leq n$. Kita peroleh $p^{\alpha+1}>n$, dan karena $p$ adalah bilangan prima terkecil yang membagi $n$, maka haruslah $n=p^{\alpha}$, karena jika ada bilangan prima lain katakanlah $q\neq p$ sedemikian sehingga $q | n$, maka $p^{\alpha}q | n$ mengakibatkan $p^{\alpha}{q}<n<p^{\alpha+1}$, kontradiksi dengan $p$ adalah faktor prima terkecil. Dari $n=p^{\alpha}$ kita peroleh $\tau(n)=\alpha+1$, semua bilangan yang tidak relatif prima dengan $p^{\alpha}$ pasti berbentuk $kp$ dimana $k=1,2,\cdots,p^{\alpha-1}$, jadi ada $p^{\alpha}-p^{\alpha-1}$ bilangan diantara $1$ sampai $p^{\alpha}$ yang relatif prima dengan $p^{\alpha}$, diperoleh $\varphi(n)=p^{\alpha}-p^{\alpha-1}$, dan syarat pada soal menjadi
\[(\alpha+1)+p^{\alpha}-p^{\alpha-1}=p^{\alpha}+1 \Longleftrightarrow \alpha=p^{\alpha-1}\]  
Jadi sekarang akan dicari semua pasangan bilangan $(\alpha,p)$ yang memenuhi $\alpha=p^{\alpha-1}$ dimana $p$ bilangan prima.

Perhatikan bahwa untuk sebarang prima $p$ dan $\alpha=1$, maka persamaan diatas selalu benar, jadi jika $n$ bilangan prima maka persamaan $\tau(n)+\varphi(n)=n+1$ terpenuhi.  Sekarang akan dicari solusi yang bukan bilangan prima.

Jika $\alpha=2$ maka diperoleh $2=p$ sehingga $n=4$, dapat dicek bahwa $\tau(4)+\varphi(4)=5=4+1$. Sekarang misalkan $\alpha \geq 3$, berdasarkan ketaksamaan bernoulli (atau dengan teorema binomial) diperoleh
\[\begin{align*}\alpha&=p^{\alpha-1}\\ &=(1+p-1)^{\alpha-1}\\ &\geq 1+(p-1)(\alpha-1)\\ &=1+(p-1)\alpha-(p-1)\\ &=2+(p-1)\alpha-p\end{align*}\]

dengan tanda samadengan terjadi jika dan hanya jika $\alpha-1=1$ atau $p-1=0$, dimana untuk kasus ini tidak mungkin terjadi. Jadi kita peroleh $\alpha=p^{\alpha-1}$ mengakibatkan $\alpha>2+(p-1)\alpha -p$ yang setara dengan $\alpha(p-2)>\alpha(p-2)$, kontradiksi. Jadi tidak ada solusi untuk $\alpha\geq 3$.

Sehingga bilangan asli $n>1$ yang memenuhi adalah $n=4$ dan $n$ bilangan prima.


Soal 7. (Raja Oktovin)
Misalkan $a$ dan $b$ bilangan real positif. Diberikan polinom $F(x)=x^{2}+ax+b$ dan $G(x)=x^{2}+bx+a$ sehingga semua akar dari polinom $F(G(x))$ dan $G(F(x))$ adalah bilangan real. Buktikan bahwa $a$ dan $b$ lebih dari $6$.

Solusi: 

Dengan memfaktorkan $F(x)$ kita peroleh

\[F(x)=\left[x-\left(\frac{-a+\sqrt{a^2-4b}}{2}\right)\right]\left[x-\left(\frac{-a-\sqrt{a^2+4b}}{2}\right)\right].\]

Jadi

\[F(G(x))=\left[G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)\right]\left[G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)\right].\]

Karena $F(G(x))$ harus mempunyai akar real maka $G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)$ dan $G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)$ juga harus punya akar real, jadi mempunyai kedua diskriminant persamaan kuadrat diatas harus tak-negatif. Sehingga diperoleh
\[b^2-4\left(\frac{3a}{2}-\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\qquad b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Tambahkan kedua ketaksamaan diatas kita peroleh
\[b^2\geq 6a\]
Secara similar, dengan menukar peran $a$ dan $b$, dan karena $G(F(x))$ mempunyai akar real diperoleh
\[a^2\geq 6b\]
Jadi $b^4\geq 36a^2 \geq 6b \Rightarrow b^3\geq b \Rightarrow b\geq 6$, secara similar $a^4\geq 36b^2 \Rightarrow a\geq 6.$

Jika $a=6$, karena $a^2 \geq 6b$ diperoleh $36\geq 6b$ jadi kita peroleh $b \leq 6$, sehingga $b=6$. Begitu juga jika $b=6$ maka $a=6$. Namun untuk $a=b=6$, maka $F(G(x))=G(F(x))$ pandang lagi ketaksamaan diskriminant
\[b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Jika $a=b=6$ maka ketaksamaan diatas setara dengan $-\sqrt{12}\geq 0$ yang jelas salah, jadi diskriminant tidak positif, untuk $a=b=6$, dan disimpulkan $a>6$ dan $b>6$.


Soal 8. (Raja Oktovin)
Diberikan segitiga lancip $ABC$ dengan titik pusat lingkaran luar $O$ dan titik tinggi $H$. Misalkan $K$ sebarang titik di dalam segitiga $ABC$ yang tidak sama dengan $O$ maupun $H$. Titik $L$ dan $M$ terletak di luar segitiga $ABC$ sedemikian sehingga $AKCL$ dan $AKBM$ jajaran genjang. Terakhir, misalkan $BL$ dan $CM$ berpotongan di titik $N$ dan misalkan juga $J$ adalah titik tengah $HK$. Buktikan bahwa bahwa $KONJ$ jajaran genjang.

Solusi:

Continue Reading

OSN 2010 hari pertama

OSN 2010 hari pertama

21:19:00   Olimpiade Matematika, soal-soal,

Sedikit rileks, dengan soal-soal SMA, yang tidak mudah dan lumayan menarik. OSN tahun ini diadakan di Medan. Berikut adalah soal-soal beserta solusi nya (kecuali soal no 2, karena saya kurang begitu paham geometri). Solusi saya tulis sedetil mungkin, agar (menurut pendapat saya) mendapat nilai penuh di OSN untuk masing-masing soal.

Soal 1 (Fajar Yuliawan)
Misalkan $a,b,c$ adalah bilangan asli yang berbeda. Buktikan bahwa barisan \[a+b+c, ab+ac+bc, 3abc\]
tidak mungkin membentuk barisan geometri maupun aritmatika.

Solusi:
Misalkan barisan diatas membentuk barisan geometri, maka berlaku \[3abc(a+b+c)=(ab+ac+bc)^2\]
Misalkan $x=ab$, $y=bc$ dan $z=ac$ maka diperoleh

\[3(xy+yz+xz)=(x+y+z)^2 \Longleftrightarrow \frac{(x-y)^2+(y-z)^2+(x-z)^2}{2} =0.\]

Jadi diperoleh $x=y=z$, atau $ab=bc=ac$, dan karena $a,b,c \neq 0$, diperoleh $a=b=c$, kontradiksi.

Misalkan barisan tersebut membentuk barisan aritmatika, maka

\[a+b+c+3abc=2(ab+ac+bc)\]

persamaan diatas setara dengan

\[b(a-1)(1-c)+c(b-1)(1-a)+a(c-1)(1-b)=0.\]

Perhatikan bahwa karena $a,b,c$ bilangan asli maka

\[k=b(a-1)(1-c) \leq 0 \qquad l=c(b-1)(1-a) \leq 0\] \[m=a(c-1)(1-b) \leq 0.\]

Salah satu dari $k,l$ atau $m$ harus samadengan $0$, karena jika tidak demikian, $0=k+l+m<0+0+0=0$, kontradiksi.

Tanpa mengurangi keumuman, misalkan $k=0$, atau $b(a-1)(1-c)=0$, karena $b \neq 0$, maka $a=1$ atau $c=1$. Jika $a=1$ maka $l=0$ yaitu $k=l=0$, dan jika $c=1$ maka $m=0$ yaitu $k=m=0$ Jadi dapat kita simpulkan setidaknya dua buah  dari variabel $k,l$ atau $m$ samadengan $0$, dan karena $k+l+m=0$ maka $k=l=m=0$. Ini mengakibatkan

 \[b(a-1)(1-c)=0 \qquad a(c-1)(1-b)=0 \qquad c(b-1)(1-a)=0\]

Perhatikan $b(a-1)(1-c)=0$ dan $a(c-1)(1-b)=0$, jika $c\neq 1$ maka diperoleh $a=1$ dan $b=1$ kontradiksi karena $a$ dan $b$ berbeda,  jadi haruslah $c=1$, akan tetapi hal ini menyebabkan $0=c(b-1)(1-a)=(b-1)(1-a)$ yang setara dengan $a=1$ atau $b=1$, atau dengan kata lain salah satu dari $a$ atau $b$ samadengan $c$, kontradikisi karena $a,b$ dan $c$ semua berbeda.

Soal 2 (Fajar Yuliawan)
 Diberikan segitiga lancip $ABC$ dengan $AC>BC$ dan titik pusat lingkaran luar $O$ . Garis tinggi segitiga $ABC$ dari  $C$ memotong  $AB$ dan lingkaran luar segitiga  $ABC$ lagi berturut-turut di titik $D$ dan $E$. Garis melalui $O$ sejajar $AB$ memotong garis  $AC$ di titik $F$. Buktikan bahwa garis $CO$, garis melalui  $F$ tegak lurus $AC$, dan  garis melalui $E$  sejajar  $DO$ bertemu di satu titik.

Solusi:

Soal 3 (Raymond Christoper Sitorus)
Suatu kompetisi matematika diikuti oleh $120$ peserta dari beberapa kontingen. Pada acara penutupan, setiap peserta memberikan $1$ souvenir pada setiap peserta dari kontingen yang sama dan $1$ souvenir pada salah seorang peserta dari tiap kontingen lainnya. Di akhir acara, diketahui terdapat $3840$ souvenir yang dipertukarkan.
Berapa banyak kontingen maksimal sehingga kondisi di atas dapat terpenuhi?


Solusi:
Misalkan banyaknya kontingen adalah $n$, dimana kontingen ke-$i$ mempunyai $x_i$ orang peserta. Kita akan menghitung banyaknya souvenir yang dipertukarkan. Pertama-tama, setiap dua peserta pada satu kontingen pasti melakukan transaksi, dengan demikian pada tiap-tiap  kontingen ke-$i$ terjadi ${x_i\choose 2}$ transaksi.   Jika $a$ memberikan souvenir ke $b$ maka $b$ juga memberikan souvenir pada $a$, jadi setiap transaksi melibatkan dua buah souvenir. Jadi untuk masing-masing kontingen ke-$i$, banyaknya souvenir yang dipertukarkan di dalam satu kontingen adalah $2{x_i\choose 2}=x_i(x_i-1)$, untuk $i=1,2,\cdots,n$. Secara total banyaknya souvenir yang ditukarkan sesama peserta satu kontingen adalah

\[\sum_{i=1}^n x_i(x_i-1)\]

Selanjutnya akan dihitung jumlah souvenir yang ditukarkan antar kontingen. Setiap satu peserta pada kompetisi tersebut memberikan tepat satu souvenir pada tepat satu orang dari tiap kontingen yang lain, dan karena ada $n-1$ buah kontingen yang lain, maka tiap satu peserta memberikan $n-1$ buah souvenir. Karena ada $120$ peserta maka, total souvenir yang ditukarkan keluar kontingen adalah

\[120(n-1)\]

Jadi total souvenir yang dipertukarkan adalah

\[\sum_{i=1}^n x_i(x_i-1)+120(n-1)=3840.\]

Karena $\sum_{i=1}^n x_i =120$ maka

\[\sum_{i=1}^n x_i^2 +120(n-2)=3840 \Longleftrightarrow \sum_{i=1}^n x_i^2 +120n=4080\]

Perhatikan bahwa dengan RMS-AM diperoleh $\sqrt{\frac{\sum_{i=1}^nx_i^2}{n}}\geq \frac{\sum_{i=1}^n x_i}{n}=\frac{120}{n}$, jadi $\sum_{i=1}^n x_i^2 \geq \frac{120^2}{n}$. Diperoleh

\[4080\geq 120n +\frac{120^2}{n} \Longrightarrow 34 \geq n + \frac{120}{n} \Longrightarrow (n-30)(n-4)\leq 0 \] sehingga \[ 4\leq n \leq 30\]

Jadi $n$ maksimal adalah 30.

Sekarang akan ditunjukan bahwa , $n=30$, tercapai. Misalkan $a_{ij}$ menyatakan peserta ke-$i$ dari kontingen ke-$j$.  Jika kontingen dinyatakan sebagai $k_1, k_2, \cdots, k_{30}$, mak $k_i=\{a_{i1},a_{i2},a_{i3},a_{i4}\}$, sehingga $|k_i|=4$. Diperoleh banyak pertukaran souvenir adalah $30 \times 4(4-1)+120(29)=3840$.

Soal 4 (Nanang Susyanto)
Diketahui bahwa  $m $ dan $n$ adalah bilangan-bilangan asli dengan sifat

\[(mn)|(m^{2010}+n^{2010}+n)\]

Buktikan bahwa terdapat bilangan asli  $k$ sehingga $n=k^{2010}$.

Solusi:
Misalkan $d=\text{FPB}(m,n)$. Pertama-tama akan dibuktikan bahwa $d^{2010}|n$. Perhatikan bahwa $m=k d$ untuk suatu $k \in \mathbb{Z}$ dan $n=l d$ untuk suatu $l \in \mathbb{Z}$, jadi

\[d^{2010} k^{2010} + d^{2010} l^{2010} + n =x  kl d^2\]

atau setara dengan
\[\frac{n}{d^2}=x kl-d^{2008}k^{2010}-d^{2008}l^{2010} \in \mathbb{Z}\]

dengan kata lain $d^2 | n$. Apabila benar bahwa $d^i | n$, dimana $2\leq i\leq 2009$, diperoleh $n=l_id^i$ untuk suatu $l_i \in \mathbb{Z}$, sehingga

\[\begin{align*}d^{2010} k^{2010} + d^{2010} l^{2010} + n &= x kl_i d^{i+1} \Leftrightarrow \\ \frac{n}{d^{i+1}} &= x kl_i-d^{2009-i} k^{2010}-d^{2009-i}k^{2010} \in \mathbb{Z}.\end{align*}\]

Dengan demikian $d^i | n \Rightarrow d^{i+1} | n$ untuk $i=2,3,\cdots, 2009$, dan karena diketahui $d^2 | n$ maka $d^3 | n , d^4 | n, \cdots d^{2010} | n$, sehingga diperoleh $d^{2010} | n$.

Misalkan $n=s d^{2010}$, untuk suatu $s \in \mathbb{Z}$. Akan dibuktikan bahwa $s=1$. Kita peroleh

\[\begin{align*}d^{2010} k^{2010} + d^{2010^2} s^{2010} + s d^{2010} &= x m s d^{2010} \Longrightarrow \\ k^{2010}+d^{2009\cdot 2010}s^{2010}+s&=x ms\end{align*}\]

sehingga diperoleh $s | k^{2010}$. Jika $s \neq 1$, maka ada bilangan prima $p$ sehingga $p | s$, dan karena $s | k^{2010}$, maka $p|k^{2010}$, mengakibatkan $p | k$. Ini berarti $m=kd=(pu)d = (pd) u$, untuk suatu $u \in \mathbb{Z}$ dan $n=sd^{2010}=(pv)d^{2010}=(pd)vd^{2009}$ untuk suatu $v \in \mathbb{Z}$, mengakibatkan  $pd | m$ dan $pd | n$, kontradiksi karena $pd>d = \text{FPB}(m,n)$.

Jadi $n=d^{2010}$.

Continue Reading