^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} CWI Amsterdam^{3} CWI, Amsterdam^{4} Institut de Mathematiques de Bordeaux^{5} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1109/TIT.2015.2393251

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.

Type:

Journal article

Language:

English

Published in:

I E E E Transactions on Information Theory, 2015, Vol 61, Issue 3, p. 1159-1173