# On the Measurement of the (Non)linearity of Costas Permutations

Authors: Konstantinos Drakakis
Journal: Journal of Applied Mathematics
 (2010)

---

## Abstract

We study several criteria for the (non)linearity of Costas permutations, with or without the
imposition of additional algebraic structure in the domain and the range of the permutation, aiming
to find one that successfully identifies Costas permutations as more nonlinear than randomly chosen
permutations of the same order.


---

## Body

## 1. Introduction

Costas arrays, namely, square arrangements of dots and blanks such that there lies exactly one dot per row and column, and such that no four dots form a parallelogram and no three dots lying on a straight line are equidistant, appeared for the first time in 1965 in the context of SONAR detection [1, 2], when Costas, disappointed by the poor performance of SONAR systems, used them to describe a novel frequency hopping pattern for SONARs with optimal auto-correlation properties. About two decades later, Professor S. Golomb published two generation techniques [3–5] for Costas permutations, both based on the theory of finite fields, known as the Welch and the Golomb method, respectively. These are still the only general construction methods for Costas permutations available today. Despite the intensive mathematical research dedicated to Costas arrays in the last two decades, many key questions about them remain unresolved, and most notably the issue of their existence: do Costas arrays exist for all orders? There is currently no order known for which Costas arrays provably do not exist, while the two smallest orders for which no Costas arrays are known are 32 and 33 [3].An interesting application of Costas arrays in cryptography was discovered when it was shown that Welch Costas arrays are Almost Perfect Nonlinear (APN) permutations [6]. This prompted further an investigation of the nonlinearity of Welch Costas permutations, in the sense defined in [7, 8], whereby Welch Costas permutations were interpreted as mappings on ℤn, the group of integers modulo n, and were indeed shown to exhibit high nonlinearity among all such functions/permutations [9]. Costas permutations, however, are not defined over ℤn, but rather over [n]⊂ℕ, the set of the first n nonnegative integers, on which no group structure is imposed. The object of this work is to investigate the correct interpretation and calculation of the (non)linearity of a Costas permutation, and, by extension, of any discrete function, in this context. What does it mean for a discrete function to be linear? How can the concept of linearity be quantified? Can this quantification benefit, in the case of functions on [n], from the fact that such functions can be extended to functions on ℤn? Assuming that this latter extension exhibits indeed high nonlinearity, can we infer that the original function on [n] is also highly nonlinear (according to some appropriate definition)?In what follows we will study several (non)linearity criteria, and more specifically their performance on Costas permutations versus collections of random permutations. In order to maintain compatibility between them and to be able to compare them, we will use Costas permutations of order 15 (but also 16 and 27 on some occasions) as a test case and recurrent example. The conclusions drawn have, of course, been verified on a wider range of orders.


## 2. Costas Permutations, APN Functions, and Linearity

In this section we provide some background information on Costas permutations and APN functions. We will note, in particular, that, though the definitions of Costas and APN permutations appear deceptively similar, there are nonetheless important differences one has to pay attention to.


### 2.1. The Definitions

In what follows, let[n] denote the set {0,1,…,n-1}, and ℤn the additive group of integers modulo n, n∈ℕ*; in other words, [n] and ℤn differ just by the imposition of an algebraic structure on the latter, which makes it a ring. We are now ready to define the Costas permutation.Definition 2.1.
Consider a bijectionf:[n]→[n];fis a Costas permutation if and only if:
(2.1)∀i,j,ksuchthati,j,i+k,j+k∈[n],f(i+k)-f(i)=f(j+k)-f(j)⇒i=jork=0.
An alternative yet fully equivalent way to state this condition is to stipulate that, for any k∈[n]* and any l∈[n], the equation
(2.2)f(i+k)-f(i)=l,i∈[n-k],
has at most one root i.A permutationf corresponds to a permutation array Af=[ai,jf] by setting the elements of the permutation to denote the positions of the (unique) 1 in the corresponding column of the array, counting from top to bottom: af(i),if=1. It is customary to represent the 1s of a permutation array as “dots” and the 0s as “blanks”. From now on the terms “array” and “permutation” will be used interchangeably, in view of this correspondence.The Costas property is invariant under horizontal and vertical flips, as well as transposition (and therefore also under rotations of the array by multiples of90°, which can be expressed as combinations of the previous two operations), hence a Costas array gives birth to an equivalence class that contains either eight Costas arrays, or four if the array happens to be symmetric: this Costas array is then considered to be the unique representative of the equivalence class, and normally the array within the equivalence class that comes first in lexicographical order is selected for this purpose.We now give the definition of the APN function.Definition 2.2.
f:ℤn→ℤn is APN if and only if,for anyα∈ℤn*and anyβ∈ℤn, the equation
(2.3)f(x+α)-f(x)=β,x∈ℤn,
has at most two roots x.The relation of the two definitions becomes clearer if we also look at the definition of the Perfect Nonlinear (PN) function:Definition 2.3.
f:ℤn→ℤnis PN if and only if, for any α∈ℤn* and any β∈ℤn, the equation
(2.4)f(x+α)-f(x)=β,x∈ℤn,
has at most one root (hence exactly one root) x.We now see how close Definitions2.1 and 2.2 are. When we focus exclusively on permutations, thought, we see that a PN permutation is a contradiction in terms: by Definition 2.3, for any α, there has to be an x such that f(x+α)-f(x)=0, hence f cannot possibly be a permutation! Consequently, when studying permutations, we can only hope for the next best thing, namely, an APN permutation. Note that the definitions of a Costas permutation and of an APN function show that these two types of functions are far from being “linear”, namely, far from being similar to a “straight line”, since the distance vectors between pairs of points in the function graph are not, in general, allowed to be collinear.


### 2.2. Construction Methods for Costas Permutations

