Integer Linear Programming Models for Subspace Codes and Finite Geomery

纠错码几乎用于所有形式的信息传输和存储。众所周知的例子包括与空间探测器、数字电视(DVB)、ADSL、分布式存储系统(Windows Azure)和CD播放器的通信。在互联网、智能手机和云计算等移动设备等通信网络中的大量应用，都需要独立于确切网络拓扑的数学理论。几年前，人们认识到，在某些情况下，通过使用多路数据分组，即在适当的有限域上的线性组合，可以显著提高吞吐量。如果通信模型中的错误也应该被纠正，那么有限向量空间的所有子空间的集合很适合作为字母表。这样，子空间码就是方便的子空间的子集。一个主要的研究方向是好的甚至是最优子空间码的存在和构造问题。这个问题是最新的，确实是欧盟成本行动IC1104的主题。将执行对子空间代码的穷举搜索。由有限向量空间的大量子空间和自同构群的大小引起的问题必须得到解决。为了将搜索空间缩小到合适的大小，将密集使用以前在Bayreuth研究组中应用的构造方法，该方法使用规定的自同构群的子群。其基本思想是将问题表述为整数线性方程组。这种描述很好地符合自同构的条件，因为它大大减少了变量的数量和约束的数量。有理由希望具有良好性质的子空间码具有一定的自同构。作为一项创新，应该找到更尖锐的整数公式。这里的基本思想是利用向量空间上的有限几何的结果和子结构。从算法的观点来看，这里使用的一些论点对应于添加可行的不等式或Gomory-Chvátal割平面。这里的主要思想是建模和枚举几何结构，如孔、切割或规则，并使用整数线性优化方法。对于所谓的(6，3，4)_2常维码的分类，可视为新战略方法的一个例子，其描述的过程可被视为新的战略方法的一个例子(见附录)。由于子空间码领域中的适度参数很少，因此有理由对每个参数都做出相当大的努力。然而，所有较小的案件都应进行系统的审查。即使在某些特殊情况下，障碍的改善也可以是一种进步。

Error-correcting codes are employed in almost every form of information transmission and storage. Well known examples include communication with space probes, Digital TV (DVB), ADSL, distributed storage systems (Windows Azure) and CD player. Numerous applications in communication networks such as the Internet, mobile devices like smartphones and cloud computing, require a mathematical theory that is independent of the exact network topology. A few years ago it was recognized that the throughput rates in certain situations can significantly be improved by using multiplexed data packets, i.e., linear combinations over a suitable finite field. If also errors shall be corrected in the communication model, the set of all subspaces of a finite vector space is well suited as an alphabet. With this a subspace code is a subset of convenient subspaces. One major research direction is the question of existence and construction of good or even optimal subspace codes. This problem is up-to-the-minute and indeed the topic of the EU COST Action IC1104. An exhaustive search of subspace codes will be performed. Problems, caused by the huge number of subspaces of a finite vector space and the size of the automorphism group, have to be tackled. The construction methods previously applied in the Bayreuth research group using prescribing a subgroup of the automorphism group, will be used intensively in order to reduce the search space to a convenient size. The underlying idea is to formulate the problem as an integer linear system of equations. This description fits well with the conditions of automorphisms, since it massively reduces both, the number of variables and the number of constraints. There is reason to hope that subspace codes with good properties have some automorphisms. As an innovation, sharper integer formulations shall be found. The basic idea here is to use results and substructures of finite geometry on vector spaces. From an algorithmic point of view, some of the arguments used there correspond to adding feasible inequalities or Gomory-Chvátal cutting planes. The main idea here is to model and enumerate geometric structures, such as holes, cuts, or regulus, and the use of methods of integer linear optimization. The procedure described in "T. Honold, M. Kiermaier, and S. Kurz. Optimal binary subspace codes of length 6, constant dimension 3 and minimum distance 4. 2014. to appear in the Proceedings of Fq 11" for the classification of so-called (6,3,4)_2 constant-dimension codes can be seen as an example for the new strategic approach (see appendix). Since there are very few moderate parameters in the area of subspace codes, it is justified to make a considerable effort for each of them. Nevertheless, all smaller cases shall be examined systematically. Even the improvement of barriers in some special cases can be a progress.