Algebraic Geometry Modeling in Information Theory

The following sections are included:

• Preface

• Contents

This brief paper surveys recent work in Sage, a free and open-source mathematics package, on implementing algorithms to compute with linear block codes and cryptography. The paper ends with a “wish-list” of coding-theoretic functionality that the author hopes will be added to Sage in the not-too-distant future.

This chapter gives an introduction to basic network coding and treats the estimation of success probability when linear encoding functions are chosen by random in an error-free acyclic network. With regard to the latter we give a coherent description.

Steganography is the science of invisible communications. It is a very old method that, thanks to recent progress, has begun to play an important role as an alternative and as a complement of Cryptography. This Chapter presents an introduction to the objectives, the methods and some open problems of Steganography, conducted from a Coding Theory point of view.

The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.

A numerical semigroup is a subset of ℕ containing 0, closed under addition and with finite complement in ℕ. An important example of numerical semigroup is given by the Weierstrass semigroup at one point of a curve. In the theory of algebraic geometry codes, Weierstrass semigroups are crucial for defining bounds on the minimum distance as well as for defining improvements on the dimension of codes. We present these applications and some theoretical problems related to classification, characterization and counting of numerical semigroups.

This chapter treats error-correcting codes and their weight enumerator as the center of several closely related topics such as arrangements of hyperplanes, graph theory, matroids, posets and geometric lattices and their characteristic, chromatic, Tutte, Möbius and coboundary polynomial, respectively. Their interrelations and many examples and counterexamples are given. It is concluded with a section with references to the literature for further reading and open questions.