Formal power series

Định nghĩa 1. Một chuỗi lũy thừa hình thức là một biểu diễn có dạng

$a_0+a_1x+a_2x^2+a_3x^3+\ldots,$

hay gọn hơn $\displaystyle\sum_{k=0}^{\infty}a_kx^k.$ Trong đó $(a_n)_{n\geq 0}$ là một dãy các số phức. Các $a_i$ được gọi là các hệ số của chuỗi lũy thừa hình thức, $a_0$ được gọi là hệ số tự do của chuỗi lũy thừa hình thức.

Từ “hình thức” trong định nghĩa trên có nghĩa là ta không bận tâm đến việc cho $x$ các giá trị đặc biệt, ta cũng không quan tâm đến tính hội tụ hay phân kỳ của chuỗi. Tập tất cả các chuỗi lũy thừa hình thức với hệ số thuộc một tập hợp $A$ được ký hiệu bởi $A[[x]]$ . Với một chuỗi lũy thừa hình thức $a(x)$ , ta ký hiệu hệ số của $x^n$ trong chuỗi này bởi $[x^n]a(x)$ .

Nếu $a_i=0$ với mọi $i>m$ thì để cho gọn, chuỗi $\sum_{n=0}^{\infty}a_nx^n$ sẽ được viết là

$a_0+a_1x+\ldots+a_mx^m.$

Chuỗi lũy thừa hình thức với tất cả các hệ số bằng $0$ được gọi là chuỗi không, ký hiệu là $0$ . Tổng và tích của hai chuỗi lũy thừa hình thức $\displaystyle\sum_{n=0}^{\infty}a_nx^n$ và $\displaystyle\sum_{n=0}^{\infty}b_nx^n$ được định nghĩa bởi

$\displaystyle\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n$

và

