\documentclass{mc} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{235} \renewcommand\thisnumber{x} \renewcommand\thisyear {2019} \renewcommand\thismonth{xxx} \renewcommand\thisvolume{24} \renewcommand\datereceived{December 13, 2018} \renewcommand\dateaccepted{May 20, 2019} %%%%%%%% end journal info %%%%%%%%%%%%% \usepackage[displaymath,mathlines,pagewise]{lineno} %Rad zaprimljen dana: 13.12.2018. %Rad prihvacen dana: 20.05.2019. %%%%% author macros %%%%%%%%% % place your own macros HERE \def\N{\mathbb{N}} \def\R{\mathbb{R}} \def\Z{\mathbb{Z}} \def\C{\mathbb{C}} \def\Q{\mathbb{Q}} %%%%% end %%%%%%%%% %%%%%%%%% already loaded packages -- DO NOT RELOAD %%%%% % \usepackage{amssymb} % \usepackage{amsmath,amsthm} % \usepackage{latexsym} % \usepackage{amsfonts} % \usepackage{amsbsyt} % \usepackage{graphicx} %%%%%% end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} %% \begin{linenumbers} \markboth{L.\,H.\,Gallardo}{Ryser's conjecture} \title{Ryser's conjecture under eigenvalue conditions} \author[L.\,H.\,Gallardo]{Luis H. Gallardo\corrauth} \address{Department of Mathematics, University of Brest, 6 Avenue Victor Le Gorgeu, C.\,S. 93\,837, 29\,238 Brest Cedex 3, France} \email{{\tt Luis.Gallardo@univ-brest.fr} (L.\,H.\,Gallardo)} \begin{abstract} We prove the nonexistence of a circulant Hadamard matrix $H$ of order $n$, under technical conditions on the eigenvalues of $H$, when $n$ has only two odd prime divisors and in the general case. \end{abstract} \keywords{ Hadamard matrices, circulant matrices, eigenvalues, cyclotomic polynomials, congruences} \ams{11R18, 15B34, 11A24, 11A07, 11B30} \maketitle \section{Introduction} A matrix of order $n$ is a square matrix with $n$ rows. A \emph{circulant} matrix $A := {\rm{circ}}(a_1,\ldots, a_n)$ of order $n$ is a matrix of order $n$ of first row $[a_1, \ldots,a_{n}]$, in which each row after the first is obtained by a cyclic shift of its predecessor by one position. For example, the second row of $A$ is $[a_{n}, a_1,\ldots,a_{n-1}].$ A \emph{Hadamard} matrix $H$ of order $n$ is a matrix of order $n$ with entries in $\{-1,1\}$ such that $K := \frac{H}{\sqrt{n}}$ is an orthogonal matrix. A \emph{circulant Hadamard} matrix of order $n$ is a circulant matrix that is Hadamard. The $10$ known circulant Hadamard matrices are: $H_1 :={\rm{circ}}(1), H_2 := -H_1, H_3 :={\rm{circ}}(1,-1,-1,-1), H_4 := -H_3, H_5 :={\rm{circ}}(-1,1,-1,-1), H_6 := -H_5, $ $H_7 := {\rm{circ}}(-1,-1,1,-1), H_8 := -H_7, H_9 := {\rm{circ}}(-1,-1,-1,1)$, and $H_{10} := -H_9.$ If $H = {\rm{circ}}(h_1,\ldots,h_n),$ is a circulant Hadamard matrix of order $n$, then its \emph{representer} polynomial is the polynomial $R(x):=h_1+h_2x+\cdots+h_nx^{n-1}.$ Despite several deep computations (see \cite{BorMoss}) no one has been able to discover any other circulant Hadamard matrix. In $1963$, Ryser proposed (see \cite{Ryser}, \cite[p. 97]{davis}) the conjecture of the non-existence of these matrices when $n>4.$ Previous work on the conjecture includes \cite{EGR, EGRcomb, luisAMEN, luisEJC, JedwabLloyd, Leungzero, Leung, Leunguno, Mato, SchmidtSmith, Turyn}. Ryser's conjecture (there are no circulant Hadamard matrices of order$ >4$) has been studied by several different methods. The first special case done (by Brualdi \cite{brualdi} in 1965) assumed that all eigenvalues of $H := circ(h_1,\ldots,h_n)$, a circulant Hadamard matrix of order $ n>4$, were real; i.e., that $H$ is symmetric. Below, $\omega(k)$ counts the number of distinct prime divisors of the positive integer $k.$ Besides Brualdi's result, all other known results are only partial results for particular $n$'s obtained by deep methods. For example, the known case $\omega(n)= 2$ is a consequence of some results of Turyn \cite{Turyn}. More precisely, Turyn proved that if $ n >4$, then $n=4h^2$ with odd $h$ and $h$ must have more than two distinct prime factors, so that $n$ must have the following form $n= 4p_{1}^{2a_{1}} p_{2}^{2a_{2}} \cdots p_{s}^{2a_{s}}$ with $s \geq 2,$ and, say, $p_{1} < p_{2}$ two odd prime numbers. In particular, $n$ cannot be a power of $2$, $n$ cannot be a power of $3$, and $n$ cannot be a product of powers of $2$ by powers of $3$. This latter result was also reproved by Schmidt and Smith \cite{SchmidtSmith} as a special case of their more general results. Moreover, when $\omega(n)=3,$ i.e., when $n =4 p_{1}^{2a_{1}}p_{2}^{2a_{2}}$ as before with $s=2$, it is known that the odd prime divisors $p_{1},p_{2}$ of $n$ must be Wieferich's pairs, i.e, $p_{1}^{p_{2}-1} \equiv 1 \pmod{p_{2}^2}$ and $p_{2}^{p_{1}-1} \equiv 1 \pmod{p_{1}^2}$. These results allowed some computer calculations, from which the result essentially follows for increasing numerical values of $n.$ However, these methods seems to be unable to produce general proofs (say, a proof of the conjecture for an infinity of $n$'s with $\omega(n)\geq 3$). It is worth reporting that Schmidt and Leung (see, e.g., \cite{Leungzero, Leunguno}) obtained the best known results about this problem. Their approach uses sophisticated technical results about group rings, characters and cyclotomic fields. Their main results might be roughly described as: (a) results that reduce the number of cases to consider in order to prove the full conjecture, and (b) results that can be used further to practical important things as to exclude specific numerical values of $n$ as possible candidates to be the order of a possible circulant Hadamard matrix $H.$ The reason why (b) is possible is that in the above results the possible prime divisors of $n$ play an important role. The present paper is much more modest; our results are obtained by using elementary methods, and we are (unfortunately) not specialists in this subject, so that we are only able to contribute to part (a) of the above discussion. More precisely, we believe that our results in the present paper may be useful to reduce the number of cases to consider in order to advance to the proof of the full conjecture. However, our results cannot contribute to the second, more concrete and important, part (b). Besides perhaps in Lemma \ref{boundabove}, that might be an interesting more general contribution, the exact reason of the lack of results of type (b) is as follows: Condition \ref{dsmall} does not depend only on the prime divisors of $n$ , so that our first two theorems cannot contribute to (b). Moreover, our latter theorem cannot contribute to (b) since in both hypothesis in Theorem \ref{neigen} the prime divisors of $h$ are not used. We describe now our results. Our general approach is (a) to assume that a possible circulant Hadamard matrix $H$ of order $n$ exists, (b) to consider cases in which some conditions on the eigenvalues of $H$ matrix imply contradictions. The first part of our results is about the case $\omega(n)=3.$ The second part is about the general case $\omega(n) \geq 2.$ The technical condition required in the case $\omega(n)=3$ reads: \begin{condition} \label{dsmall} Let $H$ be a circulant Hadamard matrix of order $n=4p^{2a}q^{2b}$, where $p\neq q$ are odd prime numbers, and $a,b$ are positive integers. Let $R(x)$ be the representer polynomial of $H.$ One has \[ d < \varphi(n)/2, \] where $d= \deg(R(x) \pmod{\Phi_n(x)}),$ ${\Phi_n(x)}$ is the $n$-th cyclotomic polynomial and $\varphi$ is Euler's function. \end{condition} Our first result comes from known properties of the cyclotomic polynomial $\Phi_n(x)$, when $n$ has only two distinct odd prime divisors \cite{thanga}, together with a variant of our argument used in \cite{EGR}: \begin{theorem} \label{agou3} There is no circulant Hadamard matrix that satisfies Condition \ref{dsmall} when $a,b$ are large enough. Large enough means that $a,b$ satisfy \[ p^a q^b > (p+q-1) (pq) ! \exp(pq) +1. \] \end{theorem} \begin{remark} \label{boundabove} Lemma \ref{cds} that gives the crucial upper bound for the proof of Theorem \ref{agou3} does {\emph{not}} depend on Condition \ref{dsmall}; thus, besides being new, it might have an interest in itself. \end{remark} It appears that our method above cannot deal with small exponents. Thus, besides Condition \ref{dsmall}, more conditions are expected in the smallest case $a=1$ and $b=1$: \begin{theorem} \label{abeq1} There is no circulant Hadamard matrix $H$ that satisfies Condition \ref{dsmall} when $a=b=1$, provided that \begin{equation} \label{cond2} \{ R(\omega^t) : 1 \leq t \leq n,\; R(\omega^t) \not \in \R\} = \{ R(\omega^k) :1 \leq k \leq n,\;\gcd(k,n)=1\} \end{equation} if $H$ has some non-real eigenvalue. \end{theorem} We checked by a simple computation that $4$ of the $8$ circulant Hadamard $4 \times 4$ matrices, namely, $H_5, H_6,H_9$ and $H_{10}$, all satisfy Condition \eqref{cond2}.\\ More generally, for any possible $n$, not just for an $n$ with $\omega(n)=3,$ some conditions on the eigenvalues of $H$ guarantee the non-existence. \begin{theorem} \label{neigen} There is no circulant Hadamard matrix $H$ of order $n=4h^2$, where $h >1$ is an odd number, provided both conditions below hold: \begin{itemize} \item[(a)] $\mathrm{Tr}(H^2)=0,$ where $\mathrm{Tr}$ means the trace. \item[(b)] $ A := \frac{H+H^{\ast}}{2}$ is positive-semidefinite, where $H^{\ast}$ is the transpose conjugate (transpose here) of $H$. \end{itemize} \end{theorem} We checked by a computation that for $2$ of the $8$ circulant Hadamard matrices with $n=4$, namely, for $H_6$ and for $H_{10}$, both conditions on Theorem \ref{neigen} hold. The main tools necessary for the proofs are given in Section \ref{known}. The proofs of Theorem \ref{agou3}, Theorem \ref{abeq1}, and Theorem \ref{neigen} are given in Section \ref{Th1}, Section \ref{Th2}, and Section~\ref{Th3}, respectively. \section{Tools} \label{known} The following result attributed to Migotti (in 1883) in \cite{thanga} is important for our work. \begin{lemma} \label{migotti} The cyclotomic polynomial $\Phi_{mn}(x)$ has all its coefficients in $\{-1,0,1\}.$ \end{lemma} A special useful case we require is \begin{lemma} \label{cyclospecial} Let $h= p_1^{r_1} p_2^{r_1}$ be a positive integer with two distinct odd prime factors $p_1 \neq p_2.$ Then \begin{equation*} \label{cycloformula} \Phi_{4h^2}(t) =\Phi_{{p_1}{p_2}}(-t^{2{p_1}^{2{r_1}-1}{p_2}^{2{r_2} -1}}). \end{equation*} \end{lemma} Thus from Lemmas \ref{migotti} and \ref{cyclospecial} one has: \begin{lemma} \label{migottispec} The cyclotomic polynomial $\Phi_{4p^{2a} q^{2b}}(x)$ has all its coefficients in \linebreak $\{-1,0,1\}$, where $p \neq q$ are two odd prime numbers. \end{lemma} The following lemma of Agou \cite{agou, agou1} is crucial. \begin{lemma} \label{agoureste} Let $R$ be a ring with $1.$ Let $S = x^n -s_{1}x^{n-1} - \cdots -s_{n} \in R[x]$ be a polynomial of degree $n > 0.$ Let $k>0$ be a positive integer. Let $T = \sum_{j=0}^{n-1}{t_{k,j}x^j}$ be the remainder of the Euclidean division (long division) of the monomial $M=x^{k+n-1}$ by the polynomial $S$ in $R[x].$ Then for $j=0,\ldots,n-1$ one has \[ t_{k,j} = \sum_{\substack{u_{1}+2u_{2}+\cdots +nu_{n}=k+n-j-1,\\ u_{i} \geq 0,i=1,\ldots,n}} \left ({\frac{(u_{1}+\cdots+u_{n}-1)!}{u_{1}! \cdots u_{n}!}} \sum_{t=0}^{j}u_{n-t}\right ) s_{1}^{u_{1}} \cdots s_{n}^{u_{n}}. \] For $j=0$ we get \begin{equation*} \label{constante} t_{k,0} = s_n \left (\sum_{\substack{u_{1}+2u_{2}+\cdots +nu_{n}=k-1,\\ u_{i} \geq 0,i=1,\ldots,n}} {\frac{(u_{1}+\cdots+u_{n})!}{u_{1}! \cdots u_{n}!}} s_{1}^{u_{1}} \cdots s_{n}^{u_{n}}\right ) \end{equation*} if $k \geq 1$ and \begin{equation*} \label{constante0} t_{k,0} = 0 \end{equation*} if $-n+1 \leq k-1 <0$ (provided $n>1$) and assuming that $0^0=1$. \end{lemma} We proceed then to prove the following lemma that is key to the proof of Theorem~\ref{agou3}. \begin{lemma} \label{cds} Let $H$ be a circulant Hadamard matrix of order $n = 4p^{2a}q^{2b},$ where $p \neq q$ are prime numbers and $a,b$ are non-negative integers. Let $R(x)$ be the representer polynomial of $H.$ Let $S(x)$ be the remainder of the Euclidean division of $R(x)$ by the cyclotomic polynomial $\Phi_n(x).$ Let $d >0$ be a positive integer such that $d \leq \deg(S).$ Let $C(d,S)$ be the coefficient of the monomial $x^d$ that appears in $S(x).$ Then \begin{equation*} \label{upperpq} \vert C(d,S) \vert \leq 2 (p+q-1)(pq)! \exp(pq) +2. \end{equation*} \end{lemma} \begin{proof} Let \begin{equation} \label{stepl} l := n/(2pq). \end{equation} Write $\Phi_n(x) = x^{\varphi(n)} -\sum_{j=1}^{\varphi(n)} c_j x^{\varphi(n) -j}.$ By Lemma \ref{cycloformula}, $\Phi_n(x) = \Phi_{pq}(-x^l)$ so that $c_{j}=0$ for all $j$ not a multiple of $l$. More precisely, \begin{equation} \label{verange} c_{j}=0\;\text{for all}\; j \neq v l,\;\text{where}\; 0 \leq v \leq K := \varphi(p q) =(p-1)(q-1). \end{equation} Let $\omega \in \C$ be an $n$-th primitive root of $1.$ Since $\omega^{n/2} =-1$, so that $\omega^{n/2+i} = -\omega^i$ one can write $R(\omega) = r_{0}+ r_{1}\omega + \cdots +r_{n/2-1} \omega^{n/2-1}$, where each $r_{j} \in \{-2,0,2\}$ by Lemma \ref{migottispec}. Define then the \emph{reduced representer} polynomial $V(x)$ of $H$ by $V(x) := \sum_{j=0}^{n/2-1} r_{j}x^{j}.$ Clearly, $S(x)$ is also the remainder of the Euclidean division of $V(x)$ by $\Phi_n(x).$ Put $M_{k} := x^{k+\varphi(n) -1},$ for each $k \in \{1,\ldots,n/2 -\varphi(n) \}.$ Therefore, defining $V_1(x)$ by \begin{equation*} \label{VV} V(x) = r_0+ r_1 x + \cdots + r_{\varphi(n)-1} x^{\varphi(n)-1} + V_1(x) \end{equation*} one has \begin{equation*} \label{cesd} C(d,S) = r_{d}+ \sum_{k=1}^{n/2-\varphi(n)} r_{k+\varphi(n)-1} t_{k,d}, \end{equation*} where $t_{k,d}$ is the remainder of the Euclidean division of the monomial $M_k$ of $V_1(x)$ by $\Phi_n(x).$ Since $d>0$ and $K l= \varphi(n)$, from Lemma \ref{agoureste} and our discussion above (see \eqref{verange}) one has \begin{equation} \label{tekade1} t_{k,d}\! = \!\!\!\sum_{\substack{l u_{l}+2 l u_{2 l}+\cdots + K l u_{K l}=k -1 + \varphi(n) -d,\\ u_{i l} \geq 0,i=1,\ldots,K}}\!\!\!\! \left ( \!\!{\frac{(u_{l}+\cdots+u_{K l}-1)!}{u_{l}! \cdots u_{K l}!}} \sum_{t=0}^{d}u_{K l-t}\!\!\right ) \! c_{l}^{u_{l}} \cdots c_{K l}^{u_{K l}}\!. \end{equation} Define then the integer $X$ by \begin{equation} \label{lebigX} k +\varphi(n) -d -1 = l X. \end{equation} Therefore, $t_{k,d} =0$ for all other possible $k$'s for which $ k +\varphi(n) -d -1 $ is not divisible by $l.$ In other words, \begin{equation} \label{trueces} C(d,S) = r_{d}+ \sum_{X_{min}}^{X_{max}} r_{l X+d+1-\varphi(n)} t_{k,d}, \end{equation} where $X_{min}$ (respectively, $X_{max}$ ) is the minimum (respectively, the maximum) of integers $X$'s that satisfy \eqref{lebigX} when $k$ goes from $1$ to $n/2-\varphi(n).$ Observe that \begin{equation} \label{termsX} X_{max} - X_{min} \leq \frac{n/2- \varphi(n)}{l} = pq -(p-1)(q-1) = p+q-1. \end{equation} and that from \eqref{lebigX} and \eqref{tekade1} we get \begin{equation} \label{tekade2} t_{k,d} = \sum_{\substack{u_{l}+2 u_{2 l}+\cdots + K u_{K l}= X,\\ u_{i l} \geq 0,i=1,\ldots,K}} \left ({\frac{(u_{l}+\cdots+u_{K l}-1)!}{u_{l}! \cdots u_{K l}!}} \sum_{t=0}^{d}u_{K l-t}\right ) c_{l}^{u_{l}} \cdots c_{K l}^{u_{K l}}. \end{equation} We want to bound above $\vert t_{k,d} \vert.$ In order to do that, observe first that for the whole range $ v =0,\ldots,K$ one has $c_{v l} \in \{-1,0,1\}$ by Lemma \ref{migottispec} so that $\vert c_{l}^{u_{l}} \cdots c_{K l}^{u_{K l}} \vert \leq 1,$ we also have $\sum_{t=0}^{d}u_{K l-t} \leq u_{l}+ u_{2 l}+\cdots + u_{K l}$ so that \begin{equation} \label{lesul} 0 \leq \left ({\frac{(u_{l}+\cdots+u_{K l}-1)!}{u_{l}! \cdots u_{K l}!}} \sum_{t=0}^{d}u_{K l-t}\right ) \leq {\frac{(u_{l}+\cdots+u_{K l})!}{u_{l}! \cdots u_{K l}!}} \end{equation} Trivially, for the whole range of $v$ one has $u_{v l} ! \geq 1$ since $u_{v l} \geq 0.$ Thus from \eqref{tekade2} and \eqref{lesul} we get \begin{equation} \label{tekade3} \vert t_{k,d} \vert \leq \sum_{\substack{u_{l}+2 u_{2 l}+\cdots + K u_{K l}= X,\\ u_{i l} \geq 0,i=1,\ldots,K}} (u_{l}+\cdots+u_{K l})! \end{equation} Since $0 \leq u_{l}+\cdots+u_{K l} \leq u_{l}+2 u_{2 l}+\cdots + K u_{K l}= X$, an upper bound of $\vert u_{l}+\cdots+u_{K l} \vert$ will be the maximal possible $X$, say $X_2$ in the range of $k$, i.e., $1 \leq k \leq n/2 - \varphi(n).$ Thus from \eqref{lebigX} one immediately has \begin{equation} \label{X2} l X_2 \leq (n/2 -\varphi(n) ) +\varphi(n) -d - 1 \leq n/2. \end{equation} Since $X \leq X_2$, by rewriting \eqref{X2} and using \eqref{stepl} one gets \begin{equation} \label{XX2} X \leq X_2 \leq n/(2l) = pq. \end{equation} Put $\Theta$ the number of terms in the sum in \eqref{tekade3}. The $u_{ m l}$'s in the sum of the right-hand side of \eqref{tekade3} are non-negative integers such that \begin{equation*} \label{ulX} u_{l}+2 u_{2 l}+\cdots + K u_{K l}= X, \end{equation*} thus $\vert u_{l} \vert \leq X,$ $\vert u_{2 l} \vert \leq X/2, \ldots, \vert u_{K l} \vert \leq X/K.$ By using \eqref{XX2} it follows that \begin{equation} \label{ulXXK} \Theta \leq X^K/K! \leq exp(X) \leq exp(X_2) \leq exp(p q). \end{equation} Thus from \eqref{tekade3}, and \eqref{XX2}, \eqref{ulXXK}, it follows that \begin{equation} \label{tekadebounded} \vert t_{k,d} \vert \leq \Theta \cdot X_2!\leq (pq) ! exp(pq). \end{equation} We are ready to prove the result. Observing that for any $j$, $\vert r_j \vert \leq 2$, from \eqref{trueces}, \eqref{termsX}, and \eqref{tekadebounded} it follows that \begin{equation*} \label{tekadeRbounded} \vert C(d,S) \vert \leq 2 + 2(p+q-1) (pq)! exp(pq). \end{equation*} This finishes the proof of the lemma. \end{proof} The following is well known. See, e.g., \cite[p. 1193]{HWallis}, \cite[p. 234]{Meisner}, \cite[pp. 329-330] {Turyn} for the first lemma and \cite[p. 73]{davis} for the second. \begin{lemma} \label{regular} Let $H$ be a regular Hadamard matrix of order $n\geq 4$, i.e., a Hadamard matrix whose row and column sums are all equal. Then $n=4h^2$ for some positive integer $h.$ Moreover, the row and column sums are all equal to $\pm2h$ and each row has $2h^2\pm h$ positive and $2h^2 \mp h$ negative entries. \end{lemma} \begin{lemma} \label{eigens} Let $H$ be a circulant Hadamard matrix of order $n,$ let $w= \exp(2 \pi i/n)$ and let $R(x)$ be its representer polynomial. Then the set of all eigenvalues of $H$ consists of the set of all $R(v)$, where $v \in \{1,w,w^2,\ldots,w^{n-1}\}.$ Moreover, they satisfy \[ \vert R(v) \vert = \sqrt{n}. \] \end{lemma} More generally and for more details see \cite{davis}. \begin{lemma} \label{fourier} Let $C=circ(c_1, \ldots, c_n)$ be a circulant matrix of order $n>0$ with \emph{representer} polynomial $P(t)= c_1+c_2 t + \ldots +c_nt^{n-1}$. Let $\omega$ be the primitive complex $n$-th root of unity with a smaller positive argument. $C$ is diagonalizable and $C = F\sp{*}\Delta F$, where $\Delta = diag(P(1),P(w),\ldots, P(w^{n-1})$ is a diagonal matrix containing the eigenvalues of $C$ and $F\sp{*}= (\frac{ \omega^{(i-1)(j-1)}}{n\sp{1/2}})$ is the conjugate of the Fourier matrix. Moreover, $F$ is unitary. \end{lemma} The next lemma is \cite[Theorem 3]{ma}, which also appeared as \cite[Theorem 3.1]{craigen}. It was already used in \cite{luisAMEN}. \begin{lemma} \label{oldma} Let $A$ be a circulant matrix of order $n>0$ with entries in $\{0,1\}.$ Let $m$ be an even positive integer. Assume that $A^m \in \Z I + \Z J.$ Then $A \in \{0,P,J,J-P\}$, where $P$ is a permutation matrix of order $n.$ \end{lemma} Using Lemma \ref{regular} and Lemma \ref{oldma} Craigen and Kharaghani \cite[Lemma 4]{craigen} proved: \begin{lemma} \label{craigenl4} Let $H$ be a circulant Hadamard matrix of order $n>0$ such that for some positive number $m$ \[ H^m =n^{\frac{m}{2}}I. \] Then $n \leq 4.$ \end{lemma} We can also write the case $n>1$ of Lemma \ref{craigenl4} as \begin{lemma} \label{craigenK} Let $H$ be a circulant Hadamard matrix of order $n>1$, and let $K := H/\sqrt{n}.$ Assume that for some positive number $m$ the orthogonal matrix $K$ has multiplicative order $m.$ Then $n=4.$ \end{lemma} \section{ Proof of Theorem \ref{agou3}} \label{Th1} \begin{proof} Assume the existence of a circulant Hadamard matrix $H$ that satisfies the hypothesis. By Brualdi's result in the introduction (see \cite{brualdi}) we can take $H$ to be nonsymmetrical. This implies that \begin{equation} \label{brualdiconcrete} \text{some eigenvalue of}\;H\;\text{is non-real}. \end{equation} In our special case $n=4p^{2a}q^{2b}$ with odd prime numbers, say, $p < q.$ Write the Euclidean division (long division) of the representer polynomial $R(x)$ of $H$ by the cyclotomic polynomial $\Phi_n(x)$ as \begin{equation} \label{RS} R(x) = Q(x)\Phi_n(x)+S(x), \end{equation} with, say, $S(x) = s_d x^d+ s_{d-1}x^{d-1}+ \cdots + s_{1}x+s_{0}$ so that $d = \deg(S(x))$. Let $\omega \in \C$ be an $n$-th primitive root of $1$. Since by \eqref{RS} one has $R(\omega)=S(\omega)$, \eqref{brualdiconcrete} implies that we have $d>0.$ From Lemma \ref{eigens} one has $R(\omega)R (\overline{\omega})=1,$ thus \begin{equation} \label{system} S(\omega)S^{\ast}(\omega)=n \omega^d, \end{equation} where $S^{\ast}(x)$ is the reciprocal polynomial of $S(x).$ From Condition \ref{dsmall} and \eqref{system} we get easily $s_{0}=s_{1}= \cdots = s_{d-1} =0$ and $s_d^{2} =n.$ Therefore $S(\omega)=s_d \omega^d.$ Now, from Lemma \ref{cds} we get \begin{equation} \label{upperB} p^a q^b = \vert s_d /2\vert \leq (p+q-1) (pq) ! \exp(pq) +1, \end{equation} But, \eqref{upperB} contradicts to hypothesis. This finishes the proof of the theorem. \end{proof} \section{ Proof of Theorem \ref{abeq1}} \label{Th2} \begin{proof} Assume the existence of a circulant Hadamard matrix $H$ that satisfies the hypothesis. In particular, by Brualdi's result above (see again \cite{brualdi}) we can assume that $H$ has some non-real eigenvalue. In our special case $n=4p^{2}q^{2}$ with odd prime numbers, say, $p < q.$ Using the same notation as in Section \ref{Th1}, from Condition \ref{dsmall} and \eqref{system} we get as before $s_{j}=0$ for $j=0, \ldots, {d-1}$ and $s_d^2=4p^2q^2$ so that, up to switching $q$ and $-q$, from \eqref{system} we obtain \begin{equation*} \label{td} S(\omega) = 2qp \omega^d, \; \text{and}\; S^{\ast}(\omega) =2qp. \end{equation*} From \eqref{RS} this implies \begin{equation} \label{angleR} R(\omega) =2qp \omega^d. \end{equation} From \eqref{angleR} and Lemma \ref{eigens} it follows that $v^d$, where $v$ is any $n$-th primitive root of $1$, are eigenvalues of the orthogonal matrix $M := H/2qp.$ Any other eigenvalue $\lambda$ of $M$ has the form $\lambda = R(\omega^t)/2qp$ with $1 \leq t \leq n.$ If $\lambda$ is real, then it equals $1$ or $-1$ so that it has order at most equal to $2;$ if $\lambda$ is non-real, then by the hypothesis $\lambda = R(\omega^k)/2qp$ for some $k$ coprime with $n$. This means that $\lambda = v^d$ for the $n$-th primitive root of $1$, $v = \omega^k.$ Therefore each eigenvalue of $M$ has finite order. In other words, the diagonalizable matrix $M$ (see Lemma \ref{fourier}) has finite multiplicative order. By Lemma \ref{craigenK} this implies the contradiction $n=4.$ This proves the theorem. \end{proof} \section{ Proof of Theorem \ref{neigen}} \label{Th3} \begin{proof} Assume the existence of a circulant Hadamard matrix $H$ that satisfies the hypothesis. In particular, \begin{equation} \label{tra0} n >4. \end{equation} We can take $H$ of the form $H = {\rm{circ}}(1,h_2,\ldots,h_n)$ with $h_j \in \{-1,1\}$. Let $B = A^{\ast} = A.$ Then \begin{equation*} \label{tra1} \mathrm{Tr}(AB)= \mathrm{Tr}(A A^{\ast}) = \sum_{i,j} a_{ij}^2. \end{equation*} In each row of the circulant matrix $A$ of order $n$ there are, say, $t$ zeros, and thus $n-t,$ $1$'s or $-1$'s. Since $a_{ij} \neq 0$ implies $a_{ij}^2=1$, we get \begin{equation} \label{tra2} \mathrm{Tr}(AB)= n(n-t). \end{equation} But $AB = A A^{\ast} =A^2 = \frac{1}{4}(H^2+{H^{\ast}}^2 +2 H H^{\ast}).$ Since $H$ is Hadamard, then we obtain $AB = \frac{1}{4}(H^2+{H^{\ast}}^2 +2 n I)$, where $I$ is the identity matrix of order $n.$ Taking traces on both sides of the latter equality we get $\mathrm{Tr}(AB) = \frac{1}{4}(2 \mathrm{Tr}(H^2)+2n^2)$ so that using hypothesis (a) we obtain \begin{equation} \label{tra3} \mathrm{Tr}(AB)= \frac{n^2}{2}. \end{equation} From \eqref{tra2} and \eqref{tra3} it follows that \begin{equation} \label{tra4} t= \frac{n}{2}. \end{equation} By Lemma \ref{eigens} the eigenvalues $\mu$ of $H$ are of the form $\mu = \sqrt{n} \exp(i \theta).$ It follows then by (b) that the eigenvalues $\lambda = \sqrt{n} \cos(\theta)$ of $A$ have arguments $\theta$ in between $-\pi/2$ and $\pi/2.$ Thus $\cos(\theta) \geq 0$ for each eigenvalue of $A.$ We compute $\mathrm{Tr}(AB)$ now by using the eigenvalues of $A$. One has $\mathrm{Tr}(AB)= \mathrm{Tr}(A A^{\ast}) = \mathrm{Tr}(A^2) = \sum_{\lambda} \lambda^2 = n \sum_{\theta} \cos(\theta)^2.$ Therefore \begin{equation} \label{tra5} \sum_{\theta} \cos(\theta)^2 = \frac{\mathrm{Tr}(AB)}{n} . \end{equation} Since $1 \geq \cos(\theta) \geq 0$, one has $\sum_{\theta} \cos(\theta)^2 \leq \sum_{\theta} \cos(\theta) = \frac{\mathrm{Tr}(A)}{\sqrt{n}} .$ Thus by \eqref{tra5} and since $A = {\rm{circ}}(1,\ldots)$ \begin{equation} \label{tra6} \frac{\mathrm{Tr}(AB)}{n} \leq \frac{\mathrm{Tr}(A)}{\sqrt{n}}= \sqrt{n}. \end{equation} Directly by \eqref{tra3}, or alternatively by (\eqref{tra2} and \eqref{tra4}) from \eqref{tra6} we get \begin{equation} \label{tra7} \frac{n}{2} \leq \sqrt{n}. \end{equation} Thus, in \eqref{tra7} we obtain \begin{equation*} \label{tra8} n \leq 4. \end{equation*} This contradicts \eqref{tra0}, thereby finishing the proof of the theorem. \end{proof} %%%% Acknowledgment %%%%%%%% \section{Acknowledgement} We thank Bahman Saffari (Babar) for his nice inspiring papers. We are also grateful to the referee for careful reading, great suggestions, pointing out the important works of Schmidt and Leung in this subject, letting know the bibliography items \cite{Leungzero, SchmidtSmith} and more importantly, for his suggestions about the scope of the present paper. We are convinced that the paper is now better thanks to his/her suggestions. %%%% Bibliography %%%%%%%%%% \begin{thebibliography}{99} \bibitem{agou} {\sc S.\,Agou}, {\em Sur les formules explicites intervenant dans la division euclidienne des polyn\^{o}mes et leurs cons\'{e}quences}, C. R. Acad. Sci. Paris Ser. A-B {\bf 273}(1971), A209--A211. \bibitem{agou1} {\sc S.\,Agou}, {\em Sur les formules explicites intervenant dans la division euclidienne des polyn\^{o}mes \`{a} coefficients dans un anneau unitaire et applications diverses}, Publ. D\'{e}p. Math. (Lyon) {\bf 8}(1971), 107--121. \bibitem{BorMoss} {\sc P.\,Borwein, M.\,J.\,Mossinghoff}, {\em Wieferich pairs and Barker sequences, II}, LMS J. Comput. Math. {\bf 17}(2014), 24--32. \bibitem{brualdi} {\sc R.\,A.\,Brualdi}, {\em A note on multipliers of difference sets}, J. Res. Nat. Bur. Standards Sect. B {\bf 69}(1965), 87--89. \bibitem{craigen} {\sc R.\,Craigen, H.\,Kharaghani}, {\em On the nonexistence of Hermitian circulant complex Hadamard matrices}, Australas. J. Combin. {\bf 7}(1993), 225--227. \bibitem{davis} {\sc P.\,J.\,Davis}, {\em Circulant matrices}, 2nd ed., AMS Chelsea Publishing, New York, 1994. \bibitem{EGR} {\sc R.\,Euler, L.\,H.\,Gallardo, O.\,Rahavandrainy}, {\em Sufficient conditions for a conjecture of Ryser about Hadamard circulant matrices}, Lin. Alg. Appl. {\bf 437}(2012), 2877--2886. \bibitem{EGRcomb} {\sc R.\,Euler, L.\,H.\,Gallardo, O.\,Rahavandrainy}, {\em Combinatorial properties of circulant Hadamard matrices}, in: {\em A panorama of mathematics: pure and applied}, (C.\,M.\,da Fonseca, A.\,V.\,Huynh, S.\,Kirkland, V.\,K.\,Tuan, Eds.), Contemp. Math. {\bf 658}, AMS, Providence, Rhode Island, 2016, 9--19. \bibitem{luisAMEN} {\sc L.\,Gallardo}, {\em On a special case of a conjecture of Ryser about Hadamard circulant matrices}, Appl. Math. E-Notes {\bf 12}(2012), 182-188. \bibitem{luisEJC} {\sc L.\,H.\,Gallardo}, {\em New duality operator for complex circulant matrices and a conjecture of Ryser}, Electron. J. Combin. {\bf 23}(2016), Article Number P1.59, 10 pp. \bibitem{HWallis} {\sc A.\,Hedayat, W.\,D.\,Wallis}, {\em Hadamard matrices and their applications}, Ann. Statist. {\bf 6}(1978), 1184--1238. \bibitem{JedwabLloyd} {\sc J.\,Jedwab, S.\,Lloyd}, {\em A note on the nonexistence of Barker sequences}, Des. Codes Cryptogr.{\bf 2}(1992), 93--97. \bibitem{Leungzero} {\sc K.\,H.\,Leung, B.\,Schmidt}, {\em The field descent method}, Des. Codes Cryptogr. {\bf 36}(2005), 171--188. \bibitem{Leung} {\sc K.\,H.\,Leung, B.\,Schmidt}, {\em New restrictions on possible orders of circulant Hadamard matrices}, Des. Codes Cryptogr. {\bf 64}(2012), 143--151. \bibitem{Leunguno} {\sc K.\,H.\,Leung, B.\,Schmidt}, {\em The anti-field-descent method}, J. Combin. Theory Ser. A {\bf 139}(2016), 87--131. \bibitem{ma} {\sc S.\,L.\,Ma}, {\em On rational circulants satisfying $A^m = dI + \lambda J$}, Linear Algebra Appl. {\bf 62}(1984), 155--161. \bibitem{Mato} {\sc M.\,Matolcsi}, {\em A Walsh-Fourier approach to the circulant Hadamard conjecture}, {\em Algebraic design theory and Hadamard matrices}, Springer Proc. Math. Stat. {\bf 133}, Springer, Cham, 2015, 201--208. \bibitem{Meisner} {\sc D.\,B.\,Meisner}, {\em On a construction of regular Hadamard matrices}, Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl. {\bf 3}(1992), 233--240. \bibitem{Ryser} {\sc H.\,J.\,Ryser}, {\em Combinatorial mathematics}, Carus Mathematical Monographs 14, Mathematical Association of America, %John Wiley and Sons, Inc., New York, 1963. \bibitem{SchmidtSmith} {\sc B.\,Schmidt, K.\,W.\,Smith}, {\em Circulant weighing matrices whose order and weight are products of powers of $2$ and $3$}, J. Combin. Theory Ser. A {\bf 120}(2013), 275--287. \bibitem{thanga} {\sc R.\,Thangadurai}, {\em On the coefficients of cyclotomic polynomials}, in: {\em Cyclotomic fields and related topics}, (S.\,D.\,Adhikari, Ed.), Proceedings of the summer school (Pune, 1999), Bhaskaracharya Pratishthana, Pune, 2000, 311--322. \bibitem{Turyn} {\sc R.\,J.\,Turyn}, {\em Character sums and difference sets}, Pac. J. Math. {\bf 15}(1965), 319--346. \end{thebibliography} %% \end{linenumbers} \end{document}