מערכת שטיינר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
מישור פאנו המגדיר מערכת S(2,3,7)

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

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

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

אם זורקים נקודה ממערכת קיימת \ 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.

בגאומטריה האפינית המישורית מעל השדה הסופי \ \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}.

חבורות הסימטריה של כמה מערכות שטיינר מיוחדות (הנוצרות מן המערכות \ S(5,6,12) או \ S(5,8,24)) הן חבורות פשוטות ספורדיות הקרויות חבורות מתיו.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ כדי למנוע מקרים טריוויאליים, מניחים \ 1<t<k<n.