نظام التغطية

في الرياضيات ، نظام التغطية (ويسمى أيضًا نظام البقايا الكامل ) هو مجموعة

${\displaystyle \{a_{1}{\pmod {n_{1}}},\ \ldots ,\ a_{k}{\pmod {n_{k}}}\}}$

من عدد محدود من فئات البقايا

${\displaystyle a_{i}{\pmod {n_{i}}}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \},}$

والتي يحتوي اتحادها على كل عدد صحيح.

تم تقديم مفهوم نظام التغطية من قبل بول إيردوس في أوائل الثلاثينيات.

فيما يلي أمثلة على أنظمة التغطية:

1. ${\displaystyle \{0{\pmod {3}},\ 1{\pmod {3}},\ 2{\pmod {3}}\},}$
2. ${\displaystyle \{1{\pmod {2}},\ 2{\pmod {4}},\ 4{\pmod {8}},\ 0{\pmod {8}}\},}$
3. ${\displaystyle \{0{\pmod {2}},\ 0{\pmod {3}},\ 1{\pmod {4}},\ 5{\pmod {6}},\ 7{\pmod {12}}\}.}$

يُطلق على نظام التغطية اسم نظام منفصل (أو نظام دقيق ) إذا لم يتداخل أي عنصرين فيه.

يُطلق على نظام التغطية اسم نظام متميز (أو غير متطابق ) إذا كانت جميع المعاملات${\displaystyle n_{i}}$تختلف (وأكبر من 1). أثبت هوف ونيلسن (2019) ^{[ 1 ]} أن أي نظام تغطية مميز له معامل قابل للقسمة إما على 2 أو 3.

يُطلق على نظام التغطية اسم نظام غير زائد (أو نظام الحد الأدنى ) إذا كانت جميع فئات البقايا مطلوبة لتغطية الأعداد الصحيحة.

المثالان الأولان منفصلان.

المثال الثالث متميز.

نظام (أي مجموعة متعددة غير مرتبة)

${\displaystyle \{a_{1}{\pmod {n_{1}}},\ \ldots ,\ a_{k}{\pmod {n_{k}}}\}}$

يُطلق على عدد محدود من فئات البقايا اسم${\displaystyle m}$- تغطية إذا كانت تغطي كل عدد صحيح على الأقل ${\displaystyle m}$الأوقات، وعدد دقيق${\displaystyle m}$- تغطية إذا كانت تغطي كل عدد صحيح تمامًا${\displaystyle m}$مرات. من المعروف أنه لكل ${\displaystyle m=2,3,\ldots }$هناك تحديداً${\displaystyle m}$- أغلفة لا يمكن كتابتها كاتحاد غلافين. على سبيل المثال،

${\displaystyle \{1{\pmod {2}};\ 0{\pmod {3}};\ 2{\pmod {6}};\ 0,4,6,8{\pmod {10}};}$

${\displaystyle 1,2,4,7,10,13{\pmod {15}};\ 5,11,12,22,23,29{\pmod {30}}\}}$

هو غلاف مزدوج متطابق، وليس اتحاد غلافين.

المثال الأول أعلاه هو غطاء دقيق من الدرجة 1 (يُسمى أيضًا غطاءً دقيقًا ). ومن الأغطية الدقيقة الأخرى الشائعة الاستخدام غطاء الأعداد الفردية والزوجية ، أو

${\displaystyle \{0{\pmod {2}},\ 1{\pmod {2}}\}.}$

هذه مجرد حالة واحدة من الحقيقة التالية: لكل عدد صحيح موجب معياري${\displaystyle m}$يوجد غلاف مطابق تمامًا:

${\displaystyle \{0{\pmod {m}},\ 1{\pmod {m}},\ \ldots ,\ {m-1}{\pmod {m}}\}.}$

