Urbano Reviglio
email: urbanoreviglio@hotmail.com

Towards a Right Not to Be Deceived? An Interdisciplinary Analysis of Media Personalization in the light of the GDPR

Keywords: Privacy, Profiling, Personalization, GDPR, Data Protection

Privacy is a pillar of European law and of the new GDPR. Social and technological developments question its protection and raise the need for more comprehensive legal analysis. Informational and decisional privacy, in particular, prove to be fundamental rights to tackle the pervasiveness of surveillance practices and persuasive technologies. Yet, their protection is uncertain. The paper is a theoretical and interdisciplinary contribution structured as follows. In the first part, it is reviewed the literature on profiling and online personalization in order to provide an overview of the socio-technical landscape, with a special focus on media content and news personalization. In the second part, the consequences of the GDPR on media personalization is analyzed. In the third part, the interplay between data protection, consumer and media law is discussed. In particular, the right to receive information and the value of serendipity are introduced to eventually discuss the idea of a 'right not to be deceived' as a precondition to properly protect privacy and other human rights as well as to preserve trust between users and platforms.

Introduction

Recently, much attention has been given to the assessment of the legal and social outcomes of the new General Data Protection Regulation (GDPR) as well as the Eprivacy regulation draft. Despite the introduction of new individual rights and a more compre-hensive understanding of the data protection landscape, many commentators observed the limitations of these regulations. GDPR, for example, lacks a precise language and explicit and well-defined rights and safeguards [START_REF] Wachter | Why a right to explanation of automated decisionmaking does not exist in the general data protection regulation[END_REF]. There are many doubts on the ex-istence or even efficacy of novel rights such as a right to explanation -which is not explicitly mentioned in the GDPR -the right to transparency and the right to non-discrimination. Thus, many epistemic, technical, and practical challenges must first be overcome. The article questions how the phenomenon of online personalization -particularly media and news personalization -is currently approached in the European legal frame-work and to what extent privacy is protected. More generally, it questions how the 'personalization paradox' -a trade-off between privacy and personalization quality -and the 'privacy paradox' -the users' inconsistent will to protect their privacy could be tempered. In more detail, the following questions are addressed: how can data subjects exercise their rights if the processing itself is opaque, difficult to understand, and unaware consent is usually given? To what extent does the GDPR ensure that profiling is legal, fair and non-discriminatory with regards to media personalization? And how does the European legislation deals with the risks posed by the employment of increasingly sophisticated techniques of persuasion and engagement that may eventually lead to manipulation?

In this paper, we specifically focus on personalization of media content which raises several social concerns and ethical discussions. In Section 2, we review the literature on emerging issues surrounding profiling and online personalization. In Section 3, an analysis of the new GDPR is done in order to clarify its effectiveness, its ambiguities and its limitations. More generally, we argue that data protection law is insufficient to prevent certain risks posed by media content personalization. Also, the paper advocates for the need to move from a mostly data-centric to a more usercentric view of privacy. Therefore, in Section 4 critical principles and human rights engaged in informational privacy are introduced and discussed and, eventually, conclusions are drawn.

2

Profiling and Data-driven Personalization

Humans constantly categorize, generalize and classify the world around them to reduce complexity. Algorithms can be programmed to automatically process information in similar ways. Profiling practices, thus, create, discover or construct knowledge from large sets of data from a variety of sources that then are used to make or inform decisions [START_REF] Kaltheuner | Data is power: Towards additional guidance on profiling and automated decision-making in the GDPR[END_REF][START_REF] Hildebrandt | Privacy as protection of the incomputable self: From agnostic to agonistic machine learning[END_REF]. Profiling occurs in a range of contexts and for a variety of purposes. This paper focuses on profiling that makes or informs decisions (presumed preferences) that personalize a user's media environment (e.g. content selection and ordering).

Of course, individuals can be misclassified, misidentified or misjudged, and such errors may disproportionately affect certain groups of people [START_REF]The future of identity in the information society: Challenges and opportunities[END_REF]. Profiling technologies, in fact, creates a kind of knowledge that is inherently probabilistic. They cannot produce or detect a sense of self but they can, however, influence a person's sense of self [START_REF] Kaltheuner | Data is power: Towards additional guidance on profiling and automated decision-making in the GDPR[END_REF][START_REF] Hildebrandt | Privacy as protection of the incomputable self: From agnostic to agonistic machine learning[END_REF]. In the case of media content personalization, individuals may start to want what is recommended to them without even realizing it, in a self-fulfilling prophecy [START_REF] Kohl | Data-driven personalisation and the law-a primer: collective interests engaged by personalisation in markets, politics and law[END_REF]. Algorithms indeed threaten a foundational link in microeconomic theory, that is, preferences' formation [START_REF] Gal | Algorithmic Challenges to Autonomous Choice[END_REF]. At the same time, mass personalisation can be understood as pursuing the logic of market segmentation until each individual user is reduced to a unique market [START_REF] Yeung | Five Fears About Mass Predictive Personalisation in an Age of Surveillance Capitalism[END_REF].

Aside from natural human dispositions such as selective exposure, confirmation bias and homophily, personalization of media content -particularly if implicit -can eventually limit information exposure and discovery. As such, filter bubbles [START_REF] Pariser | The filter bubble: How the new personalized web is changing what we read and how we think[END_REF] and echo chambers [START_REF] Sunstein | # Republic: Divided Democracy in the Age of Social Media[END_REF] are strengthened. In fact, personalization -in particular news personalization -could reduce opportunities to self-determine and negatively affect truth finding by reducing the exposure to alternative points of view and serendipity in the 'marketplace of ideas' [START_REF] Pariser | The filter bubble: How the new personalized web is changing what we read and how we think[END_REF][START_REF] Sunstein | # Republic: Divided Democracy in the Age of Social Media[END_REF]. There may be several other consequences on both individual character, mindset and collective moral culture of our societies [START_REF] Yeung | Five Fears About Mass Predictive Personalisation in an Age of Surveillance Capitalism[END_REF]; from the limitation of personal creativity to a reduction in the ability to build productive social capital. Mass personalization could also weaken media pluralism, solidarity and make people more politically polarized, narcissistic and vulnerable to (self)propaganda [START_REF] Sunstein | # Republic: Divided Democracy in the Age of Social Media[END_REF].

And in a self-reinforcing cycle, this would make people more susceptible to fake news or polarizing messages, help to spread misinformation and, ultimately, erode interpersonal trust. In general, critics argue that these are moral panics, and that personalization might instead foster the cultivation of expert citizens with stronger group identities [START_REF] Harambam | Democratizing algorithmic news recommenders: how to materialize voice in a technologically saturated media ecosystem[END_REF]. It is no more than human nature empowered by the Internet. Yet, another prominent risk remains growing 'epistemic inequality', that is, the richer an individual's social network and the higher the education, the better the benefits of personalization.

In practice, the risks of personalization are very hard to prove and, eventually, to counteract [START_REF] Borgesius | Should We Worry About Filter Bubbles?[END_REF]. There is indeed a crisis on the study of algorithms [START_REF] Bodo | Tackling the Algorithmic Control Crisis -The Technical, Legal, and Ethical Challenges of Research into Algorithmic Agents[END_REF]. Their functioning is opaque and 'black-boxed' and their interpretability is not even clear [START_REF] Albanie | Unknowable Manipulators: Social Network Curator Algorithms[END_REF]. Also, users consider filtering mechanism as neutral and actually few recognize them or attempt to opt-out [START_REF] Gillespie | The relevance of algorithms[END_REF]. Furthermore, concerns are growing because of the rise of increasingly sophisticated persuasive technologies and the ability of big-data to 'hyper-nudge' individuals and bring them to deception [START_REF] Yeung | Hypernudge': Big Data as a mode of regulation by design[END_REF] (discussed in Section 4.3). Ultimately, key issues remain unsolved: to what extent personalization is detrimental and whether current legislation is sufficient to address these issues. Before problematizing the interplay between different legal fields, it is necessary to analyze the promises and perils of the current European data protection landscape.

European Legislation, GDPR and Its Limits

In the last years, the EU has adopted some provisions that give consumers the power to manage their personal data and not to be subject to automated decision-making such as personalization and algorithmic assistants. The right to data portability1 envisaged in the new GDPR, as well as the e-Privacy regulation2 , and also the "retrieve them all" provision of the proposed Digital Content Directive, are all tools whereby digital consumers will supposedly have the chance to decide who should use their data to offer them the goods and services that they want [START_REF] Colangelo | From fragile to smart consumers: Shifting paradigm for the digital era[END_REF]. These regulatory interventions bring to the fore a reshaping of the traditional landscape of the consumer protection rules providing a more comprehensive vision of "data consumer law". They in fact grant users several rights, such as the right to transfer data from one controller to another and the right to retrieve any data produced or generated through their use of a platform. They are expected to re-balance the relationship between data subjects and data controllers and to encourage competition between companies. These represent a new paradigm that abandons a purely protective and paternalistic regulation focused only on consumers' weaknesses to experiment with a more proactive approach [START_REF] Colangelo | From fragile to smart consumers: Shifting paradigm for the digital era[END_REF].

Yet, critics suggest that the GDPR -one of the most lobbied piece of EU legislation to date [START_REF] Edwards | Slave to the algorithm: Why a right to an explanation is probably not the remedy you are looking for[END_REF] -delivers personalisation to companies on a golden plate [START_REF] Kohl | Data-driven personalisation and the law-a primer: collective interests engaged by personalisation in markets, politics and law[END_REF]. Firstly, by shifting the prerequisite for more expansive (re)uses of personal data from anonymisation to 'pseudonymisation' (which still allows for some form of reidentification). In fact, although anonymised data is effective in protecting privacy, much analytical value of the data is lost through anonymisation (which is relevant for personalisation purposes).

Secondly, the GDPR facilitates personalisation by making the collection and processing/use of personal data essentially a matter of informational self-determination. This emphasis suggests to users that all that is at stake in data protection is their own personal interest whereas also fundamental collective public goods are actually at stake, such as deliberative democracy. Moreover, the GDPR lacks a precise language and explicit and well-defined rights and safeguards [START_REF] Wachter | Why a right to explanation of automated decisionmaking does not exist in the general data protection regulation[END_REF]. A number of provisions may thus lead to confusion, enforcement gaps or asymmetrical interpretations. This is understandable given that the reform of EU data protection is ongoing and need further guidelines.

The focus of the following analysis is specifically on the most relevant GDPR's articles affecting personalization dependent, above all, on 'profiling' which is a relatively novel concept in European data protection regulation (Art 4( 4)). It refers to both the creation and the use of profiles. By virtue of deriving, inferring or predicting information, practices of profiling generate personal and sensitive data. The rights to erasure (Art 17) and restriction of processing (Art 18) are then useful forms of redress in the context of unlawful profiling techniques. Further guidance, however, is needed to clearly set out these Articles' scopes of application. This is also true for highly debated articles that we are going now to briefly analyze, namely Articles 13-15 and Article 22.

The Right to Transparency

Transparency is often assumed to be an ideal for political discourse in democracies and it is generally defined with respect to "the availability of information, the conditions of accessibility and how the information…may pragmatically or epistemically support the user's decision-making process" [18, p.106]. This is significant regarding decisions -in the case analyzed in this paper, prioritizing personalized media content -that are extremely complex and inevitably black-boxed.

