# Legendre pairs of lengths $\ell\equiv 0\,(\mathrm{mod}\;3)$

Ilias Kotsireas & Christoph Koutschan Corresponding author. Supported by an
NSERC grant.Supported by the Austrian Science Fund (FWF): F5011-N15.
This paper has been published in Journal of Combinatorial Designs 29:870–887,
DOI: 10.1002/jcd.21806

###### Abstract

We prove a proposition that connects constant-PAF sequences and the
corresponding Legendre pairs with integer PSD values. We show how to determine
explicitly the complete spectrum of the $({\ell}/{3})$-rd value of the
discrete Fourier transform for Legendre pairs of lengths $\ell\equiv
0\,(\mathrm{mod}\;3)$. This is accomplished by two new algorithms based on
number-theoretic arguments. As an application, we prove that Legendre pairs of
the open lengths $117$, $129$, $133$, and $147$ exist by finding Legendre
pairs of these lengths with a multiplier group of order at least $3$. As a
consequence, $85$, $87$, $115$, $145$, $159$, $161$, $169$, $175$, $177$,
$185$, $187$, $195$ are the twelve integers in the range $<200$ for which the
question of existence of Legendre pairs remains unsolved.

Keywords: Legendre pairs, Discrete Fourier Transform, Compression, Hadamard
matrix

##  1 Introduction

Let $A$ denote a finite sequence $A=[a_{1},\ldots,a_{\ell}]$ of length $\ell$.

The periodic autocorrelation function (PAF) of $A$ at lag $s$ is defined as

$\operatorname{PAF}(A,s)=\displaystyle\sum_{i=1}^{\ell}a_{i}\,a_{i+s},\quad\forall\,\,s=0,\ldots,\ell-1,$
(1)

where $i+s$ is taken modulo $\ell$, when $i+s>\ell$.

The discrete Fourier transform (DFT) of $A$ at lag $s$ is defined as

$\operatorname{DFT}(A,s)=\displaystyle\sum_{i=1}^{\ell}a_{i}\,\omega^{s\cdot(i-1)},\quad\forall\,\,s=1,\ldots,\ell,$
(2)

where $\omega=\cos\left({2\pi}/{\ell}\right)+i\sin\left({2\pi}/{\ell}\right)$
is the primitive $\ell$-th root of unity, that satisfies $\omega^{\ell}=1$.

The power spectral density (PSD) of $A$ at lag $s$ is defined as

$\operatorname{PSD}(A,s)=\bigl{|}\operatorname{DFT}(A,s)\bigr{|}^{2}=\Re(\operatorname{DFT}(A,s))^{2}+\Im(\operatorname{DFT}(A,s))^{2},\quad\forall\,\,s=1,\ldots,\ell$
(3)

i.e., the PSD values are defined as the sum of squares of the real and
imaginary parts of the DFT values.

Let $\ell$ be an odd positive integer. Two sequences
$A=[a_{1},\ldots,a_{\ell}]$ and $B=[b_{1},\ldots,b_{\ell}]$ of length $\ell$
and consisting of elements from $\\{-1,+1\\}$, such that
$a_{1}+\ldots+a_{\ell}=b_{1}+\ldots+b_{\ell}=\pm 1$ form a Legendre pair of
length $\ell$ if

$\operatorname{PAF}(A,s)+\operatorname{PAF}(B,s)=-2,\quad\forall\,\,s=1,\ldots,\frac{\ell-1}{2}.$
(4)

In the context of Legendre pairs, we typically work with the sole assumption
that $a_{1}+\ldots+a_{\ell}=1$ and $b_{1}+\ldots+b_{\ell}=1$, without loss of
generality. It is well-known, see [3], that if $(A,B)$ form a Legendre pair of
length $\ell$, then we have

$\operatorname{PSD}(A,s)+\operatorname{PSD}(B,s)=2\ell+2,\quad\forall\,\,s=1,\ldots,\frac{\ell-1}{2}.$
(5)

The paper [3] is fundamental in the study of Legendre pairs, as it initiated
the use of the PSD criterion, in the search for Legendre pairs. More
specifically, the PSD criterion asserts that if, in the course of a search
algorithm, an index $i$ in the range $1,\ldots,(\ell-1)/{2}$ is detected, such
that $\operatorname{PSD}(A,i)>2\ell+2$, then the corresponding (candidate)
sequence $A$ can be discarded from the search, because it is unsuitable to
form a Legendre pair. This is due to the fact that the PSD values are always
non-negative, as sums of norm squares. Given a Legendre pair of length $\ell$,
one can construct a Hadamard matrix of order $2\ell+2$, using a two circulant
core template array found in [3].

Throughout this paper, we use the notation $\mathbb{Z}_{\ell}^{\star}$ to
denote the multiplicative group
$\\{j\in\mathbb{Z}_{\ell}\mid\gcd(j,\ell)=1\\}$. Let
$I\subseteq\mathbb{Z}_{\ell}$, then an element $t\in\mathbb{Z}_{\ell}^{\star}$
is called a multiplier of $I$ if there exists $g\in\mathbb{Z}_{\ell}$ such
that

$t\cdot I=I+g,$

where $I+g:=\\{i+g\mid i\in I\\}$ and analogously for $t\cdot I$. We say that
$t$ is a multiplier for a sequence
$A=[a_{1},\dots,a_{\ell}]\in\\{-1,+1\\}^{\ell}$ if it is a multiplier of
$I:=\\{i\in\mathbb{Z}_{\ell}\mid a_{i}=1\\}$. See [9] for more details. In
this paper, we restrict our searches for Legendre pairs to sequences whose
group of multipliers contains a prespecified subgroup of
$\mathbb{Z}_{\ell}^{\star}$, also known as the union-of-orbits approach. In
most instances considered here, we specify a subgroup of size $3$, so that the
search space is neither too restrictive causing no Legendre pairs to be found,
nor too large causing the algorithm to get stuck in parts of the search space
that contain no Legendre pairs given the current computational resources.

The rest of the paper is organized as follows. In Section 2, we present some
theoretical results on the possible PSD values of sequences in Legendre pairs,
under the assumption that their length $\ell$ is divisible by $3$. These
results are then exploited in Section 4, where we use them as additional
filter criteria in order to speed up our exhaustive searches for Legendre
pairs. With the help of considerable computational resources, we succeeded to
find Legendre pairs of lengths $\ell=117$, $\ell=129$, and $\ell=147$. It was
unknown until now whether Legendre pairs of these lengths existed or not (see
Sections 4.1 – 4.3). As an encore, in Section 4.4 we hint at the possibility
of extending our ideas to lengths $\ell$ that are not necessarily divisible by
$3$ but by some other small prime, and for the first time present some
examples of Legendre pairs of length $\ell=133$.

##  2 Legendre pairs of length $\ell\equiv 0\,(\mathrm{mod}\;3)$

Consider $(A,B)$ a Legendre pair of length $\ell$ such that $\ell\equiv
0\,(\mathrm{mod}\;3)$ and set $m={\ell}/{3}$. The following lemma is proved in
[4]

######  Lemma 1.

Let $\ell$ be an odd integer such that $\ell\equiv 0\,(\mathrm{mod}\;3)$ and
let $m={\ell}/{3}$. Let $A=[a_{1},\ldots,a_{\ell}]$ be a
$\\{-1,+1\\}$-sequence. Then

$\operatorname{DFT}(A,m)=\left(A_{1}-\frac{1}{2}A_{2}-\frac{1}{2}A_{3}\right)+\left(\frac{\sqrt{3}}{2}A_{2}-\frac{\sqrt{3}}{2}A_{3}\right)i,$
$\operatorname{PSD}(A,m)=A_{1}^{2}+A_{2}^{2}+A_{3}^{2}-A_{1}A_{2}-A_{1}A_{3}-A_{2}A_{3},$

where

$A_{1}=\sum_{i=0}^{m-1}a_{3i+1},\,\,\,A_{2}=\sum_{i=0}^{m-1}a_{3i+2},\,\,\,A_{3}=\sum_{i=0}^{m-1}a_{3i+3}.$

The proof of Lemma 1 is based on the exact evaluation of the roots of the
cyclotomic polynomial of degree $3$.

Let $\mathcal{A}=\\{a_{1},\ldots,a_{\ell}\\}$, and

$e_{2}(\mathcal{A})=\sum_{i<j}a_{i}a_{j}$

denote the second elementary symmetric function on $\mathcal{A}$. Let

$p_{1}(\mathcal{A})=\sum_{i=1}^{\ell}a_{i}\quad\text{and}\quad
p_{2}(\mathcal{A})=\displaystyle\sum_{i=1}^{\ell}a_{i}^{2}$

