Squares of Random Linear Codes

DOI10.1109/TIT.2015.2393251MaRDI QIDQ2978722zbMATH OpenOpenAlexFDO

Authors Ignacio Cascudo, Ronald Cramer, Diego Mirandola, Gilles Zémor

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0848

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

f r a c 12 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 in

(12)

This page was built for publication: Squares of Random Linear Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978722)