Hoang La

Borut Lužar
email: borut.luzar@gmail.com

Kenny Štorgel

Further Extensions of the Grötzsch Theorem

Keywords: Grötzsch Theorem, planar graph, 3-coloring, precoloring extension, one triangle

The Grötzsch Theorem states that every triangle-free planar graph admits a proper 3-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending 3-colorings of subgraphs to the whole graph. In this paper, we consider 3-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most 4 can be extended to a 3-coloring of the graph. Additionally, we show that for every vertex of degree at most 3, a precoloring of its neighborhood with the same color extends to a 3coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.

Introduction

A proper coloring of a graph G is an assignment of colors to its vertices such that adjacent vertices are assigned distinct colors. For an integer k, a graph is k-colorable if it admits a proper coloring with at most k colors; the smallest such k is called the chromatic number of G, denoted by χ(G).

The Four Color Theorem [START_REF] Appel | Every planar map is four colorable. part I: Discharging[END_REF][START_REF] Appel | Every planar map is four colorable. part II: Reducibility[END_REF] states that the chromatic number of any planar graph is at most 4, but determining which graphs achieve the equality is an NP-complete problem [START_REF] Dailey | Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete[END_REF]. Consequently, searching for properties of (planar) graphs that guarantee 3colorability is a very vibrant field (see, e.g., [START_REF] Borodin | Colorings of plane graphs: A survey[END_REF] for a survey). It turns out that triangles play an important role in this decision problem; indeed, a cornerstone theorem of Grötzsch [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] states that every triangle-free planar graph is 3-colorable. Consequently, the focus in the field turned to investigating ways in which triangles can appear in 3-colorable planar graphs. For example, for any plane triangulation, Heawood [START_REF] Heawood | On the four-colour map theorem[END_REF] established a necessary and sufficient condition by showing that it is 3-colorable if and only if all of its vertices have even degrees (see [START_REF] Diks | A New 3-Color Criterion for Planar Graphs[END_REF][START_REF] Ellingham | Colorability of Planar Graphs with Isolated Nontriangular Faces[END_REF][START_REF] Kochol | Three colorability characterized by shrinking of locally connected subgraphs into triangles[END_REF] for generalizations of this statement).

We may also allow triangles in general planar graphs and still retain 3-colorability: Havel [START_REF] Havel | On a Conjecture of B. Grünbaum[END_REF] conjectured that a 3-colorable planar graph may contain arbitrarily many triangles as long as they are sufficiently far apart and Steinberg [START_REF] Steinberg | The State of the Three Color Problem[END_REF] conjectured that every planar graph without cycles of length 4 and 5 is 3-colorable. While Havel's conjecture has been proved by Dvořák, Kráľ, and Thomas [START_REF] Dvořák | Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies[END_REF], Steinberg's conjecture has been refuted by Cohen-Addad et al. [START_REF] Cohen-Addad | Steinberg's Conjecture is false[END_REF]. Currently the best result of a similar flavor is due to Borodin et al. [START_REF] Borodin | Planar graphs without 5-and 7-cycles and without adjacent triangles are 3-colorable[END_REF], stating that every planar graph without cycles of length 5 and 7, and without adjacent triangles is 3-colorable. On the other hand, there are 3-colorable planar graphs that may have close triangles (even incident) and have no short cycles forbidden: as proved in [START_REF] Dross | Note on 3-choosability of planar graphs with maximum degree 4[END_REF], every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is 3-colorable (in fact, 3-choosable).

Another direction of research is focused on planar graphs with small number of triangles. Grünbaum [START_REF] Grünbaum | Grötzsch's theorem on 3-coloring[END_REF] noticed that a planar graph may contain three triangles and still retain 3-colorability. His original proof was incorrect and a corrected version was published by Aksenov [START_REF] Aksenov | On continuation of 3-colouring of planar graphs (in Russian)[END_REF].

Theorem 1.1 ( [START_REF] Aksenov | On continuation of 3-colouring of planar graphs (in Russian)[END_REF]). Every planar graph with at most three triangles is 3-colorable.

Shorter proofs of this result were given by Borodin [START_REF] Borodin | A new proof of Grünbaum's 3 color theorem[END_REF] and Borodin et al. [START_REF] Borodin | Short proofs of coloring theorems on planar graphs[END_REF]. The authors of the latter used the following result on 4-critical graphs due to Kostochka and Yancey [START_REF] Kostochka | Ore's conjecture for k=4 and Grötzsch's Theorem[END_REF].

Theorem 1.2 ( [START_REF] Kostochka | Ore's conjecture for k=4 and Grötzsch's Theorem[END_REF]). If G is a 4-critical graph on n vertices, then

|E(G)| ≥ 5n -2 3 .
Theorem 1.2 is a restricted version of a more general theorem from [START_REF] Kostochka | A Brooks-Type Result for Sparse Critical Graphs[END_REF], which describes k-critical graphs and was used in [START_REF] Borodin | Planar 4-critical graphs with four triangles[END_REF] to characterize all planar 4-critical graphs with exactly four triangles; we present these two results in Section 2.

Along with a short proof of Theorem 1.1, using Theorem 1.2, the authors of [START_REF] Borodin | Short proofs of coloring theorems on planar graphs[END_REF] presented short proofs of several other extensions of the Grötzsch Theorem, which guarantee 3-colorability of graphs being close to triangle-free planar graphs. In particular, they extended a result from [START_REF] Jensen | The color space of a graph[END_REF] stating that a triangle-free planar graph with an additional vertex of degree 3 is also 3-colorable.

Theorem 1.3 ([10, 25]). Let G be a triangle-free planar graph and let H be a graph such that G = H -v for some vertex v of degree 4 of H. Then H is 3-colorable.