denote the first and second power sums on $\mathcal{A}$. The following special
case of the Jacobi-Trudi identity

$e_{2}(\mathcal{A})=\frac{p_{1}(\mathcal{A})^{2}}{2}-\frac{p_{2}(\mathcal{A})}{2}$
(6)

can be found in [7].

Applying Lemma 1 to a Legendre pair $(A,B)$ of length $\ell$ such that
$\ell\equiv 0\,(\mathrm{mod}\;3)$, we obtain the following:

######  Corollary 1.

If $\ell\equiv 0\,(\mathrm{mod}\;3)$, $m={\ell}/{3}$, and if the two
$\\{-1,+1\\}$-sequences $A=[a_{1},\ldots,a_{\ell}]$ and
$B=[b_{1},\ldots,b_{\ell}]$ form a Legendre pair of length $\ell$, then

$\left\\{\begin{array}[]{l}\operatorname{PSD}(A,m)=\displaystyle\frac{3}{2}\left(A_{1}^{2}+A_{2}^{2}+A_{3}^{2}\right)-\displaystyle\frac{1}{2}\\\
\\\
\operatorname{PSD}(B,m)=\displaystyle\frac{3}{2}\left(B_{1}^{2}+B_{2}^{2}+B_{3}^{2}\right)-\displaystyle\frac{1}{2}\end{array}\right.$
(7) $A_{1}^{2}+A_{2}^{2}+A_{3}^{2}+B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=4m+2$ (8)

where

$\displaystyle A_{1}$ $\displaystyle=\sum_{i=0}^{m-1}a_{3i+1},\quad$
$\displaystyle A_{2}$ $\displaystyle=\sum_{i=0}^{m-1}a_{3i+2},\quad$
$\displaystyle A_{3}$ $\displaystyle=\sum_{i=0}^{m-1}a_{3i+3},$ $\displaystyle
B_{1}$ $\displaystyle=\sum_{i=0}^{m-1}b_{3i+1},$ $\displaystyle B_{2}$
$\displaystyle=\sum_{i=0}^{m-1}b_{3i+2},$ $\displaystyle B_{3}$
$\displaystyle=\sum_{i=0}^{m-1}b_{3i+3}.$

###### Proof.

Applying Lemma 1 to the sequences $A$, $B$ separately we obtain

$\displaystyle\operatorname{PSD}(A,m)$
$\displaystyle=A_{1}^{2}+A_{2}^{2}+A_{3}^{2}-\underbrace{(A_{1}A_{2}+A_{1}A_{3}+A_{2}A_{3})}_{e_{2}(A_{1},A_{2},A_{3})},$
$\displaystyle\operatorname{PSD}(B,m)$
$\displaystyle=B_{1}^{2}+B_{2}^{2}+B_{3}^{2}-\underbrace{(B_{1}B_{2}+B_{1}B_{3}+B_{2}B_{3})}_{e_{2}(B_{1},B_{2},B_{3})}.$

The second elementary symmetric functions $e_{2}(A_{1},A_{2},A_{3})$ and
$e_{2}(B_{1},B_{2},B_{3})$ are related to the first elementary symmetric
functions $e_{1}(A_{1},A_{2},A_{3})$ and $e_{1}(B_{1},B_{2},B_{3})$ via the
special case of the Jacobi-Trudi identity (6). We also know that
$e_{1}(A_{1},A_{2},A_{3})=A_{1}+A_{2}+A_{3}=1$ and
$e_{1}(B_{1},B_{2},B_{3})=B_{1}+B_{2}+B_{3}=1$. Therefore we obtain (7), and

$\displaystyle A_{1}^{2}+A_{2}^{2}+A_{3}^{2}+B_{1}^{2}+B_{2}^{2}+B_{3}^{2}$
$\displaystyle=\frac{2\operatorname{PSD}(A,m)+1}{3}+\frac{2\operatorname{PSD}(B,m)+1}{3}$
$\displaystyle=\frac{2(2\ell+2)+2}{3}=\frac{4\ell+6}{3}=4m+2.\qed$

In the sequel, we denote $\operatorname{PSD}(A,m)$ by $\widehat{A}_{m}$ and
$\operatorname{PSD}(B,m)$ by $\widehat{B}_{m}$.

Corollary 8 can be used to derive additional decoupled constraints (i.e.,
involving $A_{i}$ and $B_{i}$ separately) based on (8). From (5) we know:

$\widehat{A}_{m}+\widehat{B}_{m}=2\ell+2.$ (9)

Moreover, from (7) we obtain:

$A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=\frac{2\widehat{A}_{m}+1}{3}\quad\text{and}\quad
B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=\frac{2\widehat{B}_{m}+1}{3}.$ (10)

Since both these sums of three odd integer squares are integers, we obtain
that $2\widehat{A}_{m}+1\equiv 9\,(\mathrm{mod}\;24)$ and
$2\widehat{B}_{m}+1\equiv 9\,(\mathrm{mod}\;24)$ i.e. $\widehat{A}_{m}\equiv
4\,(\mathrm{mod}\;12)$ and $\widehat{B}_{m}\equiv 4\,(\mathrm{mod}\;12)$.
Therefore, the set of possible pairs of values
$\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ can be restricted
considerably. In addition, a possible pair of values
$\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ has to be compatible with
the linear constraints

$A_{1}+A_{2}+A_{3}=1\quad\text{and}\quad B_{1}+B_{2}+B_{3}=1.$ (11)

For a Legendre pair $(A,B)$ of length $\ell$, we must have that
$A_{1},A_{2},A_{3},B_{1},B_{2},B_{3}$ are all odd. For given fixed values of
$\widehat{A}_{m}$, $\widehat{B}_{m}$, equations (10) can be solved
independently as sums-of-squares Diophantine equations and typically have
anywhere from $1$ to $5$ all-odd solutions (up to sign), for the right-hand-
side values that arise in the context of Legendre pairs of lengths $\ell<200$.
These solutions give possible triplets of values for $(A_{1},A_{2},A_{3})$ and
$(B_{1},B_{2},B_{3})$ that must be compatible with the linear constraints
(11). The above discussion suffices to formulate an algorithm for determining
explicitly the complete spectrum of the $({\ell}/{3})$-rd PSD values for any
Legendre pair of length $\ell$ divisible by three. We outline this algorithm
below.

Input: An odd positive integer $\ell=3\cdot m$ ;

Initialization: ${\cal S}=\\{\\}$ ;

for  _$s=0,\ldots,\lfloor(\ell-1)/6\rfloor$_ do

(1) form the candidate $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ pair
$[12s+4,2\ell+2-(12s+4)]$ ;

(2) compute the values of $A_{1}^{2}+A_{2}^{2}+A_{3}^{2}$ and
$B_{1}^{2}+B_{2}^{2}+B_{3}^{2}$ using (10) ;

(3) solve (up to sign) the two sum-of-squares Diophantine equations

[1ex] $\qquad A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=\dfrac{2(12s+4)+1}{3}$,

[1ex] $\qquad B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=\dfrac{2(2\ell+2-(12s+4))+1}{3}$ ;

if  _there are all-odd solutions of these two Diophantine equations,
compatible with the linear constraints ( 11) _ then

insert the pair $[12s+4,2\ell+2-(12s+4)]$ in ${\cal S}$, as an element of the
spectrum of $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ ;

else

discard the pair $[12s+4,2\ell+2-(12s+4)]$ as it cannot be an element of the
spectrum of $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ ;

end if

end for

Output: the spectrum ${\cal S}$ of pairs of values
$\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ for Legendre pairs $(A,B)$
of length $\ell=3\cdot m$ ;

Algorithm 1 Determination of the spectrum ${\cal S}$

######  Example 1.

We illustrate Algorithm 1 with the case $\ell=117=3\cdot 39$, i.e., $m=39$.
First, we have $\widehat{A}_{m}+\widehat{B}_{m}=2\cdot 117+2=236$ and in
addition $\widehat{A}_{m}\equiv 4\,\,(\mathrm{mod}\;12)$ and
$\widehat{B}_{m}\equiv 4\,\,(\mathrm{mod}\;12)$. Given that every pair of
values $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ determines the values
of $A_{1}^{2}+A_{2}^{2}+A_{3}^{2}$ and $B_{1}^{2}+B_{2}^{2}+B_{3}^{2}$ via
(10), we obtain Table 1. The first row of Table 1 indicates a reason why a
certain $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ combination can be
discarded. The last three rows of Table 1 indicate the only three
$\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ combinations that can
possibly hold. The remaining rows of the table corresponding to all other
$\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ combinations are omitted.
The omitted rows do not lead to compatible assignments for $A_{1},A_{2},A_{3}$
and/or $B_{1},B_{2},B_{3}$. Only $3$ pairs of values are not ruled out to
occur in Legendre pairs of length $117$. This allows us to add an additional
layer of parallelism when searching for such Legendre pairs.

$\begin{array}[]{l|l@{}}\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}&\\\
\hline\cr\rule{0.0pt}{12.0pt}(4,232)&A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=3,\leadsto[1,1,1]\\\
&B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=155,\leadsto[3,5,11],[5,7,9]\leadsto\mbox{no
compatible assignments}\\\
\hline\cr\rule{0.0pt}{12.0pt}(28,208)&A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=19,\leadsto[1,3,3]\\\
&B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=139,\leadsto[3,3,11],[3,7,9]\\\
&\mbox{compatible assignments:
}(A_{1},A_{2},A_{3})=(1,-3,3),(B_{1},B_{2},B_{3})=(3,7,-9)\\\
\hline\cr\rule{0.0pt}{12.0pt}(64,172)&A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=43,\leadsto[3,3,5]\\\
&B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=115,\leadsto[3,5,9]\\\ &\mbox{compatible
assignments: }(A_{1},A_{2},A_{3})=(3,3,-5),(B_{1},B_{2},B_{3})=(-3,-5,9)\\\
\hline\cr\rule{0.0pt}{12.0pt}(112,124)&A_{1}^{2}+A_{2}^{2}+A_{3}^{2}=75,\leadsto[1,5,7],[5,5,5]\\\
&B_{1}^{2}+B_{2}^{2}+B_{3}^{2}=83,\leadsto[1,1,9],[3,5,7]\\\ &\mbox{compatible
assignments: }(A_{1},A_{2},A_{3})=(-1,-5,7),(B_{1},B_{2},B_{3})=(3,5,-7)\\\
\hline\cr\end{array}$ Table 1: Some computations using Algorithm 1 for the
spectrum of $\bigl{[}\widehat{A}_{m},\widehat{B}_{m}\bigr{]}$ for $m=39$.

