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 .