We will denote the finite field ofq elements by 𝔽(q), where q is, in general, a power of a prime. Recall that ℤp, p is a prime, is the finite field 𝔽(p).Algorithm 2.4 (Exponential Welch ConstructionW1(p,g,c)).
Letp be a prime, g a primitive root of the finite field 𝔽(p), and c∈[p-1]; the exponential Welch permutation of order p-1 corresponding to g and c is defined by
(2.5)f(i)=gi+cmodp-1,i∈[p-1].The inverse of an Exponential Welch permutation (corresponding to the transpose of the corresponding Costas array) is a Logarithmic Welch permutation, which is itself a Costas permutation. The two permutation sets are distinct forp>5 [10], implying that there are 2(p-1)ϕ(p-1) distinct Welch Costas permutations of order p-1. Here ϕ denotes Euler's totient function: ϕ(x), x∈ℕ, is the number of positive integers less than and relatively prime to x. In particular, there are no self-inverse W1-permutations (i.e., corresponding to symmetric Welch Costas arrays) for p>5.Algorithm 2.5 (Golomb ConstructionG2(q,a,b)).
Letq=pm, where p is a prime and m∈ℕ*, and let a, b be primitive roots of the finite field 𝔽(q); the Golomb permutation f of order q-2 corresponding to a and b is defined through the equation
(2.6)ai+1+bf(i)+1=1,i∈[q-2].There areϕ2(q-1)/m distinct G2-permutations of order q-2 [3].


### 2.3. A Comprehensive Example

Consider theW1-permutation f resulting from p=11, g=2, and c=0. The values corresponding to 0,1,…,9 are, in that order, 0, 1, 3, 7, 4, 9, 8, 6, 2, and 5. As mentioned above, f is an APN permutation when construed as a function from ℤ10 to ℤ10: in this case, all additions take place in arithmetic modulo 10, and we write, for example, that f(5+7)-f(5)=f(2)-f(5)=1-4=7. Note that, after generating f, we forget all about the prime number p used to generate it (in this case p=11): henceforth, all modulo operations take place in arithmetic modulo p-1=10, which is the size of the group ℤ10, in both the domain and the range.Considering, however,f as a Costas permutation from [10] to [10]; we see that f(5+7)-f(5)=f(12)-f(5) is undefined, because f(12) is undefined. On the other hand, f(2)-f(5)=1-4=-3, because addition takes place now in the usual integer arithmetic, in both the domain and the range.


### 2.4. Linearity

What does it mean for a functionf to be linear? In general, we will assume that both the domain D(f) and the range R(f) of the function are subsets of a ring R, and we will call f linear if and only if there exist three constants α,β,γ∈R such that αf(x)+βx=γ for all x∈D(f), where addition and multiplication are as defined in R. It is important to note that, occasionally, R can be chosen in more than one way: for example, in the example shown in Section 2.3 we may choose either R=ℤ or R=ℤ10, and this leads to different functions f, neither of which is linear, however.As another example, considerf defined on [10], where the values corresponding to 0,1,…,10 are, in this order, 0, 2, 4, 6, 8, 10, 1, 3, 5, 7, and 9. This function is not linear under ℤ-arithmetic. Since [10] is closed under arithmetic modulo 11, however, we may choose R=ℤ11, in which case f(x)=2x for all x∈ℤ11, and is, therefore, linear.


## 2.1. The Definitions

In what follows, let[n] denote the set {0,1,…,n-1}, and ℤn the additive group of integers modulo n, n∈ℕ*; in other words, [n] and ℤn differ just by the imposition of an algebraic structure on the latter, which makes it a ring. We are now ready to define the Costas permutation.Definition 2.1.
Consider a bijectionf:[n]→[n];fis a Costas permutation if and only if:
(2.1)∀i,j,ksuchthati,j,i+k,j+k∈[n],f(i+k)-f(i)=f(j+k)-f(j)⇒i=jork=0.
An alternative yet fully equivalent way to state this condition is to stipulate that, for any k∈[n]* and any l∈[n], the equation
(2.2)f(i+k)-f(i)=l,i∈[n-k],
has at most one root i.A permutationf corresponds to a permutation array Af=[ai,jf] by setting the elements of the permutation to denote the positions of the (unique) 1 in the corresponding column of the array, counting from top to bottom: af(i),if=1. It is customary to represent the 1s of a permutation array as “dots” and the 0s as “blanks”. From now on the terms “array” and “permutation” will be used interchangeably, in view of this correspondence.The Costas property is invariant under horizontal and vertical flips, as well as transposition (and therefore also under rotations of the array by multiples of90°, which can be expressed as combinations of the previous two operations), hence a Costas array gives birth to an equivalence class that contains either eight Costas arrays, or four if the array happens to be symmetric: this Costas array is then considered to be the unique representative of the equivalence class, and normally the array within the equivalence class that comes first in lexicographical order is selected for this purpose.We now give the definition of the APN function.Definition 2.2.
f:ℤn→ℤn is APN if and only if,for anyα∈ℤn*and anyβ∈ℤn, the equation
(2.3)f(x+α)-f(x)=β,x∈ℤn,
has at most two roots x.The relation of the two definitions becomes clearer if we also look at the definition of the Perfect Nonlinear (PN) function:Definition 2.3.
f:ℤn→ℤnis PN if and only if, for any α∈ℤn* and any β∈ℤn, the equation
(2.4)f(x+α)-f(x)=β,x∈ℤn,
has at most one root (hence exactly one root) x.We now see how close Definitions2.1 and 2.2 are. When we focus exclusively on permutations, thought, we see that a PN permutation is a contradiction in terms: by Definition 2.3, for any α, there has to be an x such that f(x+α)-f(x)=0, hence f cannot possibly be a permutation! Consequently, when studying permutations, we can only hope for the next best thing, namely, an APN permutation. Note that the definitions of a Costas permutation and of an APN function show that these two types of functions are far from being “linear”, namely, far from being similar to a “straight line”, since the distance vectors between pairs of points in the function graph are not, in general, allowed to be collinear.


