Oxolodon Space

New Tag [Unofficial Skripsi Advisor]

2012-01-26T06:09:00.000-08:00

Following the new semester, I have some of my junior working on their undergraduate thesis (so called skripsi) with me, since I cannot come to campus quite often, I'm planning to direct them on their skripsi via this blog (LaTex would help).

The tag is [Unofficial Skripsi Advisor] and will be indicated on its title post by abbreviation [UnSA].

The proofs that will be presented might also being found on the books. But, it will be described in detail. Also, some proofs might be also a new proof based on recent Journal (if it is more elementary than the already known proof).

IMO Problem-Linear Code-Probabilistic Method

2012-01-25T06:48:00.000-08:00

Yesterday on some studying session, we solved the following Combinatorics Problem which is an IMO 1998 problem 2 day 1.

IMO 1998/2

In a contest, there are $m$ candidates and $n$ judges, where $n\geq 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most $k$ candidates. Prove that

\[\frac{k}{m} \geq \frac{n-1}{2n}\]

On my way home from the session, I tried to transform the problem into following statement which might be related to Coding Theory

Given $v_1,v_2,\cdots,v_n$ are all vectors in $\mathbb{F}_2^m$ where $n\geq 3$ is an odd integer. If $k$ is an integer such that

\[k \leq \left\lfloor \frac{(n-1)m}{2n} \right\rfloor\]

then there exist vectors $v_i$ and $v_j$ with $1\leq i < j \leq n$, such that $d_H(v_i,v_j) \leq n-k-1$, where $d_H$ denotes the Hamming Distance on $\mathbb{F}_2^m$
Recall that Hamming Distance gives us the number of different components on two vectors.

To see how the second form is derived, we create an $m \times n$ matrix $A$ where the rows represent the candidates and the columns represent the judges. We assign to this matrix, the $ij$-component as follows:

\[[A]_{ij}= \begin{cases} 1 &\text{If candidate $i$ is accepted by judge $j$} \\\ 0 &\text{If candidate $i$ is rejected by judge $i$}\end{cases}\]

Now denote the $i$-th column vectors of $A$ by $v_i$ which is clearly in $\mathbb{F}_2^m$. The Hamming Distance $d_H(v_j,v_i)$ represents the number of different result obtained by judge $i$ compared to judge $j$. Since $v_i \in \mathbb{F}_2^n$, the number of the same results obtained by the pair of judges $i$ and judges $j$ is $n-d_H(v_j,v_i)$

By IMO 1998 problem, if the above quantity is known to be at most $k$ for every pairs $(v_i,v_j)$ then the inequality $\frac{k}{m} \geq \frac{n-1}{2n}$ holds. The contraposition of this statement asserts that:

If the inequality $\frac{k}{m} \geq \frac{n-1}{2n}$ failed to hold then there exist at least one pairs $(v_i,v_j)$ such that $n-d_H(v_j,v_i)$ is greater than $k$. Which is simplified to

If $k \leq \left\lfloor \frac{(n-1)m}{2n} \right\rfloor$ then $d_H(v_j,v_i) \leq n-k-1$.

Next we will use the standard notation of Linear Code in Coding Theory which is $(n,k,d)$ and immediately deduce the following Corollary

Corollary

For any odd integers $k\geq 3$ and integers $n$, there is no linear code $(n,k,d)$ whenever $d > \frac{2k^2-kn+n}{2k}$.

Proof : If such a code exists, then $d > \frac{2k^2-kn+n}{2k}$ implies $k-d < \frac{-n+kn-2k^2 + 2k^2}{2k} = \frac{n(k-1)}{2k}$ thus there exists two vectors $v_j$ and $v_i$ on $\mathbb{F}_2^n$ with $ d_H (v_i , v_j )< k-( k- d) = d$. Contradiction, since $d$ is the minimum distance.

The Official Solution can be found on IMO Compendium Book.

We can also prove this by Probabilistic Method which is a powerful method for proving existence (see The Probabilistic Method by Noga Alon & Joel H. Spencer)

Solution:

Take two judges randomly and uniformly, let $X$ be a random variable which count the number of times the random pairs of judges agree. We wish to prove the contraposition, that is whenever $\frac{k}{m} < \frac{n-1}{2n}$ then $X$ is greater than $k$, with positive probability (i.e $\text{Prob}(X > k) > 0$).

For, $i=1,2,\cdots,m$, let $X_i$ be the $\{0,1\}$-valued random variable which represent wether or not the candidates $i$ being agreed by the pair of judges. Here $X_i=1$ if the pair of judges agree and $0$ otherwise. Thus we have
\[X=X_1+\cdots+X_m\]
taking the Expected Value of the both sides and using the linearity of Expected Value, we have
\[E[X]=E[X_1]+\cdots+E[X_m]\]

Next, we calculate $E[X_i]=\sum_{X_i \in \{0,1\} } X_i \cdot \text{Prob}(X_i)$, since $X_i$ only has value $0$ or $1$, we have $E[X_i]=\text{Prob}(X_i=1)$. Let's calculate $\text{Prob}(X_i=1)$, which is the probability that the candidate $i$ being agreed by the pairs of judges. There are ${n \choose 2}$ possible pairs. Suppose that $t_i$ is the number of judges who accept candidate $i$, then $n-t_i$ is the number of judges who reject candidate $i$. The number of pairs of judges who accept $i$ is ${t_i \choose 2}$, and the number of pairs of judges who reject $i$ is ${n-t_i \choose 2}$. The total number of pairs of judges who agree on $i$ is ${t_i \choose 2}+{n-t_i \choose 2}$. And so

$E[X_i]=\text{Prob}(X_i=1) = \frac{{t_i \choose 2}+{n-t_i \choose 2}}{{n\choose 2}}$

Thus

\[E[X]=\sum_{i=1}^m \frac{{t_i \choose 2}+{n-t_i \choose 2}}{{n\choose 2}}\]

We prove that for odd $n$, the inequality ${t_i\choose 2}+{n-t_i \choose 2} \geq \frac{(n-1)^2}{4}$. Indeed, the inequality is equivalent to

\[(n-2t_i)^2 \geq 1 \Rightarrow t_i \leq \frac{n-1}{2} \mbox{ or } t_i \geq \frac{n+1}{2}\]

which is true, since the candidate is either being failed/accepted by at most $\frac{n-1}{2}$ judges or being failed/accepted by at least $\frac{n+1}{2}$.

Using this inequality we have

\[E[X]\geq m \frac{\left(\frac{n-1}{2}\right)^2}{\frac{n(n-1)}{2}} = \frac{m(n-1)}{2n}\]

by hypothesis $\frac{m(n-1)}{2n} > k$, so we have $E[X]>k$, thus $\text{Prob}(X>k) >0$, and hence we are done.

The essence of proof is actually no different with the official proof, which is shorter. But what all I want to rephrase here is the probabilistic method :D

Early Algebraic Variety, Coordinate Ring

2011-08-14T10:18:00.000-07:00

I wrote this up, because i don't want to forget it, I made a pdf files about variety, but hasn't finished it yet... It is hard to keep things alive in your mind, if you don't get used to it a lot, after I manage to bear algebraic geometry in my faculty through a student skripsi while ago I managed to write some stuffs about variety in an undergraduate level (of course for those who have familiar with commutative algebra).. Now it's going to fade again, maybe because some are not use with "many definitions" math (that is modern math :D)

Let's recall an important thing I wrote up in the previous post. For a closed set $X$ on the affine space $\mathbb{A}^n$, define the ideal

\[\mathfrak{A}_X :=\{f\in k[T_1,\cdots,T_n] | f(X)=0\}\]

The above is indeed an ideal, we can see it by construction of the map $\tau: k[T] \rightarrow k[X]$ where $k[X]$ is the ring of regular function.

Theorem

Let $X$ be a closed set of affine space $\mathbb{A}^n$, then the following are equivalent:
i) $X$ be an irreducible closed set
ii) $\mathfrak{A}_X$ is prime ideal
iii) $k[X]$ is integral domain.

Recall that for the ring $R$ and Ideal $I$, $R/I$ is integral domain iff $I$ is prime ideal (it's standard exercise in undergraduate algebra). By the isomorphism applied on $\tau:k[T]\rightarrow k[X]$, we have $k[X]\cong k[T]/\mathfrak{A}_X$, so we have the equivalence of ii) and iii).
Now we want to prove the equivalence of iii) and i) by negating the statement first and obtain $X$ is reducible if and only if $k[X]$ is not integral domain, or equivalently $k[X]$ has zero divisors.

Suppose that $X$ is defined by polynomials $F_i$. Let $r$ and $s$ be a zero divisor of $k[X]$, the set $A=\{y\in X | r(y)=0\}$ and $B=\{y\in X | s(y)=0\}$ define closed sets (be cautious that $r$ and $s$ are not necessary polynomials, but still $A$ and $B$ are closed sets), which are propers subset of $X$, hence $A\cup B \subset X$, furthermore for any $x\in X$ we have $s(x)r(x)=0$ therefore $x\in A$ or $x\in B$, that is $x\in A\cup B$, and we also have $X\subset A\cup B$. Therefore $X=A\cup B$, and $X$ is reducible.

Suppose that $X$ is reducible, then we can find the closed set $A$ and $B$ such that $X=A\cup B$, consider $\mathfrak{A}_A$ and $\mathfrak{A}_B$, since $A\subset X$ and $B \subset X$ we have by Theorem on previous post $\mathfrak{A}_X \subset \mathfrak{A}_A$ and $\mathfrak{A}_X \subset \mathfrak{A}_B$. Since the subset is proper, we can take $F\in \mathfrak{A}_A$ and $G\in \mathfrak{A}_B$ such that $F,G\not\in \mathfrak{A}_X$, by this condition the regular function $f$ and $g$ in $k[X]$ whose representation is $F$ and $G$ respectively are both nonzero elements of $k[X]$ (if it is zero then $F,G\in \mathfrak{A}_X$ contradicting our choice of $F$ and $G$). Therefore $F(x)G(x)=0$ for all $x\in X$, thus $FG\in \mathfrak{A}_X$ and we conclude that in $k[X]$ the regular function $fg$ associate to a zero function, and since $f$ and $g$ are both nonzero in $k[X]$ with $fg=0$ in $k[X]$, thus $f$ and $g$ are zero divisor.

The Zariski Topology and The ring of Regular Function

2011-03-12T19:44:00.000-08:00

We know generalized the notation of Algebraic Curve defined in [ALGE I]. Here $k$ is an algebraic closed field.

We say a subset of $\mathbb{A}^n$ is closed set if the elements of $X$ are the common roots of some (system) of polynomial equations in algebraic closed field $k$. That is $X$ is a common solutions of $F_1=F_2=\cdots=F_k=0$. We say $F_i$ is a defining equations of $X$.

Suppose that we are given $\{X_{\alpha}\}_{\alpha \in \mathbb{I}}$, the collection of closed sets, where for each $X_{alpha}$ is defined by system of equations $F_{\alpha_i} = 0$, then

\[\bigcap_{\alpha \in J} X_\alpha\]

is also a closed set, since it is defined by the whole systems (putting all together) $F_{\alpha_i}=0$ for all $\alpha \in I$ and for all $i$.

Also, for any two closed set $X_1$ dan $X_2$, with system $F_i=0$ for $X_1$ and system $G_i=0$ for $X_2$, the set $X_1 \cup X_2$ is defined by the system $F_i G_j=0$ for all $i,j$.

And finally, the empty set and $\mathbb{A}^n$ are closed set, each defined by equation $1=0$ dan $0=0$, respectively.

Therefore Closed Set $X$ form a topology, we called this topology Zariski Topology.

Example:
Consider the Zariski Topology in the affine line $A^1$, any closed set $X$ in this topology is defined by a polynomial of one variable $F(x)=0$. Indeed, for any closed set $X$, we can associate and ideal $\mathfrak{A}_X=\{f \in k[x]\, | f(x)=0 \, \forall x \in X\}$ of $k[x]$, thus in particular $F \in \mathfrak{A}_X$. Furthermore, since $k[x]$ is a PID, we should have $\mathfrak{A}_X =(F)$, for some polynomial $F$, and thus any closed set $X$ is defined by equation $F(x)=0$, and since $k$ is algebraic closed we have $F(x)=(x-a_1)(x-a_2)\cdots(x-a_k)$ so that $X=\{a_1,a_2,\cdots,a_k\}$, that is a closed set of this topology are those set with finitely many elements. Conversely for any finite set $X=\{a_1,a_2,\cdots,a_k\}$ we can form a polynomial $F(x)=(x-a_1)\cdots (x-a_k)$ as the equation defining $X$, and so $X$ is a closed set. We conclude that all closed set of the Zariski Topology in $A^1$ are those finite set of $k$.

