J Ér

Émy Berthomieu
email: berthomieu@lix.polytechnique.fr

G R Égoire Lecerf
email: gregoire.lecerf@math.cnrs.fr

REDUCTION OF BIVARIATE POLYNOMIALS FROM CONVEX-DENSE TO DENSE, WITH APPLICATION TO FACTORIZATIONS

Keywords: 2010 Mathematics Subject Classification. Primary 12Y05, Secondary 68W30, 11Y16, 12D05, 13P05 Polynomial factorization

In this article we present a new algorithm for reducing the usual sparse bivariate factorization problems to the dense case. This reduction simply consists in computing an invertible monomial transformation that produces a polynomial with a dense size of the same order of magnitude as the size of the integral convex hull of the support of the input polynomial. This approach turns out to be very efficient in practice, as demonstrated with our implementation.

Introduction

Let K be a field. Throughout this paper, F represents the bivariate polynomial in the variables x and y over K that we want to factor. At the present time, the best known complexity bounds for the squarefree and irreducible factorization problems are essentially obtained in terms of the dense size of F . This is relevant to many situations but, in many others, it is important to take the sparsity of F into account. In this article, we present a simple method to transform F in a way that is compatible to factorizations, but so that the dense size becomes of the same order of magnitude as the size of the integral convex hull of the support of F . In the next paragraphs, we give precise definitions for the sparse and dense sizes, state our main complexity result on support reduction, and then corollaries on factorizations.

1.1. Sizes of polynomials. Let S be a finite subset of points in Z 2 . The bounding rectangle of S is the smallest rectangle of the form (o x , o y ) + [0, d x ] × [0, d y ] that contains S, where o x , o y ∈ Z and d x , d y ∈ N. We define the dense size of S as (d x + 1)(d y + 1). We write Int S for the integral convex hull of S, that is the set of integer points inside the convex hull of S seen as a subset of R 2 , so that Int S = Z 2 e∈S t e e|t e ∈ R ≥0 and e∈S t e = 1 .

The convex size of S is defined as the cardinality | Int S| of Int S.

For our purposes it will be convenient to consider bivariate Laurent polynomials. Any such polynomial F ∈ K[x, y, x -1 , y -1 ] can be stored as a vector of nonzero terms, with each term composed of a coefficient and an exponent, regarded as a vector in Z 2 . This storage is usually called the sparse representation of F . For any (i, j) ∈ Z 2 , we let F i,j denote the coefficient of x i y j in F . The support of F is defined as Supp F = (i, j) ∈ Z 2 |F i,j = 0 . The sparse size of F , written σ, refers to the cardinality of the support of F . We also define the dense size (resp. the convex size) of F as the dense size (resp. convex size) of its support.

The Newton polygon of F , written Newton F , is the convex hull of the support of F in R 2 . If F factors into GH, then it is known from Ostrowski [START_REF] Ostrowski | Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra[END_REF] (translated in [START_REF]On the significance of the theory of convex polyhedra for formal algebra[END_REF], and revisited later in [START_REF]On multiplication and factorization of polynomials, I. Lexicographic orderings and extreme aggregates of terms[END_REF]) that:

Newton F = Newton G + Newton H = {a + b|a ∈ Newton G, b ∈ Newton H} .
The latter sum of the convex hulls of G and H is usually called the Minkowski sum. In general, even if the sparse size of F is small compared to its convex size, the irreducible factors of F can be dense with respect to their Newton polygons, what we call convex-dense for short. For example, simply consider F = y p -x p ∈ Q[x, y], where p is a prime integer: here σ = 2 and F factors into x -y and F/(x -y) whose sparse size is exactly p. This shows that the irreducible factorization of F cannot be achieved in time polynomial in σ, and that the convex size of F is a relevant quantity to analyze the complexity of factorization problems.

Example 1.1. Let F = x -1 y -1 + 1 + 2x 3 + 3y 2 . The sparse size of F is σ = 4. The Newton polygon of F is drawn in following Figure 1: the black disks represent the monomials of F , while the white disks are the other monomials contained in the Newton polygon. The convex size of F is therefore π = 8, and since the bounding rectangle of the support of F is (-1, -1) + [0, 4] × [0, 3], the dense size of F is 20.

Figure 1. Newton polygon of F = x -1 y -1 + 1 + 2x 3 + 3y 2 . 1.2. Main result. The method we propose in this paper concerns all the usual types of factorization, including the squarefree, the irreducible and the absolute ones. Our main result is a pretreatment, applied to the input polynomial, which consists of a monomial transformation that preserves the sparse size and roughly the convex size, but decreases the dense size. The monomial transformations considered are the maps of the affine group over Z 2 , written Aff Z 2 . To be precise, these are the maps U

(1.1) U : (i, j) → α β α ′ β ′ i j + γ γ ′ ,
with α, β, γ, α ′ , β ′ , and γ ′ in Z, such that αβ ′ -α ′ β = ±1. Such a map U preserves the absolute value of the volumes in R 2 . Let S be a finite subset of Z 2 . The set S is said to be normalized if it belongs to N 2 and if it contains at least one point in {0} × N, and also at least one point in N × {0}. For such a normalized set, we write d x for the largest abscissa involved in S and, analogously, d y for the largest ordinate, so that the bounding rectangle

is R = [0, d x ] × [0, d y ].
The following theorem will be proven in Section 4.2: Theorem 1.2. For any normalized finite subset S of Z 2 , of cardinality σ, convex size π, bounding rectangle [0, d x ] × [0, d y ], and dense size δ = (d x + 1)(d y + 1), one can compute an invertible affine map U ∈ Aff(Z 2 ) as in (1.1), together with U (S), with O σ log 2 δ bit-operations, such that U (S) is normalized of dense size at most 9π.

Here, by the number of bit-operations we mean the size of the Boolean circuit that performs the computation, as in the computation tree model considered in [START_REF] Bürgisser | Algebraic complexity theory[END_REF]Chapter 4]. The rest of this introduction is devoted to applications of Theorem 2 to factorizations of bivariate polynomials. Roughly speaking, given a polynomial F with a small convex size compared to its dense size, we can use the algorithm underlying Theorem 1.2 on the support of F in order to construct another polynomial to factor, with the same convex size as F but with a dense size of the same order of magnitude as the convex size. Therefore, any fast factorization algorithm in terms of the dense size leads to a fast algorithm in terms of the convex size. Another important application of our Theorem 1.2, developed by Chèze in [START_REF] Chèze | A recombination algorithm for the decomposition of multivariate rational functions[END_REF], concerns the decomposition of multivariate rational functions.

The proof of Theorem 1.2 is organized as follows. In our first section we explain a naive approach to reduce S so that the ratio of the volumes of its convex hull and of its bounding rectangle increases. The second section provides us with a uniform bound on the latter ratio reached at the end of the reduction process. The last section is then devoted to a faster dichotomic reduction algorithm, to practical performances, and to a proof that our reduction technique leads to an essentially optimal volume ratio in the worst case.