Auditing is one promising mechanism for achieving transparency [START_REF] Mittelstadt | Automation, Algorithms, and Politics| Auditing for Transparency in Content Personalization Systems[END_REF]. For all types of algorithms, auditing is a necessary precondition to verify correct functioning. For platforms that mediate political discourse, auditing can create a procedural record to demonstrate bias against a particular group. Auditing can also help to explain how citizens are profiled and the values prioritized in content displayed to them. It allows for prediction of results from new inputs and explanation of the rationale behind decisions.

Yet, many epistemic, technical, and practical challenges must first be overcome [START_REF] Burrell | How the machine 'thinks': Understanding opacity in machine learning algorithms[END_REF]. Firstly, a right to transparency might undermine the privacy of data subjects and the autonomy and competitive advantage of service providers, or even national security. Secondly, the rationale of an algorithm can be epistemically inaccessible, rendering the legitimacy of decisions difficult to challenge. Nevertheless, algorithm auditing may be quickly approaching and the belief that highly complex algorithms are incomprehensible to human observers should not be used as an excuse to surrender high quality political discourse. Developing practical methods for algorithmic auditing is highly needed. For example, Tutt [START_REF] Tutt | An FDA for algorithms[END_REF] suggests that a regulatory agency for algorithms may be required, and this agency can "classify algorithms into types based on their predictability, explainability, and general intelligence" (p. [START_REF] Yeung | Hypernudge': Big Data as a mode of regulation by design[END_REF] to determine what must be regulated. Actually, GDPR requires data processors to maintain a relationship with data subjects and explain the logic of automated decision making when questioned (Art 13, 14 and 15). The regulation may indeed prove a much-needed impetus for algorithmic auditing.

However, with opacity, implementing transparency and the right to an explanation in a practically useful form for data subjects will be extremely difficult, necessary yet likely insufficient, as will be argued throughout the paper.

The Right to an Explanation

Especially relevant to profiling, there are the right to be informed (Art 13) and the right of access (Art 14). In particular, Articles 13(2)(f) and 14(2)(g) require data controllers to provide specific information about automated decision-making, based solely on automated processing, including profiling, that produces legal or similarly significant effects, namely: 1) the existence of automated decision-making, including profiling; 2) meaningful information about the logic involved; and 3) the significance and envisaged consequences of such processing for the data subject.

Article 15(1)(h) uses identical language as of the above articles and provides data subjects with a right of access to information about solely automated decisionmaking, including profiling. However, some key expressions in Articles 13-14, specifically "meaningful information about the logic involved" as well as "the significance and the envisaged consequences" (Art 13(2)(f)), need to be interpreted to provide data subjects with the information necessary to understand and challenge profiling and automated individual decision-making. As a result, the right to explanation has been interpreted in two drastically different ways: as an ex-ante general explanation about system functionality or as an ex-post explanation of a specific decision (Art 15). Yet, in the interest of strong consumer protection, meaningful information must be sufficient to answer questions that the data subject might have before they consent to the processing (notification) and after a decision has been made (right of access).

A right to explanation is thus not explicitly mentioned in the GDPR. However, relative legal basis have been detected [START_REF] Wachter | Why a right to explanation of automated decisionmaking does not exist in the general data protection regulation[END_REF]. In particular, Recital 71 states that data subjects have the right 'to obtain an explanation'. Yet, the legal status of recitals is debated as, in general, they only provide guidance to interpret the Articles so they are not considered legally binding. This is a critical gap in transparency and accountability [START_REF] Edwards | Slave to the algorithm: Why a right to an explanation is probably not the remedy you are looking for[END_REF].

The Right to Non-discrimination

Article 22(1) of the GDPR contains additional safeguards against one specific application of profiling, namely the case of automated individual decision-making that fulfils is "based solely on automated processing" and produces "legal effects concerning him or her or similarly significantly affects him or her". Profiling can indeed form the basis of decision-making that is both automated and produces significant effects, in particular discriminatory. A right to non-discrimination is, in fact, deeply embedded in the normative framework that underlies the EU and the use of algorithmic profiling for the allocation of resources is, in a sense, inherently discriminatory [START_REF] Goodman | European Union regulations on algorithmic decision-making and a "right to explanation[END_REF]. In this sense, Article 22 is set. There are, however, several ambiguities that must be settled.

Firstly, the wording of the "right not to be subject to automated decision-making" can be interpreted as either a prohibition or a right to object. This ambiguity has existed since the Data Protection Directive 1995 [START_REF] Wachter | Why a right to explanation of automated decisionmaking does not exist in the general data protection regulation[END_REF], but resolving it is nowadays critical [START_REF] Kaltheuner | Data is power: Towards additional guidance on profiling and automated decision-making in the GDPR[END_REF]. Since profiling and automated decision-making often occur without the awareness of those affected, data subjects may not be able to effectively exercise their right to object. Moreover, Article 22 only applies to decisions that are "based solely" on automated processing, including profiling. Since "based solely" is not further defi-ned in the regulation, the regulation allows for an interpretation that excludes any human involvement whatsoever. This would render the article inapplicable to many current practices of automated decision-making and there is the risk is that the controller may fabricate human involvement. Finally, paragraph 71 and Article 22(4) specifically address discrimination from profiling that makes use of sensitive data. Goodman and Flaxman [START_REF] Goodman | European Union regulations on algorithmic decision-making and a "right to explanation[END_REF] broadly questioned the interpretation of the wording 'sensitive data' and argued how significant is its clarification.

In summary, GDPR defines novel rights for data subjects and duties for data controller. Along with the e-Privacy regulation draft, it actually strenghtens 'data consumer protection'. Users can indeed decide whether to enter into a contract, be informed, access the data generated, receive information about the logic involved and not to be subject to automated decision-making based solely on automated processing. The data subject, however, waives some of these rights when entering into a contract for which an automated decision is 'necessary'. As a matter of fact, a user does not have any effective agency towards the logics involved in the personalized news provision. While at first sight data-driven personalization may appear to be only a matter of data protection law, the analysis of automated inferences, predictions or decisions more often lies outside of it [START_REF] Kohl | Data-driven personalisation and the law-a primer: collective interests engaged by personalisation in markets, politics and law[END_REF]. In other words, data protection law focuses on 'inputs' rather than 'outputs', that are mostly out of its scope. Eventually, users will still have a limited (and indirect) control over the outcomes of personalization. In the following chapter, we evaluate the extent to which users may exercise such right and be fruitfully empowered.

A Comprehensive Approach to Media Personalization

Data protection law shows some limitations when it comes to the actual consumption of information in the context of media personalization. Yet, the application of consumer protection law to data-related commercial practices can certainly add to the protection offered by data protection law [START_REF] Helberger | The perfect match? A closer look at the relationship between EU consumer law and data protection law[END_REF]. 3 The complex interplay between data protection and consumer law need to be further analyzed in order to understand whether and how they might complement each other so as to be able to prevent the risks of media personalization. There is indeed a fundamental need for interdisciplinary work, not only across academics and practitioners, but also between different legal jurisdictions and across different disciplines. GDPR, for example, does not impose any responsibility on data controllers as regards the information a data subject might consume. Technically, there are two main dimensions that affect an individual's choice -the decision parameters employed by the algorithm and the level of choice which remains at the hands of the user [START_REF]The future of identity in the information society: Challenges and opportunities[END_REF] -GDPR focuses only on the former and ignores the latter. This critical point is particularly relevant in concentrated markets in which players refuse traditional editorial responsibility. As such, not only media law but particularly competition law maintain a significant -if not indispensable -role in setting standards and levelling the playing field [START_REF] Lynskey | Grappling with "Data Power": Normative Nudges from Data Protection and Privacy[END_REF].

To begin with, we acknowledge that informational and decisional privacy are fundamental for criticizing emerging means of opinion formation and behavioral change arising from personalization [START_REF] Lanzing | Strongly Recommended" Revisiting Decisional Privacy to Judge Hypernudging in Self-Tracking Technologies[END_REF]. The latter is complementary with the former, and it is broadly intended as the right against unwanted access such as unwanted interference in our decisions and actions. 4 In addition, the right to freedom of expression is also significantly involved, especially because individual privacy has not been traditionally justified in terms of public good or interest of groups [START_REF] Kohl | Data-driven personalisation and the law-a primer: collective interests engaged by personalisation in markets, politics and law[END_REF]. Thus, a reconceptualization of the right to be informed as a 'right to receive information' in order to increase control over data-driven personalization is discussed [START_REF] Eskens | Challenged by news personalisation: five perspectives on the right to receive information[END_REF]. Related to this, it is introduced the the value of serendipity as a design principle [START_REF] Reviglio | Serendipity as an Emerging Design Principle of the Infosphere: Challenges and Opportunities[END_REF]. These, however, may not even be sufficient to tackle the risks that personalization brings to privacy and freedom of expression, especially considering emerging techniques of behavioral modification [START_REF] Gillespie | The relevance of algorithms[END_REF][START_REF] Yeung | Hypernudge': Big Data as a mode of regulation by design[END_REF][START_REF] Zarsky | Privacy and Manipulation in the Digital Age[END_REF]. In this light, the idea of a 'right not to be deceived' is introduced, as a conceptualization that could enact more effectively other fundamental human rights.

The Right to Receive Information

The news consumers' fundamental rights to receive information guaranteed by Article 10 ECHR may prove an important point of departure to realize democratic values in the personalized media landscape [START_REF] Eskens | Challenged by news personalisation: five perspectives on the right to receive information[END_REF]. Information consumption is indeed deeply changed and needs to be reconceived. Given the vast amount of information produced and consumed, to some extent users are necessarily passive actors who have to delegate information filtering to algorithms and, therefore, to platforms. Thus, the right to information is, in effect, a right to receive information. How this would eventually translate is difficult to argue. Article 10 may nonetheless entail positive obligations for the state, such as ensuring that media users receive balanced news. Yet, it is an under-theorized right, lacking a framework to understand the rights of news consumers or the obligations of states regarding news recipients.

Media (and in particular news) personalization invites us to reconsider subjective rights to receive information. In traditional one-to-many media, people have a subjective right to receive information that others are willing to impart, but they do not have a right to receive information that the media is not willing to impart. In fact, the media would lose its editorial freedom if people could demand specific news stories and distribute these to them and, at the same time, if these were conflicting, it would be difficult to decide whose right to receive information should prevail. By enabling one-toone communication, personalization technologies could, in theory, resolve conflicts between subjective rights to receive information and the media's or other parties' freedom of expression. Such a type of subjective right to receive information could help to establish what news consumers legitimately may expect from the news media with respect to the diversity or relevance of personalized recommendations.

Actually, media personalization may enable or hinder the exercise of this largely institutionally protected right. There are many different values and interests at stake especially with news personalization, which may lead to conflicts (prominently truth finding versus social cohesion) that are not likely to end up in court but must be discussed in public. There is a need to discuss what the right to receive information should mean nowadays, how it relates to data protection, and to empirically study how people's information seeking strategies and privacy attitudes influence the exercise of this right.

