## 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