One question on circulant $(-1,1)$-matrices Let $n > 13$ be a positive integer. Is there any $n\times n$ circulant $(-1,1)$-matrix $A$ satisfying the following property:
$$AA^T=(n-1)I+J$$
where $I$ is the $n\times n$ identity matrix and $J$ is the $n\times n$ matrix of ones.
I conjecture that the answer is no. But I can't prove it.
 A: This is a question about a sequence $a(t)\in \{\pm 1\}$ of period $n$ with 2 level periodic autocorrelations, with the nontrivial autocorrelations identically equal to 1. All these problems have a design theoretic aspect as well. For the relationship to the $\{0,1\}$ alphabet see the question here and its answer.
Here we define the periodic autocorrelation as
$$
C_a(\tau)=\sum_{t=0}^{n-1} a(t) a(t+\tau)
$$
where the shift by $\tau$ is modulo $n.$
Jungnickel and Pott have a paper on perfect and almost perfect autocorrelation sequences where related questions are discussed
here.
Edit: As @MaxAlekseyev points out, Corollary 2.5 in the Jungnickel and Pott paper actually rules out the existence of a circulant matrix as desired by the OP for lengths $13<n\le 20201.$
Maximal length sequences obtained from finite fields give rise to circulant matrices which satisfy
$$
A A^T = (n+1)I-J
$$
and they exist for $n=2^m-1,$ for all $m\geq 1.$ Thus they have
$$
C_a(\tau)=-1,\quad \forall  \tau \neq 0 \pmod n
$$
Legendre sequences (terminology used in coding and cryptography regarding sequences derived from quadratic characters, see comments to this answer) obtained from multiplicative characters exist for odd prime lengths with the same property.
Another conjecture of similar form, which also (curiously) is open for $n>13$ is the existence of a Barker sequence $a(t) \in \{\pm 1\}$ (or Barker code according to engineers) of length $n$ whose aperiodic autocorrelation
$$
C_a(\tau)=\sum_{t=0}^{n-1-\tau} a(t)a(t+\tau)
$$
satisfies
$$
|C_a(\tau)| \leq 1, \forall \tau \neq 0.
$$
This has been checked up to $n$ in the thousands. A good general reference for these problems is the chapter by Helleseth and Kumar in the Handbook of Coding Theory, Vol. 2.
