רצף סידון

בתורת המספרים, רצף סידון (או אשכול סידון), הקרוי על שמו של המתמטיקאי ההונגרי-יהודי שמעון סידון, הוא רצף סופי או אינסופי $A=\{a_0,a_1,a_2,\dots \}$ של מספרים טבעיים, בו כל הסכומים $$\begin{gathered} a_i+a_j \\ (i\le j) \end{gathered}$$ שונים אחד מהשני.

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

דוגמה

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

היחס לסרגל גולומב

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

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

הוכחה: נניח בשלילה ש-$S$ הוא רצף סידון סופי, אך לא סרגל גולומב.

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

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

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

אורך רצף צידון סופי

פאול ארדש ופאל טוראן העלו את השאלה כמה איברים קטנים מ-$X$ יכולים להיות ברצף סידון.

למרות שרבים עסקו בשאלה זו, השאלה עדיין פתוחה גם בימינו.

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

רצף סידון אינסופי

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

$\mathrm{lim\; inf}\frac{A(x)\sqrt{\log x}}{\sqrt{x}}\le 1$

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

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

$A(x)>c\sqrt[3]{x}$ לכל $x$.

מיקלוש אייטאי ואנדרה סמרדי שיפרו תוצאה זו ל:

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

החסם התחתון הטוב ביותר הידוע כיום ניתן על ידי אימרה רוז'ה, שהראה שיש רצף סידון שעבורו:

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

פאול ארדש ואלפרד רניי הוכיחו שיש רצף אינסופי $a_0,a_1,\dots$ שבו לכל $n$ טבעי יש לכל היותר $C$ פתרונות למשוואה $a_i+a_j=n$.

ראו גם

• Moser–de Bruijn sequence
• Sumset

קישורים חיצוניים

• .html רצף סידון, באתר MathWorld (באנגלית)