On the asymptotic existence of partial complex Hadamard matrices and related combinatorial objects

AbstractA proof of an asymptotic form of the original Goldbach conjecture for odd integers was published in 1937. In 1990, a theorem refining that result was published. In this paper, we describe some implications of that theorem in combinatorial design theory. In particular, we show that the existence of Paley's conference matrices implies that for any sufficiently large integer k there is (at least) about one third of a complex Hadamard matrix of order 2k. This implies that, for any ε>0, the well known bounds for (a) the number of codewords in moderately high distance binary block codes, (b) the number of constraints of two-level orthogonal arrays of strengths 2 and 3 and (c) the number of mutually orthogonal F-squares with certain parameters are asymptotically correct to within a factor of 13(1−ε) for cases (a) and (b) and to within a factor of 19(1−ε) for case (c). The methods yield constructive algorithms which are polynomial in the size of the object constructed. An efficient heuristic is described for constructing (for any specified order) about one half of a Hadamard matrix