Littlewood polynomials, spectral-null codes, and equipowerful partitions
HTML articles powered by AMS MathViewer
- by Joe Buhler, Shahar Golan, Rob Pratt and Stan Wagon HTML | PDF
- Math. Comp. 90 (2021), 1435-1453 Request permission
Abstract:
Let $[n]$ denote $\{0,1, ... , n-1\}$. A polynomial $f(x) = \sum a_i x^i$ is a Littlewood polynomial (LP) of length $n$ if the $a_i$ are $\pm 1$ for $i \in [n]$, and $a_i = 0$ for $i \ge n$. An LP has order $m$ if it is divisible by $(x-1)^m$. The problem of finding the set $L_m$ of lengths of LPs of order $m$ is equivalent to finding the lengths of spectral-null codes of order $m$, and to finding $n$ such that $[n]$ admits a partition into two subsets whose first $m$ moments are equal. Extending the techniques and results initiated by Boyd, we completely determine $L_7$ and $L_8$, and prove that $\min L_9=192$ and $\min L_{10}=240$. Our primary tools are (a) symmetry, and (b) the use of carefully targeted searches using integer linear programming both to find LPs and to disprove their existence for specific $n$ and $m$. Symmetry plays an unexpected role and leads to the concept of regenerative pairs, which produce infinite arithmetic progressions in $L_m$. We prove for $m \le$ 8 (and conjecture later for all $m$) that whenever there is an LP of length $n$ and order $m$, there is one of length $n$ and order $m$ that is symmetric (resp. antisymmetric) if $m$ is even (resp. odd).References
- Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
- Daniel Berend and Shahar Golan, Littlewood polynomials with high order zeros, Math. Comp. 75 (2006), no. 255, 1541–1552. MR 2219044, DOI 10.1090/S0025-5718-06-01848-5
- M. Berkelaar, K. Eikland, P. Notebaert, and others, lpsolve: Open source (mixed-integer) linear programming system, Eindhoven U. of Technology 63 (2004).
- Peter Borwein and Colin Ingalls, The Prouhet-Tarry-Escott problem revisited, Enseign. Math. (2) 40 (1994), no. 1-2, 3–27. MR 1279058
- Peter Borwein and Michael J. Mossinghoff, Polynomials with height 1 and prescribed vanishing at 1, Experiment. Math. 9 (2000), no. 3, 425–433. MR 1795875
- 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
- David W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients. II, Math. Comp. 71 (2002), no. 239, 1205–1217. MR 1898751, DOI 10.1090/S0025-5718-01-01360-6
- H. L. Dorwart and O. E. Brown, The Tarry-Escott Problem, Amer. Math. Monthly 44 (1937), no. 10, 613–626. MR 1524120, DOI 10.2307/2301480
- 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, DOI 10.1109/18.782100
- Shahar Golan, Equal moments division of a set, Math. Comp. 77 (2008), no. 263, 1695–1712. MR 2398788, DOI 10.1090/S0025-5718-08-02072-3
- D. Katz, S. Lee, and S. Trunov, Rudin-Shapiro-like sequences with maximum asymptotic merit factor. arXiv:1711.02233v4 2020.
- Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
- H. Mittelmann, Decision tree for optimization software. http://plato.asu.edu/bench.html/.
- R. M. Roth, P. H. Siegel, and A. Vardy, High-order spectral-null codes: constructions and bounds, IEEE Trans. Info. Th. 40 (1994), 1826–1840.
- SAS Institute Inc., SAS Optimization 8.5, SAS Institute Inc., Cary, NC, 2019.
- K. Schouhamer Immink and K. Cai, Estimated spectra of higher-order spectral null codes, IEEE Communications Letters 23 (2019), 20–23.
- V. Skachek, Coding for Spectral-null Constraints, M. Sc. thesis (in Hebrew), Technion, 1997.
- R. Stong, personal communication, 2019.
- Wolfram Research, Inc. Mathematica, version 12.1.1, Champaign, IL.
Additional Information
- Joe Buhler
- Affiliation: Department of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455
- MR Author ID: 43035
- Email: jbuhler@math.umn.edu
- Shahar Golan
- Affiliation: Department of Computer Science, Jerusalem College of Technology, Jerusalem, Israel
- MR Author ID: 785537
- Email: sgolan@jct.ac.il
- Rob Pratt
- Affiliation: SAS Institute, Inc., Cary, North Carolina 27513
- MR Author ID: 1334609
- Email: rob.pratt@sas.com
- Stan Wagon
- Affiliation: Department of Mathematics, Macalester College, St. Paul, Minnesota 55105
- MR Author ID: 179895
- Email: wagon@macalester.edu
- Received by editor(s): December 9, 2019
- Received by editor(s) in revised form: August 24, 2020, and September 29, 2020
- Published electronically: February 26, 2021
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1435-1453
- MSC (2020): Primary 11B83, 12D10; Secondary 94B05, 11Y99
- DOI: https://doi.org/10.1090/mcom/3612
- MathSciNet review: 4232230