Sara Bouguelia
email: sara.bouguelia@univ-lyon1.fr

Hayet Brabra
email: hayet.brabra@univ-lyon1.fr

Boualem Benatallah
email: boualem@cse.unsw.edu.au

Marcos Baez
email: marcos.baez@univ-lyon1.fr

Shayan Zamanirad
email: shayanz@cse.unsw.edu.au

Context Knowledge-aware Recognition of Composite Intents in Task-oriented Human-Bot Conversations

Keywords: Task-oriented Conversational Bots, Complex Intent Recognition, Context knowledge, Slot value inference

Task-oriented dialogue systems employ third-party APIs to serve end-users via natural language interactions. While existing advances in Natural Language Processing (NLP) and Machine Learning (ML) techniques have produced promising and useful results to recognize user intents, the synthesis of API calls to support a broad range of potentially complex user intents is still largely a manual and costly process. In this paper, we propose a new approach to recognize and realize complex user intents. Our approach relies on a new rule-based technique that leverages both (i) natural language features extracted using existing NLP and ML techniques and (ii) contextual knowledge to capture the different classes of complex intents. We devise a context knowledge service to capture the requisite contextual knowledge.

Introduction

Task-oriented dialogue systems (or simply bots) use natural language conversations to enable interactions between humans and software-enabled services [START_REF] Brabra | Dialogue management in conversational systems: A review of approaches, challenges, and opportunities[END_REF]. In these, fulfilling a user request consists of: [START_REF] Andreas | Task-oriented dialogue as dataflow synthesis[END_REF] understanding the user utterance expressed in natural language (e.g., "What is the weather in Paris?"), [START_REF] Bouguelia | Reusable abstractions and patterns for recognising compositional conversational flows[END_REF] recognizing the user intent (e.g., GetWeather), (3) extracting relevant slotvalue pairs (e.g., (location, Paris)), (4) invoking the corresponding API (e.g., OpenWeatherMap to get weather condition), and (5) returning a natural language response to the user (e.g., "We have light rain in Paris").

Ideally, the bot should detect intents and infer slot values with the least possible interactions with the user (i.e., the bot asks the user for a missing value only when it cannot infer it from other sources). A key challenge to achieve this objective is devising robust intent recognition and slot inference despite the potentially ambiguous and complex utterances. An utterance may not always follow a simple conversation pattern, where the bot recognizes a basic intent and infers all required slot values from the utterance, as in the previous example.

Natural user conversations can be rich, potentially ambiguous, and express complex user intents [START_REF] Fast | Iris: A conversational agent for complex tasks[END_REF][START_REF] Zamanirad | Superimposition of natural language conversations over software enabled services[END_REF]. An intent is complex when its realization requires the bot to break it down into a list of atomic actions and infer potentially missing values from different sources, not directly from the utterance. Given the utterance "Can you book a table for 2 people at Mirazur restaurant for the next public holiday?", the bot should be able to infer the information such as number of people and restaurant from this utterance; however, it also needs to search when will the next holiday be. Failing to support such complex intents can lead to repetitive and less natural interactions affecting the user experience [START_REF] Jain | Evaluating and informing the design of chatbots[END_REF].

Existing NLP and ML techniques have produced useful results to recognize basic intents [START_REF] Wu | Gcdst: A graph-based and copy-augmented multi-domain dialogue state tracking[END_REF]. ML based techniques rely on the availability of massive amounts of annotated data. Using these techniques to recognize complex intents requires laborious, costly and hard to acquire training datasets. In addition, each time a new complex intent is identified, extending or producing a new dataset is needed as well. Therefore, more advanced and flexible techniques that cater for complex intent recognition are needed.

In our previous work, we identified and characterized a set of composite dialog patterns that naturally emerge when conversing with services [START_REF] Bouguelia | Reusable abstractions and patterns for recognising compositional conversational flows[END_REF]. In this paper, we focus on the recognition of complex intents in human-bot conversations. We take the view that complex intent recognition could be significantly improved by considering composite dialog patterns in addition to basic intent features. We propose an approach that relies on (i) existing NLP and ML techniques to extract natural language features (e.g., basic intents, dialog acts) and (ii) a rule-based approach that leverages these features together with contextual knowledge, enabled by composite dialog patterns and other metadata, to define complex intent recognition rules. These rules enable a higher-level of abstraction that offers flexibility for an extensible library of composite dialog patterns. When a new complex intent class is identified, a new rule template is added to recognize intents of this class from utterances. This approach requires to capture fairly complex context knowledge in addition to basic intents in order recognize complex intents. Thus, there is a need for advanced context representation and exploitation techniques that go beyond conversation history to include information inference that leverage metadata such as intent and API schemas (e.g, intents, slots, API methods) and relationships between their elements. Our contributions in this work are summarized as:

-We propose a rule-based approach that combines (i) natural language features (ii) composite dialog patterns and contextual knowledge to capture different classes of complex intents in a generic way. -We propose major extensions to the preliminary context knowledge service (CKS) presented in [START_REF] Bouguelia | Reusable abstractions and patterns for recognising compositional conversational flows[END_REF]. These extensions consist of an improved context knowledge model and a set of new services providing the contextual knowledge that is needed for the rules to recognize complex intents.

-Empirical evidence showing the effectiveness and user experience of the CKS and complex intent recognition. The user study showed that endowing bots with the complex intent recognition allow more natural interactions, as perceived by users and confirmed by performance metrics.

This paper is organized as follows: Section 2 describes a scenario and the general architecture; Section 3 details the CKS; Section 4 shows the rules to recognize and realize complex intents; Section 5 presents the experimentation; Section 6 presents the related work; Section 7 presents the conclusion and future work.

Scenario and Architecture

Before delving into the main contributions, we first introduce a scenario illustrating the proposition value of the CKS, and the supporting architecture.

Scenario

Consider a user who wants to plan some activities by conversing with a bot, as shown in Figure 1. The user interacts with the bot using complex intents where there may exist missing values. Existing state-tracking3 (ST) techniques support these interactions only in some cases and tend to be chatty and prompt users for the missing values. Slot values can be inferred by leveraging different sources: Infer slot value from conversation history. The composite pattern called slot-value-flow allows resolving a missing value of a slot by extracting it from conversation history. Existing ST techniques provide a limited support to this pattern. For example, in utterance #2, they can deduce that the missing value of the slot cinema-area is the same as the value of the slot restaurant-area and reuse it. However, in utterance #3, they use a coreference model to replace the expressions "the cinema" and "the restaurant" with the mentions "UGC cinema" and "LaGoulette restaurant", respectively, which are wrong values because they should be addresses. This will lead the bot to ask the user to provide the precise addresses values. A bot improved with CKS can infer these values by detecting that the departure is more likely related to the cinema-address than the cinema-name and thus reusing the address value.

Infer slot value by calling another API method. The composite pattern called nested-method allows resolving a missing value of a slot by triggering another method. For example, in utterance #4, the user wants to send a message. Instead of giving the recipient's phone number (i.e., tel), the user gives an expression that refers to the recipient's name (i.e., "my friend" to refer to "Hayet"). While existing ST techniques can deduce that the expression "my friend" refers to "Hayet", they cannot infer the value of the slot tel. A bot improved with CKS can detect that there is an API method having an output similar to the missing slot and therefore invokes this API method to infer the missing value. Identify the dependent method to get a value of an id. The composite pattern called API-calls ordering allows mapping an intent to a sequence of API calls to satisfy order constraints. For example, in utterance #5, the user wants to start a playlist, but the value of the slot playlist_id is missing. In existing ST techniques, unless the bot developer implements an intermediate method that combines the two API methods Spotify-Search and Spotify-Player, the bot will ask the user for the value of the slot playlist_id. A bot improved with CKS will automatically map the user intent (i.e., StartPlaylist) to a sequence of API calls to get the value of the id.

Infer slot value from an external data service. The composite pattern called entity-enrichment allows resolving a missing value of a slot from an external data service. The user is not always precise; she might refer to an entity mention that is common knowledge to inform a slot value. For example, in utterance #6, the user provides "Eiffel Tower" as a taxi destination instead of the precise address. Since they leverage only the conversation history, existing ST techniques will fail to infer the value of the destination slot. A bot improved with CKS, however, can enrich the "Eiffel Tower" entity with additional information such as its address, which is the target destination value.

Architecture

To empower bots in handling the previous scenario, the bot needs services that initiate, monitor, and control conversations. Once the DM collects all required information for the current state, (5) it calls the related API method and (6) sends the results to the Natural Language Generator (NLG). (7) NLG uses then predefined templates to generate humanlike responses to the user.

Extended Context Knowledge Service

Context Knowledge Model

The context knowledge model consists of: (1) the metadata of bot schema, user profile and external services and (2) the data stored as conversation progresses. Metadata is denoted as a context knowledge graph that includes mainly: (i) the definition of intents, slots, API methods, API parameters, and entity types, and (ii) relationships between these elements (e.g., SearchCinema intent is realized by the method Yelp-SearchBusiness, departure slot is same-as address parameter, etc.). Figure 3 illustrates an example of this graph related to the conversation scenario. The context knowledge graph includes also the metadata of external data services (e.g., Google KG, wikidata) and user profiles. The key intuition behind including external data services is to endow the bot with the capability of enriching entities with additional information from these services. However, an external data service may return several entities for a given mention. Thus, having a mechanism that links the entity mention to its corresponding entity in the data service is necessary. This is where the user profile comes into play. User profile attributes like location, preferences can be used as filters to select the appropriate entity. Thus, we introduce the following node types: External service, Profile attribute and relationship types: is-retrieved-by, filtered-by. External service refers to a data service used for an entity enrichment. Often, a data service has an input parameter that takes a text query, which in our case will be filled by the entity mention (e.g., "Eiffel Tower"). is-retrieved-by is defined between an entity type and an external service, (e.g., the entity type place can be retrieved from Google-PlaceSearch service). filtered-by is defined between an entity type and a profile attribute, meaning that entities of that entity type can be filtered by the given attribute (e.g., place entities can be filtered by location). The generation of filtered-by edges is based on computing the cosine similarity [START_REF] Sitikhu | A comparison of semantic similarity methods for maximum human interpretability[END_REF] between the vector embedding 6 of each pair of entity type attributes and profile attributes. Assume that a user profile is defined by this set of attributes (gender, location, dietary) and the entity type place has the attribute city among others, a filter-by edge will be added between place and only location since it is similar to city. We assume that the external data services and their input parameters, the related is-retrieved-by relationships and the user profile attributes 7 are specified by the bot developer. Data includes relevant information that should be memorized during user-bot conversations for later reuse. Two memory structures are used to store this data: Local Context Memory (LCM) and External Context Memory (ECM). The LCM keeps track of all the traces related to each intent fulfillment. This includes the utterance, the intent, the method call, alongside with its timestamp, its inputs, and its outputs. The ECM, on the other hand, keeps track of all entities mentions in user utterances. It also provides all information that external data services extract to enrich these entities mentions. We structure ECM in terms of entities; each is associated with its mention, entity type, and its retrieved attribute values. Examples of data related to the scenario are documented in online appendix8 .

CK services

The CKS features four services, two of which are devoted to supporting the inference of slot values from the conversation history and external data services, whereas the two others aim at providing the contextual knowledge that is needed for the rules to recognize complex intents.

History search: This service allows inferring slot values from the conversation history. It is enabled by the endpoint "CKS/history? ms & u" which takes as inputs the missing slot ms, and the utterance u and returns the value of the slot ms when possible. First, the service extracts the relevant entity-mention pairs from the utterance. An entity-mention is relevant if the extracted entity has an attribute same-as the missing slot. Consider utterance #3" the entity-mention (restaurant, LaGoulette) is relevant because the entity restaurant has an attribute address same-as the missing slot taxi-destination. Second, the service rewrites the utterance by replacing each mention with the corresponding attribute's value. For example, the utterance "book a taxi from UCG cinema to LaGoulette restaurant" will be "book a taxi from [UCG-address] to [LaGouletteaddress]". The rewriting is important to know if the value of taxi-destination is the restaurant or the cinema address. The service then extracts the missing value from the new utterance. If there is no relevant entity-mention in the utterance, the service returns the most recent value of the parameters same-as the missing slot. For example, in utterance #2, there is no entity-mention, so the service returns the value of the restaurant's area.

