リトルウッド・オフォード問題

組合せ幾何学という数学の分野において、リトルウッド・オフォード問題（リトルウッド・オフォードじんか、 Littlewood–Offord problem）は、与えられた凸集合に含まれるベクトル集合の部分和の個数を決定する問題である。より正式には、次元dのベクトル空間Vに対し、ベクトルの有限部分集合Sと凸部分集合Aが与えられたとき、その和がAに含まれるSの部分集合の個数を決定する問題である。

この問題の最初の上限は、1938 年にジョン・エデンサー・リトルウッドとA. シリル・オフォードによって証明されました ( d = 1 およびd = 2 の場合) 。^{[ 1 ]}このリトルウッド–オフォードの補題は、 S が少なくとも 1 の絶対値を持つn個の実数または複素数の集合であり、 Aが半径1 の任意の円板である場合、 Sの可能な部分和の²ⁿ個のうち最大でも円板に入らないことを述べています。 ${\displaystyle {\Big (}c\,\log n/{\sqrt {n}}{\Big )}\,2^{n}}$

1945年にポール・エルデシュはd = 1 の上限を次のように改良した。

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\approx 2^{n}\,{\frac {1}{\sqrt {n}}}}$

スペルナーの定理を用いると ^、この境界は明確である。^つまり、 Sのすべてのベクトルが等しいときに、等式が成立する。1966年、クライトマンは複素数に対しても同じ境界が成り立つことを示した。1970年、彼はこれをV がノルム空間である設定にまで拡張した。^{[ 2 ]}

S = { v ₁ , …, v _n } と仮定する。

${\displaystyle {\frac {1}{2}}\sum _{i=1}^{n}v_{i}}$

それぞれの可能な部分和から（つまり、原点を変えて2倍にスケーリングすることによって）、リトルウッド・オフォード問題は、

${\displaystyle \sum _{i=1}^{n}\varepsilon _{i}v_{i}}$

対象集合Aに含まれるベクトルで、 は1または-1の値をとる。これにより問題は確率論的なものとなり、これらのランダムベクトルの分布が問題となり、 v _iについてそれ以上何も知らない状態で何が言えるかが問われる。 ${\displaystyle \varepsilon _{i}}$

参考文献

1. Littlewood, JE; Offord, AC (1943). 「ランダム代数方程式の実根の数について (III)」. Rec. Math. (Mat. Sbornik) . Nouvelle Série. 12 (54): 277– 286.
2. ボロバス、ベラ (1986)。組み合わせ論。ケンブリッジ。ISBN 0-521-33703-8。