Putnam 2022, Problem A-6

Let $n$ be a positive integer. Determine, in terms of $n$, the largest integer $m$ with the following property: There exist real numbers $x_1, \ldots, x_{2n}$ with $-1 < x_1 < x_2 < \cdots < x_{2n} < 1$ such that the sum of the lengths of the $n$ intervals $[x_1^{2k-1}, x_2^{2k-1}], [x_3^{2k-1}, x_4^{2k-1}], \ldots, [x_{2n-1}^{2k-1}, x_{2n}^{2k-1}]$ is equal to $1$ for all integers $k$ with $1 \leq k \leq m$.

Solution:
First solution. The largest such \( m \) is \( n \). To show that \( m \geq n \), we take  
\[
x_j = \cos \frac{(2n + 1 - j)\pi}{2n + 1} \quad (j = 1, \ldots, 2n).
\]  

It is apparent that \( -1 < x_1 < \cdots < x_{2n} < 1 \). The sum of the lengths of the intervals can be interpreted as  
\[
- \sum_{j=1}^{2n} ((-1)^{2n+1-j} x_j)^{2k-1}
\]  
\[
= - \sum_{j=1}^{2n} \left( \cos(2n + 1 - j) \left( \pi + \frac{\pi}{2n + 1} \right) \right)^{2k-1}
\]  
\[
= - \sum_{j=1}^{2n} \left( \cos \frac{2\pi(n + 1)j}{2n + 1} \right)^{2k-1}.
\]  

For \( \zeta = e^{2\pi i (n+1)/(2n+1)} \), this becomes  
\[
= - \sum_{j=1}^{2n} \left( \frac{\zeta^j + \zeta^{-j}}{2} \right)^{2k-1}
\]  
\[
= - \frac{1}{2^{2k-1}} \sum_{j=1}^{2n} \sum_{l=0}^{2k-1} \binom{2k-1}{l} \zeta^{j(2k-1-2l)}
\]  
\[
= - \frac{1}{2^{2k-1}} \sum_{l=0}^{2k-1} \binom{2k-1}{l} \sum_{j=1}^{2n} \zeta^{j(2k-1-2l)}
\]  
\[
= - \frac{1}{2^{2k-1}} \sum_{l=0}^{2k-1} \binom{2k-1}{l} (-1) = 1,
\]  
using the fact that \( \zeta^{2k-1-2l} \) is a nontrivial root of unity of order dividing \( 2n + 1 \).  

To show that \( m \leq n \), we use the following lemma. We say that a multiset \( \{x_1, \ldots, x_m\} \) of complex numbers is *inverse-free* if there are no two indices \( 1 \leq i \leq j \leq m \) such that \( x_i + x_j = 0 \); this implies in particular that 0 does not occur.  

**Lemma.** Let \( \{x_1, \ldots, x_m\}, \{y_1, \ldots, y_n\} \) be two inverse-free multisets of complex numbers such that  
\[
\sum_{i=1}^m x_i^{2k-1} = \sum_{i=1}^n y_i^{2k-1} \quad (k = 1, \ldots, \max\{m, n\}).
\]  
Then these two multisets are equal.  

*Proof.* We may assume without loss of generality that \( m \leq n \). Form the rational functions  
\[
f(z) = \sum_{i=1}^m \frac{x_i z}{1 - x_i^2 z^2}, \quad g(z) = \sum_{i=1}^n \frac{y_i z}{1 - y_i^2 z^2};
\]  
both \( f(z) \) and \( g(z) \) have total pole order at most \( 2n \). Meanwhile, by expanding in power series around \( z = 0 \), we see that \( f(z) - g(z) \) is divisible by \( z^{2n+1} \). Consequently, the two series are equal.  

However, we can uniquely recover the multiset \( \{x_1, \ldots, x_m\} \) from \( f(z) \): \( f \) has poles at \( \{1/x_1^2, \ldots, 1/x_m^2\} \) and the residue of the pole at \( z = 1/x_i^2 \) uniquely determines both \( x_i \) (i.e., its sign) and its multiplicity. Similarly, we may recover \( \{y_1, \ldots, y_n\} \) from \( g(z) \), so the two multisets must coincide. \( \square \)  

