Marilena Oita
email: marilena.oita@telecom-paristech.fr

Pierre Senellart
email: pierre.senellart@telecom-paristech.fr

Deriving Dynamics of Web Pages: A Survey *

Keywords: H.3.5 [Information Storage and Retrieval]: Online Information ServicesŮWeb-based services Algorithms, Experimentation, Measurement Change monitoring, Web archiving, Timestamping

The World Wide Web is dynamic by nature: content is continuously added, deleted, or changed, which makes it challenging for Web crawlers to keep up-to-date with the current version of a Web page, all the more so since not all apparent changes are signiĄcant ones. We review major approaches to change detection in Web pages and extraction of temporal properties (especially, timestamps) of Web pages. We focus our attention on techniques and systems that have been proposed in the last ten years and we analyze them to get some insight into the practical solutions and best practices available. We aim at providing an analytical view of the range of methods that can be used, distinguishing them on several dimensions, especially, their static or dynamic nature, the modeling of Web pages, or, for dynamic methods relying on comparison of successive versions of a page, the similarity metrics used. We advocate for more comprehensive studies of the efectiveness of Web page change detection methods, and Ąnally highlight open issues.

INTRODUCTION

The World Wide Web challenges our capacity to develop tools that can keep track of the huge amount of information that is getting modiĄed at speed rate. Web archiving crawlers [START_REF]Web Archiving[END_REF], especially, need the ability to detect change in Web content and to infer when a Web page last changed. This ability is fundamental in maintaining the coherence of the crawl, in adjusting its refresh rate, in versioning, and to allow a user to retrieve meaningful temporal data. The understanding of the dynamics of Web pages, that is, how fast the Web content changes and what the nature of these changes is, its implications on the structure of the Web, and the correlation with the topic of pages are also popular subjects in the research literature [START_REF] Baeza-Yates | Web dynamics, structure, and page quality[END_REF].

In addition to being of paramount importance to Web archiving, the subject of change detection is of interest in various applications and domains, such as: large-scale information monitoring and delivery systems [START_REF] Jacob | WebVigiL: An approach to just-in-time information propagation in large network-centric environments[END_REF][START_REF] Douglis | The AT&T Internet diference engine: Tracking and viewing changes on the Web[END_REF][START_REF] Liu | WebCQ: Detecting and delivering information changes on the Web[END_REF][START_REF] Flesca | Eicient and efective Web page change detection[END_REF][START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF] or services 1 , Web cache improvement [START_REF] Cho | Estimating frequency of change[END_REF], version conĄguration and management of Web archives [START_REF] Pehlivan | A novel Web archiving approach based on visual pages analysis[END_REF], active databases [START_REF] Jacob | WebVigiL: An approach to just-in-time information propagation in large network-centric environments[END_REF], servicing of continuous queries [START_REF] Abiteboul | Issues in monitoring web data[END_REF]. Research has focused on Ąnding novel techniques for comparing snapshots of Web pages (a reference Web page and its updated version) in order to detect change and estimate its frequency. Change can however be detected at various levels: there are various aspects of dynamics which must be considered when studying how Web content changes and evolves.

The majority of works have seen the change detection problem from a document-centric perspective, as opposed to an object-centric one. By object or entity we mean here any Web content, part of a Web page, that represents meaningful information per se: image, news article, blog post, comment, etc.. Comparatively, little efort has been put on making the diference between relevant changes and those that might occur because of the dynamic template of a Web page (ads, active layout, etc.), i.e., its boilerplate [START_REF] Kholschutter | Boilerplate detection using shallow text features[END_REF].

We study in this article some of the strategies that have been established in diferent settings, with the aim at providing an overview of the existing techniques used to derive temporal properties of Web pages.

There is a large body of work on the related problem of change detection in XML documents, particularly for purposes of data integration and update management in XML-centric databases. However, the solutions developed for XML documents cannot be applied without serious revisions for HTML pages. The model assumptions made for XML do not really hold for HTML. Indeed, the HTML and XML formats have a key diference: while an XML page deĄnes the nature of the content by its meta tags, HTML tags deĄne mainly presentational aspects of content within. In addition to the challenges that exist in XML documents, Web pages add some others by their lack of formal semantics, a fuzziness regarding the formatting, by the embedding of multimedia and scripts, etc.. Separate approaches commonly need to be adopted and the research done on XML documents is beyond the scope of our paper, although we mention some works on XML [START_REF] Wang | X-Dif: An efective change detection algorithm for XML documents[END_REF][START_REF] Cobéna | Detecting changes in XML documents[END_REF] that have particular relevance to Web page change detection. We refer the reader to [START_REF] Cobéna | A comparative study of XML change detection algorithms[END_REF] for a survey of XML change detection algorithms.

We focus in this survey on deriving dynamics of HTML documents.

Change detection mechanisms can either be static, estimating the date of last modiĄcation of content from the Web page itself (its code, semantics or neighbors), or dynamic, by comparing successive versions of a Web page. The structure of this article reĆects these dimensions. In Section 2, we present static approaches to timestamping Web pages, while Section 3 introduce dynamic methods. We then analyze in Section 4 the diferent models of a Web page used by existing techniques for comparing successive versions. Similarity metrics used in dynamic methods are independently investigated in Section 5. We brieĆy describe statistical modeling approaches to estimate change frequency in Section 6. We conclude with a discussion of some remaining open questions.

STATIC APPROACHES: TIMESTAMPING

This section deals with methods for inferring temporal properties of a Web page in a static manner as opposed to the commonly used dynamic computation of the diference between successive versions of a given Web page. The goal here is to infer the creation or the last modiĄcation date of a Web page or, possibly, of some parts of it. We study sources of data that can be useful for that purpose: metadata, the content of the Web page itself, or its graph neighborhood. The canonical way for timestamping a Web page is to use the Last-Modified HTTP header. Unfortunately, studies have shown this approach is not reliable in general [START_REF] Clausen | Concerning Etags and datestamps[END_REF]. We describe next why this happens in practice and other techniques for timestamping Web pages.

HTTP metadata

HTTP/1.1, the main protocol used by Web clients and servers to exchange information, ofers several features of interest for timestamping, the foremost of which are the ETag and Last-Modified HTTP response headers. Entity tags (or ETags) are unique identiĄers for a given version of a particular document. They are supposed to change if and only if the document itself changes. Servers can return this with any response, and clients can use the If-Match and If-None-Match HTTP requests headers to condition the retrieval of the document to a change in the ETag value, avoiding then to retrieve already known contents. If-Modified-Since and If-Unmodified-Since provide conditional downloading features, in a similar way as for ETags. Even when conditional downloading is not possible, Etags and HTTP timestamps can be retrieved by a Web client without downloading a whole Web page by making use of the head HTTP method. The problem is that while this information is generally provided and is very reliable for static content (e.g., static HTML pages or PDF), it is most of the time missing or changed at every request (the timestamp given is that of the request, not of the content change) when the content is dynamic (gen-erated by content management systems, etc.). Some CMSs do return correct HTTP timestamps, such as MediaWiki2 , but they seem to be a minority.

In [START_REF] Clausen | Concerning Etags and datestamps[END_REF], Clausen presents an experimental study of the reliability of Etags and HTTP timestamps on a collection of a few million Danish Web pages. He Ąnds out that the best strategy for avoiding useless downloads of versions of Web pages already available in a Web archive is to always download when the ETag server is missing, and otherwise download only if the Last-Modified header indicates change. This rather counterintuitive result yielded in this experimental study an almost perfect prediction of change, and a 63% accuracy in predicting non-change. Given that the majority of Web servers run some version of the open-source Apache3 HTTP server [START_REF]Web survey[END_REF], it would be interesting to see whether this strategy is correlated with some inherent behavior of this software. Furthermore, repeating this experiment on a larger scale and with a more recent set of Web pages would be of interest.

HTTP also provides the Cache-Control and Expires response headers. This information is often given, but with a zero or very low expiration delay, which means that nothing interesting can be derived from it. In some speciĄc and controlled environments (e.g., Intranets), it might still be useful to look at these two pieces of information to estimate the refresh rate of a Web page.

Timestamps in Web content

Content management systems, as well as Web authors, often provide in the content of a Web page some humanreadable information about its last date of modiĄcation. This can be a global timestamp (for instance, preceded by a ŞLast modiĄedŤ string, in the footer of a Web page) or a set of timestamps for individual items in the page, such as news stories, blog posts, comments, etc. In the latter case, the global timestamp might be computed as the maximum of the set of individual timestamps. It is actually quite easy to extract and recognize such information, with keyword selection (last, modification, date, etc.) or with entity recognizers for dates (built out of simple regular expressions). However, this timestamp is often quite informal and partial: there is sometimes no time indication, and most of the time no timezone. To the best of our knowledge, no formal study of the precision reached by extracting timestamps from Web content has been carried out.

Semantic temporal associations

In addition to these timestamps provided to humans, documents on the Web may include additional semantic timestamps meant for machines. No mechanism for this exists in HTML per se, but the HTML speciĄcation [START_REF]W3C. HTML 4.01 speciĄcation[END_REF] allows for arbitrary metadata in the form of <meta> tags, one particular proĄle of such metadata being Dublin Core 4 whose modified term indicates the date of last modiĄcation of a Web page. Both content management systems and Web authors occasionally use this possibility. Web feeds (in RSS or Atom formats) also have semantic timestamps, which are quite reliable, since they are essential to the working of applications that exploit them, such as feed readers. In some cases, external semantic content can be used for dating an HTML Web page: for instance, an RSS feed containing blog entries can be mapped to the corresponding Web page, in order to date individual items [START_REF] Oita | Archiving data objects using web feeds[END_REF]. Another case is that of sitemaps [START_REF]Sitemaps XML format[END_REF]. Sitemaps are Ąles that can by provided by the owner of a Web site to describe its organization, so as to improve its indexing by Web search engines. Sitemaps allow for both timestamps and change rate indications (hourly, monthly, etc.), but these features are not often used. Very few content management systems produce all of this, although it would have been the ideal case: the download of a single Ąle would suice to get all timestamping information about the whole Web site.

Using the neighborhood

It is possible to use the graph structure of the Web to help timestamping Web pages: [START_REF] Nunes | Using neighbors to date Web documents[END_REF] uses the neighboring pages of a Web page to estimate its timestamp. When no source of reliable timestamps is found for a given page using one of the technique described above, its timestamp is set to some form of average of the timestamps of pages pointed to and by this page. The inherent assumption is that pages linked together tend to have a similar update patterns. The precision is not very high, but better than nothing when no other information is available.

DYNAMIC METHODS

When static techniques do not give adequate results, there is still the possibility of comparing a Web page with its previous version in order to determine (sometimes in a rough way) an equivalent of Last-Modified. The timestamp that gives the last modiĄcation of a Web page can be inferred then as the date when change has been detected.

Nevertheless, for a precise estimation, a just-in-time crawl of versions is needed. In reality, the frequency of change is quite diicult to estimate because Web pages have diferent patterns of change. In general, many factors determine variations in the frequency of change for a given Web page: the CMS, the subject, the time of the year, even the time of the day, etc.

Estimating the Web pagesŠ frequency of change is the subject of many studies [START_REF] Fetterly | A large-scale study of the evolution of Web pages[END_REF][START_REF] Adar | The Web changes everything: Understanding the dynamics of Web content[END_REF][START_REF] Ntoulas | WhatŠs new on the Web? The evolution of the Web from a search engine perspective[END_REF][START_REF] Cho | The evolution of the Web and implications for an incremental crawler[END_REF][START_REF] Jatowt | Detecting age of page content[END_REF]. Their results are however heavily dependent on the technique of detecting change that they have used.

