|
Rudin-Shapiro-like polynomials in 
Authors:
Peter Borwein and Michael Mossinghoff
Journal:
Math. Comp. 69 (2000), 1157-1166
MSC (1991):
Primary 11J54, 11B83, 12-04
Posted:
March 2, 2000
MathSciNet review:
1709147
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We examine sequences of polynomials with coefficients constructed using the iterations , where is the degree of and is the reciprocal polynomial of . If these generate the Rudin-Shapiro polynomials. We show that the norm of these polynomials is explicitly computable. We are particularly interested in the case where the iteration produces sequences with smallest possible asymptotic norm (or, equivalently, with largest possible asymptotic merit factor). The Rudin-Shapiro polynomials form one such sequence. We determine all 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 of degree 19.
- 1.
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
(93e:11091), http://dx.doi.org/10.2307/2944358
- 2.
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
(93b:42002), http://dx.doi.org/10.1112/blms/23.3.269
- 3.
A.
T. Bharucha-Reid and M.
Sambandham, Random polynomials, Probability and Mathematical
Statistics, Academic Press Inc., Orlando, FL, 1986. MR 856019
(87m:60118)
- 4.
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
(99j:30004), http://dx.doi.org/10.1512/iumj.1997.46.1435
- 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
norm of random polynomials, Proc. Amer. Math. Soc. (to appear).
- 7.
David
W. Boyd, On a problem of Byrnes concerning
polynomials with restricted coefficients, Math.
Comp. 66 (1997), no. 220, 1697–1703. MR 1433263
(98a:11033), http://dx.doi.org/10.1090/S0025-5718-97-00892-2
- 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, 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 0480955
(58 #1102)
- 10.
J.
Clunie, The minimum modulus of a polynomial on the unit
circle, Quart. J. Math. Oxford Ser. (2) 10 (1959),
95–98. MR
0106271 (21 #5005)
- 11.
P.
Erdős, An inequality for the maximum of trigonometric
polynomials, Ann. Polon. Math. 12 (1962),
151–154. MR 0141933
(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 0280689
(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ø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
(92j:94009), http://dx.doi.org/10.1109/18.79917
- 17.
Jean-Pierre
Kahane, Sur les polynômes à coefficients
unimodulaires, Bull. London Math. Soc. 12 (1980),
no. 5, 321–342 (French). MR 587702
(82a:30003), http://dx.doi.org/10.1112/blms/12.5.321
- 18.
Jean-Pierre
Kahane, Some random series of functions, 2nd ed., Cambridge
Studies in Advanced Mathematics, vol. 5, Cambridge University Press,
Cambridge, 1985. MR 833073
(87m:60119)
- 19.
S.
V. Konyagin, On the Littlewood problem, Izv. Akad. Nauk SSSR
Ser. Mat. 45 (1981), no. 2, 243–265, 463
(Russian). MR
616222 (83d:10045)
- 20.
J.
E. Littlewood, On the mean values of certain trigonometric
polynomials, J. London Math. Soc. 36 (1961),
307–334. MR 0141934
(25 #5331a)
- 21.
J.
E. Littlewood, On polynomials
∑ⁿ±𝑧^{𝑚},
∑ⁿ𝑒^{𝛼_{𝑚}𝑖}𝑧^{𝑚},
𝑧=𝑒^{𝜃ᵢ}, J. London Math. Soc.
41 (1966), 367–376. MR 0196043
(33 #4237)
- 22.
Bruno
Šubert, An asymptotically optimal decision procedure,
Functions, Random Processes (Prague, 1965) Academia, Prague, 1967,
pp. 573–587. MR 0230415
(37 #5977)
- 23.
S.
Mertens, Exhaustive search for low-autocorrelation binary
sequences, J. Phys. A 29 (1996), no. 18,
L473–L481. MR 1419192
(97i:82050), http://dx.doi.org/10.1088/0305-4470/29/18/005
- 24.
Hugh
L. Montgomery, An exponential polynomial formed with the Legendre
symbol, Acta Arith. 37 (1980), 375–380. MR 598890
(82a:10041)
- 25.
Donald
J. Newman and J.
S. Byrnes, The 𝐿⁴ norm of a polynomial with
coefficients ±1, Amer. Math. Monthly 97
(1990), no. 1, 42–45. MR 1034349
(91d:30006), http://dx.doi.org/10.2307/2324003
- 26.
Albert
Nijenhuis and Herbert
S. Wilf, Combinatorial algorithms, Academic Press [Harcourt
Brace Jovanovich Publishers], New York, 1975. Computer Science and Applied
Mathematics. MR
0396274 (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.
Michael
L. Fredman, Bahman
Saffari, and Brent
Smith, Polynômes réciproques: conjecture
d’Erdős en norme 𝐿⁴, 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
(90c:42004)
- 29.
B.
Saffari, Barker sequences and Littlewood’s “two-sided
conjectures” on polynomials with ±1 coefficients,
Séminaire d’Analyse Harmonique. Année 1989/90, Univ.
Paris XI, Orsay, 1990, pp. 139–151. MR 1104693
(92i:11032)
- 30.
R.
Salem and A.
Zygmund, Some properties of trigonometric series whose terms have
random signs, Acta Math. 91 (1954), 245–301. MR 0065679
(16,467b)
- 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
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
and , , 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
norm of a polynomial with coefficients , 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
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
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
Email:
pborwein@cecm.sfu.ca
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
Email:
mjm@math.ucla.edu
DOI:
http://dx.doi.org/10.1090/S0025-5718-00-01221-7
PII:
S 0025-5718(00)01221-7
Keywords:
Restricted coefficients; $-1,0,1$ coefficients; Rudin-Shapiro polynomials; Littlewood conjectures
Received by editor(s):
April 14, 1998
Posted:
March 2, 2000
|