A polynomial with coefficients +/-1 very likely to be irreducible. RMM 2020 Shortlist.

Here is a problem I tried recently. It’s from 2020 Romanian Master of Mathematics Shortlist. Though it was placed as A1, I think it is much more difficult. I tried several ideas but didn’t make any progress. This additionally increased my curiosity and I started searching for similar problems. That’s how I found a paper by Kozma and Bary-Soroker dedicated on exactly the same problem [1]. It’s neither long nor involved, so it can be presented here.

Problem (RMM 2020 Shortlist, A1). Prove that for all sufficiently large positive integers $d$ , at least $99\%$ of the polynomials of the form

$\displaystyle \sum_{i\leqslant d}\sum_{j\leqslant d}\pm x^iy^j$

are irreducible over the integers.

Solution. It closely follows [1]. Denote the polynomial by $F(x,y).$ We’ll show that the probability of $F$ being reducible over $\mathbb{Z}$ tends to $0$ as $d\to\infty.$ The idea is to eliminate somehow one of the variables by a substitution.

Claim. If $F(x,y)$ is reducible then either $F(2,y)$ is reducible or $F(x,2)$ is reducible or $F(x,y)=f(x)g(y)$ .
Proof. Suppose $F(x,y)=f(x,y)g(x,y)$ and $r$ be the degree of $y$ in $F(x,y).$ Putting $x=2$ we get

$\displaystyle F(2,y)=f(2,y) g(2,y)$

Note that the coefficient of $y^r$ in $F(2,y)$ is odd, that is, it’s nonzero. If we assume $F(2,y)$ is not reducible it means one of the polynomial $f(2,y)$ or $g(2,y)$ is a constant and the degree of the other, say $g(2,y)$ is $r.$ It means the degree of $g(x,y)$ with respect to $y$ is $r$ hence $f(x,y)$ is in fact polynomial depending only on $x$ . In the same way, putting $y=2$ and assuming $F(x,2)$ is irreducible implies that $g(x,y)$ depends only on $y,$ that is, $F(x,y)=f(x)g(y).\quad \square$

Let us first prove that $F(x,2),$ resp. $F(2,y),$ most likely is irreducible.

$\displaystyle F(x,2)=\sum_{i=0}^d x^i(\pm 2^0\pm 2^1\pm\dots\pm 2^d).$

Note that the expression inside brackets in the right hand side uniquely determines an odd integer in the interval $[-2^d-1, 2^d+1].$ Let us set $N:=2^d+2.$ It boils down to prove that the portion of irreducible (over $\mathbb{Z}$ ) polynomials of the form

$\displaystyle F(x)=\sum_{i=0}^d a_i x^i \qquad(1)$

where each $a_i$ is an odd integer in the interval $[-N+1,N-1],$ tends to zero when $d\to\infty.$ Suppose

$\displaystyle \sum_{i=0}^d a_i x^i = \left( \sum_{i=0}^r b_i x^i\right)\left(\sum_{i=0}^s c_i x^ii \right) \qquad (2)$

where $r+s=d, r\ge 1,s\ge 1$ and $b_i,c_i\in\mathbb{Z}.$ Let us consider any polynomial, that can be presented as in $(2),$ modulo $N+1.$ Note that the odd numbers in $[-N+1,N-1]$ different residues modulo $N+1$ because $N+1$ is odd. Let us fix $r,s.$ All possible representation like in $(2)$ are less than all possible tuples

$(b_0,b_1,\dots,b_r), (c_0,c_1,\dots,c_s)$

of residues modulo $N+1$ where there are additional conditions for $b_0,b_r,c_0,c_s.$ All the possible cases for the rest of the coefficients are $(N+1)^{r-1+s-1}=(N+1)^{d-2}.$ Further, we have $b_0c_0=a_0, b_rc_s=a_d.$

$\displaystyle \#\{b_0,c_0,b_r,c_s \}\le \left(\sum_{b_0=1}^N \frac{N}{b_0}\right)\left( \sum_{b_r=1}^N \frac{N}{b_r}\right).$

The right hand side can be estimated by $C\left(\ln N\right)^2N^2$ for an absolute constant $C.$ Finally summing over all possible values of $r,s, r+s=d$ we get that all possible tuples $(b_i),(c_i)$ for which $(2)$ holds are less than

$\displaystyle C d\left(\ln N\right)^2(N+1)^d$

All possible polynomials like in $(1)$ are $N^{d+1},$ hence

$\displaystyle \mathbf{P}( F(x,2) \text{ is irreducible})\le C_1d \frac{\left( \ln N\right)^2}{N}\qquad (3)$

Since $N=2^d+2,$ it follows

$\displaystyle \mathbf{P}\big( F(x,2) \text{ is irreducible}\big) \le C_2 \frac{d^3}{2^d}\qquad(4)$

The same estimate holds for $\mathbf{P}( F(x,2) \text{ is irreducible}).$ It remains to estimate the cases when

$F(x,y)=f(x)g(y).$

where $f,g\in \mathbb{Z}[x].$ It easily follows that $f,g$ are of degree $d$ with coefficients $\pm 1.$ Thus

$\displaystyle \mathbf{P}\big(F(x,y)=f(x)g(y)\big) \le \frac{2^{d+1}2^{d+1}}{2^{(d+1)^2}}\qquad (5)$

Finally, from $(4)$ and $(5)$ it yields

$\displaystyle \lim_{d\to\infty}\mathbf{P}\big(F(x,y) \text{ is irreducible over }\mathbb{Z} \big)=0.$

Comments.

It’s instructive to analyze the idea behind the estimates $(4)$ and $(5).$ It can be exploited in other cases. First, the different coefficients of $F(x,2)$ have different residues modulo a proper natural number $N$ and second, the possible values of these coefficients are a lot more than the degree $d.$ In our case $N$ is something like $2^d.$ That’s why $(4)$ holds. The same idea is not possible to be carried out for the polynomial

$\displaystyle F(x)=\sum_{i=1}^d \pm x^i.$

So, thou I believe the probability of this polynomial being irreducible over $\mathbb{Z}$ also tends to zero, another idea should be used to prove it.

References.
[1] L. Bary-Soroker, G. Kozma, IS A BIVARIATE POLYNOMIAL …, https://arxiv.org/pdf/1602.06530.pdf
[2] AoPS page on this problem.

One thought on “A polynomial with coefficients +/-1 very likely to be irreducible. RMM 2020 Shortlist.”

Pingback: Almost All Binary Polynomials are Square Free. RMM 2024, Problem 6. – A Point of View.

Comments.

Share this:

Related

One thought on “A polynomial with coefficients +/-1 very likely to be irreducible. RMM 2020 Shortlist.”

Leave a comment Cancel reply