Anas Shantawi
email: anas.shatnawi@lip6.fr

Tewfik Ziadi
email: tewfik.ziadi@lip6.fr

Mohamed Yassin Mohamadi
email: em_mohamadi@esi.dz

Understanding Source Code Variability in Cloned Android Families: an Empirical Study on 75 Families

Keywords: reuse, source code, commonality and variability, android families, SPL

Software developers rely on the clone-and-own approach to rapidly develop software product variants (PVs) that meet variability in market needs. To improve the comprehension of how PVs are evolved and varied, we analyze the clone-andown practices applied by developers of these PVs. We perform an empirical study on 75 android families to gain insights about observable phenomena related to the commonality and variability between the source code of PVs of these families.

In particular, we study three research questions to identify the commonality and variability related to the organization of source code files, cloning Java methods, and configuration parameters of AndroidManifest.xml files. The results show that cloning packages, Java files and Java methods is a common practice used by developers of all android families. Maintainers should put efforts for managing the diverse implementations (bodies) of the modified cloned methods and it is essential to consider the commonality and variability of configuration parameters.

I. INTRODUCTION

Mobile applications should be in variants to follow differences in market needs and users' demands [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF]. The use of the clone-and-own approach becomes a common practice used by developers to rapidly customize existing applications to meet variability in market needs [START_REF] Fischer | Enhancing clone-and-own with systematic reuse for developing software variants[END_REF] [3] [START_REF] Shatnawi | Recovering software product line architecture of a family of object-oriented product variants[END_REF].

Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] define an android family as a group of PVs (i.e., android applications) developed and maintained in GitHub in terms of a mainline and its forks that are published in Google Play as different products. As results of their study, Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] identify 88 android families based on the analysis of the clone-and-own in fork-based development in GitHub. These families are implemented using 88 mainlines and 127 forks.

As a practical example, among 1200 forks of the bitcoinwallet/bitcoin-wallet1 git repository of the Bitcoin Wallet2 , Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] identified that 10 forks are customized to produce 10 distinguishable android applications offered in Google Play (Globaltoken Wallet3 , Europecoin Wallet4 , Fair-Coin Wallet5 , etc.) [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF]. Consequently, the mainline together with the 10 forks constitute a family of 11 PVs. Understanding the source code commonality and variability inside all these families improve the comprehension of how their PVs are evolved through the different forks. In addition, it can radically change the way how these PVs are maintained and managed by reengineered them to a systematic reuse framework such as Software Product Line Engineering (SPLE) [START_REF] Clements | Software product lines: practices and patterns[END_REF]. SPLE allows us to maintain a set of PVs in parallel by managing the commonality and the variability between PVs. Indeed, many recent work have been proposed in the last years to extract SPL from cloned PVs such as [START_REF] Shatnawi | Recovering software product line architecture of a family of object-oriented product variants[END_REF] [6] [START_REF] Parra | Split: An automated approach for enterprise product line adoption through soa[END_REF] [8] [START_REF] Martinez | Bottomup technologies for reuse: automated extractive adoption of software product lines[END_REF].

For android families, understanding source code variability concerns three main dimensions: (i) the organization of the source code files through the PVs, (ii) the Java source code variability that concerns the implementation of the different PVs, (iii) the configuration parameters that define important information about android application variants to the android build tools, the android operating system, and Google Play.

As a motivation example, we identify the number of LOCs composing the source code of each PV of the Bitcoin Wallet android family in Figure 1. The diversity in the numbers of LOCs implies the existence of variability between the source code of these 11 PVs. However, this does not provide a precise knowledge about how this variability is realized compared to the three mentioned dimensions. To do so, we need to understand the commonality and variability of source code elements in terms of what packages, Java files, Java methods and configuration parameters are added, deleted, or modified.

In this paper, we perform an empirical study to gain insights about observable phenomena of the commonality and variability across the source code of PVs of 75 android families from the results of Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF]. The goal of such phenomena is to support maintainers to understand the clone practices in the android families which helps them to take maintenance decisions related to these PVs. We select the 75 families due to the availability of their source code on GitHub repositories and their PVs are published on Google Play. Our empirical study is guided based on three Research Questions (RQs) that are related to three dimensions discussed above:

• RQ1: what is the commonality and variability in the organization of source code files of PVs? We identify the impact of clone practices on the source code organization including adding, removing and modifying Java files and packages. To study this, we rely on similarities and differences in packages and Java files composing PVs of the 75 android families.

• RQ2: what is the commonality and variability related to the cloned Java methods across PVs? We study the commonality and variability corresponding to the cloned Java methods across source code files of PVs in terms of adding, removing and modifying methods. We identity exact cloned methods and modified cloned methods based on analyzing the similarities and differences between headers and bodies of these methods in different PVs of the 75 android families.

• RQ3: what is the commonality and variability in the configuration parameters of android applications of PVs? We investigate the influence of clone practices in the variability of configuration parameters (e.g., access permissions, activities...) that characterize the android applications corresponding to the PVs. We identify the configuration variability by analyzing the AndroidManifest.xml files of PVs to identify common and variable configuration parameters. The results show that developers rename some packages of cloned Java files in different PVs of 90.66% android families (the Oracele's name convention pattern). Also, we identify that cloning exact method is a common practice used by developers of all families and developers modify the body of cloned methods but with low percentage in many families. Configuration parameters of PVs of families are varied and it is essential to consider their commonality and variability while maintaining these families.

The contributions of this paper are:

• To the best of our knowledge, our study is the first empirical study that performs a deeply analysis of the source code variability of PVs of 75 android families. • We define seven software metrics to measure the commonality and variability in PVs. • We propose a methodology for understanding code variability at different variability dimensions (organization, implementation details and configuration parameters). • We develop a parameterized tool that realizes the proposed methodology for understand code variability and it works for any java-based family. The rest of this paper is organized as follows. We describe the dataset of 75 android families and their PVs in Section II. Then, we discuss our methodology to answer research questions in Section III. Next, we discuss the results of answering the three research questions in Section IV. We discuss the usefulness of the results of our empirical study and the threats to validly in Section V. Related works are discussed in Section VI. We conclude our empirical study and draw future directions in Section VII.

II. DATASET OF ANDROID FAMILIES

Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] identified 88 android families in terms of PVs developed and maintained together based on the clone-and-own approach in fork-based development in GitHub repositories. Each family is a composition of one mainline PV and its forks represent other PVs. To identify the 88 families, they developed a search methodology to guarantee that: (i) each family consists of at least two PVs (the mainline and at least one active fork), and (ii) each PV has a unique corresponding application offered in the Google Play. For details of their identification methodology please refer to [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF].

In our study, we include 75 real android families in which all of their PVs are implemented using Java and their corresponding GitHub repositories are still accessible as public. We exclude 13 families due to that: (i) the PVs are implemented using non-Java languages (e.g., C++ and Kotlin), (ii) the GitHub repositories of PVs are not found, (iii) the PVs do not have any commonality in their source code files at all levels of abstraction and (iv) PVs of one family are exactly identical products. We consider as input for our study the source code of the last commit 6 of each PVs of the 75 families.

Figure 2 presents the numbers of Lines Of Code (LOCs) and Java files of PVs 7 to better understand the nature of the families used in our study. We have a diversity in terms of the number of PVs composing each family [START_REF] Fischer | Enhancing clone-and-own with systematic reuse for developing software variants[END_REF][START_REF] Saini | Cloned and non-cloned java methods: a comparative study[END_REF][START_REF] Shatnawi | Recovering software product line architecture of a family of object-oriented product variants[END_REF][START_REF] Clements | Software product lines: practices and patterns[END_REF][START_REF] Seriai | Mining features from the object-oriented source code of a collection of software variants using formal concept analysis and latent semantic indexing[END_REF]11 PVs) and the number of LOCs and Java files of these PVs. We have families composed of PVs including very similar numbers of LOCs and Java files and families composed of PVs having varied numbers of LOCs and Java files. Moreover, Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] reported the diversity of developers of PVs of the same families in which 74% of forks (94 out of the 127 forks) do not have any mutual developers with their mainlines.

III. METHODOLOGY FOR ANSWERING RESEARCH QUESTIONS

A. General Methodology to Identify Commonality and Variability

To understand variability and to identify the statistical data describing the commonality and variability across PVs of each android family, we develop a process presented in Figure 3. This process extends the BUT4Reuse (Bottom-Up-Technologies for Reuse) framework [START_REF] Martinez | Bottomup technologies for reuse: automated extractive adoption of software product lines[END_REF] to analyze commonality and variability corresponding to each RQ. We select to extend BUT4Reuse because: (i) it is generic that allows to use it to analyze different software artifact types (e.g., source code and XML configuration files), and (ii) it is an open-source extensible framework that allows us to (re)implement new algorithms, visualization capabilities and metric extractors.

To compare PVs, BUT4reuse is based on three main steps: identifying elements, identifying blocks and identifying variability metrics.