The ideal $\mathfrak{A}_X$ introduced in the above example, is important on characterizing the closed set. Another way to look at it, is as follow:

Let $k[T_1,T_2,\cdots,T_n]$ be the ring of polynomial of several variables, for convenience we will denote it further as $k[T]$. For any closed set $X$, consider all function $f: X \rightarrow k$ such that there exists $F\in k[T]$ satisfy $F(x)=f(x)$ for all $x \in X$. Such a function $f$ is called regular function.
We can form the ring $k[X]$, consisting all regular function on $X$. Furthermore any $f \in k[T]$ we include $f|_X \in k[X]$ (the restriction function of $f$ in X). We can check that $k[X]$ form a ring with usual addition and multiplication of functions.

Consider the homomorphism $\psi : k[T] \rightarrow k[X]$, which send any $f \in k[T]$ to $f|X \in k[X]$, $\psi$ is easily checked to be a homomorphism and since $k[X]$ is regular $\psi$ is also onto. The kernel of $\psi$ is
\[\{F \in k[T] |\,F(P)=0 ,\forall \, P \in X \}\]
which is exactly $\mathfrak{A}_X$. Moreover by isomorphism theorem we have $k[T]/\mathfrak{A}_X \cong k[X]$.
This proves that $k[X]$ is determined by the ideal $\mathfrak{A}_X$.

Remark:By Hilbert Basis Theorem, every ideal in $R[T]$ where $R$ is a nonetherian ring is finitely generated. Here $R=k$ is a field (which has $(0)$ or $k$ only has ideals) therefore clearly nonetherian ring, thus $k[T]$ is finitely generated. Being the homomorphic image of $k[T]$, $k[X]$ must also finitely generated

More interesting from the remark is that $\mathfrak{A}_X$ being an ideal is also finitely generated, therefore any closed set $X$, can be described as the common roots of finitely many polynomial equations!
This could be noted more, that whenever $F_i$ are the defining equations of $X$, it is not always the case that $\mathfrak{A}_X=(F_1,\cdots,F_k)$. Clearly by definition $F_i \in \mathfrak{A}_X$. Since $\mathfrak{A}_X$ is finitely generated say by $G_i$ (which can be obtained as Grobner Bases), we can take $G_1=G_2=\cdots=G_l=0$ as the defining equation of $X$.

Furthermore, suppose that $f\in k[X]$ is vanish at all points for which $g_1,\cdots,g_k \in k[X]$ are also vanish, we can associate $F\in k[T]$ as an inverse image of $f$ under homomorphism $\psi$, and similarly $G_i\in k[T]$ for each $g_i$ mentioned above. By Hilbert Nullstellensatz, since $F$ vanish at the same the points as $G_i$, and also in $F_i$ (the defining equations of $X$) therefore we have $F^r \in (G_1,G_2,\cdots,G_k, F_1,F_2,\cdots,F_l)$, and we have $f^r \in (g_1,\cdots,g_k)$ (since all $F_i$ is associate to zero polynomials in $k[X]$ by $\psi$.)

Theorem
Let $X$ and $Y$ be closed sets. Then $Y \subset X$ if and only if $\mathfrak{A}_X \subset \mathfrak{A}_Y$

proof:

Suppose that $Y \subset X$, take $f\in \mathfrak{A}_X$, then $F(P)=0$ for all $P \in X$, since $Y \subset X$, therefore for every $Q\in Y$ we should have $F(Q)=0$, thus $f\in \mathfrak{A}_Y$.
Now suppose that $\mathfrak{A}_X \subset \mathfrak{A}_Y$ and $Y \not \subset X$, that is there exists $Q \in Y$ such that $Q \not \in X$. Suppose that $\mathfrak{A}_X=(G_1,G_2,\cdots,G_k)$ , then $G_i \in \mathfrak{A}_X \subset \mathfrak{A}_Y$, therefore we have $G_i(Q)=0$, and hence $F(Q)=0$ for all $F \in \mathfrak{A}_X$, thus in particular $Q$ is a common root of the defining equations of $X$, and hence $Q\in X$, a contradiction.

Bacot-Bacot tentang definisi limit

2011-02-24T00:28:00.000-08:00

Salah satu tantangan bagi seorang pengajar Kalkulus adalah bagaimana memberikan penjelsan pada konsep limit yang menggambarkan hubungan yang jelas antara intuisi dan definisi.

Kebanyakan orang yang berlatar math, jika ditanya "limit itu apa?" maka bagi yang tau definisi akan langsung menjawab menggunakan epsilon-delta, lalu apabila ditanya lebih lanjut, "mengapa demikian?" , maka dapat menjawab "karena itu definisi".

Sekarang jika misalkan kita diberikan definisi limit seperti ini:

$\exists\, \delta>0 \forall \epsilon>0 \, \ni \forall \, x\in\text{dom}(f)\, (0<|x-c|<\delta\Rightarrow |f(x)-L|<\epsilon)$

atau

$\exists\,\epsilon>0\forall\delta>0 \,\ni \forall \, x\in\text{dom}(f)\, (0<|x-c|<\delta\Rightarrow |f(x)-L|<\epsilon)$

atau

$\exists\,\delta>0 \,\ni \forall \, x\in\text{dom}(f)\, (0<|x-c|<\delta\Rightarrow \forall\,\epsilon>0\, |f(x)-L|<\epsilon)$atau (saya memperoleh ini ketika saya pertama kali mencoba mencari definisi tentang limit)

\[\begin{align*}\exists \, &s:\mathbb{R^{+}}\cup\{0\}\rightarrow\mathbb{R^{+}}\cup\{0\}\,\text{monoton naik dan $s(0)=0$}\\ \ni \, &\forall \delta>0 \,\forall x \, (|x-c|<\delta \Rightarrow \, |f(x)-L|<s(\delta))\end{align*}\]

Mau percaya begitu aja??

Yang pertama menyatakan bahwa terdapat suatu batas jarak antara $x$ dan $c$ sedemikian sehingga pada batas tersebut, jarak antara $f(x)$ dan $L$ dapat dibuat sekecil mungkin. Hal ini salah karena pada saat kita menentukan suatu batas jarak dari $x$ dan $c$, jarak antara $f(x)$ dan $L$ secara otomatis akan tertentu, sehingga pernyataan diatas terlalu naif untuk benar (dapat benar jika $f(x)$ konstan)

Yang kedua lebih jauh dari makna limit, yaitu menyatakan ketika $x$ dan $c$ dapat sedekat mungkin, maka jarak $f(x)$ dan $L$ tidak akan melebihi suatu kuantitas, sangat bertentangan dengan menyatakan $L$ adalah limit dari $f$.

Yang ketiga menyatakan terdapat suatu batas jarak antara $x$ dan $c$ sehingga pada nilai-nilai $x$ di bawah batas jarak tersebut, $f(x)$ dan $L$ menjadi lebih dekat dari apapun. Kesalahannya terletak pada kenyataan bahwa, $f(x)$ menjadi lebih dekat dari apapun, berarti $f(x)=L$ pada saat $|x-c|<\delta$, sedangkan hal ini tidak mesti benar.

Yang keempat terlalu ribet dan rekursif, karena berarti mencari fungsi $s$ yang memenuhi $\lim_{t \rightarrow 0} s(t)=0$. meskipun ini benar dengan teorema apit.

Memang dalam matematika, definisi adalah hak bebas bagi seorang matematikawan untuk menciptakan nya, tapi tentunya juga menurut etika yang ada dalam cabang ilmu tersebut, definisi itu harus konsisten dan pas dengan yang dituju, dan pada perkembangannya, matematikawan akan memilih definisi yang paling umum dan konsisten.

Sebelum pengetahuan kita tentang definisi yang sebenarnya "mengganggu motivasi murni" kita, anggap kita adalah orang yang tidak tahu apa-apa tentang definisi limit dalam $\epsilon-\delta$. Misalkan anda hidup dijaman sebelum Bolzano, Cauchy dan Weierstrass memberikan definisi yang formal $\epsilon-\delta$ tentang limit atau misalkan anda sebagai teman dekat dari Sir Isaac Newton, diminta oleh Newton sendiri untuk membantunya memformalkan konsep limit dalam bahasa matematika. cukup menghayalnya :D mari kita mulai dengan pertanyaan:

Apakah itu limit dari sebuah fungsi?

Untuk membantu intuisi kita, mari lihat grafik dari $f(x)=\frac{\sin x}{x}$

Jika ditanya $\lim_{x\rightarrow 0} \frac{\sin x}{x}$ maka jawabannya adalah 1, yakin? kenapa 1? karena dari gambar grafik $f(x)$ menuju nilai $1$. Hal ini juga disokong oleh fakta numerik berikut

\[\begin{array}{lcr} x & \frac{\sin x}{x} \\ 0.5 & 0.9588 \\ 0.1 & 0.9983 \\ 0.095 & 0.9984 \\ 0.05 & 0.9999\end{array}.\]

tapi tetap saja, hal ini tidak cukup memuaskan secara matematika. Yang dapat kita maknai disini adalah dalam menyatakan suatu limit, kita sebelumnya sudah mempunyai sebuah angka yang "sepertinya" merupakan limit dari $f(x)$, yaitu $L$.

Berawal dari hal ini, definisi yang kita punya nanti harus dapat memberikan garansi penuh bahwa $L$ yang kita punya adalah limit tersebut. Dengan kata lain, definisi memberikan jawaban dari tantangan :

"Apabila anda berani mengatakan bahwa $\large L$ adalah limit dari $\large f(x)$ ketika $\large x$ menuju $\large c$, tunjukkan pada saya"

Dengan demikian kita memilih satu buah $L$ dari tak-hingga dan tak-terhitung kemungkinan bilangan real, dan kita cek apakah $L$ memenuhi definisi kita. We'll see it later :D..

Notasi Limit adalah

\[\lim_{x \rightarrow c} f(x)=L\]

dapat menyatakan:

"Apabila $x$ bergerak menuju $c$ maka $f(x)$ bergerak menuju $Lquot;.

Dalam bahasa lain, "apabila $x$ dan $c$ semakin dekat maka $f(x)$ semakin dekat dengan $Lquot;. Pernyataan ini kita ambil sebagai definisi intuitif. Adalah hal yang ingin kita abstrakkan, tentunya dengan beberapa tambahan sebagai berikut:

Nilai $L$ harus unik.
Nilai $f(c)$ tidak harus terdefinisi dan kalaupun terdefinisi tidak harus sama dengan $L$.

Sangat kritis apabila ditanyakan ulang: Mengapa kita yakin ini benar? Bagaimana jika kita tidak mendapatkan cara pikir seperti diatas? Bagaimana jika dengan cara berpikir yang beragam definisi yang diperoleh jadi beda?

Kita bisa saja mendapatkan definisi yang beda, tapi apakah hal tersebut sesuai dengan kesepakatan?

Apabila dari awal kita sudah menentukan tujuan dan maksud dari menyatakan limit, maka hampir dapat dipastikan bahwa hanya ada satu definisi yang mungkin, terlepas dari ekuivalen antar definisi.

Pada hal ini, untuk maksud apa kita mendekatkan $x$ dengan $c$? karena harapannya agar $f(x)$ dekat dengan suatu nilai $L$, setelah sebelumnya menemukan nilai $L$ sedemikian sehingga jika $x$ semakin dekat dengan $c$ maka $f(x)$ semakin dekat dengan $L$.

Dengan kata lain nilai $L$ disebut suatu limit dari $f(x)$ berarti $L$ adalah nilai terakhir (ultimate) yang paling dekat dengan $f(x)$ ketika $x$ menuju $c$, lebih tegasnya tidak ada bilangan lain yang sedekat $L$ dengan $f(x)$ pada saat $x$ dekat dengan $c$. Dapat diringkas:

3. Berkaitan dengan tambahan (1), nilai $L$ adalah nilai yang ultimate, tidak ada nilai lain yang merupakan approksimasi atau pendekatan yang lebih baik dari $f(x)$ selain dari $L$, ketika $x$ dekat $c$.

Yang menjadi fokus kita adalah seberapa dekat $f(x)$ dan $L$, dan hal yang dapat kita kontrol kita adalah variabel $x$ yang dapat kita geser-geser mendekat ke $c$. Seperti halnya jika anda ditanya "Mengapa Limit dari $f(x)$ adalah $L$ ketika $x$ menuju $c$?" tentunya jawabannya secara ringkas akan fokus pada "karena $f(x)$ dan $L$ itu blablabla , ketika $x$ menuju $c$ atau dalam bentuk "karena ketika $x$ menuju $c$ $f(x)$ dan $L$ itu blablabla", dua jawaban tersebut fokus ke $f(x)$ dan $L$, sedangkan frasa "$x$ menuju $c$ hanyalah perulangan dari pertanyaan, begitu kan?