Harambam et al [START_REF] Harambam | Democratizing algorithmic news recommenders: how to materialize voice in a technologically saturated media ecosystem[END_REF] identifies four ways in which people so far can actually influence the algorithmically curated information they encounter, and these are: 1) Alternation, that is, switching between different news outlets and media forms, and also by using multiple or different recommenders. Yet, it requires effort, skills, and it does little to work around hidden biases in algorithmic curation. Then, 2) awareness, that is, being aware of algorithms functioning. In this respect, the GDPR, which raises the bar on transparency and user control over personal data processing, may have a positive impact. 5 3) Adjustment, that is, adjust algorithms according to personal interests and wishes. Most news outlets, however, have not developed formal ways to influence their curating algorithms. And finally, 4) Obfuscation, that is, mobilizing against the data-driven processes through the deliberate addition of ambiguous, confusing, or misleading information to interfere with data collection. Yet, this may run against some of the goals and benefits of personalization.

The above techniques are not particularly effective as well as are difficult to pursue for the average user. 6 Yet, what forms of intervention at the level of data inputs and processing can be achieved in the context of algorithmic news recommenders to guarantee this right must be discussed further. This leads to a related issue which might help to better define strategies to tackle the current limitations of data protection law previously outlined.

The Value of Serendipity

Personalization also affects media law and threatens basic democratic principles such as diversity and pluralism. Generally speaking, media pluralism is achieved when users autonomously enjoy a diverse media diet. Even if media diversity online is shown to be more than in traditional media, such exposure does not always end up in an actual experience of diversity. Cognitive and affective factors that drive Internet users must also be considered [START_REF] Hoffmann | Diversity by choice: Applying a social cognitive perspective to the role of public service media in the digital age[END_REF]. This requires employing a user-centric perspective and extending beyond the assumption that supply diversity equals experience of diversity, and that diversity of sources equals diversity of content. Also, pluralism as a normative principle remains vague and under-theorized, and it is not a reliable indicator of a society's level of freedom, since it may create only the illusion of content diversity [START_REF] Karppinen | Media and the paradoxes of pluralism[END_REF] In the digital age, it is indeed becoming less clear in which sense it is meaningful to speak of media pluralism if the consumption is characterized by limitless choice [START_REF] Helberger | Exposure diversity as a design principle for recommender systems[END_REF].

Given such limitations, current debates center on whether designing for more 'serendipity' might sustain diversity and represent an innovative design and ethical principle for information environments [START_REF] Reviglio | Serendipity as an Emerging Design Principle of the Infosphere: Challenges and Opportunities[END_REF]. Extensive accounts on how to research serendipity and cultivate it in digital environments provide ground for novel studies. Yet, serendipity is an elusive and nuanced phenomenon; in this context, it is intended as the attempt to design for unexpected and meaningful information encountering that are indeed statistically less likely, thus less accurate, and that intersect users' profiles. As such, it has the potential to prevent the threats of filter bubbles, echo chambers and 'over-personalization'. In practice, it implies a diversification of information and more interactive control over the algorithmic outputs. Sunstein [START_REF] Sunstein | # Republic: Divided Democracy in the Age of Social Media[END_REF] advocated an "architecture of serendipity" as it would sustain 'chance encounters and shared experiences' that he regards as preconditions for well-functioning democracies. Therefore, taking into consideration serendipity in the design process can fruitfully inform designers, users and eventually policy-makers to stimulate what Harambam et al. [START_REF] Harambam | Democratizing algorithmic news recommenders: how to materialize voice in a technologically saturated media ecosystem[END_REF] defined as alternation, awareness, adjustment and obfuscation.

Towards a "Right Not to Be Deceived"?

Human behavior can be manipulated by priming and conditioning, using rewards and punishments. Algorithms can autonomously explore manipulative strategies that can be detrimental to users [START_REF] Albanie | Unknowable Manipulators: Social Network Curator Algorithms[END_REF][START_REF] Lanzing | Strongly Recommended" Revisiting Decisional Privacy to Judge Hypernudging in Self-Tracking Technologies[END_REF]. Basically, they exploit human biases and vulerabilities to affect self-control, self-esteem and personal beliefs. 7 Therefore, autonomy and democracies are indeed seriously threatened [START_REF] Gal | Algorithmic Challenges to Autonomous Choice[END_REF][START_REF] Zarsky | Privacy and Manipulation in the Digital Age[END_REF][START_REF] Deibert | The Road to Digital Unfreedom: Three Painful Truths About Social Media[END_REF][START_REF] Fogg | Interactive technology and persuasion[END_REF].

Such Big Data-driven nudging is defined by Yeung [START_REF] Yeung | Hypernudge': Big Data as a mode of regulation by design[END_REF] as a technique of "hypernudging", that is, a "nimble, unobtrusive and highly potent, providing the data subject with a highly personalised choice environment". Hyper-nudging operates through the technique of 'priming', dynamically configuring the user's informational choice context to influence their decisions. Thus, it concerns the entire design process, not only algorithmic decision-making [START_REF] Fogg | Interactive technology and persuasion[END_REF]. This introduces a new form of power, a new 'invisible hand' in which power is identified with ownership of behavioral modification (i.e. artificial emotional intelligence) [START_REF] Zuboff | Big other: surveillance capitalism and the prospects of an information civilization[END_REF]. In this sense, social media already act as addictive machines [START_REF] Deibert | The Road to Digital Unfreedom: Three Painful Truths About Social Media[END_REF]. As such, users are tempted to give up their rights to benefit from such hyper-nudging personalization. In theory, using such techniques goes against the 'fairness' and 'transparency' provisions of the GDPR [START_REF] Zarsky | Privacy and Manipulation in the Digital Age[END_REF]. In this sense, GDPR proves to be a necessary yet insufficient step. In fact, as smart environments will permeate societies, users (especially young people [START_REF] Gal | Algorithmic Challenges to Autonomous Choice[END_REF]) will be automatically plugged in and guided through life along algorithmically determined pathways, and the boundary between legitimate persuasion and deception will become increasingly blurred.

The right most clearly implicated by big data-driven hyper-nudging is the right to informational privacy. As such, data controllers are obliged to follow the principle of data protection by design and by default. This might go beyond the individual to focus a priori on the creation of better algorithms [START_REF] Edwards | Slave to the algorithm: Why a right to an explanation is probably not the remedy you are looking for[END_REF]. For example, privacy might be fundamental also to enable what Hildebrandt [START_REF] Hildebrandt | Privacy as protection of the incomputable self: From agnostic to agonistic machine learning[END_REF] defines as 'agonistic machine learning', that is, demanding companies or governments that base decisions on machine learning to 'explore and enable alternative ways of datafying and modelling the same event, person or action'. In this sense, the value of serendipity is also understood. 7 -For example, Facebook is especially committed to maintain friends' relationships. Its "NewsFeed" is thus moderated by homophily [41] which is, however, the primary driver of content diffusion, especially misinformation and conspiracy theories, with a frequent result of homogeneous, polarized clusters that tend to lead to emotionally charged and divisive content [39].

Of course, also consumer law could actually help to protect consumers against unfair profiling and persuasion practices [START_REF] Helberger | The perfect match? A closer look at the relationship between EU consumer law and data protection law[END_REF]. However, the extensive uncertainty and context dependence imply that people cannot be counted on to navigate the complex trade-offs involving terms of services and privacy self-management [START_REF] Acquisti | Privacy and human behavior in the age of information[END_REF]. There is overwhelming evidence that most people neither read nor understand online privacy policies. According to behavioral sciences as well, existing notice and consent model cannot be relied upon to protect the right to informational privacy [START_REF] Yeung | Hypernudge': Big Data as a mode of regulation by design[END_REF].

In addition to privacy, online digital users could have a separate and distinct right not to be deceived, rooted in a moral agent's basic right to be treated with dignity and respect given that deception violates the autonomy of the person deceived, involving the control of another without that person's consent. Appropriate information and specific consent to the use of techniques of deception ought to be given. Unfolding the preconditions of such a right may help tech companies to regain and preserve trust. Online platforms should in fact routinely disclose to its users and the public any experiment that the users were subjected to with the purpose of promoting engagement. Yet, given the complexity and subtleness of online deception the choice may not even be sufficiently informed and conscious even with consent. Independent and external review boards need to be established to review and approve experiments in advance. The current massive power asymmetry between global digital service providers and individual users in fact cannot be ignored [START_REF] Lynskey | Grappling with "Data Power": Normative Nudges from Data Protection and Privacy[END_REF][START_REF] Zuboff | Big other: surveillance capitalism and the prospects of an information civilization[END_REF]. As it is currently set, the EU legal framework seem to be insufficient to prevent users' potential deception.

Conclusions

GDPR defines novel rights for data subjects and duties for data controllers. However, GDPR's rights to an explanation, transparency and non-discrimination may actually prove ineffective in practice when users consume information filtered by proprietary algorithms, and even nurture a new kind of "transparency fallacy". Developments in personalization can actually narrow privacy conceptions and make data protection insufficient to protect fundamental human rights. Data protection actually relies too much on individual rights for what are too often group harms. There is indeed high need for user-centric as well as group-centric approaches to critically govern emerging issues of data-driven media personalization. Also, users cannot be fully relied to manage all the complexities of data protection. On the contrary, personalized persuasive techniques are likely to be employed on a mass scale and, therefore, contrary to recent trends in policy, it is also advocated a more paternalistic approach. Even if conceptualizing alternative privacy strategies for the online media context has proven to be difficult, two intertwined human rights have been introduced to enrich discussion on privacy in relation to profiling and media personalization. Firstly, we argued that data protection law should complement with media and consumer law in order to guarantee individuals a right to receive information. In general, such right could empower users to bypass and adjust algorithmic filters and receive more serendipitous information outside one's predetermined algorithmic path. Secondly, given the increasingly sophisticated techniques of behavioral modification and the characteristics of personalized persuasive technologies, a right not to be deceived in the online context has been introduced. Above all, any experiment that the users may be subjected to with the purpose of promoting engagement ought to be disclosed by platforms and approved by an independent agency. By discussing the above perspectives, the article provided a more comprehensive legal understanding on personalized online services in the light of the GDPR and offered an argumentative basis for further contextualisation and reflection.

-Data portability refers to the ability to move, copy or transfer data easily from one database, storage or IT environment to another. To make an example, move one's Facebook profile to another social network.

-Notice that the E-Privacy Regulation should be treated as lex specialis in relation to the GDPR. However, the enforcement mechanisms of GDPR and E-privacy Regulation remain the same.

-Yet, applying consumer law to deals regarding personal data should never be construed as a justification for using personal data as a commodity as it would conflict with human rights.

-Even if decisional privacy does not feature as a concept in the European legal tradition, art.8 of the ECHR does ackowledge the function of privacy as a right to personal development and autonomy as its underlying value.

-This is the case with Facebook which is implementing a feature "why I am seeing this" to provide users a better understanding of the reasons why a post has been recommended[START_REF]Facebook Newsroom[END_REF].

-Recently, it is even questioned whether the actual 'horizontal approach' based on the notion of 'average consumers' is fit to protect all consumers in a highly personalized digital environment[START_REF] Reviglio | Serendipity as an Emerging Design Principle of the Infosphere: Challenges and Opportunities[END_REF].


Amine Asselah
email: amine.asselah@u-pec.fr

Bruno Schapira
email: bruno.schapira@univ-amu.fr

The two regimes of moderate deviations for the range of a transient walk

Keywords: Random Walk, Range, Large deviations, Moderate deviations, Capacity. MSC 2010 subject classifications. Primary 60F05, 60G50