(1) Identifying elements. It aims to identify the set of elements from each PV. BUT4Reuse allows us to define the granularity of the elements to be identified corresponding to each RQ. For the same PV, we can select from coarse to fine granularity (e.g., package level versus statement level for source code). To identify the elements corresponding to each RQ, we extend BUT4Reuse by integrating two parsers: Java and XML parsers. The Java parser aims to break the source code of PVs into packages and Java files for RQ1, and methods for RQ2. It relies on the Abstract Syntax Tree (AST) of JDT.The XML parser aims to identify a set of XML tags corresponding to configuration parameters based on the analysis of AndroidManifest.xml files of PVs.

(2) Identifying blocks. It aims to identify the commonality in terms of interdependent similar elements across PVs and the variability in terms of dissimilar elements across PVs. Based on a user-defined similarity metric between any pair of elements, a set of elements is considered as interdependent if and only if they belong to exactly the same PVs. We perform this identification based on reusing algorithms implemented in BUT4Reuse which automatically identify sets of elements that correspond to the distinguishable features from PVs. These sets of elements are named Blocks. Each block contains a set of interdependent elements belonging to exactly the same PVs.

We categorize the identified blocks into complete common, partial common and product exclusive blocks based on the number of PVs sharing the interdependent elements of blocks, as presented in Figure 4. The complete common block includes elements that are interdependent in all PVs of the android family. The partial common blocks contains elements that are interdependent in subsets of PVs but not all of them. The product exclusive blocks are composed of elements that are specific to individual PVs and does not have any interdependent relation with other elements in other PVs.

(3) Identifying variability metrics. We measure the commonality and variability by performing statistics that describe behaviour of PVs based on the complete common, partial common and product exclusive blocks. We define a set of commonality and variability metrics to measure four characteristics: the complete commonality in all PVs, the partial commonality in subsets of PVs, the product exclusive variability and the general variability degree.

1) Complete commonality across all PVs: this aims to measure the interdependent code elements in all PVs. We define two metrics: (i) percent of complete common block (%CCB) and (ii) percent of complete common elements (%CCE). We measure %CCB based the ratio between the complete common block and the total number of identified blocks ( #of CompleteCommonBlocks #of Identif iedBlocks

) and %CCE based on the ratio between number of elements of common block and number of elements of all identified blocks ( #ElementsInCompleteCommonBlock #DistinctElementsInAllP V s

). %CCB and %CCE values are always situated in [0-1]. The higher values mean that all PVs share more identical code elements and vice versa.

2) Partial commonality in subsets of PVs: this aims to measure the interdependent code elements across a subset of PVs. We define two metrics (i) percent of partial commonality block (%PCB) and (ii) percent of partial commonality elements (%PCE). %PCB is the ratio between the number of partial common blocks and the total number of identified blocks ( #of P artialCommonBlocks

#of Identif iedBlocks
), and %PCE is the ratio between the number of elements of partial common blocks and the total number of elements of all identified blocks ( #ElementsInP artialCommonBlocks #DistinctElementsInAllP V s ), Values of %PCB and %PCE are situated in [0-1]. The higher values mean that PVs share more interdependent code elements and vice versa.

3) Product exclusive variability: it measures the code elements that are exclusive only for individual PVs. We define two metrics (i) percent of product exclusive blocks (%PEB) and (ii) percent of product exclusive elements (%PEE). %PEB refers to the ratio between the number of product exclusive blocks and the total number of identified blocks ( #of P roductExclusiveBlocks

#of Identif iedBlocks

). %PEE is calculated based on the ratio between the number of elements of product exclusive blocks to the total number of elements of all identified blocks ( #ElementsInP roductExclusiveBlocks

#DistinctElementsInAllP V s
). Values of %PEB and %PEE are situated in [0-1]. The higher values mean that PVs are different from each others.

4) General variability degree (GVD): it aims to measure the diversity between PVs of an android family based on the ratio between the number of identified blocks and the maximum number of possible blocks ( GVD = #of Identif iedBlocks

(2 #of P V s -1)
). The values of GVD are situated in [0-1]. The height value refers to more diversity between PVs. If GVD = 1, then PVs reach the maximum possible diversity level. If GVD = 0, then PVs are identical in their source code.

We identify the seven commonality and variability metrics for each android family for the three RQs. Then, we use the XLSTAT tool to analyze these metrics.

B. Specific Methodology for Research Questions

In this section, we present the specific methodology used to answer each research question.

1) RQ1: What is the Commonality and Variability in the Organization of Source Code Files of PVs: We compare PVs based on packages and Java files constituting these PVs. We consider packages and Java files as representative of the source code organization (i.e., an android application is structured in terms of .java files organized in packages based on their categories or functionalities). To understand the general behaviour of cloning practices related to adding and deleting packages and Java files across PVs, we study the amount of the commonality and variability of packages and Java files across PVs. We identify if the cloning of PVs causes the resettlement of the same packages and Java files from one package to another across different PVs of the same family based on the analysis of the commonality and variability based on two scenarios. In the first scenario, we consider as interdependent packages and Java files those sharing exactly their full qualified names across PVs (e.g., com.preminer...BitcoinIntegration.java should be identical across PVs). In the other scenario, we consider those sharing only the same base-names across PVs (com.preminer...BitcoinIntegration.java and de.schildbach.wallet...BitcoinIntegration.java 8 are equal Java files organized in different packages). We test the amount of commonality and variability corresponding to packages and Java files of the two scenarios by comparing the values of the seven metrics. If the values of these metrics are different in the two scenarios, then the resettlement of packages and Java files across PVs exists. Otherwise, there are no resettlement of packages and Java files across PVs.

2) RQ2: What is the Commonality and Variability Related to the Cloned Java Methods across PVs: We compare PVs based on methods implemented in the cloned Java files across different PVs (i.e., methods of classes having the same basename across the PVs). We focus on Java methods because they implement the behaviour of functionalities of PVs.

We identify Java method variability based on similarities and differences in their headers and bodies to allow maintainers to understand the types of variability existed in cloned methods. We focus on two types of cloned methods: exact cloned methods and modified cloned methods.

Exact cloned methods are methods having identical headers and bodies across PVs of the same family. This represents type-1 method cloning [START_REF] Bellon | Comparison and evaluation of clone detection tools[END_REF]. We identify these methods by defining the similarity metrics of But4Reuse to detect as interdependent methods only those having identical headers and bodies except for white spaces.

Modified cloned methods are methods having the exact identical headers but different bodies across cloned Java files of PVs of the same family. This type of cloned methods includes type-2 and type-3 method cloning [START_REF] Bellon | Comparison and evaluation of clone detection tools[END_REF] because we consider bodies as different if they have at least one variation in their identifiers, literals, types, layout, comments or statements. We give attention to these types of cloned methods because they need a special processing corresponding to merge these method bodies while reengineering PVs to SPLs. To identify these methods, we define the similarity metrics of But4Reuse between any pair of methods as follows. Methods are consider as interdependent ones if and only if they have the exact identical headers and different bodies across PVs.

3) RQ3: What is the Variability in the Configuration Parameters of Android Applications of PVs: We compare PVs based on the configuration parameters identified from XML tags in the AndroidManifest.xml9 of each PV. Developers use these XML tags to configure parameters for characterizing important information concerning each PV to the Android operating system, the build tools and the Google Play store. We consider in our study configuration parameters that describe:

• The android application components of PVs including Activities, Services, Broadcast Receivers and Content Providers. This enables to identify the commonality and the variability in application components of PVs. • The permissions granted to PVs to access private user data or to perform sensitive operations (e.g., send SMS, access camera, etc.). This allows us to test how developers change permissions of PVs. • The package names of PVs that are used by the Android build tools to identify the directory of source code files. This enables to check whether PVs source code files are replaced or not while cloning them. • The hardware and software features defining the device compatibility of PVs. This allows us to identify if PVs are customized to be compatible with different devices.

IV. RESULTS FOR ANSWERING RQS

A. RQ1: What is the Commonality and Variability in the Organization of Source Code Files of PVs?

In Figure 5, we present the box plots of the seven metrics corresponding to the two scenarios of the full qualified name vs the base-name of packages and Java files of PVs in all families. As all of the box plots are tall, families hold quite different patterns compared to their commonality and variability elements in both scenarios of base-name and full qualified name. The results show that we have more commonality (%CCE and %PCE are increased) and less variability (%PPE is decreased) when the base-name is considered compared to the full name for 90.66% (68/75) families. We observe that the reason behind these different values is that developers rename some root packages in different PVs while keeping the same sub-packages of cloned Java files. These cloned Java files are identified as interdependent ones across PVs only when we consider their base-names. We interpret this observation by the Oracle's naming conventions10 as a clone practice where companies should start their package names by reversing their Internet domain name. For example from 11 PVs of the Bitcoin Wallet family, we find that 8 PVs have the same root packages as de.schildbach.wallet while they have been changed in 3 PVs to com.hivewallet, com.viacoin.wallet and com.preminer.

For 9.33% (7/75) families, we identify that their PVs have exactly the same commonality and variability level based on the identical values of our commonality and variability metrics in the two scenarios. This means that clone practices in these families do not include any resettlement in the organization of PVs and they do not adhere to the Oracle's naming conventions (they are anti-patterns).

