Parity check matrices and product representations of squares (Q949791)

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.