## 2.2. Construction Methods for Costas Permutations

We will denote the finite field ofq elements by 𝔽(q), where q is, in general, a power of a prime. Recall that ℤp, p is a prime, is the finite field 𝔽(p).Algorithm 2.4 (Exponential Welch ConstructionW1(p,g,c)).
Letp be a prime, g a primitive root of the finite field 𝔽(p), and c∈[p-1]; the exponential Welch permutation of order p-1 corresponding to g and c is defined by
(2.5)f(i)=gi+cmodp-1,i∈[p-1].The inverse of an Exponential Welch permutation (corresponding to the transpose of the corresponding Costas array) is a Logarithmic Welch permutation, which is itself a Costas permutation. The two permutation sets are distinct forp>5 [10], implying that there are 2(p-1)ϕ(p-1) distinct Welch Costas permutations of order p-1. Here ϕ denotes Euler's totient function: ϕ(x), x∈ℕ, is the number of positive integers less than and relatively prime to x. In particular, there are no self-inverse W1-permutations (i.e., corresponding to symmetric Welch Costas arrays) for p>5.Algorithm 2.5 (Golomb ConstructionG2(q,a,b)).
Letq=pm, where p is a prime and m∈ℕ*, and let a, b be primitive roots of the finite field 𝔽(q); the Golomb permutation f of order q-2 corresponding to a and b is defined through the equation
(2.6)ai+1+bf(i)+1=1,i∈[q-2].There areϕ2(q-1)/m distinct G2-permutations of order q-2 [3].


## 2.3. A Comprehensive Example

Consider theW1-permutation f resulting from p=11, g=2, and c=0. The values corresponding to 0,1,…,9 are, in that order, 0, 1, 3, 7, 4, 9, 8, 6, 2, and 5. As mentioned above, f is an APN permutation when construed as a function from ℤ10 to ℤ10: in this case, all additions take place in arithmetic modulo 10, and we write, for example, that f(5+7)-f(5)=f(2)-f(5)=1-4=7. Note that, after generating f, we forget all about the prime number p used to generate it (in this case p=11): henceforth, all modulo operations take place in arithmetic modulo p-1=10, which is the size of the group ℤ10, in both the domain and the range.Considering, however,f as a Costas permutation from [10] to [10]; we see that f(5+7)-f(5)=f(12)-f(5) is undefined, because f(12) is undefined. On the other hand, f(2)-f(5)=1-4=-3, because addition takes place now in the usual integer arithmetic, in both the domain and the range.


## 2.4. Linearity

What does it mean for a functionf to be linear? In general, we will assume that both the domain D(f) and the range R(f) of the function are subsets of a ring R, and we will call f linear if and only if there exist three constants α,β,γ∈R such that αf(x)+βx=γ for all x∈D(f), where addition and multiplication are as defined in R. It is important to note that, occasionally, R can be chosen in more than one way: for example, in the example shown in Section 2.3 we may choose either R=ℤ or R=ℤ10, and this leads to different functions f, neither of which is linear, however.As another example, considerf defined on [10], where the values corresponding to 0,1,…,10 are, in this order, 0, 2, 4, 6, 8, 10, 1, 3, 5, 7, and 9. This function is not linear under ℤ-arithmetic. Since [10] is closed under arithmetic modulo 11, however, we may choose R=ℤ11, in which case f(x)=2x for all x∈ℤ11, and is, therefore, linear.


## 3. Linearity Measures for Discrete Functions

How can we quantify the linearity of a discrete function, and especially of a Costas permutation, in a meaningful way? There are essentially two different ways to proceed, according to whether we are willing/able to introduce some sort of an algebraic structure to the problem or not. Note that we will follow the convention of labeling the criteria we study below by𝕃 or ℕ𝕃, according to whether an increase in the value returned by the criterion implies increased linearity or nonlinearity for the tested function, respectively.


### 3.1. Linearity without Algebraic Structure

#### 3.1.1. Least Squares

In this version of the problem we are given a set ofn points (xi,yi=f(xi)), i∈[n] on the plane as an input, and we are asked to determine how closely they correspond to the graph of a linear function. The obvious course of action is to fit a line of the form c1x+c2y=c, c,c1,c2∈ℝ, according to some fitting criterion, and determine the error of the approximation. The smaller the error, the more “linear” f is. Perhaps the most frequently used fitting method used in such cases is the familiar least squares approximation.


#### 3.1.2. Nonmodular Phases

Within the same context, an alternative, completely different concept of linearity can be defined based on the distance vectors between pairs of points(xi-xj,f(xi)-f(xj)), i,j∈[n], i>j, where, without loss of generality we may assume that xi≥xj whenever i≥j: the function f is linear if and only if all such distance vectors have the same phase on the plane. A way to quantify this idea in a continuous way is to determine the unit vector with each such phase, sum the vectors, and find the length of the vector sum. In other words, we consider  (3.1)∑i>jexp(iϕf(xi,xj)),ϕf(xi,xj):=∠(xi-xj,f(xi)-f(xj)).
As there are n(n-1)/2 such vectors in total, the length of the vector sum will be n(n-1)/2 when f is linear and less than that otherwise. The normalized  (3.2)𝕃(f)=2n(n-1)|∑i>jexp(i∠(xi-xj,f(xi)-f(xj)))|
is then a number between 0 and 1: the larger it is, the more linear f is. In particular, since each phase is confined to (-π/2,π/2), we may substitute ∠(u,v) by tan-1(v/u). Given that  (3.3)eiu=cos(u)+isin(u),cos(u)=11+tan2(u),sin(u)=tan(u)1+tan2(u),
we can write  (3.4)𝕃(f)=2n(n-1)|∑x>y1+i((f(x)-f(y))/(x-y))1+((f(x)-f(y))/(x-y))2|=2n(n-1)|∑x>yx-y+i(f(x)-f(y))(x-y)2+(f(x)-f(y))2|.


