Vassili Rivron
email: vassili.rivron@inria.fr

Mohammad Irfan Khan
email: mohammad-irfan.khan@inria.fr

Simon Charneau
email: simon.charneau@inria.fr

Isabelle Chrisment
email: isabelle.chrisment@loria.fr

Exploring Smartphone Application Usage Logs with Declared Sociological Information

In this paper we present an exploratory smartphone usage study with logs collected from users in the wild, combined with the sociodemographic, technological and cultural information provided by them. We observe a high diversity among users' most used applications, but by classifying applications into services we find significant correlations between service usage and socio-demographic profile. We discuss that sociological information has rich potential in characterizing smartphone usage and can be applied to interesting incentive strategies and use cases based on users' sociological context.

I. INTRODUCTION

Since the launching of the touchscreen mobile phones in 2007, the number of smartphone users and the applications and services offered on mobile platforms have grown exponentially, transforming the communication, cultural, media and entertainment practices and, at the same time, the possibilities for scientists to observe them. This growth has mainly led to a rising interest by ISPs, content providers, governments and audience measurement companies to analyze the population's smartphone usage. However, the data collected by those entities are seldom open or made available to the scientific community.

Numerous studies have been conducted within the IT community over the last five years to study people's smartphone usage. These studies mainly look at the smartphone usage pattern, the usage context, the user privacy and security with implications such as enhancing quality of service, reducing power consumption, improving content caching, management and delivery. However, one particular aspect that has been lacking among these scientific studies is that not enough consideration is given to socio-demographic and lifestyle aspects of users. Even a few interdisciplinary studies focus on usage patterns as behavioral or interaction indicators, but, due to the nature of their datasets and theoretical positions, they rarely explore further social and cultural implications of usage profiling, or reduce it to economic or generational factors. Our approach is not incompatible with uses and gratifications theory [START_REF] Ruggiero | Uses and gratifications theory in the 21st century[END_REF], but, inspired from sociology of cultural practices [START_REF] Donnat | Cultural practice and internet usage[END_REF], it broadens a common "context" conception from actual situation [START_REF] Do | Smartphone usage in the wild: A large-scale analysis of applications and context[END_REF], to social and cultural structures that are involved in the construction of the needs (which are not the same for all) and of the conditions of their satisfaction.

In this exploratory paper we analyze the application popularity among a small set of users and show the enormous diversity that exists among them. Due to this diversity it is not feasible to relate the popularity of specific applications with particular socio-demographic profiles. Nevertheless, when we group the applications according to the kind of service or content they provide, we find interesting relations among user profiles and popularity of particular types of application. Moreover, we discuss how the combination of sociological declared data of users could be used to renew the statistics methodology, to improve application recommendation on application stores or to optimize the device's performance.

For our study we invited the general public to participate and contribute with anonymous smartphone usage logs, by respecting privacy and in the most natural settings (their own device and tariff plan). Besides, we used a questionnaire to accompany the usage logs, to gather anonymous sociodemographic data of the users along with some questions regarding lifestyle and smartphone usage. This experiment was conducted in the context of building a french countrywide open Internet observation platform called Metroscope 1 , for the scientific study of fixed and mobile Internet from a neutral perspective. Our main contributions in this paper are: 1) We show that most of the usage time is due to a set of few applications, which for most users remains relatively constant over time, illustrating different appropriation of the device in daily routine.

2) We show that there is a significant diversity in terms of application popularity, even among demographically similar users, making it infeasible to associate application usage with user profile.

3) We group applications into types of services and explore several methodologies to correlate service usage and users' socio-demographic, technological and cultural profile.

II. RELATED WORK

Similarly to our approach, most past studies about smartphone usage involve either logs collection by deploying passive sensors on users' smartphones [START_REF] Falaki | Diversity in smartphone usage[END_REF], [START_REF] Bohmer | Falling asleep with angry birds, facebook and kindle: A large scale study mobil application usage[END_REF], [START_REF] Do | Smartphone usage in the wild: A large-scale analysis of applications and context[END_REF], [START_REF] Falaki | A first look at traffic on smartphones[END_REF], or from the ISP side [START_REF] Xu | Identifying diverse usage behaviors of smartphone apps[END_REF] or a combination of both [START_REF] Gember | Obtaining in-context measurements of cellular network performance[END_REF]. Some others [START_REF] Bohmer | Falling asleep with angry birds, facebook and kindle: A large scale study mobil application usage[END_REF] even gather traces from users' phones by implementing sensors in other applications downloaded from application stores, perhaps without users' informed consent. Only two studies [START_REF] Wagner | Device analyzer: Understanding smartphone usage[END_REF], [START_REF] Tossell | Getting real: a naturalistic methodology for using smartphones to collect mediated communications[END_REF] collect usage logs in the wild as we do, but they do not collect profile information about users.

There have been several researches on application usage such as [START_REF] Do | Smartphone usage in the wild: A large-scale analysis of applications and context[END_REF], [START_REF] Xu | Identifying diverse usage behaviors of smartphone apps[END_REF]. They consider some common metrics of smartphone usage, such as usage duration, frequency, temporal and diurnal patterns. Some of these studies relate smartphone usage with contextual factors such as usage location and social surrounding [START_REF] Do | Smartphone usage in the wild: A large-scale analysis of applications and context[END_REF], geography [START_REF] Xu | Identifying diverse usage behaviors of smartphone apps[END_REF] etc. In a more qualitative approach, a previous exploitation of our own survey that combines usage logs, multiple choices questionnaires and interviews, was done to understand how the smartphone usage both reveals and modifies the social rhythms of student lifestyle [START_REF] Ouakrat | Du rythme d'usage du smartphone aux rythmes de vie: les normes temporelles informelles des pratiques d'une population étudiante[END_REF].

Bohmer et al. [START_REF] Bohmer | Falling asleep with angry birds, facebook and kindle: A large scale study mobil application usage[END_REF] and Trinh et al. [START_REF] Do | By their apps you shall understand them: Mining large-scale patterns of mobile phone usage[END_REF] study smartphone usage patterns by considering applications which are used together. ] Fig. 1: Data Collection platform Joon et al. [START_REF] Kang | Usage pattern analysis of smartphones[END_REF] show some basic data on sessions, usage and traffic. They work on smartphone battery optimization as a use case. Stober et al. [START_REF] Stober | Who do you sync you are?: Smartphone fingerprinting via application behaviour[END_REF] fingerprint individual smartphones based on background traffic of popular applications. Rahmati et al. [START_REF] Rahmati | Studying smartphone usage: Lessons from a four-month field study[END_REF] study usage behavior but only specific to first time smartphone users. Falaki et al. [START_REF] Falaki | Diversity in smartphone usage[END_REF] analyze various aspects of smartphone usage and present usage diversity among users in terms of usage duration, frequency, traffic volume, with some statistical distribution of diverse usage patterns. However none of these studies sufficiently face the huge diversity of application popularity among users.

Machine learning techniques have also been applied to learn individual application usage patterns and to exploit them for user experience improvement, such as faster app launching [START_REF] Yan | Fast app launching for mobile devices using predictive user context[END_REF], [START_REF] Srinivasan | Mobileminer: Mining your frequent patterns on your phone[END_REF], better app organization [START_REF] Shin | Understanding and prediction of mobile application usage for smart phones[END_REF], app recommender system [START_REF] Bohmer | Appfunnel: A framework for usage-centric evaluation of recommender systems that suggest mobile applications[END_REF].

Although these studies produce interesting results about various aspects of smartphone usage, none of these thoroughly consider users' socio-demographic profile or find relations between demographic data and smartphone usage. We in our paper address this point and use social science methods to find correlation between users' socio-demographic data and mobile phone usage patterns.

There have been some sociological studies which show the importance of socio-demographic factors in understanding the diverse uses of digital technologies [START_REF] Donnat | Cultural practice and internet usage[END_REF]. However, apart from some audience measurement companies (such as Nielsen or Mediamétrie in France), there are very few studies by sociologists which analyze usage traces in combination with demographic data. Some papers combine Internet usage logs on personal computers with demographic data for usage analysis [START_REF] Beauvisage | From user-centric web traffic data to usage data[END_REF], [START_REF] Beauvisage | Computer usage in daily life[END_REF]. And, closer to our interests, some other studies [START_REF] Licoppe | Using mobile phone geolocalisation for 'socio-geographical'analysis of coordination, urban mobilities, and social integration patterns[END_REF] have experimented the translation of usage logs (such as phone calls) into sociological indicators such as social capital or employability.

III. DATA COLLECTION AND DATASET

Our data collection platform called Apisense [START_REF] Haderer | Dynamic deployment of sensing experiments in the wild using smartphones[END_REF], which as shown in Figure 1, is composed of a client application running on the background (available on Android OS only, at the time of the experiment), a central server and a logs collection or sensing server.

In order to carry out an experiment, a scientist registers on the central server [START_REF] Ruggiero | Uses and gratifications theory in the 21st century[END_REF] and deploys an experiment's scripts on the sensing server [START_REF] Donnat | Cultural practice and internet usage[END_REF] and the experiment appears on the Store of the central server [START_REF] Do | Smartphone usage in the wild: A large-scale analysis of applications and context[END_REF]. A participant installs the sensing application (4) and after registration to the experiment, the sensing application downloads the scripts from the sensing server [START_REF] Bohmer | Falling asleep with angry birds, facebook and kindle: A large scale study mobil application usage[END_REF]. The logs are stored on the phone and periodically uploaded to the collection server via Wi-Fi network [START_REF] Falaki | A first look at traffic on smartphones[END_REF]. A Multiple Choice Questionnaire (MCQ) was also installed on the client application containing questions about sociodemographic, technological and cultural profile of the user, and could be uploaded similarly.

Convincing the crowd to contribute smartphone usage logs is quite difficult due to privacy and performance concerns (although our setup handles these issues). Therefore we organized a contest called PRACTIC [START_REF] V. Rivron | Refining smartphone usage analysis by combining crowdsensing and survey[END_REF] and invited the public to participate and win prizes based on their level of contribution and recruitment of other participants.

