On lower bounds on the size of sums-of-squares formulas

Abstract: For sums-of-squares formulas of the form where the are bilinear functions of the and . Let denote the smallest possible value of t allowing such a formula to hold. We have two well-known lower bounds on the size of . One was obtained independently by Hopf and Stiefel, and another by Atiyah. These bounds are given by requiring certain binomial coefficients be divisible by certain powers of 2. Although the behavior of the Hopf–Stiefel bound is fairly well understood, the Atiyah bound is not. In this paper we provide an efficient algorithm for computing the Atiyah bound and some results on which of the lower bounds is larger. [Copyright &y& Elsevier]