Squares of Random Linear Codes

Abstract

Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code "typically" fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $\frac{1}{2}{k}^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

Cited by in corpus (10)

• On squares of cyclic codes
• Critical pairs for the Product Singleton Bound
• Squares of Matrix-product Codes
• On the security of subspace subcodes of Reed-Solomon codes for public key encryption
• On asymptotically good ramp secret sharing schemes
• Algebraic geometry codes and some applications
• How arithmetic and geometry make error correcting codes better
• A Polynomial-Time Attack on the BBCRS Scheme
• Linear independence of rank 1 matrices and the dimension of *-products of codes
• A geometric invariant of linear rank-metric codes