The campaign was organized between 10 March and 20 April 2014, for six weeks and attracted 260 participants from several cities in France. All 260 participants filled the multiple choices questionnaire while only 97 of them also installed the client application, because of system requirements (Android Only), privacy or incentive reasons. Out of those 97 users, only 42 users produced logs continuously for at least two weeks with complete questionnaire, which make our dataset for this paper. This filtration criteria of logs continuity for a minimum duration of two weeks was important because we study usage patterns in terms of lifestyle routines and cultural habits. Therefore we had to sacrifice on the quantity of users to get homogeneous quality logs, a selection that is common with other crowdsourced studies [START_REF] Hamka | Mobile customer segmentation based on smartphone measurement[END_REF].

The participation duration of these 42 users varied from 17 to 139 days (some users continued even beyond the contest), with an average of 53 days and median 58 days. It represents 3621 hours of smartphone usage logs, from the usage of 929 different applications by the participants. Table I shows the statistics about the dataset and reveals the predominant IT scholar composition of our sample (due to the campaign's dissemination launching channels). This composition leads to a representativity bias that we will discuss in section VI.

IV. APPLICATION USAGE DIVERSITY

In this section we analyze how the smartphone is used by users i.e. for what applications and services. We first present the distribution of application popularity among users at an aggregate time scale. This is followed by an analysis at a finer time scale i.e. whether the set of popular applications remains constant or how those vary on a daily or other cyclic basis. Subsequently we compare between users their sets of most popular apps and show the enormous diversity which exists among users.

A. Application Usage Distribution per User

We measure smartphone usage with two basic metrics: usage duration and usage frequency. Usage duration is calculated for only the period during which the user is interacting with the phone i.e. application is running on the foreground. Similarly usage frequency is the number of times the application is launched or comes to foreground. For most applications, both metrics are pertinent, while for some applications such as GPS, usage duration is more relevant. Whenever the two metrics tend to provide similar results, we mostly present our findings for duration only. For applications that can also be considered as directly used even when running in background, such as phonecalls or music, we only considered frequency.

In order to analyze application popularity for a user, we calculate how many applications consume what percentage of usage time and usage frequency. Figure 2 shows the distribution of the most popular applications in terms of usage duration. In the graph the x-axis represents the Top applications (1 to 10) resulting the most usage duration and the y-axis shows the percentage of usage time due to those applications, averaged for 42 users with 95% Confidence Interval. The graph shows that the most used application causes about 35% of usage time and only 3 top applications account for 60% of usage time. The next 7 applications among the Top 10 only add 20% of usage time, giving a ratio of 10 applications being used 80% of the time. The application popularity in terms of frequency shows very similar results. Even though at an average, each phone in our dataset contains around 84 applications, either pre-installed or installed by the user, but only less than 10 applications are actually used most of the time, a fact that is also demonstrated by other studies [START_REF] Falaki | Diversity in smartphone usage[END_REF]. Thus in this paper, we 2 shows the most common applications among the Top10 lists of the users and the number of users who have the application in his Top10 list.

B. Temporal Regularity of Most Used Apps

The ratio presented above (3 apps causing 60% and 10 apps causing 80% of usage time) is calculated at an aggregate time scale for the whole participation duration of each user. Here we analyze how do the Top10 popular apps vary or remain constant over time for each user.

Figure 3 shows how the popular apps for the users are regularly used or persistent, considering periods of 1 (daily), 2 and 3 days cycles.

Everyday: As shown by the leftmost bar, 12% users (in blue on top) have 3 or 4 apps which appear daily on his list of Top10 apps. These users make high usage of 3 to 4 specific applications every single day. However 50% of users (in gray) have no such application which ranks on the Top10 list every consecutive day.

day cycle:

The number of regularly used applications improves drastically when a cycle of 3 days is considered (rightmost bar). We see that more than 40% of users (green portion) have at least 5 such apps which ranks on his Top10 list during every 3 day cycle.

In terms of granularity, a cycle of 3 days is relevant, indicating that a user may not use an application everyday, nevertheless that application is among his most used apps over a 3 day period. This is acceptable and still describes social routines, Fig. 4: Average Jaccard Index for comparison of most used applications of each user with others because app usage patterns vary between weekdays/weekends and also due to temporal lifestyle change as we discussed in another paper [START_REF] V. Rivron | Refining smartphone usage analysis by combining crowdsensing and survey[END_REF].

Similarly we also found that the 3 most used apps which rank regularly among the Top10 of every 3 day cycle are also present on the user's list of 10 most used apps for the whole participation duration. Thus it can be concluded that the ratio of 3 apps causing of 60% usage time, holds true not only at an aggregate time scale but also over short time scale.

C. Diversity of Application Popularity among Users

As each individual in our dataset can be associated to only a handful of applications he uses most of the time, we would like to know whether these applications are similar or diversified between one user and another. Here we compare the set of popular applications of each individual user with 41 other users and analyze the general trend of popular application commonality among the 42 users. We use the Jaccard Index to pairwise compare the set of the most used applications of each user with all other users. The index is calculated by dividing the intersection by the union of the two sets. Its value ranges from 0 (when intersection=0 i.e. maximum diversity), to 1 (when intersection=union i.e. minimum diversity).

J(A, B) = |A ∩ B| |A ∪ B| ; 0 ≤ J(A, B) ≤ 1 (1)
In our set of 42 users we have: N(N-1)/2 or 861 pairs and each pair is commutative as A∩B = B∩A. For each set size (Top 1 to Top 10 apps per set) the average of 861 Jaccard Indices is calculated, such as:

AvgJaccardIndex = 861 i=1 J i (A, B) 861 (2)
Figure 4 shows the average Jaccard Index versus the set size.

The Jaccard Indices result from the comparison of the top apps, in terms of duration, among users. When only top 1 application is compared among users, the level of diversity or the Jaccard Index is highest. The average Jaccard Index increases with increased set size as because the larger the set, the higher is the probability of obtaining common items between them. Nevertheless, for set size of 3 (60% usage time) and set size of 10 (80% usage time) the average Jaccard Index is quite close to zero, which is the level of maximum diversity.

Table III details the comparison results when the set size is 3 and 10 (Top3 and Top10 apps respectively). Among their Top 3 app set (middle column), 643 pairs do not have any application in common. Some pairs have one or two applications in common and not a single pair has 3 applications in common.

A similar pattern is visible for the comparison of Top 10 application set and only one pair of users has a maximum of 6 applications in common. Thus it indicates that there is a large degree of diversity among users in terms of usage duration for their most used applications (the sessions frequency show very similar results).

Moreover it has to be noted that our population set is not highly varied demographically i.e. 60% are students, 59% aged between 17-25 years and 68% in the same domain of activity, as shown in Table I. However each user mostly uses applications which are different from other users.

As a result of this high diversity of application usage, it is not feasible to relate the social profile of each user with the exact applications he uses.

V. USAGE ANALYSIS IN TERMS OF SERVICES

The last section demonstrated the large diversity in the application usage, which prevented the comparison of smartphone users in terms of application usage. In this section we group the applications into categories of services in order to show how the usage of certain services can be related to sociodemographic profiles. In addition to demographic data, we also discuss how smartphone usage can be related to other factors of lifestyle, technological and cultural habits.

A. Application Categorization by Service

During their participation, the 42 users of our dataset used a total of 929 different applications and 149 of those applications were on the list of Top 10 apps of all users. In order to categorize the apps as services we could not fully rely on the Google Play Store as its categorization is not highly methodical. Rather, each application developer assigns a category based on strategies such as commercial motives, category competition, recommendation of ranking services (ex: www.applyzer.com).

Our application categorization is done in three steps: 1) assign our own category based on the app's description. 2) compare it to the category of Google Play Store. 3) in case of a mismatch or absent on Google Play Store, decide based on further information from the web. Nevertheless, for nonambiguous types such as Weather, Transport, Games our own categorization matched mostly with Google Play Store. Thus we classified the 149 different applications in the Top10 list of all users into 26 different service types. Figure 5 shows the 17 most used types of services we defined through this method. IV, which are just some of the many questions answered by the participants. The parameter values divide our user population into various demographic groups. For each sociological parameter, we compare the average usage of different services between the groups such as Male vs Female, Student vs Working, as shown in Figure 5. As the smartphone usage is deeply embedded within people's lifestyle, profession, social behavior, amusement habits, we expected that some classes of the population would use some types of services more than other classes. To ensure whether the usage difference of a particular service between two groups is really due to the demographic parameter, we conducted the two-sample t-test (assuming equal variances, significance level: 0.05) and calculated the two-tailed p-value. If the p-value was 0.04 or less, we accepted the relation. In order to elaborate indicators that take into account the duration, the frequency and the most used apps per user, we have considered four metrics to evaluate and compare the usage of a service type by a demographic group. Metric 1 is the percentage of total usage duration resulted by a particular service type and Metric 2 is the percentage of total usage frequency due to that service type. Metric 3 is the average minutes spent on that service per day and Metric 4 is the average number of times the service is used per day.

Moreover, Metrics 1 and 2, have been multiplied by a coefficient and corrected to take into account the importance of the service for a particular user. To calculate the coefficient, the services used by a user are ranked (from highest to lowest) according to the percentage of contribution of each service towards the total usage. The actual percentage is lowered for lower ranked services as:

Corrected Percentage = Actual Percentage x Rank of the service ÷ Total Nb of services Example: User 1 and 2 both use 10 services in total.

For user 1, voice call is ranked 10 (the highest rank) and accounts for 20% of his total usage duration. For user 2, voice call is also responsible for 20% of his usage duration, but is ranked 7th. So for user 1, the corrected % of voice call is: (20x10)÷10 = 20% and for user 2 it is: (20x7)÷10 = 14%.

C. Service Usage and Socio-demographic Factors

Here we analyze the usage difference between demographic groups for particular types of services and present some hypotheses.

Professional Factors: In our dataset, the most distinctive difference is in terms of telephone usage, i.e. people who are married, older, professionally active or with higher income use telephone significantly more than people in their opposite group. These 4 parameters are themselves co-related, as people who are students, are younger, earn lesser and are mostly unmarried. Figure 6 shows the difference in telephone usage between students versus people with a job/income for all the 4 metrics. Our metrics show that telephone accounts for 19.0±6.8% of usage time for professionals whereas just 5.2±1.8% for students, p-val < 0.001. A possible factor for this difference is that people who are professionally active use telephone for their work, causing this higher usage.