They also gave a short proof of a precoloring extension result of Aksenov, Borodin, and Glebov [START_REF] Aksenov | Continuation of a 3-coloring from a 6-face to a plane graph without 3-cycles[END_REF]. Theorem 1.4 ([3,[START_REF] Borodin | Short proofs of coloring theorems on planar graphs[END_REF]). Let G be a triangle-free planar graph. Then each coloring of any two non-adjacent vertices can be extended to a 3-coloring of G.

Note that Theorem 1.4 extends the result of Aksenov [START_REF] Aksenov | Chromatic connected vertices in planar graphs (in Russian)[END_REF] and Jensen and Thomassen [START_REF] Jensen | The color space of a graph[END_REF] that a graph obtained from a triangle-free planar graph by adding one edge is 3-colorable.

From Theorems 1.3 and 1.4 one can derive another precoloring extension result.

Theorem 1.5 ([10]). Let G be a triangle-free planar graph and let f be a face of G of length at most 5. Then each 3-coloring of f can be extended to a 3-coloring of G.

On the other hand, if the face f has length k with k ≥ 6, then not every precoloring of its vertices can be extended to a 3-coloring of G. The cases when k = 6, 7, 8, 9 were completely characterized in [START_REF] Gimbel | Coloring graphs with fixed genus and girth[END_REF], [START_REF] Aksenov | Continuation of a 3-coloring from a 7-face onto a plane graph without 3-cycles[END_REF], [START_REF] Dvořák | 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle[END_REF], and [START_REF] Choi | 3-coloring triangle-free planar graphs with a precolored 9-cycle[END_REF], respectively. Moreover, precoloring faces in planar graph of girth at least 5 have also been studied (see, e.g., [START_REF] Choi | 3-coloring triangle-free planar graphs with a precolored 9-cycle[END_REF] for more details).

In this paper, we introduce new results about 3-colorability of planar graphs with small number of triangles and some precolored vertices. First, we extend Theorem 1.4 to planar graphs with at most one triangle.

Theorem 1.6. Let G be a planar graph with at most one triangle. Then each coloring of any two non-adjacent vertices can be extended to a 3-coloring of G.

The result is tight in terms of the number of precolored vertices and in terms of the number of triangles; for example, the precolorings of graphs depicted in Figure 1 cannot be extended to a 3-coloring of the whole graph. As a corollary of Theorem 1.6, we obtain a theorem similar to Theorem 1.3 for planar graphs with at most one triangle.

Theorem 1.7. Let G be a planar graph with at most one triangle and let H be a graph such that G = H -v for some vertex v of degree at most 3 in H, which is adjacent with at most two vertices of the triangle in G if it exists. Then H is 3-colorable.

Proof. Let N (v) = {v 1 , v 2 , v 3 }. Without loss of generality, we may assume that v 1 and v 2 are not adjacent. Then, by Theorem 1.6, we can color v 1 and v 2 with the same color and so the three vertices in N (v) will be colored with at most two colors, which means there is an available color for coloring v.

Again, the result is tight in terms of the number of precolored vertices and in terms of the number of triangles (see Figure 2 for examples), as well as in terms of the number of neighbors of v on the triangle. Clearly, connecting v with all three vertices of the triangle would result in a subgraph isomorphic to K 4 . Extending precolorings of small faces in planar graphs with one triangle is more restricted. We prove an analogue of Theorem 1.5 for faces of length at most 4.

Theorem 1.8. Let G be a planar graph with at most one triangle and let f be a face of G of length at most 4. Then each 3-coloring of f can be extended to a 3-coloring of G.

On the other hand, a precoloring of a 5-face in a planar graph with one triangle cannot always be extended to a 3-coloring of the whole graph; see example in Figure 3. The result about extending a precoloring of an 8-cycle from [START_REF] Dvořák | 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle[END_REF] (as remarked in [START_REF] Choi | 3-coloring triangle-free planar graphs with a precolored 9-cycle[END_REF]) implies the following. Theorem 1.9 ( [START_REF] Dvořák | 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle[END_REF]). Let G be a triangle-free planar graph and let v be a vertex of degree at most 4 in G. Then there exists a 3-coloring of G where all neighbors of v are colored with the same color.

A similar result to Theorem 1.9 about coloring three neighbors of a vertex of an arbitrary degree can be obtained as a corollary of Theorem 1.3.

Corollary 1.10. Let G be a triangle-free planar graph and let v 1 , v 2 , and v 3 be distinct vertices with a common neighbor v. Then there exists a 3-coloring of G where v 1 , v 2 , and v 3 are colored with the same color.

Proof. By Theorem 1.3, the graph obtained from G by adding a 4-vertex x adjacent to v, v 1 , v 2 , and v 3 is 3-colorable. In its coloring, the vertices v 1 , v 2 , and v 3 are colored with the same color, since they must all be colored differently from v and x, which receive two distinct colors.

We prove a somewhat weaker result for the case of planar graphs with one triangle. Let K 4 be the graph obtained from K 4 by subdividing once the three edges incident with a vertex v (see Figure 4). We call a graph K 4 -free if it does not contain K 4 as a subgraph in such a way that the vertex v of K 4 has degree 3 also in G. It is easy to see that the vertices in the neighborhood of v cannot be colored with a same color. v Figure 4: A planar graph with at most one triangle with a vertex v of degree 3 having an independent neighborhood N (v) for which there is no 3-coloring such that all vertices in N (v) receive the same color.

Theorem 1.11. Let G be a K 4 -free planar graph with at most one triangle. Then, for every vertex of degree at most 3 with an independent neighborhood, a precoloring of its neighbors with the same color can be extended to a 3-coloring of G.

Theorem 1.11 is tight in terms of the degree of a vertex and in terms of the number of triangles (see examples in Figure 5).

Preliminaries

In this section we present the terminology and the auxiliary results that we are using in the proofs of our theorems. Note that we only consider simple graphs, i.e., loopless graphs without parallel edges; thus, whenever we perform identification of vertices in our proofs, we discard eventual parallel edges.

For a graph G, we denote the number of its vertices and edges by n G and m G , respectively. If G is a plane graph, i.e., a planar graph embedded in the plane, we denote the set of its faces by F (G) and their number by f G ; in particular, the number of faces of length k is denoted by f k,G or simply f k if G is evident from the context. The length of a face α is denoted by (α). A vertex of degree k (resp., at least k) is called a k-vertex (resp., a k + -vertex), and similarly, a face of length k is called a k-face.

We denote the graph obtained from a graph G by deleting a vertex v (resp., an edge e) by

G -v (resp., G -e). A graph is k-critical, if χ(G) = k and for any x ∈ V (G) ∪ E(G), χ(G -x) < k. A subgraph of G induced by a set of vertices U is denoted by G[U ].
For a given cycle C in a plane embedding of a graph G, we define int(C) to be the graph induced by the vertices lying strictly in the interior of C. Similarly, ext(C) is the graph induced by the vertices lying strictly in the exterior of C.

A separating cycle is a cycle C such that int(C) = ∅ and ext(C) = ∅.
The following lemma is a crucial tool in the proofs, where we use minimality of counterexamples; see, e.g., [START_REF] Borodin | Short proofs of coloring theorems on planar graphs[END_REF] for its proof.

Lemma 2.1 (Lemma 10, Borodin). Let G be a plane graph and

F = v 1 v 2 v 3 v 4 be a 4-face in G such that v 1 v 3 , v 2 v 4 / ∈ E(G)
. Let G i be obtained from G by identifying v i and v i+2 where i ∈ {1, 2}. If the number of triangles increases in both G 1 and G 2 , then there exists a triangle v i v i+1 z for some z ∈ V (G) and i ∈ {1, 2, 3, 4}. Moreover, G contains vertices x and y not in F such that v i+1 zxv i+3 and v i zyv i+2 are paths in G (indices are modulo 4).

In the case of planar graphs with one triangle, we can use the following simpler statement of Lemma 2.1. Corollary 2.2. Let G be a plane graph with at most one triangle and let α be any 4-face of G. Then, at least one of the following holds:

(a) α is adjacent to a triangle, or (b) for at least one pair of opposite vertices of α, we can identify them without creating any new triangles.

Theorem 1.1 settles 3-colorability of planar graphs with at most three triangles. The smallest example of a planar graph with four triangles that is not 3-colorable is the complete graph K 4 . Plane 4-critical graphs with exactly four triangles have been completely characterized by Borodin et al. [START_REF] Borodin | Planar 4-critical graphs with four triangles[END_REF]. In their proofs, they used the following result of Kostochka and Yancey [START_REF] Kostochka | A Brooks-Type Result for Sparse Critical Graphs[END_REF], which is a stronger version of Theorem 1.2.

Theorem 2.3 ([28]). If G is a 4-critical graph, then m G ≥ 5n G -2 3 .
Moreover, the equality is achieved if and only if G is a 4-Ore graph.

Here, a graph is k-Ore if it is obtained from a set of copies of K k by a sequence of DHGO-compositions, where a DHGO-composition O(G 1 , G 2 ) of graphs G 1 and G 2 is the graph obtained through the sequence of the following steps: delete some edge xy from G 1 , split a vertex z of G 2 into non-isolated vertices z 1 and z 2 , and identify x with z 1 and y with z 2 .

By a Pl 4,4f -graph we denote a planar graph with exactly four triangles and no 4-faces. A correlation between 4-Ore graphs and Pl 4,4f -graphs was given in [START_REF] Borodin | Planar 4-critical graphs with four triangles[END_REF].

Theorem 2.4 ([8]

). Every 4-Ore graph has at least four triangles. Moreover, a 4-Ore graph has exactly four triangles if and only if it is a Pl 4,4f -graph.

3 Proofs of Theorems 1.6, 1.8, and 1.11

We prove Theorem 1.6 in two steps. First, we consider the case when the two precolored vertices receive distinct colors, which is equivalent to the statement of Theorem 3.1. Theorem 3.1. Let G be a planar graph with at most one triangle and let H be a graph such that G = H -e for some edge e of H. Then H is 3-colorable.

Proof. We prove the theorem by contradiction. Suppose that H is a counterexample minimizing the number of vertices plus the number of edges and let G be a plane graph with at most one triangle such that G = H -e for some edge e of H. Note that since G is planar and contains at most one triangle, it is 3-colorable by Theorem 1.1. By Theorem 1.4, we may assume that G contains exactly one triangle T . Moreover, by the minimality, H is 4-critical.

We consider five cases regarding 4-faces in G.

Case 1: G has at most two 4-faces. By the Handshaking Lemma, we have

2m G = α∈F (G) (α) ≥ 3 + 4 • f 4,G + 5 • (f G -(1 + f 4,G )) = 5f G -2 -f 4,G
(in the calculation, we assume that T is a face, otherwise the lower bound on the number of edges would be even higher). Then, 5f G ≤ 2m G + 4 and by applying the Euler's Formula and observing that n H = n G and m H = m G + 1, we infer that

10 = 5n G -5m G + 5f G ≤ 5n G -3m G + 4 = 5n H -3(m H -1) + 4 .
Thus,

m H ≤ 5n H -3 3 , a contradiction to Theorem 1.2.
Case 2: G has a 4-face α = v 1 v 2 v 3 v 4 such that at most one vertex of α is incident with T and at most one vertex of e is incident with α. Let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}. By the assumption and Corollary 2.2, we may assume, without loss of generality, that G 1 contains T as the unique triangle. Note that the graph H 1 obtained from H by identifying v 1 and v 3 contains e and is thus 3-colorable by the minimality. Thus, we can extend the coloring of H 1 to the coloring of H in which v 1 and v 3 receive the same color, a contradiction.

Case 3: G has a 4-face α = v 1 v 2 v 3 v 4 such that at most one vertex of α is incident with T and both vertices of e are incident with α. We may assume, without loss of generality, that e = v 1 v 3 . Let G 2 be the graph obtained from G by identifying v 2 and v 4 . Note that if the number of triangles does not increase in G 2 , then we can continue as in Case 2. Therefore, by Lemma 2.1, there exist vertices x, z ∈ V (G) such that xv 4 , xz, zv 2 ∈ E(G). Consequently, no 4-face of G, other than α, can contain both vertices v 1 and v 3 due to planarity.

Due to Cases 1 and 2, and the fact that α contains both vertices of e, there exists a 4-face α = v 1 v 2 v 3 v 4 such that α contains two vertices of T , say v 1 and v 2 (note that the two vertices incident with T are not opposite in α , otherwise there would be another triangle in G), with z being the third vertex of T . Let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}. Again, if the number of triangles does not increase in G 1 or G 2 , then we can color H with 3-colors.

It follows that there exist vertices x , y ∈ V (G) such that x z , x v 4 , y z , and y v 3 ∈ E(G). Suppose that at least one of

C 1 = z v 2 v 3 y or C 2 = z v 1 v 4 x is a 4-face, say C 1 .
By our observation above, C 1 does not contain both vertices of e. Let G be the graph obtained from G by identifying v 2 and y . Note that the number of triangles in G does not increase. Let H be the graph obtained from G by adding the edge e. By the minimality, we can color H with 3 colors and extend the coloring to a coloring of H, in which y and v 2 receive the same color, a contradiction.

Thus, we may assume that both C 1 and C 2 are separating 4-cycles. Note that if the vertices of α (and thus also the endvertices of e) belong to the vertex set

V 1 = V (ext(C 1 )) ∪ V (C 1 ), then H[V 1 ] contains both T and e. Therefore, we can color H[V 1 ]
by the minimality and extend the coloring of C 1 to a coloring of H[V (int(C 1 )) ∪ V (C 1 )] by Theorem 1.5. We use an analogous argument for C 2 in the case when the vertices of α belong to the graph induced by the vertex set V (int(C 1 )) ∪ V (C 1 ), which implies that the vertices of α belong to the vertex set

V (ext(C 2 )) ∪ V (C 2 ). Thus, H is 3-colorable, a contradiction.
Case 4: G has a 4-face α = v 1 v 2 v 3 v 4 such that exactly two of its vertices, say v 1 and v 2 , are incident with T , and at most one vertex of the edge e is incident with α. Let z be the third vertex of T . Using similar arguments as in the previous cases, we infer that there exist vertices x, y ∈ V (G) such that xz, xv 4 , yz, and yv 3 ∈ E(G).

Suppose that C 1 = zv 2 v 3 y is a 4-face. If e = v 2 y, then consider the graph G obtained from G by identifying v 2 and y. Note that the number of triangles in G does not increase. Let H be the graph obtained from G by adding the edge e. By the minimality, we can color H with 3-colors and extend the coloring to a coloring of H, in which y and v 2 receive the same color, a contradiction. Therefore, e = v 2 y. But then, either C 2 = zv 1 v 4 x is a 4-face, in which case we can apply the same procedure on v 1 and x as we did on v 2 and y, or C 2 is a separating 4-cycle. However, since both V (T ) and V (e) belong to the vertex set

V 1 = V (ext(C 2 )) ∪ V (C 2 )
, we can complete the coloring in a similar manner as in the last paragraph of Case 3, a contradiction. Thus, by symmetry, both C 1 and C 2 are separating 4-cycles. Moreover, each of C 1 and C 2 contains exactly one vertex of e in its interior. Furthermore, T is a 3-face, otherwise we can color H[V (ext(T )) ∪ V (T )] by the minimality, and then extend the coloring to the interior of T by Theorem 1.5. Additionally, due to Case 1, there exists a 4-face α = v 1 v 2 v 3 v 4 in G, distinct from α. If identifying either v 1 and v 3 , or v 2 and v 4 results in a graph with one triangle, namely T , then by the minimality, it is 3-colorable and the coloring can be extended to H. Therefore, by the fact that G has only one triangle and Lemma 2.1, two vertices of α are incident with T , say v 1 = v 1 and v 2 = z (meaning that at least one of v 3 and v 4 is in V (int(C 2 )), see Figure 7) and there are vertices x and y in G such that x v 4 , x v 2 , y v 3 , and y v 2 ∈ E(G). This is not possible due to the planarity of G, a contradiction.

