Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

   
 
 

 

Explicit merit factor formulae for Fekete and Turyn polynomials


Authors: Peter Borwein and Kwok-Kwong Stephen Choi
Journal: Trans. Amer. Math. Soc. 354 (2002), 219-234
MSC (1991): Primary 11J54, 11B83, 12-04
DOI: https://doi.org/10.1090/S0002-9947-01-02859-8
Published electronically: August 20, 2001
MathSciNet review: 1859033
Full-text PDF Free Access

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 [Enhancements On Off] (What's this?)

  • [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: https://doi.org/10.1090/S0002-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
Published electronically: 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
Article copyright: © Copyright 2001 by the authors

American Mathematical Society