מערכת שטיינר

מערכת שטיינר עם פרמטרים $t,k,n$ היא מבנה קומבינטורי סימטרי הכולל תת-קבוצות בגודל $k$ , הקרויות בלוקים, של קבוצה בגודל $n$ , באופן שכל $t$ נקודות מוכלות בבלוק יחיד. מערכת כזו נקראת $S(t,k,n)$ . ^[1]. מערכות כאלה קרויות על שם המתמטיקאי השווייצרי יאקוב שטיינר שחי במאה התשע עשרה.

כל גאומטריה סופית (אפינית או פרויקטיבית) היא מערכת שטיינר, שבה הבלוקים הם ישרים, וכל $t=2$ נקודות מוכלות בישר יחיד. ההכללה שבה כל קבוצה בגודל $t$ מוכלת במספר קבוע של בלוקים (ולאו דווקא בבלוק יחיד) נקראת "תכנון בלוקים" (בסימון זה, מערכת שטיינר היא תכנון $t-(k,n,1)$ ).

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

אם זורקים נקודה ממערכת קיימת $S(t,k,n)$ ושומרים רק את הבלוקים שעברו דרכה, מתקבלת מערכת $S(t-1,k-1,n-1)$ . הכיוון ההפוך (הוספת נקודה למערכת קיימת) בדרך כלל בלתי אפשרי. קל להראות שבמערכת שטיינר $S(t,k,n)$ יש $b={\frac {\binom {n}{t}}{\binom {k}{t}}}$ בלוקים בסך-הכל, ושדרך כל נקודה עוברים $r={\frac {\binom {n-1}{t-1}}{\binom {k-1}{t-1}}}$ בלוקים; אם המערכת קיימת, המספרים האלו חייבים כמובן להיות שלמים, והם מקיימים $bk=rn$ . בעיית הקיום של מערכת שטיינר $S(2,6,36)$ היתה ידועה בשם בעיית הקצינים של אוילר; למרות שהשלשה (2,6,36) מקיימת את תנאי הקיום האריתמטי, מערכת כזו אינה קיימת (G. Tarry, 1900). משפט הקיום של וילסון (Richard Wilson) קובע שעבור פרמטרים גדולים מספיק, לכל שלשה המקיימת את תנאי ההתחלקות קיימות מערכות שטיינר מתאימות [1].

בגאומטריה האפינית המישורית מעל השדה הסופי $\mathbb {F} _{q}$ יש $q^{2}$ נקודות, שדרך כל שתיים מהן עובר ישר יחיד, עליו $q$ נקודות. לכן אוסף הישרים מהווה מערכת שטיינר $S(2,q,q^{2})$ . בדומה לזה, קבוצת הישרים במישור הפרויקטיבי מעל אותו שדה היא מערכת שטיינר $S(2,q+1,q^{2}+q+1)$ . קבוצת המישורים במרחב האפיני ה- $n$ -ממדי $\mathbb {F} _{2}^{n}$ היא מערכת שטיינר $S(3,4,2^{n})$ (משום שדרך כל שלוש נקודות $x,y,z$ עובר מישור יחיד, $\{x,y,z,x+y+z\}$ ).

מערכת שטיינר עם הפרמטרים $t=2$ ו- $k=3$ נקראת מערכת שטיינר משולשת. קיימת מערכת כזו על $n$ נקודות אם ורק אם $n\equiv 1,3{\pmod {6}}$ . מערכת שטיינר המשולשת היחידה בגודל n=7 היא מישור פאנו. מערכת שטיינר המשולשת היחידה בגודל n=9 היא המישור האפיני מעל השדה מסדר 3. מערכת שטיינר משולשת שבה כל שתי שלשות נחתכות מוכלות בתת-מערכת בגודל 9 נקראת מערכת הול משולשת.