Entity enrichment: This service allows enriching entity attributes from external data services. It is enabled by the endpoint "CKS/invoke_external_service? s & em & a". Consider utterance #6, the service takes as inputs: the external data service s: Google-PlaceSearch, the entity-mention em: (place, Eiffel Tower), and the attribute a: address and it returns the value of a. To obtain the attribute value from the appropriate entity, three steps are followed. First, the service invokes the external data service related to the given entity-mention em, which returns a set of entities. Then, it filters the returned entities by discarding any entity, whose similarity with the entity-mention em is less than a predefined threshold and it does not contain the target attribute value. The similarity is computed on the basis of the cosine distance between the embedding vectors of the entity-mention em and the name of the entity returned by the external service. After this step, if only one entity is returned, the service retrieves the target attribute value from it. Otherwise, in order to identify the right entity, the service proceeds a second filtering step based on the filter attributes related to the mention entity type in the metadata. This filter step is expected to return one entity that matches the most of filters while giving a high priority to the location filter. Nested method identification: This service allows identifying an API method that needs to be invoked to obtain the missing value. It is enabled by the endpoint "CKS/nested_method? ms & set_em". Consider utterance #4. The service takes as inputs the missing slot ms: tel, and the set of detected entity-mentions set_em: {(person, Hayet)}. It then gets from the metadata the methods that have an output parameter same-as the slot. For example, the service gets the set of methods {contacts-get, businessDetails-get} where the missing slot tel is the same-as one of the outputs of contacts-get (i.e., phoneNbr) and also the same-as one of the outputs of businessDetails-get (i.e., phone). The service relies on the detected entity-mentions to select the relevant method from the set of methods. For example, in contrast to the method businessDetails-get, the method contacts-get has an input parameter contact same-as to one of the detected entity person. Thus, the service selects contacts-get as the nested method and returns it along with its input values {(contact, Hayet)} and one of its outputs phoneNbr that is same-as the slot tel. Dependent Method identification: This service allows identifying a dependent method to get a value of an id. It is enabled by the endpoint "CKS/dependent _method? i" where i is the given intent. This endpoint first gets the method m1 that realize the intent i. Then, it gets the dependent method m2 where m1 depends on m2. For example, in utterance #5, the endpoint takes the intent StartPlaylist as input and returns: the dependent method Spotify-Search, its input parameters {q, item}, and its id output parameter spotify_id.

Complex Intent Recognition

We propose a new rule-based approach to support Complex Intent Recognition (CIR). Our approach offers flexibility for an extensible library of dialog patterns, i.e., when a new class of a complex intent is identified, we can add its new rule to recognize the intents of this class from user utterances. We express a rule using a combination of natural language features and contextual knowledge. In what follows, we first define functions that we use to specify the rules, then we specify the rule of each pattern introduced in Section 2.1.

Functions

Functions are the primitives that we use to define the rules. We consider function input and output types to be standard data types found in common programming languages such as string and boolean; as well complex data types such as Tuple or Set. Thus, we can leverage the standard operators designed for these data types. We distinguish two types of functions: dialog act functions to capture natural language features and context metadata functions to capture contextual knowledge. These functions are offered by the NLU and the CKS, respectively. Dialog Act functions identify hidden actions in user or bot messages. Whether the user is providing information, or asking a question, or the bot is providing suggestions, are all hidden acts in user or bot messages. We focus on two dialog act functions: INTENT_OF(), which identifies the intent i expressed in a given utterance u, and SLOT_VALUE(), which returns the value of a given slot s recognized in the utterance u or NULL if no value of s is recognized in u.

Context Metadata functions allow to access and query the metadata graph defined in Section 3.1 to get the contextual knowledge. For example: GET_SAMEAS_ PARA() is a metadata function that returns a set of parameters that are the sameas a given slot s; DEPENDS_ON() returns a method name m b given a method name m a where m a depends on m b or it returns NULL if there is no dependent method.

Complex Intent Recognition Rules

A rule consists of trigger and action clauses. The trigger clause specifies the conditions that need to be verified to recognize complex intents. Then, the sequence of operations specified in the action clause are executed to fulfill the related complex intent. The following statement specify a rule:

Rule "name of the rule" when trigger then action

Triggers are expressed as boolean conditions over functions, including dialog act and metadata functions. Table 1 provides examples of boolean functions that are used to define triggers. Conditions may be combined using conjunction operator (AND). The action is a sequence of operations. For instance, an operation can be an assignment of a value to a given variable, or an invocation of a CKS service. Figure 4 shows the definition of rules for each composite pattern: Slot-value-flow Rule. The first condition checks if the identified intent i is a new intent. The second condition checks if the value of the slot ms is missing. These two conditions are the same for nested-method and entity-enrichment rules. The third condition checks if there is at least one already fulfilled parameter that is the same-as the slot ms. If the conditions are satisfied, the bot: (1) invokes Nested-method Rule. The third condition checks if there is at least one output parameter that is the same-as the slot ms. If the conditions are satisfied, the bot: (1) invokes the nested method CKS service to identify: the nested method m nes , its input values set_iv nes , and its output parameter o nes . Then, the bot (2) invokes the method m nes to get the value of o nes , (3) uses this value as a value for the slot ms, and (4) invokes the method that realize the intent i.

API-calls-ordering Rule.

The first condition is similar to the first condition of the other rules. The second condition checks if the method that realize the intent i depends on another method. If the conditions are satisfied, the bot: (1) invokes the CKS service to identify: the dependent method m dep , its inputs set_i dep , and the id parameter id dep . Then, the bot (2) calls GET_VALUES_ASKUSER() to get the input values of the method m dep by extracting them from the utterance, the history, or by asking the user. After getting the input values, (3) invokes m dep to get the value of id dep , (4) uses this value as a value for the parameter id, and (5) invokes the method that realize the intent i.

Entity-enrichment Rule. Given a set of entities mentions set_em, extracted from u, the third condition checks if there is at least one attribute of an entitymention that is the same-as the slot ms. If the conditions are satisfied, the bot: (1) calls the metadata function GET_REQUIREMENTS() to get the following information: the related service s, the entity-mention em, and the attribute a.

Note that this function chooses one entity-mention from set_em based on the one that has an attribute same-as the slot ms, (2) invokes the entity enrichment CKS service to get the value of the attribute, (3) uses this value as a value for the slot ms, and (4) invokes the method that realize the intent i.

Experiments

