BinSYS
Project
Eotvos Lorand University, Faculty of Informatics,
Department of Computer Algebra
Project description
Aims
The aim of
the project is to find all the
generalized binary number systems up to dimension
11. Below we give a short description
of the number
system concept and mention a few possible applications.
Introduction
Let n be an
integer greater than one. When we
speak of number systems in the original
sense, we use the fact
that each natural number
z can be written uniquely in the
finite form
.
We say that n is the base
of the number
system, the
are
called the digits. If n = 2 then we speak
of a binary number system. These systems are
too poor to represent negative
numbers so we need a sign.
If we allow
the base to be a negative integer, a representation of all integers may
become possible. Such, for example
if we use
the base -2, each integer has a form
This can
be generalized for the algebraic integers
of a finite extension of the
rational number field. A simple example: all the
Gaussian integers (complex numbers of the
form x+yi, where x,y
are integers) can be written uiquely in the
base (-1+i) as follows
.
Using linear
algebra we can define number systems
in an even
more general way. The base is now a matrix
and the digits
are vectors. We can reformulate
the previous example. Each two-dimensional
integer vector has a representation
as a finite sum
,
where
and 
.
We speak of a binary system
if the determinant
of M is ±2. In this case there
are only two digits, one
of them being the origin. This
means that if we have
a number system then every integer vector can be represented
as a finite series of 0s and
1s.
Not every
matrix M can be a number system base.
Until now no characterisation of ”good” matrices have been given.
There are sufficient conditions and there are
necessary ones but the gap
between them is too large. There
is no known efficient method of dealing with
matrices that fulfil necessary conditions but fail sufficient conditions. One thing to note
is that if we fix the determinant
and the dimension
then roughly speaking there are only a finite
number of possible matrices.
Expected results
The program aims at finding many
generalized binary number systems. An extensive search
is performed in the finite set
of matrices of given size
fulfilling some necessary conditions. The difficulty is that the size of
this finite set is an exponantial
function of the dimension. It now seems
possible to attack the case
of 11 ´ 11 matrices. To check
further necessary conditions the program performs a lot of floating-point calculation. Thus, a lot of CPU time
is needed. Luckily, parallelization is possible and we can
benefit of running on several
machines.
The program outputs a list of matrices
(being more precise characteristic
polynomials) that are already likely
to be number system bases. This
list is processed by another program (which does not
need so much
CPU). The final result is then a (complete) list of binary
number systems in a fixed dimension.
Thereafter we
perform information theoretical analysis. The number systems provide a binary representation of integer vectors. Using coordinates we have another (more standard) representation. The two representations usually differ in length.
Besides, vectors close to each
other in the space can
have binary representations that look very different.
These observations suggest that one
could apply number systems in data compression,
coding or cryptography.
Number systems
are interesting from a geometrical point of view,
too. If we
allow negative powers of M to
appear in the binary representation
we get a possibly infinite representation of real vectors (we
could say that we use
a radix point). The boundary of the
set of vectors
with binary representation containing only negative powers
of M (the set H of numbers
with zero integer part) has
mostly fractional dimension (it is a „fractal”). The output of the program can be used to analyze
these sets. This means topologocal
analysis, e.g.
calculation of the dimension, connectedness etc. If we use
the matrix M above, we get
the following set.
Finally, knowing all matrices
up to a given
dimension could help us to
a deeper understanding of the mathematics
of generalized number systems.
For more detailed information about this project visit this
site.
Visit the project's homepage hosted by ELTE (Eötvös Loránd
University).