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

Sparse Polynomial Interpolation and Division in So -linear Time

Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. ese methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover a polynomial ( ) with integer coefficients given a way to evaluate ( ) mod for any chosen integers and . is algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is so ly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with so -linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents. * Unless otherwise stated, logarithms are in base 2; We shall also use base-logarithms for some prime , and natural logarithms for prime-related statements.

† In this work, we do not consider the case of unbalanced bit lengths, where the differing sizes of each coefficient and exponent are considered in the complexity.

Introduction

Sparse and supersparse polynomials. Sparse polynomial interpolation is an important and well-studied problem in computer algebra, with numerous connections to related problems in signal processing and coding theory. In our context, the task is to determine the sparse representation of an unknown polynomial ∈ ℤ[ 1 , … , ],

which is the list of nonzero coefficients 1 , … , ∈ ℤ and corresponding exponent tuples 1 , … , ∈ ℕ such that = 1 1 + 2 2 + ⋯ + .

Here we use the convenient notation for each monomial

= ,1 1 ,2 2 ⋯ , .
We assume every ≠ 0 and all the 's are distinct. e number of nonzero terms in , also known as the sparsity, is wri en as = # . e bit size of the sparse representation of is ( log + log ) * with the max degree of , that is the largest exponent , , and its height, that is the maximum magnitude of a coefficient † . Any sparse interpolation algorithm requires some bounds on the unknown (typically on the degree, size of coefficients, and possibly number of nonzero terms), as well as a way to evaluate .

e algorithm constructs a series of evaluation points, performs said evaluations, then performs some computations, possibly iterating these steps before se ling on the final result.

Dense polynomial interpolation algorithms have been known for centuries and can always recover a unique result, even if the evaluation points are not chosen by the algorithm. However, methods such as Lagrange interpolation scale at least linearly with the degree of the unknown polynomial. Sparse polynomial algorithms, by contrast, should scale according to the number of nonzero terms, which in general can be much smaller than the degree.

In fact, the degree could be exponentially larger than the sparse representation. Algorithms whose cost scales with the bit-length of the exponents, i.e., the logarithm of the degree, are called supersparse or lacunary polynomial algorithms.

Sparse interpolation Sparse interpolation has received much a ention since the landmark paper by Ben-Or and Tiwari [START_REF] Ben | A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation[END_REF], which provides a deterministic algorithm of complexity polynomial in , , for multivariate polynomials over ℤ, given a bound on ≥ as input. is algorithm is given in the context of an unknown polynomial that a black box allows to evaluate at any point of ℤ freely chosen by the algorithm. Numerous extensions have been proposed [START_REF] Zippel | Interpolating polynomials from their values[END_REF][START_REF] Kaltofen | Improved Sparse Multivariate Polynomial Interpolation Algorithms[END_REF][START_REF] Huang | Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution[END_REF], in particular in order to: deal with finite fields [START_REF] Yu Grigoriev | Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields[END_REF][START_REF] Ming-Deh | Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications[END_REF][START_REF] Mohammad | Parallel sparse polynomial interpolation over finite fields[END_REF][START_REF] Giesbrecht | Diversification improves interpolation[END_REF][START_REF] Huang | Sparse polynomial interpolation based on diversification[END_REF], avoid the bound on by early termination techniques [START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF] or extend the problem to the case of sparse rational functions [START_REF] Kaltofen | On exact and approximate interpolation of sparse rational functions[END_REF][START_REF] Kaltofen | Supersparse black box rational function interpolation[END_REF][START_REF] Cuyt | Sparse interpolation of multivariate rational functions[END_REF][START_REF] Van Der Hoeven | On sparse interpolation of rational functions and gcds[END_REF]. Some algorithms require the black box model to be slightly relaxed and allow evaluations in extension rings or quotient rings [START_REF] Yu Grigoriev | Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields[END_REF][START_REF] Mansour | Randomized Interpolation and Approximation of Sparse Polynomials[END_REF][START_REF] Alon | epsilon-discrepancy sets and their application for interpolation of sparse polynomials[END_REF][START_REF] Murao | Modular Algorithm for Sparse Multivariate Polynomial Interpolationand its Parallel Implementation[END_REF][START_REF] Kaltofen | Supersparse black box rational function interpolation[END_REF][START_REF] Giesbrecht | Diversification improves interpolation[END_REF][START_REF] Bläser | A new deterministic algorithm for sparse multivariate polynomial interpolation[END_REF][START_REF] Van Der Hoeven | Sparse Polynomial Interpolation in Practice[END_REF].

Garg and Schost [START_REF] Garg | Interpolation of polynomials given by straight-line programs[END_REF] described the first algorithm for a generic ring whose complexity is polynomial in log (supersparse interpolation).

eir algorithm takes as input a straight-line program (SLP) rather than a black box. Hence, there is no restriction on the evaluation domain, but the evaluation cost has to be taken into account. Subsequent works have refined the complexity bounds of this algorithm when the ring of coefficients is a finite field, the ring of integers or rational numbers [START_REF] Arnold | Sparse interpolation over finite fields via low-order roots of unity[END_REF][START_REF] Arnold | Faster sparse multivariate polynomial interpolation of straight-line programs[END_REF][START_REF] Huang | Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs[END_REF][START_REF] Huang | Sparse Polynomial Interpolation Based on Derivative[END_REF].

e best currently known complexity is due to Huang [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF] for the interpolation of an SLP of length on a finite field of large characteristic in ̃ ( log log ) bit operations. is complexity is however not quasi-linear in the output size due to the factor log times log .

More details on algorithms and techniques are given in Arnold's esis [START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF] or in the survey from van der Hoeven and Lecerf [START_REF] Van Der Hoeven | Sparse polynomial interpolation[END_REF].

In unbounded coefficient domains such as ℤ, the bit size of the values involved in the evaluation and computation can grow exponentially. Working with such exponentialsize integers is unrealistic and may even make the problem trivial: the unknown polynomial can be recovered from a single evaluation at a point larger than any coefficient, using the -adic expansion of the result. Hence, modular techniques are needed to get efficient algorithms [START_REF] Kaltofen | Modular rational sparse multivariate polynomial interpolation[END_REF][START_REF] Van Der Hoeven | Sparse Polynomial Interpolation in Practice[END_REF]. is motivated the definition of more general black boxes that enable to perform evaluation modulo a chosen integer . A fair analysis of a sparse interpolation algorithm over ℤ[ ] should therefore consider four things: (1) the number of evaluations, (2) the bit-length of these evaluations, (3) the arithmetic complexity of extra processing to produce the result, and (4) the bitlength of integers involved in the extra processing.

