![](https://csdnimg.cn/release/download_crawler_static/88777918/bg5.jpg)
多 项 式 在 单 项 式 的 基 础 上 由 Klivans 和 Spielman [KS01] 。 通 过
对
L
asco
x
和
S
chu
?
t
zen
b
e
r
ge
r
[LS 85]
的
模拟,我们推导出
了S chub
e
r
t
pol
y
n
o
m
i
a l
s的关键性质,使其具有较
好的可靠性I友好基的概念和相应的插值算法可能是独立的兴趣,因为它们可以用于
应用于多元多项式环(的子环)的其他基,例如Grothendieck多项式和Macdonald多项
式[Las13]。
我们想强调舒伯特多项式的一个微妙的点
,这
对我们的算法至关重要:对于
Y
v
,
如 果 单 项 式 x
u
在
Y
v
中 , 则 v 优 于
u
;
也 就 是
说 ,
v
n
≥
un
,
v
n
+
v
n−
1
≥
un
+
un
−
1
,
.. . ,
vn
+
···
+
v1
≥
un
+
···
+
u1
。 虽 然 这 绝 不 是 一 个 困 难 的 属 性
和 知 识 , 但 它 并
不 意 味 着 在
Lascox
62,脚注4],所以我们在引理14中证明了它另一方面,在文献中经常提到一个
较弱的性质,即v在逆字典序中不小于
u
然而,这一顺序证明
不
足以达到插值的目的。
与Barvinok-Fomin算法的比较。Barvinok-Fomin算法的底层结构和我们的算法非常相
似。但也有一些主要的区别
从数学方面来看,注意Barvinok和Fomin使用了mono-mial的优势阶另一方面,我们
利用逆优势阶,这对应于命题18中使用的下三角不难看出,优势阶并不适用于所有的
舒伯特多项式。我们还需要将几个点(例如计算和系数的界限)从Schur多项式升级
为Schubert多项式。
从算法方面来看,本文的算法和Barvinok-Fomin算法都将多元插值问题归结为一元
插值问题。这里有两个关键的区别。首先,Barvinok和Fomin依靠随机性得到一组线性
形式s. t。它们中的大多数对于一小组向量实现不同的值。我们诉诸于一个确定性的
建设Klivans和Spielman为这个集合,因此去随机化的Barvinok-Fomin算法。其次,我们
的算法具有递归结构的Barvinok-Fomin算法。但在每个递归步骤中,方法是不同的;我
们的方法是基于Klivans-Spielman算法。因此,我们的算法不需要知道展开式中系数的
界限,而[BF 97,Sec.4.1]可以这Barvinok和Fomin在[BF 97,Sec. 4.2]。然而,似乎很难
去随机化这种概率验证过程。
Organization. 在第2节中,我们提出了一些问题。在第三节中,我们定义了斜舒伯特多
项式和舒伯特多项式,并给出了定理2、推论3和定理4的证明。在第四节中,我们定
义了插值友好基,并给出了在这种基上的插值算法。在第5节中,我们证明了舒伯特
多项式形成一个I-友好的基础,从而证明定理1。我们提醒读者,斜舒伯特多项式只
在第3节中研究。
2
预赛
符号。 对于
n ∈ N
,
[
n
]
:=
{
1,
. . .
,
n}
。 设x =(
x1
,
. . .
,
xn
)是n个变量的元
组
。当
没有歧义时,x可以表示集合
{x
1
,
. . .
,
xn
}
。 对于e =(
e1
,
. . .
,
en
)
∈
Nn
,
则
指数为e的单项式为
xe
:=
xe1
. . . x
e
n
. 给定
f
∈ Z
[x]和e
∈ N
n
,
Coeff(e,
f
)
表示