Case 5: G has at least three 4-faces and each of them is incident with two vertices of T and both vertices of e.

Let α = v 1 v 2 v 3 v 4 be such a face and let T = v 1 v 2 z. Without loss of generality, we may assume that e = v 1 v 3 . Let G 2 be the graph obtained from G by identifying v 2 and v 4 . If the number of triangles does not increase in G 2 , then we are done. Thus, by Lemma 2.1, there exists a vertex x ∈ V (G) such that xz, xv 4 ∈ E(G).

v 1 = v 1 v 2 = z v 3 v 4 y x z = v
Note that by the assumptions, C = zv 1 v 4 x is not a 4-face, since it is incident to exactly one vertex of e. Therefore, C is a separating 4-cycle. But then, the vertices of both T and e are contained in the vertex set

V 1 = V (ext(C)) ∪ V (C). Let V 2 = V (int(C)) ∪ V (C).
By the minimality, we can color G[V 1 ] and extend the coloring of C to the coloring of G[V 2 ] by Theorem 1.5, a contradiction.

Since no 4-face can be incident with all three vertices of T , the proof is completed.

In the second step of proving Theorem 1.6, we show that any two non-adjacent vertices in a planar graph with one triangle can be colored with the same color. Theorem 3.2. Let G be a planar graph with at most one triangle. Then each coloring of any two non-adjacent vertices with the same color can be extended to a 3-coloring of G.

Proof. We prove the theorem by contradiction. Suppose that a counterexample G is a plane graph with the minimum number of vertices. By Theorem 1.4, we may also assume that G contains exactly one triangle T . Let u and v be two non-adjacent vertices of G.

Let H be the graph obtained from G by identifying the vertices u and v. Clearly, n G = n H + 1 and m G = m H . By the minimality, H is 4-critical. To reach a contradiction, we only need to prove that H is 3-colorable, which implies that there exists a 3-coloring of G in which u and v receive the same color.

We consider three cases regarding 4-faces in G.

Case 1: G has no 4-faces. By the Handshaking Lemma, we have

2m G = α∈F (G) (α) ≥ 3 + 5 • (f G -1) = 5f G -2 .
Then, 5f G ≤ 2m G + 2 and by applying the Euler's Formula, we infer that

10 = 5n G -5m G + 5f G ≤ 5n G -3m G + 2 = 5n H + 5 -3m H + 2 .
Thus,

m H ≤ 5n H -3 3 , a contradiction to Theorem 1.2.
Case 2: G has exactly one 4-face.

Similarly as in Case 1, we can compute that 5f G ≤ 2m G + 3 and by applying Euler's Formula, we infer that

m H ≤ 5n H -2 3 .
In the case when m H < 5n H -2

3

, we obtain a contradiction to Theorem 1.2, and therefore, H has exactly 5n H -2 3 edges. Let α = v 1 v 2 v 3 v 4 be the 4-face in G and let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}.

Suppose first that the number of triangles does not increase in G 1 or G 2 , say G 1 . In the case {u, v} = {v 1 , v 3 }, we identify v 1 and v 3 in H to obtain the graph H 1 . By the minimality, we can color H 1 with 3 colors and extend the coloring to a coloring of H, and therefore also to G, a contradiction. Hence, we may assume that {u, v} = {v 1 , v 3 }. In this case, H is a planar graph with exactly one triangle. Thus, by Theorem 1.1, there exists a 3-coloring of H, and therefore also of G, a contradiction.

We may thus assume that the number of triangles increases in both G 1 and G 2 . By Lemma 2.1, without loss of generality, we may assume that there exist vertices x, y, z ∈ V (G) such that zv 1 , zv 2 , xz, xv 4 , yz, and yv 3 ∈ E(G), where zv 1 v 2 is T . Since G contains exactly one 4-face, it follows that both C 1 = zv 1 v 4 x and C 2 = zv 2 v 3 y are separating 4-cycles.

Note that if both u and v belong to the subgraph of G induced by the vertex set

V 1 = V (ext(C 1 )) ∪ V (C 1 ), then we can color G[V 1
] by the minimality and use Theorem 1.5 to extend the coloring of C 1 to the coloring of the interior of C 1 . By symmetry, we may thus assume, without loss of generality, that u ∈ V (int(C 1 )) and v ∈ V (int(C 2 )).

Since m H = 5n-2 3 , by Theorems 2.3 and 2.4, we infer that H must have at least 5 triangles. Therefore, since G has exactly one triangle, it follows that by identifying u and v, we create at least four new triangles. We will prove that this cannot happen.

First, observe that no new triangle can contain vertices x or y, since that would imply the existence of another triangle, distinct from T , in G. Next, observe that u is adjacent with at most one of the vertices v 1 and v 4 , and v is adjacent with at most one of the vertices v 2 and v 3 . Thus, at most one new triangle can be formed using the edges v 1 v 2 or v 3 v 4 , and so there must exist at least three triangles in H which contain the vertex z and either u or v, say u, is adjacent to z. Therefore, there exist at least three vertices

w 1 , w 2 , w 3 ∈ V (G) such that w 1 , w 2 , w 3 ∈ V (int(C 2 ))
. Moreover, each of them is adjacent to z and v (see Figure 8). Consider now the 4-cycle C = zw 1 vw 2 . Since G contains exactly one 4-face, it follows that C is a separating 4-cycle. Furthermore, the exterior of C together with the vertices of C contains both u and v, as well as T . Thus, by the minimality, we can color G[V (ext(C)) ∪ V (C)] and extend the 3-coloring of the vertices of C to a 3-coloring of H by Theorem 1.5.

Case 3: G has at least two 4-faces.

Let α = v 1 v 2 v 3 v 4 be a 4-face and let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}. Since G contains exactly one triangle, by Corollary 2.2, either, without loss of generality, v 1 v 2 is an edge of T or we can identify v 1 and v 3 or v 2 and v 4 without creating any new triangles. Suppose first that v 1 v 2 is not an edge of T ; say that G 1 has at most one triangle. Then, in the case {u, v} = {v 1 , v 3 }, we identify v 1 and v 3 in H to obtain the graph H 1 . By the minimality, we can color H 1 with 3 colors and extend the coloring to a coloring of H, and therefore also to G, a contradiction. Hence, we may assume that {u, v} = {v 1 , v 3 }. In this case, H is a planar graph with exactly one triangle. Thus, by Theorem 1.1, there exists a 3-coloring of H, and therefore also of G, a contradiction. Thus, we may assume that T = v 1 v 2 z, with z being distinct from v 3 and v 4 , and that in both G 1 and G 2 the number of triangles is at least 2. Therefore, by Lemma 2.1, there exist vertices x, y ∈ V (G) such that xz, xv 4 , yz, and yv 3 ∈ E(G).

Suppose that C 1 = zv 1 v 4 x is a 4-face. Then, due to planarity of G, in the graph G obtained by identifying v 1 and z, no new triangle is created. Thus, by the minimality, we can color G and infer 3-colorability of G in a similar manner as above, a contradiction.

Therefore, by symmetry, we may assume that both C 1 and C 2 = zv 2 v 3 y are separating 4-cycles. Note that if both u and v belong to the vertex set

V 1 = V (ext(C 1 )) ∪ V (C 1 ) (resp., V 2 = V (ext(C 2 )) ∪ V (C 2 )
), then, by the minimality, we can color the graph H 1 (resp.,

H 2 ) obtained from G[V 1 ] (resp., G[V 2 ]
) by identifying u and v and extend the coloring to a coloring of H by Theorem 1.5, hence also obtaining a 3-colorability of G.

Thus, we may assume, without loss of generality, that u ∈ int(C 1 ) and v ∈ int(C 2 ). Now, consider a 4-face α = v 1 v 2 v 3 v 4 . If α satisfies the property (b) of Corollary 2.2, then we proceed as above to obtain a contradiction. Therefore, α is incident with T and, by planarity of G, the vertices of α are all contained in V (int(T )) ∪ V (T ). But then, both u and v belong to the exterior of T and we can color, by the minimality, the graph obtained from G[V (ext(T ) ∪ V (T ))] by identifying u and v. Finally, we extend the obtained coloring to a coloring of H by Theorem 1.5. Hence, from the coloring of H, we again obtain 3-colorability of G, a contradiction. This completes the proof. Theorems 3.1 and 3.2 combined settle Theorem 1.6. Next, we prove Theorem 1.8.

Proof of Theorem 1.8. Let G be a planar graph with at most one triangle and let f be a precolored face of length at most 4.

Suppose first that f is of length 3. Since there is only one coloring of f (up to a permutation of colors), the result follows from Theorem 1.1.

Thus, we may assume that f = v 1 v 2 v 3 v 4 is a 4-face. Suppose that the precoloring of f uses all three colors. Then, two non-adjacent vertices of f , say v 1 and v 3 , receive distinct colors and the other two vertices are colored with the third. Note that the same coloring of f (up to a permutation of colors) can be obtained by adding an edge between v 1 and v 3 . The obtained graph is 3-colorable by Theorem 3.1.

Therefore, we may assume that the vertices of f are precolored with two colors. We proceed by contradiction. Let G be a plane graph with at most one triangle such that a precoloring of some 4-face f with two colors cannot be extended to a 3-coloring of G. Moreover, let G be the smallest such graph in terms of the vertices. Clearly, G has exactly one triangle T , otherwise the precoloring can be extended by Theorem 1.5.

Let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}. If the number of triangles does not increase in G 1 or G 2 , say G 1 , then there is a 3-coloring of G 1 , guaranteed by Theorem 1.6, which induces a 3-coloring of G such that the vertices of f are colored with two colors.

Thus, by Lemma 2.1, without loss of generality, we may assume that there exist vertices x, y, z ∈ V (G) such that zv 1 , zv 2 , xz, xv 4 , yz, and yv 3 ∈ E(G), where T = zv 1 v 2 . Observe that coloring of f forces also the colors on x, y, and z (see Figure 9). Let

C 1 = zv 1 v 4 x and C 2 = zv 2 v 3 y. Suppose that at least one of C 1 or C 2 , say C 1 , is a separating 4-cycle. Then, by the minimality, the coloring of f extends to a 3-coloring of G[V (ext(C 1 )) ∪ V (C 1 )]. Since the obtained coloring of C 1 extends to a 3-coloring of G[V (int(C 1 )) ∪ V (C 1 )
] by Theorem 1.5, we obtain a 3-coloring of G, a contradiction.

Thus, we may assume that both C 1 and C 2 are 4-faces in G. In a similar manner as above, we infer that T must be a 3-face. But then, the precoloring of the 5-cycle C 3 = v 3 v 4 xzy given in Figure 9 extends to a 3-coloring of G[V (ext(C 3 ) ∪ V (C 3 ))] (which might as well be an empty graph) by Theorem 1.5 and we color the two vertices in the interior of C 3 as in Figure 9, hence obtaining a 3-coloring of G, a contradiction. This completes the proof.