There are two parameters that inĆuence the process of determining the dynamics:

1. the frequency of change is not known in advance, but if we do not crawl the Web pages on time, we miss versions and the timestamp detected will be then imprecise;

2. the change detection technique, which heavily relies on the similarity metrics and on the model (that can capture more or less types of changes) and the Ąltering of dynamic elements that inĆuence the frequency without being truly relevant (and which occur quite often in Web pages because of AJAX applications or advertisements).

A method of Ąltering irrelevant content is to know what is important rather than trying to Ąlter what is unimportant. If we knew in advance the frequency of crawl, then we would know when change occurs and therefore set timestamps for new versions. This is unfortunately not the case, but we need however to crawl frequently enough (better too frequently than not frequent enough). Once we have these versions, we can detect if there is any change that happened in the interval of time that represents the interval of crawl. Based on this, timestamps can be derived with good approximation.

The majority of works consider that they have an access to the versions and they focus on detecting change eiciently. Few make a semantic distinction between changes by disregarding insigniĄcant ones. Next, we present some general notions about changes: what kind of changes can occur in Web pages, which have been identiĄed in our studied approaches and which have not, and Ąnally we give an insight into how change is actually represented.

Types of changes

We summarize here the types of changes detected by diferent approaches. There are however other, more sophisticated types that are sometimes mentioned, but not treated. For instance, behavioral changes are mentioned in [START_REF] Yadav | Change detection in Web pages[END_REF]; they occur in active HTML elements like scripts, embedded applications and multimedia. These new forms of Web content have a big impact on the Web today, but they require a more complex modeling.

All considered approaches detect changes in content.

Works that model the HTML page as a tree, including page digest encoding, usually detect also structural and attribute changes. However, diferences exist in the coverage of cases for these types of changes. For example, MH-Dif [START_REF] Chawathe | Meaningful change detection in structured data[END_REF] detects also move and copy structural changes, which is an improvement over the traditional detection of insert, delete and update. Structural (or layout) changes occur when the position of elements in the page is modiĄed. Attribute (or presentation) changes are related to the representation of information, for instance changes in the font, colors or captions. For capturing structural and attribute changes, the model has to be aware their existence; this implies a more complex model which inĆuences generally in a negatice manner the performance. Unlike Ćat-Ąle models of Web pages, the output of content change detection in hierarchical models is more meaningful: the type of node in which the content change occured can also be identiĄed.

There are also type changes, that are modiĄcations which come about when the HTML tags change: e.g., a p tag which becomes a div. Type changes can be detected by [START_REF] Rocco | Page digest for large-scale Web services[END_REF] which uses the page digest encoding that provides a mechanism for locating nodes of a particular type (see further).

Semantic types of change capture the meaning of content that has changed. They are deĄned in SCD [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF], a pioneer work in this direction.

Changes are sometimes captured in a quantitative manner rather than in a qualitative one. In contrast with the qualitative way, where the change is described (in a delta Ąle) or visualized in a comparative manner, quantitative approaches estimate the amount of change of a speciĄc type. More speciĄcally, all approaches that use the similarity formula deĄned in CMW [START_REF] Flesca | Eicient and efective Web page change detection[END_REF] do not reconstruct the complete sequence of changes, but give a numerical value of it. In this case, supposing a threshold of change, we can determine if a page has changed or not, which actually represent more an oracle response, still useful in the majority of applications.

The representation of change

There are various ways to present the diference between two documents. Changes are usually stored in a physical structure generically called delta file or delta tree. The format of storing the change for RMS [START_REF] Yadav | Change detection in Web pages[END_REF] consists in specialized set of arrays that capture the relationships among the nodes and the changes that occur both in structure and content. Systems for monitoring change like [START_REF] Liu | WebCQ: Detecting and delivering information changes on the Web[END_REF][START_REF] Jacob | WebVigiL: An approach to just-in-time information propagation in large network-centric environments[END_REF] have typically a user interface and present changes in a graphical way. HTMLdiff merge the input Web page versions into one document that will summarize all the common parts and also the changed ones. The advantage is that the common parts are displayed just once, but on the other hand, the resulting merged HTML can be syntactically or semantically incorrect. Another choice linked to change presentation is to display only the diferences and omit the common parts of the two Web pages. When the documents have a lot of data in common, presenting only the diferences could be better, with the drawback that the context is missing. The last approach is to present the diferences between the old and new version side by side.

These presentation modes are used in combination, rather than being the unique choice for a given system. For example, [START_REF] Liu | WebCQ: Detecting and delivering information changes on the Web[END_REF][START_REF] Jacob | WebVigiL: An approach to just-in-time information propagation in large network-centric environments[END_REF] are presenting the results of the change monitoring service using a hybrid approach: presentation modes are combined depening on the type of change that is presented.

HTML DOCUMENT MODELS

This section contains an overview of the models that are considered in the quest of detecting changes in Web documents. The modeling step is a key one as it will determine the elements on which the comparison algorithms operate.

We Ąrst discuss the ŞnaïveŤ approach, that is, to consider Web pages as Ćat Ąles (strings); then we describe tree models, a popular choice in the literature. We explore also some approaches that are based on tree models, but which are essentially transforming the two versions to be compared in a bipartite graph on which speciĄc algorithms are applied. Finally, we present the Page Digest design of Web pages, a manner of encoding that clearly separates structural elements of Web documents from their content, while remaining highly compact.

Flat-files

Some early change detection systems model Web pages as Ćat Ąles [START_REF] Douglis | The AT&T Internet diference engine: Tracking and viewing changes on the Web[END_REF]. As these models do not take into account the hierarchical structure of HTML documents and neither the characteristics of the layout, they can detect only content changes Ű and this without making any semantic diference in the content.

Some works [START_REF] Sigurðsson | Incremental crawling with Heritrix[END_REF] try to Ąlter Ąrst irrelevant content by using heuristics on the type of content and regular expressions. After this basic Ąltering, the Web page content is direcly hashed and compared between versions. Unfortunately, we can never Ąlter all kind of inconvenient content, especially when its manner of encoding or type get more complex.

Trees

A natural approach is to represent a Web page as a tree using the DOM model. By taking into account the hierarchies, structural and attribute changes can be detected besides content changes.

Diferences between tree models appear in their ordered characteristics and in the level of granularity on which change is detected: node, branch, subtree or ŞobjectŤ. We will further discuss these aspects.

First, the modeling of a Web page into a tree requires a preprocessing step of cleaning. This is a signiĄcant one because it corrects missing or mismatching, out-of-order end tags, as well as all other syntactic ill-formedness of the HTML document. A tree is constructed Ąrst by Ąltering the Ştag soupŤ HTML into an XML document and second, by manipulating the result in order to obtain a workable tree structure using implementations of the DOM standard (that usually employ XSLT and XPath). Sometimes also an initial pruning of elements is done: [START_REF] Khoury | An eicient Web page change detection system based on an optimized Hungarian algorithm[END_REF] is Ąltering out scripts, applets, embedded objects and comments.

Many works do not specify how they realize the cleaning, so either they assume it to be done in advance, or they solve this issue by using an HTML cleaning tool. HTML Tidy5 is well-suited for this purpose and mentioned in [START_REF] Artail | A fast HTML Web change detection approach based on hashing and reducing the number of similarity computations[END_REF].

There are however cases [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF] when the tree model does not need to be cleaned: as the semantics of tags (value, name) is leveraged in the technique, the structure does not have to be enforced.

Ordered trees.

The ordered characteristic of trees implies that the order of appearance of nodes is considered in the algorithm and therefore included in the model.

RMS algorithm [START_REF] Yadav | Change detection in Web pages[END_REF] stores the level (depth) of a node, information which will be used in the tree traversal and parsing. The SCD [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF] algorithm uses branches of ordered trees to detect semantic changes. The notion of branch is used to give the context of a node and is formalized as an ordered multiset, in which the elements are designated by the tag name of the HTML non-leaf node, or its content (text), if it represents a leaf node. The order is very important in this model because of the data hierarchy considered (e.g., book.author.name.Eminescu vs. a markup hierarchy like div.p.b.PCDATA). In this model, if we change the order, we change the semantics of hierarchies or this semantics becomes incoherent.

Ordered tree model is also used in [START_REF] Khandagale | A novel approach for web page change detection system[END_REF].

Unordered trees.

The unordered labeled tree model does not consider the order of appearance of elements in the tree as relevant, instead only the parent-child relationships are captured.

It is mentioned in MHDif [START_REF] Chawathe | Meaningful change detection in structured data[END_REF] that the change detection problem for unordered trees is harder that for ordered ones. Like [START_REF] Flesca | Eicient and efective Web page change detection[END_REF][START_REF] Chawathe | Meaningful change detection in structured data[END_REF], [START_REF] Khoury | An eicient Web page change detection system based on an optimized Hungarian algorithm[END_REF] constructs a weighted bipartite graph from the two trees given as entry. In these models, the order has not an importance on the Ąnal structure for which further processing will be done, therefore this feature is not captured.

[3] delimits and encodes subtrees; these are generated by analyzing the level of a node in the unordered tree. From the root, when we arrive at level % 3, a subtree is created; the node at (level % 3 + 1) becomes the local root of the following subtree, and this iteratively until the end of the hierarchy. Each subtree is marked with the tag name of its local root and indexed based on its start and end node identiĄers. A hashtable will Ąnally map metadata about nodes (like tag name, content, path to the root, attributes pair values, etc.).

Bipartite graph

The bipartite graph model is a model derived from unordered trees: it consists in two independent sets (acquired after tree pruning), each corresponding to a version, that are connected by cost edges. As set elements, subtrees are chosen over nodes in [START_REF] Khoury | An eicient Web page change detection system based on an optimized Hungarian algorithm[END_REF][START_REF] Flesca | Eicient and efective Web page change detection[END_REF]. The assumption [START_REF] Flesca | Eicient and efective Web page change detection[END_REF] is that we might be more interested in which subtree the change occurs, than in which speciĄc node.

The cost of an edge represent the cost of the edit scripting needed to make a model entity (node or subtree) of the Ąrst set isomorphic with one of the second set. The similarities between all subtrees in the Ąrst tree and all those of the second tree are computed and placed in a cost matrix. Having this matrix, the Hungarian [START_REF] Bertsekas | Parallel asynchronous Hungarian methods for the assignment problem[END_REF] algorithm is used to Ąnd in polynomial time a minimum-cost bijection between the two partitions. This algorithm is typically used in linear programming to Ąnd the optimal solution to the assignment problem.

CMW [START_REF] Flesca | Eicient and efective Web page change detection[END_REF] as well as MH-Dif [START_REF] Chawathe | Meaningful change detection in structured data[END_REF] algorithm, are based on transforming the change detection problem in one of computing a minimum cost edge cover on a bipartite graph. Optimizations are brought out in [START_REF] Khoury | An eicient Web page change detection system based on an optimized Hungarian algorithm[END_REF] in comparison with the work in [START_REF] Bertsekas | Parallel asynchronous Hungarian methods for the assignment problem[END_REF], but the general aim and similarity metrics remain the same as in [START_REF] Artail | A fast HTML Web change detection approach based on hashing and reducing the number of similarity computations[END_REF].

Page Digest

