Bounds on certain multiplications of affine combinations (Q1331901)

Let \(A\) and \(B\) be \(n \times n\) matrices the entries of which are affine combinations of the variables \(a_ 1, \dots, a_ m\), \(b_ 1, \dots, b_ m\) over GF(2). Suppose that for each \(i\), \(1 \leq i \leq m\), the term \(a_ i b_ i\) is an element of the product matrix \(C = A \cdot B\). For a given \(n\), let \(M(n)\) denote the maximum value that \(m\) can have. This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs. Let \(u = {1 \over 2} (\lceil n/3 \rceil - 1) (n - 1) (n - 2)\) and \(v = \sqrt {u^ 2 - {1 \over 27}}\). In this paper it is shown that for \(n \geq 4\), \[ M(n) \leq n(1 + \root 3\of {u + v} + \root 3\of {u - v}) = n^ 2/ {\root 3 \of {3}} + O(n) \] and \(M(2) = 2\), \(M(3) = 6\), and \(M(4) = 9\). Note that this problem has some connections with the so-called Zarankiewicz problem.