• 汇集公众科学智慧交流科学思想见解
  • 点燃科学智慧火花构建互动交流平台
科学智慧火花
发表评论  25                

Collatz 3x+1问题难在哪里?

投稿时间:2017-12-29 08:17 投稿人:郑敏 【字号: 访问量:

2001年6月,邬家邦的《3N+1猜想》[3]较全面详细地介绍了国际上对该问题研究的一些主要方法与成果;同年7月,异调的《3x+1问题》[1]在互联网上用较通俗的语言向我们描述了研究该问题的各种重要观点;几年后,两位年青的高中生整站翻译了国际分布式官方计算网站:“On the 3x+1 Problem”[4],为我们打通了了解、参与Collatz问题的一个重要平台。

关注这个问题的人,有一些是专业人士,也有不少业余数学爱好者。不时有人宣称意见攻克了这个世界难题,其中有的仅用了几个简单的公式,有的出版长篇著作(如四川中学教师李中华的《角谷猜想揭谜》[5])。

(一)入门容易

Collatz问题比较容易入门。问题涉及的各种定义、定理、观点以及研究方式方法五花八门,但许多初级内容实质上是一致的。我通过学习总结出定理1、2,后来发现,前人早有类似的结论,一些老师朋友在交流中也常常提到类似的内容。以《3N+1猜想》一书中介绍的有关内容为例。

 该书引理9.1:如果n∈Nd,则h(4n+1)=h(n)。

定理9.1:设对于某数m∈N和对于所有的n≡(22m-1)/3(mod22m-1)有h(n)<∞,则对于每个n∈Nd,有h(n)<∞。

定理9.1说明,在以下个奇数组中任取一组,若该组中的每个奇数满足3N+1猜想,则全体奇数都满足3N+1猜想。

 令:A=({x|x?101(mod1000),x∈M})2 ={x|x?5(mod8),x∈M}

定理1:若m == m0×22k+ (22k-1)/3  且m≠(22k-1)/3 (k∈N,k≠0,m0>1,m0∈A),则D(m)=D(m0)

由定理1得出结论:若Collatz问题对于数集A的所有元素都成立,则对于奇数集M、自然数集N的所有元素都成立。(注:《3N+1猜想》的定义高h(n)与我采用的归一步数D(m)是同一概念)

 举例:D(9)   =D(37)    =D(149)     =D(597)……

D(1001)=D(100101)=D(10010101)=D(1001010101)……

(注:我采用二进制数研究该问题。实例用十进制、二进制数同时写出,请对照)

显然,定理1与前人的结论完全一致。

 下表列出该书表3.1与3.2部分同高连续数对,与取m=1后的对应二进制数。

n

n(二进制)

n+1(二进制)

n

n(二进制)

n+1(二进制)

1

24 m +   2

10010

10011

25 m +  5

100101

100110

2

25 m +  22

110110

110111

26 m + 45

1101101

1101110

3

 26 m +  14

1001110

1001111

27 m + 29

10011101

10011110

4

27 m +  94

11011110

11011111

28 m +189

110111101

110111110

5

 28 m +  62

100111110

100111111

29 m +125

1001111101

1001111110

6

 29 m + 382

1101111110

1101111111

210m +765

11011111101

11011111110

令 B={x|x=n×22k+(22k-1-1)or m×22k+1+(22k-1),x∈A,k≧1,n≡0(mod2),m≡1(mod2)}

定理2:若 m1∈B, m2=2m1+1,则D(m1)=D(m2)。

 先看左半表,例:

n=54=(1100110)2、n+1=55=(110111) 2,n/2=27=(11011)2=3×2^3+(2^2-1)∈B,D(27)=D(55);

n=78=(1001110)2、n+1=79=(1001111)2,n/2=39=(100111)2=10×2^4+(2^3-1)∈B,D(39)=D(79);

……

再看右半表,例:

n=109=(1101101)2∈AC、n+1=110=(1101110)2,(n+1)/2=55=(110111)2∈BC, 27=(11011)2∈B,D(27)=D(55)=D(109);

n=157=(10011101)2∈AC、n+1=158=(10011110)2,(n+1)/2=79=(1001111)2∈BC, 39=(100111)2∈B,D(39)=D(79)=D(157);

……

将表中偶数除以2变为奇数后,左半表的数据完全是定理2的实例,右半表则是组合运用定理1、2得到的结果。

 专业的、业余的、不同国度的研究者得出基本相同的结论,虽然是较浅显的结论,对我也是鼓舞。入门不难,沿着这些初步的结论继续向前,会遇到什么问题呢?

(二)透过启发式论证看我们面临的困境

很难预料,入门如此容易的问题,几十年后依然令数学家与众多研究者苦不堪言。

