Available in electronic format
Available in print format		 Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Explicit merit factor formulae for Fekete and Turyn polynomials

Author(s): Peter Borwein; Kwok-Kwong Stephen Choi
Journal: Trans. Amer. Math. Soc. 354 (2002), 219-234.
MSC (1991): Primary 11J54, 11B83, 12-04
Posted: August 20, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: We give explicit formulas for the $L_{4}$ norm (or equivalently for the merit factors) of various sequences of polynomials related to the Fekete polynomials

\begin{displaymath}f_{q}(z) := \sum ^{q-1}_{k=1} \left (\frac{k}{q}\right ) z^{k} \end{displaymath}

where $\left (\frac{\cdot }{q}\right )$ is the Legendre symbol. For example for $q$ an odd prime,

\begin{displaymath}\Vert f_{q}\Vert _{4}^{4} : = \frac{5q^{2}}{3}-3q+ \frac{4}{3} - 12 (h(-q))^{2} \end{displaymath}

where $h(-q)$ is the class number of $\mathbb{Q}(\sqrt {-q})$. Similar explicit formulas are given for various polynomials including an example of Turyn's that is constructed by cyclically permuting the first quarter of the coefficients of $f_{q}$. This is the sequence that has the largest known asymptotic merit factor. Explicitly,

\begin{displaymath}R_{q}(z) := \sum ^{q-1}_{k=0} \left (\frac{k+[q/4] }{q}\right ) z^{k} \end{displaymath}

where $[\cdot ]$ denotes the nearest integer, satisfies

\begin{displaymath}\Vert R_{q}\Vert _{4}^{4} = \frac{7q^{2}}{6}- {q} - \frac{1}{6} - \gamma _{q} \end{displaymath}

where

\begin{displaymath}\gamma _{q}: = \begin{cases} h(-q) (h(-q)-4) & \text{if} \qu... ...pmod 8, 0 & \text{if} \quad q \equiv 7 \pmod 8. \end{cases}\end{displaymath}

Indeed we derive a closed form for the $L_{4}$ norm of all shifted Fekete polynomials

\begin{displaymath}f_{q}^{t}(z) := \sum ^{q-1}_{k=0} \left (\frac{k+t}{q}\right ) z^{k}. \end{displaymath}

Namely
\begin{align*}\Vert f_{q}^{t} \Vert _{4}^{4} &= \frac{1}{3}(5q^{2}+3q+4)+8t^{2}-... ...tyle \sum _{n=1}^{q-1}n\left(\frac{n+t}{q}\right)}\right \vert^{2}, \end{align*}
and $\Vert f_{q}^{q-t+1} \Vert _{4}^{4}= \Vert f_{q}^{t} \Vert _{4}^{4}$ if $1 \le t \le (q+1)/2$.

References:

[Be-91]
J. Beck, Flat polynomials on the unit circle - note on a problem of Littlewood, Bull. London Math. Soc. 23 (1991), 269-277. MR 93b:42002

[Bo-98]
P. Borwein, Some Old Problems on Polynomials with Integer Coefficients, Approximation theory IX Vol. I. (Nashville, TN, 1998), 31-50. MR 2001b:41004

[BC-00]
P. Borwein and K.K. Choi, Merit Factors for Character Polynomials, Journal of the London Mathematical Society, (2) 61 (2000), no. 3, 706-720. CMP 2000:14

[BC-01]
P. Borwein and K.K. Choi, Merit Factors of Polynomials formed by Jacobi Symbols, Canadian Journal of Mathematics 53 (2001), no. 1, 33-50. CMP 2001:08

[BL-0]
P. Borwein and R. Lockhart, The expected $L_{p}$ norm of random polynomials, Proc. Amer. Math. Soc. 129 (2001), 1463-1472. CMP 2001:08

[BM-00]
P. Borwein and M. Mossinghoff, Rudin-Shapiro like Polynomials in $L_{4}$, Math. Comp. 69 (2000), 1157-1166. MR 2000j:11100

[CGPS-98]
B. Conrey, A. Granville, B. Poonen and K. Soundararajan, Zeros of Fekete polynomials, Annales Institut Fourier (Grenoble) 50 (2000), no. 3, 865-889. CMP 2000:17

[Go-77]
M. J. Golay, Sieves for low autocorrelation binary sequences, IEEE Trans. Inform. Theory 23 (1977), 43-51.

[Go-83]
M. J. Golay, The merit factor of Legendre sequences, IEEE Trans. Inform. Theory 29 (1983), 934-936.

[Hø-88]
T. Høholdt and H. Jensen, Determination of the merit factor of Legendre sequences, IEEE Trans. Inform. Theory 34 (1988), 161-164.

[Hu-82]
L. K. Hua, Introduction to Number Theory, Springer-Verlag, Berlin, 1982. MR 83f:10001

[Je-91]
J. Jensen, H. Jensen and T. Høholdt, The merit factor of binary sequences related to difference sets, IEEE Trans. Inform. Theory 37 (1991), 617-626. MR 92f:94009

[Ka-80]
J-P. Kahane, Sur les polynômes á coefficients unimodulaires, Bull. London Math. Soc. 12 (1980), 321-342. MR 82a:30003

[Li-68]
J. E. Littlewood, Some Problems in Real and Complex Analysis, Heath Mathematical Monographs, Lexington, Massachusetts, 1968. MR 39:5777

[Me-96]
S. Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A 29 (1996), L473-L481. MR 97i:82050

[Mo-80]
H. L. Montgomery, An exponential polynomial formed with the Legendre symbol, Acta Arith. 37 (1980), 375-380. MR 82a:10041

[Ne-90]
D. J. Newman and J. S. Byrnes, The $L^{4}$ norm of a polynomial with coefficients $\pm 1$, Amer. Math. Monthly 97 (1990), 42-45. MR 91d:30006

[Re-93]
A. Reinholz, Ein paralleler genetische Algorithmus zur Optimierung der binären Autokorrelations-Funktion, Diplomarbeit, Rheinische Friedrich-Wilhelms-Universität Bonn, 1993.

[Saf-90]
B. Saffari, Barker sequences and Littlewood's ``two-sided conjectures'' on polynomials with $\pm 1$ coefficients, Séminaire d'Analyse Harmonique. Anneé 1989/90, 139-151, Univ. Paris XI, Orsay, 1990. MR 92i:11032

Similar Articles:

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 11J54, 11B83, 12-04

Retrieve articles in all Journals with MSC (1991): 11J54, 11B83, 12-04

Additional Information:

Peter Borwein
Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

Kwok-Kwong Stephen Choi
Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

DOI: 10.1090/S0002-9947-01-02859-8
PII: S 0002-9947(01)02859-8
Keywords: Class number, $-1,1$ coefficients, merit factor, Fekete polynomials, Turyn polynomials, Littlewood polynomials
Received by editor(s): April 24, 2000
Posted: August 20, 2001
Additional Notes: Research of P. Borwein is supported, in part, by NSERC of Canada. K.K. Choi is a Pacific Institute of Mathematics Postdoctoral Fellow and the Institute's support is gratefully acknowledged
Copyright of article: Copyright 2001, by the authors

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google