The page digest model6 has been adopted in [START_REF] Rocco | Page digest for large-scale Web services[END_REF] and [START_REF] Yadav | Change detection in Web pages[END_REF], and represents a more compact encoding of data than HTML and XML formats, while preserving all their advantages. To construct this model, some steps are performed: counting the nodes, enumerating children in a depth-Ąrst manner (in order to capture the structure of the document), and content encoding and mapping for each node -encoding which will preserve the natural order of text in the Web page.

SDif [START_REF] Rocco | Page digest for large-scale Web services[END_REF] is a Web change monitoring application that uses a digest format that includes also tag type and attribute information. RMS [START_REF] Yadav | Change detection in Web pages[END_REF] also uses this model, although without giving many details. The advantages of the Page Digest over the DOM tree model are enumerated in [START_REF] Rocco | Page digest for large-scale Web services[END_REF]. We mention minimality and execution performance: the reduction of tag redundancy gives a more compact model, therefore a faster document traversal. The algorithms developed on this model run in linear time without making too many heuristics or restrictions, while capturing also a large palette of changes.

SIMILARITY METRICS

Similarity metrics are used in dynamic methods of detecting change, in the matching stage of the two versions modelled as described in section 4.

For string models, (content) change is identiĄed when the data strings are discovered to be partially unsimilar. For tree models that have various dimensions, the problem gets more complex.

The aim is to identify model elements that are essentially the same, but which have been afected by change. Model elements that are the identical are pruned because they have basically not changed between versions; also, totally dissimilar model elements do not represent instances of the object that has evolved, so will not be included in further processing steps. Essentially, only approximatively similar model elements will be further studied. A typical matching is based on comparisons of attribute values of the model elements. If they have the same properties, then they are similar.

We will describe next the types of similarity metrics used for change detection in diferent settings or applications, for the studied cases.

String matching techniques

Approaches that compare two Web pages modeled as Ćat Ąles (i.e. strings), rely on hash-based methods, edit distance metrics or techniques based on the longest common subsequence. We do not exhaustively cover all the possiblities, but rather present some of them that we have encountered in the analyzed works.

Naïve: Jaccard.

One simple technique for change detection in text is to count the number of words that are common (regardless of their position) for two string sequences and to divide the result by the number of distinct words. Another possiblity is to divide by the length of the Ąrst string, as done in [START_REF] Pehlivan | A novel Web archiving approach based on visual pages analysis[END_REF].

Hash-based methods.

In this category, we mention [START_REF] Broder | On the resemblance and containment of documents[END_REF][START_REF] Khandagale | A novel approach for web page change detection system[END_REF][START_REF] Artail | A fast HTML Web change detection approach based on hashing and reducing the number of similarity computations[END_REF]. The method of [START_REF] Broder | On the resemblance and containment of documents[END_REF] uses shingling, which is a Ćexible method of detecting changes between two strings. It is usually referred to as w-shingling, where w the denotes the number of tokens in each shingle in the set. A shingle is a contiguous subsequence (w-gram) of the reference string. For the two strings to be compared, their shingles are hashed; if these strings have a lot of shingle values in common, then they are similar.

Another method is to use signatures. A signature of a string is a function of its hashed value. When the model is hierarchical, the signature of a node is computed based on its terminal path. For a formatting (or non-leaf) node, the signature represents the sum of the signatures of its children, until leaf nodes, where changes are actually detected. In [START_REF] Khandagale | A novel approach for web page change detection system[END_REF], only nodes that have diferent signatures from those in the original version will be compared. Change detection algorithms that employ signatures have the disadvantage that false negatives are possible: change exists, but a diferent signature for it does not. It obviously depends on the careful choice of the space of hashing, and eventually on the application: if it can tolerate or not false results.

Another hash-based approach is presented in [START_REF] Artail | A fast HTML Web change detection approach based on hashing and reducing the number of similarity computations[END_REF], where the change is detected at atomic element level using a direct hash.

Longest common subsequence.

A diff is a Ąle comparison program that outputs the diferences between two Ąles. Dif tools are based on computing the longest common subsequence between two strings [START_REF] Sahinalp | Hardness of string similarity search and other indexing problems[END_REF]. For instance, HTMLDiff uses GNU dif utility adapted for HTML page change detection. This program treats Web pages as strings and, after processing, highlights the changes directly in a merged document; as mentioned in [START_REF] Douglis | The AT&T Internet diference engine: Tracking and viewing changes on the Web[END_REF], HTMLDiff can consume signiĄcant memory and computation resources, and this might have an inĆuence on the scalability of the tool. Tree models of Web pages also use dif techniques, but not at HTML page level, but at subtree (or node) content level, which has the advantage of making the computation less complex. For instance, WebCQ [START_REF] Liu | WebCQ: Detecting and delivering information changes on the Web[END_REF] uses HTMLDiff to detect change at object level. Here, the object represents in fact a part of a Web page speciĄed for monitoring by the user, either by means of regular expressions or by marking elements of the HTML DOM tree like a table, list, link etc.. Another example of system that uses GNU dif tool is WebVigiL [START_REF] Jacob | WebVigiL: An approach to just-in-time information propagation in large network-centric environments[END_REF].

Edit scripting on strings.

The edit distance between two strings of characters represents the number of operations required to transform one string into another. There are diferent ways of deĄning an edit distance, depending on which edit operations are allowed: delete, insert, etc.. In string edit scripting, the atomic element is a single character and the cost is usually unitary, for every edit operation deĄned.

Root Mean Square.

Another notable way [START_REF] Yadav | Change detection in Web pages[END_REF] of compute similarity is to use RMS(Root Mean Square) value, i.e., the quadratic mean. RMS represents a statistical measure for the magnitude of a varying quantity and permits therefore to quantify the change. If its value is small, then the diference between the compared elements is not signiĄcative. Often used in engineering to do an estimation of the similarity between a canonical model and an empirical one (in order to see the precision of the experiment), RMS formula needs numeric values of the model parameters. In the HTML context, ASCII values of the Web documentŠs text characters are utilized in the canonical formula. Although a good idea, RMS measure applied for the ASCII values of each character has some drawbacks: Ąrst it does not take into account the hierarchies (it considers that every character has equal inĆuence, independently of its position in the page), and second, it cannot take into account the semantics of context. Variants of this measure are presented in [START_REF] Yadav | Parallel crawler architecture and web page change detection[END_REF].

Matching of hierarchical models

Edit scripting on trees.

has the same formal deĄnition as for strings, excepting for the fact that the basic entities are here tree elements (nodes or subtrees). Also, edit operations can occur at diferent levels, depending on the types of changes considered. As a consequence, cost models of edit operations become more complex. Each edit operation has a cost associated (cost proportional to the complexity of the operation, or based on heuristics of the model), so the execution of an edit script as a sequence of operations will return a cumulated cost. The similarity measure can be then computed as the inverse of this total cost. The interpretation is the following: less unimportant modiĄcations we do to the Ąrst structure of data in order to make it isomorphic with its version, the more similar the two structures are.

This problem of determining the distance between two trees is referred to as the tree-to-tree correction problem and this is more in depth covered in [START_REF] Barnard | Tree-to-tree correction for document trees[END_REF]. Some works [START_REF] Chawathe | Meaningful change detection in structured data[END_REF] report that edit scripting with moving operations is NPhard. Usually, every model introduces some kind of model or computational heuristics that make the problem (a little) less diicult. As an example, [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF] computes an edit scripting on branches. It can be also done on subtrees, rather than on complete trees, for the same complexity reasons. Concerning the cost of change operations, every technique makes its own decisions. MH-Dif [START_REF] Chawathe | Meaningful change detection in structured data[END_REF] for example deĄnes the costs as being moderated by some constants, all depending on the type of change.

Quantitative measures of change.

Various works [START_REF] Flesca | Eicient and efective Web page change detection[END_REF][START_REF] Artail | A fast HTML Web change detection approach based on hashing and reducing the number of similarity computations[END_REF][START_REF] Khoury | An eicient Web page change detection system based on an optimized Hungarian algorithm[END_REF] use a composed measure of similarity that tries to better adapt to the speciĄc of the types of changes considered. The change is measured by a formula that incorporates three sub-measures of speciĄc similarity: on the content (intersect: the percentage of words that appear in both textual content of subtrees), attributes (attdist: the relative weight of the attributes that have the same value in the model elements) and on the types of elements considered in the path (typedist emphasizes diferences on the tag names when going up in the hierarchy). The Ąnal measure incorporates all above-deĄned types of similarity, together with some parameters that are meant to inĆuence the importance of certain types of changes over others. The advantage of this measure is that it captures the symbiosis of diferent types of changes that occur in a certain way independently: content changes in leaf nodes, attribute changes in internal nodes; the third submeasure is more focused on the position of nodes in the structure.

Another quantitative measure of change is proposed in [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF]. Here, a weighted measure that determines the magnitude of the diference between two ordered multisets (i.e., branches) is employed. In an ordered multiset, the weight of the ith node is deĄned as (2 i ) -1 (where i represents the depth of an element of the branch considered). Finally, the quantity of change is measured by computing the sum of the weights of the nodes that appear in the symmetric diference set.

STATISTICALLY ESTIMATING CHANGE

Motivating estimative models

We have seen the multitude of domains that are interested in the change detection issue. The general aim is to get an idea about the dynamics of a certain type of content, at a given granularity.

In Web crawler-related applications, the interest is more in whether a Web page has changed or not, in order to know if a new version of a Web page shall be downloaded or not. Only a binary response is needed; this does not happen because it is not interesting to make a distinction between the diferent types of changes that can occur, but because current crawlers treat information at Web page level. In this case, an estimation of the change frequency is as efective as explicitly computing it, as we show in Section 3. Indeed, if archive crawlers were more aware of the semantics of data they process, they could clearly beneĄt of a broader, richer insight into the data and could develop diferent strategies related to storage and processing. An estimation of the change rate, although not very descriptive (we usually do not know where the change appeared or its type), is still useful, especially when we can imagine a strategy that combines estimative and comparative methods of deriving dynamics. For this reason, we shortly present some of the existing statistical approaches.

Poisson model

The study carried out in [START_REF] Cho | The evolution of the Web and implications for an incremental crawler[END_REF] reports the fact that changes that occur in Web pages can be modeled as a Poisson process. A Poisson process is used to model a sequence of random events that happen independently with a Ąxed rate over time. Based on a(n ideally complete) change history, the frequency of change is estimated. The time-independence assumption in homogeneous models [START_REF] Cho | The evolution of the Web and implications for an incremental crawler[END_REF][START_REF] Cho | Estimating frequency of change[END_REF] does not really capture the reality of the Web. The authors of [START_REF] Sia | Eicient monitoring algorithm for fast news alerts[END_REF] airm that in the case of dynamic Web content (like blogs), the posting rates vary very much depending on diferent parameters. Hence, they propose an inhomogeneous Poisson model (which do not assume that events happen independently); this model learns the posting patterns of Web pages and predicts a recheck for new content.

The work in [START_REF] Cho | Estimating frequency of change[END_REF] formalizes some use cases where, by adapting the parameters of the Poisson model to the requirements of the application, a better accuracy of the estimation can be achieved. The situation when we do not have a complete change history of a Web page is treated, which is actually the real world case. Sometimes, we have only the last date of change or we at best just know that a change has occurred. Contributions are also related to the fact that the authors adapt the canonical model to interesting applications and feed diferent estimators, improving thus the technique for the considered cases.

Kalman filters

