# Interlaced Costas Arrays Do Not Exist

Authors: Konstantinos Drakakis; Rod Gow; Scott Rickard
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

We prove that the only Costas arrays that can be constructed
by interlacing 2 Costas arrays of smaller orders (either equal or differing by 1) are those of order 2, and
that, consequently, no non-trivial Costas arrays result from this method.


---

## Body

## 1. Introduction

The  longest-standing open problems in the  field of
Costas arrays [1, 2] are, at the same time, the most fundamental ones: the
existence of Costas arrays for all orders and techniques for their construction
[3–5]. In an effort to construct
new Costas arrays (where by “new” we mean arrays that neither have been
discovered yet through exhaustive search nor can be constructed by the known
algebraic techniques [3–5]), one is tempted to apply various empirical or semiempirical improvised methods that
may lead to a Costas array. One of the
first ideas that spring into mind is to “interlace” 2 known Costas arrays
into a larger one, hoping that the result will be a (new) Costas array. By
“interlacing” we mean that the new array will contain columns alternatively
chosen from the 2 Costas arrays, so that all odd columns come from the first
and all even from the second, and similarly for the rows (see Figure 1). It
looks at first that such a technique is promising, as it mixes the arrays while
preserving the Costas property for each one of them.Figure 1
A demonstration of interlacing for 24×4 arrays: the elements of the first are in
normal script and that of the second are in bold script; the interlaced
array has rows and columns alternatively chosen from each of the arrays. As a
result, the elements of the 2 old arrays occupy only those elements of the new
array whose coordinates have the same parity modulo 2 (are either both even or
both odd).It is clear that interlacing can be attempted with
arrays of either the same order (e.g., 2 Costas arrays of order 16 can be
combined into an array of order 32), or of orders differing by 1 (e.g., a
Costas array of order 17 and a Costas array of order 16 can be combined into an
array of order 33). Virtually, every novice in the field spends several hours
playing around with this idea, until (s)he gets eventually disappointed as no
array produced seems to have the Costas property. In this work, we prove that
neither case of interlacing can produce a Costas array, except perhaps in
trivial situations where the interlaced arrays are very small. Although the
proofs we offer are quite elementary and straightforward, they are significant
in the sense that they rely exclusively on the Costas property, and not on any
extra assumptions. Indeed, it is notoriously difficult to prove rigorously
results for Costas arrays in general, and most rigorous results available are
about the algebraically constructed Costas arrays [4–6]. A proof on the futility of interlacing can save
researchers in the field precious time.


## 2. Basics

