In the previous post, we saw the problem of determining the asymptotic growth of the function , which is the largest size of vector subspace
, with the property that for any three distinct vectors
in
, there is a coordinate
, such that
. A code
with these properties is called a linear trifferent code. Note that,
, and thus it suffices to study the largest dimension of such codes.
In this post, I will show that linear trifferent codes are in fact related to another well-studied notion in coding theory, minimal codes.
A (linear) code is a
-dimensional subspace of
such that every codeword has at least
non-zero coordinates. The classic problem in coding theory is to understand the trade-off between
and
, as
corresponds to the error-correcting capabilities of the code, and
corresponds to the amount of information that can be transferred. Asymptotically, for a family of codes with parameters
, we want to understand the trade-off between the rate
and the relative distaudimennlesnce
. Any family with both
and
strictly bigger than
, is called an asymptotically good family.
A non-zero codeword in
is called minimal, if there is no non-zero codeword
such that the set of coordinates where
is non-zero is a proper subset of the set of coordinates where
is non-zero. For example, in the
code
generated by the vectors
and
, the vector
is a minimal codeword while
is not. Minimal codes are linear codes in which all codewords are minimal. For example, any linear code where all vectors have the same number of non-zero coordinates is automatically minimal, but they can be much more interesting than that example. Over the binary field
, coincidentally, a minimal code is equivalent to an intersecting code (where the support of any two vectors intersects non-trivially), which have been studied extensively since 1980s, due to various theoretical and applied reasons. But over larger fields, minimal codes have not been so well-studied. In an earlier post, I talked about the work of Alfarano, Borello, Neri and Ravagnani, who showed that every minimal
code satisfies
.
The first statement shows that any infinite family of minimal codes where is a linear function of
, must be asymptotically good. Therefore, it is very interesting to construct such families. In my work with Noga Alon, Shagnik Das, and Alessandro Neri (that we will hopefully upload on arXiv by next month), we give the first explicit construction of minimal
codes where
for some absolute constant
, using expander graphs. I will talk about this construction in a later post.
With all of this discussion around minimal codes, it is not at all clear what they might have to do with linear trifferent codes. Well, it turns out these two are the same objects over . This is not something I expected when I started working on the trifference problem! Here is a short proof from my paper with Jozefien, Dion and Aditya:
Theorem 1. Let be a vector subspace of
. Then
is a trifferent code if and only if it is a minimal code.
Proof. First suppose that is not minimal. Then there exist distinct nonzero codewords
with
.
Let , which must also lie in
as
is linear.
Then there is no index such that
, since
implies
and
. We conclude that
is not a trifferent code.
For the other direction, suppose that is a minimal linear code. Say
is not a trifferent code.Then there exist distinct codewords
such that there is no coordinate in which they all have a different value.
Consider the vectors and
, which all belong to
because
is linear. The first two vectors are non-zero because
and
. We first show that
is also a non-zero vector. As
and
are distinct, there is an
such that
.
Since must be equal to
or
, it follows that
is either equal to
or
, which are both non-zero.
This also shows that is not a scalar multiple of
, and thus
.
We now show that is a subset of
. Let
such that
. We need to show that
. Since
, we must have the following two cases: (i)
and
; (ii)
and
.
In the first case , which is non-zero. In the second case,
, which is also non-zero. Similarly, we can show that
is also a subset of
. Since
is not equal to
, at least one of them must be a proper subset of
, which contradicts the minimality of
.
From this new equivalence, it follows that determining is equivalent to determining the largest dimension
of a minimal
-code of length
, which gives us a new way of attacking this problem. In fact, finding the largest dimension
of a minimal code of length
is equivalent to a finite geometric problem on something called a strong blocking set. In the next post, I will show how to improve the current best bounds on these blocking sets over arbitrary finite fields. When restricted to
, these improvements will imply the new bounds on
that I described in my previous post. In particular, I will prove the following two theorems.
Theorem 2. For every prime power there is a constant
such that every linear minimal code of length
and dimension
satisfies
, for large enough
.
Theorem 3. For every prime power , there exists a linear minimal
-dimensional code of length
with
.