A Note on the Cross-Correlation of Costas Permutations
Domingo Gómez‐Pérez, Arne Winterhof · IEEE Transactions on Information Theory · 2020
We build on the work of Drakakis et al. (2011) on the maximal cross-correlation of the families of Welch and Golomb Costas permutations. In particular, we settle some of their conjectures. More precisely, we prove two results. First, for a prime p ≥ 5, the maximal cross-correlation of the family of the φ(p-1) different Welch Costas permutations of {1, . . . , p-1} is (p - 1)/t, where t is the smallest prime divisor of (p - 1)/2 if p is not a safe prime and at most 1 + p1/2otherwise. Here φ denotes Euler's totient function and a prime p is a safe prime if (p - 1)/2 is also prime. Second, for a prime power q ≥ 4 the maximal cross-correlation of a subfamily of Golomb Costas permutations of {1, . . . , q - 2} is (q - 1)/t - 1 if t is the smallest prime divisor of (q - 1)/2 if q is odd and of q - 1 if q is even provided that (q - 1)/2 and q - 1 are not prime, and at most 1 + q1/2otherwise. Note that we consider a smaller family than Drakakis et al. Our family is of size φ(q - 1) whereas there are φ(q - 1)2different Golomb Costas permutations. The maximal cross-correlation of the larger family given in the tables of Drakakis et al. is larger than our bound (for the smaller family) for some q.