# On Costas Sets and Costas Clouds

Authors: Konstantinos Drakakis
Journal: Abstract and Applied Analysis
 (2009)

---

## Abstract

We abstract the definition of the Costas property in the context of a group and study specifically dense
Costas sets (named Costas clouds) in groups with the topological property that they are dense in themselves:
as a result, we prove the existence of nowhere continuous dense bijections that satisfy the Costas property onℚ2, ℝ2, and ℂ2, the latter two being based on nonlinear solutions of Cauchy's functional equation, as well as on
ℚ, ℝ, and ℂ, which are, in effect, generalized Golomb rulers. We generalize the Welch and Golomb construction
methods for Costas arrays to apply on ℝ and ℂ, and we prove that group isomorphisms on and tensor products of Costas sets result to new Costas sets with respect to an appropriate set of distance vectors. We also give two constructive examples of a nowhere continuous function that satisfies a constrained form of the Costas property (over rational or algebraic displacements only, i.e.), based on the indicator function of a dense subset of ℝ.


---

## Body

## 1. Introduction

Costas arrays are square arrangements of dots and blanks such that there is exactly one dot per row and column (i.e., permutation arrays), and such that no four dots form a parallelogram and no three dots on the same straight line are equidistant. They arose in the 1960s in connection with the development of SONAR/RADAR frequency-hopped waveforms with ideal autocorrelation properties [1, 2] but have been the subject of increasingly intensive mathematical study ever since Professor S. Golomb published in 1984 [3, 4] some algebraic construction techniques (still the only ones available today) based on finite fields. Mathematicians are mainly concerned with the study of properties of Costas arrays but also with the settlement of the question of their existence for all orders, which, despite all efforts, still remains open.Golomb rulers are 1D analogs of Costas arrays: they are linear arrangements of dots and blanks such that no distance between pairs of dots is repeated. The term “ruler’’ arises from the equivalent visualization as a ruler with markings at the integers, where the dots correspond to those markings that get selected. Golomb rulers are, in fact, older than Costas arrays themselves, originally described as Sidon sets, namely, sets of integers whose pairwise sums are all distinct (a moment's reflection shows that the two definitions are completely equivalent).A deeper study of the Costas property, which we attempt in this work, reveals that it requires surprisingly little, namely, only an underlying algebraic group structure. After recognizing that some parts of the definition of a Costas array are actually additional, peripheral requirements, imposed for convenience by the nature of the engineering application, but not essential (even for the application itself), we show that Costas arrays and Golomb rulers are essentially instantiations of the same concept/property over different groups.Though this approach opens the door for the study of “exotic’’ Costas structures on arbitrary algebraic groups (possibly nonAbelian), we restrict our attention almost immediately on groups with the analytic property of being dense in themselves, and in particular the fieldsℚ, ℝ, and ℂ. Indeed, Costas arrays tend to be very irregular: large arrays look like “clouds’’ of dots scattered all over (see Figure 1). Similarly, the density of dots in Golomb rulers appears to be very uneven. Naturally, when one contemplates possible generalizations of Costas arrays to these three fields (namely, subsets of ℚ2, ℝ2, and ℂ2 with the Costas property, or generalizations of Golomb rulers on ℚ, ℝ, and ℂ), one's first instinct would most likely dictate that these sets, if they exist at all, will be very irregular.Figure 1
An example of a Costas array of order 27: note the haphazard positioning of its dots.In a previous work [5] we considered bijections with the Costas property on ℚ and ℝ, and we arrived at the (perhaps surprising) result that not only such functions exist that are as regular as possible, namely, (infinitely) smooth but also that irregular (e.g., nowhere continuous) examples are nontrivial to come by; indeed, no such example was given there.In this work, which can be construed as a continuation of [5], albeit independent and self-contained, we prove the existence of dense (within the appropriate set) countable and uncountable Costas sets, taking advantage of discontinuous solutions of Cauchy's integral equation. We also construct explicitly two examples of nowhere continuous Costas bijections, using nowhere continuous indicator functions of dense subsets of the real line as building blocks.


## 2. Basics—The Costas Property

### 2.1. Notation

We denote the set of the firstn integers {1,2,…,n} by [n], and more generally the set {α+β,α+2β,…,α+nβ} by α+β[n]; in particular, [n]-1={0,1,…,n-1}. The set of algebraic real numbers, namely, those real numbers that can be solutions of polynomials with rational (or, equivalently, integer) coefficients, is denoted by ℙ; note that this set includes not only ℚ but also many irrational numbers. For any subset A of a group G under operation ⊗ with identity element e we set A*:=A∖{e}, while, for any g∈G, we also set g⊗A:={g⊗a:a∈A}.


### 2.2. Definition

In this section we provide an overview of the Costas property and, at the same time, an appropriate generalization to an arbitrary group; usually the Costas property is defined on[n] [6].Definition 2.1.
LetG be a group under operation ⊗ and let C,D⊂G. C will be called a left Costas set in G with respect to the distance vectors subgroupD, or simply a left Costas set if D=G*, if and only if
(2.1)∀d∈D*:|(d⊗C)∩C|≤1,
or, equivalently, if and only if
(2.2)∀d∈D*,∀c1,c2∈C,d⊗c1,d⊗c2∈C⇒c1=c2.
A right Costas set is defined by substituting d⊗C by C⊗d. If G is Abelian, the two definitions coincide.Remark 2.2.
LetG=G1×G2 be a Cartesian group; then C can be represented by points on the plane whose axes represent the points of G1 and G2, respectively, and its elements are ordered pairs of the form c=(c1,c2), c1∈G1, c2∈G2. Assuming that C has either of the properties that each g1∈G1 appears as the first coordinate of a c∈C at most once, or that each g2∈G2 appears as the second coordinate of a c∈C at most once, C represents the graph of a function with the Costas property (a Costas function, for short) from (a subset of) G1 to G2 or from (a subset of) G2 to G1, respectively. If both properties hold, the Costas function is injective, hence bijective by an appropriate redefinition of its domain and range.Remark 2.3.
The elements ofD can be considered as vectors (as opposed to scalars) when G=G1×⋯×Gk is a tensor product of k>1 groups. In that case C can be interpreted geometrically to lie in a k-dimensional space, and d⊗C, d={d1,…,dk}∈D to be a shifted version of C by di in dimension i, i∈[k]. In particular, the Costas property forbids the existence of c1,c2∈C, c1≠c2, such that, for some d∈D, d⊗c1, d⊗c2∈D: no four points in C can form a “parallelogram’’ (under ⊗), and no three points in C can be both on a straight line and equidistant.Remark 2.4.
Letf:C1⊂G1→G2 be a function; an equivalent definition of the Costas property with respect to D is then that
(2.3)∀d∈D1*,∀x,y∈C1:d⊗x,d⊗y∈C1,f(x⊗d)-f(x)=f(y⊗d)-f(y)⇒x=y,
where D1={d∈G1∣∃d2∈G2:(d1,d2)∈D}.Remark 2.5.
The usual definition of a Costas bijection usesG=ℤ×ℤ, ⊗=+, D=ℤ*, and C⊂[n]×[n], n∈ℕ, with the additional requirement that C is the graph of a bijection on [n] [1, 2, 6]. Costas arrays are mapped bijectively to Costas permutations using the convention that the ith element of the permutation indicates the position of the dot in the ith column of the array. Henceforth the terms “Costas array’’ and “Costas permutation’’ will be used interchangeably. Figure 1 shows a Costas array of order 27.
Similarly, the definition of a Golomb ruler usesG=ℤ, ⊗=+, D=ℤ*, and C⊂[n+1]-1, n∈ℕ, so that 0,n∈C. The length of this Golomb ruler is defined to be n (this agrees with the usual concept of the term of a physical ruler), while, if |C|=m∈ℕ, the Golomb ruler is said to have m markings.Remark 2.6.
Historically, the Costas property has been construed to include bijectivity: this is because the original engineering application that introduced Costas arrays does not benefit any further from nonbijective Costas sets, namely, Costas arrays with two or more dots on the same row or column, though such Costas arrays can still be used successfully [1, 2]. In this work, bijectivity/injectivity is no longer considered to be a formally required component of the Costas property; in fact, the Costas set may not even be the graph of a function. Respecting tradition, however, we will endeavor to provide examples of injective Costas functions.Remark 2.7.
A direct consequence of the definition is that for alld∈D, d⊗C is also a Costas set with respect to D. In particular, Golomb rulers can be shifted over the integers and still retain the Costas property, and so do Costas arrays if shifted in either direction.We finally specialize the definition of a Costas set on groups that are dense in themselves.Definition 2.8 (Costas clouds).
LetG in Definition 2.1 be dense in itself, and let D=G. Whenever a Costas set C is dense in G, it will be called a Costas cloud.In particular, Costas clouds can exist inℚ, ℝ, ℂ or powers thereof (ℚ2, etc.).


### 2.3. Construction of Costas Permutations

Two algebraic construction methods exist for Costas permutations [3, 4, 6]. Let us review them briefly without proof, as they will be needed later.


#### 2.3.1. The Welch Construction

Theorem 2.9 (Welch constructionW1(p,α,c)).
Letp be a prime, let α be a primitive root of the finite field 𝔽(p) of p elements, and let c∈[p-1]-1 be a constant; then, the function f:[p-1]→[p-1] where f(i)=αi-1+cmodp is a bijection with the Costas property.The reason for the presence of-1 in the exponent is that, when c=0, 1 is a fixed point: f(1)=1. We refer to arrays generated with c≠0 as circular shifts of the array generated by c=0 for the same p and α.


#### 2.3.2. The Golomb Construction

Theorem 2.10 (Golomb constructionG2(p,m,a,b)).
Letp be a prime, m∈ℕ, and let α, β be primitive roots of the finite field 𝔽(pm) of q=pm elements; then, the function f:[q-2]→[q-2] where αi+βf(i)=1 is a bijection with the Costas property.


### 2.4. Constructions for Golomb Rulers/Sidon Sets

Golomb rulers, though bearing the name of Professor S. Golomb, were originally described by W. C. Babcock in the context of an application in telecommunications [7]. It later emerged that they had made their appearance even earlier in the context of harmonic analysis, in a completely equivalent formulation, known as Sidon sets [8]. In this work, the two terms will be used interchangeably. A very comprehensive source of information about Golomb rulers is [9].Definition2.1, in the context of Remark 2.5, yields the usual definition of Golomb rulers/Sidon sets.Definition 2.11.
LetS⊂[n+1]-1, n∈ℕ, so that 0,n∈S. S is a Sidon set or a Golomb ruler if and only if
(2.4)∀x1,x2,x3,x4∈S:x1+x2=x3+x4⇔x1-x3=x4-x2⇔{x1,x2}={x3,x4}.The sum version corresponds to Sidon sets, the difference version to Golomb rulers: they are obviously equivalent. What is the relation betweenm=|S| and n? In particular, what is the smallest n for a given m? What is the largest m for a given n? Golomb rulers that satisfy either of these conditions are dubbed optimal. It is conjectured [9] that optimal Golomb rulers asymptotically satisfy the condition
(2.5)m≈n.Though they will not be needed further in this work, and for the sake of completeness only, we also present some construction methods for Golomb rulers. Note that, contrary to the case of Costas arrays, where the order specifies the number of dots, the definition of a Golomb ruler does not relate the length to the number of markings in any way. Needless to say, construction methods for Golomb rulers considered to be of interest tend to produce reasonably densely populated Golomb rulers, and, in particular, families that asymptotically satisfy (2.5).


#### 2.4.1. Erdös-Turan Construction [10, 11]

Theorem 2.12.
For every primep, the sequence
(2.6)2pk+(k2modp),k∈[p]-1
forms a Golomb ruler.The approximate asymptotic length of such a Golomb ruler withp markings is 2p2; hence it deviates from optimality by a factor of 2.


#### 2.4.2. Rusza-Lindström Construction [12, 13]

Theorem 2.13.
Letp be prime, g a primitive root of 𝔽(p), and s relatively prime to p-1. The following sequence
(2.7)(psk+(p-1)gk)modp(p-1),k∈[p-1]-1
forms a Golomb ruler.These rulers are of length (at most)p(p-1) and have p-1 markings; hence they are optimal.


#### 2.4.3. Bose-Chowla Construction [14, 15]

Theorem 2.14.
Letq=pn be a power of a prime and g a primitive root in 𝔽(q2). Then the q integers
(2.8)S={i∈[q2-2]:gi-g∈𝔽(q)}
have distinct pairwise differences modulo q2-1.
In addition, the set ofq(q-1) pairwise differences in S, reduced modulo q2-1, equals the set of all nonzero integers less than q2-1 which are not divisible by q+1.These rulers are optimal: they haveq markings and their length is (at most) q2-1.


#### 2.4.4. An Always Applicable Construction [9]

The previous constructions work only when the number of markings is a (power ofa) prime. The following construction works always but, unfortunately, is far from optimal.Theorem 2.15.
For anyn∈ℕ*, and for a fixed a∈{1,2}, the sequence
(2.9)ank2+k,k∈[n]-1
forms a Golomb ruler.This ruler hasn markings and its length is asymptotically an3; hence it is far from optimal.


## 2.1. Notation

We denote the set of the firstn integers {1,2,…,n} by [n], and more generally the set {α+β,α+2β,…,α+nβ} by α+β[n]; in particular, [n]-1={0,1,…,n-1}. The set of algebraic real numbers, namely, those real numbers that can be solutions of polynomials with rational (or, equivalently, integer) coefficients, is denoted by ℙ; note that this set includes not only ℚ but also many irrational numbers. For any subset A of a group G under operation ⊗ with identity element e we set A*:=A∖{e}, while, for any g∈G, we also set g⊗A:={g⊗a:a∈A}.


## 2.2. Definition

In this section we provide an overview of the Costas property and, at the same time, an appropriate generalization to an arbitrary group; usually the Costas property is defined on[n] [6].Definition 2.1.
LetG be a group under operation ⊗ and let C,D⊂G. C will be called a left Costas set in G with respect to the distance vectors subgroupD, or simply a left Costas set if D=G*, if and only if
(2.1)∀d∈D*:|(d⊗C)∩C|≤1,
or, equivalently, if and only if
(2.2)∀d∈D*,∀c1,c2∈C,d⊗c1,d⊗c2∈C⇒c1=c2.
A right Costas set is defined by substituting d⊗C by C⊗d. If G is Abelian, the two definitions coincide.Remark 2.2.
LetG=G1×G2 be a Cartesian group; then C can be represented by points on the plane whose axes represent the points of G1 and G2, respectively, and its elements are ordered pairs of the form c=(c1,c2), c1∈G1, c2∈G2. Assuming that C has either of the properties that each g1∈G1 appears as the first coordinate of a c∈C at most once, or that each g2∈G2 appears as the second coordinate of a c∈C at most once, C represents the graph of a function with the Costas property (a Costas function, for short) from (a subset of) G1 to G2 or from (a subset of) G2 to G1, respectively. If both properties hold, the Costas function is injective, hence bijective by an appropriate redefinition of its domain and range.Remark 2.3.
The elements ofD can be considered as vectors (as opposed to scalars) when G=G1×⋯×Gk is a tensor product of k>1 groups. In that case C can be interpreted geometrically to lie in a k-dimensional space, and d⊗C, d={d1,…,dk}∈D to be a shifted version of C by di in dimension i, i∈[k]. In particular, the Costas property forbids the existence of c1,c2∈C, c1≠c2, such that, for some d∈D, d⊗c1, d⊗c2∈D: no four points in C can form a “parallelogram’’ (under ⊗), and no three points in C can be both on a straight line and equidistant.Remark 2.4.
Letf:C1⊂G1→G2 be a function; an equivalent definition of the Costas property with respect to D is then that
(2.3)∀d∈D1*,∀x,y∈C1:d⊗x,d⊗y∈C1,f(x⊗d)-f(x)=f(y⊗d)-f(y)⇒x=y,
where D1={d∈G1∣∃d2∈G2:(d1,d2)∈D}.Remark 2.5.
The usual definition of a Costas bijection usesG=ℤ×ℤ, ⊗=+, D=ℤ*, and C⊂[n]×[n], n∈ℕ, with the additional requirement that C is the graph of a bijection on [n] [1, 2, 6]. Costas arrays are mapped bijectively to Costas permutations using the convention that the ith element of the permutation indicates the position of the dot in the ith column of the array. Henceforth the terms “Costas array’’ and “Costas permutation’’ will be used interchangeably. Figure 1 shows a Costas array of order 27.
Similarly, the definition of a Golomb ruler usesG=ℤ, ⊗=+, D=ℤ*, and C⊂[n+1]-1, n∈ℕ, so that 0,n∈C. The length of this Golomb ruler is defined to be n (this agrees with the usual concept of the term of a physical ruler), while, if |C|=m∈ℕ, the Golomb ruler is said to have m markings.Remark 2.6.
Historically, the Costas property has been construed to include bijectivity: this is because the original engineering application that introduced Costas arrays does not benefit any further from nonbijective Costas sets, namely, Costas arrays with two or more dots on the same row or column, though such Costas arrays can still be used successfully [1, 2]. In this work, bijectivity/injectivity is no longer considered to be a formally required component of the Costas property; in fact, the Costas set may not even be the graph of a function. Respecting tradition, however, we will endeavor to provide examples of injective Costas functions.Remark 2.7.
A direct consequence of the definition is that for alld∈D, d⊗C is also a Costas set with respect to D. In particular, Golomb rulers can be shifted over the integers and still retain the Costas property, and so do Costas arrays if shifted in either direction.We finally specialize the definition of a Costas set on groups that are dense in themselves.Definition 2.8 (Costas clouds).
LetG in Definition 2.1 be dense in itself, and let D=G. Whenever a Costas set C is dense in G, it will be called a Costas cloud.In particular, Costas clouds can exist inℚ, ℝ, ℂ or powers thereof (ℚ2, etc.).


## 2.3. Construction of Costas Permutations

Two algebraic construction methods exist for Costas permutations [3, 4, 6]. Let us review them briefly without proof, as they will be needed later.


### 2.3.1. The Welch Construction

Theorem 2.9 (Welch constructionW1(p,α,c)).
Letp be a prime, let α be a primitive root of the finite field 𝔽(p) of p elements, and let c∈[p-1]-1 be a constant; then, the function f:[p-1]→[p-1] where f(i)=αi-1+cmodp is a bijection with the Costas property.The reason for the presence of-1 in the exponent is that, when c=0, 1 is a fixed point: f(1)=1. We refer to arrays generated with c≠0 as circular shifts of the array generated by c=0 for the same p and α.


### 2.3.2. The Golomb Construction

Theorem 2.10 (Golomb constructionG2(p,m,a,b)).
Letp be a prime, m∈ℕ, and let α, β be primitive roots of the finite field 𝔽(pm) of q=pm elements; then, the function f:[q-2]→[q-2] where αi+βf(i)=1 is a bijection with the Costas property.


## 2.3.1. The Welch Construction

Theorem 2.9 (Welch constructionW1(p,α,c)).
Letp be a prime, let α be a primitive root of the finite field 𝔽(p) of p elements, and let c∈[p-1]-1 be a constant; then, the function f:[p-1]→[p-1] where f(i)=αi-1+cmodp is a bijection with the Costas property.The reason for the presence of-1 in the exponent is that, when c=0, 1 is a fixed point: f(1)=1. We refer to arrays generated with c≠0 as circular shifts of the array generated by c=0 for the same p and α.


## 2.3.2. The Golomb Construction

Theorem 2.10 (Golomb constructionG2(p,m,a,b)).
Letp be a prime, m∈ℕ, and let α, β be primitive roots of the finite field 𝔽(pm) of q=pm elements; then, the function f:[q-2]→[q-2] where αi+βf(i)=1 is a bijection with the Costas property.


## 2.4. Constructions for Golomb Rulers/Sidon Sets

Golomb rulers, though bearing the name of Professor S. Golomb, were originally described by W. C. Babcock in the context of an application in telecommunications [7]. It later emerged that they had made their appearance even earlier in the context of harmonic analysis, in a completely equivalent formulation, known as Sidon sets [8]. In this work, the two terms will be used interchangeably. A very comprehensive source of information about Golomb rulers is [9].Definition2.1, in the context of Remark 2.5, yields the usual definition of Golomb rulers/Sidon sets.Definition 2.11.
LetS⊂[n+1]-1, n∈ℕ, so that 0,n∈S. S is a Sidon set or a Golomb ruler if and only if
(2.4)∀x1,x2,x3,x4∈S:x1+x2=x3+x4⇔x1-x3=x4-x2⇔{x1,x2}={x3,x4}.The sum version corresponds to Sidon sets, the difference version to Golomb rulers: they are obviously equivalent. What is the relation betweenm=|S| and n? In particular, what is the smallest n for a given m? What is the largest m for a given n? Golomb rulers that satisfy either of these conditions are dubbed optimal. It is conjectured [9] that optimal Golomb rulers asymptotically satisfy the condition
(2.5)m≈n.Though they will not be needed further in this work, and for the sake of completeness only, we also present some construction methods for Golomb rulers. Note that, contrary to the case of Costas arrays, where the order specifies the number of dots, the definition of a Golomb ruler does not relate the length to the number of markings in any way. Needless to say, construction methods for Golomb rulers considered to be of interest tend to produce reasonably densely populated Golomb rulers, and, in particular, families that asymptotically satisfy (2.5).


### 2.4.1. Erdös-Turan Construction [10, 11]

Theorem 2.12.
For every primep, the sequence
(2.6)2pk+(k2modp),k∈[p]-1
forms a Golomb ruler.The approximate asymptotic length of such a Golomb ruler withp markings is 2p2; hence it deviates from optimality by a factor of 2.


### 2.4.2. Rusza-Lindström Construction [12, 13]

Theorem 2.13.
Letp be prime, g a primitive root of 𝔽(p), and s relatively prime to p-1. The following sequence
(2.7)(psk+(p-1)gk)modp(p-1),k∈[p-1]-1
forms a Golomb ruler.These rulers are of length (at most)p(p-1) and have p-1 markings; hence they are optimal.


### 2.4.3. Bose-Chowla Construction [14, 15]

Theorem 2.14.
Letq=pn be a power of a prime and g a primitive root in 𝔽(q2). Then the q integers
(2.8)S={i∈[q2-2]:gi-g∈𝔽(q)}
have distinct pairwise differences modulo q2-1.
In addition, the set ofq(q-1) pairwise differences in S, reduced modulo q2-1, equals the set of all nonzero integers less than q2-1 which are not divisible by q+1.These rulers are optimal: they haveq markings and their length is (at most) q2-1.


### 2.4.4. An Always Applicable Construction [9]

The previous constructions work only when the number of markings is a (power ofa) prime. The following construction works always but, unfortunately, is far from optimal.Theorem 2.15.
For anyn∈ℕ*, and for a fixed a∈{1,2}, the sequence
(2.9)ank2+k,k∈[n]-1
forms a Golomb ruler.This ruler hasn markings and its length is asymptotically an3; hence it is far from optimal.


## 2.4.1. Erdös-Turan Construction [10, 11]

Theorem 2.12.
For every primep, the sequence
(2.6)2pk+(k2modp),k∈[p]-1
forms a Golomb ruler.The approximate asymptotic length of such a Golomb ruler withp markings is 2p2; hence it deviates from optimality by a factor of 2.


## 2.4.2. Rusza-Lindström Construction [12, 13]

Theorem 2.13.
Letp be prime, g a primitive root of 𝔽(p), and s relatively prime to p-1. The following sequence
(2.7)(psk+(p-1)gk)modp(p-1),k∈[p-1]-1
forms a Golomb ruler.These rulers are of length (at most)p(p-1) and have p-1 markings; hence they are optimal.


## 2.4.3. Bose-Chowla Construction [14, 15]

Theorem 2.14.
Letq=pn be a power of a prime and g a primitive root in 𝔽(q2). Then the q integers
(2.8)S={i∈[q2-2]:gi-g∈𝔽(q)}
have distinct pairwise differences modulo q2-1.
In addition, the set ofq(q-1) pairwise differences in S, reduced modulo q2-1, equals the set of all nonzero integers less than q2-1 which are not divisible by q+1.These rulers are optimal: they haveq markings and their length is (at most) q2-1.


## 2.4.4. An Always Applicable Construction [9]

The previous constructions work only when the number of markings is a (power ofa) prime. The following construction works always but, unfortunately, is far from optimal.Theorem 2.15.
For anyn∈ℕ*, and for a fixed a∈{1,2}, the sequence
(2.9)ank2+k,k∈[n]-1
forms a Golomb ruler.This ruler hasn markings and its length is asymptotically an3; hence it is far from optimal.


## 3. Explicit Constructions of Nowhere Continuous Costas Functions

The following two examples use the indicator function of a dense subsetS of ℝ as a building block, denoted by 1S; specifically, 1S(x)=1 if ∈S and 1S(x)=0 otherwise.Theorem 3.1.
Letf:ℝ+→ℝ+ so that
(3.1)f(x)=x2(1+a1ℚ(x)),1+a=c2,c∈ℚ+.
Then f is a nowhere continuous Costas bijection on ℝ+ with respect to ℚ+.Proof.
We will denote the set of irrational numbers by𝔸. First, we show that f is injective; we distinguish two cases for the equation f(x)=f(y). (i)
x and y are both in ℚ+ or both in 𝔸+: we get x2=y2⇔x=y.(ii)
x∈ℚ+, y∈𝔸+ (the opposite case is obviously similar): we get (1+a)x2=(cx)2=y2⇔y=cx which is impossible, as this equation implies that y∈ℚ+ as well.Therefore, f is injective.
We now show thatf is surjective; we distinguish two cases for the equation f(x)=y∈ℝ+. (i)
x∈ℚ+: then (cx)2=y⇔x=y/c.(ii)
x∈𝔸+: then x2=y⇔x=y.For every y, then, each of the 2 cases formally yields a solution, but the injectivity of f guarantees that only one will be admissible: specifically, if y is the square of a rational, the solution comes from the first case, otherwise from the second. In particular, we find an x for every y; therefore f is surjective.
Sinceℚ+ is dense in ℝ+, the indicator function 1ℚ is nowhere continuous in ℝ+, and therefore f is nowhere continuous as well.
We finally need to show thatf has the Costas property. We consider the equation
(3.2)f(x+z)-f(x)=f(y+z)-f(y),x,y∈ℝ+,z∈ℚ+*
and observe that x+z is rational if and only if x is rational. We only need to consider then two cases:  (i)
x and y are both in ℚ+ or both in 𝔸+: we get
(3.3)(x+z)2-x2=(y+z)2-y2⇔z(x-y)=0⇔x=y,(ii)
x∈ℚ+, y∈𝔸+ (the opposite case is obviously similar): we get
(3.4)c2[(x+z)2-x2]=(y+z)2-y2⇔y=c2(2xz+z2)-z22z,
implying that y∈ℚ, a contradiction.Overall then, f(x+z)-f(x)=f(y+z)-f(y)⇒x=y and the Costas property is confirmed. This completes the proof.The previous idea can be successfully generalized to yield an expanded family of nowhere continuous functions with the Costas property ifℚ is substituted by ℙ.Theorem 3.2.
Letf:R+*→R+* so that
(3.5)f(x)=xs(1+a1ℙ(x)),s∈ℚ∖{0,1},a∈ℙ.
Then f is a nowhere continuous Costas bijection on ℝ+* with respect to ℙ+*.Proof.
The setℝ∖ℙ=ℙc is known as the set of transcendental numbers. The proof follows closely the previous proof. Throughout the proof it will be important to keep in mind that ℙ is conveniently closed under several operations such as addition, multiplication, inversion, and exponentiation by a rational exponent.
The equationf(x)=f(y) leads to the two possibilities xs=ys and (1+a)xs=ys according to whether both x and y are of the same type (algebraic or not) or of different types (in which case, without loss of generality, we consider x∈ℙ, y∈ℙc): the former leads to x=y (for s≠0) while the latter implies y=x(1+a)1/s, whereby y is algebraic, a contradiction. It follows that f is injective.
The equationf(x)=y leads to the two possibilities xs(1+a)=y or xs=y, according to whether x∈ℙ or not, respectively: the former yields an admissible solution if and only if y is algebraic, and the latter if and only if y is transcendental. Hence, a valid x corresponds to each y and f is surjective.
Sinceℙ+ is dense in ℝ+, the indicator function 1ℙ is nowhere continuous in ℝ+, and therefore f is nowhere continuous as well.
Finally, we need to show thatf satisfies the Costas property. To see this, we form the equation
(3.6)f(x+z)-f(x)=f(y+z)-f(y),x,y∈ℝ+*,z∈ℙ+*
and consider the resulting two cases.  (i)
Ifx and y are both in ℙ+ or both in (ℙc)+, (3.6) becomes
(3.7)(x+z)s-xs=(y+z)s-ys.
According to [5, Theorem  5], since the function g(x)=xs is strictly monotonic with a strictly monotonic derivative in ℝ+, it has the Costas property over this set; hence the only possible solution is x=y.(ii)
Ifx and y are of different types, let (without loss of generality) x∈ℙ+ and y∈(ℙc)+: the equation becomes
(3.8)(1+a)[(x+z)s-xs]=(y+z)s-ys.
For a fixed x, z≠0, and s≠1, this is an algebraic equation in y, implying that y is algebraic, a contradiction.Overall then, f(x+z)-f(x)=f(y+z)-f(y)⇒x=y and the Costas property is confirmed. This completes the proof.Remark 3.3.
ℝ+* was chosen instead of ℝ+ as the domain of f in a preceding theorem because f is not defined at 0 when s<0; ℝ+ could have been used for s>0.Although both constructions above are nowhere continuous, their behavior is not as “wild’’ as one might have hoped for: their graph is entirely included within two smooth curves, given by the equationsy=xs and y=Kxs, K>1, the latter containing countably many points. Is there a function satisfying the Costas property whose graph is everywhere dense on a region of the real plane? This leads to the notion of Costas clouds, studied below.


## 4. Costas Clouds

Our foremost intention here is to prove that bijective Costas clouds exist; to carry out the proof, we will need some background.


### 4.1. Cauchy's Functional Equation

Definition 4.1.
Letf:ℝ→ℝ; it satisfies Cauchy's functional equation if and only if
(4.1)∀x,y∈ℝ,f(x+y)=f(x)+f(y).A detailed study of this equation can be found in [16]. For the sake of completeness, we state and prove below those properties of the solutions we will need.Theorem 4.2.
The solutionf of Cauchy's equation (4.1) satisfies the following properties. (1)
For allq∈ℚ, for all x∈ℝ,f(qx)=qf(x).(2)
f is continuous if and only if ∃c∈ℝ:∀x∈ℝ,f(cx)=cx.(3)
f is continuous everywhere if and only if it is continuous at a point.(4)
f is discontinuous if and only if its graph is everywhere dense on the real plane.Proof.
(i) Settingx=y=0 we get f(0+0)=f(0)=f(0)+f(0)⇔f(0)=0.
(ii) Settingy=-x we get f(x-x)=f(0)=0=f(x)+f(-x)⇔f(-x)=-f(x).
(iii) Settingx=x1, y=x2+⋯+xn for n∈ℕ* we get f(x1+x2+⋯+xn)=f(x1)+f(x2+⋯+xn)=⋯=f(x1)+f(x2)+⋯+f(xn).
(iv) Settingx1=x2=⋯=xn=x we get f(nx)=nf(x). Setting y=nx we get f(y/n)=(1/n)f(y).
Expressing the rationalq as m/n, all of the above shows that, for any x∈ℝ,
(4.2)f(qx)=f(mnx)=sign(m)f(|m|nx)=sign(m)|m|f(1nx)=mnf(x)=qf(x).
Assume now thatf is continuous: for every x∈ℝ there exists a sequence {qn} of rationals such that qn→x. It follows that
(4.3)f(x)=f(limqn)=limf(qn)=limqnf(1)=xf(1)=cx,c=f(1).
Conversely, every function of the form f(x)=cx satisfies Cauchy's equation (4.1) and is continuous.
Assume thatf is continuous at some point x0; then
(4.4)limy→xf(y)=f(y-x+x-x0+x0)=limy→xf(y-x+x0)+f(x-x0)=limu→x0f(u)+f(x-x0)=f(x0)+f(x-x0)=f(x);
hence f is continuous at (an arbitrary) x.
Assume now thatf is not continuous: then, by what we just proved, it must be nowhere continuous and it cannot be linear (though it has to be linear over the rationals). This implies
(4.5)∃x1,x2∈ℝ:f(x1)x1≠f(x2)x2;
whence it follows that the two vectors v1=(x1,f(x1)), v2=(x2,f(x2)) are linearly independent and, consequently, span the entire real plane. The set of vectors, then, of the form {r1v1+r2v2:r1,r2∈ℚ} are an everywhere dense subset of the real plane, but
(4.6)r1v1+r2v2=r1(x1,f(x1))+r2(x2,f(x2))=(r1x1+r2x2,f(r1x1+r2x2)),
which means that the subset {f(x):x=r1x1+r2x2,r1,r2∈ℚ} of the graph of f is everywhere dense on the plane; whence the graph of f itself is everywhere dense on the plane. Conversely, if the graph of f is everywhere dense on the real plane, f cannot possibly be continuous, or else it would be linear and thus would not possess an everywhere dense graph. This completes the proof.Remark 4.3.
Cauchy's functional equation, despite its simplicity, has been playing a prominent role in analysis: Hilbert's 5th problem essentially proposes a generalization of this equation, while an important area of study is the Hyers-Rassias-Ulam stability of this equation (or slight variants thereof) [17–19].


### 4.2. Bijective/Injective Solutions of Cauchy's Functional Equation

Theorem 4.4.
There exist solutions of Cauchy's equation that are nowhere continuous bijections/injections, everywhere dense on the real plane.Proof.
Considerℝ as a vector space over ℚ. This vector space must necessarily have an uncountable basis, or else ℝ itself would be countable: it follows by the Continuum Hypothesis that this basis can be indexed by the real numbers and, therefore, that we can describe the basis as B={ba:a∈ℝ}. By definition, any real number x admits a (finite) linear expansion x=q1ba1+⋯+qnban over this basis (where the rational q, the indices ai, i∈[n], and n are obviously functions of x). Furthermore, a solution f of Cauchy's equation (4.1) can be considered as a linear map over this vector space, and we can write
(4.7)f(x)=f(q1ba1+⋯+qnban)=q1f(ba1)+⋯+qnf(ban),
which expresses the well-known result that a linear map over a vector space is unambiguously defined by its effect on the vector space basis B. Assuming now that ∃c∈ℝ:∀a∈ℝ, f(ba)=cba, we get f(x)=cx for all x, namely, that f is linear. By Theorem 4.2, though, this will be the only case resulting to a linear f: in all other cases f will be nowhere continuous and its graph everywhere dense. Choosing a bijection/injection g over ℝ (other than the identity) such that for all a∈ℝ, f(ba)=bg(a) results to an f that is bijective/injective as well. This completes the proof.Remark 4.5.
The theorem does not rely on the exact nature ofℚ: it only requires a field over which ℝ has an uncountable basis. In particular, any countable field extension of ℚ would have been equally suitable, such as ℙ.


### 4.3. The Existence of Bijective Costas Clouds onℝ×ℝ+*—The Welch and Golomb Methods

Theorem 4.6.
Bijective Costas clouds onℝ×ℝ+* exist.Proof.
Consider a nowhere continuous bijectionf on ℝ whose graph is everywhere dense on ℝ2, and that further satisfies Cauchy's equation (4.1). Construct g:ℝ→ℝ+* such that g(x)=exp(f(x)); g inherits the properties f has and is then itself a nowhere continuous bijection (as the exponential function is strictly monotonic), whose graph is everywhere dense in ℝ×ℝ+*. Furthermore, it satisfies the Costas property from ℝ to ℝ+* with respect to ℝ+*:
(4.8)g(x+z)-g(x)=g(y+z)-g(y)⇔exp(f(x+z))-exp(f(x))=exp(f(y+z))-exp(f(y))⇔(exp(f(z))-1)(exp(f(x))-exp(f(y)))=0⇔exp(f(z))=1orexp(f(x))=exp(f(y))⇔f(z)=0orf(x)=f(y)⇔z=0(rejected)orx=y.
This completes the proof.Corollary 4.7.
Costas clouds on(ℝ+*)2 exist.It has been suggested that the success of the Welch method (Theorem2.9) in the construction of Costas permutations lies in the interplay between an additive and a multiplicative structure [20]: indeed, the exponent is an additive function, while the exponentiation turns this additive structure into a multiplicative one. But, according to the proof of Theorem 4.6, g(x)=exp(f(x)), where f:ℝ→ℝ satisfies Cauchy's functional equation (4.1) and is additive: this function, therefore, exhibits the same interplay between the additive and the multiplicative structure and can accordingly be considered a generalization of the Welch construction. Theorem 4.6, then, viewed from the point of view of the method it follows instead of the result it achieves, reads as follows.Theorem 4.8 (Generalized Welch construction in the continuum).
Letf:ℝ→ℝ be a nowhere continuous injection that satisfies (4.1), and let g:ℝ→ℝ+* be such that g(x)=exp(f(x)). Then g is a Costas cloud: if f has an everywhere dense graph in ℝ2, so does g in ℝ×ℝ+*; if f is bijective, so is g.Since the Welch method can be successfully generalized on the real line, can the same be done for the Golomb method (Theorem2.10)?Theorem 4.9 (Generalized Golomb construction in the continuum).
Letf:ℝ→ℝ be a nowhere continuous injection that satisfies (4.1), and let g:ℝ→ℝ+* be such that exp(g(x))-exp(f(x))=1. Then g is a Costas cloud: if f has an everywhere dense graph in ℝ2, so does g in ℝ×ℝ+*; if f is bijective, so is g.Proof.
g is clearly bijective if and only if f is, and it inherits the property of the everywhere dense graph as long as f has it; we just need to show the Costas property:
(4.9)g(x+z)-g(x)=g(y+z)-g(y)⇔ln(1+exp(f(x+z)))-ln(1+exp(f(x)))=ln(1+exp(f(y+z)))-ln(1+exp(f(y)))⇔1+exp(f(x)+f(z))1+exp(f(x))=1+exp(f(y)+f(z))1+exp(f(y))⇔exp(f(x))exp(f(z))+exp(f(y))=exp(f(y))exp(f(z))+exp(f(x))⇔(1-exp(f(z)))(exp(f(x))-exp(f(x)))=0⇔f(z)=0orf(x)=f(y)⇔z=0(rejected)orx=y.
Note finally that x=0⇔f(x)=0⇔exp(g(0))=0, which is impossible, so g cannot be defined on x=0. This completes the proof.


### 4.4. The Existence of Bijective Costas Clouds onℝ×(0,1)

Based on Theorem4.6, we can apply a simple transformation and obtain a Costas cloud on ℝ×(0,1).Theorem 4.10.
Bijective Costas clouds onℝ×(0,1) exist.Proof.
Consider the functiong of (the proof of) Theorem 4.6, note that g(x+y)=g(x)g(y), and consider h:ℝ→(0,1) such that h(x)=exp(-g(x)). It clearly follows that h is bijective, nowhere continuous, and that it has an everywhere dense graph, as g has these properties. We need to verify the Costas property:
(4.10)exp(-g(x+z))-exp(-g(x))=exp(-g(y+z))-exp(-g(y))⇔exp(-g(x)g(z))-exp(-g(x))=exp(-g(y)g(z))-exp(-g(y))⇔ua-u=va-v,
where u=exp(-g(x)), v=exp(-g(y)), a=-g(z), u,v∈(0,1), a∈(-∞,0). But (ua-u)′=aua-1-1<0 since a<0, whence the function is monotonic, and therefor,
(4.11)ua-u=va-v⇔u=v⇔g(x)=g(y)⇔x=y.
This completes the proof.Corollary 4.11.
Costas clouds on(0,1)2 exist.But we can also apply another simple transformation, again based on Theorem4.6, to obtain this result.Alternative proof of Corollary4.11.
Consider the functiong of (the proof of) Theorem 4.6, and consider h:(0,1)→(0,1) such that h=g/(1+g). Clearly h is injective, nowhere continuous on (0,1), and has a graph everywhere dense in (0,1)2, because g has all these properties. We only need to make sure it has the Costas property:
(4.12)g(x+d)1+g(x+d)-g(x)1+g(x)=g(y+d)1+g(y+d)-g(y)1+g(y)⇔g(x)g(d)1+g(x)g(d)-g(x)1+g(x)=g(y)g(d)1+g(y)g(d)-g(y)1+g(y)⇔g(x)(g(d)-1)(1+g(x)g(d))(1+g(x))=g(y)(g(d)-1)(1+g(y)g(d))(1+g(y))⇔g(x)(1+g(y)g(d))(1+g(y))=g(y)(1+g(x)g(d))(1+g(x))⇔(g(x)-g(y))(1-g(x)g(y)g(d))=0=(g(x)-g(y))(1-g(x+y+d))⇔x=yorx+y+d=0.
The second alternative is impossible as x,y,z>0, so we necessarily obtain x=y, and the Costas property is verified. This completes the proof.


### 4.5. Rational Costas Clouds

An algorithm to construct Costas bijections on the setQ=[0,1]∩ℚ has already been proposed in [5], but the density of its graph in [0,1]2 was not considered or studied at the time. We propose here a different algorithm that produces a rational Costas cloud. Referring to Definition 2.8, note that it is of no interest to consider the density of the graph of a function on A×A whenever A⊂ℚ: we correct then this part of the definition to read that the graph has to be dense on I(A)×I(A), where I(A) denotes the smallest (closed) interval in ℝ containing A.The construction proposed in Theorem4.6 does not produce a rational Costas cloud, as not only does the function fail to be a bijection on the rationals but also the images of all rationals lie on a curve. We need then a new mechanism, such as the following.Theorem 4.12.
EnumerateQ so that Q={rn:n∈ℕ}, and consider two copies of it, Qx1 and Qy1 (it is also allowed to use different enumeration schemes in the two sets). Consider the following inductive construction on S=Q2.  Stage 1:
Draw the horizontal line through(0,2-1) and the vertical line through (2-1,0), thus dividing S into 4 smaller squares; choose one point with rational coordinates in each so that the Costas property holds, and so that the points (r0,u) and (v,r0) are chosen. Let the points be (x1i,y1i), i∈[4], and set Qx2=Qx1-{x1i:i∈[4]}, Qy2=Qy1-{y1i:i∈[4]}.Stagen:
Draw the horizontal lines through(0,k2-n), k=1,…,2n-1 and the vertical lines through (k2-n,0), k=1,…,2n-1, thus dividing S into 4n smaller squares. Choose one point (xni,yni)xni∈Qxn,yni∈Qyn in each square (i∈[4n]), so that, for all points together chosen in stages 1 through n inclusive, the Costas property holds, and so that, if Nx(n) and Ny(n) are the smallest natural numbers so that rNx(n)∈Qxn and rNy(n)∈Qyn, respectively, one of the chosen points has rNx(n) as its first coordinate and one rNy(n) as its second. Set Qxn+1=Qxn-{xni:i∈[4n]}, Qyn+1=Qyn-{yni:i∈[4n]}.The set of points so constructed corresponds to the graph of a bijective rational Costas cloud on Q2.Proof.
The construction is possible because, for every stage and every square, we are called to choose a rational point in this square so that finitely many constraints are satisfied: this is always possible as there are infinitely many rational points in a square. The resulting function clearly satisfies the Costas property, it is injective between its domain and its range, and its graph is everywhere dense inS. Further, every rational number in the domain and the range is used exactly once. This completes the proof.Remark 4.13.
The construction above can be modified to yield bijective rational Costas clouds on the entireℚ2: just apply stage n to the square Sn={(x,y)∈ℝ2:max(|x|,|y|)<2n}. In other words, as stages progress, the grid not only becomes more and more refined but also expands.Remark 4.14.
The square grid described in the theorem has the property that the squares in a given stage are all of the same size, and that any two squares either share a common boundary or else one contains the other. Neither of these properties is necessary, strictly speaking: for example, we could have used a grid of the formk17-n, or even kπ-n.Remark 4.15.
The proof does not depend on the exact nature ofℚ, except for the facts that it is countably infinite and everywhere dense in ℝ: any other set with these properties would have sufficed, such as ℙ.


## 4.1. Cauchy's Functional Equation

Definition 4.1.
Letf:ℝ→ℝ; it satisfies Cauchy's functional equation if and only if
(4.1)∀x,y∈ℝ,f(x+y)=f(x)+f(y).A detailed study of this equation can be found in [16]. For the sake of completeness, we state and prove below those properties of the solutions we will need.Theorem 4.2.
The solutionf of Cauchy's equation (4.1) satisfies the following properties. (1)
For allq∈ℚ, for all x∈ℝ,f(qx)=qf(x).(2)
f is continuous if and only if ∃c∈ℝ:∀x∈ℝ,f(cx)=cx.(3)
f is continuous everywhere if and only if it is continuous at a point.(4)
f is discontinuous if and only if its graph is everywhere dense on the real plane.Proof.
(i) Settingx=y=0 we get f(0+0)=f(0)=f(0)+f(0)⇔f(0)=0.
(ii) Settingy=-x we get f(x-x)=f(0)=0=f(x)+f(-x)⇔f(-x)=-f(x).
(iii) Settingx=x1, y=x2+⋯+xn for n∈ℕ* we get f(x1+x2+⋯+xn)=f(x1)+f(x2+⋯+xn)=⋯=f(x1)+f(x2)+⋯+f(xn).
(iv) Settingx1=x2=⋯=xn=x we get f(nx)=nf(x). Setting y=nx we get f(y/n)=(1/n)f(y).
Expressing the rationalq as m/n, all of the above shows that, for any x∈ℝ,
(4.2)f(qx)=f(mnx)=sign(m)f(|m|nx)=sign(m)|m|f(1nx)=mnf(x)=qf(x).
Assume now thatf is continuous: for every x∈ℝ there exists a sequence {qn} of rationals such that qn→x. It follows that
(4.3)f(x)=f(limqn)=limf(qn)=limqnf(1)=xf(1)=cx,c=f(1).
Conversely, every function of the form f(x)=cx satisfies Cauchy's equation (4.1) and is continuous.
Assume thatf is continuous at some point x0; then
(4.4)limy→xf(y)=f(y-x+x-x0+x0)=limy→xf(y-x+x0)+f(x-x0)=limu→x0f(u)+f(x-x0)=f(x0)+f(x-x0)=f(x);
hence f is continuous at (an arbitrary) x.
Assume now thatf is not continuous: then, by what we just proved, it must be nowhere continuous and it cannot be linear (though it has to be linear over the rationals). This implies
(4.5)∃x1,x2∈ℝ:f(x1)x1≠f(x2)x2;
whence it follows that the two vectors v1=(x1,f(x1)), v2=(x2,f(x2)) are linearly independent and, consequently, span the entire real plane. The set of vectors, then, of the form {r1v1+r2v2:r1,r2∈ℚ} are an everywhere dense subset of the real plane, but
(4.6)r1v1+r2v2=r1(x1,f(x1))+r2(x2,f(x2))=(r1x1+r2x2,f(r1x1+r2x2)),
which means that the subset {f(x):x=r1x1+r2x2,r1,r2∈ℚ} of the graph of f is everywhere dense on the plane; whence the graph of f itself is everywhere dense on the plane. Conversely, if the graph of f is everywhere dense on the real plane, f cannot possibly be continuous, or else it would be linear and thus would not possess an everywhere dense graph. This completes the proof.Remark 4.3.
Cauchy's functional equation, despite its simplicity, has been playing a prominent role in analysis: Hilbert's 5th problem essentially proposes a generalization of this equation, while an important area of study is the Hyers-Rassias-Ulam stability of this equation (or slight variants thereof) [17–19].


## 4.2. Bijective/Injective Solutions of Cauchy's Functional Equation

Theorem 4.4.
There exist solutions of Cauchy's equation that are nowhere continuous bijections/injections, everywhere dense on the real plane.Proof.
Considerℝ as a vector space over ℚ. This vector space must necessarily have an uncountable basis, or else ℝ itself would be countable: it follows by the Continuum Hypothesis that this basis can be indexed by the real numbers and, therefore, that we can describe the basis as B={ba:a∈ℝ}. By definition, any real number x admits a (finite) linear expansion x=q1ba1+⋯+qnban over this basis (where the rational q, the indices ai, i∈[n], and n are obviously functions of x). Furthermore, a solution f of Cauchy's equation (4.1) can be considered as a linear map over this vector space, and we can write
(4.7)f(x)=f(q1ba1+⋯+qnban)=q1f(ba1)+⋯+qnf(ban),
which expresses the well-known result that a linear map over a vector space is unambiguously defined by its effect on the vector space basis B. Assuming now that ∃c∈ℝ:∀a∈ℝ, f(ba)=cba, we get f(x)=cx for all x, namely, that f is linear. By Theorem 4.2, though, this will be the only case resulting to a linear f: in all other cases f will be nowhere continuous and its graph everywhere dense. Choosing a bijection/injection g over ℝ (other than the identity) such that for all a∈ℝ, f(ba)=bg(a) results to an f that is bijective/injective as well. This completes the proof.Remark 4.5.
The theorem does not rely on the exact nature ofℚ: it only requires a field over which ℝ has an uncountable basis. In particular, any countable field extension of ℚ would have been equally suitable, such as ℙ.


## 4.3. The Existence of Bijective Costas Clouds onℝ×ℝ+*—The Welch and Golomb Methods

Theorem 4.6.
Bijective Costas clouds onℝ×ℝ+* exist.Proof.
Consider a nowhere continuous bijectionf on ℝ whose graph is everywhere dense on ℝ2, and that further satisfies Cauchy's equation (4.1). Construct g:ℝ→ℝ+* such that g(x)=exp(f(x)); g inherits the properties f has and is then itself a nowhere continuous bijection (as the exponential function is strictly monotonic), whose graph is everywhere dense in ℝ×ℝ+*. Furthermore, it satisfies the Costas property from ℝ to ℝ+* with respect to ℝ+*:
(4.8)g(x+z)-g(x)=g(y+z)-g(y)⇔exp(f(x+z))-exp(f(x))=exp(f(y+z))-exp(f(y))⇔(exp(f(z))-1)(exp(f(x))-exp(f(y)))=0⇔exp(f(z))=1orexp(f(x))=exp(f(y))⇔f(z)=0orf(x)=f(y)⇔z=0(rejected)orx=y.
This completes the proof.Corollary 4.7.
Costas clouds on(ℝ+*)2 exist.It has been suggested that the success of the Welch method (Theorem2.9) in the construction of Costas permutations lies in the interplay between an additive and a multiplicative structure [20]: indeed, the exponent is an additive function, while the exponentiation turns this additive structure into a multiplicative one. But, according to the proof of Theorem 4.6, g(x)=exp(f(x)), where f:ℝ→ℝ satisfies Cauchy's functional equation (4.1) and is additive: this function, therefore, exhibits the same interplay between the additive and the multiplicative structure and can accordingly be considered a generalization of the Welch construction. Theorem 4.6, then, viewed from the point of view of the method it follows instead of the result it achieves, reads as follows.Theorem 4.8 (Generalized Welch construction in the continuum).
Letf:ℝ→ℝ be a nowhere continuous injection that satisfies (4.1), and let g:ℝ→ℝ+* be such that g(x)=exp(f(x)). Then g is a Costas cloud: if f has an everywhere dense graph in ℝ2, so does g in ℝ×ℝ+*; if f is bijective, so is g.Since the Welch method can be successfully generalized on the real line, can the same be done for the Golomb method (Theorem2.10)?Theorem 4.9 (Generalized Golomb construction in the continuum).
Letf:ℝ→ℝ be a nowhere continuous injection that satisfies (4.1), and let g:ℝ→ℝ+* be such that exp(g(x))-exp(f(x))=1. Then g is a Costas cloud: if f has an everywhere dense graph in ℝ2, so does g in ℝ×ℝ+*; if f is bijective, so is g.Proof.
g is clearly bijective if and only if f is, and it inherits the property of the everywhere dense graph as long as f has it; we just need to show the Costas property:
(4.9)g(x+z)-g(x)=g(y+z)-g(y)⇔ln(1+exp(f(x+z)))-ln(1+exp(f(x)))=ln(1+exp(f(y+z)))-ln(1+exp(f(y)))⇔1+exp(f(x)+f(z))1+exp(f(x))=1+exp(f(y)+f(z))1+exp(f(y))⇔exp(f(x))exp(f(z))+exp(f(y))=exp(f(y))exp(f(z))+exp(f(x))⇔(1-exp(f(z)))(exp(f(x))-exp(f(x)))=0⇔f(z)=0orf(x)=f(y)⇔z=0(rejected)orx=y.
Note finally that x=0⇔f(x)=0⇔exp(g(0))=0, which is impossible, so g cannot be defined on x=0. This completes the proof.


## 4.4. The Existence of Bijective Costas Clouds onℝ×(0,1)

Based on Theorem4.6, we can apply a simple transformation and obtain a Costas cloud on ℝ×(0,1).Theorem 4.10.
Bijective Costas clouds onℝ×(0,1) exist.Proof.
Consider the functiong of (the proof of) Theorem 4.6, note that g(x+y)=g(x)g(y), and consider h:ℝ→(0,1) such that h(x)=exp(-g(x)). It clearly follows that h is bijective, nowhere continuous, and that it has an everywhere dense graph, as g has these properties. We need to verify the Costas property:
(4.10)exp(-g(x+z))-exp(-g(x))=exp(-g(y+z))-exp(-g(y))⇔exp(-g(x)g(z))-exp(-g(x))=exp(-g(y)g(z))-exp(-g(y))⇔ua-u=va-v,
where u=exp(-g(x)), v=exp(-g(y)), a=-g(z), u,v∈(0,1), a∈(-∞,0). But (ua-u)′=aua-1-1<0 since a<0, whence the function is monotonic, and therefor,
(4.11)ua-u=va-v⇔u=v⇔g(x)=g(y)⇔x=y.
This completes the proof.Corollary 4.11.
Costas clouds on(0,1)2 exist.But we can also apply another simple transformation, again based on Theorem4.6, to obtain this result.Alternative proof of Corollary4.11.
Consider the functiong of (the proof of) Theorem 4.6, and consider h:(0,1)→(0,1) such that h=g/(1+g). Clearly h is injective, nowhere continuous on (0,1), and has a graph everywhere dense in (0,1)2, because g has all these properties. We only need to make sure it has the Costas property:
(4.12)g(x+d)1+g(x+d)-g(x)1+g(x)=g(y+d)1+g(y+d)-g(y)1+g(y)⇔g(x)g(d)1+g(x)g(d)-g(x)1+g(x)=g(y)g(d)1+g(y)g(d)-g(y)1+g(y)⇔g(x)(g(d)-1)(1+g(x)g(d))(1+g(x))=g(y)(g(d)-1)(1+g(y)g(d))(1+g(y))⇔g(x)(1+g(y)g(d))(1+g(y))=g(y)(1+g(x)g(d))(1+g(x))⇔(g(x)-g(y))(1-g(x)g(y)g(d))=0=(g(x)-g(y))(1-g(x+y+d))⇔x=yorx+y+d=0.
The second alternative is impossible as x,y,z>0, so we necessarily obtain x=y, and the Costas property is verified. This completes the proof.


## 4.5. Rational Costas Clouds

An algorithm to construct Costas bijections on the setQ=[0,1]∩ℚ has already been proposed in [5], but the density of its graph in [0,1]2 was not considered or studied at the time. We propose here a different algorithm that produces a rational Costas cloud. Referring to Definition 2.8, note that it is of no interest to consider the density of the graph of a function on A×A whenever A⊂ℚ: we correct then this part of the definition to read that the graph has to be dense on I(A)×I(A), where I(A) denotes the smallest (closed) interval in ℝ containing A.The construction proposed in Theorem4.6 does not produce a rational Costas cloud, as not only does the function fail to be a bijection on the rationals but also the images of all rationals lie on a curve. We need then a new mechanism, such as the following.Theorem 4.12.
EnumerateQ so that Q={rn:n∈ℕ}, and consider two copies of it, Qx1 and Qy1 (it is also allowed to use different enumeration schemes in the two sets). Consider the following inductive construction on S=Q2.  Stage 1:
Draw the horizontal line through(0,2-1) and the vertical line through (2-1,0), thus dividing S into 4 smaller squares; choose one point with rational coordinates in each so that the Costas property holds, and so that the points (r0,u) and (v,r0) are chosen. Let the points be (x1i,y1i), i∈[4], and set Qx2=Qx1-{x1i:i∈[4]}, Qy2=Qy1-{y1i:i∈[4]}.Stagen:
Draw the horizontal lines through(0,k2-n), k=1,…,2n-1 and the vertical lines through (k2-n,0), k=1,…,2n-1, thus dividing S into 4n smaller squares. Choose one point (xni,yni)xni∈Qxn,yni∈Qyn in each square (i∈[4n]), so that, for all points together chosen in stages 1 through n inclusive, the Costas property holds, and so that, if Nx(n) and Ny(n) are the smallest natural numbers so that rNx(n)∈Qxn and rNy(n)∈Qyn, respectively, one of the chosen points has rNx(n) as its first coordinate and one rNy(n) as its second. Set Qxn+1=Qxn-{xni:i∈[4n]}, Qyn+1=Qyn-{yni:i∈[4n]}.The set of points so constructed corresponds to the graph of a bijective rational Costas cloud on Q2.Proof.
The construction is possible because, for every stage and every square, we are called to choose a rational point in this square so that finitely many constraints are satisfied: this is always possible as there are infinitely many rational points in a square. The resulting function clearly satisfies the Costas property, it is injective between its domain and its range, and its graph is everywhere dense inS. Further, every rational number in the domain and the range is used exactly once. This completes the proof.Remark 4.13.
The construction above can be modified to yield bijective rational Costas clouds on the entireℚ2: just apply stage n to the square Sn={(x,y)∈ℝ2:max(|x|,|y|)<2n}. In other words, as stages progress, the grid not only becomes more and more refined but also expands.Remark 4.14.
The square grid described in the theorem has the property that the squares in a given stage are all of the same size, and that any two squares either share a common boundary or else one contains the other. Neither of these properties is necessary, strictly speaking: for example, we could have used a grid of the formk17-n, or even kπ-n.Remark 4.15.
The proof does not depend on the exact nature ofℚ, except for the facts that it is countably infinite and everywhere dense in ℝ: any other set with these properties would have sufficed, such as ℙ.


## 5. Countably and Uncountably Infinite Dense Golomb Rulers

Infinite Golomb rulers have been studied in the past [21]: the main point of interest in these studies has been the behavior of the density m(n)/n, m(n) being the number of markings within the set [n+1]-1. It should be mentioned here that, even though references to “dense infinite Sidon sequences’’ can be found in literature (e.g., [22]), giving the impression, at first sight, that the results below may not be novel after all, in fact the term “dense’’ is used not in the analytic sense but in conjunction with the behavior of m(n)/n. Such references are, then, totally unrelated to the task we are about to embark on.


### 5.1. The Existence of Countably Infinite Dense Golomb Rulers

Theorem 5.1.
LetI be a subinterval of ℝ (possibly infinite, possibly ℝ itself): countably infinite Golomb rulers in I exist and may be suitably chosen to be dense in I.Proof.
The idea of the proof is essentially the same as in Theorem4.12 and relies upon the enumerability of ℚ. Enumerate Q=ℚ∩I so that Q={rn:n∈ℕ}, and then set S0={r0}. Assume now that Sm, containing m rationals, has been created, and that rn is being currently considered: if Sm∪{rn} is a Golomb ruler, set Sm+1=Sm∪{rn}; proceed to consider rn+1. For each m we are bound to construct Sm+1 out of Sm, as there are infinitely many rationals to choose from, and only finitely many constraints due to the Golomb ruler property. S=limSm is a countably infinite Golomb ruler.
To ensure that the ruler is dense inI, let IN,k be the kth subinterval of length 2-N (say counting from left to right) of I∩[-2N,2N], and then order all IN,k consecutively, first by N and then by k: I1,1,I1,2,I1,3,I1,4,I2,1,…,I2,16,…, thus obtaining a sequence of intervals In. Now apply the construction proposed above with the extra requirement that, for every m, the element x that turns Sm into Sm+1 must belong in Im+1: this is always possible, as Im+1 itself contains infinitely many rationals. This completes the proof.Remark 5.2.
Any countably infinite set, such asℙ, could have been used in the proof above, instead of ℚ; the proof clearly does not rely on the exact nature of the set used.


### 5.2. The Existence of Uncountably Infinite Dense Golomb Rulers

Theorem 5.3.
LetI be a subinterval of ℝ (possibly infinite, possibly R itself): uncountably infinite Golomb rulers in I exist and may be suitably chosen to be dense in I.Proof.
Considerℝ as a vector space over ℚ, and let B={ba:a∈ℝ} be an (uncountable) basis of this vector space (see the proof of Theorem 4.4). Consider the family of subspaces Vx=span{bu:u≤x}, and observe that Vx⊂Vy if and only if x≤y. Choose a unique point sx∈Vx such that sx∈I and that sx∉Vy, y<x (in other words, choose sx=qxbx for some qx∈ℚ), and form the set S={sx:x∈ℝ}. This is an uncountable subset of I, and we show that it is indeed a Golomb ruler. Consider the equation
(5.1)sx1+sx2=sx3+sx4,x1<x2,x3<x4⇔sx2=sx3+sx4-sx1;
whence sx2∈Vx2∩Vmax(x1,x3,x4). Since, by assumption, x3<x4, it follows that max(x1,x3,x4)=max(x1,x4). If x1>x4, we obtain sx2∈Vx1 which is impossible; therefore x1<x4, implying that x2=x4, and, consequently, that x3=x1.
Note that, for anyx∈ℝ, any qsx∈I with q∈ℚ can be chosen instead of sx. This allows us to choose S dense in I. This completes the proof.Remark 5.4.
ℙ could have been used instead of ℚ (see Remark 4.5).


## 5.1. The Existence of Countably Infinite Dense Golomb Rulers

Theorem 5.1.
LetI be a subinterval of ℝ (possibly infinite, possibly ℝ itself): countably infinite Golomb rulers in I exist and may be suitably chosen to be dense in I.Proof.
The idea of the proof is essentially the same as in Theorem4.12 and relies upon the enumerability of ℚ. Enumerate Q=ℚ∩I so that Q={rn:n∈ℕ}, and then set S0={r0}. Assume now that Sm, containing m rationals, has been created, and that rn is being currently considered: if Sm∪{rn} is a Golomb ruler, set Sm+1=Sm∪{rn}; proceed to consider rn+1. For each m we are bound to construct Sm+1 out of Sm, as there are infinitely many rationals to choose from, and only finitely many constraints due to the Golomb ruler property. S=limSm is a countably infinite Golomb ruler.
To ensure that the ruler is dense inI, let IN,k be the kth subinterval of length 2-N (say counting from left to right) of I∩[-2N,2N], and then order all IN,k consecutively, first by N and then by k: I1,1,I1,2,I1,3,I1,4,I2,1,…,I2,16,…, thus obtaining a sequence of intervals In. Now apply the construction proposed above with the extra requirement that, for every m, the element x that turns Sm into Sm+1 must belong in Im+1: this is always possible, as Im+1 itself contains infinitely many rationals. This completes the proof.Remark 5.2.
Any countably infinite set, such asℙ, could have been used in the proof above, instead of ℚ; the proof clearly does not rely on the exact nature of the set used.


## 5.2. The Existence of Uncountably Infinite Dense Golomb Rulers

Theorem 5.3.
LetI be a subinterval of ℝ (possibly infinite, possibly R itself): uncountably infinite Golomb rulers in I exist and may be suitably chosen to be dense in I.Proof.
Considerℝ as a vector space over ℚ, and let B={ba:a∈ℝ} be an (uncountable) basis of this vector space (see the proof of Theorem 4.4). Consider the family of subspaces Vx=span{bu:u≤x}, and observe that Vx⊂Vy if and only if x≤y. Choose a unique point sx∈Vx such that sx∈I and that sx∉Vy, y<x (in other words, choose sx=qxbx for some qx∈ℚ), and form the set S={sx:x∈ℝ}. This is an uncountable subset of I, and we show that it is indeed a Golomb ruler. Consider the equation
(5.1)sx1+sx2=sx3+sx4,x1<x2,x3<x4⇔sx2=sx3+sx4-sx1;
whence sx2∈Vx2∩Vmax(x1,x3,x4). Since, by assumption, x3<x4, it follows that max(x1,x3,x4)=max(x1,x4). If x1>x4, we obtain sx2∈Vx1 which is impossible; therefore x1<x4, implying that x2=x4, and, consequently, that x3=x1.
Note that, for anyx∈ℝ, any qsx∈I with q∈ℚ can be chosen instead of sx. This allows us to choose S dense in I. This completes the proof.Remark 5.4.
ℙ could have been used instead of ℚ (see Remark 4.5).


## 6. Extensions on the Complex Plane

Having investigated the Costas property onℚ and ℝ, we turn our attention to the field of complex numbers ℂ. To ensure the success of the extension of the various constructions proposed above, we need to revisit each step and identify the necessary modifications, if any. We find then the following.(i)
Cauchy's functional equation (4.1) needs to be reworked to yield a bijection/injection with the required properties in ℂ.(ii)
The proofs of the extended Welch (Theorem4.6) and Golomb (Theorem 4.9) constructions are (formally) still valid, once the right domain and range for the functions is specified and the multivalued nature of the exponential function in ℂ is taken into account.


### 6.1. Cauchy's Functional Equation onℂ

We need to study the properties of a functionf:ℂ→ℂ such that
(6.1)∀u,v∈ℂ:f(u+v)=f(u)+f(v).Applying the real argument twice (on the real and the imaginary numbers), we obtain(6.2)∀x,y∈ℚ,z∈ℂ:f((x+iy)z)=xf(z)+yf(iz).
Assuming that
(6.3)∃a,b∈ℝ,|a|+|b|>0:af(i)+bf(1)=0,f(ℚ+iℚ) lies on a straight line of ℂ; otherwise it is dense in ℂ. A verbatim repetition of the proof of the real case shows that f is continuous on ℂ if and only if it is continuous at a point: in this case, it follows that
(6.4)∀x,y∈ℝ,f(x+iy)=xf(1)+yf(i).We now need to ensure thatf is an injection/bijection, and that the graph of f, namely, {(z,f(z)):z∈ℂ}, is dense in ℂ2. The corresponding proof in the real case relied heavily on the linearity of f over rational multipliers, namely, on the condition that for all q∈ℚ, for all x∈ℝ,f(qx)=qf(x) (see Theorem 4.2), but this time the condition stated in (6.2) is not a linearity condition. We can still restrict our attention to linear solutions of (6.1) by imposing the compatibility condition:
(6.5)∀x∈ℝ,f(ix)=if(x);
this condition is equivalent to
(6.6)∀z∈ℂ,f(iz)=if(z),
because, letting z=x+iy, x,y∈ℝ, we get
(6.7)f(iz)=f(ix-y)=if(x)-f(y)=i(f(x)+if(y))=if(x+iy)=if(z).
Applying this condition to (6.2), we obtain
(6.8)∀x,y∈ℚ,z∈ℂ:f((x+iy)z)=(x+iy)f(z),
while we find directly that
(6.9)∀x,y∈ℝ,f(x+iy)=f(x)+if(y).
In other words, every solution of (4.1) can be extended to a solution of (6.1) that obeys the linearity property (6.8) over the complex rationals ℚ+iℚ; such functions have the property that f(ℝ)⊂ℝ, which is equivalent to f(iℝ)⊂iℝ. As (6.3) and (6.5) are not compatible, f(ℚ+iℚ) is dense in ℂ.Assumingf is continuous, (6.4) shows that for all z∈ℂ, f(z)=zf(1); assuming that the function is nowhere continuous, hence nonlinear, there exist z,w∈ℂ such that the vectors (z,f(z)) and (w,f(w)) are linearly independent. It follows that the set
(6.10){p(z,f(z))+q(w,f(w)):p,q∈ℚ+iℚ}={(pz+qw,f(pz+qw)):p,q∈ℚ+iℚ},
namely a subset of the graph of f, is countably infinite and dense in ℂ2.It remains to be seen that such a nonlinear function can be constructed. To achieve this, we proceed as in the proof of Theorem4.4: we consider ℂ2 as a vector space over the field of complex rationals ℚ+iℚ with an uncountable basis B={ba:a∈ℝ}. If f:B→B is a permutation other than the identity, f:ℂ→ℂ is a nowhere continuous bijection on ℂ whose graph is dense in ℂ2; if f:B→B is injective, f:ℂ→ℂ is a nowhere continuous injection on ℂ whose graph is dense in ℂ2.


### 6.2. The Golomb and Welch Constructions onℂ

The extensions of both the Golomb and the Welch construction inℝ, as seen in Section 4.3, involved the exponential function, which is multivalued over ℂ. For this reason, any further extension over ℂ will necessitate an appropriate restriction of the domain, or, equivalently, the redefinition of Costas property over equivalence classes of points, in order to restore injectivity and surjectivity. Both extensions, as stated below, follow this principle, setting their domain and/or range, as appropriate, to be sets of distinct representatives of such equivalence classes.Theorem 6.1 (Generalized Welch construction in the complex continuum).
Letf:ℂ→ℂ be a nowhere continuous injection that satisfies (6.1) and (6.5), and let g:ℂ→ℂ* be such that g(x)=exp(f(x)). Then g is surjective but not injective. Considering the unique t∈ℝ such that f(t)=2π, setting D(x):={x+nit:n∈ℤ}, and letting D be the choice set containing a unique element from each set in the collection {D(x):x∈ℂ}, it follows that g:D→CC* is a Costas cloud: if f has an everywhere dense graph in ℂ2, so does g in D×ℂ; if f is bijective, so is g. In particular, the choice D=ℝ+i[0,t) is possible.Proof.
The proof is a verbatim repetition of the proof of Theorem4.6, once the new range of the method (ℂ*) is established and injectivity is restored: to this end, we observe that
(6.11)ef(x′)=ef(x)⇔x′∈D(x),
hence the restriction of the domain to D, a set of distinct representatives of the various equivalence classes D(x), x∈ℂ, restores injectivity, hence bijectivity.Theorem 6.2 (Generalized Golomb construction in the complex continuum).
Letf:ℂ→ℂ be a nowhere continuous injection that satisfies (6.1) and (6.5), and let g:ℂ→ℂ* be such that exp(g(x))-exp(f(x))=1. Considering the unique t∈ℝ such that f(t)=2π, setting D(x)={x+nit:n∈ℤ} and R(y)={y+n2πi:n∈ℤ}, and letting D and R be the choice sets containing a unique element from each set in the collection {D(x):x∈ℂ} and {R(y):y∈ℂ*}, respectively, it follows that g:D→R is a Costas cloud: if f has an everywhere dense graph in ℂ2, so does g in D×R; if f is bijective, so is g. In particular, the choices D=ℝ+i[0,t) and R=(ℝ+i[0,2π))∖{0} are possible.Proof.
The proof is a verbatim repetition of the proof of Theorem4.9, after establishing bijectivity along the lines of the proof of Theorem 6.2. Note that here the exponential function affects both the domain and the range; so both of these sets need to be restricted to distinct representatives of equivalence classes.


## 6.1. Cauchy's Functional Equation onℂ

We need to study the properties of a functionf:ℂ→ℂ such that
(6.1)∀u,v∈ℂ:f(u+v)=f(u)+f(v).Applying the real argument twice (on the real and the imaginary numbers), we obtain(6.2)∀x,y∈ℚ,z∈ℂ:f((x+iy)z)=xf(z)+yf(iz).
Assuming that
(6.3)∃a,b∈ℝ,|a|+|b|>0:af(i)+bf(1)=0,f(ℚ+iℚ) lies on a straight line of ℂ; otherwise it is dense in ℂ. A verbatim repetition of the proof of the real case shows that f is continuous on ℂ if and only if it is continuous at a point: in this case, it follows that
(6.4)∀x,y∈ℝ,f(x+iy)=xf(1)+yf(i).We now need to ensure thatf is an injection/bijection, and that the graph of f, namely, {(z,f(z)):z∈ℂ}, is dense in ℂ2. The corresponding proof in the real case relied heavily on the linearity of f over rational multipliers, namely, on the condition that for all q∈ℚ, for all x∈ℝ,f(qx)=qf(x) (see Theorem 4.2), but this time the condition stated in (6.2) is not a linearity condition. We can still restrict our attention to linear solutions of (6.1) by imposing the compatibility condition:
(6.5)∀x∈ℝ,f(ix)=if(x);
this condition is equivalent to
(6.6)∀z∈ℂ,f(iz)=if(z),
because, letting z=x+iy, x,y∈ℝ, we get
(6.7)f(iz)=f(ix-y)=if(x)-f(y)=i(f(x)+if(y))=if(x+iy)=if(z).
Applying this condition to (6.2), we obtain
(6.8)∀x,y∈ℚ,z∈ℂ:f((x+iy)z)=(x+iy)f(z),
while we find directly that
(6.9)∀x,y∈ℝ,f(x+iy)=f(x)+if(y).
In other words, every solution of (4.1) can be extended to a solution of (6.1) that obeys the linearity property (6.8) over the complex rationals ℚ+iℚ; such functions have the property that f(ℝ)⊂ℝ, which is equivalent to f(iℝ)⊂iℝ. As (6.3) and (6.5) are not compatible, f(ℚ+iℚ) is dense in ℂ.Assumingf is continuous, (6.4) shows that for all z∈ℂ, f(z)=zf(1); assuming that the function is nowhere continuous, hence nonlinear, there exist z,w∈ℂ such that the vectors (z,f(z)) and (w,f(w)) are linearly independent. It follows that the set
(6.10){p(z,f(z))+q(w,f(w)):p,q∈ℚ+iℚ}={(pz+qw,f(pz+qw)):p,q∈ℚ+iℚ},
namely a subset of the graph of f, is countably infinite and dense in ℂ2.It remains to be seen that such a nonlinear function can be constructed. To achieve this, we proceed as in the proof of Theorem4.4: we consider ℂ2 as a vector space over the field of complex rationals ℚ+iℚ with an uncountable basis B={ba:a∈ℝ}. If f:B→B is a permutation other than the identity, f:ℂ→ℂ is a nowhere continuous bijection on ℂ whose graph is dense in ℂ2; if f:B→B is injective, f:ℂ→ℂ is a nowhere continuous injection on ℂ whose graph is dense in ℂ2.


## 6.2. The Golomb and Welch Constructions onℂ

The extensions of both the Golomb and the Welch construction inℝ, as seen in Section 4.3, involved the exponential function, which is multivalued over ℂ. For this reason, any further extension over ℂ will necessitate an appropriate restriction of the domain, or, equivalently, the redefinition of Costas property over equivalence classes of points, in order to restore injectivity and surjectivity. Both extensions, as stated below, follow this principle, setting their domain and/or range, as appropriate, to be sets of distinct representatives of such equivalence classes.Theorem 6.1 (Generalized Welch construction in the complex continuum).
Letf:ℂ→ℂ be a nowhere continuous injection that satisfies (6.1) and (6.5), and let g:ℂ→ℂ* be such that g(x)=exp(f(x)). Then g is surjective but not injective. Considering the unique t∈ℝ such that f(t)=2π, setting D(x):={x+nit:n∈ℤ}, and letting D be the choice set containing a unique element from each set in the collection {D(x):x∈ℂ}, it follows that g:D→CC* is a Costas cloud: if f has an everywhere dense graph in ℂ2, so does g in D×ℂ; if f is bijective, so is g. In particular, the choice D=ℝ+i[0,t) is possible.Proof.
The proof is a verbatim repetition of the proof of Theorem4.6, once the new range of the method (ℂ*) is established and injectivity is restored: to this end, we observe that
(6.11)ef(x′)=ef(x)⇔x′∈D(x),
hence the restriction of the domain to D, a set of distinct representatives of the various equivalence classes D(x), x∈ℂ, restores injectivity, hence bijectivity.Theorem 6.2 (Generalized Golomb construction in the complex continuum).
Letf:ℂ→ℂ be a nowhere continuous injection that satisfies (6.1) and (6.5), and let g:ℂ→ℂ* be such that exp(g(x))-exp(f(x))=1. Considering the unique t∈ℝ such that f(t)=2π, setting D(x)={x+nit:n∈ℤ} and R(y)={y+n2πi:n∈ℤ}, and letting D and R be the choice sets containing a unique element from each set in the collection {D(x):x∈ℂ} and {R(y):y∈ℂ*}, respectively, it follows that g:D→R is a Costas cloud: if f has an everywhere dense graph in ℂ2, so does g in D×R; if f is bijective, so is g. In particular, the choices D=ℝ+i[0,t) and R=(ℝ+i[0,2π))∖{0} are possible.Proof.
The proof is a verbatim repetition of the proof of Theorem4.9, after establishing bijectivity along the lines of the proof of Theorem 6.2. Note that here the exponential function affects both the domain and the range; so both of these sets need to be restricted to distinct representatives of equivalence classes.


## 7. General Construction Principles

The Costas property is very “unalgebraic’’, as most of the usual algebraic operations fail to preserve it: for example, the composition of two Costas functions is, in general, not a Costas function, and the same goes for their sum, product, and so forth. We now take a look at two operations that do preserve the Costas property.


### 7.1. Isomorphisms of Costas Sets

Group isomorphisms can be composed with Costas sets to yield new Costas sets, or to divide Costas sets into equivalence classes. This seemingly simple result has some important consequences; in particular, it can be used to prove the existence of new Costas clouds.Theorem 7.1.
LetC be a left Costas set in G1 with respect to D, and let f:G1→G2 be an isomorphism; then, f(C) is a left Costas set in G2 with respect to f(D).Proof.
Let⨂1, ⨂2 be the group operations in G1 and G2, respectively. Let d′∈f(D), and let c1′,c2′∈f(C); since f is an isomorphism, there exist unique d∈D and c1,c2∈C such that d′=f(d) and c1′=f(c1), c2′=f(c2). We need to verify that
(7.1)d′⨂2c1′,d′⨂2c2′∈f(C)⇒c1′=c2′.
But, because f is an isomorphism, it follows that
(7.2)d′⨂2c1′=f(d⨂1c1),d′⨂2c2′=f(d⨂1c2),
which implies that
(7.3)d⨂1c1,d⨂1c2∈C,
and therefore that c1=c2, as C is a Costas set. But then c1′=f(c1)=f(c2)=c2′, and this completes the proof.Theorem 7.2.
Bijective Costas clouds onℝ2 exist.Proof.
We use Theorem7.1 with G1=G2=ℝ2. Letting C correspond to the graph of a Costas bijection c:ℝ→ℝ with respect to ℝ, so that C is itself a Costas set with respect to ℝ2, and letting h:ℝ→ℝ be a nowhere continuous bijection (whose graph is then everywhere dense on ℝ2) that further satisfies Cauchy's equation (4.1), we obtain an (additive) isomorphism f:ℝ2→ℝ2, where f(x,y)=(x,h(y)), hence a bijective Costas cloud.
It all then comes down to finding the appropriate functionc; according to the results in [5], it is enough to find c:ℝ→ℝ bijective, differentiable, and strictly monotonic, with a strictly monotonic derivative, as such a function is guaranteed to have the Costas property. We propose
(7.4)c(x)={ln(1+x),x≥0,-x2+x,x<0.
This function is bijective, as c(ℝ+)=ℝ+, c(ℝ-)=ℝ-, and c is strictly increasing in each of its two branches. It is also continuous everywhere, as it is continuous on each branch and also c(0)=0; furthermore, it is also continuously differentiable everywhere, as
(7.5)c′(x)={11+x,x>0,-2x+1,x<0,
and also, by taking the limits on each branch, c′(0)=1. Finally, the derivative is decreasing on each branch, hence everywhere by its continuity: in particular, c′(x)≤1, x≥0, while c′(x)>1, x<0.
It follows thatf(C)={(x,h(c(x))):x∈ℝ} is a bijective Costas cloud. This completes the proof.


### 7.2. Tensor Products

Theorem 7.3.
LetSi be a left (right) Costas set in Gi with respect to Di, i=1,2; then S1×S2 is a left (right) Costas set in G1×G2 with respect to D1×D2.Proof.
The proof is practically obvious: letting⨂1, ⨂2, and ⊗ be the group operations in G1, G2, and G, respectively, and letting di∈Di, i=1,2, we consider S1×S2∩((d1,d2)⊗S1×S2). Should (x1,x2), (y1,y2) be in this intersection, there would exist (x1′,x2′),(y1′,y2′)∈S1×S2 such that
(7.6)(d1,d2)⊗(x1,x2)=(x1′,x2′),(d1,d2)⊗(y1,y2)=(y1′,y2′),
which is equivalent to saying that the following 4 equalities should hold concurrently:
(7.7)d1⨂1x1=x1′,d1⨂1y1=y1′,d2⨂2x2=x2′,d2⨂2y2=y2′.
The former two relations, though, because S1 is a Costas set, would imply that x1=y1, and similarly the latter two that x2=y2; thus, (x1,x2)=(y1,y2), and this completes the proof.For example, letS be the bijective Costas cloud constructed in Theorem 7.2; it follows from Theorem 7.3 that S×S is a Costas set in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)*. Considering further the set A={(s1,s3,s2,s4):(s1,s2,s3,s4)∈S×S}, resulting from a permutation of the coordinates of S×S, we see that coordinates a1=s1 and a2=s3 span ℝ2, and so do a3=s2 and a4=s4, in such a way that the mapping between (a1,a2) and (a3,a4) is bijective and dense in ℝ2×ℝ2=ℝ4; it follows that A is a bijective Costas set dense in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)* is or, equivalently, in ℂ×ℂ=ℂ2 with respect to ℂ*×ℂ*, due to the isomorphism between ℂ and ℝ2.As another example, let nowf1,f2:ℝ→ℝ be smooth Costas bijections, for example, such as g constructed in the proof of Theorem 7.2, and let S1, S2 be the graphs of f1, f2, respectively. Invoking Theorem 7.3, we see that S1×S2 is a Costas set in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)*. But, using again the isomorphism between ℝ2 and ℂ and the permutation of coordinates mentioned above to construct A from S1×S2, we find that A is the graph of f:ℂ→ℂ such that
(7.8)f(x+iy)=f1(x)+if2(y),x,y∈ℝ,
which is clearly a smooth bijection.As a final caveat, however, note that Theorem7.3 can easily be misunderstood to assert more than it actually does: assuming Di=Gi, i=1,2, the theorem asserts that S1×S2 is a Costas set with respect to G1*×G2*, which is quite a different set than (G1×G2)*. In particular, neither of the Costas sets constructed in the two examples above is a Costas cloud. Finding a tensor construction for Costas clouds remains, then, an open problem.