1.3. Applications. We shall now explain how Theorem 1.2 can be used to reduce convex-dense factorization problems to the usual dense case. For the cost analysis we use the computation tree model for counting the number of operations in the ground field K. Let us recall that the "soft-Oh" notation f

(n) ∈ Õ(g(n)) means that f (n) ∈ g(n) log O(1) (3 + g(n)
) (we refer the reader to [GG03, Chapter 25, Section 7] for details).

If U is an affine map of Z 2 as in (1.1), then we consider its action on the monomials, and we write U (x i y j ) for x αi+βj+γ y α ′ i+β ′ j+γ ′ . By linearity, this action extends to K[x, y, x -1 , y -1 ] as follows:

U (F ) = (i,j)∈Supp F F i,j U (x i y j ).

Greatest common divisor.

A Laurent polynomial is said to be normalized if its support is normalized. Let F and G be two normalized polynomials in K[x, y] of degree at most d x in x and d y in y, and with supports included in a common convex polygon of convex size π. This situation naturally occurs for instance when computing the discriminant of F , say in y, where G is set to ∂ ∂y F .

Thanks to Theorem 1.2, we can compute a reduction map U with O σ log 2 δ bit-operations such that the partial degrees of F = U (F ) and G = U (G) are at most dx in x and dy in y, and with dx dy ∈ O(π). Without loss of generality we can further assume that dx ≥ dy , so that the computation of H = gcd( F , G) in K[x, y] can be done with Õ π 1.5 operations in K, assuming that K has cardinality at least (6 dy + 3) dx , by [GG03, Corollary 11.9, part i]. Under the same assumptions on the cardinality of K, a randomized variant can also obtain the same g.c.d. with an expected number of operations only in Õ(π), by [GG03, Corollary 11.9, part ii].

There exists a unit h in K[x, y, x -1 , y -1 ] (that is a term cx i y j with c invertible in K) such that H = hU -1 ( H) is normalized. We say that H is a normalization of U -1 ( H). By the aforementioned Ostrowski theorem, it is classical to deduce that H is the actual g.c.d. of F and G, and that the convex size of H is at most π. Finally, the computation of H from H takes Õ(π log δ) more bit-operations. Of course this approach leads to a significant speedup when compared to a direct application of [GG03, Corollary 11.9] as soon as π is much smaller than δ. Squarefree factorization. Let U be an invertible affine map over Z 2 as in Equation (1.1), and let L be the linear part of U . Let F still be a normalized polynomial in K[x, y] of degree at most d x in x and d y in y, of sparse size σ, and of convex size π. If the squarefree factorization of F writes into

F = F 1 1 F 2 2 • • • F r r
, where the F i are the pairwise coprime squarefree factors, then

L(F ) = L(F 1 ) 1 L(F 2 ) 2 • • • L(F r ) r .
As for the g.c.d., thanks to Theorem 1.2, we can compute a reduction map U with O σ log 2 δ bit-operations such that the partial degrees of F = U (F ) are at most dx in x and dy in y, and with dx dy ∈ O(π). Without loss of generality we can again assume that dx ≥ dy .

If K has characteristic 0, then the squarefree factorization of F takes Õ π 1.5 operations in K by [START_REF]Fast separable factorization and applications[END_REF]Proposition 8]. This cost further drops to an expected one in Õ(π) with the randomized variant of [Lec08, Proposition 9]. Then the squarefree factors can be easily deduced by applying U -1 and normalizing. Other algorithms of [START_REF]Fast separable factorization and applications[END_REF] concerning the separable factorization can be also adapted in the same way to benefit of sparsity.

Irreducible factorization. If F is a Laurent polynomial, then U (F ) is irreducible if, and only if, F is irreducible. If F is normalized, then F is irreducible in K[x, y] if, and only if, F is irreducible in K[x, y, x -1 , y -1 ]. The irreducible factorization in K[x,
y] can thus be deduced from the one in K[x, y, x -1 , y -1 ]. As for the squarefree factorization, we first compute a reduction map U , then we compute the irreducible factorization of U (F ), and finally we apply U -1 and normalize all the factors.

With this strategy, informally speaking, the algorithms of [START_REF]New recombination algorithms for bivariate polynomial factorization based on Hensel lifting[END_REF] for instance show that the number of operations in a prime finite field can grow with only Õ(π 1.5 ). In Section 4.3 we report on examples that illustrate the speedup gained thanks to the reduction process.

1.4. Related work. Fast arithmetic operations on sparse polynomials are still a matter of active research. At the present time, the best performances are achieved essentially with supports being close to rectangles, thanks to the Kronecker substitution that reduces the product to a single variable [GG03, Chapter 8, Section 4].

