Lanjutan Exact Kanan dari Tensor Product.

Lanjutan Exact Kanan dari Tensor Product.

21:00:00  

Akhirnya saya sudah bisa menggambar commutative diagram, mari kita lanjutkan bukti bahwa fungtor $(\cdot) \otimes N$ adalah exact kanan.

Untuk kemudahan penulisan, karena $Hom(N,P)$ juga merupakan $R$-Module, kita definisikan $\mathfrak{F}_X(M) = Hom(M,Hom(N,P))$, dimana $\mathfrak{F}_X(M')$ dan $\mathfrak{F}_X(M'')$ didefinisikan secara similar. 

Perhatikan diagram
\[\xymatrix{ M \ar[d] \ar[r]^f & M^{\prime} \ar[d] \ar[r]^g & M^{\prime \prime} \ar[d] \ar[r] & 0 \ar[d] \\ \mathfrak{F}_X(M) \ar[d]^{\psi} & \mathfrak{F}_X(M') \ar[l]_{\varphi_f(\lambda) = \lambda \circ f} \ar[d]^{\psi'} & \mathfrak{F}_X(M'') \ar[l]_{\varphi_g(\mu) = \mu \circ g} \ar[d]^{\psi''} &0 \ar[d]\ar[l] \\ Hom(M \otimes N, P)\ar[d] &Hom(M^{\prime} \otimes N, P)\ar[d] \ar[l]_{v} & Hom(M^{\prime \prime} \otimes N, P) \ar[l]_{w} \ar[d] &0 \ar[l] \ar[d] \\ M \otimes N \ar[r] & M^{\prime} \otimes N \ar[r] & M^{\prime \prime} \otimes N \ar[r] &0} \]

Kita akan "menginduksi" ke-exact-an dari baris pertama pada diagram diatas, ke baris kedua, ketiga dan keempat.

Catatan bahwa module $P$ pada diagram diatas adalah "sebarang module",  ini berarti baris ketiga/kedua dibaca  "exact untuk sebarang module $P$".

Perhatikan bahwa pemetaan $\psi, \psi^{\prime}$ dan $\psi^{\prime \prime}$ diperoleh dari fungtoriality di post sebelumnya, dan seperti yang telah dibuktikan semuanya merupakan isomorphism, kita definisikan pemetaan $w$ dan $v$ sebagai: 

\[w = \psi^{\prime} \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1} \qquad v = \psi \circ \varphi_f \circ (\psi^{\prime})^{-1}\]

yakni kita membuat ketiga kotak ditengah membentuk diagram komutatif, atau dengan kata lain disini $\psi, \psi^{\prime}$ dan $\psi^{\prime \prime}$ adalah komponen Natural Transformation dari fungtor $\mathfrak{F}$ ke fungtor $((\cdot) \otimes N, P)$.

Hal ini dapat digunakan untuk membuktikan bahwa baris ketiga dari diagram diatas membentuk barisan exact. 

Baris 1 exact $\Longrightarrow$ Baris 2 exact

Kita pakai hasil  berikut :

