Cryptology ePrint Archive: Report 2014/520

On powers of codes

Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Gilles Z\'emor

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

Contact author: diego at cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20140703:180838 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]