We note that the complete commonality (%CCB and %CCE) is decreased in favour to the partial commonality (%PCB and %PCE) when the number of PVs is increased. Also, the exclusive variability is decreased for families of large number of PVs compared to those of small number of PVs based on %PEB and %PEE. For GVD, it is decreased as well as the number of PVs is increased. The GVD reaches the peak (GVD = 1) for most of families of 2 PVs because the maximum number of possible blocks is 3: common block and 2 exclusive ones for each PV. We find that 2 families have identical packages and Java files in their PVs (have one interdependent common block) and 5 families that one PV is subset of the other PV in terms of packages and Java files (have 2 blocks: 1 common: 1 exclusive).

B. RQ2: What is the Commonality and Variability Related to the Cloned Java Methods across PVs?

Based on the results of RQ1, we consider that Java files having the identical base-names across PVs as the same cloned Java files.

1) Exact Cloned Methods: Figure 6 shows the results of the commonality and variability metrics corresponding to the exact cloned methods across PVs. The results of these metrics The very short box plot of %CCB shows a sort of agreement between families in terms of the existence of a common block of exact cloned methods and its percentage compared to shared and exclusive blocks identified in these families. This percentage of the common block is relatively decreased compared to the number of PVs composing the families. We find that the centrality of this percentage is between 29% and 33% where the mean and the median are placed respectively.

The relatively tall box plot of %CCE shows a disagreement in terms of the number of exact cloned methods in all PVs of different families. The number of exact cloned methods compared to the complete commonality is less than 8% for 24% (18/75) of the families, more than 72% for 20% (15/75) of the families, and between 8% anf 72% for 56% (42/75) of the families. We find that the number of the exact cloned methods in all PVs of a given family is decreased relatively when this family has more PVs.

Concerning the partial commonality, the box plots of %PCB and %PCE show the percentages of the shared blocks compared to common and exclusive blocks and the number of exact cloned methods compared to the partial commonality. As all families of 2 PVs do not have any partial commonality naturally, the box plots of %PCB and and %PCE are very short and their centrality is at 0. The values of %PCB and %PCE are increased compared to the number of PVs composing families (more PVs means more partial commonality). By comparing %PCB with %CCB and %PCE with %CCE, we find that the complete commonality of exact cloned methods is transformed to the partial commonality as well as more PVs are cloned in a given family. The reason is that new cloned PVs may not consider a subset of exact cloned methods corresponding to the complete commonality which transforms these methods to be a part of the partial commonality. For instance, in the family of 11 PVs, we identify that 1.8% of the methods are exact cloned methods in the 11 PVs (complete commonality) compared to 33.1% of the methods are extract cloned ones across subsets of these 11 PVs (partial commonality). This means that PVs have different amounts of productexclusive feature extensions. The box plot of GVD shows that most of families reach a high variability degree compared to the exact cloned methods across the PVs. Large families have less general diversity compared to small ones, e.g., all families of 2 PVs reach the maximum possible diversity level (GVL = 1), while the family of 11 PVs is considered relatively similar (GVD is 4%).

2) Modified Cloned Methods: We provide the results of the complete and partial commonality metrics corresponding to modified cloned methods in Figure 7. As all box plots are comparatively short ones, we have a sort of agreement between different android families in terms of the number of modified cloned methods compared to all methods of the corresponding family. %CCB and %CCE show that 98.6% (74/75) of android families have applied modified cloned methods across all PVs in which each PV has a different implementation of the same method. The centrality of the box plot is between 1% and 6% of the methods are modified cloned methods. The outliers of this centrality is realized in terms of 4 families that have 15%, 16.5%, 48.6%, and 57.8% of their methods as complete modified cloned methods.

Based on %PCE, all families of 3, 4, 5, 6 and 11 PVs contain modified cloned methods in subsets of their PVs. The %PCE of families of 2 PVs is zero because families of 2 PVs cannot have a partial commonality. In general, the centrality pattern of %PCE for families of 4, 5, 6 and 11 PVs is between 6% and 17% of their methods as modified cloned methods in subsets of the PVs. We have one outlier family that have 39.3% of its methods. For families of 3 PVs, the centrality pattern of %PCE is between 1.8% and 3.9%. The results of the commonality and variability metrics are presented in Figure 8. %CCB is reduced in favor of %PCB as well as families have more PVs. We find that the main reason of this reduction in %CCB is mainly due to the differences in the application components (Activities, Services, Broadcast Receivers and Content Providers) compared to slice differences in the other parameters in PVs of the same families.

The box plot of %CCB is comparatively short that means all families have the same pattern in terms of the ratio between the common block and the total number of identified blocks. On the other hand, the box plot of %CCE is very tall. Therefore, families hold quite different patterns in terms of the volume of complete common configuration parameters. The reason behind the tall box plot is the outliers of some families. For examples, we identify one family that has no common parameters in its PVs and 4 families that their PVs have exactly the same configuration parameters.

Unlike %CCB and %PCB, %CCE is not reduced in favor of %PCE by comparing %CCE and %PCE of the same families. For example in the family of 11 PVs, the number of configuration parameters in the common block are equal to those in the shared blocks (%CCB = %PCB = 32). Therefore, it is not important to have less complete commonality if we have extra partial commonality. Based on the comparatively tall box plots of % PEE, families have disagreement in terms of variability degree in their configuration parameters.

V. DISCUSSIONS

A. How the Results Help Maintainers?

The results obtained in our empirical study provide useful information for maintainers of cloned android families. As we find that most of android families follow the Oracele's name convention that makes packages and Java files that have the exact identical base-names and different full qualified names across PVs are the same cloned Java files, we recommend to ignore the differences in full qualified names related to the variability of root packages of PVs of these families to be able to identify cloned method variability.

The cloning exact method is a common practice used by developers of all families. This produces a large number of methods that have the exact headers and bodies across all or a subset of PVs. To better maintain (e.g., fixing bugs) these cloned methods, we recommend to reengineer these cloned methods to construct reusable software libraries (i.e., APIs).

The presence of modified cloned methods in PVs highlights challenges to be encountered during reengineering these PVs to SPLs. Such challenges are related to merge the different implementations (bodies) of the same cloned methods by creating reusable and representative abstractions for the SPL core assets. We recommend to reuse existing approaches that contribute to cope with method merging challenges [START_REF] Narasimhan | Cleaning up copy-paste clones with interactive merging[END_REF] [START_REF] Krishnan | Unification and refactoring of clones[END_REF]. Also, configuration parameters of PVs of android families are varied and it is essential to consider their commonality and variability while migrating these families to SPLs.

B. Threats to Validity

Internal validity. While measuring the partial commonality using %PCB and %PCE metrics, we treat all shared blocks equally without considering the number of PVs represented by each shared block. This means that our results do not represent this dimension in a deep way.

To obtain the commonality and variability metrics, we extend the But4Reuse tool by adding two components for parsing Java source code and XML files of PVs. We rely on the Eclipse Java development tools and the DOM parsers that are well-tested, evaluated and used in several tools and research papers. DOM is officially recommended by the World Wide Web Consortium (W3C). For identifying blocks, we use But4Reuse intersection algorithms that are also tested in several research papers [?] [START_REF] Martinez | Bottomup technologies for reuse: automated extractive adoption of software product lines[END_REF]. To mitigate related threats, we validate the correctness of our extension of But4Reuse based on the Java unit test and the manual validation of toy examples.

External validity. The main concern against the generalizability of our results is that we rely on a dataset of open-source android families developed in GitHub repositories based of fork-based development. Therefore, our results cannot be generalized for android families developed using other clone practices in the industrial companies.

VI. RELATED WORK

To the best of our knowledge, our study is the first empirical study that performs a deeply analysis of the source code variability of PVs of 75 android families. We identify two crosscutting domains: analyzing reuse in android ecosystem and reengineering PVs to SPLs.

Analyzing reuse in android ecosystem. Li et al. [START_REF] Li | Mining families of android applications for extractive spl adoption[END_REF] analyzed 1.5 million android applications and classified them to 75,963 different families. They identified applications developed by the same company based on package name and the certificate signed by developers. They only performed a high abstract code comparison to remove potential outliers. The resulting families are not open-source. Thus, we cannot include them in our study. Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] identified 88 android families by analyzing the fork-based clone-and-own in GitHub. Businge et al. [START_REF] Businge | Clonebased variability management in the android ecosystem[END_REF] studied four research questions to analyze: the characteristics of android families, the behaviour of pull requests, the diversity of developers of PVs, and the type of product customization. Shatnawi et al. [14] [15] invested the reuse practices of android APIs to identify reusable components corresponding to functionalities of android APIs. They extracted reuse practices in terms of frequent usage patterns of API classes and methods by analyzing how developers reused classes and methods of android APIs in their applications. Mojica et al. [START_REF] Mojica | A large-scale empirical study on software reuse in mobile apps[END_REF] studied 200,000 applications (not families) to analyze the inheritance, library and framework reuse practices in these applications based on class signatures. However, none of these existing studies performed a deep analysis of the source code commonality and variability in android families related to our RQs.

