Jaka jest tendencja do losowych wielomianów o niskim stopniu nad GF (2)?

$p$$\le d$$bias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon$

* Gdy piszę losowy wielomian o stopniu $\le d$ a n zmiennych, można myśleć o każdy jednomianów całkowitego stopnia $\le d$ pobrane z prawdopodobieństwem 1/2.

Jedyną istotną rzeczą, jaką znam, jest wariant Schwartza-Zippla, który stwierdza, że ​​jeśli wielomian jest niestały, wówczas jego odchylenie wynosi co najwyżej $1-2^{1-d}$ . Stąd dla $\epsilon=1-2^{1-d}$ prawdopodobieństwo wynosi dokładnie $1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$ gdzie jest to prawdopodobieństwo, że $p$ jest stała. Niestety ten $\epsilon$ jest dość duży.

Artykuł „Losowe wielomiany niskiego stopnia są trudne do przybliżenia” autorstwa Ben-Eliezera, Hoda i Lovetta odpowiada na twoje pytanie. Wykazują silne granice korelacji losowych wielomianów stopnia z wielomianami stopnia co najwyżej , analizując tendencyjność losowych wielomianów. Zobacz ich Lemat 2: błąd systematyczny wielomianu stopnia (do pewnego który jest liniowy w ) wynosi co najwyżej , z wyjątkiem prawdopodobieństwa .$d$$d-1$$d$$d$$n$$2^{-\Omega(n / d)}$$2^{-\Omega\Big(\binom{n}{\le d}\Big)}$

Twoje pytanie jest równoważne ograniczeniom ogona w rozkładzie masy kodów Reeda-Mullera. Zrozumienie rozkładu ciężaru kodów Reeda-Mullera jest starym i trudnym pytaniem w teorii kodowania, i wiadomo o nim kilka interesujących wyników (rozkład masy jest całkowicie zrozumiały tylko dla i ). Jako doskonały punkt wyjścia, patrz „Rozkład masy i rozmiar dekodowania kodów kodów Reeda-Mullera” Tali Kaufmana, Shachara Lovetta, Ely'ego Porata i odnośniki w nim zawarte.$d=1$$d=2$