午夜学术新闻

之前介绍过著名的秘书问题网页链接，现在把它推广到拟阵结构（matroid），即在满足独立性约束的前提下选择多个元素，目标是最大化总价值。

猜想：任何拟阵都存在一个常数竞争比（O(1)-competitive）的在线算法。长期以来，最好的结果是 𝑂(log⁡log⁡𝑟)，其中 𝑟 是拟阵的秩。

现在这篇论文网页链接 提出一个算法，保证每个最优解中的元素被接受的概率至少为 1/4。

这相当于直接给出了一个 4-competitive 算法，从而证明了拟阵秘书猜想成立。

————————

另外，据说两位作者（其一来自北京大学）证明了Sylvester猜想网页链接

因为毕业论文里做了与这个猜想相关的事情，所以稍微写一点关于Sylvester猜想的内容吧

其基础是以下经典的丢番图方程问题：素数p何时可以表示为两个有理数的三次幂之和？

如果是整数的三次和则很简单，但有理数的三次和这个问题就很棘手。

相对不容易好想的如 17=（18/7）^3+(-1/17)^3

当 p=2 时，2=1^3+1^3 可以表示，因此以下假设 p>2。

三次之和问题可以重新表述为“曲线Ep：x^3+y^3=p何时有Q有理点？”

事实上，Ep具有Q上的椭圆曲线结构，尤其是Q中所有有理点的集合Ep（Q），构成一个有限生成的阿贝尔群。

此外，由于Ep（Q）中唯一的有限阶点是无穷远点，最终Ep（Q）作为群同构于形式 Z^r。

从上述讨论得出

素数p可表示为有理数的3次幂之和⇔Ep上有Q有理点存在⇔r≠0

之后只要能计算r（Mordell-Weil秩）即可。

完全确定秩r是个非常困难的问题，但通过三阶下降法，可以确定r的候选人：

1） p≡2,5 mod 9 ⇒ r = 02） p≡4,7,8 模9 ⇒ r = 0,13） p≡1 mod 9 ⇒ r = 0,1,2

因此，在（1）情况下，p 不能表示为有理数的三个平方和。

此外，假设泰特-沙法列维奇群是有限的，我们可以确定秩r的奇偶性。

1'） p≡2,5 mod 9 ⇒ r = 02'） p≡4,7,8 mod 9 ⇒ r = 13'） p≡1 模9 ⇒ r = 0,2

因此，在（2'）的情况下，p总可以表示为有理数的三次和。

如今，由于泰特-沙法列维奇群被认为是有限的，（2'） 和 （2） 预期等价，即 r = 1。

这正是西尔维斯特的预言。

西尔维斯特猜想：当素数 p 满足模 9 的 p≡4,7,8 时，Ep 的秩为 1（p可表示为有理数的三次和）。

p≡4、7的情况已被证明。

另一方面，对于p≡8，之前未实现完整的证明。