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

בתורת המספרים האדיטיבית, משפטי שנירלמן עוסקים בצפיפות של קבוצות מספרים טבעיים ובתכונות של הסכום שלהן. הסימון δ מייצג את צפיפות שנירלמן של קבוצה. כאן משתמשים בתכונה שמתקיימת לכל n: |A(n)|/n ≥ δ(A).

יהיו A,B קבוצות של מספרים טבעיים. אזי:
1) δ(A+B) ≥ δ(A) + δ(B) − δ(A)δ(B). (δ היא צפיפות שנירלמן)
2) אם |A(n)| + |B(n)| > n−1 אז n שייך ל־A+B. בהנחה ש־0 שייך ל־A ו־B.
3) אם δ(A)+δ(B) ≥ 1 אז A+B = N (כל המספרים הטבעיים). גם כאן מניחים 0∈A,B.

בודקים שתי אפשרויות. אם לכל קבוצה יש לכל היותר איבר אחד, הצפיפות שלהן היא אפס והאי־שוויון טריוויאלי.
אם אחת הקבוצות, נניח A, מכילה יותר מאיבר אחד, מסדרים את האיברים שלה כ־a1,a2,… ומשתמשים ברווחים ביניהם. נסמן L_k = a_{k+1} − a_k − 1, כך שהמספרים שבין a_k ל־a_{k+1} לא שייכים ל־A.
עבור כל רווח כזה, האיברים a_k + B(L_k) (כלומר סכום a_k עם איברים של B עד גודל L_k) כלולים ב־A+B. סכום כל האורכים L_k עד n מחזיר את n − |A(n)|.
בעזרת הערך המינימלי של |B(L_k)| ≥ δ(B)·L_k ומכפלת המדידות מקבלים ש־|(A+B)(n)| ≥ |A(n)| + δ(B)(n − |A(n)|).
לחלק ב־n ולתת n גדל מביא לאי־השוויון המבוקש: δ(A+B) ≥ δ(A)+δ(B) − δ(A)δ(B).

אם n שייך ל־A או ל־B אז ברור ש־n∈A+B כי 0∈האחרת. לכן נבחן את המקרה שבו n אינו שייך לאף אחת.
נסמן r=|A(n−1)| ו־s=|B(n−1)|. התנאי r+s>n−1 אומר שיש יותר מ־n−1 מספרים בין 1 ל־n−1 בחיבור של שתי הקבוצות הללו. לפי עקרון היונה (pigeonhole) חייב להיות חפיפה: יש a_i ו־b_j כך ש־a_i = n − b_j, כלומר a_i + b_j = n. כך n∈A+B.

מכיוון שלכל n מתקיים |A(n)|/n ≥ δ(A) ו|B(n)|/n ≥ δ(B), סכום השברים גדול או שווה ל־δ(A)+δ(B) ≥ 1.
מכאן |A(n)|+|B(n)| ≥ n, ולכן לפי משפט שני כל n נמצא ב־A+B. כך A+B שווה לכל המספרים הטבעיים.

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

1) הצפיפות של A+B גדולה לפחות כמו סכום הצפיפויות של A ו־B פחות המכפלה שלהן.
2) אם ביחד יש יותר מ־n−1 איברים עד n אז המספר n ניתן לכתיבה כסכום של איבר מ־A ואיבר מ־B. מניחים ש־0 בקבוצות.
3) אם הצפיפות של A ועוד הצפיפות של B שווה או גדולה מאחד, אז כל מספר טבעי הוא סכום מאיברים של A ו־B.

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

אם n כבר שייך ל־A או ל־B אז ברור שהוא ב־A+B. אם לא, מסתכלים על כל המספרים עד n−1 שבשתי הקבוצות. אם יש יותר מ־n−1 מספרים, חייבים להיות שני מספרים שיחסרו זה לזה ביחס ל־n. זה אומר שאחד ועוד השני שווים ל־n.

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