Monthly Archives: October 2011

An independent discovery of Costas arrays

In today’s post, I will discuss a little-known combinatorics paper by E.N. Gilbert from 1965, in which he independently discovered the “logarithmic Welch” construction of Costas arrays.  Costas arrays are named after the late IEEE fellow John Costas, whose seminal paper on what are now called Costas arrays appeared, coincidentially, in 1965, the same year as Gilbert’s paper.  I had never heard of Costas arrays until just a few weeks ago, when I needed a combinatorial object with their properties for a problem I am trying to solve about error-prevention in molecular self-assembly.  So I approached the literature in a nonstandard way, found Gilbert’s paper, and eventually wrote experts on Costas arrays to confirm that Theorem 6 of Gilbert’s Latin Squares Which Contain No Repeated Digrams did indeed produce a construction that independently appeared in the literature “for the first time” in 1982.  Therefore, my objective with this blog post is twofold: (1) to make better known an area of combinatorics that may be familiar to information theorists but not to computer scientists; and (2) to change in a small way the intellectual history of this area, so Gilbert is recognized as a co-inventor of an important class of combinatorial designs.  (ADDED LATER: It appears I may have accomplished (2).  The Wikipedia page on Gilbert now states that he was a co-inventor of Costas arrays, and cites this blog entry as justification.  This is my first Wikipedia citation, to my knowledge.  Somewhere along the way, I seem to have morphed from off-the-wall commentator to reliable source.)

First, though, a quick pointer for anyone interested in DNA computation: Dave Doty just contributed an entry to the CSTheory Community Blog on the DNA Computing conference that took place last month at CalTech.  Dave was on the local arrangements committee, and, in his post, he talks about both technical results presented at the conference, and suggestions for organization of future CS conferences.  Good stuff. Continue reading