* Gdy piszę losowy wielomian o stopniu a n zmiennych, można myśleć o każdy jednomianów całkowitego stopnia 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 . Stąd dla prawdopodobieństwo wynosi dokładnie gdzie jest to prawdopodobieństwo, że jest stała. Niestety ten jest dość duży.
randomness
pr.probability
algebra
polynomials
Avishay Tal
źródło
źródło
Odpowiedzi:
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−Ω(n/d) 2−Ω((n≤d))
źródło
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
źródło