Mari kita telaah lagi kata "dekat" , untuk membahasakan ini, dibutuhkan notasi dari "dekat", dan hal ini tentunya berhubungan dengan "jarak". Yup dua objek dapat disebut dekat berdasarkan jaraknya. Khususnya pada dimensi satu, jarak antara titik $c$ dan $x$ adalah $|x-c|$ dan jarak antara $f(x)$ dan $L$ adalah $|f(x)-L|$:

"$L$ adalah bilangan sedemikian sehingga $|f(x)-L|$ kecil apabila $|x-c|$ kecil."

namun kekurangannya disini terletak pada persisi kata "kecil". Seperti pada tabel diatas, jarak $|x-0|$ dan $\left|\frac{\sin x}{x}-1\right|$ berubah-ubah hampir tak terduga jika tanpa perhitungan, dan jika dilihat dari gambar, sebenarnya perubahan antara keduanya berhubungan.

Masalahnya $|x-c|$ dan $|f(x)-L|$ mempunyai perubahan jarak yang berbeda, contoh nya $\left|\frac{\sin 0.5}{0.5}-1\right|=0.0412$ sedangkan $|0.5-0|=0.5$, terlebih lagi pada fungsi yang berbeda, perubahan jarak $|f(x)-L|$ juga akan berbeda. Jadi tujuannya adalah membuat $|f(x)-L|$ kecil dengan cara membuat $|x-c|$ kecil.

Karena perbedaan dalam perubahan mereka, mari kita nyatakan $|x-c|=\delta$ dan $|f(x)-L|=\epsilon$, karena $\delta$ dan $\epsilon$ tertentu maka nilai $x$ yang memenuhi dua persamaan tersebut akan berhingga (jadi seperti sistem persamaan dalam $x$). Kemudian menyatakan "kecil" berarti membatasi dengan standar kuantitas yg relatif, jadi tentunya lebih benar jika kita menyatakan $\delta>0$ sebagai bilangan sehingga $|x-c|<\delta$ dan $\epsilon>0$ adalah bilangan sehingga $|f(x)-L|<\epsilon$. Hal ini dapat mengantisipasi kata "kecil" yang kita peroleh sebelumnya, karena seperti yang telah dikatakan sebelumnya, kecil saja "tidak persisi" jadi penggunaan $ < \epsilon$ lebih flexibel.

Karena nilai dari fungsi $f(x)$ bergantung dengan $x$, maka definisi kita akan memuat bentuk proposisi $|x-c|< \delta \Rightarrow |f(x)-L|<\epsilon$.

Kontrol kita disini terletak pada variable $x$, karena $x$ adalah variabel yang digerakkan/berubah (oleh kita) menuju $c$, sedangkan $f(x)$ menuju $L$ adalah hasil implikasi nya. Sekarang informasi yang diperoleh adalah

"jarak $f(x)$ dan $L$ dapat menjadi sangat kecil seiring dengan mengecilnya jarak $x$ dan $c$, ketika $x$ berubah."

yang menganggu adalah "kecil", hal relatif ini susah dibahasakan dalam bahasa formal, contohnya $10^{-10}$ itu tidak kecil jika dibandingkan dengan $10^{-10^{10}}$. Tetapi "semakin kecil" lebih mudah dibahasakan. Maka dari itu, akan lebih baik apabila kita sebagai 'pemain' yang menentukan jarak-jarak tersebut, diberikan kontrol(untuk menentukan) pada nilai-nilai yang dapat semakin kecil. Kata kecil lebih aman dihilangkan pada $|x-c|$, karena kontrol kita pada variabel $x$ lebih baik, sedangkan untuk $|f(x)-L|$ bergantung dengan jenis fungsinya, yang pada kasus ini sebarang. Oleh karena itu diperoleh

"Dengan cara membatasi jarak $|x-c|$ menurut nilai $x$ yang berubah maka jarak $|f(x)-L|$ pada nilai $x$ tersebut akan ikut terbatasi"

Bagaimana menyatakan "Dengan cara" dalam notasi matematika, tentunya secara logika, apabila kita menyebut "dengan cara" maka hal tersebut berarti kita mempunyai suatu tujuan, dan untuk mencapai tujuan tersebut maka "dengan cara" blablabla.

Pada kasus ini tujuan nya adalah membatasi nilai $|f(x)-L|$. Oleh karena itu tentunya Logisn, jika kita tentukan terlebih dahulu tujuan kita, baru kemudian menuliskan bagaimana cara nya mencapai tujuan tersebut. Perhatikan juga bahwa nilai $x$ yang dimaksud harus berada dalam lingkup domain $f$, agar $f(x)$ terdefinisi. Diperoleh

"Untuk membatasi $|f(x)-L|$ berdasarkan variabel bebas $x$ yang berada pada domain dari fungsi $f$, dapat dilakukan dengan cara membatasi $|x-c|$ pada nilai $x$ tersebut"

Selanjutnya adalah memperjelas tujuan tersebut.

Seberapa banyak kita ingin membatasi $|f(x)-L|$?

Tentu saja sekecil mungkin.

Mengapa?

Karena untuk menjawab tantangan yang diberikan definisi, yaitu berani menyatakan bahwa $f(x)$ menuju $L$ atau berani menyatakan $L$ adalah limit dari $f(x)$, maka berarti berani menyatakan $|f(x)-L|$ sangat kecil, yang berarti jarak $f(x)$ dan $L$ sangat dekat, bahkan untuk lebih menjawab tantangan tersebut kita mungkin bisa mengatakan $f(x)$ dan $L$ dapat sedekat apapun yang kita mau. wahh, really? Iya, dengan demikian secara tak langsung kita telah menyatakan bahwa $L$ adalah bilangan yang paling dekat dengan $f(x)$, hal ini sesuai dengan sifat "ultimate" dari $L$.

Jika benar demikian maka definisi nya akan menjadi

"Kita dapat membuat $|f(x)-L|$ sekecil mungkin yang kita mau dengan cara membatasi nilai dari $|x-c|$ menurut variabel bebas $x$

dalam jarak ini berarti

"Kita dapat membuat jarak $f(x)$ dan $L$ sekecil mungkin yang kita mau dengan cara membatasi jarak $x$ dan $c$

Terlihat menjanjikan dan kuat untuk menjawab tantangan? Bisa dibilang jika pernyataan diatas benar - benar terpenuhi maka tantangan akan lebih dari terjawab, dengan kata lain, sesumbar yang menyatakan "dapat membuat $|f(x)-L|$ sekecil mungkin" bahkan terlalu memuaskan untuk mendefinisikan kata "dekat".

Mari kita mulai membentuk definisi diatas dengan notasi matematika (jika bisa), jika masih belum bisa, kita akan mengubah lagi kata-kata nya sampai penerjemahannya kedalam notasi matematika menjadi mungkin.

Apabila kita ingin membuat/menentukan jarak $f(x)$ dan $L$, maka kita tentukan suatu bilangan misalkan $\epsilon$ yang merupakan bilangan positif (karena jarak tidak negatif dan jika samadengan nol, berarti mereka berhimpit).
Menyatakan "sekecil mungkin", itu berarti kita dapat menerima $\epsilon$ yang berapapun asalkan positif.

jadi apabila diberikan suatu $\epsilon>0$ maka jarak $f(x)$ dan $L$ dapat dibuat lebih kecil dari $\epsilon$ tersebut, dengan kata lain $|f(x)-L|<\epsilon$

Dengan cara membatasi jarak $x$ dan $c$, berarti menentukan suatu $\delta$ sedemikian sehingga membuat ketaksamaan diatas benar ketika $|x-c|<\delta$.

Ringkasnya

Apabila diberikan suatu $\epsilon>0$ maka dapat ditemukan suatu $\delta>0$ sedemikian sehingga untuk semua $x$ pada domain $f$ pernyataan ($ \ni |x-c|<\delta \Rightarrow |f(x)-L|<\epsilon)$ benar

Oops kita melupakan aturan (2), yaitu $f(x)$ tidak mesti terdefinisi pada $x=c$, jadi syarat $|x-c|<\delta$ dapat direnggangkan menjadi $|x-c|<\delta$ dan $x\neq c$, dalam notasi dapat diringkas $0<|x-c|<\delta$. Sehingga, dalam notasi quantifer diperoleh

$\forall \epsilon>0 \, \exists \, \delta>0 \ni \forall \, x \in \text{dom}(f) \, (0<|x-c|<\delta \Rightarrow |f(x)-L|<\epsilon)$

oh well, welcome $\epsilon$! $\delta$ is here :D

Nah sekarang jika ditantang:

"Mengapa anda yakin $\lim_{x\rightarrow c} f(x) =L$ ?"

tinggal jawab:

"Karena saya yakin saya bisa membuat jarak dari $f(x)$ dan $L$ sekecil mungkin yang anda/saya mau dengan cara membuat jarak $x$ dan $c$ cukup dekat."

jika penantang masih tidak percaya, dan bekata : "ah masa?"

tinggal bilang:

"coba, anda mau nya $f(x)$ dan $L$ sedekat apa? nanti saya cari jarak $x$ dan $c$ yang sesuai agar $f(x)$ dan $L$ dapat sedekat yang anda mau tadi"

apabila kita sudah menghitung $\epsilon-\delta$ dari awal, maka untuk semua nilai $\epsilon$ yang diberikan penantang akan dapat kita berikan nilai $\delta$.. hal ini akan terus berlanjut sampai yang nantangin capek :D

[Part II] The first attempt in the difference of pi(x) and Li(x)

2011-02-16T23:43:00.000-08:00

Following the post from Part I , where we have

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

\[T_2(s)=\ln(s-1)+\ln \zeta(s),\]

\[T_3(s)=\sum_{p \text{ is prime}}\frac{1}{p^s}-\ln\zeta(s).\]

and $T_i(s)$ has derivative of order $n$ for $s\rightarrow 1^+$.

Now consider

\[-\frac{d^n T_3(s)}{d s^n} - \frac{d^n T_2(s)}{ds^n} - \frac{d^{n-1} T_1(s)}{ds^n}\]

by our previous result, the above derivative exist. So the result is finite. Looking at canceled terms from $-T_1^{(n)}(s)$ and $-T_2^{(n-1)}(s)$ those are $\ln (s-1)$ and $\frac{1}{s-1}$, and the canceled term for $-T_3^{(n)}(s)$ and $-T_2^{(n)}(s)$ is $\ln \zeta(s)$. We have the derivative equals

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

which is finite. Now we consider the real valued value of $s$, let say $t=\Re \, s$. Therefore

\[\pm\left(\sum_{p\text{ prime}}\frac{\ln^n p}{p^{t}}-\sum_{k=2}\frac{\ln^{n-1} k}{k^{t}}\right)\]

is finite for $t>1$, or precisely for $t \rightarrow 1^+$.

Taking the positive difference we have

\[S=\left(\sum_{p\text{ prime}}\frac{\ln^n p}{p^{t}}-\sum_{k=2}\frac{\ln^{n-1} k}{k^{t}}\right)\]

Now consider $\pi(x+1)-\pi(x)$ where $\pi(x)$ is the number of prime not exceeding $x$. We see that when $x$ is prime then $\pi(x+1)-\pi(x)$ equals to $1$, while when $x$ is not prime then $\pi(x+1)-\pi(x)$ equals $0$. Thus

\[\sum_{p\text{ prime}}\frac{\ln^n p}{p^{t}}=\sum_{k=2}^{\infty}(\pi(k+1)-\pi(k))\frac{\ln^n k}{k^{t}}\]

Ann expression $S$ can be written as

\[S=\sum_{k=2}^{\infty}\left[(\pi(k+1)-\pi(k))\frac{\ln^n k}{k^{t}}-\frac{\ln^{n-1} k}{k^{t}}\right]\]
\[=\sum_{k=2}^{\infty}\left[\pi(k+1)-\pi(k)-\frac{1}{\ln k}\right]\frac{\ln^n k}{k^{t}}\]

Now consider

\[\frac{1}{\ln x} - \int_x^{x+1} \frac{1}{\ln x}\,dx\]

By the mean value theorem for integral, there exists $c_x \in (x,x+1)$ such that $\int_x^{x+1}\frac{1}{\ln x}\,dx=\frac{1}{\ln c_x}$. Thus $\frac{1}{\ln x}-\int_x^{x+1} \frac{1}{\ln x}\,dx=\frac{1}{\ln x}-\frac{1}{\ln c_x}$ for some $c_x \in (x,x+1)$.
Since $c_x \rightarrow \infty$ whenever $x \rightarrow \infty$, we have