#### 3.1.3. The Log-Ratio

In order to obtain a more sensitive measure of linearity, we observe that iff(x)=αx+β, we would get(3.5)∑x>yx-y(x-y)2+(f(x)-f(y))2=n(n-1)211+α2,∑x>yf(x)-f(y)(x-y)2+(f(x)-f(y))2=n(n-1)2α1+α2.
For a general function f, these two expressions yield two estimates for α, namely, α1 and α2, where we assume α1>α2 without loss of generality. The log-ratio ℕ𝕃c(f):=ln(α1/α2)≥0 is a kind of condition number for f: the larger it is, the more nonlinear f is, so we can use this log-ratio as a measure of the nonlinearity of f.


### 3.2. Linearity with Algebraic Structure

Let us reformulate the ideas presented above regarding distance vectors and their phases in the special case of a functionf:[n]→[n]. An indication of the linearity of f is the degree to which a constant multiple of x-y approximates (a constant multiple of) the difference f(x)-f(y), the approximation holding for all pairs (x,y), x,y∈[n]: in other words, we consider the functions F(α,β;x,y)=β(f(x)-f(y))-α(x-y) and we determine whether any specific choice of the parameters α and β leads to values that lie uniformly “close to” 0 for all pairs (x,y), according to some proximity criterion.A possible proximity criterion is again to apply “phase modulation”, namely, to allow the values ofF(α,β;x,y) to multiply the phase of complex exponential exp(iϕ), which represents a vector of unit length, and then find the length of the aggregate vectors and choose the longest one. This we define as the (square of the) linearity of f:  (3.6)𝕃a2(f)=supα,β∈ℝ∑x,y∈[n]ei[β(f(x)-f(y))-α(x-y)]ϕ=supα,β∈ℝ|∑x∈[n]ei[βf(x)-αx]ϕ|2.
Clearly, f is linear if and only if 𝕃(f)=n.Sincef is an integer function, and remembering that our ultimate goal is to introduce algebraic structure in the problem at some point, it makes sense to confine α and β to integer values as well. Choosing further ϕ=2π/N, N∈ℕ*, we effectively impose a modulo N addition and consider FmodN instead of F:  (3.7)𝕃N(f)=maxα,β|∑x∈[n]ei(2π/N)[βf(x)-αx]|.
Sometimes [9] it even makes sense to generalize the previous expression slightly and use two different integer parameters M and N as follows:  (3.8)𝕃M,N(f)=maxα,β|∑x∈[n]ei2π[β(f(x)/N)-α(x/M)]|,
though we will mostly focus on the simple case M=N from now on.So far we have not relatedN and n; how should we choose N for a given n? A first possibility is dictated by the extension of f to a function on ℤn, that is, f:ℤn→Zn, in which case the obvious choice would be N=n. Alternatively, considering still f as a function on [n], both x-y and f(x)-f(y), x,y∈[n] range from -(n-1) to n-1 included, so the range includes 2(n-1)+1=2n-1 distinct values and hence it suffices to choose N=2n-1, if our goal is to avoid any fold-over of values within this range. Finally, note that if f:ℤp-1→ℤp* is a W1-permutation, it makes sense to choose either M=N=p-1, as both the domain and the range contain p-1 elements, or M=p-1 and N=p, as these parameters reflect the natural modulo arithmetic in the domain and the range, respectively (both cases were studied in [9]).Let us finish this discussion by mentioning that1-𝕃n(f)/n has already been proposed as a measure of the nonlinearity of f:ℤn→ℤn in the literature [7, 8], though, in our opinion, the presentation therein was much less straightforward and intuitive than the one given here.


## 3.1. Linearity without Algebraic Structure

### 3.1.1. Least Squares

In this version of the problem we are given a set ofn points (xi,yi=f(xi)), i∈[n] on the plane as an input, and we are asked to determine how closely they correspond to the graph of a linear function. The obvious course of action is to fit a line of the form c1x+c2y=c, c,c1,c2∈ℝ, according to some fitting criterion, and determine the error of the approximation. The smaller the error, the more “linear” f is. Perhaps the most frequently used fitting method used in such cases is the familiar least squares approximation.


### 3.1.2. Nonmodular Phases

Within the same context, an alternative, completely different concept of linearity can be defined based on the distance vectors between pairs of points(xi-xj,f(xi)-f(xj)), i,j∈[n], i>j, where, without loss of generality we may assume that xi≥xj whenever i≥j: the function f is linear if and only if all such distance vectors have the same phase on the plane. A way to quantify this idea in a continuous way is to determine the unit vector with each such phase, sum the vectors, and find the length of the vector sum. In other words, we consider  (3.1)∑i>jexp(iϕf(xi,xj)),ϕf(xi,xj):=∠(xi-xj,f(xi)-f(xj)).
As there are n(n-1)/2 such vectors in total, the length of the vector sum will be n(n-1)/2 when f is linear and less than that otherwise. The normalized  (3.2)𝕃(f)=2n(n-1)|∑i>jexp(i∠(xi-xj,f(xi)-f(xj)))|
is then a number between 0 and 1: the larger it is, the more linear f is. In particular, since each phase is confined to (-π/2,π/2), we may substitute ∠(u,v) by tan-1(v/u). Given that  (3.3)eiu=cos(u)+isin(u),cos(u)=11+tan2(u),sin(u)=tan(u)1+tan2(u),
we can write  (3.4)𝕃(f)=2n(n-1)|∑x>y1+i((f(x)-f(y))/(x-y))1+((f(x)-f(y))/(x-y))2|=2n(n-1)|∑x>yx-y+i(f(x)-f(y))(x-y)2+(f(x)-f(y))2|.


