Romanian Master of Mathematics

Clearly, $|P_n|=2^n$. Alternatively, but equivalently, we prove that less than $\frac{1}{100}\cdot 2^n$ of the polynomials in $P_n$ are not square-free for all but finitely many $n$. Throughout the solution $n$ is always assumed to be sufficiently large to allow room for as large integers $r\le n$ as the different stages of the argument require. Also, all polynomials have integer coefficients and divisibility is always understood in $\mathbb{Z}[X]$. The proof consists of three parts:

(1) Upper bounding the number of polynomials in $P_n$ divisible by the square of a non-constant polynomial of degree at most $r$; (2) Upper bounding the number of polynomials in $P_n$ divisible by the square of a polynomial of degree greater than $r$; and (3) Choosing a suitable $r$.

Before dealing with the three parts above, we prove a useful lemma.

Lemma. The zeroes of any polynomial in $P_n$ all lie in the open disc $|z|<2$ and their real parts are all less than $C=\frac{1}{2}(1+\sqrt{5})$.

Proof. Let $P$ be a degree $m$ polynomial in $P_n$. Leaving aside the trivial case $m=0$, let $m\ge 1$. Write $P={\sum }_{k=0}^m{a}_k{X}^k$ and consider a complex number $z$ of absolute value $|z|\ge 2$. Then $$|P(z)|\ge |z{|}^m-\sum _{k=0}^{m-1}|z{|}^k=\frac{(|z|-2)|z{|}^m+1}{|z|-1}\ge \frac{1}{|z|-1}>0,$$ and the first part follows.

To prove the second part, let $z$ have a real part $\Re z\ge C>1$. Clearly, $|z|\ge \Re z\ge C>1$. Leaving aside the trivial cases $m=0$ and $m=1$, let $m\ge 2$ to write $$\begin{array}{rl}\left|\frac{P(z)}{z^m}\right|& \ge \left|a_m+\frac{a_{m-1}}{z}\right|-\frac{1}{|z{|}^2}-\cdots -\frac{1}{|z{|}^m}\\ & >\left|a_m+\frac{a_{m-1}}{z}\right|-\frac{1}{|z{|}^2-|z|}\\ & \ge \left|a_m+\frac{a_{m-1}}{z}\right|-1,\text{as }|z|\ge C,\\ & \ge \Re \left(a_m+\frac{a_{m-1}}{z}\right)-1\ge a_m-1\ge 0.\end{array}$$ This establishes the second part and completes the proof. (The argument in the second part shows in fact that, if $\Re z>0$ and $|z|\ge C$, then $P(z)\ne 0$. Hence the zeroes of $P$ with a positive real part all lie in the open disc $|z|<C$.)

To deal with (1), consider a polynomial $P$ in $P_n$ divisible by the square of a non-constant polynomial $Q$ of degree $q\le r$. We first show that there are at most $(2^{2r+1}-1{)}^{r+1}$ such $Q$'s.

Clearly, the leading coefficient of $Q$ is $\pm 1$. The zeroes $z_1,\dots ,z_q$ of $Q$ are amongst those of $P$, so $|z_k|<2$, by the lemma. The absolute value of the coefficient of $X^{q-k}$ in $Q$ is then $\left|\sum z_{i_1}\cdots z_{i_k}\right|<\left(\genfrac{}{}{0ex}{}{q}{k}\right)\cdot 2^k<2^{q+k}\le 2^{2q}\le 2^{2r}$. Hence each coefficient of $Q$ takes on at most $2\cdot 2^{2r}-1=2^{2r+1}-1$ values, so there are at most $(2^{2r+1}-1{)}^{r+1}$ such $Q$'s, as stated.

