Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Rudin-Shapiro-like polynomials in $L_{4}$

Authors: Peter Borwein and Michael Mossinghoff
Journal: Math. Comp. 69 (2000), 1157-1166
MSC (1991): Primary 11J54, 11B83, 12-04
Published electronically: March 2, 2000
MathSciNet review: 1709147
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We examine sequences of polynomials with $\{+1,-1\}$ coefficients constructed using the iterations $p(x)\rightarrow p(x)\pm x^{d+ 1}p^{*}(-x)$, where $d$ is the degree of $p$ and $p^{*}$ is the reciprocal polynomial of $p$. If $p_{0}=1$ these generate the Rudin-Shapiro polynomials. We show that the $L_{4}$ norm of these polynomials is explicitly computable. We are particularly interested in the case where the iteration produces sequences with smallest possible asymptotic $L_{4}$ norm (or, equivalently, with largest possible asymptotic merit factor). The Rudin-Shapiro polynomials form one such sequence.

We determine all $p_{0}$ of degree less than 40 that generate sequences under the iteration with this property. These sequences have asymptotic merit factor 3. The first really distinct example has a $p_{0}$ of degree 19.

References [Enhancements On Off] (What's this?)

  • 1. J. Beck, The modulus of polynomials with zeros on the unit circle: A problem of Erdös, Ann. of Math. (2) 134 (1991), 609-651. MR 93e:11091
  • 2. 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
  • 3. A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, Orlando, 1986. MR 87m:60118
  • 4. P. Borwein and T. Erdélyi, Littlewood-type problems on subarcs of the unit circle, Indiana Univ. Math. J. 46 (1997), 1323-1346. MR 99j:30004
  • 5. P. Borwein and T. Erdélyi, Markov-Bernstein type inequalities under Littlewood-type coefficient constraints, Indagationes, to appear.
  • 6. P. Borwein and R. Lockhart, The expected $L_{p}$ norm of random polynomials, Proc. Amer. Math. Soc. (to appear).
  • 7. D. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997), 1697-1703. MR 98a:11033
  • 8. J. S. Byrnes and D. J. Newman, Null steering employing polynomials with restricted coefficients, IEEE Trans. Antennas and Propagation 36 (1988), 301-303.
  • 9. F. W. Carroll, D. Eustice and T. Figiel, The minimum modulus of polynomials with coefficients of modulus one, J. London Math. Soc. 16 (1977), 76-82. MR 58:1102
  • 10. J. Clunie, On the minimum modulus of a polynomial on the unit circle, Quart. J. Math. 10 (1959), 95-98. MR 21:5005
  • 11. P. Erdos, An inequality for the maximum of trigonometric polynomials, Annales Polonica Math. 12 (1962), 151-154. MR 25:5330
  • 12. G. T. Fielding, The expected value of the integral around the unit circle of a certain class of polynomials, Bull. London Math. Soc. 2 (1970), 301-306. MR 43:6408
  • 13. M. J. Golay, Sieves for low autocorrelation binary sequences, IEEE Trans. Inform. Theory 23 (1977), 43-51.
  • 14. M. J. Golay, The merit factor of Legendre sequences, IEEE Trans. Inform. Theory 29 (1983), 934-936.
  • 15. T. Høholdt and H. Jensen, Determination of the merit factor of Legendre sequences, IEEE Trans. Inform. Theory 34 (1988), 161-164.
  • 16. 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 92j:94009
  • 17. J-P. Kahane, Sur les polynômes á coefficients unimodulaires, Bull. London Math. Soc. 12 (1980), 321-342. MR 82a:30003
  • 18. J-P. Kahane, Some Random Series of Functions, Cambridge Stud. Adv. Math., vol. 5, Cambridge, 2nd ed. MR 87m:60119
  • 19. S. Konjagin, On a problem of Littlewood, Izv. A. N. SSSR, ser. mat. 45, 2 (1981), 243-265; English transl., Math. USSR Izv. 18 (1982), 205-225. MR 83d:10045
  • 20. J. E. Littlewood, On the mean value of certain trigonometric polynomials, J. London Math. Soc. 36 (1961), 307-334. MR 25:5331a
  • 21. J. E. Littlewood, On polynomials $\sum ^{n} \pm z^{m}$ and $\sum ^{n} e^{\alpha _{m}i} z^{m}$, $z=e^{\theta i}$, J. London Math. Soc. 41 (1966), 367-376. MR 33:4237
  • 22. J. E. Littlewood, Some Problems in Real and Complex Analysis, Heath Mathematical Monographs, Lexington, Massachusetts, 1968. MR 37:5977
  • 23. S. Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A 29 (1996), L473-L481. MR 97i:82050
  • 24. H. L. Montgomery, An exponential sum formed with the Legendre symbol, Acta Arith. 37 (1980), 375-380. MR 82a:10041
  • 25. D. J. Newman and J. S. Byrnes, The $L^{4}$ norm of a polynomial with coefficients $\pm 1$, Amer. Math. Monthly 97 (1990), 42-45. MR 91d:30006
  • 26. A. Nijenhuis and H. S. Wilf, Combinatorial Algorithms, Academic Press, New York, 1975. MR 53:142
  • 27. A. Reinholz, Ein paralleler genetische Algorithmus zur Optimierung der binären Autokorrelations-Funktion, Diplomarbeit, Rheinische Friedrich-Wilhelms-Universität Bonn, 1993.
  • 28. B. Saffari, Polynômes réciproques: conjecture d'Erdos en norme $L\sp{4},$ taille des autocorrélations et inexistence des codes de Barker, C. R. Acad. Sci. Paris Sér. I Math. 308 (1989), 461-464. MR 90c:42004
  • 29. B. Saffari, Barker sequences and Littlewood's ``two-sided conjectures'' on polynomials with $\pm 1$ coefficients, Séminaire d'Analyse Harmonique. Anneé 1989/90, 139-151, Univ. Paris XI, Orsay, 1990. MR 92i:11032
  • 30. R. Salem and A. Zygmund, Some properties of trigonometric series whose terms have random signs, Acta Math. 91 (1954), 254-301. MR 16:467b

Similar Articles

Retrieve articles in Mathematics of Computation 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

Michael Mossinghoff
Affiliation: Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608
Address at time of publication: Department of Mathematics, UCLA, Los Angeles, California 90095

Keywords: Restricted coefficients; $-1,0,1$ coefficients; Rudin-Shapiro polynomials; Littlewood conjectures
Received by editor(s): April 14, 1998
Published electronically: March 2, 2000

American Mathematical Society