Other statistical approach to change detection is that of [START_REF] Bogen | Application of Kalman Ąlters to identify unexpected change in blogs[END_REF]. Here, the textual vector space model is employed to identify the patterns of the page and to train Kalman Ąlters with these patterns. In the end, the change represents the event that does not match the The possible disadvantages of this method is that it assumes the linearity of the system (because of the the Kalman Ąlter model, which is doing an exact inference in a linear dynamical system) and uses an incomplete vector space model (for complexity reasons).

OPEN QUESTIONS

We end this article by discussing several issues that have not been addressed yet and which are related to the deriv-ing of temporal properties of Web pages. The selection of subjects reĆects our personal vision on the topic.

Further studies on timestamping.

With the large number of sources of timestamping hints, it should indeed be possible to estimate the freshness of a Web page. An experimental study on the reliability of these sources, perhaps in speciĄc contexts (a given Web server software, a given CMS, etc.), which could provide more insight into optimal strategies for timestamping Web pages, is still to be carried out.

Relevant change detection.

An important question when detecting changes is whether the changes are relevant to the interests or needs of the user or archivist. Web users are exposed to many advertisements and content becomes pre-fabricated, put in containers and delivered in a targeted way, so much more attention should be paid to the relevance factor. Additionally, Web pages have some components that are more dynamic than others; it is not possible to say if the dynamics come from irrelevant content (think of ads changing at every request) or precisely because the content is very informative (e.g. frequently updated news). To make the distinction between these, techniques that deĄne and extract semantics (e.g., by looking at the topic and linked data) might be used as a Ąltering method or just for adding more signiĄcance to the change detection results. The cleaning of the Web page or its segmentation into semantic blocks is of interest in many information extraction Ąelds and, although we mention only [START_REF] Yu | Improving pseudo-relevance feedback in Web information retrieval using Web page segmentation[END_REF][START_REF] Kholschutter | Boilerplate detection using shallow text features[END_REF][START_REF] Oita | Archiving data objects using web feeds[END_REF], there exists a large number of works that treat this subject.

As an observation, there exists a subtle diference in the use of the term ŞmeaningfulŤ in the various works that we have studied. While some works [START_REF] Lim | An automated change-detection algorithm for HTML documents based on semantic hierarchies[END_REF] use it to emphasize the fact that more types of changes are detected, other approaches [START_REF] Pehlivan | A novel Web archiving approach based on visual pages analysis[END_REF] use it as synonym to ŞrelevantŤ, from the content point of view. Vi-Dif [START_REF] Pehlivan | A novel Web archiving approach based on visual pages analysis[END_REF] uses the VIPS algorithm [START_REF] Yu | Improving pseudo-relevance feedback in Web information retrieval using Web page segmentation[END_REF] to get from a Web page an hierarchy of semantic blocks and detect changes only from this perspective, hopefully ignoring all boilerplate content. However, a deeper insight into the relevance aspect is mentioned as future work; the authors of [START_REF] Pehlivan | A novel Web archiving approach based on visual pages analysis[END_REF] talk about using machine learning techniques for this issue, which would be an interesting line of research. Usually, heuristics [START_REF] Yu | Improving pseudo-relevance feedback in Web information retrieval using Web page segmentation[END_REF] are employed to get a measure of relevance because having a generic source of knowledge which can be automatically used for this task is very diicult.

Recently, [START_REF] Oita | Archiving data objects using web feeds[END_REF] used the concepts that can be extracted from the description of Web feeds to get the content of interest from Web pages. However, this kind of semantics can only be obtained in the case of Web pages that have feeds associated.

With the emergence of the Semantic Web, we envision new ways of distinguishing timestamps or of Ąltering irrelevant content from Web pages and therefore more eicient methods for deriving dynamics of Web pages.

Figure 1 :

 1 Figure 1: Summary of the presented approaches

Examples of these include http://timelyweb.en. softonic.com/, http://www.urlywarning.net/, http:// www.changealarm.com/, http://www.changedetect.com/.

http://www.mediawiki.org/

http://www.apache.org/

http://dublincore.org/documents/dcmi-terms/

http://tidy.sourceforge.net/

http://www.cc.gatech.edu/projects/disl/ PageDigest/

* This research was funded by the European Research Council grant Webdam FP7-ICT-226513.


Ricardo J Alonso
email: ralonso@math.utexas.edu

Bertrand Lods
email: bertrand.lods@math.univ-bpclermont.fr

D I Dipartimento

Statistica

Matematica Applicata

Carlo Collegio

Alberto

TWO PROOFS OF HAFF'S LAW FOR DISSIPATIVE GASES: THE USE OF ENTROPY AND THE WEAKLY INELASTIC REGIME

Keywords: Boltzmann equation, inelastic hard spheres, granular gas, cooling rate, Haff's law. AMS SUBJECT CLASSIFICATION: 76P05, 76P05, 47G10, 82B40, 35Q70, 35Q82

 and give two simpler proofs of the socalled Haff's law for granular gases (with non-necessarily constant restitution coefficient). The first proof is based upon the use of entropy and asserts that Haff's law holds whenever the initial datum is of finite entropy. The second proof uses only the moments of the solutions and holds in some weakly inelasticity regime which has to be clearly defined whenever the restitution coefficient is non-constant.

INTRODUCTION

The main objective of the present paper is to revisit our recent contribution [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] and give two simpler proofs of the so-called Haff's law for granular gases (with non-necessarily constant restitution coefficient). The first proof is based upon the use of Boltzmann's entropy and asserts that Haff's law holds whenever the initial datum is of finite entropy. The second proof uses only the moments of the solutions and shows that Haff's law holds in some weakly inelasticity regime (see Theorem 1.9 for a precise definition in the case of non-constant restitution coefficient) for initial datum with finite energy.

1.1. Motivation. We consider in this paper freely cooling granular gases governed by the spatially homogeneous Boltzmann equation

∂ t f (t, v) = Q e (f, f )(t, v) t > 0, v ∈ R 3 f (0, v) = f 0 (v), v ∈ R 3 (1.1)
where the initial datum f 0 is a nonnegative velocity distribution such that

R 3 f 0 (v) dv = 1, R 3 f 0 (v)v dv = 0 and R 3 f 0 (v)|v| 2 dv < ∞. (1.2)
The operator Q e (f, f ) is the inelastic Boltzmann collision operator, expressing the effect of binary collisions of particles. We assume here that the granular particles are perfectly smooth hard-spheres of mass m = 1. The inelasticity of the collision mechanism is characterized by a single scalar parameter known as the coefficient of normal restitution 0 e 1. Indeed, if v and v ⋆ denote the velocities of two particles before they collide, their respective velocities v ′ and v ′ ⋆ after collisions are such that

(u ′ • n) = -(u • n) e, (1.3)
where n ∈ S 2 determines the impact direction, i.e. n stands for the unit vector that points from the v-particle center to the v ⋆ -particle center at the instant of impact. Here above

u = v -v ⋆ and u ′ = v ′ -v ′ ⋆ ,
R. Alonso acknowledges the support from NSF grant DMS-0439872 and ONR grant N000140910290.

denote respectively the relative velocity before and after collision. In this work, the restitution coefficient e is assumed to be a function of the impact velocity, i.e.

e := e(|u • n|).

In virtue of (1.3) and the conservation of momentum, the post-collision velocities (v ′ , v ′ ⋆ ) are given by

v ′ = v - 1 + e 2 (u • n) n, v ′ ⋆ = v ⋆ + 1 + e 2 (u • n) n.
(1.4)

The main assumptions on the function e(•) are listed here after (see Proposition 1.1) and ensure that the Jacobian of the above transformation (1.4) is given by

J e (|u • n|) = ∂v ′ ∂v ′ ⋆ ∂v∂v ⋆ = e(|u • n|) + |u • n|e ′ (|u • n|) =: ϑ ′ e (|u • n|)
where e ′ (•) and ϑ ′ e (•) denote the derivative of r → e(r) and r → ϑ e (r) respectively (this prime symbol should not be confused with the one we have chosen for the post-collisional velocity). We refer the reader to [START_REF] Alonso | Existence of global solutions to the Cauchy problem for the inelastic Boltzmann equation with near-vacuum data[END_REF] for more details. The main examples of restitution coefficient we shall deal within this paper are the following:

(1) The first fundamental example is the one of a constant restitution coefficient for which e(r) = e ∈ (0, 1] for any r 0.

(2) The most physically relevant variable restitution coefficient is the one corresponding to the so-called viscoelastic hard-spheres [START_REF] Brilliantov | Kinetic theory of granular gases[END_REF]. For such a model, the properties of the restitution coefficient have been derived in [START_REF] Brilliantov | Kinetic theory of granular gases[END_REF][START_REF] Schwager | Coefficient of normal restitution of viscous particles and cooling rate of granular gases[END_REF] and it can be shown that e(z) is defined implicitly by the following e(r) + ar 1/5 e(r) 3/5 = 1 ∀r 0

where a > 0 is a suitable positive constant depending on the material viscosity.

With the above notations, the Boltzmann collision operator is given, in weak form, by the following equation

R 3 Q e (f, f )ψ(v) dv = 1 2π R 3 ×R 3 ×S 2 |u • n|f (v)f (v ⋆ ) ψ(v ′ ) + ψ(v ′ ⋆ ) -ψ(v) -ψ(v ⋆ ) dv dv ⋆ d n (1.6)
for any smooth test-function ψ(v). The strong form of Q e can be recovered easily (see [START_REF] Alonso | Existence of global solutions to the Cauchy problem for the inelastic Boltzmann equation with near-vacuum data[END_REF]).

Notice that an alternative parametrization of the post-collision velocities (1.4) would lead to a slighty different weak formulation of the collision operator (this alternative formulation was preferred in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF]).

As explained in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF], in absence of any heating source, the granular temperature

E(t) = R 3 f (t, v)|v| 2 dv, t 0
is continuously decreasing and tending to zero as time goes to infinity, expressing the cooling of the granular gases. The precise cooling rate of the temperature is the main concern of this note. It was proven in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF], and predicted by the physics literature long ago, that the cooling rate is strongly depending on the choice of the restitution coefficient. Note that using the weak form (1.6) with the test function ψ(v) = |v| 2 , the evolution of E(t) is governed by the following relation

d dt E(t) = - R 3 ×R 3 f (t, v)f (t, v ⋆ )Ψ e (|u| 2 ) dv dv ⋆ , (1.7)
where the dissipation energy potential associated to e(•) is given by

Ψ e (r) = r 3/2 2 1 0 1 -e 2 ( √ rz) z 3 dz r > 0. (1.8)
We refer to [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] for technical details. In the op. cit. we introduced the following general assumptions:

Assumptions 1.1. The restitution coefficient e(•) is such that the following hold:

(1) The mapping r ∈ R + → e(r) ∈ (0, 1] is absolutely continuous.

(2) The mapping r ∈ R + → ϑ(r) := r e(r) is strictly increasing.

(3) lim sup r→∞ e(r) = e 0 < 1.

(4) The function x > 0 -→ Ψ e (x) defined in (1.8) is strictly increasing and convex over (0, +∞).

These assumptions are fulfilled by the two examples described above and, more generally, they hold whenever the restitution coefficient r → e(r) is an absolutely continuous and non-increasing mapping (see [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF]Appendix]). Notice that the first two assumptions are exactly those needed in order to compute the Jacobian of the transformation (1.4). The last two are needed in order to get the following proposition which is based on Jensen's inequality. and, as a consequence, lim t→∞ E(t) = 0. Moreover, if one assumes that there exist α > 0 and γ 0 such that e(z) ≃ 1 -α z γ for z ≃ 0 (1.9)

then there exist C > 0 and t 0 > 0 such that