We conclude this section with a proof of Theorem 1.11.

Proof of Theorem 1.11. We prove the theorem by contradiction. Let G be a minimal counterexample to the theorem, i.e., G is a K 4 -free planar graph with at most one triangle and the minimum number of vertices such that there is a vertex u of degree at most 3 with an independent neighborhood, such that precoloring the vertices in N (u) with a same color does not extend to a 3-coloring of G.

First, observe that by Theorem 1.3, G has exactly one triangle T , and by Theorem 1.6, u is a 3-vertex. Let N [u] = {u, u 1 , u 2 , u 3 } and let H be the graph obtained by identifying N [u] into a vertex w. Let α 1 , α 2 , and α 3 be the three faces incident to u in G that contain respectively {u 1 , u 2 }, {u 2 , u 3 }, and {u 1 , u 3 }. Furthermore, let α 1 , α 2 , and 3 be the faces incident to w in H corresponding to α 1 , α 2 , and α 3 .

Clearly, every 3-coloring of H induces a 3-coloring of G with u 1 , u 2 , and u 3 colored with a same color, while u can be colored with either of the remaining two colors. Additionally, since G is a planar graph, H is also a planar graph and by the minimality of G, H is 4-critical. Observe also that n G = n H + 3, m G = m H + 3, and f G = f H . Now, we prove two structural properties of H.

Claim 1. H has no separating triangles.

Proof. Suppose the contrary and let C be a separating triangle in H. First, suppose that C is the triangle of G. Without loss of generality, we may assume that w ∈ V (int(C)). By the minimality, there is a 3-coloring of H[V (int(C)) ∪ V (C)], and by Theorem 1.1, we can extend it to a 3-coloring of H, since H[V (ext(C)) ∪ V (C)] has exactly one triangle, a contradiction. Therefore, we may assume that C = T . In that case, C has been created from a 5-cycle C G after we identified N [u] into w and thus w ∈ V (C). Since C = T , we may assume, without loss of generality, that H[V (int(C)) ∪ V (C)] contains α 1 but not α 2 or α 3 (see Figure 10). By the minimality, there is a 3-coloring φ of H[V (ext(C)) ∪ V (C)]. Now, we show that we can extend φ to the interior of C.

Let H 1 = H[V (int(C)) ∪ V (C)].
We proceed by induction on the number of separating triangles in H 1 . First, recall that all separating triangles in H 1 are incident to w; more precisely, they were obtained from 5-cycles in G containing {u 1 , x, u 2 }.

Suppose that H 1 = H[V (int(C)) ∪ V (C)] has no separating triangle. Then it has at most three triangles: C as its outer face, possibly α 1 , and possibly T . Therefore, H 1 is a planar graph with at most three triangles and thus 3-colorable by Theorem 1.1.

So, we may assume that H 1 has at least one separating triangle; we select a separating triangle C such that all separating triangles in H 1 are contained in

H 1 = H 1 [V (int(C )) ∪ V (C )].
Then, by induction, there is a 3-coloring φ of H 1 . Finally, using the colorings φ and φ , we can complete the coloring of H by coloring H[V (H 1 ) \ V (int(C ))] using Theorem 1.1 and an eventual permutation of colors in φ , a contradiction. Claim 2. If H has a separating 4-cycle, then both its interior and exterior must contain w or a triangle.

Proof. Suppose the contrary and let C be a separating 4-cycle of H such that H[V (int(C))∪ V (C)] is a triangle-free planar graph that does not contain w. By the minimality, there is a 3-coloring φ of H[V (ext(C)) ∪ V (C)]. By Theorem 1.5, we can extend φ to the whole graph H, a contradiction. Now, we are ready to finish the proof by considering three cases regarding 4-faces of G.

Case 1: G has no 4-faces. By the Handshaking Lemma, we have 2m G ≥ 5f G -2 and so 2m H + 6 ≥ 5f H -2. Then, 5f H ≤ 2m H + 8 and by applying the Euler's Formula on G, we infer that

m H ≤ 5n H -2 3 .
Since H is 4-critical, by Theorem 2.3, we have that m H = 5n H -2

3

and that H is a 4-Ore graph. Moreover, since H does not have separating triangles by Claim 1, there are at most four triangles in H (T and the faces α 1 , α 2 , and α 3 ). Thus, by Theorem 1.1, H has exactly four triangles and by Theorem 2.4, H is a Pl 4,4f -graph. Recall that three of the triangles are incident to the same vertex w. The only Pl 4,4f -graph for which this is true is K 4 [START_REF] Borodin | Planar 4-critical graphs with four triangles[END_REF]Theorem 4]. However, to obtain K 4 , all three neighbors of u in G must be of degree 2, meaning that G must be K 4 , a contradiction.

Case 2: G has a 4-face that is incident to u.

As a result, after identifying u and its neighbors, H has at most three triangles by Claim 1. Therefore, H is 3-colorable by Theorem 1.1.

Case 3: G has a 4-face α = v 1 v 2 v 3 v 4 and α is not incident to u. The edges v 1 v 3 and v 2 v 4 are not present in G, otherwise G would have at least two triangles. Moreover, if u is adjacent to two (opposite) vertices of α, say v 1 = u 1 and v 3 = u 3 , then, by Case 2, neither C 1 = uv 1 v 2 v 3 nor C 2 = uv 1 v 4 v 3 is a 4-face.
Moreover, without loss of generality, we may assume that u 2 ∈ V (ext(C 1 )). However, by the minimality, there is a 3-coloring of G[V (ext(C 1 )) ∪ V (C 1 )], and it can easily be extended to the whole G by Theorem 1.8. Therefore, at most one of the vertices of α is adjacent to u.

Let G i be the graph obtained from G by identifying v i and v i+2 , where i ∈ {1, 2}. Suppose that the only triangle in G 1 is T . Then, by the minimality, the graph H 1 obtained by identifying the vertices v 1 and v 3 in H is 3-colorable. Clearly, its coloring can be extended to H and thus also to G, a contradiction.

Therefore, by symmetry, we may assume that in G 1 and G 2 the number of triangles increases. It follows by Lemma 2.1 that there are vertices x, y, and z such that v 1 z, v 2 z, xz, xv 4 , yz, yv 3 ∈ E(G), where T = v 1 v 2 z. If one of C 1 = zv 1 v 4 x and C 2 = zv 2 v 3 y is a 4-face, it has the same properties as α and two of its vertices are incident with T . But that is not possible due to planarity.

Thus, C 1 and C 2 are separating 4-cycles of G. Since, at most one of them can contain u = z (by definition, u is not incident with a triangle), the other one remains a separating 4-cycle of H, which does not contain T nor w, a contradiction to Claim 2. This completes the proof.

Conclusion

One motivation for the research presented in this paper was a conjecture on adynamic coloring of planar graphs with one triangle. An adynamic coloring is a proper vertex coloring of a graph G such that for at least one 2 + -vertex all of its neighbors are colored with a same color. Clearly, to admit such a coloring, G must have at least one 2 + vertex v with an independent neighborhood, i.e., v is not incident to a triangle. This is also a sufficient condition.

In [START_REF] Šurimová | Adynamic coloring of graphs[END_REF], it was proved that every triangle-free planar graph admits an adynamic 3coloring (note that this fact is also a corollary of Theorem 1.3). On the other hand, there are planar graphs with two triangles that need 4 colors (see, e.g., the graph in Figure 5(b)). Regarding planar graphs with one triangle, Šurimová et al. [START_REF] Šurimová | Adynamic coloring of graphs[END_REF] conjectured that they are 3-colorable as soon as they contain a 2 + -vertex with an independent neighborhood. Using the results of this paper, we are able to answer the conjecture in affirmative.

Theorem 4.1. Every planar graph with at most one triangle and a 2 + -vertex with an independent neighborhood is adynamically 3-colorable.

Proof. We again proceed by contradiction. Let G be a minimum counterexample in terms of the number of vertices with some fixed embedding. By Theorem 1.3, G has exactly one triangle T . Suppose first that there is a 2-vertex v in G and let N (v) = {v 1 , v 2 }. The graph G obtained by splitting v into two adjacent vertices both connected to v 1 and v 2 is planar with at most three triangles and thus 3-colorable by Theorem 1.1. Its coloring induces a coloring of G in which v 1 and v 2 receive the same color, a contradiction.

Therefore, δ(G) ≥ 3. Moreover, by the Handshaking Lemma and the Euler's Formula, there are at least nine 3-vertices in G, and so at least six 3-vertices are not incident with T . Hence, by Theorem 1.11, G contains a subgraph D isomorphic to K 4 . Since δ(G) ≥ 3, there is a 5-face α of D that is not a face in G.

The graph induced by the interior of α in G and V (α) is a triangle-free plane graph, which we can 3-color adynamically. This coloring gives us a coloring of the vertices of α and fixes also the color of the vertex of T that is not incident with α. It remains to color (eventual) interiors of the other two 5-faces of D in G and the interior of T . All can be colored by Theorem 1.5. This completes the proof.

Regarding other results in this paper, there are a number of possibilities for further work. For example, similar results for planar graphs with two triangles and three triangles would be interesing. Problem 4.2. Characterize planar graphs with two (resp., three) triangles, in which precoloring of any two non-adjacent vertices extends to a 3-coloring of the graph. Also, one could investigate in more details precoloring extensions from larger independent sets. Additionally, Problem 4.3 could be extended to determining the properties of triples of non-adjacent vertices whose precoloring does not extend to the whole graph; particularly, which colorings of them.

We showed that a precoloring of a 5-face in a planar graph G with one triangle cannot always be extended to a 3-coloring of G. So it is natural to ask for a characterization similar to characterizations for faces of lengths 6 to 9 in triangle-free planar graphs.

Figure 1 :

 1 Figure1: Not every precoloring of three vertices can be extended to a 3-coloring of a planar graph with at most one triangle (example (a)), nor can be every precoloring of two vertices in a planar graph with two triangles (example (b)).

Figure 2 :

 2 Figure2: Not every graph obtained from a planar graph with at most one triangle by adding a 4-vertex is 3-colorable (example (a)), nor is a graph obtained from a planar graph with two triangles by adding a 3-vertex (example (b)). The added vertex is depicted with an empty disk in both cases.

Figure 3 :

 3 Figure 3: Precoloring of the outer 5-face which cannot be extended to a 3-coloring of the graph.

Figure 5 :

 5 Figure 5: Precoloring of the neighborhood of a 4-vertex v in a K 4 -free planar graph G with one triangle cannot always be extended to a 3-coloring of G (example (a)). Similarly, precoloring of the neighborhood of a 2-vertex v in a planar graph G with two triangles cannot always be extended to a 3-coloring of G (example (b)).