Recent progress has been accomplished for instance in [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial and series multiplication[END_REF], but even when softly linear time algorithms are available for the sparse product, the overhead compared to dense sizes remains important. These facts motivate the strategy of the present paper: by a direct reduction to the dense case we avoid relying on sparse arithmetic at all.

Concerning the irreducible factorization of bivariate polynomials, the Hensel lifting and recombination technique is the most popular. It leads to the best known complexity bounds [START_REF] Bostan | Complexity issues in bivariate polynomial factorization[END_REF][START_REF] Lecerf | Sharp precision in Hensel lifting for bivariate polynomial factorization[END_REF][START_REF]Improved dense multivariate polynomial factorization algorithms[END_REF][START_REF]New recombination algorithms for bivariate polynomial factorization based on Hensel lifting[END_REF] in the dense case. Hensel lifting is used in Bernardin's implementation within Maple [START_REF] Bernardin | On square-free factorization of multivariate polynomials over a finite field[END_REF][START_REF]On bivariate Hensel lifting and its parallelization[END_REF], and in Steel's one in Magma [START_REF] Steel | Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic[END_REF][START_REF] Belabas | Factoring polynomials over global fields[END_REF]. In order to benefit from fast Hensel lifting, which means here with a softly linear cost, in the bivariate case, one needs first to assume that F is separable, say in y, and then find a value x 0 such that F (x 0 , y) remains separable. Unfortunately the shift of x spoils the sparse and convex sizes. One possible solution consists in the direct computation of the irreducible factorization in K[[x]][y] but, at the present time, no algorithm with softly linear time is known for that task. Efforts have been made in this direction. For instance, in [START_REF] Salem | Factoring polynomials via polytopes[END_REF] an algorithm for computing a factor of a given convex support is designed for special cases, with time polynomial in the convex size of the input polynomial. In [START_REF] Belabas | Factoring polynomials over global fields[END_REF], Puiseux series solutions of F are computed directly, with no shift in x. The best known complexity bounds for the Puiseux expansions seem to be found in [START_REF] Poteaux | Calcul de développements de Puiseux et application au calcul du groupe de monodromie d'une courbe algébrique plane[END_REF][START_REF] Poteaux | Complexity bounds for the rational Newton-Puiseux algorithm over finite fields[END_REF]. Recently, in [START_REF] Weimann | A lifting and recombination algorithm for rational factorization of sparse polynomials[END_REF], Weimann proposed partial generalizations of the algorithms of [START_REF] Lecerf | Sharp precision in Hensel lifting for bivariate polynomial factorization[END_REF][START_REF]Improved dense multivariate polynomial factorization algorithms[END_REF]: if K is a number field, and if the polynomials supported by the exterior facets of the Newton polygon are separable, then, from their irreducible factors, one can deduce the factorization with O(π ω ) operations in K, where ω is the linear algebra exponent (known to be between 2 and 2.37, but unfortunately close to 3 in practice). Compared to these methods, our approach has the advantage that it can be performed from the outset with no separability assumption, that it does not need to compute the Newton polygon, and that it can benefit from fast Hensel lifting.

Another important class of factorization algorithms is due to Gao in [START_REF] Gao | Factoring multivariate polynomials via partial differential equations[END_REF], who showed that the absolute factorization can be performed in softly quadratic time in terms of the dense size. The first half of his algorithm consists in computing a basis of the first De Rham cohomology group of the complementary of the hypersurface defined by F . In [START_REF] Gao | Irreducibility of polynomials modulo p via Newton polytopes[END_REF] it has been shown that this task can be done in time polynomial in the convex size. When a fast sparse polynomial product is available, one can even compute the probable number of absolute factors in time softly quadratic in the convex size, over finite fields with sufficiently large characteristic [HL10, Section 7]. However these approaches still suffer an overhead when compared to the dense case, and it requires the input polynomial to be separable.

The factorization of sparse polynomials in terms of the sparse size is an active research area. Although this is not the main goal of the present article, let us mention briefly important results for multivariate polynomials. Polynomial time in terms of the sparse size of the output has been investigated by Zippel in [START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF][START_REF] Zippel | Newton's iteration and the sparse Hensel algorithm (Extended Abstract)[END_REF] (see also [START_REF]Effective Polynomial Computation[END_REF]Chapter 17]). Specifically, he proposed a probabilistic variant of Hensel lifting that runs in time polynomial in the total sparse size of the lifted factors of

F in K[[x]][y].
f d y d x h b d R 0 R A B C D E F G H (0; 0) O Figure 2.
Bounding octagon O and rectangles R and R ′ for S = {(2, 0) , (1, 1) , (5, 2) , (7, 2) , (2, 3) , (0, 4) , (7, 4) , (8, 4) , (5, 5)}.

the irreducible factors of a bounded given degree. A polynomial time bound has been proved recently for this task in [START_REF] Avendaño | Factoring bivariate sparse (lacunary) polynomials[END_REF] for two variables and, independently, in [START_REF] Kaltofen | Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields[END_REF] directly with several variables.

Support reduction

This section is devoted to the reduction algorithm underlying Theorem 1.2. We start with a naive version that is to be refined in Section 4.

2.1. Bounding rectangles. Let S be a normalized finite subset of Z 2 with bound-

ing rectangle R = [0, d x ]×[0, d y ].
We introduce the integers b, d, f and h as follows:

• b = d x -max (i,j)∈S (i -j), • d = d x + d y -max (i,j)∈S (i + j), • f = d y + min (i,j)∈S (i -j), • h = min (i,j)∈S (i + j).
Then, let us define the following eight points, drawn in Figure 2 above:

A = (h, 0) , B = (d x -b, 0) , C = (d x , b) , D = (d x , d y -d) , E = (d x -d, d y ) , F = (f, d y ) , G = (0, d y -f ) , H = (0, h) .
The rectangle R ′ supported by lines (AH), (BC), (DE), (F G) is the smallest rectangle containing S whose edges are parallel to the two main bissectors. The octagon O = ABCDEF GH contains S and any of its edges contains a point of S, O is the bounding octagon of S.

2.2. Elementary transformations. Our reduction algorithm will only use the three following elementary transformations. The first one, written λ, corresponds to substituting y/x into y, this yields the following map of Z 2 :

λ : Z 2 → Z 2 (i, j) → (i -j, j) .
We will need to swap x and y. This is the role of µ:

µ : Z 2 → Z 2 (i, j) → (j, i) .
Finally, translations in x are necessary to normalize the supports occurring in the reduction algorithm: in S that are sent to the far left of λ(S) are such that i -j is minimal. Analogously, those that are sent to the far right of λ(S) are such that i -j is maximal. Applying λ -1 instead of λ will result in the horizontal length of the new R being the difference between max (i + j) and min (i + j), namely d x + d y -d -h, as illustrated by Figure 4.

τ k : Z 2 → Z 2 (i, j) → (i + k, j) .
From now on and until the end of this article, η represents a real number in [0, 3/4). h Definition 2.1. A finite subset S of Z 2 is said to be η-reduced whenever S is normalized, with d x greater than or equal to d y , and such that b, d, f and h, as defined in Section 2.1, satisfy the following two conditions:

(A) (F ) (G) (H ) d x b d y + f (0; 0) (B) (C) (D) (E)
1 (A) 1 (H ) 1 (G) d x + d y d (0; 0) 1 (B) 1 (C) 1 (E) 1 (F ) 1 (D)
b + f ≤ (1 + η)d y and d + h ≤ (1 + η)d y .
If S has only one point, then it is already η-reduced. In the next subsection, we propose an algorithm for reducing any finite subset of points of Z 2 . We shall see that η is used for controlling the tradeoff between the quality of the reduction and the time needed to reduce. The strongest reduction corresponds to η = 0. 2.4. Degenerate case. In this subsection we consider the case when S is degenerate, which means that all the points of S are aligned. If S is normalized and is a singleton, then it is the origin and it is already η-reduced, whatever the value of η is. Otherwise we have the following proposition: Proof. According to the hypotheses, the following two situations can occur: the points of S are either on the segment between (0, 0) and (d x , d y ), or on the segment joining (0, d y ) to (d x , 0). Let us first deal with the former case. Let g ≥ 0 be the g.c.d. of d x and d y , and let u and v be the Bézout coefficients so that g = ud x + vd y holds with |u| ≤ d y and |v| ≤ d x . We refer the reader to [GG03, Lemma 3.12] for instance for these classical facts. We take U to be the linear map whose matrix is

u v -d y /g d x /g .
Since Int S = {(id x /g, id y /g)|i ∈ {0, . . . , g}} we have that π = g + 1 and that U (Int S) is the segment joining (0, 0) to (g, 0). It follows that U (S) has dense size exactly π. The latter case, where S is on the segment joining (0, d y ) to (d x , 0), is similar, taking

U : (i, j) → -u v d y /g d x /g i j + ud x -d x d y /g .
By [GG03, Theorem 3.13] the computation of g, u, and v can be done with O(log 2 δ) bit-operations using the naive version of the Euclidean algorithm. Then applying U to all the points of S takes O σ log 2 δ bit-operations by multiplying naively the integers in quadratic time [GG03, Chapter 2, Section 3].

We remark that the value of η does not intervene in this degenerate case.

2.5. Reduction algorithm. Until the end of this section we assume that S is a nondegenerate finite set of points. The following algorithm computes U ∈ Aff Z 2 such that U (S) is η-reduced.

Algorithm 1. Support reduction.

Input: a nondegenerate normalized finite subset S of N 2 of cardinality σ, and a real number η in 0, 3 4 . Example 2.4. Assume η = 0 and let F = 1 + xy + x 5 y 2 , whose support S is {(0, 0) , (1, 1) , (5, 2)}, as drawn in Figure 5 below. After the first step of the algorithm, where λ is applied, S becomes as in the left part of Figure 6. In the second step, λ is applied once more and makes S reduced, as shown in the right part of Figure 6. In the end, the algorithm returns U = τ 1 • λ 2 , so that we have U (F ) = x + y + x 2 y 2 . The bounding rectangle of U (F ) corresponds to d x = d y = 2, while its bounding octagon O is defined by b = f = h = 1, and d = 0. Example 2.5. Let S be {(0, 0) , (1, 1) , (5, 2)} as in Example 2.4 and Figure 5, and assume η = 1/2. Since b + f = 4 and (1 + η) d y = 3, the input set S can be reduced by applying λ to obtain the same set as in the left part of Figure 6. However, after this reduction, we have b + f = 3 which is not strictly greater than (1 + η) d y = 3. We thus see with this example that the reduction process stops earlier with η = 1/2 than with η = 0. 2.6. Bit-cost analysis. The main difficulty in analyzing the bit-cost of Algorithm 1 resides in bounding the size of the entries of the map U . This is the purpose of the following lemma: Proof. Since the maximum of d x and d y never increases during the main loop, the bit-size of the points in S remains in O(log δ). Therefore Lemma 2.6 implies that all the entries in U also remain bounded by O (log δ) at every step. Each reduction step thus takes O(σ log δ) bit-operations. The conclusion follows from Proposition 2.3.

Output: U ∈ Aff(Z 2 ), such that U (S) is η-reduced. Compute (d x , d y ) for S,
(3) If b + f > (1 + η) d y then S := τ dy-f • λ(S) U := τ dy-f • λ • U d x := d x + d y -b -f else if d + h > (1 + η) d y then S := τ -h • λ -1 (S) U := τ -h • λ -1 • U d x := d x + d y -d -h else return U .
|α(x B -x A ) + β(y B -y A )| ≤ dx |α(x C -x A ) + β(y C -y A )| ≤ dx . . It follows that |α(x B -x A )(x C -x A ) + β(y B -y A )(x C -x A )| ≤ d x dx |α(x C -x A )(x B -x A ) + β(y C -y A )(x B -x A )| ≤ d x dx , whence |β||(y B -y A )(x C -x A ) -(y C -y A )(x B -x A )| ≤ 2d x dx . Since |(y B -y A )(x C -x A ) -(y C -y A )(x B -x A )|

Dense size of reduced sets

Let S be a finite subset of Z 2 . In this section, we carry on using the notation of Section 2.1, and we further write Vol S for the volume of the convex hull of S. In the next paragraphs, we show that Vol S cannot be too small compared to the volume Vol R of the bounding rectangle R of S, whenever S is reduced. In the second subsection, we deduce similar bounds in terms of discrete sizes while taking care of the degenerate cases.

Continuous bound.

Recall that η is a real constant in [0, 3/4). The following theorem guarantees that the volume spanned by an η-reduced set of points can be uniformly controlled in terms of the volume of its bounding rectangle: Theorem 3.1. If S is an η-reduced set of points, then Vol S ≥ 3-4η 8 Vol R, where R is the bounding rectangle of S.

Proof. In Lemma 3.2 below, we shall show that the volume of S is larger or equal to the volume of at least one of the following polygons:

Q 1 = ACEG, Q 2 = BDF H, P 1 = ABDEG, P 2 = BCEGH, P 3 = BCEF H, P 4 = BDEGH, P 5 = ABDF G, P 6 = ACDF H, P 7 = ACEF H, P 8 = ACDF G.
Then, Lemma 3.3 asserts that Vol Q i ≥ 1-η 2 Vol R, for all i ∈ {1, 2}. And finally, for the eight pentagons, the combination of Lemmas 3.4 and 3.6 below provides us with Vol P i ≥ 3-4η 8 Vol R, for all i ∈ {1, . . . , 8}. Lemma 3.2. Let S be a normalized finite set of points (not necessarily η-reduced). Then at least one of the polygons Q 1 , Q 2 , P 1 ,...,P 8 defined above has at most Vol S.

Proof. From the definitions of the bounding rectangle, and of b, d, f , h, there exist eight points I, J, K, L, M , N , O and P in S such that I ∈ [AB], J ∈ [BC] , . . . , P ∈ [AH], as drawn on the following figure (note that some of these points may coincide in particular degenerate cases): • If I, K, M and O all move counterclockwise, then we get the polygon BJDLF N HP whose volume is at least Vol Q 2 . • Otherwise two consecutive points among the cycle I, K, M , and O move into opposite directions. We now remark that the symmetries i → d x -i, j → d y -j and (i, j) → (j, i) preserve the problem, the volumes, exchange the roles of Q 1 and Q 2 , and globally preserve the set of the eight pentagons P 1 , . . . , P 8 . We can thus restrict ourselves to considering for instance the case for when I moves to B and K moves to C, and examine the following subcases:

-

M
Vol Q i ≥ 1 -η 2 Vol R, for i ∈ {1, 2}. G H F D C E B A Figure 8. Quadrangle Q 1 in octagon O and rectangle R.
Proof. Since the roles of Q 1 and Q 2 are interchanged by the symmetry i → d x -i, it suffices to prove the lemma for Q 1 only. We compute the volume of Q 1 as the difference between the volume d x d y of the bounding rectangle and the volume of the four triangles outside of Q 1 : Proof. Thanks to the symmetries, it suffices to prove the lemma for P 1 . The volume of P 1 is computed as the difference of the volume of R with those of the four triangles outside of P 1 :

Vol Q 1 = d x d y -(d x -h)b/2 -(d y -b)d/2 -(d x -d)f /2 -(d y -f )h/2 = 1 2 (d y -b -f ) (d x -d -h) + 1 2 d x d y . (3.1) Since S is η-reduced, we have (1 + η) d y -b -f ≥ 0, d x -d-h ≥ 0, thus d y -b -f ≥ -ηd y . This yields Vol Q 1 ≥ 1 2 d x d y -η 2 d x d y = 1-η 2 Vol R. Lemma 3.4. If S is an η-reduced set of points, then Vol P i ≥ 3 -4η 8 Vol R, for i ∈ {1, 3, 5, 7} .
Vol P 1 = Vol R - 1 2 b (d y -d) + d 2 + f (d x -d) + h (d y -f ) .
From (3.1) we deduce that:

Vol P 1 -Vol Q 1 = 1 2 (b (d x -d y -h) + d (d y -d)) .
Then, from

4b (d x -d y -h) + d 2 y = 4b(d x -b -h) + (2b -d y ) 2 , and d x -b -h ≥ 0, it follows that 4b (d x -d y -h) + d 2 y ≥ 0, and that Vol P 1 - Vol Q 1 ≥ -1 8 d 2 y .
The conclusion comes from Lemma 3.3: Proof. Thanks to the symmetries, it suffices to prove the lemma for P 2 . Specifically we shall prove that the following quantity is nonnegative:

Vol P 1 ≥ 1 -η 2 d x d y - 1 8 d 2 y ≥ 3 -4η 8 Vol R.
θ (b, d, f, h) = 8 Vol P 2 -(3 -4η) Vol R = (5 + 4η) d x d y + 4h (b -d x ) -4b 2 + 4d (b -d y ) + 4f (d -d x ) = (1 + 4η) d x d y + 4 (d x -d) (d y -f -h) -4 (b -d) (b -h) . Since f + h ≤ d y , we have that (1 + 4η) d x d y + 4 (d x -d) (d y -f -h) ≥ 0. There- fore, if h ≥ b ≥ d or d ≥ b ≥ h, then the lemma is proved. Otherwise, if b ≤ d and b ≤ h, |b -d| |b -h| is maximal for b = 0 and, for d = h = (1 + η) d y /2, since d + h ≤ (1 + η) d y . It follows that -4 (b -d) (b -h) ≥ -(1 + η) 2 d 2 y . From d x ≥ d y and η ∈ [0, 3/4) we deduce that (1 + 4η) d x ≥ (1 + η) 2 d y ,
≥ h. Using d x -d ≥ b -d, we obtain: θ (b, d, f, h) ≥ (1 + 4η) d x d y + 4 (b -d) (d y -b -f ) .
Then applying b + f ≤ (1 + η)d y leads to:

θ (b, d, f, h) ≥ (1 + 4η) d x d y -4 (b -d) ηd y ≥ (1 + 4η) d x d y -4ηd x d y ≥ 0,
which concludes the proof.

3.2. Discrete bound. For our algorithmic purposes, we need to control the number of integral points in the convex hull, instead of its volume.

Vol S = 1 2 | Int b S| + | Int i S| -1.
It follows that π ≥ Vol S, and that π ≥ 3-4η 8 d x d y by Theorem 3.1. Whenever d y = 1, we have b

+ d + f + h ∈ {0, 1, 2}. If b + h = 1 and d + f = 1, then from b + f ≤ 1 and d + h ≤ 1, we can deduce that f = h which implies f = h = 0 because f + h ≤ 1. Therefore, b = d = 1, which is impossible since b + d ≤ 1. Finally, we must have b + h = 0 or d + f = 0, hence π ≥ d x + 1.
If d y ≥ 2, the conclusion follows from d x ≥ 2(d x + 1)/3 and d y ≥ 2(d y + 1)/3.

Remark 3.8. In the case for when η = 0, if α is such that the inequality α| Int R| ≤ | Int S| holds for every reduced finite subset S in Z 2 , with Vol S > 0, then necessarily we have that α ≤ 3/8. In fact it suffices to consider the family S n = {(n/2, 0) , (0, n/2) , (n, n)} for n even. We have

| Int S 2 | = 4 and | Int S n+2 | = | Int S n | + 3 n 2 + 1 , and deduce that | Int S n | | Int R n | = 3n (n + 2) + 8 8 (n + 1)
2 is decreasing and converges to 3/8. In general, the constant 3-4η 18 thus may be rather pessimistic for large S.

Faster reduction algorithm

The last ingredient now missing to prove Theorem 1.2 is a reduction algorithm with a number of reduction steps that grows only with the logarithm of the dense size. This is the goal of this section. 4.1. Dichotomic approach. This section is dedicated to a fast variant of Algorithm 1. We do not compute exactly the same output, however. Roughly speaking, the main idea is to determine quickly how many times λ or λ -1 can be applied before two consecutive swaps.

Let S be a normalized finite subset of N 2 with bounding rectangle [0, d x ]×[0, d y ], and let q be a positive integer. The points (i, j) in S that are sent to the far left of λ q (S) are such that i -qj is minimal. Analogously, those that are sent to the far right of λ q (S) are such that i -qj is maximal. This motivates the introduction of b q , d q , f q , and h q as

• b q = d x -max (i,j)∈S (i -qj), • d q = d x + qd y -max (i,j)∈S (i + qj), • f q = qd y + min (i,j)∈S (i -qj),
• h q = min (i,j)∈S (i + qj).

For q = 1, these definitions coincide with those of b, d, f , and h of Section 2.1. The following inequalities hold:

b q + d q ≤ qd y , b q + h q ≤ d x , f q + h q ≤ qd y , d q + f q ≤ d x .
The height of the bounding rectangle of λ q (S) is still d y , while the horizontal length becomes d x + qd y -b q -f q . In the same manner, the horizontal length of the bounding rectangle of λ -q (S) becomes d x + qd y -d q -h q . From now on, the reduction factor η is supposed to be positive, that is in (0, 3/4). We write ⌊a⌋ for the integer part of a (⌊a⌋ ≤ a < ⌊a⌋ + 1), and log 2 a for the logarithm of a in base 2. The fast algorithm we propose summarizes as follows:

Algorithm 2. Dichotomic support reduction.

Input: a nondegenerate normalized finite subset S of N 2 of cardinality σ, and a real number η in 0, 3 4 . Output: U ∈ Aff(Z 2 ), such that U (S) is η-reduced.

m + f 2 m > 2 m (1 + η) d y then S := τ 2 m dy-f 2 m • λ 2 m (S) U := τ 2 m dy-f 2 m • λ 2 m • U d x := d x + 2 m d y -b 2 m -f 2 m else if d 2 m + h 2 m > 2 m (1 + η) d y then S := τ -h 2 m • λ -2 m (S) U := τ -h 2 m • λ -2 m • U d x := d x + 2 m d y -d 2 m -h 2 m . (5) m := m -1.
Proposition 4.1. Assume that η > 0. For any nondegenerate normalized finite subset S of N 2 , of cardinality σ and dense size δ, Algorithm 2 is correct and runs in O σ log 2 δ bit-operations.

Proof. Let us consider that the bounding rectangle of S is [0, d x ] × [0, d y ] at input. Without loss of generality, we can assume that d x ≥ d y holds in order to simplify the proof. Then we let ℓ 0 = d x and ℓ 1 = d y , and define the sequence (S i ) i with S 0 = S and S i is the current value of the set just after the ith swap, that is at the end of step 1. We write r for the total number of swaps performed during the execution of the algorithm, we let ℓ i be the largest abscissa in S i , and m i be ⌊log 2 (ℓ i / (ηℓ i+1 ))⌋. By convention, ℓ r+1 is the largest ordinate in S r .

For when i+2 ≤ r holds, we have that ℓ i+2 ≤ ℓ i -ηℓ i+1 . By descending induction, starting with ℓ r ≥ 1 and ℓ r-1 ≥ 1, we shall prove that ℓ i ≥ ϕ r-i-1 , where ϕ is the positive root η+ √ 4+η 2 2 > 1 of the characteristic equation x 2 -ηx -1 = 0. Since this is true for i = r and i = r -1, and since ℓ i ≥ ηℓ i+1 + ℓ i+2 ≥ ηϕ r-i-2 + ϕ r-i-3 = ϕ r-i-1 , we deduce that d x = ℓ 0 ≥ ϕ r-1 . The number of swaps r thus drops to O (log d x ).

By Lemma 2.6, since all the S i are normalized, each reduction step amounts to O (σ log δ) bit-operations. On the other hand the total number of steps is

r i=0 m i , r i=0 m i ∈ O r i=0 log 2 ℓ i ℓ i+1 + r log 2 1 η ∈ O (log δ) ,
which concludes the cost analysis. We shall prove that when the algorithm stops, the final value of S is η-reduced. We now focus on what happens just after the last swap. In short, we let M be m r and T M+1 be S r . We denote by T m the current value of S just before entering step 6, where m being the corresponding current value of m. Therefore T 0 corresponds to the output of the algorithm and we want to prove that it is η-reduced. If T 0 = T 1 then we are done.

If A is a subset of points, then we write ℓ x (A) for the horizontal length of the bounding rectangle of A. Let us now assume that T 0 is the normalization of λ(T 1 ). In this case, of course, λ -1 does not reduce T 0 . Let us prove that λ does not reduce T 0 either. If T m were the normalization of λ 2 m (T m+1 ) for all m in {0, . . . , M }, then we would deduce that

ℓ x (T 0 ) ≤ ℓ x (T M+1 ) - M m=0 2 m ηℓ r+1 = ℓ r -(2 M+1 -1)ηℓ r+1 < ℓ r -(ℓ r /(ηℓ r+1 ) -1)ηℓ r+1 = ηℓ r+1 ,
which is impossible. Therefore there exists a largest integer µ ∈ {0, . . . , M } such that for all m in {0, . . . , µ -1}, T m is the normalization of λ 2 m (T m+1 ). This yields that T 0 is the normalization of λ 2 µ -1 (T µ ) and also that (4.1)

ℓ x (T 0 ) < ℓ x (T µ ) -(2 µ -1) ηℓ r+1 .
One of the following two cases arises:

• If T µ = T µ+1 then we have that ℓ x (λ(T 0 )) = ℓ x (λ 2 µ (T µ )) = ℓ x (λ 2 µ (T µ+1 )) ≥ ℓ x (T µ+1 ) -2 µ ηℓ r+1 .
Combined with (4.1) it follows that ℓ x (λ(T 0 )) > ℓ x (T 0 ) -ηℓ r+1 , and hence that T 0 is η-reduced. • Otherwise, if T µ is the normalization of λ -2 µ (T µ+1 ), then we have that ℓ x (T µ ) < ℓ x (T µ+1 ) -2 µ ηℓ r+1 , so that

ℓ x (T 0 ) ≤ ℓ x (T µ+1 ) -(2 µ+1 -1)ηℓ r+1 .
Since T µ+1 is the normalization of λ(T 0 ), we deduce that

ℓ x (λ(T 0 )) = ℓ x (T µ+1 ) ≥ ℓ x (T 0 ) + (2 µ+1 -1)ηℓ r+1 ,
whence that T 0 is η-reduced. Finally the last case for when T 0 is the normalization of λ -1 (T 1 ) can be treated in the same way.

Remark 4.2. At each step of the algorithm, the current degree, say dy , in y, is smaller than the initial d y . Therefore whenever one chooses η < 1 dy from the outset, the reduction is at least dy dy = 1. Therefore the algorithms behaves the same as with η = 0 and Proposition 4.1 is still valid if η = 0. However, there is no uniform η > 0 such that, for every input, the behaviour of the algorithm is the same as with η = 0. 4.2. Proof of Theorem 1.2. We prove a slightly more precise theorem than Theorem 1.2, which contains bounds on the bit-size of the entries of the affine map U : Proof. Proposition 2.2 already covers the degenerate case. In the nondegenerate situation, the theorem follows from Proposition 3.7 for the dense size of the output, from Proposition 4.1 with taking η = 1/4 for the bit-complexity, and from Lemma 2.6 for the size of the entries of U .

4.3. Timings. We report on performances obtained with our implementation in Maple 14 for computing the irreducible factorization of the following polynomials in Q[x, y]:

P n = x n+1 + n i=0 ix i y n-i y n+1 + n i=0 (n -i)x i y n-i × x ⌊ n 2 ⌋-1 y ⌊ n 2 ⌋-1 + n i=0 x i y n-i .
The source code is available from http://www.lix.polytechnique.fr/~berthomieu/convex-dense.htm.

In As expected, our reduction strategy leads to a significant speedup. In fact, with this family, notice that the dense size grows with n 2 while the convex size only grows with n. We have also tried Algorithm 2: the gains are not substantial since most of the time is spent in the factorization. Finally let us mention that one could investigate the design of a reduction algorithm featuring a dichotomy in the size of the exponents, in a way similar to the half-g.c.d. algorithm (see for instance [START_REF] Zur Gathen | Modern computer algebra[END_REF]Chapter 11]). This would probably lead to a bit-complexity bound in Õ (σ log δ). However, the practical impact would be minor as long as the sizes of the exponents are intended to fit into one machine word. 4.4. Optimality of the reduction. It is natural to ask if our algorithm computes the best transformation U of Z 2 , that maximizes the ratio of the volumes of U (S) and R(U (S)), where R(U (S)) represents the bounding rectangle of U (S).