If $H$ is a subgroup of $\mathbb{Z}_{\ell}^{\star}$ of size $3$, then $H$ is
cyclic and all of its elements must be $1\,(\mathrm{mod}\;3)$. Moreover, if
$H$ is a subgroup of $\mathbb{Z}_{\ell}^{\star}$ with all its members equal to
$1\,(\mathrm{mod}\;3)$, then each orbit of $H$ consists of elements that are
equal to each other $(\mathrm{mod}\;3)$. The consequence is that each orbit
contributes to exactly one of the three quantities $A_{1},A_{2},A_{3}$ that
were defined in Lemma 1. We can exploit this observation to further confine
the potential values for $\widehat{A}_{m}$ and $\widehat{B}_{m}$. The
following algorithm is formulated under the assumption that the chosen orbits
indicate the positions of the $+1$’s, but since $\widehat{A}_{m}$ is a sum-of-
squares in the $A_{i}$, it works also in situations where the chosen orbits
mark the positions of the $-1$’s.

Input: An odd positive integer $\ell=3\cdot m$, a subgroup $H$ of
$\mathbb{Z}_{\ell}^{\star}$ s.t. $h\equiv 1\,(\mathrm{mod}\;3)$ for all $h\in
H$, and non-negative integers $c_{1},\dots,c_{t}$ indicating the number of
chosen orbits of sizes $s_{1},\dots,s_{t}$, respectively ;

for  _$i=1,\dots,t$_ do

for  _$j\in\\{0,1,2\\}$_ do

$n_{i,j}=$ number of orbits of size $s_{i}$ with elements $\equiv
j\,(\mathrm{mod}\;3)$ ;

end for

end for

$T=\bigl{\\{}(k_{1,1},\dots,k_{t,1},k_{1,2},\dots,k_{t,2})\mathrel{\big{|}}$

$0\leq k_{1,1}\leq\min\\{c_{1},n_{1,1}\\},\dots,0\leq
k_{t,1}\leq\min\\{c_{t},n_{t,1}\\},$

$0\leq k_{1,2}\leq\min\\{c_{1},n_{1,2}\\},\dots,0\leq
k_{t,2}\leq\min\\{c_{t},n_{t,2}\\},$

$0\leq c_{1}-k_{1,1}-k_{1,2}\leq n_{1,0},\dots,0\leq c_{t}-k_{t,1}-k_{t,2}\leq
n_{t,0}\bigr{\\}}$ ;

${\cal C}=\\{\\}$ ;

for  _$(k_{1,1},\dots,k_{t,1},k_{1,2},\dots,k_{t,2})\in T$_ do

$A_{1}=-m+2\cdot\sum_{i=1}^{t}s_{i}\cdot k_{i,1}$ ;

$A_{2}=-m+2\cdot\sum_{i=1}^{t}s_{i}\cdot k_{i,2}$ ;

$A_{3}=-m+2\cdot\sum_{i=1}^{t}s_{i}\cdot(c_{i}-k_{i,1}-k_{i,2})$ ;

$P=A_{1}^{2}+A_{2}^{2}+A_{3}^{2}-A_{1}A_{2}-A_{1}A_{3}-A_{2}A_{3}$ ;

${\cal C}={\cal C}\cup\\{P\\}$ ;

end for

Output: the set ${\cal C}$ of potential values for $\widehat{A}_{m}$ that are
compatible with the choice of $c_{1},\dots,c_{t}$ orbits of $H$ ;

Algorithm 2 Determination of PSD values $\widehat{A}_{m}$ compatible with the
$H$ orbits

######  Example 2.

Continuing Example 1 for $\ell=117$, we apply Algorithm 2 in order to show
that $\bigl{[}\widehat{A}_{39},\widehat{B}_{39}\bigr{]}=[112,124]$ cannot
appear when we employ the subgroup $H_{1}=\\{1,16,22\\}$ for conducting a
search with the orbits method. The subgroup $H_{1}$ induces $2$ orbits of size
$s_{1}=1$, and $38$ orbits of size $s_{2}=3$. For such a search one may choose
$c_{1}=2$ orbits of size $1$ and $c_{2}=19$ orbits of size $3$. By looking at
the orbits (they are listed explicitly below in Section 4.1.1), we find
$n_{2,0}=12$ orbits whose elements are divisible by $3$, and similarly
$n_{2,1}=n_{2,2}=13$. Moreover, $n_{1,0}=2$ and $n_{1,1}=n_{1,2}=0$, which
eventually implies $k_{1,1}=k_{1,2}=0$. Let $k_{2,1}$ (resp. $k_{2,2}$) denote
the number of chosen $3$-orbits whose elements are $1\,(\mathrm{mod}\;3)$
(resp. $2\,(\mathrm{mod}\;3)$). Then we obtain

$A_{1}=6\cdot k_{2,1}-39,\quad A_{2}=6\cdot k_{2,2}-39,\quad A_{3}=2\cdot
2+6\cdot(19-k_{2,1}-k_{2,2})-39.$

Letting $k_{2,1}$ and $k_{2,2}$ range over all admissible values, i.e.,

$0\leq k_{2,1}\leq 13\;\land\;0\leq k_{2,2}\leq 13\;\land\;0\leq
19-k_{2,1}-k_{2,2}\leq 12,$

we get all possible values for $A_{1},A_{2},A_{3}$ and determine the potential
values

$\widehat{A}_{39}=\operatorname{PSD}(A,39)=A_{1}^{2}+A_{2}^{2}+A_{3}^{2}-A_{1}A_{2}-A_{1}A_{3}-A_{2}A_{3}.$

to be

$28,\,64,\,100,\,172,\,208,\,244,\,316,\,388,\,496,\dots,4132,\,4348,\,4564.$

This list excludes the possibility of finding a Legendre pair with
$\bigl{[}\widehat{A}_{39},\widehat{B}_{39}\bigr{]}=[112,124]$. Note that this
result does not change if we set $c_{1}=1$ and $c_{2}=19$ (a situation where
the chosen orbits indicate the positions of the $-1$’s).

##  3 Compression and constant-PAF sequences

The term “constant-PAF sequences” is taken to mean sequences all of whose PAF
values are equal to the same constant. We refer the reader to [2] for the
definition and properties of compression of Legendre pairs. It has been
observed experimentally in the current paper, as well as in [10], that some
Legendre pairs of composite length $\ell=n\cdot m$ have the properties that:

  * •

their $m$-compression is made up from two constant-PAF sequences of length $n$

  * •

some of the PSD values of the resulting Legendre pairs of length $\ell$ are
integers.

In this section, we prove a proposition that elucidates the connection between
these two aforementioned facts.

######  Proposition 1.

