数学家最新重大突破：发现了第九个戴德金数

KeyTo9_Fans

“含有n个变量的单调布尔函数有多少种？”

数学家们把这个问题的答案称为“第n个戴德金数”

前9个戴德金数如下图所示：



其中，第8个戴德金数，是在1991年使用当时最强大的超级计算机Cray 2算出来的

而最新的第9个戴德金数，是在可编程门阵列（Field Programmable Gate Arrays，FPGA）的硬件上，经过几年的时间开发软件（程序），然后在超级计算机上运行了大约5个月，最终在2023年3月8日算出来的

新闻链接：
https://www.huxiu.com/article/1732768.html
https://baijiahao.baidu.com/s?id=1769861253645924163

OEIS链接：
https://oeis.org/A000372

nyy

第一次听说戴德金数，不知道能干嘛

KeyTo9_Fans

我也不知道能干什么，继续查阅了一些资料，发现：

新闻里的“戴德金数”是“含有n个变量的单调布尔函数有多少种”

百度百科上面的“戴德金数”是“数论中的一种著名函数s(p,q)=∑((k/q))((pk/q))”：
https://baike.baidu.com/item/%E6%88%B4%E5%BE%B7%E9%87%91%E6%95%B0

关于“第n个戴德金数”，百度百科里压根就没提到。

不知道百度百科里讲的“戴德金数”为什么完全不一样呢？

它和“第n个戴德金数”有联系吗？

nyy

不知道戴德金数能干嘛，我孤陋寡闻第一次听说

nyy

KeyTo9_Fans 发表于 2023-7-11 20:01
我也不知道能干什么，继续查阅了一些资料，发现：

新闻里的“戴德金数”是“含有n个变量的单调布尔函数 ...

数学没啥用，还是学计算机实在，郭先强去码代码了，最后还创业当老板了

mathe

这个概念有点难理解，看了大半天才明白。
原来所谓n个变量的布尔函数就是n个元素集合{1,2,3,...,n}的所有子集到{0,1}集合的映射。
比如n=2,那么就是{{}, {1},{2},{1,2}}到{0,1}的所有映射，比如f({})=f({1})=0, f({2})=f({1,2})=1就是一个n=2的布尔函数。
而单调递增的布尔函数要求，如果一个集合被映射到0，那么它的所有子集也都映射为0，比如上面我给出的例子就是单调递增的。
而函数f({})=f({1,2})=0,f({1})=f({2})=1就不单调递增。

oeis链接里面还给出了一个antichain的概念，但是没有给出解释，这个比较费解。
由于如果一个集合被映射到0,那么它的所有子集也都会被映射到0，所以我们只需要找到所有那些被映射到0的极大集合(也就是所有包含它的集合都被映射到1)，这些极大集合就构成了antichain。然后，我们就可以用antichain来表示这个函数映射了。
比如n=0有两个antichain,也就是有两个不同的单调增函数:
{}:，代表所有集合被映射为1，也就是函数f({})=1
{{}}: 代表空集被映射为0，也就是函数f({})=0

n=2有6个antichain
{}: 代表所有集合被映射为1，也就是函数f({})=f({1})=f({2})=f({1,2})=1
{{}}: 代表仅空集被映射为0, 也就是函数f({})=0， f({1})=f({2})=f({1,2})=1
{{1}}： 代表{1}和它子集被映射为0， 也就是函数f({})=f({1})=0，f({2})=f({1,2})=1
{{2}} : 代表{2}和它子集被映射为0， 也就是函数f({})=f({2})=0，f({1})=f({1,2})=1
{{12}}： 代表{12}和它子集被映射为0， 也就是函数f({})=f({1})=f({2})=f({1,2})=0
{{1}{2}}： 代表{1}，{2}和它们的子集被映射为0，也就是函数f({})=f({1})=f({2})=0，f({1,2})=1

另外我们可以看出对于一个antichain, 它的任意两个元素（都是集合）相互不包含。而对于任何一个符合这个条件的子集集合，它也是一个antichain.
所以可以通过计数所有任意两个元素都互相不包含的集合的数目就可以。