First, let us mention that the transformations λ, µ and τ 1 used within our algorithm actually generate Aff Z 2 . In fact it is classical that SL Z 2 is generated by λ and the rotation ρ = 0 -1 1 0 by the angle π/2 [Ser96, Chapter 7, Theorem 2]. Since ρ can be decomposed into ρ = µλµλ -1 µλµ, and since det µ = -1, we deduce that λ and µ generate GL Z 2 . However we will not prove that our algorithm returns the best U ∈ Aff(Z 2 ) on all input. Roughly speaking, we will only prove that the bound 3/8 of the ratio of the volumes at the end of our reduction algorithm is the best bound one can expect in general when η = 0. This bound is attained with the example of Figure 10. Specifically, we aim at proving there is no transformation U such that for all finite subset S ⊂ Z 2 , the inequality Vol U (S) ≥ α Vol R(U (S)) holds with α > 3/8: Proof. The degenerate case, that is when Vol S = 0, follows from Proposition 2.2, so that from now on, we can assume that Vol S > 0. By Theorem 3.1, there exists U ∈ Aff(Z 2 ) such that Vol U (S) ≥ 3 8 Vol R(U (S)), whence inf

S⊂Z 2 ,|S|<∞ sup U∈Aff(Z 2 )
Vol U (S) Vol R(U (S)) ≥ 3 8 .