Let $A=[a_{1},\ldots,a_{\ell}]$ and $B=[b_{1},\ldots,b_{\ell}]$ be a Legendre
pair of composite length $\ell=n\cdot m$. Let
$\mathcal{A}=[A_{1},\ldots,A_{n}]$, $\mathcal{B}=[B_{1},\ldots,B_{n}]$, where

$A_{j}=\sum_{i=0}^{m-1}a_{ni+j}\quad\text{and}\quad
B_{j}=\sum_{i=0}^{m-1}b_{ni+j}$

for $j=1,\ldots,n$, i.e. $(\mathcal{A},\mathcal{B})$ is the $m$-compression of
$(A,B)$.
If the $m$-compression of $(A,B)$ is made up from two constant-PAF sequences
of length $n$:

$\operatorname{PAF}(\mathcal{A},1)=\operatorname{PAF}(\mathcal{A},2)=\cdots=\operatorname{PAF}(\mathcal{A},\frac{n-1}{2})$
$\operatorname{PAF}(\mathcal{B},1)=\operatorname{PAF}(\mathcal{B},2)=\cdots=\operatorname{PAF}(\mathcal{B},\frac{n-1}{2})$

(where
$\operatorname{PAF}(\mathcal{A},1)+\operatorname{PAF}(\mathcal{B},1)=(-2)\cdot
m$), then the PSD values at integer multiples of $m$ of $A$ and $B$ are
integers, with the explicit evaluations

$\operatorname{PSD}(A,m\cdot
s)=p_{2}(\mathcal{A})-\operatorname{PAF}(\mathcal{A},1),\quad
s=1,2,\ldots,\frac{n-1}{2}$ $\operatorname{PSD}(B,m\cdot
s)=p_{2}(\mathcal{B})-\operatorname{PAF}(\mathcal{B},1),\quad
s=1,2,\ldots,\frac{n-1}{2}$

(where $\operatorname{PSD}(A,m\cdot s)+\operatorname{PSD}(B,m\cdot
s)=2\cdot\ell+2$).

###### Proof.

We use the fact that the PSD remains invariant under $m$-compression, see [2].
We also use the Wiener-Khinchin theorem, see [3], that states that the PSD of
a sequence is equal to the DFT of its periodic autocorrelation function. We
also use the fact that certain sums of roots of unity vanish identically. For
every $s=1,2,\ldots,(n-1)/2$ and $\omega$ the primitive $n$-th root of unity
we have:

$\begin{array}[]{lcl}\operatorname{PSD}(A,m\cdot
s)&=&\operatorname{PSD}(\mathcal{A},s)\\\
&=&\displaystyle\sum_{j=0}^{n-1}\operatorname{PAF}(\mathcal{A},j)\,\omega^{js}\\\
&=&\operatorname{PAF}(\mathcal{A},0)+\operatorname{PAF}(\mathcal{A},1)\left(\displaystyle\sum_{j=1}^{n-1}\omega^{js}\right)\\\
&=&p_{2}(\mathcal{A})-\operatorname{PAF}(\mathcal{A},1).\end{array}$

The assertion $\operatorname{PSD}(B,m\cdot
s)=p_{2}(\mathcal{B})-\operatorname{PAF}(\mathcal{B},1)$ is proved in a
completely analogous manner. ∎

We remark that the roles of $n$ and $m$ in Proposition 1 are not
interchangeable. Proposition 1 will be illustrated in the next section.

##  4 Computational results

We have implemented the systematic traversal of the search space in the C
language, gaining (not surprisingly) a considerable speed-up compared to our
prototype implementations in Maple and Mathematica. For each sequence $A$ in
the search space, we first apply Lemma 1 (provided that $\ell\equiv
0\,\,(\mathrm{mod}\;3)$), by computing the sums $A_{1},A_{2},A_{3}$ and then
$\operatorname{PSD}(A,{\ell}/{3})$ in exact arithmetic. If a sequence passes
this test (or if $\ell\not\equiv 0\,\,(\mathrm{mod}\;3)$), our program
continues with the full PSD test, i.e., it checks whether
$\operatorname{PSD}(A,k)\leq 2\ell+2$ for all $1\leq k\leq(\ell-1)/2$ (note
that we can exploit early termination here). The DFT is computed in floating
point arithmetic using double precision. For each sequence passing this second
test, we write the two sequences
$\bigl{(}\operatorname{PSD}(A,k)\bigr{)}_{k\in I}$ and
$\bigl{(}2\ell+2-\operatorname{PSD}(A,k)\bigr{)}_{k\in I}$ with
$I=\\{1,\dots,(\ell-1)/2\\}\setminus\\{{\ell}/{3}\\}$ into an output file.
Since the PSD values are floating point numbers, we convert them to integers
and, in order to save disk space, hash them modulo 16. The results are then
saved as hexadecimal strings of length $|I|$. A Legendre pair corresponds to
two lines in the output file whose two strings match pairwise (but in reverse
order). Due to the hashing there is the possibility to find matches which do
not correspond to Legendre pairs, but the probability that this happens is
negligible and such false candidates can easily be sorted out in a post-
processing step.

All times were measured on RICAM’s computing cluster radon1, which has 1168
Xeon E5-2630v3 (2.4Ghz) threads. For the reported computations, we employed a
moderate parallelization, typically using 16 threads for one task. Since the
parallelization is done by splitting the search space into pieces, it scales
very well. The reported times are given in CPU hours, i.e., as the sum of the
times of each thread.

###  4.1 Legendre pairs of length $117$

We executed Algorithm 1 for Legendre pairs of length $\ell=117=3\cdot 39$ and
obtained

$\bigl{[}\operatorname{PSD}(A,39),\operatorname{PSD}(B,39)\bigr{]}\in\bigl{\\{}[28,208],[64,172],[112,124]\bigr{\\}},$

as in Example 1. There are four subgroups of order 3 in
$\mathbb{Z}_{117}^{\star}$

$H_{1}=\\{1,16,22\\},\quad H_{2}=\\{1,40,79\\},\quad
H_{3}=\\{1,55,100\\},\quad H_{4}=\\{1,61,94\\}.$

In the following subsections we investigate these subgroups separately, by
considering only sequences whose multiplier group contains the respective
subgroup.

####  4.1.1 Legendre pairs of length $117$ via $H_{1}$

The subgroup $H_{1}=\\{1,16,22\\}$ of order 3 of $\mathbb{Z}_{117}^{\star}$
acts on $\mathbb{Z}_{117}$ and yields $38$ orbits of size $3$ and $2$ orbits
of size $1$. We list the $38+2$ orbits of the action of $H_{1}=\\{1,16,22\\}$
on $\mathbb{Z}_{117}$ as follows:

$\begin{array}[]{l@{\qquad}l@{\qquad}l}H_{1}\cdot 1=\\{1,16,22\\},&H_{1}\cdot
2=\\{2,32,44\\},&H_{1}\cdot 3=\\{3,48,66\\},\\\ H_{1}\cdot
4=\\{4,64,88\\},&H_{1}\cdot 5=\\{5,80,110\\},&H_{1}\cdot 6=\\{6,15,96\\},\\\
H_{1}\cdot 7=\\{7,37,112\\},&H_{1}\cdot 8=\\{8,11,59\\},&H_{1}\cdot
9=\\{9,27,81\\},\\\ H_{1}\cdot 10=\\{10,43,103\\},&H_{1}\cdot
12=\\{12,30,75\\},&H_{1}\cdot 13=\\{13,52,91\\},\\\ H_{1}\cdot
14=\\{14,74,107\\},&H_{1}\cdot 17=\\{17,23,38\\},&H_{1}\cdot
18=\\{18,45,54\\},\\\ H_{1}\cdot 19=\\{19,67,70\\},&H_{1}\cdot
20=\\{20,86,89\\},&H_{1}\cdot 21=\\{21,102,111\\},\\\ H_{1}\cdot
24=\\{24,33,60\\},&H_{1}\cdot 25=\\{25,49,82\\},&H_{1}\cdot
26=\\{26,65,104\\},\\\ H_{1}\cdot 28=\\{28,31,97\\},&H_{1}\cdot
29=\\{29,53,113\\},&H_{1}\cdot 34=\\{34,46,76\\},\\\ H_{1}\cdot
35=\\{35,68,92\\},&H_{1}\cdot 36=\\{36,90,108\\},&H_{1}\cdot
40=\\{40,55,61\\},\\\ H_{1}\cdot 41=\\{41,71,83\\},&H_{1}\cdot
42=\\{42,87,105\\},&H_{1}\cdot 47=\\{47,50,98\\},\\\ H_{1}\cdot
51=\\{51,69,114\\},&H_{1}\cdot 56=\\{56,62,77\\},&H_{1}\cdot
57=\\{57,84,93\\},\\\ H_{1}\cdot 58=\\{58,106,109\\},&H_{1}\cdot
63=\\{63,72,99\\},&H_{1}\cdot 73=\\{73,85,115\\},\\\ H_{1}\cdot
79=\\{79,94,100\\},&H_{1}\cdot 95=\\{95,101,116\\},&\\\ H_{1}\cdot
39=\\{39\\},&H_{1}\cdot 78=\\{78\\}.&\end{array}$

