Littlewood polynomials, spectral-null codes, and equipowerful partitions

Authors:
Joe Buhler, Shahar Golan, Rob Pratt and Stan Wagon

Journal:
Math. Comp. **90** (2021), 1435-1453

MSC (2020):
Primary 11B83, 12D10; Secondary 94B05, 11Y99

DOI:
https://doi.org/10.1090/mcom/3612

Published electronically:
February 26, 2021

MathSciNet review:
4232230

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

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).

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

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

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

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

Keywords:
Littlewood polynomials,
spectral-null code,
antenna array,
multigrade identity,
equal power sum partition,
integer linear programming

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

Article copyright:
© Copyright 2021
American Mathematical Society