论文标题
确定复杂性的下限
A Lower Bound on Determinantal Complexity
论文作者
论文摘要
在字段$ \ mathbb {f}上，多项式$ p \ in \ mathbb {f} [x_1，\ ldots，x_n] $的确定复杂性在$ \ mathbb {f} $上是最小的矩阵$ m $的尺寸，其条目是$ \ \ m m mathbb {$ p {$ p {$ p} $ p {$ p} $ p} [x_1，\ ld]， det（m）$。我们证明多项式$ \ sum_ {i = 1}^n x_i^n $的确定复杂性至少为$ 1.5N-3 $。 对于度量$ d $的每$ n $变量多项式，确定性复杂性至少至少$ d $，这是一个长期的开放问题，证明是一个较低的限制，它是$ \ max \ {n，d \} $的超级线性。我们的结果是任何显式多项式的第一个下限，该限制比$ \ max \ {n，d \} $更大，并且在$ n + 1 $的先前最佳界限上得到了改进，并由Alper，Bogart和Velasco [ABV17]证明，同一多项元素证明。
The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ is at least $1.5n - 3$. For every $n$-variate polynomial of degree $d$, the determinantal complexity is trivially at least $d$, and it is a long standing open problem to prove a lower bound which is super linear in $\max\{n,d\}$. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than $\max\{n,d\}$, and improves upon the prior best bound of $n + 1$, proved by Alper, Bogart and Velasco [ABV17] for the same polynomial.
