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