Similarly, Email is more used by people who are older and professionally active compared to their opposite groups, possibly for professional reasons. Moreover, this difference of Email usage is apparent for Metrics 1 and 2 but not for Metrics 3 and 4. This indicates that although their is no significant difference between professionals/older people and students/younger people in terms of their daily Email usage, for the former group, Email is a higher ranked than for the latter group, which creates the differences of Metrics 1 and 2 compared to Metrics 3 and 4.

Economic Factors: Similarly there is also an economic factor i.e. unlimited telephone/voice plans are more expensive, which younger people with limited budget cannot afford. However, the least expensive phone plan in France, offer unlimited SMS. So student/younger people prefer SMS over phone call, and the number of SMS sent by younger people (33±18.4 SMS/day), is superior to the ones of older people (7.2±5.6 SMS/day).

Age vs Technological Preference: Another explanation of younger people using more SMS is related to the generational effect of technological preference. Text/SMS is the preferred medium of social conversation for teens compared to voice call [START_REF] Lenhart | Teens, smartphones & texting[END_REF]. There can be several reasons for this, such as SMS provides the required privacy desired by teens during communication, for example in a classroom or when surrounded by adults.

In out dataset, the average duration of a SMS session of people aged 17-22 years is 40.2 seconds with standard deviation 23 sec compared to average of 31.1 seconds, (SD 19 sec) for people aged 29+. Although the standard deviation is high, we also observed that more frequently for younger people, one SMS followed a chain of other SMSs in a short span of time, suggesting a session of conversation. Whereas older people's SMS sessions were shorter in duration and tented to be sporadic, suggesting the use of SMS for sending factual information or any short or rapid communication.

GPS vs

Gender & Smartphone Quality: We characterize the phone models of our participants based on the classification specified by the phone manufacturer into high-end and low/medium-end. In our dataset, applications which require geo-localization such as travel/tourism are more used on higher-end phones, 4.3±2.3% of total usage duration vs 0.3±0.3% on lower-end models, as shown in Figure 7 (metric 1). Moreover, 85% of males in our dataset use a high-end smartphone while a lesser number of women (63%) use a highend model. This is coherent with a survey of Nielsen 2 , which shows that males are more attentive towards technical specifications of smartphones, whereas women are more concerned about price, contract options and aesthetics.

However, we cannot hypothesize any economic relation in this case because there are more females who are professionally active in our dataset than males. Nevertheless, the males who are professionally active are mainly researchers and professors who have generally a wide-scale geographic mobility for 2 http://www.nielsen.com/us/en/insights/news/2014/ the-female-male-digital-divide.html

VI. MULTIPLE CORRESPONDENCE ANALYSIS FOR TECHNOLOGICAL AND CULTURAL HABITS

A. Sociodemographic Factors: Multiple Correspondence Analysis

In the last section, we showed the difference in service usage considering one sociodemographic factor at a time. However more advanced methods can be used such as Multiple Correspondence Analysis (MCA) [START_REF] Hoffman | Interpreting multiple correspondence analysis as a multidimensional scaling method[END_REF] to find the correlation bemeasured service usage frequency and multiple declared factors. MCA is particularly adapted to find correlations in small and non-representative corpora. For example, in the case of Games usage, no clear distinction could be found among population groups by simply comparing the average usage among population groups. Therefore we use MCA on Games and find correlation trends simultaneously among multiple socio-demographic factors, as shown in Figure 8.

In our dataset, gaming applications are used frequently (at least once every 4 days) by everybody except 5 users. We elaborated a simple aggregated game usage frequency indicator with 4 degrees of routine usage as: No/Rarely (used only between 0-25% of the days), Occasional: used 25-50% of the days, Recurrent: used 50-75% of the days, Regular: used 75-100% of the days. In figure 8, we have highlighted 3 groups of factors (A, B & C) that are strongly correlated with the users around each zone (marked by grey spots). Dimension 1 represents three demographic parameters: age, marital status and professional activity with discrimination measure = 0.69. Dimension 2 explains the regularity of playing games on smartphones with discrimination measure = 0.85. The reliability of the results is measured by Cronbach's alpha, which is 0.844 and 0.317 for dimensions 1 and 2 respectively. These reliability values are within the acceptable range of 0.7 (subject to discussion), considering our relatively small dataset.

Zone A shows users aged between 17-22 years, who are students and single, appear to play games on phone with recurrent frequency. On the opposite side, zone C shows users who do not play games and are more aged, married and professionally active. In the middle, zone B represents users aged 23-28 years, either student or professional, with an intermediate level of income, who play games either occasionally or regularly.

B. Smartphone Usage Correlation with Cultural Habits

Although MCA is not a highly precise method i.e. does not divide the users into well-defined clusters, it can sense complex multifactorial correlations. Thus using MCA we can represent how smartphone usage is intertwined with complex sociological factors and parameters of lifestyle, technological preferences or cultural profiles.

For example, MCA allows us to identify two different longterm effects of the introduction of the smartphone as a device for entertainment: the different degrees of substitution of entertainment devices and the intensity of entertainment practices. As shown in Figure 9, we associated the degree of regularity of listening to music on smartphones with two factors: i) frequency of focused music listening in general, ii) most preferred device for music listening. These two factors are declared by users on MCQ and music listening regularity on smartphone is obtained from usage logs. The 4 levels of regularity are the same as used earlier for games. By focused music listening, we mean listening attentively to music, for its own sake.

In Figure 9, the discrimination measures do not associate each variable distinctly with any dimension unlike the previous MCA. Nevertheless Cronbach's alpha is satisfactory for both the dimensions i.e. 0.765 and 0.569 respectively. Zone D gives us two information, firstly users who declared to use smartphone as the preferred device for music listening, indeed declared it correctly as determined from their usage logs. Secondly, these users are also music lovers who regularly spend time just listening to music without doing anything else. On the contrary, zones G and F show users who prefer listening to music on Hi-Fi systems or computers, tend to use music as a background ambiance and use smartphone irregularly for music listening.

VII. DISCUSSION AND FURTHER APPLICATIONS

Thus we have shown how smartphone usage is related to not only users' demographic factors but also lifestyle factors such as cultural habits or technological preferences. Considering sociological factors for the analysis of smartphone usage, not only helps to better identify and interpret usage patterns, but on the other hand helps social science to understand the impact of smartphones on people's habits and lifestyle. Despite the limitations of our dataset, our is an interesting path in order to analyze both the reproduction of cultural practices (as developed in French sociological tradition, [START_REF] Fleury | Sociology of Culture and Cultural Practices: The Transformative Power of Institutions[END_REF]) from one technological generation of devices for cultural consumption to another, and also to analyze the modification of cultural behaviours due to portability of devices and accessibility of contents

In further studies, we aim to collect larger and more diversified samples of smartphone operating systems and users, which will enable us to examine more consistently the effects of user class or cultural group. A track to achieve this goal is to design incentive strategies, such as the sensing application would be associated to services that allow users to benefit from gathered data. There is an ongoing study based on similar methods but about network Quality of Experience3 . The goal of this project is to articulate social factors of quality perception, usage patterns and network analysis in order to provide diagnosis and technical support.

However, this kind of perspective does not resolve by itself two major methodological challenges. Even if it is not a totally new topic [START_REF] Bethlehem | Can we make official statistics with self-selection web surveys?[END_REF], and beside the crowdsourcing/sensing disintermediation enthusiasm (skipping the expensive pollsters and collecting extensive datasets per user), these emergent survey techniques create methodological challenges for both social and data scientists. The insurmountable web diffusion bias and technological filters (availability of smartphones in the population and coverage of very diverse operating systems) impose us to rethink the paradigm of representativeness as it is conceived today in surveys and official statistics. Another major challenge for the consolidation of this field of research would be the elaboration of common methodologies and user classifications in order to make cumulative, comparative and periodical studies [START_REF] Brandtzaeg | Towards a unified media-user typology (mut): A meta-analysis and review of the research literature on media-user typologies[END_REF].

Further, another use case of implementing smartphone usage pattern would be to recommend apps based on usage pattern and sociological factors. It is important as we have seen that in our dataset, a smarphone contains 84 apps in average, but only 10 apps are used 80% of the time, suggesting that a lot of apps are downloaded but not used regularly. As the number of apps available on app stores continuously increases, the number of app downloads as surveyed by Stastista, reached over 200bn downloads in 2015 4 . Therefore, the necessity for recommender systems to bring the right app to the right user will increase. Several propositions on recommender systems have been published, which are based on features such as usage pattern [START_REF] Yan | Appjoy: Personalized mobile application discovery[END_REF], usage location [START_REF] Davidsson | Utilizing implicit feedback and context to recommend mobile applications from first use[END_REF], social surrounding [START_REF] Girardello | Appaware: Which mobile applications are hot?[END_REF]. However, these studies have not considered sociological context : the closest parameters to social context are only related with social networks or social surroundings. If an app recommender system knows socio-demography, lifestyle, on-line and offline cultural tastes, amusement habits as part of users' profile, then it can suggest a user about the popular apps currently trending among people sharing those commonalities such as common interests, hobbies, cultural preferences etc. Moreover, sociological information can help improve the precision of application categorization and app developers can provide sociological meta-data about their applications, concerning the potential audience to be interested by the application.

VIII. CONCLUSION

In this study, we have explored several methods to exploit a new generation of tools and data based on the crowdsensing of smartphone usage and combining it to declared about socio-demographics, lifestyle, technological preferences and cultural habits of their users. We have shown that application usage among users is highly diverse. However when the applications are grouped as services, interesting relations appear between user profiles and types of services used. We have discussed that socio-demographic and lifestyle information can be used for user profiling and characterizing smartphone usage pattern. We have proposed several possible use cases of how sociological information can be used to renew the official statistics, to recommend suitable applications to potential users. As part of our ongoing and future work we are building a crowdsourcing model that will increase the incentive for participants and give us a larger dataset. One use case we will consider is to combine sociological information, network access and usage patterns to improve QoS and network troubleshooting for mobile data users.

Fig. 2 :

 2 Fig. 2: Application usage distribution per user

Fig. 3 :

 3 Fig. 3: Persistence of Popular Applications

Fig. 5 :Fig. 6 :

 56 Fig. 5: Comparison of avg daily usage (metric 3) of different services between demographic groups

Fig. 7 :Fig. 8 :

 78 Fig. 7: Use of GPS wrt Smartphone Quality

Fig. 9 :

 9 Fig. 9: Multiple Correspondence Analysis for Music

