Parity check matrices and product representations of squares (Q949791): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1007/s00493-008-2195-2 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00493-008-2195-2 / rank
 
Normal rank

Latest revision as of 09:32, 10 December 2024

scientific article
Language Label Description Also known as
English
Parity check matrices and product representations of squares
scientific article

    Statements

    Parity check matrices and product representations of squares (English)
    0 references
    0 references
    0 references
    21 October 2008
    0 references
    Let \(N_{F}(n,k,r)\) denote the maximum number of columns in an \(n\)-row matrix with entries in a finite field \(F\) in which each column has at most \(r\) nonzero entries and every \(k\) columns are linearly independent over \(F\). In this paper it is shown that \(N_{F}(n,k,r)\ll n^{r/2+cr/k}\) where \(c\approx 4/3\) for large \(k\) and \(a_n\ll b_n\) means that there exists a constant \(C>0\) such that for all \(n\), \(a_n\leq Cb_n\). The proof of this result is based on a novel reduction of the problem to the following Turán type problem: What is the maximum number of edges in an \(n\)-vertex graph which does not contain an even cycle of length \(2k\)? and the method yields a fast algorithm for finding short linear dependencies. Some applications of this method to a problem on hypergraphs which do not contain an even cover of a given size and a problem on product representations of squares in combinatorial number theory are presented.
    0 references
    0 references
    finite field
    0 references
    parity check matrix
    0 references
    linear dependency
    0 references
    even hypergraph cover
    0 references
    forbidden cycle
    0 references
    product representations of squares
    0 references
    Turan type problem
    0 references

    Identifiers