### 3.1.3. The Log-Ratio

In order to obtain a more sensitive measure of linearity, we observe that iff(x)=αx+β, we would get(3.5)∑x>yx-y(x-y)2+(f(x)-f(y))2=n(n-1)211+α2,∑x>yf(x)-f(y)(x-y)2+(f(x)-f(y))2=n(n-1)2α1+α2.
For a general function f, these two expressions yield two estimates for α, namely, α1 and α2, where we assume α1>α2 without loss of generality. The log-ratio ℕ𝕃c(f):=ln(α1/α2)≥0 is a kind of condition number for f: the larger it is, the more nonlinear f is, so we can use this log-ratio as a measure of the nonlinearity of f.


## 3.1.1. Least Squares

In this version of the problem we are given a set ofn points (xi,yi=f(xi)), i∈[n] on the plane as an input, and we are asked to determine how closely they correspond to the graph of a linear function. The obvious course of action is to fit a line of the form c1x+c2y=c, c,c1,c2∈ℝ, according to some fitting criterion, and determine the error of the approximation. The smaller the error, the more “linear” f is. Perhaps the most frequently used fitting method used in such cases is the familiar least squares approximation.


## 3.1.2. Nonmodular Phases

Within the same context, an alternative, completely different concept of linearity can be defined based on the distance vectors between pairs of points(xi-xj,f(xi)-f(xj)), i,j∈[n], i>j, where, without loss of generality we may assume that xi≥xj whenever i≥j: the function f is linear if and only if all such distance vectors have the same phase on the plane. A way to quantify this idea in a continuous way is to determine the unit vector with each such phase, sum the vectors, and find the length of the vector sum. In other words, we consider  (3.1)∑i>jexp(iϕf(xi,xj)),ϕf(xi,xj):=∠(xi-xj,f(xi)-f(xj)).
As there are n(n-1)/2 such vectors in total, the length of the vector sum will be n(n-1)/2 when f is linear and less than that otherwise. The normalized  (3.2)𝕃(f)=2n(n-1)|∑i>jexp(i∠(xi-xj,f(xi)-f(xj)))|
is then a number between 0 and 1: the larger it is, the more linear f is. In particular, since each phase is confined to (-π/2,π/2), we may substitute ∠(u,v) by tan-1(v/u). Given that  (3.3)eiu=cos(u)+isin(u),cos(u)=11+tan2(u),sin(u)=tan(u)1+tan2(u),
we can write  (3.4)𝕃(f)=2n(n-1)|∑x>y1+i((f(x)-f(y))/(x-y))1+((f(x)-f(y))/(x-y))2|=2n(n-1)|∑x>yx-y+i(f(x)-f(y))(x-y)2+(f(x)-f(y))2|.


## 3.1.3. The Log-Ratio

In order to obtain a more sensitive measure of linearity, we observe that iff(x)=αx+β, we would get(3.5)∑x>yx-y(x-y)2+(f(x)-f(y))2=n(n-1)211+α2,∑x>yf(x)-f(y)(x-y)2+(f(x)-f(y))2=n(n-1)2α1+α2.
For a general function f, these two expressions yield two estimates for α, namely, α1 and α2, where we assume α1>α2 without loss of generality. The log-ratio ℕ𝕃c(f):=ln(α1/α2)≥0 is a kind of condition number for f: the larger it is, the more nonlinear f is, so we can use this log-ratio as a measure of the nonlinearity of f.


## 3.2. Linearity with Algebraic Structure

Let us reformulate the ideas presented above regarding distance vectors and their phases in the special case of a functionf:[n]→[n]. An indication of the linearity of f is the degree to which a constant multiple of x-y approximates (a constant multiple of) the difference f(x)-f(y), the approximation holding for all pairs (x,y), x,y∈[n]: in other words, we consider the functions F(α,β;x,y)=β(f(x)-f(y))-α(x-y) and we determine whether any specific choice of the parameters α and β leads to values that lie uniformly “close to” 0 for all pairs (x,y), according to some proximity criterion.A possible proximity criterion is again to apply “phase modulation”, namely, to allow the values ofF(α,β;x,y) to multiply the phase of complex exponential exp(iϕ), which represents a vector of unit length, and then find the length of the aggregate vectors and choose the longest one. This we define as the (square of the) linearity of f:  (3.6)𝕃a2(f)=supα,β∈ℝ∑x,y∈[n]ei[β(f(x)-f(y))-α(x-y)]ϕ=supα,β∈ℝ|∑x∈[n]ei[βf(x)-αx]ϕ|2.
Clearly, f is linear if and only if 𝕃(f)=n.Sincef is an integer function, and remembering that our ultimate goal is to introduce algebraic structure in the problem at some point, it makes sense to confine α and β to integer values as well. Choosing further ϕ=2π/N, N∈ℕ*, we effectively impose a modulo N addition and consider FmodN instead of F:  (3.7)𝕃N(f)=maxα,β|∑x∈[n]ei(2π/N)[βf(x)-αx]|.
Sometimes [9] it even makes sense to generalize the previous expression slightly and use two different integer parameters M and N as follows:  (3.8)𝕃M,N(f)=maxα,β|∑x∈[n]ei2π[β(f(x)/N)-α(x/M)]|,
though we will mostly focus on the simple case M=N from now on.So far we have not relatedN and n; how should we choose N for a given n? A first possibility is dictated by the extension of f to a function on ℤn, that is, f:ℤn→Zn, in which case the obvious choice would be N=n. Alternatively, considering still f as a function on [n], both x-y and f(x)-f(y), x,y∈[n] range from -(n-1) to n-1 included, so the range includes 2(n-1)+1=2n-1 distinct values and hence it suffices to choose N=2n-1, if our goal is to avoid any fold-over of values within this range. Finally, note that if f:ℤp-1→ℤp* is a W1-permutation, it makes sense to choose either M=N=p-1, as both the domain and the range contain p-1 elements, or M=p-1 and N=p, as these parameters reflect the natural modulo arithmetic in the domain and the range, respectively (both cases were studied in [9]).Let us finish this discussion by mentioning that1-𝕃n(f)/n has already been proposed as a measure of the nonlinearity of f:ℤn→ℤn in the literature [7, 8], though, in our opinion, the presentation therein was much less straightforward and intuitive than the one given here.