\[\lim_{x \rightarrow \infty}\frac{\frac{1}{\ln x}-\int_x^{x+1} \frac{1}{\ln x}\,dx}{\frac{1}{x}}=\lim_{x\rightarrow\infty}\left(\frac{x}{\ln x}-\frac{x}{\ln c_x}\right)=0\]

Thus there exists $K$ such that for $x>K$ we have $\left|\frac{1}{\ln x}-\int_x^{x+1} \frac{1}{\ln x}\,dx\right|<\frac{1}{x}$. We conclude that

\[T=T^{\prime}+\left|\sum_{k=K}^{\infty}\left(\frac{1}{\ln k}-\int_k^{k+1} \frac{1}{\ln x}\,dx\right)\frac{\ln^{n}k}{k^t}\right| < T^{\prime}+\sum_{k=K}^{\infty}\frac{\ln^{n}k}{k^{t}}\]

which converges to a finite value. Therefore

\[S+T = \sum_{k=1}^{\infty}\left(\pi(k+1)-\pi(k)-\int_k^{k+1} \frac{1}{\ln x}\,dx\right)\frac{\ln^{n}k}{k^{t}}\]

converges to a finite value.

Define the offset Logarithmic Integral Function by $\text{Li}(x)=\int_2^{x}\frac{1}{\ln x}\, dx$. Therefore

\[\pi(k+1)-\pi(k)-\int_k^{k+1} \frac{1}{\ln x}\,dx=[\pi(k+1)-\text{Li}(k+1)]- [\pi(k)-\text{Li}(k)]\qquad (1)\]

Now for the theorem itself:

[Theorem]
For $x\geq 2$, the inequality $|\pi(x)-\text{Li}(x)| < \frac{\alpha x}{\ln^n x}$ is true for infinitely many $x$, where $\alpha$ is a positive constant, and for a sufficiently large number $n$.

To prove this, suppose for the contrary, that is we can find positive constant $\alpha$, and bound a number $n$ such that there are only finite value of $x$ such that the inequality is true. Suppose $a$ is the the largest integer value of $x$, such that the inequality is true, and also satisfies $a>e^n$, thus for $x>a$, the inequality is not true and we have

\[|\text{Li}(x)-\pi(x)|\geq \frac{\alpha x}{\ln^n x}\qquad \qquad \ln x>n\]

Now let $U>a$ and consider the sum

\[R=C+\sum_{k=a+1}^{U}\left(\pi(k+1)-\pi(k)-\int_k^{k+1} \frac{1}{\ln x}\,dx\right)\frac{\ln^{n}k}{k^{t}}\]

where

\[C=\sum_{k=2}^{a}\left(\pi(k+1)-\pi(k)-\int_k^{k+1} \frac{1}{\ln x}\,dx\right)\frac{\ln^{n}k}{k^{t}}\]

by equation (1) and then Abel Summation by part we have

\[\begin{align*}&\sum_{k=a+1}^{U}\left(\pi(k+1)-\pi(k)-\int_k^{k+1} \frac{1}{\ln x}\,dx\right)\frac{\ln^{n}k}{k^{t}}\\ &=\sum_{k=a+1}^{t}\left([\pi(k+1)-\text{Li}(k+1)]- [\pi(k)-\text{Li}(k)]\right)\frac{\ln^{n}k}{k^{t+1}}\\ &=(\pi(U+1)-\text{Li}(U))\frac{\ln^n U}{U^{t}}-(\pi(a+1)-\text{Li}(a))\frac{\ln^n a}{a^t}\\ & \qquad\qquad-\sum_{k=a+1}^U [\pi(k)-\text{Li}(k)]\left[\frac{\ln^n (k)}{k^t}-\frac{\ln^n (k-1)}{(k-1)^t}\right]\end{align*}\]

By our hypothesis $(\pi(U+1)-\text{Li}(U))\frac{\ln^n U}{U^{s}}>\left(\frac{\alpha U}{\ln^n U}\right)\frac{\ln^n U}{U^{t}}=\frac{\alpha}{U^{s-1}}>0$.
Moreover by the mean value theorem, there exists $\xi\in[k-1,k]$ such that

\[\left[\frac{\ln^n (k)}{k^t}-\frac{\ln^n (k-1)}{(k-1)^s}\right]=\left(\frac{n}{\ln \xi}-t \right)\frac{\ln^{n}\xi}{\xi^{t+1}}\]

Thus

\[R>C-(\pi(a+1)-\text{Li}(a))\frac{\ln^n a}{a^t}+\sum_{k=a+1}^U[\pi(k)-\text{Li}(k)]\left(t-\frac{n}{\ln \xi}\right)\frac{\ln^{n}\xi}{\xi^{t+1}}\]

Consider $f(x)=\frac{\alpha x}{\ln^n x}$, then $f^{\prime}(x)=\alpha \left(1-\frac{n}{\ln x}\right)\frac{1}{\ln x}>0$ since $\ln x>n$ and $\alpha>0$, thus the function is increasing.

Since for $k\geq a+1$ and $k>\xi$ we have

\[[\pi(k)-\text{Li}(k)]\geq\frac{\alpha k}{\ln^n k}\geq\frac{\alpha \xi}{\ln^n \xi}\]

Writing $D=C-(\pi(a+1)-\text{Li}(a))\frac{\ln^n a}{a^t}$ we have

\[R>D+\sum_{k=a+1}^U\left(\frac{\alpha \xi}{\ln^n \xi}\right)\left(s-\frac{n}{\ln \xi}\right)\frac{\ln^{n}\xi}{\xi^{t+1}}=D+\alpha\sum_{k=a+1}^U\left(t-\frac{n}{\ln \xi}\right)\frac{1}{\xi^t}\]

Also note that $t>1$ and so $t-\frac{n}{\ln \xi} >1-\frac{n}{\ln\xi}$ thus we have

$R>D+\left(1-\frac{n}{\ln\xi}\right)\sum_{k=a+1}^U \frac{1}{\xi^t}$.

Letting $U \rightarrow \infty$ and then $t\rightarrow 1^+$, we have the right hand side is approaching $\infty$, while we already established that $\lim_{t\rightarrow 1^+} R$ is finite. Contradiction.

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

2011-01-21T20:38:00.000-08:00

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.

Riemann Hypothesis (post yang dulu tapi dalam Bahasa Indonesia)

2011-01-02T04:27:00.000-08:00

Saya tidak menyangka ada juga orang yang membaca post tentang Hipotesa Riemann yg saya buat beberapa bulan lalu. Terlebih lagi meminta saya menulis ulang dalam bahasa Indonesia. Ok, karena kemudahan teknologi copy-paste, tentunya tidak susah untuk menulis kembali semua equations yang ada pada post sebelumnya. Namun cukup sulit untuk menulis istilah-istilah matematika dalam bahasa Indonesia, karena belum ada yang baku.

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 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 (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] Semua akar tak-trivial dari fungsi $\zeta(s)$ berada pada garis kritis $\Re(s)=\frac{1}{2}$.

Pertanyaan yang langsung muncul disini adalah: bukannya deret tersebut divergen untuk $\Re(s) \leq 1$? Lalu mengapa disebutkan $\Re(s)=\frac{1}{2}$? Dan juga 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 ini hanya terdefinisi di $\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, hal ini dapat dilakukan 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, 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$ when $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 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.

Riemann Hypothesis for Dummies?

2010-11-18T05:23:00.000-08:00

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 I might don't understand the Hypothesis well, because even to describe it, the miscellaneous properties of the other special functions are used.

[ALGAE IV] Rational Curve and Rational Function.

2010-11-16T22:41:00.000-08:00

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.

OSN 2010 hari kedua

2010-08-06T03:41:00.000-07:00

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:

OSN 2010 hari pertama

2010-08-03T21:19:00.000-07:00

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\qquad 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 $\binom{x_i}{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\binom{x_i}{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 \Longrightarrow 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

\[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}.\]

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

\[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\]

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}$.

17th IMC Day 1. [part 1] Problem 1, Problem 2, Problem 3.

2010-07-27T04:21:00.000-07:00

In this part 1, i'll give some solution of the previous IMC 2010 problems. The problems are relatively easy compared to the last year.

Problem 1. Let $a\leq b$ where $a$ is a positive real number
\[\int_a^b(x^2+1)e^{-x^2}dx\geq e^{-a^2}-e^{-b^2}.\]

Solution: Okay, this is too easy for IMC, first we prove that $(x^2+1)e^{-x^2}\geq 2xe^{-x^2}$ for all $x\in [a,b]$, this would mean $x^2+1 \geq x \Longleftrightarrow (x-1)^2\geq 0$ which is obvious. Since $\int_a^b 2xe^{-x^2} \, dx = \int_{a}^{b} e^{-x^2} \, d\left(x^2\right)=-e^{-b^2}+e^{-a^2}.$

comment: This can be one of the easiest problem along with problem 1 day 1 in IMC 2007. No trick, quickly recognize and less trouble.

Problem 2. Compute the sum of the series
\[\sum_{k=0}^{\infty} \frac1{(4k+1)(4k+2)(4k+3)(4k+4)}=\frac{1}{1\cdot 2 \cdot 3 \cdot 4} +\frac{1}{5\cdot 6 \cdot 7 \cdot 8} +\dots .\]

Solution: There you go, so many ideas for this one.. I you have enough mental to do some tedeous computation, you can start with
\[\int_0^1 \int_0^t \int_0^u \int_v \sum_{k=0}^{\infty} x^{4k} \, dx \, dv \, du \, dt=\int_0^1 \int_0^t \int_0^u \int_0^v \frac{1}{1-x^4} \, dx \, dv \, du \, dt\].

For $0\leqx\leq v \leq u \leq t <1 $, the power series converges uniformly (by abel's test).
Notice that

\[\begin{align*}\int_0^v \frac{1}{1-x^4} \, dx &= \int_0^v \frac{1}{2}\left( \frac{1}{1-x^2} + \frac{1}{1+x^2}\right)\\ &=\int_0^v \frac{1}{4}\left( \frac{1}{1+x} + \frac{1}{1-x}\right) +\frac{1}{2}\arctan v \\ &= \frac{1}{4}\ln \left|\frac{1+v}{1-v}\right|+\frac{1}{2}\arctan v \end{align*}\]

Now for the second integral, first by partial integration we have $\int_0^u \ln |1-v| \, dv = (u-1)\ln |1-u|-u$ and similarly $\int_0^u \ln |1+v| \, dv = (u+1) \ln |u+1|-u$. Also, by partial integration we have
$\int_0^u \arctan v \, dv = u \arctan u - \int_0^u \frac{u}{1+u^2}= u \arctan u - \frac{1}{2} \ln |1+u^2|$

Yes, that is just second.. Now we can add them altogether yields

\[\frac{u}{4} \ln \left|\frac{1+u}{1-u}\right| + \frac{1}{4} \ln \left|\frac{1-u^2}{1+u^2}\right|+\frac{u}{2}\arctan u\]

First we compute

\[\int_0^t \frac{u}{2} \arctan u=\frac{1}{4} t^2 \arctan t -\frac{1}{4}\int_0^t \left(\frac{u^2}{1+u^2}\right)=\frac{1}{4}\left( (t^2 +1) \arctan t -t \right)\]

just finish it $\int_0^1\frac{1}{4}\left( (t^2 +1) \arctan t -t \right) dt$

$=\frac{1}{4} (\frac{t^3}{3}+t) \arctan t \right|_0^1 - \left(\int_0^1 \frac{t^3+t}{12(t^2+1)} + \frac{2t}{12(t^2+1)}dt\right) - \frac{1}{8}$

$=\frac{\pi}{12}-\frac{1}{24}+\frac{1}{12}\int_0^1 \frac{2t}{t^2+1}-\frac{1}{8} = \frac{\pi}{12}-\frac{1}{6}-\frac{1}{12} \ln 2.$

Then we compute
\[\int_0^t\frac{u}{4}\ln\left(\frac{1+u}{1-u}\right)\, dt=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)-\left(\int_0^t\frac{u^2}{4}\left(\frac{1}{1-u^2}\right)\dt\right)\]
\[=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)+\frac{1}{4}\int_0^t 1-\frac{1}{1-u^2}\, dt\]
\[=\frac{t^2}{8}\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}-\frac{1}{8}\ln\left(\frac{1+t}{1-t}\right)\]