Subsequently, we distinguish two cases:

  * •

Case (I): make use of $2$ orbits of size $1$ and $19$ orbits of size $3$, to
make a subset of size $2\cdot 1+19\cdot 3=59=(117+1)/{2}$. The search space is
of size: $\binom{2}{2}\cdot\binom{38}{19}=35{,}345{,}263{,}800$.

  * •

Case (II): make use of $1$ orbit of size $1$ and $19$ orbits of size $3$, to
make a subset of size $1\cdot 1+19\cdot 3=58=(117-1)/{2}$. The search space is
of size: $\binom{2}{1}\cdot\binom{38}{19}=70{,}690{,}527{,}600$. In order to
have sequences whose entries sum up to $1$, these orbits have to encode the
positions of the $-1$’s.

For case (I), we conducted an exhaustive search for Legendre pairs of order
$117$ using the subgroup $\\{1,16,22\\}$ in 31 CPU hours. The search yielded
$69{,}735{,}984$ candidate sequences passing the PSD test, among them 192
Legendre pairs of lengths $117$ were found. These pairs occur in 48 four-
cycles (bipartite complete graphs $K_{2,2}$): by a four-cycle we mean four
sequences $A,B,C,D$ forming four Legendre pairs $(A,B)$, $(B,C)$, $(C,D)$, and
$(D,A)$. However, these 192 Legendre pairs contain some redundancy due to
symmetries. Denote by $\sigma$ the cyclic (forward) shift and by $\rho$ the
reverting of a sequence, and assume that $(A,B)$ is a Legendre pair. Then also
$\bigl{(}A,\rho^{i}(\sigma^{j}(B))\bigr{)}$ is a Legendre pair for any choice
of $i$ and $j$, because the sequence of PAF values is invariant under shifting
and reverting, i.e.,
$\operatorname{PAF}(B,s)=\operatorname{PAF}(\rho^{i}(\sigma^{j}(B)),s)$ for
any $s$. Note that most of these pairs will not be found during this
exhaustive search, because they are not compatible with the imposed orbit
structure. The only operation that is compatible is $A\mapsto\rho(\sigma(A))$,
because the set of orbits is invariant under $i\mapsto\ell-i$. Thus, we can
design four Legendre pairs from the four sequences

$A,\quad\rho(\sigma(A)),\quad B,\quad\rho(\sigma(B)).$

Ten out of the $192$ Legendre pairs are given below in the form
$(A_{k},B_{k}),k=1,\ldots,10$. Moreover, all 10 Legendre pairs of length $117$
shown below, have $117/3=39$-th PSD values equal to $[64,172]$. Among the
remaining Legendre pairs of length $117$, some also have $117/3=39$-th PSD
values equal to $[28,208]$. Algorithm 2 explains why there are no pairs with
$[112,124]$, see Example 2. Taking advantage of this property computationally,
results in significant gains in CPU time, because we first use this property
as a fast filtering mechanism (using exact arithmetic), before applying the
computationally expensive full PSD test (using floating-point arithmetic). We
also used the PSD constancy property over the orbits, see [2], in order to
compute solely one PSD value per orbit.

In the following list, each Legendre pair $(A,B)$ is given by two index sets
$I_{A}$ and $I_{B}$. The positions $k$ where the sequence $A$ equals $1$,
i.e., $a_{k}=1$, are given by $\bigcup_{i\in I_{A}}H_{1}\cdot i$, and the
sequence $A$ equals $-1$ at all other positions. Analogously, the index set
$I_{B}$ encodes the $\\{-1,+1\\}$-sequence $B$.

  1. 1.

$I_{A_{1}}=\\{1,3,4,7,8,13,14,17,19,24,28,29,36,39,40,47,51,56,63,78,95\\}$
$I_{B_{1}}=\\{2,5,7,9,13,14,18,19,20,24,34,36,39,40,42,47,56,58,73,78,79\\}$

  2. 2.

$I_{A_{2}}=\\{1,4,8,10,12,18,20,29,34,35,36,39,40,47,56,57,58,63,73,78,95\\}$
$I_{B_{2}}=\\{3,5,6,7,8,9,10,12,13,14,18,19,20,26,28,39,40,41,47,56,78\\}$

  3. 3.

$I_{A_{3}}=\\{1,2,4,6,7,8,10,14,18,29,34,36,39,47,51,56,63,73,78,79,95\\}$
$I_{B_{3}}=\\{2,3,5,7,10,12,13,14,20,24,26,28,34,36,39,40,41,47,56,63,78\\}$

  4. 4.

$I_{A_{4}}=\\{2,3,6,7,9,19,21,26,29,34,39,40,41,47,56,58,63,73,78,79,95\\}$
$I_{B_{4}}=\\{1,2,3,4,5,14,17,18,25,26,29,35,36,39,40,56,57,58,63,73,78\\}$

  5. 5.

$I_{A_{5}}=\\{2,3,9,10,17,18,19,20,25,34,36,39,41,47,56,57,58,73,78,79,95\\}$
$I_{B_{5}}=\\{1,2,4,8,9,13,14,17,21,26,29,39,40,42,56,57,58,63,73,78,95\\}$

  6. 6.

$I_{A_{6}}=\\{1,2,4,5,6,8,13,17,18,19,21,34,36,39,40,41,47,51,56,73,78\\}$
$I_{B_{6}}=\\{2,4,7,8,9,10,13,18,24,25,29,35,39,40,51,56,63,73,78,79,95\\}$

  7. 7.

$I_{A_{7}}=\\{2,5,6,7,8,10,13,17,18,20,21,36,39,40,41,51,58,73,78,79,95\\}$
$I_{B_{7}}=\\{3,4,5,7,10,14,17,18,26,28,29,35,36,39,40,41,57,63,78,79,95\\}$

  8. 8.

$I_{A_{8}}=\\{3,4,5,7,8,18,21,24,25,28,29,34,39,40,41,42,47,56,73,78,95\\}$
$I_{B_{8}}=\\{3,9,14,17,19,21,25,28,29,34,35,39,40,47,51,57,58,73,78,79,95\\}$

  9. 9.

$I_{A_{9}}=\\{1,2,4,6,7,9,10,12,13,14,18,28,29,34,35,39,41,42,56,78,95\\}$
$I_{B_{9}}=\\{5,6,8,9,10,13,14,19,20,25,28,34,36,39,41,51,56,58,63,73,78\\}$

  10. 10.

$I_{A_{10}}=\\{1,2,5,7,8,9,19,20,24,29,35,36,39,40,51,58,63,73,78,79,95\\}$
$I_{B_{10}}=\\{5,7,9,10,13,14,17,20,21,26,28,35,39,40,42,56,57,63,78,79,95\\}$

We also list the above 10 Legendre pairs of pairs length $117$ in a more
succinct manner, using the lexicographic ranks of the subsets encoding the
positions of $+1^{\prime}s$:

$\begin{array}[]{ll}(10327421105,25363140085),&(15300082821,29082145926),\\\
(5172847060,20669267508),&(21265971921,810444739),\\\
(22124932714,6023154169),&(4370665803,24003646556),\\\
(24634133277,27568254144),&(27457918899,31248697558),\\\
(5218049000,33814036464),&(6896605532,34222709639).\\\ \end{array}$

More specifically, these are the $19$-element subsets of $\\{1,\ldots,38\\}$,
ranked lexicographically from $0$ to
$\binom{38}{19}-1=35{,}345{,}263{,}800-1$. See [5] for ranking and unranking
algorithms for $k$-element subsets and other useful combinatorial structures.
For example, the integer $10327421105$ encodes the subset

$\\{1,3,4,7,8,12,13,14,16,19,22,23,26,27,30,31,32,35,38\\}\subset\\{1,\dots,38\\},$

which corresponds to $I_{A_{1}}$ (using the order of the orbits as displayed
above).

For case (II), we conducted an exhaustive search for Legendre pairs of order
$117$ using the subgroup $\\{1,16,22\\}$. The search yielded $139{,}471{,}968$
candidate sequences passing the PSD test, among them $768$ Legendre pairs of
lengths $117$ were found. These $768$ Legendre pairs occur in $48$ $K_{4,4}$
bipartite graphs. Similar to case (I), we can explain this phenomenon via the
underlying symmetries.

