Integer Linear Programming Models for Subspace Codes and Finite Geomery

点击翻译按钮获取中文摘要

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.