**Squares of Random Linear Codes**

*Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Gilles Zémor*

**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.

**Category / Keywords: **foundations / Error-correcting codes

**Date: **received 3 Jul 2014, last revised 14 Jan 2015

**Contact author: **diego at cwi nl

**Available format(s): **PDF | BibTeX Citation

**Note: **Final version, to appear on IEEE Transactions on Information Theory

**Version: **20150114:152247 (All versions of this report)

**Short URL: **ia.cr/2014/520

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]