论文标题
在大多数HyperCube上消失至高阶的多项式
Polynomials that vanish to high order on most of the hypercube
论文作者
论文摘要
由于对Alon的组合无效的无效概括及其应用，我们研究了以下问题：对于固定的$ k \ geq 1 $和$ n $，相对于$ k $ $ p（0，\ dots，0）\ neq 0 $，以至于$ p $在$ \ {0,1 \}^n \ setMinus \ {（0，\ dots，\ dots，0，0）\} $的所有点的$ p $中至少为$ k $？对于$ k = 1 $，Alon和Füredi的经典定理指出，这种多项式的最低程度等于$ n $。在本文中，我们解决了所有$ k \ geq 2 $的问题，证明答案是$ n+2k-3 $。作为一个应用程序，我们改善了克利夫顿和黄的结果，以$ \ mathbb {r}^n $中的超平面配置为$ \ {0,1 \}^n \ setMinus \ {（0，\ dots，0）\} $，至少是$ k $ k $ kyperplanes，0 $ boint $ dopt（0），$ k $ k $ k $ k $ k $ k $ n opter（0），0）upert（0）令人惊讶的是，我们结果的证明涉及加泰罗尼亚的数字和列举组合学的论点。
Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed $k\geq 1$ and $n$ large with respect to $k$, what is the minimum possible degree of a polynomial $P\in \mathbb{R}[x_1,\dots,x_n]$ with $P(0,\dots,0)\neq 0$ such that $P$ has zeroes of multiplicity at least $k$ at all points in $\{0,1\}^n\setminus \{(0,\dots,0)\}$? For $k=1$, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals $n$. In this paper, we solve the problem for all $k\geq 2$, proving that the answer is $n+2k-3$. As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in $\mathbb{R}^n$ such that each point in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ is covered by at least $k$ hyperplanes, but the point $(0,\dots,0)$ is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.
