2024/10/06 by Minjia Shi, Xuan Wang, Shi, Minjia +5
Computer Science · Mathematics · #94B15 #Cellular Automata and Applications #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.2410.04412
openalex publication_date 2024/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the notion of logarithmically concave (or log-concave) sequences in Coding Theory. A sequence a0, a1, …, an of real numbers is called log-concave if ai2 ≥ ai-1ai+1 for all 1 ≤ i ≤ 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 Ai's where Ai 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 2r -1 (r=3 or r ≥ 5), the binary extended Hamming codes of length 2r ~(r ≥ 3), and the second order Reed-Muller codes R(2, m)~ (m ≥ 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 Fq satisfying 3 \leqslant k \leqslant n/2 +3 is log-concave if q \geqslant q0(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.