TABLE I :

 I DataSet Statistics

	Gender	66% male, 34% female
	Profession 60% students, 40% professionals
	Field	68% IT/engineering, 7% humanities/ economics, 25% others

Age

59% 17-25 years, 29% 26-35 years, 12% over 36 Android 3% 2.3.X, 6% 4.0.X 60% 4.1-4.3.X, 31% 4.4.X Brand 37% Samsung , 23% LG, 14% Sony 9% Wiko, 6% Motorola, 11% Others

TABLE II :

 II Most common apps among Top10 list of users

	AppName	Nb of User	AppName	Nb of User
	Chrome	24	Youtube	10
	Facebook	22	2048	9
	SMS/MMS	21	Google Dialer	8
	Hangout	16	WhatsApp	6
	Telephone	15	Candy Crush	5
	Gmail	12	Firefox	5
	Contacts	11	Twitter	5
	Maps	11	Browser	5
	Clock	10	Camera	5
	Gallery	10	Snapchat	5

TABLE III :

 III Number of user pairs having commons apps among their Top3 and Top10 most used apps

	Nb. Of	Nb. Of Pairs in	Nb. Of Pairs in
	Common	Comparison	Comparison
	Apps	of Top3	of Top10
	Zero	643	118
	One	205	266
	Two	13	251
	Three	0	154
	Four	0	59
	Five	0	12
	Six	0	1
	Total:	861	861

TABLE IV :

 IV Sociodemographic Parameters Analyzed

	Sociological Parameters	Parameter Values
	Gender	Male	Female
	Age	17 to 22	23 to 28	29 or +
	Monthly revenue	<1.5k C	1.5k-3k C	3k C +
	Marital Status	Single	Couple/Married
	Nb of Children	0	1 or 2	More
	Profession	Student	Active
	Domain of Activity	Science/ IT	Humanities/ Commerce	Others
	Daily Time Spent on PC	<1hr	1-3hr	3hr+
	Preferred for Net Access	PC	Smartphone
	Smartphone Quality Range	Low/Med End	High-End

http://www.metroscope.org

http://project.inria.fr/bottlenet/

http://www.statista.com/statistics/271644


Imen Achour
email: imen.achour@supcom.tn

Tarek Bejaoui
email: tarek.bejaoui@supcom.tn

Anthony Busson
email: anthony.busson@inria.fr

Sami Tabbane
email: sami.tabbane@supcom.rnu.tn

Delay-Based Strategy for Safety Message Dissemination in Vehicular Ad Hoc Networks: Slotted or Continuous?

Keywords: Vehicular Ad hoc Networks, Broadcast storm, Slotted delay-based technique, Continuous delay-based technique, Data Dissemination, Vehicles to Vehicle Communication

The diversity of applications' types in Vehicular Ad hoc NETworks (VANETs) has spawned a large variety of messages that need to be efficiently disseminated between connected vehicles. The most critical messages are those dedicated for safety applications such as road hazardous warning, signal violation warning, etc. The dissemination of this sort of messages is considered as a challenging task in mobile networks where the topology changes dynamically. Indeed, transmitted messages should achieve a high data reachability within a limited transmission delay and an acceptable overhead in a Vehicle to Vehicle (V2V) communication mode. In this work, we focus on a special type of data dissemination protocols based on the delay strategy. The purpose of this paper is to compare two basic distinguished techniques, namely the slotted technique and the continuous technique, and study in depth their impact on the data dissemination performance. A proper selection of the convenient technique according to the application's requirements is consequently deduced. For a faithful and rigorous study, simulations are performed by means of ns-3 simulator under a realistic VANET environment in terms of map layout, mobility pattern and radio model. Simulation results show that contrary to the theoretical reflection, slotted technique is approved as the most appropriate one for safety message dissemination. This technique achieves the same packet data ratio and redundancy ratio, compared to the continuous one, while reducing the data transmission delay.

I. INTRODUCTION

Vehicular Ad-hoc Networks (VANETs) are emerging as new prominent technologies that have a great impact on the new concept known as Internet of Vehicles (IoV) and improve the efficiency and the safety of intelligent transportation systems (ITSs). Composed of mobile vehicles connected via wireless links, VANETs may support a wide variety of applications ranging from safety and traffic management to generalized infotainment and entertainment applications [START_REF] Tcits Etsi | Intelligent transport systems (its); vehicular communications; basic set of applications; definitions[END_REF].

In order to ensure all these applications a wide variety of messages need to be efficiently disseminated between vehicles. Considering the wireless environment of VANET, where nodes are in a high mobility and the topology changes dynamically, these messages are typically disseminated through a broadcast technique. However, this technique suffers from the so called "Broadcast Storm" problem [START_REF] Tseng | The broadcast storm problem in a mobile ad hoc network[END_REF] in a dense network. The medium occupancy is increased due to an excessive amount of redundant messages which results in serious contention and collisions.

In this context, several dissemination protocols have been proposed to overcome this problem. Their main purpose is to reduce the number of excessive transmissions by reducing the number of forwarding nodes. These protocols may be classified into different categories and according to different criteria. Based on the forwarders selection metric, we mainly distinguish the delay-based protocols, probability-based protocols, and deterministic protocols.

In the current paper, we focus on the well known category of protocols based on the time delay strategy. Two main techniques are distinguished within this category, denoted slotted technique and continuous technique. To the best of our knowledge, no prior work has evaluated and compared these two techniques within the vehicular environment. Therefore, we aim in this work to thoroughly investigate their design, compare their performance efficiency, and conclude their convenience to the data dissemination in VANET. In particular, we attempt to study the impact of each technique on the performance of a "Redundancy-based Protocol (RBP)" [START_REF] Imen | A redundancy based protocol for safety message dissemination in vehicular ad hoc networks[END_REF], that combines a delay-based strategy with a probability-based strategy, and then deduce the most appropriate technique. To this end, three versions of the RBP protocol are proposed. In each version we alter the delay strategy by the studied technique and combine it with the probability-based strategy. The originality of such protocol relies on the design of the probability of broadcast. Indeed, RBP implicitly takes into account the surrounding vehicles density, in a beaconless manner where no message exchange among neighbors is needed. Thanks to a particular defined metric, called "Redundancy Ratio", each vehicle is able to locally determine its possibility of broadcast with regard to the network state. However, this latter strategy remains inefficient if no transmission scheduling is planned. Therefore, an accurate delay-based technique selection should be performed.

The remainder of this paper is organized as follows. In Section II, we report previous works from each delay-based technique. Section III is dedicated to thoroughly describe the principle of each technique and theoretically compare their transmission delay. In section IV, we present the simulation environment and we discuss the performance evaluation. At the end, concluding remarks and future works are presented in Section V.

II. RELATED WORKS

Various solutions have been proposed in the literature to overcome the Broadcast Storm problem. Among these solutions we mainly point out the protocols' category which is based on the time delay strategy. The basic idea behind this strategy is to reduce the number of relaying nodes by scheduling their upcoming transmissions. Therefore, as opposed to the blind flooding strategy, each receiver must wait a period of time before reforwarding. Different waiting times are assigned to each node. This timer is canceled by a vehicle upon the reception of the same message. As a result, only few vehicles perform their transmissions after the timer expiration. The main concern of such category lies in how to define the appropriate waiting time, i.e., according to which criteria and based on which technique. Through some presented reviews [START_REF] Panichpapiboon | A review of information dissemination protocols for vehicular ad hoc networks[END_REF][5], we may distinguish two time assignment techniques, namely the slotted technique and the continuous technique.

Most of researchers build their broadcast protocol on slotted delay based technique [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF]- [11]. In [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF], the authors propose the basic slotted technique, denoted Slotted 1-persistence protocol (S1PD). According to this technique the sender transmission range R is divided into N st segments. All vehicles belonging to the same segment are assigned to the same waiting time. The criteria considered in the defined timer, presented in Eq. 1, is the distance D ij between the transmitter i and the receiver j. The longer the distance, the shorter the waiting period. Thus, distant vehicles have more chance to relay message further in the network than near ones. Notice that the waiting time within a segment is a multiple of δ, which is a period of time larger than one hop delay including medium access delay and propagation delay.

W t = N st * (1 - min(D ij , R) R ) * δ (1)
Based on this protocol, authors in [START_REF] Schwartz | A directional data dissemination protocol for vehicular environments[END_REF] propose a sophisticated slotted waiting timer leading to an "Optimized S1PD" (OS1PD) protocol. Adding to the distance separating the transmitter and the receiver, the timer design takes into account the receiver moving direction toward the message dissemination direction. Therefore, vehicles moving in the same direction as that of the message dissemination have more priority to reforward their messages, unlike vehicles moving in the opposite direction. Thus, they are assigned to lower segment number, i.e., shorter timer. Moreover, they have tackled the synchronization problem between vehicles within the same segment by adding a micro delay µ to the waiting time W t , which is defined as follows:

W t = N st * (1 -P Dij ) * δ + µ if V dir = M dir N st * (2 -P Dij ) * δ + µ if V dir = M dir (2)
where P Dij is the ratio between D ij and R, as defined in Eq. 3.

V dir and M dir represent the vehicle direction and the high direction priority of the message dissemination, respectively.

P Dij = min(D ij , R) R (3)
In [START_REF] Ramon S Schwartz | Exploiting beacons for scalable broadcast data dissemination in vanets[END_REF], the authors enhanced the aforementioned timer design and proposed a new broadcast scheme called "Distributed Optimized Time" (DOT) slot. The contribution of this work, is that it takes into account the surrounding vehicles' density to determine the number of vehicles assigned to a single segment. Thus, the number of segments is no longer a predefined parameter but a function of the vehicles' density in vicinity. More the vehicles' density is high more the segments' number, within the transmission range, is high. Simulation results, have confirmed that DOT outperforms S1PD and OS1PD under different networks' density. However, in order to ensure this feature, a periodic safety beacon exchange between 1-hop neighbors is required. This obviously leads to a messaging overhead and probably collisions problems in dense network. Still on the basis of the delay slotted technique, authors in [START_REF] Imen | A redundancy based protocol for safety message dissemination in vehicular ad hoc networks[END_REF], [START_REF] Chaqfeh | Beacon-free scalable multi-hop data dissemination in vehicular ad hoc networks[END_REF] and [11] succeed to propose efficient data dissemination protocols, that takes into account the vehicles' density parameter by applying beacon-free design.