The first objective of the study was to explore the effectiveness and limitations of (i) the proposed CKS (i.e., its capability of inferring slots' values correctly and reducing unnecessary interactions) and (ii) the CIR (i.e., its capability of recognizing correctly the composite dialog patterns mentioned previously). The second objective was to evaluate the user experience (i.e., naturalness, repetitiveness, understanding) in interacting with a bot improved with CIR and CKS.

Methods

Experimental design. Participants were recruited via email from the extended network of contacts of the authors. The call for volunteers resulted in a total of 20 participants. We prepared an evaluation scenario that required participants to interact with a set of API methods through a bot to plan an evening activity in Paris. Participants were asked to complete four different tasks in this scenario (T1: checking the weather and searching for restaurants, T2: booking a restaurant table, T3: booking a taxi, and T4: sending a confirmation message to the travel partner). The tasks were designed to leverage the type of support provided by the CKS, if the composite dialog patterns were to be effectively recognized (T1: inferring slot value from conversation history, T2: identifying dependent method, T3: using an external data source, and T4: identifying nested method). We followed a within-subjects design,9 tasking participants to interact with two bots representing the following experimental conditions:

-DM-Baseline. The baseline implements a standard conversational management, without composite dialog patterns and CKS support. -DM-CKS. This bot is implemented with the CIR and CKS support.

The two bots relied on the same NLU implementation (in DialogFlow), bot interface, and differed only in the composite patterns and CKS support. Procedure. The study was conducted online. Participants received a link to an online form that included an informed consent, all the instructions, links to the bots and feedback required. In the study, participants were introduced to the evaluation scenario and tasks, and were asked to perform those tasks with the two bots. The order in which the bots were presented to users was counterbalanced. For each bot, participants were asked to provide open-ended feedback on the pros and cons of their experience. The last part of the study then asked participants about their preferred bot, the reason why, and a quantitative feedback on their user experience. We adopted the user experience questions from prior work [START_REF] Holmes | Usability testing of a healthcare chatbot: Can we use conventional methods to assess conversational user interfaces?[END_REF], to get feedback on the perceived naturalness (i.e., ability to fulfill user tasks in human-like conversations), repetitiveness (i.e., ability to avoid redundant questions) and understanding (i.e., ability to interpret user requests). Data analysis. We performed an analysis of conversation logs so as to assess the effectiveness of the CKS and the CIR. These are calculated in relation to optimal conversation scenarios 10 that we designed based on participants conversations. The CKS effectiveness is calculated by considering the following metrics: number of (M1) conversation turns, (M2) prompts asking for missing slot values, and (M3) missing slot values correctly inferred. The effectiveness of the CIR (only available in DM-CKS) is calculated by considering the number of (M4) complex intents correctly detected. These metrics are calculated per user conversation, aggregated (mean) and then used to compute the relative performance against the optimal scenario. We also performed a qualitative analysis of open-ended responses and conversation logs to contextualise the results from the metrics and identify limitations.

Results

Effectiveness of CKS and CIR. Table 2 shows the relative performance by task of both bots DM-Baseline and DM-CKS in relation to the optimal reference scenario. For the four tasks, we can see that DM-CKS bot experienced a boost in performance for M1 and M2 metrics (mean across tasks 94.66% and 88.4% respectively), approaching the efficiency in terms of number of turns and prompts of the reference ideal scenario. This level of performance is possible due to the accuracy of the slot value inference (M3) performed by the CKS services supporting each task -a mean relative performance across tasks of 96%. In contrast, not having the support of the CKS services lead the DM-Baseline bot to perform poorly in comparison, with the best performance being at around 37.18% for the metrics considered. These results provide evidence for the benefits and effectiveness of the CKS support. Table 2 also shows the relative performance of recognizing complex intent (M4) by the bot DM-CKS in relation to the reference scenario. By analyzing the conversations, we noticed that the recognition error of the composite dialog patterns is mostly caused by the detection error of the correct intent by the NLU during the conversation. For example, if the NLU detects the intent SearchRestaurant instead of BookTaxi, in the utterance "I want to go to this restaurant", this will lead to an error in detecting the slot-value-flow pattern that takes the restaurant address as the destination address. However, for the four tasks, we can see that DM-CKS bot is close to the reference scenario with a mean relative performance across tasks of 94.86%. User experience. All but one participant (19/20 participants) expressed a preference towards the DM-CKS bot as opposed to the baseline. The one exception was due to NLU limitations in recognizing user expressions that led to the enactment of the wrong services. The feedback to the specific user experience questions, as well as the open-ended feedback, highlighted the reasons behind the preference. Participants agreed with DM-CKS interactions describing naturalness (14/20), less repetitiveness (16/20) and understanding (15/20), whereas the baseline was poorly rated on these fronts (1/20). Interestingly, these qualities were linked to the CKS support, such as the ability to infer missing slot values from conversation history (e.g., "saying that the drop-off address was the restaurant I have just booked was enough", P1), or from external services (e.g., "

[it] found the address when I said Eiffel Tower", P6). The ability to handle complex intents also emerged as a defining feature (e.g., "[DM-CKS] is capable of undertaking complex tasks and retaining previous information", P16). In contrast, participants reported having to copy & paste previous values or google some information during their interactions with the baseline bot.

Limitations. The conversation analysis revealed some limitations in supporting the natural language interaction described by the users: Enumerating entities when the number of entities is expected. In the context of T2, when asked "For how many people do you want to book a table?", some participants would respond with "For me and my friend". The bot could not infer the number of seats from the participant's utterance because it expected to extract a number. This would be an acceptable answer in a natural conversation, and represent as a new type of inference that needs to be considered.

Introducing typos when providing slot values. When booking a taxi in the context of T3, some participants spelled "Eiffel tower" incorrectly (e.g., "Book a Taxi from the Eifeltower"), which led to the failure of the CKS service for inferring values from a external data source. Handling mistakes when performing inferences is a situation that needs to be addressed.

Related Work

Our work is related to the ST process that aims to infer the dialog state in terms of the user intent and its slot-value pairs during conversations [START_REF] Rastogi | Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset[END_REF]. Depending on the leveraged knowledge sources, existing ST approaches can be organized into history-based, schema-based, and Linguistic patterns (LPs) based.

History-based approaches rely on the whole or window-size of the dialogue history to predict the dialog state. Deep learning models including HRNN [START_REF] Goel | Hyst: A hybrid approach for flexible and accurate dialogue state tracking[END_REF], LSTM [START_REF] Gao | Dialog state tracking: A neural reading comprehension approach[END_REF] and BERT [START_REF] Zhang | Find or classify? dual strategy for slot-value predictions on multidomain dialog state tracking[END_REF] are utilised to encode the dialog history. Other works [START_REF] Chao | Bert-dst: Scalable end-to-end dialogue state tracking with bidirectional encoder representations from transformer[END_REF][START_REF] Ren | Scalable and accurate dialogue state tracking via hierarchical sequence generation[END_REF] leverage only on the previous dialog states to predict the current state instead of taking the whole history. More advanced approaches [START_REF] Ouyang | Dialogue state tracking with explicit slot connection modeling[END_REF][START_REF] Ye | Slot self-attentive dialogue state tracking[END_REF][START_REF] Hu | SAS: Dialogue state tracking via slot attention and slot information sharing[END_REF] focused first on the learning of slot dependencies from the history and then incorporated them into the ST model, allowing it to infer slot values from similar slots. Most of the ST approaches either focused on recognizing only basic intents or ignored their recognition at all. Similar to some of these, we build upon advances in ML techniques to enable the recognition of basic intents but contribute a new rule-based approach to recognize complex intents.

Schemas-based approaches leverage schemas capturing the structural representation of conversation data to predict the dialog state. Works like [START_REF] Chen | Schema-guided multi-domain dialogue state tracking with graph attention neural networks[END_REF], [START_REF] Lin | Knowledge-aware graph-enhanced GPT-2 for dialogue state tracking[END_REF] [19] use a slot-level schema graph that captures dependencies between slots. The aim is to allow the ST model to infer slot values from similar slots. Other efforts like [START_REF] Liao | Dialogue State Tracking with Incremental Reasoning[END_REF] leverage the backend database schema in ST model to allow slot inference from the database entities. These methods, however, work with bots integrated only with databases, where the inferred slot-value pairs are used to frame the query. Since our context knowledge model integrates API/Service schema, where each intent is associated with its corresponding API method, our approach can handle flows supported by software-enabled services. The work [START_REF] Andreas | Task-oriented dialogue as dataflow synthesis[END_REF] represents the dialogue state as a dataflow graph and the complex user intent as a dataflow program. For each user utterance, a trained model allows predicting the corresponding dataflow program. This approach relies on datasets where each utterance must be annotated with the corresponding dataflow program; however, it is not intuitive task to annotate utterances with programs. The closest work to ours is [START_REF] Rastogi | Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset[END_REF] which introduced a unified schema defining a service or API as a combination of intents and slots. A BERT-based ST model then takes this schema as input to enable the recognition of intents and inferring their slot-value pairs. The captured knowledge (i.e., the unified schema), however, can only help in the recognition of basic intents. In our work, we devise the CKS mainly to capture the contextual knowledge that is required to recognize complex intents.

In addition to the conversation history and intent/slot schemas, this knowledge includes API/Service schemas and enriched entities. Our CIR technique exploits both this knowledge and basic intent features to recognize the complex intents.

LPs-based approaches leverages linguistic patterns that are drawn mainly from human conversation to handle some complex intents and inferring their slots [START_REF] Fast | Iris: A conversational agent for complex tasks[END_REF], [START_REF] Rastogi | Scaling multi-domain dialogue state tracking via query reformulation[END_REF]. For example, IRIS [START_REF] Fast | Iris: A conversational agent for complex tasks[END_REF] draws on two existing LPs dependent questions (i.e., one question depends on the answer to some subsequent request), and anaphora (i.e., expressions that depend on previous expressions) to allow composition and sequencing of intents.These approaches, however, are not enough to capture complex intents that naturally emerge when conversing with services. For instance, while this utterance "Send the message 'I will be at UGC cinema at 3 pm' to Hayet" refers to a complex intent requiring a composition of two API methods, it cannot be recognized by IRIS. The reason is that IRIS can recognize composition based only on linguistic features (e.g., A composition is recognized when a user answers with a new intent to the bot request for a missing slot). In contrast to the LPs-based approaches, we focus on using composite dialog patterns that cater to the inherent features in interactions between humans, bots, and services in addition to the linguistic ones. These patterns are used to enable the contextual knowledge required by the CIR to recognize complex intents.

Conclusions and Future Work

We proposed reusable and extensible rule-based technique that uses a sophisticated context service to recognize and realize complex intents. We believe that our approach charts novel abstractions that unlock the seamless and scalable integration of natural language-based conversations with software-enabled services. We devised a novel complex intent recognition that allows the incremental acquisition of rule templates to identify composite intents from basic dialog acts and context features. The contextual knowledge required at run-time to recognise complex intents and infer slot values from user-bot conversations is extracted from conversation history, enriched entities, intents and API schemas and represented in graph structure. Future work includes identifying new composite patterns (e.g., supporting conversations with business process models) and developing privacy-aware task-oriented bots by reasoning about privacy-preserving conversations.

Fig. 1 .

 1 Fig. 1. Example of user-bot conversation where there are some complex intents.

Figure 2 Fig. 2 . 3 )

 223 Fig. 2. General architecture supporting our approach.tween these services. When a bot receives a new utterance, (1) the Co-Ref service takes this utterance and the previous messages as input and resolves the potential referenced mentions. We use Neuralcoref 4 , as a coreference resolution model. Then, (2) the utterance is sent to the Natural Language Understanding (NLU) service to extract intent and slot values. We use DialogFlow 5 NLU model. The Dialogue Manager (DM) aims to coordinate the information flow in the conversation. In our approach, the DM uses a Conversational State Machine (CSM) model to represent bot behaviors[START_REF] Zamanirad | Hierarchical state machine based conversation model and services[END_REF] and relies on a Complex Intent Recognition (CIR) technique to identify complex intents (details in Section 4).(3) Once the DM gets the intent and slot values, it creates a composite state, in the CSM, if the CIR recognizes a complex intent. Otherwise it creates an ordinary state. (4) The CKS keeps track of conversation knowledge, infers missing slot values, and provides a set of new services supporting the recognition of complex intents (details in Section 3).Once the DM collects all required information for the current state, (5) it calls the related API method and (6) sends the results to the Natural Language Generator (NLG). (7) NLG uses then predefined templates to generate humanlike responses to the user.

Fig. 3 .

 3 Fig. 3. Context knowledge graph related to the conversation of Figure 1. For clarity purpose we do not represent all nodes and edges.

Fig. 4 .

 4 Fig. 4. Rules of composite dialog patterns

21 Rue Maximilien Palaiseau Paris to the Eiffel Tower today at 10 am Bot: Done! I have booked a taxi from 21 Rue Maximilien Palaiseau Paris to Champ de Mars, 5 Av. Anatole France, Paris today at 10 am. User: Just one last thing, can you start the playlist called My Happy Melodies on Spotiffy

	User: Send a message to my friend, tell her "I'll
	User: Oh, I also need a taxi to go from Bot: Sure, starting playlist ...Done!

be at UGC cinema at 3 pm" Bot: Done

  ! I sent the message "I'll

be at UGC cinema at 3 pm" to

	User: I am excited to see my friend Hayet! Book a taxi from the cinema to the restaurant today at 5 pm
	Bot: Done! I booked a taxi from
	Hayet phone number +33783425005
	API-METHOD: contacts-get: (contact, Hayet), (phoneNbr, +33783425005), (email, b.hayet@gmail.com)
	twilio-SendMessages: (tel, +33783425005) (msg, I'll be at UGC cinema at 3 pm)

166 Boulevard Macdonald Paris to 59 Rue de la verrerie Paris today at 5 pm.

	User: I am also looking for a cinema
	Bot: I found the UGC cinema. The address is
	.
	Text

166 Boulevard Macdonald Paris. #2 #3 #4 #5 #6 User: I am looking for a Tunisian restaurant in Paris Bot: LaGoulette restaurant serves Tunisian food. The address is 59 Rue de la verrerie Paris. #1

	INTENT: SearchRestaurant: (restaurant-area, Paris), (food, Tunisian restaurant)
	API-METHOD: Yelp-SearchBusiness: (location, Paris), (term, Tunisian restaurant), (name, LaGoulette), (address, 59 Rue de la verrerie Paris)
	INTENT: SearchCinema: (cinema-area, ?), (term, cinema)
	API-METHOD: Yelp-SearchBusiness: (location, Paris), (term, cinema), (name, UGC), (address, 166 Boulevard Macdonald Paris)
	INTENT: BookTaxi: (departure, ?), (destination, ?), (date, today), (time, 5 pm)
	API-METHOD: taxicode-booking: (pickup,

166 Boulevard Macdonald Paris), (destination, 59 Rue de la verrerie Paris), (

	date, today), (time, 5 pm)
	API-METHOD: Soptify-Search: (q, My Happy Melodies) (item, playlist) (spotify_id, 59ZbFPE)
	Soptify-Player: (spotify_id, 59ZbFPE)
	INTENT: BookTaxi: (departure, 21 Rue Maximilien Palaiseau Paris), (destination, ?), (date, today), (time, 10 am)
	API-METHOD: taxicode-booking: (pickup, 21 Rue Maximilien Palaiseau Paris), (destination,

Champ de Mars, 5 Av. Anatole France, Paris),

		Legend
		Input parameter
		Output parameter
		Inferred value
	value inferred from history
	value inferred from history	value inferred from history
	INTENT: SendMsg: (tel, ?) (msg, I'll be at UGC cinema at 3 pm)
	value inferred by calling another API Method (i.e., contacts-get)
	INTENT: StartPlaylist: (playlist-id, ?)
	value inferred by calling the dependent method (i.e., Spotify-Search)
	(date, today), (time, 10 am)	value inferred from an external data service

Table 1 .

 1 Examples of boolean functions to express triggers

	Functions	Inputs	Description
	IS_NEW_INTENT()	u: string	returns true if the identified intent in the utterance u
			is a new intent.
	HAS_MISSING_SLOT()	u: string	returns true if the value of the given slot s is not rec-
		s: string	ognized in the utterance u.
	HAS_SAMEAS_PARA()	s: string	returns true if there is at least one parameter that is
			the same-as the slot s.
	EXIST_NESTED()	s: string	returns true if there is at least one output parameter
			that is the same-as the slot s.
	IS_DEPENDENT()	i: string	returns true if the method that realize i depends on
			another method.
	HAS_SAMEAS_ATT()	set_em: set	returns true if at least one entity in set_em has an
		s: string	attribute that is the same-as the slot s.

Table 2 .

 2 Bot performance for each task according to relevant metrics. Values in bold denote best performance. Percentages denote the relative performance with respect to the reference (optimal) scenario.

			DM-Baseline			DM-CKS
	Task (service)	M1 (TURNS)	M2 (PROMPTS)	M3 (SLOTS)	M1 (TURNS)	M2 (PROMPTS)	M3 (SLOTS)	M4 (PATTERN)
	T1 (history)	59.70%	21.18%	49.24%	98.04%	90%	96.97%	95%
	T2 (dependent)	61.18%	42.11%	17.86%	92.86%	95.24%	95.24%	94.44%
	T3 (external)	46.97%	32.39%	3.17%	91.18%	88.37%	95.24%	95%
	T4 (nested)	52.97%	20%	39.41%	96.55%	80%	96.55%	95%
	Mean	55.21%	28.92%	27.42%	94.66%	88.4%	96%	94.86%

State-tracking consists of determining user intent and its required slot values.

NeuralCoref: https://spacy.io/universe/project/neuralcoref

DialogFlow: https://dialogflow.com/

Vector embeddings are obtained using the off-the-shelf spaCy NLP model

Updating user profiles from conversations is out of the paper scope.

Examples of data: https://tinyurl.com/scenario-data

Study materials and in-depth results available at https://tinyurl.com/ study-materials


Gisella Croce
email: gisella.croce@univ-lehavre.fr

Catherine Lacour
email: lacour@math.univ-montp2.fr

Gérard Michaille

A CHARACTERIZATION OF GRADIENT YOUNG-CONCENTRATION MEASURES GENERATED BY SOLUTIONS OF DIRICHLET-TYPE PROBLEMS WITH LARGE SOURCES *

Keywords: Mathematics Subject Classification. 49Q20, 28A33 Gradient Young measures, concentration measures, minimization problems, quasiconvexity

come

A characterization of gradient Young-concentration measures generated by solutions of Dirichlet-type problems with large sources

Introduction

Let us consider the one-dimensional Dirichlet problem in (-1, 1) with a second member measure

⎧ ⎪ ⎨ ⎪ ⎩ (σ ε (x)u ) = 1 √ ε m k=0 a k δ t ε k u(-1) = u(1) = 0, (1.1)
where ε > 0, m ∈ N, a k ∈ R * , (t ε k ) k=0,...,m is a non decreasing family of numbers in [-

ε 2 , ε 2 ] with t ε 0 = -ε 2 , t ε m = ε 2 , lim ε→0 t ε k+1 -t ε k ε = 1
m := l for k = 0, . . . , m -1, and σ ε is given by

σ ε (x) = 1 ε , if x ∈ (-1, 1) \ (-ε 2 , ε 2 ) 1, if x ∈ (-ε 2 , ε 2 ).
Let ūε be the solution of (1.1); then clearly ū ε is of the form

ū ε (x) = ⎧ ⎪ ⎨ ⎪ ⎩ εc ε , if x ∈ (-1, -ε 2 ) c ε + s k √ ε , if x ∈ (t ε k , t ε k+1 ), k = 0, . . . , m -1 ε(c ε + sm √ ε ), if x ∈ ( ε 2 , 1),
where s k := k i=0 a i and c ε is a constant which can be computed from the boundary conditions. Setting vε = ūε √ ε one can show that the measure ½ (-ε 2 , ε 2 ) ε|v ε | 2 dx weakly converges to l m-1 k=0 (L + s k ) 2 δ 0 , where L is the limit of √ εc ε (see Sect. 4 for the computations). Consequently the gradient of the solution ūε presents a concentration phenomenon in L 2 ((-1, 1)). The knowledge of the limit measure l m-1 k=0 (L + s k ) 2 δ 0 is not completely satisfactory to describe the concentration phenomenon. Indeed v ε clearly oscillates near x = 0 from the observation that not all the coefficients s k are necessarily of the same sign. A natural question to ask is how to capture these oscillations at the limit. To this end, we compute the weak limit μ = μx ⊗ π of the measure

με := δ v ε |v ε | (x) ⊗ ½ (-ε 2 , ε 2 ) ε|v ε | 2 dx ∈ M([-1, 1] × {-1, 1}) in the sense that ε 1 -1 ½ (-ε 2 , ε 2 ) ϕ(v ε )θ(x) dx → 1 -1 θ(x) {-1,1} ϕ(ζ) dμ x dπ
for all 2-homogeneous and continuous functions ϕ on R and all functions θ in C( [-1, 1]). We write μx ⊗ π to denote the slicing decomposition of the measure μ with respect to its projection measure π on [-1, 1]. We will call μ the gradient Young-concentration measure generated by (v ε>0 ). Note that (μ x ) x∈(-1,1) is a family of probability measures on the unit sphere S 0 := {-1, 1} of R. Why is μ useful to capture the oscillations of v ε at the limit? It is easy to show that π is nothing but the weak limit l m-1 k=0 (L + s k ) 2 δ 0 of the measure

½ (-ε 2 , ε
2 ) ε|v ε | 2 dx. Moreover, we show that (see Sect. [START_REF] Kinderlehrer | Characterization of Young measures generated by gradients[END_REF] for the details) μx = aδ 1 + bδ -1

where, if we assume for instance L ≥ 0, a = k=0,...,m-1:

s k ≥0 (L + s k ) 2 m-1 k=0 (L + s k ) 2 , b= 1 -a = k=0,...,m-1:s k <0 (L + s k ) 2 m-1 k=0 (L + s k ) 2
(if L ≤ 0, take the condition s k > 0 in the sum defining a, and s k ≤ 0 in the sum defining b). One sees that whereas the measure π provides the intensity l m-1 k=0 (L + s k ) 2 and the support {0} of the concentration, the coefficients a and b in [0, 1] provide the desired additional information, i.e., the proportion of change of sign of v ε captured at the limit, with respect to the total mass of the limit measure π.

In this article we want to generalize the previous notion of gradient Young-concentration measure when ūε is the solution of a Dirichlet problem on a domain Ω of R N , N > 1, with a source of magnitude order 1 √ ε . We assume that a (N -1)-dimensional manifold Σ, possessing an unit normal vector ν at H N -1 a.e. x, splits Ω into two subdomains and that the conductivity outside the ε-neighborhood Σ ε of Σ grows as 1 ε . The simplest model is given by ūε ∈ argmin 1

ε Ω\Σε |∇u| 2 dx + Σε |∇u| 2 dx - 1 √ ε F ε , u : u ∈ W 1,2 0 (Ω) (1.2)
where

F ε ∈ H -1 (Ω); setting v := u √ ε , (1.2) is equivalent to vε ∈ argmin Ω\Σε |∇v| 2 dx + ε Σε |∇v| 2 dx -F ε , v : v ∈ W 1,2 0 (Ω) .
By analogy with the one-dimensional case, the estimation

sup ε>0 Ω\Σε |∇v ε | 2 dx + ε Σε ∂v ε ∂ν 2 dx < +∞
implies that ∂vε ∂ν presents a concentration phenomenon on S ⊂⊂ Ω. To describe it, we will characterize the weak cluster points μ of the sequence δ ∂ vε

∂ν /| ∂ vε ∂ν | (x) ⊗ ε½ Bε | ∂vε ∂ν | 2 dx
in the set of non-negative bounded Borel measures M + ( Ω × S 0 ) on Ω × S 0 , where B ε denotes the ε-neighborhood of S. We will call μ the gradient Youngconcentration measure generated by (v ε ) ε>0 . In contrast to the one-dimensional case, it is difficult to express the measure μ and we adopt the following strategy: under some additional hypotheses on F ε , one can prove that a subsequence of vε strongly converges in L 2 (Ω) to some function v ∈ W 1,2 (Ω \ Σ); our objective is to provide an intrinsic characterization of μ (i.e., independent of the sequence) with respect to the Sobolev function v, in the spirit of [START_REF] Fonseca | Analysis of concentration and oscillation effects generated by gradients[END_REF][START_REF] Kinderlehrer | Characterization of Young measures generated by gradients[END_REF]. Actually, we characterize the limits (v, μ) generated by sequences (v ε ) ε satisfying the partial finite energy condition

sup ε>0 Ω\Σε |∇v ε | 2 dx + ε Σε ∂v ε ∂ν 2 dx < +∞.
We show that v and μ = μ x ⊗ π with μ = (a(x)δ 1 + b(x)δ -1 ) ⊗ π, are linked by the necessary and sufficient conditions:

v ∈ W 1,2 (Ω \ Σ), v = 0 on ∂Ω; spt(π) ⊂ S; dπ dH N -1 S (x)(a(x)c + b(x)d) ≥ ϕ([v](x)) (1.3) for H N -1 S a.e.
x and for all (c, d) ∈ R + × R + where

ϕ(ξ) = cξ 2 , if ξ ≥ 0 dξ 2 , if ξ ≤ 0.
In addition, in Example 3.2 we will exhibit a large class of non trivial pairs (v, μ) satisfying (1.3) and generated by sequences (v ε ) ε>0 of solutions to Dirichlet problems with large sources concentrated on Σ ε . Moreover the probability measure μ x can be completely expressed.

It is worth noticing that the internal energy functional of (1.2) or (1.4), (1.5) below, rewritten in terms of the rescaled function v, is the type of functionals considered in [START_REF] Licht | A modelling of elastic adhesive bonded joints[END_REF][START_REF] Licht | A model of elastic adhesive bonded joints through oscillation-concentration measures[END_REF] in order to model adhesive bounded joints through the computation of a variational limit problem. In this paper, it is not our purpose to describe a variational limit of (1.2), (1.4) or (1.5), even if this program would be interesting because of the additional difficulty due to the source. Among the physical motivations of (1.2), or of more general Dirichlet problems of the form

-div (σ ε (x)∂f (∇u)) = 1 √ ε F ε on Ω u = 0 on ∂Ω, (1.4) ν Ω Σ S B ε Figure 1. The physical configuration.
where σ ε := 1 ε ½ Ω\Σε + ½ Σε and f : R N → R is a positively 2-homogeneous convex function, one may mention various applications to:

-heat conduction or electrostatic problems subjected to large concentrated sources, with high conductivity outside the support of the sources; -membrane problems with large concentrated exterior loading and high stiffness outside the support of the loading.

Note that we treat this study in a vectorial environment, that is, we consider the following problems defined over W 1,2 0 (Ω, R m ), with m ≥ 1 by

ūε ∈ argmin 1 ε p-1 Ω\Σε f (∇u) dx + Σε g(∇u) dx - 1 ε 1-1/p F ε , u : u ∈ W 1,p 0 (Ω, R m ) , p > 1 (1.5)
where f, g : R N ×m → R are two positively p-homogeneous and quasiconvex functions, and

1 ε 1-1/p F ε
is the exterior loading. To shorten the proofs, we only consider the case p = 2.

Towards the definition of gradient Young-concentration measures

Let N , m be two positive integers. Throughout this paper L N and H N -1 denote the N -dimensional Lebesgue measure and the (N -1)-dimensional Hausdorff measure on Ω, respectively. We will sometimes write dx for the measure L N and |B| for the N -dimensional Lebesgue measure or the (N -1)-dimensional Hausdorff measure of any Borel subset B of Ω, if there is no ambiguity. In the N -dimensional Euclidean space R N with respect to the orthonormal frame (O, e 1 , . . . , e N ), we consider a (N -1)-hypersurface Σ which splits Ω into two subdomains Ω + and Ω -, i.e. Ω = Ω + ∪ Σ ∪ Ω -. To avoid certain technical complications, we will additionally assume that Σ is included in the hyperplane vect(e 1 , . . . , e N -1 ) generated by {e 1 , . . . , e N -1 } and orthogonal to the unit vector ν = e N , but we point out that we could treat the problem in the more general case where Σ is the graph of a Lipschitz function. Such a general geometry leads to technical complications in the proofs, but the overall strategy remains the same. For any point x in Ω, we write x for its projection on vect(e 1 , . . . , e N -1 ), so that x = (x, x N ). We set Σ 1).

ε := {x + tν : x ∈ Σ, -ε 2 < t < ε 2 } and, for S ⊂⊂ Σ, B ε := {x + tν : x ∈ S, -ε 2 < t < ε 2 } (see Fig.
We assume that (F ε ) ε>0 is a bounded sequence in the topological dual of W 1,1 0 (Ω, R m ), and we define on W 1,2 0 (Ω, R m ) the family of functionals

F ε (u) = 1 ε Ω\Σε f (∇u) dx + Σε g(∇u) dx - 1 √ ε F ε , u
where f, g : R N ×m → R are two positively 2-homogeneous and quasiconvex functions satisfying the standard growth conditions: there exist two constants 0 < α ≤ β such that

α|ζ| 2 ≤ f (ζ) ≤ β(1 + |ζ| 2 ) ∀ζ ∈ R N ×m , ( 2.1)
same for g. We consider the functional

G ε defined in W 1,2 0 (Ω, R m ) by G ε (v) = F ε ( √ εv) = Ω\Σε f (∇v) dx + ε Σε g(∇v) dx -F ε , v
and the problem vε ∈ argmin v∈W 1,2 0 (Ω,R m ) G ε . Note that, by using the direct methods of the Calculus of Variations, one can easily establish that argmin v∈W 1,2 0 (Ω,R m ) G ε = ∅. We could also treat the problem with various other boundary conditions. Throughout this paper C will denote various constants independent of ε and we do not relabel the subsequences considered.

Lemma 2.1. Let (v ε ) ε>0 be a sequence in W 1,2 0 (Ω, R m ) satisfying sup ε>0 G ε (v ε ) < ∞. Then sup ε>0 ε Σε |∇v ε | 2 dx + Ω\Σε |∇v ε | 2 dx < +∞. (2.2) Proof. Estimate (2.
2) is a straightforward consequence of estimates (a), (b) and (c) below: there exists a non-negative constant C such that (a)

Σε ε|∇v ε | 2 dx ≤ C 1 + Ω |∇v ε | dx ; (b) Ω\Σε |∇v ε | 2 dx ≤ C 1 + Ω |∇v ε | dx ; (c) sup ε>0 Ω |∇v ε | dx < +∞.
Proof of (a). Since sup ε>0 G ε (v ε ) < +∞, using (2.1), and Poincaré's inequality, we have

α Σε ε|∇v ε | 2 dx ≤ Σε εg(∇v ε ) dx ≤ C + F ε v ε W 1,1 0 (Ω,R m ) ≤ C 1 + Ω |∇v ε | dx . Proof of (b). Since α Ω\Σε |∇v ε | 2 dx ≤ Ω\Σε f (∇v ε ) dx, reproducing the proof of (a), one has Ω\Σε |∇v ε | 2 dx ≤ C 1 + Ω |∇v ε | dx .
Proof of (c). Using the Cauchy-Schwartz inequality and (a), one can show that

Σε |∇v ε | dx ≤ C 1 + Ω |∇v ε | dx 1 2
.

Using the Cauchy-Schwartz inequality and (b), one can show that

Ω\Σε |∇v ε | dx ≤ C 1 + Ω |∇v ε | dx 1 2
.

From the previous estimates one has We will consider this condition in the definition of gradient Young-concentration measures. Let us introduce the space

Ω |∇v ε | dx = Σε |∇v ε | dx + Ω\Σε |∇v ε | dx ≤ C 1 + Ω |∇v ε | dx 1 2 , thus sup ε>0 Ω |∇v ε | dx < +∞. Obviously vε ∈ argmin v∈W 1,2 0 (Ω,R m ) G ε (v) satisfies sup ε>0 G ε (v ε ) < +∞;
W 1,2 ∂Ω (Ω\Σ, R m ) := v ∈ W 1,2 (Ω + , R m ) ∩ W 1,2 (Ω -, R m ) : v = 0 on ∂Ω in the sense of traces .
Then we have:

Lemma 2.2. Let (v ε ) ε>0 be a sequence in W 1,2 0 (Ω, R m ) such that sup ε>0 ε Σε ∂v ε ∂ν 2 dx + Ω\Σε |∇v ε | 2 dx < +∞. (2.3)
Then there exist a not relabeled subsequence and

v ∈ W 1,2 ∂Ω (Ω\Σ, R m ) such that v ε → v in L 2 (Ω, R m ). Proof. For every function w ∈ W 1,2 0 (Ω, R m ) we define its ε-translate T ε w by T ε w(x, x N ) = w(x, x N + ε/2), if x ∈ Ω + , w(x, x N -ε/2), if x ∈ Ω -. First step. We claim that there exist z ∈ W 1,2 ∂Ω (Ω \ Σ, R m ) and a subsequence v ε such that T ε v ε z in W 1,2
∂Ω (Ω\Σ, R m ) and strongly in L 2 (Ω, R m ). Indeed because of the boundary condition, by extending all the considered functions by zero outside of Ω, one may assume that Ω + and Ω -are cubes; clearly

∇T ε v ε = T ε ∇v ε so that sup ε Ω\Σ |∇T ε v ε | 2 dx = sup ε Ω\Σε |∇v ε | 2 dx < +∞. Poincaré's inequality then yields T ε v ε W 1,2
∂Ω (Ω\Σ,R m ) ≤ C and the claim follows immediately. We denote by z + and z -the traces of z considered as a Sobolev function on Ω + and Ω -respectively. Second step. We claim that there exists v ∈ L 2 (Ω, R m ) such that we can extract from the previous subsequence

(v ε ) ε>0 a subsequence which weakly converges to v in L 2 (Ω, R m ). Indeed Ω v 2 ε dx = Ω\Σε v 2 ε dx + Σε v 2 ε dx = Ω + ∪Ω - |T ε v ε | 2 dx + Σε v 2 ε dx. (2.4)
We are going to show that Σε v 2 ε dx → 0 as ε → 0. An integration with respect to x N gives

v ε (x, x N ) = v ε (x, ε/2) + xN ε/2 ∂v ε ∂ν (x, s)ds. It is not difficult to show, setting Σ + ε = Σ ε ∩ Ω + , that this implies Σ + ε |v ε | 2 ≤ Cε S+ε/2ν |v ε | 2 dx + ε Σ + ε ∂v ε ∂ν 2 ds .
The same calculation on

Σ - ε = Σ ε ∩ Ω -gives Σ - ε |v ε | 2 ≤ Cε S-ε/2ν |v ε | 2 dx + ε Σ - ε ∂v ε ∂ν 2 ds .
Summing up, we obtain

Σε |v ε | 2 dx ≤ Cε S+ε/2ν |v ε | 2 dx + S-ε/2ν |v ε | 2 dx + ε Σε ∂v ε ∂ν 2 dx .
By using (2.3) and the fact that

lim ε→0 S+ε/2ν |v ε | 2 dx + S-ε/2ν |v ε | 2 dx = S |z + | 2 dx + S |z -| 2 dx, we have lim ε→0 Σε |v ε | 2 dx = 0. (2.5)
Estimate (2.5) and the fact that

T ε v ε converges to z in L 2 (Ω, R m ) imply lim ε→0 Ω |v ε | 2 dx = Ω |z| 2 dx (2.6)
from (2.4). In particular we deduce that v ε is bounded in L 2 (Ω, R) and the conclusion follows immediately. Last step. To conclude, we establish that v = z. Indeed, for every

ϕ ∈ C ∞ c (Ω, R m ) we have Ω v • ϕ dx = lim ε→0 Ω v ε • ϕ dx = lim ε→0 Ω T ε v ε • T ε ϕ dx = Ω z • ϕ dx. This completes the proof because v ε v in L 2 (Ω, R m ) and, from (2.6), v ε L 2 (Ω,R) → v L 2 (Ω,R) .
We denote by S m-1 the unit sphere of R m and by M + ( Ω × S m-1 ) the set of non negative bounded Borel measures on Ω × S m-1 . For every measure μ in M + ( Ω × S m-1 ), μ = μ x ⊗ π denotes its slicing decomposition. We recall that μ x is a probability measure on S m-1 and π is the projection measure of μ on Ω.

Recall that the 2-homogeneous extension φ :

R m → R of a continuous function ϕ on S m-1 is defined for all ζ ∈ R m by φ(ζ) = |ζ| 2 ϕ( ζ |ζ| ), if ζ = 0, 0, otherwise.
It is well known (see [START_REF] Fonseca | Analysis of concentration and oscillation effects generated by gradients[END_REF], p. 741) that the 2-homogeneous extension of a Lipschitz function ϕ in S m-1 fulfills the following locally Lipschitz property: there exists c = c(ϕ) such that

∀ζ, ζ ∈ R m , | φ(ζ) -φ(ζ )| ≤ c|ζ -ζ | (|ζ| + |ζ |) . (2.7)
To shorten notation we will not distinguish ϕ from its 2-homogeneous extension φ.

Definition 2.3. We say that a pair (v, μ) belongs to the set

E ⊂ L 2 (Ω, R m ) × M + ( Ω × S m-1 ) of elementary gradient Young-concentration measures if and only if v ∈ W 1,2 0 (Ω, R m ) and μ = δ ∂v ∂ν /| ∂v ∂ν | (x) ⊗ | ∂v ∂ν | 2 dx.
We introduce the convergence of a sequence

((v ε , μ ε )) ε>0 of E to a pair (v, μ) of L 2 (Ω, R m ) × M + ( Ω × S m-1
) in the sense of concentration measures as follows:

(v ε , μ ε ) (v, μ) ⇐⇒ v ε → v strongly in L 2 (Ω, R m ) ε½ Bε μ ε * μ in M + ( Ω × S m-1
(v, μ) ∈ YC ⇐⇒ ∃ v ε ∈ W 1,2 0 (Ω, R m ) s.t. ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ v ε → v strongly in L 2 (Ω, R m ), sup ε>0 ε Σε ∂v ε ∂ν 2 dx + Ω\Σε |∇v ε | 2 dx < +∞, δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ ε½ Bε | ∂vε ∂ν | 2 dx * μ (2.8)
when ε → 0. We say that the sequence (v ε ) ε>0 generates the gradient Young-concentration measure (v, μ) or, in short, that the sequence (v ε ) ε>0 generates the Young-concentration measure μ. Recall that the weak convergence * above is defined by

Bε εθ(x)ϕ ∂v ε ∂ν dx → Ω S m-1 θ(x)ϕ(ζ) dμ
for all θ ∈ C( Ω) and all ϕ ∈ C(S m-1 ). The set YC abs is the subset of the elements (v, μ) of YC such that the projection measure π of μ on Ω is absolutely continuous with respect to the measure

H N -1 S. Remark 2.5. Let (v ε ) ε>0 be a sequence of W 1,2 0 (Ω, R m ) which satisfies (2.3). Clearly δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ε½ Bε | ∂vε ∂ν | 2 dx is bounded in M + ( Ω × S m-1
). On the other hand, from Lemma 2.2, one can extract a subsequence of (

v ε ) ε>0 which converges in L 2 (Ω, R m ) to some v ∈ W 1,2 ∂Ω (Ω \ Σ, R m ). Then one can extract a subsequence such that (v ε ) ε>0 generates some (v, μ) ∈ YC, that is (v ε , δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ ε½ Bε | ∂vε ∂ν | 2 dx) (v, μ) ∈ YC. Note that, according to Lemma 2.1, the sequence (v ε ) ε>0 of solutions of Dirichlet problems vε ∈ argmin v∈W 1,2 0 (Ω,R m ) G ε satisfies (2.
3), then generates a gradient Young-concentration measure (v, μ).

Characterization of the set of gradient Young-concentration measures

This section is devoted to the proof of the following characterization of YC:

Theorem 3.1 (characterization). A pair (v, μ = μ x ⊗ π) belongs to YC if and only if v ∈ W 1,2 ∂Ω (Ω \ Σ, R m ), π is concentrated on S and, for every ϕ ∈ C(S m-1 ) such that ϕ * * > -∞, dπ dH N -1 S (x) S m-1 ϕ(ζ) dμ x ≥ ϕ * * ([v](x)) for H N -1 a.e. x ∈ S S m-1 ϕ(ζ) dμ x ≥ 0 for π s a.e. x ∈ S (3.1)
where π = dπ dH N -1 S H N -1 S +π s is the Radon-Nikodym decomposition of π with respect to the measure H N -1 S. By analogy with the gradient Young measures (see [START_REF] Kinderlehrer | Characterization of Young measures generated by gradients[END_REF]), the Sobolev function v will be refered to as the underlying deformation of the measure μ. Note that for each

v ∈ W 1,2 ∂Ω (Ω \ Σ, R m ), the pair (v, δ [v] |[v]| (x) ⊗ |[v](x)| 2 H N -1 S
) belongs to YC (more precisely to YC abs ) and v is its underlying deformation. We call these pairs elementary limit gradient Young-concentration measures.

Gradient Young-concentration measures which are not elementary limit gradient Young-concentration measures and which are generated by a sequence of solutions of Dirichlet problems of the type (1.4) exist in abundance, as seen in the next example. Consider the measure μ = μ x ⊗ μx H N -1 S. According to Jensen's inequality, clearly the pair (v, μ) fulfills all the conditions of Theorem 3.1, but it is a non elementary limit concentration measure when φ ≡ 0 (the elementary limit concentration measures correspond to the case when φ ≡ 0). In the scalar case m = 1 where S m-1 = {-1, 1} and μ x = a(x)δ 1 + b(x)δ -1 , we can express a and b completely thanks to Theorem 3.1. Indeed ϕ ∈ C(S m-1 ) fulfills the condition ϕ * * > -∞, if and only if its extension is of the form

Example 3.2. Fix an arbitrary open interval

I in R, a function φ : I → R m in W 1,2 0 (I, R m ) and v ∈ W 1,2 ∂Ω (Ω\ Σ, R m ). For H N -1 almost every x ∈ Σ,
ϕ(ζ) = cζ 2 , if ζ ≥ 0 dζ 2 , if ζ ≤ 0
where c and d are two non-negative real numbers (note that in this case ϕ * * = ϕ). With these considerations taking successively c > 0, d = 0 and c = 0, d > 0, we easily deduce

a(x) = [[v](x)>-dφ dy ] [v](x) + dφ dy (y) 2 dy I [v](x) + dφ dy (y) 2 dy , b(x) = [[v](x)<-dφ dy ] [v](x) + dφ dy (y) 2 dy I [v](x) + dφ dy (y) 2 dy • Let us now exhibit a sequence (v ε ) ε>0 generating (v, μ). To this end we define R ε : W 1,2 (Ω \ Σ, R m ) → W 1,2 (Ω, R m ) by R ε v(x, x N ) = xN ε [v(x, ε/2) -v(x, -ε/2)] + 1 2 [v(x, ε/2) + v(x, -ε/2)] if x ∈ Σ ε v if x ∈ Ω \ Σ ε , ( 3.2)
where v ε (x, ε/2) and v ε (x, -ε/2) should be taken within the meaning of traces on Σ + ε 2 e N and Σ -ε 2 e N respectively. Take I = (- 1 2 , 1 2 ) and set

v ε (x) := R ε v(x)+φ( xN ε ), B = S×I. For all θ ∈ C( Ω) and all ϕ ∈ C(S m-1 )
we have

ε Bε θ(x)ϕ ∂v ε ∂ν dx = ε Bε θ(x)ϕ 1 ε v(x, ε/2) -v(x, -ε/2) + dφ dν x N ε dx = 1 ε Bε θ(x)ϕ v(x, ε/2) -v(x, -ε/2) + dφ dν x N ε dx = B θ(x, εx N )ϕ v(x, ε/2) -v(x, -ε/2) + dφ dν (x N ) dx which tends to S θ(x, 0) I ϕ [v](x) + dφ dy (y) dy dx = μx ⊗ H N -1 S, θ ⊗ ϕ . Since moreover clearly v ε → v in L 2 (Ω, R m ), the sequence (v ε ) ε>0 generates (v, μ).
We claim that u ε = √ εv ε , where v ε is the function constructed above, is the solution to a Dirichlet problem with large source. In order to shorten the calculation we prove the claim in the scalar case (m = 1) and we begin by the one dimensional case (N = 1).

Take

φ ∈ C 2 0 (I), v ∈ C 2 ((-1, 0) ∪ (0, 1)) with v(-1) = v(1) = 0 and denote by [v] ε the approximate jump v(ε/2) -v(-ε/2).
Then by an elementary computation, it is readily seen that u ε is solution to

(σ ε u ε ) = 1 √ ε F ε in (-1, 1) u ε (-1) = u ε (1) = 0, where F ε is the measure v -1, - ε 2 ∪ ε 2 , 1 + 1 ε φ t ε - ε 2 , ε 2 + [v] ε -v - ε 2 δ -ε 2 + v - ε 2 -[v] ε δ ε 2 .
Note that, choosing v such that v = 0, i.e. v of the form v(t) = a -(t + 1) on (-1, 0) and v(t) = a + (t -1) on (0, 1), the measure F ε is concentrated on (-ε 2 , ε 2 ). We treat now the case N = 2 (the calculation in the general case is similar). We set Ω = (-1, 1) 2 and Σ = (-1, 1) × {0}. Take φ ∈ C 2 0 (I) and v ∈ C 2 (Ω \ Σ) satisfying v = 0 on ∂Ω. One can easily show that u ε is the solution of the Dirichlet problem div(σ

ε ∇u ε ) = 1 √ ε F ε in Ω u ε = 0 on ∂Ω,
where σ ε := 1 ε ½ Ω\Σε + ½ Σε , and F ε is given by

F ε = Δu ε (Ω \ Σ ε ) + [v] ε (x 1 ) - ∂v ∂x 2 x 1 , - ε 2 H 1 S - ε 2 e 2 + ∂v ∂x 2 x 1 , ε 2 -[v] ε (x 1 ) H 1 S + ε 2 e 2 + x 2 ∂ 2 v ∂ 2 x 1 x 1 , ε 2 - ∂ 2 v ∂ 2 x 1 x 1 , - ε 2 + ε 2 ∂ 2 v ∂ 2 x 1 x 1 , ε 2 + ∂ 2 v ∂ 2 x 1 x 1 , - ε 2 Σ ε + 1 ε d 2 φ d 2 x 2 x 2 ε Σ ε . The approximated jump [v] ε is given now by [v] ε (x 1 ) := v(x 1 , ε 2 ) -v(x 1 , -ε 2 ). Note that, taking v solution of the Dirichlet-Neumann problem ⎧ ⎨ ⎩ Δv = 0 in Ω + v = 0 on ∂Ω + \ Σ ∂v ∂x2 prescribed on Σ, ⎧ ⎨ ⎩ Δv = 0 in Ω - v = 0 on ∂Ω -\ Σ ∂v ∂x2 prescribed on Σ, the source F ε is concentrated on Σ ε .
The proof of Theorem 3.1 is divided into two propositions, the necessary condition (Prop. 3.3) and the sufficient condition (Prop. 3.5).

Proposition 3.3 (necessary condition). Assume that

(v, μ = μ x ⊗ π) belongs to YC. Then v ∈ W 1,2
∂Ω (Ω\Σ, R m ), π is concentrated on S and, for every ϕ ∈ C(S m-1 ) such that ϕ * * > -∞, (3.1) holds.

The proof of Proposition 3.3 is based on next Lemma 3.4.

Lemma 3.4. Let (v ε ) ε>0 be a sequence in W 1,2 0 (Ω, R m ) satisfying (2.3) and converging to v in L 2 (Ω, R m ). Then v ∈ W 1,2 ∂Ω (Ω \ Σ, R m )
; moreover for all continuous functions ϕ on S m-1 and all non-negative functions θ in C( S), we have

lim inf ε→0 ε Bε θ(x)ϕ ∂v ε ∂ν dx ≥ S θ(x)ϕ * * ([v]) dx. (3.3) Proof. According to Lemma 2.2, one has v ∈ W 1,2 ∂Ω (Ω \ Σ, R m ).
Consider the Moreau-Yosida proximal approximation ϕ p of the continuous function ϕ : S m-1 → R defined by

ϕ p (ζ) = inf ξ∈S m-1 ϕ(ξ) + p|ξ -ζ| 2 .
It is well known that ϕ p is a Lipschitz function and that the sequence (ϕ p ) p∈N converges increasing to ϕ (for a proof consult [START_REF] Attouch | Variational Convergence for Functions and Operators, Applicable Mathematics Series[END_REF], Thm. 2.6.4). Consequently, according to Dini's theorem (ϕ p ) p∈N converges uniformly to ϕ on S m-1 . Let η > 0 and p(η) ∈ N be such that sup

ξ∈S m-1 |ϕ(ξ) -ϕ p(η) (ξ)| < η. (3.4)
We establish the existence of a non-negative constant C independent on ε and η such that

lim inf ε→0 ε Bε θ(x)ϕ p(η) ∂v ε ∂ν dx ≥ S θ(x)ϕ * * ([v]) dx -Cη. (3.5)
Consider the function

w ε := v ε -R ε v, where R ε : W 1,2 (Ω \ Σ, R m ) → W 1,2 (Ω, R m ) is the map defined in (3.2). It is readily seen that w ε converges to 0 in L 2 (Ω, R m ), since v ε → v in L 2 (Ω, R m )
. By using the locally Lipschitz property (2.7) satisfied by the 2-homogeneous extension of ϕ p(η) (recall that ϕ p(η) is Lipschitz), we have

lim inf ε→0 ε Bε θ (x) ϕ p(η) ∂v ε ∂ν dx = lim inf ε→0 1 ε Bε θ (x) ϕ p(η) ε ∂v ε ∂ν dx = lim inf ε→0 1 ε Bε θ (x) ϕ p(η) ε ∂w ε ∂ν + v (x, ε/2) -v (x, -ε/2) dx = lim inf ε→0 1 ε Bε θ (x) ϕ p(η) [v] + ε ∂w ε ∂ν dx. (3.6)
Indeed using the Cauchy-Schwartz inequality and (2.3), it is easy to establish

lim ε→0 1 ε Bε |v (x, ε/2) -v (x, -ε/2) -[v]| |v (x, ε/2) -v (x, -ε/2) | + |[v]| + 2 ε ∂w ε ∂ν dx = 0.
Since w ε → 0 in L 2 (Ω, R m ), by using a truncation argument, one can modify w ε into a Sobolev function wε vanishing at the boundary of S ± ε 2 ν of B ε where ε := ε(1 + t(ε)) and t(ε) > 0 is suitably chosen so that lim ε→0 t(ε) = 0 and

lim inf ε→0 - Bε θ(x)ϕ p(η) [v] + ε ∂w ε ∂ν dx = lim inf ε→0 - B ε θ(x)ϕ p(η) [v] + ε ∂ wε ∂ν dx (3.7)
(see Lem. 4.5 in [START_REF] Licht | A modelling of elastic adhesive bonded joints[END_REF]). According to (3.7), (3.4) and Jensen's inequality, we have

lim inf ε→0 - Bε θ (x) ϕ p(η) [v] + ε ∂w ε ∂ν dx = lim inf ε→0 - B ε θ (x) ϕ p(η) [v] + ε ∂ wε ∂ν dx ≥ lim inf ε→0 - B ε θ (x) ϕ [v] + ε ∂ wε ∂ν dx -η θ ∞ |S| sup ε>0 1 ε B ε [v] + ε ∂ wε ∂ν 2 dx ≥ lim inf ε→0 - S×(-ε 2 , ε 2 ) θ (x) ϕ * * [v] + ε ∂ wε ∂ν dx -Cη ≥ S θ (x) ϕ * * ([v]) dx -Cη. (3.8)
Notice that in the second inequality, we have used the bound sup ε>0

1 ε Bε |[v] + ∂ wε ∂ν | 2 dx < +∞:
this is a straightforward consequence of (3.7) applied with ϕ = |.| 2 and (2.3). We conclude the proof of (3.5) by combining (3.6) and (3.8). Estimate (3.3) follows letting η → 0 and noticing that ϕ ≥ ϕ p(η) .

Proof of Proposition 3.3. Let (v, μ) in YC. Then, by definition of YC, there exists a sequence

(v ε ) ε>0 in W 1,2 0 (Ω, R m ) satisfying (2.3) such that v ε → v strongly in L 2 (Ω, R m ), μ ε := δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ ε½ Bε | ∂vε ∂ν | 2 dx * μ when ε → 0. According to Lemma 2.2, v belongs to W 1,2 ∂Ω (Ω \ Σ, R m ).
The fact that π is concentrated on S is easy to see. We are going to prove (3.1). Let θ be a non-negative function in C( S) and ϕ in C(S m-1 ) such that where μ = μ x ⊗ π is the slicing decomposition of μ with respect to its projection π on Ω. Combining (3.9) and (3.10), it follows that

ϕ * * > -∞. Since v ε → v in L 2 (Ω, R m ),
dπ dH N -1 (x) S m-1 ϕ(ζ) dμ x ≥ ϕ * * ([u](x)) for H N -1 S a.e. x, S m-1 ϕ(ζ) dμ x ≥ 0 for π s a.e. x ∈ S. Proposition 3.5 (sufficient conditions). Assume that (v, μ = μ x ⊗ π) belongs to W 1,2 ∂Ω (Ω \ Σ, R m ) × M + ( Ω × S m-1
), satisfies (3.1), and that π is concentrated on S. Then (v, μ) belongs to YC.

Proof. We divide the proof into three steps. In Step 1, using the Hahn-Banach separation theorem, we approximate the homogeneous components μ of YC (i.e. μ x does not depend of x) by the same type of measures as in Example 3.2. In Step 2, we construct a sequence of Sobolev functions generating these measures and conclude by a standard diagonalization argument. In Step 3, we build a sequence of Sobolev functions generating the components μ of YC: according to a standard covering argument, we localize the construction above and stick together the various generating functions obtained in Step 2. We show that this sequence generates the pair (v, μ). In order to make easier the reading of the proof, we begin by treating the case N = m = 1.

Proof in the case

N = m = 1. Let (v, μ) in W 1,2 ∂Ω ((-1/2, 0) ∪ (0, 1/2)) ⊗ M + ([-1/2, 1/2] × S 0
), satisfying (3.1) with π concentrated in {0}. The measure μ = μ 0 ⊗π(0)δ 0 can be written as π(0)μ 0 ⊗δ 0 , where π(0)μ 0 ∈ M + (S 0 ) satisfies

S 0 ϕ(ζ) d(π(0)μ 0 ) ≥ ϕ * * ([v](0)) (3.11)
for all ϕ ∈ C(S 0 ) such that ϕ * * > -∞. Note that such functions ϕ, (actually their extensions) are of the form

ϕ(ζ) = cζ 2 , if ζ ≤ 0 dζ 2 , if ζ ≥ 0
where c and d are two nonnegative real numbers. Note also that since μ is homogeneous, Step 3 described above is not necessary.

Step 1. Let us consider the following subset of M + (S 0 ):

H := λ ∈ M + (S 0 ) : ∀ϕ ∈ C(S 0 ), s.t. ϕ * * > -∞, S 0 ϕ dλ ≥ ϕ * * ([v](0)) .
H is non empty, because it contains π(0)μ(0) as (3.11) shows. It is easily seen that H is convex and closed with respect to the weak convergence in M + (S 0 ). For all w ∈ W 1,2 0 ((-1/2, 1/2)), consider the measure μ w in M + (S 0 ) which acts on all ϕ ∈ C(S 0 ) as follows:

μ w , ϕ := (-1/2,1/2) ϕ([v](0) + ẇ) dx.
According to Jensen's inequality we have

μ w , ϕ ≥ (-1/2,1/2) ϕ * * ([v](0) + ẇ) dx ≥ ϕ * * ([v](0))
so that μ w belongs to H. Let us introduce the subset C of H made up of such measures μ w , i.e.,

C := μ w : w ∈ W 1,2 0 ((-1/2, 1/2)) .
In this step we prove that C is a dense convex subset of H for the weak convergence of measures. Let us first prove the convexity of C. Let a, b in (0, 1) be such that a + b = 1, w 1 , w 2 in W 1,2 0 ((-1/2, 1/2)). Then

aμ w1 + bμ w2 , ϕ = a 1/2 -1/2 ϕ([v](0) + w 1 ) dx + b 1/2 -1/2 ϕ([v](0) + w 2 ) dx.
The change of scale x = t a -1 2 + a 2 in the first integral and x = t 1-a -a 2(1-a) in the second one give

aμ w1 + bμ w2 , ϕ = μ w , ϕ
where w is the function of W 1,2 0 ((-1/2, 1/2)) defined by

w(t) = ⎧ ⎨ ⎩ aw 1 t-a 2 + 1 2 a , if t ∈ -1 2 , -1 2 + a , bw 2 t+ b 2 -1 2 b , if t ∈ -1 2 + a, 1 2 .
It remains to establish that C is a dense subset of H. Indeed otherwise there exists λ 0 in H which does not belong to C. According to the Hahn-Banach theorem, there exist ϕ 0 ∈ C(S 0 ) and r ∈ R such that for all μ ∈ C, μ, ϕ 0 > r > λ 0 , ϕ 0 . In particular for all w ∈ W 1,2 0 ((-1/2, 1/2)) we have μ w , ϕ 0 > r > λ 0 , ϕ 0 ; from the characterization of the convexification ϕ * * of ϕ, this implies

ϕ * * 0 ([v](0)) = inf w∈W 1,2 0 ((-1/2,1/2))
μ w , ϕ 0 ≥ r > λ 0 , ϕ 0 .

(3.12)

The first inequality forces ϕ * * 0 to be finite; since λ 0 ∈ H one has λ 0 , ϕ 0 ≥ ϕ * * 0 ([v](0)). Therefore (3.12) involves a contradiction.

Step 2. Since π(0)μ 0 belongs to H and, from Step 1, C is dense in H, there exists a sequence (

w n ) n∈N in W 1,2 0 ((-1/2, 1/2)) such that μ wn * μ = π(0)μ 0 in M + (S 0 ) when n → +∞. Consequently μ n := μ wn ⊗ δ 0 * μ = π(0)μ 0 ⊗ δ 0 (3.13) for the weak convergence of σ(M + ([-1/2, 1/2] × S 0 )). Taking θ ≡ 1 and ϕ ≡ 1 (i.e. φ = |.| 2 )
we also obtain

μ n → μ = π(0);
this implies that for n large enough, say n ≥ n 0 , μ n belongs to the ball B(0, π(0

) + 1) of M + ([-1/2, 1/2] × S 0 ).
We take n ≥ n 0 and we are going to approximate the measure μ n by a measure of the form

δ vn,ε/| vn,ε| (x) ⊗ ε½ Bε | vn,ε | 2 dx. Consider the W 1,2 0 ((-1/2, 1/2)) function v n,ε defined by v n,ε (x) := R ε v + w n (x/ε), where R ε v(x) = x ε v( ε 2 ) -v(-ε 2 ) + 1 2 v( ε 2 ) + v(-ε 2 ) , if x ∈ (-ε 2 , ε 2 ), v, otherwise,
and set μ n,ε := δ vn,ε/| vn,ε| (x) ⊗ ε½ Bε | vn,ε | 2 dx. A straightforward calculation and a change of scale give, for all θ ∈ C([-1/2, 1/2]) and all ϕ ∈ C(S 0 ),

μ n,ε , θ ⊗ ϕ = ε ε/2 -ε/2 θ (x) ϕ 1 ε v ε 2 -v -ε 2 + ẇn x ε dx = - (-ε/2,ε/2) θ (x) ϕ v ε 2 -v -ε 2 + ẇn x ε dx = 1/2 -1/2 θ (εy) ϕ v ε 2 -v -ε 2 + ẇn (y) dy → θ (0) 1/2 -1/2 ϕ ([v] (0) + ẇn (y)) dy = μ wn ⊗ δ 0 , θ ⊗ ϕ when ε → 0, that is μ n,ε * μ wn ⊗ δ 0 = μ n . (3.14)
We are going to show, using a standard diagonalization argument, that a sequence constructed from v n,ε generates (v, μ). By a straightforward calculation, we get, taking θ ≡ 1 and ϕ ≡ 1 as test functions

μ n,ε = 1/2 -1/2 v ε 2 -v -ε 2 + ẇn (y) 2 dy ≤ 2 1/2 -1/2 v ε 2 -v -ε 2 -[v] (0) 2 dy + 2 μ n ≤ 2 1/2 -1/2 v ε 2 -v -ε 2 -[v] (0) 2 dy + 2 (1 + π (0)) .
This implies, for ε small enough, say ε < ε 0 where ε 0 does not depend on n, that μ n,ε belongs to the closed ball B(0, 2(π(0

) + 2) of M + ([-1/2, 1/2] × S 0 )). Since the closed balls of M + ([-1/2, 1/2] × S 0 ) are metrizable, combining (3.13)
, (3.14) and using a standard diagonalization argument, there exists a map ε → n(ε) such that

μ ε := δ vn(ε),ε | vn(ε),ε | (x) ⊗ ε½ Bε | vn(ε),ε | 2 dx * μ (3.15) when ε → 0. Set v ε := v n(ε),ε . Condition (2.
3) follows straightforwardly from (3.15) (take θ ≡ 1 and ϕ ≡ 1 as test functions). To prove that v ε generates (v, μ), it remains to establish that

v ε → v in L 2 ((-1, 1)). Noticing that v ε = v on (-1, 1) \ (-ε/2, ε/2
), and by using Poincaré's inequality and condition (2.3) satisfied by v ε , we have

(-1,1) |v ε -v| 2 dx = (-ε/2,ε/2) |v ε -v| 2 dx ≤ ε 2 (-ε/2,ε/2) | vε -v| 2 dx ≤ Cε
where C is a non negative constant independent on ε.

Proof of the general case.

Let (v, μ) in W 1,2 ∂Ω (Ω \ Σ, R m ) ⊗ M + (Ω × S m-1
) satisfying (3.1) with π concentrated in S. We want to prove that (v, μ) belongs to YC. The proof is very close to the previous one but with an additional step.

Step 1. Let a ∈ R m be fixed, and consider the following subset of M + (S m-1 ):

H(a) := λ ∈ M(S m-1 ) : ∀ϕ ∈ C(S m-1 ), s.t. ϕ * * > -∞,
C(a) := μ w : w ∈ W 1,2 0 (I, R m ) .
Using the same arguments of the first step in the one dimensional case (N = 1), we obtain that C(a) is a dense convex subset of H(a) for the σ(M(S m-1 ), C(S m-1 )) topology.

Step 2. Let x 0 be a fixed element of S and Q(x 0 ) a fixed open cube of R N -1 centered at x 0 . Given m ∈ H(a), according to the first step, there exists a sequence (w n ) n∈N of functions in W 1,2 0 (I, R m ) such that

μ wn * m in M + (S m-1
), when n → +∞. Consequently

μ n := μ wn ⊗ H N -1 Q(x 0 ) ∩ S | Q(x 0 )| * m ⊗ H N -1 Q(x 0 ) ∩ S | Q(x 0 )| (3.17) in M( Ω × S m-1
). For each w n we define the function ξ n,ε on B ε depending only of the variable x N by

ξ n,ε (x) := | Q(x 0 )| -1 2 x N ε a + w n x N ε • (3.18) A straightforward calculation gives lim ε→0 ε Q(x0)×( -ε 2 , ε 2 )∩ Ω θ(x)ϕ ∂ξ n,ε ∂ν dx = - Q(x0) θ(x, 0)dH N -1 S I ϕ a + dw n dν dx
for all ϕ ∈ C(S m-1 ) and all θ ∈ C( Ω), so that

μ n,ε := ε½ Q(x0)×( -ε 2 , ε 2 ) δ ∂ξn,ε ∂ν / ∂ξn,ε ∂ν (x) ⊗ | ∂ξ n,ε ∂ν | 2 dx * μ wn ⊗ H N -1 Q(x 0 ) ∩ S | Q(x 0 )| (3.19) in M( Ω × S m-1
) when ε → 0. Combining (3.17), (3.19) and using a diagonalization argument like in Step 2 of the 1-dimensional case N = 1, there exists a map n → n(ε) and ξ ε such that

ξ ε := ξ n(ε),ε = | Q(x 0 )| -1 2 x N ε a + w n(ε) x N ε , w n(ε) ∈ C 1 0 (I, R m ), ε½ Q(x0)×( -ε 2 , ε 2 ) δ ∂ξε ∂ν /| ∂ξε ∂ν |(x) ⊗ ∂ξ ε ∂ν 2 dx * m ⊗ H N -1 Q(x 0 ) ∩ S | Q(x 0 )| (3.20)
in M( Ω × S m-1 ).

Step 3. Let (v, μ) in YC: we are going to construct a sequence (v ε ) ε>0 which generates (v, μ). The sequence (v ε ) ε>0 is composed by functions in W 1,2 0 (Ω, R m ) whose restriction on Ω \ Σ ε is equal to v, it converges to v in L 2 (Ω, R m ), it satisfies (2.3) and

δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ ε½ Bε | ∂v ε ∂ν | 2 dx * μ (3.21) in M( Ω × S m-1 ).
In what follows, we continue to write the measure π on R N defined for all Borel set E of R N by π(E) := π( S ∩ E) as π. According to the Vitali covering theorem (see [START_REF] Federer | Geometric Measure Theory[END_REF], Cor. 2.8.15) there exists a finite family ( Qi,k ) i∈I k of disjoint closed squares in R N -1 , centered at x i,k ∈ S, with diameter less than 1/k, k ∈ N * and satisfying

π S \ i∈I k Qi,k < 1 k • (3.22)
One may assume that Qi,k ⊂ Σ. Define the measure μ i,k of M(S m-1 ) by

μ i,k := Qi,k μ x dπ.
From (3.1) and Jensen's inequality, for all ϕ ∈ C(S m-1 ) such that ϕ * * > -∞ we have

μ i,k , ϕ = Qi,k S m-1 ϕ(ζ) dμ x dπ ≥ Qi,k ϕ * * ([v](x)) dH N -1 S ≥ ϕ * * | Qi,k | 1 2 - Qi,k [v](x) dH N -1 S . (3.23) Let us set a i,k = | Qi,k | 1 2 - Qi,k [v] dH N -1 S. ( 3
i,k,ε ) ε>0 in W 1,2 (B ε , R m ), of the form ξ i,k,ε (x) = x N ε - Qi,k [v] dH N -1 S + ξi,k,ε (x N ),
with ξi,k,ε in W 1,2 0 (I, R m ) and with the property that,

μ i,k,ε := ε½ Qi,k ×( -ε 2 , ε 2 ) δ ∂ξ i,k,ε ∂ν / ∂ξ i,k,ε ∂ν (x) ⊗ ∂ξ i,k,ε ∂ν 2 dx * μ i,k ⊗ H N -1 Qi,k ∩ S | Qi,k | (3.25) in M( Ω × S m-1
) when ε → 0, and μ i,k,ε ≤ 2π( Qi,k ). For all θ ∈ C( Ω) and all ϕ ∈ C(S m-1 ), (3.25) yields lim

ε→0 i∈I k ε Qi,k ×(-ε 2 , ε 2 )∩ Ω θ(x)ϕ ∂ξ i,k,ε ∂ν dx = i∈I k - Qi,k θ(x) dH N -1 S S m-1 ϕ(ζ) dμ i,k = i∈I k - Qi,k θ(x) dH N -1 S Qi,k S m-1 ϕ(ζ) dμ x dπ.
When θ is a Lipschitz-continuous function, one easily deduces from (3.22) that lim

k→+∞ lim ε→0 i∈I k ε Qi,k ×(-ε 2 , ε 2 )∩ Ω θ(x)ϕ ∂ξ i,k,ε ∂ν dx = S S m-1 θϕ dμ. (3.26)
In the general case, when θ ∈ C( Ω), the same conclusion holds by an approximation argument.

Set ξ k,ε (x) := i∈I k ξ i,k,ε (x N ) ½ Qi,k (x). In order that the value of ξ k,ε agrees with that of v on Ω \ Σ ε , we modify ξ i,k,ε into the function v i,k,ε given by

v i,k,ε (x) := R ε v(x) + ξi,k,ε (x N ) ½ Qi,k (x)
where

R ε : W 1,2 (Ω \ Σ, R m ) → W 1,2 (Ω, R m ) is the operator defined in (3.2).
We claim that (3.26) holds when we replace ξ i,k,ε by v i,k,ε . Indeed one may assume ϕ ∈ Lip(S m-1 ) and, from the Lipschitz property (2.7), it is easily seen that we are reduced to establish

lim k→+∞ lim ε→0 i∈I k ε Qi,k ×(-ε 2 , ε 2 )∩ Ω 1 ε - Qi,k [v]dH N -1 S - ∂R ε v ∂ν 2 dx = 0 :
this can be straightforward checked. Thus (3.26) becomes Note that v k,δ,ε belongs to W 1,2 0 (Ω, R m ). Now, using a standard diagonalization argument (all the considered measures are bounded by 2π( S) in M( Ω × S m-1 )), we infer

lim k→+∞ lim ε→0 i∈I k ε Qi,k ×(-ε 2 , ε 2 )∩ Ω θ(x)ϕ ∂v i,k,ε ∂ν dx = S S m-1 θϕ dμ. (3.27) It is worth noticing that v k,ε := i∈I k v i,k,ε ½ Qi,
δ ∂vε ∂ν / ∂vε ∂ν (x) ⊗ ε½ Bε | ∂v ε ∂ν | 2 dx * μ where v ε := v k(ε),δ(ε),ε for some map ε → (k(ε), δ(ε)
|v -v ε | 2 dx = Σε |v -v ε | 2 dx ≤ ε 2 Σε ∂(v -v ε ) ∂ν 2 dx ≤ Cε
where we have used Poincaré's inequality, and (2.3) in the two last inequalities.

(x)δ -1 ) ⊗ π) belongs to YC if and only if v ∈ W 1,2 ∂Ω (Ω \ Σ), π is concentrated on S and dπ dH N -1 S (x) a(x)c + b(x)d ≥ ϕ([v](x)) for H N -1 S a.e.
x and for all (c, d

) ∈ R + × R + where ϕ(ζ) = cζ 2 if ζ ≥ 0, dζ 2 if ζ ≤ 0.
Consequently the following estimates hold:

a(x) ≥ |[v](x)| 2 dπ dH N -1 S (x) for H N -1 S a.e. x such that [v](x) > 0 b(x) ≥ |[v](x)| 2 dπ dH N -1 S (x)
for H N -1 S a.e. x such that [v](x) < 0.

(3.28)

Proof. Since m = 1 we have S m-1 = {-1, 1}, μ x = a(x)δ 1 + b(x)δ -1 with 0 ≤ a(x) ≤ 1, 0 ≤ b(x) ≤ 1,
σ ε (x) = 1 ε if x ∈ (-1, 1) \ (-ε 2 , ε 2 ) 1 if x ∈ -ε 2 , ε 2 .
Clearly ū ε is of the form

ū ε (x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ εc ε , if x ∈ (-1, -ε 2 ) c ε + s k √ ε , if x ∈ (t ε k , t ε k+1 ), k = 0, . . . , m -1 ε c ε + sm √ ε , if x ∈ ( ε 2 , 1),
where s k := k i=0 a i and c ε is a constant which can be computed from the boundary conditions.

Let us show that ū ε has a concentration phenomenon. To this end we set vε = ūε √ ε and compute the weak limit of the measure πε := ½ (-ε 2 , ε

2 ) ε|v ε | 2 dx in M([-1, 1]). Let θ ∈ C([-1, 1]); we have

1 -1 θ(x)½ (-ε 2 , ε 2 ) ε|v ε | 2 dx = m-1 k=0 ε c ε √ ε + s k ε 2 t ε k+1 t ε k θ(x) dx = m-1 k=0 |c ε √ ε + s k | 2 t ε k+1 -t ε k ε - t ε k+1 t ε k θ(x) dx.
Taking into account that vε is a solution of min 1 2 (-1,1)\(-

ε 2 , ε 2 ) |v | 2 dx + ε 2 (-ε 2 , ε 2 ) |v | 2 dx + m k=0 a k v(t ε k ) : v ∈ W 1

  define now the probability measure μ x on S m-1 by μ x = μx / μx , where for all ϕ ∈ C(S m-1 ) μx , ϕ := -I ϕ [v](x) + dφ dy (y) dy.

S m- 1 ϕ

 1 dλ ≥ ϕ * * (a) . (3.16) For all w ∈ W 1,2 0 (I, R m ) where I = (-1 2 , 1 2 ), consider the measure μ w in M(S m-1 ) which acts on all ϕ ∈ C(S m-1 ) as follows: μ w , ϕ := I the following subset C(a) of M(S m-1 ):

  k is not a Sobolev function. Take now a partition of unity (ϕ i,δ ) i∈I k subordined to the family ( Qi,k ) i∈I k , satisfying lim δ→0 Qi,k |ϕ δ -1| 2 dx = 0, and set v k,δ,ε := i∈I k v i,k,ε ϕ i,δ . Taking into account that ϕ δ depends only on x, it is readily seen that[START_REF] Fonseca | Analysis of concentration and oscillation effects generated by gradients[END_REF]

Corollary 3 . 6 (

 36 characterization of YC in the scalar case m = 1). Assume that m = 1. Then (v, μ = (a(x)δ 1 + b

4 . 1 )

 41 and a(x) + b(x) = 1 for H N -1 S a.e. x. Moreover ϕ ∈ C(S m-1 ) fulfils the condition ϕ * * > -∞ if and only if its extension is of the formϕ(ζ) = cζ 2 , if ζ ≥ 0 dζ 2 , if ζ ≤ 0where c and d are two non-negative real numbers. Note that in this case ϕ * * = ϕ. Then (3.1) is equivalent todπ dH N -1 S (x) a(x)c + b(x)d ≥ ϕ([v](x)) for H N -1 S a.e. x.Estimates (3.28) follow easily, choosing d = 0 or c = 0. Computations in the 1-dimensional case Let us consider the elementary Dirichlet problem described in the introduction: = u(1) = 0, where a k ∈ R * , (t ε k ) k=0,...,m is a non decreasing family of numbers in [-ε 2 , ε 2 ] with t ε 0 = -ε 2 , l for k = 0, . . . , m -1, and σ ε is given by

1 - 1 θ(x)½ (-ε 2 , ε 2 ) 1 k=0( 1 k=0(L + s k ) 2 δ 0 and ū ε presents a concentration phenomenon of intensity l m- 1 k=0⊗ ½ (-ε 2 , ε 2 ) 1 - 1 ½

 11221112211 ,2 0 ((-1, 1)) , and using point (c) of Lemma 2.1, c e √ ε is bounded and tends to some constant L. This implies that limε→0 ε|v ε | 2 dx = l m-L + s k ) 2 θ(0).Thus πε weakly converges to the measure π = l m-(L + s k ) 2 at 0.We are going to compute the weak limit μ of the measure με := δ v ε |v ε | (x) ε|v ε | 2 dx. We assume for instance that L ≥ 0. Let ϕ be any 2-homogeneous continuous function on R and θ any function in C([-1, 1]). We have for small ε ε (-ε 2 , ε 2 ) ϕ(v ε )θ(x) dx = k=0,...,m-1:s k <0

2 m- 1 k=0(L + s k ) 2 , 2 m- 1 k=0(L + s k ) 2 • ( 4 . 1 )

 21221241 ..,m-1:s k <0 (L + s k ) 2 ϕ(-1) + k=0,...,m-1:s k ≥0 (L + s k ) 2 ϕ(1) s k ) 2 θ(0), where a = k=0,...,m-1:s k ≥0 (L + s k ) b= k=0,...,m-1:s k <0 (L + s k )This proves that the measure με := δ v ε |v ε | (x) ⊗ ½ (-ε 2 , ε 2 ) ε|v ε | 2 dxweakly converges to the measure μ = (aδ 1 + bδ -1 ) ⊗ π, where π = l m-1 k=0 (L + s k ) 2 δ 0 and a and b are given by (4.1).

  ). We have thus proved(3.21). Estimate (2.3) follows straightforward from (3.21) (take θ ≡ 1 and ϕ ≡ 1 as a test function). At last we have

	Ω

Acknowledgements. The authors would like to thank the referee for helpful comments and suggestions on the paper.

was partially supported by ATER grant of Université Montpellier II.


Valerii Hadamard Sopin

Conjecture

Hadamard Conjecture Proof

Keywords:

est destinée au dépôt

Introduction

A Hadamard matrix, named after French mathematician Jacques Hadamard [START_REF] Hadamard | Résolution d'une question relative aux déterminants[END_REF], is a square matrix whose entries are either +1 or -1 and whose rows are mutually orthogonal. In combinatorial terms, it means that each pair of rows has matching entries in exactly half of their columns and mismatched entries in the remaining columns. It is a consequence of this definition that the corresponding properties hold for columns as well. A Hadamard matrix has maximal determinant among matrices with entries of absolute value less than or equal to 1 and so is an extremal solution of Hadamard's maximal determinant problem [START_REF] Hadamard | Résolution d'une question relative aux déterminants[END_REF]. The last indicates that the order of a Hadamard matrix must be 1, 2, or a multiple of 4.

The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every natural k. Many authors developed methods to construct Hadamard matrices (Sylvester's construction [START_REF] Joseph | Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers[END_REF] and Paley's work [START_REF] Edward | On orthogonal matrices[END_REF] are the most famous). There are infinitely many orders of Hadamard matrices have been constructed. However, the conjecture has been open (the smallest order, for which the existence of a Hadamard matrix is in doubt, is currently 668 = 4 • 167).

It is apparent that if the rows and columns of a Hadamard matrix are permuted, the matrix remains Hadamard. It is also true that if any row or column is multiplied by -1, the Hadamard property is retained. Thus, it is always possible to arrange to have the first row and first column of a Hadamard matrix contain only +1 entries. A Hadamard matrix in this form is said to be normalized.

If H 4k is a normalized Hadamard matrix of order 4k, then every row/column except the first has 2k minus ones and 2k plus ones. Further, k minus ones in any row/column overlap with k minus ones in each other row/column.

Hadamard matrices can be regarded as generalizations of the Walsh matrices (a non-standard branch of discrete Fourier analysis) and can almost directly be used as an error-correcting codes. Moreover, Hadamard matrices find applications in balanced repeated replication and in appraisal of the variance of a parameter estimator, see [START_REF] Horadam | Hadamard Matrices and Their Application[END_REF][5] [START_REF] Bose | A note on a result in the theory of code construction[END_REF] and references therein.

In this paper we construct a Hadamard matrix of order 4n from a Hadamard matrix of order 4nm for any natural n and m. The outcome (along with known constructions of Hadamard matrices) gives the resulting solution and the closure of the Hadamard conjecture since it is left to show that for any prime number p there exists a natural number k that a Hadamard matrix of order 4pk can be constructed using known results.

Indeed, Paley's construction [START_REF] Edward | On orthogonal matrices[END_REF] produces a Hadamard matrix of order q + 1 when q is any prime power that is congruent to 3 modulo 4 and a Hadamard matrix of order 2(q + 1) when q is a prime power that is congruent to 1 modulo 4. So, the question about divisors of q + 1 with prime q raises. But it can be reformulated as existence of a prime number of the form 4pk -1 with fixed prime p and any natural k. The last amounts to Dirichlet's theorem on primes in arithmetic progressions.

It is worthy to mention that Hadamard matrices of order 4k 4 exist for all odd k [START_REF] Muzychuk | Symmetric Bush-type Hadamard matrices of order 4m 4 exist for all odd m[END_REF].

There are at least three possible ways (the last one is the most evident). The implication 4nm ⇒ 4n guarantees that the chain survives. Notice that a Hadamard matrix is symmetric if H 4k = H t 4k and is skew if H 4k -I 4k is skew-symmetric, i.e. H 4k + H t 4k = 2I 4k . Paley's first construction gives skew Hadamard matrices and the second construction gives symmetric ones [START_REF] Edward | On orthogonal matrices[END_REF].

For more constructions of Hadamard matrices check [START_REF] Seberry | Hadamard Matrices: Constructions using Number Theory and Linear Algebra[END_REF].

Pigeonhole principle

The pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. In a more quantified version: for natural numbers k and m, if n = km + 1 objects are distributed among m sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects.

Hadamard codes

Hadamard codes are obtained from an 4n-by-4n Hadamard matrix H [START_REF] Bose | A note on a result in the theory of code construction[END_REF]. In particular, the 8n codewords of the code are the rows of H and the rows of -H. To obtain a code over the alphabet {0, 1}, the mapping

x -→ (1 -x)/2
is applied to the matrix elements.

That the minimum distance of the code is 2n follows from the defining property of Hadamard matrices, namely that their rows are mutually orthogonal. This implies that two distinct rows of a Hadamard matrix differ in exactly 2n positions, and, since negation of a row does not affect orthogonality, that any row of H differs from any row of -H in 2n positions as well, except when the rows correspond, in which case they differ in 4n positions. Thus, a Hadamard code is a [4n, 2n, 2n] not-necessarily-linear code and it will correct any error pattern of weight (n -1), see Theorem 1 from [START_REF] Bose | A note on a result in the theory of code construction[END_REF].

It is needed to use the techniques of puncturing and shortening from coding theory.

Integer lattices

Let L be an integer lattice and S a set of lattice points in L. It is said that the set S is optimal if it minimises the number of rectangular sublattices of L (including degenerate ones) which contain an even number of points in S. The resolution of the Hadamard conjecture is equivalent to the determination of |S| for an optimal set S in a (4s -1) × (4s -1) integer lattice L, see [START_REF] Mccall | The Hadamard conjecture and integer lattices[END_REF].