Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48 .

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Explicit merit factor formulae for Fekete and Turyn polynomials
HTML articles powered by AMS MathViewer

by Peter Borwein and Kwok-Kwong Stephen Choi PDF
Trans. Amer. Math. Soc. 354 (2002), 219-234

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 \[ f_{q}(z) := \sum ^{q-1}_{k=1} \left (\frac {k}{q}\right ) z^{k} \] where $\left (\frac {\cdot }{q}\right )$ is the Legendre symbol. For example for $q$ an odd prime, \[ \|f_{q}\|_{4}^{4} : = \frac {5q^{2}}{3}-3q+ \frac {4}{3} - 12 (h(-q))^{2} \] 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, \[ R_{q}(z) := \sum ^{q-1}_{k=0} \left (\frac {k+[q/4] }{q}\right ) z^{k} \] where $[\cdot ]$ denotes the nearest integer, satisfies \[ \|R_{q}\|_{4}^{4} = \frac {7q^{2}}{6}- {q} - \frac {1}{6} - \gamma _{q} \] where \[ \gamma _{q}: = \begin {cases} h(-q) (h(-q)-4) & \text {if $q \equiv 1,5 \pmod 8$},\\ 12 (h(-q))^{2} & \text {if $q \equiv 3 \pmod 8$}, \\ 0 & \text {if $q \equiv 7 \pmod 8$}. \end {cases} \] Indeed we derive a closed form for the $L_{4}$ norm of all shifted Fekete polynomials \[ f_{q}^{t}(z) := \sum ^{q-1}_{k=0} \left (\frac {k+t}{q}\right ) z^{k}. \] Namely \begin{align*} \| f_{q}^{t} \|_{4}^{4} &= \frac {1}{3}(5q^{2}+3q+4)+8t^{2}-4qt-8t &\quad -\frac {8}{q^{2}}\left ( 1-\frac {1}{2} \left (\frac {-1}{q}\right ) \right ) \left |{\displaystyle \sum _{n=1}^{q-1}n \left (\frac {n+t}{q}\right )} \right |^{2}, \end{align*} and $\| f_{q}^{q-t+1} \|_{4}^{4}= \| f_{q}^{t} \|_{4}^{4}$ if $1 \le t \le (q+1)/2$.
References
  • 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, DOI 10.1112/blms/23.3.269
  • 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
  • P. Borwein and K.K. Choi, Merit Factors for Character Polynomials, Journal of the London Mathematical Society, (2) 61 (2000), no. 3, 706-720.
  • P. Borwein and K.K. Choi, Merit Factors of Polynomials formed by Jacobi Symbols, Canadian Journal of Mathematics 53 (2001), no. 1, 33-50.
  • P. Borwein and R. Lockhart, The expected $L_{p}$ norm of random polynomials, Proc. Amer. Math. Soc. 129 (2001), 1463-1472.
  • Peter Borwein and Michael Mossinghoff, Rudin-Shapiro-like polynomials in $L_4$, Math. Comp. 69 (2000), no. 231, 1157–1166. MR 1709147, DOI 10.1090/S0025-5718-00-01221-7
  • B. Conrey, A. Granville, B. Poonen and K. Soundararajan, Zeros of Fekete polynomials, Annales Institut Fourier (Grenoble) 50 (2000), no. 3, 865–889.
  • M. J. Golay, Sieves for low autocorrelation binary sequences, IEEE Trans. Inform. Theory 23 (1977), 43–51.
  • M. J. Golay, The merit factor of Legendre sequences, IEEE Trans. Inform. Theory 29 (1983), 934–936.
  • T. Høholdt and H. Jensen, Determination of the merit factor of Legendre sequences, IEEE Trans. Inform. Theory 34 (1988), 161–164.
  • Loo Keng Hua, Introduction to number theory, Springer-Verlag, Berlin-New York, 1982. Translated from the Chinese by Peter Shiu. MR 665428, DOI 10.1007/978-3-642-68130-1
  • Wen Liu, Some properties of the relative entropy density of arbitrary information source, Chinese Sci. Bull. 35 (1990), no. 11, 888–892. MR 1071841
  • Jean-Pierre Kahane, Sur les polynômes à coefficients unimodulaires, Bull. London Math. Soc. 12 (1980), no. 5, 321–342 (French). MR 587702, DOI 10.1112/blms/12.5.321
  • John E. Littlewood, Some problems in real and complex analysis, D. C. Heath and Company Raytheon Education Company, Lexington, Mass., 1968. MR 0244463
  • S. Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A 29 (1996), no. 18, L473–L481. MR 1419192, DOI 10.1088/0305-4470/29/18/005
  • Hugh L. Montgomery, An exponential polynomial formed with the Legendre symbol, Acta Arith. 37 (1980), 375–380. MR 598890, DOI 10.4064/aa-37-1-375-380
  • Donald J. Newman and J. S. Byrnes, The $L^4$ norm of a polynomial with coefficients $\pm 1$, Amer. Math. Monthly 97 (1990), no. 1, 42–45. MR 1034349, DOI 10.2307/2324003
  • A. Reinholz, Ein paralleler genetische Algorithmus zur Optimierung der binären Autokorrelations-Funktion, Diplomarbeit, Rheinische Friedrich-Wilhelms-Universität Bonn, 1993.
  • B. Saffari, Barker sequences and Littlewood’s “two-sided conjectures” on polynomials with $\pm 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
  • 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
  • © Copyright 2001 by the authors
  • 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
  • MathSciNet review: 1859033