## 4. Results

In this section we discuss the results obtained for each (non)linearity criterion through simulation. Simulation has been used extensively in recent times for the study of the properties of Costas arrays (see, e.g., [12, 13]).


### 4.1. Least Squares

Whenf is a Costas permutation of order n, linear least squares fitting fails to reveal any meaningful information, precisely because the points are very dispersed on the n×n square, owing to the Costas property. Computer simulations confirm our expectations in that the line fitted by least squares is invariably either horizontal or vertical, while the line fitted by orthogonal least squares, namely the variant of the method where the sum of the square distances of the points from the fitted line is minimized, yields invariably either y=x or y=n-1-x as the fitted line. To conclude, Costas arrays are so far from being linear that it makes no sense to measure how far from linearity they are using this criterion.


### 4.2. Nonmodular Phases

The real part of the vector sum (3.4) is in general much larger than the imaginary part, precisely because we always choose x>y, so the real parts of the summands add constructively. This, in turn, implies that this criterion is not sensitive enough. For example, Figure 1 shows the histograms of 𝕃 over all Costas arrays of order 15 and over an equinumerous collection of randomly chosen permutations of order 15: though the histograms look different, the range of the former lies entirely within the range of the latter, so this criterion is not sensitive enough to determine that Costas permutations are more nonlinear than random permutations.The histograms of all Costas permutations of order 15 (a) and an equinumerous collection of randomly chosen permutations of order 15 (b), according to𝕃: Costas permutations are shown to be more nonlinear.
(a)(b)


### 4.3. The Log-Ratio

What if𝕃c is used instead of 𝕃? The log-ratio histograms for all Costas permutations of order 15 and an equinumerous collection of random permutations of order 15, as well as the log-ratio histograms for all Costas permutations of order 16 and for all algebraically constructed Costas permutations of order 16 are shown in Figure 2. Costas permutations are indeed found to be more nonlinear than random ones, even if only slightly so: though the random permutations histogram contains a few outliers at higher values, its main body lies clearly at smaller values compared to the Costas permutations histogram. Similarly, algebraically constructed Costas permutations are observed to be, on average, some of the most linear Costas permutations.(a, b) the log-ratio histograms of all Costas permutations of order 15 (a) and an equinumerous collection of randomly chosen permutations of order 15 (b); Costas permutations are shown to be more nonlinear. (c, d) the log-ratio histograms of all Costas permutations of order 16 (c) and of all algebraically constructed Costas permutations of order 16 (d); algebraically constructed Costas permutations seem to be amongst the most linear ones.
(a)(b)(c)(d)


### 4.4. Linearity with Algebraic Structure

