Schrijver’s SDP Bound for Network Codes

This is a small report on a failed project — obtaining semidefinite programming bounds on constant dimension network codes. But let us start with some context …

A network code consists of a set of subspaces in [latex]\mathbb{F}_q^n[/latex]. It is a code, so we want to maximize the distance between subspaces (or increase the code’s cardinality or rate). The most reasonable metric for this is the subspace metric in which two subspaces [latex]U[/latex] and [latex]W[/latex] have distance [latex]\dim(U+W) – \dim(U \cap W)[/latex], that is the shortest distance between [latex]U[/latex] and [latex]W[/latex] in the subspace lattice. These codes are used in random linear network coding, that is a method for the many-to-many transmission of data in a network which is faster than multiple one-to-one connections. As in classical coding theory, one area of research on those subspace codes is concerned with bounding the maximal size of a code with minimum distance [latex]d[/latex] in [latex]\mathbb{F}_q^n[/latex]. Notice that one can interpret [latex]q=1[/latex] as a field with one element as is explained here by Peter Cameron. Then it corresponds to classical coding theory.

One method for bounding codes is Delsarte’s linear programming (LP) bound. Delsarte noticed in his PhD thesis (written in 1973) that one can very efficiently calculate Lovász’ theta function (only defined later in 1979) in so-called association schemes, where it corresponds to a very small linear program. Classical coding theory works on subsets of [latex]\{ 1, \ldots, n \}[/latex], which is an association scheme. This makes it possible to calculate the LP bound very efficiently for relatively large n and d. If we go from coding theory to network coding theory, then we go from subsets of [latex]\{ 1, \ldots, n \}[/latex] to subspaces of [latex]\mathbb{F}_q^n[/latex]. This is no longer an association scheme, but a coherent configuration and in coherent configurations Lovász’ theta function corresponds to a small semidefinite program (SDP). Sylvia Hobart and Jason Williford described this nicely in Delsarte’s style of notation.

These SDP bounds for network codes were first calculated by Bachoc, Passuello and Vallentin for small [latex]n[/latex], [latex]q=2[/latex] or [latex]d[/latex] odd. Now a few months ago I met Daniel Heinlein at the conference Combinatorics 2018 in Arco, Italy, and he told me that he would like to update the results by Bachoc et al. One reason for this is that they did not cover [latex]q > 2[/latex] and [latex]d[/latex] even. Another reason is that since their paper was published, many better bounds on codes on [latex]k[/latex]-spaces of [latex]\mathbb{F}_q^n[/latex] were obtained. Daniel wanted to add these additional constraints, coming from bounds on constant dimension codes, to the SDP and obtain better bounds. Indeed, this worked out very well. We now have a paper on the arXiv and we are now the record holders for many upper bounds. You can find the best known bounds for subspace codes under http://subspacecodes.uni-bayreuth.de/, a website primarily maintained by Daniel.

So this was a successful project. Where is the failed project?

Schrijver noticed based on previous work of him together with Lovász, that Delsarte’s LP bound for codes can be improved if we refine the optimization problem by fixing one code word [latex]c[/latex] and considering all the other code words in relation to [latex]c[/latex]. For constant weight codes Schrijver used this to obtain many new bounds and for the following I will call this type of bound Schrijver’s SDP bound. For example if we look at codes of length 17, weight 7 and minimum distance 6, then Delsarte’s LP bound gives an upper bound of 249, other techniques at the time of Schrijver’s paper gave 234, Schrijver’s SDP bound improved this to 228, and, extending Schrijver’s method, the current best is due to Polak with 206 from last year. It is worth mentioning that Schrijver needed the so-called Terwilliger algebra/centralizer algebra of the corresponding graph to calculate some of the semidefinite matrices for the SDP.

So this is promising! Let us do the same for network codes, for instance for 7-dimensional spaces in [latex]\mathbb{F}_2^{17}[/latex] and minimum distance 6. This is where the problems started. As far as I could tell, this the centralizer algebra for vector spaces was not known in sufficient detail, so Maarten de Boeck, a colleague of mine and fellow postdoc at Ghent University, and I started calculating it. But then I went to a research stay to the Tohoku University, Sendai, Japan. There I talk to my host, Hajime Tanaka, and he tells me that a former student of his, Yuta Watanabe, already did all of this in his Master thesis! Indeed, the centralizer algebra for vector spaces was calculated in disguise by Dunkl in 1978 and Watanabe explains this nicely in his thesis (which does not seem to be online, so I can only give you my word for it which you can find on his homepage).

Now we are all set and can run an SDP solver! But what happens? Delsarte’s LP bound and Schrijver’s SDP bound turn out to be the same for all the tested parameters. Failure!

Of course I wanted to rule out any errors on my part, so I used the fact that Dunkl’s formulas work for all [latex]q > 1[/latex], not just prime powers. If I did everything correctly, then Schrijver’s SDP should approach the value 228 in Schrijver’s paper for [latex]q \rightarrow 1[/latex] as [latex]q=1[/latex] corresponds to the classical case. This actually happens:

Therefore, I did (most likely) everything correctly and the Schrijver’s SDP is just not better than Delsarte’s LP bound for network codes — at least for the small parameters which I tested, but even 1450279444830258 is already quite gigantic. This concludes my report on this failed project.

What is the outlook? Using higher moments such as Polak for his bound of 206 might help (see Section 4.3 here). But here we have no centralizer algebra to use, so I am not sure if any calculations are currently feasible.

Acknowledgements: I thank Daniel Heinlein and Hajime Tanaka for their comments on a draft of this document.

Bonus Question: The field with one element has its own Wikipedia article. But what is a field with 1.01 elements?

Update: Yuta Watanabe’s Master thesis is now online on his homepage.

Follow the blog!