$\displaystyle\left(\sum_{n=0}^{\infty}a_nx^n\right)\left(\sum_{n=0}^{\infty}b_nx^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n.$

Với hai phép toán này thì $\mathbb{C}[[x]]$ là một vành giao hoán có đơn vị là chuỗi đơn vị $1+0x^1+0x^2+0x^3+\ldots,$ ký hiệu là $1$ .

Tương tự như với các số phức, ta có kết quả sau:

Định lý 1. Nếu $a$ và $b$ là các phần tử khác không của $\mathbb{C}[[x]]$ , thì chuỗi tích $ab$ cũng khác chuỗi không.

Chứng minh. Gọi $m$ là số tự nhiên nhỏ nhất sao cho $[x^m]a\not=0$ , và $n$ là số tự nhiên nhỏ nhất sao cho $[x^n]b\not=0$ . Khi đó

$[x^{m+n}](ab)=([x^m]a)([x^n]b)\not=0,$

suy ra $ab$ khác chuỗi không. $\Box$

Khác với phép nhân trong tập các số phức, không phải mọi chuỗi khác không đều có nghịch đảo. Chẳng hạn, khi $a(x)=0+x+0x^2+0x^3+\ldots,$ (chuỗi này thường được viết là $a(x)=x$ ) thì $a(x)\not=0$ nhưng không có chuỗi $b(x)$ để $a(x)b(x)=1$ .

Định lý 2. Chuỗi $a(x)$ có nghịch đảo khi và chỉ khi $[x^0]a(x)\not=0$ .

Chứng minh. Giả sử chuỗi $a(x)$ có nghịch đảo, và $b(x)$ là nghịch đảo của nó. Khi đó

$1=[x^0](ab)=([x^0]a)([x^0]b),$

suy ra $[x^0]a(x)\not=0$ .

Bây giờ giả sử $\displaystyle a(x)=\sum_{n=0}^{\infty}a_nx^n$ là một chuỗi lũy thừa hình thức có $a_0=[x^0]a(x)\not=0$ . Chuỗi lũy thừa hình thức $\displaystyle b(x)=\sum_{n=0}^{\infty}b_nx^n$ là nghịch đảo của $a(x)$ khi và chỉ khi $a_0b_0=1$ và

$\displaystyle\sum _{k=0}^na_kb_{n-k}=0,\quad\forall n\geq 1.$

Từ hệ này ta có thể xác định $b(x)$ bởi $b_0=1/a_0$ và

$\displaystyle b_n=-\frac{1}{a_0}\sum _{k=1}^na_kb_{n-k},\quad\forall n\geq 1.$ $\Box$

Khi $a$ là một chuỗi có nghịch đảo thì ta ký hiệu chuỗi nghịch đảo của nó bởi $a^{-1}$ . Tích của chuỗi $b$ và chuỗi $a^{-1}$ thường được viết là $\frac{b}{a}$ .

Ví dụ. Chuỗi lũy thừa hình thức $1-x$ có nghịch đảo là chuỗi

$\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+\ldots$

Định nghĩa 2. Dãy các chuỗi lũy thừa hình thức với hệ số phức $\{S_n(x)\}_{n\geq 1}$ được gọi là hội tụ đến chuỗi lũy thừa hình thức với hệ số phức $S(x)$ , ký hiệu $\displaystyle\lim_{n\to\infty} S_n(x)=S(x)$ , nếu với mỗi $n\geq 0$ có số nguyên dương $N$ sao cho $[x^n]S_i(x)=[x^n]S(x)$ mỗi khi $i\geq N$ . Trong trường hợp này ta nói $\{S_n(x)\}_{n\geq 1}$ là một dãy hội tụ.

Khi $\displaystyle A(x)=\sum_{n\geq 0}a_nx^n$ là một phần tử khác không của $\mathbb{C}[[x]]$ , ta gọi bậc của $A(x)$ , ký hiệu $\deg A(x)$ , là số $n$ nhỏ nhất sao cho $a_n\not=0$ . Dễ thấy nếu $B(x)$ và $C(x)$ là các phần tử khác không của $\mathbb{C}[[x]]$ thì $B(x)C(x)$ cũng là một phần tử khác không của $\mathbb{C}[[x]]$ , và

$\deg B(x)C(x)=\deg B(x)+\deg C(x).$

Ta quy ước $\deg 0=\infty$ . Sử dụng bậc của một chuỗi lũy thừa hình thức ta có một định nghĩa khác của tính hội tụ của dãy các chuỗi lũy thừa hình thức.

Continue reading →

Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

[3] https://nttuan.org/2023/09/01/graph02/

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$

Erdos–Ginzburg–Ziv theorem

Định lí Erdos–Ginzburg–Ziv. Cho số nguyên dương $n.$ Khi đó trong mỗi $2n-1$ số nguyên, tồn tại $n$ số có tổng chia hết cho $n.$

Chứng minh. Trước tiên ta thấy khẳng định đúng với $n=1,$ và nếu khẳng định đúng với $x>1$ và $y>1$ thì nó cũng đúng với $xy.$ Thật vậy, giả sử $a_1,a_2,\ldots,a_{2xy-1}$ là các số nguyên bất kỳ. Trước tiên, vì $2xy-1>2y-1$ nên trong các số đã cho ta có thể chọn $y$ số $a_{1j}$ sao cho $\displaystyle a_{11}+a_{12}+\cdots +a_{1y}\equiv 0\pmod{y},$ sau bước này ta còn $2xy-1-y=(2x-1)y-1>2y-1$ số. Trong $(2x-1)y-1$ số đó ta chọn $y$ số $a_{2j}$ sao cho

$a_{21}+a_{22}+\cdots+a_{2y}\equiv 0\pmod{y},$ sau bước này ta còn $(2x-2)y-1$ số. Tiếp tục làm như vậy cuối cùng ta được $(2x-1)y$ số $a_{ij}$ thỏa mãn

$a_{i1}+a_{i2}+\cdots+a_{iy}\equiv 0\pmod{y},\quad \forall i=\overline{1,2x-1}.$ Vì khẳng định đúng với $n=x$ nên trong $2x-1$ số nguyên $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy}),$ tồn tại $x$ số, chẳng hạn $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy})$ với $i=1,$ $2,\ldots,$ $x$ , có tổng chia hết cho $x.$ Khi đó $xy$ số $a_{ij}$ với $(i,j)\in [x]\times [y]$ có tổng chia hết cho $xy,$ suy ra khẳng định đúng với $xy.$

Vậy ta chỉ cần chứng minh nó đúng với các số nguyên tố. Giả sử $n=p$ là một số nguyên tố và $a_0,$ $a_1,\ldots,$ $a_{2p-2}$ là các số nguyên bất kỳ. Ta cần chỉ ra có $p$ số trong các số đã cho có tổng chia hết cho $p.$ Với mỗi số nguyên $\alpha,$ ký hiệu $(\alpha)_p$ là số dư khi chia $\alpha$ cho $p.$ Không mất tính tổng quát, giả sử $\{(a_i)_p\}$ là một dãy không giảm. Nếu tồn tại $i\in [p-1]$ sao cho $(a_i)_p=(a_{i+p-1})_p$ thì