Figure 6 :

 6 Figure 6: The configuration in Lemma 2.1 in the case of a graph with one triangle.

2 v 3 v 4 eFigure 7 :

 2347 Figure 7: The 4-faces α and α in the last part of Case 4.

w 2 w 3 Figure 8 :

 38 Figure 8: The vertices in G comprising triangles in H in the last part of Case 2.

Figure 9 :

 9 Figure 9: The coloring of f forces the colors of x, y, and z.

Figure 10 :

 10 Figure 10: A separating 5-cycle in G containing α 1 .

Problem 4 . 3 .

 43 Characterize planar graphs with one triangle, in which precoloring of any three non-adjacent vertices extends to a 3-coloring of the graph.

Problem 4 . 4 .

 44 Characterize planar graphs with one triangle, in which precoloring of a 5-face (resp., k-face for any k ≥ 6) extends to a 3-coloring of the graph.

Acknowledgment. The first author was partially supported by the grant HOSIGRA funded by the French National Research Agency (ANR, Agence Nationale de la Recherche) under the contract number ANR-17-CE40-0022. The second and the third author were partially supported by the Slovenian Research Agency program P1-0383 and the project J1-1692. The third author also acknowledges support by the Young Researchers Grant of the Slovenian Research Agency.


Pascal Giorgi
email: pascal.giorgi@lirmm.fr

Bruno Grenet
email: bruno.grenet@lirmm.fr

Armelle Perret
email: armelle.perret-du-cray@lirmm.fr

Du Cray

Daniel S Roche
email: roche@usna.edu

Random primes without primality testing

Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate the total running time. We propose a new variant of the classic D5 algorithm for "dynamic evaluation", applied to a randomly-chosen (composite) integer. Unlike the D5 principle which has been used in the past to compute over a direct product of fields, our method is simpler as it only requires following a single path a er any modulus splits. e transformation we propose can apply to any algorithm in the algebraic RAM model, even allowing randomization. e resulting transformed algorithm avoids any primality tests and will, with constant positive probability, have the same result as the original computation modulo a randomly-chosen prime. As an application, we demonstrate how to compute the exact number of nonzero terms in an unknown integer polynomial in quasi-linear time. We also show how the same algorithmic transformation technique can be used for computing modulo random irreducible polynomials over a finite field.

Introduction

Consider the following situation which arises commonly in exact computational problems: We have a problem over the integers ℤ to solve, but perhaps due to intermediate expression swell or the need for exact divisions, solving direcly in ℤ or ℚ is infeasible.

ere may be fast algorithms for this problem over a finite field, say modulo a prime , but then some (unknown) conditions on the prime must be met in order for the solution over to coincide with the actual integer solution. Typically, must not be a divisor of some unknown (but bounded) large value. en a classical approach, called the big-prime technique, is to randomly choose a large prime , with sufficient bit-length to overcome any non-divisibility conditions with high probability, solve the problem over , and return the result; see [START_REF] Von | Modern Computer Algebra[END_REF]Chapter 5].

When the computation itself is expensive, we can ignore the cost of prime number generation for practical purposes; the running time to compute will be dwarfed by the computations within that follow. But as the computation becomes more efficient, and particularly for algorithms that have quasi-linear complexity, the cost of prime number generation is more significant, and may be a performance bo leneck in theory and/or in practice.

e most efficient Monte Carlo method to generate a random prime number is to sample random integers of the required size and then test them for primality. To find a -bit prime, using fast arithmetic, each primality test costs ̃ 2 time, and because the density of primes among all -bit numbers is proportional to 1/ , the total cost of prime generation in this way is ̃ 3 . Faster practical techniques by [START_REF] Ueli | Fast generation of prime numbers and secure public-key cryptographic parameters[END_REF][START_REF] Joye | Efficient generation of prime numbers[END_REF] incorporate many clever ideas but do not improve on this cubic complexity bound; see [START_REF] Shoup | A Computational Introduction to Number eory and Algebra[END_REF]Chapter 10].

In summary: the cubic cost of generating a large probable-prime may dominate the total cost of the big-prime method when the needed primes are quite large and the mod-algorithm is quite fast. e aim of this paper is to tackle this issue with a general technique that uses random moduli, not necessarily prime, with various extra checks along the way, to provably get the same result in many cases as would be achieved by explicitly generating a random prime.

An analogous situation occurs for polynomials over finite fields: if the original problem is in a fixed finite field , then in many cases one needs to compute over an extension field for sufficiently large. is then poses the challenge of computing a random irreducible degree-polynomial in [ ], which again takes at least quasi-cubic time using the best current methods. We will show that our same basic algorithm transformation technique for integers applies in this case as well, with similar probability bounds.

Algorithmic transformation technique

Our method builds on the long line of techniques known as dynamic evaluation, or the D 5 principle [START_REF] Della | About a new method for computing in algebraic number fields[END_REF]. is is a very general technique which has since been employed for a wide range of computational problems [START_REF] Duval | Rational Puiseux expansions[END_REF][START_REF] Lazard | A new method for solving algebraic systems of positive dimension[END_REF][START_REF] Duval | Sketches and computation-ii: dynamic evaluation and applications[END_REF][START_REF] Moreno | Polynomial gcd computations over towers of algebraic extensions[END_REF][START_REF] Dahan | On the complexity of the d5 principle[END_REF][START_REF] Noro | Modular dynamic evaluation[END_REF][START_REF] Caviness | Dynamic galois theory[END_REF][START_REF] Van Der Hoeven | Directed evaluation[END_REF][START_REF] Poteaux | Computing puiseux series: a fast divide and conquer algorithm[END_REF]. For our purposes the idea is to start computing modulo a possibly-composite , and "split" the evaluation with an efficient GCD computation whenever we need to test for zero or perform a division.

Like the recent directed evaluation technique proposed by van der Hoeven and Lecerf [START_REF] Van Der Hoeven | Directed evaluation[END_REF], we opt to first take the larger-size branch in any GCD spli ing. But unlike their method (and prior work) which is ultimately focused on recovering the correct result over the original product of fields, here the goal is only to have an answer which is consistent with what it would have been in some randomly-chosen finite field. For that reason, we can ignore the smaller branch of any split, avoiding the reconstruction process altogether.

In terms of running time, the key observation is that GCDs can be computed in quasi-linear bit complexity using the half-GCD algorithm of [START_REF] Moenck | Fast computation of gcds[END_REF][START_REF] Brent | Fast solution of toeplitz systems of equations and computation of padé approximants[END_REF], and therefore this transformation has the same so -oh bit complexity as it would to compute over an actual prime of the desired size. We save because there is no longer a need to actually generate (and test for) the random prime.

Proving the probabilistic correctness of this approach is the main challenge and contribution of our paper. First we need good estimates on the probability that a random integer has a large prime factor. In our technique, having a single prime factor where 2 ≥ is necessary and sufficient. Second, and more challengingly, we need to allow for a general model of computation where the algorithm may sample uniformly from the random field it is computing over, and probabilistic correctness over a randomly-chosen field should carry over to probabilistic correctness of our method with random not-necessarily-prime moduli.

To our knowledge, previous applications of the D 5 principle have considered only computational models which are deterministic and do not allow random sampling of field elements. van der Hoeven and Lecerf [START_REF] Van Der Hoeven | Directed evaluation[END_REF] suggest that this can be overcome by providing the deterministic computation tree with a "pool" of pre-selected random field elements, and the recent paper of Neiger, Salvy, Schost, and Villard [START_REF] Neiger | Faster modular composition[END_REF] mentions this limitation and also skirts around it by providing pre-selected "random" choices as additional algorithm inputs.

But this pre-selection does not really make sense in our se ing, where the initial modulus itself is randomly chosen as well, as we must do in order to avoid "unlucky" choices of the underlying finite field . Which is to say, for any fixed, pre-selected value of and "random" elements modulo , there is no way to argue that the result will be correct with high probability; but it is also impossible to choose uniform-random elements modulo or without knowing the modulus in advance. Instead, we take care to actually allow randomization within the transformed algorithm, and prove that probabilistic correctness modulo most sufficiently large primes does indeed imply probabilistic correctness modulo a large-enough random integer (and equivalently with random extension fields over a fixed finite field).

Our optimization to compute on only one branch in fact adds new wrinkles to the challenge of proving correctness. As a small illustration, consider a very simple algebraic algorithm which simply chooses a random field element and tests whether it is zero. Over 2 there should clearly be a 1 2 probability of each outcome. But if we instead compute with initial modulus = 30 and use our "largest branch" spli ing technique, whenever 2 divides the final modulus, there is only a 1 3 chance of ge ing zero over 2 . e reason this can occur is that the branches, and hence the choice of which modulus to use at the end, may themselves depend on previous random choices. In fact it is not hard to construct pathological algorithmic examples which are usually correct modulo some certain-sized primes , but usually incorrect modulo when is a multiple of . Overcoming such issues in a proven and generic way is a major challenge of the present investigation.

Application to sparsity determination

As an important application of our technique to avoid primality testing in randomized computation, and indeed our original motivation for this work, we develop a new algorithm to compute the sparsity of an unknown black-box polynomial.

is Monte Carlo randomized algorithm uses samples of a modular black box, via which an unknown sparse integer polynomial ∈ ℤ[ 1 , … , ] can be evaluated for any chosen modulus ∈ ℕ and point ( 1 , … , ) ∈ [0, ) , as well as bounds and on the height and max degree, respectively, to determine the number of nonzero terms # in the unknown polynomial, correct with high probability.

e bit complexity (accounting for black box evaluations) is so ly-linear in the size ; see eorem 5.2 for a precise statement.

is problem is closely related to the more general problem of sparse interpolation [START_REF] Ben | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF][START_REF] Kaltofen | Improved sparse multivariate polynomial interpolation algorithms[END_REF][START_REF] Kaltofen | Computing with Polynomials Given By Black Boxes for eir Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators[END_REF][START_REF] Garg | Interpolation of polynomials given by straightline programs[END_REF][START_REF] Mohammad | Parallel sparse polynomial interpolation over finite fields[END_REF][START_REF] Kaltofen | Fi een years a er DSC and WLSS2: What parallel computations I do today[END_REF][START_REF] Arnold | Faster sparse multivariate polynomial interpolation of straight-line programs[END_REF][START_REF] Van Der Hoeven | Sparse polynomial interpolation in practice[END_REF][START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF][START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF], where all coefficients and exponents of are to be recovered. O entimes such algorithms assume they are given an upper bound ≥ # and have running time proportional to this , so having a fast way to determine # exactly can be valuable in practice.

Our method mostly follows the early termination strategy by Kaltofen and Lee [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF], which was the first efficient sparse interpolation algorithm not to require an a priori upper bound ≥ # . We save on the running time by explicitly stopping the algorithm early as soon as # is learned, and avoiding costly later steps which require special field structure.

