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

Abstract | References | Similar Articles | Additional Information

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

where is the Legendre symbol. For example for an odd prime,

where is the class number of . 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 . This is the sequence that has the largest known asymptotic merit factor. Explicitly,

where denotes the nearest integer, satisfies

where

Indeed we derive a closed form for the norm of all shifted Fekete polynomials

Namely

and if .

**[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**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*, 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**norm of a polynomial with coefficients*, 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**coefficients*, Séminaire d'Analyse Harmonique. Anneé 1989/90, 139-151, Univ. Paris XI, Orsay, 1990. MR**92i:11032**

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