BinSYS 项目

 

项目介绍

 

目标

 

项目的目标是找出所有直到 11 维的广义二进制数系。在下面我们会给出数系的概念和一些可能的程序。

 

介绍

 

令 n 为大于一的正整数。当我们谈论普通意义上的数系时,我们涉及到以下的一个事实:任何自然数都可以唯一地表示为

 

 

我们说 n 是这个数系的基,被称为位。当 n=2 时我们就把这个数系称为二进制数系。这些数系太弱了,以至于不能表达负数,所以我们需要符号。如果我们允许数系的基为小于 -1 的负整数,我们就能用这个数系表达全部整数。比如说,如果我们以 -2 作为基,那么每个整数都可以唯一表示为

 

这能够推广到所有代数整数上。比如说,所有高斯整数(形如 x+yi 的复数,x,y 为整数)能以 -1+i 为基唯一地表示为

 

利用线形代数我们甚至可以再推广数系。现在,数系的基是矩阵而位是向量。我们现在可以重写更前面的例子。每一个二维整向量能够唯一地表示为

 

 

这里,

 

如果M的行列式的值是 ±2 的话,我们就把这个数系称为二进制数系。在这个例子中每位只有两个值,其中一个是原点。这就意味着我们有一个能把每个整向量唯一地标为一串 0 和 1 的组合的数系。

 

不是每个矩阵 M 都能成为数系的基。直到现在我们还不知道一个能成为数系的基的矩阵会有什么性质。我们有判别一个矩阵是否能成为数系的基的充分和必要条件,但是它们之间的强弱差距太大了。现在还没有有效的方法来处理满足必要条件但不满足充分条件的方法。我们只知道如果我们限定维数,可能的矩阵是有限的。

 

期待的结果

 

这个程序旨在寻找多维广义二进制数系。一个扩展的搜索已经在满足某些必要条件的矩阵的有限集中展开。困难在于,这个集合的大小是给定维数的一个指数函数。现在我们认为进行 11 维的搜索是可行的。为了检验更严格的必要条件,程序需要做很多的浮点运算,所以我们需要许多 CPU 时间。幸运地,我们能把这个程序并行化,从而加快速度。

 

程序的输出是一个可能可以成为数系的基的矩阵的列表(以更加精确的特征多项式的形式)。这个列表会被另一个程序处理,最终得到的就是一个完整的可以成为数系的基的给定维数的矩阵列表。

 

然后我们就可以对这些数据进行理论分析。数系提供对整向量的二进制表达。利用坐标我们可以得到一个更标准的表达。两种表示方法各有长处。况且,两个很接近的向量的二进制表达可能会很不同。这就暗示了我们可以把这些数系应用到压缩、编码或者密码学当中去。
 

从几何角度看,数系也是很有趣的。如果我们允许 M 的负数次幂出现在二进表达中的话,我们能获得实向量的无穷表达式。表达式中只含有M的负数次幂的向量集合通常是一个分形。程序的输出可以用来分析这些集合的拓扑性质,比如说分维数和连通度。如果我们用上面的M的话,我们得到的是以下的集合:

 

 

 

最后,得到所有在给定维度下的矩阵能帮助我们对广义数系有更深的认识。

 


For more detailed information about this project visit this site.

Visit the project's homepage hosted by ELTE (Eötvös Loránd University).


Return to SZTAKI Desktop Grid main page

Copyright © 2006 SZTAKI Desktop Grid