The Trifference Problem
M.J. van Donkelaar (TU Delft - Electrical Engineering, Mathematics and Computer Science)
DC Gijswijt – Mentor (TU Delft - Discrete Mathematics and Optimization)
Anurag Bishnoi – Mentor (TU Delft - Discrete Mathematics and Optimization)
Júlia Komjáthy – Graduation committee member (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.