Rudin-Shapiro-like polynomials in 𝐿₄

Borwein, Peter; Mossinghoff, Michael

doi:10.1090/S0025-5718-00-01221-7

Rudin-Shapiro-like polynomials in $L_{4}$
HTML articles powered by AMS MathViewer

by Peter Borwein and Michael Mossinghoff;

Math. Comp. 69 (2000), 1157-1166

DOI: https://doi.org/10.1090/S0025-5718-00-01221-7

Published electronically: March 2, 2000

PDF | Request permission

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

József Beck, The modulus of polynomials with zeros on the unit circle: a problem of Erdős, Ann. of Math. (2) 134 (1991), no. 3, 609–651. MR 1135879, DOI 10.2307/2944358
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
A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. MR 856019
P. Borwein and T. Erdélyi, Littlewood-type problems on subarcs of the unit circle, Indiana Univ. Math. J. 46 (1997), no. 4, 1323–1346. MR 1631600, DOI 10.1512/iumj.1997.46.1435
P. Borwein and T. Erdélyi, Markov-Bernstein type inequalities under Littlewood-type coefficient constraints, Indagationes, to appear.
P. Borwein and R. Lockhart, The expected $L_{p}$ norm of random polynomials, Proc. Amer. Math. Soc. (to appear).
David W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997), no. 220, 1697–1703. MR 1433263, DOI 10.1090/S0025-5718-97-00892-2
J. S. Byrnes and D. J. Newman, Null steering employing polynomials with restricted coefficients, IEEE Trans. Antennas and Propagation 36 (1988), 301–303.
F. W. Carroll, Dan Eustice, and T. Figiel, The minimum modulus of polynomials with coefficients of modulus one, J. London Math. Soc. (2) 16 (1977), no. 1, 76–82. MR 480955, DOI 10.1112/jlms/s2-16.1.76
J. Clunie, The minimum modulus of a polynomial on the unit circle, Quart. J. Math. Oxford Ser. (2) 10 (1959), 95–98. MR 106271, DOI 10.1093/qmath/10.1.95
P. Erdős, An inequality for the maximum of trigonometric polynomials, Ann. Polon. Math. 12 (1962), 151–154. MR 141933, DOI 10.4064/ap-12-2-151-154
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 280689, DOI 10.1112/blms/2.3.301
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.
Jørn M. Jensen, Helge Elbrønd Jensen, and Tom Høholdt, The merit factor of binary sequences related to difference sets, IEEE Trans. Inform. Theory 37 (1991), no. 3, 617–626. MR 1145821, DOI 10.1109/18.79917
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
Jean-Pierre Kahane, Some random series of functions, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 5, Cambridge University Press, Cambridge, 1985. MR 833073
S. V. Konyagin, On the Littlewood problem, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 2, 243–265, 463 (Russian). MR 616222
J. E. Littlewood, On the mean values of certain trigonometric polynomials, J. London Math. Soc. 36 (1961), 307–334. MR 141934, DOI 10.1112/jlms/s1-36.1.307
J. E. Littlewood, On polynomials $\sum ^{n}\pm z^{m}$, $\sum ^{n}e^{\alpha _{m}i}z^{m}$, $z=e^{\theta _{i}}$, J. London Math. Soc. 41 (1966), 367–376. MR 196043, DOI 10.1112/jlms/s1-41.1.367
Bruno Šubert, An asymptotically optimal decision procedure, Trans. Fourth Prague Conf. on Information Theory, Statistical Decision Functions, Random Processes (Prague, 1965) Academia [Publishing House of the Czechoslovak Academy of Sciences], Prague, 1967, pp. 573–587. MR 230415
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
Albert Nijenhuis and Herbert S. Wilf, Combinatorial algorithms, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 396274
A. Reinholz, Ein paralleler genetische Algorithmus zur Optimierung der binären Autokorrelations-Funktion, Diplomarbeit, Rheinische Friedrich-Wilhelms-Universität Bonn, 1993.
Michael L. Fredman, Bahman Saffari, and Brent Smith, Polynômes réciproques: conjecture d’Erdős en norme $L^4,$ taille des autocorrélations et inexistence des codes de Barker, C. R. Acad. Sci. Paris Sér. I Math. 308 (1989), no. 15, 461–464 (French, with English summary). MR 994692
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
Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946