From another side, only few works have adopted the continuous strategy. As opposed to the slotted strategy, the waiting time is continuously assigned to each receiver. In [START_REF] Mirani | Improving delaybased data dissemination protocol in vanets with network coding[END_REF], the authors propose a delay-based data dissemination protocol that applies the basic design of the continuous technique. In such technique, the waiting time W t for each node is linearly inversely proportional to the distance D ij separating the sending node i and the receiver j. This waiting time is represented by the following equation:

W t = -a * D ij + c (4)
where a and c are constant parameters.

In [START_REF] Bachir | A multicast protocol in ad hoc networks inter-vehicle geocast[END_REF], the authors propose a continuous delay-based technique, called "Inter-Vehicle Geocast" (IVG) where a non linear waiting time is defined, as presented in Eq.5:

W t = T max * R β -D β ij R β (5)
T max denotes the maximum delay that a node should wait. β is a critical parameter that has a great impact on the waiting time curve and then on the timer values' distribution, i.e., W t more or less close. In attempt to generate a uniform waiting time between [0, T max ], authors suggest to settle β = 2.

On the basis of this work, authors in [START_REF] Ibrahim | p-ivg: Probabilistic inter-vehicle geocast for dense vehicular networks[END_REF] introduce a probabilistic rebroadcast scheme, called "probabilistic Inter-Vehicle Geocast" (p-IVG) that depends on the surrounding vehicles' density. In this work, authors are convinced that the continuous technique presents better performance than the slotted one. They argue this choice by the fact that, the node transmission in the slotted technique is restricted to be initiated at certain defined times (time-slot) which leads to channel contention. Whereas, by applying continuous strategy nodes are able to perform their transmissions in different times. Even this fact is true, many researchers are entirely convinced that the slotted delay technique is an efficient way to achieve high data broadcast performance. Overall, we find that if the efficiency of each scheme is proven, none can conclude which technique is in reality better than the other. For this reason, we definitely believe that a comparative study between the slotted and the continuous techniques should be conducted in order to reveal the strength and the weakness of each one. As a result, we become able to rigorously choose the appropriate technique for safety message dissemination.

III. DELAY BASED-PROTOCOL TECHNIQUES : PRINCIPLES AND CHARACTERISTICS

In this section, we aim to describe in detail the principle of each technique and depict their distinctive features. In order to make it simple we propose the following example, illustrated in Fig. 1. Let's consider S a source node that has detected a dangerous condition and thus started sending a warning message. We assume that the transmission range is configured to reach 300 m. Upon the reception of the warning message, each node holds the message for a period of time, called Waiting Time W t, before rebroadcasting it. The calculation of such timer depends on the deployed technique.

A. Slotted technique

According to the slotted strategy, the transmission range of the sender is divided into a fixed number of segments. In our example, presented in Fig. 1.a, we assume that the number of segments is 3, i.e., one segment per 100 m. All vehicles within the same segment are assigned to the same waiting time which is multiple of δ. Generally, the distance separating the transmitter and the receiver position is the typical parameter taken into account for the timer computation. More the distance is higher, more the waiting time is shorter. Therefore, vehicle (e) and (f) immediately send the message, whereas vehicles (b), (c) and (d) wait for 1δ and (a) for 2δ, knowing that the δ value is more than twice 1-hop delay. Thereby, nodes belonging to different segments have enough time to receive the message sent from the last segment before their waiting time expires. Once vehicles (a), (b), (c) and (d) receive the same message, they cancel their transmissions. In this way, the number of transmitters is efficiently reduced. Notice that, in this example the transmissions of nodes (e) and (f) do not collide due to the backoff mechanism. Nevertheless, if we consider a dense network, the number of vehicles within the same segment is then increased which results in high collisions between nodes that attempt to simultaneously send their messages. Based on the delay slotted principle description we can deduce the following characteristics:

• two vehicles belonging to different segments have enough time to receive message from each other even when they are close (e.g., nodes (d) and (e)),

• the slotted technique guarantees a certain amount of message redundancy to overcome the lost messages due to the VANET environment (e.g., nodes (e) and (f)),

• given a dense network, high collisions are expected between vehicles within the same segment.

B. Continuous technique

Based on such technique, the waiting time is continuously assigned to each receiving vehicle according to its distance from the sending vehicle. Generally, the farthest node is assigned to the shortest timer to enhance the data propagation farther in the message direction. By this way, each vehicle is assigned to a different waiting time. Based on the same example, illustrated in Fig. 1.b, we notice that node (f) is theoretically selected as a relaying node, which may significantly reduce the number of forwarders, since it is assigned to the shortest waiting time. However, in reality, this period of time seems insufficient for the message to reach the application layer of neighboring nodes before their timer expiration. This means that for a protocol implemented at the application layer, the difference of waiting times between two close vehicles must be sufficiently great to allow the message reaching the application layer, which is always in progress, before being transmitted to lower layers and cancel its transmission. As a result, both of nodes (e) and (f) are forwarding nodes. At first glance, the continuous technique seems to be the best solution to efficiently reduce the number of forwarders; each vehicles has a different timer from the others. Therefore, it is considered as the appropriate technique to resolve collisions' problems between neighbors vehicles and mitigate the broadcast storm. Nevertheless, a deep investigation in the transmission phases shows that a minimum Time delay T min , discussed below, should be respected between two adjacent nodes to effectively overcome the problem of collisions in dense network. This additional delay will induce an increase of the end-to-end delay. Based on this description we can conclude the following:

• the number of forwarders is significantly reduced,

• the forwarding transmission is not restricted to a certain period of times,

• introducing enough waiting delay may induce to an extra end-to-end delay.

C. Delay assignment investigation

The purpose of this section is to further explain the continuous technique weakness in terms of delay transmission. Thus, for a proper investigation, we illustrate in Fig. 2 the schedule of the different times delay that could be encountered in a typical wireless transmission, performed between two nodes n1 and n2 using CSMA/CA protocol. Based on this analysis, we become able to precisely determine the period of time that where D T is the transmission delay for a packet size, set to 500 bytes at 6 Mbit/s (D T = 666 µs). " " is the propagation delay upon 100 m ( = 0.33 µs). D AppP hy and D P hyApp are the times delay for the packet reception between the physical layer (wireless card) and the application layer. We assume that they are negligible, as well as the θ which represents the time delay while the medium is busy. As we are considering safety applications, the considered packets have the highest priority and should then wait for an "Arbitration inter-frame spacing" AIF S = 2 • t s + SIF S where the time slot t s = 13 µs and the Short Interframe Space SIF S = 32 µs according to the IEEE 802.11p standard [START_REF][END_REF]. Thereafter, the transmission shall wait for a contention period C p , randomly selected according to the backoff mechanism within the range [0, CW], where CW is the contention window size (CW = 15 in case of broadcast technique). Therefore, for a proper reception of the message from n 1 before the re-forwarding process, the node n 2 shall wait for a total delay W t 2 = W t 1 + T min . By taking into account T min in Eq. 4, we can notice the impact of such delay on the curve slope. For example, for two close vehicles located 10 m of distance from each other, T min is estimated to 860 µs in the worst case where C p = 15. Hence, a steep slope is induced for a transmission range of 500 m. This leads to increase the end-to-end transmission delay, up to 28 ms over a distance of 500 m, as compared to the slotted technique.

IV. PERFORMANCE EVALUATION

Based on the principle design of each delay-based technique, we are conducted to theoretically compare the performance of the slotted technique with the continuous technique, depict significant features and therefore be aware of the best technique. However, in order to confirm this investigation, simulation experiments are required. We propose, in this section, to thoroughly evaluate and compare the performance of both slotted and continuous techniques under realistic vehicular environment. In particular, we propose to evaluate their impact on the performance of a recent dissemination protocol, called "Redundancy Based Protocol" (RBP). The originality of this protocol is that it enhances the delay scheme performance by applying an efficient probability strategy. Based on redundancy ratio (r) parameter, which is integrated in the broadcast probability (P ) defined in Eq. 7, each vehicle is able to determine its ability of broadcast, after the timer expiration, in relation with the surrounding vehicles' density.

P = 2 r * P prev = 2 r current * 2 r prev ( 7
)
Three RBP versions implemented in this work are:

• RBP-S1PD: the slotted version of the protocol that combines the RBP with the typical slotted protocol (S1PD) proposed in [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF].

• RBP-LCD: the linear continuous version of the protocol that combines the RBP with a Linear Continuous Dissemination protocol (LCD) proposed in [START_REF] Mirani | Improving delaybased data dissemination protocol in vanets with network coding[END_REF].

• RBP-NLCD: the non-linear continuous version of the protocol that combines the RBP with a Non-Linear Continuous Dissemination protocol (NLCD) [START_REF] Bachir | A multicast protocol in ad hoc networks inter-vehicle geocast[END_REF].

A. Simulation Platform and Parameters Simulation experiments were performed while assuming the real city map of Afton Oaks in Houston, United States, to carry out a realistic VANET scenario. The topology related to the map shown in Fig. 3, is generated by MOVE using TIGER (Topologically Integrated GEographic Encoding and Referencing) database [START_REF] Census | Census Bureau-Topologically Integrated Geographic Encoding and Referencing (TIGER) system[END_REF]. The simulated road, in the considered city map, is composed of a set of segments. Each segment is a multi-lane road where the overtaking behavior between vehicles is allowed. The number of lanes and maximum velocity may vary (from 2 up to 6 lanes and from 15 m/s up to 90 m/s, respectively) from one segment to another. Given the traffic lights absence, each segment of the simulated road is characterized by a priority percentage.

The performance evaluation of the selected delay-based technique is carried out through extensive simulations, using NS3.19 [START_REF]Network Simulator project[END_REF] simulator, where a full implementation of VANET protocol stack is integrated. For a realistic mobility pattern within the considered map, we generated the traffic using the micro-traffic simulator, called "SUMO -Simulation of Urban Mobility" [START_REF] Sumo | Sumo -simulation of urban mobility[END_REF]. We set the bit rate to 6 M bit/s in the MAC layer. The transmission power is tuned to roughly achieve 500 meters of transmission range while assuming m-Nakagami propagation model. For the delay based techniques, we set δ to 4 ms. We fix the total number of slots N st to 5 (one slot per 100 m). We set the constant a to 0.004 ms and the constant b to 20 ms. We fix T max to 16 ms and β to 2. It should be noticed that, for a proper comparison, all these waiting time parameters are adjusted in a way to guarantee the same data reachability for all the studied versions. For the application scenario, we configure the 5 first vehicles to periodically generate a new message with 500 bytes of size at a frequency of 1Hz. In order to evaluate the RBP versions scalability, we vary the number of the simulated vehicles until 90 vehicles with a maximum speed defined by the selected road. For the protocols evaluation we consider the following metrics:

