戴德景问题的降维算法

戴德景问题的降维算法 ON THE ALGORITHM BY REDUCTION OF RANK FOR SOLVING DEDEKIND’S PROBLEM 胡守木 1 2 first-author 代大为 1 2 刘初长 1 2 国营华中精密仪器厂 国营华中精密仪器厂 武汉大学 武汉大学 < 正 > 关于代德景问题,即"有穷个元生成的分配格,应有多少个元素?"至今没有完全解决。我们用D n 表示n个元生成的分配格,|D n |表示其元素个数。对于n≤5,手算容易解决。至于|D 6 |,还是Ward在1946年借助于计算机获得的。Agnew于1960年验证了这一结果。1965年,Church根据元素的秩,采用枚举法得到了|D 7 |。我们认为,利用二进制堆垛数集研究D n ,可以使问题简化。而降维方法,则是一个很有效的方法。本文是这方面工作的一个尝试。 It is well know that the free distributive lattice generated by n elements is isomorphic to the set A n of the pile-numbers. Now we define recursively the set V n of vertices of the n dimensional cube A 0 n as the following: If a permutation of 2 k elements taken from A n is denoted by U n （2 k ）, then we have Lemma: The relationship between A n+l and A n is presented by the formula: In this paper, Using this lemma, an algorithm by reduction of rank for solving Dedekind’s problem is given. Then we have calculated the order of the distributive lattice generated by 7 elements and verified that |D 7 |=2,411,682,040,998 which is agree with the church’s result obtaned in 1965. 1982-02-01 2021-04-01 2