## 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**

## 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