• Packet Delivery Ratio (PDR): the average number of original packets successfully received by a vehicle, compared to the total number of generated messages.

• Redundancy Ratio (R): the average amount of received messages per one original message.

• Forwarding Ratio (FR): the proportion of vehicles in the network that are involved in the rebroadcast of a new packet.

• End-to-End Delay (E2EDelay): the average difference between the packet generation time by the source vehicle and the reception time of this packet by the last reached vehicle.

B. Simulation Analysis

As we can notice from Fig. 4(a), the RBP-S1PD and RBP-LCD protocols outperform RBP-NLCD in terms of redundancy ratio. In order to achieve the same amount of packet reachability, Fig. 4(c), as it is achieved by RBP-S1PD and RBP-LCD, the non-linear continuous delay-based technique exhibits more redundant packets and therefore more network resources consumption. This fact, may be explained through Fig. 4(b), where more vehicles are involved in the re-forwarding process of RBP-NLCD protocol, compared to RBP-S1PD and RBP-LCD protocols, especially for low dense networks. On the whole, we can say that the NLCD technique is less reliable than the slotted and the linear continuous techniques. Therefore it is not the best solution to reduce unnecessary transmissions and to overcome the broadcast storm. Moreover, it is clearly noticed, through Fig. 4(d) that the RBP-NLCD protocol induces more end-to-end delay, as compared to the slotted and the linear continuous versions. This result remains the most important one, since it reflects the efficiency of a certain protocol toward safety message dissemination in VANET.

The focus on comparing the slotted and the linear continuous RBP versions leads us to deduce that the slotted technique outperforms the continuous one, since it is able to achieve the same packet delivery ratio in a short transmission delay. Based on Fig. 4(d), the continuous technique presents more end-toend delay for all amounts of vehicles that operate in the system, compared to slotted one. This delay may reach up to 15 ms, which could be critical mostly for message dissemination in dangerous situations, such as hard braking, road accident, hazardous road condition. This result highlights the fact that in continuous design, forwarding-nodes need to wait enough time in order to give the chance to the nearest vehicles to cancel their transmissions, once they receive the same message from their neighbors. Elsewhere, all adjacent vehicles will send the same message at close time which may result in increasing resources' consumption and maybe collisions at a serious redundancy ratio. Overall, the slotted scheme is suitable either for safety applications or for further kinds of applications by saving the network capacity consumption.

With regard to the simulation environment, it should be noticed that the scenario characteristics has a great impact on the protocol performance evaluation. In prior work presented in [START_REF] Imen | A redundancy based protocol for safety message dissemination in vehicular ad hoc networks[END_REF], RBP protocol has achieved an outstanding performance for safety message dissemination in a simple highway scenario. In short, it has shown i) a high efficiency in terms of data reachability, transmission delay and network resources consumption and ii) a high robustness toward the network scalability. However, under a realistic map as it is presented in this work, RBP reveals its design weakness against the variable speed and direction of the simulated vehicles and therefore against the intermittent connectivity. The reason for which we can explain the data reachability performance of RBP, that does not exceed 70% for all protocol versions, as illustrated in Fig. 4(c). Thus, we can confirm that more the simulation environment is realistic more the data dissemination performance analysis are exhaustive and robust.

Theoretically speaking, we can affirm that the continuous version is more efficient than the slotted technique to alleviate the broadcast storm problem effect. In fact, the number of transmissions is effectively reduced and fewer nodes are chosen as relaying nodes. Whereas in the slotted technique, all vehicles belonging to the furthest segment are chosen as forwarders. Although this prominent property, and as opposed to what was expected, we notice that the continuous technique suffers from a high end-to-end delay in order to achieve the same packet delivery ratio reached by the slotted strategy, as it is depicted in Fig. 4(d) and Fig. 4(c). This observed delay amounts to a steep slope, required in the waiting time calculation. If the waiting times of nearby nodes are not enough spaced, serious collisions' problems may occur, especially in dense network. In fact, as nearby vehicles have not enough time to receive messages from each other to cancel their redundant transmissions, they consequently decide to retransmit their messages almost at the same time. From the other side, under the same condition, the slotted strategy is able to mitigate this problem by assigning enough time space between two close vehicles belonging to different segments. Whereas, vehicles belonging to the same segment are managed through a probability-based strategy, offered by RBP protocol.

Moreover, this delay spanned by the continuous technique, may be a way to overcome the network reliability under a realistic radio model, where the messages are likely to be lost. Therefore, having enough time-space between forwarding nodes leads to decrease collisions and then ensure a certain amount of redundancy which would be able to fill lost messages. However, in the slotted technique, this amount of redundancy is guaranteed through one segment without the need of extra waiting delay.

V. CONCLUDING REMARKS

In this work, we propose a comparative study between two delay-based techniques (slotted and continuous techniques). Our focus is to reveal the strength and the weakness of each technique and then to conclude which technique is the most appropriate for safety message dissemination. In particular, our investigation is performed upon an original dissemination protocol denoted "Redundancy based protocol (RBP)". The particularity of such protocol, is that it improves the delaybased technique by combining it with a probabilistic design in order to further overcome the collisions problems. Simulation results of RBP slotted version outperforms the RBP continuous version under realistic VANET environment. It was shown that compared to the slotted strategy, the continuous strategy reduces the number of forwarders and ensures an acceptable amount of data reachability. But, these benefits are achieved at the cost of the end-to-end dissemination delay throughout the network. Then, the continuous delay-based technique is not convenient for safety applications, where the transmission delay is a crucial metric for the warning messages dissemination.

As a future work, and on the basis of the slotted version, we will try to enhance the RBP performance in a sparse network where the connectivity between vehicles is not constantly guaranteed.

Fig. 1 .

 1 Fig. 1. Example of delay-based techniques

Fig. 2 .

 2 Fig. 2. Typical 1-hop time delay

Fig. 3 .

 3 Fig. 3. "Afton Oaks" Area.

Fig. 4 .

 4 Fig. 4. Simulation results under various vehicles' number.

ACKNOWLEDGMENT

This work is a part of the MOBIDOC project achieved under the PASRI program, funded by the European Union and administrated by the ANPR.


come

A Generating Polynomial For the Octahedral Extension in the 4-Torsion Point Field of an Elliptic Curve

A GENERATING POLYNOMIAL FOR THE OCTAHEDRAL EXTENSION IN THE 4-TORSION POINT FIELD OF AN ELLIPTIC CURVE

KEVIN MUGO

Abstract. Let E be an elliptic curve with invariant j 0 ∈ Q, and denote K = Q(j 0 ) as a number field. Assume that the canonical composition

G K(i) ρ E,4 ----→ SL 2 (Z/4Z) → P SL 2 (Z/4Z) ≃ ----→ S 4
as a projective representation is surjective. We show that j 0 = 0, 1728, ∞, and that the splitting field M of the quartic polynomial q(r) = r 4 + 32 j 0 r + 4 j 0 is an S 4 -extension of K.

Congruence Subgroups and Modular Curves

Recall that we have an left action

• : SL 2 (Z) × H * → H * defined by a b c d • τ = a τ + b c τ + d
and the extended upper-half plane H * = x + i y y > 0 ∪ P 1 (Q) is isomorphic to the unit disk via the map H * → P 1 (C) which sends τ to q = e 2πiτ . For any positive integer N, we consider the congruence subgroups

Γ 0 (N) = a b c d ∈ SL 2 (Z) c ≡ 0 mod N Γ 1 (N) = a b c d ∈ SL 2 (Z) a ≡ d ≡ 1, c ≡ 0 mod N Γ(N) = a b c d ∈ SL 2 (Z) a ≡ d ≡ 1, b ≡ c ≡ 0 mod N
Using the Dedekind eta function η(τ ) = q 1/24 ∞ n=1 1 -q n , we define the following maps

1 H * Γ(4) z / / P 1 (C) 2 z(τ ) = 2 η(τ ) η(4τ ) 2 η(2τ ) 3 2 H * Γ(2) ∩ Γ 1 (4) k / /
x x r r r r r r r r r r

k(τ ) = 4 η(τ ) η(4τ ) 2 η(2τ ) 3 4 H * Γ 1 (4)
t(τ ) = 256 η(4τ ) η(τ ) 8 H * Γ(2) λ / / r r r
x x r r r r r r r r r r