Reengineering PVs to SPLs. Different approaches were proposed to support reengineering PVs to SPLs. These approaches aim to identify features [START_REF] Seriai | Mining features from the object-oriented source code of a collection of software variants using formal concept analysis and latent semantic indexing[END_REF] [9], software product line architectures [START_REF] Shatnawi | Recovering software product line architecture of a family of object-oriented product variants[END_REF] [8], reusable assets [7] [17], and feature model synthesis [18] [19] . They analyze variability between PVs based on several algorithms including FCA [START_REF] Shatnawi | Recovering software product line architecture of a family of object-oriented product variants[END_REF] [19], interdependent element identification [START_REF] Martinez | Bottomup technologies for reuse: automated extractive adoption of software product lines[END_REF], latent semantic indexing [START_REF] Seriai | Mining features from the object-oriented source code of a collection of software variants using formal concept analysis and latent semantic indexing[END_REF], clustering algorithm [START_REF] Shatnawi | Mining reusable software components from object-oriented source code of a set of similar software[END_REF] and clone detection [START_REF] Mende | Supporting the grow-and-prune model in software product lines evolution using clone detection[END_REF]. Although these approaches contribute to manage the commonality and variability of PVs by reengineering to SPLs, their aim is not to understand the commonality and variability patterns based on empirical studies on cloned android families. We plan to adapt a number of these approaches to migrate android families into SPLs in our future works.

VII. CONCLUSION AND FUTURE WORKS

We performed an empirical study on 75 android families developed using clone-and-own approach in fork-based development. We investigated three main RQs for analyzing the commonality and variability of: (i) the organization of source code files, (ii) the cloning of Java methods and (iii) the configuration parameters in PVs of the 75 families.

We defined seven software metrics to measure the commonality and variability and proposed a methodology to extract values of these metrics for corresponding to the three RQs. We automated this methodology as an extension of But4Reuse.

The results of our empirical study show that developers of 90.66% of families rename root packages in different PVs while keeping the same sub-packages of cloned Java files following the Oracele's name convention pattern. Regarding the cloning of Java methods, we identify that cloning exact method is a common practice used by developers of all families and developers modify the body of cloned methods but with low percentage in most of families. The presence of modified cloned methods in PVs indicates that maintainers should put efforts for merging the diverse implementations (bodies) of the same cloned methods for creating reusable abstracted methods for the SPL core assets. The variability in configuration parameters are due to the differences in the application components (Activities, Services, Broadcast Receivers and Content Providers) compared to slice differences in the other parameters in PVs of the same families.

As future works, we plan to identify more cloned families from open-source repositories, to analyze the variability over time based on the version history and to reengineer the cloned android families into SPLs.

Figure 1 .

 1 Figure 1. Number of LOCs of 11 PVs of the Bitcoin Wallet android families

Figure 2 .

 2 Figure 2. The size of PVs of android families

Figure 3 .

 3 Figure 3. Process to identify variability for answering the research questions

Figure 4 .

 4 Figure 4. Commonality and variability using blocks of interdependent elements

Figure 5 .

 5 Figure 5. RQ1: the commonality and variability of packages and Java files across PVs

Figure 6 .

 6 Figure 6. RQ2: the commonality and variability of exact cloned methods

Figure 7 .

 7 Figure 7. RQ2: the commonality of modified cloned methods

Figure 8 .

 8 Figure 8. RQ3: The commonality and variability of configuration parameters

https://github.com/bitcoin-wallet/bitcoin-wallet

play.google.com/store/apps/details?id=de.schildbach.wallet&hl

play.google.com/store/apps/details?id=org.globaltoken.wallet&hl

play.google.com/store/apps/details?id=madzebra.erc.wallet&hl

play.google.com/store/apps/details?id=de.schildbach.wallet.faircoin&hl

We downloaded last commits of product variants in March 2019.

Software metrics are calculated using the Understand tool, and the statistics are identified using the XLSTAT tool.

https://developer.android.com/guide/topics/manifest/manifest-intro

https://docs.oracle.com/javase/tutorial/java/package/namingpkgs.html

ACKNOWLEDGMENT

This work was supported by the ITEA 3 REVaMP 2 project.


Bruno Leggio

Anna Napoli

Hiromichi Nakazato

Antonino Messina

Bounds on mixed state entanglement

I. INTRODUCTION

