Combinatorial Nullstellensatz

Trong bài này chúng tôi giới thiệu một chứng minh ngắn của định lý không điểm tổ hợp của Noga Alon, và sử dụng nó chứng minh định lý Cauchy – Davenport (xem [1]). Từ bây giờ, khi nói đến trường thì các bạn hiểu là nói đến $\displaystyle \mathbb{C}$ , $\displaystyle \mathbb{R}$ , $\displaystyle \mathbb{Q}$ , hay $\displaystyle \mathbb{Z}/p\mathbb{Z}$ .

Định lý 1 (N. Alon, 1999). Cho $\displaystyle \mathbb{F}$ là một trường bất kỳ, và cho $\displaystyle P\left(x_{1}, \ldots, x_{n}\right)$ là một đa thức trong $\displaystyle \mathbb{F}\left[x_{1}, \ldots, x_{n}\right]$ . Giả sử bậc của $\displaystyle P$ là $\displaystyle \sum_{i=1}^{n} k_{i}$ , trong đó $\displaystyle k_{i}$ là một số nguyên không âm, và hệ số của đơn thức $\displaystyle x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ trong $\displaystyle P$ khác không. Khi đó với mỗi tập con $\displaystyle A_{1}, \ldots, A_{n}$ của $\displaystyle \mathbb{F}$ thỏa mãn $\displaystyle \left|A_{i}\right| \geq k_{i}+1$ với mỗi $\displaystyle i=1,2, \ldots, n$ , tồn tại $\displaystyle a_{1} \in A_{1}, \ldots, a_{n} \in A_{n}$ để $\displaystyle P\left(a_{1}, \ldots, a_{n}\right) \neq 0$ .

Định lý trên được gọi là định lý không điểm tổ hợp, nó là một tổng quát của kết quả: Với mỗi đa thức khác không $\displaystyle f(x)$ với hệ số thuộc một trường $\displaystyle \mathbb F$ , số nghiệm của $\displaystyle f$ trong $\displaystyle \mathbb F$ không vượt quá $\displaystyle \deg f$ .

Chứng minh (Mateusz Michalek). Khẳng định là đúng một cách hiển nhiên khi $\displaystyle P$ là đa thức hằng, bây giờ ta xét trường hợp còn lại.

Quy nạp theo $\displaystyle \deg P$ . Nếu $\displaystyle \deg(P)=1$ thì định lý là đúng. Giả sử $\displaystyle \deg(P)>1$ và $\displaystyle P$ thỏa mãn các giả thiết của định lý nhưng kết luận là sai. Nghĩa là $\displaystyle P(x)=0$ với mọi $\displaystyle x \in A_{1} \times \ldots \times A_{n}$ . Không mất tính tổng quát, giả sử $\displaystyle k_{1}>0$ . Xét một $\displaystyle a \in A_{1}$ và viết

$\displaystyle P=\left(x_{1}-a\right) Q+R\quad \quad (1)$

bằng cách sử dụng thuật toán chia. Xem (1) là một đẳng thức của các đa thức một biến $\displaystyle x_{1}$ với hệ số thuộc $\displaystyle \mathbb{F}\left[x_{2}, \ldots, x_{n}\right]$ . Vì bậc của $\displaystyle R$ theo biến $\displaystyle x_{1}$ là bé hơn $\displaystyle \deg\left(x_{1}-a\right)$ , đa thức $\displaystyle R$ không chứa $\displaystyle x_{1}$ . Từ giả thiết về $\displaystyle P$ ta có $\displaystyle Q$ phải có một đơn thức không bị triệt tiêu có dạng $\displaystyle x_{1}^{k_{1}-1} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ và

$\displaystyle \deg(Q)=\sum_{i=1}^{n} k_{i}-1=\deg(P)-1.$

Lấy mỗi $\displaystyle x \in\{a\} \times A_{2} \times \ldots \times A_{n}$ và thay vào (1). Vì $\displaystyle P(x)=0$ ta có $\displaystyle R(x)=0$ . Nhưng $\displaystyle R$ không chứa $\displaystyle x_{1}$ , suy ra $\displaystyle R$ cũng bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ .

Bây giờ thay mỗi $\displaystyle x \in\left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ vào (1). Vì $\displaystyle x_{1}-a$ khác không, ta có $\displaystyle Q(x)=0$ . Vậy là $\displaystyle Q$ bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ , trái với giả thiết quy nạp. $\Box$

Một áp dụng đầu tiên là chứng minh ngắn của định lý Cauchy – Davenport trong lý thuyết số cộng tính. Định lý được chứng minh đầu tiên bởi Cauchy vào năm 1813 và bởi Davenport vào năm 1935. Cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Hỏi tập

$\displaystyle A+B:=\{a+b\mid (a,b)\in A\times B\}$

có thể có ít nhất bao nhiêu phần tử?

Định lý 2 (Cauchy – Davenport). Cho số nguyên tố $\displaystyle p$ và cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Khi đó

$\displaystyle |A+B|\geq\min \{p,a+b-1\}.$

Chứng minh. Nếu $\displaystyle a+b>p$ thì $\displaystyle \mid A+B\mid =p$ . Thật vậy, với mỗi $\displaystyle g\in \mathbb{Z}/{p}\mathbb{Z}$ , hai tập $\displaystyle g-A$ và $\displaystyle B$ có giao khác rỗng vì $\displaystyle a+b>p$ . Lấy $\displaystyle h\in (g-A)\cap B$ ta có ngay $\displaystyle h=b=g-a\quad (a\in A,b\in B),$ suy ra $\displaystyle g=a+b\in A+B$ . Từ đây ta có $\displaystyle |A+B|=p=\min \{p,a+b-1\}.$

Bây giờ ta xét $\displaystyle a+b\leq p$ và giả sử bất đẳng thức là sai. Gọi $\displaystyle C$ là một tập có cỡ $\displaystyle a+b-2$ trong $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ chứa $\displaystyle A+B$ . Xét đa thức

$\displaystyle f(x, y)=\prod_{c \in C}(x+y-c)$

trên $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ . Đây là một đa thức hai biến có bậc $\displaystyle a+b-2$ . Ta sẽ chứng minh

$\displaystyle \left[x^{a-1} y^{b-1}\right] f(x, y)=\left(\begin{array}{c}a+b-2 \\ a-1\end{array}\right) \not =0.$

Để hình thành hệ số này khi khai triển $\displaystyle f$ , ta chọn $\displaystyle x$ đúng $\displaystyle a-1$ lần và $\displaystyle y$ đúng $\displaystyle b-1$ lần trong $\displaystyle a+b-2$ thừa số. Như vậy ta có đẳng thức đầu. Hệ số nhị thức khác không là vì $\displaystyle a+b-2<p$ và $\displaystyle p$ là số nguyên tố.

Vì $\displaystyle |A|=a$ và $\displaystyle |B|=b$ , định lý không điểm tổ hợp cho ta $\displaystyle x \in A$ và $\displaystyle y \in B$ mà $\displaystyle f(x, y) \neq 0$ . Điều này không thể xảy ra vì $\displaystyle f$ đã được dựng để triệt tiêu trên mọi cặp $\displaystyle (x, y)$ như vậy. $\Box$

Bài đọc thêm

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

Seven bridges of Konigsberg

Tôi sẽ dịch một đoạn trong bài Leonard Euler’s Solution to the Konigsberg Bridge Problem của Teo Paoletti. Khi tình cờ gặp bài viết này tôi đã quyết định sử dụng nó làm bài mở đầu trong bài giảng về lý thuyết đồ thị của tôi.

Câu chuyện của chúng ta bắt đầu vào thế kỷ 18, tại thị trấn cổ kính Konigsberg, Phổ, bên bờ sông Pregel. Năm 1254, các hiệp sĩ Teutonic thành lập thành phố Konigsberg dưới sự lãnh đạo của Vua Bohemian Ottoker II sau cuộc thập tự chinh thứ hai chống lại quân Phổ. Vào thời Trung cổ, Konigsberg đã trở thành một thành phố và trung tâm thương mại rất quan trọng với vị trí chiến lược bên sông. Các tác phẩm nghệ thuật từ thế kỷ 18 cho thấy Konigsberg là một thành phố thịnh vượng, nơi các đội tàu cập bến Pregel, và hoạt động buôn bán của họ mang lại cuộc sống thoải mái cho cả thương nhân địa phương và gia đình họ. Nền kinh tế phát triển cho phép người dân thành phố xây dựng bảy cây cầu bắc qua sông, hầu hết trong số đó nối với đảo Kneiphof, vị trí của chúng có thể được thấy trong hình dưới đây.