and so $\int \left(\frac{t^2-1}{8}\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}\, dt=$
$\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)-\frac{1}{4}\int\left(\frac{\left(t^3-t\right)}{3(1-t^2)}-\frac{2t}{3(1-t^2)\right)}\, dt +\frac{t^2}{8}$
$=\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t^2}{24}+\frac{1}{12}\int \left(\frac{2t}{(1-t^2)\right)}\, dt +\frac{t^2}{8}$
$=\frac{1}{8}\left(\frac{t^3}{3}-t\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t^2}{24}-\frac{\ln(1-t^2)}{12} +\frac{t^2}{8}$
$\left(\frac{t^3}{24}-\frac{t}{8}-\frac{1}{12}\right)\ln(1+t)+\left(-\frac{t^3}{24}+\frac{t}{8}-\frac{1}{12}\right)\ln(1-t)+\frac{t^2}{6}.$
Therefore

\[\int_0^1 \left(\frac{t^2-1}{8}\right)\ln\left(\frac{1+t}{1-t}\right)+\frac{t}{4}\, dt=\frac{1-\ln 2}{6}\]

Lastly, we compute, $\int_0^1\int_0^t \frac{1}{4} \ln \left\frac{1-u^2}{1+u^2}\right|\,du$.

By partial integration
\[\frac{1}{4}\int_0^t \ln(1+u^2)\,du=\frac{1}{4}\left(u\ln(1+u^2)|_0^t-\int_0^t \frac{2u^2}{1+u^2}\right)\]
\[=\frac{t}{4}\ln(1+t^2)-\frac{t}{2}+\frac{\arctan t}{2}\]

Also by partial integration
\[\frac{1}{4}\int_0^t \ln(1-u^2)\,du=\frac{1}{4}\left(u\ln(1-u^2)|_0^t+\int_0^t \frac{2u^2}{1-u^2}\right)\]
\[=\frac{t}{4}\ln(1-t^2)-\frac{t}{2}+\frac{1}{4}\ln\left|\frac{1+t}{1-t}\right|\]

Therefore \[\frac{1}{4}\int_0^t \ln\left|\frac{1-u^2}{1+u^2}\right|\,dt=\frac{t}{4}\ln\left|\frac{1-t^2}{1+t^2}\right|+\frac{1}{4}\ln\left|\frac{1+t}{1-t}\right|-\frac{\arctan t}{2}\]

By previous computation $\int_0^1 \frac{\arctan t}{2}\,dt=\frac{t\arctan t}{2}-\frac{\ln(1+t^2)}{4}|_0^1=\frac{\pi}{8}-\frac{\ln 2}{4}$ and
$\frac{1}{4}\int_0^1 \ln\left|\frac{1+t}{1-t}\right|\,dt=\frac{(t+1)\ln(1+t)+(1-t)\ln(1-t)}{4}_0^1=\frac{\ln 2}{2}$ and
$\int_0^1\frac{t}{4}\ln\left|\frac{1-t^2}{1+t^2}\right|\,dt=\frac{-1}{2}\left(\frac{1}{4}\int_0^1\ln\left|\frac{1+t^2}{1-t^2}\right|\,d(t^2)\right)=\frac{-1}{2}\left(\frac{\ln 2}{2}\right)=\frac{-\ln 2}{4}$

Adding all numerical values we have the answer is
\[\frac{\ln(2)}{2}-\frac{\ln 2}{4}-\frac{\pi}{8}+\frac{\ln 2}{4}+\frac{\pi}{12}-\frac{1}{6}-\frac{\ln 2}{12}+\left(\frac{1-\ln 2}{6}\right)=\frac{\ln 2}{4}-\frac{\pi}{24}.\]

comment: This is a sudden-death problem, if you miscalculate the integral somewhere in the middle, you've wasted your valuable time nor you get a false answer. From the first minute i see the problem, i have so many ideas, but the surely one is the above. One possible idea is to use the Beta integral, or euler reflection formula. It is similar to the problem I solved in College Mathematical Journal years ago and the problem can be generalized to the following: Calculate
\[\sum_{k=1}^{\infty}\frac{m!}{\binom{mk}{m}} \qquad m\in \mathbb{Z} \qquad m>0\]
where in this problem $m=4$.

Problem 3. Define the sequence $x_1,x_2,\dots$ inductively by $x_1=\sqrt{5}$ and $x_{n+1}=x^2_n-2$ for each $n\geq 1.$ Compute
\[\lim_{n\to \infty} \frac{x_1\cdot x_2\cdots x_3\dots x_n}{x_{n+1}}.\]

Solution: We have $x_{n+2}=x_{n+1}^2-2$ thus $x_{n+2}-2=x_{n+1}^2-4=(x_{n+1}-2)(x_{n+1}+2)$.The function $f(x)=x^2-2$ is increasing for positive $x$, and since $x_2 >x_1$ by induction the sequence is increasing, also $x_1>1$ inductively implies $x_n>n$, and hence $x_n$ is unbounded increasing positive sequence. Thus $\lim \frac{1}{x_n}=0$.
and related to $x_2=3>2$, we have $x_n > 2$ for all $n$, or in particular $x_n \neq 2$ for all $n$. Thus
\[x_{n+1}+2 = \frac{x_{n+2}-2}{x_{n+1}-2}\]
and since $x_n=\sqrt{x_{n+1}+2}$ we have
\[x_n =\sqrt{\frac{x_{n+2}-2}{x_{n+1}-2}}}.\]
Now taking the product and telescoping we have
\[x_1 x_2 \cdots x_n =\sqrt{\frac{x_{n+2}-2}{x_2-2}}=\sqrt{x_{n+2}-2}=\sqrt{x_{n+1}^2-4}\]
and we wish to calculate
\[\lim_{n\to \infty} \frac{x_1\cdot x_2\cdots x_3\dots x_n}{x_{n+1}}=\lim_{n\rightarrow \infty} \sqrt{1-\frac{4}{x_{n+1}^2}}=1.\]

comment: As usual problem 3 is tricky, i spent quite a lot of time to figure it out, after the unsuccessful trigonometric substitution, hyperbolic estimation, i finally arrive to the telescoping relation. I believe there should be a nice trigonometric substitution for this problem.

Next part is problem 4 and problem 5.. I couldn't solve them if i was given only 5 hours. The post is still in the draft, since i only can solve problem 5 for the moment.. :)

[ALGE III] The Field Of Rational Function of The Irreducible Variety

2010-03-13T00:33:00.000-08:00

Let $X$ be an irreducible curve given by $f(x,y)=0$ in the algebraic closed field $\mathbb{F}$, then we define the set
\[\mathbb{F}(X)=\left\{\frac{p(x,y)}{q(x,y)} | p,q \in \mathbb{F}[x,y] \mbox{ and } f(x,y)\not | q(x,y) \right\}\]
Then $\mathbb{F}(X)$ contains the rational functions of two variables $x$ and $y$. We say two elements of $\mathbb{F}(X)$, $\frac{p_1(x,y)}{q_1(x,y)}$ and $\frac{p_2(x,y)}{q_2(x,y)}$ are equal in $X$ if and only if

\[f(x,y) | (p_1(x,y)q_2(x,y)-p_2(x,y)q_1(x,y))\]

It is easy to see that, along with this equality, $\mathbb{F}(X)$ is a field. We call $\mathbb{F}(X)$ is a Field of Rational Function on $X$ (or funcion field of algebraic variety $X$).
Before we proceed, we should aware that, the denominator of the rational function $\frac{p(x,y)}{q(x,y)} \in \mathbb{F}(X)$ can be zero only for finitely many points of $X$, that is $q(x,y)=0$ in a finite subset of $X$. This can be proved easily by using the Lemma in my first post [ALGE I]. It also can happen that, a rational function can be represented in two different expression $u=\frac{p(x,y)}{q(x,y)}$ and $\frac{p_1(x,y)}{q_1(x,y)}$ where $q(x,y)=0$ but $q_1(x,y) \neq 0$. If $u$ has the exspresion $\frac{p(x,y)}{q(x,y)}$ where $q(P) \neq 0$, then we say $u$ is regular at $P$.

Now suppose that $X$ is rational curve, then by using the parametrization of $X$, we can substitue $x=\varphi(t)$ and $y=\psi(t)$ to the rational function $u=\frac{p}{q} \in \mathbb{F}(X)$. The substitution takes any element of $\mathbb{F}(X)$ to the rational function of one variable in $t$. Notice that, the denominator $q(\varphi(t),\psi(t))$ can only equals zero in a finitely many times, by the same reason from the previous paragraph. Suppose that $u_1=\frac{p_1}{q_1}$ and $u_2=\frac{p_2}{q_2}$ are equals on $X$, then

\[p_1(x,y)q_2(x,y)- p_2(x,y) q_1(x,y) = \lambda(x,y) f(x,y)\]

substitute $x=\varphi(t)$ and $y=\psi(t)$, since $f(\varphi(t),\psi(t)) \equiv 0$ we have

\[\frac{p_1(\varphi(t),\psi(t))}{q_1(\varphi(t),\psi(t))}=\frac{p_2(\varphi(t),\psi(t))}{q_2(\varphi(t),\psi(t))}\]

thus, the substitution exhibit the map from $\mathbb{F}(X)$ to the $\mathbb{F}[t]$ (the field of rational function in $t$). This map is also an isomophism from $\mathbb{F}(X)$ to some subfield of $\mathbb{F}[t]$.
Now we can use Lüroth's Theorem to extend this property, that is it is indeed true that $\mathbb{F}(X)$ is isomorphic to $\mathbb{F}[t]$.

[ALGE II] Rational Parametrization of Algebraic Curve

2010-03-06T07:52:00.000-08:00

From the previous post, we know that any algebraic curve in the algebraic closed field can be decomposed into irreducible curves, which is a unique representation. So, it would be natural to look deeper on the irreducible curve. Recall that an algebraic curve $X$ defined by the equation $f(x,y)=0$, with irreducible polynomial $f(x,y) \in \mathbb{F}[x,y]$, where $\mathbb{F}$ is an algebraic closed field

We say an irreducible algebraic curve $X$ is a rational curve, whenever there exist rational functions $\varphi$ and $\psi$ at least one is non-constant, such that \[f(\varphi(t), \psi(t)) \equiv 0.\]
$\varphi$ and $\psi$ are rational parametrization of $f$.

It is not hard to prove that every degree two irreducible curves $X$ (a conic) are rational curves, take a point $(x_0,y_0) \in X$ then substitute $y=t(x-x_0)+y_0$ to the equation $f(x,y)=0$, solving for $x$ we will find $x=\varphi(t)$ and substituting back to $y=t(x-x_0)+y_0$ we will find $y=\psi(t)$.

Example: The Folium of Descartes is an algebraic curve $X$ defined by \[x^3+y^3-3axy=0\]
for the real number $a$.
Since $(0,0) \in X$, to get the rational parametrization we can try to substitute $y=tx$ yields
\[(t^3+1)x^3 - 3atx^2=0\]
for the points other than $(0,0)$ we have from the above equation the parametrization
\[x=\varphi(t)=\frac{3at}{t^3+1}\qquad\text{and}\qquad y=tx=\psi(t)=\frac{3at^2}{t^3+1}\]

The geometric interpretation is also obvious. As we can see in the picture below, we can draw a line not contain the point $(0,0)$. and for any point $P \in X$ we project it to the line $x=-1$ by making the line joining $(0,0)$ and $P$. Hence, each point of the curve (other than $(0,0)$) produce a unique point on the line $x=-1$, and each point on the line $x=-1$ produce a unique point (correspondence with the origin) on the curve.

here the points on the line $x=-1$ act like $t$ in the parametrization, the parameter $t$ is the slope of the produced lines. So that the point $(-1,1)$ (which means $t=-1$) does not produce any point of the curve except $(0,0)$. This also can be seen in the parametrization $\varphi(t)$ and $\psi(t)$, where when $t=-1$, the denominator of both is zero.

We have seen that, the parametrization is important on determining the point on the curve. When the curve $X$ satisfy some criterion, for a suitable choice of $\varphi(t)$ and $\psi(t)$, we can get a one-to-one correspondence map $t \rightarrow (\varphi(t),\psi(t))$, by excluding some finite points of the curve. This is really interesting, one possible application is to the theory of indeterminte equation. Suppose that $f(x,y)=0$ has rational coefficient, and suppose that the parametrization $\varphi(t)$ and $\psi(t)$ also have rational coefficient. If both $\varphi(t)$ and $\psi(t)$ are a bijection, we can list all the rational points of the curve, given we know only one point (for example, in the previous example we were given $(0,0)$ on the folium).

In the number theory, The Fermat Last Theorem, can be viewed as proving that a rational point of the of the curve $x^n+y^n-1=0$ does not exist.

Thus the problem whether a curve have a rational parametrization is essentially important.
Our next realm is to determine when a given curve is a rational curve?

[ ALGE I ] Introduction to the Plane Algebraic Curve