Untuk sebarang $X \in Mod_R$, contravariant functor $\mathfrak{F}_X : Mod_R \rightarrow Mod_R$ yang diberikan $M \rightarrow Hom(M, X)$, adalah exact kanan, yakni
\[\xymatrix{ M \ar[r]^f & M^{\prime} \ar[r]^g & M^{\prime \prime} \ar[r] & 0 }\]
adalah barisan exact maka barisan \[\xymatrix{0 \ar[r] & Hom(M'',X) \ar[r]^{\varphi_g(\mu)=\mu \circ g} & Hom(M',X) \ar[r]^{\varphi_f(\lambda)=\lambda \circ f} & Hom(M,X)} \]
juga exact. 

Bukti: 

Pertama-tama kita buktikan $ker(\varphi_g) = \{0\}$, ini mudah karena jika $\varphi_g(\mu)=0$ maka diperoleh $(\mu \circ g)(m) = 0$ untuk setiap $m \in M'$, tapi karena $g$ surjective maka ini berarti untuk setiap $m_2 \in M^{\prime \prime}$ berlaku $\mu(m_2) = 0$, sehingga $\mu=0$, terbukti  $ker(\varphi_g) = \{0\}$. 

Selanjutnya akan dibuktikan $ker(\varphi_f) = img(\varphi_g)$. Untuk $\varphi_g(\lambda) \in img(\varphi_g)$ dimana $\lambda \in Hom(M'', X)$, diperoleh \[\varphi_f(\varphi_g(\lambda)) = (\varphi_g(\lambda)) \circ f = \lambda \circ  g \circ f\]

tapi karena $img(f) = ker(g)$, maka $\lambda \circ g \circ f = 0$, sehingga diperoleh $\varphi_g(\lambda) \in ker(\varphi_f)$, jadi $img(\varphi_g) \subseteq ker(\varphi_f)$. 

Misalkan $\lambda \in Hom(M',X)$ sedemikian sehingga $\varphi_f(\lambda)=0$,  diperoleh $(\lambda \circ f)(m) = 0$ untuk setiap $m \in M$.  Kita harus membuktikan $\lambda \in img(\varphi_g)$, yakni terdapat $\mu \in Hom(M^{\prime \prime}, X)$ sedemikian sehingga $\mu \circ g = \lambda$.  Kita definisikan saja $\mu$ sebagai:

\[\mu(x) = \lambda(y) \qquad \text{Jika $x=g(y)$ }\]

perhatikan bahwa eksistensi dari $y$ diberikan oleh sifat surjective dari $g$, agar $\mu$ well-defined misalkan $g(y_1)=x_1$ dan  $g(y_2)=x_2$ dimana $x_1=x_2$ maka 

\[0=x_1-x_2 = g(y_1) - g(y_2) = g(y_1-y_2)\]

jadi $y_1-y_2 \in ker(g) = img(f)$, sehingga diperoleh $y_1-y_2 = f(m)$ untuk suatu $m \in M$, ini berarti \[\lambda(y_1-y_2) = \lambda (f(m)) = (\lambda\circ f)(m) = 0 \Longrightarrow \lambda(y_1) = \lambda(y_2) \Longrightarrow \mu(x_1)=\mu(x_2)\]

Jadi $\mu$ well-defined dan merupakan linear map karena komposisi dari dua linear map, terlebih lagi untuk setiap $y \in M^{\prime}$ diperoleh  $(\mu \circ g)(y) = \mu(g(y)) = \lambda(y)$.  $\blacksquare$.

Dengan menggunakan $X=Hom(N,P)$ pada teorema diatas, maka kita peroleh baris 2 diagram diatas exact apapun $R$-module $P$ nya.

Baris 2 exact  $\Longrightarrow$ Baris 3 exact untuk setiap $P$

Perhatikan bahwa $w = \psi^{\prime} \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1}$, yakni komposisi dari pemetaan injective, maka $w$ juga injective.  Lalu karena $v \circ w = \psi \circ \varphi_f \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1}$ dan $img(\varphi_g) = ker(\varphi_f)$ maka untuk setiap $x \in Hom(M^{\prime \prime} \otimes N,P)$ berlaku \[(v \circ w)(x) = \psi \circ \varphi_f \circ (\varphi_g ( (\psi^{\prime \prime} )^{-1} (x)) ) = \psi(0) = 0 , \]
jadi $img(w) \subseteq ker(v)$.

Sebaliknya untuk setiap $x \in Hom(M^{\prime} \otimes N,P)$ dengan $v(x)=0$ , maka
\[(\varphi_f \circ (\psi^{\prime})^{-1} ) (x) = (\psi^{-1} \circ v )(x) = \psi^{-1}(0) = 0\]

sehingga diperoleh $(\psi^{\prime})^{-1} (x) \in ker (\varphi_f) = img(\varphi_g)$.

Ini berarti
\[(\psi^{\prime})^{-1} (x) = \varphi_g (\mu) \text{ untuk suatu } \mu \in \mathfrak{F}_X(M'') \Longrightarrow x = \psi^{\prime} \circ \varphi_g (\mu) \] Misalkan $ y = \psi^{\prime \prime}(\mu)$, dengan sifat isomorphism diperoleh $\mu =( \psi^{\prime \prime})^{-1}(y)$, sehingga \[x= \psi^{\prime} \circ \varphi_g \circ( \psi^{\prime \prime})^{-1}(y) = w(y) \] sehingga $x \in img(w)$.

Baris 3 exact untuk setiap $P$ $\Longrightarrow$ Baris 4 exact

Kita akan buktikan

Misalkan $A$, $B$, dan $C$ adalah $R$-module maka jika untuk setiap $X$ barisan
 \[\xymatrix{& Hom(C',X) \ar[r]^{\varphi_g(\mu)=\mu \circ g} & Hom(B,X) \ar[r]^{\varphi_f(\lambda)=\lambda \circ f} & Hom(A,X)} \]
 exact maka diperoleh
\[\xymatrix{ A \ar[r]^f & B \ar[r]^g & C}\]
juga exact

Bukti:

Kita gunakan cara yang sama ketika membuktikan Lemma Yoneda. Karena hipotesa menyatakan berlaku untuk semua $X$, maka kita boleh melihat ketika $X=C$. Ini berarti 

\[g= id_{C} \circ g = \varphi_g( id_{C} ) \in img(\varphi_g) = ker(\varphi_f)\]

Sehingga $\varphi_f(g)=0$, jadi $g \circ f = 0 $, diperoleh $img(f) \subseteq ker(g)$. 

Kita kemudian pilih $X$ sedemikian sehingga terdapat linear map $\lambda : B \rightarrow X$ mempunyai kernel tepat sama dengan $img(f)$. Hal ini diberikan oleh pemetaan canonical $\lambda: B \rightarrow B/ img(f)$,  $b \rightarrow img(f)+b$.   

Dengan pemetaan canonic diatas $(\lambda \circ f)(a) = img(f)+f(a) = img(f)=0$, jadi pemetaan canonic merupakan anggota $ker(\varphi_f)=img(\varphi_g)$, sehingga diperoleh $\lambda = \mu \circ g$ untuk suatu $\mu \in Hom(C, B/img(f))$. Sedangkan untuk setiap $m_1 \in ker(g)$, kita peroleh $0=(\mu \circ g)(m_1) = \lambda(m_1)$, jadi $m_1 \in ker(\lambda)=img(f)$, sehingga terbukti $ker(g) \subseteq img(f)$. $\blacksquare$

q.e.d

Apabila kita gunakan teorema diatas dengan $(A,B,C)=(M\otimes N, M^{\prime} \otimes N, M^{\prime \prime} {\otimes} N)$ dan ketika $(A,B,C) = ( M^{\prime} \otimes N, M^{\prime \prime} \otimes N , 0)$ maka diperoleh

\[\xymatrix{M \otimes N \ar[r] & M^{\prime} \otimes N \ar[r] & M^{\prime \prime} \otimes N \ar[r] &0}\]

barisan  exact.

Continue Reading

Tensor Product sebagai Fungtoriality

Tensor Product sebagai Fungtoriality

19:53:00  

Semalam, ketika mendiskusikan tentang contoh Sheafification. Pak Fajar bilang bahwa itu diberikan dari left-adjoint functor $L: PSh(\mathcal{C}) \rightarrow Sh(\mathcal{C})$ dari inklusi $Sh(\mathcal{C}) \hookrightarrow Psh(\mathcal{C})$.

Karena bahasa Category saya belum lancar, saya mencoba mencari kasus-kasus less abstract yang saya kenal dari -so called- adjoint functor. Anyway pada definisi yang diberikan  (bukan full definition) terdapat isomorphism

\[ Hom_\mathcal{D} (L(C),D) \simeq Hom_\mathcal{D} (C,R(D)) \]

untuk $C \in \mathcal{C}$ dan $D \in \mathcal{D}$.

Dulu sekali, saya pernah mengerjakan sebuah latihan tentang right exactness dari Tensor Product terhadap suatu $R$-module $N$. (Sepertinya ada di Attiyah), yaitu

Untuk $R$-module $A$, $B$, dan $C$, jika
\[A \rightarrow B \rightarrow C \rightarrow 0 \]
adalah barisan exact maka
\[A \otimes N \rightarrow B \otimes N \rightarrow C \otimes N \rightarrow 0\]
juga barisan exact. 

Pada buktinya, terdapat (hint?) untuk membuktikan hal ini terlebih dahulu:

Untuk $R$-module $M$, $N$, dan $P$ maka berlaku
\[Hom_R(M \otimes N, P) \simeq Hom_R(M , Hom_R(N, P)) \]

In other words, dalam bahasa Category,  kita punya functor $\mathcal{F} : Mod_R \rightarrow Mod_R$ diberikan dengan $(\cdot) \otimes N$ dan functor $\mathcal{G} : Mod_R \rightarrow Mod_R$ diberikan dengan $Hom(N, \cdot)$ dan mereka memenuhi bentuk yang saya berikan diatas.

Bukti:

Definisikan $\Psi : Hom_R (M \otimes N, P) \rightarrow Hom_R (M , Hom(N, P)) $
dengan aturan:

Untuk $f: M \otimes N  \rightarrow P$, hasil pemetaan dari $\Psi(f)$ adalah fungsi $g$  yang memetakan $x \in M$ ke fungsi $g(x) : N \rightarrow P$, dimana $g(x)$ memetakan $y \in N$ ke $[g(x)](y)=f(x \otimes y)$.

Singkatnya kita tulis

\[\Psi(f)(x)(y) = f(x \otimes y) \qquad x\in M \, , \, y\in N\]

   Pembuktian bahwa $[g(x)](y) = f(x \otimes y)$ adalah benar anggota $Hom_R(N, P)$ , cukup rutin dengan menggunakan sifat billinear dari tensor product.   Pembuktian bahwa $g(x)$ adalah benar anggota $Hom_R (M , Hom(N, P))$ juga cukup jelas dengan sifat billinear dan sifat linear dari $f$.
Pembuktian bahwa $\Psi$ injective (monomorphism) juga tidak begitu sulit.

Yang menarik adalah pembuktian bahwa $\Psi$ surjective, saya akan coba jabarkan.

Ambil sebarang $g \in Hom_R(M, Hom_R(N,P))$, kita akan membuktikan terdapat $f \in Hom_R(M \otimes N, P)$ sedemikian sehingga $\Psi(f) = g$. Perhatikan bahwa $g$ memetakan anggota $x\in M$ ke anggota $Hom_R(N, P)$.

Kita akan menggunakan Universal Property dari Tensor Product, yaitu dimulai dari mendefinisikan billinear map $f^{\prime} : M \times N \rightarrow P$ sebagai berikut:
\[f^{\prime}(x,y) = g(x)(y)\]

Karena $g$ linear maps maka $f^{\prime}(ax_1+bx_2 ,y ) = g(ax_1 +bx_2))(y) = g(ax_1)(y)+g(bx_2)(y) = [ag(x_1)](y)+[bg(x_2)](y)$, secara similar ini juga berlaku untuk variabel $y$. Sehingga diperoleh $f^{\prime}$ adalah fungsi billinear.

Jadi dengan Universal Property dari Tensor Product (maaf saya belum bisa gambar commutative diagram di blogger)  terdapat unique $f \in Hom_R(M \otimes N, P)$ sedemikian sehingga

\[\Psi(f)(x)(y) = f(x \otimes y) = f^{\prime}(x,y) = g(x)(y)\]

terbukti.

Saya ingin lanjut ke right-exactness agar relevant ke adjoint functor, dan saya bisa lebih mengerti secara lebih natural tentang adjoint functor,  tapi saat ini belum tahu cara mengetik commutative diagram dengan nyaman di Mathjax :[

Continue Reading

Soal Batu

Soal Batu

03:47:00  

Beberapa bulan yang lalu, di olimpiade.org, sayakalah (Erlang) mem-posting soal berikut:

Diberikan $2n+1$ buah batu dengan berat bilangan real positif. Untuk setiap $1 \leq i \leq 2n+1$, apabila batu dengan berat $a_i$ kita pisahkan, maka $2n$ buah batu sisanya dapat dikelompokan menjadi dua grup dengan $n$ anggota, dimana berat total kedua grup batu tersebut sama. Buktikan bahwa berat batu sama semua. 

Bagi saya soal ini sangat susah, karena beratnya yang harus bilangan real positif.  Saya menyelesaikan soal ini dengan menggunakan Hamel Basis, dan argumen yang similar juga berlaku ketika "berat" batu boleh bilangan  negatif. (solusi saya di olimpiade.org dapat dilihat dengan mengklik soal diatas, saya=Adri :p )

Beberapa hari yang lalu, saya melihat soal serupa yang relatif lebih mudah dimana berat batu adalah bilangan bulat positif, yang merupakan soal Kompetisi Putnam ke-34 (saya kurang tahu Putnam tahun berapa itu, google saja).  (Update: Soal yang sama ternyata juga ada di buku The USSR OLYMPIAD PROBLEM BOOK oleh Shklarsjy, Chentzov, Yaglom). Soal versi bilangan real ini muncul (tanpa solusi) di buku Problems From The Book, dan ada di bab yang membahas tentang Dirichlet Approximation (Kronecker's Theorem  dan kawan2). Mungkin perlu dicoba mencari solusi yang menggunakan Dirichlet Approximation.

Argumen yang saya pakai di olimpiade.org ternyata bisa  mengeneralisasi soal ini dimana "berat" batu  merupakan Matriks berukuran $n \times n$ dengan komponen matriks berupa bilangan-bilangan kompleks, sebenarnya argumen saya juga berlaku untuk sebarang ruang vektor atas lapangan kompleks.

Untuk kemudahan, seperti pada post di olimpiade.org, kita sebut syarat :

"Jika diambil sebarang satu anggota, sisanya dapat dipartisi menjadi dua grup sama banyak dengan total kuantitas sama besar"

sebagai syarat bagus.

Kita telah membuktikan bahwa jika $2n+1$ buah bilangan real memenuhi syarat bagus maka $2n+1$ buah bilangan tersebut akan sama.

Dengan argument yang sama, kita akan buktikan untuk kasus bilangan kompleks.

Misalkan $z_j=x_j + i y_j$ untuk $j=1,2, \cdots, 2n+1$ adalah bilangan kompleks yang memenuhi syarat bagus. Maka berlaku $z_1=z_2= \cdots = z_{2n+1}$.

Solusi: Perhatikan bahwa apabila $z_k$ diambil, maka dengan syarat bagus kita peroleh terdapat dua himpunan disjoint $A_k, B_k \subseteq \{z_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ dan memenuhi

\[\sum_{j \in A_k} x_j + i \left( \sum_{j \in A_k} y_j \right) = \sum_{j \in B_k} x_j + i \left( \sum_{j \in B_k} y_j \right) \]

Ini berarti $\sum_{j \in A_k} x_j = \sum_{j \in B_k} x_j$ dan $\sum_{j \in A_k} y_j = \sum_{j \in B_k} y_j$, dengan kata lain bilangan real $x_1, x_2, \cdots, x_{2n+1}$ dan $y_1, y_2, \cdots, y_{2n+1}$ memenuhi syarat bagus, dan karena kita sudah membuktikan soal untuk bilangan real, maka diperoleh $x_1 = x_2 = \cdots = x_{2n+1}$ dan $y_1 = y_2 = \cdots =y_{2n+1}$. Dari sini kita peroleh $z_1 = z_2= \cdots = z_{2n+1}$ dan kita selesai. $\blacksquare$

Sekarang jelas bahwa argumen yang similar dapat digunakan apabila berat batu adalah anggota dari ruang vektor berdimensi hingga  $V$ atas lapangan $\mathbb{C}$.

Diberikan $\mathbf{w}_1 , \mathbf{w}_2, \cdots, \mathbf{w}_{2n+1}$ adalah vektor-vektor di $V$ yang memenuhi syarat bagus.  Misalkan $\mathbf{b}_1, \mathbf{b}_2, \cdots, \mathbf{b}_{m}$ adalah basis dari $V$.  Kita tulis

\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i\]

dimana $\alpha_{si} \in \mathbb{C}$ untuk $1 \leq s \leq 2n+1$ dan $1 \leq i \leq m$.


Maka jika $\mathbf{w}_k$ dibuang,  dari syarat bagus  sisanya dapat dipartisi menjadi dua himpunan disjoint $A_k, B_k \subseteq \{\mathbf{w}_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ yang memenuhi

\[\left( \sum_{j \in A_k} \alpha_{j1} \right) b_1 +  \cdots + \left( \sum_{j \in A_k} \alpha_{jm} \right) b_m = \left( \sum_{j \in B_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in B_k} \alpha_{jm} \right) b_m \]

Ini berarti untuk setiap $i \in \{1, 2, \cdots, m\}$ bilangan kompleks $\alpha_{1i}, \alpha_{2i}, \cdots, \alpha_{2n+1 i}$ memenuhi syarat bagus, sehingga $\alpha_{1i}=\alpha_{2i}= \cdots=\alpha_{2n+1 i}$. Jadi diperoleh untuk sebarang $s, t \in {1, 2, \cdots, 2n+1}$ berlaku

\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i = \sum_{i=1}^m \alpha_{ti} \mathbf{b}_i = \mathbf{w}_{t}\]

dan kita selesai.

Dari sini kita bisa melihat bahwa jika "berat" batu merupakan vektor, matriks, atau bahkan ketika batu tersebut mempunyai "berat"  polynomial, jika syarat bagus terpenuhi maka berat mereka sama.


Sebenarnya (mungkin )kita bisa mengeneralisasi lebih jauh, pada artikel "A Combinatorial Generalization of a Putnam Problem" oleh Ömer Egecioglu, di American Mathematical Monthly, dia membuktikan (dengan menggunakan Cyclotomic Polynomial ) pernyataan berikut:

Misalkan $\xi$ sebuah akar primitif dari $x^q-1$ dimana $q=p^r$, dan $p$ adalah bilangan prima. Diberikan barisan $S$ yang terdiri dari $qn+1$ buah bilangan komplex $z_1, z_2, \cdots, z_{qn+1}$ dengan sifat :  Untuk setiap $i \in \{1, 2, \cdots qn+1\}$. $S \backslash \{z_i\}$ dapat di partisi menjadi $q$ buah himpunan sama besar $S_{i0}, S_{i1}, \cdots, S_{i, q-1}$ dengan
\[\sum_{k=0}^{q-1} \xi^k \sum_{z_j \in S_{t,k}} z_j=0\]
maka $z_1 = z_2 = \cdots = z_{qn+1}=0$

Ketika $k=1$ dan $p=2$, kita peroleh versi bilangan kompleks yang telah kita buktikan diatas.

Jika digabung dengan argumen saya yang sebelumnya, teorema diatas harusnya juga berkerja untuk sebarang ruangan vektor atas bilangan kompleks. [ya kan? :p ]

Continue Reading

Aftermath dan Beforemath Mario di ISMOC.

Aftermath dan Beforemath Mario di ISMOC.

00:04:00  

Beberapa hari yang lalu, saya mengajukan sebuah soal di lomba ISMOC, yang ternyata semalam sebelum lomba, diberi counter-example oleh Erlang Wiratama Surya T_T.  Tapi untungnya kita beri sebuah phrase sehingga bisa dikerjakan.


Karena soalnya berasal dari sebuah argument extermal (karena saya bikin soalnya pakai argument dulu, trus ditambah macam-macam baru jadi soal), akhirnya kita memberikan tambahan kata-kata pada soalnya agar argument extermal saya tetap jalan. Tambahannya cukup minim yaitu ""beserta sebuah kanal dari $G$ ke $X$"" seperti pada soal dibawah (huruf tebal menyatakan ralat yang ditambahkan).

Walaupun sebenarnya, karena sudah mengantuk, kita melakukan argument ekstermal pada directed graph menggunakan arah yang berbeda dengan yang diberikan soal, dan untungnya suatu struktur pada soal merupakan sebuah cycle, jadi pada akhirnya arahnya tidak begitu ngaruh, dan soal masih benar, ini hoki maksimal sih :p.

Saya minta maaf atas kesalahan ini, dan berterima kasih kepada Erlang yang sudah mau berdiskusi sampai jam 2 subuh pada malam sebelum lomba.
Pada saat lomba, terdapat dua orang yang berhasil menyelesaikan soal ini dengan sempurna.

Mario sedang berada  pada Negeri Jamur yang mempunyai $n$ buah kota. Beberapa dari kota tersebut terhubung oleh saluran pipa yang mempunyai arus satu arah, pipa-pipa ini dapat digunakan sebagai sarana transportasi antar kota, namun Mario tidak bisa berpindah melawan arus pada pipa-pipa tersebut, sehingga setiap pipa hanya berlaku sebagai jalan satu arah.  Diketahui bahwa untuk setiap kota, banyak pipa dengan arus menuju keluar kota sama banyak dengan banyak pipa dengan arus menuju masuk ke kota tersebut.  

Suatu hari pada kota $P$, Mario menekan tombol P-Switch  yang menyebabkan semua arus  pipa pada Negeri Jamur berbalik arah, yakni pipa dengan arus dari kota $a$ ke kota $b$ berubah menjadi  pipa dengan arus dari kota $b$ ke kota $a$. Kemudian dimulai dari kota $P$, Mario berkelana ke kota-kota dengan menggunakan arus pada pipa-pipa tersebut.  Setelah efek P-Switch habis, semua arah arus pipa kembali seperti semula dan pada saat itu Mario sudah berada di kota $X$ dan telah mengunjungi semua kota tepat sekali dengan menggunakan tepat $n-1$ buah pipa,  sebutlah $n-1$ buah pipa yang telah dilalui Mario tersebut (beserta sebuah kanal dari $G$ ke $X$) sebagai pipa spesial, dan pipa yang lain sebagai pipa tak-spesial. 

Misalkan dimulai dari kota $X$, Mario akan menutup pipa-pipa pada Negeri Jamur dengan berkelana ke kota-kota melalui pipa-pipa tersebut dengan aturan berikut: 

• Apabila sebuah pipa telah dilalui oleh Mario, maka pipa tersebut langsung dia tutup dan tidak bisa dilalui lagi. 
• Pada setiap kota, Mario akan memilih keluar melalui pipa spesial hanya jika semua pipa tak-spesial yang menuju keluar dari kota tersebut sudah ditutup. 

Buktikan bahwa dengan aturan diatas, (apapun pilihan Mario) ketika Mario sudah tidak bisa berpindah kota, maka pada saat itu dia sedang berada kembali di kota $X$ dan telah menutup semua pipa pada Negeri Jamur.  

Solusi (Outline) :   Pertama-tama buktikan dulu ketika Mario stuck di suatu kota, yakni sudah tidak bisa kemana-mana lagi, maka pasti kota itu adalah kota $X$.  Jadi pipa spesial yang masuk dan keluar kota $X$ sudah dipakai.  Jika ada pipa yang belum dipakai, pilih pipa spesial $A$ ke $B$ yang belum terpakai dengan $B$ paling jauh ke $X$, maka nanti diperoleh pipa spesial dari $B$ juga belum terpakai, kontradiksi dengan $B$ paling jauh.


Yang jadi masalah adalah struktur pipa spesial pada soal, yang akhirnya kita ubah pada soal diatas menjadi cycle.

Berikut adalah beberapa versi soal :

1.  (Sebelum Ralat)  Struktur pipa spesial pada soal adalah directed path dari $X$ ke $G$ yang memuat semua kota.

2. (Setelah Ralat) Struktur pipa spesial pada soal adalah directed cycle yang memuat semua kota.

3. (Awal ketika buat) Struktur pipa spesial pada soal adalah directed path dari $G$ ke $X$ yang memuat semua kota.

Perhatikan bahwa yang membedakan  1 dan 3  itu hanya arah saja (mungkin dulu saya lupa bahwa ketika efek P-Switch habis, maka pipa spesialnya kembali ke arah semua juga.)

Versi 1 tidak berkerja karena ketika $B$ terjauh,  belum tentu ada pipa spesial bermula dari $B$.

Versi 3 harusnya tetap berkeja, namun ceritanya akan sedikit ribet, dan soal sekarang saja sudah panjang (Saya baru nyadar bahwa sebenarnya cukup bilang, pipa spesial ga balik lagi ke arah awal).

Ketika saya melihat kembali ketikan saya beberapa bulan lalu, ternyata saya menggunakan argument "$B$ paling dekat ke $X$" ,  sepertinya saya melakukan argument nya dengan asumsi bahwa pipa spesial arahnya tetap sama ketika P-Switch ditekan lagi.

Anyway, soal diatas merupakan adaptasi dari sebuah Algoritma untuk mendeteksi Eulerian Cycle pada sebuah graph simple, yang disebut Fleury's Algorithm. Algoritma yang saya tahu berkerja di Graph Simple, yaitu dengan melihat sebuah struktur subgraph berupa "bridge".  Nantinya edges yang berada pada bridge ini akan digunakan sebagai last resort ketika mencari Eulerian Cycle.

Saya mencoba mengerjakan Algoritma serupa ketika Graph yang diberikan adalah Graph berarah,  namun disini, agar terdapat Eulerian Cycle, saya beri kondisi in degree sama dengan out degree (yang ini saya jadiin soal Final ISMOC SMP :p ).

 Sayangnya meskipun dengan syarat in-degree dan out-degree, saya masih belum bisa menemukan struktur yang cocok untuk "bridge" di directed graph.  Setelah beberapa lama,  saya menggunakan argument ekstermal diatas, dan ambil asumsi malas bahwa bridge nya berbentuk garis saja. (yang akhirnya diubah menjadi cycle, karena phrase minim yang dibutuhkan).

Kira-kira struktur general subgraph spesial untuk Fleury's Algortihm versi directed graph ini apa ya?

Continue Reading

Masalah Cap-Set

Masalah Cap-Set

07:19:00   Cap Set,

Beberapa hari yang lalu, saya diberikan sebuah link oleh Pak Aleams Barra.   Pada link tersebut dijelaskan tentang sebuah masalah Kombinatorika yang baru-baru ini mendapat sebuah perkembangan berarti. Masalah ini biasa disebut sebagai cap set problem.  Masalah ini cukup high-profile karena beberapa matematikawan terkenal seperti Field Medalist Timothy Gowers dan Terrence Tao juga pernah tertarik dalam masalah ini.
Posting Blog Terrence Tao tahun 2007 tentang capset
Posting Blog Timothy Gowers tahun 2011 tentang capset

Dari hasil ini, dua konjektur langsung terbukti (dari post Prof. Gil Kalai) yaitu :

1. Erdos-Szemeredi Sunflower Conjecture dan 
2. Strong Cap Set Conjecture

Teorema 2.8 pada Paper Ini (oleh Noga Alon, Amir Shpilka, and Christopher Umans) 2 menyebabkan 1.  

Yang menghangatkan lagi diskusi tentang cap set baru-baru ini adalah ketika Ernie Croot, Vsevolod F. Lev, dan Péter P. Pach meletakkan paper pra-review mereka ke arxiv.org, tentang progression-free set di $\mathbb{Z}_4^n$ . Teknik Polynomial yang mereka pakai, menjadi game-changing dalam diskusi mengenai cap problem ini, sebelumnya para matematikawan menggunakan pendekatan Metode Fourier untuk memperoleh batas dari cap problem tersebut.  (Péter P. Pach ini ternyata pernah ikut IMO dua kali, dapat medali emas di tahun 2004)

Lemma polynomial (atau sekarang disebut Croot-Lev-Pach Lemma) sebenarnya sudah ditanyakan beberapa kali oleh Vsevolod Lev di mathoverflow (klik disini)  untuk melihat pertanyaaan Vsevolod Lev (dia sudah mencari jawabannya sampai tiga tahun!) (Vsevolod Lev ini ternyata proposer soal IMO 1989 no 6)

Argument yang dipakai oleh Croot-Lev-Pach, di adaptasi oleh matematikawan Jordan Ellenberg dan Dion Gijswijt untuk menyelesaikan masalah cap-set di $\mathbb{F}_q^n$. Setelah melihat Croot-Lev-Pach Lemma,  mereka berdua awalnya membuat paper yang terpisah  (sampai akhirnya mereka sadar bahwa argument mereka mirip) jadi mereka memutuskan untuk (akan) mempublish paper nya sebagai joint paper. (Ternyata si Jordan Ellenberg ini dulu tiga kali ikut IMO, dua kali perfect score 1987/1989 ) (Ternyata juga Dion Gijswijt ini pernah ikut IMO tiga kali, dua kali dapat HM , salah satunya di problem no 6 tahun 1994. )

Yang menarik adalah, argument yang dipakai pada paper diatas, cukup elementer sampai-sampai (seharusnya) mahasiswa matematika S1 bisa mengerti , yang tidak begitu elementer mungkin hanya pembatasan generalized binomial coefficient dengan ketaksamaan probabilistik, tapi jika sudah mengetahui variant-variant dari Ketaksamaan Probabilistic Tchebishev, harusnya tidak masalah.

Pada post-post ini saya akan mencoba (menjelaskan) argumen-argumen yang dipakai pada paper tersebut.   Anda bisa baca paper ini  yang katanya "cukup jelas".   Post-post berikut  ini sebenarnya hanyalah break-down argument dari paper tersebut (karena pak Barra bilang "mulai dari mana?" (breakdown-nya) ).  Saya rasa, yang sudah belajar sedikit tentang vektor space harusnya bisa mengikuti.

Post-post nya saya bagi menjadi 3 bagian: 

1.  Part I  (Ini menjelaskan masalah Cap Set, jika anda baca link di awal post ini, masalahnya dijelaskan oleh sebuah permainan kartu SET , disini saya mencoba menjelaskan mengapa bisa sampai nyasar ke vektor space)

2. Part II (Post ini cukup technical, saya mencoba menjelaskan beberapa pernyataan "satu baris" di paper tersebut yang sebenarnya jika di break-down mungkin 20 baris, tapi tetap elementer)

3. Part III (Karena part II kepanjangan, saya pisah, di Part II key lemma nya yaitu Croot-Lev-Pach Lemma sudah dibuktikan, disini kita pakai argument probabilistik untuk melakukan pembatasan (large deviation problem), saya  tidak buktikan ketaksamaannya karena itu bisa satu paper sendiri (saya paparkan paper nya di post part III )  )

Intinya jika anda mau baca paper nya langsung juga bisa, (cuma tiga halaman).

Continue Reading

Part II (Croot-Lev-Pach Lemma), Ellenberg-Gijswijt argument.

Part II (Croot-Lev-Pach Lemma), Ellenberg-Gijswijt argument.

07:18:00   Cap Set,

Pada post kali ini, saya akan membahas lebih detail tentang salah satu teknik yang dipakai untuk memperoleh batas baru  dari "Cap Set",  kurang dari satu bulan paper tentang teknik ini di input ke arxiv.org ,  sudah banyak para matematikawan yang meng "abuse" teknik ini. Argument yang dipakai merupakan break-down dari paper  Ellenberg dan Gijswijt di joint paper mereka.

Kita akan melakukan perkejaan pada Lapangan Berhingga $\mathbb{F}_q$, dimana $q=p^{r}$ untuk suatu bilangan prima $p$, notasi $\mathbb{F}_q^n$ menyatakan ruang vektor terhadap lapangan $\mathbb{F}_q$.

Huruf besar $X$ menyatakan $n$ buah variabel $(x_1, x_2,\cdots, x_n)$, jadi ketimbang menulis $m(x_1, x_2, \cdots, x_n)$ kita akan cukup menuliskan $m(X)$.  Setiap variabel yang menggunakan huruf tebal seperti $\mathbf{a}$ akan menyatakan nilai vektor di $\mathbb{F}_q^n$ dengan komponen kei-i samadengan $a_i$, jadi $\mathbf{a}=(a_1, \cdots, a_n)$ dimana $a_i \in \mathbb{F}_q$.  Dengan demikian notasi $m(\mathbf{a})$   berarti  sama saja dengan mengevaluasi  fungsi $m(X)$ ketika $x_i=a_i$, yakni
\[m(\mathbf{a}) = m(a_1, a_2, \cdots, a_n)\]
Kita juga menggunakan notasi
\[m(X-\mathbf{a}) = m(x_1-a_1, \cdots, x_n-a_n)\]

Sebuah polynomial multivariable $P(X)=\sum h_j x_1^{d_1} \cdots x_n^{d_n}$ mempunyai suku derajat $d$ apabila terdapat salah satu dari monomial $x_1^{d_1} \cdots x_n^{d_n}$ pada jumlahan diatas yang derajat total-nya $d_1+\cdots+d_n=d$.

Lemma 1
Semua fungsi  $f: \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ adalah polinomial multivariabel dengan derajat setiap variabel tidak lebih dari $q-1$.

Bukti :


Kita akan menggunakan "Interpolasi Langrange", oleh karena itu kita membutuhkan sebuah indicator function $\mathbb{1}_0(X)$, yang didefinisikan sebagai:
\[\mathbb{1}_0(x_1, x_2, \cdots, x_n) = \prod_{j=1}^n (1-x_j^{q-1})\]

Perhatikan bahwa $\mathbb{1}_0(\mathbf{0}) = 1$, sedangkan jika $X \neq \mathbf{0}$, karena di $\mathbb{F}_q$ berlaku $x_i^{q-1}=1$ maka $\mathbb{1}_0(X) = 0$ jika $X \neq \mathbf{0}$.
Karena anggota $\mathbb{F}_{q}^n$ ada berhingga banyaknya, maka nilai dari $f(\mathbf{b})$ bisa kita list untuk semua $\mathbf{b} \in \mathbb{F}_q^{n}$ .
Untuk sebarang $\mathbf{b} \in \mathbb{F}_q^n$ definisikan fungsi
\[\mathbb{1}_{\mathbf{b}}(X) : = \mathbb{1}_0(X-\mathbf{b})\]
Perhatikan bahwa dari definisi $\mathbb{1}_0(X)$, kita peroleh
\[\mathbb{1}_{\mathbf{b}}(\mathbf{b}) = \mathbb{1}_0(\mathbf{0})=1 \qquad \text{dan}\qquad
\mathbb{1}_{\mathbf{b}}(X) = 0 \quad \text{untuk $X \neq \mathbf{b}$}\]
Misalkan $\mathbb{F}_q^n=\{\mathbf{c}_1, \mathbf{c}_2, \cdots, \mathbf{c}_{q^n}\}$. Semua fungsi $f \in \mathbb{F}_q^{\mathbb{F}_q^n}$ juga dapat dinyatakan sebagai $q^n$-tuple
\[(f(\mathbf{c}_1), \cdots , f(\mathbf{c}_{q^n} ))\]
yang merupakan daftar dari semua nilai fungsi tersebut untuk semua $q^n$ buah anggota $\mathbb{F}_q^n$. Dari daftar nilai $f$ diatas kita bentuk fungsi
\[g(X) = \sum_{j=1}^{q^n} f(\mathbf{c}_j) \cdot \mathbb{1}_{\mathbf{c}_j}(X) \]
Karena $\mathbb{1}_{\mathbf{c}_j}(X)$ adalah sebuah polinomial, maka $g(X)$ juga sebuah polinomial, dan dari definisi $\mathbb{1}_0 (X)$, pada polinomial $g(X)$ berlaku derajat dari tiap-tiap variabel $x_i$ selalu kurang dari $q$.

Perhatikan bahwa untuk setiap $j=1, \cdots, q^n$ berlaku $g(\mathbf{c}_j) = f(\mathbf{c}_j)$, jadi $f(X)$ dan $g(X)$ adalah fungsi yang sama.
$\blacksquare$


Misalkan $S_n$ adalah ruang vektor atas $\mathbb{F}_q$ yang direntang oleh monomial $x_1^{d_1} \cdots x_n^{d_n}$ dimana $0\leq d_i \leq q-1$ untuk setiap $i$, dengan kata lain kita bisa bilang $S_n$ adalah himpunan semua polynomial $n$-variable dengan koefisien di $\mathbb{F}_q$ yang derajat setiap variabel nya kurang dari $q$.

Perhatikan bahwa tiap monomial tersebut menjadi basis dari ruang vektor $S_n$, dan karena terdapat $q^n$ buah monomial yang mungkin, maka diperoleh $dim(S_n)=q^n$.   Dari Lemma 1, kita ketahui bahwa semua anggota dari ruang vektor fungsi dari $\mathbb{F}_q^n \rightarrow \mathbb{F}$ (atau biasanya dinotasikan $\mathbb{F}_q^{\mathbb{F}_q^n}$ ) dapat diinterpertasikan sebagai sebuah polynomial multivariabel  yang derajat tiap-tiap variabelnya kurang dari $q$.


Lemma 2

Pemetaan $\varphi : S_n \rightarrow \mathbb{F}_q^{\mathbb{F}_q^n} $ dengan aturan:
\[\varphi(P) =  (P(\mathbf{c}_1) , \cdots, P(\mathbf{c}_{q^n}) ) \]
 adalah sebuah Transformasi Linear yang satu-satu pada (linear isomorphism)  .

Bukti :  Untuk sifat linear nya sudah cukup jelas. Sedangkan Lemma 1 telah membuktikan bahwa $\varphi$ surjektif. Namun karena keduanya mempunyai dimensi yang sama yaitu $q^n$, maka $\varphi$ juga injektif. $\blacksquare$.

Misalkan $S_n^d$ adalah subruang yang direntang oleh monomial dengan derajat tidak lebih dari $d$ , dan misalkan $m_d= \text{dim}(S_n^d)$. Misalkan juga  $A\subset \mathbb{F}_q^n$.

Misalkan $\gamma \in \mathbb{F}_q$, definisikan subruang $V_{\gamma}$ sebagai, sebuah subruang dari $S_n$  yang berisikan semua polinomial di $S_n$, katakanlah polinomial $P(X)$ sedemikian sehingga jika  $\mathbf{t} \not\in -\gamma A$ maka $P(\mathbf{t})=0$.

Lemma 3  $\text{dim}(V_{\gamma}) =  |A| $

Bukti: 
Misalkan $\text{dim}(V_\gamma) = l$.  Misalkan $-\gamma A=\{\mathbf{a}_1, \mathbf{a}_2, \cdots, \mathbf{a}_{k}\}$, dimana $k=|-\gamma A|=|A|$. Akan dibuktikan bahwa polynomial :

\[\mathbb{1}_{\mathbf{a}_1}(X) ,  \cdots,  \mathbb{1}_{\mathbf{a}_k}(X)\]

bebas linear. Misalkan

\[T(X) = \alpha_1 \mathbb{1}_{\mathbf{a}_1}(X) + \cdots + \alpha_k \mathbb{1}_{\mathbf{a}_k}(X) = 0\]
untuk setiap $X \in \mathbb{F}_q^n$, maka secara khusus $T(\mathbf{a}_i)=0$ untuk setiap $i$, namun $T(\mathbf{a}_i) = \alpha_i$, sehingga $\alpha_1 = \cdots =\alpha_k=0$, jadi terbukti bebas linear.

Perhatikan juga bahwa untuk setiap $j$,  $\mathbb{1}_{\mathbf{a}_j}(X)$ bernilai tak-nol hanya jika $X=\mathbf{a}_j \in -\gamma A$, jadi untuk $X \not \in -\gamma A$ haruslah $\mathbb{1}_{\mathbf{a}_j}(X)=0$, sehingga semua fungsi $\mathbb{1}_{\mathbf{a}_j}(X)$ diatas adalah anggota $V_{\gamma}$. Ini berarti kita telah menemukan $|A|$ buah anggota di $V_{\gamma}$ yang bebas linear, sehingga diperoleh $\text{dim}(V_{\gamma}) = l \geq |A|$.

Sekarang akan dibuktikan bahwa $\text{dim}(V_{\gamma}) \leq |A|$.

Dari lemma $2$, jika $m_1(X), m_2(X), \cdots , m_{l}(X)$ adalah monomial yang merupakan basis dari $V_{\gamma}$, maka $\varphi(m_i(X))$ untuk $i=1,2, \cdots, l$ juga membentuk basis. Kita dapat menulis

\[\varphi(m_1(X)) = (m_1(\mathbf{c}_1), \cdots , m_1(\mathbf{c}_{q^n}) )\]
\[\varphi(m_2(X)) = (m_2(\mathbf{c}_1), \cdots , m_2(\mathbf{c}_{q^n}) )\]
\[...\]
\[\varphi(m_l(X)) = (m_l(\mathbf{c}_1), \cdots , m_l(\mathbf{c}_{q^n}) )\]

Dari daftar semua nilai $m_i(X)$ diatas, yang mungkin tidak bernilai nol hanya pada kolom-kolom dengan indeks $j$ ketika $\mathbf{c}_j \in -\gamma A$. Jadi hanya ada paling banyak $|-\gamma A|= |A|$ buah kolom yang bukan nol.

Kita dapat melihat daftar diatas sebagai matriks $l \times q^n$, dimana hanya ada paling banyak $|A|$ buah kolom yang tak-nol. Karena $m_i(X)$ basis dan sifat $\varphi$ yang merupakan linear isomorphism, maka semua vektor baris $(m_i(\mathbf{c}_1), \cdots , m_i(\mathbf{c}_{q^n}) )$ juga merupakan basis, oleh karena itu mereka semua bebas linear, dengan kata lain matriks tersebut full-rank baris. Jadi dimensi dari $V_{\gamma}$ yaitu $l$ adalah rank dari matriks $l \times q^n$ tersebut.

Kita dapat membuang kolom-kolom yang sudah pasti bernilai nol dari daftar-daftar diatas tanpa mengubah rank, yakni membuang sebanyak $q^n-|A|$ buah kolom.

Dengan demikian setelah membuang $q^n-|A|$ buah kolom, kita akan memperoleh suatu matriks $M$ dengan ukuran $l \times |A|$ . Diperoleh $\text{dim}(V_{\gamma}) = l = \text{rank}(M)$ , sedangkan sebesar-besarnya rank dari suatu matriks yang berukuran $l \times |A|$ adalah $\min(l, |A|)$. Jika $l>|A|$ maka $\min(l, |A|) = |A|$, tapi $l \leq \min(l, |A|) = |A| < l$, kontradiksi. Jadi haruslah $l \leq |A|$, sehingga kita telah membuktikan bahwa $\text{dim}(V_{\gamma})= l = |A|$. $\blacksquare$

Lemma 4
Misalkan $\alpha + \beta + \gamma = 0$ dimana $\alpha , \beta , \gamma \in \mathbb{F}_q$. Misalkan juga  $A \subset \mathbb{F}_q^n$.
Jika $P \in S_n^d$ memenuhi $P(\alpha \mathbf{a} + \beta \mathbf{b}) = 0$ untuk setiap dua anggota berbeda $\mathbf{a},\mathbf{b} \in A$ maka
\[\left| \mathbf{s} \in A \, : \, P(-\gamma \mathbf{s}) \neq  0 \right| \leq 2m_{d/2}.\]

Bukti:

Setiap $P\in S_n^d$ dapat kita tulis $P(t_1, t_2, \cdots, t_n) = \sum c_k (t_1^{d_1} \cdots t_n^{d_n})$, dimana $d_1 + \cdots + d_n \leq d$.  Jadi jika $\mathbf{x} = (x_1, \cdots, x_n)$ dan $\mathbf{y} = (y_1, \cdots, y_n)$ maka

\[P(\alpha \mathbf{x} + \beta \mathbf{y}) =  P(\alpha x_1 + \beta y_1 , \cdots, \alpha x_n + \beta y_n) = \sum c (\alpha x_1 + \beta y_1)^{d_1} \cdots (\alpha x_n + \beta y_n)^{d_n}\]

apabila di expansi maka diperoleh

\[P(\alpha \mathbf{x} + \beta \mathbf{y}) = \sum c^{\prime} x_1^{k_1} \cdots x_n^{k_n} y_1^{l_1} \cdots y_n^{l_n} \qquad \qquad (1) \]

dimana $k_1 + \cdots + k_n + l_1 + \cdots + l_n  \leq d$.  Kemudian  kita bisa sisihkan semua suku yang memuat monomial $v(\mathbf{x})= x_1^{k_1} \cdots x_n^{k_n}$  dengan  $k_1 + \cdots + k_n \leq d/2$, monomial yang seperti ini adalah basis dari $S_n^{d/2}$, sebutlah himpunan basis ini $M_n^{d/2}$. Kontribusi mereka pada jumlahan (1) adalah

\[\sum_{v \in M_n^{d/2}} c_v  F_v(\mathbf{y}) v(\mathbf{x})\]

dimana $F_v(\mathbf{y})$ adalah bagian variabel yang mengandung $y_1^{l_1} \cdots y_n^{l_n}$


Suku yang tersisa adalah ketika $k_1 + \cdots + k_n > d/2$, namun ini menyebabkan $l_1 + \cdots +l_n < \frac{d}{2}$, jadi suku-suku yang tersisa ini memuat $u(\mathbf{y})=y_1^{l_1} \cdots y_n^{l_n}$ dimana $l_1 + \cdots +l_n < \frac{d}{2}$, sehingga dapat ditulis

\[\sum_{v \in M_n^{d/2}} c_u  G_u(\mathbf{x}) u(\mathbf{y})\]

dimana $G_u(\mathbf{x})$ adalah bagian variabel yang mengandung $x_1^{l_1} \cdots x_n^{l_n}$.

sehingga diperoleh

\[P(\alpha \mathbf{x} + \beta \mathbf{y}) = \sum_{v \in M_n^{d/2}} F_v(\mathbf{y}) v(\mathbf{x}) + \sum_{u \in M_n^{d/2}} G_u(\mathbf{x}) u(\mathbf{y}) \]

Karena basis $S_n^{d/2}$ adalah $M_n^{d/2}$ maka $|M_n^{d/2}| = m_{d/2}$. Jadi persamaan diatas dapat ditulis


\[P(\alpha \mathbf{x} + \beta \mathbf{y}) = \sum_{i=1}^{m_{d/2}} F_i (\mathbf{y}) v_i(\mathbf{x}) + \sum_{j=1}^{m_{d/2}} G_j(\mathbf{x}) u_j(\mathbf{y}) \]

(disini $F_i$ dan $G_j$ bisa saja nol bila perlu).

Misalkan $A = \{\mathbf{a}_1, \cdots, \mathbf{a}_m\}$, maka $|A|=m$. Tinjau matriks $B$ yang berukuran $|A| \times |A|$ dengan entry

\[B_{st} = P(\alpha\mathbf{a}_s + \beta \mathbf{a}_t) = \sum_{i=1}^{m_{d/2}} F_i (\mathbf{a}_t) v_i(\mathbf{a}_s) + \sum_{j=1}^{m_{d/2}} G_j(\mathbf{a}_s) u_j(\mathbf{a}_t) \]

Jadi

\[B=\sum_{i=1}^{m_{d/2}} \begin{pmatrix} F_i(\mathbf{a}_1) \\  \vdots  \\ F_i(\mathbf{a}_m ) \end{pmatrix}(v_i(\mathbf{a}_1) , \dots , v_i(\mathbf{a}_m) ) + \sum_{j=1}^{m_{d/2}} \begin{pmatrix} G_j(\mathbf{a}_1) \\  \vdots  \\ G_j(\mathbf{a}_m ) \end{pmatrix}(u_j(\mathbf{a}_1) , \dots , u_j(\mathbf{a}_m) )  \]

Tiap matriks dalam summands diatas adalah perkalian dari vektor $n \times 1$ dan $1 \times n$, maka dari itu mereka semua mempunyai rank kurang dari atau sama dengan $1$. Jadi $B$ adalah penjumlahan dari $2m_{d/2}$ buah matriks yang mempunyai rank $\leq 1$. Karena rank memenuhi sifat $rank(X+Y) \leq rank(X)+rank(Y)$, maka diperoleh $rank(B) \leq 2 m_{d/2}$. Namun dari hipotesa, diperoleh $B_{st}=0$ jika $s\neq t$. Jadi $B$ adalah matriks diagonal, sehingga rank dari $B$ sama-dengan banyaknya entri pada diagonal yang tidak sama-dengan nol.  Sehingga kita simpulkan, banyak entri pada diagonal yang tidak sama-dengan nol harus lebih kecil atau samadengan $2m_{d/2}$.

Ini berarti banyak $\mathbf{s}\in A$ sedemikian sehingga $P(-\gamma \mathbf{s}) = P(\alpha \mathbf{s} + \beta \mathbf{s}) \neq 0$ harus lebih kecil atau samadengan $2m_{d/2}$. Lemma terbukti. $\blacksquare$

Lemma 5Misalkan $d \in [0,(q-1)n]$ dan definisikan $V_{\lambda}^d$ adalah himpunan semua polynomial dengan derajat paling banyak $d$, sedemikian sehingga jika $\mathbf{t} \not \in -\lambda A$ maka berlaku $P(\mathbf{t}) = 0$. Maka berlaku
\[\text{dim} (V_{\lambda}^d)  \geq m_d - q^n + |A| \]

Bukti:

Perhatikan bahwa $V_{\gamma}^d = V_{\gamma} \cap S_n^d$, yang merupakan irisan dari dua subruang, kita ketahui dari lemma 3 bahwa $\text{dim}(V_{\lambda})=|A|$ dan juga kita menggunakan notasi $\text{dim}(S_n^d) = m_d$  jadi diperoleh dengan rumus dimensi

\[\begin{align*} \text{dim}(V_{\gamma}^d) &=\text{dim}(V_{\gamma} \cap S_n^d) \\ &= \text{dim}(V_{\gamma})+\text{dim}( S_n^d) - \text{dim}(V_{\gamma} + S_n^d) \\ &= m_d+|A|  - \text{dim}(V_{\gamma} + S_n^d) \\  & \geq m_d+|A|-q^n\end{align*} \]


Berikutnya kita akan membuktikan batas atas dari $\text{dim} (V_{\lambda}^d)$.

Lemma 6$\text{dim} (V_{\lambda}^d) \leq 2m_{d/2}$

Bukti:

Dengan menggunakan Lemma 4, Kita cukup membuktikan bahwa

\[ \text{dim} (V_{\lambda}^d) \leq \left| \mathbf{s} \in A \, : \, P(-\gamma \mathbf{s}) \neq  0 \right|  \]

untuk suatu polinomial $P\in S_n^d$ yang memenuhi $P(\alpha \mathbf{a} + \beta \mathbf{b}) = 0$ untuk setiap dua anggota berbeda $\mathbf{a},\mathbf{b} \in A$.

Untuk kemudahan kita definisikan $\Sigma_{\lambda} =  \mathbf{s} \in A \, : \, P(-\gamma \mathbf{s}) \neq  0 \right|$

Continue Reading

Part I (Permainan Set)

Part I (Permainan Set)

21:46:00   Cap Set,

Sederhananya begini:

Misalkan terdapat $81$ buah kartu, dimana setiap kartu  mempunyai empat buah atribut yaitu: gambar, angka, warna, dan arsiran, dimana masing-masing atribut dapat berupa $3$ kemungkinan.

Apabila diambil 12 kartu, kemudian dipaparkan, kita diminta untuk menemukan tiga buah kartu dari 12 kartu tersebut sedemikian sehingga untuk tiap-tiap atribut pada ketiga kartu tersebut, semuanya berbeda atau semuanya sama.   Singkatnya seperti pada gambar berikut (diambil dari link yang sama) :

Tiga buah kartu yang memenuhi kondisi diatas, disebut SET.

Masalah ini dapat diintepretasikan dalam bentuk Aljabar Linear.  Setiap $81$ kartu dapat dinyatakan sebagai sebuah vektor berdimensi empat  $(a_1, a_2, a_3, a_4)$  dimana $a_i \in \{0,1,2\}$.

• $a_1$ menyatakan bentuk,  $0$ bila berbentuk diamond, $1$ bila berbentuk oval, $2$ bila berbentuk cacing.
• $a_2$ menyatakan angka,   $0$ bila ada satu buah, $1$ bila ada dua buah, $2$ bila ada tiga buah
• $a_3$ menyatakan warna, $0$ bila berwarna merah, $1$ bila berwarna hijau, $2$ bila berwarna ungu,
• dan $a_4$ menyatakan arsiran, $0$ bila tidak diarsir, $1$ bila diarsir garis-garis, $2$ bila diarsir penuh.

Sebagai contoh, $(1,1,0,1)$ berarti $a_1=1$ (oval) , $a_2=1$ (dua buah), $a_3=0$ (warna merah), $a_4=1$ (diarsir penuh), jadi kartu yang dimaksud adalah :

Dengan demikian, triple SET adalah tiga buah 4-tuple :

\[(a_1, a_2, a_3, a_4) ,  (b_1, b_2, b_3, b_4), (c_1, c_2, c_3, c_4)\]

dimana untuk tiap-tiap $i=1,2, 3, 4$ bilangan $a_i, b_i, c_i$ berbeda semua atau sama semua.

Perhatikan bahwa kita bisa menganggap $\{0,1,2\}$ sebagai sebuah lapangan hingga $\mathbb{F}_3$, dengan operasi modulo $3$.  Pandang persamaan

\[\alpha + \beta + \gamma = 0 \qquad \alpha,\beta, \gamma \in \mathbb{F}_3\]

hanya mempunyai solusi ketika $\alpha=\beta=\gamma$ atau ketika $\{\alpha, \beta, \gamma \}=\{0,1,2\}$. Dengan kata lain, ketika semuanya sama atau semuanya berbeda. 

Dari sini kita peroleh, tiga buah vektor di $\mathbb{F}_3^4$  :

\[\mathbf{a} = (a_1, a_2, a_3, a_4) ,  \mathbf{b}=(b_1, b_2, b_3, b_4), \mathbf{c}=(c_1, c_2, c_3, c_4)\]

membentuk SET jika dan hanya jika $\mathbf{a}+\mathbf{b}+\mathbf{c}=0$.   Hal ini juga berlaku secara general untuk $n\geq 4$, yakni pada vektor-vektor di $\mathbb{F}_3^n$, karena komponen mereka masih di $\mathbb{F}_3$. Yakni, apabila persamaan $\mathbf{a}+\mathbf{b}+\mathbf{c}=0$ terpenuhi maka $\mathbf{a}, \mathbf{b}, \mathbf{c}$ adalah Cap Set.


Persamaan $\mathbf{a}+\mathbf{b}+\mathbf{c}=0$ dimana $\mathbf{a}, \mathbf{b}, \mathbf{c} \in \mathbb{F}_3^n$, misalkan  $\mathbf{b}-\mathbf{a}= \mathbf{d}$. Maka $\mathbf{c}= -2\mathbf{x}-\mathbf{d} = \mathbf{x} + 2\mathbf{d}$ (karena field $\mathbb{F}_3$ mempunyai karakteristik 3).

Ini berarti himpunan triple yang memenuhi SET membentuk barisan aritmatika $\{\mathbf{a}, \mathbf{a}+\mathbf{d}, \mathbf{a} + 2\mathbf{d}\}$.

Jadi masalah :

Dari $3^n$ buah kartu,  berapa banyakkah kartu terbanyak yang bisa kita paparkan di meja, sehingga tidak ada tiga buah yang membentuk  SET?

Setara dengan masalah:

Berapa subhimpunan terbesar dari $\mathbb{F}_3^n$ yang tidak memuat barisan aritmatika tiga suku?

Masalah diatas disebut Cap Set problem.

Disini cukup natural bahwa jika kita ingin memperumum permasalahan ke lapangan $\mathbb{F}_q$, dimana ruang vektor yang dilihat adalah $\mathbb{F}_q^n$, namun perlu diperhatikan bahwa apabila kita bermain di lapangan dengan karakteristik bukan $3$, maka  syarat semua berbeda atau semua sama belum tentu setara dengan syarat $\sum a_i = 0$. Sebagai contoh
 misalkan karakteristik $5$, maka persamaan $x_1+ x_2 + x_3+x_4+x_5= 0$  belum tentu menghasilkan solusi semua sama atau semua beda,  contoh $(1,1,4,2,2)$ adalah solusi di lapangan $\mathbb{Z}/5\mathbb{Z}$.

Pada lapangan dengan karakteristik yang lebih umum , yang dimaksud masalah CAP SET adalah masalah mencari himpunan terbesar yang tidak mempunyai tiga buah suku barisan aritmatika.
Sedangkan masalah dimana semua koordinat berbeda atau semua koordinat sama itu disebut masalah sunflower.  Disini kita akan berpindah ke masalah Cap Set saja.

Pada post berikutnya, saya akan memberikan argument untuk mendapatkan batas atas dari Cap Set.

Continue Reading

Soal dari Monthly

Soal dari Monthly

08:34:00   Univ,

Beberapa minggu yang lalu, saya sempat pengen mengirim jawaban ke rubrik American Mathematical Monthly tapi pas saya cek deadline nya sudah lewat, jadi ya saya post disini saja.

11876 Let $a$ and $b$ be the roots of $x^2+x+\frac{1}{2}=0$. Find\[\sum_{n=1}^{\infty} \frac{(-1)^n (a^n+b^n)}{n+2} \]

Solution

Define the sequence $\{a_n\}_{n\geq 0}$ as
\[a_n := (-1)^n (a^n+b^n)  \]
where $a$ and $b$ are the roots of $x^2+x+\frac{1}{2}=0$.

Note that $\alpha:=-a$ and $\beta:=-b$ are  the roots of quadratic equation $x^2-x+\frac{1}{2}=0$, and so $a_n$ can also be written as \[a_n= (-a)^n + (-b)^n = \alpha^n+\beta^n.\] We can directly check that $a_0=2$, and by Viete's Formula we have $a_1=\alpha+\beta=1$ and $a_2=\alpha^2 + \beta^2= (\alpha+\beta)^2-2\alpha \beta= 1-1=0$.


Also by multiplying the equation with $\alpha^n$ we have $\alpha^{n+2} = \alpha^{n+1}-\frac{\alpha^n}{2}$, similarly $\beta^{n+2} = \beta^{n+1}-\frac{\beta^n}{2}$ and hence

\begin{align*} \alpha^{n+2} + \beta^{n+2} = \alpha^{n+1} + \beta^{n+1} - \frac{\alpha^n + \beta^n}{2} \end{align*}
Therefore we have the following recursive formula for the sequence $a_n = (-1)^n (a^n + b^n) = \alpha^n + \beta^n$
\[ a_0=  2\quad a_1=1 \qquad a_{n+2} =  a_{n+1} - \frac{a_n}{2} \quad n\geq 0 \]

Since $a_2 = \alpha^2+\beta^2 = 0$, we have for $j \geq 0$ \[a_{4j+2} = (\alpha^2)^{2j+1} + (\beta^2)^{2j+1} = (\alpha^2+\beta^2)(\alpha^{2j-1} + \cdots + \alpha^{2j-1})=0\]
Thus by the recursive formula
\[a_{4j+3} = -\frac{a_{4j+1}}{2} \qquad \text{and}\qquad a_{4j+4} = a_{4j+3} \qquad  \text{for $j\geq 0$} \]
This gives us the formula of $a_{4k+1}$  which is
\[ a_{4k+1} = a_{4k} - \frac{a_{4k-1}}{2} = \frac{a_{4k-1}}{2} = -\frac{a_{4(k-1)+1}}{4}  = \frac{a_{4(k-2)+1}}{4^2}=\cdots  = \frac{(-1)^{k}}{4^{k}} a_1 =  \frac{(-1)^{k}}{4^{k}}\]
From $a_{4k+2}=0$ and $a_{4k+2} = a_{4k+1} - \frac{a_{4k}}{2}$ we have \[ a_{4k} =2 a_{4k+1} =2\cdot \frac{(-1)^k}{4^k}\]
And using $a_{4k+3} = -\frac{a_{4k+1}}{2}$ we have
\[a_{4k+3}  = \frac{(-1)^{k+1} }{2\cdot 4^k} =  2\cdot \frac{(-1)^{k+1}}{ 4^{k+1}} \]
So the formula for $a_n$ is

\[a_{4k} = 2\cdot \frac{(-1)^k}{4^k} \qquad  a_{4k+1}=\frac{(-1)^{k}}{4^{k}} \qquad a_{4k+2}=0 \qquad a_{4k+3}=2\cdot \frac{(-1)^{k+1}}{ 4^{k+1}} \]
For $|x| \leq 1$, we have for any $n \geq 1$
\[ \left| a_n x^{n+1} \right| \leq |a_{n}| \]
While
\[\sum_{n=1}^{\infty} |a_n| = \sum_{j=1}^{\infty} \left(\frac{2}{4^j} + \frac{1}{4^j} + \frac{2}{4^{j+1}} \right) = \frac{7}{6}\]


Therefore  by the Weierstrass M-Test, $\sum_{n=1}^{\infty} a_n x^{n+1}$ converges uniformly on $[-1,1]$, let say it converges to a function $f(x)$. We have

\begin{align*} f(x)=\sum_{n=1}^{\infty}a_n x^{n+1} &= \sum_{n=1}^{\infty} a_{n+2} x^{n+3}  + a_2 x^3  + a_1 x^2 \\ &=  \sum_{n=1}^{\infty} a_{n+1}x^{n+3} - \sum_{n=1}^{\infty} \frac{a_{n}}{2}x^{n+3} + a_2 x^3  + a_1 x^2  \\ &= xf(x) -\frac{x^2f(x)}{2} + x^2  \end{align*}

Thus
\[f(x)=\frac{2x^2}{x^2-2x+2} \]

By uniform convergence we have

\[\int_0^1 f(x) \, dx = \int_0^1 \sum_{n=1}^{\infty}a_n x^{n+1} \, dx = \sum_{n=1}^{\infty} \int_0^1 a_n x^{n+1} \, dx = \sum_{n=1}^{\infty} \frac{a_n}{n+2}  \]

Therefore the sum equals to

\[\int_0^1 \frac{2x^2}{(x^2-2x+2)}\, dx = \int_0^1 1 + \frac{4x-4}{x^2-2x+2} \, dx =  2x + 2\ln (x^2-2x+2) \bigg|_0^1 = 2-2\ln 2 \]

Continue Reading

Soal Partisi Bilangan Bulat.

Soal Partisi Bilangan Bulat.

00:17:00   Olimpiade Matematika, Umum,

Beberapa hari yang lalu, saya diberi soal berikut oleh Erlang Wiratama Surya :

Diberikan himpunan $X \subset \mathbb{Z}$ dan misalkan $a_1, a_2, \cdots, a_n$ adalah bilangan bulat sedemikian sehingga
\[\mathbb{Z} = \bigcup_{j=1}^n (X+a_j)\]
dan $X+a_i \cap X+a_j = \emptyset$ untuk sebarang $i\neq j$.  Buktikan bahwa terdapat bilangan  bulat tak-nol $p$ sedemikian sehingga $X+p=X$.(Disini definisi dari $X+d:= \{x+d | x \in X\}$ ).

Katanya soal ini ada di Sesi Mandiri Pembinaan IMO Tahap 4.

Sebenarnya saya sudah pernah lihat soal ini sebelumnya (dan waktu itu saya tidak bisa menyelesaikannya).  Tapi sudah lupa dimana.

Sampai sekarang, saya masih penasaran tentang dimana saya melihat soal ini (saya memang sering berasa tidak lega dan agak annoying kalo ada sesuatu berasa di ujung lidah seperti ini :/  )

Bahkan setelah beberapa hari, saya berhasil menyelesaikan soal ini, tapi masih belum tahu source nya (sampai bikin thread di math.stackexcange menanyakan sumber).

Saya  (secara dejavu) merasa  ini bukan soal yang bersumber dari olimpiade, tapi dari matematika popular yang saya pernah baca di blog-blog post beken (Terence Tao, Timothy Gowers, dll)

Anyway ini solusinya, lagi-lagi saya pakai sesuatu yang sering saya pakai beberapa bulan terakhir (lihat soal kompetisi olimpiade.org no 4 buatan saya dan juga teknik yang sama di mini-artikel yang saya tulis ini ) yaitu kombinasi dari Indicator Function + PigeonHole Principle.

Solusi: 
Pertama-tama perhatikan bahwa apabila kita pilih bilangan asli $d$ sedemikian sehingga $a_i^{\prime}=a_i + d$ semua positif maka himpunan $X=X^{\prime} - d$ juga memenuhi

\[\mathbb{Z} = \bigcup_{i=1}^n (X^{\prime} + a_i^{\prime})\]

dan $X^{\prime} + a_i^{\prime} \cap X^{\prime} + a_j^{\prime} = \emptyset$. Lalu, apabila kita berhasil membuktikan $X^{\prime} + p^{\prime} = X^{\prime}$ maka diperoleh $X+p-d= X-d$, jadi $X+p=X$, dan soal terbukti.  Ini berarti pengubahan $a_i \rightarrow a_i^{\prime}$ tidak mengubah maksud soal.

Sehingga tanpa kehilangan keumuman soal bisa diasumsikan semua $a_i$ positif, dan tanpa kehilangan keumuman juga bisa diasumsikan $a_n > a_{n-1} > \cdots  > a_1$.

Sekarang kita definisikan fungsi indikator

\[v_i = \begin{cases} 1 & \text{jika $i\in X$, } \\ 0 & \text{jika tidak} \end{cases} \]

Idenya adalah dengan membuktikan bahwa fungsi indikator $v_i$ periodik, yakni $v_{i+p} =v_i$ untuk suatu $p$.

Maka dari kondisi $X+a_1, X+a_2, \cdots, X+a_n$ adalah partisi dari $\mathbb{Z}$,  diperoleh untuk setiap bilangan bulat $r$ berlaku

\[v_{r-a_1} + v_{r-a_2} + \cdots + v_{r-a_n} = 1\]

Sekarang misalkan $\lambda=a_n - a_1$.  Persamaan diatas adalah relasi rekursif, jadi apabila kita mempunyai informasi nilai awal  paling banyak $\lambda=a_n-a_1$ buah, maka solusi rekursif tersebut akan unik.

Jadi apabila nilai dari

\[v_{r+1}, v_{r+2}, \cdots, v_{r+\lambda}\]

diketahui maka nilai $v_i$ akan bisa di-generate  untuk setiap $i$. Karena $v_i$ hanya bisa nol atau satu, maka kemungkinan nilai awal diatas  hanya ada $2^{\lambda}$. Jadi apabila kita bentuk block-block dengan panjang $\lambda$ :

\[\cdots ,  \{ v_{-\lambda-1},  \cdots, v_{-1}, v_0\} , \{v_1, v_2, \cdots, v_{\lambda} \} , \{v_{\lambda+1}, v_{\lambda+1}, \cdots, v_{2 \lambda}\} , \cdots , \{v_{r+1}, v_{r+2}, \cdots , v_{r+\lambda}\}, \cdots  \]

 maka berdasarkan prinsip PigeonHole terdapat $u_1$ dan $u_2$ sedemikian sehingga

\[v_{u_1+i}=v_{u_2+i} \qquad i=1, \cdots, \lambda \]

dan karena block $v_{u_1 + 1}, v_{u_1+2}, \cdots , v_{u_1 + \lambda}$ men-generate nilai $v_i$,   maka  $v_{u_2 + 1}, v_{u_1+2}, \cdots , v_{u_2 + \lambda}$ juga men-generate nilai $v_i$ yang sama, jadi  nilai setelah $u_2$ mengulangi nilai setelah $u_1$, dan nilai sebelum $u_2+1$ mengulangi nilai sebelum $u_1+1$, sehingga $v_i$ periodic.

Ini berarti terdapat $p \neq 0$ sedemikian sehingga $v_{i+p} = v_i$,  untuk setiap $i$. Sehingga jika $h \in X$ jika dan hanya jika $v_{h} = 1 = v_{h+p}$ jika dan hanya jika $h+p \in X$. Terbukti.

Continue Reading