Intuition for why Costas arrays of order $n$ fail to undergo combinatorial explosion.

A Costas array can be regarded geometrically as a set of $n$ points lying on the squares of a $n \times n$ checkerboard, such that each row or column contains only one point, and that all of the $\frac{n(n − 1)}{2}$ displacement vectors between each pair of dots are distinct. —Costas array, Wikipedia

OEIS sequence A001441 counts the "number of inequivalent Costas arrays of order $n$ under [the action of the] dihedral group [of order 8]":

1, 1, 1, 2, 6, 17, 30, 60, 100, 277, 555, 990, 1616, 2168, 2467, 2648, 2294, 1892, 1283, 810, 446, 259, 114, 25, 12, 8, 29, 89, 23

Usually combinatorial things undergo "combinatorial explosions"—it's surprising that this one grows for a bit, and then decreases again.

What is the intuition for the local (global?) maximum at $n=16$?

Are asymptotic bounds known for this sequence? In particular, should I expect a value like $a(10^{10})$ to be small?

Solution 1:

Considering this question, the asymptotic number of rationals in $[0,1]$ with denominator less than $n$ is $\,\sim \dfrac{3}{\pi^2}n^2$. Now in the problem we are looking at, the slopes can be any of these rationals, or their inverses, their negatives, or their negative inverses.

Therefore there are asymptotically $\dfrac{12}{\pi^2}n^2$ slopes available, and each valid configuration is using up $\dfrac{n(n-1)}{2}$ of them which represents an asymptotical proportion of $\dfrac{\pi^2}{24}$ which is roughly $41\%$. I think that part of the point lies in the fact that this proportion is uniformly bounded away from $0$.

If we consider a probabilistic approach (for what it is worth since there is clearly some bias which I will disregard): let $N\sim \dfrac{12}{\pi^2}n^2$ and consider picking successively at random $a N$ numbers between $1$ and $N$, where $0<a<1$ is a constant ($41\%$, it doesn't really matter). The probability that all these numbers are different is $$\prod_{i=1}^{aN}(1-\frac{i}{N})$$ Now to be fair we really run the experiment $n!$ times (the number of permutation matrices), and if we keep assuming independent trials, the expected number of Costas arrays of order $n$ would be $$n!\prod_{i=1}^{aN}(1-\frac{i}{N})$$ Since $N>n^2$ this still tends to $0$ pretty quickly.

Then again, this mustn't be completely right, since the works of James K. Beard seem to indicate that for higher values of $n$ the curve would get off again - see e.g. this article.