\documentstyle[11pt]{article} \input amssym.def \input amssym.tex \newcommand{\dd}{\ldots} \newcommand{\sE}{{\cal E}} \newcommand{\hsp}{\hspace{\parindent}} \newcommand{\tht}{\theta} \newcommand{\af}{\alpha} \newcommand{\be}{\beta} \newcommand{\la}{\lambda} \newcommand{\cd}{\cdots} \newcommand{\mem}{\in} \newcommand{\lt}{\left(} \newcommand{\rt}{\right)} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \def\binom#1#2{{#1}\choose{#2}} \newcommand{\dis}{\displaystyle} \newcommand{\df}{\displaystyle\frac} \newcommand{\ds}{\displaystyle\sum} \newcommand{\In}{\infty} \newcommand{\wg}{\sim} \newcommand{\Tht}{\Theta} \newcommand{\sq}{\sqrt} \newcommand{\ep}{\epsilon} \newcommand{\RR}{{\Bbb R}} \newcommand{\CC}{{\Bbb C}} \newcommand{\ZZ}{{\Bbb Z}} \newcommand{\Om}{\Omega} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \newcommand{\eeq}{\end{equation}} \newcommand{\eqn}[1]{(\ref{#1})} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \setlength{\textwidth}{6.2in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} \setlength{\headheight}{0in} \makeatletter \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \thispagestyle{empty} \begin{document} \begin{center} {\large {\bf Construction of invertible sequences for multipath estimation}} \\ \vspace{1\baselineskip} {\em A. M. Odlyzko} \\ \vspace{.5\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ amo@research.att.com \\ \vspace{1\baselineskip} {\em Dedicated to Jim Massey on the occasion of his 60th birthday} \\ \vspace{1.5\baselineskip} {\bf ABSTRACT} \\ \vspace{1\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} J. Ruprecht has proposed coding schemes that allow for multipath estimation. They use sequences $a_0 , \dd , a_n$ with $a_j = \pm 1$ for each $j$ such that the associated polynomial $f(z) = \sum a_j z^j$ has a large $$R_p(f) = \frac{n+1}{\dis\sum_{k=0}^n \left| f(e^{2 \pi ik / (n+1)} ) \right|^{-2}} ~.$$ Most sequences have a small $R_p(f)$, and those with maximal $R_p(f)$ are hard to find. This note shows for $n$ of the form $n= q-1$, $q$ a prime, one can construct sequences with $R_p(f) \ge n - O(n^{1/3})$. Since $R_p(f) \le n+1$ for any sequence, this construction is asymptotically close to optimal. It also produces large values of $R_p(f)$ for small $n$. It is also shown that for $n=q-1$, $q$ a prime, there exist sequences $a_0 , \dd , a_n$ such that the associated polynomial $f(z)$ satisfies $$| f(e^{2 \pi ik / (n+1)}) | = (1+ o(1))n^{1/2} ~~~\mbox{as}~~~n \to \infty$$ uniformly for $0 \le k \le n$. \clearpage \large\normalsize \renewcommand{\baselinestretch}{1} \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\large {\bf Construction of invertible sequences for multipath estimation}} \\ \vspace{1\baselineskip} {\em A. M. Odlyzko} \\ \vspace{.5\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ amo@research.att.com \\ \vspace{1\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp In the Ph.D. thesis \cite{Rup}, written under the supervision of Jim Massey, J\"{u}rg Ruprecht has proposed coding schemes designed for effective multipath estimation. Such schemes might be useful in indoor wireless systems \cite{RupNH,WallisSW} or other communication settings. These schemes use {\em invertible sequences}, which are sequences $a_0 , \dd , a_n$, with $a_j = \pm 1$ for each $j$, such that the associated polynomial \begin{equation} f(z) = \sum_{j=0}^n a_j z^j \label{eq101} \end{equation} satisfies \beql{BBBeq12} f(e^{2 \pi it} ) \neq 0 ~~\mbox{for all real}~~t ~. \eeq In some situations these schemes use {\em invertible periodic sequences}, for which the polynomial $f(z)$ only has to satisfy \begin{equation} f(e^{2 \pi ik/(n+1)}) \neq 0 ,~~~~ 0 \le k \le n ~. \label{eq102} \end{equation} (These invertible periodic sequences possess inverses under periodic convolution, which is required for Ruprecht's maximum likelihood estimation methods \cite{Rup}.) For best performance in estimating multipath interference, it is desirable to find invertible periodic sequences that maximize \begin{equation} R_p(f) = \frac{n+1}{\dis\sum_{k=0}^n \left| f(e^{2 \pi i k / (n+1)}) \right|^{-2}} ~. \label{eq103} \end{equation} In \cite{Rup}, this figure of merit is referred to as even processing gain $G_e^{(vs)}$ of a sequence $s$ and its periodic inverse $v$, and is defined in a much more complicated form. However, a short calculation based on the formulas on p.~27 and in Appendix~A of \cite{Rup} shows that it equals our $R_p(f)$. We will call $R_p(f)$ the periodic Ruprecht merit factor, to distinguish it from other merit factors, such as that of Golay \cite{Golay72,Massey,Odl3}, as well as the aperiodic Ruprecht merit factor, defined as \beql{eqZ14} R_a (f) = \lt \int_0^1 | f(e^{2 \pi it} ) |^{-2} dt \rt^{-1}~. \eeq (For $R_a (f)$ to exist, we require that $f(z)$ be an invertible sequence.) Sequences with large $R_a (f)$ are more desirable than those with large $R_p (f)$, since they can be used for transmission \cite{RupNH}, not just for multipath estimation. Unfortunately while we will provide constructions of sequences with large $R_p (f)$, the problem of obtaining large $R_a (f)$ remains open. Since \begin{equation} \sum_{k=0}^n \left| f( e^{2 \pi ik /(n+1)} ) \right|^2 = (n+1)^2 \label{eq104} \end{equation} and \beql{eqZ16} \int_0^1 | f(e^{2 \pi it}) |^2 dt = n+1 \eeq by a familiar calculation, the Cauchy-Schwarz inequality shows that $R_p(f) \le n+1$, $R_a (f) \le n+1$ for any sequence $a_0 , \dd , a_n$. How close can $R_a(f)$ and $R_p (f)$ come to $n+1$? Ruprecht \cite{Rup} lists in Table~B.6 the sequences $a_0 , \dd , a_n$ with the highest values of $R_p(f)$ for $n \le 29$, as well as some sequences with high values of $R_p(f)$ for $30 \le n \le 32$. The maximal value of $R_p(f)$ for $n=29$ is 26.6583, for example. Ruprecht also gives, in Table~B.8, the best sequences drawn from a restricted class, that of the {\em skew-symmetric} $a_j$ (i.e., those with even $n$ and $a_{n/2 -r} = (-1)^r a_{n/2+r}$) for $n \le 44$. (The value for $n=44$ is incorrect, though. See \cite{Odl3}.) The maximal value of $R_p(f)$ for $n=42$ is 37.4244. In Tables~B.9 and B.10 of \cite{Rup} Ruprecht lists sequences with large $R_a (f)$, for $n \le 23$ in the general case and $n \le 44$ for the skew-symmetric case. For example, for $n=44$ he gives a skew-symmetric sequence with $R_a (f) = 39.7753$. Most of the values, especially for large $n$, are not known to be maximal. Skew-symmetric sequences with large $R_a(f)$ and $R_p (f)$ for $n \le 90$ (obtained from a search for other types of extremal $\pm 1$ sequences) are given in \cite{Odl3}. The nonexhaustive search for high $R_a(f)$ and $R_p (f)$ that is documented in that paper has produced a value of $R_p(f) = 77.5820$ for $n=90$, for example. What can one do for larger lengths $n$? Random choices of the $a_j$ almost always give small values of $R(f)$ (cf. \cite{Odl3}). This is because random trigonometric polynomials have small minimal absolute values \cite{Kashin2,Odl4}, as was conjectured by Littlewood \cite{Litt,Litt2}. Thus the situation is completely different than it is in coding theory, where random codes are good. Sometimes one can construct a sequence with a large Ruprecht merit factor from shorter sequences. For example, if $n=12$ and $(a_0 , \dd , a_n ) = (1,1,1,1,1,-1,-1,1,1,-1,1,-1,1)$ is the 13-term Barker sequence, with associated polynomial $f(z)$, then $f(z^{13} ) f(z)$ is a polynomial associated to a $\pm 1$ sequence of 169 terms, and \begin{equation} R_a (f(z^{13}) f(z)) = 153.1014 \dd~,~~~~ R_p(f(z^{13}) f(z)) = 154.6331 ~ \dd \label{eq105} \end{equation} However, even this construction does not produce good asymptotic results. The main result of this note is to show that high periodic Ruprecht merit factors can be achieved for a dense sequence of values of $n$. \begin{theorem} \label{th1} There is a constant $c > 0$ such that if $n=q-1$ for $q$ a prime, then there exists a sequence $a_0 , \dd , a_n$ with $a_j = \pm 1$ for all $j$ such that \begin{equation} n-cn^{1/3} \le R_p(f) \le n+1 ~. \label{eq106} \end{equation} \end{theorem} The proof of Theorem~\ref{th1}, given in Section~2, shows how to construct these sequences. The sequences of Theorem~\ref{th1} do have higher $R_a (f)$ than random sequences, but not very high ones. There is a discussion of this disappointing behavior in Section~4. The search for $\pm 1$ sequences with large Ruprecht merit factors is just one part of the huge subject of extremal and statistical properties of $\pm 1$ sequences. For results, surveys, and applications, see \cite{Luke1,Odl3,Schr}. In particular, there are connections to the search for sequences with large Golay merit factor \cite{Golay72,Massey,Odl3}. For $R_p(f)$ to be large, $|f( \exp ( 2 \pi ik / (n+1))) |$ has to be large for most $k$. Erd\"{o}s \cite{Erd} and Littlewood \cite{Litt,Litt2} have raised the question of whether there exist $\pm 1$ sequences $a_0 , \dd , a_n$ such that the associated polynomials $f(z)$ satisfy \beql{Neq107} \min_{|z|=1}~n^{-1/2} |f(z)| = 1+ o(1) ~~~\mbox{as}~~~ n \to \In ~. \eeq If such sequences existed, then we would have $R_a(f) \sim n$ and $R_p (f) \sim n$ as $n \to \infty$ for their polynomials. The current evidence is that such sequences don't exist (cf. \cite{Odl3}). However, to obtain large $R_p(f)$ we do not require \eqn{Neq107} to hold. We even do not require $n^{-1/2} | f( \exp (2 \pi ik /(n+1)) | = 1+o(1)$ as $n \to \infty$ to hold uniformly for all $k$, $0 \le k \le n$. Instead, we prove Theorem~\ref{th1} by modifying the Legendre sequence $a_j = \left( \frac{j}{q} \right)$. It is easy to see that modifications of that sequence achieve $R_p(f) \sim n$ as $n=q-1 \to \infty$, but the difference $R_p(f) -n$ usually turns out to be much larger than $n^{1/3}$ when one uses some of the obvious methods. By a careful analysis of what happens to $R_p(f)$ as the Legendre sequence is changed, we can obtain the bound of Theorem~\ref{th1}. The construction of Theorem~\ref{th1} produces sequences for which $n^{-1/2} | f( \exp ( 2 \pi i k / (n+1)) | = 1+o(1)$ as $n \to \In$ uniformly in $k$ satisfying $1 \le k \le n$. For $k=0$, though, $|f(1)|$ is of order $n^{1/3}$. However, we prove the following result. \begin{theorem} \label{Nth2} If $n=q-1$ for $q$ a prime, then there exists a sequence $a_0 , \dd , a_n$ with $a_j = \pm 1$ for all $j$ such that \beql{eqZ18} n^{-1/2} | f(\exp (2 \pi ik / (n+1)) | = 1+O(n^{-1/4} ( \log n )^{1/2} )~~~\mbox{as}~~~ n \to \In \eeq uniformly in $k$, $0 \le k \le n$. \end{theorem} If we use only the bound \eqn{eqZ18} for the sequences of Theorem~\ref{Nth2}, we find that these sequences have $R_p (f) \ge n- c' n^{3/4} ( \log n)^{1/2}$ for some constant $c' > 0$. With more care, one can show that these sequences have larger $R_p (f)$, but the bound for $n-R_p (f)$ that one can prove for these sequences appears to be considerably weaker than that given by Theorem~\ref{th1} for its sequences. We note that if \beql{OZ109} n^{-1/2} | f(e^{2 \pi ik / (n+1)}) | =1 ,~~~ 0 \le k \le n~, \eeq which is equivalent to $R_p(f) =n+1$, then $a_0 , \dd , a_n$ is a Barker sequence and also the first row of a circulant Hadamard matrix, and so is thought not to exist for $n > 3$ \cite{Davis,WallisSW}. However, there is still no proof of this conjecture. We leave several problems open. For example, can Theorems~\ref{th1} and \ref{Nth2} be generalized so that $n$ does not have to be of the form $n=q-1$ for $q$ a prime? Also, can one prove analogs of Theorems~\ref{th1} and \ref{Nth2} for the aperiodic merit factor $R_a (f)$? Numerical evidence (cf. \cite{Odl3}) suggests that there do exist $\pm 1$ sequences $a_0 , \dd , a_n$ for $n \ge 10$ such that the associated polynomials $f(z)$ have \beql{eqZ19} \min_{|z|=1} n^{-1/2} |f(z)| \ge 1/2 ~. \eeq A sequence satisfying \eqn{eqZ19} is guaranteed to have $R_a (f) \ge n/4$. However, since $R_a (f)$ is an average result, we might expect that some of these sequences might have $R_a (f) \sim n$ as $n \to \In$. That is what seems to happen for the sequences listed in \cite{Odl3}. \vspace*{.1in} \noindent{\bf Acknowledgement.} The author thanks J\"{u}rg Ruprecht for helpful correspondence. \section{Proof of Theorem~\protect\ref{th1}} \hsp Let $q$ be an odd prime, and define \begin{eqnarray} \label{eq201} \zeta & = & \exp ( 2 \pi i /q) ~, \\ \label{eq202} g(z) & = & \sum_{k=1}^{q-1} \left( \frac{k}{q} \right) z^k ~, \end{eqnarray} where $\left( \frac{k}{q} \right)$ is the Legendre symbol. (Thus $\left( \frac{k}{q} \right)$ is 0 for $k=0$, 1 if $k$ is a nonzero quadratic residue modulo $q$, and $-1$ if $k$ is a nonresidue modulo $q$.) The $g( \zeta^j )$ are Gauss suns, and have an extensive literature. It is known (and easy to derive \cite{Apostol}) that \begin{equation} g(1) =0 ,~~g( \zeta^j) = \left( \frac{j}{q} \right) g( \zeta )~~~\mbox{for}~~~ 1 \le j \le q-1 ~. \label{eq203} \end{equation} It is also easy to see (cf. \cite{Apostol}) that \begin{equation} g( \zeta )^2 = (-1)^{(q-1)/2} q ~. \label{eq204} \end{equation} It is further known that \begin{equation} g( \zeta ) = \left\{ \begin{array}{cc} q^{1/2}~, & q \equiv 1 ~~( \bmod~4) ~, \\ ~~ \\ [-.09in] iq^{1/2}~, & q \equiv 3 ~~( \bmod~4)~, \end{array} \right. \label{eq205} \end{equation} but this is much harder to prove, and we will not use it. It is also known that $g(z)$ is large for some $z$ with $|z|=1$ \cite{Montg}. We cannot use the sequence of coefficients of $g(z)$, because (i)~$a_0 =0$ and (ii)~$g(1)=0$. The main idea behind the construction below is to modify $g(z)$ slightly. We note that if we take $f(z) = 1+g(z)$, then the coefficient sequence does consist of $\pm 1$'s, and $f(1) =1$, $|f(\zeta^k )| \ge q^{1/2} -1$ for $1 \le k \le q-1$. Therefore $R(f) \sim q/2$ as $q \to \In$, and this already gives a merit factor far superior to that of almost all $\pm 1$ sequences. We set \begin{equation} f(z) = g(z) + h(z) ~, \label{eq206} \end{equation} where \begin{equation} h(z) = a - 2 \sum_{k \in S} \left( \frac{k}{q} \right ) z^k ~, \label{eq207} \end{equation} $a= \pm 1$, and $S \subseteq \{ 1, \dd , q-1 \}$, $| S| < q^{1/2} / 100$. It is easy to see, using the results on maximal values of random trigonometric polynomials, that random choices of $S$ give $R(f) \sim n$ as $n \to \In$. What we show, however, is that a nonrandom choice produces much better answers due to the special number theoretic properties of the Legendre sequence. We will select $S$ to consist entirely of residues or else entirely of nonresidues, so that \begin{equation} \left( \frac{k}{q} \right) =b ~~~\mbox{for all}~~~ k \in S~, \label{eq208} \end{equation} where $b= \pm 1$. The precise selection of $a$ and $S$ will be discussed later. We now observe that all coefficients of $f(z)$ are $\pm 1$. Further, we have \begin{equation} f(1) = g(1) = a - 2b | S | ~. \label{eq209} \end{equation} For $1 \le j \le q-1$, \begin{equation} | f( \zeta^j)|^2 = |g( \zeta^j ) + h( \zeta^j )|^2 = q+ | h( \zeta^j )|^2 + 2~\mbox{Re} \, \left( \overline{g( \zeta^j)} h( \zeta^j ) \right)~. \label{eq210} \end{equation} Since $| S| < q^{1/2} / 100$, we find that for large $q$, \begin{equation} | h( \zeta^j ) | < q^{1/2} / 10 = |g( \zeta^j ) | /10 ~. \label{eq211} \end{equation} Therefore we can write, for $1 \le j \le q-1$, \begin{equation} | f( \zeta^j ) |^{-2} = q^{-1} \left( 1- 2q^{-1}~\mbox{Re} \, \left( \overline{g( \zeta^j)} h( \zeta^j) \right) + O ( q^{-1} | h( \zeta^j) |^2 ) \right)~. \label{eq212} \end{equation} This implies, by \eqn{eq203}, that \begin{equation} |f( \zeta^j) |^{-2} = q^{-1} \left( 1 - 2q^{-1} \left( \frac{j}{q} \right)~\mbox{Re}~ \left( \overline{g( \zeta )} h( \zeta^j ) \right) + O( q^{-1} | h( \zeta^j) |^2 ) \right)~, \label{eq213} \end{equation} and therefore \begin{equation} \sum_{j=1}^{q-1} |f( \zeta^j)|^{-2} = \frac{q-1}{q} - 2q^{-2} ~\mbox{Re}~ \overline{g( \zeta)} \sum_{j=1}^{q-1} \left( \frac{j}{q} \right) h( \zeta^j ) + O \left( q^{-2} \sum_{j=1}^{q-1} | h( \zeta^j )|^2 \right)~. \label{eq214} \end{equation} Now \begin{equation} \sum_{j=1}^{q-1} | h( \zeta^j )|^2 \le \sum_{j=0}^{q-1} | h( \zeta^j)|^2 = 4 q | S| ~. \label{eq215} \end{equation} On the other hand, by \eqn{eq208}, \begin{eqnarray} \sum_{j=1}^{q-1} \left( \frac{j}{q} \right) h( \zeta^j) & = & a \sum_{j=1}^{q-1} \left( \frac{j}{q} \right) - 2b \sum_{k \in S}~ \sum_{j=1}^{q-1} \left( \frac{j}{q} \right) \zeta^{kj} \nonumber \\ \label{eq216} & ~ & \\ & = & - 2b \sum_{k \in S} \left( \frac{k}{q} \right) g( \zeta ) = - 2g( \zeta ) | S| ~. \nonumber \end{eqnarray} If we now combine \eqn{eq209}, \eqn{eq214}, \eqn{eq215}, and \eqn{eq216}, we find that \begin{equation} \sum_{j=0}^{q-1} | f( \zeta^j)|^{-2} = (2 b | S| -a)^{-2} + \frac{q-1}{q} + O( q^{-1} | S | ) ~. \label{eq217} \end{equation} If we select $| S| \sim q^{1/3}$ as $q \to \In$, say, then we obtain \begin{equation} \sum_{j=0}^{q-1} | f( \zeta^j )|^{-2} = 1 + O( q^{-2/3} ) ~, \label{eq218} \end{equation} which yields the claim of Theorem~\ref{th1}. \section{Proof of Theorem~\protect\ref{Nth2}} \hspace*{\parindent} Theorem~\ref{Nth2} follows from a modification of the proof of Theorem~\ref{th1}, using methods similar to those of \cite{Odl0}. As in the preceding section, we define $f(z)$ by \eqn{eq206} and \eqn{eq207} with $a=1$. However, this time we will take $S$ to be of size about $q^{1/2}$, and it will contain only nonresidues. The set $S$ will be chosen at random, with each $k$, $1 \le k \le q-1$, $\lt \frac{k}{q} \rt =-1$, selected independently to be in $S$ with probability \beql{eqB31} Pr (k \in S) = q^{-1/2} /2 ~. \eeq Thus we have \beql{eqB32} h(z) =1 - 2 \sum_{k=1}^{q-1} \eta_k \lt \frac{k}{q} \rt z^k ~, \eeq where $\eta_k =0$ or 1 is a random variable with $\eta_k$ identically 0 if $\lt \frac{k}{q} \rt =1$, and $\sE (\eta_k ) = q^{-1/2} /2$ if $\lt \frac{k}{q} \rt = -1$. We need to determine the behavior of $h( \zeta^j )$ for $0 \le j \le q-1$, where $\zeta$ is defined by \eqn{eq201}. We first consider the expected value $\sE (h( \zeta^j ))$ for a fixed $j$. For $j=0$ we have \beql{eqB33} \sE (h(1) =1 + 2 \sum_{h=1 \atop \lt \frac{k}{q} \rt = -1}^{q-1} \sE ( \eta_k ) = 1 + (q-1) q^{-1/2} = q^{1/2} +1 - q^{-1/2} ~. \eeq For $1 \le j \le q-1$, on the other hand, \beql{eqB34} \sE (h( \zeta^j )) = 1 + q^{-1/2} \sum_{k=1 \atop \lt \frac{k}{q} \rt =-1}^{q-1} \zeta^{kj} ~. \eeq Since $\sum\limits_{k=0}^{q-1} \zeta^{kj} =0$ for $1 \le j \le q-1$, the sum in \eqn{eqB34} is $- \lt \lt \frac{j}{q} \rt q ( \zeta ) +1 \rt / 2$. Hence \beql{eqB35} \sE (h( \zeta^j)) = 1 - q^{-1/2} /2 - \lt \frac{j}{q} \rt q^{-1/2} g( \zeta) /2 ~, \eeq and so \beql{eqB36} \sE (h ( \zeta^j )) = O(1) ~. \eeq We conclude that $\sE (h( \zeta^j ))$ has the desired behavior uniformly for all $j$, $0 \le j \le q-1$. It remains to prove that for some choice of coefficients, $h( \zeta^j )$ will be close to $\sE (h( \zeta^j ))$ for all $j$. This will follow from the following result, which is similar to those in \cite{Kahane,Odl0}. \begin{lemma} \label{leB31} There exists a constant $C >0$ such that if \beql{eqB37} W = \sum_{k=1}^n \tau_k a_k ~, \eeq where the $a_k$ are real constants, $|a_k | \le 1$ for all $k$, and the $\tau_k$ are independent random variables with \beql{eqB38} Pr ( \tau_k = - \gamma_k ) = 1- \gamma_k ,~~~~ Pr ( \tau_k = 1- \gamma_k ) = \gamma_k ~, \eeq for some constants $\gamma_k$, $0 \le \gamma_k \le 1$, then \beql{eqB39} Pr \lt |W| > C \lt \sum_{k=1}^n \gamma_k \rt^{1/2} ( \log n)^{1/2} \rt < n^{-10} ~. \eeq \end{lemma} \noindent{\bf Proof.} We have, for any $\lambda > 0$, \beql{eqB40} Pr (W>x) e^{\lambda x} \le \sE (e^{\lambda W} ) ~. \eeq Now the $\tau_k$ are independent, so \beql{eqB310} \sE (e^{\lambda W} ) = \prod_{k=1}^n \sE ( e^{\lambda \tau_k a_k} ) ~. \eeq We next note that \beql{eqB311} \sE (e^{\la \tau_k a_k }) = e^{- \la \gamma_k a_k} (1- \gamma_k) + e^{\lambda (1- \gamma_k ) a_k} \gamma_k \le e^{C' \lambda^2 \gamma_k} \eeq if $C'$ is sufficiently large. Therefore \beql{eqB312} Pr (W > x) \le \exp \lt C' \la^2 \sum_{k=1}^n \gamma_k - \la x \rt ~. \eeq This bound holds for all $\la > 0$, so for $x > 0$ we select $\la = x (2 C' \sum \gamma_k )^{-1}$ and obtain \beql{eqB313} Pr (W > x) \le \exp \lt -x^2 \lt 4C' \sum_{k=1}^n \gamma_k \rt^{-1} \rt ~. \eeq Since the same bound for $Pr(W < -x)$ follows by applying \eqn{eqB313} to the problem with $a_k$ replaced by $- a_k$, we easily obtain the claim of the lemma. \hfill $\blacksquare$ To conclude the proof of Theorem~\ref{Nth2}, we apply Lemma~\ref{leB31} to the real and imaginary parts of $$h( \zeta^j ) - \sE (h( \zeta^j )) ~, ~~~~~ 0 \le j \le q-1 ~. $$ We find that with probability $\ge 1-n^{-8}$, \beql{eqB315} \left| h( \zeta^j ) - \sE (h( \zeta^j )) \right| < 10 C q^{1/4} ( \log q)^{1/2} \eeq holds for all $j$, $0 \le j \le q-1$. Therefore \beql{eqB316} | f( \zeta^j ) | = q^{1/2} + O(q^{1/4} ( \log q )^{1/2} ) \eeq for all $j$, which yields Theorem~\ref{Nth2}. There is a method of Kolountzakis \cite{Ko} that often manages to remove factors such as the $(\log q)^{1/2}$ in the estimate \eqn{eqB316}. However, it does not seem to apply in this case. \section{Final remarks} \hspace*{\parindent} How large are the $R_p(f)$ produced by the above construction for moderate lengths $n$? For $n=82$, the largest $R_p(f)$ that is known is 72.02 \cite{Odl3}. The construction of this section produces a sequence with $R_p(f) = 69.90$. Surprisingly, this result is achieved with $|S| =1$. As was noted at the beginning of this section, if $|S| =0$, then $R_p(f) \sim q/2$ as $q \to \In$ (for $n=q-1$, $q$ a prime). However, if we choose $|S|=1$, $a= -b=1$, then we obtain $R_p(f) \sim 9 q /10$ as $q \to \In$. Choices of $S$ with $|S| \ge 2$ give better $R_p(f)$ only for $q \gtrsim 130$, and the improvement is slight initially. (We note also that while $R_p(f)$ is the same for all choices of $S$ with $|S| =1$, $a= -b$, the precise selection of $S$ does make a slight difference for $|S| \ge 2$.) The resulting sequences for $p < 180$ are not as good (say, when judged by the value of the ratio $R_p(f) / (n+1))$ as the sequence obtained from the 13-term Barker sequence (see the discussion preceding Eq.~\eqn{eq105}), but they are better than some other sequences that have been proposed. For example, Ruprecht, Neeser, and Hufschmid \cite{RupNH} list a sequence with $n=143$ and $R_p(f) = 120.69862$. Our construction with $n=q-1=138$ and $|S|=2$ yields a value of $R_p(f) =121.32578$, so that $R_p(f)$ is higher even though $n$ is lower. (It should be mentioned, though, that the Ruprecht et~al. sequence was chosen to have a high $R_a (f)$, not a high $R_p (f)$.) The construction of Theorem~\ref{th1} produces a sequence with high $R_p (f)$ because the polynomials associated to the Legendre sequences already have the desired behavior at the points $z= \exp (2 \pi ik/q)$ for $1 \le k \le q-1$, and it is only at $z=1$ that they need to be modified. Unfortunately the behavior of these polynomials at other points on the unit circle is not as well controlled. Montgomery \cite{Montg} showed that \beql{eqZ41} \max_{|z|=1} |f(z)| > 2 \pi^{-1} q^{1/2} \log \log q \eeq for all sufficiently large $q$, and he conjectured that this bound is of the right order of magnitude. If Montgomery's conjecture is right, these polynomials will be smaller than random ones, which reach $q^{1/2} ( \log q)^{1/2}$ in size (cf.~\cite{Odl3}). However, these polynomials do have small minimal absolute values. B. Conrey and A. Granville have observed (unpublished) that the polynomial $g(z)$ of Eq.~\eqn{eq202} has $> p/2$ zeros with $|z| =1$. Therefore it is not straightforward to modify those polynomials to obtain large $R_a (f)$. The highest value of $R_a (f)$ that our construction obtains for $n=138$, $|S| \le 2$ is 28.764, while the Ruprecht et~al. sequence of \cite{RupNH} has $R_a (f) = 110.57658$. However, there are ways of modifying our construction to obtain higher values of $R_a (f)$. For example, it is known (see \cite{Odl3} for references) that cyclic shifts of the coefficients of $1+g(z)$ (with $g(z)$ given by \eqn{eq202}) produce improved values for the Golay merit factor, which measures how far $|f(z)|$ is away from $(n+1)^{1/2}$ on average as $z$ runs over $|z|=1$. (We note that cyclic shifts of coefficients of $f(z)$ do not affect the value of $R_p (f)$.) A nonexhaustive search of cyclic shifts of the sequences constructed in Section~2 with $n=138$, $|S| \le 2$, found a sequence with $R_a (f) = 110.2457$, which is better than the Ruprecht et~al. sequence of \cite{RupNH}, since the length is less. Thus modifications of our construction yield good values even for $R_a (f)$, although there is no proof that they will work for large lengths. It is also possible to try other modifications, which might yield even better results. \clearpage %\begin{thebibliography}{McGehee} \begin{thebibliography}{99} %\bibitem[Apostol]{Apostol} \bibitem{Apostol} T. M. Apostol, {\em Introduction to Analytic Number Theory}, Springer, 1976. %\bibitem[Bjorck]{Bjorck} \bibitem{Bjorck} G. Bj\"{o}rck, Functions of modulus 1 on $Z_n$ whose Fourier transforms have constant modulus, and ``cyclic $n$-roots,'' pp.~131--140 in {\em Recent Advances in Fourier Analysis and its Applications}, J.~S. Byrnes and J.~F. Byrnes, eds., Kluwer, 1990. %\bibitem[Davis]{Davis} \bibitem{Davis} P. J. Davis, {\em Circulant Matrices}, Wiley, 1979. %\bibitem[Erd]{Erd} \bibitem{Erd} P. Erd\"{o}s, Some unsolved problems, {\em Michigan Math. J. 4} (1957), 291--300. %\bibitem[Golay72]{Golay72} \bibitem{Golay72} M.~J.~E. Golay, A class of finite binary sequences with alternate autocorrelation values equal to zero, {\em IEEE Trans. Information Theory} {\em IT-18} (1972), 449--450. %\bibitem[Kahane]{Kahane} \bibitem{Kahane} J.-P. Kahane, {\em Some Random Series of Functions}, Heath, 1968. %\bibitem[Kashin2]{Kashin2} \bibitem{Kashin2} B. S. Kashin, Properties of random trigonometric polynomials with coefficients $\pm 1$, {\em Moscow Univ. Math. Bull. 42}, no.~5, (1987), 45--51. %\bibitem[Ko]{Ko} \bibitem{Ko} M.~N. Kolountzakis, On nonnegative cosine polynomials with nonnegative integral coefficients, {\em Proc. Amer. Math. Soc.}, to appear. %\bibitem[Litt]{Litt} \bibitem{Litt} J.~E. Littlewood, On polynomials $\Sigma z^m$, $\Sigma e^{\alpha mi} z^m$, $z = e^{i \theta}$ $\Sigma e^{\af mi} z^m$, $z = e^{i \theta}$, {\em J. London Math. Soc. 41} (1966), 367--376. {\em Reprinted in the Collected Papers of J.~E. Littlewood}, vol.~2, pp.~1423--1433, Oxford Univ. Press, 1982. %\bibitem[Litt2]{Litt2} \bibitem{Litt2} J.~E. Littlewood, {\em Some Problems in Real and Complex Analysis}, Heath, 1968. %\bibitem[Luke1]{Luke1} \bibitem{Luke1} H.~D. L\"{u}ke, {\em Korrelationssignale}, Springer, 1992. %\bibitem[Massey]{Massey} \bibitem{Massey} J. L. Massey, Marcel E. Golay (1902--1989), {\em IEEE Inform. Theory Newsletter}, June 1990. %\bibitem[McGehee]{McGehee} \bibitem{McGehee} O.~C. McGehee, Gaussian sums and harmonic analysis on finite fields, pp.~171--191 in Contemporary Mathematics \#91, Am. Math. Soc. 1989. %\bibitem[Montg]{Montg} \bibitem{Montg} H.~L. Montgomery, An exponential polynomial formed with the Legendre symbol, {\em Acta Arith. 37} (1980), 375--380. %\bibitem[Odl0]{Odl0} \bibitem{Odl0} A. M. Odlyzko, Minima of cosine sums and maxima of polynomials on the unit circle, {\em J. London Math. Soc. (2)}, {\em 26} (1982), 412--420. %\bibitem[Odl3]{Odl3} \bibitem{Odl3} A. M. Odlyzko, Extremal and statistical properties of trigonometric polynomials with $\pm 1$ and $0,1$ coefficients, manuscript in preparation. %\bibitem[Odl4]{Odl4} \bibitem{Odl4} A. M. Odlyzko, Minimal absolute values of random trigonometric polynomials with $\pm 1$ coefficients, manuscript in preparation. %\bibitem[Rup]{Rup} \bibitem{Rup} J. Ruprecht, Maximum-likelihood estimation of multipath channels, Ph.D. thesis, ETH, 1989. (Published by Hartung Gorre Verlag, Konstanz, Germany, 1989, ISBN 3-89191-270-6.) %\bibitem[RupNH]{RupNH} \bibitem{RupNH} J. Ruprecht, F.~D. Neeser, and M. Hufschmid, Code time division multiple access: an indoor cellular system, {\em Proc. IEEE Vehicular Techn. Conf. VTC~'92}, May 1992, pp.~1--4. %\bibitem[Schr]{Schr} \bibitem{Schr} M.~R. Schroeder, {\em Number Theory in Science and Communication}, Springer 1984. %\bibitem[WallisSW]{WallisSW} \bibitem{WallisSW} W. D. Wallis, A. P. Street, and J. S. Wallis, {\em Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices}, Lecture Notes in Math. \#292, Springer, 1972. %\bibitem[WR]{WR} \bibitem{WR} J.-P. de~Weck and J. Ruprecht, Real-time ML estimation of very frequency selective multipath channels, pp.~908.5.1--908.5.6 in {\em Proc. Globecom 1990}, (San Diego), IEEE Press, 1990. \end{thebibliography} \end{document}