$(a_i)_p=(a_{i+1})_p=\cdots =(a_{i+p-1})_p\Rightarrow \sum_{j=i}^{i+p-1}a_j\equiv 0\pmod{p},$ nếu không, xét $p-1$ tập $A_i=\{a_i,a_{i+p-1}\}$ và dùng hệ quả trong [1] ta có

$\mid A_1+A_2+\cdots+A_{p-1}\mid \geq \min (p,(p-1)\times 2-(p-1)+1)=p,$ suy ra với mỗi $i\in [p-1],$ tồn tại $b_i\in A_i$ để

$b_1+b_2+\cdots+b_{p-1}\equiv -a_0\pmod{p}\Rightarrow b_1+b_2+\cdots+b_{p-1}+a_0\equiv 0\pmod{p}.$ $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2014/09/29/cauchy-davenport/

A proof of Pick’s theorem

Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ $Oxy$ , cho tam giác $ABC.$ Khi đó diện tích của tam giác $ABC$ bằng $\displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|.$ Nói riêng, với mỗi hai điểm $M$ và $N$ ta có diện tích của tam giác $OMN$ bằng $\dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.$

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng $\dfrac{1}{2}.$

Chứng minh. Giả sử $TAB$ là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem $T$ trùng với gốc tọa độ $O.$ Ta cần chứng minh $\mid x_1y_2-x_2y_1\mid =1,$ với $(x_1;y_1)$ và $(x_2;y_2)$ lần lượt là tọa độ của $A$ và $B.$

Gọi $K$ là điểm sao cho $OAKB$ là hình bình hành. Giả sử $M$ là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho $M$ khác các đỉnh. Khi đó $M$ thuộc tam giác $ABK$ và điểm $N$ đối xứng với $M$ qua tâm hình bình hành là điểm nguyên thuộc tam giác $OAB$ nhưng khác các đỉnh, không thể xảy ra điều này do $OAB$ là một tam giác cơ bản. Như vậy hình bình hành $OAKB$ không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử $P$ là một điểm nguyên bất kỳ. Vì $\overrightarrow{OA}$ và $\overrightarrow{OB}$ là hai vector không cùng phương nên tồn tại cặp số thực $(\alpha,\beta)$ để $\overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}.$ Gọi $P'$ là điểm xác định bởi $\overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.$ Vì $\{\alpha\}$ và $\{\beta\}$ thuộc $[0;1)$ nên $P'$ thuộc hình bình hành $OAKB$ , nhưng $P'$ lại là một điểm nguyên, suy ra $P'$ phải là một trong bốn đỉnh của hình bình hành. Dễ thấy $P'\equiv O$ và do đó $\alpha$ và $\beta$ là hai số nguyên.

Gọi $\overrightarrow{i}$ và $\overrightarrow{j}$ lần lượt là các vector đơn vị đặt trên $Ox$ và $Oy$ . Khi đó theo lập luận trên, tồn tại các cặp số nguyên $(u,v)$ và $(u',v')$ để $\overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}$ và $\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}.$ Từ hai đẳng thức này ta có $\begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}$ và $\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases}$ suy ra $\displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}$ và $\displaystyle v'=\frac{x_1}{D},$ trong đó $D=x_1y_2-x_2y_1\not =0$ do $O,A$ và $B$ không thẳng hàng. Vì $u,$ $v,$ $u'$ và $v'$ là các số nguyên nên $x_1,x_2,y_1$ và $y_2$ đều là bội của $D$ , do đó $D^2\mid D$ và bởi thế, $D=\pm 1.$

Định lí Pick. Cho $P$ là một đa giác đơn có các đỉnh là các điểm nguyên, $I$ là số điểm nguyên nằm trong và $B$ là số điểm nguyên nằm trên biên của $P$ . Khi đó ta có đẳng thức $\displaystyle S_P=I+\frac{1}{2}B-1.$

Chứng minh. Chia $P$ thành $N$ tam giác cơ bản. Gọi $S$ là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính $S$ theo hai cách. Vì số tam giác là $N$ nên $S=N\pi.$

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong $P$ bằng $2\pi$ , tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của $P$ nhưng không phải đỉnh của $P$ bằng $\pi$ và tổng của tất cả các góc có đỉnh là đỉnh của $P$ bằng $(n-2)\pi$ , ở đây $n$ là số đỉnh của $P$ . Do đó $S=2\pi I+\pi B-2\pi$ , suy ra $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ . Để ý thêm $S_P=\dfrac{1}{2}N$ , ta có điều phải chứng minh.