Part II (Croot-Lev-Pach Lemma), Ellenberg-Gijswijt argument.
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.
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.
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.
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
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
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).
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|
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|
%2C%20Ellenberg-Gijswijt%20argument.%20%20)
Post a Comment: