Generating Integrally Indecomposable Newton Polygons with Arbitrary Many Vertices

Abstract

In this paper we shall give another proof of a special case of Gao’s theorem for generating integrally indecomposable polygons in the sense of Minkowski. The approach of proving this theorem will enable us to give an effective algorithm for construction integrally indecomposable convex integral polygons with arbitrary many vertices. In such a way, classes of absolute irreducible bivariate polynomials corresponding to those indecomposable Newton polygons are generated.

1. Introduction

Geometrical approach to irreducibility testing of bivariate polynomials via associated polygons originates at geometrical generalization of some irreducibility criterions for univariate polynomials. Dumas [1], J. Kurschak [2], O. Ore [3,4,5] and T. Rella [6] have generalized Eisenstein irreducibility criterion [7] using Newton polygons and enabled geometrical approach in further research of irreducibility of multivariate polynomials. Lipkovski [8] associates a polynomial to an unbounded Newton polyhedron, which is a direct analogue of Newton polygon in higher dimensions. Schmidt [9] gives a method for constructing some classes of absolutely irreducible bivariate polynomials. A theoretical basis for geometrical approach in research into the irreducibility of polynomials in more than two variables is given by Ostrowski [10,11]. The relationship between the absolute irreducibility of multivariate polynomials and integral indecomposibility of associated Newton polytopes, in the sense of Minkowski, is fully explained by Gao in [12]. However, Erich Kaltofen [13] and Sturmfels [14] emphasized importance of solving the reverse problem, finding possible factorizations for multivariate polynomials with decomposable Newton polytopes. Koyuncu [15] discusses possible factorizations for bi- and tri-variate polynomials with decomposable Newton polytopes depending on the characteristic of the field. The necessary and sufficient condition for the existence of a non-trivial factorization of an arbitrary bivariate polynomial with integer coefficients into factor-polynomials with integer coefficients is given in [16]. An effective factorization algorithm based on this result is presented in [17].

Definition 1.

A polynomial over a field F is called absolutely irreducible if it remains irreducible over every algebraic extension of F.

The convex hull of a set S in ${\mathbb{R}}^2$ (denoted by $conv\left(S\right)$) is the smallest convex set that contains the set S. Graham [18] presented an algorithm for construction of the convex hull of a finite planar set.

Definition 2.

Let $f(x,y)\in \mathbb{Z}[x,y]$:

$$f(x,y)=\sum C_{e_1{e}_2}{x}^{e_1}{y}^{e_2}.$$

Consider an exponent vector $(e_1,e_2)$ as a point in ${\mathbb{Z}}^2$. The Newton polygon of the polynomial $f(x,y)$, denoted by $P_f$, is defined as the convex hull in ${\mathbb{R}}^2$ of all the points $(e_1,e_2)$ with $C_{e_1{e}_2}\ne 0$.

Definition 3.

For two arbitrary sets$A,B\subset {\mathbb{R}}^2$, the set $A+B=\{a+b\mid a\in A,b\in B\}$ is called the Minkowski sum of sets A and B.

A point in ${\mathbb{R}}^2$ is called integral if both of its coordinates are integers. A polygon in ${\mathbb{R}}^2$ is called integral if all of its vertices are integral.

Definition 4.

An integral polygon C is called integrally decomposable if there exist integral polygons A and B such that $C=A+B$, where both A and B have at least two points. Otherwise, C is called integrally indecomposable.

Theorem 1

([10]). Let F be a field. Let $f,g,h\in F[x,y]$ with $f=gh$. Then $P_f=P_g+P_h$.

Theorem 2

([12]). Let $f(x,y)$ be a non-zero polynomial over an arbitrary field F, non-divisible either by x or by y. If the Newton polygon of the polynomial $f(x,y)$ is integrally indecomposable, then $f(x,y)$ is absolutely irreducible over F.

For an arbitrary integral point $a=(a_x,a_y)$, $GCD(a_x,a_y)$ is denoted by $GCD\left(a\right)$. For arbitrary integral points a and b, $GCD\left(GCD\right(a),GCD(b\left)\right)$, is denoted by $GCD(a,b)$. In [19] necessary and sufficient conditions for integral indecomposability in the sense of Minkowski for line segments and triangles are given.

Theorem 3

