Combinatorics and Computing Weekly Seminar
Legendre Pairs
Legendre Pairs
Arne Winterhof , RICAM, Austrian Academy of Sciences, Austria
23 APR 2025
14:00 - 15:00
Let A=[a_₀, a_₁, ..., a_{n-1}] ∈ ℂ^ℓ be a finite complex sequence of length ℓ periodically continued with period ℓ. The periodic autocorrelation function PAF(A,s) of A at lag s is PAF(A, s) =∑ {j=0}^{ℓ-1} a_joverline{a_{j+s}}, s=0,1, ..., ℓ-1. Two sequences A and B of the same length ℓ. form a Legendre pair (A,B) if PAF(A,s)+PAF(B,s)=-2, s=1,2, ?, ⌊n/2⌋. Binary Legendre pairs of length ℓ are pertinent to the construction of Hadamard matrices of order ℓ +2 which can exist only if ℓ is odd. It is conjectured that there is a binary Legendre pair of every odd length ℓ which is stronger than the Hadamard-matrix conjecture. Several infinite classes of Legendre pairs are known. The most prominent constructions are defined via characters of finite fields. In particular, there are Legendre pairs of length ℓ for every prime ℓ =p and every Mersenne number ℓ =2^s-1, respectively. The smallest undecided case is ℓ=11. In the first part of the talk we summarize the known results on binary Legendre pairs. In the second part we discuss quaternary Legendre pairs of length ℓ. In contrast to binary Legendre pairs they can exist for even ℓ as well. Very recently, the first infinite construction was found by Jedwab and Pender completing our earlier semi-construction. We give also constructions of quaternary Legendre pairs of length ℓ for all remaining even ℓ < 42. The smallest open case is ℓ =42 and the case ℓ =46 is particularly interesting since the existence of a quaternary Legendre pair of this length would imply the existence of a quaternary Hadamard matrix of order 94. Finally, we mention generalizations to k-ary sequences.
Zoom room information:
https://us06web.zoom.us/j/84906984159?pwd=BCWaIbXBuku3A5I84zNg9mHFxVZjXD.1
Meeting ID: 849 0698 4159
Passcode: 362880
Venue: Niavaran, Lecture Hall 1