In dealing with mixed states of a physical system, one has to be careful when speaking about entanglement. The definition of bipartite mixed state entanglement is unique (although problems may arise in dealing with multipartite entanglement [1]), but its quantification relies on several different criteria and it is not yet fully developed: many difficulties arise already in the definition of physically sensible measures [START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Mintert | Concurrence of Mixed Bipartite Quantum States in Arbitrary Dimensions[END_REF]. The main problem affecting a few known mixed state entanglement measures is, indeed, the fact that extending a measure from a pure state case to a mixed state case usually requires challenging maximization procedures over all its possible pure state decompositions [START_REF] Eisert | A comparison of entanglement measures[END_REF]- [START_REF] Takayanagi | Towards an entanglement measure for mixed states in CFTs based on relative entropy[END_REF]. Notwithstanding, the investigation of the connection between entanglement and mixedness exhibited by a quantum system is of great interest, e.g. in quantum computation theory [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF][START_REF] Datta | Role of entanglement and correlations in mixed-state quantum computation[END_REF] as well in quantum teleportation [START_REF] Paulson | Bounds on mixedness and entanglement of quantum teleportation resources[END_REF]. The threshold of mixedness exhibited by a quantum system compatible with the occurrence of entanglement between two parties of the same system has been analyzed, leading for example to the so-called Kus-Zyczkowski ball of absolutely separable states [START_REF] Kus | Geometry of entangled states[END_REF]- [START_REF] Aubrun | Tensor products of convex sets and the volume of separable states on N qudits[END_REF]. Quite recently, possible links between entanglement and easily measurable observables have been exploited to define experimental protocols aimed at measuring quantum correlations [START_REF] Brida | Experimental Estimation of Entanglement at the Quantum Limit[END_REF]- [START_REF] Johnston | The inverse eigenvalue problem for entanglement witnesses Linear Algebra and its Applications[END_REF]. The use of measurable quantities as entanglement witnesses for a wide class of systems has been known for some time [START_REF] Toth | Entanglement witnesses in spin models[END_REF][START_REF] Wiesniak | Heat capacity as an indicator of entanglement[END_REF], but an analogous possibility amounting at entanglement measures is a recent and growing challenge. To present day some bounds for entanglement are measured in terms of correlation functions in spin systems [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF] or using quantum quenches [START_REF] Cardy | Measuring Entanglement Using Quantum Quenches[END_REF]. Indeed an experimental measure of entanglement is, generally speaking, out of reach because of the difficulty in addressing local properties of many-particle systems and of the fundamental non-linearity of entanglement quantifiers. For such a reason the best one can do is to provide experimentally accessible bounds on some entanglement quantifiers [START_REF] Guhne | Estimating Entanglement Measures in Experiments[END_REF]. The aim of this paper is to build a bound to the entanglement degree in a general bipartition of a physical system in a mixed state. We are going to establish an upper bound to the Negativity N [START_REF] Peres | Separability Criterion for Density Matrices[END_REF] in terms of the Linear Entropy S L . We are thus studying what is called Negative Partial Transpose (NPT) entanglement. It should however be emphasized that a non-zero Negativity is a sufficient but not necessary condition to detect entanglement, since Positive Partial Transpose (PPT, or bound) entanglement exists across bipartitions of dimensions higher than 2 × 3, which can not be detected by means of the Negativity criterion [START_REF] Horodecki | Mixed-State Entanglement and Distillation: Is there a Bound Entanglement in Nature?[END_REF]. Our investigation contributes to the topical debate concerning a link between quantum correlations and mixedness [START_REF] Wei | Maximal entanglement versus entropy for mixed quantum states[END_REF]. We stress that our result is of experimental interest since the bound on N may easily be evaluated measuring the Linear Entropy.

II. AN UPPER BOUND TO THE NEGATIVITY IN TERMS OF LINEAR ENTROPY

Consider a d-dimensional system S in a state described by the density matrix (0 ≤ p i ≤ 1, ∀i)

ρ = i p i σ i (1)
where each σ i represents a pure state, and define a bipartition into two subsystems S 1 and S 2 with dimensions d 1 and d 2 respectively (d = d 1 • d 2 ). It is common [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF] to define Negativity as

N = ρ T1 -1 d m -1 = Tr ρ T1 (ρ T1 ) † -1 d m -1 (2)
where d m = min{d 1 , d 2 }, ρ T1 is the matrix obtained through a partial transposition with respect to the subsystem S 1 and • is the trace norm

( O ≡ Tr{ √ OO † }).
In what follows we will call d M = max{d 1 , d 2 }. By construction, 0 ≤ N ≤ 1, with N = 1 for maximally entangled states only. Furthermore, the Linear Entropy S L in our system is defined as

S L = d d -1 (1 -Trρ 2 ) = d d -1 P E (3)
where

P E = 1 -Trρ 2 = 1 -ρ 2
2 is a measure of mixedness in terms of the Purity Trρ 2 of the state, ρ 2 being the Hilbert-Schmidt norm of ρ ( O 2 ≡ Tr{OO † }). By definition, S L = 0 for any pure state while S L = 1 for maximally mixed states. It is easy to see that there exists a link between the trace norm of an operator O in a d-dimensional Hilbert space and its Hilbert-Schmidt norm. Such a link can be expressed as

O 2 = ( d i=1 |λ i |) 2 ≤ d d i=1 |λ i | 2 = d O 2 2 (4)
where λ i is the i-th eigenvalue of O and the so-called Chebyshev sum inequality

d i=1 a i 2 ≤ d d i=1 a 2
i has been used. Since, in addition, the Hilbert-Schmidt norm is invariant under partial transposition, one readily gets a first explicit link between Negativity and mixedness P E , valid for generic d-dimensional systems, in the form of an upper bound, which reads

N ≤ √ d √ 1 -P E -1 d m -1 ≡ Q 1 (5)
Equation ( 5) provides an upper bound to the Negativity N in terms of P E and thus, in view of equation [START_REF] Mintert | Concurrence of Mixed Bipartite Quantum States in Arbitrary Dimensions[END_REF], in terms of the Linear Entropy. This bound imposes a zero value for N only for a maximally mixed state. It is known [START_REF] Thirring | Entanglement or separability: the choice of how to factorize the algebra of a density matrix[END_REF], however, that no entanglement can survive in a state whose purity is smaller than or equal to (d -1) -1 . Also in the case of a pure (or almost pure) state, the bound becomes useless as long as the bipartition is not "balanced" (by "balanced" we mean a bipartition where d m = √ d). It indeed becomes greater than one (thus being unable to give information about entanglement) for mixedness smaller than d-d 2 m d which might even approach 1 in some specific cases (recall that, by definition, d m ≤ d). We however expect entanglement to be unbounded only in the case of pure states (P E = 0). In the following we show that bound (5) can be strengthened.

III. STRENGTHENING THE PREVIOUS BOUND

Observe firstly that the rank r ρ of ρ T1 is not greater than d 2 m (equal to d) when ρ is pure (maximally mixed). For this reason we write

r(S L ) ≡ max {ρ:Trρ 2 =1-d-1 d S L } r ρ (6)
By construction, r(0) = d 2 m since any pure state can be written in Schmidt decomposition consisting of d m vectors, and r(1) = d because a maximally mixed state is proportional to identity. Since by definition

d i=1 |λ i | 2 = r(S L ) i=1 |λ i | 2
holds for any physical system, equation ( 5) may be substituted by the following inequality

N ≤ r(S L ) √ 1 -P E -1 d m -1 (7)
Note however that there exist at least some physical systems for which the function in [START_REF] Takayanagi | Towards an entanglement measure for mixed states in CFTs based on relative entropy[END_REF], due to the maximization procedure involved in its definition, is always equal to d in the range S L ∈ (0, 1], showing then a discontinuity at S L = 0 as lim

S L →0 r(S L ) = d = d 2 m = r(0) (8)
Since we want our result to hold generally, independently on the particular system analyzed, equation ( 7) can not improve equation ( 5) because even for slightly mixed states (0 < S L << 1) we have a priori no information on r(S L ) which might be equal to d, tracing back equation [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF] to [START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF]. Despite this, we may correct [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF] exploiting the expectation that for very low mixedness some of these eigenvalues are much smaller than the other ones. Indeed for all the r(S L ), not vanishing eigenvalues appearing in (4) are treated on equal footing in going from ρ T1 to ρ T1 2 . To properly take into account the difference between them, go back to equation (1) and define a reference pure state σ R at will among the ones having the largest occupation probability p R . The spectrum of σ T1 R consists of n p non-zero eigenvalues {µ

(R) α } max n p = d 2 m and of n m = d -n p zero eigenvalues {ν (R)
α }. We call the former α-class eigenvalues and the latter β-class eigenvalues, and obviously the latter class does not contribute to σ T1 R . In order to strengthen [START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF] we are interested in the spectrum of ρ T1 which, in general, consists of d non-zero eigenvalues. Unfortunately, then, we can not directly introduce analogous α-and β-classes to identify which eigenvalues contribute to the sum involved in (4) comparatively much less than the other ones, when the state ρ possesses a low mixedness degree and is thus very close to a pure state. To overcome this difficulty let us consider a parameter-dependent class of density matrices associated to the given ρ

τ (x) = i q i (x)σ i (9)
with x ≥ 0, such that, for all i,

lim x→x1 q i (x) = p i lim x→0 q i (x) = δ iR (10)
and such that all q i (x)s are continuous functions of x. Thus τ (x) T1 continuously connects ρ T1 and σ T 1 R and, as a consequence, any ν (R) β is continuously connected to a particular eigenvalue of ρ T1 which will be the the corresponding mixed state β-class eigenvalue ν β . In such a way one can define the function ν β0 (x) as the eigenvalue of τ (x) T1 having the property lim x→0 ν β0 (x) = ν (R) β0 [START_REF] Thirring | Entanglement or separability: the choice of how to factorize the algebra of a density matrix[END_REF] and so the β-class eigenvalue for ρ T1 as

ν β0 ≡ lim x→x1 ν β0 (x) (12)
We emphasize at this point that the results of this paper do not depend on the explicit functional dependence of τ (x) on x, which can be chosen at will provided it satisfies conditions [START_REF] Kus | Geometry of entangled states[END_REF]. Indeed, τ (x) is just a mathematical tool, with (in general) no physical meaning. To save some writing and in view of equation ( 4), we put

A = α µ 2 α B = β ν 2 β (13)
and notice that Tr(ρ T1 ) 2 = Trρ 2 = A + B. We can now state (see Appendix for a proof) the following.

Lemma 1 Given a state ρ of a system in a d-dimensional Hilbert space, and the associated reference pure state σ R , for any set of states τ (t) satisfying ( 9) and [START_REF] Kus | Geometry of entangled states[END_REF], there exists a value δ ≥ x 1 such that 1 -A(t) -B(t) ≥ B(t)d for any t ∈ [0, δ]. This result allows us to find a function w(S L ) such that w(0) = d 2 m and

ρ T1 2 ≤ w(S L ) = f ( ρ T1 2 2 ) (14)
Starting from the identity

ρ T1 2 = ( d 2 m α |µ α |) 2 + ( d-1 β |ν β |) 2 + d 2 m α |µ α | d-1 β |ν β | (15)
and applying the Chebyshev sum inequality term by term we obtain

ρ T1 2 ≤ (d m √ A + B + d -1 d √ 1 -A -B) 2 (16)
where Lemma 1 has been exploited. Expressing equation ( 16) in terms of Negativity and Purity we finally get

N ≤ d m √ 1 -P E + d-1 d √ P E -1 d m -1 ≡ Q 2 (17)
Bound [START_REF] Toth | Entanglement witnesses in spin models[END_REF] improves bound [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF] for high purity when S L is small, that is Q 2 < Q 1 , becoming in general greater than Q 1 at low purity. In addition it still suffers the same drawback as Q 1 , not vanishing when 1

-P E = 1 d-1 .
In such a case one has to consider the lower bound 1 d-1 on purity, below which no entanglement survives. In order to take such a bound into account, instead of distinguishing among α and β eigenvalues of ρ T1 , we can divide them into positive ones {ξ i } and negative ones {χ i }. In this way, calling n -and (dn -) the numbers of negative and positive eigenvalues, respectively and applying the Lagrange multiplier method to the function

ρ T1 = d-n- i ξ i + n- j χ j subjected to constraints i ξ 2 i + j χ 2 j = 1 -P E and i ξ i + j χ j = 1 one finds ρ T1 2 ≤ d -2n -+ 2 n -(d -n -)(d(1 -P E ) -1) d (18)
Bound ( 18) can be exploited to show that no entanglement can survive at purity lower than 1 d-1 . Indeed, for entanglement to exist, one eigenvalue at least has to be negative. However, by normalization, it always has to be true that ρ T1 ≥ 1 and this implies that, as long as n -≥ 1, purity 1 -P E can not be smaller than 1 d-1 as expected. However, in general, the number of negative eigenvalues is not known. In these cases the best one can do is to look for the maximum, with respect to n -, of the right-hand side of [START_REF] Wiesniak | Heat capacity as an indicator of entanglement[END_REF], leading unfortunately once again to bound (5) on N . However, since always N ≤ Θ( d-2

d-1 -P E ) ≡ Q 3 , where Θ(x) is the Heaviside step function, defining Q = min{Q 1 , Q 2 , Q 3 }, we state our final and main result as

N ≤ Q (19)
valid for every possible bipartition of a quantum system, independently on its (finite) dimension, its detailed structure or its properties. It is worth stressing that computing Negativity quickly becomes a very hard task as the dimension of the Hilbert space grows, while the evaluation of purity can be performed without particular efforts. We emphasize in addition that bound Q in ( 19) only depends on purity, and is completely determined once a bipartition of the physical system is fixed and purity is known. This means that an experimental measure of purity allows to extract information about the maximal degree of bipartite entanglement one can find in the system under scrutiny. Some purity measuring protocols, or at least purity estimations based on experimental data, have been proposed. They are based on statistical analysis of homodyne distributions, obtained measuring radiation field tomograms [START_REF] Manko | Homodyne estimation of quantum state purity by exploiting the covariant uncertainty relation[END_REF], on the properties of graph states [START_REF] Wunderlich | Estimating purity and entropy in stabilizer state experiments[END_REF], or on the availability of many different copies of the state over which separable measurements are performed [START_REF] Bagan | Purity Estimation with Separable Measurements[END_REF]. In all the cases where a measure of purity is possible, an experimental estimation of bipartite entanglement is available thanks to [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF] which is then actually experimentally accessible.

IV. CROSSOVER BETWEEN Q1 AND Q2 AND NUMERICAL RESULTS

As commented previously, bounds Q 1 (Eq. ( 5)) and Q 2 (Eq. ( 17)) can supply information about bipartite entanglement in two different setups: Q 1 is indeed accurate enough for a balanced bipartition (i.e. when d m ∼ √ d) but fails when √ d d m since it rapidly becomes greater than 1. To solve this problem, we obtained the bound Q 2 which, by construction, provides nontrivial information about bipartite entanglement in an unbalanced bipartition ( √ d d m ), but may not work properly for a balanced one. It is actually a very easy task to show that our new bound Q 2 works better than the old one, Q 1 , (i.e., Q 1 ≥ Q 2 ) when the purity P is greater than a critical value given in terms of the total Hilbert space dimension and of the subdimensions of the bipartition, i.e. when

P (ρ) ≥ d -1 d( √ d -d m ) 2 + d -1 = P c (20)
Two limiting cases are easily studied directly from Eq. ( 20): for a perfectly balanced bipartition ( √ d = d m ), one gets P c = 1 and, since by definition 1 d ≤ P (ρ) ≤ 1, in this case the bound Q 1 is smaller (and therefore works better) than the bound Q 2 for any possible quantum state. In the opposite limit, in a strongly unbalanced bipartition, one can roughly approximate ( √ dd m ) 2 ∼ d and, since by definition d ≥ 4, this leads to

P c ∼ d-1 d 2 +d-1 < 1 d .
Taking into account the natural bounds for the purity of a quantum state, this in turn means that in such a limit Q 1 > Q 2 for any quantum state or, in other words, our new bound works always better. This behavior can be clearly seen in Fig.

(1), where the dependence of P c on d and d m is shown together with the natural limiting values of P (ρ).

To better exemplify such a behavior, we report here results of numerical simulations performed with the aid of the QI package for Mathematica [START_REF] Miszczak | Singular value decomposition and matrix reorderings in quantum information theory[END_REF], by which random quantum states have been generated in different dimensions, uniformly distributed according to different metrics. On these states, we tested bounds 2) clearly show that ∆ 1 < ∆ 2 for all the analyzed states. The second run of simulations has been performed with d m randomly chosen in [START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Brida | Experimental Estimation of Entanglement at the Quantum Limit[END_REF] and d M = d m + 60. In such a case, as can be seen in Fig. (3) the difference ∆ 1 -∆ 2 has no fixed sign. The two subdimensions are, indeed, such that the critical value of purity P c in Eq. ( 20) is neither extremely close to 1 d nor to 1. As can be noticed from the inset of Fig. (3) which shows the difference ∆ 1 -∆ 2 , however, on the average it is still true that ∆ 1 < ∆ 2 . The third set of numerical data, finally, has been obtained generating 10 3 random states with subdimensions d M = d m + 70 and d m randomly drawn in [START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF]. In this limit the value of P c is very close to the minimum of purity and we therefore expect Q 2 to work better than Q 1 for almost any state. This is indeed confirmed by the simulations shown in Fig. [START_REF] Eisert | A comparison of entanglement measures[END_REF], in which ∆ 2 < ∆ 1 . As an example of application of our results, consider a single two-level system interacting with a spin system composed of n s spins, each of which lives in a d s dimensional Hilbert space. Therefore the total system Hilbert space has dimension d = 2(d s ) ns . Let us suppose the spin system is a chain of 10 spin 1 2 (which is a relatively small system, very far from its thermodynamic limit). The total Hilbert space dimension will then be d = 2 11 , and considering the natural bipartition into the two-level system and the spin chain, one has d m = 2 and d M = 2 10 . For such a system, the critical value of purity P c in Eq. ( 20) is As an example of application of our results, consider a single two-level system interacting with a spin system composed of n s spins, each of which lives in a d s dimensional Hilbert space. Therefore the total system Hilbert space has dimension d = 2 ⇥ (d s )

Q 1 and Q 2 . Figures (2)-(4) show the differences ∆ i = Q i -N (i = 1,
n s . Let us suppose the spin system is a chain of 10 spin 1/2 (which is a relatively "small" system, very far from its thermodynamic limit). The total Hilbert space dimension will then be 10 . For such a system, P c in Eq. ( 22) is

P c = 2 11 1 2 11 ⇣ p 2 11 2 ⌘ 2 + 2 1
The lower value of purity fo glement can survive is, as s 0.00049. Therefore, for all the 0.000534  P (⇢)  1, bound ter than Q 1 . Only for the sma an extremely low purity in the bound Q 1 gives better informa This shows again that, fo (and even in the case of a rela vidual components of the tota better than Q 1 .

IV. CONCL

Incidentally, bounds like Eq the underlying physics behin shown in [START_REF] Wei | Maximal entanglement versus entropy for mixed quantum states[END_REF], connecting Neg in a thermal bipartite state. H measure of the mixedness of en state and is therefore strongly self. As an example of application of our results, consider a single two-level system interacting with a spin system composed of n s spins, each of which lives in a d s dimensional Hilbert space. Therefore the total system Hilbert space has dimension d = 2 ⇥ (d s )

ACKNOWLED

n s . Let us suppose the spin system is a chain of 10 spin 1/2 (which is a relatively "small" system, very far from its thermodynamic limit). The total Hilbert space dimension will then be d = 2 11 , and considering the natural bipartition into the 10 . For such a system, P c in Eq. ( 22) is

P c = 2 11 1 2 11 ⇣ p 2 11 2 ⌘ 2 + 2
The lower value of purity f glement can survive is, as s 0.00049. Therefore, for all the 0.000534  P (⇢)  1, bound ter than Q 1 . Only for the sma an extremely low purity in th bound Q 1 gives better inform This shows again that, fo (and even in the case of a rela vidual components of the tota better than Q 1 .

IV. CONC

Incidentally, bounds like Eq the underlying physics behi shown in [START_REF] Wei | Maximal entanglement versus entropy for mixed quantum states[END_REF], connecting Ne in a thermal bipartite state. measure of the mixedness of e state and is therefore strongly self.

ACKNOWLE

HN acknowledges partial s

P c = 2 11 -1 2 11 ( √ 2 11 -2) 2 + 2 11 -1 ∼ 0.000534 (21)
The lower value of purity for which bipartite entanglement can survive is, as said before, P l = 1 d-1 ∼ 0.00049. Therefore, for all the total states having purity 0.000534 ≤ P (ρ) ≤ 1, bound Q 2 in Eq. ( 17) works better than Q 1 . Only for the small fraction of states having an extremely low purity in the range [0.00049, 0.000534] bound Q 1 gives better information than Q 2 . This shows again that, for unbalanced bipartitions (and even in the case of a relatively small number of individual components of the total system), Q 2 works much better than Q 1 . tion of our results, consider teracting with a spin system of which lives in a d s dimenfore the total system Hilbert ⇥ (d s ) n s . Let us suppose the 0 spin 1/2 (which is a relafar from its thermodynamic d M = 2 10 . For such a system, the critical value of purity P c in Eq. ( 22) is

P c = 2 11 1 2 11 ⇣ p 2 11 2 ⌘ 2 + 2 11 1 ⇠ 0.000534. ( 23
)
The lower value of purity for which bipartite entanglement can survive is, as said before, P l = 1 d 1 ⇠ 0.00049. Therefore, for all the total states having purity 0.000534  P (⇢)  1, bound Q 2 in Eq. ( 19) works better than Q 1 . Only for the small fraction of states having an extremely low purity in the range [0.00049, 0.000534] bound Q 1 gives better information than Q 2 .

This shows again that, for unbalanced bipartitions (and even in the case of a relative small number of individual components of the total system), Q 2 works much better than Q 1 .

IV. CONCLUSIONS

Incidentally, bounds like Eqs. ( 5), ( 19) and [START_REF] Guhne | Estimating Entanglement Measures in Experiments[END_REF] show the underlying physics behind results, such as those shown in [START_REF] Wei | Maximal entanglement versus entropy for mixed quantum states[END_REF], connecting Negativity and heat capacity in a thermal bipartite state. Heat capacity is, indeed, a measure of the mixedness of energy levels within a Gibbs state and is therefore strongly a↵ected by the purity itself.

ACKNOWLEDGMENTS FIG. 4: (Color online) ∆1 (light red triangles) and ∆2(dark blue circles) evaluated for 1000 randomly generated bipartite with dM = dm + 70 and dm randomly chosen in [START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF]. For these strongly unbalanced bipartitions we always detect ∆1 > ∆2.

The inset shows the difference ∆1 -∆2.

V. APPLICATION TO THERMAL ENTANGLEMENT

Of particular interest is the of the results of this paper to the case of thermal entanglement, where both Linear Entropy and its link to Negativity acquire a much clearer meaning. A recent result [START_REF] Popescu | Entanglement and the foundations of statistical mechanics[END_REF], indeed, shows how the canonical ensemble description of thermal equilibrium stems from the existence of quantum correlations between a system and its thermal bath. In view of this it has been shown that it is possible, with a very small statistical error, to replace the system + bath microcanonical ensemble with a pure state inside the suitable energy shell, still obtaining the appropriate thermal statistics characterizing Gibbs distribution. In this context, then, the Linear Entropy of the mixed Gibbs state provides a system/bath entanglement measure. Equation [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF] then can be viewed as a monogamy relation, describing the competition between two kinds of quantum correlations -internal ones measured by Negativity and external ones measured by Entropy. On the other hand it is known that some thermodynamic quantities (like e.g. heat capacity or internal energy) can be used as entanglement witnesses [START_REF] Wiesniak | Heat capacity as an indicator of entanglement[END_REF], and recent works have shown an even closer link between heat capacity and entanglement for particular systems [30,[START_REF] Leggio | Heat capacity and entanglement measure in a simple two-qubit model[END_REF]. The result of this paper suggests this link might hold very generally. Indeed, in the case of a Gibbs equilibrium state, P E can be given by the expression

P E = i =j e -βEi e -βEj Z 2 = i =j P ij E ( 22
)
where E i is the i-th energy level of the system and Z is its partition function, β being the inverse temperature in units of k B . Heat capacity in a finite dimensional system reads

C V ≡ β 2 ( H 2 -H 2 ) = β 2 i =j P ij E E i -E j 2 ( 23
)
There is then a similarity between P E and C V as given by equations ( 22) and ( 23), suggesting how a measure of the latter, together with little knowledge about the energy spectrum of the physical system, might supply significant information on the Linear Entropy of the system and, as a consequence, on its maximal degree of internal bipartite entanglement. This triggers interest in further future investigation on a detailed analysis of the relation between P E and C V which, in turn, might supply us with an easily experimentally measurable entanglement bound as well as highlight how the origin of thermodynamical properties is strongly related to non-classical correlations and monogamy effects. Such a connection, and the usefulness of the bounds derived in the previous sections, can be exemplified with a simple three qutrit system with a parameter-dependent Hamiltonian parameter values then one has strong arguments in claiming that such a range is associated to a well defined, almost unchanged value of Heat Capacity. Appendix: Proof of Le tice that both B(t) and 1 the state ⌧ (t) is pure. Inde purity, while B by construc (see equations ( 9)-( 13)). N and B(t) are quadratic in ⌫ statement of Lemma 1 is ind a statement can be rewritten

1 A B d B
The function l(A, B) at the (corresponding to a pure an satisfies [START_REF] Horodecki | Mixed-State Entanglement and Distillation: Is there a Bound Entanglement in Nature?[END_REF]. Appendix: Proof of Le tice that both B(t) and 1 the state ⌧ (t) is pure. Inde purity, while B by construc (see equations ( 9)-( 13)). N and B(t) are quadratic in ⌫ statement of Lemma 1 is ind a statement can be rewritten

1 A B d B
The function l(A, B) at the (corresponding to a pure an satisfies [START_REF] Horodecki | Mixed-State Entanglement and Distillation: Is there a Bound Entanglement in Nature?[END_REF].

H l = ωJ z + τ J 1 • J 2 + (J 1 • J 2 ) 2 + kJ 0 • (J 1 + J 2 ) ( 24
)
where J i is the spin operator of the i-th particle, J = J 0 + J 1 + J 2 . and ω, τ, k are real interaction parameters. This effective Hamiltonian operator describes a system consisting of two ultracold atoms (spins labeled as 1 and 2) in a two-well optical lattice and in the Mott insulator phase, where thus the tunneling term in the usual Bose-Hubbard picture is accounted for as a second order perturbative term, both coupled with a third atom (labeled as 0) via an Heisenberg-like interaction. An external magnetic field is also present, uniformly coupled to the three atoms. Such a system is a generalization of the one studied in [START_REF] Leggio | Heat capacity and entanglement measure in a simple two-qubit model[END_REF], where a deep connection between thermal entanglement and heat capacity in parameter space has been shown. Hamiltonian ( 24) is analytically diagonalizable, thus allowing us to obtain explicit expressions for thermodynamic quantities characterizing the Gibbs equilibrium state of the three-atom system, together with the Negativity of the reduced state of the two quadratically coupled spins. The mathematical origin of the connection between heat capacity and Negativity was already discussed in [START_REF] Leggio | Heat capacity and entanglement measure in a simple two-qubit model[END_REF] and Appendix: Proof of Lemma 1. -Let us first notice that both B(t) and 1 A(t) B(t) go to zero when the state ⌧ (t) is pure. Indeed A + B = Tr⌧ 2 equals the purity, while B by construction vanishes when ⌧ is pure (see equations ( 9)-( 13)). Notice further that both A(t) and B(t) are quadratic in ⌫ (t) and µ ↵ (t) and then the statement of Lemma 1 is independent of their sign. Such a statement can be rewritten as Appendix: Proof of Lemma 1. -Let us first notice that both B(t) and 1 A(t) B(t) go to zero when the state ⌧ (t) is pure. Indeed A + B = Tr⌧ 2 equals the purity, while B by construction vanishes when ⌧ is pure (see equations ( 9)-( 13)). Notice further that both A(t) and B(t) are quadratic in ⌫ (t) and µ ↵ (t) and then the statement of Lemma 1 is independent of their sign. Such a statement can be rewritten as

1 A B d B = l(A, B) 0 ( 23
)
The function l(A, B) at the extremal points of its domain (corresponding to a pure and a maximally mixed state) is ultimately due to the presence of level crossing in the low-lying energy eigenvalues of the system. Here we want to show how the existence of the strong connection between purity and Negativity, expressed by bound [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF], can give some hints for a physical explanation of such an effect, and moreover to exemplify how bound ( 19) can often supply important information on the amount of thermal entanglement. Figure [START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF] shows how the connection between thermal entanglement and heat capacity highlighted in [START_REF] Leggio | Heat capacity and entanglement measure in a simple two-qubit model[END_REF] is still present despite the interaction with a third atom. Figures [START_REF] Takayanagi | Towards an entanglement measure for mixed states in CFTs based on relative entropy[END_REF] and [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF] show bounds ( 5) and ( 17), together with the Negativity of the reduced state of two atoms, versus a certain interaction parameter in the Hamiltonian. Figure [START_REF] Datta | Role of entanglement and correlations in mixed-state quantum computation[END_REF] finally shows the same quantities versus temperature for fixed Hamiltonian parameters. All energies in the plots are expressed in units of ω. It is worth stressing here that, in all these plots, bound Q 3 = Θ( d-2 d-1 -P E ) is not shown. The reason is that, in order to preserve thermal entanglement, temperature in our simulations has to be kept at most of the same order of magnitude of spin-spin interactions, and in such a regime P E has not yet crossed the threshold d-2 d-1 so that Q 3 is constantly equal to one. It is clearly shown in Figures [START_REF] Takayanagi | Towards an entanglement measure for mixed states in CFTs based on relative entropy[END_REF] and ( 8) how bound Q 1 given in (5) can become, as discussed, larger than 1. In all these cases (except for a small temperature range in Figure [START_REF] Datta | Role of entanglement and correlations in mixed-state quantum computation[END_REF], however, ( 17) is still able to sensibly bound Negativity. In all the plots shown, and in general every time the bounds ( 5) and ( 17) are applied to the particular system analyzed here, one always gets useful information about bipartite entanglement in the form, of course, of an upper bound. Such a bound, however, gets very close to zero in some particular cases (see, for example, Figures [START_REF] Jozsa | On the role of entanglement in quantum-computational speed-up[END_REF] and ( 8)), strongly restricting the allowed range of values for the Negativity. It is then shown that ( 19) is able to produce non-trivial results. It is worthy noting from that in Fig. [START_REF] Van Nieuwenburg | Entanglement spectrum of mixed states[END_REF] there exist ranges of the parameter γ where the Negativity and the Heat Capacity exhibit simultaneous plateaus. This fact, previously shown and commented in reference [START_REF] Leggio | Heat capacity and entanglement measure in a simple two-qubit model[END_REF] too, in view of Equation [START_REF] Cramer | Measuring Entanglement in Condensed Matter Systems[END_REF] and the strong link between Heat Capacity and the mixedness P E of a quantum state legitimates the deduction that in the parameter regions of very low Negativity the Heat capacity may be assumed as almost constant.

VI. CONCLUSIONS

In this paper we derived a bound on the degree of information storable as bipartite quantum entanglement within an open d-dimensional quantum system in terms of its Linear Entropy. Our result is quite general, holding for arbitrary bipartitions of an as well arbitrary system. We emphasize that our result is experimentally appreciable in view of quite recently proposed protocols aimed at measuring the Purity of a state of a quantum system. Inspired by the seminal paper of Popescu, Short and Winter [START_REF] Popescu | Entanglement and the foundations of statistical mechanics[END_REF], our conclusions highlight the interplay between quantum entanglement inside a thermalized system and its physical properties. Our results are of interest not only for the Quantum Information researchers but also for the growing cross-community of theoreticians and experimentalists investigating the subtle underlying link between quantum features and thermodynamics.

VII. APPENDIX

Proof of Lemma 1. Let us first notice that both B(t) and 1 -A(t) -B(t) go to zero when the state τ (t) is pure. Indeed A + B = Trτ 2 equals the purity, while B by construction vanishes when τ is pure (see Equations ( 9)-( 13)). Notice further that both A(t) and B(t) are quadratic in ν β (t) and µ α (t) and then the statement of Lemma 1 is independent of their sign. Such a statement can be rewritten as

1 -A -B d -B = l(A, B) ≥ 0 (25)
The function l(A, B) at the extremal points of its domain (corresponding to a pure and a maximally mixed state) satisfies [START_REF] Zyczkowski | Volume of the set of separable states[END_REF] We can address the investigation on internal points using the Lagrange multiplier method, taking into account the trace condition nα α µ 2 α + n β β ν 2 β = 1. From this method only one stationary point results, characterized by values of ν β and µ α such that the corresponding state is mixed. It is straightforward to check that at this point the function ( 26) is positive. We then deduce that l(A, B) ≥ 0, from which Lemma 1 directly follows. Finally, the range δ of validity of Lemma 1 is given by the requirement q R (t) ≥ q i =R (t), such a property being necessary for the sensible definition of the reference pure state σ R which guarantees, in turn, that B(t) vanishes on pure states.

FIG. 1 :

 1 FIG. 1: (Color online) Purity threshold Pc given in Eq. (20) (green surface) and natural purity limits 1 (blue upper surface) and 1 d (red lower surface) as functions of d ∈ [4, 1000] and dm ∈ [2, 25] such that d 2 m ≤ d. Values of purity below the green surface are such that Q1 < Q2, while values of purity above the green surface yield Q2 < Q1. It is clear that, when d 2 m < d, Pc ∼ 1 d meaning that Q2 < Q1 for most of quantum states. On the other hand, when d 2 m ∼ d and Q1 < Q2 almost everywhere in state space.

  2) of the bounds with the Negativity of the state, once a bipartition has been fixed. In particular, in a first run of simulations (Fig. (2)) we generated 10 3 perfectly balanced bipartite states (such that d m = d M = √ d), randomly choosing the dimension of the two subsystems for each quantum state within the range d M = d m ∈ [2, 10]. The results in Fig. (

FIG. 2 .

 2 FIG. 2. (Color online)1 (light red triangles) and 2 (dark blue circles) evaluated for 1000 randomly generated bipartite states, with d m = d M randomly chosen in[START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Kus | Geometry of entangled states[END_REF]. For these perfectly balanced bipartite states 1 < 2 everywhere in state space.

FIG. 4 .

 4 FIG. 4. (Color online) 1 (light blue circles) evaluated for 1000 r states, with d M = d m + 70 and d For these strongly unbalanced b 1 > 2 . The inset shows the d

FIG. 2 :

 2 FIG.2:((Color online) ∆1 (light red triangles) and ∆2 (dark blue circles) evaluated for 1000 randomly generated bipartite states, with dm = dM randomly chosen in[START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Kus | Geometry of entangled states[END_REF]. For these perfectly balanced bipartite states ∆1 < ∆2 everywhere in state space.FIG. 2. (Color online)1 (light red triangles) and 2 (dark blue circles) evaluated for 1000 randomly generated bipartite states, with d m = d M randomly chosen in[START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Kus | Geometry of entangled states[END_REF]. For these perfectly balanced bipartite states 1 < 2 everywhere in state space.

FIG. 4 .

 4 FIG. 4. (Color online) 1 (light blue circles) evaluated for 1000 states, with d M = d m + 70 and For these strongly unbalanced b 1 > 2 . The inset shows the d

FIG. 3 :

 3 FIG. 3: (Color online) ∆1 (light red triangles) and ∆2 (dark blue circles) evaluated for 1000 randomly generated bipartite states, with dM = dm + 60 and dm randomly chosen in [2, 10]. Since the bipartitions are no longer perfectly balanced, there is a much broader mixing of values of ∆1 and ∆2. In particular, ∆1 has a much wider distribution of values, while ∆2 seems to have a much denser distribution around central values. The inset shows the difference ∆1 -∆2.

5

  ht red triangles) and 2 (dark 0 randomly generated bipartite ly chosen in[START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Kus | Geometry of entangled states[END_REF]. For these tates 1 < 2 everywhere in ht red triangles) and 2 (dark 0 randomly generated bipartite d m randomly chosen in[START_REF] Horodecki | Quantum entanglement[END_REF][START_REF] Kus | Geometry of entangled states[END_REF]. onger perfefctly balanced, there values of 1 and 2 . In parr distribution of values, while ser distribution around central i↵erence 1 2 .

FIG. 4 .

 4 FIG. 4. (Color online) 1 (light red triangles) and 2 (dark blue circles) evaluated for 1000 randomly generated bipartite states, with d M = d m + 70 and d m randomly chosen in [2, 5]. For these strongly unbalanced bipartitions we always detect 1 > 2 . The inset shows the di↵erence 1 2 .

Fig. 1 :

 1 Fig. 1: Negativity of reduced state of the two ultracold atoms (full line) and Heat Capacity of the system (dashed line) versus quadratic interaction parameter . The other parameters have been fixed as k B T = 2, ⌧ = 3 and k = 1.

Fig. 2 :

 2 Fig. 2: Negativity of reduced state of the two ultracold atoms (full line), bound Q 1 (dotted line) and bound Q 2 (dashed line) versus quadratic interaction parameter . The other parameters have been fixed as k B T = 2, ⌧ = 3 and k = 1.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Negativity of reduced s (full bound Q 1 (dotted li versus Heisenberg interaction eters have been fixed as k B T =

5 FIG. 5 :Fig. 1 :Fig. 2 :Fig. 3 :Fig. 4 :

 551234 FIG. 5: Negativity of reduced state of the two ultracold atoms (full line) and Capacity of the system (dashed line) versus quadratic interaction parameter γ. The other parameters have been fixed as kBT = 2, τ = 3, and k = 1.Fig. 1: Negativity of reduced state of the two ultracold atoms (full line) and Heat Capacity of the system (dashed line) versus quadratic interaction parameter . The other parameters have been fixed as k B T = 2, ⌧ = 3 and k = 1.

5 FIG. 6 :

 56 FIG. 6: Negativity of reduced state of the two ultracold atoms (full line), bound Q1 (dotted line) and bound Q2 (dashed line) versus quadratic interaction parameter γ. The other parameters have been fixed as kBT = 2, τ = 3, and k = 1.

  ate of the two ultracold atoms he system (dashed line) versus . The other parameters have d k = 1. ate of the two ultracold atoms e) and bound Q 2 (dashed line) ameter . The other parame-, ⌧ = 3 and k = 1.

Fig. 3 :

 3 Fig. 3: Negativity of reduced state of the two ultracold atoms (full line), bound Q 1 (dotted line) and bound Q 2 (dashed line) versus Heisenberg interaction parameter k. The other parameters have been fixed as k B T = 10, ⌧ = 3 and = 1.

Fig. 4 :

 4 Fig. 4: Negativity of reduced state of the two ultracold atoms (full line), bound Q 1 (dotted line) and bound Q 2 (dashed line) versus temperature T (in units of k B ). The interaction parameters have been fixed as ⌧ = 4, k = 5 and = 1.

FIG. 7 :

 7 FIG. 7: Negativity of reduced state of the two ultracold atoms (full line), bound Q1 (dotted line) and bound Q2 (dashed line) versus Heisenberg interaction parameter k. The other parameters have been fixed as kBT = 10, τ = 3, and γ = 1.

Fig. 3 :

 3 Fig. 3: Negativity of reduced state of the two ultracold atoms (full line), bound Q 1 (dotted line) and bound Q 2 (dashed line) versus Heisenberg interaction parameter k. The other parameters have been fixed as k B T = 10, ⌧ = 3 and = 1.

Fig. 4 :

 4 Fig. 4: Negativity of reduced state of the two ultracold atoms (full line), bound Q 1 (dotted line) and bound Q 2 (dashed line) versus temperature T (in units of k B ). The interaction parameters have been fixed as ⌧ = 4, k = 5 and = 1.

FIG. 8 :

 8 FIG.8: Negativity of reduced state of the two ultracold atoms (full line), bound Q1 (dotted line) and bound Q2 (dashed line) versus temperature T (in units of kB). The interaction parameters have been fixed as τ = 4, k = 5 and γ = 1.

  For a maximally mixed state, calling n α (n β ) the number of α-(β-)class eigenvalues (n α + n β ), one gets A = nα d 2 and B = n β d 2 and thus l = nα-1 d 2 ≥ 0 since n α ≥ 1. Let us now express l(A, B) as h({µ α }, {ν β })

[1] Guhne, O. and Seevinck, M. Separability criteria genuine multiparticle entanglement, New. J. Phys. 2010, 12, 053002

Acknowledgments

A.M. acknowledges the kind hospitality provided by HN at the Physics Department of Waseda University on November 2019. All the authors are grateful to Marek Kus for his constructive and stimulating suggestion and for carefully reading the manuscript. HN was partly supported by Waseda University Grant for Special Research Projects (Project number: 2019C-256).