([19]). Let $a_1$ and $a_2$ be integer points from ${\mathbb{R}}^2$. Line segment $[a_1,a_2]$ is integrally indecomposable in the sense of Minkowski if and only if $GCD(a_2-a_1)=1$.

Theorem 4

([19]). A triangle $conv(v_1,v_2,v_3)$ in ${\mathbb{R}}^2$ with integer vertices $v_1$, $v_2$, $v_3$ is integrally indecomposable in the sense of Minkowski if and only if:

$$GCD(v_1-v_2,v_1-v_3)=1.$$

Definition 5.

Let $f(x,y)\in \mathbb{Z}[x,y]$. The non-extended lattice of nodes of the polynomial $f(x,y)$ consists of all the points ${(e_1,e_2)}_i$, $i=1,\dots ,k$ corresponding to the monomials of $f(x,y)$ with non-zero coefficients. If the Newton polygon of $f(x,y)$ contains some integer points in its inner area or on its edges different from ${(e_1,e_2)}_i,$$i=1,\dots ,k,$ some of these points, together with ${(e_1,e_2)}_i,$$i=1,\dots ,k,$ form an extended lattice of nodes of the polynomial $f(x,y)$.

Definition 6.

Let $f(x,y)\in \mathbb{Z}[x,y]$ and let $P=\{A_1,A_2,\dots ,A_n\}$ be the lattice of nodes of the polynomial $f(x,y)$ possibly extended by some integer points that lay inside Newton polygon of the polynomial $f(x,y)$ or on its edges. Without loss of generality, we can assume that after the construction of the Newton polygon of $f(x,y)$, $A_1,A_2,\dots ,A_k,$$k\ge 2,$ become its vertices, and $A_{k+1},\dots ,A_n$ do not. We say that the grouping $G_1,\dots ,G_l,$$l\ge 2,$ of the set P is asuper-covering ofP if:

1.

Each group $G_i,$$i=1,\dots ,l,$ contains the same number of points not less than two,

2.

$\bigcup _{i=1}^l{G}_i=P,$

3.

Points $A_1,A_2,\dots ,A_k$ appear in exactly one of the sets $G_1,\dots ,G_l,$

4.

Points $A_{k+1},\dots ,A_n$ appear in at least one of the sets $G_1,\dots ,G_l,$

5.

Sets $G_2,\dots ,G_l$ are obtained from $G_1$ by translation.

Definition 7.

Let $f(x,y)\in \mathbb{Z}[x,y]$ and let $P=\{A_1,A_2,\dots ,$$A_n\}$ be the lattice of nodes of the polynomial $f(x,y)$ possibly extended by some integer points that lay inside the Newton polygon of the polynomial $f(x,y)$ or on its edges. Let

$$G_1=conv(A_{i_{1,1}},\dots ,A_{i_{1,k}}),\dots ,G_l=conv(A_{i_{l,1}},\dots ,A_{i_{l,k}}),l\ge 2,$$

$\{i_{1,1},\dots ,i_{1,k},\dots ,i_{l,1},\dots ,i_{l,k}\}=\{1,\dots ,n\}$, be a super-covering of P by l congruent $k-$gons. Furtherly, let $G_2={\tau }_2\left(G_1\right)$,…,$G_l={\tau }_l\left(G_1\right)$. Then:

$$conv(A_{i_{1,1}},{\tau }_2\left(A_{i_{1,1}}\right),\dots ,{\tau }_l\left(A_{i_{1,1}}\right)),\dots ,conv(A_{i_{1,k}},{\tau }_2\left(A_{i_{1,k}}\right),\dots ,{\tau }_l\left(A_{i_{1,k}}\right))$$

is also a super-covering of P by k congruent $l-$gons, called dual super-covering of the aforementioned super-covering.

Remark 1.

Notions of extended lattice of nodes, non-extended lattice of nodes, super-covering and dual super-covering are not necessary related to the Newton polygon of a bivariate polynomial. These notions can be defined completely analogously for an arbitrary integral convex polygon.

