Enumeration of parallelograms in permutation matrices for improved bounds on the density of Costas arrays (Q259176)

Summary: A Costas array of order \(n\) is an \(n\times n\) permutation matrix such that all vectors between pairs of ones are distinct. Thus, a permutation matrix fails to be a Costas array if and only if it contains ones that form a (possibly degenerate) parallelogram. In this paper, we enumerate parallelograms in an \(n\times n\) permutation matrix. We use our new formulas to improve Davies's \(O(n^{-1})\) result for the density of Costas arrays.