In this post I attempt to answer this question: How many Littlewood polynomials of degree n have a closed Lill path?
A Littlewood polynomial is a polynomial that has all its coefficients equal to 1 or -1. Littlewood polynomials seem to be studied for their properties related to autocorrelation.
A polynomial has a closed Lill path if the Lill’s method representation of the polynomial starts and ends at the same point. According to [1], a polynomial p(x) (with real coefficients) has a closed Lill path if and only if p(x) is divisible by x^2 +1. This means that a polynomial p(x) has a closed Lill path if i and -i are two of its roots.
When dealing with polynomials with closed Lill paths, it’s convenient to start the path at the origin point P0 (0,0). I’ll use the formulas from Riaz’s paper [2] to represent the polynomials using Lill’s method. I’ll also use the formulas from [2] to create new formulas for polynomials with closed Lill paths.
Lill’s Method Representation and the Sum Formula
Let’s have the general Littlewood polynomial of order n, p(x)=
anxn+an-1xn-1+…+a1x+a0 ,where the coefficients {an, an-1, … , a1, a0} are equal to 1 or -1. The direction and length of the Lill vector corresponding to the coefficient ak is given by the formula: akei(n-k)π/2 , where i is the imaginary number and 0≤ 𝑘 ≤ 𝑛.
If P0P1 is the Lill path vector corresponding to an and P0 is placed at (0,0), then a polynomial has a closed Lill path if and only if:
Half of the terms in the sum should be real and half should be complex. The real terms should cancel each other and the imaginary terms should also cancel each other. The sum formula is equal to 0 only when the degree n of the polynomial has the following condition: n+1=4m, where m is a positive natural number equal or greater than 1. This means that there are Littlewood polynomials with closed Lill paths only when n is equal to 3,7,11,15,etc.
The number of coefficients is n+1. Each term in the sum is 1,-1,i or -i. The number of real terms {-1,1} in the sum must be even so that the 1s and the -1s cancel each other. We also need an even number of imaginary terms so that the is and the -is cancel each other. This is why only Littlewood polynomials of degree n+1=4m can have closed Lill paths.
n=3
The first degree with solutions is n=3. Overall, there are 4 Littlewood polynomials of degree 3 that have a closed Lill path. The 4 solutions can be seen below.
When represented using Lill’s method, all these polynomials describe squares. The polynomial x3+x2+x+1 is represented below. P0P1 represents the coefficient of x3 (we always start with the coefficient of the highest degree power). In the image I named the first point P0P4 since the first point P0 and the last point P4 are the same point (thus the closed Lill Path). Overall, we can say that the Lill representation is a square that turns counterclockwise (this is because all the coefficients have the same positive sign).
The polynomial -x3+x2-x+1 is represented by a square that turns clockwise, because it has coefficients that alternate between positive and negative.
Combinatorics
The next degree with solutions is n=7. We can use the sum formula to get all the combinations of coefficients that create a closed path, but we have to check 28 =256 combinations. Maybe we can use some combinatorics to obtain a general formula.
Generally, the sum has n+1 terms as mentioned above. If n+1=4m, then 2m terms are real (1 or -1) and 2m terms are imaginary (i or -i). The real terms cancel each other if and only if the number of 1s or equal to the number of -1s. So we must have an m amount of 1s and a m amount of -1s. Similarly, we must have an m amount of i and m amount of -i to cancel each other.
The number of unique way we can arrange an m amount of 1s and m amount of -1s is:
The number of arrangements for the complex terms is the same. So to get the total number of combinations or the total number of Littlewood of degree n that have a closed Lill path is:
For n=3 and m=1, we get 4 closed polynomials. For n=7 and m=2, we get 36 closed polynomials. For n=11 and m=3, we get 400 closed polynomials.
It is important to point out that the Lill vector formula akei(n-k)π/2 is real when k=n,n-2,n-4 etc. The vector formula yields an imaginary term when k=n-1,n-3,n-5 etc. Thus, the sum formula will alternate between real and complex terms. This is important to point out when we think about the combinatorics formula. We cannot place the real terms in the place for complex terms and vice versa.
Final Notes
As I mentioned in many of my posts or papers on Lill’s method, the beauty of this method is that it combines many areas of mathematics in an elegant way. Here we showed how the number of Littlewood polynomials with closed Lill paths can be determined using algebraic methods and combinatorics.
The problem can be extended to polynomials that have 1,-1,i and -i as coefficients. In my paper “Representing Polynomials with Complex Coefficients using Lill’s Method” I mentioned that a polynomial with complex coefficients has a closed Lill path if -i is one of the roots ( i is not necessarily a root since the Complex Conjugate Root Theorem may not apply anymore). The paper has some useful algebraic formulas that can be used to create a sum formula similar to the one discussed in this post.
References
[1] Dan Kalman, and Mark Verdi. “Polynomials with Closed Lill Paths.” Mathematics Magazine, vol. 88, no. 1, 2015, pp. 3–10. JSTOR,
www.jstor.org/stable/10.4169/math.mag.88.1.3.
[2] Riaz, M. “Geometric Solutions of Algebraic Equations.” The American Mathematical Monthly, vol. 69, no. 7, 1962, pp. 654–658. JSTOR, www.jstor.org/stable/2310843.