E(t) C (1 + t) -2 1+γ ∀t t 0 .
Remark 1.3. The well-posedness of the Cauchy problem (1.1) has been proved in [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part I: The Cauchy problem[END_REF].

Remark 1.4. Notice that the above assumption (1.9) is equivalent to assume that

ℓ γ (e) = sup r>0 1 -e(r) r γ < ∞ (1.10)
since, for large value of r > 0, (1 -e(r))/r γ is clearly finite for any γ > 0. In particular, for a constant restitution coefficient e(r) = e 0 , one has ℓ 0 (e) = 1 -e 0 which means that (1.10) holds. For the model of viscoelastic hard-spheres given by (1.5), the restitution coefficient e(•) is such that ℓ 1/5 (e) = a. Furthermore, if ℓ γ (e) < ∞ for some γ > 0, then ℓ α (e) = ∞ for any α = γ. Indeed, the parameter γ is exactly the one that prescribes the behavior of e(r) for small values of r.

Proposition 1.2 illustrates the fact that the decay of the temperature is governed by the behavior of the restitution coefficient e(r) for small value of r. Now, in order to match the precise cooling rate of the temperature and prove the so-called generalized Haff's law, one needs to prove that, under Assumptions 1.1 and (1.10), there exists c > 0 such that .11) This was precisely the main objective in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] and, as far as the cooling rate is concerned, the main result of the op. cit. can be formulate as Theorem 1.5. For any initial distribution velocity f 0 0 satisfying the conditions given by (1.2) with f 0 ∈ L p (R 3 ) for some 1 < p < ∞, the solution f (t, v) to the associated Boltzmann equation (1.1) satisfies the generalized Haff's law for variable restitution coefficient e(•) fulfilling Assumptions 1.1 and (1.10):

E(t) c(1 + t) -2 1+γ ∀t 0. ( 1
c(1 + t) -2 1+γ E(t) C(1 + t) -2 1+γ , t 0 (1.12)
where c, C are positive constants.

Remark 1.6. An additional assumption was required in theorem 1.5 on the restitution coefficient e(•), see [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF]Assumption 4.10]. We do not insist on this point since we believe such assumption is only of technical nature and likely unnecessary.

For constant restitution coefficient, Haff's law has been proved in [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part II: Self-similar solution and tail behavior[END_REF]. This approach was generalized in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] leading to Theorem 1.5. The proof is based on the following steps:

(1) The study of the moments of solutions to the Boltzmann equation using a generalization of the Povzner's lemma developed in [START_REF] Bobylev | Moment inequalities and high-energy tails for the Boltzmann equations with inelastic interactions[END_REF]. (2) Precise L p estimates, in the same spirit of [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part II: Self-similar solution and tail behavior[END_REF], of the solution to the Boltzmann equation for 1 < p < ∞.

(3) A study of the problem (1.1) in self-similar variable (that is, for suitable rescaled solutions).

Because of the method of proof, step (2) hereabove, the above result requires strong integrability assumption on the initial density f 0 which has to belong to some L p space with p > 1. The main purpose of this paper is to remove the unphysical assumption

f 0 ∈ L p for some p > 1, (1.13)
and prove that the generalized Haff's law still holds under less restrictive assumptions.

1.2. Main results. We present two independent treatments of the above problem:

(1) We prove that Haff's law still holds if we replace (1.13) by the less restrictive constraint

H(f 0 ) = R 3 f 0 (v) log f 0 (v) dv < ∞
and e(•) satisfying (1.10) for some γ > 0.

(2) Using only finiteness of mass and energy on the initial datum, we prove that Haff's law (4.7) holds true in some weakly inelastic regime defined in the sequel. We notice that for constant restitution coefficient, the proof of Haff's law given in [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part II: Self-similar solution and tail behavior[END_REF] required the assumption f 0 ∈ L p with p > 1. However, it was observed in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] that, for this case, Haff's law holds assuming only that the restitution coefficient is sufficiently close to one. We give a complete proof of this fact in the sequel.

More precisely, the main results of the present paper can be stated in the following theorems.

Theorem For non-constant restitution coefficient, the situation is different and the condition on the restitution coefficient will depend on the initial datum. One can formulate our result as follows (see Theorem 4.4 for a more precise statement).

Theorem 1.9. Let f 0 be a nonnegative velocity distribution satisfying (1.2) and let f (t, v) be the associated solution to the Cauchy problem (1.1). For any γ > 0, there exists some explicit ℓ 0 := ℓ 0 (f 0 , γ) > 0 such that, if the restitution coefficient e(•) satisfies Assumptions 1.1 and (1.10) with ℓ γ (e) < ℓ 0 , then the generalized Haff's law (4.7) hold true.

The proof of Theorem 1.7 is much simpler than the proof of [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] under the assumption (1.13) on the initial datum. In particular, it does not requires the introduction of selfsimilar variables. It is based essentially on the fact that entropy of the solution f (t, v) to (1.1) grows at most logarithmically, namely, there exists K 0 > 0 such that

H(f (t)) K 0 log(1 + t) ∀t 0.
Then, using some estimates which allow to relate the energy E(t) to the entropy, we can deduce from such logarithmic growth that the decreasing of the energy E(t) is at most algebraic, that is, there exists some finite λ > 0 such that inf t 0 (1 + t) λ E(t) > 0. It is known from [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF] (see also Proposition 2.4) that for non-constant restitution coefficient, this is enough to conclude the Haff's law (4.7). The proof of Theorem 1.7 is given in Section 3 (see Theorem 3.9) while several inequalities relating energy and entropy are given in the Appendix.

Concerning Theorems 1.8 and 1.9, their proofs are surprisingly simple and rely only on a careful study of the various moments of the solution to the Cauchy problem (1.1). They will be the object of Section 4.

SOME KNOWN RESULTS

We briefly recall some known estimates on the moments of the solution to the Cauchy problem. In this section, we will assume that the restitution coefficient e(•) satisfies Assumptions 1.1 and that the initial datum f 0 satisfies (1.2). We denote then by f (t, v) the associated solution to the Cauchy problem (1.1). For any t 0 and any p 1 we define

m p (t) := R 3 f (t, v)|v| 2p dv (2.1)
with the convention of notation E(t) = m 1 (t). Then, one has the following proposition, see [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF].

Proposition 2.1. For any real p 1, one has

d dt m p (t) = R 3 Q e (f, f )(t, v)|v| 2p dv -(1 -κ p )m p+1/2 (t) + κ p S p (t), (2.2)
where,

S p (t) = [ p+1 2 ] k=1 p k m k+1/2 (t) m p-k (t) + m k (t) m p-k+1/2 (t) , [ p+1 2 ]
denoting the integer part of p+1 2 and

κ p = sup U ∈S 2 U •σ 0 3 + U • σ 4 p + 1 -U • σ 4 p dσ 2π = 1 0 3 + t 4 p + 1 -t 4 p dt > 0 is an explicit constant such that κ p < 1 for any p > 1.
A simple consequence of the above is the following, [2, Corollary 3.6]: For any p 1, there exists some constant K p > 0 such that

m p (0) < ∞ =⇒ m p (t) K p (1 + t) -2p 1+γ ∀t 0.
Furthermore, since we are dealing with hard spheres, the phenomenon of appearance of moments occurs in the same way as in the classical elastic Boltzmann [START_REF] Desvillettes | Some applications of the method of moments for the homogeneous Boltzmann and Kac equations[END_REF][START_REF] Wennberg | On moments and uniqueness for solutions to the space homogeneous Boltzmann equation[END_REF]. Thus, as soon as E(0) < ∞, the higher moments satisfy sup t t 0 m p (t) < ∞ for any t 0 > 0. In particular, one can rephrase [2, Corollary 3.6].

Proposition 2.2. Let f 0 be a nonnegative velocity distribution satisfying (1.2) and let f (t, v) be the associated solution to the Cauchy problem (1.1) where the variable restitution coefficient satisfies Assumptions 1.1 and (1.9). For any t 0 > 0 and any p 0, there exists

K p > 0 such that m p (t) K p (1 + t) -2p 1+γ ∀t t 0 . (2.3)
Observe that in order to prove that the second part of Haff's law (1.11), it is enough to control m 3+γ

2 (t) in terms of E(t) 3+γ 2 . Indeed, recall that - d dt E(t) = R 3 ×R 3 f (t, v)f (t, v ⋆ )Ψ e (|u| 2 ) dv dv ⋆ ∀t 0.
Since ℓ γ (e) < ∞, one has 1 -e(r) ℓ γ (e)r γ ∀r > 0.

Plugging this estimate in the definition of Ψ e (r 2 ) and using the fact that 1 -e 2 (r) 2(1 -e(r)) for any r > 0, we get that

Ψ e (|u| 2 ) ℓ γ (e)|u| 3+γ 1 0 z 3+γ dz = ℓ γ (e) 4 + γ |u| 3+γ ∀u ∈ R 3 . Since |u| 3+γ 2 2+γ |v| 3+γ + |v ⋆ | 3+γ , one gets - d dt E(t) 2 2+γ ℓ γ (e) 4 + γ R 3 ×R 3 f (t, v)f (t, v ⋆ ) |v| 3+γ + |v ⋆ | 3+γ dv dv ⋆ = 2 3+γ ℓ γ (e) 4 + γ m 3+γ 2 (t).
(2.4)

Therefore, if there exists some constant K > 0 such that

m 3+γ 2 (t) KE(t) 3+γ 2 (t) ∀t t 0 > 0, (2.5)
setting C γ = 2 3+γ K 4+γ ℓ γ (e), we obtain from (2.4) that

- d dt E(t) C γ E(t) 3+γ 2 ∀t t 0 .
A simple integration of this inequality yields implies,

E(t) E(t 0 ) 1 + 1+γ 2 E(t 0 ) 1+γ 2 C γ (t -t 0 ) 2 1+γ ∀t t 0 .
which implies (1.11). An additional simplification in the arguments comes with the following proposition which has already been used implicitly in [START_REF] Alonso | Free cooling and high-energy tails of granular gases with variable restitution coefficient[END_REF]. We give a complete proof of it for the sake of clarity. Proposition 2.3. Assume that the restitution coefficient e(•) satisfy Assumptions 1.1 and is such that ℓ γ (e) < ∞ for some γ 0. Assume that there exists some constant C > 0 such that

m 3 2 (t) CE(t) 3 2 (t) ∀t t 0 > 0. (2.6)
Then, for any p 3/2, there exists a constant K p > 0 such that

m p (t) K p E(t) p ∀t t 0 . (2.7)
In particular, the generalized Haff's law (4.7) holds.

Proof. Let t 0 > 0 be fixed. First observe that using classical interpolation, it suffices to prove the result for any p 3/2 such that 2p ∈ N. Argue by induction assuming that for any integer j such that 2j ∈ N, and 1 j p -1/2 there exists K j > 0 such that m j (t) K j E(t) j for t t 0 .

Recall that, according to Proposition 2.1

d dt m p (t) -(1 -κ p )m p+1/2 (t) + κ p S p (t),
where

S p (t) = [ p+1 2 ] k=1 p k m k+1/2 (t) m p-k (t) + m k (t) m p-k+1/2 (t) .
The crucial point is that, for p 2, the above expression S p (t) involves moments of order less than p -1/2 except for p = 3/2 which explains its peculiar role. The induction hypothesis implies therefore that there exists a constant C p > 0 such that

S p (t) C p E(t) p+1/2 ∀t t 0 ,
where C p can be taken as

C p = [ p+1 2 ] k=1 p k K k+1/2 K p-k + K k K p-k+1/2 .
Furthermore, according to Jensen's inequality m p+1/2 (t) m 1+1/2p p (t), therefore we obtain

d dt m p (t) -(1 -κ p )m 1+1/2p p (t) + κ p C p E(t) p+1/2 ∀t t 0 . (2.8)
Additionally, according to (3.3) and since e(r) 1 for any r 0, one has clearly Ψ e (|u| 2 )

|u| 3
8 for any u ∈ R 3 . Thus, using (1.7),

- d dt E(t) 1 8 R 3 ×R 3 |u| 3 f (t, v)f (t, v ⋆ ) dv dv ⋆ R 3 f (t, v)|v| 3 dv = m 3/2 (t) ∀t t 0 .
(2.9)

Let K > be conveniently chosen later and define U p (t) := m p (t)-KE(t) p . Then, combining (2.8) and (2.9),

d dt U p (t) = d dt m p (t) -pKE(t) p-1 d dt E(t) -(1 -κ p )m 1+1/2p p (t) + κ p C p E(t) p+1/2 + pKm 3/2 (t)E(t) p-1 ∀t t 0 .
Therefore, using (2.6) we obtain

d dt U p (t) -(1 -κ p )m 1+1/2p p (t) + κ p C p E(t) p+1/2 + pKE(t) p+1/2 ∀t t 0 .
This is enough to prove (2.7) for K = K p large enough. Indeed, pick K so that m p (t 0 ) < KE(t 0 ) p . Then, by time-continuity in the moments, the estimate (2.7) follows at least for some finite subsequent time. Assume that there exists a time t ⋆ > t 0 such that m p (t ⋆ ) = KE(t ⋆ ) p , then the above inequality implies

dU p dt (t ⋆ ) -(1 -κ p )K 1+1/2p + κ p C p + pK E(t ⋆ ) p+1/2 <
E(t) C 0 (1 + t) -λ ∀t > 0, then there exists C > 0 such that E(t) C (1 + t) - 2
1+γ for any t 0, i.e. the generalized Haff's law (4.7) holds true.

ENTROPY-BASED PROOF OF HAFF'S LAW

The aim of this section is to prove Theorem 1.7. We begin computing the entropy production associated to the Boltzmann equation for granular gases (1.1).

3.1. Entropy production functional. For any nonnegative f , one can use the weak form (1.6) with the test function ψ(v) = log f (v) to compute the production of entropy

S e (f ) := R 3 Q e (f, f ) log f dv. More precisely, S e (f ) = 1 2π R 6 ×S 2 |u • n|f (v)f (v ⋆ ) log f (v ′ )f (v ′ ⋆ ) f (v)f (v ⋆ ) dv dv ⋆ d n = 1 2π R 6 ×S 2 |u • n|f (v)f (v ⋆ ) log f (v ′ )f (v ′ ⋆ ) f (v)f (v ⋆ ) - f (v ′ )f (v ′ ⋆ ) f (v)f (v ⋆ ) + 1 dv dv ⋆ d n + 1 2π R 6 ×S 2 |u • n| f (v ′ )f (v ′ ⋆ ) -f (v)f (v ⋆ ) dv dv ⋆ d n.
Define,

D e (f ) := - 1 2π R 6 ×S 2 |u • n|f (v)f (v ⋆ ) log f (v ′ )f (v ′ ⋆ ) f (v)f (v ⋆ ) - f (v ′ )f (v ′ ⋆ ) f (v)f (v ⋆ ) + 1 dv dv ⋆ d n (3.1
) which is a non-negative quantity since log x x -1 for any x > 0. Notice that, if e = 1, then D e is the classical entropy production functional and S e (f ) = -D e (f ) 0, which means that the entropy production S e is non-positive.

For inelastic collisions, the entropy production functional is more intricate,

S e (f ) = -D e (f ) + 1 2π R 6 ×S 2 |u • n| f (v ′ )f (v ′ ⋆ ) -f (v)f (v ⋆ ) dv dv ⋆ d n
which means that the entropy production splits into a dissipative part (-D e ) and a nonnegative part. Let us compute more precisely this last term. Since ϑ e (•) is strictly increasing, it is bijective. Moreover,

|u ′ • n| = ϑ e (|u • n|)), thus, one can write |u • n| = ϑ -1 e (|u ′ • n|). Then, using the change of variables (v ′ , v ′ ⋆ ) → (v, v ⋆ ) we obtain R 6 ×S 2 |u • n|f (v ′ )f (v ′ ⋆ ) dv dv ⋆ d n = R 6 ×S 2 ϑ -1 e (|u ′ • n|)f (v ′ )f (v ′ ⋆ ) dv dv ⋆ d n = R 6 ×S 2 ϑ -1 e (|u • n|)f (v)f (v ⋆ ) dv dv ⋆ d n J e (ϑ -1 e (|u • n|))
.

