משפטי שנירלמן

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

ניסוח המשפטים

יהו $A,B$ קבוצות מספרים המוכלות בקבוצת המספרים הטבעיים, אזי:

1. $\delta (A+B)\geq \delta (A)+\delta (B)-\delta (A)\delta (B)$ , כאשר $\delta$ צפיפות שנירלמן.
2. אם $|A(n)|+|B(n)|>n-1$ אזי $n\in A+B$ .
3. אם $\delta (A)+\delta (B)\geq 1$ אזי $A+B=\mathbb {N}$ .

במשפט השני והשלישי אנחנו מניחים כי $0\in A,B$ .

הוכחת המשפטים

המשפט הראשון

נבדוק שני מקרים: מקרה ראשון כאשר $A,B$ מכילים לכל היותר איבר אחד, ומקרה שני כאשר לפחות אחד מהקבוצות $A,B$ מכילות יותר מאיבר אחד. בהינתן שמתקיים המקרה הראשון אי-השוויון הוא טריוויאלי, שכן במקרה זה $\delta (A)=\delta (B)=0$ ודי ברור כי $\delta (A+B)\geq 0=\delta (A)+\delta (B)-\delta (A)\delta (B)$ . עכשיו נותר להוכיח את המשפט למקרה השני.

נניח ללא הגבלת הכלליות כי $|A|>1$ , נסדר את איברי $A$ לפי הסדר הרגיל של המספרים הטבעיים:

$A=\{a_{1},a_{2},\ldots \}$

כאשר $a_{n}<a_{n+1}$ לכל $n$ . יהיו $a_{k},a_{k+1}\in A$ , אז לפי סידור איברי הקבוצה $a_{k}<a_{k+1}$ . נגדיר $a_{k+1}-a_{k}-1=L_{k}$ .

ברור שהמספרים $a_{k}+1,\ldots ,a_{k}+L_{k}=a_{k+1}-1$ לא שייכים לקבוצה $A$ . כמו כן המספר $a_{k}+r\in A+B$ אם ורק אם $r\in B,1<r<L_{k}$ , לכן $r\in B(L_{k})$ .

לכן הקבוצה $a_{k}+B(L_{k})\subseteq A+B$ . לכן גם האיחוד $\bigcup _{k=1}^{n-1}{\bigl (}a_{k}+B(L_{k}){\bigr )}\subseteq A+B$ שזה הקבוצה $A(n)+\sum _{k=1}^{n-1}B(L_{k})$

מכאן נובע כי ${\bigl |}A(n){\bigr |}+{\bigg |}\sum _{k=1}^{n-1}B(L_{k}){\bigg |}\leq {\bigl |}(A+B)(n){\bigr |}$ לפי הגדרת הצפיפות ${\bigl |}B(L_{k}){\bigr |}\geq \delta (B)\cdot L_{k}$ וגם ${\bigl |}A(n){\bigr |}\geq \delta (A)\cdot n$ , ומובן כי $\sum _{k=1}^{n-1}L_{k}=n-A(n)$ (כי המקומות שבהם אין איבר מ-$A$ הוא סכום כל האיברים הנמצאים בין $a_{k},a_{k+1}$)

לכן

${\begin{aligned}\delta (A)\!\cdot \!n+\delta (B)\!\cdot \!n-\delta (A)\delta (B)\!\cdot \!n&\leq {\bigl |}A(n){\bigr |}+\delta (B){\bigl (}n-\delta (A)\!\cdot \!n{\bigr )}={\bigl |}A(n){\bigr |}+\delta (B)\sum _{k=1}^{n-1}L_{k}\\&\leq {\bigl |}A(n){\bigr |}+\sum _{k=1}^{n-1}{\bigl |}B(L_{k}){\bigr |}\leq {\bigl |}(A+B)(n){\bigr |}\end{aligned}}$

לכן לכל $n$ מתקיים ${\frac {{\bigl |}(A+B)(n){\bigr |}}{n}}\geq \delta (A)+\delta (B)-\delta (A)\delta (B)$ . בהכרח מתקיים $\delta (A+B)\geq \delta (A)+\delta (B)-\delta (A)\delta (B)$ .

משפט שני

נניח כי $n\in A$. ידוע כי $0\in B$ ולכן $n=n+0\in A+B$ (באותו אופן המשפט נכון כאשר $n\in B$). לכן אם נוכיח את הטענה ל $n\notin B,A$ נוכיח את המשפט.

כאשר $n\notin B,A$ מתקיים $A(n)=A(n-1),B(n)=B(n-1)$ ונקבל $A(n-1)+B(n-1)>n-1$ . נגדיר ${\bigl |}A(n-1){\bigr |}=r,{\bigl |}B(n-1){\bigr |}=s$ כלומר $r+s>n-1$ . לכן אם יש $r+s$ מספרים כאשר כל המספרים הם בין $1,n-1$ אז יש לפחות מספר אחד שמופיע פעמיים.

לכן בהכרח שניים מהמספרים $a_{1},\ldots ,a_{r},n-b_{1},\ldots ,n-b_{s}$ מתלכדים. כלומר ישנם $i,j$ עבורם $a_{i}=n-b_{j}$ כלומר $a_{i}+b_{j}=n\in A+B$

משפט שלישי

לפי הגדרת הצפיפות לכל $n$ מתקיים ${\frac {{\bigl |}A(n){\bigr |}}{n}}\geq \delta (A),{\frac {{\bigl |}B(n){\bigr |}}{n}}\geq \delta (B)$ . לכן ${\frac {{\bigl |}A(n){\bigr |}}{n}}+{\frac {{\bigl |}B(n){\bigr |}}{n}}\geq \delta (A)+\delta (B)\geq 1$ כלומר ${\bigl |}A(n){\bigr |}+{\bigl |}B(n){\bigr |}\geq n>n-1$ .

לכן לפי משפט 2 כל $n\in A+B$ ולכן $A+B=\mathbb {N}$ .

ראו גם

• צפיפות שנירלמן