## 7.1. Isomorphisms of Costas Sets

Group isomorphisms can be composed with Costas sets to yield new Costas sets, or to divide Costas sets into equivalence classes. This seemingly simple result has some important consequences; in particular, it can be used to prove the existence of new Costas clouds.Theorem 7.1.
LetC be a left Costas set in G1 with respect to D, and let f:G1→G2 be an isomorphism; then, f(C) is a left Costas set in G2 with respect to f(D).Proof.
Let⨂1, ⨂2 be the group operations in G1 and G2, respectively. Let d′∈f(D), and let c1′,c2′∈f(C); since f is an isomorphism, there exist unique d∈D and c1,c2∈C such that d′=f(d) and c1′=f(c1), c2′=f(c2). We need to verify that
(7.1)d′⨂2c1′,d′⨂2c2′∈f(C)⇒c1′=c2′.
But, because f is an isomorphism, it follows that
(7.2)d′⨂2c1′=f(d⨂1c1),d′⨂2c2′=f(d⨂1c2),
which implies that
(7.3)d⨂1c1,d⨂1c2∈C,
and therefore that c1=c2, as C is a Costas set. But then c1′=f(c1)=f(c2)=c2′, and this completes the proof.Theorem 7.2.
Bijective Costas clouds onℝ2 exist.Proof.
We use Theorem7.1 with G1=G2=ℝ2. Letting C correspond to the graph of a Costas bijection c:ℝ→ℝ with respect to ℝ, so that C is itself a Costas set with respect to ℝ2, and letting h:ℝ→ℝ be a nowhere continuous bijection (whose graph is then everywhere dense on ℝ2) that further satisfies Cauchy's equation (4.1), we obtain an (additive) isomorphism f:ℝ2→ℝ2, where f(x,y)=(x,h(y)), hence a bijective Costas cloud.
It all then comes down to finding the appropriate functionc; according to the results in [5], it is enough to find c:ℝ→ℝ bijective, differentiable, and strictly monotonic, with a strictly monotonic derivative, as such a function is guaranteed to have the Costas property. We propose
(7.4)c(x)={ln(1+x),x≥0,-x2+x,x<0.
This function is bijective, as c(ℝ+)=ℝ+, c(ℝ-)=ℝ-, and c is strictly increasing in each of its two branches. It is also continuous everywhere, as it is continuous on each branch and also c(0)=0; furthermore, it is also continuously differentiable everywhere, as
(7.5)c′(x)={11+x,x>0,-2x+1,x<0,
and also, by taking the limits on each branch, c′(0)=1. Finally, the derivative is decreasing on each branch, hence everywhere by its continuity: in particular, c′(x)≤1, x≥0, while c′(x)>1, x<0.
It follows thatf(C)={(x,h(c(x))):x∈ℝ} is a bijective Costas cloud. This completes the proof.


## 7.2. Tensor Products

Theorem 7.3.
LetSi be a left (right) Costas set in Gi with respect to Di, i=1,2; then S1×S2 is a left (right) Costas set in G1×G2 with respect to D1×D2.Proof.
The proof is practically obvious: letting⨂1, ⨂2, and ⊗ be the group operations in G1, G2, and G, respectively, and letting di∈Di, i=1,2, we consider S1×S2∩((d1,d2)⊗S1×S2). Should (x1,x2), (y1,y2) be in this intersection, there would exist (x1′,x2′),(y1′,y2′)∈S1×S2 such that
(7.6)(d1,d2)⊗(x1,x2)=(x1′,x2′),(d1,d2)⊗(y1,y2)=(y1′,y2′),
which is equivalent to saying that the following 4 equalities should hold concurrently:
(7.7)d1⨂1x1=x1′,d1⨂1y1=y1′,d2⨂2x2=x2′,d2⨂2y2=y2′.
The former two relations, though, because S1 is a Costas set, would imply that x1=y1, and similarly the latter two that x2=y2; thus, (x1,x2)=(y1,y2), and this completes the proof.For example, letS be the bijective Costas cloud constructed in Theorem 7.2; it follows from Theorem 7.3 that S×S is a Costas set in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)*. Considering further the set A={(s1,s3,s2,s4):(s1,s2,s3,s4)∈S×S}, resulting from a permutation of the coordinates of S×S, we see that coordinates a1=s1 and a2=s3 span ℝ2, and so do a3=s2 and a4=s4, in such a way that the mapping between (a1,a2) and (a3,a4) is bijective and dense in ℝ2×ℝ2=ℝ4; it follows that A is a bijective Costas set dense in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)* is or, equivalently, in ℂ×ℂ=ℂ2 with respect to ℂ*×ℂ*, due to the isomorphism between ℂ and ℝ2.As another example, let nowf1,f2:ℝ→ℝ be smooth Costas bijections, for example, such as g constructed in the proof of Theorem 7.2, and let S1, S2 be the graphs of f1, f2, respectively. Invoking Theorem 7.3, we see that S1×S2 is a Costas set in ℝ2×ℝ2=ℝ4 with respect to (ℝ2)*×(ℝ2)*. But, using again the isomorphism between ℝ2 and ℂ and the permutation of coordinates mentioned above to construct A from S1×S2, we find that A is the graph of f:ℂ→ℂ such that
(7.8)f(x+iy)=f1(x)+if2(y),x,y∈ℝ,
which is clearly a smooth bijection.As a final caveat, however, note that Theorem7.3 can easily be misunderstood to assert more than it actually does: assuming Di=Gi, i=1,2, the theorem asserts that S1×S2 is a Costas set with respect to G1*×G2*, which is quite a different set than (G1×G2)*. In particular, neither of the Costas sets constructed in the two examples above is a Costas cloud. Finding a tensor construction for Costas clouds remains, then, an open problem.