Recall the notations $\sigma$ and $\rho$ for the cyclic shift and reverting of
a sequence. In case (I) we chose both $1$-orbits, and therefore all sequences
$A$ in the search space satisfied $A_{39}=A_{78}=1$ and $A_{117}=-1$. In
contrast, we choose in case (II) only one $1$-orbit and hence the sequences in
the search space have $(A_{39},A_{78},A_{117})$ equal to $(-1,1,1)$ or
$(1,-1,1)$. A sequence of the first type ($A_{39}=-1$) can be mapped to one of
the second type ($A_{78}=-1$) by $\sigma^{39}$, notably without leaving the
search space, because the set of orbits is invariant under $i\mapsto
i+39\;(\mathrm{mod}\;117)$. Hence one finds the following four sequences with
identical PAF values in the search space of case (II):

$A,\quad\sigma^{39}(A),\quad\rho(\sigma(A)),\quad\rho(\sigma^{40}(A)).$

Combining any of these four sequences with any of the four sequences with
complementary PAF sequence forms a Legendre pair. This explains the occurrence
of $K_{4,4}$ bipartite graphs.

Also note that for any sequence $A$ with $A_{39}=-1$ in case (II), we find the
sequence $\sigma^{-39}(A)$ in the search space of case (I). Ignoring the
symmetries, i.e., picking one representative from each class, yields $48$
Legendre pairs which are non-equivalent under shifting and reverting.

####  4.1.2 Legendre pairs of length $117$ via $H_{2}$

The subgroup $H_{2}=\\{1,40,79\\}$ of order 3 of $\mathbb{Z}_{117}^{\star}$
acts on $\mathbb{Z}_{117}$ and yields $38$ size 1 orbits and $26$ size 3
orbits, which gives a lot of possible combinations to build subsets of size
$58$ (or $59$). We have not been able to construct Legendre pairs of length
$117$ using $H_{2}$, possibly because we did not implement an exhaustive
search in this case.

####  4.1.3 Legendre pairs of length $117$ via $H_{3}$

The subgroup $H_{3}=\\{1,55,100\\}$ of order 3 of $\mathbb{Z}_{117}^{\star}$
acts on $\mathbb{Z}_{117}$ and yields $8$ size 1 orbits and $36$ size 3
orbits, which gives $3$ possible combinations to build subsets of size $59$:

  * (a)

$8\cdot 1+17\cdot 3=59$ with search space of size $8{,}597{,}496{,}600$ (2.7
CPU hours); there are $2{,}812{,}308$ sequences passing the PSD test.

  * (b)

$5\cdot 1+18\cdot 3=59$ with search space of size $508{,}207{,}576{,}800$ (95
CPU hours); there are $50{,}685{,}120$ sequences passing the PSD test.

  * (c)

$2\cdot 1+19\cdot 3=59$ with search space of size $240{,}729{,}904{,}800$ (49
CPU hours); there are $36{,}699{,}600$ sequences passing the PSD test.

In addition, there are also $3$ possible combinations to build blocks of size
$58$:

  * (d)

$7\cdot 1+17\cdot 3=58$ with search space of size $68{,}779{,}972{,}800$ (13.5
CPU hours); there are $10{,}485{,}600$ sequences passing the PSD test.

  * (e)

$4\cdot 1+18\cdot 3=58$ with search space of size $635{,}259{,}471{,}000$ (119
CPU hours); there are $63{,}356{,}400$ sequences passing the PSD test.

  * (f)

$1\cdot 1+19\cdot 3=58$ with search space of size $68{,}779{,}972{,}800$ (22
CPU hours); there are $22{,}498{,}464$ sequences passing the PSD test.

No Legendre pair of length $117$ whose multiplier group contains $H_{3}$
exists.

####  4.1.4 Legendre pairs of length $117$ via $H_{4}$

The subgroup $H_{4}=\\{1,61,94\\}$ of order 3 of $\mathbb{Z}_{117}^{\star}$
acts on $\mathbb{Z}_{117}$ and yields a search space of size:
$\binom{2}{2}\cdot\binom{38}{19}=35{,}345{,}263{,}800$, because there are $38$
orbits of size $3$ and $2$ orbits of size $1$, and we need $19$ orbits of size
$3$ and $2$ orbits of size $1$ to make a subset of size $19\cdot 3+2\cdot
1=59=(117+1)/{2}$. We found $240$ Legendre pairs of length $117$ via an
exhaustive search. Some of them are shown below in LexRank form:

$\begin{array}[]{@{}lll@{}}(8221110983,12044164377),&(12702071296,15372978390),&(23944768832,15178414396),\\\
(20338660993,90051589),&(7146518669,23738703053),&(3073133857,30770050335),\\\
(32540516078,3097218289),&(33749219312,4797783684),&(5422010999,7269176966).\end{array}$

Among the $240$ pairs, there are $144$ pairs with
$[\operatorname{PSD}(A,39),\operatorname{PSD}(B,39)]$ equal to $[64,172]$ and
$96$ pairs with $[\operatorname{PSD}(A,39),\operatorname{PSD}(B,39)]$ equal to
$[28,208]$.

A search with block size $58$ delivered $960$ Legendre pairs of length $117$.
Analogous to subgroup $H_{1}$, any of these pairs can be obtained from others
by shifting and reverting one or both sequences. Hence, we can extract $60$
Legendre pairs using $H_{4}$ which are non-equivalent under shifting and
reverting.

###  4.2 Legendre pairs of length $129$

We executed Algorithm 1 for Legendre pairs of length $\ell=129=3\cdot 43$ and
obtained that the spectrum of possible pairs of values for
$\operatorname{PSD}(A,43)$ and $\operatorname{PSD}(B,43)$ is made up of only 5
pairs:

$\bigl{[}\operatorname{PSD}(A,43),\operatorname{PSD}(B,43)\bigr{]}\in\bigl{\\{}[4,256],[16,244],[52,208],[64,196],[112,148]\bigr{\\}}.$

There is one subgroup of order 3 in $\mathbb{Z}_{129}^{\star}$

$H=\\{1,49,79\\}$

acting on $\mathbb{Z}_{129}$ and yielding a search space of size
$\binom{2}{2}\cdot\binom{42}{21}=538{,}257{,}874{,}440$. Since there are $42$
orbits of size $3$ and $2$ orbits of size $1$, we need $21$ orbits of size $3$
and $2$ orbits of size $1$, to make a subset of size $21\cdot 3+2\cdot
1=65=(129+1)/{2}$. The $42+2$ orbits of the action of $H=\\{1,49,79\\}$ on
$\mathbb{Z}_{129}$ are

$\begin{array}[]{l@{\qquad}l@{\qquad}l}H\cdot 1=\\{1,49,79\\},&H\cdot
2=\\{2,29,98\\},&H\cdot 3=\\{3,18,108\\},\\\ H\cdot 4=\\{4,58,67\\},&H\cdot
5=\\{5,8,116\\},&H\cdot 6=\\{6,36,87\\},\\\ H\cdot 7=\\{7,37,85\\},&H\cdot
9=\\{9,54,66\\},&H\cdot 10=\\{10,16,103\\},\\\ H\cdot
11=\\{11,23,95\\},&H\cdot 12=\\{12,45,72\\},&H\cdot 13=\\{13,121,124\\},\\\
H\cdot 14=\\{14,41,74\\},&H\cdot 15=\\{15,24,90\\},&H\cdot
17=\\{17,53,59\\},\\\ H\cdot 19=\\{19,28,82\\},&H\cdot
20=\\{20,32,77\\},&H\cdot 21=\\{21,111,126\\},\\\ H\cdot
22=\\{22,46,61\\},&H\cdot 25=\\{25,40,64\\},&H\cdot 26=\\{26,113,119\\},\\\
H\cdot 27=\\{27,33,69\\},&H\cdot 30=\\{30,48,51\\},&H\cdot
31=\\{31,100,127\\},\\\ H\cdot 34=\\{34,106,118\\},&H\cdot
35=\\{35,38,56\\},&H\cdot 39=\\{39,105,114\\},\\\ H\cdot
42=\\{42,93,123\\},&H\cdot 44=\\{44,92,122\\},&H\cdot 47=\\{47,101,110\\},\\\
H\cdot 50=\\{50,80,128\\},&H\cdot 52=\\{52,97,109\\},&H\cdot
55=\\{55,88,115\\},\\\ H\cdot 57=\\{57,84,117\\},&H\cdot
60=\\{60,96,102\\},&H\cdot 62=\\{62,71,125\\},\\\ H\cdot
63=\\{63,75,120\\},&H\cdot 65=\\{65,89,104\\},&H\cdot 68=\\{68,83,107\\},\\\
H\cdot 70=\\{70,76,112\\},&H\cdot 73=\\{73,91,94\\},&H\cdot
78=\\{78,81,99\\},\\\ H\cdot 43=\\{43\\},&H\cdot 86=\\{86\\}.&\end{array}$