For a convex polygon in the Euclidean plane, there is a finite sequence of vectors associated with it in the following way. Let $v_0,v_1,\dots ,v_{m-1}$ be the vertices of the polygon in the counterclockwise direction. The edges of P are represented by the vectors $E_i=v_i-v_{i-1}=(a_i,b_i)$ for $1\le i\le m$, where $a_i$, $b_i\in \mathbb{Z}$ and the indices are taken modulo m. A vector $E_i$ is called an edge vector. A vector $v=(a,b)\in {\mathbb{Z}}^2$ is called a primitive vector if $gcd(a,b)=1$. Let $n_i=gcd(a_i,b_i)$ and let $e_i=(a_i/n_i,b_i/n_i)$. Then $E_i=n_i{e}_i$ where $e_i$ is a primitive vector, $1\le i\le m$. Each edge $E_i$ contains precisely $n_{i+1}$ integral points including its endpoints. The sequence of vectors ${\left\{n_i{e}_i\right\}}_{1\le i\le m}$ is called the edge sequence or a polygonal sequence. By its edge sequence each polygon is determined uniquely up to translation determined by $v_0$. As the boundary of the polygon is a closed path, we have that ${\sum }_{1\le i\le m}{n}_i{e}_i=(0,0)$.

Lemma 1

([20]). Let P be a polygon with edge sequence ${n_i{e}_i}_{1\le i\le m}$ where $e_i\in {\mathbb{Z}}^2$ are primitive vectors. Then an integral polygon is a summand of P iff its edge sequence is of the form ${\left\{k_i{e}_i\right\}}_{1\le i\le m}$, $0\le k_i\le n_i$, with ${\sum }_{1\le i\le m}{n}_i{e}_i=(0,0)$.

2. Main Results

Lemma 2.

Each non-trivial decomposition of an integral polygon in the sense of Minkowski induces super-covering of the extended lattice of nodes of the polygon.

Proof. 

Let P be an integral polygon and $P=Q+R$ its non-trivial decomposition, with polygons Q and R having at least two points. Suppose that $Q=conv(q_1,q_2,\dots ,q_{2+k})$, $k\ge 0$. It is obvious that ${\tau }_{q_1}\left(R\right),{\tau }_{q_2}\left(R\right),\dots ,{\tau }_{q_{2+k}}\left(R\right)$, $k\ge 0$, is a super-covering of the extended lattice of nodes of the polygon P. □

Lemma 3.

Let P be an integral polygon that has non-trivial decomposition. Each edge of P that does not contain integer points except its vertices is covered by each super-covering or its dual super-covering of the extended lattice of nodes of the polygon P by a line segment or as an edge of a polygon.

Proof. 

Let $conv(x_k,x_{k+1})$ be an edge of P that does not contain integer points except $x_k$ and $x_{k+1}$ and consider an arbitrary super-covering of the extended lattice of nodes of the polygon P. If $conv(x_k,x_{k+1})$ in super-covering, the assertion holds. If $conv(x_k,x_{k+1})$ is not in some super-covering, let us prove that $conv(x_k,x_{k+1})$ is in the super-covering which is dual of that one. Suppose the opposite, i.e., ${\tau }_i\left(x_k\right)\ne x_{k+1}$, for any translation ${\tau }_i$, determined by super-covering. It follows that ${\tau }_i\left(x_l\right)=x_{k+1}$, for some ${\tau }_i$ and some $l\ne k$. It is obvious that ${\tau }_i\left(x_k\right)$ is not on the same side of the line determined with $x_k$ and $x_{k+1}$ as the point $x_l$, that is contradiction to the construction of the convex hull of a finite planar set described in [18]. □

Definition 8.

Let $conv(x_1,x_2,\dots ,x_n)$ be an arbitrary convex polygon with integer vertices. Let $x_1$ be the vertex of the polygon with the smallest $x-$coordinate having simultaneously the largest $y-$coordinate and let $x_k$ be the vertex of the polygon with the smallest $y-$coordinate having simultaneously the largest $x-$coordinate. Consider the line determined by $x_1$ and $x_k$. Vertices of the polygon that lay on the same side of the line as origin are called inner vertices. Other vertices of the polygon are called outer vertices.

The following theorem is a direct consequence of Theorem 4.11 from [12]. We shall give two different proofs of the theorem that give an idea for the construction of an effective algorithm which generates integrally indecomposable Newton polygons with arbitrary many vertices.

Theorem 5.

Let $conv(x_1,x_2,\dots ,x_n)$ be an arbitrary convex polygon with integer vertices and let $x_l$ be an arbitrary outer vertex of the polygon. Let $x_{n+1}$ be an integer point such that:

1.

Line segment $conv(x_l,x_{n+1})$ does not contain any integer points except $x_l$ and $x_{n+1}$,

2.

All the points $x_1,\dots ,x_n$ except $x_l$ are on the same side of the line determined by points $x_l$ and $x_{n+1}$,

3.

Line segment $conv(x_l,x_{n+1})$ is larger than any parallel line segment whose vertices are integer points from $conv(x_1,x_2,\dots ,x_{n+1})$,

Then polygon $conv(x_1,x_2,\dots ,x_{n+1})$ is integrally indecomposable in the sense of Minkowski.

First Proof. 

Suppose the opposite, $conv(x_1,x_2,\dots ,x_{n+1})$ is integrally decomposable in the sense of Minkowski. From Lemma 2 it follows that extended lattice of nodes of the polygon has super-covering. Due to the point 2 in Theorem 5, line segment $conv(x_l,x_{n+1})$ is an edge of the polygon $conv(x_1,x_2,\dots ,x_{n+1})$. From point 1 in Theorem 5 and Lemma 3 it follows that line segment $conv(x_l,x_{n+1})$ is covered by that super-covering or dual super-covering. Consider the super-covering having $conv(x_l,x_{n+1})$. Then there exists a line segment whose vertices are from extended lattice of nodes of the polygon $conv(x_1,x_2,\dots ,x_{n+1})$ different from $x_l$ and $x_{n+1}$ that is congruent and parallel to the line segment $conv(x_l,x_{n+1})$, that is in contradiction to point 3 in Theorem 5. □

Second Proof. 

Let $B_1,\dots ,B_k$ be vertices of the polygon $conv(x_l,\dots ,x_{n+1})$ in counterclockwise order, where $B_1$ and $B_k$ correspond to the points $x_l$ and $x_{n+1}$. Let ${\left\{c_i{e}_i\right\}}_{1\le i\le k}$ be the edge sequence and the intersection of the lines $l(B_1,B_2)$ and $l(B_k,B_{k-1})$ is the point C. Let q be the line of symmetry of the angle $\angle B_{1}C{B}_k$. Note thet, according to the condition 1, $c_k=1$ holds. Denote with $p{r}_p^q\left(K\right)$ the set of points belonging to the line p which are projections of the points of a set K on the line p in the direction determined by q.

According to the point 2 in Theorem 5 and point 3 in Theorem 5, the point C exists and lays on the same side of the line $l(B_1,B_k)$ as the remaining vertices of the constructed polygon and $P=conv(x_1,x_2,\dots ,x_{n+1})\subseteq conv(B_1,C,B_k)$. Let $F=\{p{r}_p^q\left(conv\left(B_i{B}_{i+1}\right)\right)\mid 1\le i\le n-1\}$. Then all the elements of F are real line segments (not points) and intersection of any two elements from F the one neighboring point at most. Hence,

$$\sum _{x\in K}\mid x\mid =\mid B_1{B}_k\mid .$$

Suppose the opposite, i.e., that the polygon P is decomposable in the sense of Minkowski sum. Let $P=Q+R$. Without loss of generality, according to Lemma 1 it follows that ${\left\{d_i{e}_i\right\}}_{1\le i\le k}$ is the edge sequence of Q different from the edge sequence of P, with $0\le d_i\le c_i$ for $1\le i\le k-1$ and $d_k=c_k=1$. Then we will have $\mid B_1{B}_k\mid \le {\sum }_{1\le i\le n-1}\mid d_i{e}_i\mid <{\sum }_{x\in K}\mid x\mid =\mid B_1{B}_k\mid$ (the inequality is strict due to the fact that $p{r}_p^q\left(e_i\right)$ are real line segments, not the points), that is an obvious contradiction. □

Remark 2.

Inner vertices of the polygon, as well as the vertex of the polygon with the smallest $x-$coordinate having simultaneously the largest $y-$coordinate and the vertex of the polygon with the smallest $y-$coordinate having simultaneously the largest $x-$coordinate, are also vertices of the polygon $conv(x_1,x_2,\dots ,x_{n+1})$. Therefore, absolute irreducible bivariate polynomials generated by $conv(x_1,x_2,\dots ,x_{n+1})$ have non-zero monomials corresponding to those vertices.

