Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Littlewood polynomials with high order zeros


Authors: Daniel Berend and Shahar Golan
Journal: Math. Comp. 75 (2006), 1541-1552
MSC (2000): Primary 11B83, 12D10; Secondary 94B05, 11Y99
DOI: https://doi.org/10.1090/S0025-5718-06-01848-5
Published electronically: May 1, 2006
MathSciNet review: 2219044
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ N^{*}(m)$ be the minimal length of a polynomial with $ \pm1$ coefficients divisible by $ (x-1)^m$. Byrnes noted that $ N^{*}(m)\leq2^m$ for each $ m$, and asked whether in fact $ N^{*}(m)=2^m$. Boyd showed that $ N^{*}(m) = 2^{m}$ for all $ m \le 5$, but $ N^{*}(6) = 48$. He further showed that $ N^*(7)=96$, and that $ N^{*}(8)$ is one of the 5 numbers $ 96, 144, 160, 176$, or $ 192$. Here we prove that $ N^{*}(8) = 144$. Similarly, let $ m^*(N)$ be the maximal power of $ (x-1)$ dividing some polynomial of degree $ N-1$ with $ \pm1$ coefficients. Boyd was able to find $ m^*(N)$ for $ N<88$. In this paper we determine $ m^*(N)$ for $ N<168$.


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

  • 1. J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences and their applications, Proceedings of SETA'98 (C. Ding, T. Helleseth & H. Niederreiter, eds.), Spinger-Verlag, 1999, pp. 1-16. MR 1843077 (2002e:11025)
  • 2. D.W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997), 1697-1703.MR 1433263 (98a:11033)
  • 3. D.W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, II, Math. Comp. 71 (2002), 1205-1217.MR 1898751 (2003d:11035)
  • 4. J.S. Byrnes, Problems on polynomials with restricted coefficients arising from questions in antenna array theory, Recent Advances in Fourier Analysis and Its Applications (J.S. Byrnes & J.F. Byrnes, eds.), Kluwer Academic Publishers, Dordrecht, 1990, pp. 677-678. MR 1081341 (91g:42001)
  • 5. J.S. Byrnes and D.J. Newman, Null steering employing polynomials with restricted coefficients, IEEE Trans. Antennas and Propagation 36 (1988), 301-303.
  • 6. S. Golan, http://www.cs.bgu.ac.il/ golansha/polynomials http://www.cs.bgu.ac.il/$ \sim$golansha/polynomials.
  • 7. R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, 1983. MR 0746963 (86c:11106)
  • 8. V. Skachek, T. Etzion, and R.M. Roth, Efficient encoding algorithm for third-order spectral-null codes, IEEE Trans. Inform. Theory 44 (1998), 846-851.MR 1607751 (98k:94017)
  • 9. A. Nijenhuis and H.S. Wilf, Combinatorial Algorithms, Academic Press, Orlando, 1978.MR 0510047 (80a:68076)
  • 10. R.M. Roth, P.H. Siegel, and A. Vardy, High-order spectral-null codes: Constructions and bounds, IEEE Trans. Inform. Theory 35 (1989), 463-472.
  • 11. R.M. Roth, Spectral-null codes and null spaces of Hadamard submatrices, Designs, Codes and Cryptography 9 (1996), 177-191. MR 1409444 (98e:94034)
  • 12. L. C. Washington, Introduction to Cyclotomic Fields, Springer, New York (1982). MR 0718674 (85g:11001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B83, 12D10, 94B05, 11Y99

Retrieve articles in all journals with MSC (2000): 11B83, 12D10, 94B05, 11Y99


Additional Information

Daniel Berend
Affiliation: Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva 84105 Israel
Email: berend@cs.bgu.ac.il

Shahar Golan
Affiliation: Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva 84105 Israel
Email: golansha@cs.bgu.ac.il

DOI: https://doi.org/10.1090/S0025-5718-06-01848-5
Keywords: Littlewood polynomials, spectral-null code, antenna array
Received by editor(s): May 5, 2005
Received by editor(s) in revised form: June 30, 2005
Published electronically: May 1, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society