Dãy Sidon

Trong lý thuyết số, một dãy Sidon (hay tập hợp Sidon), đặt theo tên của nhà toán học Hungary Simon Sidon, là một dãy các số tự nhiên A = {a₀, a₁, a₂, ...} sao cho các tổng của hai số bất kì trong dãy a_i + a_j (i ≤ j) đôi một khác nhau. Sidon đưa ra khái niệm này trong nghiên cứu của ông về chuỗi Fourier. Tổng quát hơn, một dãy g-Sidon là một dãy số tự nhiên sao cho một số tự nhiên bất kì có không quá g cách biểu diễn dưới dạng tổng hai số trong dãy.

Vấn đề chính, đặt ra bởi Sidon, là A chứa tối đa bao nhiêu phần tử nhỏ hơn hoặc bằng một giá trị x cho trước. Mặc dù đã có nhiều nghiên cứu về vấn đề này, câu hỏi cho trường hợp g tổng quát vẫn chưa được giải đáp sau gần 80 năm. Gần đây, lời giải cuối cùng đã được tìm ra bởi J. Cilleruelo, I. Ruzsa và C. Vinuesa.

Paul Erdős và Pál Turán chứng minh số phần tử của A không quá x nhiều nhất là ${\sqrt {x}}+O({\sqrt[{4}]{x}})$ và bằng một ví dụ xây dựng bởi J. Singer, họ thu được chặn dưới ${\sqrt {x}}(1-o(1))$.

Tuy nhiên, nếu ta xét dãy Sidon vô hạn A và đặt A(x) là số phần tử nhỏ hơn hoặc bằng x, thì Erdos chứng minh rằng

$\liminf {\frac {A(x){\sqrt {\log x}}}{\sqrt {x}}}\leq 1$

nghĩa là, dãy Sidon vô hạn có mật độ thấp hơn chặn thu được ở trên cho dãy hữu hạn.

Cho chặn ở phía còn lại, Chowla và Mian nhận thấy thuật toán tham lam xây dựng được một dãy Sidon vô hạn có $A(x)>c{\sqrt[{3}]{x}}$ với mọi x. Ajtai, Komlós, và Szemerédi xây dựng được một dãy Sidon tốt hơn với

$A(x)>{\sqrt[{3}]{x\log x}}.$

Chặn dưới tốt nhất hiện nay là của Imre Z. Ruzsa, chỉ ra rằng tồn tại dãy Sidon có

$A(x)>x^{{\sqrt {2}}-1-o(1)}$

Erdős giả thuyết rằng tồn tại tập hợp Sidon vô hạn A với $A(x)>x^{1/2-o(1)}$. Ông cùng với Rényi chứng minh rằng tồn tại dãy a₀,a₁,... với một tính chất yếu hơn là với mọi số tự nhiên n tồn tại không quá c lời giải cho phương trình a_i+a_j=n với c là một hằng số.

Erdős còn đưa ra một giả thuyết khác là tồn tại một đa thức với hệ số nguyên sao cho giá trị của đa thức ở các số tự nhiên tạo thành một dãy Sidon vô hạn. Cụ thể hơn, ông đưa ra câu hỏi liệu tập hợp các lũy thừa bậc 5 có là một tập hợp Sidon. Ruzsa đã chứng minh được rằng tồn tại số thực 0<c<1 sao cho tập giá trị của hàm f(x)=x⁵+[cx⁴] là một dãy Sidon, trong đó [.] ký hiệu hàm phần nguyên.

Liên hệ với thước Golomb

Mọi tập hợp Sidon hữu hạn đều là một thước Golomb và ngược lại.

Có thể chứng minh bằng phản chứng mệnh đề trên như sau. Giả sử S là một tập hợp Sidon và không là thước Golomb. Do nó không là thước Golomb, tồn tại 4 phần tử sao cho $a_{i}-a_{j}=a_{k}-a_{l}$. Do đó $a_{i}+a_{l}=a_{k}+a_{j}$, mâu thuẫn với giả thuyết S là một tập hợp Sidon. Vì vậy mọi tập hợp Sidon đều là một thước Golomb. Bằng một chứng minh tương tự, mọi thước Golomb đều là một tập hợp Sidon.

Xem thêm

• Tập hợp tổng