Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On a problem of Byrnes concerning polynomials with restricted coefficients, II

Author: David W. Boyd
Journal: Math. Comp. 71 (2002), 1205-1217
MSC (2000): Primary 11C08, 12D10; Secondary 94B05, 11Y99
Published electronically: May 11, 2001
MathSciNet review: 1898751
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


As in the earlier paper with this title, we consider a question of Byrnes concerning the minimal length $N^{*}(m)$ of a polynomial with all coefficients in $\{-1,1\}$ which has a zero of a given order $m$ at $x = 1$. In that paper we showed that $N^{*}(m) = 2^{m}$ for all $m \le 5$ and showed that the extremal polynomials for were those conjectured by Byrnes, but for $m = 6$ that $N^{*}(6) = 48$ rather than $64$. A polynomial with $N = 48$ was exhibited for $m = 6$, but it was not shown there that this extremal was unique. Here we show that the extremal is unique. In the previous paper, we showed that $N^{*}(7)$ is one of the 7 values $48, 56, 64, 72, 80, 88$ or $96$. Here we prove that $N^{*}(7) = 96$ without determining all extremal polynomials. We also make some progress toward determining $N^{*}(8)$. As in the previous paper, we use a combination of number theoretic ideas and combinatorial computation. The main point is that if $\zeta _{p}$ is a primitive $p$th root of unity where $p \le m+1$ is a prime, then the condition that all coefficients of $P$ be in $\{-1,1\}$, together with the requirement that $P(x)$be divisible by $(x-1)^{m}$ puts severe restrictions on the possible values for the cyclotomic integer $P(\zeta _{p})$.

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

  • [BM] P. Borwein and M. Mossinghoff, Polynomials with height $1$and prescribed vanishing at $1$, Experiment. Math. 9 (2000), 425-433. CMP 2001:04
  • [Bo] David W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997), no. 220, 1697–1703. MR 1433263,
  • [By] 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 and J.F. Byrnes, eds.), Kluwer Academic Publishers, Dordrecht, 1990, pp. 677-678.
  • [E] Harold M. Edwards, Fermat’s last theorem, Graduate Texts in Mathematics, vol. 50, Springer-Verlag, New York-Berlin, 1977. A genetic introduction to algebraic number theory. MR 616635
    Harold M. Edwards, \cyr Poslednyaya teorema Ferma, “Mir”, Moscow, 1980 (Russian). \cyr Geneticheskoe vvedenie v algebraicheskuyu teoriyu chisel. [A genetic introduction to algebraic number theory]; Translated from the English by V. L. Kalinin and A. I. Skopin. MR 616636
  • [FL] Gregory Freiman and Simon Litsyn, Asymptotically exact bounds on the size of high-order spectral-null codes, IEEE Trans. Inform. Theory 45 (1999), no. 6, 1798–1807. MR 1720633,
  • [LN] Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
  • [NW] Albert Nijenhuis and Herbert S. Wilf, Combinatorial algorithms, 2nd ed., Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. For computers and calculators; Computer Science and Applied Mathematics. MR 510047
  • [RSV] 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.
  • [R] Ron M. Roth, Spectral-null codes and null spaces of Hadamard submatrices, Des. Codes Cryptogr. 9 (1996), no. 2, 177–191. MR 1409444,
  • [S] V. Skachek, Coding for Spectral-Null Constraints, Research Thesis, Master of Science in Computer Science, Technion, Israel Institute of Technology, November 1997 (Hebrew).

Similar Articles

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

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

Additional Information

David W. Boyd
Affiliation: Department of Mathematics, University of British Columbia, Vancouver, B.C., Canada V6T 1Z2

Keywords: Polynomial, zero, spectral-null code
Received by editor(s): September 8, 1997
Received by editor(s) in revised form: September 19, 2000
Published electronically: May 11, 2001
Additional Notes: This research was supported by a grant from NSERC
Article copyright: © Copyright 2001 American Mathematical Society