We shall show that sup U∈Aff(Z 2 )

Vol U(S)

Vol R(U(S)) = 3 8 holds for when S = {(1, 0) , (0, 1) , (2, 2)}, which will conclude the proof. For the rest of the proof, S represents the particular set of points {(1, 0) , (0, 1) , (2, 2)}. As Vol U (S) is constant, and equals 3/2 for all U , it suffices to show that, for any U ∈ Aff Z 2 , Vol R(U (S)) ≥ 4. As translating and swapping x and y do not change Vol R(U (S)), we can assume that U ∈ SL Z 2 . Let α β α ′ β ′ be the matricial representation of U , with αβ ′ -βα ′ = 1.

Let ρ be the rotation by the angle π/2. As Vol R(ρ(U (S))) = Vol R(U (S)), one can apply ρ, or ρ -1 , once or twice so that we can further assume that α ≥ 1 and α ′ ≥ 0 hold.

If α ′ = 0, then αβ ′ = 1 so that α = 1 and β ′ = 1. Since the image of (2, 2) is (2 + 2β, 2), the height of the bounding rectangle of U (S) is 2, and Vol R(U (S)) ≥ 4 as soon as the horizontal length of R(U (S)) is greater or equal to 2. In fact, this length is the maximum of |β -1|, |2β + 1| and |β + 2|. If |β -1| = 0, then β = 1 and 2β + 1 = 3. Otherwise, if |β -1| = 1 then either β = 0 and β + 2 = 2, or β = 2 and β + 2 = 4. In this way we observe that, in all cases, the length is at least 2. We can now restrict to considering α ′ ≥ 1.