P 1 (C) 2 { { v v v v v v v v v v v v λ(τ ) = 16 η(τ /2) η(2τ ) 2 η(τ ) 3 8 H * Γ 0 (2) w / / P 1 (C) 3 w(τ ) = -64 η(2τ ) η(τ ) 24 H * Γ(1) J / / P 1 (C) J(τ ) = 1 + 240 ∞ n=1 σ 3 (n) q n 3 1728 q ∞ n=1 1 -q n 24
Here k is the elliptic modulus, λ is the modular lambda function, and J is Klein's absolute invariant.

Lemma 1. With the maps as defined above, we have the identities

k(τ ) = z(τ ) 2 t(τ ) = 16 k(τ ) 2 1 -k(τ ) 2 = 16 z(τ ) 4 1 -z(τ ) 4 λ(τ ) = 4 k(τ ) k(τ ) + 1 2 = 4 z(τ ) 2 z(τ ) 2 + 1 2 w(τ ) = - t(τ ) t(τ ) + 16 64 = λ(τ ) 2 4 λ(τ ) -1 = - 4 k(τ ) 2 k(τ ) 2 -1 2 = - 4 z(τ ) 4 z(τ ) 4 -1 2 J(τ ) = 4 w(τ ) -1 3 27 w(τ ) = t(τ ) 2 + 16 t(τ ) + 16 3 1728 t(τ ) t(τ ) + 16 = 4 λ(τ ) 2 -λ(τ ) + 1 3 27 λ(τ ) 2 λ(τ ) -1 2 = k(τ ) 4 + 14 k(τ ) 2 + 1 3 108 k(τ ) 2 k(τ ) 2 -1 4 = z(τ ) 8 + 14 z(τ ) 4 + 1 3 108 z(τ ) 4 z(τ ) 4 -1 4
In particular, these maps are isomorphisms of compact Riemann surfaces.

We omit the proof since it is a straightforward computation by looking at the q-series expansions.

Automorphisms of the Riemann Sphere

Using the formulae in Lemma 1, we see that the map

H * Γ(4) ։ H * Γ(1)
which sends z → J = (z 8 + 14 z 4 + 1) 3 108 z 4 (z 4 -1) 4

is a covering map of Riemmann surfaces, so we can focus on the group of Deck transformations. This automorphism group is

Aut H * Γ(4) ։ H * Γ(1) ≃ Γ(1) Γ(4) ≃ P SL 2 (Z/4Z) ≃ S 4 .
The automorphisms of the Riemann sphere P 1 (C) are just the Möbius transformations, so the group

S 4 = σ 0 , σ 1 , σ ∞ σ 0 2 = σ 1 3 = σ ∞ 4 = σ 0 σ 1 σ ∞ = 1
as expressed in terms of the rational functions

σ 0 (z) = 1 -z 1 + z , σ 1 (z) = i -z i + z , and σ ∞ (z) = i z leaves J invariant.
Along these lines, that is, using the formulae in Lemma 1, we find the following subgroups and the corresponding rational functions which are invariant under them:

Q(i, r) r = ( * ) V 4 2 Q(i, λ) λ = 4 z 2 z 2 + 1 2 D 4 3 o o o o o o o o o o o o Q(i, w) o o o o o o o o w = - 4 z 4 z 4 -1 2 S 4 Q(i, J) J = z 8 + 14 z 4 + 1 3 108 z 4 (z 4 -1) 4
Here we have define the following subgroups of S 4 as triangle groups:

• D 4 = a, b, c a 2 = b 2 = c 4 = a b c = 1 is the dihedral group as expressed in terms of the Möbius transformations a = σ 0 σ ∞ 2 σ 0 , b = σ ∞ σ 0 σ ∞ 2 σ 0 , and c = σ ∞ ; • V 4 = a, b, c a 2 = b 2 = c 2 = a b c = 1 is the Klein four group as expressed in terms of the Möbius transformations a = σ ∞ 2 , b = σ 0 σ ∞ 2 σ 0 , and c = σ ∞ 2 σ 0 σ ∞ 2 σ 0 ; • Z 4 = a, b, c a = b 4 = c 4 = a b c = 1 is the cyclic group as expressed in terms of the Möbius transformations a = 1, b = σ ∞ , and c = σ ∞ 3 . • Z 2 = a, b, c a = b 2 = c 2 = a b c = 1 is
= σ ∞ σ 1 , b = σ 0 σ ∞ 2 σ 1 , c = σ ∞ 3 σ 0 .
The function r mentioned above is given by the rational function

r(z) = z (z 4 -1) (1 + i) z 2 -(1 + i) z -i z 2 -(1 -i) z + i z 2 + (1 + i) z -i .

Splitting Fields and S 4 -Extensions

We use the hauptmoduli on the modular curves previously discussed to study splitting fields of polynomials.

Theorem 2. Let be K = Q J(z) be that transcendental extension of Q in terms of the rational function

J(z) = z 8 + 14 z 4 + 1 3 108 z 4 z 4 -1 4 ,
and choose an elliptic curve E over K with invariant j(E) = 1728 J(z). The following are equal:

(1) The splitting field K(i) z of 16 z 8 + 14

z 4 + 1 3 -j(E) z 4 (z 4 -1) 4 .
(2) The splitting field K(i) r 1 , r 2 , r 3 , r 4 of r 4 + 32 r/j(E) + 4/j(E).

(3) The splitting field K(i) t 1 , t 2 , t 3 , t 4 , t 5 , t 6 of t 2 + 16 t + 16 3 -j(E) t t + 16 .

(4) The splitting field K E[4] x = K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) of the 4-division polynomial ψ 4 (x).

Proof. Let E be any elliptic curve over K with invariant j(E) = 1728 J(z). There exists

D ∈ K × such that E has a Weierstrass model y 2 + a 1 x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 in terms of the F -rational quantities b 2 = a 2 1 + 4 a 2 b 4 = a 1 a 3 + 2 a 4 b 6 = a 2 3 + 4 a 6 b 8 = a 2 a 2 3 -a 1 a 3 a 4 -a 2 4 + a 2 1 a 6 + 4 a 2 a 6
and

a 1 = 0 a 2 = 0 a 3 = 0 a 4 = 3 J(z) D 2 / 1 -J(z) a 6 = 2 J(z) D 3 / 1 -J(z)
Recall that J(z) is invariant under the group

S 4 = σ 0 , σ 1 , σ ∞ σ 0 2 = σ 1 3 = σ ∞ 4 = σ 0 σ 1 σ ∞ = 1 .
For what follows, define the Q(i)-rational functions

x 1 = x(z)
x 2 = x σ 0 (z)

x 3 = x σ 1 (z)
x 4 = x σ 1 σ 0 (z)

x 5 = x σ 0 σ ∞ σ 1 (z) x 6 = x σ 0 σ ∞ σ 1 σ 0 (z) t 1 = t(z) t 2 = t σ 0 (z) t 3 = t σ 1 (z) t 4 = t σ 1 σ 0 (z) t 5 = t σ 0 σ ∞ σ 1 (z) t 6 = t σ 0 σ ∞ σ 1 σ 0 (z) r 1 = r(z) r 2 = r σ ∞ (z) r 3 = r σ ∞ 2 (z) r 4 = r σ ∞ 3 (z) in terms of the Q(i)-rational functions σ 0 (z) = 1 -z 1 + z x(z) = -D (z 4 -5) (z 8 + 14 z 4 + 1) (z 4 + 1) (z 8 -34 z 4 + 1) σ 1 (z) = i -z i + z t(z) = 16 z 4 1 -z 4 σ ∞ (z) = i z r(z) = z (z 4 -1) (1 + i) z 2 -(1 + i) z -i z 2 -(1 -i) z + i z 2 + (1 + i) z -i
The splitting field of the polynomial 16 z 8 + 14 z 4 + 1 3 -j(E) z 4 (z 4 -1) 4 is the function field K(i) z because we have the factorization

16 Z 8 + 14 Z 4 + 1 3 -j(E) Z 4 (Z 4 -1) 4 = 16 σ∈S 4 Z -σ(z) .
The splitting field K(i) r 1 , r 2 , r 3 , r 4 of r 4 + 32 r/j(E) + 4/j(E) is contained in K(i) z because r ν ∈ K(i) z and we have the factorization

r 4 + 32 j(E) r + 4 j(E) = 4 ν=1 r -r ν .
The splitting field K(i) t 1 , t 2 , t 3 , t 4 , t 5 , t 6 of t 2 + 16 t + 16 3 -j(E) t t + 16 is contained in K(i) r 1 , r 2 , r 3 , r 4 because we have the identity

t 1 = -16 4 ν=1 i ν r ν 2   4 ν=1 i ν r ν 2 + 4 ν=1 (-i) ν r ν 2 
 so that each t ν ∈ K(i) r 1 , r 2 , r 3 , r 4 , and we have the factorization

t 2 + 16 t + 16 3 -j(E) t t + 16 = 6 ν=1 t -t ν .
The splitting field K E[4] x = K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) of the 4-division polynomial

ψ 4 (x) = 2 x 6 + b 2 x 5 + 5 b 4 x 4 + 10 b 6 x 3 + 10 b 8 x 2 + (b 2 b 8 -b 4 b 6 ) x + (b 4 b 8 -b 2 6 ) is contained in K(i) t 1 , t 2 ,
t 3 , t 4 , t 5 , t 6 because we have the factorization

ψ 4 (x) = 2 6 ν=1 x -x ν where x ν = -D t ν + 20 t ν 2 + 16 t ν + 16 t ν + 8 t ν 2 + 16 t ν -8 . Finally, K(i) z is contained in K E[4] x because z = (x 6 -x 2 )/(x 1 -x 2 ).
Hence the splitting fields are indeed equal.

Modular Curves as Moduli Spaces

The moduli spaces X 0 (N), X 1 (N), and X(N) consist of pairs (E, C), (E, P ), and (E, P, Q) of elliptic curves E with a cyclic subgroup C of order N, a specified point P of order N, or full level N structure P, Q ≃ Z N × Z N , respectively. By "forgetting" the level structures, we have a commutative diagram

H * Γ(N) ∼ / / X(N) H * Γ 1 (N) ∼ / / X 1 (N) H * Γ 0 (N) ∼ / / X 0 (N)
We will make these maps explicit when N divides 4. To begin, we have the following result which was known to Felix Klein.

Theorem 3.

(1) The general linear group

GL 2 (Z/4 Z) = a b c d ∈ Mat 2×2 (Z/4 Z) a d -b c ∈ Z/4 Z × = γ 0 , γ 1 , γ ∞ γ 0 4 = γ 1 6 = γ ∞ 4 = γ 0 γ 1 γ ∞ = I
can be expressed in terms of the 2 × 2 matrices

γ 0 = 3 3 2 1 , γ 1 = 3 1 1 0 , and γ ∞ = 2 3 3 0 .
(2) The group homomorphism γ ν to the cosets σ ν = γ ν V 4 in terms of the normal subgroup

V 4 = ± 1 0 0 1 , ± 1 2 2 3 = γ 0 2 , γ 1 3 , γ ∞ 4 induces a short exact sequence 1 ---→ V 4 ---→ GL 2 (Z/4 Z) ---→ S 4 ---→ 1
in terms of the symmetric group

S 4 = σ 0 , σ 1 , σ ∞ σ 0 2 = σ 1 3 = σ ∞ 4 = σ 0 σ 1 σ ∞ = 1 .
(3) Denote the rational functions c 4 (z) = 9 z 8 + 14 z 4 + 1 c 6 (z) = 27 z 12 -33 z 8 -33 z 4 + 1

