カバーシステム

数学において、被覆系（完全剰余系とも呼ばれる）は、集合である。

${\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} \},}$

その和集合にはすべての整数が含まれます。

被覆システムの概念は、1930 年代初頭に ポール・エルデシュによって導入されました。

カバーシステムの例は次のとおりです。

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}}\}.}$

2 つのメンバーが重なり合わない場合、被覆システムは非結合(または正確) であると呼ばれます。

すべてのモジュラスが異なる（かつ1より大きい）場合、被覆システムは別個（または不同）であると呼ばれます。HoughとNielsen（2019）^[1]は、任意の別個の被覆システムのモジュラスは2または3で割り切れることを証明しました。 ${\displaystyle n_{i}}$

すべての剰余類が整数をカバーすることが必要な場合、 被覆システムは非冗長（または最小）であると呼ばれます。

最初の 2 つの例は互いに独立しています。

3番目の例は異なります。

システム（つまり、順序付けされていない多重集合）

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

有限個の剰余類の -被覆は、すべての整数を少なくとも回覆う場合 -被覆 と呼ばれ、各整数を正確に 回覆う場合、正確な-被覆と呼ばれます。それぞれに対して、2つの被覆の和として表すことができない正確な -被覆が存在することが知られています 。たとえば、 ${\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}}\}}$

は、2 つの被覆の和集合ではない正確な 2 被覆です。

上記の最初の例は、正確な1被覆（正確被覆とも呼ばれる）である。よく使われるもう1つの正確被覆は、奇数と偶数の被覆、つまり

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

これは、次の事実の一例にすぎません。すべての正の整数係数 に対して、正確な被覆が存在します。 ${\displaystyle m}$

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

ヘルツォーク・シェーンハイム予想の特殊なケースであるミルスキー・ニューマン定理は、互いに素で異なる被覆系は存在しないことを述べている。この結果は1950年にポール・エルデシュによって予想され、その後すぐにレオン・ミルスキーとドナルド・J・ニューマンによって証明された。しかし、ミルスキーとニューマンは証明を公表しなかった。同じ証明はハロルド・ダベンポートとリチャード・ラドによっても独立に発見された。^[2]

被覆システムは、素数のない数列、つまりフィボナッチ数列と同じ再帰関係を満たす整数の列を見つけるために使用できます。この数列では、連続する数は互いに素ですが、すべての数は合成数です。たとえば、ハーバート・ウィルフによって発見されたこのタイプの数列は、初期項が

a ₁ = 20615674205555510、a _{2 = 3794765361567513（} OEISの配列A083216）。

この数列では、数列内の数字が素数pで割り切れる位置が等差数列を形成します。たとえば、数列内の偶数は、iが1 mod 3 に一致する数a _iです。異なる素数で割り切れる数列は被覆システムを形成し、数列内のすべての数字が少なくとも 1 つの素数で割り切れることを示します。

ポール・エルデシュは、任意の大きさの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) です)。D. スウィフトは、モジュライの最小値が 4 である例を示しました (モジュライは 2880 の約数の集合内にあります)。 SLG Choiは^[3] N = 20の例を挙げることが可能であることを証明し、Pace P Nielsenは^[4] N = 40の例の存在を実証し、これは100以上の合同を含む。Tyler Owens ^[5]はN = 42の例の存在を実証している。 ${\displaystyle 10^{50}}$

エルデシュの疑問はボブ・ハフによって否定的に解決された。^[6]ハフはロヴァースの局所補題を用いて、 N <10 ¹⁶の最大値が存在し、それが被覆システムの最小係数となり得ることを示しました。

エルデシュとセルフリッジによる有名な未解決の予想がある。それは、モジュラスが奇数である不同な被覆システム（最小モジュラスが1より大きい）は存在しない、というものである。そのようなシステムが平方自由モジュラスを持つ場合、全体のモジュラスには少なくとも22個の素因数がなければならないことが知られている。^[7]

• 中国剰余定理
• カバーセット
• 残基数システム

• 孫志偉：被覆システムに関する問題と結果（調査）（PDF）
• 孫志偉: カバーリングシステムに関する機密出版物(PDF) 2007-09-29 にWayback Machineでアーカイブ