Khi dòng sông chảy quanh Kneiphof và một hòn đảo khác, nó chia thành phố thành bốn vùng độc lập. Theo truyền thuyết, người dân Konigsberg thường dành những buổi chiều Chủ nhật để đi dạo quanh thành phố xinh đẹp của họ. Trong khi đi bộ, người dân thành phố quyết định tạo ra một trò chơi cho chính họ. Mục tiêu là nghĩ ra cách để có thể đi bộ quanh thành phố mà chỉ băng qua mỗi cây cầu đúng một lần. Mặc dù không ai ở Konigsberg có thể phát hiện ra một tuyến đường như vậy, nhưng họ vẫn không thể chứng minh được rằng điều đó là không thể. May mắn cho họ, Konigsberg không quá xa St. Petersburg, quê hương của nhà toán học nổi tiếng Leonard Euler.

Tại sao Euler lại quan tâm đến một vấn đề không liên quan đến lĩnh vực toán học như vậy? Tại sao một nhà toán học vĩ đại như vậy lại dành nhiều thời gian cho một bài toán tầm thường như bài toán cây cầu Konigsberg? Euler rõ ràng là một người bận rộn, đã xuất bản hơn 500 cuốn sách và bài báo trong suốt cuộc đời của mình. Riêng năm 1775, trung bình mỗi tuần ông viết một bài báo toán học, và trong suốt cuộc đời mình, ông viết về nhiều chủ đề khác nhau ngoài toán học bao gồm cơ học, quang học, thiên văn học, hàng hải và thủy động lực học. Không có gì đáng ngạc nhiên khi Euler cảm thấy vấn đề này thật tầm thường, ông viết trong một bức thư năm 1736 gửi cho Carl Leonhard Gottlieb Ehler, thị trưởng của Danzig, người đã nhờ ông đưa ra lời giải cho bài toán:

“…Vì vậy, thưa ngài, ngài thấy đấy, bài toán này ít liên quan đến toán học như thế nào, và tôi không hiểu tại sao ngài lại mong đợi một nhà toán học tìm ra nó chứ không phải bất kỳ ai khác, vì lời giải chỉ dựa trên lý trí và khám phá ra nó. Không phụ thuộc vào bất kỳ nguyên tắc toán học nào. Vì điều này, tôi không biết tại sao ngay cả những câu hỏi ít liên quan đến toán học cũng được các nhà toán học giải nhanh hơn những người khác.”

Mặc dù Euler thấy vấn đề tầm thường nhưng ông vẫn bị hấp dẫn bởi nó. Trong một bức thư viết cùng năm cho Giovanni Marinoni, một nhà toán học và kỹ sư người Ý, Euler nói:

“Câu hỏi này thật tầm thường, nhưng đối với tôi, dường như nó đáng được chú ý bởi cả hình học, đại số, thậm chí cả nghệ thuật đếm cũng không đủ để giải quyết nó.”

Euler tin rằng vấn đề này có liên quan đến một chủ đề mà Gottfried Wilhelm Leibniz đã từng thảo luận và mong muốn được làm việc cùng, chủ đề mà Leibniz gọi là geometria situs, hay hình học vị trí. Cái gọi là hình học vị trí này là cái ngày nay ta gọi là lý thuyết đồ thị.

Continue reading →

Làm thế nào để cải thiện trực giác Toán học?