We conducted an exhaustive search for Legendre pairs of order $129$ using the
subgroup $H=\\{1,49,79\\}$ in 431 CPU hours. The search was done in parallel
on 16 threads and yielded output files of total size 80 gigabytes, containing
more than $460$ million sequences which passed the PSD test; among them 112
Legendre pairs of length $129$ were found. Analogous to $\ell=117$, this list
can be condensed to $28$ pairs, where the remaining ones are obtained by
symmetry.

Here are two Legendre pairs of length $129$, given by index sets
$I_{A},I_{B}$:

  1. 1.

$I_{A}=\\{1,2,5,13,17,19,21,22,25,26,27,34,39,43,50,55,60,62,63,68,73,78,86\\}$
$I_{B}=\\{1,3,11,12,13,17,21,26,31,34,35,42,43,47,50,52,57,60,62,68,70,78,86\\}$

  2. 2.

$I_{A}=\\{1,2,5,13,17,19,21,22,25,26,27,34,39,43,50,55,60,62,63,68,73,78,86\\}$
$I_{B}=\\{1,2,3,4,5,6,10,11,12,17,19,20,21,22,27,30,34,43,50,57,70,73,86\\}$

Both the above Legendre pairs of length $129$ have
$\bigl{[}\widehat{A}_{43},\widehat{B}_{43}\bigr{]}=[148,112]$. In fact, all
the 112 Legendre pairs of length $129$ that we found have this property. This
is partly explained by applying Algorithm 2, where

$4,\,76,\,112,\,148,\,256,\,292,\,364,\,400,\dots$

are returned as potential values for $\widehat{A}_{43}$ and
$\widehat{B}_{43}$, leaving only two possible pairs, namely $[4,256]$ and
$[112,148]$.

###  4.3 Legendre pairs of length $147$

We executed Algorithm 1 for Legendre pairs of length $\ell=147=3\cdot 49$ and
obtained that the spectrum of possible pairs of values for
$\operatorname{PSD}(A,49)$ and $\operatorname{PSD}(B,49)$ is made up of only 6
pairs

$\bigl{[}\operatorname{PSD}(A,49),\operatorname{PSD}(B,49)\bigr{]}\in\bigl{\\{}[4,292],[28,268],[52,244],[100,196],[124,172],[148,148]\bigr{\\}}.$

Algorithm 2 further shows that in fact only two of the above six pairs (namely
the first and the last one) are compatible with the particular orbit structure
induced by the subgroup $H$ of order $3$ in $\mathbb{Z}_{147}^{\star}$

$H=\\{1,67,79\\}$

acting on $\mathbb{Z}_{147}$. This information prevents us from conducting
redundant computations and helps us target the search more narrowly. The $50$
orbits of the action of $H=\\{1,67,79\\}$ on $\mathbb{Z}_{147}$ are

$\begin{array}[]{l@{\qquad}l@{\qquad}l}H\cdot 1=\\{1,67,79\\},&H\cdot
2=\\{2,11,134\\},&H\cdot 3=\\{3,54,90\\},\\\ H\cdot 4=\\{4,22,121\\},&H\cdot
5=\\{5,41,101\\},&H\cdot 6=\\{6,33,108\\},\\\ H\cdot 7=\\{7,28,112\\},&H\cdot
8=\\{8,44,95\\},&H\cdot 9=\\{9,15,123\\},\\\ H\cdot 10=\\{10,55,82\\},&H\cdot
12=\\{12,66,69\\},&H\cdot 13=\\{13,136,145\\},\\\ H\cdot
14=\\{14,56,77\\},&H\cdot 16=\\{16,43,88\\},&H\cdot 17=\\{17,20,110\\},\\\
H\cdot 18=\\{18,30,99\\},&H\cdot 19=\\{19,31,97\\},&H\cdot
21=\\{21,42,84\\},\\\ H\cdot 23=\\{23,53,71\\},&H\cdot
24=\\{24,132,138\\},&H\cdot 25=\\{25,58,64\\},\\\ H\cdot
26=\\{26,125,143\\},&H\cdot 27=\\{27,45,75\\},&H\cdot 29=\\{29,32,86\\},\\\
H\cdot 34=\\{34,40,73\\},&H\cdot 35=\\{35,119,140\\},&H\cdot
36=\\{36,51,60\\},\\\ H\cdot 37=\\{37,127,130\\},&H\cdot
38=\\{38,47,62\\},&H\cdot 39=\\{39,114,141\\},\\\ H\cdot
46=\\{46,106,142\\},&H\cdot 48=\\{48,117,129\\},&H\cdot 49=\\{49\\},\\\ H\cdot
50=\\{50,116,128\\},&H\cdot 52=\\{52,103,139\\},&H\cdot 57=\\{57,93,144\\},\\\
H\cdot 59=\\{59,104,131\\},&H\cdot 61=\\{61,115,118\\},&H\cdot
63=\\{63,105,126\\},\\\ H\cdot 65=\\{65,92,137\\},&H\cdot
68=\\{68,80,146\\},&H\cdot 70=\\{70,91,133\\}\\\ H\cdot
72=\\{72,102,120\\},&H\cdot 74=\\{74,107,113\\},&H\cdot 76=\\{76,94,124\\},\\\
H\cdot 78=\\{78,81,135\\},&H\cdot 83=\\{83,89,122\\},&H\cdot
85=\\{85,100,109\\},\\\ H\cdot 87=\\{87,96,111\\},&H\cdot 98=\\{98\\}.&\\\
\end{array}$

Here is a Legendre pair $(A,B)$ of length $\ell=147$, given by two index sets
$I_{A}$ and $I_{B}$. The positions $k$ where the sequence $A$ equals $1$,
i.e., $a_{k}=1$, are given by $\bigcup_{i\in I_{A}}H\cdot i$, and the sequence
$A$ equals $-1$ at all other positions. Analogously, the index set $I_{B}$
encodes the $\\{-1,+1\\}$-sequence $B$:

$\displaystyle I_{A}$
$\displaystyle=\\{1,2,3,5,7,8,10,14,16,17,19,21,27,35,38,39,49,52,57,61,70,72,74,83,87,98\\},$
$\displaystyle I_{B}$
$\displaystyle=\\{1,2,6,7,9,10,12,16,17,19,23,24,26,35,39,46,48,49,50,59,65,68,70,78,85,98\\}.$

The LexRank encoding of the Legendre pair $(A,B)$ of length $\ell=147$ is

$(2279447240326,6981583007090).$

This Legendre pair $(A,B)$ of length $\ell=147$ has
$\bigl{[}\widehat{A}_{49}$, $\widehat{B}_{49}\bigr{]}=[148,148]$, the second
pair of values predicted by Algorithms 1 and 2.

We also give three Legendre pairs of length $\ell=147$ with
$\bigl{[}\widehat{A}_{49}$, $\widehat{B}_{49}\bigr{]}=[4,292]$, the first pair
of values predicted by Algorithms 1 and 2:

  1. 1.

$(1685512212865,3612702197526)$,

  2. 2.

$(2926263388957,265692014998)$,

  3. 3.

$(4357037511235,3728601853735)$.

We remark that the combination of Algorithms 1 and 2 was of critical
importance, in order to traverse the first portion (15%) of the huge search
space of 32 trillion elements and find the Legendre pairs of length
$\ell=147$.

###  4.4 Legendre pairs of length $133$

We used the subgroup of order $3$, $H=\\{1,11,121\\}$, acting on
$\mathbb{Z}_{133}$. This yields a search space of size
$\binom{44}{22}=2{,}104{,}098{,}963{,}720$ elements. The computation was
stopped after $20\%$ of the search space was traversed, in 707 hours of CPU
time. The output files grew to a total size of 108 gigabytes and $5$ new
Legendre pairs of length $133$ were discovered (we display their lexicographic
rank for a $22$-subset of the $44$ orbits of size $3$, but this time these
indices give the positions of the $-1$’s):

  1. 1.

$(128572618842,210086022915)$,

  2. 2.

$(17644506807,41167368128)$,

  3. 3.

$(179364459458,27235734754)$,

  4. 4.

$(213277890206,251235525902)$,

  5. 5.

$(272147218211,279717372516)$.

These five Legendre pairs can be used to make Hadamard matrices of order
$2\cdot 133+2=268$, via the two circulant core template array in [3]. The
order $268$ was the smallest open order for Hadamard matrices until 1985 [6].