We computed the linearity of several families of Costas permutations, using𝕃2n-1 as the measure of linearity, n being the order of the Costas permutation. More specifically, we focused on the families of all Costas permutations of order 27 and below (Table 1), and on the families of W1- and G2-permutations generated in 𝔽(p), 3≤p≤151 (Table 2). For each family we recorded the minimal and maximal linearities found, the mean linearity and the standard deviation.Table 1
Linearity results for all Costas permutations of orders3≤n≤27: the columns correspond from left to right to n, the minimal and maximal linearities observed, and the mean and standard deviations of the linearity.
nmin𝕃max𝕃mean𝕃std𝕃32.49722.49722.4972042.97503.70693.50830.304653.48864.34593.89020.274163.72445.10084.39180.383474.15345.17864.64960.298884.42345.92415.02750.296494.70156.82185.54970.3621104.93017.47565.88750.3519115.19137.66106.26600.3775125.48158.53416.59520.3965135.90158.72616.91150.4053146.20149.43887.22700.4082156.21869.85197.53330.4320166.515911.01867.85090.4521176.958211.40458.13150.4465187.184612.96608.41670.4811197.516512.44718.71360.4935207.757911.84798.94610.4815217.989413.91959.26450.5443228.160315.23239.81220.9286238.637614.74809.91750.8786248.702815.975610.25081.0853259.725616.586111.16841.5209269.401914.827511.57881.60352710.250216.872912.10961.4790Table 2
Linearity results forW1- (a) and G2- (b) permutations generated in 𝔽(p), 7≤p≤151: the columns correspond from left to right to p, the minimal and maximal linearity observed, and the mean and standard deviations of the linearities.
(a)pmin𝕃max𝕃mean𝕃std𝕃73.83443.83443.83440114.70156.55985.93620.6950135.19137.54146.49480.8282176.21879.31257.80760.7503197.695511.40458.98870.8291238.234713.91959.97971.12942910.250216.872912.05151.43183110.967716.058413.09761.47723711.289220.587114.83512.11804112.728921.629216.10722.22664312.610926.928017.15952.71434713.682028.331118.36782.59445314.748329.080720.73233.45505916.524033.810523.12383.74936118.020335.198723.86613.58716717.992438.690126.22754.05157119.237836.415127.69383.98077318.182343.109628.63514.71677919.447141.346330.93274.20148321.238845.447832.56264.27638921.342150.358035.03114.61159724.660653.288838.25124.687610127.187952.600739.83795.079610325.417855.259840.65395.548210727.322257.938242.26015.451810924.982659.981043.11395.511311329.613260.627344.70295.680812732.515170.135350.49635.348713131.287970.719851.98305.758113737.295571.095854.43375.756613939.284571.456155.28876.365314940.543476.098159.29186.076415137.417081.033360.10706.0674(b)pmin𝕃max𝕃mean𝕃std𝕃73.78804.84394.44650.4119115.50537.47566.14620.4734136.51548.53417.30520.6860177.050111.01868.57790.8158197.517212.96609.28071.1130238.925415.232310.69361.21872910.333118.319212.95651.83573110.919219.977013.56351.64043711.964324.364215.78002.58234112.786325.172017.17712.88224312.741925.332217.85913.06734714.021228.162719.12283.26895315.006633.397021.59393.84455916.431635.521323.59664.33406116.290236.133124.36844.55476717.447939.855326.72674.91727118.422540.798528.28505.09887318.324442.126729.04825.14307918.563547.833131.44865.55268320.010149.178033.03525.69578921.253451.471735.42185.57419722.198657.746438.66176.228810122.994456.865640.28686.602010325.536257.279641.08556.560610724.094163.604542.70786.593010924.788864.262343.51236.642711326.501764.305445.13977.010712735.198065.918050.76446.175313130.977773.944152.43227.410113732.774077.696854.85847.562613931.617079.506755.66647.573214935.030683.290959.71937.805215136.342384.354060.53948.0897As a general observation, the linearity histograms for all families are well approximated by Gaussian distributions (see, e.g., Figure3), provided the families contain enough Costas permutations (at least a few hundred). Furthermore, the mean linearities 𝕃¯W(n) and 𝕃¯G(n) for W1- and G2-permutations of order n, respectively, seem to increase asymptotically linearly with n (see Figure 4): 𝕃¯G(n)≈𝕃¯W(n)≈0.4035n. Furthermore, it is clear from Figure 3 that 𝕃2n-1 successfully distinguishes Costas permutations from random permutations, assigning on average smaller linearity to the former.The linearity histogram of all Costas permutations of order 15 (a) is well approximated by the Gaussian of the same mean and variance, but the corresponding histogram of order 27 (c) is not, due to the small number of samples. Furthermore, the linearity criterion is efficient: histograms show that the linearity of Costas permutations of order 15 is clearly less than that of an equinumerous collection of randomly chosen permutations of order 15 (b).
(a)(b)(c)(a) plot of the minimal, maximal, and mean linearities for the Welch and Golomb family generated in𝔽(p), 3≤p≤151. (b) plot of the mean linearity divided by the order, indicating convergence near 0.4. (c) a detail of the tail of the previous plot.
(a)(b)(c)


## 4.1. Least Squares

Whenf is a Costas permutation of order n, linear least squares fitting fails to reveal any meaningful information, precisely because the points are very dispersed on the n×n square, owing to the Costas property. Computer simulations confirm our expectations in that the line fitted by least squares is invariably either horizontal or vertical, while the line fitted by orthogonal least squares, namely the variant of the method where the sum of the square distances of the points from the fitted line is minimized, yields invariably either y=x or y=n-1-x as the fitted line. To conclude, Costas arrays are so far from being linear that it makes no sense to measure how far from linearity they are using this criterion.


## 4.2. Nonmodular Phases

The real part of the vector sum (3.4) is in general much larger than the imaginary part, precisely because we always choose x>y, so the real parts of the summands add constructively. This, in turn, implies that this criterion is not sensitive enough. For example, Figure 1 shows the histograms of 𝕃 over all Costas arrays of order 15 and over an equinumerous collection of randomly chosen permutations of order 15: though the histograms look different, the range of the former lies entirely within the range of the latter, so this criterion is not sensitive enough to determine that Costas permutations are more nonlinear than random permutations.The histograms of all Costas permutations of order 15 (a) and an equinumerous collection of randomly chosen permutations of order 15 (b), according to𝕃: Costas permutations are shown to be more nonlinear.
(a)(b)


## 4.3. The Log-Ratio

What if𝕃c is used instead of 𝕃? The log-ratio histograms for all Costas permutations of order 15 and an equinumerous collection of random permutations of order 15, as well as the log-ratio histograms for all Costas permutations of order 16 and for all algebraically constructed Costas permutations of order 16 are shown in Figure 2. Costas permutations are indeed found to be more nonlinear than random ones, even if only slightly so: though the random permutations histogram contains a few outliers at higher values, its main body lies clearly at smaller values compared to the Costas permutations histogram. Similarly, algebraically constructed Costas permutations are observed to be, on average, some of the most linear Costas permutations.(a, b) the log-ratio histograms of all Costas permutations of order 15 (a) and an equinumerous collection of randomly chosen permutations of order 15 (b); Costas permutations are shown to be more nonlinear. (c, d) the log-ratio histograms of all Costas permutations of order 16 (c) and of all algebraically constructed Costas permutations of order 16 (d); algebraically constructed Costas permutations seem to be amongst the most linear ones.
(a)(b)(c)(d)


## 4.4. Linearity with Algebraic Structure

