Littlewood–Oford problem

Inom det matematiska området för kombinatorisk geometri är Littlewood -Oford-problemet problemet med att bestämma antalet subsummor av en uppsättning vektorer som faller i en given konvex uppsättning . Mer formellt, om V är ett vektorrum med dimensionen d , är problemet att, givet en ändlig delmängd av vektorer S och en konvex delmängd A , bestämma antalet delmängder av S vars summering är i A .

Den första övre gränsen för detta problem bevisades (för d = 1 och d = 2) 1938 av John Edensor Littlewood och A. Cyril Offord . Detta Littlewood–Oford-lemma anger att om S är en uppsättning av n reella eller komplexa tal med absolut värde minst ett och A är vilken skiva som helst med radie ett, då inte mer än ( $\displaystyle {\Big (}c\,\log n/{\sqrt {n}}{\Big )}\,2^{n}}$ av de 2 ⁿ möjliga subsummorna av S faller in på skivan.

1945 förbättrade Paul Erdős den övre gränsen för d = 1 till

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

med Sperners sats . Denna gräns är skarp; Likhet uppnås när alla vektorer i S är lika. 1966 visade Kleitman att samma gräns gällde för komplexa tal. 1970 utvidgade han detta till inställningen när V är ett normerat utrymme .

Antag att S = { v ₁ , …, v _n }. Genom att subtrahera

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

från varje möjlig delsumma (det vill säga genom att ändra ursprunget och sedan skala med en faktor 2), är Littlewood–Offord-problemet ekvivalent med problemet med att bestämma antalet summor av formen

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

som faller i målmängden A , där $\varepsilon _{i}$ tar värdet 1 eller −1. Detta gör problemet till ett probabilistiskt , där frågan är fördelningen av dessa slumpmässiga vektorer och vad man kan säga utan att veta mer om v _i .