تنص نظرية ميرسكي-نيومان، وهي حالة خاصة من حدسية هيرتسوغ-شونهايم ، على أنه لا يوجد نظام تغطية منفصل ومتميز. وقد افترض بول إيردوس هذه النتيجة عام 1950 ، وأثبتها ليون ميرسكي ودونالد ج . نيومان بعد ذلك بوقت قصير. مع ذلك، لم ينشر ميرسكي ونيومان برهانهما. كما توصل هارولد دافنبورت وريتشارد رادو بشكل مستقل إلى البرهان نفسه . ^{[ 2 ]} في عام 1970، كانت المسألة رقم 8 في أولمبياد الرياضيات السوفيتي للصف العاشر عبارة عن مسألة تلوين مضلعات مكافئة لنظرية ميرسكي-نيومان. ^{[ 3 ]}

يمكن استخدام أنظمة التغطية لإيجاد متواليات خالية من الأعداد الأولية ، وهي متواليات من الأعداد الصحيحة تحقق نفس علاقة التكرار التي تحققها أعداد فيبوناتشي ، بحيث تكون الأعداد المتتالية في المتوالية أولية فيما بينها، ولكن جميع الأعداد في المتوالية أعداد مركبة . على سبيل المثال، متوالية من هذا النوع التي اكتشفها هربرت ويلف لها حدود ابتدائية

a ₁ = 20615674205555510، a ₂ = 3794765361567513 (التسلسل A083216 في OEIS ) .

في هذه المتتالية، تشكل المواضع التي تكون فيها الأعداد في المتتالية قابلة للقسمة على عدد أولي p متتابعة حسابية؛ على سبيل المثال، الأعداد الزوجية في المتتالية هي الأعداد a _i حيث i متطابقة مع 1 mod 3. تشكل المتتابعات القابلة للقسمة على أعداد أولية مختلفة نظام تغطية، مما يدل على أن كل عدد في المتتالية قابل للقسمة على عدد أولي واحد على الأقل.

تساءل بول إردوش عما إذا كان لأي قيمة كبيرة N نظام تغطية غير متطابق يكون الحد الأدنى لمعاملاته على الأقل N. من السهل إيجاد أمثلة يكون فيها الحد الأدنى للمعاملات في مثل هذا النظام 2 أو 3 (أعطى إردوش مثالًا حيث تكون المعاملات في مجموعة قواسم العدد 120؛ والتغطية المناسبة هي 0(3)، 0(4)، 0(5)، 1(6)، 1(8)، 2(10)، 11(12)، 1(15)، 14(20)، 5(24)، 8(30)، 6(40)، 58(60)، 26(120)). أعطى د. سويفت مثالًا يكون فيه الحد الأدنى للمعاملات 4 (وتقع المعاملات في مجموعة قواسم العدد 2880). أثبت إس إل جي تشوي ^{[ 7 ]} أنه من الممكن تقديم مثال لـ N = 20، كما أثبت بايس بي نيلسن ^{[ 8 ]} وجود مثال لـ N = 40، يتكون من أكثر من${\displaystyle 10^{50}}$التطابقات. يوضح تايلر أوينز ^{[ 9 ]} وجود مثال مع N = 42 .

تم حل سؤال إردوش بالنفي بواسطة بوب هوف. ^{[ 10 ]} استخدم هوف ليمّة لوفاس المحلية لإثبات وجود قيمة قصوى N <10 ¹⁶ يمكن أن تكون أصغر قيمة معيارية على نظام تغطية.

هناك حدسية شهيرة لم تُحل بعد من إردوس وسيلفريدج : لا يوجد نظام تغطية غير متطابق (بمعامل أدنى أكبر من 1) تكون معاملاته فردية. من المعروف أنه إذا وُجد مثل هذا النظام بمعاملات خالية من المربعات، فيجب أن يحتوي المعامل الكلي على 22 عاملاً أولياً على الأقل. ^{[ 11 ]}

• نظرية الباقي الصينية
• طقم غطاء
• نظام الأرقام المتبقية

• تشي-وي صن : مشاكل ونتائج حول أنظمة التغطية (دراسة استقصائية) ( ملف PDF )
• تشي-وي صن: منشورات سرية حول أنظمة التغطية (ملف PDF) مؤرشفة بتاريخ 29-09-2007 على موقع Wayback Machine