Weight enumerator classifiers

Question

Let $f(x,y)$ be a polynomial with integer coefficients. What conditions guarantee that this is the weight enumerator of a binary linear code of size $n$ and dimension $k$?

I’m almost certain that the answer to this question is unknown...so instead i’ll settle for anything that is conjectural.

There’s a list of necessary conditions:

1. $f$ must be homogeneous of degree $n$ with non-negative coefficients.

2. The $x^n$ coefficient has to be $1$ since the zero vector is the unique weight $0$ vector.

3. The $y^n$ coefficient has to be $0$ or $1$ since the all $1$’s vector either belongs to the code or doesn’t.

4. The sum of the coefficients has to be $2^k$ since every vector has a unique weight and so is counted exactly once by some coefficient.

5. The MacWilliams transform ($g(x,y) = \frac{1}{2^k}f(x+y,x-y)$) has to have all of the above properties but with coefficient sum $2^{n-k}$ since if $f$ corresponds to a code then $g$ would correspond to the dual code.

Are there any more necessary conditions missing?

Answer 1

Although the OP has stated that he is not interested in only the case of (binary) self-dual codes but in linear codes in general, let us restrict ourselves to self-dual codes. Then the code must have even block length. Furthermore, a result of Gleason (A. M. Gleason, Weight Polynomials of Self-Dual Codes and the MacWilliams Identities, 1970 Act. Congr. Int. Math., vol. 3, pp. 211-215, Paris:Gauthier-Villars, 1971) says that the weight enumerator of such a code can be expressed as a polynomial in $x^2+y^2$ and $x^2y^2(x^2-y^2)^2 = x^6y^2-2x^4y^4+x^2y^6$. The shortest self-dual code is the $[2,1]$ repetition code with weight enumerator $$x^2+y^2 = 1\cdot\big(x^2+y^2\big) + 0\cdot\big(x^6y^2-2x^4y^4+x^2y^6\big).$$ The well-known $[8,4]$ Hamming code has weight enumerator $$x^8+14x^4y^4+y^8 = 1\cdot\big(x^2+y^2\big)^4 - 4\cdot \big(x^6y^2-2x^4y^4+x^2y^6\big)$$ However, not all polynomials in $x^2+y^2$ and $x^2y^2(x^2-y^2)^2$ that simplify to polynomials in $x$ and $y$ with all coefficients positive are necessarily weight enumerators of self-dual codes. For example, $$x^8+3x^6y^2+8x^4y^4+3x^2y^6 + y^8 = 1\cdot\big(x^2+y^2\big)^4 - 1\cdot \big(x^6y^2-2x^4y^4+x^2y^6\big)$$ is a solution to the MacWilliams identities with all coefficients being nonnegative but is not the weight enumerator of any self-dual code of length $8$.

If self-dual codes are restricted to having weights that are multiples of $4$, then Gleason's results say that the weight enumerator can be expressed as a polynomial in $x^8 + 14 x^4y^4 + y^8$ and $x^4y^4(x^4-y^4)^4 = x^{20}y^4-4x^{16}y^8+6x^{12}y^{12}-4x^{8}y{16}+x^4y^{20}.$ The simplest example is the $[8,4]$ Hamming code whose weight enumerator is $$x^8 + 14 x^4y^4 + y^8 = 1\cdot\big(x^8 + 14 x^4y^4 + y^8\big) + 0\cdot \big(x^{20}y^4-4x^{16}y^8+6x^{12}y^{12}-4x^{8}y{16}+x^4y^{20}\big).$$ The $[24,12]$ Golay code has weight enumerator $$x^{24}+759x^{16}y^8 + 2576x^{12}y^{12}+759x^8y^{16}+y^{24} = 1\cdot\big(x^8 + 14 x^4y^4 + y^8\big)^3-672\cdot\big(x^4y^4(x^4-y^4)^4\big)$$ but similar to the case of self-dual codes with even-weight codewords, one can find examples of solutions to the MacWilliams identities that have nonnegative coefficients but are not the weight enumerators of any self-dual code.

All this just illustrates Jyrki Lahtonen's point that finding sufficient conditions on polynomials that will guarantee the existence of a code with the specified weight enumerator is a very difficult task.