2010-03-05T22:24:00.000-08:00

Well i'm going to retell what i've studied from the algebraic geometry books so far.. one of my favorite book is the Basic Algebraic Geometry: Varieties in Projective Space By Shafarevich.

Let $\mathbb{F}$ be an algebraic closed field. An algebraic curve $X$ is the set of points $(x.y)$ defined by the equation \[f(x,y)=0\]
where $f(x,y) \in \mathbb{F}[x,y]$.
When $f(x,y)$ is an irreducible polynomial, we say $X$ is an algebraic irreducible curve.
The degree of $X$ is equal to $\text{deg}f$. The condition that $\mathbb{F}$ must be an algebraic closed field is necessary for the uniqueness of the degree of $X$.
For example the curve $(0,0)$ in the field of real numbers is defined by infinitely many equations that is $x^{2n}+y^{2n}=0$ for any positive integers $n$. For even $n$ the curve is irreducible, while whenever $n$ is odd, the curve is reducible.This confusion doesn't happen when $\mathbb{F}$ is an algebraic closed field. As we can prove it by the following very useful lemma:

Lemma: Let $\mathbb{F}$ be a field, given an irreducible polynomial $f \in \mathbb{F}[x,y]$. Then for any polynomial $g \in \mathbb{F}[x,y]$ which is not divisible by $f$, the system of equations $f(x,y)=g(x,y)=0$ has only finitely many solutions.

Proof: We view $f$ and $g$ as the element of $u[y]$, where $u$ is the field of rational function of $x$ with coefficient in $\mathbb{F}$. By Gauss Lemma, it is easy to see that $f$ remains irreducible in $u[x]$ and also $f$ and $g$ are still relatively prime in $u[y]$. Thus there exists $\lambda, \mu \in u[y]$ such that
\[f \lambda + g \mu =1\]
Multiplying by the common denominator $a(y) \in \mathbb{F}[y]$ we will get
\[f(x,y) \lambda(x,y) + g(x,y) \mu(x,y) = a(y)\]
If $(\alpha, \beta)$ is the solution of the system of equations. Then $a(\beta)=0$, and there are only finitely many possibility of such $\beta$. Thus $\alpha$ is the root of equation $f(x, \beta)=0$, and there are also a finitely many value of them. The result follows.

Applying the lemma, let $X$ be an irreducible algebraic curve in an algebraic closed field. If there are two such equations which define $X$ say $f(x,y)=0$ and $g(x,y)=0$, since $f(x,y)=0$ has infinitely many solution in the algebraic closed field then the systems of equations $f(x,y)=g(x,y)=0$ also has infinitely many solutions. Hence the lemma says that $f(x,y)=c g(x,y)$. Thus the two equations are essentially the same.

The same is true for arbitrary curve $X$. Suppose that its equation is $h(x,y)=0$. Since $\mathbb{F}[x,y]$ is a Unique Factorization Domain, therefore
\[h=f_1^{k_1} f_2^{k_2} \cdots f_n^{k_n}\]
for irreducible polynomial $f_i \in \mathbb{F}[x,y]$. The points such that $h(x,y)=0$ are also such points so that $f_i(x,y)=0$ for some $i$. Let $X_i$ be a curve defined by $f_i (x,y)=0$, then we have \[X= \bigcup_{i=1}^n X_i \]
where $X_i$ is an irreducible curves.
This decomposition is called the irreducible components decomposition. Since the equation of each $X_i$ is irreducible and defined by the equation which only may differ by constant multiple, so any other equation of $X$ is also differ from $h$ by the constant multiple.

Just an exam problem

2010-01-03T11:12:00.000-08:00

Soal

Misalkan \[A={\underbrace{(999 \cdots 9)}_{\mbox{2008 buah}}}^{2009} \qquad \mbox{dan} \qquad B={\underbrace{(999 \cdots 9)}_{\mbox{2005 buah}}}^{2009}\]

Tunjukan bahwa digit dari

B dapat diperoleh dari A dengan cara menghapus beberapa buah digit

nya.

Solusi:

Untuk $0\leq m \leq 2009$ misalkan

\[A_m=\sum_{k=0}^{m} \binom{2009}{k} 10^{2008k} (-1)^{k+1} \qquad B_m= \sum_{k=0}^{m} \binom{2009}{k} 10^{2005k} (-1)^{k+1}\]

Jadi $A_{2009}=A$ dan $B_{2009}=B$.

Pertama-tama ditunjukan bahwa $2005$ buah digit terakhir dari $A$ dan $B$ sama. Karena $2005<2008$ maka $A \pmod {10^{2005}} = -1$ dan $B \pmod {10^{2005}} = -1$. Jadi $2005$ buah digit terakhir $A$ dan $B$ sama.

Berikutnya akan ditunjukan bahwa aturan pencoretan dari digit-digit $A$ untuk memperoleh digit-digit $B$ adalah dengan sebagai berikut:

Mulai dari digit paling kanan, dimana telah dibuktikan $2005$ buah digit paling kanan $A$ sama dengan $B$. Kemudian hapus $3$ digit seterusnya (digit ke $2006$ sampai digit ke $2008$ dari kanan)

kemudian $2005$ digit berikutnya dari $A$ akan sama dengan digit ke $2006$ sampai $2(2005)$ digit $B$ dari kanan, dan seterusnya.

\[A=\underbrace{c_1 c_2 c_3}_{\mbox{dicoret}} d_1 d_2 \cdots d_{2005}\underbrace{e_1 e_2 e_3}_{\mbox{dicoret}}\cdots\cdots\underbrace{f_1 f_2 f_3}_{\mbox{dicoret}} g_1 g_2 \cdots g_{2005} \]

\[B= b_1 b_2 \cdots b_{2005} \cdots \cdots d_1 d_2 \cdots d_{2005} \cdots \cdots g_1 g_2 \cdots g_{2005}\]

Untuk membuktikan hal ini, pertama-tama kita buktikan beberapa lemma berikut:

Lemma 1

Untuk $0\leq m \leq 2009$ berlaku

\[|A_m|<10^{2008m+1005} \qquad \text{dan} \qquad |B_m|<10^{2005m+1005}\]

bukti:

Berdasarkan sifat koefisien binomial $\binom{2009}{k} < \binom{2009}{1004} = \frac{(2009)(2008)\cdots (1006)}{(1004)(1003)\cdots (1)}<10^{1004}$. Dengan ketaksamaan segitiga

\[\begin{align*}\left|\sum_{k=0}^{m} \binom{2009}{k} (-1)^{k+1} 10^{2008k}\right| &\leq \sum_{k=0}^m \left|\binom{2009}{k} 10^{2008k}\right|\\ &<\binom{2009}{1004} \sum_{k=0}^{m} 10^{2008k}\\ &= \binom{2009}{1004} \left(\frac{10^{2008m+2008}}{10^{2008}-1}\right)\\ &< 10^{1004} \left(\frac{10^{2008m+2008}-1}{10^{2008}-1}\right) \\ &< 10^{1004} \left(\frac{10^{2008m+2008}}{ 10^{2007}}\right)\\ &< 10^{2008m+1005}\end{align*}\]

Ketaksamaan yang kedua dapat dibuktikan secara similar.

Lemma 2

Jika $m$ ganjil maka $A_m >0$ dan $B_m>0$, sebaliknya jika $m$ genap maka $A_m<0$ dan $B_m<0$.

Bukti:

Berdasarkan Lemma 1,
\[-10^{2008m}< A_{m-1} <10^{2008m}.\]

Untuk $m$ ganjil berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m+1} 10^{2008m}$. Sehingga diperoleh

\[0<-10^{2008m}+\binom{2009}{m} (-1)^{m+1} 10^{2008m}< A_m \Longrightarrow A_m>0.\]

Untuk $m$ genap berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m} 10^{2008m}$, kalikan ketaksamaan ini dengan $-1$ diperoleh \\ $\binom{2009}{n} (-1)^{n+1} 10^{2008n}<-10^{2008n}$. Sehingga diperoleh

\[A_m < \binom{2009}{m} (-1)^{m+1} 10^{2008m}+10^{2008m} < 0 \Longrightarrow A_m<0.\]

Pembuktian untuk $B_m$ dapat dilakukan dengan similar.

Sekarang akan dibuktikan pernyataan yang diklaim diawal. Misalkan $n$ adalah bilangan bulat yang terletak pada interval $(0,2009)$.

perhatikan bahwa hasil dari $A \mod {10^{2008n+2005}}$ menyatakan $2008n+2005$ digit terakhir dari $A$ (dengan menambahkan beberapa buah 0 dikiri apabila diperlukan). Karena $10^p \mod 10^q=0$ untuk $p \geq q$ maka

\[\begin{align*}A \mod 10^{2008n+2005} &=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n+2005}\\ &=A_n +a10^{2008n+2005}\end{align*}\]

Berdasarkan Lemma 1 , $|A_n|<10^{2008n+1005}<10^{2008n+2005}$, jadi hasil modulo diatas tidak lebih dari $10^{2008n+2005}$ sehingga apabila $A_n$ positif maka nilai $A_n$ samadengan $2008n+2005$ digit terakhir dari $A$, dan apabila $A_n$ negatif maka $2008n+2005$ digit terakhir dari $A$ adalah $10^{2008n+2005}+A_n$. Dengan kata lain, menggunakan Lemma 2 diperoleh

\[a=\begin{cases}1\quad & \mbox{$n$ genap}\\ 0 \quad & \mbox{$n$ ganjil}\end{cases}\]

Kemudian $2008n$ digit terakhir dari $A$ adalah

\[\begin{align*}A \mod {10^{2008n}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\\ &=A_{n-1}+b10^{2008n}\end{align*}\]

Berdasarkan Lemma 1 , $|A_{n-1}|<10^{2008(n-1)+1005}<10^{2008n}$, jadi hasil modulo diatas tidak lebih dari $10^{2008n}$ sehingga apabila $A_{n-1}$ positif maka nilai $A_{n-1}$ samadengan $2008n$ digit terakhir dari $A$, dan apabila $A_{n-1}$ negatif maka $2008n$ digit terakhir dari $A$ adalah $10^{2008n}+A_{n-1}$. Dengan kata lain, menggunakan Lemma 2 diperoleh

\[b=\begin{cases}1 \quad & \mbox{$n-1$ genap}\\ 0 \quad & \mbox{$n-1$ ganjil}\end{cases}\]

Hal ini berarti $a \neq b$, atau $|a-b|=1$.

Dengan penalaran yang sama

\[\begin{align*}B \mod {10^{2005n}} &=\left[\sum_{k=0}^{2009} \binom{2009}{k}10^{2008k}(-1)^{k+1}\right]\mod 10^{2005n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2005k} (-1)^{k+1} \\ &=B_{n-1}+c10^{2005n}\end{align*}\]

dimana $c=b$.

\[\begin{align*}B\mod{10^{2005(n+1)}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2005(n+1)}\\ &\equiv\sum_{k=0}^{n} \binom{2009}{k} 10^{2005k} (-1)^{k+1}\\ &=B_{n}+d10^{2005(n+1)}\end{align*}\]

dimana $d=a$.

Akan dibuktikan

\[\begin{align}\left(\frac{A \mod {10^{2008n+2005}} - A \mod {10^{2008n}}}{10^{3n}}\right)+ B \mod {10^{2005n}} = \\ B \mod {10^{2005(n+1)}}\end{align}\]

yang berarti bagian digit $2008n+1$ sampai $2008n+2005$ dari $A$ samadengan bagian digit ke $2005n+1$ sampai $2005(n+1)$ dari $B$. Persamaan (1) setara dengan

\[\begin{aligned}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} =B_{n}+d10^{2005(n+1)}\end{aligned}\]

Dari persamaan-persamaan yang diperoleh sebelumnya diperoleh

\[\begin{align*}A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n} =\\ \binom{2009}{n}10^{2008n} (-1)^n + a10^{2008n+2005} -b10^{2008n} \end{align*}\]

Jadi

\[\begin{align*}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} = \\ B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} \end{align*}\]

Karena $c=b$ dan $a=d$ diperoleh

\[B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} =B_n + a10^{2005(n+1)} = B_n + d10^{2005(n+1)}\]

seperti yang diharapkan.

Burnside's Lemma and coloring graph (first insight)

2009-12-25T03:45:00.000-08:00

Months ago, while helping my junior working his skripsi, I learned about a theorem in algebraic combinatorics called Polya's Enumeration Theorem. Actually I already known this handy theorem before, but haven't give it much thought before.

Before explaining about Polya's Enumeration Theorem, it is cultural to explain first about Burnside Lemma, which is a theorem in a Group Theory..

