Weight distribution of random linear codes and Krawchouk polynomials

2022/05/04 by Samorodnitsky, Alex · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2205.02051

Abstract

For 0 < λ< 1 and n → ∞ pick uniformly at random λn vectors in \0,1\ⁿ and let C be the orthogonal complement of their span. Given 0 < γ< \frac12 with 0 < λ< h(γ), let X be the random variable that counts the number of words in C of Hamming weight i = γn (where i is assumed to be an even integer). Linial and Mosheiff determined the asymptotics of the moments of X of all orders o((n)/(log n)). In this paper we extend their estimates up to moments of linear order. Our key observation is that the behavior of the suitably normalized k^th moment of X is essentially determined by the k^th norm of the Krawchouk polynomial K_i.

Cited by

• On the Complexity of Decoded Quantum Interferometry

Related

• A note on random orthogonal polynomials on a compact interval
• Higher Moments for Polynomial Chowla
• Random linear combinations of functions from L₁
• Moments of characteristic polynomials for classical β ensembles
• Moments of moments of characteristic polynomials of random unitary matrices and lattice point counts