Moreover, while the algorithm of [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF] works over a more general domain, its bit complexity over ℤ is exponentially large; thus, a "big prime" technique is commonly employed; see [START_REF] Kaltofen | Modular rational sparse multivariate polynomial interpolation[END_REF][START_REF] Kaltofen | Fi een years a er DSC and WLSS2: What parallel computations I do today[END_REF][START_REF] Mohammad | Parallel sparse polynomial interpolation over finite fields[END_REF]. But now that we have reduced the arithmetic complexity to quasi-linear, the cubic bit-cost of large prime generation becomes significant. is is where our new algorithm transformation technique comes into play: we use our new methods to obtain the same results as if working modulo a random prime, while actually computing modulo a random composite number with at most twice the bit length.

Summary of contributions

e main results of this paper are:

• A new variant of the D 5 principle which focuses on computing modulo random primes rather than in a given product of fields (Section 4.1);

• A careful analysis which shows that any algorithm which is probably correct for most random, sufficiently-large primes, can be solved without the cost of prime number generation using our new technique (Section 4.3);

• A new algorithm with nearly-optimal bit complexity to determine the number of nonzero terms of an unknown sparse integer polynomial (Section 5); and

• An adaptation of the same techniques to computing modulo random irreducible polynomials over finite fields without irreducibility testing (Section 6).

Prime density and counting bounds

In this section we review some mostly-known results on the number of primes in intervals with certain properties, that will be needed for the probabilistic analysis of our main results. roughout, we use the notation [ , ) to denote the set of integers satisfying ≤ < , and we use the term -bit integer to mean an integer in the range [2 -1 , 2 ). Note that there are 2 -1 integers with bit-length . Definition 2.1. For any positive integers and , we say is -fat if has a prime divisor ≥ 2 .

is follows the definition of -fat in the classic paper of Karp and Rabin [START_REF] Karp | Efficient randomized pa ern-matching algorithms[END_REF], except that we focus only on power-of-two bounds.

We first prove that at least half of all 2 -bit integers have a prime factor with at least bits, largely following [25, Lemma 8], which in turn is based on bounds from Rosser and Schoenfeld [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF].

Lemma 2.2. For any ≥ 1, the number of (2 )-bit integers which are -fat is at least

2 2 -2 .
Proof.

e claim is verified numerically for 1 ≤ ≤ 6. If ≥ 7, then Lemma 8 of [START_REF] Karp | Efficient randomized pa ern-matching algorithms[END_REF] tells us that the number of -fat integers in the range

[1, 2 2 ] is at least 2 2 -1 .
We need to show that at least half of the -fat integers are in top half of this range. For any prime with ≥ 2 , consider the multiples of in the range [1, 2 2 ]. By definition, all such multiples are -fat. Let ∈ ℕ so that is the largest multiple of less than 2 2 -1 .

us exactly multiples of have bit-length strictly less than 2 . And because 2 < 2 2 , there are at least multiples of with exactly 2 bits.

Incorporating the fact that 2 2 is never a multiple of , we see that at least half of the multiples of in the range [1, 2 2 ] have bit-length exactly 2 .

Because any number less than 2 2 can only be divisible by at most one prime ≥ 2 , the sets of multiples for 2 ≤ < 2 2 in fact form a partition of the -fat numbers with at most 2 bits. erefore, summing over all sets in this partition, we see that the total number of -fat integers with 2 bits is at least 2 2 -2 .

Many algorithms which perform computations modulo a random prime in fact need to avoid a certain number of unlucky or "bad" primes. Here we give an upper bound on the chance that a -fat number is divisible by a large bad prime. e proof is trivially just dividing the range by .

Lemma 2.3. For any ≥ 1 and prime ≥ 2 , at most 2 -1 integers with bit-length 2 are multiples of .

Computational model

Our main result is a transformation which, roughly speaking, takes any algorithm in the algebraic RAM model for any chosen prime , and converts it into a randomized algorithm in the (non-algebraic) RAM model that produces the same output most of the time while avoiding prime number generation.

Here we must take care to define the requirements on the initial algebraic algorithm. Prior work such as [START_REF] Della | About a new method for computing in algebraic number fields[END_REF][START_REF] Dahan | On the complexity of the d5 principle[END_REF][START_REF] Van Der Hoeven | Directed evaluation[END_REF] considered more general se ings beyond computing in random finite fields, but in fairly restricted models of deterministic algebraic computation such as straight-line programs or computational trees. Here we have a more restricted algebraic se ing but a more general computational one, allowing for loops, memory, and pseudorandom integer or field element generation.

Modular PRNGs

We define a modular pseudo-random number generator, or modular PRNG, as a pair of deterministic algorithms:

• R M ( , ) → takes a fixed-length state and any positive integer and produces a pseudorandom value uniformly distributed from the range [0, ).

• R U ( ) → ′ takes the current state and produces a value (with the same bit-length) for the next state.

(In practice there would also be an initialization procedure which takes a smaller seed value to produce the initial state, but this detail is unimportant for our discussion.

at is, we treat the seed as synonymous with the initial state .) Conceptually, both of these functions should be indistinguishable from random. More precisely, define ( , , ) as the 'th output modulo from initial state , that is,

R M (R U (⋯ (R U ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ times ( ))), ).
en, even with an oracle to compute ( , ′ , ′ ) for any tuple (i',m') not both equal to ( , ), it should be infeasible to distinguish ( , , ) from a truly random output modulo .

Algebraic RAM with integer I/O

Our model of computation is a classical random access machine (RAM), with an "integer side" and an "arithmetic side". e integer side is a normal RAM machine with instructions involving integer inputs and outputs, and the arithmetic side involves only the following computations with elements of an arbitrary field:

• Ring arithmetic: +, -, ×

• Multiplicative inverse (which in turn allows exact division)

• Pseudo-random generation of a field element e multiplicative inverse computation may fail, e.g., on division by zero, in which case the algorithm returns the special symbol ⊥.

ere are also two special instructions which take input from one side and output to the other side:

• Conversion of an integer to a field element • Zero-testing of any field element Note that zero-testing and subtraction obviously allow equality comparisons between field elements, but not ordering them.

We restrict the inputs and outputs to be integers (or output of ⊥ on error). is is necessary for our use case where the inputs are actually integers which are then reduced modulo , but in any case is not a restriction due to the integer-to-field-element conversion instruction.

For computations over prime fields, we can formally define an algorithm in our algebraic RAM model as having:

• Parameters: prime and initial Modular PRNG state

• Input: ∈ ℤ • Output: ∈ ℤ ⋃{⊥}
• Program: A series of integer instructions as in a normal RAM model and arithmetic instructions as defined above, along with labels, conditional branches, and memory load/store operations We write  , ( ) for the output of algorithm  with field and initial PRNG state .

Note that some abuses of the RAM model are possible, particularly for algebraic algorithms, by using arbitrarily large integers. Rather than avoid such abuses by, e.g., using a word RAM model, we merely note that our transformations do not affect the integer side operations at all, and thus would in principle work the same under any such model restrictions. Indeed, our work applies over most algebraic computational models we know of, such as straight-line programs, branching programs, multi-tape Turing machines, or the closely-related BSS model.

Algorithm transformation for random prime fields

Recall the general idea of our approach, building on [START_REF] Della | About a new method for computing in algebraic number fields[END_REF][START_REF] Van Der Hoeven | Directed evaluation[END_REF]: Given an algorithm  which works over any prime field, we transform it into a transformed version  that instead samples a possibly-composite modulus which probably contains a large prime factor ≥ √ . Any time a comparison or multiplicative inverse occurs,  first performs a GCD of the operand with the current modulus . If a nontrivial factor of is found, then the (unknown) large prime factor of must divide max( , / ). Update the modulus accordingly and continue.

We first fully present our algorithmic transformation, then examine some thorny issues related to the use of pseudorandom numbers in the algorithms, and finally prove the correctness and performance bounds which are the main results of this paper.

Transformation procedure

We begin with the crucial subroutine Algorithm 1 (N M

), which shows how to update the modulus while carefully ensuring no significant blow-up in bit or arithmetic complexity.

Algorithm 1: N M ( , ) Input: Integer ∈ ℤ and modulus ∈ ℕ Output: New modulus ′ ∈ ℕ 1 ← gcd( , ) if 2 1 > then return 1 else ← ⌊log 2 ⌋ 1 mod 2 ← gcd( , ) return / 2
Lemma 4.1. Given any , ∈ ℤ, the integer ′ ∈ ℕ returned by N M ( , ) has the following properties:

• ′

• is either zero or invertible modulo ′ • If is a prime with 2 > and , then ′ also Proof. Let , ∈ ℤ be arbitrary and 1 , , 2 as in the algorithm.

For the first property, we see that the integer returned is either 1 or / 2 , both of which are always divisors of .

For the second property, consider two cases. First, if 2 1 > and thus ′ = 1 is returned, then 1 , so is zero modulo ′ . Otherwise, let ≥ 2 be any common factor of and (if one exists). By the definition of gcd,

1 . Now let ≥ 1 such that is the largest power of that divides . Because ≥ 2, ≤ log 2 , and therefore ⌊log 2 ⌋

1

. From the gcd algorithm, this means that 2 , and thus does not divide / 2 . Hence and / 2 do not share any common factor, i.e., gcd( , ′ ) = 1 as required.

For the third property, assume has a prime factor with 2 > . If 1 , then 2 1 > and the new modulus ′ = 1 returned in the first case is be divisible by . Otherwise, if does not divide 1 , then does not divide 2 either, and hence / 2 .

Lemma 4.2. For any ∈ ℤ and ∈ ℕ, the worst-case bit complexity of Algorithm N M ( , ) is ̃ (log + log ).

Proof.

e bit complexity is dominated by the two GCD computations and the modular exponentiation to compute . Using the asymptotically fast Half-GCD algorithm [START_REF] Schönhage | Schnelle berechnung von ke enbruchentwicklungen[END_REF][START_REF] Stehlé | A binary recursive gcd algorithm[END_REF], and binary powering for the modular exponentiation, all three steps have bit cost within the stated bound.

We now proceed to incorporate the N M subroutine into the algorithm transformation procedure. Algorithm  will be in the model of an algebraic RAM from Section 3.2. We also require a companion procedure  which takes any input ∈ ℤ for  and deterministically produces a positive integer , which should be a minimal bit-length of primes to ensure that  produces correct results on input with high probability. (In most applications we can imagine,  is a simple function of the input sizes and bit-lengths.)

Algorithm 2 details the construction of the transformed algorithm  based on  and . • All additions, subtractions, and multiplications on the "algebraic side" are replaced by integer arithmetic followed by explicit reduction modulo .

• Any random field element generation instructions are replaced by sampling a number in the range [0, ) using the modular PRNG.

• All zero tests and multiplicative inverses on the "algebraic side" for some value first call N M ( , ), update the modulus accordingly, and then perform either a divisible-by-test or modular inverse computation, respectively.