As some of undergraduate student learn about permutation group. Denote $S_n$ as the permuation group of $n$ elements. It's particularly useful to think the $S_n$ as the set of all bijective functions $p:\{1,2,\cdots,n\} \rightarrow \{1,2,\cdots,n\}$.

Recall that any elements of $S_n$ can be represented by its cycle decomposition. For example in $S_8$, the function $p$ s.t $p(1)=1$, $p(2)=4$, $p(3)=2$, $p(4)=3 $, $p(5)=7$, $p(6)=5$, $p(7)=8$, $p(8)=6$ can be rewritten as $(1)(2 4 3)(5 7 8 6)$. In this case we say $f$ is decomposed into three cycles:

$(1)$ has length one

$(2 4 3)$ has length three

$(5 7 8 6)$ has length four.

Some books usually remove the cycle of length one, so then the permutation above simply written as

$(2 4 3)(5 7 8 6)$, with no danger of confusion.

Orbit = Equivalence Class

Given a subgroup $D \subset S_n$, we define the relation $\sim_D$ on the set $\{1,2,\cdots, n\}$ as follow

$x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$.

It is easy to see that the above relation is an equivalence relation and so partitioning the set $\{1,2,\cdots, n\}$ into some disjoint classes by the rule of subgroup $D$. We call these equivalence classes as the orbits of $D$ . When the notation comes into play , the orbit of $D$ which contains $x$ is usually denoted by $O_x$ and clearly since the identity function is always in the subgroup we have $O_x=\{p(x) | p \in D\}$.

Two elements $x$ and $y$ are contained in the same orbit of $D$ if and only if $x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$ if and only if by some rule of permutation in $D$, $x$ can be placed in the position that is previously occupied by $y$, and vice versa.

To count how many different orbit of $D$ are there we can use the following lemma, known as Burnside's Lemma

\[t=\frac{1}{|D|} \sum_{p \in D} F(p)\]

where $F(p)$ is the number of the fix points of permutation $p$.

Permuting The Graph

Suppose that the graph $G$ has $n$ vertices, each vertices are numbered by numbers from $1$ to $n$. Since for any $p \in S_n$, $p$ permutes $1,2, \cdots, n$ then $p$ also permutes the vertices of $G$ without changing its edging rule, that's the resulting graph is isomorphic to the permuted graph.

For example doing the permutation $(1 2 3)$ to a triangle graph (vertices are numbered 1,2, and 3 clockwise from the top ) is equivalent to rotating the triangle.

Coloring Graph

Suppose that we want to color a graph $n$ vertices $G$ , with the set of Color $V:=\{c_1,c_2, \cdots. c_m\}$. Each coloring can be uniquely represented by the function $c: \{1,2, \cdots, n\} \rightarrow V$, by mean that $c(k)=c_3$ means that the vertex with number $k$ is colored by $c_3$ color (one can specify $c_3$ as blue, red, white etc.). The function ruling the assignment of the colors into each vertex. The set of all functions $c: \{1,2, \cdots, n\} \rightarrow V$ is denoted by $C_{n,m}$.

Given a permutation $p \in S_n$, for any coloring function $c \in C_{n,m}$ consider the function $\bar{p}: C_{n,m} \rightarrow C_{n,m}$

\[\bar{p}(c) := c \circ p^{-1}\].

We can prove that $\bar{p}$ is a bijective from $C_{n,m}$ to itself.

What does the $\bar{p}$ actually mean?

As we already know that $p$ permutes the vertices of the graph. And after the graph has been colored, we know that permuting the vertices also permuting the color attached on each of it and hence resulting the other coloring, OR in other words resulting another element of $C_{n,m}$. For example $\bar{p}(c_1)=c_2$ means that the coloring $c_2$ is obtained by permuting the vertices of the graph which are already been colored by using coloring $c_1$, and the permutation used is permutation $p$.

The set $\bar{S_n}=\{\bar{p}: p \in S_n\}$ is a group. In fact, it consists the permutation of the color-function. That is we can view it as the permuation group $S_{|C_{n,m}|}$. It is easy to see that $|C(n,m)|=m^n$ and hence $|S_{|C_{n,m}|}|=(m^n)!$

Given a subgroup $H$, then we can define $\bar{H}=\{\bar{p}: p \in H\}$. It is not hard to prove that $\bar{H}$ is a subgroup of $\bar{S_n}$.

A question then arise:

What are the orbits of $\bar{H}$ in $S_{|C{m,n}|}$ ?

They should be the subsets of $C_{n,m}$. Observe that, two elements $c_1,c_2 \in C_{n,m}$ are in the same orbit of $\bar{H}$ if and only if there exists $\bar{p} \in \bar{H}$ such that $p(c_1)=c_2$.

That is any coloring contained in the same orbit of $\bar{H}$ is just the permutation of each other using permutation in $H$ (not necessarily $\bar{H}$).

