Kvant Math Problem 1552

The polynomial $P_n(x)=1+x+\cdots+x^{n-1}$ satisfies

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 22m50s
Source on kvant.digital

Problem

Let $P_n(x)=1+x+x^2+\ldots+x^{n-1}$ denote the polynomial of degree $(n-1)$ all of whose coefficients are equal to 1.

  1. Prove that for every positive integer $s$ there exists a number $k$ such that the polynomial $P_k(x)$ can be factored into a product of two polynomials with integer coefficients, one of which has the form $1+sx+\ldots$ (the ellipsis stands for terms of degree higher than one).
  2. Prove that such a number $k$ exists for every integer $s$ as well.

V. A. Senderov

59th Moscow Mathematical Olympiad, 1996, Tournament of Towns (Spring 1996)

Exploration

The polynomial $P_n(x)=1+x+\cdots+x^{n-1}$ satisfies

$P_n(x)=\frac{x^n-1}{x-1}.$

Its factorization into cyclotomic polynomials is

$P_n(x)=\prod_{\substack{d\mid n\ d>1}}\Phi_d(x).$

Each $\Phi_d(x)$ has integer coefficients and constant term $1$, so any product of such factors also has constant term $1$. If $F(x)=\prod_i F_i(x)$ and each $F_i(x)=1+a_i x+\cdots$, then the coefficient of $x$ in $F(x)$ equals $\sum_i a_i$ because the linear term can only arise by selecting the linear term from exactly one factor.

The problem therefore reduces to selecting cyclotomic factors $\Phi_d(x)$ dividing some $P_k(x)$ so that their linear coefficients sum to a prescribed integer $s$.

For primes $p$, one has

$\Phi_p(x)=1+x+\cdots+x^{p-1},$

so the coefficient of $x$ equals $1$.

For primes $p$,

$\Phi_{2p}(x)=\Phi_p(-x),$

so expanding the first terms gives

$\Phi_{2p}(x)=1-x+\cdots,$

hence the coefficient of $x$ equals $-1$.

This provides elementary building blocks with linear coefficients $+1$ and $-1$.

Problem Understanding

The task is to construct, for any integer $s$, a number $k$ and a factor $A(x)$ of $P_k(x)$ with integer coefficients such that

$A(x)=1+s x+\cdots.$

Since every divisor $d$ of $k$ contributes a cyclotomic factor $\Phi_d(x)$ to $P_k(x)$, the problem becomes selecting a subset of these factors whose product has the required linear coefficient.

Proof Architecture

The key structure is that divisibility $d\mid k$ guarantees $\Phi_d(x)\mid P_k(x)$.

The coefficient of $x$ in a product of polynomials with constant term $1$ is additive in the coefficients of $x$ of the factors.

The cyclotomic polynomials $\Phi_p(x)$ and $\Phi_{2p}(x)$ provide explicit control of linear coefficients equal to $1$ and $-1$.

Constructing $k$ so that it contains chosen divisors allows arbitrary selection of these building blocks.

Solution

Let $s\ge 0$. Choose $s$ distinct odd primes $p_1,\dots,p_s$ and set

$k=p_1p_2\cdots p_s.$

For each $p_i\mid k$, the polynomial $\Phi_{p_i}(x)$ is a factor of $P_k(x)$ and satisfies

$\Phi_{p_i}(x)=1+x+\cdots,$

so its linear coefficient equals $1$.

Define

$A(x)=\prod_{i=1}^s \Phi_{p_i}(x).$

The constant term of each factor is $1$, so the coefficient of $x$ in $A(x)$ equals $s$, hence

$A(x)=1+s x+\cdots.$

Now let $s<0$ and write $s=-t$ with $t>0$. Choose $t$ distinct odd primes $q_1,\dots,q_t$ and set

$k=2q_1q_2\cdots q_t.$

For each $q_i\mid k$, the divisor $2q_i$ also divides $k$, hence $\Phi_{2q_i}(x)$ divides $P_k(x)$.

Using $\Phi_{2p}(x)=\Phi_p(-x)$, we obtain

$\Phi_{2q_i}(x)=1-x+\cdots,$

so its linear coefficient equals $-1$.

Define

$A(x)=\prod_{i=1}^t \Phi_{2q_i}(x).$

Again all factors have constant term $1$, so the coefficient of $x$ in $A(x)$ equals $-t=s$, giving

$A(x)=1+s x+\cdots.$

For $s=0$, take $k=4$. Then

$P_4(x)=1+x+x^2+x^3=(x^4-1)/(x-1),$

and $\Phi_4(x)=x^2+1$ divides $P_4(x)$ with zero linear coefficient, so it has the required form.

Verification of Key Steps

Each constructed $A(x)$ is a product of cyclotomic polynomials whose indices divide $k$, hence $A(x)\mid P_k(x)$ follows from the cyclotomic factorization of $P_k(x)$.

The linear coefficient computation uses only the additivity of linear terms in products of polynomials with constant term $1$, which applies because every cyclotomic polynomial satisfies $\Phi_d(0)=1$ for $d>1$.

The sign control comes from explicit expansions $\Phi_p(x)=1+x+\cdots$ and $\Phi_{2p}(x)=\Phi_p(-x)=1-x+\cdots$, which provide coefficients $+1$ and $-1$ respectively, sufficient to realize any integer $s$.

Final Conclusion

For every integer $s$ there exists a positive integer $k$ and a factor $A(x)$ of $P_k(x)$ with integer coefficients such that

$A(x)=1+s x+\cdots,$

by choosing $k$ so that it contains appropriate primes or twice-primes and selecting the corresponding cyclotomic factors inside the factorization of $P_k(x)$.