Next, upper bound the number of $P$'s in $P_n$ that are divisible by the same $Q^2$. Consider such a $P=a_0+\cdots +a_n{X}^n$ and let $S_n(P)$ be the set of all polynomials $R=b_0+\cdots +b_n{X}^n$ in $P_n$ such that $b_k\ne a_k$ for exactly one $k$; note that $k\ge 1$, as $b_0=a_0=1$. Alternatively, but equivalently, there exists a $k\ge 1$ such that $b_{\ell }=a_{\ell }$ for $\ell \ne k$ and $b_k+a_k=1$. Hence $|S_n(P)|=n$. Note further that $P-R=\pm X^k$ vanishes at 0, whereas $Q$ does not, as $Q(0{)}^2$ divides $P(0)\ne 0$. Hence $R$ is not divisible by $Q^2$, showing that none of the $n$ polynomials in $S_n(P)$ is.

Consider now distinct $P_1$ and $P_2$ in $P_n$, both divisible by $Q^2$, to show that $S_n(P_1)$ and $S_n(P_2)$ are disjoint: If they shared some $R$, then $P_1-R=\pm X^{k_1}$ and $P_2-R=\pm X^{k_2}$ for some distinct $k_1,k_2\ge 1$, so $P_1-P_2=\pm X^{k_1}\pm X^{k_2}$ would be divisible by $Q^2$, which is clearly not the case.

By the two paragraphs above, there are then at most $2^n/(n+1)$ polynomials in $P_n$ that are divisible by the same $Q^2$.

As there are at most $(2^{2r+1}-1{)}^{r+1}$ such $Q$'s of degree at most $r$, there are at most $$\frac{(2^{2r+1}-1{)}^{r+1}}{n+1}\cdot 2^n$$ polynomials in $P_n$ divisible by the square of a non-constant polynomial of degree at most $r$. For a fixed $r$ this upper bound is clearly of order $o(2^n)$.

To deal with (2), consider a polynomial $P$ in $P_n$ divisible by the square of a non-constant polynomial $Q$ of degree $q>r$.

The zeroes $z_1,\dots ,z_q$ of $Q$ are amongst those of $P$, so $|z_k|<2$ and $\mathfrak{R}{z}_k<C$, by the lemma. As the leading coefficient of $Q$ is clearly $\pm 1$, $$|Q(3)|=|(3-z_1)\cdots (3-z_q)|\ge (3-\mathfrak{R}{z}_1)\cdots (3-\mathfrak{R}{z}_q)>(3-C{)}^q>(3-C{)}^r.$$ As $3-C>1$, letting $r$ be large enough, $P(3)$ is then divisible by $d^2$ for some large enough $d>(3-C{)}^r$.

Consider the largest integer $s=s_d$ satisfying $3^s<d^2\le 3^{s+1}$. Clearly, $s\ge 1$. Write $P={\sum }_{k=0}^n{a}_k{X}^k$. Then $1=a_0\le {\sum }_{k=0}^{s-1}{3}^k{a}_k\le {\sum }_{k=0}^{s-1}{3}^k=\frac{1}{2}(3^s-1)<\frac{1}{2}(d^2-1)<d^2$. As for distinct choices of $a_1,\dots ,a_{s-1}$ from $\{0,1\}$ the sums ${\sum }_{k=0}^{s-1}{3}^k{a}_k$ are pairwise distinct, they are also pairwise distinct modulo $d^2$. Noting that these sums are all positive, it follows that there are at most $2^{n-s+1}$ polynomials $P$ in ${\mathcal{P}}_n$ such that $P(3)$ is divisible by $d^2$.

If $r$ is sufficiently large, then so is $d>(3-C{)}^r$. Thus, if $d$ is large enough, then $2^s>d^{5/4}$, as $d^2\le 3^{s+1}$ and ${\log }_{2}3<\frac{8}{5}$, so there are at most $2^{n-s+1}\le 2^{n+1}{d}^{-5/4}$ polynomials $P$ in ${\mathcal{P}}_n$ such that $P(3)$ is divisible by $d^2$. Hence, if $d_0$ is large enough, then the number of such $P$'s is at most $2^{n+1}{\sum }_{d>d_0}{d}^{-5/4}$.

Now, as ${\sum }_{d\ge 1}{d}^{-5/4}$ converges, given any $c>0$, the remainder ${\sum }_{d>d_0}{d}^{-5/4}<c$ for some large enough $d_0$ depending on $c$, of course. For any such $d_0$, the number of $P$'s in ${\mathcal{P}}_n$ such that $P(3)$ is divisible by $d^2$ is then less than $2c\cdot 2^n$.