Example 1.

Consider the line segment:

$$conv\left(\right(2,1),(0,9\left)\right).$$

It is obvious that:

$$GCD\left(\right(0,9)-(2,1\left)\right))=GCD(-2,8)=2.$$

From Theorem 3 it follows that line segment $conv\left(\right(2,1),(0,9\left)\right)$ shown in Figure 1 is integrally decomposable.

The point $(0,9)$ is outer vertex. Due to the fact that:

$$GCD\left(\right(13,0)-(0,9\left)\right)=GCD(13,-9)=1,$$

from Theorem 3 it follows that line segment $conv\left(\right(0,9),(13,0\left)\right)$ does not contain any integer points except $(0,9)$ and $(13,0)$. It is obvious that conditions of Theorem 5 are satisfied, so triangle $conv\left(\right(13,0),(0,9),(2,1\left)\right)$ (see Figure 2) is integrally indecomposable.

Therefore, the polynomial

$$f(x,y)=a_1{x}^{13}+a_2{y}^9+a_3{x}^{2}y,$$

$a_1,a_2,a_3\in F\backslash \left\{0\right\}$, is absolutely irreducible over an arbitrary field F. It remains absolutely irreducible over F if some monomials whose exponent vectors lay inside the triangle $conv\left(\right(13,0),(0,9),$$(2,1))$ or on its edge are added. In other words, each polynomial:

$$f(x,y)=a_1{x}^{13}+a_2{y}^9+a_3{x}^{2}y+\sum c_{ij}{x}^i{y}^j,$$

with $a_1,a_2,a_3\in F\backslash \left\{0\right\}$, $(i,j)\in conv\left(\right(13,0),(0,9),(2,1\left)\right)\backslash \left\{\right(13,0),(0,9),(2,1\left)\right\}$ is absolutely irreducible over F.

Analogously, e.g., by adding point (17,14) to the triangle $conv\left(\right(13,0),(0,9),(2,1\left)\right)$, integrally indecomposable quadrilateral $conv\left(\right(13,0),(0,9),(2,1),(17,14\left)\right)$ shown in Figure 3 is obtained.

Therefore, each polynomial:

$$f(x,y)=a_1{x}^{13}+a_2{y}^9+a_3{x}^{2}y+a_4{x}^{17}{y}^{14}+\sum c_{ij}{x}^i{y}^j,$$

with $a_1,a_2,a_3,a_4\in F\backslash \left\{0\right\}$, $(i,j)\in conv\left(\right(13,0),(0,9),(2,1),(17,14\left)\right)$ is absolutely irreducible over F.

3. Constructions of Integrally Indecomposable n-Gons

Lemma 4.

Let $i,j$ be natural numbers, such that $GCD(i,j)=1$, $i>1$. Let p be the line determined by $iy-jx=0$ and $A(c,d)$ be an integer point laying above the line p. Then, for an arbitrary natural number k, there exists an integer point $B(x_0,y_0)$ below the line p, such that the angle between the line p and the line containing line segment $AB$ is less than arctan 2^−k−arctan 2^−k−1 and line segment $AB$ contains no integer points except its vertices.

Proof. 

As $i>1$, it follows that there exists a natural number m such that the point $C(0,j-i^m)$ is at a greater distance from the line p than the point A (see Figure 4). The previous holds for the big enough natural number m.

Let q be the line determined by $iy-jx=i(j-i^m)$. Line q contains point C and is parallel with the line p. For each natural number t, line q contains the point $(x_t,y_t)=(i^t·i,i^t·j+j-i^m)$. Also, for each natural number t, $GCD(x_t,y_t)=1$ holds. From Theorem 3 it follows that the line segment $conv((x_t,y_t),(0,0))$ contains no integer points except its vertices. There exists big enough natural number $t_0$ such that for the point $D(x_{t_0},y_{t_0})$, $\angle pOD<$ arctan 2^−k−arctan 2^−k−1 holds.

Let $x_0=x_{t_0}+c$, $y_0=y_{t_0}+d$ and let $B(x_0,y_0)$. Due to the fact that the angle between the line p and the line containing the line segment $AB$ is less than arctan 2^−k−arctan 2^−k−1, point B lays below the line p and the line segment $AB$ contains no integer points except its vertices. □