Observe that the transformed algorithm  no longer works in the algebraic RAM model, but handles explicit integers only. More precisely, each algebraic operation in  is replaced with a constant number of arithmetic or gcd computations on integers with bit-length at most 2 .

Correlated PRNGs

A technical detail of our analysis requires a tight relationship between the random choices made by  and  for the same input and seed value. Even using the same PRNG for both algorithms, there is no reason to think that a random sample in  modulo a prime would have any relationship to a corresponding random sample in  modulo a multiple of .

We achieve this by defining a pair of modular PRNGs -one for  and one for  -both based on the same underlying high-quality PRNG, and having the desired correlation property. e constructions are based on three key insights. First, in defining the transformed algorithm  above, we are careful to sample the initial modulus inside the algorithm, rather than taking it as input. Second, the PRNG for the algebraic algorithm  also samples a random modulus even though this is not directly used in the computations, in order to match random outputs between  and . ird, our correlated PRNG construction doubles the state size so that this modulus is chosen completely independently from the future sampled random values; this allows us later to translate probabilistic correctness modulo in  to probabilistic correctness modulo in .

Before describing the PRNGs in detail, it is important to stress that this is purely a proof technique. While these PRNG constructions are efficient and realizable, their need is motivated only by the probabilistic analysis that follows; in reality, we could just use any normal high-quality PRNG and achieve the same results except for some pathological algorithms would not arise in practice.

For what follows, we assume the existence of a high-quality modular PRNG as defined in Section 3.1.

We begin by describing the PRNG for the transformed algorithm  of Algorithm 2, which we call ′ .

We will use two simultaneous instances of the underlying modular PRNG , and therefore double the state size so that the seed for ′ can be wri en = ( 0 , 1 ). e first instance with initial state 0 is used only to generate the initial modulus on the first step.

A erwards, a random sample modulo some integer ∈ ℕ is generated as follows.

If

, then ′ first generates a random integer modulo using with the second part of the current state 1 , and then reduces the result again modulo before returning it. Because , this is indistinguishable from (though less efficient than) randomly choosing an integer modulo directly.

Otherwise, if is not a divisor of the original modulus , then ′ simply calls directly with the current state 1 and the requested modulus.

e PRNG ′ for the algebraic algorithm  is almost identical to ′ , except that the value of is only used inside the PRNG. Indeed, for a random seed and run of the algorithm modulo some prime , it is unlikely that , and then this construction doesn't change the results at all compared to using with the second part of the state 1 alone.

e need for this strange PRNG construction is the correlation that exists between  and  whenever the seed = ( 0 , 1 ) is the same for both, as captured in the following lemma: Lemma 4.3. Let = ( 0 , 1 ) be a PRNG state for ′ or ′ , be the initial 2 -bit random value chosen using 0 , and , ′ ∈ ℕ such that ′ and ′ . Writing as the pseudorandom result from ′ with current state modulo , and as the result from ′ with the same state and larger modulus ′ , then we have ≡ mod .

Proof. Consider the memory states at some point in the program where they are equivalent between the two runs. We show that, no ma er the next instruction in , the memory states a er that instruction (and the corresponding instruction(s) in  according to Algorithm 2) are the still equivalent.

Any arithmetic-side operations are unchanged in Algorithm 2.

Because reduction modulo is a homomorphism, any algebraic additions, subtractions, or multiplications also maintain equivalence.

Let be the original modulus chosen at the beginning of . From the first point of Lemma 4.1, we know that ′ , and therefore also. e same is true for any intermediate value of in the run.

is means that any conversion operation in , reducing an integer modulo , will be mod-equivalent to the corresponding operation in , reducing modulo the current value of .

Considering zero-test instructions, let (resp. ) be the value of some algebraic value in the run of  (resp. ). If = 0 in , then . en, because divides every modulus value in the run, is not invertible modulo . en according to the second point in Lemma 4.1, is zero mod , and the zero test will have the same result.

By the same reasoning, any multiplicative inverse instruction will also be equivalent between the runs of  and , or in the case the denominator is zero, both runs will result in ⊥.

Finally, by using the correlated PRNGs defined in Section 4.2, we can apply Lemma 4.3 to conclude that any random field element generation instruction also results in equivalent outputs at the same step of both runs.

is covers all possible types of instructions and completes the proof.

If the original algorithm  is deterministic, this equivalence of runs is enough to prove correctness of . Indeed, this has been the assumption in most prior works on the D 5 principle, which also o en employ simpler models of computation such as straight-line programs or deterministic computation trees.

By contrast, we want to allow  to be randomized. First, we affirm that any deterministic property of the output is preserved a er our transformation to  in the following lemma, which follows directly from Lemma 4.6. Lemma 4.7. Suppose ∈ ℤ is an input for , and ⊆ ℤ ⋃{⊥} is a family of outputs, such that for any prime and random seed , the output of  on input is always a member of . en the output of  on input is always a member of as well.

e more difficult case is when  may return incorrect values. ere are two types of causes for an incorrect result: when the prime is one of a small set of "unlucky" values, or when randomly-sampled field elements in the algorithm are unlucky and produce and incorrect result. Although many actual algorithms only have one of these two types of failure, we account for both types in order to have the most general result.

For convenience of exposition, we will capture these failure modes in the following definition: Definition 4.8. Let ∈ ℤ be any input for , ∈ ℕ and ∈ ℝ with 0 ≤ < 1. We say that  is ( , )-correct for input if, for all but at most primes with ≥ 2 ( ) , running  on produces a correct output with probability at least 1 -. e following theorem, which is the main result of our paper, combines the prevalence of -fat integers with the run-equivalence of  to prove probabilistic correctness. eorem 4.9. Let ∈ ℤ , ∈ ℕ, and ∈ ℝ with 0 ≤ < 1 2 , and write = ( ). If  is ( , )-correct for input , then the probability that  produces the correct output for input is at least

1 2 - 2 -2 -2 .
Proof. Let be the initial prime modulus chosen uniformly in the range [2 2 -1 , 2 2 ) by . Two things can make an unlucky choice: if it has no large prime divisor (i.e., if it is not -fat), or if its largest prime divisor is one of the unlucky primes that cause  to fail. Lemma 2.2 tells us that the probability of the former is at most 1 2 . And, disjointly, the probability that does have a large prime factor but it is one of the unlucky choices for  is at most /2 -1 .

erefore, over all choices of the first part of the PRNG initial state 0 , at least 1/2 -/2 -2 of them lead to an with a prime factor ≥ 2 which is not one of the "unlucky" primes for  on this input. For such "lucky" choices of 0 and thereby , because 2 > , from Lemma 4.1 we know that will always divide the updated modulus a er any call to N M , and in particular, will divide the final modulus ′ . We can therefore apply Lemma 4.6 with the same for all possible runs of  with the same 0 .

Finally, considering the remaining part of the PRNG initial state 1 , Corollary 4.5 tells us that in these cases  produces the correct result with probability at least 1 -, conditional on the previously-derived chance that is "lucky".

When combined with an efficient verification algorithm, eorem 4.9 immediately yields a Las Vegas randomized algorithm.

But without an efficient verifier, the result seems to be not very useful: it proves that  is a Monte Carlo randomized algorithm with success probability strictly less than one-half.

Still, we can combine eorem 4.9 with the preceding Lemma 4.7 in the case of algorithms  which have one-sided error, meaning that, for any prime and initial PRNG state , the output from  is never larger (or, equivalently, never smaller) than the correct answer.

Corollary 4.10. Let > 0 such that, for any input , algorithm  is ( , )-correct where 1 --/2 ( )-1 < . If  furthermore has only one-sided error, then the correct output can be determined with high probability a er ( 1 ) runs of .

Proof. Because of one-sided error, you can repeatedly run  and take the maximum (resp. minimum) result if the output of  never larger (resp. smaller) than the correct output.

Computing the sparsity of integer polynomials

Sparse polynomial interpolation is an important and well-studied problem in computer algebra: Given an unknown polynomial ∈ R[ 1 , … , ] through a blackbox or a Straight Line Program (SLP), one wants to recover the non-zero coefficients of and their corresponding exponents. Of course, the main goal is to have an algorithm with a complexity that is quasi-linear in the bit-length of the output, that is ̃ ( (log + log ℎ)), where = # is the number of non-zero terms, the maximal degree and ℎ the height, i.e., largest absolute value of any coefficient.

e fastest algorithm for this task are of two kinds, depending of the model in which the polynomial is given. For Straight Line Programs, following the deterministic polynomial algorithm of Garg and Schost [START_REF] Garg | Interpolation of polynomials given by straightline programs[END_REF], many improvements have been made through randomization to reach a quasi-linear complexity in every parameter of , i.e., , log and log ℎ [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF]. For a polynomial given instead by a black box for its evaluation, following the seminal papers of Ben-Or and Tiwari [START_REF] Ben | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF] and Kaltofen and Yagati [START_REF] Kaltofen | Improved sparse multivariate polynomial interpolation algorithms[END_REF], we have now reached a quasi-linear complexity in the sparsity of , see Arnold's PhD thesis [START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF]. Note that an algorithm with quasi-linear complexity in all the parameters of in this model is still not available.

One of the main ingredients of these algorithms is that they require bounds for every parameter ( , , ℎ) of . A few works considered to replace these bounds with explicit randomized algorithms. As outlined in [START_REF] Kaltofen | Computing with Polynomials Given By Black Boxes for eir Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators[END_REF][START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF], one can calculate such a degree bound in polynomial time but this might dominate the cost of the interpolation. e situation is clearly different for the sparsity parameter as interpolation with early termination exists [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF]. is is only the case with Prony-style interpolation, popularized by Ben-Or and Tiwari [START_REF] Ben | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF] for polynomials given as a blackbox.

In this work we will consider the model of Modular Blackbox (MBB) that allows to control the size of the evaluation of the polynomial. In particular, this is of great interest to efficiently deal with sparse polynomials over the integers as one evaluation might be exponentially large than the polynomial itself.

Kronecker substitution [START_REF] Kronecker | Grundzüge einer arithmetischen theorie der algebraischen grössen[END_REF] is a fairly classical tool to reduce multivariate problems to univariate ones. It is easy to see that this transformation does not change the size of the polynomial and its sparsity. erefore, we will only focus on the univariate case here for simplicity of presentation.

Sparsity over a sufficiently large field

First we develop a Monte Carlo algorithm to compute # over a sufficiently-large finite field . For this, we can use Ben-Or and Tiwari [START_REF] Ben | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF] and the extension of Kaltofen and Lee [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF] that study the probability that some early zeros appear during the course of the Berlekamp-Massey algorithm.

Taking a random ∈ and = ( ) ∈ , it is shown that for = 1, … , all Hankel matrices = [ + ] -1 , =0 are non-singular with a probability greater than 1 -( -1)( +1)

