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
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ózsef Beck, Flat polynomials on the unit circle—note on a problem of Littlewood, Bull. London Math. Soc. 23 (1991), no. 3, 269–277. MR 1123337, 10.1112/blms/23.3.269
  • [Bo-98] Peter Borwein, Some old problems on polynomials with integer coefficients, Approximation theory IX, Vol. I. (Nashville, TN, 1998) Innov. Appl. Math., Vanderbilt Univ. Press, Nashville, TN, 1998, pp. 31–50. MR 1742989
  • [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] Peter Borwein and Michael Mossinghoff, Rudin-Shapiro-like polynomials in 𝐿₄, Math. Comp. 69 (2000), no. 231, 1157–1166. MR 1709147, 10.1090/S0025-5718-00-01221-7
  • [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] Loo Keng Hua, Introduction to number theory, Springer-Verlag, Berlin-New York, 1982. Translated from the Chinese by Peter Shiu. MR 665428
  • [Je-91] Wen Liu, Some properties of the relative entropy density of arbitrary information source, Chinese Sci. Bull. 35 (1990), no. 11, 888–892. MR 1071841
  • [Ka-80] Jean-Pierre Kahane, Sur les polynômes à coefficients unimodulaires, Bull. London Math. Soc. 12 (1980), no. 5, 321–342 (French). MR 587702, 10.1112/blms/12.5.321
  • [Li-68] John E. Littlewood, Some problems in real and complex analysis, D. C. Heath and Co. Raytheon Education Co., Lexington, Mass., 1968. MR 0244463
  • [Me-96] S. Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A 29 (1996), no. 18, L473–L481. MR 1419192, 10.1088/0305-4470/29/18/005
  • [Mo-80] Hugh L. Montgomery, An exponential polynomial formed with the Legendre symbol, Acta Arith. 37 (1980), 375–380. MR 598890
  • [Ne-90] Donald J. Newman and J. S. Byrnes, The 𝐿⁴ norm of a polynomial with coefficients ±1, Amer. Math. Monthly 97 (1990), no. 1, 42–45. MR 1034349, 10.2307/2324003
  • [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 ±1 coefficients, Séminaire d’Analyse Harmonique. Année 1989/90, Univ. Paris XI, Orsay, 1990, pp. 139–151. MR 1104693

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