The following corollary is a consequence of Lemma 4.

Corollary 1.

Let p be the line determined by $iy-jx=if-je$, with $i,j,e,f$ natural numbers such that $GCD(i,j)=1$ and $i>1$. Let $A(c,d)$ be an integer point that lays above the line p. Then for an arbitrary natural number k there exists an integer point $B(x_0,y_0)$ under the line p, such that the angle between the line p and the line containing the line segment $AB$ is less than arctan 2^−k−arctan 2^−k−1 and the line segment $AB$ contains no integer points except its vertices.

Theorem 6.

There exist an infinite sequence of monomials $p_1,p_2,\dots ,p_n,\dots$ such that the polynomial $f_n={\sum }_{j=1}^n{p}_i$ is absolutely irreducible over F for each natural number $n>1$ and the corresponding Newton polygon has n vertices.

Proof. 

Let us denote by $A_i$ vertex corresponding to the monomial $p_i$, $i=1,2,\dots$. From Theorems 3 and 4 it follows that there exist monomials $p_1,p_2,p_3$ such that $A_1$ lays on the x-axis and $A_2$ lays on the y-axis, polynomials $f_2$ and $f_3$ are absolutely irreducible over F and slope coefficient of the line that contains the line segment $A_2{A}_3$ is less than 1 (see Figure 5). There exists natural number k such that $2^{-k}$ is less than the slope coefficient of the line that contains the line segment $A_2{A}_3$.

Let us prove by induction, for $n>3$, that there exist integer points $A_4,A_5,\dots ,A_n$ in the first quadrant that satisfy conditions of the Corollary 1 and slope coefficient of the line that contains the line segment $A_{n-1}{A}_n$ is greater than $2^{-k-n+3}$, for each $n>3$.

Consider the line $q_4$ that contains the point $A_1$ and has the same slope coefficient as the line that contains the line segment $A_2{A}_3$. From Corollary 1 it follows that there exists point $A_4$ that lays on the other side of the line $q_4$ than the polygon $P_{f_3}$, $A_3{A}_4$ has no integer points except its vertices and the angle between the line $q_4$ and the line containing the line segment $A_3{A}_4$ is less than arctan 2^−k−arctan 2^−k−1. The slope coefficient of the line that contains the line segment $A_3{A}_4$ is greater than $2^{-k-1}$. The projection of the polygon $P_{f_3}$ in direction of the line $q_4$ on the line containing the line segment $A_3{A}_4$ is contained in the line segment $A_3{A}_4$. From Theorem 5 it follows that polygon $conv(A_1,A_2,A_3,A_4)$ is integrally indecomposable in the sense of Minkowski and has four vertices.

Let us suppose that there exist integer points $A_4,A_5,\dots ,A_{n-1}$ in the first quadrant that satisfy conditions of the induction hypothesis and slope coefficients of the lines that contain line segments $A_{i-1}{A}_i$ are bigger than $2^{-k-i+3}$, for each $3<i<n$ (see Figure 6). Let $q_n$ be the line that contains point $A_1$ and has the same slope coefficient as the line segment $A_{n-2}{A}_{n-1}$ bigger than $2^{-k-n+4}$. From Corollary 1 it follows that there exists a point $A_n$ that lays on the other side of the line $q_n$ than the polygon $P_{f_{n-1}}$, $A_{n-1}{A}_n$ has no integer points except its vertices and the angle between the line $q_n$ and the line containing the line segment $A_{n-1}{A}_n$ is less than arctan 2^−k−n+4−arctan 2^−k−n+3. The slope coefficient of the line that contains the line segment $A_{n-1}{A}_n$ is greater than $2^{-k-n+3}$. The projection of polygon $P_{f_{n-1}}$ in the direction of the line $q_n$ on the line $A_{n-1}{A}_n$ is contained in the line segment $A_{n-1}{A}_n$. According to Theorem 5 polygon $conv(A_1,A_2,\dots ,A_n)$ is integrally indecomposable in the sense of Minkowski and has n vertices. □

4. Conclusions

Proving a special case of Gao’s theorem presented in the paper enabled construction of an effective algorithm for building integrally indecomposable convex integral polygons with arbitrary many vertices and thus generating classes of absolute irreducible bivariate polynomials.