J(z) = z 8 + 14 z 4 + 1 3 108 z 4 (z 4 -1) 4 =⇒ J(z) = c 4 (z) 3 c 4 (z) 3 -c 6 (z) 2 ;
and let E z be the elliptic curve y 2 = x 3 -3 c 4 (z) x -2 c 6 (z) with invariant j(E z ) = 1728 J(z) as defined over the field

K = Q J(z) = Q c 4 (z), c 6 (z) . Then E z [4] = P z , Q z ≃ Z 4 × Z 4 is generated by the points P z = -3 (z 4 -5) : 54 (z 4 -1) : 1 Q z = -3 (z 4 + 6 z 3 + 6 z 2 + 6 z + 1) : 54 i z (z + 1) 2 (z 2 + 1) : 1 . (4) The map H * Γ(4) → P 1 (C) → X(4) which sends τ → z = z(τ ) → (E z , P z , Q z ) is an isomorphism. (5) Denoting M = K r 1 , r 2 , r 3 , r 4 as the splitting field of the quartic polynomial r 4 + 32 r/j(E z ) + 4/j(E z ), then M(i) = K E z [4] x = K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6
) is the splitting field of the 4-division polynomial ψ 4 (x).

This gives explicit information about the full level 4 structure of an elliptic curve. The complete list of "forgetful" maps can be found below.

z _ H * Γ(4) / / X(4) E z : y 2 = x 3 -3 c 4 (z) x -2 c 6 (z) P z = 3 (5 -z 4 ) : 54 (1 -z 4 ) : 1 Q z = 3 (5 z 4 -1) : 54 z 2 (z 4 -1) : k = z 2 ? E t : y 2 -t x y + t 2 y = x 3 -t x 2 P t = (0 : 0 : 1) λ = 4 k (k + 1) 2 ? H * Γ(2) / / X(2) E λ : y 2 = x (x -1) (x -λ) P λ = (0 : 0 : 1) Q λ = (1 : 0 : 1) w = - t (t + 16) 64 = λ 2 4 (λ -1) _ H * Γ 0 (2) / / X 0 (2) E w : y 2 = x 3 + 2 x 2 + 1 1 -w x
C w = (0 : 0 : 1), (0 : 1 : 0)

J = (4 w -1) 3 27 w H * Γ(1) / / X(1) E J : y 2 = x 3 + 3 J 1 -J x + 2 J 1 -J O J = (0 : 1 : 0)
Proof. The first two statements are straightforward to verify. As for the third and fourth statements, the following table explicitly lists the 16 elements in

E z [4] = P z , Q z .
It suffices to show the final statement. The idea will be to focus on the following subfields and their Galois groups:

K E z [4] I M(i) = K E z [4] x g g g g g g

±I

dd dd dd dd dd dd dd dd dd dd dd dd dd dd dd

M = K(r 1 , r 2 , r 3 , r 4 ) V 4 F (i) l l l l l l l l l l l l l l l ker SL 2 Z 4Z → SL 2 2 g g g g g g F = K E z [2] ker GL 2 Z 4Z → GL 2 Z 2Z K(i)
g g g g g g g g g g g g g SL 2 (Z/4Z) dd dd dd dd dd dd dd dd dd dd dd

K = Q(J) GL 2 (Z/4Z) Q Let M = K r 1 , r 2 ,
r 3 , r 4 be the splitting field of r 4 + 32 r/j(E z ) + 4/j(E z ) viewed as a polynomial over K(J). Theorem 2 asserts that

M(i) = K(i) r 1 , r 2 , r 3 , r 4 = K E z [4] x = K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6 )
where the x ν are the roots of the 4-division polynomial ψ 4 (x) of E z . In fact, to be quite explicit in the notation used during the proof above,

P = P x 1 = -3 (z 4 -5) σ 0 (P z ) = Q z x 2 = -3 (z 4 + 6 z 3 + 6 z 2 + 6 z + 1) σ 1 (P z ) = P z ⊕ Q z x 3 = -3 (z 4 + 6 i z 3 -6 z 2 -6 i z + 1) σ 1 σ 0 (P Z ) = P z ⊕ [3]Q z x 4 = -3 (z 4 -6 i z 3 -6 z 2 + 6 i z + 1) σ 0 σ ∞ σ 1 (P z ) = [2]P z ⊕ [3]Q z x 5 = -3 (z 4 -6 z 3 + 6 z 2 -6 z + 1) σ 0 σ ∞ σ 1 σ 0 (P z ) = P z ⊕ [2]Q z x 6 = 3 (5 z 4 -1)
Using the maps γ ν → σ ν one can determine the action of GL 2 (Z/4Z) on these coordinates. For example, is easy to verify that the rational function

x 2 -x 5 x 3 -x 4 (x 1 -x 2 ) 2 -(x 2 -x 6 ) 2 (x 1 -x 2 ) 2 + (x 2 -x 6 ) 2 = i
is invariant under SL 2 (Z/4 Z), so we may conclude that K(i) is that subfield of K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) which is invariant under the special linear group SL 2 (Z/4 Z).

The subgroup

V 4 ֒→ GL 2 (Z/4Z) ≃ Aut E z [4] acts on E z [4] = P z , Q z ≃ Z 4 × Z 4
, so we have a permutation representation V 4 → GL 6 (F ) coming from the induced action on the roots x ν of the 4-division polynomial ψ 4 (x). This representation sends

± 1 0 0 1 →       
1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

       and ± 1 2 2 3 →       
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0

      
.

It is easy to check that the roots -e 4 -e 5 -e 6 e 1 e 2 + e 2 e 3 + e 3 e 1 are invariant under the action of V 4 , so we may conclude that M = K r 1 , r 2 , r 3 , r 4 = K e 1 , e 2 , e 3 , e 4 , e 5 , e 6 is that subfield of K(x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) which is invariant under V 4 . In fact, since we have the factorization

e 1 = x 1 + x 6 2 = - c 6 (z) c 4 (z) r 1 r 3 + r 2 r 4 r 1 r 3 + r 2 r 4 + 24 r 1 r 2 r 3 r 4 e 2 = x 2 + x 5 2 = - c 6 (z) c 4 (z) r 1 r 2 + r 3 r 4 r 1 r 2 + r 3 r 4 + 24 r 1 r 2 r 3 r 4 e 3 = x 3 + x 4 2 = - c 6 (z) c 4 (z) r 1 r 2 + r 3 r 4 r 1 r 2 + r 3 r 4 + 24 r 1 r 2 r 3 r 4 e 4 = (x 1 -x 6 ) (x 2 -x 5 ) 48 = 3 4 c 4 (z) +r 1 -r 2 -r 3 + r 4 e 5 = (x 2 -x 5 ) (x 3 -x 4 ) 48 = 3 4 c 4 (z) -r 1 + r 2 -r 3 + r 4 e 6 = (x 3 -x 4 ) (x 1 -x 6 ) 48 = 3 4 c 4 (z) -r 1 -r 2 + r 3 +
ψ 2 (x) = 4 x 3 -3 c 4 (z) x -2 c 6 (z) = 4 (x -e 1 ) (x -e 2 ) (x -e 3 )
we have the F = K(e 1 , e 2 , e 3 ) = K E z [2] as the splitting field of the 2-division polynomial ψ 2 (x).

Main Result

We can now state and prove the main result.

Corollary 4. Let E be an elliptic curve with invariant j 0 ∈ Q, and denote K = Q(j 0 ) as a number field. Assume that the canonical composition

G K(i) ρ E,4 ---→ SL 2 (Z/4Z) → P SL 2 (Z/4Z) ≃ ---→ S 4
as a projective representation is surjective.

(1) j 0 = 0, 1728, ∞.

(2) The splitting field M of the quartic polynomial q(r) = r 4 + 32 j 0 r+ 4 j 0 is an S 4 -extension of K.

Proof. We show the first statement. If j 0 = 0, then E would have Weierstrass model y But the composition of representations is surjective, so that 24 = S 4 = Gal K(E[4] x )/K(i) ≤ Z 2 × D 2 = 8. If j 0 = ∞, then E would be a singular projective curve. In either of these three cases we find a contradiction, so we must have j 0 = 0, 1728, ∞.

2 = x 3 + D for some D ∈ K × . This model has 4-division polynomial ψ 4 (x) = 2 x 6 + 20 D x 3 -8 D 2 with splitting field K(E[4] x ) = K 3 √ D, √ -1, √ 3 and Galois group Gal K(E[4] x )/K ֒→ Z 2 × D 3 = {±1} × a,
We show the second statement. Let E be as above. There exists z 0 ∈ Q such that j 0 = 1728 J(z 0 ); then J(z 0 ) = 0, 1, ∞. Denote M as the splitting field of q(r) = r 4 + 32 j 0 r+ 4 j 0 as a polynomial over K, so that M(i) is the splitting field of the 4-division polynomial ψ 4 (x) over K(i). Since ρ E,4 is surjective, we see that Gal(M/K) ≃ Gal M(i)/K(i) ≃ P SL 2 (Z/4Z) ≃ S 4 .

Department of Mathematics, Purdue University, W. Lafayette, IN,

  the cyclic group as expressed in terms of the Möbius transformations a = 1 and b = c = σ ∞ 2 ; and • S 3 = a, b, c a 2 = b 2 = c 3 = a b c = 1 is the symmetric group as expressed in terms of the Möbius transformations a

  + e 5 + e 6 e 1 e 2 + e 2 e 3 + e 3 e 1 r 2 = +e 4 -e 5 + e 6 e 1 e 2 + e 2 e 3 + e 3 e 1 r 3 = +e 4 + e 5 -e 6 e 1 e 2 + e 2 e 3 + e 3 e 1 r 4 =

  b, c a 2 = b 3 = c 2 = a b c = But the composition of representations is surjective, so that 24= S 4 = Gal K(E[4] x )/K(i) ≤ Z 2 × D 3 = 12. If j 0 = 1728, then E would have Weierstrass model y 2 = x 3 + D x for some D ∈ K × . This model has 4-division polynomial ψ 4 (x) = 2 x 2 -D x 4 + 6 D x 2 + D 2 with splitting field K(E[4] x ) = K x )/K ֒→ Z 2 × D 2 = {±1} × a, b, c a 2 = b 2 = c 2 =a b c = 1 as generated by the Möbius transformations a(x) = -D x , b(x) = -x, and c(x) = + D x .

-3 (z 4 -6 i z 3 -6 z 2 + 6 i z + 1) -54 z (z + i) 2 (z 2 -1)