Consequently, so is the number of polynomials in ${\mathcal{P}}_n$ divisible by the square of a polynomial of degree greater than $r$.

Finally, we deal with (3). Fix any $c>0$. Then choose $r$ large enough so that the remainder ${\sum }_{d>(3-C)r}{d}^{-5/4}<c$. At this stage $n>r$. Let further $n>\frac{1}{c}(2^{2r+1}-1{)}^{r+1}$. By (1) and (2), the number of non-square-free polynomials in ${\mathcal{P}}_n$ is then less than $3c\cdot 2^n$. Setting $c=\frac{1}{300}$ provides the answer to the problem at hand.

Alternative solution:

We present an alternative approach to parts (1) and (2).

To deal with (1), use the first part of the lemma to bound the number of possible polynomials $Q$ by some constant. For every such $Q$, we then prove that few polynomials in ${\mathcal{P}}_n$ are divisible by $Q$. This follows from the claim below:

Claim. Given a non-constant polynomial $Q$, the number of polynomials in ${\mathcal{P}}_n$ that are divisible by $Q$ does not exceed $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$.

Proof. Let $\zeta$ be a non-zero complex root of $Q$ (if there are no such, then no polynomial in ${\mathcal{P}}_n$ is divisible by $Q$). Then each polynomial $P=p_n{X}^n+\cdots +p_{1}X+p_0$ in ${\mathcal{P}}_n$ divisible by $Q$ satisfies ${\sum }_{i=0}^n{p}_i\cdot c^{\zeta }=0$, for any complex $c$. Choose a suitable $c$ so that the $a_i=\text{Re }{c}^{\zeta }$ are all non-zero. Then ${\sum }_{i=0}^n{a}_i{p}_i=0$.

Partially order the (binary) tuples of coefficients by letting $(p_1,p_2,\dots ,p_n)⪯(p_1^{\prime },p_2^{\prime },\dots ,p_n^{\prime })$ if and only if the non-zero $a_i(p_i^{\prime }-p_i)$ are all positive. The tuples corresponding to polynomials divisible by $Q$ then form an independent set (anti-chain) in the $⪯$-partially ordered $n$-cube.

Assign each tuple $(p_1,p_2,\dots ,p_n)$ the tuple $(\sigma p_1,\sigma p_2,\dots ,\sigma p_n)$, where $\sigma p_i=p_i$, if $a_i>0$, and $\sigma p_i=1-p_i$, otherwise. This assignment shows $⪯$ isomorphic to the (index) set-inclusion partial order on the binary $n$-cube, so the length of any $\le$-anti-chain is at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, by Sperner's theorem. This proves the claim.

The standard bound provided by Stirling's formula (or any of its elementary relaxations) establishes part (1).

To prove (2), deal more algebraically. Let $P$ be a polynomial in $P_n$ divisible by some $Q^2$, where $\mathrm{deg}Q=d>r$. Reduce modulo 2 to get the polynomials $\overline{P}$ and $\overline{Q}$, where $\mathrm{deg}\overline{Q}=d$, as the leading coefficient of $Q$ is $\pm 1$. Then $\overline{P}$ is divisible by ${\overline{Q}}^2=\overline{Q}(X^2)$. Write $\overline{P}={\overline{P}}_{+}(X^2)+X{\overline{P}}_{-}(X^2)$. Then ${\overline{P}}_{+}$ and ${\overline{P}}_{-}$ are both divisible by $\overline{Q}$. So, for a fixed $\overline{Q}$, the number of such polynomials does not exceed $2^{n-2d}$. Hence for all degree $d$ polynomials $\overline{Q}$, the number of such $P$'s does not exceed $2^{d-1}\cdot 2^{n-2d}=2^{n-d-1}$, so their fraction in $P_n$ is at most $2^{-d-1}$. Finally, sum over all $d\ge r$, to conclude that the fraction of $P$'s in (2) does not exceed $2^{-r}$.