If β = 0 then α = 1 and β ′ = 1. The horizontal length of U (S) is 2 and its height is 2α ′ + 1. Therefore we have again that Vol R(U (S)) ≥ 4. Similarly, when β ′ = 0, we have β = -1 and α ′ = 1: the height of U (S) is 2 and its horizontal length is at least α + 1 ≥ 2, which yields the same conclusion. Thus, we can now further restrict to considering the case that none of the coefficients of the matrix of U is zero.

From U (1, 0) -U (0, 1) = (α -β, α ′ -β ′ ), we deduce that • If |α -β| = 1, then we distinguish:

if β = α+1, then the horizontal length of R(U (S)) is at least 3α+2 ≥ 5, -if α = β+1, then the horizontal length of R(U (S)) is at least 3β+2 ≥ 5. • If |α ′ -β ′ | = 1, then we distinguish:

if β ′ = α ′ + 1 then the height of R(U (S)) is at least 3α ′ + 2 ≥ 5, -if α ′ = β ′ + 1 then the height of R(U (S)) is at least 3β ′ + 2 ≥ 5.

  His results have been extended and refined in [Gat83, Kal85, GK85, Kal89]. These techniques perform well only if the lifted factors are very sparse. Finally another class of results focuses on the only computation of

2. 3 .

 3 Reduced sets of points. Applying λ to S modifies the volume of the bounding rectangle. For instance Figure 3 is the image of Figure 2 by λ: the height of R does not change, but the horizontal length becomes d x + d y -b -f . The points (i, j)