“We face this dilemma: On the one hand, to the extent that the problem has structure, we can analyze it—yet it is precisely this structure that seems to prevent us from proving that it behaves “randomly”. On the other hand, to the extent that the problem is structureless and “random,” we have nothing to analyze and consequently cannot rigorously prove anything.”[2]

对于这样的问题,梦想一举成功不可能,不如做一点点具体分析。

面对复杂的研究对象,人们努力把“把某个集合中的对象排列成某种模式,使其满足一些指定的规则”[6]

“启发式论证”是一个设想。J. Lagarias指出,如果我们把奇变换后再作偶变换考虑在一起,那么这样得到的结果可以看作是真的“很随机”。于是有1/2的可能性它是奇数,有1/4的可能性是一个奇数的2倍,有1/8的可能性是一个奇数的4倍,等等。于是平均来讲,每次变换后高度的变化就是:c=(3/2)1/2(3/4)1/4(3/8)1/8(3/16)1/16……=3/4,所以高度在总体上来说应该是越来越低,每次大约低25%……。[1][2]但“就算再有实验证据来表明它是对的,也只不过是个论证,只能使我们对猜想的正确性更充满信心。它不能代替真正的数学证明。”因为,这个论证的基础——平均、随机仅仅是一种假设,我们不能依靠假设做出严谨的证明。

研究者也构建了某些模式。“数学家们证明了,存在一个常数c,当n足够大的时候,在比n小的航班中,能够在1上着陆的航班的个数大于等于nc。”“1995年D. Applegate和J. Lagarias得到c=0.81。……在论文中,我们看见一个关于如何写出这个巨大方程组的说明,和由程序计算出来的结果,以及如何使用这些结果来解释c=0.81。其他的数学家如果想验证这个结果,必须首先看懂关于方程组的证明和那些解释,再按照里面的说明来写一个程序(很复杂的!),运行它,再看看结果是否和文章中的相同。”[1]从介绍来看,此模式极其复杂。

从单一的Collatz序列出发,很难构建出较好的模式。众多Collatz序列组成一个Collatz图,图虽然比序列更庞大、复杂,但只要能够建立一个模式,显示出同级元素排列规律,各级元素之间的变换都规则,这个问题就不是“structureless”和“random”了。

(三)Collatz图基本单元

下面按照以上的思路,利用定理1、2的结论,在Collatz图中把数集B中的对象进行排列。

先将研究范围压缩到奇数。继续把研究范围缩小到数集A,由于数集Ac中与m(m∈A)对应的奇数m×22k+(22k-1)/3有无穷多个, m的父项是一个无穷数列,(数列前项×106+110001)2=后项。进一步缩小研究范围到数集B,奇数m (m∈B)同时代表数集Bc中奇数2m+1,m的父项扩展为2列无穷数列,这两个数列的2个最小项(mx1与mx2)合称为m的最小父项对。

奇数m(m>1)的最小父项对由下式(二进制)确定:                                         

当m≡0(mod11)时: mx1=      (m/11)×103+1  mx2=    (m/11)×104+1

当m≡1(mod11)时: mx1=((m- 1)/11)×102+1  mx2= (m-1)/11×105+10001

当m≡10(mod11)时:mx1=((m-10)/11)×10 +1  mx2=(m-10)/11×106+110001            (3.1)

奇数m与其最小父项对构成了Collatz图的基本单元(见下图)。

依据(3.1)式,可以计算出奇数m的最小父项对的二进制平均数位与m数位的差值(m≡d(mod3),m>3):

(B(mx1)+B(mx2))/2-B(m) = ([ln(mx1)]+[ln(mx2)])/2-[ln(m)]

   =([ln(m-d)/3] + 7/2-[ln(m)] = 7/2 - k > 1    (k=[ln(m)]-[ln(m-d)/3]=1或2)

   [x]表示取x的最大指数值。

由于Collatz图全部由同样的基本单元组成,因此各级元素的平均数位逐级递减,无一例外。也就是说,假如Collatz图中不存在出4-2-1以外的循环圈,就一定是收敛的。

真诚请各位专家、老师、朋友批评指正。无论成败,我都会逐步深入,逐步提高自己的思维能力。

参考资料:

[1] 异调:《3x+1问题》 《三思科学》电子杂志创刊号 2001.07.01

[2] Jeffrey C. Lagarias, The 3x+1 Problem and its Generalizations, AT&T Bell Laboratories Murray Hill,NJ 07974. January 16,1996.)

[3] 邬家邦,2001年6月,《3N+1猜想》,湖南大学出版社,25、29、119-121、132页。

[4] [荷] Eric Roosendaal,“On the 3x+1 Problem”网站(http://www.ericr.nl/wondrous/index.html.

[5] 李中华,《角谷猜想揭谜》 中华经纶出版社 2005年8月。

[6] Richard A.Rrualdi著,冯速译,《组合数学》机械工业出版社2012年5月