一个1969年提出的关于和相互抵消的猜想被证明是错的
拿一个只有六个小时的时钟,再列出一串拨动:“把指针向前拨1小时”“向前拨4小时”,等等。如果有五次拨动,每次都拨一小时,那么其中任何一组都不会让指针恰好回到起点。而有了六次拨动,无论它们是什么,总有某一组能做到。数学家把这种时钟算术记作C₆,而这里的六就是这个时钟的Davenport常数。
现在把r个这样的时钟并排放置,并让每次拨动把每根指针各拨动它自己的量。这组时钟的Davenport常数记作D(C₆^r),它是能保证存在一组拨动、其总和让每根指针同时回到起点所需的最少拨动次数——用论文的话说,就是一个零和子序列。这个常数与图论、有限几何、组合学和因子分解理论中的问题都有关联。
一个来自1969年的公式
有一个简单的下界。在每个时钟上,取五次只作用于这个时钟、每次拨一小时的拨动:有r个时钟时,就得到5r次拨动,其中没有任何一组能相互抵消。所以至少需要5r + 1次拨动。一般地,对于有n个小时的时钟,至少需要r(n − 1) + 1次。
1969年,van Emde Boas和Kruyswijk猜想,这个简单的下界总是确切的答案:
D(C_n^r) = r(n − 1) + 1.
在1960年代,它在某些情形下得到了证明,例如时钟的小时数是素数的幂,或者时钟至多有两个。除此之外,确切值始终遥不可及:直到2018年,就连四个六小时制时钟的情形都还是未知的。尽管如此,这个猜想还是成了该领域“一个著名的长期悬而未决的问题”,人们预计它会成立。
永不抵消的116次拨动
Weidong Gao(天津大学)、Alfred Geroldinger(格拉茨大学)、Guoqing Wang(天津工业大学)和Xiangneng Zeng(中山大学)现在证明它不成立。
这个团队像搭积木一样组装这些拨动:
- 一个作用于五个六小时制时钟、由24次拨动组成的列表,由一张小表构造而成:其中任何一组拨动,只要总和落在由三个位置组成的一个小集合内,就总是落在同一个非零位置上;
- 两个这样的列表,它们共享这三个位置,由此得到48次拨动,其中没有任何一组能相互抵消;
- 另一个由20次拨动组成的列表,其中同样没有任何一组能相互抵消。
把它们并排放在一起,就得到23个六小时制时钟上的2 × 48 + 20 = 116次拨动,其中没有任何一组能让每根指针都回到起点。按照猜想,23 × 5 = 115是这类列表可能的最大长度。所以对于23个时钟,Davenport常数至少是117,而不是116。
这样的积木块可以叠加复制:一般的结果是D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1,其中⌊r/23⌋表示r中能容纳多少个由23个时钟组成的完整块。因此,对于六小时制时钟,一旦r达到23,这个猜想就不成立,对于每个更大的r也是如此。作者们指出,同一定理还否定了一个关于覆盖的猜想结果。
仍未解决的问题
这个证明没有给出D(C₆^r)的真实值,只给出了一个猜想所不允许的界。对于少于23个时钟的情形——此时新的界等于原来的公式——以及小时数不是六的时钟,它没有带来任何新结论。这篇短文共五页,尚待同行评审。