For simplicity, let assume that $G=R_4$ is a rectangle and $V=\{red,blue,green\}$. In this case $R_4$ has four vertices denoted by the number $1,2,3$ and $4$, numbered clockwise starting from the top-left vertex (actually the rule of numbering isn't really a big deal, one can use different numbering for initial graph as long as he/she keep it consistent).

To make it shorter, we will refer a coloring as a string with four letters, where the $i$-th letter denote the initial of the color assigned to vertex $i$, that is the coloring $rbrg$is understood to br$c(1)=red$, $c(2)=blue$, $c(3)=red$ and $c(4)=green$.

Now, imagine an already colored rectangular graph as a rectangular toy. Then the toys obtained from the coloring $rbrg$, $grbr$, $rgrb$, and $brgr$ are the same toy, up to a rotation (several rotations $90^\circ$ clockwise by the center of rectangle). And the toys obtained from the coloring $rbrg$ and $brgr$ are also the same (obtained by flipping the toy).

Therefore to enumerate all different toys, we need to count the toy and its corresponded toys obtained by rotation or flip as one.

[for those who are not familiar with symmetric group]

In $R_4$, initially we have the numbered vertices in order 1-2-3-4. After rotating the graph 90 degree clockwise, the position previously occupied by 1 is now being occupied by 4, the 2's position is now being occupied by 1, the 3's position is now being occupied by 2, and the 4's position is now being occupied by 3. Therefore we have done the permutation $\rho(1)=4$, $\rho(2)=1$, $\rho(3)=2$, $\rho(4)=3$ or $(1 4 3 2)$. Similarly, the flip permutation is simply $(1 2)(3 4)$. And all possible combination of permutation of the $R_4$ obtained from flipping or rotating are contained in

\[\begin{align*}D_4 =\{& (1)(2)(3)(4), (1)(2 4)(3), (1 2)(3 4), (1 2 3 4), (1 3)(2)(4), \\ &(1 3)(2 4), (1 4 3 2), (1,4)(2,3)\}\end{align*}\]

that is our Dihedral Group.

[Don't Forget Our $\bar{H}$ ]

As, we already seen before, the orbits of $\bar{H}$ are the subsets of $C_{n,m}$. And two elements (colorings) $c_1,c_2 \in C_{n,m}$ are in the same orbit, if there exists $\overar{p} \in \bar{H}$ such that $\bar{p}(c_1)=c_2$.

Therefore, in the Toy Factory example, if we set $H=D_4$, we see that the Toys contained in the same orbit of $\bar{H}$ in $S_{|C_{n,m}|}$ are same. Thus the number of different orbits of $overbar{H}$ in $S_{|C_{n,m}|}$ is equal to the number of different Toys. The Burnside Lemma now becomes very handful.

In general, for any subgroup $H \subset S_n$, the number of different Orbits of $\bar{H}$ in $\bar{S_{n}}$ tells us the number of nonequivalent coloring of the $n$ vertices graph (up to subgroup $H$).

So then, how can we apply Burnside Lemma here? It should be

\[\frac{1}{|\bar{H}|} \sum_{ \bar{p} \in \bar{H} } F(\bar{p})\]

well, clearly $|\bar{H}|=|H|$, and also it doesn't really matter if we replace $\sum_{\bar{p} \in \bar{H}}$ with $\sum_{p \in H}$, since for each $p \in H$ we have $\bar{p} \in \bar{H}$ and vice-versa. Now it remains to find $F(\bar{p})$.

$F(\bar{p})$ counts how many elements of $C_{n,m}$ which is sent to itself by $\bar{p}$ (i.e the fixed-point of $\bar{p}$). That is how many $k$ such that $\bar{p}(f_k)=f_k$. Recall that $\bar{p}(f_k)= f_k \circ p^{-1}$, thus $\bar{p}(f_k)=f_k$ is equivalent to $f_k \circ p^{-1} = f_k$ and so $f_k = f_k \circ p$. If we set $p$ to be identity map $id_n$, then all $f_k \in C_{n,m}$ satisfy $f_k = f_k \circ p$, thus $F(\bar{id_n})= |C_{n,m}|=m^n$.

Consider the cycle composition of $p$, say

\[p=(a_{j_1} a_{j_1+1} \cdots a_{j_2 -1})(a_{j_2} \cdots a_{j_3 -1}) \cdots (a_{j_i} \cdots a_{j_{i+1}-1}) \cdots (a_{j_l} \cdots a_n)\]

that is $p$ is composed into $l$ cycles.

A routine calculation shows that $f_k = f_k \circ p$ implies

\[f_k(a_{j_1})=f_k(a_{j_1+1}) = \cdots = f_k(a_{j_2 -1}).\]

And similarly

\[f_k(a_{j_i })= f_k(a_{j_i + 1}) \cdots = f_k(a_{j_{i + 1}-1}).\]

An indication that the number of the cycles of $p$ is involved in the $F(\bar{p})$, so we denote it by $c(p)$, where in above $c(p)=l$. In fact, to determine $f_k$, we only need to know the value of $f_k(a_{j_i})$ for $i=1,2,\cdots,l$. So the number of such $f_k$ is equal to the number of function $f: \{a_{j_1}, \cdots, a_{j_l} \} \rightarrow \{c_1, c_2, \cdots, c_m\}$ which is easily computed to be $m^{l}$. Thus we have $F(\bar{p})= m^{c(p)}$. (it is consistent with our earlier observation when $p$ is identity map.)

And we get the formula for the number of nonequivalent colorings (up to symmetric group $H$) of graph $G$ with $n$ vertices is

\[\frac{1}{|H|} \sum_{p \in H} m^{c(p)}\]

where $m$ is the number of colors used and $c(p)$ is the number of cycles in the cycle decomposition of $p$.

The application of this theorem will be reviewed on the next post.

Generating the Oxolodon Space

2009-11-28T06:44:00.000-08:00

What is Oxolodon? It's just a strange term that I made it up myself (you can check by typing "oxolodon" into google, then the term oxolodon only belongs to this blog or any link directed here :p)

Well, I'm a little bit "stuck" after graduating from the bachelor degree of mathematics in the University Of Indonesia, since i still don't get a way to proceed to a master degree. Perhaps because most of the scholarships believe those A, A-, B+, B, C+, C, C-, D or E stuffs more than what actually we can do.

During this "empty state", I remember that once I was in the undergraduate there were so many materials that should be taught but they were not (due to the lack of time or the atmosphere of the class). Here are some of the materials I've gotten and what was missed, while I was taking my bachelor.

Calculus I : Almost all materials were discussed. But I need to teach myself about
Transcendence Function and Technique Of Integration.

Real Analysis I & II: Using Bartle's Book, The Elements Of Analysis, We couldn't reach
Section 6: Differentiation.

Complex Analysis : We know what is the analytic functions but we stopped in the Cauchy-
Riemann Equations section. I should study myself: singularity, Liouville
Theorem, Uniqueness Extension Theorem, Poles, Cauchy-Goursat
Theorem, Residue theorem, Schwarz lemma, Picard Theorem, Winding
Numbers.

Algebra : I love the Algebra I course. It almost covered all the materials except Galois Theory (Introductory), Sylow Theorems and the Finite Simple Group (we actually discussed
about an active research in the Characterization Of Finite Simple Group :
Sporadic Groups.) This course is the best i've followed so far!

They suggest me to become

self-active to enrich my understanding on every courses.

Because due to the lack of time or the class atmosphere, the instructor cannot cover all the materials required by the syllabus.
As for me., I found that it is easier to understand about a subject (particularly math) by trying to explain it to the others. Unfortunately, I rarely find someone who want to listen the "hard-stuff" about pure mathematics (except when they're really need it, for example before the exam).

This is the Idea behind Generating Oxolodon Space.
-It maybe me talking to myself-

one more thing: Our mathematics skill will be decayed by time, if we never use it frequently. I am no longer in the academic.

accepted mathematical problem

2009-11-27T06:25:00.000-08:00

I found some problems that i doubly call them a mathematics competition problems, one example is:

Problem 1:
"The autopsion result that propofol was found in the death body of the king of pop, Michael Jackson.

Dr Murray told the police that he gave the propofol in effort to help him sleep. Worried that jackson might become addicted to
the drug, Murray tried to wean Jackson from it and using another alternative drugs to make Jackson sleep.
But On the morning, Jackson had found to be death."
Formulate and solve the mathematics model of the above problem!

The problem was given as a take-home problem for a math competition. From my opinion, this is not a typical of the competition problem nor a research one (it's just a new story taken from CNN.)
It has no objection, no clear instruction, even worse: given that we know what to do, it does not provide us with a sufficient data to proceed (even though we can search it ourselves.)
Problem 1 might be transformed into a mathematics problem. But from the way it was stated, i think it is not a good mathematics problem, not even i want to call it one.

Without dishonor the numerical analysts and staticians, I prefer the problem with the exact answer. That is whenever the problem is
being attacked by some mathematicians, then they would purpose a same true answer (up to any dummy variables or the notations.)
If the numerical analysts and staticians are being included, then our type of problem must tackle the ambiguity of its purposes and it should possess a halt-condition (the condition that must be satisfied to flag the problem as SOLVED.)
[The Problem 1 above failed to win these criteria]

One might thinks that a yes-no (true-false) question would fit this criteria, but others type of problem like root-finding problem also fit the criteria well.

Thinking about this type of problems, lets make a deeper investigation about how they might look like.

How about this problem:
Problem 2 :\[ \text{"Find $x$!"}\]

First question might be arise here would be "What is the x?". Although "Find x!" is a question, but it shouldn't be called a math question, since it is not a proposition. That's right, we need a proposition (you can find $x$ by pointing out the variable ;p). The question itself must be related to a proposition.

Now how about:
Problem 3 :\[\text{"The production of the gasoline has arised up to 110.3$\%$. True or Not?"}\]

Here we have the question and the proposition. But what's wrong? well it might be a well-posed problem, but it can only be answered, given a sufficient and relevant data to proceed.
Another lesson here: The problem which doesn't give a complete data can lead to a dead-end.

Perhaps, some theorists might try to independently collect the data in order to solve the problem, or simply by making some assumptions before they proceed. But then the answers can be varied as these assumptions are being made.
As we already noted before, we want a same correct answer for each people who solve the problem. So we need to include the general assumption into the problem. The stated assumption simply becomes a signed proposition, that is the proposition which value is known.
The proposition which has an unknown value is included in the question. Notice that as long as we know its logic value (or simply assign it by using the assumption), the proposition itself can be viewed as a data. So we count them as one.

Are those all we need?
Oh no, what about the Definitions and Axioms? No worry, they are also can be viewed as propositions. So, let test our result:

Problem 4:\[\text{ Given integer $n \geq 3$. Find all positive integers $x,y$ and $z$ such that} \] \[x^n+y^n=z^n\]

The signed propositions here are :
1. $n$ is an integer greater than 3
2. $x,y$ and $z$ are positive integers.

The above propositions need another propositions (i.e definition of integers or axiom of numbers.)

And the question is "Find all $x,y,z$ such that the proposition $x^n+y^n=z^n$ is true".

The proposition and the question, that's all we need?
Back to 1920s, the structure about how (in general) the mathematics is posed was already stated by a famous German Mathematicians , David Hilbert. It's called the Hilbert program. The goal is to formalize the mathematics such that :

Completeness: a proof that all true mathematical statements can be proved in the formalism
Consistency: a proof that no contradiction can be obtained in the formalism of mathematics.
Conservation: a proof that any result about "real objects" obtained using reasoning about "ideal objects" (such as uncountable sets) can be proved without using ideal objects.
Decidability: there should be an algorithm for deciding the truth or falsity of any mathematical statement.

The question then arise, do all the well-posed math problems have a solution? in term of Hilbert Program : "Can we achieve the goal of Hilbert Program?"
Well, not all of them have.

The first Godel's Incompleteness Theorem merely state that
"There exists an arithmatical statement that is true but not provable."

Some mathematicians argue this "scary" statement might be exists in the unintended area of mathematics.

For example, in the number theory, since the area relies on the arithmatic statements. There could be some number-theorytic problem that is true but cannot be proved.

Does the Godel Sentence only exists on the alien area in mathematics?
Not really, The Whitehead Problem which states

Is every abelian group $G$ with $Ext(G,\mathbb{Z})=0$ a free abelian group?

Where $\mathbb{Z}$ is the group of integers and $Ext$ is the Ext Functor. This Whitehead problem was proved by shelah to be undecideable within the Zermelo–Fraenkel set theory. That is it cannot be proved to be true or wrong given the already known axiom in Zermelo–Fraenkel set theory.

soal simulasi

2009-07-19T10:20:00.001-07:00

Problem

Misalkan $a$ dan $b$ adalah bilangan positif yang memenuhi $a+b=1$, Buktikan

\[ \left(\frac{a}{a+x} \right)^{a+x} \left(\frac{b}{b-x}\right)^{b-x} < e^{-2x^2} \]

untuk setiap $x\in (0,b)$

Donald E. Knuth

Solution:

Tetapkan $a$ and $b$ dengan $a+b=1$. Misalkan

\[f(x)=e^{2x^2} \left(\frac{a}{a+x} \right)^{a+x} \left(\frac{b}{b-x}\right)^{b-x} \]

yang didefinisikan untuk $x\in[0,b)$. Akan ditunjukkan bahwa $f(x) < 1$ untuk $x > 0$, misalkan

\[g(x):= \log f(x) = 2x^2+ (a+x) \log \left(\frac{a}{a+x} \right) + (b-x) \log \left(\frac{b}{b-x} \right). \]

Maka

\[g^{\prime}(x) = \frac{f^{\prime}(x)}{f(x)} = 4x+\log \frac{a(b-x)}{a(b+x)}\]

Perhatikan bahwa $g^{\prime}(0)=0$ dan

\[g^{\prime \prime}(x)=4-\left(\frac{1}{a+x} + \frac{1}{b-x} \right) = 4 - \frac{1}{(a+x)(b-x)} .\]

Berdasarkan ketaksamaan arithmatik-geometrik mean , $(a+x)(b-x)\leq1/4$, jadi $g^{\prime \prime}(x)\leq 0$. dengan tanda sama dengan ketika $a+x=b-x$. Jadi $g^{\prime} (x)\leq g^{\prime}(0) =0$ untuk $x \geq 0$ yang menyebabkam $g(x) \leq g(0) =0$ untuk $x \geq 0$. Dengan demikian $f(x) < 1$ untuk $x > 0$.

Pelatihan Tim ISOM

2009-07-10T08:13:00.000-07:00

Hari ini aku membahas soal-soal ISOM (International Scientific Olympiad in Mathematic) bersama-sama Tim ISOM Indonesia 2009.

Ini dia soal-soal nya:

1. Misalkan $f(x)$ adalah fungsi yang kontinu piecewise dan terdifferentiable di $[0,a]$. Jika $f(0)=0$ buktikan bahwa \[\int_0^a |f^{\prime}(t)f(t)| dt \leq \frac{a}{2} \int_0^a f^{\prime}(t)^2\,dt\]

2. Jika $G$ suatu grup hingga, dan $H$ subgrup dari $G$. Buktikan $n_p(H) \leq n_p(G)$ [ Disini $n_p(S)$ menyatakan banyak nya $p$-sylow subgroup dari group $S$]

Solusi:

Untuk $a\geq 0$, misalkan \[h(a)= \frac{a}{2} \int_0^a f^{\prime}(t)^2 dt- \int_0^a |f^{\prime}(t) f(t) |\,dt\]

1 .akan ditunjukkan bahwa $h(a)\geq 0$ untuk setiap $a \geq 0$. Perhatikan bahwa $h(0)=0$. Turunan dari $h$ terhadap $a$ adalah

      \[h^{\prime}(a)=\left(\frac{1}{2}\right)\int_0^a f^{\prime}(t)^2\,dt+\left(\frac{a}{2}\right) f^{\prime}(a)^2-|f^{\prime}(a)f(a)|\]
      perhatikan bahwa $h^{\prime}(0)=0$ dan untuk $a>0$, $h^{\prime}(a)$ dapat ditulis

      \[h^{\prime}(a)=\frac{1}{2} \left[\int_0^a f^{\prime}(t)^2 \, dt - \frac{f(a)^2}{a} + \left(\frac{|f(a)|}{\sqrt{a}} - \sqrt{a}|f(a)|\right)^2\right]\]
      Misalkan

      \[g(a)= \begin{cases} \int_0^a f^{\prime}(t)^2 \, dt -\frac{f(a)^2}{a} & a>0 \\ 0 & a=0 \end{cases}\]

      Perhatikan bahwa $\lim_{a \rightarrow 0^+} g(a)= \lim_{a \rightarrow 0^+ } \frac{f(a)^2}{a} = \lim_{a \rightarrow 0^+} 2f(a)f^{\prime}(a)=0$ (karena $f(0)=0$). Jadi $g(a)$ kontinu. Lalu,

      \[g^{\prime}(a) = f^{\prime}(a)^2 - \frac{2f(a)f^{\prime}(a)}{a}+\frac{f(a)^2}{a^2} = \frac{1}{a^2} \left(f^{\prime}(a)-\frac{f(a)}{a}\right)^2 \geq 0\]

      dan $g^{\prime}(0)=0$. Jadi $g(a)$ adalah fungsi naik sehingga $a\geq 0$ menyebabkan $g(a) \geq g(0)=0$.

      Sehingga kita peroleh

      \[h^{\prime}(a)=g(a)+\left(\frac{|f(a)|}{\sqrt{a}} - \sqrt{a}|f(a)|\right)^2 \geq 0\]

      Jadi $h(a)$ juga fungsi naik dan untuk $a\geq 0$ diperoleh $h(a)\geq h(0)=0$. Yaitu

      \[h(a)= \frac{a}{2} \int_0^a f^{\prime}(t)^2 \, dt - \int_0^a |f^{\prime}(t)f(t)| \, dt \geq 0\]

2. Lemma: Jika $H$ adalah subgrup dari $G$ dengan order $p^{\alpha}$ dengan $p$ bilangan prima, maka $H$ berada dalam suatu $p$-sylow subgrup dari $G$.

Misalkan $|G|=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ dengan $\alpha_i > 0$, maka berdasarkan teorema Langrange $|H|=p_1^{\beta_1}\cdots p_k^{\beta_k}$, $0\leq \beta_i \leq \alpha_i$.

Akan dibuktikan bahwa untuk setiap $p_i$ faktor prima dari $|H|$, tidak ada dua $p_i$-sylow subgrup dari $H$ yang termuat dalam tepat satu $p_i$-sylow subgrup dari $G$.

Misalkan $P$ adalah $p$-sylow subgrup dari $G$, dengan order $p^{\alpha}$, untuk suatu bilangan prima $p$. Misalkan ada $R$ dan $Q$ berbeda yang merupakan $p$-sylow subgrup dari $H$ sedemikian sehingga $R \subset P$ dan $Q \subset P$. Sehingga $R \subset P \cap H$ dan $Q \subset P \cap H$, Jadi---

\[|R| \text{ membagi }|P\cap H| \qquad |Q| \text{ membagi } |P \cap H|\]

Jelas bahwa $P \cap H$ juga merupakan subgrup dari $H$ dan $P$, karena $|P|=p^{\alpha}$ maka berdasarkan teorema Langrange $|P \cap H|=p^{t} $ untuk suatu $t\leq \alpha$.

Tapi karena $R$ dan $Q$ adalah $p$-sylow subgrup dari $H$, maka mereka merupakan subgrup dari $H$ dengan order $p^\beta$, dengan $\beta$ terbesar .

\[\begin{align*}p^{\beta}=|R| \text{ membagi } |P\cap H|=p^{t} \qquad p^{\beta}=|Q| \text{ membagi } |P \cap H|=p^{t}\end{align*}\]

karena $\beta$ pangkat terbesar maka $p^t \leq p^{\beta}$ jadi (1) mengahasilkan $p^t=p^{\beta}$, atau $|P \cap H|$ mempunyai order yang sama dengan $Q$ dan $R$, namun karena $Q$ dan $R$ keduanya merupakan subset dari $P \cap H$ maka $Q=P \cap H = R$. Kontradiksi.

Jadi untuk setiap faktor prima $p$ dari $|G|$, tidak ada $p$-sylow subgrup dari $G$ yang memuat dua $p$-sylow subgrup dari $H$. Sehingga $n_p(H) \leq n_p(G)$.

Bandung, Isola resort UPI