Log-Concave Sequences in Coding Theory

Minjia Shi, Xuan Wang, Junmin An, Jon-Lark Kim

Abstract

We introduce the notion of logarithmically concave (or log-concave) sequences in Coding Theory. A sequence $a_0, a_1, \dots, a_n$ of real numbers is called log-concave if $a_i^2 \ge a_{i-1}a_{i+1}$ for all $1 \le i \le n-1$. A natural sequence of positive numbers in coding theory is the weight distribution of a linear code consisting of the nonzero values among $A_i$'s where $A_i$ denotes the number of codewords of weight $i$. We call a linear code log-concave if its nonzero weight distribution is log-concave. Our main contribution is to show that all binary general Hamming codes of length $2^r -1$ ($r=3$ or $r \ge 5$), the binary extended Hamming codes of length $2^r ~(r \ge 3)$, and the second order Reed-Muller codes $R(2, m)~ (m \ge 2)$ are all log-concave while the homogeneous and projective second order Reed-Muller codes are either log-concave, or 1-gap log-concave. Furthermore, we show that any MDS $[n, k]$ code over $\mathbb F_q$ satisfying $3 \leqslant k \leqslant n/2 +3$ is log-concave if $q \geqslant q_0(n, k)$ which is the larger root of a quadratic polynomial. Hence, we expect that the concept of log-concavity in coding theory will stimulate many interesting problems.

Introduction

In coding theory, the weight distribution of a linear code is a fundamental sequence $A_0, A_1, \dots, A_n$, where $A_i$ represents the number of codewords with Hamming weight $i$. This distribution is critical for determining the code's error-correcting performance, yet it is often computationally difficult to determine for arbitrary codes. This paper bridges algebraic combinatorics and coding theory by introducing the concept of log-concavity to these sequences.

A sequence is defined as log-concave if the square of any term is at least as large as the product of its neighbors ($a_i^2 \ge a_{i-1}a_{i+1}$). This property is mathematically powerful because it implies unimodality—the sequence rises to a single peak and then falls, without internal fluctuations or "bumps."

The Log-Concavity Property

Log-concavity is a strong structural property that has recently seen major breakthroughs in combinatorics, particularly regarding matroids. Given that linear codes are intimately related to vector matroids, the authors investigate whether this property is inherited by the code's weight distribution.

Logarithmic scatterplot of sequence A010086(n), illustrating the characteristic unimodal 'bell' shape of a log-concave sequence.

As shown in Figure 1, a log-concave sequence typically exhibits a smooth, parabolic shape when plotted on a logarithmic scale. A critical insight of this research is the focus on the nonzero weight distribution. Many codes (such as even-weight codes) have zeros in their distribution (e.g., $1, 0, 6, 0, 1$), which would trivially violate the log-concavity condition. By analyzing only the nonzero terms, the authors reveal a hidden, underlying regularity in the "shape" of codeword weights.

Analysis of Fundamental Code Families

The researchers employed a mix of analytical proofs using explicit formulas (such as the MacWilliams identity) and computational verification using the Magma algebra system.

Hamming and Reed-Muller Codes

Binary Hamming codes of length $2^r - 1$ were found to be log-concave for $r=3$ and $r \ge 5$. Interestingly, the $r=4$ case (length 15) is an exception, being "2-gap log-concave," meaning the property holds for all but two indices. Extended Hamming codes, which include an additional parity bit, are log-concave for all $r \ge 3$. Furthermore, second-order binary Reed-Muller codes $R(2, m)$ are log-concave for all $m \ge 2$.

Weight distribution table for a linear code, showing the frequency $A_i$ for each weight $i$.

Figure 2 provides an empirical example of a weight distribution table. Such data served as the basis for identifying patterns that were later formalized into general theorems. The table illustrates the rapid growth and eventual decline of codeword frequencies, a hallmark of the unimodal distributions studied here.

MDS Codes and Field Size

For Maximum Distance Separable (MDS) codes, log-concavity is not universal but depends on the field size $q$. The authors established that any $[n, k]$ MDS code over $\mathbb{F}_q$ where the dimension $k$ is roughly half the length ($3 \le k \le n/2 + 3$) is log-concave, provided the field size $q$ is sufficiently large (specifically, larger than the root of a certain quadratic polynomial).

Conclusion and Future Work

The discovery of log-concavity in these fundamental code families introduces a new structural frontier in coding theory. While some famous codes, like the binary Golay code of length 23, fail the test (it is 2-gap log-concave), the property is remarkably prevalent in Hamming and Reed-Muller families. Future research will explore whether log-concavity can be used to provide tighter bounds on error probability and if other sequences, such as coset leader weight distributions, exhibit similar mathematical discipline.

Summary updated

Abstract

We introduce the notion of logarithmically concave (or log-concave) sequences in Coding Theory. A sequence $a_0, a_1, \dots, a_n$ of real numbers is called log-concave if $a_i^2 \ge a_{i-1}a_{i+1}$ for all $1 \le i \le n-1$. A natural sequence of positive numbers in coding theory is the weight distribution of a linear code consisting of the nonzero values among $A_i$'s where $A_i$ denotes the number of codewords of weight $i$. We call a linear code log-concave if its nonzero weight distribution is log-concave. Our main contribution is to show that all binary general Hamming codes of length $2^r -1$ ($r=3$ or $r \ge 5$), the binary extended Hamming codes of length $2^r ~(r \ge 3)$, and the second order Reed-Muller codes $R(2, m)~ (m \ge 2)$ are all log-concave while the homogeneous and projective second order Reed-Muller codes are either log-concave, or 1-gap log-concave. Furthermore, we show that any MDS $[n, k]$ code over $\mathbb F_q$ satisfying $3 \leqslant k \leqslant n/2 +3$ is log-concave if $q \geqslant q_0(n, k)$ which is the larger root of a quadratic polynomial. Hence, we expect that the concept of log-concavity in coding theory will stimulate many interesting problems.
BibTeX
@misc{shi2024log,
  author = {Minjia Shi and Xuan Wang and Junmin An and Jon-Lark Kim},
  title = {{Log-Concave Sequences in Coding Theory}},
  year = {2024},
  eprint = {2410.04412},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.04412},
}
Figure