Figure 3 .

 3 Figure 3. Image of the octagon of Figure 2 by λ, and its new bounding rectangle.

Figure 4 .

 4 Figure 4. Image of the octagon of Figure 2 by λ -1 , and its new bounding rectangle.

  Proposition 2.2. For any degenerate normalized finite set of points S of cardinality σ, convex size π, and bounding rectangle [0, d x ] × [0, d y ], one can compute an invertible affine map U ∈ Aff(Z 2 ) as in (1.1), together with U (S), with O σ log 2 δ bit-operations, where δ = (d x + 1)(d y + 1), such that: • |α|, |β|, |α ′ |, and |β ′ | are at most max(d x , d y , 1), • |γ| and |γ ′ | are at most d x d y , • U (S) is normalized of dense size π.

  as defined in Section 2.1. Initialize U with the identity. Repeat (1) If d x < d y then S := µ(S) U := µ • U Swap d x and d y . (2) Compute b, d, f , h for S, as defined in Section 2.1.

Proposition 2. 3 .

 3 Algorithm 1 is correct. For any nondegenerate normalized finite subset S of N 2 with bounding rectangle [0, d x ] × [0, d y ], Algorithm 1 performs at most O (max(d x , d y )) steps in the main "Repeat" loop. Proof. After each reduction step in the main loop, either d x and d y are swapped, or d x decreases by at least 1 and d y is left unchanged. Therefore the number of steps is bounded by O (max(d x , d y )). Since S remains normalized all along the process, the algorithm always terminates with S being η-reduced.

Figure 5 .

 5 Figure 5. Input set S = {(0, 0) , (1, 1) , (5, 2)}.

Figure 6 .

 6 Figure 6. S after one, and then two reduction steps.

Lemma 2. 6 .

 6 Let S be a nondegenerate normalized finite subset S of N 2 with bounding rectangle [0, d x ] × [0, d y ], and let U be an affine map as in (1.1) that sends S to a normalized set S with bounding rectangle [0, dx ] × [0, dy ]. Then we have: • |α| ≤ 2 dx d y , |β| ≤ 2d x dx , |α ′ | ≤ 2d y dy , and |β ′ | ≤ 2d x dy , • |γ| ≤ 4d x d y dx and |γ ′ | ≤ 4d x d y dy . Proof. Since S is nondegenerate, then it contains at least three points A = (x A , y A ), B = (x B , y B ), and C = (x C , y C ) that are not aligned. Computing the images of A, B, and C by the linear part L = α β α ′ β ′ of U leads to:

  Proposition 2.7. For any nondegenerate normalized finite subset S of N 2 of cardinality σ, with bounding rectangle [0, d x ]×[0, d y ], and dense size δ = (d x +1)(d y +1), Algorithm 1 takes O (σ max(d x , d y ) log δ) bit-operations.