Sparse polynomial exact division Another issue with sparse polynomials is the complexity of the basic arithmetic operations; see the survey of Roche [START_REF] Daniel | What Can (and Can't) we Do with Sparse Polynomials?[END_REF]. Even for standard operations such as multiplication or division, no deterministic quasi-linear time algorithm is known. In spite of some theoretical improvements and practical implementations, deterministic algorithms for these operations remain quadratic in the sparsity [START_REF] Johnson | Sparse polynomial arithmetic[END_REF][START_REF] Monagan | Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors[END_REF][START_REF] Monagan | Parallel sparse polynomial multiplication using heaps[END_REF][START_REF] Monagan | Sparse polynomial division using a heap[END_REF][START_REF] Gastineau | Parallel sparse multivariate polynomial division[END_REF]. e major difficulty comes from the unpredictability of the sparsity of the result.

ite recently, new probabilistic algorithms for sparse polynomial multiplication have been proposed [START_REF] Arnold | Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication[END_REF][START_REF] Nakos | Nearly Optimal Sparse Polynomial Multiplication[END_REF][START_REF] Van Der Hoeven | Probably faster multiplication of sparse polynomials[END_REF]. is led to the first quasilinear algorithm for sparse polynomial multiplication over the integers or finite fields with large characteristic [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF], based on sparse interpolation and sparse polynomial verification [START_REF] Giorgi | Polynomial modular product verification and its implications[END_REF].

For the Euclidean division of sparse polynomials, the case of exact division (when the remainder is known to be zero) was improved by similar techniques [START_REF] Giorgi | On exact division and divisibility testing for sparse polynomials[END_REF]. is led to the first algorithm that is quasi-linear in the sparsity, though not in the total bit size.

Summary of results

We provide the first truly quasi-linear sparse interpolation algorithm, for integer polynomials. eorem 1.2. ere is a Monte Carlo randomized algorithm that, given an MBB for an unknown polynomial ∈ ℤ[ 1 , … , ] and bounds , , and on respectively its max degree, height and sparsity, recovers the sparse representation of with probability at least 2 3 . It requires ( ) probes to the MBB plus ̃ ( ( log + log )) bit operations.

Based on similar techniques, we are also able to provide the first quasi-linear time algorithm for computing the exact quotient of two sparse polynomials.

eorem 1.3.
ere is a Monte Carlo randomized algorithm that, given two sparse polynomials , ∈ ℤ[ 1 , … , ] such that divides and a bound on the sparsity of the quotient / , computes the sparse representation of / with probability at least 2 3 . It requires ̃ (( + # + # )( log + log )) bit operations where = deg( ), and is a bound on the height of the three polynomials , and / .

Our algorithms are randomized of the Monte Carlo type, meaning that they can return incorrect results. By repeatedly running the algorithms and taking the majority result, the probability of error decreases exponentially in the number of iterations.

e exact division algorithm can be performed without an a priori sparsity bound. For that, we rely on the sparse product verification algorithm of Giorgi et al. [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF][START_REF] Giorgi | Polynomial modular product verification and its implications[END_REF]. It becomes an Atlantic City algorithm (both its correctness and running time are probabilistic) since the verification algorithm is randomized of Monte Carlo type.

We present our results for multivariate polynomials but will focus on univariate polynomials in our descriptions and proofs that follow. is is allowed by the fairly classical Kronecker substitution [START_REF] Kronecker | Grundzüge einer arithmetischen eorie der algebraischen Grössen[END_REF][START_REF] Kaltofen | Fi een years a er DSC and WLSS2: What parallel computations I do today[END_REF]. Indeed, there is a one-to-one correspondence between polynomials ∈ ℤ[ 1 , … , ] with deg < , and univariate polynomials in ℤ[ ] of degree < through the transformation ( ) = ( , , 2 , … , -1 ).

Note that Kronecker substitution preserves the bit size of the polynomials. For sparse polynomials, the transformation and its inverse require ̃ ( log ) bit operations.

An MBB for can simulate a univariate MBB for by evaluating at the powers of the given point. is adds a negligible cost in our algorithms since we probe the MBB on points of known low order. e rest of the paper is then devoted to univariate polynomials. By abuse of notation we still use to denote the degree of the univariate polynomial, instead of .

Main ideas

Our new algorithms mostly combine aspects of existing techniques initiated by the work of Garg and Schost [START_REF] Garg | Interpolation of polynomials given by straight-line programs[END_REF] and Ben-Or and Tiwari [START_REF] Ben | A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation[END_REF] plus a few new techniques. We outline the most important of them to give a broad overview of the main interpolation algorithms.

Finding candidate exponents Like in the recent line of work of Gao and Huang [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF][START_REF] Huang | Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs[END_REF][START_REF] Huang | Sparse Polynomial Interpolation Based on Derivative[END_REF][START_REF] Huang | Sparse polynomial interpolation based on diversification[END_REF], our overall approach is to generate candidate terms of the unknown sparse polynomials . is is achieved by interpolating mod -1 for tiny primes , where ∈ ( log ) is so small that even performing ̃ ( ) operations is allowable within the targeted complexity.

is approach originates in the work of Garg and Schost [START_REF] Garg | Interpolation of polynomials given by straight-line programs[END_REF] on SLP. In that and subsequent works, the polynomial reduced modulo -1 is explicitly computed using dense arithmetic. is step alone is too costly to get a quasi-linear complexity.

Our approach is to instead compute mod -1 using sparse interpolation à la Prony. To this end, we have to evaluate on elements of order . If is the generator of an order-subgroup of , then ( ) = ( mod -1)( ). is allows us to recover the polynomial modulo ⟨ -1, ⟩. If is a small field, namely ∈ poly( ), this Prony-based interpolation has quasi-linear cost. Since is rather small, this actually only provides the exponents modulo of , but almost no information on the coefficients.

To recover the values of the coefficients, we need to work in a ring ℤ/ ℤ for some large modulus . A full Prony-based sparse interpolation over that ring would be too expensive. However, the exponents of mod -1 have already been computed and we only need to perform the second part of the algorithm, namely sparse interpolation with known support. Also we cannot afford to compute a large enough prime number . Instead, we work over a prime power modulus, namely = for some . is part can still be done in quasi-linear time, even in this larger ring, since it amounts to solving structured linear system of size (# ).

ere, we can only ensure a good probability that one-half of the terms do not collide in the reduction modulo -1. As proposed by Huang [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF] this can be easily turned into a Monte Carlo algorithm by doing (log ) interpolations with different primes . A second problem is that, from this step, we learn only the exponents modulo and not the full exponents themselves. Here we can rely on the clever idea of embedding the exponents in the coefficients [START_REF] Van Der Hoeven | Sparse Polynomial Interpolation in Practice[END_REF][START_REF] Arnold | Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication[END_REF][START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF].

e approach of Huang [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF] is to use the derivative for that purpose. is is well adapted for SLP since the derivative can be computed by means of automatic differentiation. A more general way that encompasses the MBB, reminiscent of Paillier encryption scheme [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF], has been proposed by Arnold and Roche [START_REF] Arnold | Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication[END_REF]. Given a modulus , they consider both polynomials ( ) and ((1 + ) ) in the ring ℤ/ 2 ℤ. Because of the identity (1 +

) mod 2 = 1 + , the ratio of corresponding coefficients between these two polynomials reveals each exponent modulo 2 , provided that term did not collide with any others. In our case, the modulus is and we actually perform the second part of the Prony-based interpolation algorithm over ℤ/ 2 ℤ to compute both ( ) and

((1 + ) ) modulo ⟨ -1, 2 ⟩.
Finding rings with specified subgroups Our approach crucially relies on the ability of finding prime numbers , and elements and such that and are generators of order-subgroups of respectively and ℤ/ 2 ℤ. In particular, must divide -1. Effective versions of Dirichlet's theorem on primes in arithmetic progressions tell us that, for a prime , we can (usually) find another prime such that | ( -1), where ≤ ( 6 ) is not too much larger than , see [START_REF] Rousselet | Estimations du type Brun-Titchmarsh[END_REF]. is allows us to choose as a prime in the arithmetic progression { + 1 ∶ ≥ 1} and to set = ( -1)/ for a random ∈ . Furthermore, one can easily construct an element of order in ℤ/ 2 ℤ by li ing through Newton iteration. We also demonstrate that is principal, which is a necessary condition to be able to solve our structured linear system which is of transposed Vandermonde type.

Notice that changing the base ring is mandatory to minimize the bit complexity. Namely, the large rings have a modulus with (log + log ) bits, but we only do ̃ ( ) arithmetic operations in such rings. e tiny fields, by contrast, have a modulus of only (log( log )) bits, but require at most ̃ ( log ) operations.

Exact division

To compute the quotient of two sparse polynomials and such that divides , we adapt our interpolation techniques. To allow the evaluation of / by evaluating both and , we slightly change the values of and and ensure that , and their powers are not roots of . e values of and do not grow too much: remains linear in the input plus the output bit size, and polynomial in . Since the height and sparsity of / are unknown, we must discover them during the computation. e idea is to begin with small bounds for both and increase them when needed. For this we rely on sparse polynomial product and modular product verification [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF][START_REF] Giorgi | Polynomial modular product verification and its implications[END_REF]. A delicate aspect is to intertwine both bound increases.

Outline of the paper

We start with a preliminary section that gives few number theoretic results that are needed to prove the correctness of our algorithms.

Section 3 provides our so ly linear interpolation algorithm extending further the main idea described above.

is interpolation algorithm is re-used in Section 4 to provide a similar algorithm for the computation of the exact quotient of two sparse polynomials. Moreover, we will present an unconditional algorithm that does not require any prior knowledge of the quotient, and which has an expected so ly linear running time.

Number-theoretic preliminaries

Our algorithms use number-theoretic results that are for many of them quite standard in the sparse interpolation literature. We recall them in this section, in the specific form required for our proofs. One slightly less common routine consists in computing a primitive root of unity (PRU) of prime order in a ring ℤ/ ℤ where = + 1 is also a prime number. We show how to use Newton iteration for this purpose.

Prime number generation

Our algorithm first computes mod -1 where is the polynomial to be interpolated, and some random prime number. e goal is that not too many exponents of collide modulo to be able to recover the terms of . We use a result of Arnold and Roche [START_REF] Arnold | Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication[END_REF]. Note that similar results are given in other references [START_REF] Arnold | Sparse interpolation over finite fields via low-order roots of unity[END_REF][START_REF] Huang | Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs[END_REF]. Lemma 3.4]). Let be a -sparse degree-univariate polynomial, and be a random prime number in ( , 2 ) where ≥ 5 3 (1-) ( -1) ln for some and . en mod -1 has at least collision-free terms with probability at least 1 -.

Fact 2.1 ([6,
To compute mod -1, one has to evaluate on -PRUs. First, we need a -PRU ∈ for some prime , and then a -PRU ∈ ℤ/ ℤ for some integer . To get , we actually generate the triple ( , , ) in a single algorithm, with the required properties. In particular, we need to find two prime numbers , such that | ( -1), that is is in the arithmetic progression { + 1 ∶ ≥ 1}, and such that = poly( ). To this end, we generate at random and sample random elements < 6 in the arithmetic progression until a prime is found. Such an algorithm can be found in Arnold's Ph.D. thesis [START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF] with a rigorous proof based on effective versions of Dirichlet's theorem [START_REF] Akbary | A variant of the Bombieri-Vinogradov theorem with explicit constants and applications[END_REF][START_REF] Sedunova | A partial Bombieri-Vinogradov theorem with explicit constants[END_REF]. e next fact presents a variant with be er probability bounds and a larger range of validity. We provide the complete proof in a short note [START_REF] Giorgi | Random primes in arithmetic progressions[END_REF].

Fact 2.2. ere exists an explicit Monte Carlo algorithm which, given a bound ≥ 2 58 2 , produces a triple ( , , ) that has the following properties with probability at least 1 -, and returns otherwise:

• is uniformly distributed amongst the primes of ( , 2 );

• ≤ 6 is a prime such that | ( -1);

• is a -primitive root of unity in ;

Its worst-case bit complexity is polylog( ). Further, if ≥ 5 48 ln for some integer > 0, the probability that divides is at most .

While the rigorous proof of this fact implies to have large values for , it is not too difficult to see by running few experiments that such triples exist with good probability even for smaller values. One can find some preliminary experiments in our short note [START_REF] Giorgi | Random primes in arithmetic progressions[END_REF]. In this paper, we rely on Fact 2.2 to provide rigorously proven algorithm, thus implying limitations on its practicability. Nevertheless, Algorithms 2 and 3 can be turned into practical ones just by ignoring the constant 2 58 2 but without any formal proof.

Generators of prime-order subgroups

In the crucial steps of our interpolation algorithm, we need to evaluate in a small sizemultiplicative subgroup within a larger ring of order , where | ( -1) and ≥ 1.

In order to do so, we need a generator of the order-subgroup of the ring ℤ/ ℤ, that is, a th primitive root of unity (PRU) in the ring. One way to obtain such a generator would be to take a random invertible element in the ring and raise it to the power ( )/ = ( -1) -1 / modulo . e result will certainly have multiplicative order which divides , and therefore this power of a random element is a -PRU unless it equals 1.

Unfortunately, that approach is too costly for our purposes, because the modulus and exponent could both have roughly log bits. ere is a solution to this: take a -PRU in the field ℤ/ ℤ, and li it to a -PRU in ℤ/ ℤ using a Newton iteration.

is works because of the following elementary lemma.

Lemma 2.3. Suppose , are primes such that | ( -1) and ≥ 1. Let be any -PRU modulo . en mod is also a -PRU modulo . Moreover, is principal, that is -1 is not a zero divisor for 0 < < .

Proof. Let be any generator of (ℤ/ ℤ) * , which is cyclic since is a prime power. en mod must also be a generator of the smaller group (ℤ/ ℤ) * ; otherwise the set { mod } ≥0 would be too small. Because is a generator and is a -PRU modulo , we can write = ( )/ for some integer ∈ {1, 2, … , -1}. is means that mod = ( )/ mod = ( mod ) ( -1)/ mod , where we use the fact that ( ) = ( -1) -1 and mod = for any integer .

Because mod is a generator modulo , and 1 ≤ ≤ -1, this means that mod is a -PRU modulo .

For the second part, since mod is a -PRU, -1 mod ≠ 0 for 0 < < .

And zero divisors modulo must be multiple of , since is prime.

Roughly speaking, Lemma 2.3 states that there is a 1-1 correspondence between -PRUs modulo and -PRUs modulo . In particular, for any -PRU modulo , there is a unique -PRU modulo such that mod = . We construct the larger -PRU through a standard Newton iteration, solving the equation -1 = 0 modulo higher and higher powers of . Assuming we know = mod already, write 2 = + , where < consists of the next base-digits of . Solving the modular equation 2 mod 2 = 1 gives

= 1 - mod 2 -1 mod ,
where the fraction divided by is exact integer division, and the inverse -1 is modulo . Proof. e loop runs (log ) times. e dominating step is mod 2 at the last phase of the Newton iteration with 2 ≥ . Because < , this gives the stated bit complexity.

Algorithm 1: L PRU Input: Primes , with | ( -1), a -PRU ∈ and an integer ≥ 1 Output: , a -PRU modulo

1 ← 1 ; 1 ← 2 while < do 3 ← mod 2 4 ′ ← (1 -)/ using exact integer division 5 ′′ ← ′ -1 mod 6 2 ← + ′′ 7 ← 2
8 return mod

Univariate Interpolation

In this section, we present a Monte Carlo algorithm to interpolate a sparse polynomial given through an MBB. Our algorithm builds on classical techniques but with the originality to use non-integral domains and not only finite fields. We first recall some of these techniques before describing the algorithm. Given an MBB for , we need to compute the exponents of mod -1. We note that evaluating at powers of a -th primitive root of unity ( -PRU) is equivalent to evaluating mod -1 at the same points. As in the classical Ben-Or-Tiwari algorithm, given the sequence (1), ( ), . . . , ( 2 -1 ), we can compute a degree-≤ annihilator polynomial Λ in ̃ ( ) operations in using fast Berlekamp-Massey algorithm [START_REF] Schönhage | Schnelle Berechnung von Ke enbruchentwicklungen[END_REF][START_REF] Er | On the Equivalence Between Berlekamp's and Euclid's Algorithms[END_REF]. e roots of Λ are the where < belongs to the support of mod -1. In our case, is small and these exponents can be retrieved in ̃ ( ) arithmetic operations using Bluestein's chirp transform [START_REF] Bluestein | A Linear Filtering Approach to the Computation of Discrete Fourier Transform[END_REF] to evaluate Λ at 1, , . . . , -1 . Altogether, this gives the following.

Fact 3.1. Given the evaluations of a -sparse polynomial ∈ [ ] at 1, , . . . , 2 -1 where ∈ is a -PRU, one can compute the exponents of mod -1 in ̃ ( + ) operations in or ̃ (( + ) log ) bit operations.

During the algorithm, we need both to evaluate a sparse polynomial on a geometric progression and to reconstruct a sparse polynomial from these evaluations and its exponents.

If = ∑ -1 =0 ∈ [ ] is a sparse polynomial, then for any ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 ⋯ 1 0 ⋯ -1 2 0 ⋯ 2 -1 ⋮ ⋮ ( -1) 0 ⋯ ( -1) -1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 0 1 1 ⋮ -1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ (1) ( ) ( 2 ) ⋮ ( -1 ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
. is shows that the evaluation is a matrix-vector product and the interpolation the resolution of a linear system, where the matrix is a transposed Vandermonde matrix. ese problems admit algorithms of complexity ̃ ( ) over any finite field through connections to dense polynomial arithmetic in degree [START_REF] Kaltofen | Improved Sparse Multivariate Polynomial Interpolation Algorithms[END_REF][START_REF] Bostan | Tellegen's Principle into Practice[END_REF] Actually, these algorithms work for more general rings. It is trivial for the matrix-vector product that does not require any inversion in the ring. e resolution of the linear system requires the matrix to be invertible, that is must be a unit for ≠ . is condition holds when is a -th principal root of unity, that is when = 1 and -1 is not a zero divisior for 0 < < . e following fact summarizes these known results.

Fact 3.2. Let be a ring, = ∑ -1 =0 be a sparse polynomial over , and a principal -th root of unity. en

• evaluating mod -1 at 1, , . . . , -1 , and

• retrieving the coefficients of mod -1 from its set of exponents and (1), . . . , ( -1 ) can be done in ̃ ( log ) operations in .

We shall use these results over two rings. First, using Fact 3.1 we perform the evaluation on powers of a -PRU in to recover the set of exponents modulo . From these exponents, we rely on Fact 3.2 with a -PRU ∈ ℤ/ ℤ to recover the polynomial modulo -1 over the larger ring ℤ/ ℤ, using this time both evaluation and interpolation. Note that is carefully chosen so that it allows to recover all the integer coefficients of mod ( -1). e correctness follows directly from Lemma 2.3 that shows that a -PRU in ℤ/ ℤ is also principal. While we completely know mod -1, some terms of this polynomial come from collisions: at is, two (or more) distinct monomials and from may collide modulo and create the term ( + ) mod in mod -1. We shall overcome this difficulty by a random choice of that guarantees that with good probability, not too many terms collide. Other terms of mod -1 are collision-free, that is of the form mod . To recover the exponent from these terms, we embed the exponents into its coefficients. e idea, due to Arnold and Roche [START_REF] Arnold | Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication[END_REF], is to compute the sparse representations of both and ((1 + ) ), modulo ⟨ -1, 2 ⟩. Since (1 + ) = 1 + mod 2 , a collision-free term is mapped to mod in mod ⟨ -1, 2 ⟩ and ′ mod in ((1 + ) ) mod ⟨ -1, 2 ⟩ where ′ = (1 + ). is allows us to recover both and = ( ′ / -1)/ as soon as is large enough. More precisely, we need to be a unit and representable in ℤ/ 2 ℤ, and (1 + ) ≤ 2 so that the division by remains over the integers. at is, must be chosen not to divide any coefficient and > max( 12 log 2 , log ). We note that there is no a priori way to distinguish between collision-free terms and colliding terms. For some colliding terms, the recovered value of is clearly wrong since it is not integral or too large, but one cannot avoid recovering unwanted terms in general. is is again taken care of through the choice of , as in [START_REF] Huang | Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic[END_REF][START_REF] Huang | Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution[END_REF], to avoid reconstructing too many erroneous terms. Fact 3.3. Given the sparse representation of ( ) mod ⟨ -1, 2 ⟩ and ((1+ ) ) mod ⟨ -1, 2 ⟩ such that does not divide any coefficient of mod -1 and ≥ max( 1 2 log 2 , log ), one can compute a set of tentative terms of , containing all the collision-free terms modulo -1, in ( ) arithmetic operations.

I

given in Algorithm 2 follows the idea from the three previous facts to reach a so ly-linear time complexity. ) operations on integers of size (log ). If the input is an SLP of length and if is also a bound on the absolute values of the constants of the SLP, the bit complexity of the algorithm is ̃ ( (log + log )).

For any ≥ 1, ( ) repetitions of the algorithm improve the success probability to 1 -1 2 . Correctness.

e algorithm has three sources of failure at each iteration. First, the algorithm may fail to produce a triple ( , , ) satisfying the conditions. By Fact 2.2, this probability is at most . Second, the number of collisions of ( - * ) mod -1 may be too large. Fact 2.1 and our choice of guarantee that with probability at least 1 -, the number of collisions is at most 1 3 where ≤ is the true sparsity of ( - * ).

ird, some coefficients of ( - * ) mod -1 may vanish modulo . Fact 2.2 and our choice of guarantee that this probability is at most . erefore, each iteration fails with probability at most 3 = 1/3 ⌈log ⌉, whence the algorithm fails with probability at most 1 3 . We now prove that, assuming that none of these possible failures happens, * = at the end of the algorithm. Fact 3.1 proves that Line 5 correctly computes the exponents of ( - * ) mod -1. Fact 3.2 proves that Lines 7 and 8 correctly compute the sparse representations of ( - * ) mod ⟨ -1, 2 ⟩ and its shi ed counterpart. erefore, since is large enough, Fact 3.3 ensures that Line 9 computes all the collisionfree terms of ( - * ) plus some erroneous terms. By assumption, the number of collisions of ( - * ) mod -1 is at most 1 3 . Since collisions involve at least two terms, the number of colliding terms in ( - * ) mod -1 is at most 6 . erefore, the tentative terms at Line 9 contain at least 2 3 correct terms and at most 1 6 incorrect terms. In other words, the number of terms in ( - * ) at the end of the iteration is at most -2 3 + 1 6 = 1 2 . A er log iterations, = * . To improve the success probability, we repeat the algorithm 48 / log times and return the majority polynomial. Let be the number of repetitions that produce the correct polynomial. Since each repetition is correct with probability at least 2 3 , [ ] = 32 log . erefore, by Chernoff bound, the probability that the correct polynomial is produced by less than half of the repetitions is Pr[

≤ 24 log ] = Pr[ ≤ (1 -1 4 ) [ ]] ≤ exp(-( 1 4 ) 2 [ ]/2) = 1 2 .
Complexity. Each iteration require 3 probes to the MBB (with the current value of ). Hence the total number of probes is < 6 . e evaluations of * at powers of and require ̃ ( log ) = ̃ ( log log ) operations in or ℤ/ 2 ℤ by Fact 3.2. Apart from the evaluations, Line 5 requires ̃ ( ) = ̃ ( log ) operations in using Fact 3.1 and Lines 7 and 8 require ̃ ( log ) = ̃ ( log log ) operations in ℤ/ 2 ℤ using Fact 3.2.

e bit cost of each arithmetic operation is ̃ (log ) = ̃ (log( log ) + log log )) for those in , and ̃ ( log ) = ̃ (log + log ) for those in ℤ/ 2 ℤ. If the MBB is implemented with an SLP, the overall bit complexity, dominated by the evaluations of the SLP, is ̃ ( (log + log )). Note that computing , , and is cheap, since , are rather small. Our algorithm is randomized of Monte Carlo type since it may return an incorrect answer, in addition to fail. To get a Las Vegas variant, the algorithm should only be allowed to fail. For, we need a verification procedure that itself is a Las Vegas algorithm.

e problem to solve is then: Given an MBB for a polynomial and a sparse polynomial * , determine whether = * . Bläser et al. [START_REF] Bläser | Deterministically Testing Sparse Polynomial Identities of Unbounded Degree[END_REF] provide deterministic algorithms for this task but with polynomial, and not quasi-linear complexity. Another approach relies on the same tools as Ben-Or-Tiwari algorithm. If both and * have sparsity at most and degree at most , and is an element of order at least , then - * vanishes on 1, , . . . , 2 -1 if and only if = * (cf. for instance [START_REF] Arnold | Sparse Polynomial Interpolation and Testing[END_REF]). It is deterministic as long as an element of large order can be computed deterministically.

For a polynomial over ℤ, we must evaluate and * modulo some integer to avoid expression swell. As before, we can produce a triple ( , , ) such that is a -PRU in . Since should have order ≥ , we take a random prime ≥ , and ≥ so that the coefficients do not vanish modulo . is can be done in time polylog( + ). en, evaluating * on 1, , . . . , 2 -1 requires 2 probes to the MBB for , and ( log ) operations in for * . If is represented by an SLP of length , the bit complexity becomes ̃ ( log( + ) + log( ) log( + )). Note that this complexity is quadratic in log .

Altogether, we obtain a Las Vegas algorithm using ( ) probes, ( log ) operations in and polylog( + ) bit operations, with a constant probability of failure. If is represented by an SLP, the bit complexity is ̃ ( log( + ) + log( ) log( + )). Using repetition, we obtain an algorithm that never fails, with the same expected complexity.

It is an intriguing open question whether a quasi-linear Las Vegas algorithm exists. In particular, can we verify an equality = * where is given by an SLP and * is sparse, in quasi-linear time?

Exact division

Given two sparse polynomials and such that divides , the problem of computing / can be seen as a sparse interpolation of a specific SLP that has a single division.

As shown in Giorgi et al. [START_REF] Giorgi | On exact division and divisibility testing for sparse polynomials[END_REF] some sparse interpolation algorithms can be carefully adapted to produce division algorithms if there is no remainder. As the interpolation algorithms they rely on, these division algorithms are not quasi-linear in the input plus the output bit-size. In this section we show how to adapt of our quasi-linear interpolation algorithm to derive fast sparse polynomial exact division. As a result, we obtain the first quasi-linear exact division algorithm for sparse polynomial over the integers. ere are three main difficulties in adapting our interpolation algorithm. First, no bound is given for #( / ) except the potentially exponential degree one. Second, we do not know the height of / while the interpolation algorithm depends on it. Last, to evaluate the quotient / at a root of unity , we compute both ( ) and ( ) and perform the division. Hence, must not be a root of .

To overcome the first difficulty, we use the same method as Giorgi et al. [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF][START_REF] Giorgi | On exact division and divisibility testing for sparse polynomials[END_REF]. We guess a sparsity bound for the quotient, interpolate a candidate quotient assuming the bound, and check its correctness a posteriori with a probabilistic verification. In case of failure we double the sparsity bound and start again.

Besides verifying products of sparse polynomials, we will also need in our algorithm an efficient verification of sparse polynomial product modulo a binomial. Such algorithms have been recently proposed by some of the authors in [START_REF] Giorgi | Polynomial modular product verification and its implications[END_REF], and we recall the useful results below. Fact 4.1 (Giorgi et al. [START_REF] Giorgi | Polynomial modular product verification and its implications[END_REF]).

ere exists a Monte Carlo algorithm that, given threesparse degree-polynomials , , ℎ ∈ ℤ[ ] of height ≤ , and ≥ 1, verify if = ℎ.

e algorithm can give a wrong answer with probability at most 1 2 when ≠ ℎ. Its bit complexity is ̃ (log + log + ) + 4 . ere exists a Monte Carlo algorithm that similarly tests if = ℎ mod -1, with the same error probability and bit complexity ̃ log + log + 4 log 3 .

A similar guess and check method can be used to determine an appropriate bound for the height of the quotient: Start with a small bound and increase it when necessary. Indeed, Line 7 of algorithm I correctly computes the polynomial modulo -1 as soon as 2 is greater than its height. ere, verifying the sparse product modulo -1 allows us to determine if the bound on the height is large enough. is method is necessary as the bound we have for the height is exponential. where = # and , are the respective heights of and .

For the last difficulty, we want ( ) ≠ 0 for any th primitive root of unity in . at is, we want to be coprime with the th cyclotomic polynomial

Φ = ∑ -1 =0 in [ ]. In ℤ[ ],
if is a prime larger than # such that mod -1 ≠ 0, then and Φ are coprime. If is taken at random and large enough, namely = Ω(# log(deg )), Fact 2.1 ensures that mod -1 ≠ 0 with good probability. en, and Φ are coprime in [ ] if and only if does not divide their resultant, an integer bounded by (# ⋅ ) -1 where is the height of . We can therefore choose two primes and so that and Φ are coprime in [ ] with good probability, using Fact 2.2.

We first describe an algorithm to compute an exact quotient with a given bound on its sparsity but no precise bound on its height.

e algorithm can return an erroneous polynomial by adding false terms. However this polynomial cannot be much larger than the correct polynomial. Proof. For the sparsity, Line 6 uses a Vandermonde system to interpolate a sparse polynomial of sparsity at most and cannot compute more than monomials. erefore, as is divided by 2 every time we add new terms to ℎ, the result has at most 2 terms.

For the height, only erroneous terms can have coefficients larger than . However those terms necessarily come from collisions. Hence at each iteration, the sum of the erroneous terms is at most equal to the sum of the terms of /ℎ. Initially, ℎ = 0 and the sum is bounded by . At each iteration, erroneous terms can at most double the sum. A er ⌈log ⌉ iteration, the sum is bounded by ⋅ and so is the height of ℎ. Correctness. e algorithm may fail for five distinct reasons. e first three reasons are the same as in I : It may fail to compute the triple ( , , ) required to compute ℎ ; e prime may cause too many collisions in /ℎ mod ( -1); some terms of /ℎ mod ( -1) may vanish modulo . e two other sources of failure are specific to this algorithm: One of the powers of or may be a root of ; e test at Line 7 may fail to detect an error. e choice of ≥ 4 96 ln implies ≥ 5 48 ln( 2 ). Facts 2.1 and 2.2 ensure that, with probability at least 1 -3 , the algorithm successfully produces a triple ( , , ) such that does not cause too many collisions and does not divide an unknown integer of value at most . If does not cause too many collisions, mod -1 ≠ 0. Since # < , and Φ = ∑ ) . Moreover, since bounds the height of both ℎ and / using Fact 4.2, and since > , the height of ( /ℎ) mod -1 is at most . Hence with probability at least 1 -, does not divide the resultant of and Φ nor any coefficient of ( /ℎ) mod -1. In particular, and Φ remain coprime in and so in ℤ/ 2 ℤ since -PRU in ℤ/ 2 are also -PRU in .

Altogether, the four following properties hold with probability at least 1 -4 : e algorithm succeeds in producing two primes , and ∈ ; and Φ are coprime in [ ] and in ℤ/ 2 ℤ; ere are few collisions in /ℎ modulo -1; does not divide any of the coefficients of ( /ℎ) mod -1. If all these conditions hold, we can use Facts 3.1 and 3.2 to compute ℎ . e choice of implies that 2 is larger than twice the height of /ℎ as soon as 0 is larger than the (unknown) height of / . In that case, the equality ℎ = /ℎ holds in ℤ[ ] and the test at Line 7 returns . Computing tentative terms and updating ℎ can then be done exactly as in I . If 0 < , there are two possibilities. Either ℎ ≠ /ℎ mod -1 in ℤ[ ]. With probability at least 1 -, the test detects that and 0 is squared. Or the equality indeed holds. is means that the terms of /ℎ that have a larger height collide modulo -1. Hence, the collision-free terms are correctly computed.

Consequently, the loop works correctly with probability 1 -5 : Either the number of terms that remain to be computed is halved, or the height bound is squared if it was too small. At most ⌈log log ⌉ ≤ ⌈log log ⌉ iterations where the test returns are needed to get to a correct bound 0 ≥ , and at most ⌈log ⌉ iterations where the test returns are needed to to compute all the coefficients. erefore the algorithm performs at most (⌈log ⌉+⌈log log ⌉) iterations. Its success probability is at least 1 -5 (⌈log ⌉ + ⌈log log ⌉) ≥ 2 3 . To improve the success probability, we repeat the algorithm 48 / log times and return the majority polynomial, as in I .

Complexity. Since the number of iterations is logarithmic in the input and output size, the complexity of the algorithm is given by the complexity of one iteration. As in I , the algorithm requires ̃ ( + ) operations in and ̃ ( log ) operations ℤ/ 2 ℤ for the evaluations of ℎ, computing the exponents modulo and then retrieving the coefficients and the entire exponents.

e evaluations of / require ̃ (( + # + # ) log ) operations in both domains by Fact 3.2 plus (# + # ) operations in ℤ to reduce the initial coefficients and degree. As the height of an erroneous answer is at most 2 by Lemma 4.3, the maximal value of 2 is 2 + . erefore arithmetic operations in ℤ/ 2 ℤ have bit cost ̃ (log + log ). Moreover the choice of ensures that = ̃ (( + # )(log + log )). As is polynomial in this leads to a total bit complexity of ̃ (( + # + # )(log + log )).

Our main division algorithm uses B

with growing sparsity bound until a result is found. Proof.

e probability 1 -1 2 concerns both the correctness and the complexity of the algorithm. We prove that each of them holds independently with probability ≥ 1-1 2 +1 . e algorithm is incorrect when ≠ ℎ. is happens if at some iteration, the candidate quotient is incorrect but the verification algorithm fails to detect it. Since each verification fails with probability at most 1 2 +1 and values of range over powers of two, the algorithm is correct with probability at least 1 -1 2 +1 . For the complexity we first need to bound the number of iterations. Since the values of are powers of two, the first value ≥ #( / ) is at most 2#( / ). As soon as reaches this value, the return value is actually / with probability at least 1 -1 2 +1 according to eorem 4.4 when the number of candidates is ≥ 48( +1)/ log . In that case, the test which is only one-sided error, succeeds and the algorithm returns ℎ = / . at is, with probability at least 1 -1 2 +1 , the number of iterations is (log #( / )). Even with false sparsity, Lemma 4.3 ensures that the size of the candidate quotients is at most quasi-linear in the size of the actual quotient.

erefore we can apply eorem 4.4 to obtain the claimed complexity with probability at least 1 -1 2 +1 .

Definition 1 . 1 .

 11 A modular black box (MBB, for short) for a multivariate polynomial ∈ ℤ[ 1 , … , ] is a function that takes any modulus ∈ ℕ and -tuple of evaluation points ( 1 , … , ) ∈ {0, 1, … , -1} , and produces the evaluation( 1 , … , ) mod . 1 , … , ( 1 , … , ) modAn alternative input for sparse interpolation is straight-line programs (SLP). An SLP naturally implements an MBB: Given the SLP for ∈ ℤ[ 1 , … , ], one can compute ( 1 , … , ) mod . If the SLP has length , this amounts to ( ) operations in ℤ/ ℤ, or ̃ ( (log + log )) bit operations, where bounds the absolute values of the constants used by the SLP. (More precisely, if the SLP uses constants ≤ in absolute value, and > , we need to reduce these integers modulo , in time ̃ ( log ).)

eorem 2 . 4 .

 24 Provided is a -PRU modulo , Algorithm 1 returns a -PRU modulo . It has bit complexity ̃ log 2 .

Algorithm 2 : 2 ← 2 5 1 6 4 7 2 8 9 3 10

 22214293 I Input : a polynomial ∈ ℤ[ ] represented by an MBB; bounds , and on respectively the degree, the sparsity and the height of Output : the sparse representation of ∈ ℤ[ ] with probability ≥ 2 3 ; otherwise any -sparse polynomial or 1 * ← 0 ; ← 1/(9 ⌈log ⌉) max 2 58 2 , 5 ( -1) ln , 5 48 ln /* Heuristically 2 58 2 can be replaced by 1, see discussion after Fact 2.2. */ 3 while ≥ 1 do 4Compute a triple ( , , ) such that ∈ is a -PRU where and are prime numbers and < < 2 using Fact 2.Evaluate ( - * ) at 1, , . . . , 2 -1 and compute the exponents of ( - * ) mod ⟨ -1, ⟩ using Fact 3.Compute a -PRU ∈ ℤ/ 2 ℤ where = ⌈max( 1 2 log 2 , log )⌉ using eorem 2.Evaluate ( - * ) at 1, , . . . , -1 and compute the sparse representation of ( - * ) mod ⟨ -1, 2 ⟩ using Fact 3.Perform the same step with shi ed evaluation points to compute the sparse representation of ( - * )((1 + ) ) mod ⟨ -1, 2 ⟩Compute tentative terms of ( - * ) using Fact 3.Add the tentative terms to * ; ← ⌊ /2⌋ 11 return * eorem 3.4. Algorithm I works as specified. It requires ( ) probes to the MBB, ̃ ( log ) operations on integers of size (log( log )), and ̃ ( log log

Fact 4 . 2 (

 42 Giorgi et al. [19]). Let , , ∈ ℤ[ ] be three sparse polynomials such that = . en the height of satisfies ≤ ( + 1) ⌈ -1 2 ⌉

Lemma 4 . 3 .

 43 Algorithm B always returns a polynomial with at most 2 terms and height at most ⋅ where and are the actual sparsity and height of the quotient we intend to compute.

  eorem

- 1 =0

 1 are coprime in ℤ[]. e resultant of and Φ is at most (#

Algorithm 4 : 2 4 1 2 +1 6 If the test returns , return ℎ eorem 4 . 5 .

 421645 E Input : , ∈ ℤ[ ], such that divides , ≥ 1 Output : / with probability at least 1 Compute ( ) candidates ℎ for / using Algorithm 3 with sparsity bound and keep the most frequent one 5Test if = ℎ using the algorithm from Fact 4.1, se ing its failure probability to Let , be sparse polynomials in ℤ[ ] such that divides , be a bound on the height of , and / , and ≥ 1. With probability at least 1 -1 2 , Algorithm E returns / in ̃ (#( / ) + # + # )(log + log + ) + 4 bit operations.

Acknowledgements

We are grateful to the reviewers for their insightful comments.


Hoang La

Mickael Montassier
email: mickael.montassier@lirmm.fr

2-distance (∆ + 2)-coloring of sparse graphs

A 2-distance k-coloring of a graph is a proper k-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance (∆ + 2)-coloring for graphs with maximum average degree less than 8 3 (resp. 14 5 ) and maximum degree ∆ ≥ 6 (resp. ∆ ≥ 10). As a corollary, every planar graph with girth at least 8 (resp. 7) and maximum degree ∆ ≥ 6 (resp. ∆ ≥ 10) admits a 2-distance (∆ + 2)-coloring.

Introduction

A k-coloring of the vertices of a graph G = (V, E) is a map φ : V → {1, 2, . . . , k}. A k-coloring φ is a proper coloring, if and only if, for all edge xy ∈ E, φ(x) = φ(y). In other words, no two adjacent vertices share the same color. The chromatic number of G, denoted by χ(G), is the smallest integer k such that G has a proper k-coloring. A generalization of k-coloring is k-list-coloring. A graph G is L-list colorable if for a given list assignment L = {L(v) : v ∈ V (G)} there is a proper coloring φ of G such that for all v ∈ V (G), φ(v) ∈ L(v). If G is L-list colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V (G), then G is said to be k-choosable or k-list-colorable. The list chromatic number of a graph G is the smallest integer k such that G is k-choosable. List coloring can be very different from usual coloring as there exist graphs with a small chromatic number and an arbitrarily large list chromatic number.

In 1969, Kramer and Kramer introduced the notion of 2-distance coloring [START_REF] Kramer | Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz p[END_REF][START_REF] Kramer | Un problème de coloration des sommets d'un graphe[END_REF]. This notion generalizes the "proper" constraint (that does not allow two adjacent vertices to have the same color) in the following way: a 2-distance k-coloring is such that no pair of vertices at distance at most 2 have the same color. The 2-distance chromatic number of G, denoted by χ 2 (G), is the smallest integer k such that G has a 2-distance k-coloring. Similarly to proper k-list-coloring, one can also define 2-distance k-list-coloring and a 2-distance list chromatic number.

For all v ∈ V , we denote d G (v) the degree of v in G and by ∆(G) = max v∈V d G (v) the maximum degree of a graph G. For brevity, when it is clear from the context, we will use ∆ (resp. d(v)) instead of ∆(G) (resp. d G (v)). One can observe that, for any graph G, ∆ + 1 ≤ χ 2 (G) ≤ ∆ 2 + 1. The lower bound is trivial since, in a 2-distance coloring, every neighbor of a vertex v with degree ∆, and v itself must have a different color. As for the upper bound, a greedy algorithm shows that χ 2 (G) ≤ ∆ 2 + 1. Moreover, that upper bound is tight for some graphs, for example, Moore graphs of type (∆, 2), which are graphs where all vertices have degree ∆, are at distance at most two from each other, and the total number of vertices is ∆ 2 + 1. See Figure 1.

By nature, 2-distance colorings and the 2-distance chromatic number of a graph depend a lot on the number of vertices in the neighborhood of every vertex. More precisely, the "sparser" a graph is, the lower its 2-distance chromatic number will be. One way to quantify the sparsity of a graph is through its maximum average degree. The average degree ad of a graph G = (V, E) is defined by ad(G) = 2|E|

|V | . The maximum average degree mad(G) is the maximum, over all subgraphs H of G, of ad(H). Another way to measure the sparsity is through the girth, i.e. the length of a shortest cycle. We denote g(G) the girth of G. Intuitively, the higher the girth of a graph is, the sparser it gets. These two measures can actually be linked directly in the case of planar graphs.

A graph is planar if one can draw its vertices with points on the plane, and edges with curves intersecting only at its endpoints. When G is a planar graph, Wegner conjectured in 1977 that χ 2 (G) becomes linear in ∆(G): Conjecture 1 (Wegner [27]). Let G be a planar graph with maximum degree ∆. Then,

χ 2 (G) ≤    7, if ∆ ≤ 3, ∆ + 5, if 4 ≤ ∆ ≤ 7, 3∆ 2 + 1, if ∆ ≥ 8.
The upper bound for the case where ∆ ≥ 8 is tight (see Figure 2(i)). Recently, the case ∆ ≤ 3 was proved by Thomassen [START_REF] Thomassen | The square of a planar cubic graph is 7-colorable[END_REF], and by Hartke et al. [START_REF] Hartke | The chromatic number of the square of subcubic planar graphs[END_REF] independently. For ∆ ≥ 8, Havet et al. [START_REF] Havet | List colouring squares of planar graphs[END_REF] proved that the bound is

3 2 ∆(1 + o(1)
), where o( 1) is as ∆ → ∞ (this bound holds for 2-distance list-colorings). Conjecture 1 is known to be true for some subfamilies of planar graphs, for example K 4 -minor free graphs [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF]. Wegner's conjecture motivated extensive researches on 2-distance chromatic number of sparse graphs, either of planar graphs with high girth or of graphs with upper bounded maximum average degree which are directly linked due to Proposition 2.

Proposition 2 (Folklore). For every planar graph G, (mad

(G) -2)(g(G) -2) < 4.
As a consequence, any theorem with an upper bound on mad(G) can be translated to a theorem with a lower bound on g(G) under the condition that G is planar. Many results have taken the following form: every graph G of mad(G) < m 0 and ∆(G) ≥ ∆ 0 satisfies χ 2 (G) ≤ ∆(G) + c(m 0 , ∆ 0 ) where c(m 0 , ∆ 0 ) is a constant depending only on m 0 and ∆ 0 . Due to Proposition 2, as a corollary, the same results on planar graphs of girth g ≥ g 0 (m 0 ) where g 0 depends on m 0 follow. Table 1 shows all known such results, up to our knowledge, on the 2-distance chromatic number of planar graphs with fixed girth, either proven directly for planar graphs with high girth or came as a corollary of a result on graphs with bounded maximum average degree. Table 1. The latest results with a coefficient 1 before ∆ in the upper bound of χ 2 .

For example, the result from line "7" and column "∆ + 1" from Table 1 reads as follows : "every planar graph G of girth at least 7 and of ∆ at least 16 satisfies χ 2 (G) ≤ ∆ + 1". The crossed out cases in the first column correspond to the fact that, for g 0 ≤ 6, there are planar graphs G with χ 2 (G) = ∆ + 2 for arbitrarily large ∆ [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF][START_REF] Dvořák | Coloring squares of planar graphs with girth six[END_REF]. The lack of results for g = 4 is due to the fact that the graph in Figure 2(ii) has girth 4, and

χ 2 = 3∆ 2 -1 for all ∆.
We are interested in the case χ 2 (G) ≤ ∆ + 2. In particular, we were looking for the smallest integer ∆ 0 such that every graph with maximum degree ∆ ≥ ∆ 0 and mad < 8 3 (resp. mad < 14 5 ) can be 2-distance colored with ∆ + 2 colors. That family contains planar graphs with ∆ ≥ ∆ 0 and girth at least 8 (resp. 7).

Our main results are the following:

Theorem 3. If G is a graph with mad(G) ≤ 8 3 , then G is 2-distance (∆(G) + 2)-colorable for ∆(G) ≥ 6. Theorem 4. If G is a graph with mad(G) ≤ 14 5 , then G is 2-distance (∆(G) + 2)-colorable for ∆(G) ≥ 10.
For planar graphs, we obtain the following corollaries:

Corollary 5. If G is a graph with g(G) ≥ 8, then G is 2-distance (∆(G) + 2)-colorable for ∆(G) ≥ 6. Corollary 6. If G is a graph with g(G) ≥ 7, then G is 2-distance (∆(G) + 2)-colorable for ∆(G) ≥ 10.
We will prove Theorems 3 and 4 respectively in Sections 2 and 3 using the same scheme.

Proof of Theorem 3

Notations and drawing conventions.

For v ∈ V (G), the 2-distance neighborhood of v, denoted N * G (v)
, is the set of 2-distance neighbors of v, which are vertices at distance at most two from v, not including v. We also denote

d * G (v) = |N * G (v)|.
We will drop the subscript and the argument when it is clear from the context. Also for conciseness, from now on, when we say "to color" a vertex, it means to color such vertex differently from all of its colored neighbors at distance at most two. Similarly, any considered coloring will be a 2-distance coloring. We say that a vertex u "sees" a vertex v if v ∈ N * G (u). We also say that u "sees a color" c if there exists v ∈ N * G (u) such that v is colored c. Some more notations:

• A d-vertex (d + -vertex, d --vertex) is a vertex of degree d (at least d, at most d). A (d ↔ e)-vertex is a
vertex of degree between d and e included.

• A k-path (k + -path, k --path) is a path of length k + 1 (at least k + 1, at most k + 1) where the k internal vertices are 2-vertices. The endvertices of a k-path are 3 + -vertices.

• A (k 1 , k 2 , . . . , k d )-vertex is a d-vertex incident to d different paths, where the i th path is a k i -path for all 1 ≤ i ≤ d.
As a drawing convention for the rest of the figures, black vertices will have a fixed degree, which is represented, and white vertices may have a higher degree than what is drawn. Also, we will represented the lower bound on the number of available colors next to each not yet colored vertex in a subgraph H of G when G -H is colored.

Let G 1 be a counterexample to Theorem 3 with the fewest number of vertices. Graph G 1 has maximum degree ∆ ≥ 6 and mad(G) < 8 3 . The purpose of the proof is to prove that G 1 cannot exist. In the following we will study the structural properties of G 1 . We will then apply a discharging procedure.

Structural properties of

G 1 Lemma 7. Graph G 1 is connected.
Proof. Otherwise a component of G 1 would be a smaller counterexample. Lemma 8. The minimum degree of G 1 is at least 2.

Proof. By Lemma 7, the minimum degree is at least 1. If G 1 contains a degree 1 vertex v, then we can simply remove v and 2-distance color the resulting graph, which is possible by minimality of G 1 . Then, we add v back and color it (at most ∆ constraints and ∆ + 2 colors).

Lemma 9. Graph G 1 has no 3 + -paths. Proof. Suppose G 1 contains a 3 + -path v 0 v 1 v 2 v 3 . . . v k with k ≥ 4. We color H = G 1 -{v 1 , v 2 , v 3 } by minimality of G 1 ,
then we finish by coloring v 1 , v 3 , and v 2 in this order, which is possible since they have at least respectively 2, 2, and ∆ ≥ 6 available colors left after the coloring of H. Lemma 10. A 2-path has two distinct endvertices and both have degree ∆.

Proof. Suppose that G 1 contains a 2-path v 0 v 1 v 2 v 3 . If v 0 = v 3 , then we color G 1 -{v 1 , v 2 }
by minimality of G 1 and extend the coloring to G 1 by coloring greedily v 1 and v 2 who has 3 available colors each. Now, suppose that v 0 = v 3 , and that d(v 3 ) ≤ ∆ -1. We color G 1 -{v 1 , v 2 } by minimality of G 1 and extend the coloring to G 1 by coloring v 1 then v 2 , which is possible since they have respectively 1 and 2 available colors left. Thus, d(v 3 ) = ∆ and the same holds for d(v 0 ) by symmetry.

v 0 v 1 2 v 2 6 v 3 2 v 4 (i) A 3 + -path. v 0 v 1 3 v 2 3
(ii) A 2-path where both endvertices are the same.

v 0 v 1 1 v 2 2 (∆ -1) - v 3 (iii) A 2-path incident to a (∆ -1) -- vertex.
Figure 3.

Lemma 11.

Graph G 1 has no cycles consisting of 2-paths.

Proof. Suppose that G 1 contains a cycle consisting of k 2-paths (see Figure 4). We remove all vertices v 3i+1 and v 3i+2 for 0 ≤ i ≤ k -1. Consider a coloring of the resulting graph. It is then possible to color v 1 , v 2 , v 4 , . . . , v 3k-1 since each of them has at least two choices of colors (as

d(v 0 ) = d(v 3 ) = • • • = d(v 3(k-1) ) = ∆ due to Lemma 10)
and by 2-choosability of even cycles. Proof. Suppose there exists a (1, 1, 1)-vertex u with three 2-neighbors u 1 , u 2 , and u 3 . Let v i be the other endvertex of

v 3 v 0 v 2 2 v 1 2 2 2 v 3j 2 2 v 3(j+1) v 3k-1
uu i v i for 1 ≤ i ≤ 3.
First, suppose by contradiction that v 1 = v 2 (and possibly = v 3 ). We color G 1 -{u, u 1 , u 2 , u 3 } by minimality of G 1 . Then, we color u 3 , u 1 , u 2 , and u in this order, which is possible since they have at least respectively 2, 3, 3, and ∆ ≥ 6 colors. So, v 1 , v 2 , and v 3 are all distinct. Now, suppose w.l.o.g. that d(v 1 ) ≤ ∆ -1 by contradiction. We color

G 1 -{u, u 1 , u 2 , u 3 } by minimality of G 1 .
Then, we color u 3 , u 2 , u 1 , and u in this order. So,

d(v 1 ) = d(v 2 ) = d(v 3 ) = ∆. v 1 = v 2 u 1 3 u 6 u 3 2 v 3 u 2

3

(i) A (1, 1, 1)-vertex that sees only two vertices at distance 2.

(∆ -1) -

v 1 u 1 3 u 5 u 3 2 v 3 u 2 2 v 2
(ii) A (1, 1, 1)-vertex that sees a (∆-1) --vertex at distance 2.

Figure 5.

Definition 13 ((1, 1, 1)-paths). We call v 0 v 1 v 2 v 3 v 4 a (1, 1, 1)-path when v 0 and v 4 are ∆-vertices, v 1 and v 3 are 2-vertices, and v 2 is a (1, 1, 1)-vertex.

Lemma 14.

Graph G 1 has no cycles consisting of (1, 1, 1)-paths.

Proof. Suppose that G contains a cycle consisting of k (1, 1, 1)-paths (see Figure 6). We remove all vertices v 4i+1 , v 4i+2 , v 4i+3 for 0 ≤ i ≤ k -1. Consider a coloring of the resulting graph. We color v 1 , v 3 , v 5 , . . . , v 4k-1 since each of them has at least two choices of colors (as

d(v 0 ) = d(v 4 ) = • • • = d(v 4(k-1) ) = ∆ due to Lemma 12)
and by 2-choosability of even cycles. Finally, it is easy to color greedily v 2 , v 6 , . . . , v 4k-2 since they each have at most six forbidden colors. Proof. Suppose that there exists a (1, 1, 0)-vertex u with a (3 ↔ ∆ -3)-neighbor. Let u 1 and u 2 be its 2neighbors. Let v = u be the other neighbor of u 1 . Suppose w.l.o.g. that d(v) ≤ ∆ -1 by contradiction. We color G 1 -{u, u 1 , u 2 } by minimality of G 1 . Then, we color u 2 , u 1 , and u in this order, which is possible since they have at least respectively 1, 2, and 3 colors as we have ∆ + 2 colors.

v 4 v 0 v 3 2 v 2 ∆ -2 v 1 2 2 2 v 4j v 4j+1 2 v 4j+2 ∆ -2 v 4j+3 2 v 4(j+1) v 4k-1
(∆ -1) - v u 1 2 u 3 u 2 1 3 ↔ ∆ -3
uu i v i (1 ≤ i ≤ ∆ -2) where each v i is a 3 --vertex. Proof. Let uu ∆-1 v ∆-1 / ∈ {uu i v i |1 ≤ i ≤ ∆ -2} be a 1-path where v ∆-1 is a (1, 1, 1)-vertex. Let uu ∆ u ∆ v ∆ be a 2-path incident to u where uu ∆ u ∆ / ∈ {uu i v i |1 ≤ i ≤ ∆ -1}. Observe that v ∆-1 / ∈ {v i |1 ≤ i ≤ ∆ -2} due to Lemma 12 and v ∆ / ∈ {v i |1 ≤ i ≤ ∆ -2} due to Lemma 10. Let H = u ∪ N G (u) ∪ {u ∆ }.
We color G -H by minimality of G and we uncolor v ∆-1 . Let L(x) be the list of remaining colors for a vertex

x ∈ H ∪ {v ∆-1 }. Observe that |L(u)| ≥ ∆ + 2 -(∆ -2) ≥ 4, |L(u ∆ )| ≥ 2 (since d(v ∆ ) = ∆ by Lemma 10), |L(v ∆-1 )| ≥ ∆ -2 ≥ 4, |L(u i )| ≥ ∆ -1 (since d(v i ) ≤ 3) for 1 ≤ i ≤ ∆ -2, |L(u ∆-1 )| ≥ ∆, and |L(u ∆ )| ≥ ∆ + 1.
We remove the extra colors from L(u ∆ ) so that |L(u ∆ )| = 2. We color u with a color that is not in L(u ∆ ), then u 1 , u 2 , . . . , u ∆ , v ∆-1 , and u ∆ in this order. Observe that when

v i = v j for 1 ≤ i ≤ j ≤ ∆ -2, then |L(u i )| ≥ ∆ and |L(u j )| ≥ ∆
so the order in our coloring still hold. Thus, we obtain a valid coloring of G, which is a contradiction.

v ∆-1 4 u ∆-1 ∆ u 4 u ∆ ∆ + 1 u ∆ 2 v ∆ u 1 ∆ -1 . . . 3 - v 1 u ∆-2 ∆ -1 3 - v ∆-2
Figure 8. A ∆-vertex incident to a 2-path, a (1, 1, 1)-path, and ∆ -2 other 1 + -paths with 3-endvertices.

Discharging rules

Definition 17 (2-path sponsors). Consider the set of 2-paths in G. By Lemma 10, the endvertices of every 2-paths are ∆-vertices and by Lemma 11, the graph induced by the edges of all the 2-paths of G is a forest F. For each tree of F, we choose one ∆-vertex as an arbitrary root. Each 2-path is assigned a unique sponsor which is the ∆-endvertex that is further away from the root. See Figure 9. Definition 18 ((1, 1, 1)-path sponsors). Consider the set of (1, 1, 1)-paths in G. By Lemma 12, the endvertices of every (1, 1, 1)-paths are ∆-vertices and by Lemma 14, the graph induced by the edges of all the (1, 1, 1)-paths of G is a forest F. For each tree of F, we choose one ∆-vertex as an arbitrary root. Each (1, 1, 1)-vertex v is assigned two sponsors which are the ∆-vertices that are grandsons of v. See Figure 10. 10. The sponsor assignment in a tree consisting of (1, 1, 1)-paths.

∆ root ∆ ∆ sponsor ∆ ∆ ∆ ∆ Figure
Since we have mad(G 1 ) < 8 3 , we must have

v∈V (G1) (3d(v) -8) < 0 (1)
We assign to each vertex v the charge µ(v) = 3d(v) -8. To prove the non-existence of G 1 , we will redistribute the charges preserving their sum and obtaining a non-negative total charge, which will contradict Equation (1). R0 (see Figure 11): Every 3 + -vertex gives 1 to each 2-neighbor on an incident 1-path.

R1 (see Figure 12): Let u be incident to a 2-path P = uu 1 u 2 v.

(i) If u is not P 's sponsor, then u gives 3 2 to u 1 . (ii) If u is P 's sponsor, then u gives 2 to u 1 and 1 2 to u 2 . R2 (see Figure 13): Every 4 + -vertex gives 1 to each 3-neighbor. R3 (see Figure 14): Let uvw be a 1-path.

(i) If u is a ∆-vertex, w is a (1, 1, 1)-vertex, and u is w's sponsor, then u gives 1 to w.

(ii) If u is a ∆-vertex and w is a (1, 1, 0)-vertex, then u gives 1 2 to w.

w v ∆ u ∆ sponsors 1 1 (i) (1, 1, 1)-path sponsor. ∆ u v w 3 + 3 + 1 2
(ii)

Figure 14. R3.

Verifying that charges on each vertex are non-negative

Let µ * be the assigned charges after the procedure. In what follows, we prove that:

∀u ∈ V (G 1 ), µ * (u) ≥ 0. Let u ∈ V (G 1 ). Case 1: If d(u) = 2, then recall that µ(u) = 3 • 2 -8 = -2.
There are no 3 + -paths due to Lemma 9 so u must lie on a 1-path or a 2-path.

If u is on a 1-path, then it has two 3 + -neighbors which give it 1 each by R0. Thus,

µ * (u) = -2 + 2 • 1 = 0.
If u is on a 2-path, then it either receives 2 from an adjacent sponsor by R1(ii), or it receives 3 2 + 1 2 = 2 from an adjacent non-sponsor ∆-neighbor and a distance 2 sponsor respectively by R1(i) and R1(ii). Thus,

µ * (u) = -2 + 2 = 0. Case 2: If d(u) = 3, then recall that µ(u) = 3 • 3 -8 = 1.
Observe that u only gives charge away by R0 (charge 1 to each 2-neighbor).

If u is a (1, 1, 1)-vertex, then the other endvertices of the 1-paths incident to u are all ∆-vertices due to Lemma 12. Moreover, by Definition 18, u has two sponsors which give it 1 each by R3(i). Hence,

µ * (u) = 1 -3 • 1 + 2 • 1 = 0.
If u is a (1, 1, 0)-vertex with a 4 + -neighbor, then it receives 1 from its neighbor by R2. Thus,

µ * (u) = 1 -2 • 1 + 1 = 0.
If u is a (1, 1, 0)-vertex with a 3-neighbor (3 ≤ ∆ -3 since ∆ ≥ 6), then it receives 1 2 by R3(ii) from each of the other endvertices of its incident 1-paths due to Lemma 15. Thus, • If u is neither a 2-path sponsor nor a (1, 1, 1)-path sponsor, then observe that u gives away at most 3 2 along an incident path by R1(i), a combination of R0 and R3(i), or less by R2. So at worst,

µ * (u) = 1 -2 • 1 + 2 • 1 2 = 0. If u is a (1 -, 0, 0)-vertex, then µ * (u) ≥ 1 -1 = 0.
µ * (u) ≥ 3∆ -8 - 3 2 ∆ ≥ 3 2 • 6 -8 = 1.
• If u is a 2-path sponsor but not a (1, 1, 1)-path sponsor, then u gives 2 + 1 2 = 5 2 to its unique sponsored incident 2-path by R1(ii). For the other incident paths, it gives at most 3 2 like above. So,

µ * (u) ≥ 3∆ -8 - 5 2 - 3 2 (∆ -1) ≥ 3 2 • 6 -8 - 5 2 + 3 2 = 0.
• If u is a (1, 1, 1)-path sponsor but not a 2-path sponsor, then u gives 1 + 1 = 2 to the unique incident (1, 1, 1)-path containing its assigned (1, 1, 1)-vertex v: 1 to the 2-neighbor by R0 and 1 to v by R3(i).

Once again, u gives at most 3 2 to the other incident paths. So,

µ * (u) ≥ 3∆ -8 -2 - 2 (∆ -1) ≥ 3 2 • 6 -8 -2 + 3 2 = 1 2 .
• If u is both a 2-path sponsor and a (1, 1, 1)-path sponsor, then u gives 5 2 to its unique sponsored 2-path and 2 to its unique assigned (1, 1, 1)-vertex like above. Now, let us consider the other ∆ -2 paths incident to u. Observe that when u gives 3 2 along an incident path either by R1(i) or by a combination of R0 and R3(ii), that path must be a 1 + -path where the vertex at distance 2 from u is a 3 --vertex. Due to Lemma 16, u never has to give 3 2 to each of the ∆ -2 paths. As a result, there exists one path to which u gives at most 1. So at worst,

µ * (u) ≥ 3∆ -8 - 5 2 -2 -1 - 3 2 (∆ -3) ≥ 3 2 • 6 -8 - 5 2 -2 -1 + 9 2 = 0.
We obtain a non-negative amount of charge on each vertex, which is impossible since the total amount of charge is negative. As such, G 1 cannot exist. That concludes the proof of Theorem 3.

Lemma 28. A (1, 0, 0)-vertex with two (3 ↔ 4)-neighbors shares its 2-neighbor with a ∆-vertex.

Proof. Suppose by contradiction that there exists a (1, 0, 0)-vertex u with two (3 ↔ 4)-neighbors u 1 , u 2 , and let uvw be the

(∆ -2) - v 1 u 1 4 u 8 u 2 4 (∆ -2) - v 2 u 3 2 v 3 u 4 2 v 4
Figure 16. A (1, 1, 1, 1)-vertex that sees two (∆ -2) --vertex at distance 2.

Discharging rules

Since we have mad(G 2 ) < 14 5 , we must have

v∈V (G2) (5d(v) -14) < 0 (2)
We assign to each vertex v the charge µ(v) = 5d(v) -14. To prove the non-existence of G 2 , we will redistribute the charges preserving their sum and obtaining a positive total charge, which will contradict Equation (2).

Observe that Definitions 17 and 18 also hold for G 2 thanks to Lemmas 23 and 25.

We apply the following discharging rules: R0 (see Figure 17): Every 3 + -vertex gives 2 to each 2-neighbor on an incident 1-path.

R1 (see Figure 18): Let u be incident to a 2-path P = uu 1 u 2 v.

(i) If u is not P 's sponsor, then u gives 7 2 to u 1 . (ii) If u is P 's sponsor, then u gives 4 to u 1 and 1 2 to u 2 . R2 (see Figure 19): (i) Every (5 ↔ 7)-vertex gives 1 to each 3-neighbor.

• If u is a (1, 1, 1)-path sponsor but not a 2-path sponsor, then u gives 2 + 2 = 4 to the unique incident (1, 1, 1)-path containing its assigned (1, 1, 1)-vertex v: 1 to the 2-neighbor by R0 and 1 to v by R3(i).

Once again, u gives at most 7 2 to the other incident paths. So, µ * (u) ≥ 5∆ -14 -4 -7 2 (∆ -1) ≥ 3 2

• 10 -14 -4 + 7 2 = 1 2 .

• If u is both a 2-path sponsor and a (1, 1, 1)-path sponsor, then u gives 9 2 to its unique sponsored 2-path and 4 to its unique assigned (1, 1, 1)-vertex like above. Now, let us consider the other ∆ -2 paths incident to u. Observe that when u gives 7 2 along an incident path either by R1(i) or by a combination of R0 and R3(iii), that path must be a 1 + -path where the vertex at distance 2 from u is a 3 --vertex. Due to Lemma 27, u never has to give 7 2 to each of the ∆ -2 paths. As a result, there exists one path to which u gives at most 3. So at worst, µ * (u) ≥ 5∆ -14 - We obtain a non-negative amount of charge on each vertex, which is impossible since the total amount of charge is negative. As such, G 2 cannot exist. That concludes the proof of Theorem 4.

  The Moore graph of type (2,2): the odd cycle C5.

  The Moore graph of type (3,2): the Petersen graph. (iii) The Moore graph of type (7,2): the Hoffman-Singleton graph.

Figure 1 .

 1 Figure 1. Examples of Moore graphs for which χ 2 = ∆ 2 + 1.

Figure 2 .

 2 Figure 2. Graphs with χ 2 ≈ 3 2 ∆.

2 2 Figure 4 .Lemma 12 .

 22412 Figure 4. A cycle consisting of consecutive 2-paths.

2 2 Figure 6 .

 226 Figure 6. A cycle consisting of consecutive (1, 1, 1)-paths.

Figure 7 .

 7 Figure 7. A (1, 1, 0)-vertex with a (3 ↔ ∆ -3)-neighbor that shares a 2-neighbor with a (∆ -1) --vertex.

Figure 9 .

 9 Figure 9. The sponsor assignment in a tree consisting of 2-paths.

  Figure 11. R0.

Figure 12 .

 12 Figure 12. R1.

  Figure 13. R2.

Case 3 :Case 4 :

 34 [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF] ≤ d(u) ≤ ∆ -1, then u only gives away at most 1 to each neighbor by R0 or R2. Thus,µ * (u) ≥ 3d(u) -8 -d(u) ≥ 2 • 4 -8 = 0. If d(u) = ∆,then we distinguish the following cases.

  1-path incident to u, where d(w) ≤ ∆ -1. We color G 2 -{v} by minimality of G 2 , then we uncolor u. Since we have ∆ + 2 ≥ 12 colors and d * (u) = d(u 1 ) + d(u 2 ) + 2 ≤ 4 + 4 + 2 = 10, we can always color u last. Finally, v has at least one available color. Thus, we obtain a valid coloring of G 2 , which is a contradiction. Consider the four other endvertices of the 1-paths incident to a (1, 1, 1, 1)-vertex. At most one of them is a (∆ -2) --vertex.Proof. Suppose by contradiction that we have a (1, 1, 1, 1)-vertex u incident to four 1-paths uu i v i for 1 ≤ i ≤ 4, where v 1 and v 2 are (∆ -2) --vertices. We color G 2 -{u, u 1 , u 2 , u 3 , u 4 } by minimality of G 2 . Then, it suffices to color u 3 , u 4 , u 1 , u 2 , and u in this order, which is possible since they have at least respectively 2, 2, 4, 4, and 8 available colors as we have ∆ + 2 colors and ∆ ≥ 10.

		u 2
		3 ↔ 4
	3 ↔ 4 u 1	u	v	(∆ -1) -w
		2	1
	Figure 15. A (1, 0, 0)-vertex with two (3 ↔ 4)-neighbor that shares a 2-neighbor with a (∆ -1) --vertex.
	Lemma 29.

Acknowledgements

This work 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.

Proof of Theorem 4

We will reuse similar notations to Section 2. Let G 2 be a counterexample to Theorem 4 with the fewest number of vertices. Graph G 2 has maximum degree ∆ ≥ 10 and mad < 14 5 . The purpose of the proof is to prove that G 2 cannot exist.

Structural properties of G 2

Observe that the proofs of Lemmas 7 to 12 and 14 to 16 only rely on the facts that we have a minimal counterexample, two more colors than the maximum degree, and that ∆ was large enough (∆(G 1 ) ≥ 6). All of these still hold for G 2 (∆(G 2 ) ≥ 10). Thus, we also have the following.

We will show some more reducible configurations.

(ii) Every 8 + -vertex gives 3 to each 3-neighbor. R3 (see Figure 20): Let uvw be a 1-path.

(i) If u is a ∆-vertex, w is a (1, 1, 1)-vertex, and u is w's sponsor, then u gives 2 to w.

(ii) If u is a ∆-vertex, w is a (1, 1, 1)-vertex, and u is not w's sponsor, then u gives 1 to w.

(iii) If u is a ∆-vertex and w is a (1, 1 -, 0)-vertex, then u gives 3 2 to w. (iv) If u is a 9 + -vertex and w is a 4-vertex, then u gives 2 3 to w.

Verifying that charges on each vertex are non-negative

Let µ * be the assigned charges after the discharging procedure. In what follows, we prove that:

Recall that there exists no 3 + -path due to Lemma 21. So, u must lie on a 1-path or a 2-path.

If u is on a 1-path, then it has two 3 + -neighbors which give it 2 each by R0. Thus,

If u is on a 2-path, then u receives 4 from an adjacent sponsor by R1(ii), or it receives 7 2 + 1 2 = 4 from an adjacent non-sponsor and a distance 2 sponsor respectively by R1(i) and R1(ii). Thus,

Observe that u only gives charge away by R0 (charge 2 to each 2-neighbor).

If u is a (1, 1, 1)-vertex, then the other endvertices of the 1-paths incident to u are all ∆-vertices due to Lemma 24. As a result, u receives 2 from each of its two sponsors and 1 from the non-sponsor ∆-vertex by R3(i) and R3(ii). Hence,

If u is a (1, 1, 0)-vertex with a 8 + -neighbor, then it receives 3 from its 8 + -neighbor by R2(ii). Thus,

If u is a (1, 1, 0)-vertex with an 7 --neighbor (7 ≤ ∆ -3 since ∆ ≥ 10), then it receives 3 2 by R3(iii) from each of the other endvertices of its incident 1-paths due to Lemma 26. Thus,

If u is a (1, 0, 0)-vertex with a 5 + -neighbor, then it receives at least 1 from that neighbor by R2. Thus,

If u is a (1, 0, 0)-vertex with two (3 ↔ 4)-neighbors, then it receives 3 2 by R3(i) from the other endvertex of its incident 1-path due to Lemma 28. So,

Observe that u only gives charge by R0 (charge 2 to each 2-neighbor).

If u is a (1, 1, 1, 1)-vertex, then at least three of the four other endvertices of the 1-paths incident to u are (∆ -1) + -vertices (which are 9 + -vertices since ∆ ≥ 10) due to Lemma 29. As a result, u receives 2 3 from each of the 9 + -endvertex by R3(iv). Hence, • If u is a 2-path sponsor but not a (1, 1, 1)-path sponsor, then u gives 4 + 1 2 = 9 2 to its unique sponsored incident 2-path by R1(ii). For the other incident paths, it gives at most