We used that

dv ′ dv ′ ⋆ = J e (|u • n|) dv dv ⋆ = J e (ϑ -1 e (|u ′ • n|) dv dv ⋆ . It is easy to see that ϑ -1 e (|u • n|) = |u• n| e(ϑ -1 e (|u• n|) . Then, we deduce that 1 2π R 6 ×S 2 |u • n| f (v ′ )f (v ′ ⋆ ) -f (v)f (v ⋆ ) dv dv ⋆ d n = 1 2π R 6 ×S 2 |u • n|f (v)f (v ⋆ ) 1 e(ϑ -1 e (|u • n|))J e (ϑ -1 e (|u • n|)) -1 dv dv ⋆ d n = R 3 ×R 3 |u|f (v)f (v ⋆ )Φ e (|u|) dv dv ⋆ .
For any fixed v, v ⋆ , we have defined

Φ e (|u|) := 1 2π S 2 | u • n| 1 e(ϑ -1 e (|u • n|))J e (ϑ -1 e (|u • n|)) -1 d n.
After some minor computations,

Φ e (|u|) = 2 |u| 2 |u| 0 1 e(ϑ -1 e (z)) J e (ϑ -1 e (z)) -1 z dz.
Setting then r = ϑ -1 e (z) and recalling that J e (y) = ϑ ′ e (y), we easily get that

Φ e (|u|) = 2 |u| 2 ϑ -1 e (|u|) 0 r -ϑ e (r) ϑ ′ e (r) dr
where we also used that ϑ -1 e (0) = 0. We just proved the following proposition.

Proposition 3.1. Assume that the restitution coefficient e(•) satisfies Assumption 1.1, items (1) and (2). Then, for any non-negative distribution function

f (v) S e (f ) = R 3 Q e (f, f ) log f dv = -D e (f ) + R 3 ×R 3 |u|f (v)f (v ⋆ )Φ e (|u|) dv dv ⋆ (3.2)
where D e (f ) 0 is given by (3.1) while Φ e (•) is defined by

Φ e (̺) = 2 ̺ 2 ϑ -1 e (̺) 0 r -ϑ e (r) ϑ ′ e (r) dr, ∀̺ > 0. (3.3)
Additional qualitative properties of Φ e are given in the following lemma. Proof. Since ϑ e (•) is assumed to be increasing, one clearly has r -ϑ e (r)ϑ ′ e (r) r for any r 0. Therefore,

Φ e (|u|) ϑ -1 e (|u|) |u| 2 ∀u ∈ R 3
and the first part of the Lemma follows from (3.4). Moreover, if e(r) ≃ 1 -αr γ for r ≃ 0 and γ > 0, then r -ϑ e (r) ϑ ′ e (r) ≃ α(2 + γ)r γ+1 for r ≃ 0. Since ϑ -1 e (r) ≃ r for small r, one gets easily the second part of the result.

The case of a constant restitution coefficient is included in the previous lemma, however, in this case Φ e is explicit, we refer to [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part II: Self-similar solution and tail behavior[END_REF][START_REF] Gamba | On the Boltzmann equation for diffusively excited granular media[END_REF] for previous uses of the entropy production functional in the constant case. One checks without difficulty that e(r) ≃ a -5 3 r -1 3 as r → ∞. In particular,

ϑ e (r) ≃ a -5 3 r 2 3
as r → ∞.

Consequently, there exists some positive constant C a > 0 such that ϑ -1 e (y) C 0 y 3 2 for large y > 0. Therefore, the assumption (3.4) of the above Lemma is fulfilled with m = 3/2, and one obtains that there exists some positive constant C > 0 such that Φ e (|u|) C|u| for large u ∈ R 3 .

Since (1.9) is known to hold with γ = 1/5 and α = a, we also have Φ e (|u|) ≃ 2a|u| 1/5 as |u| ≃ 0.

3.2.

Evolution of the entropy and the temperature: Haff's law. In all this section, we shall assume the following additional conditions on the restitution coefficient.

Assumptions 3.5. Assume that the restitution coefficient fulfills Assumptions 1.1. Moreover, assume that (1.9) and (3.4) holds, that is,

(1) There exist α > 0 and γ 0 such that 1 -e(r) ≃ αr γ as r ≃ 0.

(2) There exist m 1 + γ/2 and C > 0 such that ϑ -1 e (y) Cy m for large y.

Remark 3.6. Note that the assumption m 1 + γ/2 is no restrictive since the condition (2) concerns large values of y.

Under this conditions, the growth of the entropy of the solution to (1.1) is at most logarithmic.

Proposition 3.7. Assume that the restitution coefficient e(•) satisfies Assumptions 3.5. In addition, assume that the initial distribution f 0 satisfies (1.2) together with H(f 0 ) < ∞ and let f (t, v) be the solution to (1.1). Then, there exists a constant C 0 > 0 such that the entropy

H(f (t)) of f (t, v) satisfies H(f (t)) H(f 0 ) + C 0 log(1 + t) ∀t 0.
Proof. From the results of previous section, the evolution of the entropy

H(f (t)) is gov- erned by d dt H(f (t)) = -D e (f (t)) + R 3 ×R 3 |u|f (t, v)f (t, v ⋆ )Φ e (|u|) dv dv ⋆ ∀t 0. (3.5)
Under Assumption 3.5, Lemma 3.2 implies that we have Φ e (|u|) C|u| 2(m-1) for large |u| while Φ e (|u|) ≃ 2α|u| γ for small |u| ≃ 0. In particular, there are two positive constants A and B such that

Φ e (|u|) A|u| γ + B|u| 2(m-1) ∀u ∈ R 3 .
From (3.5) and since -D e (f (t)) 0,

d dt H(f (t)) A R 3 ×R 3 |u| γ+1 f (t, v)f (t, v ⋆ ) dv dv ⋆ + B R 3 ×R 3 |u| 2m-1 f (t, v)f (t, v ⋆ ) dv dv ⋆ .
Moreover, since |u| γ+1 2 γ |v| γ+1 + |v ⋆ | γ+1 one has

R 3 ×R 3 |u| γ+1 f (t, v)f (t, v ⋆ ) dv dv ⋆ 2 γ+1 R 3 ×R 3 |v| γ+1 f (t, v) dv = 2 γ+1 m γ+1 2 (t).
Moreover, setting p = m -1/2, one notices that there is a constant c p depending only on p such that

R 3 ×R 3 |u| 2m-1 f (t, v)f (t, v ⋆ ) dv dv ⋆ m p (t)
where the m p (t) terms are the p th order moments defined in (2.1). Using Proposition 1.2 together with Proposition 2.2, one concludes that there exist two positive constants C 1 and

C 2 such that d dt H(t) C 1 (1 + t) -1 + C 2 (1 + t) -2p 1+γ ∀t > 0.
Since p = m -1/2 with m 1 + γ/2 one has 2p 1+γ 1 and, setting

C 0 = C 1 + C 2 , we get d dt H(t) C 0 (1 + t) -1 ∀t > 0
which yields the conclusion.

The above logarithmic growth is exactly what we need to prove Haff's law. Indeed, the following general result allows to control from below the temperature using the entropy. The proof of the following proposition is given in the Appendix.

Proposition 3.8. Let C denote the class of nonnegative velocity distributions f = f (v) with unit mass, finite energy and finite entropy

R 3 f (v) dv = 1 R 3 |v| 2 f (v) dv < ∞, H(f ) = R 3 f (v) log f (v) dv < ∞. Define H(f ) = R 3 f (v)| log f (v)| dv, f ∈ C.
Then, there is some constant c > 0 such that

H(f ) H(f ) + c R 3 f (v) |v| 2 dv 5/3
, and some other constant C > 0 such that

R 3 f (v)|v| 2 dv C exp -4 3 H(f ) ∀f ∈ C. (3.6)
Proposition 3.8 combined with the logarithmic growth of H(f (t)) prove the Haff's law for non-constant restitution coefficient.

Theorem 3.9. Assume that the restitution coefficient e(•) satisfies Assumptions 3.5 with γ > 0. Let the initial distribution f 0 satisfies (1.2) and H(f 0 ) < ∞, and let f (t, v) be the unique solution to (1.1). Then, there is a constant c > 0 such that

E(t) c (1 + t) -2 1+γ ∀t 0.
In particular, the generalized Haff's law (4.7) holds true.

Proof. With the notations of the above Proposition 3.8, there is some constant C > 0 independent of time such that

H(f (t)) H(f (t)) + CE(t) 5/3 ∀t 0.
Since E(t) is bounded, one can find constants k 0 , K 0 > 0 such that

H(f (t)) k 0 + K 0 log(1 + t) ∀t 0. (3.7)
Proposition 3.8 also implies that there exists a constant c 1 > 0 such that

E(t) c 1 exp - 4 3 H(f (t)) c 2 exp - 4K 0 3 log(1 + t) ∀t 0, with c 2 = c 1 exp(-4k 0 3 ). Therefore, setting λ 0 = 2K 0 3 > 0 we get that E(t) c 2 (1 + t) -2λ 0 ∀t 0. (3.8)
Therefore, according to Proposition 2.4, the estimate (3.8) is enough to prove the second part of Haff's law (1.11).

For constant restitution coefficient, our result is less precise, however, we prove an integrated version of Haff's law in the next theorem. Consequently,

sup λ 0 , sup t 0 (1 + t) 2λ E(t) < ∞ = inf λ > 0 ; lim sup t→∞ (1 + t) 2λ E(t) > 0 = 1.
Proof. Recall that, for constant restitution coefficient e ∈ (0, 1) the evolution of the entropy is given by

d dt H(f (t)) = -D e (f (t)) + 1 -e 2 e 2 R 3 ×R 3 |u|f (t, v)f (t, v ⋆ ) dv dv ⋆ ∀t 0
where we used Eq. (3.5) and Example 3.3. Arguing as in the previous proof, we see that

d dt H(f (t)) 2 1 -e 2 e 2 m 1/2 (t) 2 1 -e 2 e 2 E(t) ∀t 0.
Integrating this inequality yields

H(f (t)) H(f 0 ) + 2 1 -e 2 e 2 t 0 E(s) ds ∀t 0.
Consequently, there exists a positive constant K 1 > 0 such that

H(f (t)) K 1 + 2 1 -e 2 e 2 t 0 E(s) ds ∀t 0.
Then, from Proposition 3.8,

E(t) C exp - 4K 1 3 - 8(1 -e 2 ) 3e 2 t 0 E(s) ds ∀t 0, i.e. there are two positive constants a = √ C exp(-2K 1 3 ) and b = 4(1-e 2 )
3e 2

such that

E(t) a exp -b t 0 E(s) ds ∀t 0
which yields (3.9). Now, setting

A = {λ 0 ; sup t 0 (1 + t) 2λ E(t) < ∞}
we know from Proposition 1.2 that 1 ∈ A, i.e. A = ∅. Then, it follows from (3.9) that sup A = 1. Now, let us define

B = {λ 0 ; lim sup t→∞ (1 + t) 2λ E(t) > 0}.
Notice that inequality (3.8) holds for constant restitution coefficient. In particular, it proves that B = ∅. Notice also that if λ 1 ∈ B, then any λ 2 λ 1 belongs to B. We argue by contradiction to prove that inf B = 1. Otherwise, from the previous observation, one

would have inf B = λ B > 1. Pick λ ∈ (1, λ B ), it follows that λ /
∈ B, that is, lim sup t→∞ (1 + t) 2λ E(t) = 0 and, in particular, λ ∈ A. This is impossible since sup A = 1, and thus, inf B = 1. Remark 3.11. Though less precise that the converse inequality (1.11), the above integrated version of Haff's law asserts that (1 + t) -2 is the only possible algebraic rate for the cooling of the temperature E(t). Notice that v T (t) = E(t) is proportional to the so-called thermal velocity [START_REF] Brilliantov | Kinetic theory of granular gases[END_REF] and we may wonder what is the physical relevance of the above identity (3.9). Finally, we recall that it is expected the existence of a self-similar profile Φ H (•), an homogeneous cooling state, such that t) is a solution to (1.1). The existence of homogeneous cooling state has been proven in [START_REF] Mischler | Cooling process for inelastic Boltzmann equations for hard-spheres, Part II: Self-similar solution and tail behavior[END_REF] (with a slightly different definition where v T (t) was replaced by (1 + t) -1 ) and where the self-similar profile Φ H is, by construction, satisfying Φ H ∈ L p for some p > 1. We conjecture that the existence of such an homogeneous cooling state can be obtained using only entropy estimates, that is H(Φ H ) < ∞. Remark 3.12. Notice that, since E(t)

f (t, v) = v T (t) -3 Φ H v v T (
C(1 + t) - 2
1+γ , it follows from (3.6) that there is some constant K > 0 such that

H(f (t)) K log(1 + t) ∀t 0
which means that the logarithmic growth obtained in Proposition 3.7 is optimal.

HAFF'S LAW IN THE WEAKLY INELASTIC REGIME

This section is devoted to the proof of Theorems 1.8 and 1.9. Let us now explain briefly the strategy of proof to get a precise version of generalized Haff's law. Note that due to Proposition 1.2, one only has to prove a lower bound of the type

E(t) c(1 + t) -2 1+γ
for some positive constant c > 0 independent of time. The following approach uses only the evolution of some moments of the solution f (t, v) with the particular use of Proposition 2.3. We will distinguish between the case of a constant restitution coefficient γ = 0 and the non-constant case γ > 0 since the two results are different. 4.1. The case of a constant restitution coefficient. We assume here that the restitution coefficient e(•) is constant: e(r) = e for for any r ∈ R + . In this case, Ψ e (r) =

1 -e 2 8 r 3/2 ∀r > 0 and the evolution of the temperature is given by

d dt E(t) = - 1 -e 2 8 R 3 ×R 3 f (t, v)f (t, v ⋆ )|v -v ⋆ | 3 dv dv ⋆ , t 0. Since |v -v ⋆ | 3 (|v| + |v ⋆ |) 3 = |v| 3 + |v ⋆ | 3 + 3|v| 2 |v ⋆ | + 3|v||v ⋆ | 2 , one deduces that - d dt E(t) 1 -e 2 4 m 3/2 (t) + 3 1 -e 2 4 E(t)m 1/2 (t) ∀t 0. (4.1)
This observation will help us in proving the following theorem.

Theorem 4.1. Let f 0 be a nonnegative velocity distribution satisfying (1.2) and let f (t, v) be the associated solution to (1.1). Assume that the constant restitution coefficient e is such that

3(1 -e 2 ) 8 < 1 -κ 3/2 . (4.2)
Then, for any t 0 > 0, there is an explicit positive constant C 0 > 0 such that

m 3/2 (t) C 0 E(t) 3/2 ∀t t 0 . (4.3)
Consequently, the second part of Haff's law holds

E(t) E(0) 1 + C 0 E(0)(1 -e 2 )t 2 ∀t 0.
Proof. Let t 0 > 0 be fixed. According to Proposition 2.1

d dt m 3/2 (t) -(1 -κ 3/2 )m 2 (t) + κ 3/2 S 3/2 (t).
From the expression of S 3/2 (t) one gets

d dt m 3/2 (t) -(1 -κ 3/2 )m 2 (t) + m 3/2 (t)m 1/2 (t) + E 2 (t) ∀t t 0 (4.4)
where we used the fact that κ 3/2 < 1. Let K be a positive number to be chosen later and define U 3/2 (t) := m 3/2 (t) -KE(t)

ℓ γ (e) = sup r 1 -e(r) r γ < ∞ for some γ > 0.
The proof is more involved but still based on Proposition 2.3. We therefore need only to estimate m 3/2 (t). We will work with the following class of initial datum: Let E 0 , ̺ 0 be two fixed positive constants. Define F (E 0 , ̺ 0 ) as the set of nonnegative distributions g ∈ L 1 3 such that

R 3 g(v) dv = 1, R 3 g(v)v dv = 0, R 3 |v| 2 g(v) dv = E 0 and R 3 g(v)|v| 3 dv ̺ 0 R 3 g(v)|v| 2 dv 3/2
.

With this definitions we have the following result.

Theorem 4.4. Let f 0 be a nonnegative velocity distribution satisfying (1.2) with initial energy E 0 . Then, there exists ℓ 0 := ℓ 0 (E 0 , γ) > 0 such that, if the restitution coefficient satisfies ℓ γ (e) < ℓ 0 , then solution f (t, v) to (1.1) fulfills the generalized Haff's law (4.7).

Proof. Throughout the proof, we simply denote ℓ γ (e) = λ since both γ and e(•) are fixed. Fix a time t 0 > 0, due to appearance of moments, there exists a e-independent constant

C := C(t 0 , E 0 , γ) > 0 such that sup t t 0 m 2γ (t) C. Note that f (t 0 , v) ∈ F (E t 0 , ̺ t 0 ) where m 3/2 (t 0 ) m 1 (t 0 ) 3/2 < ̺ t 0 < ∞.
Additionally, recall that

d dt m 3/2 (t) -2αm 2 (t) + m 3/2 (t)m 1/2 (t) + E 2 (t) ∀t t 0 , (4.8)
where we have set 2α = (1 -κ 3/2 ) > 0. Now, using (2.4)

-E(t) 1/2 d dt E(t) λ c γ E(t) 1/2 m (3+γ)/2 (t) λ c γ 1 4 E(t) 2 + 3 4 m 4/3 (3+γ)/2 (t) λ c γ 1 4 E(t) 2 + 3 4 m 1/3 2γ (t)m 2 (t) ∀t t 0 .
For t t 0 the quantity m 2γ (t) 1/3 is controlled uniformly by A := C 1/3 , therefore, -E(t)

(t) + m 3/2 (t)m 1/2 (t) + 1 + λ K 3c γ 8 E(t) 2 + -α + λ K 9c γ 8 A m 2 (t).
For the first term in the left-hand side, one uses the same estimate as in Theorem 2.2

-αm 2 (t) + m 3/2 (t)m 1/2 (t) -αE(t) -1 m 2 3/2 (t) + m 3/2 (t)E(t) 1/2 , thus, d dt U 3/2 (t) -αE(t) -1 m 2 3/2 (t) + m 3/2 (t)E(t) 1/2 + (1 + 3Kc γ ) E(t) 2 + -α + λ K 9c γ 8 A m 2 (t) ∀t t 0 . (4.10)
Without loss of generality, we have assumed λ < 8 (any other positive number would have worked). Now, let K 0 > 0 be the positive root of -αX

2 + (1 + 3c γ )X + 1 = 0. Then, if K = max(K 0 , ̺ t 0 ), one gets that λ < ℓ 0 =⇒ m 3/2 (t) KE 3/2 (t) ∀t t 0
where ℓ 0 = 8α 9Acγ K . Indeed, since U 3/2 (t 0 ) < 0, by a continuity argument, then U 3/2 (t) remains nonpositive at least for some finite time. Assume that there exists a time t

⋆ > t 0 such that U 3/2 (t ⋆ ) = 0, that is, m 3/2 (t ⋆ ) = KE 3/2 (t ⋆ ). Then, from (4.10) d dt U 3/2 (t ⋆ ) -αK 2 + (1 + 3c γ ) K + 1 E(t ⋆ ) 2 + -α + λ K 9c γ 8 A m 2 (t ⋆ ).
Since K K 0 , the first term on the right-hand side is negative while, by choice of λ < ℓ 0 := ℓ 0 (t 0 , E 0 , γ), the last term is negative as well. In other words, d dt U 3/2 (t ⋆ ) < 0 from which we deduce that U 3/2 (t) will remain non-positive for all t t 0 . As explained in the paragraph precedent to Proposition 2.3, this yields Theorem 4.4.

Remark 4.5. It is important to notice that the smallness condition is depending on the initial datum f 0 . This is the major difference with respect to the constant case where the smallness assumption (4.2) is universal.

APPENDIX: FUNCTIONAL INEQUALITIES RELATING MOMENTS AND ENTROPY

In this section, we present some functional inequalities that relate moments and entropy. We present the results in R n with n 1 regardless we only use them in dimension n = 3. In this section, for any measurable subset E ⊂ R n , |E| will stand for the Lebesgue measure of E. Let f = f (v) be a nonnegative distribution and denote

H(f ) = R n f (v) log f (v) dv, H(f ) = R n f (v)| log f (v)| dv,
while, for any k 0 we set

M k (f ) = R n f (v)|v| k dv.
First recall the following simple estimate which can be traced back to [START_REF] Di Perna | On the Fokker-Planck-Boltzmann equation[END_REF]:

Lemma A. 1. If there is k ∈ (0, n) such that M k (f ) < ∞ and H(f ) < ∞ then H(f ) < ∞.
More precisely, for any k ∈ (0, n) there exists some positive constant c n,k > 0 such that

0 H(f ) H(f ) + c n,k M k (f ) n n+k . (A.1)
Proof. Although it is almost explicitly stated in [START_REF] Di Perna | On the Fokker-Planck-Boltzmann equation[END_REF], we provide the complete proof of the above estimate. Define

A = {v ∈ R n , f (v) < 1}, thus H(f ) = R n \A f (v) log f (v) dv - A f (v) log f (v) dv = H(f ) -2 A f (v) log f (v) dv = H(f ) + 2 A f (v) log 1 f (v) dv.
For any a > 0, let B = {v ∈ R n ; f (v) exp(-a|v| k )} and

B c = R n \ B. If v ∈ A ∩ B then log( 1 f (v) ) a|v| k and H(f ) H(f ) + 2a A∩B f (v)|v| k dv + 2 B c ∩A f (v) log 1 f (v) dv H(f ) + 2aM k (f ) + 2 B c f (v) log 1 f (v)
dv.

Since x log(1/x) M √ x for any x ∈ (0, 1), where M = 2 exp(-1), we get

B c f (v) log 1 f (v) dv M B c f (v) dv M R n exp -a |v| k 2 dv. Set J n,k (a) = R n exp - a 2 |v| k dv = |S n-1 | k 2 a n k
Γ n k where Γ(•) is the Gamma function. We have H(f ) H(f ) + 2aM k (f ) + 2J n,k (a) for any a > 0. Therefore, for any k ∈ (0, n), there exists some positive constant C n,k > 0 such that

H(f ) H(f ) + 2aM k + C n,k a -n k ∀a > 0.
Optimizing the parameter a > 0 yields (A.1) for some explicit constant c n,k .

We now give a general estimate which allow to control M k (f ) from below in terms of H(f ). It is likely that such an estimate is well-known by specialists. We include a proof below.

Proposition A. 1. Let f 0 be such that H(f ) < ∞ with R n f (v) dv = 1. Then, for any k 0 and any ε > 0, there exists C(n, k, ε) > 0 independent of f such that

M k (f ) C(n, k, ε) exp - k n(1 -ε) H(f ) . (A.2)
Proof. For any R > 0, let B R denote the ball with center in the origin and radius R, and let B c R be its complement. Then, Using this inequality with x = f (v) and y = 1 and integrating the inequality over B R we obtain

M k (f ) = B R f (v)|v| k dv + B c R f (v)|v| k dv R k B c R f (v) dv = R k 1 - B R f (
B R f (v) dv 1 λ B R f (v) log f (v) dv - 1 λ (log λ + 1) B R f (v) dv + exp(λ)|B R | ∀λ > 0.
Consequently, since B R f (v) log f (v) dv H(f ), we get We optimize the parameter x > -1 by noticing that the right-hand side reaches its minimal value for x 0 such that x 0 exp(x 0 )|B R | = H(f ).

1 λ (log λ + λ + 1) B R f (v) dv 1 λ H(f ) + exp(λ)|B R | ∀λ > 0,
The mapping x → x exp(x) is strictly increasing over (-1, ∞) and we define W its inverse (Lambert function). We get then x 0 = W (H(f )/|B R |) and

B R f (v) dv H(f ) + exp(x 0 )|B R | 1 + x 0 = exp(x 0 )|B R | = exp W H(f ) |B R | |B R |.
Combining this with (A.3) we get

M k R k 1 -exp W H(f ) |B R | |B R | ∀R > 0
and we still have to optimize the parameter R. For simplicity, set Y = H(f ) and X = |B R |.

For any ε ∈ (0, 1),

1 -exp(W (Y /X))X = ε ⇐⇒ W (Y /X) = log 1 -ε X ⇐⇒ Y /X = 1 -ε X log 1 -ε X ,
where we used that W -1 (t) = t exp(t). Thus,

1 -exp(W (Y /X))X = ε ⇐⇒ Y 1 -ε = log 1 -ε X ⇐⇒ X = (1 -ε) exp - Y 1 -ε .
To summarize, for any ε > 0, if R 0 (ε) > 0 is such that |B R 0 | = (1 -ε) exp -H(f ) 1-ε , then

M k εR k 0 . Since |B R 0 | = |S n-1 | n R

Lemma 3 . 2 .

 32 Assume that the restitution coefficient e(•) satisfies Assumption 1.1. Assume moreover that (1.9) is satisfied for some α > 0 and γ > 0 and that there exist two positive constants C > 0 and m 1 such that ϑ -1 e (y) Cy m for large y.(3.4)Then, Φ e (|u|) C|u| 2(m-1) for large |u|, and Φ e (|u|) ≃ 2α|u| γ for small |u| ≃ 0.

Example 3 . 3 ( 2 ( 1 -e 2 e 2 . 3 . 4 . 5 e 3 5

 332123453 Constant restitution coefficient). If e(z) = e ∈ (0, 1] for any z 0, then J e = e and Φ e (̺) = Example If e(•) is the restitution coefficient for visco-elastic hard-spheres, there exists a > 0 such that e(r) + ar 1 (r) = 1 ∀r > 0.

Theorem 3 . 10 . 0 E

 3100 Let e ∈ (0, 1) be a constant restitution coefficient and let the initial distribution f 0 satisfies (1.2) with H(f 0 ) < ∞ , and let f (t, v) be the unique solution to (1.1). Then, there are two positive constants a, b > 0 such that t

  v) dv . (A.3)Therefore, in order to control M k (f ) from below it is enough to control the mass of f on a suitable ball. Let us fix R > 0 and recall the generalized Young's inequality xy x log x -x + exp(y) ∀x > 0, λ y) ∀x > 0, λ > 0, ∀y ∈ R.

f

  (v) dv H(f ) + λ exp(λ)|B R | ∀λ > 0.Set x = log(λ exp(λ)) and assume x > -1. The last inequality becomesB R f (v) dv H(f ) + exp(x)|B R | 1 + x ∀x > -1.

1 . 3 f 4 )

 134 n 0 we get our conclusion with C(n, k, ε) = ε n(1-ε) In dimension n = 3 with k = 2 and ε = 1/2, one sees that there is some constant C > 0 such that R for any nonnegative distribution function f (v) > 0 with R 3 f (v) dv = 1.

  0 whenever K is large enough. This proves that (2.7) holds for any p 3/2.For non-constant restitution coefficient, an interesting result holds: in order to prove the lower bound(1.11), it is enough to prove that the cooling of E(t) is at most algebraic with arbitrary rate. More precisely, we have [2, Theorem 3.7] the following proposition which follows from Proposition 2.3.

Proposition 2.4. Assume that the restitution coefficient e(•) satisfy Assumptions 1.1 and (1.9) with γ > 0. If there exist C 0 > 0 and λ > 0 such that

  3/2 . This last inequality, together with the smallness assumption (4.2) imply the result provided K is large enough. Indeed, choose K so that m 3/2 (t 0 ) < KE 3/2 (t 0 ). Then, by timecontinuity of the moments, the result follows at least for some finite time. Assume that there exists a time t ⋆ > t 0 such that m 3/2 (t ⋆ ) = KE 3/2 (t ⋆ ), then (4.6) implies Non-constant case γ > 0. We consider in this section the non-constant case γ > 0 with restitution coefficient e(•) satisfying Assumption 1.1 with

			dU 3/2 dt	(t ⋆ )	-aK 2 + 1 + 1 +	9(1 -e 2 ) 8	K E 2 (t ⋆ )
	where a := (1 -κ 3/2 ) -3 8 (1 -e 2 ) > 0 by (4.2). Choosing K = C 0 large enough such that dU 3/2 dt (t ⋆ ) 0 for any t ⋆ the conclusion holds.
	Remark 4.2. We just proved that, under the sole assumption (4.2), the solution f (t, v) to the
	Boltzmann equation (1.1) satisfies the generalized Haff's law
				c(1 + t) -2 E(t) C(1 + t) -2 ,	t 0	(4.7)
	where c, C are positive constants depending only on E(0).
	Remark 4.3. Using the explicit expression of κ 3/2 given by Proposition 2.1, one sees that (4.2)
	amounts to e	8κ 3/2 3 -5 3 ≃ 0.809.
	4.2.
	From Holder's inequality,
			m 3/2 (t)	E(t) m 2 (t) and m 1/2 (t)	E(t)	∀t 0,	(4.5)
	so that
	dU 3/2 dt	(t) -(1 -κ 3/2 )	m 2 3/2 (t) E(t)	+ E(t)m 3/2 (t) + E 2 (t) -	3 2	K	dE(t) dt	E(t) 1/2 .
	Now, using (4.1), one gets
	dU 3/2 dt	(t) -(1 -κ 3/2 ) + 3(1 -e 2 ) m 2 3/2 (t) E(t) 8	+ E(t)m 3/2 (t) + E 2 (t) Km 3/2 (t)E(t) 1/2 + 9(1 -e 2 ) 8	KE(t) 2 .	∀t > t 0 . (4.6)