These five Legendre pairs have integer PSD values at integer multiples of the
prime factor $19$ of $\ell=133$. More specifically, using the above numbering
we have

  1. 1.

$\bigl{[}\widehat{A}_{19},\widehat{B}_{19}\bigr{]}=\bigl{[}\widehat{A}_{38},\widehat{B}_{38}\bigr{]}=\bigl{[}\widehat{A}_{57},\widehat{B}_{57}\bigr{]}=[176,92]$,

  2. 2.

$\bigl{[}\widehat{A}_{19},\widehat{B}_{19}\bigr{]}=\bigl{[}\widehat{A}_{38},\widehat{B}_{38}\bigr{]}=\bigl{[}\widehat{A}_{57},\widehat{B}_{57}\bigr{]}=[92,176]$,

  3. 3.

$\bigl{[}\widehat{A}_{19},\widehat{B}_{19}\bigr{]}=\bigl{[}\widehat{A}_{38},\widehat{B}_{38}\bigr{]}=\bigl{[}\widehat{A}_{57},\widehat{B}_{57}\bigr{]}=[36,232]$,

  4. 4.

$\bigl{[}\widehat{A}_{19},\widehat{B}_{19}\bigr{]}=\bigl{[}\widehat{A}_{38},\widehat{B}_{38}\bigr{]}=\bigl{[}\widehat{A}_{57},\widehat{B}_{57}\bigr{]}=[92,176]$,

  5. 5.

$\bigl{[}\widehat{A}_{19},\widehat{B}_{19}\bigr{]}=\bigl{[}\widehat{A}_{38},\widehat{B}_{38}\bigr{]}=\bigl{[}\widehat{A}_{57},\widehat{B}_{57}\bigr{]}=[92,176]$.

Using Proposition 1 with $\ell=133,m=19,n=7$, we are able to ascertain the
cause of this property.

  * •

For the 3rd Legendre pair of length $133$ we found, using the notations of
Proposition 1 we have:

$\displaystyle\mathcal{A}$ $\displaystyle=[1,1,1,1,1,1,-5],\quad$
$\displaystyle\operatorname{PAF}(\mathcal{A},1)=\operatorname{PAF}(\mathcal{A},2)=\operatorname{PAF}(\mathcal{A},3)$
$\displaystyle=-5,$ $\displaystyle\mathcal{B}$
$\displaystyle=[-1,-1,5,-1,5,5,-11],\quad$
$\displaystyle\operatorname{PAF}(\mathcal{B},1)=\operatorname{PAF}(\mathcal{B},2)=\operatorname{PAF}(\mathcal{B},3)$
$\displaystyle=-33.$

Therefore, by applying Proposition 1, we obtain (note that
$-5-33=2\cdot(-19)$)

$\displaystyle\operatorname{PSD}(A,19)=\operatorname{PSD}(A,38)=\operatorname{PSD}(A,57)$
$\displaystyle=p_{2}(\mathcal{A})-\operatorname{PAF}(\mathcal{A},1)=31+5=36,$
$\displaystyle\operatorname{PSD}(B,19)=\operatorname{PSD}(B,38)=\operatorname{PSD}(B,57)$
$\displaystyle=p_{2}(\mathcal{B})-\operatorname{PAF}(\mathcal{B},1)=199+33=232.$

  * •

For the 5th Legendre pair of length $133$ we found, using the notations of
Proposition 1 we have:

$\displaystyle\mathcal{A}$ $\displaystyle=[1,1,-3,1,-3,-3,7],\quad$
$\displaystyle\operatorname{PAF}(\mathcal{A},1)=\operatorname{PAF}(\mathcal{A},2)=\operatorname{PAF}(\mathcal{A},3)$
$\displaystyle=-13,$ $\displaystyle\mathcal{B}$
$\displaystyle=[-5,-5,5,-5,5,5,1],\quad$
$\displaystyle\operatorname{PAF}(\mathcal{B},1)=\operatorname{PAF}(\mathcal{B},2)=\operatorname{PAF}(\mathcal{B},3)$
$\displaystyle=-25.$

Therefore, by applying Proposition 1, we obtain (note that
$-13-25=2\cdot(-19)$)

$\displaystyle\operatorname{PSD}(A,19)=\operatorname{PSD}(A,38)=\operatorname{PSD}(A,57)$
$\displaystyle=p_{2}(\mathcal{A})-\operatorname{PAF}(\mathcal{A},1)=79+13=92,$
$\displaystyle\operatorname{PSD}(B,19)=\operatorname{PSD}(B,38)=\operatorname{PSD}(B,57)$
$\displaystyle=p_{2}(\mathcal{B})-\operatorname{PAF}(\mathcal{B},1)=151+25=176.$

##  5 Conclusion

We prove a proposition that connects constant-PAF sequences and the
corresponding Legendre pairs with integer PSD values. We update the list of
open lengths for Legendre pairs, in [1]. In particular, we furnish the first
ever examples of Legendre pairs of the four open lengths $117,129,133,147$. In
the case of the three open lengths $117,129,147$, we make extensive use of two
new algorithms. Our first algorithm yields the determination of the complete
spectrum of the (resp. $39$-th, $43$-rd, $49$-th) value of the discrete
Fourier transform for Legendre pairs. In fact, our algorithm yields the
complete spectrum of the $({\ell}/{3})$-rd value of the discrete Fourier
transform for Legendre pairs of lengths $\ell\equiv 0\,\,(\mathrm{mod}\;3)$.
Our second algorithm exploits the particular orbit structure induced by
specific subgroups of their multiplier group, to disqualify certain elements
of the spectrum determined by the first algorithm. The combination of both
algorithms for Legendre pairs of lengths $\ell\equiv 0\,(\mathrm{mod}\;3)$ was
a decisive factor in discovering Legendre pairs of the three open lengths
$117,129,147$. A Legendre pair of length $\ell=77$ was reported in 2020 in
[8], see [10]. Therefore, the state-of-the-art list of twelve integers in the
range $<200$ for which the question of existence of Legendre pairs is still
unsolved is

$85,87,115,145,159,161,169,175,177,185,187,195.$

For $\ell=87$, the order-$7$ subgroup $\\{1,7,16,25,49,52,82\\}$, and both
subgroups of order $4$ (namely, $\\{1,17,28,41\\}$ and $\\{1,28,46,70\\}$) did
not yield any solutions by exhaustive search. We also tried some of the
subgroups of order $2$ (there are three of them:
$\\{1,28\\},\\{1,59\\},\\{1,86\\}$), which admit many possible combinations of
their associated subsets, some of whose search spaces being beyond our
computational resources, but without success. Therefore, even twenty years
after the fundamental paper [3] for Legendre pairs appeared, there are still
interesting questions and open problems to ponder in this area.

##### Acknowledgment

We are grateful for the detailed and pertinent referee comments that
contributed to improving our paper. In particular, one of the referees
provided a generalized version of our original Proposition 1 and a
significantly simplified version of its proof.

## References

  * [1] N. A. Balonin and D. Z. Djokovic.  Three new lengths for cyclic Legendre pairs.  https://arxiv.org/abs/2010.02829.
  * [2] D. Z. Djokovic and I. S. Kotsireas.  Compression of periodic complementary sequences and applications.  Des. Codes Cryptogr., 74(2):365–377, 2015.
  * [3] R. J. Fletcher, M. Gysin, and J. Seberry.  Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices.  Australas. J. Combin., 23:75–86, 2001.
  * [4] I. S. Kotsireas, C. Koukouvinos, and J. Seberry.  Weighing matrices and string sorting.  Ann. Comb., 13(3):305–313, 2009.
  * [5] D. L. Kreher and D. R. Stinson.  Combinatorial Algorithms. Generation, Enumeration, and Search.  CRC Press, Taylor & Francis, 1st edition, 1998.
  * [6] K. Sawade.  A Hadamard matrix of order $268$.  Graphs Combin., 1(2):185–187, 1985.
  * [7] B. Sturmfels.  Algorithms in Invariant Theory.  Texts and Monographs in Symbolic Computation. Springer-Verlag, Vienna, 1993.
  * [8] J. S. Turner.  personal communication.  Dec 7, 2020.
  * [9] J. S. Turner, D. Bulutoglu, D. Baczkowski, and A. Geyer.  Counting the decimation classes of binary vectors with relatively prime length and density.  J. of Algebraic Comb., 2021 (to appear).
  * [10] J. S. Turner, I. S. Kotsireas, D. Bulutoglu, and A. Geyer.  A Legendre pair of length 77 using complementary binary matrices with fixed marginals.  Des. Codes Cryptogr., 89(6):1321–1333, 2021.