Figure 7 .

 7 Figure 7. Points of S lying on the bounding octagon O. Since Vol S is the volume of the convex hull spanned by S, it is already clear that Vol(IJKLM N OP ) ≤ Vol S. By considering the subdivision of IJKLM N OP into the triangle IJP and the polygon JKLM N OP , we see that Vol(AJP ) ≤ Vol(IJP ) or Vol(BJP ) ≤ Vol(IJP ), according to the slope of (P J) being positive or not. It follows that Vol(AJKLM N OP ) ≤ Vol S or Vol(BJKLM N OP ) ≤ Vol S. In other words, moving I on its supporting segment [A, B] makes Vol(IJKLM N OP ) either decrease or increase. Doing so with K, M and O, and then with some points among J, L, N and P , so that Vol (IJKLM N OP ) decreases, we are led to distinguish the following cases: • If I, K, M and O all move clockwise, that is I moves to A, K moves to C, M moves to E and O moves to G, then we get the polygon AJCLEN GP whose volume is at least Vol Q 1 .

Figure 9 .

 9 Figure 9. Pentagon P 1 in octagon O and rectangle R.

Remark 3. 5 .Figure 10 .Figure 11 .

 51011 Figure 10. Minimal pentagon P 1 with d x = d y .

  and that θ (b, d, f, h) ≥ 0. It remains to study the case for when b ≥ d and b

Proposition 3. 7 .

 7 If S is an η-reduced subset of N 2 of convex size π and with bounding rectangle R = [0, d x ] × [0, d y ], then the following inequalities hold: 3 -4η 18 (d x + 1)(d y + 1) ≤ π ≤ (d x + 1)(d y + 1). Proof. As R contains S, the convex size π is always at most (d x + 1)(d y + 1). If S is degenerate, then d y = 0 and π = d x + 1, so that the proposition is correct. Let us now assume that S is nondegenerate. We decompose Int S into Int b S ∪Int i S, where Int b S are the points lying upon the boundary of the Newton polygon of S, while Int i S are the other ones strictly inside. Pick's Theorem (see [Cox69, Chapter 13, Proposition 51] or [GS93]) relates Vol S to | Int b S| and | Int i S|, as follows:

  Compute (d x , d y ) for S, as defined in Section 2.1. Initialize U with the identity. Initialize m with ⌊log 2 (d x / (ηd y ))⌋. Repeat (1) If d x < d y then S := µ(S) U := µ • U Swap d x and d y m := ⌊log 2 (d x / (ηd y ))⌋. (2) If m < 0 then return U . (3) Compute b 2 m , d 2 m , f 2 m , h 2 m for S as defined above. (4) If b 2

Theorem 4. 3 .

 3 For any normalized finite subset S of Z 2 , of cardinality σ, convex size π, bounding rectangle [0, d x ] × [0, d y ], and dense size δ = (d x + 1)(d y + 1), one can compute an invertible affine map U ∈ Aff(Z 2 ) as in (1.1), with O σ log 2 δ bit-operations, such that: • |α|, |β|, |α ′ |, and |β ′ | are at most max(2 max(d x , d y ) 2 , 1), • |γ| and |γ ′ | are at most 4 max(d x , d y ) 3 , • U (S) is normalized of dense size at most 9π.

Proposition 4. 4 .

 4 With the convention Vol U(S) Vol R(U(S)) = 1 whenever Vol S = 0, one has inf U (S)) represents the bounding rectangle of U (S).

  Vol R(U (S)) ≥ |α -β| |α ′ -β ′ | .Whenever |α -β| ≥ 2 and |α ′ -β ′ | ≥ 2, we are done. Therefore, it remains to examine the following cases:• If α = β, then αβ ′ -βα ′ = α (β ′ -α ′ ) = 1 implies α = β = 1 and β ′ = α ′ + 1. A direct calculation yields Vol R(U (S)) = 3(3α ′ + 2) ≥ 4. • If α ′ = β ′ , then αβ ′ -βα ′ = α ′ (α -β) = 1 implies α ′ = β ′ =1 and α = β + 1, and then Vol R(U (S)) = 3(3β + 2) ≥ 4, since β ≥ 1 holds in this case.

  is a nonzero integer, we deduce that |β| ≤ 2d x dx . The bounds for α, α ′ and β ′ can be obtained mutatis mutandis.Since points of the image of S by L have abscissae (resp. ordinates) with absolute values at most 4d x d y dx (resp. 4d x d y dy ), the absolute value of γ (resp. γ ′ ) is at most 4d x d y dx (resp. 4d x d y dy ).

  moves to E and O to H. If N moves to F , then we get the polygon BCLEF HP , that has volume at least Vol P 3 . Otherwise, if N moves to G, then we get the polygon BCLEGHP , which has volume at least Vol P 2 . -M moves to E and O to G. If P moves to H, then we get the polygon BCLEN GH, that has volume at least Vol P 2 . Otherwise, if P moves to A, then we get the polygon BCLEN GA, which has volume at least Vol Q 1 . -M moves to F and O to H. If L moves to D then we get the polygon BCDF N HP , that has volume at least Vol Q 2 . Otherwise, if L moves to E, then we get the polygon BCEF N HP , which has volume at least Vol P 3 .

-M moves to F and O to G. Let us assume that P moves to A. Then if L moves to D, then we get the polygon BCDF N GA, which has volume at least Vol P 5 . Otherwise, if L moves to E then we get the polygon BCEF N GA, that has volume at least Vol Q 1 . The symmetries then handle the situation of P moving to H instead of A.

Lemma 3.3. If S is an η-reduced set of points, then

Table 1 .

 1 Table1, we display timings, in seconds obtained using an Intel Xeon X5450 at 3.0 GHz running Linux. The first line contains the time spent in the direct call of the native function factor. The second line concerns the time spent in our Algorithm 1 with η = 0. The last line corresponds to calling factor on the reduced polynomial. Indeed, as an optimization, Algorithm 1 is run on the set of vertices of the convex hull of the support of the input polynomial. For a set of size σ, it is classical that the convex hull can be computed in time softly linear in σ: we refer the reader to [PS85, Chapter 3, Theorem 3.7] for instance. Factorization of P n , in seconds.

	n	8	16	32	64	128
	dense factorization	0.04 0.25 2.3 48	1100
	reduction	0.06 0.14 0.28 0.54	1.1
	convex factorization 0.04 0.06 0.22 1.5	25

Acknowledgments. We would like to thank the anonymous referees for their helpful comments.

This work has been partly supported by the French ANR-09-JCJC-0098-01 MaGiX project, and by the Digiteo 2009-36HD grant of the Région Île-de-France.