1221876
Dãy Sidon
https://vi.wikipedia.org/wiki?curid=1221876
Title: 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"0, "a"1, "a"2, ...} 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à formula_1 và bằng một ví dụ xây dựng bởi J. Singer, họ thu được chặn dưới formula_2.
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
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ó formula_4 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
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ó