Trực giác Toán học có thể được hiểu là khả năng nhận ra các mẫu hình, mối liên hệ, hoặc cách tiếp cận một bài toán mà không cần dựa hoàn toàn vào các bước suy luận logic chi tiết. Trực giác này giống như một “cảm giác” về Toán học, cho phép người học dự đoán, hình dung, và đưa ra giả thuyết một cách tự nhiên. Trực giác Toán học không phải là một “phép màu” hay sự đoán mò. Nó được xây dựng dựa trên kinh nghiệm, sự quen thuộc với các khái niệm Toán học, và khả năng liên kết các ý tưởng. Nhà Toán học nổi tiếng Henri Poincaré từng mô tả trực giác như một công cụ giúp ông khám phá các ý tưởng mới, nhưng chỉ khi kết hợp với tư duy logic thì trực giác mới trở thành nền tảng cho những khám phá lớn.

Để cải thiện trực giác Toán học, bạn cần rèn luyện khả năng nhận diện các cấu hình, hiểu sâu các khái niệm và áp dụng chúng một cách linh hoạt. Dưới đây là một số kinh nghiệm hữu ích:

1. Thay vì chỉ học thuộc khái niệm hay định lý, hãy tìm hiểu tại sao chúng hoạt động. Đọc các chứng minh khác nhau khi học định lý, cố gắng nắm rõ ý tưởng chứng minh. Ngoài ra, có thể tự hỏi: Khái niệm này đến từ đâu? Ý nghĩa của kết quả này là gì? Nếu thay đổi hay bỏ bớt điều kiện, kết quả sẽ ra sao? Nó còn đúng không? Việc tìm câu trả lời sẽ kích thích tư duy trực giác và khả năng liên kết.

2. Giải nhiều bài toán ở các mức độ khác nhau, kể cả các bài toán mở. Các bài toán hình học, đại số, hay tổ hợp thường giúp phát triển trực giác nhờ tính trực quan. Những bài toán mở khuyến khích bạn suy nghĩ sáng tạo và hình dung cách giải quyết vấn đề.

3. Vẽ hình, biểu đồ, hoặc sơ đồ để minh họa bài toán. Chúng giúp bạn “thấy” được các mối liên hệ. Sử dụng các công cụ như GeoGebra hoặc giấy và bút để thử nghiệm các ý tưởng.

4. Thử giải bài toán theo nhiều cách khác nhau. Ví dụ, một bài toán hình học có thể được giải bằng đại số, lượng giác, hoặc hình học thuần túy. Điều này giúp bạn phát triển sự linh hoạt và nhận ra các mẫu ẩn. Khi gặp bài toán khó, hãy cố gắng chia nhỏ hoặc giải các bài toán đơn giản hơn.

5. Khi giải sai hay không giải được một bài toán, hãy dừng lại và phân tích lý do. Hỏi bản thân: “Mình đã bỏ qua điều gì?” hoặc “Có tính chất nào mình chưa nhận ra không?” Đây là cơ hội để phát triển trực giác, vì chúng chỉ ra những điểm mù trong tư duy.

6. Đọc và học từ các nguồn chất lượng. Đọc sách, xem video bài giảng hoặc bài viết của các nhà Toán học nổi tiếng để hiểu cách họ tiếp cận vấn đề. Các cuốn sách như “How to Solve It” của George Polya hoặc “The Art and Craft of Problem Solving” của Paul Zeitz rất hữu ích.

7. Hãy học hỏi từ những người khác ngoài thầy trực tiếp dạy bạn. Tham gia các nhóm học Toán hoặc diễn đàn như Art of Problem Solving. Thảo luận với người khác giúp tiếp cận các cách suy nghĩ mới và củng cố trực giác của mình. Dạy lại khái niệm cho người khác. Khi bạn giải thích một ý tưởng Toán học, bạn buộc phải hiểu nó sâu hơn, từ đó cải thiện trực giác.

Trực giác Toán học cần phải được rèn luyện thường xuyên, bạn nên dành thời gian mỗi ngày để giải một bài toán nhỏ hoặc suy nghĩ về một khái niệm mới. Trực giác Toán học không phát triển ngay lập tức, nó đòi hỏi thời gian và sự kiên trì. Hãy coi mỗi bài toán là một cơ hội để học hỏi, ngay cả khi bạn chưa tìm ra lời giải.

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có