Аннотация:We prove a lower bound on the maximal possible weight of a (k,l)-free (that is, free of all-ones k×l submatrices) Boolean circulant N×N matrix. The bound is close to the known bound for the class of all (k,l)-free matrices. As a consequence, we obtain new bounds for several complexity measures of Boolean sums' systems and a lower bound Ω(N^2 / log^6 N) on the monotone complexity of the Boolean convolution of order N.