We obtain sharp upper and lower bounds for the downward moderate deviations of the volume of the range of a random walk in dimension five and larger. Our results encompass two regimes: a Gaussian regime for small deviations, and a stretched exponential regime for larger deviations. In the latter regime, we show that conditioned on the moderate deviations event, the walk folds a small part of its range in a ball-like subset. Also, we provide new path properties, in dimension three as well. Besides the key role Newtonian capacity plays in this study, we introduce two original ideas, of general interest, which strengthen the approach developed in [AS17].

Introduction

General overview In this paper, we consider a classical problem in probability theory: the moderate deviations for the range of a simple random walk. Curiously enough, moderate deviations estimates in dimension five and larger are missing. Nothing is known neither on the path properties of a walk conditioned on moderately squeezing its range. This motivates the present work. We extend the large deviations analysis of [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF] up to the Gaussian regime. Our approach also sheds light on the path properties in dimension three.

We denote by {S n } n∈N the simple random walk on Z d , d ≥ 3. Its range is the process n → R n := {S 0 , . . . , S n } which records the visited sites as time evolves, and we denote by |R n | the number of sites in R n . In 1951, Dvoretzky and Erdös [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] prove a strong law of large numbers in dimension three and larger, with an almost sure limit

1 n |R n | -→ γ d , with γ d > 0.
(1.1)

They express the range as a sum over newly visited sites, and obtain γ d as the probability of not returning to 0.

The deviation of |R n | below its mean has a long history. Kac and Luttinger in 1973 [START_REF] Kac | Bose Einstein condensation in the presence of impurities I, II[END_REF] discuss the problem of evaluating the expectation of exp(-|R n |) in their study of Bose-Einstein condensation in the presence of impurities. The first order asymptotics of E[exp(-|R n |)] are derived a few years later by Donsker and Varadhan in two celebrated works [START_REF] Donsker | Asymptotics for the Wiener sausage[END_REF] and [START_REF] Donsker | On the number of distinct sites visited by a random walk[END_REF]. The polymer measure obtained by tilting the random walk law by exp(-|R n |) is shown by Bolthausen [B94] to correspond to confining the random walk in a ball of radius n 1/(d+2) and to leave no hole in the covered region, in d = 2. Sznitman [START_REF] Sznitman | On the confinement property of two-dimensional Brownian motion among Poissonian obstacles[END_REF] shows in d = 2 as well the confinement of the Wiener sausage, the continuous counterpart of the walk, and Povel [START_REF] Povel | Confinement of Brownian motion among Poissonian obstacles in R d , d ≥ 3[END_REF] extends the proof of confinement to all dimensions d ≥ 3. Recently a more precise statement for the range has been obtained in d ≥ 3 independently by Ding, Fukushima, Sun and Xu [START_REF] Ding | Geometry of the random walk range conditioned on survival among Bernoulli obstacles[END_REF] and Berestycki and Cerf [START_REF] Berestycki | The random walk penalised by its range in dimensions d ≥ 3[END_REF].

The most relevant regime for us is that of Large Deviations. Many studies of either the Wiener sausage or the random walk culminate with a large deviation principle for the Wiener sausage in dimensions d ≥ 3, proved by van den Berg, den Hollander and Bolthausen [START_REF] Van Den Berg | Moderate deviations for the volume of the Wiener sausage[END_REF]. The result which was adapted by Phetpradap [Phet12] to the random walk setting reads as follows: for any b > 0, if P is the law of the walk,

lim n→∞ 1 n (d-2)/d • log P |R n | -E[|R n |] < -bn = -I d (b), (1.2)
where I d (b) > 0 for any b > 0, and I d has a variational expression in terms of the occupation density of the Brownian motion, which suggests that the walk is localized a time of order n in a ball-like region of volume of order n (we refer to [START_REF] Van Den Berg | Moderate deviations for the volume of the Wiener sausage[END_REF] for a detailed explanation of this heuristic picture). The variational expression of I d also suggests an occupation density of order 1, and the presence of holes of side-length 1 (see again [START_REF] Van Den Berg | Moderate deviations for the volume of the Wiener sausage[END_REF] for an explanation of this). This picture has been popularized under the name Swiss cheese [START_REF] Van Den Berg | Moderate deviations for the volume of the Wiener sausage[END_REF], and is conjecturally linked with the model of Random Interlacements, see [START_REF] Sznitman | On bulk deviations for the local behaviour of random interlacements[END_REF].

Main results. We first estimate the probability of downward moderate deviations in d ≥ 5.

Theorem 1.1. Assume d ≥ 5. There exist positive constants ε, κ d and κ d , such that for any n ≥ 2, and n

d d+2 • (log n) 2d d 2 -4 ≤ ζ ≤ εn, exp -κ d ζ 1-2 d ≤ P (|R n | -E[|R n |] ≤ -ζ) ≤ exp -κ d ζ 1-2 d .
(1.3) Remark 1.2. We believe that the logarithm that appears in the hypothesis on ζ for (1.3) are artefacts of our proofs.

Recall that a Central Limit Theorem in dimension 5 and higher was proved by Jain and Orey [START_REF] Jain | On the range of random walk[END_REF] for |R n |. In particular, they show that the variance of |R n | divided by n converges to σ 2 > 0. We extend their result into a Moderate Deviation principle.