Now suppose by way of contradiction that we have an example showing that \( m \geq n + 1 \). We then have  
\[
1^{2k-1} + \sum_{i=1}^n x_{2i-1}^{2k-1} = \sum_{i=1}^n x_{2i}^{2k-1} \quad (k = 1, \ldots, n + 1).
\]  

By the lemma, this means that the multisets \( \{1, x_1, x_3, \ldots, x_{2n-1}\} \) and \( \{x_2, x_4, \ldots, x_{2n}\} \) become equal after removing pairs of inverses until this becomes impossible. However, of the resulting two multisets, the first contains 1 and the second does not, yielding the desired contradiction.  

**Remark.** One can also prove the lemma using the invertibility of the Vandermonde matrix  
\[
(x_i^j)_{i=0, \ldots, n; j=0, \ldots, n}
\]  
for \( x_0, \ldots, x_n \) pairwise distinct (this matrix has determinant \( \prod_{0 \leq i < j \leq n} (x_i - x_j) \neq 0 \)). For a similar argument, see Proposition 22 of: M. Bhargava, Galois groups of random integer polynomials and van der Waerden’s conjecture, arXiv:2111.06507.  

**Remark.** The solution for \( m = n \) given above is not unique (see below). However, it does become unique if we add the assumption that \( x_i = -x_{2n+1-i} \) for \( i = 1, \ldots, 2n \) (i.e., the set of intervals is symmetric around 0).  

Second solution. (by Evan Dummit) Define the polynomial  
\[
p(x) = (x - x_1)(x + x_2) \cdots (x - x_{2n-1})(x + x_{2n})(x + 1);
\]  
by hypothesis, \( p(x) \) has \( 2n + 1 \) distinct real roots in the interval \( [-1, 1] \). Let \( s_k \) denote the \( k \)-th power sum of \( p(x) \); then for any given \( m \), the desired condition is that \( s_{2k-1} = 0 \) for \( k = 1, \ldots, m \). Let \( e_k \) denote the \( k \)-th elementary symmetric function of the roots of \( p(x) \); that is,  
\[
p(x) = x^{2n+1} + \sum_{i=k}^{2n+1} (-1)^k e_k x^{2n+1-k}.
\]  

By the Girard–Newton identities,  
\[
(2k - 1) e_{2k-1} = s_1 e_{2k-2} - s_2 e_{2k-3} + \cdots - s_{2k} e_1;
\]  
hence the desired condition implies that \( e_{2k-1} = 0 \) for \( k = 1, \ldots, m \).  

If we had a solution with \( m = n + 1 \), then the vanishing of \( e_1, \ldots, e_{2n+1} \) would imply that \( p(x) \) is an odd polynomial (that is, \( p(x) = -p(-x) \) for all \( x \)), which in turn would imply that \( x = 1 \) is also a root of \( p \). Since we have already identified \( 2n + 1 \) other roots of \( p \), this yields a contradiction.  

By the same token, a solution with \( m = n \) corresponds to a polynomial \( p(x) \) of the form \( x q(x^2) + a \) for some polynomial \( q(x) \) of degree \( n \) and some real number \( a \) (necessarily equal to \( q(1) \)). It will thus suffice to choose \( q(x) \) so that the resulting polynomial \( p(x) \) has roots consisting of \( -1 \) plus \( 2n \) distinct values in \( (-1, 1) \). To do this, start with any polynomial \( r(x) \) of degree \( n \) with \( n \) distinct positive roots (e.g., \( r(x) = (x - 1) \cdots (x - n) \)). The polynomial \( x r(x^2) \) then has \( 2n + 1 \) distinct real roots; consequently, for \( \epsilon > 0 \) sufficiently small, \( x r(x^2) + \epsilon \) also has \( 2n + 1 \) distinct real roots. Let \( -\alpha \) be the smallest of these roots (so that \( \alpha > 0 \)); we then take \( q(x) = r(x \sqrt{\alpha}) \) to achieve the desired result.