## 8. Conclusion

We abstracted the Costas property and stated it in the context of an arbitrary (possibly even nonAbelian) group. As a consequence, Costas arrays and Golomb rulers were both found to be Costas sets, instantiations of the Costas property over different groups. The bijectivity condition in the case of Costas arrays is an additional, peripheral requirement, not directly related to the Costas property. We did not further pursue the direction of the study of Costas sets over nonAbelian groups, which we leave as future work, but turned our attention to groups with the analytic property of being dense in themselves instead (such asℚ, ℝ, and ℂ): after a brief overview of the known construction methods for Costas arrays and Golomb rulers, we embarked on the study of Costas sets that are dense in the group they belong to; we named these sets Costas clouds.We first constructed explicit examples of real, nowhere continuous bijections whose graphs satisfy a constrained form of the Costas property (over rational or algebraic displacements only, i.e.), using the indicator function of the rationals or of the algebraic numbers as a building block. Furthermore, we constructed real Costas clouds, based on Cauchy's functional equation: these are perhaps what first springs into one's mind when considering possible generalizations of Costas arrays in the continuum, due to the very haphazard positioning of their dots. These Costas clouds led to the generalization in the continuum of the two main generation methods for Costas permutations, namely, the Welch and the Golomb construction. These functions are highly nontrivial to construct, and their existence nontrivial to prove. We also considered rational Costas clouds, which were easier to construct thanks to the enumerability of the rationals.Similarly, we proved the existence of (countably and uncountably) infinite Golomb rulers in a (finite of infinite) interval of the real line, that can optionally be constructed so that they have the extra property of being everywhere dense in this interval. We also noted that, though “infinite dense’’ Golomb rulers have appeared in literature before, the word “dense’’ had an entirely different meaning and was not used in the analytic sense.Both uncountable constructions (Costas clouds and Golomb rulers) relied on two ideas, namely, the consideration ofℝ as vector space over ℚ possessing an uncountable basis, and the use of Cauchy's functional equation (in the case of Costas clouds). These ideas not only made the proof of the existence of these objects possible but also revealed how much freedom we have for their construction; without these ideas the tasks seemed hopeless. Regarding the corresponding countably infinite (e.g., rational) objects, enumerability itself is sufficient to both establish existence and allow great freedom of construction.The extension to complex numbers of the construction methods for Costas clouds we presented was possible and necessitated a slight modification of the Cauchy functions used. The main obstacle, however, was the multivalued nature of the exponential function that is involved in both the Golomb and the Welch method: in order to re-establish bijectivity, the Costas sets produced by these methods needed to be appropriately redefined over equivalence classes of points (or distinct representatives thereof).Despite all of our efforts, the real Costas clouds we were able to construct through the extensions of the Golomb and the Welch method were limited on genuine subsets of the real plane (the upper half plane, an infinite strip, etc.). A bijective Costas cloud on the entire real plane was finally constructed by a new general construction principle applicable on any group, namely, that the composition of a Costas set with a group isomorphism results in a new Costas set: in this particular instance, the graph of a suitably constructed smooth Costas function onℝ was composed with a Cauchy function. Another general construction principle, namely, the formation of tensor products of Costas sets, allowed the construction of a bijective Costas set on ℂ2.The ideas presented here have potentially far reaching consequences, which we intend to investigate as future work: for example, Costas sets over arbitrary (even noncommutative) groups have never been studied (to the best of our knowledge); how would Costas arrays over GL(n) or SL(n) look, or even over more complex groups, such as fields of rational functions over finite fields or p-adic fields? Furthermore, Theorem 7.1 implies that Costas sets in a group can be classified into equivalence classes defined by their orbits under the automorphism group of the group in question; we hope that this classification will help us further understand the structure of Costas sets.



---

*Source: 467342-2009-11-23.xml*