This web site was created as supportive material for my diploma thesis "An analysis of the Golomb ruler and the Sidon set problems, and determination of large near-optimal Golomb rulers", submitted to the department of Electronic and Computer Engineering at Technical University of Crete (June 2002). The discrete mathematics problems of
Sidon sets and Golomb rulers have been studied since the 1930's
and 1960's respectively by non-overlaping groups of researchers. The
main contribution of this diploma thesis was a study of the
relationship between the two problems and the computational
verification of a conjecture by Erdös on Sidon sets up to a much
larger bound than the one previously known.
All the the source code used and the resulting Golomb rulers
used for the proof of the main result of this thesis can be found at
the bottom of this page.What are Golomb rulers and Sidon sets? Golomb rulers are sets of positive integer numbers having all the differences between any pair of elements of the set to be unique. These numbers can be thought of as ruler marks (at integer locations) as an analogy with common rulers. Golomb rulers have many applications ranging from constructions for error correcting codes, to placement of radio telescopes in linear arrays. They were first studied by Babock in 1953 who was led to their definition to solve a problem in inteference between communication channels. Golomb was the first researcher to systematically study the subject in the 1960's and since then his name is associated with these constructions. The function G(n), referred to as the
length of an optimal
Golomb ruler , is defined as the smallest possible length of a
ruler
with n marks.Sidon sets or B2 sequences is a related problem from
combinatorial number theory. These sequences are subsets of 1,2,...,n
having distinct pairwise sums between the elements. Sidon sets are
named
after Fourier analyst Simon Sidon who defined these sets in order to
solve
a problem in harmonic analysis. Sidon communicated the problem
to Erdös who,
together with Paul Turan, made the first publication on the topic in
1934. It was Erdös who gave the name Sidon sets to these
constructions. The function F2(n) is defined as the largest number of element
which can be selected from the first n positive integers
forming a Sidon set. The full text of the thesis is available online in the
following formats:Diploma Thesis - Postscript file:
**main.ps.gz (1.1MB)** - PDF file:
**main.pdf (5.1MB)**
- PDF file:
**presentation.pdf (3.8MB)**
- PDF file:
**presentation.pdf (3.9MB)**
Source code is i C++, and compiles well under GCC.
However it uses some GCC extensions like Source Code long long for 64-bit
integers
and therefore it needs some modifications to compile under other
compilers.
- README.txt Instructions for running the software.
- ruzsa.cpp Uses Ruzsa's construction to find near-optimal Golomb ruler lengths.
- ruzsa-reconstruct.cpp Uses parameters from the previous program to construct the actual rulers.
- bose-fast.cpp Use's Bose-Chowla construction and finds near-optimal Golomb ruler lengths.
- bose-reconstruct.cpp Reconstructs the rulers from the data of the previous program.
- common.cpp Common subroutines used by all the following programs.
- sort.cpp Sorting functions
g++ -O2 -o ruzsa ruzsa.CGolomb rulers were found by exhaustive search of Ruzsa's
construction for up to 65000 marks. The resulting Golomb ruler sizes
are contained in the following file:Results and tables of Golomb rulers up to 65000 marks This text file contains 5 integer number in each line. The format of each line is: n p l g mwhere:
n: number of marks of the Golomb ruler foundp: prime number used for Ruzsa's constructionl: length of the resulting Golomb rulerg: primitive element of Z_p usedm: multiplier used The actual Golomb rulers are not contained since it
would require about 20GB of storage. The first 1000 Golomb rulers are
contained in the following file:For the remaining Golomb rulers use the ruzsa-reconstruct
program with suitable parameters to find the actual rulers. Or type
here the number of marks and the resulting Golomb ruler will be
returned:Related Sites
(for more information contact me at the
email address shown at the top of this page)Back to my home page Dimitromanolakis Apostolos |