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:
Source code is i C++, and compiles well under GCC. However it uses some GCC extensions like long long for 64-bit integers and therefore it needs some modifications to compile under other compilers.
g++ -O2 -o ruzsa ruzsa.C
Results and tables of Golomb rulers up to 65000 marks
Golomb 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:
n p l g mThe 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:
n: number of marks of the Golomb ruler found
p: prime number used for Ruzsa's construction
l: length of the resulting Golomb ruler
g: primitive element of Z_p used
m: multiplier used