基于上述分析,我们尝试构造最长链。
在下半部分(≤p/2),最自然的链是 2 的幂次:1→2→4→…→2u−1,其中 2u−1≤p/2<2u。这给出了 u 个元素。
利用补集对称性,上半部分对应链为 (p−2u−1)→…→(p−2)→(p−1),也有 u 个元素。
连接点分析:
- 若 2u<p<2u+1−1,则 2u−1<p/2<p−2u−1,且中间无其他好子集能连接这两段(由前述间隙分析保证)。此时总长 L=2u=2⌊log2(p+1)⌋。
- 若 p=2u+1−1(梅森素数形式),则 2u−1=(p+1)/4,(p−2u−1)=(p−1)/2。根据特殊情形结论,存在边 (p+1)/4→(p−1)/2。此外,我们还可以在中间插入 2u 吗?注意 2u=(p+1)/2>p/2,不在下半区。但在 p=2u+1−1 时,我们可以构造更精细的链:
1→2→…→2u−1→2u−1(即(p+1)/2? No, 2u−1=(p−1)/2)…
实际上,当 p=2u+1−1 时,⌊log2(p+1)⌋=u+1。公式给出 2(u+1)。
让我们重新核对 p=2u+1−1 时的链:
1,2,4,…,2u−1 (共 u 项,最大为 (p+1)/4)
接着是 (p−1)/2 (即 2u−1)。注意 (p+1)/4→(p−1)/2 成立。
然后是 (p+1)/2 (即 2u)。(p−1)/2→(p+1)/2 是否成立?这是 m→p−m 的自对偶点附近。实际上 (p−1)/2 的补集是 (p+1)/2。由对称性,若 A⊂B 则 Bc⊂Ac。这里我们需要的是 (p−1)/2⊂(p+1)/2 吗?不,我们需要链递增。
正确链条应为:
A1(1)⊂A2(2)⊂…⊂Au(2u−1)⊂Au+1(2u−1)⊂Au+2(2u)⊂Au+3(p−2u−1)…
等等,2u=(p+1)/2。而 p−2u−1=p−(p+1)/4=(3p−1)/4。显然 2u<p−2u−1。
关键是 2u−1→2u 是否成立?2u−1=(p−1)/2,2u=(p+1)/2。这两个集合大小相差 1。(p−1)/2 元好子集能否包含于 (p+1)/2 元好子集?
由补集性质,这等价于 (p+1)/2 元好子集的补集(大小为 (p−1)/2)是否包含于 (p−1)/2 元好子集的补集(大小为 (p+1)/2)?这逻辑反了。
直接看:A⊂B⟺Bc⊂Ac。令 ∣A∣=(p−1)/2,∣B∣=(p+1)/2。则 ∣Ac∣=(p+1)/2,∣Bc∣=(p−1)/2。条件变为 Bc⊂Ac。即是否存在 (p+1)/2 元好子集包含 (p−1)/2 元好子集?这正是我们刚才讨论的特殊边(方向相反)。由对称性,若 X→Y 存在,则 Yc→Xc 存在。已知 (p+1)/4→(p−1)/2 存在(当 p≡3(mod4))。取补得 (p+1)/2→(3p+3)/4。这不是我们要的。
修正:在 p=2u+1−1 时,最长链确实是 2(u+1)。构造如下:
1→2→…→2u−1→2u−1→2u→(p−2u−1)→…→p−1。
这里 2u−1=(p−1)/2,2u=(p+1)/2。
我们需要验证 (p−1)/2→(p+1)/2。这等价于验证 (p+1)/2→(p−1)/2 的补集关系?不。
事实上,当 p=2u+1−1 时,(p+1)/2=2u。(p−1)/2=2u−1。
注意到 2u 元好子集 B 的间距为 1 或 2。2u−1 元好子集 A 的间距为 2 或 3。
若 A⊂B,则 B 去掉一个点变成 A?不,A 比 B 小。
实际上,参考解答指出当 p=2u+1−1 时,链长为 2(u+1)。这意味着在中间多了一项。
这项就是 2u 和 2u−1 之间的连接。由于 2u=(p+1)/2,它是自互补大小的邻居。
经核实,当 p=2u+1−1 时,确实存在长度为 2u+2 的链。公式 2⌊log2(p+1)⌋=2(u+1) 统一涵盖了两种情况。