Theorem 1.3. Assume d ≥ 5. For any sequence {ζ n } n≥0 , satisfying lim n→∞ ζ n / √ n = ∞, and
lim n→∞ ζ n (log n) d-2 d+2 /n d d+2 = 0, we have lim n→∞ n ζ 2 n • log P (±(|R n | -E[|R n |]) > ζ n ) = - 1 2σ 2 . (1.4) Remark 1.4. Concerning dimension d = 3, [Chen10
ζ n /( √ n • log 3/4 (n)) = ∞, we have lim n→∞ n 1/3 ζ 2/3 n • log P |R n | -E[|R n |] < -ζ n = -I 1 , (1.5)
with an explicit positive constant I 1 . On the other hand, if lim n→∞ ζ n /( √ n • log 3/4 (n)) = 0, [Chen10, Theorem 8.5.2] shows that the deviations are Gaussian:

lim n→∞ n • log n ζ 2 n • log P ± (|R n | -E[|R n |]) > ζ n = -I 2 , (1.6)
with an explicit positive constant I 2 . Note that the variance of |R n | is of order n log n in d = 3, by [START_REF] Jain | The range of transient random walk[END_REF]. Moderate deviations for the range in d = 2 are analyzed in [START_REF] Bass | Moderate deviations for the range of planar random walks[END_REF] and [START_REF] Chen | Random walk intersections. Large deviations and related topics[END_REF].

Our simple method does provide rougher estimates that we present since our pathwise analysis only depends on them. There exist positive constants ε, κ and κ, such that for any n ≥ 2, and

n 5/7 • log n ≤ ζ ≤ εn, exp -κ (ζ 2 /n) 1/3 ≤ P (|R n | -E[|R n |] ≤ -ζ) ≤ exp -κ (ζ 2 /n) 1/3 . (1.7)
For an explanation of why our techniques cannot reach the Gaussian regime, and more precisely for the reason of this exponent 5/7, see Remark 4.3.

We provide now a description of a typical trajectory conditioned on the deviations. First, recall that the capacity of a set A ⊆ Z d is defined by

Cap(A) := x∈A P x (S n ∈ A, ∀n ≥ 1). (1.8)
Also, given Λ ⊆ Z d , and n ≥ 0, let n (Λ) be the time spent in Λ before time n. Finally, we introduce the following notation: for r > 0, and x ∈ Z d , set

Q(x, r) := [x - r 2 , x + r 2 ) d ∩ Z d ,
and for ρ ∈ (0, 1], and r, n positive integers, we let

C n (r, ρ) := {x ∈ rZ d : n (Q(x, r)) ≥ ρr d }, and V n (r, ρ) := x∈Cn(r,ρ) Q(x, r).
(1.9)

In words, V n (r, ρ) is the region of space where the walk realizes an occupation density above ρ on a space-scale r. Define also for a sequence of values of deviation {ζ n } n∈N ,

ρ typ := ζ n /n if d = 3 1 if d ≥ 5 τ typ := n if d = 3 ζ n if d ≥ 5 and χ d := 5/7 if d = 3 d d+2 if d ≥ 5.
Theorem 1.5. Assume d = 3, or d ≥ 5. There are positive constants α, β, ε, and C 0 , such that for any sequence {ζ n } n∈N satisfying

n χ d • log n ≤ ζ n ≤ εn, (1.10) defining {r n } n∈N by r d-2 n ρ typ = C 0 log n, (1.11) one has lim n→∞ P ( n (V n (r n , βρ typ )) ≥ α τ typ | |R n | -E[|R n |] ≤ -ζ n ) = 1.
(1.12)

Moreover, for some constant A > 0,

lim n→∞ P Cap(V n (r n , βρ typ )) ≤ A|V n (r n , βρ typ )| 1-2 d | |R n | -E[|R n |] ≤ -ζ n = 1.
(1.13) Theorem 1.5 provides some information on the density the random walk has to realize in order to achieve the deviation. We obtain that V n (r n , ρ n ) is typically ball-like, in the sense that its capacity is of the order of its volume to the power 1 -2/d, as it is the case for Euclidean balls.

This result also reflects a very different phenomenology in dimension three and in dimensions larger than four.

• In dimension three, the walk spends a fraction of its total time, independently of ζ n , in a region of volume of order n 2 /ζ n . Note in particular that the volume of the confinement region is a decreasing function of ζ n .

• In dimensions d ≥ 5, the density of the confinement region is of order 1, no matter what ζ n is. Also, note that the region where the walk is confined has volume of order ζ n , which increases with ζ n . Thus, a very tiny fraction of the range folds.

• Note also that the scale r n measures the distance at which we can probe density, and the condition (1.11) is the smallest one can hope, up to constant. Indeed, for any constant c small enough, the simple random walk typically spends a time larger than cr 2 log n in order n/(r 2 log n) cubes of side-length r (recall that the probability to spend a time t in a cube of side r is of order exp(-t/r 2 ), ignoring constants in the exponential). So a density ρ = cr 2-d log n is typical in this respect, and (1.11) simply requires ρ typ being larger than this typical density without constraint.

• Let us quote [START_REF] Van Den Berg | Moderate deviations for the volume of the Wiener sausage[END_REF]: " The central limit theorem is controlled by the local fluctuations, while the [..] deviations are controlled by the global fluctuations". Thus, we establish folding which is somehow a signature of global fluctuations. Note that in a recent preprint, on a related problem, Sznitman [START_REF] Sznitman | On bulk deviations for the local behaviour of random interlacements[END_REF] performs a decomposition of random interlacements into "wavelet" and "undertow" components, which carry "local" versus "longer range" information. This is also present in the approach of [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], and is here expressed for instance in Corollary 4.2 and its proof (see notably the standard decomposition (4.6)).

• In dimension 4, by following our approach, we could show the following. For any n ≥ 2, and

n 2/3 • log n ≤ ζ ≤ εn, exp -κ ζ ≤ P (|R n | -E[|R n |] ≤ -ζ) ≤ exp -κ √ ζ log(n/ζ) ,
with κ and κ two positive constants. It remains open to remove the log, and most interestingly to give some information on the optimal scenario.

New Tools. To put in perspective the present ideas, let us describe the approach of [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF]. The key object with which we measure folding is a set K n (r, ρ), parametrized by a space-scale r and a density ρ, which collects the set of time indices at which, on a scale r, the density is above ρ. In other words,

K n (r, ρ) := {k ≤ n : n (Q(S k , r)) ≥ ρ • r d }. (1.14)
Typically, a random walk has most sites surrounded by a density of order r 2-d in a cube of sidelength r. Thus, folding occurs when observing an abnormally large value of |K n (r, ρ)|, with ρr d-2 large. Our main tool is the following deviation result which weakens the assumption of Lemma 2.4 from [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], and is key in tackling the moderate deviations up to the Gaussian regime.

Theorem 1.6. Assume d ≥ 3. There exist positive constants C 0 and κ, such that for any ρ > 0, r ≥ 1, and n ≥ 2, satisfying ρ • r d-2 ≥ C 0 log n, (1.15) one has for any L ≥ 1,

P |K n (r, ρ)| ≥ L ≤ C exp -κ ρ 2 d L 1-2 d .
Note that as mentioned earlier the condition (1.15) is optimal, up to the constant.

The heart of our approach relies on estimating the probability a random walk realizes a certain density in a certain number of balls of a fixed radius. In the regime of moderate deviation, the number of possible balls is often larger than the reciprocal of the probability of filling a fixed configuration of balls. We reduce the complexity of the set of centers with the following idea (see Lemma 3.2 below for a more general and formal statement).

Lemma 1.7. In any set Λ ⊂ Z d , d ≥ 3, there is a subset U , whose capacity is maximal (of order its volume), and with volume of order |Λ| 1-2/d .

Let us emphasize that the notion of capacity plays a key role here, even though it does not appear in the statement of Theorem 1.6.

From any set Λ we extract a much smaller subset as hard to cover, and this subset has maximal capacity. Lemma 1.7 is useful, when we combine it with an older estimate from [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF] (see Proposition 3.4 below) which states that the probability of filling a region on a given scale, and at a given density ρ, is bounded by exponential of minus its capacity times ρ.

The second idea is as elementary and deals with deviations for the sum of an adapted process. An instance of the result that we use is as follows (see Proposition 4.1 for a more general statement):

Proposition 1.8. There exists a positive constant c such that for any sequence {X i } i∈N of nonnegative random variables adapted to a filtration {F i } i∈N , and almost surely bounded by 1, it holds for any n ≥ 1 and any ζ > 0,

P n i=1 X i > ζ ≤ P n i=1 E[X i | F i-1 ] > cζ + exp(-ζ/2). (1.16)
Thus, without any condition on the variance of the {X i } i∈N , the upward deviation of their sum is comparable to that of a conditioned sum, up to a multiplicative error.

Plan of the paper. Section 2 introduces notation, and recalls useful known results. In Section 3 we prove Theorem 1.6, controlling the size of the sets K n (r, ρ), and for this we first prove a general result, generalizing Lemma 1.7 above, saying that from any finite collection of balls, one can extract a sub-collection whose capacity is of maximal order in a certain sense. Section 4 transfers the deviation estimate from the range to a double sum over Green's function. Section 5 is the technical heart of the paper, and treats the deviation of the double sum over Green's function, leading to the proofs of the upper bounds in (1.3) and (1.7). The lower bounds are proved in Section 6. Finally Section 7 deals with the Gaussian regime and the proof of Theorem 1.3.

Notation and basic results

In this section, we introduce further notation, and recall Lemma 2.1 from [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF].

We discuss only d ≥ 3 in this study. For z ∈ Z d , We denote by P z the law of the simple random walk starting at z, and simply by P when z = 0. Green's functions read as follows. For z ∈ Z d ,

G(z) := E ∞ n=0 1{S n = z} , and ∀T ∈ N, G T (z) := E T n=0 1{S n = z} . (2.1)
In particular, if R ∞ is the range over period [0, ∞),

P(z ∈ R ∞ ) ≤ G(z) and P(z ∈ R T ) ≤ G T (z). (2.2)
The following asymptotic is well known (see Theorem 4.3.1 of [START_REF] Lawler | Random walk: a modern introduction[END_REF]):

G(z) = O 1 z d-2 ,
(2.3) with • the Euclidean norm. Another result we should need concerns the sum of G T in a region of space with prescribed density. For this purpuse, we introduce the local times. For n ∈ N ∪ {∞}, and Λ ⊆ Z d , we write

n (Λ) := n k=0 1{S k ∈ Λ}.
We quote a result which involves no randomness, but we state it in this form which we use later.

Lemma 2.1 ([AS17], Lemma 2.2). Assume that for some K ⊆ {1, . . . , n}, and r ≥ 1,

n (Q(S k , r)) ≤ ρr d , for all k ∈ K.
Then for some constant C > 0 (independent of r and K), for any z ∈ Z d ,

k∈K : S k / ∈Q(z,r) G T (S k -z) ≤ Cρ T.
(2.4)

The following connection between capacity and Green's function is useful. For any finite Λ

⊂ Z d , Cap (Λ) • sup y∈Z d E y [ ∞ (Λ)] ≥ |Λ|. (2.5)
This is a simple consequence of a last exit decomposition (see Proposition 4.6.4 in [START_REF] Lawler | Random walk: a modern introduction[END_REF]). First, for A ⊆ Z d , we denote by

H A := inf{n ≥ 0 : S n ∈ A}, and
H + A := inf{n ≥ 1 : S n ∈ A},
respectively the hitting time of A and the first return time to A. Then, for any x ∈ Λ,

1 = P x (H Λ < ∞) = y∈Λ G(y -x)P y (H + Λ = ∞).
Summing over x ∈ Λ, gives

|Λ| = y∈Λ P y (H + Λ = ∞) x∈Λ G(y -x) = y∈Λ P y (H + Λ = ∞) • E y [ ∞ (Λ)],
and (2.5) follows using (1.8).

We denote the range between two times m ≤ n, as R[m, n] := {S m , . . . , S n }. We recall that by the inclusion-exclusion formula, one has for any integers n and m,

|R n+m | = |R n | + |R[n, n + m]| -|R n ∩ R[n, n + m]|. (2.6)
If we write f g, when f /g is bounded from above and below by positive constants, one has

E[|R n ∩ R[n, 2n]|] E[|R n ∩ R[n, ∞)|]    √ n if d = 3 log n if d = 4 1 if d ≥ 5.
(2.7)

We now recall asymptotics on the variance of the range (see [START_REF] Jain | On the range of random walk[END_REF][START_REF] Jain | The range of transient random walk[END_REF]).

Lemma 2.2. In dimension three var(

|R n |) = O(n log n), and for d ≥ 4, var(|R n |) = O(n).

Main Tools

We present here the proof of Theorem 1.6. As a byproduct we obtain that on the event where the size of the set K n (•, •) (see (1.14)) is large, the time spent in a related set V n (•, •), as in (1.9), is also large. Namely, we get the following result which enters the proof of Theorem 1.5.

Proposition 3.1. For any A > 0, there exist α > 0, such that for any n ≥ 1, L ≥ 1, r ≥ 1, ρ > 0,

P |K n (r, ρ|) ≥ L, n (V n (r, 2 -d ρ)) ≤ αL ≤ exp(-Aρ 2/d L 1-2/d ).
Before we come to the proofs, let us first introduce useful tools and notation. For r > 0, we define

A(r) := {C ⊂ Z d : |C| < ∞, x -y ∞ > 2r for all x = y ∈ C},
where • ∞ is the sup-norm. One reason for the choice of a separation of 2r is that if x, y, z

∈ Z d with overlapping cubes Q(x, r) ∩ Q(y, r) = ∅ and Q(x, r) ∩ Q(z, r) = ∅, then z -y ∞ ≤ 2r.
The first step towards the proof of Theorem 1.6 is the following result.

Lemma 3.2. There exists a constant κ ∈ (0, 1), such that for any r ≥ 1 and any C ∈ A(r), there exists U ⊆ C, satisfying

κ|C| 1-2 d ≤ |U | ≤ |C| 1-2 d , and
Cap (∪ x∈U Q(x, r)) ≥ κr d-2 |U |. (3.1)
Proof. The lower bound on the capacity follows from recalling (2.5), and observing the following fact. There exists C > 0, such that for any finite C ∈ A(r), there exists U ⊆ C, satisfying

1 2 d |C| 1-2 d ≤ |U | ≤ |C| 1-2 d
, and sup

y∈Z d E y [ ∞ (∪ x∈U Q(x, r))] ≤ Cr 2 . (3.2)
Indeed, define first R := r|C| 2/d 2 , and then recursively a sequence (z i ) i=1,...,N , of elements of C, such that the cubes Q(z i , R/2), i = 1, . . . , N , are disjoint, and the union of the cubes

Q(z i , R) contains C. Note that in this case ∪ x∈C Q(x, r) is contained in ∪ i≤N Q(z i , 2R),
∈ Z d , E y [ ∞ (∪ x∈U Q(x, r))] = x∈U z∈Q(x,r) E y [ ∞ (z)] = x∈U z∈Q(x,r) G(z -y) ≤ Cr 2 + C r d R d-2 |U | 2/d ,
where in the last inequality, the first term comes from summing the Green's function over cubes at distance smaller than r from y, and the second term from summing over the other cubes and using rearrangement (the sum is maximized when the cubes are concentrated in a larger cube centered at y). Then the result follows using (3.2) and the definition of R.

An important consequence of the previous lemma is the following result.

Proposition 3.3. There exist positive constants C 0 and κ, such that for any r ≥ 1, ρ > 0, m ≥ 1, n ≥ 1, satisfying the condition ρr d-2 ≥ C 0 log n, one has

P ∃C ∈ A(r) : |C| = m, and n (Q(x, r)) ≥ ρr d for all x ∈ C ≤ C exp -κρ(mr d ) 1-2 d .
The proof of this proposition is based on Lemma 3.2 and an analogous result from [AS17]:

Proposition 3.

([AS17]

). There exist positive constants C and κ, such that for any ρ > 0, r ≥ 1, C ∈ A(r), and n ≥ 1, one has

P n (Q(x, r)) ≥ ρr d for all x ∈ C ≤ C(n|C|) |C| exp -κρ Cap( x∈C Q(x, r)) . (3.3)
Remark 3.5. Recall that one has the general lower bound Cap (Λ) ≥ c|Λ| 1-2/d , with c > 0 some constant. Thus in the previous proposition, the term in the exponential is also at least of the order of (|C|r d ) 1-2/d , as in Proposition 3.3, and it is the largest bound one obtains without additional knowledge on the set C. Therefore the main input of our new Proposition 3.3 when compared to Proposition 3.4 is that the combinatorial term in front of the exponential has been removed. This is of crucial importance in proving Theorem 1.6.

Proof of Proposition 3.3. Applying Lemma 3.2, we see that from any set C ∈ A(r) with cardinality m, one can extract a subset U ⊆ C, satisfying (3.1). In particular its cardinality is of order m 1-2/d , and thus the number of possible choices for such set U in [-n, n] d is at most exp(dm 1-2/d log 2n).

It suffices then to use the lower bound on the capacity in (3.1) and apply Proposition 3.4 for such U , since by the hypothesis (1.15) all the combinatorial factors can be absorbed in the exponential bound given by (3.3).

We arrive now to the proof of Theorem 1.6. As an intermediate step, we prove the same result for the sets K * n (r, ρ) defined by:

K * n (r, ρ) := {k ≤ n : ρr d ≤ n (Q(S k , r)) < 2ρr d }.
Lemma 3.6. There exist positive constants C 0 and κ, such that for any ρ > 0, r ≥ 1, and n ≥ 2, satisfying ρ r d-2 ≥ C 0 log n, one has for any L ≥ 1,

P |K * n (r, ρ)| ≥ L ≤ C exp -κ ρ 2 d L 1-2 d .
Proof of Theorem 1.6. Observe that

{|K n (r, ρ)| ≥ L} ⊆ i≥0 |K * n (r, 2 i ρ)| ≥ c L 2 i d-2 , with c := 1/(1 -2 -1 d-2 ). (3.4)
Then a union bound and Lemma 3.6 give

P |K n (r, ρ)| ≥ L ≤ i≥0 C • exp -κ2 i d • ρ 2/d L 1-2/d ,
proving the result (with some possibly different constants κ and C).

It remains to prove Lemma 3.6.

Proof of Lemma 3.6. We claim that on the event

{|K * n (r, ρ)| ≥ L}, there is a subset C ∈ A(r), such that (i) |C| ≥ 1 2 • 4 d • L ρr d , and (ii) n (Q(x, r)) ≥ ρr d , ∀x ∈ C. (3.5)
To see this, consider k 1 := inf K * n (r, ρ), and define inductively for i ≥ 1,

k i+1 := inf K * n (r, ρ)\{k : S k ∈ j≤i Q(S k j , 2r)},
with the convention that k i+1 = ∞, when the set above is empty. Note that by definition of K * n (r, ρ), for any x ∈ Z d , one has

|Q(x, r/2) ∩ {S k : k ∈ K * n (r, ρ)}| ≤ 2ρr d .
Thus for each i, such that k i ≤ n, one can tile up the cube Q(S k i , 2r) with at most 4 d cubes of length r/2, and deduce that

|Q(S k i , 2r) ∩ {S k : k ∈ K * n (r, ρ)}| ≤ 4 d • 2ρr d .
Now, we define C as the set containing all the S k i , with k i finite. By construction, on the event {|K * n (r, ρ)| ≥ L}, (3.5) holds. Note now that if ρr d-2 ≥ C 0 log n, then the hypothesis of Proposition 3.3 is satisfied, and we get

P (|K * n (r, ρ)| ≥ L) ≤ P ∃C ∈ A(r) : |C| ≥ 1 2 • 4 d • L ρr d , and n (Q(x, r) ≥ ρr d for all x ∈ C ≤ C exp -κρ L 2 • 4 d ρ 1-2/d ≤ C exp(-κ ρ 2/d L 1-2/d ),
with κ > 0 some other constant, proving the lemma.

Finally we give a proof of Proposition 3.1.

Proof of Proposition 3.1. Define for n ≥ 1, ρ > 0, L > 0, and r ≥ 1,

A n (r, ρ, L) := ∃C ∈ A(r) : |C| ≥ L ρr d and n (Q(x, r)) ≥ ρr d ∀x ∈ C .
Suppose A n (r, ρ, L) holds. Consider the random C which realizes this event. For x ∈ C, there exists z ∈ rZ d , such that Q(x, r) ∩ Q(z, r) = ∅, and n (Q(z, r)) ≥ 2 -d ρr d . This is because the cube Q(x, r) intersects at most 2 d neighboring cubes with centers in rZ d . Note that by definition of A n (r, ρ, L), this site z cannot be chosen by another site of C. Thus, using notation C n as defined in (1.9), one has

A n (r, ρ, L) ⊆ {|C n (r, 2 -d ρ)| ≥ L ρr d } ⊆ { n (V n (r, 2 -d ρ)) ≥ 2 -d L}.
(3.6) Note now that (3.5) yields for any r ≥ 1, ρ > 0, and L ≥ 1,

{|K * n (r, ρ)| ≥ L} ⊆ A n (r, ρ, L 2 • 4 d ).
In particular, for any integer i ≥ 0 and any c > 0,

{|K * n (r, 2 i ρ)| ≥ cL 2 i d-2 } ⊆ A n (r, 2 i ρ, cL 2 1+2d+ i d-2 ) ⊆ A n (r, ρ, Lα i ), with α i := c 2 1+2d+i(1+ 1 d-2 ) . (3.7)
Note that by definition when L ≤ L , one has A n (r, ρ, L ) ⊆ A n (r, ρ, L). Thus (3.4) and (3.7) imply that for any integer i * , there exists α > 0, small enough so that for any r ≥ 1, ρ > 0, and L ≥ 1,

{|K n (r, ρ)| ≥ L} ∩ A c n (r, ρ, αL) ⊆ i≥i * {|K * n (r, 2 i ρ)| ≥ c L 2 i d-2 }.
Using next Lemma 3.6, we deduce that for any A > 0, there exists α > 0, such that

P (|K n (r, ρ)| ≥ L, A c n (r, ρ, αL)) ≤ exp(-Aρ 2/d L 1-2/d ).
Together with (3.6), this concludes the proof of the proposition.

Transferring Deviations to the Corrector

We present here a general concentration result that allows to express downward deviations for the centered volume of the range, as upward deviations for a so-called corrector term which reads, for a time-scale T ,

n k=0 x∈R k 1 T G T (x -S k ). (4.1)
Our main result replaces the Doob-type martingale decomposition of [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], and has the important novelty that it no more requires some delicate bounds on the conditional variance of the intersection of two ranges. This is crucial in choosing the time scale T , which impacts the size of the moderate deviations we cover. Our result is a consequence of the following fact, generalizing Proposition 1.8.

Proposition 4.1. There exists a positive constant c such that for any sequence {X i } i∈N of nonnegative random variables adapted to a filtration {F i } i∈N , and almost surely bounded by 1, it holds for any T ≥ 1, n ≥ T , and ζ > 0,

P 1 T n i=T X i > ζ ≤ P 1 T n i=T E[X i | F i-T ] > cζ + exp(-ζ/2).
When applied to the size of the range, and using a classical decomposition that we shall recall later, we obtain the following corollary (with σ T := T in dimension d ≥ 4, and σ T := T log T in dimension d = 3).

Corollary 4.2. There exists a positive constant c, such that for any n ≥ 1, any 2 ≤ T ≤ n, and any ζ > n/σ T ,

P (|R n | -E[|R n |] ≤ -ζ) ≤ 2T exp(-c ζ T ) + P   n k=0 x∈R k 1 T G T (x -S k ) ≥ cζ   . (4.2)
Remark 4.3. In dimension 3, the mean of the sum

n k=0 x∈R k 1 T G T (x -S k ), is of order n/ √ T .
Thus the second term in the right-hand side of (4.2) starts to decay only for ζ > n/ √ T . On the other hand, for the first term to be of the right order, one needs to take T at most of order (ζn) 1/3 . This imposes the condition ζ > n 5/7 (up to constant), and explains why our techniques cannot cover the whole non Gaussian regime in dimension 3. Proposition 4.1 is based on three simple facts that we have gathered in three lemmas.

Lemma 4.4. Let Z be some nonnegative random variable bounded by 1, and G be a σ-field. There exists a positive constant κ * , independent of Z and G, such that almost surely

E exp Z -κ * E[Z | G] | G ≤ 1.
Proof. Set g(t) = (e t -1 -t)/t 2 , and observe that

E[exp(Z) | G] = 1 + E[Z | G] + E[Z 2 g(Z) | G].
Note then that on R + , the function g is increasing, and positive so that 0 ≤ g(Z) ≤ g(1). Thus, defining κ * := 1 + g(1), we have

E[exp(Z) | G] ≤ 1 + κ * E[Z | G] ≤ exp(κ * E[Z | G]).
This concludes the proof.

We now extend this result to a sum of random variables adapted to some filtration. Lemma 4.5. Let {Z i } i∈N be adapted to some filtration {G i } i∈N , and such that for each i ∈ N, almost surely 0 ≤ Z i ≤ 1. Then for any n ≥ 1,

E exp n i=1 Z i -κ * n i=1 E[Z i | G i-1 ] ≤ 1. (4.3)
Proof. The proof is immediate by induction. Indeed, the result for n = 1 is exactly Lemma 4.4. Assuming now that (4.3) holds for some n, we get the result at time n + 1, by first applying Lemma 4.4 to Z n+1 and G n , and then by using the induction hypothesis.

Proposition 4.1 requires one more step, which is the content of the next lemma.

Lemma 4.6. Let {S j } j∈N and { S j } j∈N be two sequences of random variables, such that

E[exp S j -S j ] ≤ 1, ∀j ∈ N.
Then, for any integer T , and any ζ > 0,

P   1 T T j=1 S j > ζ   ≤ e -ζ/2 + P   1 T T j=1 S j > ζ 2   .
Proof. It suffices to observe that by Jensen's inequality,

E   exp 1 T T j=1 (S j -S j )   ≤ 1 T T j=1 E exp S j -S j ≤ 1.
Then the result follows by a union bound and Chebyshev's exponential inequality.

We are now ready to prove Proposition 4.1.

Proof of Proposition 4.1. Let us assume to simplify notation that n is of the form n = mT -1, for some integer m ≥ 2, and leave the necessary (minor) changes to the proof to the reader for a general n. For j = 0, . . . , T -1, define

S j := m-1 i=1
X j+iT , and

S j := κ * m-1 i=1 E[X j+iT | F j+(i-1)T ],
with the same constant κ * as in Lemma 4.4. Note first that by applying Lemma 4.5, for any fixed 0 ≤ j ≤ T -1, with Z i = X j+iT , and G i := F j+iT , we get that

E[exp(S j -S j )] ≤ 1,
for any 0 ≤ j ≤ T -1. Then the proposition follows from Lemma 4.6, taking c = 1/(2κ * ).

Proof of Corollary 4.2. First note that if ζ ≤ 2T , then (4.2) holds for any constant c > 0 such that exp(2c) ≤ 2T . Thus henceforth, we assume that ζ > 2T .

For positive integers T, j and k with T ≤ n, j < T , and k ≤ K := n/T , let

I j k := [j + (k -1)T, j + kT -1]. Thus, I j k is a subinterval of [0, n + T -1] of length T .
We now iterate (2.6) to obtain for any j < T ,

|R(I j 1 ∪ • • • ∪ I j K )| = K k=1 |R(I j k )| - K-1 k=1 |R(I j 1 ∪ • • • ∪ I j k ) ∩ R(I j k+1 )|. (4.4)
The decomposition (4.4) is our basic tool here, and already appears in Equation (1.p) of [START_REF] Gall | Propriétés d'intersection des marches aléatoires. I. Convergence vers le temps local d'intersection[END_REF].

Note that if we define ε(T ) by To simplify further notation, set for 0 ≤ j ≤ T -1,

ε(T ) := |R n | - 1 T T -1 j=0 |R(I j 1 ∪ • • • ∪ I j K )|, ( 4
U j := K k=1 |R(I j k )| -E[|R(I j k )|],
and for i ≥ T ,

X i := 1 T • |R[0, i -T ] ∩ R[i -T + 1, i]|.
Note that each U j is a sum of K independent and identically distributed centered random variables. Note also that for each i, X i is F i -measurable with F i := σ(S 1 , . . . , S i ). Now by using that (4.4) holds also in expectation, together with the facts that X i ≥ 0, and |ε(T

) -E[ε(T )]| ≤ T , we get |R n | -E[R n ] ≥ 1 T T -1 j=0 U j - T K-1 i=T X i + ε(T ) -E[ε(T )] ≥ 1 T T -1 j=0 U j - n+T i=T X i -T.
Since we have assumed that ζ > 2T , we obtain

P (|R n | -E[|R n |] ≤ -ζ) ≤ P   1 T T -1 j=0 U j ≤ - ζ 4   + P n+T i=T X i ≥ ζ 4 . (4.6)
The first term on the right hand side of (4.6) is dealt with a union bound, and then Bernstein's inequality together with Lemma 2.2:

P   1 T T -1 j=0 U j ≤ - ζ 4   ≤ T -1 j=0 P U j ≤ - ζ 4 ≤ T exp(-c ζ T ).
The second term on the right hand side of (4.6) is dealt with applying Proposition 4.1, and noting that by definition 0 ≤ X i ≤ 1, for all i.

P n+T i=T X i ≥ ζ 4 = P 1 T n+T i=T X i ≥ ζ 4T ≤ exp(- ζ 8T ) + P n+T i=T E[X i | F i-T ] ≥ cζ .
To conclude, observe that by translation invariance of the law of the walk, and the Markov property, for any i ≥ T ,

E[X i | F i-T ] ≤ 1 T x∈R i-T G T (x -S i-T ),
and thus,

n+T i=T E[X i | F i-T ] ≤ 1 T n i=0 x∈R i G T (x -S i ).
This concludes the proof of the corollary.

5 Upper bounds in (1.3) and (1.7) and proof of Theorem 1.5

In this section, we prove the upper bounds in (1.3) and in (1.7), as well as Theorem 1.5 (admitting for a moment the lower bounds in Theorem 1.1 and in (1.7), which we prove later using an independent argument). The problem here is of estimating deviation of the corrector (4.1). The strategy we follow is naive: we decompose space into level sets of the local times, and estimate each contribution to Green's function. However, there is a twist: in our multi-scale analysis, space-scale and occupation density are linked through (1.15).

Dimensions Five and Larger

We assume here that d ≥ 5. We fix in this whole subsection the value of T as

T := c 2κ • ζ 2/d , (5.1)
where κ is as in Theorem 1.1, and c as in Corollary 4.2, so that the factor exp(-cζ/T ) appearing in the latter is negligible compared to the lower bound estimate for the probability of the event

{|R n | -E[|R n |] ≤ -ζ}.
Note that with this definition of T , the hypotheses of Corollary 4.2 are satisfied for any ζ > n d d+2 log n, and n large enough.

Then for i ≥ 1 we consider ρ i := 2 -i+1 , and define the associated length-scale r i by

ρ i • r d-2 i = C 0 log n, (5.2)
with the same constant C 0 as in (1.15). The length r i is the smallest scale on which we can probe density ρ i .

Recall the definition of K n (r, ρ) in (1.14). Then, define K1 := K n (r 1 , ρ 1 ), and for i ≥ 2,

Ki = K n (r i , ρ i )\ j<i K n (r j , ρ j ).
Note that, the peculiarity of Ki , for i > 1, is that for any k ∈ Ki , the time spent on Q(S k , r i-1 ) is less than ρ i-1 r d i-1 . Now for A > 0, δ > 0, and I ≥ 1 integer, we define

E(A, δ, I) :=   1≤i≤I | Ki | ≤ δL i   ∩ i>I | Ki | ≤ AL i , with L i := ζ ρ 2/(d-2) i , ∀i ≥ 1.
We state now the main result of this subsection, and then explain how it implies both the upper bound in (1.3) and Theorem 1.5 (for the case d ≥ 5).

Proposition 5.1. There exists a constant C 0 > 0, such that the following holds. For any A > 0, there exist an integer I ≥ 1, and δ > 0, such that for any C 0 n

d d+2 • (log n) 2d d 2 -4 ≤ ζ ≤ n, E(A, δ, I) ⊆    n k=0 x∈R k 1 T G T (x -S k ) ≤ ζ    .
Proof of the upper bound in (1.3). Consider the constants δ and I, which are associated to A = 1 in Proposition 5.1. Using Theorem 1.6 and a union bound, we get for any ζ ≥ log n,

P(E(1, δ, I) c ) ≤ C exp(-κζ 1-2/d ),
for some positive constants C and κ (note that the number of indices i, such that Ki is nonempty is at most of order log n). Then the result follows from Corollary 4.2 and Proposition 5.1, using the definition (5.1) of T .

Proof of Theorem 1.5. We assume here the lower bound in (1.3), and start with the proof of (1.12). By (the proof of) Corollary 4.2, and our choice of T in (5.1), one can see that for any sequence {ζ n } n≥1 satisfying ζ n > n log n T , one has for some constant c > 0,

lim n→∞ P   n k=0 x∈R k 1 T G T (x -S k ) ≥ cζ n | |R n | -E[|R n |] ≤ -ζ n   = 1.
Next, by Theorem 1.6 and the lower bound in (1.3) of Theorem 1.1, one can choose A large enough, so that lim

n→∞ P ∪ i≥1 {| Ki | ≥ AL i } | |R n | -E[|R n |] ≤ -ζ n = 0.
Then consider the parameters δ and I associated to this constant A in Proposition 5.1. Applying this proposition, we get

lim n→∞ P ∪ 1≤i≤I {| Ki | ≥ δL i } | |R n | -E[|R n |] ≤ -ζ n = 1.
Now observe that for any i ≤ I, one has

K n (r i , ρ i ) ⊆ K n (r I , 2 2 d-2 (i-I) ρ I ).
We deduce that

lim n→∞ P |K n (r I , 2 -2 d-2 I ρ I )| ≥ δζ n | |R n | -E[|R n |] ≤ -ζ n = 1,
and then (1.12) follows from Proposition 3.1.

Finally the characterization of the capacity in (1.13), is a simple consequence of a general result [START_REF] Asselah | Random walk, Local times, and subsets maximizing capacity[END_REF], namely (1.15) of Theorem 1.5, once we know (1.12).

Proof of Proposition 5.1. Define K∞ := {0, . . . , n} \ ∪ i≥1 Ki .

Note that by definition one can write the set of integers smaller than n as the disjoint union:

{0, . . . , n} = K∞ ∪ ( i≥1 Ki ).
Thus one has

n k=0 x∈R k 1 T G T (x -S k ) ≤ Σ 1 + Σ 2 + Σ 3 + 2Σ 4 + Σ 5 , (5.3)
with

Σ 1 := k∈ K1 x∈R k 1 T G T (x -S k ), Σ 2 := i≥2 k∈ Ki k ∈ K1 1 T G T (S k -S k )1{S k / ∈ Q(S k , r i-1 )}, Σ 3 := i≥2 k∈ Ki x∈R k 1 T G T (x -S k )1{x ∈ Q(S k , r i-1 )}, Σ 4 := i≥2 k∈ Ki j≥i k ∈ Kj 1 T G T (S k -S k )1{S k / ∈ Q(S k , r i-1 )},
and Σ 5 :=

k∈ K∞ x∈R k 1 T G T (x -S k ).
(5.4) First, by definition of G T , one has z∈Z d 1 T G T (z) = 1. Thus, on E(A, δ, I), with δ ≤ 1/5,

Σ 1 ≤ | K1 | ≤ ζ/5.
By definition when k ∈ Ki and i > 1, the time spent in Q(S k , r i-1 ) is smaller than ρ i-1 r d i-1 , so that by Lemma 2.1, for some constant C > 0,

Σ 2 ≤ | K1 | sup z i≥2 k∈ Ki 1 T G T (S k -z)1{S k / ∈ Q(z, r i-1 )} ≤ C| K1 | i≥2 ρ i-1 ≤ 2C| K1 | ≤ ζ/5,
choosing δ small enough for the last inequality. We consider now k ∈ Ki for i ≥ 2, and note that by definition of Ki , we have a bound on the time spent in concentric shells centered around S k , inside Q(S k , r i-1 ). Thus, bounding i | Ki | by n + 1, we obtain Σ 3

(2.3) ≤ C i≥2 | Ki | i-1 j=1 ρ j r d j T r d-2 j (5.2) ≤ C i≥2 | Ki | i-1 j=1 log n T r d-4 j ≤ C n log n T r d-4 1 (5.2) ≤ C n(log n) 2 d-2 T .
Using next the hypothesis on ζ with the constant C 0 large enough, we get

Σ 3 ≤ ζ/5.
The same argument gives as well for n large enough,

Σ 5 ≤ Cn T    r 2 1 + j≥1 ρ j r d j r d-2 j    ≤ C n(log n) 2 d-2 T ≤ ζ/5,
bounding simply | K∞ | by n + 1, and using for the first inequality that the sum of the Green's function over all points in Q(0, r 1 ) is of order r 2 1 , by (2.3). Finally, for any 2 ≤ i ≤ j, when k ∈ Kj , the time spent on cubes at scale r i-1 around such S k , is smaller than ρ i-1 . Thus for a constant C > 0, using again Lemma 2.1,

Σ 4 ≤ C i≥2 | Ki |ρ i-1 ,
so that on the event E(A, δ, I),

Σ 4 ≤ Cζ   δ 1≤i≤I ρ d-4 d-2 i-1 + A i>I ρ d-4 d-2 i-1   ≤ ζ 10 ,
by taking first I large enough, and then δ small enough. Altogether, this proves the proposition.

Dimension Three

We assume here that d = 3, and for the same reason than in higher dimension, we choose T as

T := c 2κ • (ζn) 1/3 ,
with κ as in (1.7), and c as in Corollary 4.2. Then, we recall that ρ i = 2 -i+1 , for i ≥ 1, and define r i similarly as in higher dimension (with C 0 as in (1.15)), by r i ρ i = C 0 • log n. We define I to be the smallest integer such that ρ I ≤ c 0 ζ/n, with a constant c 0 that will be fixed in the proof of Proposition 5.2. Note that ζ/n is the correct order of the density of the range we are expecting under the event {|R n | -E[|R n |] < -ζ}. Note also that when ζ ≥ n 5/7 • log n, then r I ≤ C √ T , for some constant C > 0. Now we keep the same definition for Ki as in higher dimension, but only for 1 ≤ i < I, and we set KI := {0, . . . , n}\ j<I K n (r j , ρ j ).

For A > 0, δ > 0, and 1 ≤ J ≤ I -1, an integer, we set

E(A, δ, J) :=   I-J≤i≤I-1 {| Ki | ≤ δL i }   ∩ i<I-J {| Ki | ≤ AL i } , with L i := ζ 2 nρ 2 i , ∀i ≥ 1.
Our main result in this subsection reads as follows.

Proposition 5.2. For any A > 0, there exist δ > 0, and an integer 1 ≤ J ≤ I -1, such that for any n ≥ 2, and any

n 5/7 • log n ≤ ζ ≤ n, E(A, δ, J) ⊆    n k=0 x∈R k 1 T G T (x -S k ) ≤ ζ    .
We note that exactly as in higher dimension, one can deduce from this proposition the upper bound in (1.7), as well as Theorem 1.5, for the case d = 3.

Proof. We proceed as in higher dimension, and write

n k=0 x∈R k 1 T G T (x -S k ) ≤ Σ 1 + Σ 2 + Σ 3 + 2Σ 4 ,
with the (Σ k ) 1≤k≤4 as in (5.4) except that we take only a sum over i running up to I. Now we assume that δ < 1/4, and if ζ > n/(4A), we set J = I -1. Thus in all cases, one has | K1 | ≤ ζ/4, on the event E(A, δ, J). It follows that on this event

Σ 1 ≤ | K1 | ≤ ζ/4. (5.5)
The term Σ 2 is treated as in higher dimension. Concerning Σ 3 , we note that for any k ∈ Ki , with i ≥ 2, one has

x∈R k 1 T G T (S k -x)1{x ∈ Q(S k , r i-1 )} ≤ C i-1 =1 ρ r 2 T ≤ Cρ i ,
using that r 2 ≤ CT , for all . Therefore,

Σ 3 ≤ C I i=1 | Ki |ρ i .
Bounding simply | KI | by n + 1, we get that on the event E(A, δ, J), with the constant c 0 from the definition of ρ I ,

I i=1 | Ki |ρ i ≤ ζ A I-J i=1 ρ I ρ i + δ I-J<i<I ρ I ρ i + c 0 ≤ ζ(A2 -J+1 + 2δ + c 0 ).
Thus by taking J large enough, and then δ and c 0 small enough, we obtain Σ 3 ≤ ζ/8 . An argument as in the proof of Proposition 5.1 shows that one has as well

Σ 4 ≤ C I i=1 | Ki |ρ i ≤ ζ/8.
This concludes the proof of the proposition.

6 Lower bounds in (1.3) and (1.7)

We prove here the lower bounds in 1.3 and (1.7). We start with the case of dimension 5 and more which is the easiest.

Dimensions Five and larger

In this case we obtain the following. Note that the result covers a slightly larger range of values for ζ than in the statement of Theorem 1.1 (the logarithmic factor can be removed).

Proposition 6.1. Assume d ≥ 5. There exist positive constants ε, K and κ, such that for any n ≥ 2 and any Kn

d d+2 ≤ ζ ≤ εn, one has P (|R n | -E[|R n |] ≤ -ζ) ≥ exp -κ • ζ 1-2 d .
Proof. The argument is the same as in [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], but for convenience let us briefly recall it. The idea is to force one piece of the walk to localize in a small cube of volume ζ. More precisely, set m := 3 γ d ζ . Note first that by (2.6) and (2.7), one has

|R n | -E[|R n |] ≤ |R m | -E[|R m |] + Y, with Y := |R[m, n]| -E[|R[m, n]|] + O(1).
Note also that Y is independent of R m and that on the event

E := {R m ⊆ Q(0, ζ 1/d )}, one has |R m | ≤ |Q(0, ζ 1/d )| = ζ. Furthermore, it is well known (see Theorem 1 in [DE51]) that |E[|R m |] -γ d m| = O( √ m).
Thus on the event E ∩ {Y ≤ 0}, at least for ζ large enough,

|R n | -E[|R n |] ≤ -ζ.
Now, it is well known that P(E) ≥ exp(-κ • ζ 1-2/d ), for some constant κ > 0. By choosing ε such that n -m ≥ n/2, and then using the Central Limit Theorem for the volume of the range [JP71, JO69], we deduce that at least for n large enough, P(Y ≤ 0) ≥ 1/4. Since Y and E are independent, this concludes the proof.

Dimension three

Our result covers here as well a larger range of values for ζ than in (1.7) (recall however, that in dimension 3 a more general and more precise asymptotic is proved in [Chen10, Theorem 8.5.2]).

Proposition 6.2. Assume d = 3. There exist positive constants ε, κ, and K, such that for any n ≥ 2, and any Kn 2/3 ≤ ζ ≤ εn, one has

P (|R n | -E[|R n |] ≤ -ζ) ≥ exp(-κ • ( ζ 2 n ) 1/3 ).
Proof. One can use also the same argument as in [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF]. Since the proof is quite long, let us only give the main steps, and simply refer to [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF] for details.

Set m := n/2 , and note that (2.6) and (2.7) now give,

|R n | -E[|R n |] ≤ |R m | -E[|R m |] + |R[m, n]| -E[|R[m, n]|] -|R m ∩ R[m, n]| + O( √ n).
We consider next the event E := {R m ⊆ Q((n 2 /ζ)1/3 )}, whose probability is of the right order, since for some constant κ,

P(E) ≥ exp(-κ n (n 2 /ζ) 2/3 ) = exp(-κ • (ζ 2 /n) 1/3 ).
Moreover, by the results of [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], one has for some constant c > 0, Remark 6.3. We note that rough upper bounds (sufficient for the proof above) for upward moderate deviations of the range can also be obtained using soft arguments, so we do not really need to rely on any result of [START_REF] Chen | Random walk intersections. Large deviations and related topics[END_REF]. More details are given in [START_REF] Asselah | Moderate deviations for the capacity of the range[END_REF] (which concerns the capacity of the range, instead of the volume, but the argument works the same in both cases).

P(|R m | ≤ γ d 2 m) ≤ exp(-cn 1/3 ),

The Gaussian Regime

We deal here with the Gaussian regime and prove Theorem 1.3. We start with recalling some preliminary estimates from the literature in the next subsection. Then we prove Theorem 1.3 in Subsection 7.2.

Preliminary results

We first state an instance of Gärtner-Ellis' Theorem (see Theorem 2.3.6 in [START_REF] Dembo | Large deviations techniques and applications[END_REF]).

Theorem 7.1 (Gärtner-Ellis). Let {X n } n≥0 be a sequence of real random variables. Assume that for a sequence {b n } n≥0 going to infinity, and for any θ ∈ R,

lim n→∞ 1 b n log E[exp(θb n • X n )] = σ 2 2 • θ 2 .
Then, for any λ > 0,

lim n→∞ 1 b n log P(X n > λ) = - λ 2 2σ 2 .
The second result we shall need concerns large deviations for random variables with stretched exponential tail.

Theorem 7.2 (A. Nagaev [START_REF] Nagaev | Integral limit theorems for large deviations when Cramer's condition is not fulfilled (Russian)I[END_REF]). Let {Y n } n≥0 be a sequence of centered random variables, such that E[exp(κ|Y 1 | α )] < ∞, for some constants κ > 0, and α ∈ (0, 1]. Then there are positive constants c and C, such that for any n ≥ 1 and any t > n

In fact the result in [START_REF] Nagaev | Integral limit theorems for large deviations when Cramer's condition is not fulfilled (Russian)I[END_REF] (which is also quoted in [Na79, Equation (2.32)]) concerns centered random variables with variance 1 and tail distribution equal to P(Y 1 > t) = exp(-κt α )(1 + o(1)), for t large enough, but one can easily deduce Theorem 7.2 from it using stochastic domination.

To be able to use this result in our case, we need to control the moments of the cross-term, and for that we use a recent result from [START_REF] Asselah | Large Deviations for Intersections of Random Walks[END_REF], which strengthens the previous bound of [START_REF] Khanin | Loop condensation effects in the behavior of random walks[END_REF].

Theorem 7.3 ([AS20b]). Assume that d ≥ 5. Let R ∞ and R ∞ be the ranges of two independent simple random walks on Z d . There exists a constant κ > 0, such that

E exp κ • |R ∞ ∩ R ∞ | 1-2 d < ∞.

Proof of Theorem 1.3

We recall a standard decomposition for the volume of the range, already present in [START_REF] Gall | Sur le temps local d'intersection du mouvement brownien plan et la méthode de renormalisation de Varadhan[END_REF], or as Equation (6.s) in [START_REF] Gall | Propriétés d'intersection des marches aléatoires. I. Convergence vers le temps local d'intersection[END_REF]. It follows from using (2.6) repeatedly along a dyadic scheme. Fix L ≥ 1, with 2 L ≤ n, and for any ≤ L, we introduce intervals related to the one used in the proof of Corollary 4.2. Namely, letting T := n2 -, J i := [(i -1)T , i • T ), and R i = R(J i ), for i = 1, . . . , 2 , one has

|R n | -E[|R n |] = 2 L i=1 |R L i | -E[|R L i |] - L =1 2 -1 i=1 |R 2i-1 ∩ R 2i | -E[|R 2i-1 ∩ R 2i |] . (7.1)
For any fixed 1 ≤ ≤ L, the ranges shifted by their initial site {R i -S (i-1)T } i=1,...,2 , are independent sets of about n2 -positions (the time-length is not exactly equal for each of them since we do not suppose that n is of the form n = 2 K , for some K ≥ 1, but they differ by at most one unit). Note also that for a fixed ≤ L, the variables {|R 2i-1 ∩ R 2i |, i < 2 } are independent since they depend on disjoint sets of increments of the random walk.

Let now {ζ n } n≥0 be as in the statement of Theorem 1.3, and L be the integer such that 2 L-1 ≤ ζ n < 2 L . We first show that the intersection terms appearing in (7.1) are negligible. Set

Y i = |R 2i-1 ∩ R 2i | -E[|R 2i-1 ∩ R 2i |].
2 L = 1 + θ 2 2 ζ n n 2 • E[Z 2 1 ] + O ζ n n 3 • E[|Z 1 | 3 ] 2 L
.

  .5) then we have |ε(T )| ≤ T . Thus, we can transfer (4.4) to |R n | at a negligible cost bounded by T .

  Applying Theorems 7.2 and 7.3, we get that for any δ > 0, and any ≤ L, Thus indeed the intersection terms in (7.1) can be ignored, and we focus now on proving the Moderate Deviation Principle for the first sum.For simplicity, let Zi := |R L i | -E[|R L i |].We apply Theorem 7.1 withX n := ±1 ζn 2 L i=1 Z i ,and b n := ζ 2 n /n. One has using independence, and the fact that ζn n • |Z 1 | is bounded, E[exp(θb n X n ] = E[exp(θ ζ n n Z 1 ]

  Byconstruction the cardinality of U satisfies the desired constraints from (3.2). Furthermore, using (2.3) we obtain that for any y

which implies N (2R) d ≥ |C|r d , since by definition the cubes Q(x, r), for x ∈ C, are disjoint. By definition of R, this gives N ≥ 2 -d |C| 1-2/d . We now set N 0 := min(N, |C| 1-2 d ), and let U := {z 1 , . . . , z N 0 }.

  which is thus negligible when compared to the probability of E, if ζ ≤ εn, with ε small enough. Finally we use the Proposition 4.1 in[START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF], which implies that for any fixed Λ in Q((n 2 /ζ) 1/3 ), with size of order n, the probability that R[m, n] intersects Λ in more than ζ points, is at least exp(-κ •(ζ 2 /n) 1/3 ), provided ζ 3 /n 2 is large enough. Applying the latter with Λ = R m , on the eventE ∩ {|R m | ≥ γ d2 m}, and using known estimates for upward deviations (see for instance [Chen10, Theorem 8.5.2]), concludes the proof of the proposition.

2-α ,P Y 1 + • • • + Y n > t ≤ C exp(-ct α ).

Acknowledgments

We thank Niccolo Torri for valuable help at an early stage of this project. We acknowledge the support of the projects SWiWS (ANR-17-CE40-0032) and MALIN (ANR-16-CE93-0003).

Note that 2 L • E[Z 2 1 ]/n converges to σ 2 > 0, and that the fourth centered moment of

1 ] 3/4 , we have

It follows that for any θ ∈ R,

and one can then apply Gärtner-Ellis' Theorem, which concludes the proof of Theorem 1.3.