הצגת המקור של הדף "רצף סידון"

ב[[תורת המספרים]], '''רצף סידון''' (או אשכול סידון), הקרוי על שמו של ה[[מתמטיקאי]] ה[[יהדות הונגריה|הונגרי-יהודי]] [[שמעון סידון]], הוא רצף סופי או אינסופי <math>A=\{a_0,a_1,a_2,\dots\}</math> של [[מספר טבעי|מספרים טבעיים]], בו כל הסכומים <math>a_i+a_j \ (i \leq j)</math> שונים אחד מהשני.

סידון הציג את המושג בחקירותיו על [[טור פורייה|טורי פורייה]].

== דוגמה ==
המספרים <math>\{1, 2, 5, 7\}</math> יוצרים רצף סידון ועל פי ההשערה שטרם הוכחה, גם רצף המספרים הטבעיים בחזקה החמישית <math>\{0, 1, 32, 243, \dots\}</math> יוצרים רצף סידון.

== היחס לסרגל גולומב ==
[[סרגל גולומב]] הוא קבוצת מספרים שלמים, כך שלכל זוג מהם הפרש ייחודי.

כל סרגל גולומב סופי הוא רצף סידון סופי, ולהפך, כל רצף סידון סופי הוא סרגל גולומב.

'''הוכחה''': [[הוכחה בדרך השלילה|נניח בשלילה]] ש-<math>S</math> הוא רצף סידון סופי, אך לא סרגל גולומב.

מכיוון שהוא לא סרגל גולומב נובע שקיימים ארבעה איברים ברצף כך ש-<math>a_i-a_j=a_k-a_l</math>, ולאחר העברת אגפים מתקבל <math>a_i+a_l=a_k+a_j</math>. בסתירה לכך ש-<math>S</math> הוא רצף סידון.

לכן, כל רצף סידון סופי הוא סרגל גולומב.

בנימוק דומה ניתן להוכיח שכל סרגל גולומב סופי הוא רצף סידון סופי.

== אורך רצף צידון סופי ==
[[פאול ארדש]] ו[[פאל טוראן]] העלו את השאלה כמה איברים קטנים מ-<math>X</math> יכולים להיות ברצף סידון.<ref>{{Citation|first1=P.|last1=Erdős|author1-link=פאול ארדש|first2=P.|last2=Turán|author2-link=פאל טוראן|title=On a problem of Sidon in additive number theory and on some related problems|journal=J. London Math. Soc.|volume=16|year=1941|pages=212–215|doi=10.1112/jlms/s1-16.4.212|url=http://www.renyi.hu/~p_erdos/1941-01.pdf}}. [http://www.math-inst.hu/~p_erdos/1944-02.pdf Addendum] {{Webarchive|url=https://web.archive.org/web/20110718065345/http://www.math-inst.hu/~p_erdos/1944-02.pdf |date=2011-07-18 }} {{ארכיון האינטרנט}}, '''19''' (1944), 208.</ref>

למרות שרבים עסקו בשאלה זו, השאלה עדיין פתוחה גם בימינו.<ref>{{citation|first=K.|last=O'Bryant|url=http://www.emis.ams.org/journals/EJC/Surveys/ds11.pdf|title=A complete annotated bibliography of work related to Sidon sequences|journal=Electronic Journal of Combinatorics|volume=11|year=2004|page=39|accessdate=2020-05-27|archiveurl=https://web.archive.org/web/20110606025154/http://www.emis.ams.org/journals/EJC/Surveys/ds11.pdf|archivedate=2011-06-06|url-status=dead}}.</ref>

ארדש וטוראן הוכיחו שכמות האיברים ב-''<math>A</math>'' שקטנים מ-<math>x</math> (המסומן ''<math>A(x)</math>''), הוא לכל היותר <math>\sqrt{x}+O(\sqrt[4]{x})</math>.

== רצף סידון אינסופי ==
לעומת זאת, אם ''<math>A</math>'' הוא רצף אינסופי של רצף סידון ו-<math>A(x)</math> מציין את כמות האיברים ב-''<math>A</math>'' שקטנים מ-<math>x</math>, אז לפי התוצאות של פאול ארדש:

<math>\liminf \frac{A(x)\sqrt{\log x}}{\sqrt{x}}\leq 1</math>

כלומר, רצפים אינסופיים דלילים יותר מהרצפים הסופיים הצפופים ביותר.

בכיוון השני הראו ס. צ'ולה ומיאן שניתן ליצור רצף סידון אינסופי עם [[אלגוריתם חמדן]], שעבורו

<math>A(x)>c\sqrt[3]{x}</math> לכל ''<math>x</math>.''

מיקלוש אייטאי ואנדרה סמרדי שיפרו תוצאה זו ל:<ref>{{Citation|first1=M.|last1=Ajtai|author1-link=Ajtai Miklós (matematikus)|first2=J.|last2=Komlós|author2-link=Komlós János (matematikus)|first3=E.|last3=Szemerédi|author3-link=Szemerédi Endre|title=A dense infinite Sidon sequence|journal=European Journal of Combinatorics|volume=2|year=1981|pages=1–11|id=|issue=1}}.</ref>

<math>A(x)>\sqrt[3]{x\log x}</math>.

החסם התחתון הטוב ביותר הידוע כיום ניתן על ידי אימרה רוז'ה,<ref>{{Citation|first=I. Z.|last=Ruzsa|author-link=Ruzsa Z. Imre|title=An infinite Sidon sequence|journal=Journal of Number Theory|volume=68|year=1998|pages=63–71|id=|doi=10.1006/jnth.1997.2192}}.</ref> שהראה שיש רצף סידון שעבורו:

<math>A(x)>x^{\sqrt{2}-1-o(1)}</math>.

פאול ארדש ו[[אלפרד רניי]] הוכיחו<ref>{{Citation|first1=P.|last1=Erdős|author1-link=Erdős Pál|first2=A.|last2=Rényi|author2-link=Rényi Alfréd|title=Additive properties of random sequences of positive integers|journal=Acta Arithmetica|volume=6|year=1960|pages=83–110|id=|url=http://www.renyi.hu/~p_erdos/1960-02.pdf}}.</ref> שיש רצף אינסופי <math>a_0,a_1,\dots</math> שבו לכל <math>n</math> טבעי יש לכל היותר <math>C</math> פתרונות למשוואה <math>a_i+a_j=n</math>.

== ראו גם==
* [[:en:Moser–de_Bruijn_sequence|Moser–de Bruijn sequence]]
*[[:en:Sumset|Sumset]]

==קישורים חיצוניים==
* {{MathWorld}}

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:תורת המספרים]]
[[קטגוריה:בעיות פתוחות בתורת המספרים]]