We computed the linearity of several families of Costas permutations, using𝕃2n-1 as the measure of linearity, n being the order of the Costas permutation. More specifically, we focused on the families of all Costas permutations of order 27 and below (Table 1), and on the families of W1- and G2-permutations generated in 𝔽(p), 3≤p≤151 (Table 2). For each family we recorded the minimal and maximal linearities found, the mean linearity and the standard deviation.Table 1
Linearity results for all Costas permutations of orders3≤n≤27: the columns correspond from left to right to n, the minimal and maximal linearities observed, and the mean and standard deviations of the linearity.
nmin𝕃max𝕃mean𝕃std𝕃32.49722.49722.4972042.97503.70693.50830.304653.48864.34593.89020.274163.72445.10084.39180.383474.15345.17864.64960.298884.42345.92415.02750.296494.70156.82185.54970.3621104.93017.47565.88750.3519115.19137.66106.26600.3775125.48158.53416.59520.3965135.90158.72616.91150.4053146.20149.43887.22700.4082156.21869.85197.53330.4320166.515911.01867.85090.4521176.958211.40458.13150.4465187.184612.96608.41670.4811197.516512.44718.71360.4935207.757911.84798.94610.4815217.989413.91959.26450.5443228.160315.23239.81220.9286238.637614.74809.91750.8786248.702815.975610.25081.0853259.725616.586111.16841.5209269.401914.827511.57881.60352710.250216.872912.10961.4790Table 2
Linearity results forW1- (a) and G2- (b) permutations generated in 𝔽(p), 7≤p≤151: the columns correspond from left to right to p, the minimal and maximal linearity observed, and the mean and standard deviations of the linearities.
(a)pmin𝕃max𝕃mean𝕃std𝕃73.83443.83443.83440114.70156.55985.93620.6950135.19137.54146.49480.8282176.21879.31257.80760.7503197.695511.40458.98870.8291238.234713.91959.97971.12942910.250216.872912.05151.43183110.967716.058413.09761.47723711.289220.587114.83512.11804112.728921.629216.10722.22664312.610926.928017.15952.71434713.682028.331118.36782.59445314.748329.080720.73233.45505916.524033.810523.12383.74936118.020335.198723.86613.58716717.992438.690126.22754.05157119.237836.415127.69383.98077318.182343.109628.63514.71677919.447141.346330.93274.20148321.238845.447832.56264.27638921.342150.358035.03114.61159724.660653.288838.25124.687610127.187952.600739.83795.079610325.417855.259840.65395.548210727.322257.938242.26015.451810924.982659.981043.11395.511311329.613260.627344.70295.680812732.515170.135350.49635.348713131.287970.719851.98305.758113737.295571.095854.43375.756613939.284571.456155.28876.365314940.543476.098159.29186.076415137.417081.033360.10706.0674(b)pmin𝕃max𝕃mean𝕃std𝕃73.78804.84394.44650.4119115.50537.47566.14620.4734136.51548.53417.30520.6860177.050111.01868.57790.8158197.517212.96609.28071.1130238.925415.232310.69361.21872910.333118.319212.95651.83573110.919219.977013.56351.64043711.964324.364215.78002.58234112.786325.172017.17712.88224312.741925.332217.85913.06734714.021228.162719.12283.26895315.006633.397021.59393.84455916.431635.521323.59664.33406116.290236.133124.36844.55476717.447939.855326.72674.91727118.422540.798528.28505.09887318.324442.126729.04825.14307918.563547.833131.44865.55268320.010149.178033.03525.69578921.253451.471735.42185.57419722.198657.746438.66176.228810122.994456.865640.28686.602010325.536257.279641.08556.560610724.094163.604542.70786.593010924.788864.262343.51236.642711326.501764.305445.13977.010712735.198065.918050.76446.175313130.977773.944152.43227.410113732.774077.696854.85847.562613931.617079.506755.66647.573214935.030683.290959.71937.805215136.342384.354060.53948.0897As a general observation, the linearity histograms for all families are well approximated by Gaussian distributions (see, e.g., Figure3), provided the families contain enough Costas permutations (at least a few hundred). Furthermore, the mean linearities 𝕃¯W(n) and 𝕃¯G(n) for W1- and G2-permutations of order n, respectively, seem to increase asymptotically linearly with n (see Figure 4): 𝕃¯G(n)≈𝕃¯W(n)≈0.4035n. Furthermore, it is clear from Figure 3 that 𝕃2n-1 successfully distinguishes Costas permutations from random permutations, assigning on average smaller linearity to the former.The linearity histogram of all Costas permutations of order 15 (a) is well approximated by the Gaussian of the same mean and variance, but the corresponding histogram of order 27 (c) is not, due to the small number of samples. Furthermore, the linearity criterion is efficient: histograms show that the linearity of Costas permutations of order 15 is clearly less than that of an equinumerous collection of randomly chosen permutations of order 15 (b).
(a)(b)(c)(a) plot of the minimal, maximal, and mean linearities for the Welch and Golomb family generated in𝔽(p), 3≤p≤151. (b) plot of the mean linearity divided by the order, indicating convergence near 0.4. (c) a detail of the tail of the previous plot.
(a)(b)(c)


## 5. Conclusion

We proposed various (non)linearity measures for Costas permutations, divided in two broad categories, according to whether we are willing to impose some algebraic structure on the domain and the range or not. Amongst the measures that do not take advantage of any algebraic structure, the linear least squares fit was found inappropriate, as it was completely insensitive to the input, the nonmodular phases criterion was found not to be sensitive enough, while the log-ratio performed adequately in terms of distinguishing Costas permutations from randomly chosen permutations of the same order and correctly deciding that the former are more nonlinear than the latter; it also suggested that algebraically constructed Costas permutations are amongst the most linear Costas permutations. On the other hand, when the difference vectors are combined with an underlying modulo structure, the resulting criterion is sensitive enough to recognize that Costas permutations are less linear than randomly chosen permutations of the same order.



---

*Source: 149658-2010-06-21.xml*