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|$
Post a Comment: