% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Enumeration of Parallelograms in Permutation Matrices for Improved Bounds on the Density of Costas Arrays}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Christopher N. Swanson\\
\small Ashland University\\[-0.8ex]
\small Ashland, OH\\
\small\tt cswanson@ashland.edu\\
\and
Bill Correll, Jr.\\
\small MDA Information Systems LLC\\[-0.8ex]
\small Ypsilanti, MI\\
\small\tt william.correll@mdaus.com\\
\and
Randy W. Ho\\
\small Garmin International\\[-0.8ex]
\small Chandler, AZ\\
\small\tt googlypower@gmail.com
}

% \date{\dateline{submission date}{acceptance date}{publication date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{October 2, 2015}{February 2, 2016}\\
\small Mathematics Subject Classifications: 05A05, 05B30}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
A Costas array of order $n$ is an $n$ x $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$ x $n$ permutation matrix.  We use our new formulas to improve Davies's $O(n^{-1})$ result for the density of Costas arrays.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Costas array; Permutation; Enumeration
\end{abstract}

\section{Introduction}
In 1965, John P. Costas introduced a special class of permutations of $n$ elements with applications to improving the target detection performance of radar and sonar systems \cite{Costas}, \cite{Costas2}.  Edgar Gilbert also wrote about this special class of permutations in the same year, referring to them as permutations with distinct differences and devising a construction method for certain values of $n$ \cite{Gilbert}.  Today, these permutations are referred to as Costas arrays and mathematicians and engineers alike have been studying these structures in an attempt to answer some fundamental questions about them, such as how to construct these arrays, whether these arrays exist for all $n$, and how many distinct Costas arrays of order $n$ exist. Readers interested in more details regarding the applications of Costas arrays in target detection should read Section III of \cite{BarkerEtAl}.   

A \textit{Costas array} of order $n$ is an $n \times n$ matrix of ones and zeroes such that there is exactly one 1 per row and column (i.e., it is a permutation matrix) and such that all vectors between pairs of ones are distinct, i.e., if the permutation matrix has 1's at $(i_k,j_k)$ for $k=1, 2, 3, 4$ and if $i_1-i_2=i_3-i_4$ and $j_1-j_2=j_3-j_4$, then $(i_1,j_1)=(i_3,j_3)$ and $(i_2,j_2)=(i_4,j_4)$.  Thus, a permutation matrix fails to be a Costas array if and only if it contains (at least 3) 1's that form a (possibly degenerate) parallelogram.

One easy way to check if a given permutation matrix is a Costas array is to consider its corresponding permutation and form a triangular difference table of values where the first row of the table contains the differences between the elements of the permutation that are adjacent, the second row contains the differences between the elements that are 2 places apart, etc.  Then the permutation matrix is a Costas array if and only if the entries in each row of the triangular difference table are distinct.  For example, consider the permutation 1243.  Its triangular difference table and corresponding matrix are

\begin{align*}
\begin{matrix}
-1&-2&1\\
-3&-1&\\
-2& &\\
\end{matrix} \qquad
A=\begin{bmatrix}
1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\
\end{bmatrix}
\end{align*}
Since no row of this table has repeated entries, the permutation matrix $A$ for 1243 is a Costas array.  Alternatively, consider the permutation 3214.  Its triangular difference table and corresponding matrix are

\begin{align*}
\begin{matrix}
1&1&-3\\
2&-2&\\
-1& & \\
\end{matrix} \qquad
B=\begin{bmatrix}
0&0&1&0\\0&1&0&0\\1&0&0&0\\0&0&0&1\\
\end{bmatrix}
\end{align*}
Since the first row of this table contains the difference 1 twice, the permutation matrix $B$ for 3214 is not a Costas array.

In this paper we count how many parallelograms of 1's are possible in an $n \times n$ permutation matrix.  At first glance, this might seem like a tangential enumerative problem.  However, by understanding the ways a permutation matrix fails to be a Costas array, we are led towards new insights about density among permutation matrices and enumeration.   The proofs of our formulas make use of a geometric fact about quadrilaterals and a binomial coefficient identity known as the hockey-stick identity.

\section{Challenges and Enumerative Progress}
\label{Challenges}
In 1984, S. Golomb, using previously available empirical constructions, stated and proved two algebraic construction methods for Costas arrays based on finite fields, known as the Golomb and Welch methods \cite{golomb}, \cite{golombtaylor} (Gilbert's construction in \cite{Gilbert} is the logarithmic Welch construction.)  These remain the only general constructions available and work for infinitely many orders due to the infinitude of primes, but not all orders. It was then that Costas arrays acquired their present name and became an object of study (see \cite{survey} for more details and a summary of results).

\begin{table}
\centering
\caption{Number of Costas arrays $C(n)$ as a function of order $n$}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
n & C(n) & n & C(n) & n & C(n) & n & C(n) & n & C(n)\\
\hline \hline
1 & 1 & 7 & 200 & 13 & 12828 & 19 & 10240 & 25 & 88\\
\hline
2 & 2 & 8 & 444 & 14 & 17252 & 20 & 6464 & 26 & 56\\
\hline
3 & 4 & 9 & 760 & 15 & 19612 & 21 & 3536 & 27 & 204\\
\hline
4 & 12 & 10 & 2160 & 16 & 21104 & 22 & 2052 & 28 & 712\\
\hline
5 & 40 & 11 & 4368 & 17 & 18276 & 23 & 872 & 29 & 164\\
\hline
6 & 116 & 12 & 7852 & 18 & 15096 & 24 & 200 &  30 & ? \\
\hline
\end{tabular}
\label{Costascount}
\end{table}

The challenges of enumerating Costas arrays and improving estimates of their asymptotic density are two of the four core challenges of Costas arrays\cite{openproblems}.  It is not known if Costas arrays of all orders exist.  Besides arrays from the constructions that have been devised, sporadic arrays not arising from known constructions have also been found in exhaustive computer searches.  Massively-distributed backtracking searches \cite{count27}\cite{count28}\cite{Costas29} in recent years have helped to identify all Costas arrays for $n \leq 29$.  The search for $n=29$ required the equivalent of 366.55 years for a single CPU \cite{Costas29}.  Define $C(n)$ to be the number of Costas arrays of order $n$.  All known values of $C(n)$ are given in Table~\ref{Costascount}.  Correll \cite{BCenum} used M\"obius inversion to establish a theoretical formula for $C(n)$, but the resulting summands are impractical to evaluate. James Beard has tabulated all known Costas arrays out to $n=500$ \cite{spreadsheet500}.  Discovery of arrays up to and including order 31 has been achieved but it is not known if any Costas arrays of order $32$ or $33$ exist.  Aggressive computing with an efficient new recursive approach \cite{recursiveway} to $C(n)$ may change this, however.    Verification of the Costas property for a candidate permutation of order $n$ involves $O(n^3)$ comparisons; therefore, the decision problem ``Is $C(n) > 0$?'' is in NP \cite{openproblems} \cite{BarkerEtAl}.   

\section{Violating Configurations}

Davies, within \cite{survey}, notes that a permutation matrix fails to be a Costas array if it contains 3 equally-spaced collinear ones.  Davies referred to these configurations as \textit{$L_3$-configurations}.  An $L_3$-configuration is not the only configuration of ones whose existence prevents a permutation matrix from being a Costas array.  Four ones that form a non-degenerate parallelogram have this property.  We will refer to such sets of ones as \textit{$P_4$-configurations}.  
Two equally-spaced pairs of ones forming four distinct ones, all of which are collinear, form a degenerate parallelogram and also have this property.  We will refer to such sets of ones as \textit{$L_4$-configurations}.  One may think of an $L_3$-configuration as a degenerate $L_4$-configuration in which two ones overlap.

For the 4 permutation matrices below, matrix $A$ is a Costas array, matrix $B$ is not a Costas array as it contains an $L_3$-configuration, matrix $C$ is not a Costas array as it contains a $P_4$-configuration and matrix $D$ is not a Costas array as it contains an $L_4$-configuration (as well as two $L_3$-configurations).

\begin{align*}
A=\begin{bmatrix}
1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\
\end{bmatrix}
B=\begin{bmatrix}
0&0&1&0\\0&1&0&0\\1&0&0&0\\0&0&0&1\\
\end{bmatrix}
C=\begin{bmatrix}
0&0&1&0\\1&0&0&0\\0&0&0&1\\0&1&0&0\\
\end{bmatrix}
D=\begin{bmatrix}
1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\
\end{bmatrix}
\end{align*}

For $n \geq 3$, Davies showed that the number of $L_3$-configurations when considering permutations of $n$ elements is  

%Removes some awkward spacing and puts even first to be consistent with other piecewise definitions
\begin{equation*}\label{l3expression}
l_3(n) = 
\begin{cases}
    \frac{1}{8}n^2(n-2)^2 & , n \mbox{ even}\\
    \frac{1}{8}(n-1)^4 & , n \mbox{ odd}
  \end{cases} 
\end{equation*}

%\begin{align*}\label{l3expression}
%l_3(n) = \left\{
%        \begin{array}{ll}
%            \frac{1}{8}(n-1)^4 & \quad , n \mbox{ odd} \\[1em] 
%            \frac{1}{8}n^2(n-2)^2 & \quad ,  n \mbox{ even}
%        \end{array}
%    \right.
%\end{align*}

He derived this by considering the placement of the endpoints of an $L_3$-configuration--see \cite{survey} for details.  We created an entry in the Online Encyclopedia of Integer Sequences (OEIS, \url{http://oeis.org/}) for $l_3(n)$ which was merged into A212892.  The two distinct descriptions of the same sequence suggest the following:

\textbf{Problem:}  Let $n \geq 3 $ be a positive integer.  Let $A(n)$ be the number of ordered 4-tuples $(w,x,y,z)$ of positive integers such that $w,x,y,z \in \{0,1,\ldots,n\}$ with the differences $w-x, x-y,$ and $y-z$ all odd.  Show that $A(n-2) = l_3(n)$.

\textbf{Proof:}  Consider a 4-tuple $(w,x,y,z)$ with the desired property.  By parity arguments, the 4-tuple must be of the form (E,O,E,O) or (O,E,O,E) where O and E denote odd and even integers drawn with replacement from $\{0,1,\ldots,n\}$.  It follows that $A(n) = 2e(n)^2o(n)^2$ where $e(n)$ is the number of even integers in the set and $o(n) = n+1 - e(n)$ is the number of odd integers in the set.  It is readily seen that $e(n)$ equals $(n+2)/2$  if $n$ is even and $(n+1)/2$ if $n$ is odd and that $o(n)$ equals $n/2$ if $n$ is even and $(n+1)/2$ if $n$ is odd, so the result follows.  

So why should we care about violating configurations?  Davies studied the the random variable $X$ counting $L_3$-configurations in a permutation matrix to prove the strongest-known result about the density $\frac{C(n)}{n!}$ of Costas arrays among permutation matrices.  He showed that $\frac{C(n)}{n!} = O(\frac{1}{n})$ as $n \rightarrow \infty$ using the second moment method, thus settling Unsolved Problem 5 in {\cite{golombtaylor}}.  Davies reasoned that

\begin{align*}
\frac{C(n)}{n!} \leq  P(X=0) \leq P(|X - \mathbb{E}(X)| \geq \mathbb{E}(X)) \leq \frac{\mathbb{E}(X^2)}{\mathbb{E}^2(X)} - 1
\end{align*}
where the right-hand inequality follows from Chebyshev's Inequality.    From the formula for $l_3(n)$ it follows that $\mathbb{E}(X)=\frac{l_3(n)}{n(n-1)(n-2)}$.  Davies completed his proof by devising an upper bound on the second moment $\mathbb{E}(X^2)$ of $X$ as a function of $n$ by reasoning about how two $L_3$-configurations intersect.  Table \ref{Costascount} supports the stronger conjecture that $\frac{C(n)}{n!}$ has exponential decay \cite{BCexp}, \cite{KDexp}. 

As Davies's result only used $L_3$-configurations, it may be possible to improve on the upper bound of the asymptotic behavior of the density of Costas arrays by applying a similar technique that incorporates $P_4$-configurations and/or  $L_4$-configurations.  In order to do this, it is first necessary to determine how many $L_4$- and $P_4$-configurations exist in permutation matrices of order $n$, the theorems we present in this paper.

\section{Configuration Enumeration}\label{secreqenum}

Let $l_4(n)$ and $p_4(n)$ denote the numbers of $L_4$- and $P_4$-configurations when considering permutations of $n$ elements,  respectively.  Our main results are

\begin{theorem}\label{FirstEnumThm}
For $n > 3$,

\begin{align*}
l_4(n) = 2\sum_{a=1}^{n-1}\sum_{b=1}^{n-1}(n-a)(n-b)\left\lfloor\frac{\gcd(a,b)-1}{2}\right\rfloor
\end{align*}

\end{theorem}

\begin{theorem}\label{SecondEnumThm}
For $n > 3$,

\begin{equation*}\label{l4p4sumresult}
l_4(n) + p_4(n) = 
  \begin{cases}
      8[4{\frac{n}{2} \choose 3} + {\frac{n}{2} \choose 2}]^2=\frac{1}{72}n^2(n-2)^2(2n-5)^2  & , n \mbox{ even} \\
      8[4{\frac{n+1}{2} \choose 3} - {\frac{n-1}{2} \choose 2}]^2=\frac{1}{72}(n-1)^2(n-3)^2(2n-1)^2 & , n \mbox{ odd}
  \end{cases}
\end{equation*}

\end{theorem} 

%The key to our proofs for Theorems \ref{FirstEnumThm} and \ref{SecondEnumThm} is to note that there is a bijection between $L_4$- and $P_4$-configurations on an $n \times n$ grid and pairs of line segments with the same midpoint and each endpoint having distinct $x$- and $y$-coordinates (with values between 1 and $n$ inclusively) on the $n \times n$ grid.  More specifically, if the endpoints of the pair of line segments are collinear, then they correspond to an $L_4$-configuration while if they are not collinear, they correspond to a $P_4$-configuration. This uses the geometric result that a quadrilateral is a parallelogram if and only if its diagonals bisect each other.  

%Suggested rewrite
Theorem \ref{SecondEnumThm} refines the result of Appendix A of \cite{recursiveway}, which shows that $l_3(n) + l_4(n) + p_4(n) = O(n^6)$.  We made use of Theorem \ref{SecondEnumThm} in \cite{radarconpaper} where it was stated with proof in conjunction with the Lov\'asz Local Lemma to study the existence of Costas arrays and partial Costas arrays.  Our proofs for Theorems \ref{FirstEnumThm} and \ref{SecondEnumThm} make use of the geometric result that a quadrilateral is a parallelogram if and only if its diagonals bisect each other.  We apply this result bijectively to enumerate violating configurations by counting pairs of diagonals of a violating configuration with the same midpoint such that each of the $4$ endpoints has distinct $x$- and $y$-coordinates (with values between $1$ and $n$, inclusive) on an $n \times n$ grid.  If the $4$ endpoints are collinear, then they correspond to an $L_4$-configuration while if they are not collinear, they correspond to a $P_4$-configuration.

Focusing on counting the $L_4$-configurations, let $(x_1,y_1)$ and $(x_2,y_2)$ be two points on the $n \times n$ grid with $x_1<x_2$ and $y_1<y_2$ and let $M$ be the midpoint of the segment connecting these two points.  Then the slope of the segment connecting these two points is positive and the number of additional grid points on this line segment is $\gcd(x_2-x_1,y_2-y_1)-1$.  If  $\gcd(x_2-x_1,y_2-y_1)$ is even, then $M$ is one of these grid points.  These additional grid points (excluding $M$) can be paired together to form line segments with midpoint $M$ as well.  Thus, the number of shorter line segments having midpoint $M$ is $\left\lfloor\frac{\gcd(x_2-x_1,y_2-y_1)-1}{2}\right\rfloor$.  Summing this expression over all points  $(x_1,y_1)$ and $(x_2,y_2)$ with $x_1<x_2$ and $y_1<y_2$ counts the number of $L_4$-configurations on lines with positive slopes.  Due to symmetry, there is the same number of $L_4$-configurations on lines with negative slopes.  Thus,

\begin{eqnarray*}
l_4(n)  & = &   2\sum_{x_1=1}^{n-1}\sum_{x_2=x_1+1}^{n}\sum_{y_1=1}^{n-1}\sum_{y_2=y_1+1}^{n} \left\lfloor\frac{\gcd(x_2-x_1,y_2-y_1)-1}{2}\right\rfloor\\
\end{eqnarray*}

Let $a=x_2-x_1$ and $b=y_2-y_1$.  Then

\begin{eqnarray*}
l_4(n)  & = &   2\sum_{x_1=1}^{n-1}\sum_{a=1}^{n-x_1}\sum_{y_1=1}^{n-1}\sum_{b=1}^{n-y_1} \left\lfloor\frac{\gcd(a,b)-1}{2}\right\rfloor\\     
          & = &  2\sum_{a=1}^{n-1}\sum_{x_1=1}^{n-a}\sum_{b=1}^{n-1}\sum_{y_1=1}^{n-b} \left\lfloor\frac{\gcd(a,b)-1}{2}\right\rfloor\\
          & = &  2\sum_{a=1}^{n-1}\sum_{b=1}^{n-1}(n-a)(n-b)\left\lfloor\frac{\gcd(a,b)-1}{2}\right\rfloor
\end{eqnarray*}

Turning our attention to proving Theorem \ref{SecondEnumThm}, we need to count pairs of line segments with the same midpoint and with each endpoint having distinct $x$- and $y$-coordinates on the $n \times n$ grid.  Note the set of all midpoints of line segments having endpoints on this grid is $\{(\frac{x}{2},\frac{y}{2})|3\leq x \leq 2n-1, 3\leq y \leq 2n-1\}$. Given any one of these midpoints $M=(\frac{x}{2},\frac{y}{2})$, any line segment with endpoints $(x_1,y_1)$ and $(x_2,y_2)$ with $x_1 \neq x_2$ and midpoint $M$ on the grid must have $x_1$ or $x_2$ less than $\frac{x}{2}$ and the other coordinate greater than $\frac{x}{2}$.  Without loss of generality, assume $x_1<\frac{x}{2}<x_2$.  Note the number of positive integers less than $\frac{x}{2}$ is $\left\lfloor\frac{x-1}{2}\right\rfloor$ and the number of positive integers greater than $\frac{x}{2}$ and less than or equal to $n$ is $n-\left\lfloor\frac{x}{2}\right\rfloor$.  Thus, there are 

\begin{align*}
f_n(x) = \min\left\{\left\lfloor\frac{x-1}{2}\right\rfloor,n-\left\lfloor\frac{x}{2}\right\rfloor\right\}
\end{align*}
possible values for $x_1$.  Similarly, given $x_1$, the number of possible values for $y_1$ is $2f_n(y)$ as $y_1$ can be less than or greater than $\frac{y}{2}$.  Given any one of these line segments, the number of ways to select a second line segment with the same midpoint and endpoints with $x$- and $y$-coordinates different than $(x_1,y_1)$ and $(x_2,y_2)$ is $(f_{n}(x)-1)(2f_{n}(y)-2)$ as we lose one possible value for the $x$-coordinate (since $x_1$ must be less than $\frac{x}{2}$) and two possible values for the $y$-coordinate.  Thus, the number of pairs of line segments with midpoint $M=(\frac{x}{2},\frac{y}{2})$ and with each endpoint having distinct $x$- and $y$-coordinates on the grid equals

\begin{align*}
\frac{1}{2}( f_n(x)\cdot2f_n(y))(f_{n}(x)-1)(2f_{n}(y)-2)
\end{align*}
where we have multiplied by $\frac{1}{2}$ for otherwise we would count each pair of segments twice - once for each order the segments are selected.  We can rewrite the product with binomial coefficients as

\begin{align*}
\frac{1}{2}\cdot 2{f_n(x) \choose 2}\cdot 8 \cdot {f_n(y) \choose 2}.
\end{align*}

Thus, summing over all possible midpoints $M$ (see above), we have

\begin{eqnarray*}
l_4(n)+p_4(n) & = &   \sum_{x=3}^{2n-1}\sum_{y=3}^{2n-1} 8{f_n(x) \choose 2}{f_n(y) \choose 2}\\
 & = & 8 \sum_{x=5}^{2n-3}{f_n(x) \choose 2}\sum_{y=5}^{2n-3} {f_n(y) \choose 2}\\
\end{eqnarray*}          

The indices of the summations in the last expression change since there cannot be two line segments with distinct $x$- and $y$-coordinates for their endpoints if the $x$- or $y$-coordinate of the midpoint is in the set $\{\frac{3}{2},2,\frac{2n-1}{2},n-1\}$.  

If $n$ is even, then 

\begin{eqnarray*}
\sum_{y=5}^{2n-3} {f_n(y) \choose 2} & = & {2 \choose 2}+{2\choose 2}+{3 \choose 2}+{3 \choose 2}+\cdots +{{\frac{n}{2}-1} \choose 2}+{{\frac{n}{2}-1} \choose 2} \\
 & & +{{\frac{n}{2}} \choose 2}+ {{\frac{n}{2}-1} \choose 2}+{{\frac{n}{2}-1} \choose 2}+\cdots+ {3 \choose 2}+{3 \choose 2}+{2\choose 2}+{2 \choose 2}\\
& = & 4\cdot\left[{2 \choose 2}+{3 \choose 2}+\cdots +{{\frac{n}{2}-1} \choose 2}\right]+{{\frac{n}{2}} \choose 2}\\
& = & 4 {{\frac{n}{2}} \choose 3}+{{\frac{n}{2}} \choose 2}
\end{eqnarray*}

The final simplification follows from a binomial coefficient identity known as the hockey-stick identity, namely $\sum_{i=r}^{n} {i \choose r}={{n+1} \choose {r+1}}$.  

Repeating this for the summation involving $x$, we see that if $n$ is even, then $l_4(n)+p_4(n)=8 \cdot \left(4 {{\frac{n}{2}} \choose 3}+{{\frac{n}{2}} \choose 2}\right)^2=\frac{1}{72}n^2(n-2)^2(2n-5)^2$.

If $n$ is odd, then

\begin{eqnarray*}
\sum_{y=5}^{2n-3} {f_n(y) \choose 2} & = & {2 \choose 2}+{2\choose 2}+{3 \choose 2}+{3\choose 2}+\cdots +{{\frac{n-3}{2}} \choose 2}+{{\frac{n-3}{2}} \choose 2}\\
 & & +{{\frac{n-1}{2}} \choose 2}+{{\frac{n-1}{2}} \choose 2}+{{\frac{n-1}{2}} \choose 2} \\
& & +{{\frac{n-3}{2}} \choose 2}+{{\frac{n-3}{2}} \choose 2}+\cdots+{3 \choose 2}+{3 \choose 2}+{2\choose 2}+{2\choose 2}\\
& = & 4\cdot\left[{2 \choose 2}+{3 \choose 2}+\cdots +{{\frac{n-1}{2}} \choose 2}\right]-{{\frac{n-1}{2}} \choose 2}\\
& = & 4 {{\frac{n+1}{2}} \choose 3}-{{\frac{n-1}{2}} \choose 2}
\end{eqnarray*}

Thus, if $n$ is odd then

\begin{align*}
l_4(n)+p_4(n)=8\cdot\left(4 {{\frac{n+1}{2}} \choose 3}-{{\frac{n-1}{2}} \choose 2}\right)^2=\frac{1}{72}(n-1)^2(n-3)^2(2n-1)^2, 
\end{align*}
hence completing the proof of Theorem \ref{SecondEnumThm}.

We created OEIS entries A234471 and A243643 for $l_4(n)$ and $p_4(n)$, respectively, for $1 \leq n \leq 1000$.

Direct computation reveals that

\begin{align*}
\frac{C(n)}{n!} < \left(1 - \frac{1}{n(n-1)(n-2)}\right)^{l_3(n)}\left(1 - \frac{1}{n(n-1)(n-2)(n-3)}\right)^{l_4(n)+p_4(n)}
\end{align*}
for $4 \leq n \leq 29, n \neq 5$.  The right-hand expression can be interpreted as the probability that none of the violating configurations of order $n$ occurs if we make the assumption that the occurrences of violating configurations are mutually independent events.  We have no proof that this inequality holds for all sufficiently large $n$.  If it is valid for $n > 5$, the inequality can be used to quantify exponential decay.   For $n > 5$, define $a(n)=n(n-1)(n-2)$ and $b(n)=a(n)\cdot(n-3)$.  Rewrite the right-hand expression as

\begin{align*}
\left[\left(1 - \frac{1}{a(n)}\right)^{a(n)}\right]^{\frac{l_3(n)}{a(n)}}\left[\left(1 - \frac{1}{b(n)}\right)^{b(n)}\right]^{\frac{l_4(n)+p_4(n)}{b(n)}}.
\end{align*}
Using the formulas for $l_3(n)$ and $l_4(n)+p_4(n)$ and taking the limit of this expression as $n \rightarrow \infty$ gives 

\begin{conjecture}
\begin{align*}
\frac{C(n)}{n!} =O\left(e^{-\frac{n^2}{18} - \frac{n}{8}}\right).
\end{align*}
\end{conjecture}

\section{Configuration Enumeration for Identity Permutations}
While a Costas array is a permutation matrix that contains no violating configurations, we may also ask what is the permutation matrix that contains the maximal number of violating configurations.  Intuition and numerical evidence suggest that the identity matrix and the anti-diagonal matrix of 1's contain the maximal number of violating configurations, but how many such violating configurations do these matrices contain?  Clearly they contain no $P_4$-configurations.  Let $Idl_3(n)$ and $Idl_4(n)$ denote the number of $L_3$-configurations and $L_4$-configurations $I_n$ contains.  The results are

\begin{theorem}\label{FirstEnumThmIdentity}
For $n \geq 3$,
\begin{equation*}
Idl_3(n) = 
\begin{cases}
    ({\frac{n}{2}})({\frac{n-2}{2}}) & , n \mbox{ even} \\  
    ({\frac{n-1}{2}})^2 & , n \mbox{ odd}
  \end{cases} 
\end{equation*}
\end{theorem}

\begin{theorem}\label{SecondEnumThmIdentity}
For $n \geq 4$,
\begin{equation*}
Idl_4(n) = 
\begin{cases}
      4{\frac{n}{2} \choose 3} +{\frac{n}{2} \choose 2}=\frac{1}{24}n(n-2)(2n-5)  & , n \mbox{ even} \\
      4{\frac{n+1}{2} \choose 3} - {\frac{n-1}{2} \choose 2}=\frac{1}{24}(n-1)(n-3)(2n-1) & , n \mbox{ odd}
  \end{cases} 
\end{equation*}
\end{theorem}

Focusing on Theorem \ref{FirstEnumThmIdentity}, note that $(a,a)$ and $(b,b)$ are both endpoints of the same $L_3$-configuration if and only if $\frac{a+b}{2}$ is an integer.  Thus, $a$ and $b$ must have the same parity.  If $n$ is even, the number of pairs of even (or pairs of odd) integers less than or equal to $n$ is ${\frac{n}{2} \choose 2}$.  Thus, if $n$ is even, $Idl_3(n)={\frac{n}{2} \choose 2}\cdot2=({\frac{n}{2}})({\frac{n-2}{2}}).$  If $n$ is odd the number of pairs of even integers less than or equal to $n$ is ${\frac{n-1}{2} \choose 2}$ while the number of pairs of odd integers less than or equal to $n$ is ${\frac{n+1}{2} \choose 2}$.  Thus, if $n$ is odd, $Idl_3(n)={\frac{n-1}{2} \choose 2}+{\frac{n+1}{2} \choose 2}=({\frac{n-1}{2}})^2,$ thus completing the proof of Theorem \ref{FirstEnumThmIdentity}.
 
Turning our attention to proving Theorem \ref{SecondEnumThmIdentity}, we essentially repeat the technique that we used to prove Theorem \ref{SecondEnumThm} noting that our midpoints are of the form $M=(\frac{x}{2},\frac{x}{2})$ and the $y$-coordinates are equal to the $x$-coordinates for any $L_4$-configuration on $I_n$.  Thus, we are only free to choose 2 $x$-coordinates less than $\frac{x}{2}$ for any midpoint $M=(\frac{x}{2},\frac{x}{2})$, which can be done in ${f_n(x) \choose 2}$ ways.  Summing over the potential midpoints $M$, the number of $L_4$-configurations $I_n$ contains is 

\begin{eqnarray*}
Idl_4(n)& = &   \sum_{x=5}^{2n-3}{f_n(x) \choose 2}\\
 & = & \begin{cases}
      4{\frac{n}{2} \choose 3} +{\frac{n}{2} \choose 2}=\frac{1}{24}n(n-2)(2n-5)  & , n \mbox{ even} \\
      4{\frac{n+1}{2} \choose 3} - {\frac{n-1}{2} \choose 2}=\frac{1}{24}(n-1)(n-3)(2n-1) & , n \mbox{ odd}
  \end{cases}, 
\end{eqnarray*}          
as derived in Section 4.

Sequences $Idl_3(n)$ and $Idl_4(n)$ correspond to OEIS entry A002620 and the $(n-4)^{th}$ term of OEIS entry A002623, respectively.  We also noticed that the total number of violating configurations that $I_n$ contains, $Idl_4(n)+Idl_3(n)$, is the $(n-3)^{rd}$ term of OEIS entry A002623 and thus also equals $Idl_4(n+1)$.  While this can be verified algebraically, we provide a combinatorial proof instead.

\begin{theorem}\label{L3PlusL4ThmIdentity}
For $n \geq 4$, 
\begin{equation*}
Idl_4(n)+ Idl_3(n)=Idl_4(n+1)
\end{equation*} 
\end{theorem}

The number of $L_4$-configurations contained by $I_{n+1}$ is the number of $L_4$-configurations contained by this matrix that do not include the point $(n+1,n+1)$ plus the number that do contain the point $(n+1,n+1)$.  Those $L_4$-configurations that do not contain $(n+1,n+1)$ are precisely the $L_4$-configurations of $I_n$ and hence there are $Idl_4(n)$ such configurations.  For simplicity of notation, we represent the location of a 1 in the identity matrix simply by its corresponding integer, so $n+1$ will represent the point $(n+1,n+1)$.  Given an $L_4$-configuration with points $a<b<c<n+1$, we have $n+1-c=b-a$.  Then the points $c-b<n+1-b<n+1-a$ form an $L_3$-configuration in $I_n$.  Conversely, given an $L_3$-configuration with points $x<y<z$ in the $I_n$, we have $z-y=y-x$.  Then the points $n+1-z<n+1-y<n+1-y+x<n+1$ form an $L_4$-configuration in $I_{n+1}$.  As these two mappings are inverses of each other, the number of $L_4$-configurations that contain the point $(n+1,n+1)$ is $Idl_3(n)$.

\section{Density Revisited}
Let the random variables $X$, $Y$ and $Z$ be the number of $L_3$-, $L_4$- and $P_4$-configurations in a permutation matrix and let $W=X+Y+Z$.  Then the permutation matrix is a Costas array if and only if $W=0$.  Can we use the second moment method on $W$ to improve Davies's result?  To find out, we begin by calculating $\mathbb{E}(W)$.  By the additivity of the expectation operator, it suffices to consider $\mathbb{E}(Y)$ and $\mathbb{E}(Z)$.  Let $\mathcal{P}_n$ denote the set of $n \times n$ permutation matrices.  By $L_4 \subset A$ we denote the fact that the particular $L_4$-configuration appears in a fixed permutation matrix $A$.  For $n \geq 4$, we have

\begin{eqnarray*}
\mathbb{E}(Y) & = &  \frac{1}{n!}\sum_{A \in \mathcal{P}_n}Y(A) \\
                     & = & \frac{1}{n!}\sum_{A \in \mathcal{P}_n}\sum_{L_4 \subset A}1\\
                     & = & \frac{1}{n!}\sum_{L_4}\sum_{\{A \in \mathcal{P}_n|L_4 \subset A\}} 1\\
                     & = & \frac{1}{n!}\sum_{L_4}(n-4)! \\
                     & = & \frac{l_4(n)}{n(n-1)(n-2)(n-3)}
\end{eqnarray*}

Similar reasoning shows that

\begin{align*}
\mathbb{E}(Z) =\frac{p_4(n)}{n(n-1)(n-2)(n-3)}
\end{align*}  

Combining these results with the expression for $\mathbb{E}(X)$ gives

\begin{equation*}\label{muofW}
\mathbb{E}(W) =\left\{
       \begin{array}{ll}
            \frac{n(n-2)(4n^2-11n-2)}{72(n-1)(n-3)}  & , n \mbox{ even} \\
            \frac{(n-1)(4n-3)(n+1)}{72n} & , n \mbox{ odd} 
        \end{array}
    \right. 
\end{equation*}
which yields

\begin{equation*}
\mathbb{E}(W) \sim \frac{n^2}{18}.
\end{equation*}

At this point we suspect that an improvement over Davies's result in \cite{survey} could be possible from applying the second moment method to $W$ since $\mathbb{E}^2(W) = O(n^4)$ instead of $O(n^2)$.  We will have to show that $\mathbb{E}(W^2) = O(n^{\alpha})$ for some $\alpha < 3$ to make an improvement to his power-law decay result.  Bounding $\mathbb{E}(W^2)$ is made more complicated by the fact that $W$ is a sum and thus we would be obliged to consider cross terms upon squaring $W$.  The formula for $l_4(n)$ in Theorem \ref{FirstEnumThm} makes it clear that $l_4(n) < n^5$ and thus $\mathbb{E}(Y)=O(n)$. As $\mathbb{E}(X)=O(n)$ and $\mathbb{E}(W)=O(n^2)$, it follows that $\mathbb{E}(Z)=O(n^2)$ and thus $\mathbb{E}^2(Z) = O(n^4)$.  Hence $Z$ is the dominant term in $W$ and $\mathbb{E}(Z) \sim \frac{n^2}{18}$.  We consider applying the second moment method to $Z$: 

\begin{align*}
\frac{C(n)}{n!} = P(W=0) \leq P(Z=0) \leq P(|Z - \mathbb{E}(Z)| \geq \mathbb{E}(Z)) \leq \frac{\mathbb{E}(Z^2)}{\mathbb{E}^2(Z)} - 1
\end{align*}

We approach bounding the second moment of $Z$ in the same way that Davies did within \cite{survey} when bounding the second moment of $X$:

\begin{align*}
\mathbb{E}(Z^2) = \frac{1}{n!}\sum_{A \in \mathcal{P}_n}(Z(A))^2 = \frac{1}{n!}\sum_{A \in \mathcal{P}_n}\left(\sum_{P_4 \subset A}1\right)^2 = \frac{1}{n!}\sum_{A \in \mathcal{P}_n}\sum_{(P_4^1 \subset A,P_4^2 \subset A)} 1
\end{align*}
The inner sum in the last expression is over ordered pairs $(P_4^1 ,P_4^2)$ of $P_4$-configurations appearing in the permutation matrix $A$.  Interchanging the order of summation allows us to write

\begin{align*}
\mathbb{E}(Z^2) \leq \frac{1}{n!}\{m_4(n-4)! + m_3(n-5)! + m_2(n-6)! + m_1(n-7)! + m_0(n-8)!\}
\end{align*}
where $m_i = m_i(n)$ is the number of ordered pairs of $P_4$-configurations with exactly $i$ points in common.  Thus, the utility of the second moment method applied to $Z$ for improving density results depends on any formulas and upper bounds for the $m_i$.  In finding upper bounds for $m_i(n)$, for $i < 4$, the ones of the second $P_4$-configuration that are not also ones of the first $P_4$-configuration must be in distinct rows and columns from the ones of the first configuration.  Why is this?  If we picked one of the remaining $4-i$ points as being in the same row or column as a 1 for the first configuration, then since there is only one 1 in each row and column in the permutation matrix, it would have to be a one of the first configuration.  Thus there would be at least $i+1$ points in common.  

Without extensive effort we can derive upper bounds for the $m_i(n)$.  Clearly $m_4(n) = p_4(n)$.  To bound $m_3(n)$, note given a $P_4$-configuration, there are $4$ ways to select exactly $3$ points from it to share with another $P_4$-configuration. Given these $3$ points, at most $2$ additional $P_4$-configurations are possible. Hence

\begin{align*}
m_3(n) \leq 4 \cdot 2 \cdot p_4(n)
\end{align*}

We claim that

\begin{align*}
m_2(n) \leq 9p_4(n)(n-4)^2
\end{align*}

To see this, first note that there are ${4 \choose 2} = 6$ ways to pick two common points after fixing the first $P_4$-configuration.  There are at most $(n-4)^2$ valid ways to pick a third one in the permutation matrix.  Given the third one, the fourth one in the second $P_4$-configuration is not uniquely determined, but rather there are $3$ possibilities for the fourth one.  Since we do not care about the order in which the last 2 points are selected, we divide by $2$, avoiding double counting in the case that these last two points are both in the permutation matrix, and reducing the error in allowing the second configuration in the case that the the fourth point falls outside the permutation matrix.

Similar reasoning gives us the inequality

\begin{align*}
m_1(n) \leq \frac{4}{6}(3)p_4(n)(n-4)^2(n-5)^2.
\end{align*}
 
Finally, it is clear that $m_0 \leq p_4(n)p_4(n-4)$.  Combining these inequalities gives us

\begin{align*}
\frac{C(n)}{n!} < \frac{1 + \frac{8}{n-4} + \frac{9(n-4)}{(n-5)} + \frac{2(n-4)(n-5)}{n-6} + \frac{p_4(n-4)}{(n-4)(n-5)(n-6)(n-7)}}{\frac{p_4(n)}{n(n-1)(n-2)(n-3)}} - 1
\end{align*}

Letting $n \rightarrow \infty$ gives

\begin{align*}
\frac{C(n)}{n!} < \frac{1 + \frac{8}{n-4} + 9 + 2n + \frac{(n-4)^2}{18}}{\frac{n^2}{18}} - 1
\end{align*}

which reduces to

\begin{align*}
\frac{C(n)}{n!} < \frac{28}{n} + \frac{196}{n^2} + \frac{144}{n^2(n-4)}
\end{align*}

As mentioned in Section 3, Davies (Theorem 4.2, \cite{survey}) showed $\frac{C(n)}{n!} = O(\frac{1}{n})$ as $n \rightarrow \infty$ by studying $L_3$-configurations in permutation matrices, thereby proving the strongest known result about the asymptotic rate of decay of the density $\frac{C(n)}{n!}$ of Costas arrays.  Our result above, proven using $P_4$-configurations, confirms this rate of decay.  Looking more closely at Davies's proof, he shows that 
\begin{equation*}
\frac{C(n)}{n!}\leq \frac{c_1(n)}{\mu}+\frac{9n^2-45n+60}{(n-3)(n-4)(n-5)}
\end{equation*}
where $\mu =\mathbb{E}(X) \sim \frac{n}{8}$ is the mean number of $L_3$-configurations in a permutation matrix and $c_1(n)=1+\frac{4}{n-3}+\frac{9n^2}{4(n-3)(n-4)}$.  Note that $c_1(n) \sim 13/4$ and thus 
\begin{equation*}
\frac{c_1(n)}{\mu}+\frac{9n^2-45n+60}{(n-3)(n-4)(n-5)} \sim \frac{13/4}{n/8} + \frac{9n^2-45n+60}{(n-3)(n-4)(n-5)} \sim \frac{26}{n}+\frac{9}{n} = \frac{35}{n}
\end{equation*}
while our upper bound above is asymptotically equal to $\frac{28}{n}$.  Thus, our asymptotic upper bound above is a slight improvement over Davies's.

The presence of the term $\frac{28}{n}$ in our bound suggests that a tighter upper bound on $m_1$ or a different probabilistic inequality should be used.  If the bound on the function $m_1(n)$ could be shown to be asymptotically at most $2/9$ of what it currently is then it would be canceled in the limit by the linear term of the quadratic in the numerator:  $(\frac{2}{9})2n - \frac{8}{18}n = 0$.  The derivation of our upper bound on $m_1(n)$ is based on assumptions that do allow room for improvement.  For instance, the selection of the second and third vertices on the second $P_4$-configuration can be such that the fourth point falls outside the grid.  The function $m_1(n) = 0$ for $n < 7$ because two $P_4$-configurations would overlap in at least two rows or columns.  We wrote a C++ program to compute the values of $m_1(n)$ for $7 \leq n \leq 18$.  We found that $m_1(7) = 636, m_1(8) = 25888, m_1(9) = 401432, m_1(10) = 2788608, m_1(11) = 14302888, m_1(12) = 57333552, m_1(13) = 190675736, m_1(14) = 556245344,$ $m_1(15) = 1457381068, m_1(16) = 3498250624, m_1(17) = 7799395304,$ and that $ m_1(18)=16399389728$.  The ratio

\begin{align*}
\frac{m_1(n)}{2p_4(n)(n-4)^2(n-5)^2}
\end{align*}
is monotone increasing for $7 \leq n \leq 18$ and equals $0.2262\ldots>\frac{2}{9}$ for $n=18$.  This numerical evidence suggests that it may not be possible to establish quadratic decay for density from the second moment method applied to the random variable $Z$.  However, it is not clear that the ratio must be monotone increasing for larger $n$.

%We had a conclusion in the 020916wlc version of this paper.  However, we confirmed with editor Richard Brualdi that a Conclusion
%isn't really needed.  Most E-JC papers don't seem to have one--this one won't either.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof of Theorem~\ref{Thm:FabGraphs}}

%In this section we complete the proof of Theorem~\ref{Thm:FabGraphs}.

%\begin{proof}[Proof of Theorem~\ref{Thm:FabGraphs}]
%Let $G$ be a graph... Hence
 % use the amsmath align environment for multi-line equations
  %\begin{align}
    %|X| &= abcdefghijklmnopqrstuvwxyz \nonumber\\
    %&= \alpha\beta\gamma
  %\end{align}
  %This completes the proof of Theorem~\ref{Thm:FabGraphs}.
%\end{proof}

%\begin{figure}[!h]
  %\begin{center}
    % use \includegraphics to import figures 
    % \includegraphics{filename}
  %\end{center}
  %\caption{\label{fig:InformativeFigure} Here is an informative
    %figure.}
%\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%Thanks to our loved ones for giving us time to do this.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{plain} 

\begin{thebibliography}{10}

\bibitem{BarkerEtAl}
L.~Barker, K.~Drakakis, and S.~Rickard.
\newblock On the complexity of the verification of the {C}ostas property.
\newblock {\em Proc. IEEE}, 97(3):586--593, March 2009.

\bibitem{spreadsheet500}
J.~K. Beard.
\newblock C{D}-{ROM} images of {C}ostas arrays from {CISS}-2006/2008/2010
  papers.
\newblock \url{http://jameskbeard.com/jameskbeard/Files.html}.

\bibitem{BCenum}
B.~Correll~Jr.
\newblock A closed form expression for the number of {C}ostas arrays of
  arbitrary order.
\newblock In {\em Proceedings of IEEE Asilomar Conference on Signals, Systems,
  and Computers}, pages 2218 -- 2222, Monterey, CA, November 2007.

\bibitem{BCexp}
B.~Correll~Jr.
\newblock The density of {C}ostas arrays and three-free permutations.
\newblock In {\em Proceedings of the IEEE Statistical Signal Processing
  Workshop}, pages 492 -- 495, Ann Arbor, MI, 2012.

\bibitem{radarconpaper}
B.~Correll~Jr., C.~N. Swanson, and R.~W. Ho.
\newblock Costas arrays and the {L}ov\'asz local lemma.
\newblock In {\em Proceedings of 2015 IEEE International Radar Conference},
  Washington, DC, May 2015.

\bibitem{Costas}
J.~P. Costas.
\newblock Medium constraints on sonar design and performance.
\newblock Technical Report Class 1 Rep. R65EMH33, GE Co.,
  1965.

\bibitem{Costas2}
J.~P. Costas.
\newblock A study of detection waveforms having nearly ideal range-{D}oppler
  ambiguity properties.
\newblock {\em Proc. IEEE}, 72(8):996--1009, August 1984.

\bibitem{survey}
K.~Drakakis.
\newblock A review of {C}ostas arrays.
\newblock {\em J. Appl. Math.}, 2006:1--32, 2006.
\newblock Article ID 26385.

\bibitem{KDexp}
K.~Drakakis.
\newblock On the degrees of freedom of {C}ostas permutations and other constraints.
\newblock In {\em Adv. Math. Commun.}, 5(3):435-448, 2011.

\bibitem{openproblems}
K.~Drakakis.
\newblock Open problems in {C}ostas arrays.
\newblock Preprint, 2011.
\newblock \arxiv{1102.5727}.

\bibitem{count28}
K.~Drakakis, F.~Iorio, and S.~Rickard.
\newblock The enumeration of {C}ostas arrays of order 28 and its consequences.
\newblock In {\em Adv. Math. Commun.}, 5(1): 69-86, 2011.

\bibitem{Costas29}
K.~Drakakis, F.~Iorio, S.~Rickard, and J.~Walsh.
\newblock Results of the enumeration of {C}ostas arrays of order 29.
\newblock {\em Adv. Math. Commun.}, 5(3):547--553, 2011.

\bibitem{count27}
K.~Drakakis et~al.
\newblock Results of the enumeration of {C}ostas arrays of order 27.
\newblock {\em IEEE Trans. Inf. Theory}, 54(10):4684--4687, October 2008.

\bibitem{Gilbert}
E.~N. Gilbert.
\newblock Latin squares which contain no repeated digrams.
\newblock {\em SIAM Review}, 7(2):189--198, April 1965.

\bibitem{golomb}
S.~Golomb.
\newblock Algebraic constructions for {C}ostas arrays.
\newblock {\em J. Comb. Theory Series A}, 37(1):13--21, 1984.

\bibitem{golombtaylor}
S.~Golomb and H.~Taylor.
\newblock Constructions and properties of {C}ostas arrays.
\newblock {\em Proc. IEEE}, 72(9):1143--1163, September 1984.

\bibitem{recursiveway}
M.~Soltanalian, P.~Stoica, and J.~Li.
\newblock A recursive method for enumeration of {C}ostas arrays.
\newblock In {\em Proceedings of 22nd European Signal Processing Conference},
  Lisbon, Portugal, 2014.

\end{thebibliography}

\end{document}