showed in [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF] that the zero discrepancy corresponds exactly to hi ing a singular Hankel matrix . Since the sequence ( 1 , 2 , … ) corresponds to the evaluation of asparse polynomial at a geometric sequence, the minimal generator Λ of the recurrence sequence ( 0 , 1 , 2 , … ) has degree exactly # [START_REF] Ben | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF]. We note that there is nothing special about the constant 16; this just arises from what we need later, and it is convenient to have a very low probability of error.

If were given by a straight-line program instead of a blackbox, the same algorithm may be employed with bit complexity ̃ ( # log ), where is the length of the SLP.

Correctness comes from the previous discussion on the probability that the Hankel matrices are non-singular up to = ; see [21, eorem 9] for a complete proof. For the complexity, we can use the fast iterative order basis algorithm of [START_REF] Giorgi | Online order basis and its impact on block Wiedemann algorithm[END_REF] since the Berlekamp-Massey algorithm is related to Padé approximant involving the series ∑ >0 [START_REF] Louis | On the equivalence between Berlekamp's and Euclid's algorithms[END_REF]. e algorithm iPM-basis from [START_REF] Giorgi | Online order basis and its impact on block Wiedemann algorithm[END_REF] provides a fast iterative variant for Padé approximation that can incorporate the early termination strategy (looking for a zero constant term in the residual, denoted ).

One may remark that the algorithm of Fact 5.1 is a one-sided randomized algorithm; the returned value never exceeds the true sparsity # .

Sparsity over the integers

Now suppose ∈ ℤ[ ] is an integer polynomial given via a modular blackbox, along with bounds , such that deg < and each coefficient of is bounded by in absolute value. We want to use the techniques of Section 4 to adapt the algorithm of Fact 5.1 to find the sparsity of .

e first question is how to incorporate the modular blackbox into the algebraic RAM model of Section 3.2. We will say that the algebraic RAM is endowed with an additional instruction to probe the MBB: given any algebraic value , the MBB instruction returns a new algebraic value for ( ). In the original algorithm , each MBB evaluation will be modulo , and in the transformed algorithm , evaluations will be modulo the current value of .

Observe that this functionality is exactly what is already specified in the definition of a modular black box. Importantly, we do not require the MBB to be given in any particular computational model (such as algebraic RAM), and the instruction transformations described in Algorithm 2 will not apply inside the blackbox itself.

e next question is how large the prime should be to ensure correctness with high probability. Fact 5.1 gives a lower bound for so that the mod-algorithm succeeds, but we also need to ensure that the sparsity of modulo is the same as the actual value of # over the integers. is will be true as long as none of the coefficients of vanish modulo . en we simply observe that, with bounds , on the degree erefore, there are at least 2 /2 monic degree-2 polynomials of [ ] that have an irreducible factor of degree , for > . Summing from = + 1 to 2 , there are at least 1 for ≥ 2, and 2 -1 = 1 2 . e result follows. Note that the bound of that lemma is smaller than in the integer version, since we only proved that at least one fourth of the degree-2 polynomials over are -fat. Actually, the number of monic irreducible polynomials of degree approaches / for large values of or [START_REF] Shoup | A Computational Introduction to Number eory and Algebra[END_REF]. With the same proof, this shows that the fraction of degree-2 polynomials that are -fat approaches ln(2) ≥ 0.693 for large values of or . We now turn to the algorithm transformation. We work in the same algebraic RAM model. We adapt the definition of an algorithm of Section 3. e parameter is replaced by a parameter which is an irreducible degree-polynomial over . is requires to fix a correspondence between integers and polynomials over . is is easily done by using the -adic expansion of integers.

e N M algorithm works similarly mutatis mutandis. As input, the algorithm takes a polynomial over (or equivalently an integer that represents this polynomial) and a modulus Finally, the algorithm transformation itself is easily adapted. e bound ( ) returns the minimal degree of an extension for the algorithm to produce correct results with high probability. e transformed algorithm  computes 2 pseudorandom integers modulo using the modular PRNG, and interprets them as a monic degree-2 polynomial over . Also, conversions from integers to algebraic values are done by interpreting the integer as a polynomial over and reducing it modulo . e rest of the arguments are similar as in the integer case. Using the bound of Lemma 6.2 on the density of -fat polynomials, we obtain a similar theorem as eorem 4.9: If  is ( , )-correct of input and ( ) returns , the transformed algorithm  produces the correct output for input with probability at least 1 4 -+1 -4 .

Again, this error probability means the technique is only useful for one-sided Monte Carlo algorithms, or combined with an efficient verification algorithm.

Algorithm 2 :

 2  produced from  and  Input: Input ∈ ℤ and PRNG initial state Output: ∈ ℤ ⋃{⊥} ← ( ) ← pseudorandom (2 )-bit integer stored in memory Proceed with identical instructions of , except:• All conversions from integers to algebraic values are replaced by explicit reduction modulo .

Fact 5 . 1 .

 51 Given a blackbox for ∈ [ ] with ≥ 164 where > deg , there exists a Monte Carlo algorithm that computes integer such that ≤ # . With probability at least 1 -1 48 , we have = # exactly. e computation requires 2 probes to the modular blackbox and ̃ ( ) arithmetic operations in .

2 2 ( 2

 22 -) where = ∑ =1 1/ denotes the th harmonic number. Since1/2( + 1) < -ln( ) -< 1/2 [38], 2 -≥ ln(2) + 1/2(2 + 1) -1/2 ≥ 1 2

  ∈ [ ], and returns a new modulus ′ ∈ [ ]. e test " 2 1 > " is replaced by a test "2 deg( 1 ) > deg( )", and " proof of Lemma 4.1 is easily adapted. e worstcase bit complexity of the adapted algorithm is ̃ ((deg + deg ) log ).

	replaced by "	deg 1	mod ".	⌊log 2 ⌋ 1	mod " is

e

; see[START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF][START_REF] Grigorescu | A local decision test for sparse polynomials[END_REF][START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF].e so-called early termination strategy for sparse interpolation is then to run the Berlekamp-Massey algorithm on the infinite sequence ( 0 , 1 , 2 , … ) and to stop the algorithm whenever a zero discrepancy occurs. It is

e proof follows directly from the PRNG definitions above and the divisibility conditions given.

Besides this correlation property, we also need to know that using this constructed PRNG in the algebraic algorithm  does not affect the probabilistic correctness. Note that the assumption on the underlying PRNG is an idealistic one, as any PRNG with fixed seed length cannot actually produce uniformly random values in an arbitrary range.

Lemma 4.4. If the underlying PRNG produces uniformly random values for any sequence of moduli, then for any fixed value of 0 , the constructed modular PRNG ′ also produces uniformly random values for any sequence of moduli.

Proof. Let 0 be a fixed first half of the seed. e value of 0 purely determines what is chosen, so let ∈ ℕ be that arbitrary value. Now consider any modulus given to ′ . If does not divide , ′ returns a value from the underlying PRNG , which by assumption is uniformly random.

Otherwise, if , then is first sampled for some random value in [0, ). By assumption takes on any value in this range with probability 1 . en because is a divisor of , reducing mod produces each value in [0, ) with probability 1 .

From this, we can draw a crucial conclusion on the probabilistic correctness of  when only 1 is varied.

Corollary 4.5. For some prime and input , suppose  produces a given output with probability 1when provided an ideal perfectly-random number generator. en if the underlying PRNG is uniformly random and for any fixed value of 0 ,  returns with the same probability 1 -, where the probability is over all choices of 1 only.

Analysis

We now proceed to the main result of our paper: for any algebraic algorithm  that produces correct results with high probability for primes of bit-length at least that given by , Algorithm 2 produces a randomized algorithm  which, with constant probability, produces the same correct results with the same number of steps. at is, we can achieve (probabilistically) the same results as computing modulo random primes, without actually needing to ever conduct a primality test.

To prove this probabilistic near-equivalence, first define a run of an algorithm as the sequence of internal memory states for given inputs and seed value (and in the case of an algebraic algorithm, choice of field).

We first show that any run of the transformed algorithm  is equivalent to a run of the original  with the same input and seed for some choice of . Here and for the remainder of this section, we assume that  and  use the constructed PRNGs ′ and ′ as defined in Section 4.2.

Lemma 4.6. For any input and seed , consider the resulting run of . If ′ is the final stored value of in this run, then for any prime factor of ′ , an identical run of  is produced over with the same input and seed , where all algebraic values from the run of  are reduced modulo . and height of respectively, the number of "bad primes" which cause the sparsity to drop modulo is at most log 2 .

Set = ⌈4 + 4 log 2 + log 2 log 2 ⌉. en any ≥ 2 satisfies the condition of Fact 5.1, so we can say the algorithm is ( log 2 , 1 48 )-correct by Definition 4.8. e following theorem, our main result for this section, follows immediately a er observing that log 2 /2 -2 < 1 4 . eorem 5.2. Given a MBB for ∈ ℤ[ ] and bounds , with deg < and each coefficient of is at most in absolute value, there exists a Monte Carlo randomized algorithm that computes an integer such that ≤ # . With probability at least 0.239, we have = # exactly. e computation requires 2 probes to the MBB and ̃ ( ) arithmetic operations, all with moduli that have bit-length (log + loglog ).

Because the error is again one-sided, Corollary 4.10 applies and can be used to make the success probability arbitrarily high.

If the MBB for is in fact a straight-line program of length , the total bit complexity becomes ̃ ( (log + loglog )). While this is technically sub-linear in the bit-length of itself, we note that this is somewhat "hiding" some computation in the evaluation model itself, since to actually produce a polynomial with degree and height with bounded constants, the length of the SLP would need to be at least Ω(log + log ).

Random irreducible polynomials without irreducibility testing

In this section, we adapt our approach to computing in a field extension of a fixed finite field . is need arises frequently in se ings where the base field is too small, and one needs to find more than distinct elements in it. In that case, the standard approach is to compute a random irreducible polynomial of degree and to work within = [ ]/⟨ ⟩. If the algorithm that is run in is fairly fast, the cost of producing an irreducible polynomial of degree , ̃ 3 log , may become predominant.

We show how to adapt our techniques to compute modulo an arbitrary random polynomial. Many aspects are very similar to the integer case, so we highlight only the main differences. We begin with the polynomial counterpart of the notion of -fat integers given in Section 2. Definition 6.1. For any positive integer and finite field , a polynomial ∈ [ ] is said to be -fat if it has an irreducible factor of degree > . Lemma 6.2. For any , the number of degree-2 monic polynomials over that are -fat is at least 1 Proof. A monic degree-2 polynomial can have at most one monic irreducible factor of degree > . A given monic irreducible polynomial of degree > divides exactly 2monic polynomials of degree 2 . Moreover, the number of irreducible monic polynomials of degree over is at least /2 for any [START_REF] Shoup | A Computational Introduction to Number eory and Algebra[END_REF]Lemma 19.12].