For reasons of completeness, we give below some basic
definitions about Costas arrays [3].Definition 2.1.
Letn∈ℕ, [n]={1,…,n}, a:[n]→[n] be a bijection, namely, a permutation on the
integers 1,…,n;
its difference triangleT(a) is defined to be the collection of the
multisets {ti(a):i=1,…,n−1},
where ti(a)={a(i+j)−a(j):j=1,…,n−i} (it is customary to call ti the ith row of the triangle). Its corresponding
array is A=[αij],i,j∈[n],
so that
(2.1)αij={1,a(j)=i,0,otherwise,and it is customary to denote 1s
by dots and 0s by blanks. The collection of vectors {(i−j,a(i)−a(j)):i>j,i,j∈[n]} are the distance vectors of A (or a).Definition 2.2.
Leta:[n]→[n] be a bijection; it will have the Costas
property if the multisets in T(a) are actually sets, namely, none of them
contains a repeated entry, or, equivalently, when the distance vectors of a are all distinct.Definition 2.3.
Leta:[n]→[n], b:[m]→[m], m≤n be Costas permutations; they will be
orthogonal if the multisets ti(a)∪ti(b),i∈[m−1] are actually sets, or, equivalently, when the
distance vectors of a and the distance vectors of b have no vector in common.The Costas property can be reformulated in terms of
the autocorrelation of Costas arrays/permutations.Definition 2.4.
Leta,b:[n]→[n], n∈ℕ,
and let u,v∈ℤ;
the cross-correlation between a and b at (u,v) is defined as (2.2)Ψa,b(u,v)=|{(a(i)+v,i+u):i∈[n]}∩{(b(i),i):i∈[n]}|.When a=b, Ψa,a is the autocorrelation of a,
a local maximum M=(u0,v0) of |Ψ| along with the largest neighborhood S of M such that M is the only local maximum of |Ψ| in S is called a lobe of Ψ.
The main lobe corresponds to the global maximum (note that it may not be
unique in case of multiple equal global maxima), and the sidelobes to
the remaining maxima.Geometrically, the cross-correlation is interpreted as
follows: place the arraysA and B,
corresponding to a and b, respectively, on top of each other, so that
they overlap perfectly, then slide A by u columns to the right and v rows downwards, and set Ψa,b(u,v) to be the number of pairs of overlapping dots.In Section3, Costas arrays will be interpreted as
signal representations in the time-frequency plane (horizontal and vertical
directions, resp.), and a dot will denote the presence of energy in a certain
area of the time-frequency plane; we assume that the array tiles the plane into
equal areas, and that all dotted areas carry the same amount of energy. In this
context, the cross-correlation, as defined above, is based on the energy
content alone (and disregards completely phase information).Finally, we should also define interlacing more
formally (see Figure1, e.g., of interlacing of 2 4×4 arrays).Definition 2.5.
Leta:[n+s]→[n+s] and b:[n]→[n] be permutations, and let s∈{0,1};
then their interlaced permutation is c:[2n+s]→[2n+s],
where (2.3)c(i)={2a(i+12)−1,i≡1mod2,2b(i2),i≡0mod2,i∈[2n+s].
It is clear that, within the array corresponding toc,
the distance vectors of a and b are still present, albeit dilated by a factor
of 2. If then a and b are nonorthogonal Costas permutations, c cannot be Costas because its corresponding
array will have a pair of equal distance vectors; the same is obviously true if
either a or b fail to be Costas. Therefore, our only hope
for interlacing to yield a Costas array is to start with Costas arrays (of
equal orders or orders differing by 1). Note that a feature of such interlaced
Costas arrays would be that their dots lie exclusively at positions with
coordinates either both even or both odd, and this may already sound alarmingly
restrictive; indeed, as we are about to show, such Costas arrays do not exist,
except in trivial cases.


## 3. Why are We Interested in Costas Arrays?

RADARs and SONARs
detect the distance and the velocity
of targets around them by transmitting periodically a waveformW and listening for reflections R.
Assuming an ideal noiseless environment, R is just a copy of W,
only attenuated, and shifted in frequency and time. The time delay indicates
the distance of the target, while the frequency shift, through the Doppler
effect, indicates its velocity (we assume here that the frequency content of W is narrowband enough for the Doppler effect,
which is multiplicative, to be well approximated by a uniform additive shift
for all frequencies).How are the time and frequency shifts detected? The
simplest solution would be to apply a matched filter.R is cross-correlated with shifted versions of W for various time and frequency shifts, and the
pair of shifts corresponding to the maximal cross-correlation are the true shifts
sought. Alas, this simple idea fails to work in practice because all real media
are incoherent. Phase delay varies with frequency, hence waveforms tend to
spread while traveling in the medium, so that, by the time R reaches the RADAR/SONAR, it looks nothing like W any more.Costas's idea [2] was to discard phase
information, since it is unreliable, and carry out the cross-correlation based
on the energy contents of W and R alone. Consider a waveform of the
form(3.1)W(t)=Acos(ϕk+2π(f0+aknf1)t),t∈[k−1nT,knT],where k∈[n], T is the time duration of the pulse, f0 and f1 are two predetermined frequencies, ϕk are phases suitably chosen so that the phase
of W is continuous in t (we may choose ϕ1=0), and a:[n]→[n] is a bijection. This is a frequency hopping
waveform whose instantaneous frequency is(3.2)f(t)=f0+aknf1,t∈(k−1nT,knT),k∈[n].We observe that W is completely determined by a,
given that f0, f1,
and T are set.Costas's idea amounts effectively to placing an energy
content detector before the matched filter, thus reconstructinga from W,
and similarly for R.
The signals fed to the matched filter can then each be abstracted as a 2D
infinite sequence, representing the time-frequency plane. This sequence is full
of 0s/blanks (energy is not present), except for an n×n square that corresponds to a permutation array
(whose 1s/dots denote that energy is present there), exactly as described in
Definition 2.1. The filter overlays the two 2D sequences, then shifts one with
respect to the other by some rows vertically and some columns horizontally, and
counts how many pairs of dots overlap:(3.3)ΨA,B(u,v)=∑i,jaijbi+u,j+v,where Ψ is the cross-correlation, A,B:ℤ2→{0,1} the two 2D sequences, and u, v the shift parameters. In the absence of noise, R is an exact copy of W,
only shifted in time and frequency, so the matched filter will have found the
correct shift parameters when the cross-correlation becomes equal to n.When noise is present, however, some ofR's dots may have shifted irregularly or even
gone altogether missing. R will no longer be an exact copy of W and the maximal cross-correlation will no
longer be n.
The filter will have no alternative than to locate the maximal
cross-correlation (note that now it will not know a priori what the maximum
will be) and return the shift parameters corresponding to it; but this maximum
may no longer be unique, or one of the (former) sidelobes may have grown taller
than the main lobe. Either case will result in spurious target detection.What should the form ofa (or the corresponding array A) be in order to minimize the probability of
spurious detections? In the absence of noise, the cross-correlation is just a
shifted form of the autocorrelation of A,
so we need to choose A in such a way so as to suppress as much as
possible the height of the autocorrelation sidelobes relatively to the main
lobe (whose height is n):(3.4)A=A*=argminAmax(u,v)ΨA,A(u,v).Choosing any pair of dots in A,
there exists a shift (their distance vector) that will move these dots on top
of each other, so sidelobes of height 1 will exist and nothing can be done
about it. If, however, we stipulate that distance vectors be unique, there will
be no sidelobe of height 2 or more; but this is precisely the Costas property
(see Definitions 2.1 and 2.2). Autocorrelation is known as autoambiguity in
the SONAR/RADAR community, and waveforms with the Costas property are said to
have ideal thumbtack autoambiguity [2, 5]. Why should the optimal A be a permutation array, as we assumed (summarily
and without any further explanation) above? Would using twice the same
frequency, or using two frequencies simultaneously, not improve the
autocorrelation? Costas argued on basic engineering principles that indeed it
would not [2].


## 4. The Quest for Orthogonal Costas Arrays

The entries of the difference triangle of a
permutation exhibit strong dependence; so strong, in fact, that even the 3
entries at its bottom (namely, in rowsn−1 and n−2, n>2 being the order of the permutation) are
sometimes enough to guarantee that a (Costas) permutation with the given
difference triangle cannot possibly exist.
Lemma 4.1.
Leta:[n]→[n] be a function and let tn−1(a)={x}, tn−2(a)={y,z}, n,x,y,z∈ℕ;
then(i)
ifx=y or x=z, a cannot be a permutation;(ii)
ifx=y+z, a cannot be a permutation, unless perhaps n=3.Proof.
tn−1(a)={x} implies that ∃m∈ℕ,m≤n:a(1)=m and a(n)=m+x.
Adding the constraints imposed by tn−2(a),
we end up with 2 possible cases:
(i)
(a(1),a(2),a(n−1),a(n))=(m,m+x−y,m+z,m+x);
or(ii)
(a(1),a(2),a(n−1),a(n))=(m,m+x−z,m+y,m+x).If x=y or x=z, a cannot be a bijection, as it assumes a certain
value twice; also, if x=y+z,
it follows that a(2)=a(n−1),
in which case a cannot be a permutation unless n−1=2⇔n=3.We will use this lemma repeatedly below. As a
shorthand, we will denote the class of functionsa satisfying the assumptions of the lemma as [x∣y,z].


### 4.1. Arrays of Equal Order

This case has already been studied in [7], in the context of
electrical engineering. The authors remarked that “to increase the main
lobe/sidelobe ratio [of a signal] without increasing the number of
frequencies […] it may be possible to stagger Costas signal pulses whose
ambiguity sidelobe patterns do not coincide”, and then proceeded to show this
is not possible. For reasons of completeness, we reproduce it here in full,
albeit in a more compact and simplified form. Note, however, that this case
alone is not sufficient to preclude “staggering” (what we call interlacing)
as a strategy for building new Costas arrays; the case presented in (Section
4.2) must also be studied.Theorem 4.2.
Leta and b be Costas permutations of order n>3, n∈ℕ,
and let T(a) and T(b) be their difference triangles; then ∃i∈{1,…,n−1}:ti(a)∩ti(b)≠∅,
and, therefore, a and b are not orthogonal.Proof.
We will offer a proof by
contradiction. Assume that the statement is false and consider the collection
of multisetsT(a,b)={ti(a,b):i=1,…,n−1}, where ti(a,b)=ti(a)∪ti(b),i=1,…,n−1.
Negating the conclusion of the theorem implies that these multisets are
actually sets, since we are effectively assuming that ∀i∈{1,…,n−1}:ti(a)∩ti(b)=∅;
naturally, the very definition of the Costas property implies that all ti(a),ti(b),i=1,…,n−1 are themselves sets and not multisets, since
they cannot contain duplicate entries.
T(a) must contain n−1 entries of absolute value 1, and so must T(b).
Consequently, T(a,b) contains 2n−2 such values distributed over n−1 rows. Now, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−2=2(n−1),
each ti(a,b),i=1,…,n−1 must contain exactly 2 of them, necessarily of
opposite sign.
The same argument can be repeated with the entries of
absolute value 2.T(a) must contain n−2 entries of absolute value 2, and so must T(b).
Consequently, T(a,b) contains 2n−4 of such values distributed over n−2 rows. Again, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−4=2(n−2),
each ti(a,b),i=1,…,n−2 must contain exactly 2 of them, necessarily of
opposite sign.
Sincetn−1(a,b) only has 2 entries, necessarily tn−1(a,b)={−1,1};
similarly, since tn−2(a,b) only has 4 entries, necessarily tn−2(a,b)={−2,−1,1,2},
and, in the same way, we find that tn−3(a,b)={−3,−2,−1,1,2,3}.
We now need to determine which entries belong to T(a),
and whether the Costas property holds for each case.
(i)
[1∣−2,−1].
Lemma 4.1 is of no help here; however, the 2 possibilities are (a(1),a(2),a(n−1),a(n))=(m,m+2,m−2,m+1) or (m,m+3,m−1,m+1),
and in both cases tn−3(a) should contain a −4,
which cannot be the case, as tn−3(a,b) does not.(ii)
[1∣−2,1].
This is case x=z in Lemma 4.1.(iii)
[1∣−2,2].
Lemma 4.1 is of no help directly here; however, b should be a [−1|−1,1] in this case, which is case x=y in Lemma 4.1.(iv)
[1∣−1,1].
This is case x=z in Lemma 4.1.(v)
[1∣−1,2].
This is case x=y+z in Lemma 4.1, so a cannot be Costas except perhaps when n=3,
in which case direct verification proves it is.(vi)
[1∣1,2].
This is case x=y in Lemma 4.1.The remaining cases are also impossible, as they correspond to horizontal flips of the ones
above. So, for n>3,
in all cases we proved it is impossible to construct a pair of orthogonal
Costas arrays of equal order.


### 4.2. Arrays of Orders Differing by 1

Theorem 4.3.
Leta and b be Costas permutations of orders n and n+1,
respectively, with n∈ℕ, n>2,
and let T(a) and T(b) be their difference triangles; then ∃i∈{1,…,n−1}:ti(a)∩ti(b)≠∅,
and, therefore, a and b are not orthogonal.Proof.
We proceed to offer a proof by
contradiction along the same lines as in Theorem4.2. Assuming that the statement
is false, and considering the collection of multisets T(a,b)={ti(a,b):i=1,…,n}, where ti(a,b)=ti(a)∪ti(b),i=1,…,n−1, tn(a,b)=tn(b),
the negation of the conclusion of the theorem implies that these multisets are
actually sets, since we are actually assuming that ∀i∈{1,…,n−1}:ti(a)∩ti(b)=∅;
note that the definition of the Costas property implies that all ti(a),ti(b),i=1,…,n−1 are themselves sets and not multisets, since
they cannot contain duplicate entries.
T(a) must contain n−1 entries of absolute value 1, while T(b) must contain n such values. Consequently, T(a,b) contains 2n−1 of such values distributed over n rows. Now, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−1=2(n−1)+1,
each ti(a,b),i=1,…,n−1 must contain exactly 2 of them, necessarily of
opposite sign, while the remaining one will be tn(a,b)'s only value: tn(a,b)=tn(b)={±1}.
The same argument can be repeated with the entries of
absolute value 2.T(a) must contain n−2 entries of absolute value 2, while T(b) must contain n−1 of such values. Consequently, T(a,b) contains 2n−3 of such values distributed over n−1 rows. Again, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−3=2(n−2)+1,
each ti(a,b),i=1,…,n−2 must contain exactly 2 of them, necessarily of
opposite sign, while the remaining one will be in tn−1(a,b),
which has 3 elements: tn−1(a,b)={−1,1,±2}.
Repeating the argument verbatim with absolute value 3 yields that tn−2(a,b)={−2,−1,1,2,±3}.
Let us now attempt to constructb explicitly based on that information; without
loss of generality, let us assume that tn(a,b)=tn(b)={1} (otherwise flip both a and b horizontally). The following cases are
possible.
(i)
[1∣−1,1]. This is case x=z in Lemma 4.1.(ii)
[1∣−2,−1].
Lemma 4.1 is of no help here; however, the 2 possibilities are (b(1),b(2),b(n),b(n+1))=(m,m+2,m−2,m+1) or (m,m+3,m−1,m+1),
and in both cases, tn−2(a) should contain a −4,
which cannot be the case, as tn−2(a,b) does not.(iii)
[1∣−2,1].
This is case x=z in Lemma 4.1.(iv)
[1∣−1,2].
This is case x=y+z in Lemma 4.1, so b cannot be Costas except perhaps when n=2,
in which case direct verification proves it is.(v)
[1∣1,2].
This is case x=y in Lemma 4.1.So, for n>2,
in all cases we proved it is impossible to construct a pair of orthogonal
Costas arrays of orders differing by 1. Note that the cases appearing in this
theorem also appear in Theorem 1, where they were proved not to lead to Costas
permutations; noting this would make the proof shorter, but not self-contained.


### 4.3. Possible Exceptions

Theorems4.2 and 4.3 allow for exceptional interlaced
constructions of Costas arrays in small orders n≤6.
Do such arrays actually exist? Clearly, Costas arrays of order 2 are trivially
interlaced (as 2 Costas arrays of order 1). We checked exhaustively all Costas
arrays of order 3≤n≤6 to settle completely the issue for those
orders, where the theorems do not readily apply. None of these arrays was found
to be interlaced. Together with the 2 aforementioned theorems, then, this fact
provesTheorem 4.4.
Interlaced Costas arrays of ordern≠2 do not exist.


## 4.1. Arrays of Equal Order

This case has already been studied in [7], in the context of
electrical engineering. The authors remarked that “to increase the main
lobe/sidelobe ratio [of a signal] without increasing the number of
frequencies […] it may be possible to stagger Costas signal pulses whose
ambiguity sidelobe patterns do not coincide”, and then proceeded to show this
is not possible. For reasons of completeness, we reproduce it here in full,
albeit in a more compact and simplified form. Note, however, that this case
alone is not sufficient to preclude “staggering” (what we call interlacing)
as a strategy for building new Costas arrays; the case presented in (Section
4.2) must also be studied.Theorem 4.2.
Leta and b be Costas permutations of order n>3, n∈ℕ,
and let T(a) and T(b) be their difference triangles; then ∃i∈{1,…,n−1}:ti(a)∩ti(b)≠∅,
and, therefore, a and b are not orthogonal.Proof.
We will offer a proof by
contradiction. Assume that the statement is false and consider the collection
of multisetsT(a,b)={ti(a,b):i=1,…,n−1}, where ti(a,b)=ti(a)∪ti(b),i=1,…,n−1.
Negating the conclusion of the theorem implies that these multisets are
actually sets, since we are effectively assuming that ∀i∈{1,…,n−1}:ti(a)∩ti(b)=∅;
naturally, the very definition of the Costas property implies that all ti(a),ti(b),i=1,…,n−1 are themselves sets and not multisets, since
they cannot contain duplicate entries.
T(a) must contain n−1 entries of absolute value 1, and so must T(b).
Consequently, T(a,b) contains 2n−2 such values distributed over n−1 rows. Now, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−2=2(n−1),
each ti(a,b),i=1,…,n−1 must contain exactly 2 of them, necessarily of
opposite sign.
The same argument can be repeated with the entries of
absolute value 2.T(a) must contain n−2 entries of absolute value 2, and so must T(b).
Consequently, T(a,b) contains 2n−4 of such values distributed over n−2 rows. Again, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−4=2(n−2),
each ti(a,b),i=1,…,n−2 must contain exactly 2 of them, necessarily of
opposite sign.
Sincetn−1(a,b) only has 2 entries, necessarily tn−1(a,b)={−1,1};
similarly, since tn−2(a,b) only has 4 entries, necessarily tn−2(a,b)={−2,−1,1,2},
and, in the same way, we find that tn−3(a,b)={−3,−2,−1,1,2,3}.
We now need to determine which entries belong to T(a),
and whether the Costas property holds for each case.
(i)
[1∣−2,−1].
Lemma 4.1 is of no help here; however, the 2 possibilities are (a(1),a(2),a(n−1),a(n))=(m,m+2,m−2,m+1) or (m,m+3,m−1,m+1),
and in both cases tn−3(a) should contain a −4,
which cannot be the case, as tn−3(a,b) does not.(ii)
[1∣−2,1].
This is case x=z in Lemma 4.1.(iii)
[1∣−2,2].
Lemma 4.1 is of no help directly here; however, b should be a [−1|−1,1] in this case, which is case x=y in Lemma 4.1.(iv)
[1∣−1,1].
This is case x=z in Lemma 4.1.(v)
[1∣−1,2].
This is case x=y+z in Lemma 4.1, so a cannot be Costas except perhaps when n=3,
in which case direct verification proves it is.(vi)
[1∣1,2].
This is case x=y in Lemma 4.1.The remaining cases are also impossible, as they correspond to horizontal flips of the ones
above. So, for n>3,
in all cases we proved it is impossible to construct a pair of orthogonal
Costas arrays of equal order.


## 4.2. Arrays of Orders Differing by 1

Theorem 4.3.
Leta and b be Costas permutations of orders n and n+1,
respectively, with n∈ℕ, n>2,
and let T(a) and T(b) be their difference triangles; then ∃i∈{1,…,n−1}:ti(a)∩ti(b)≠∅,
and, therefore, a and b are not orthogonal.Proof.
We proceed to offer a proof by
contradiction along the same lines as in Theorem4.2. Assuming that the statement
is false, and considering the collection of multisets T(a,b)={ti(a,b):i=1,…,n}, where ti(a,b)=ti(a)∪ti(b),i=1,…,n−1, tn(a,b)=tn(b),
the negation of the conclusion of the theorem implies that these multisets are
actually sets, since we are actually assuming that ∀i∈{1,…,n−1}:ti(a)∩ti(b)=∅;
note that the definition of the Costas property implies that all ti(a),ti(b),i=1,…,n−1 are themselves sets and not multisets, since
they cannot contain duplicate entries.
T(a) must contain n−1 entries of absolute value 1, while T(b) must contain n such values. Consequently, T(a,b) contains 2n−1 of such values distributed over n rows. Now, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−1=2(n−1)+1,
each ti(a,b),i=1,…,n−1 must contain exactly 2 of them, necessarily of
opposite sign, while the remaining one will be tn(a,b)'s only value: tn(a,b)=tn(b)={±1}.
The same argument can be repeated with the entries of
absolute value 2.T(a) must contain n−2 entries of absolute value 2, while T(b) must contain n−1 of such values. Consequently, T(a,b) contains 2n−3 of such values distributed over n−1 rows. Again, no row can contain 3 or more of
such values, as then there would be 2 with the same sign, hence equal; and
since 2n−3=2(n−2)+1,
each ti(a,b),i=1,…,n−2 must contain exactly 2 of them, necessarily of
opposite sign, while the remaining one will be in tn−1(a,b),
which has 3 elements: tn−1(a,b)={−1,1,±2}.
Repeating the argument verbatim with absolute value 3 yields that tn−2(a,b)={−2,−1,1,2,±3}.
Let us now attempt to constructb explicitly based on that information; without
loss of generality, let us assume that tn(a,b)=tn(b)={1} (otherwise flip both a and b horizontally). The following cases are
possible.
(i)
[1∣−1,1]. This is case x=z in Lemma 4.1.(ii)
[1∣−2,−1].
Lemma 4.1 is of no help here; however, the 2 possibilities are (b(1),b(2),b(n),b(n+1))=(m,m+2,m−2,m+1) or (m,m+3,m−1,m+1),
and in both cases, tn−2(a) should contain a −4,
which cannot be the case, as tn−2(a,b) does not.(iii)
[1∣−2,1].
This is case x=z in Lemma 4.1.(iv)
[1∣−1,2].
This is case x=y+z in Lemma 4.1, so b cannot be Costas except perhaps when n=2,
in which case direct verification proves it is.(v)
[1∣1,2].
This is case x=y in Lemma 4.1.So, for n>2,
in all cases we proved it is impossible to construct a pair of orthogonal
Costas arrays of orders differing by 1. Note that the cases appearing in this
theorem also appear in Theorem 1, where they were proved not to lead to Costas
permutations; noting this would make the proof shorter, but not self-contained.


## 4.3. Possible Exceptions

Theorems4.2 and 4.3 allow for exceptional interlaced
constructions of Costas arrays in small orders n≤6.
Do such arrays actually exist? Clearly, Costas arrays of order 2 are trivially
interlaced (as 2 Costas arrays of order 1). We checked exhaustively all Costas
arrays of order 3≤n≤6 to settle completely the issue for those
orders, where the theorems do not readily apply. None of these arrays was found
to be interlaced. Together with the 2 aforementioned theorems, then, this fact
provesTheorem 4.4.
Interlaced Costas arrays of ordern≠2 do not exist.


## 5. Summary and Conclusion

We have proved that interlaced Costas arrays cannot
possibly exist, unless perhaps for very small orders because any 2 Costas
arrays of orders larger than 3 and differing at most by 1 must have a common
distance vector, and interlacing dilates vectors by a factor of 2 but
does not distort them. Further exhaustive search
actually shows that the only interlaced Costas arrays are those of order 2.
Therefore, though interlacing may initially seem a neat trick and an
interesting idea for an empirical construction method, it is doomed to fail for
all orders of interest. The result is a direct consequence of the Costas
property, hence valid for all Costas arrays, and this is a rare case of a
rigorous result that encompasses the whole family of Costas arrays, as opposed
to those usually published that are valid only for (subfamilies of)
algebraically constructed Costas arrays.As a possible future direction of research, we suggest
investigating whether it is true that any 2 Costas arrays of arbitrary orders
have a common vector and/or find conditions under which this occurs.



---

*Source: 456034-2008-12-30.xml*