Benoît Gschwind

Lionel Ménard

Thierry Ranchin

Lucien Wald

Paul Stackhouse

A Proposal for a Thesaurus for Web Services in Solar Radiation

Metadata are necessary to discover, describe and exchange any type of information, resource and service at a large scale. A significant amount of effort has been made in the field of geography and environment to establish standards. Efforts still remain to address more specific domains such as renewable energies. This communication focuses on solar energy and more specifically on aspects in solar radiation that relate to geography and meteorology. A thesaurus in solar radiation is proposed for the keys elements in solar radiation namely time, space and radiation types. The importance of time-series in solar radiation is outlined and attributes of the key elements are discussed. An XML schema for encoding metadata is proposed. The exploitation of such a schema in web services is discussed. This proposal is a first attempt at establishing a thesaurus for describing data and applications in solar radiation.

Introduction

Solar radiation is a domain where data are rare. The few providers are usually the National Meteorological Services which are geographically distributed. Such data are necessary to a large number of users (companies, consultants, researchers, students) in various business domains (energy, building engineering, health, agriculture, meteorology, climate…). Consequently, many exchanges of data occur. A recent survey conducted by the International Energy Agency (IEA) emphasises the heterogeneity observed in the data in various aspects [START_REF] Cros | The Availability of Irradiation Data[END_REF]. Access to data is complicated by the various types of data, various storage standards, various units, various time systems (coordinated universal time, mean solar time, true solar time, local time), diversity in information properties stored in databases: sampling support (e.g., pixel size or pin-point measurement), observational period, frequency of individual observations and averaging time intervals, etc. The survey identifies three major problems to solve in order to supply customers with information relevant to their requests: improved access to information, improved description and knowledge in space and time of the radiation field and related quantities, and improved matching to actual needs. It suggests that combining "measured or assessed data and physical models permits convenient access to the information. Co-operation between several sources of information provides fruitful results. Efforts made in integrated information systems and co-operative systems have to be supported to overcome the technical limits of measurements by using the information and communication technologies" [START_REF] Cros | The Availability of Irradiation Data[END_REF]).

We believe that an appropriate exploitation of metadata and web services within a collaborative system is an efficient means to solve these problems and to bring knowledge, applications and data when and where it is needed. The SoDa Service is such a collaborative information system and has been created to that aim. The success in exploitation since 2003 demonstrates that i) as foreseen by the IEA survey there is a real interest in improving access, ii) a collaborative system is an efficient solution, iii) the use of metadata permits to homogenise the graphical user interface, inputs from and outputs to users. The thesaurus of the SoDa Service is specific. An increase of capabilities in dissemination requires on the one hand, the adoption of standards and on the other hand, an extension of this thesaurus to better describe Gschwind Benoît, Lionel Ménard, Thierry Ranchin, Lucien Wald, Paul Stackhouse, 2007. A proposal for a thesaurus for web services in solar radiation. In Proceedings EnviroInfo 2007, O. Hryniewicz, J. Studzinski and M. Romaniuk (Eds), Shaker Verlag, vol. 1, pp. 135-142. specific terms in solar radiation. The projects IEA SHC #36 (2006) and EC-funded MESoR (project FP7 #038655 "management and exploitation of solar resource knowledge") partly devoted to that goal.

Metadata are necessary to ease data exchange at a large scale. A large amount of effort has been made in the field of geography and environment to establish standards. Efforts still remain to address more specific domains. This communication focuses on solar energy and more specifically on aspects in solar radiation that relate to geography and meteorology. It is a first attempt at establishing a thesaurus for describing data and applications in solar energy. A XML schema is proposed with focus on the exploitation of such a thesaurus in web services. The proposal exploits the standards available in time (ISO, W3C), geographic information (ISO, INSPIRE, GML) as well as the outcomes of several working groups for metadata in meteorology and related domains.

Users points of view are taken into account to draft this thesaurus. These views have been expressed when designing commercial products (ESRA, Meteonorm), during projects in USA, Canada or EU where dissemination is an important issue (NASA-SSE, RETScreen, EU-Satellight, EU-SoDa, EU-MESoR) and works of the IEA and the Group on Earth Observation (GEO). In addition, surveys are periodically made by managers of information systems such as NASA-SSE, RETScreen and SoDa Service.

There are three different levels that metadata may be used for: "discovery metadata", "exploration metadata" and "exploitation metadata". Each of these purposes requires different levels of information. Users needs, low number of available services and attitude of the service providers show that presently, the emphasis should be put on "exploitation metadata". These metadata describe those properties required to access, transfer, load, interpret and apply the data in the end application where it is exploited. This class of metadata often includes the details of a data dictionary, the data organisation, projection and geometric characteristics. The communication focuses on this level of metadata.

A major concern in our development and operation of the collaborative information system is the intellectual property rights (IPR). The attitude of the projects IEA SHC #36 and MESoR regarding these aspects is a respect of the IPR of the service provider with no obligation towards the collaborative information system, except those resulting from the commercial agreements if any. The "exploitation metadata" should include these aspects. However, this communication does not deal with details in IPR. The main reason is that we do not have enough experience to be able to elaborate efficienctly details on IPR with service providers and customers. For example, no agreement was reached on payment schemes in a recent workshop gathering customers and service providers (EMP 2007). Metadata proposed by ISO 19115 in sections: Identification, Distribution, Citation and Responsible Party, are believed to cover our needs in a first phase. If necessary, extension may be possible for composition of services in the same way than discussed in this communication. The encoding process of these metadata may follow ISO 19118.

Thesaurus in solar radiation

Gathering these standards, requirements and know-how gained in managing information systems, we propose a thesaurus for the main elements in solar radiation. Several thesauri exist in meteorology (AMS 2007;FAO 2007;UNESCO 2007;WMO 1966). None of them describes solar radiation accurately enough. Consequently, we establish a thesaurus that is specific to solar radiation. It comprises several elements, some of them relating to time and others to radiation. This thesaurus is based on the works of CIE (1970), [START_REF] Envisolar | Envisolar Project "Environmental Information for Solar Energy Industries[END_REF] and [START_REF] Wald | UNESCO EOLSS (Encyclopedia of Life Support System)[END_REF]. Time is a very important matter in solar radiation. The daily rotation of the earth about itself determines a day which is divided in 24 h as an average. The time defined in this way is called the mean solar time (MST). The sun is approximately at zenith when the MST is equal to 12 h. However, because the orbit of the earth is an ellipse, the sun does not reach its highest position in the sky at 12 h MST every day. The highest position is called solar noon and is reached every day at 12 h in true solar time (TST). The difference between MST and TST differs each day and may reach up to 17 min. The time standard is Coordinated Universal Time (UTC) and is the basis of the legal time. It differs by less than 1 s per day from the so-called Universal Time (UT), which is equal to the MST for longitude 0. Finally, legal time is the time legally used in one country. Several countries make use of daylight saving time, that adds 1 h to the winter legal time (summer in South hemisphere). All these times are used in solar radiation. Thus, the first elements of the thesaurus are: • Legal time, local time: The time used legally in a given country;

• Mean solar time: The time determined locally by dividing the average duration of a rotation by 24 h.

Mean solar time is equal to 12 h when the sun is at its zenith as an annual average; • True solar time: The time for which the sun is actually at its zenith when it is 12 h. This depends on the day of the year and longitude of the site; • Universal Time (UT): The mean solar time for the longitude 0.

The amount of power received by a surface depends on its geographical location. Thus, space is an important matter. This is well described in several thesauri and there is no need to adress it in a specific way in solar radiation.

Two radiation types are used to describe radiation. Irradiance is defined as a power received per area or expressed differently as radiant flux of any origin incident onto an area. Irradiation is the energy received per area; it is an irradiance integrated over a certain period of time.

The radiation at ground, whether it is expressed as irradiance or irradiation, consists of several components: direct, diffuse and reflected. This decomposition may be of importance for several solar energy conversion systems. For convenience, one may add to these components the DNI (direct normal irradiance, or irradiation). The definitions are the following:

• Diffuse component: The downward scattered shortwave radiation coming from the whole hemisphere, with the exception of the solid angle of the sun disc and of the part of the radiation reflected by the ground in the case of an inclined receiving plane; • Direct radiation: The shortwave radiation coming from the solid angle of the sun disc; • Reflected radiation: The radiation reflected by the ground and received on an inclined plane;

• Global radiation: The shortwave radiation received at ground level; it is the sum of the direct, diffuse and reflected radiations; • Direct normal radiation (DNI): The direct radiation received by a plane normal to the direction of the solar rays.

The spectral distribution of the radiation, i.e. the distribution of radiation as a function of the wavelength, varies in time and space. Its knowledge is requested for a better knowledge of the daylight, or UV radiation or any photo-energy system. Thus, we can define spectral irradiance, respectively spectral irradiation, as the spectral distribution of the irradiance, respectively irradiation, or the irradiance, respectively irradiation, integrated over a spectral window. This spectral property can be combined with the component, e.g., the spectral direct irradiance. If the spectral property is not mentioned, then it is understood that the radiation is considered as being the total, or broadband, radiation. This corresponds to an integration over the whole spectrum.

Description and attributes

How important are time-series in our activity should be underlined. Most of the information exchanged is presently under this form. We choose to focus on time-series and to use them as a basis for the description of information. A time-series is associated to a geographical site and to a period of time. In fact there are several attributes, some of them being constant in time, such as space or IPR, and others not, such as radiation values. We choose the description of a time-series as consisting of a series of constant attributes and a time-varying sequence of other time-varying attributes.

The first constant attribute is the unit in which the radiation value is expressed. The second is the type of radiation component, which is an enumeration: diffuse, direct, reflected, global, DNI. The third set of constant attributes deals with the IPR. It comprises the name of the provider and the relevant URL. An attribute conveys the name of the time-series given by the provider and another one the copyright text. Other attributes will convey information of dissemination issues. For example, data may be used freely or are of restricted access. We have chosen to attach these IPR attributes to the time-series and not only to the web services because of the composition of services that is foreseen. During composition, data flow are exchanged between services under the control of the collaborative information system and we believe that the controlling task is easier if IPR attributes are in the data flow. For the time being, we have not defined all these attributes; this should be done in close cooperation with service providers.

The next set of constant attributes deals with geographical location. Following BOM ( 2004), this set comprises the geographical coordinates and the time period of measurement which is called summarization in BOM. The associated enumeration in summarization differs slightly from WMO (2004) and BOM: 1 min, 5 min, 15 min, 1 h, 1 day, 1 week, 1 month, 1 year.

Finally, three constant attributes describe the spectral distribution. They are the two begin and end wavelengths depicting the wavelength interval over which the radiation is integrated and the unit in which these wavelengths are expressed.

It may be possible to define two other constant attributes: a scale and an offset that apply to the value as expressed in ISO 19103. We do not feel the need for these two attributes presently.

The sequence is made of a series of four time-varying attributes. One is the time corresponding to the measurement, the second is the radiation value, the third is the accuracy and the fourth one the reliability. The two latter attributes are not present in the thesaurus as there is no consensus reached up to now on that matter. This is one of the objectives of the projects IA SHC #36 and MESoR; it should be attained by the end of 2007. Though loosely defined, these attributes are present in the proposed XML schema.

Description of time is well covered by the ISO 19103, 19115 and 19118. There is no necessity for extension. Description of a date (year YYYY, month MM and day DD) and time (hour hh, minute mm and second ss) is in the form YYYY-MM-DDThh:mm:ss. Obviously, it would be better to have time expressed in decimal hour from a computational point of view. Nevertheless, we prefer to adopt this description rather than defining an extension though this would oblige most of the service providers to perform a conversion from sexagesimal system into decimal one and reciprocally.

The various systems for time may be accounted for in the ISO description. If one writes a time as hh:mm:ss±hh:mm (e.g., 18:30:43+01:00), the latter value hh:mm denotes the offset between the time used and the UT time. The offset is calculated as "local time minus UT". In the example above, 18:30:43+01:00 is the same time than 17:30:43Z where Z (or z) is the symbol used to depict UT time. As discussed before, measurements are made sometimes in TST. Using the offset permits to provide the means to represent these data in UT time. Note that the offset between TST and UT varies every day. Thus it should be computed every day. In addition, this offset should be rounded to the minute in order to conform to ISO. This may affect measurements that are made every minute or more frequently. These cases are not the most frequent presently and we believe that we can use this representation for the time being. If necessary, an extension may be performed that may include the use of decimal hours.

A limitation of this representation is encountered for data that are aggregated for, e.g., a given month over several years. For example, customers may request mean values of irradiance for each of the 12 months of a year but integrated over 10 years or more. The ISO description or that from W3C ( 2004) with the extension defining part of date, e.g. a full month within a year or a full year, does not cope with this case. An extension will be necessary.

One may note that we use only one time to describe the time range in which the measurement was made. An instant combined with a duration given by the constant attribute on summarization is sufficient. However, this assumes that all providers follow the same rule in meteorological measurements: the time given is that of the end of the measuring period. Another hypothesis is that the duration of the measurement is the same than the sampling time, which is usually the case.

We thought about another possibility to describe the instant in the time-series. We can describe the instant at which the sequence begins as a constant attribute and exploit the summarization attribute and the rank of the radiation value in the sequence to compute the measuring instant. This solution reduces the size of the message to exchange. One of the disadvantages is that it requests to have data for each instant, even if empty flag. The method for composition of services in order to detect gaps in a time-series and to fill in these gaps by invoking another web service is more difficult than if instants are provided in the sequence, even at irregular spacing. A third disadvantage is that it is more difficult to describe instant in true solar time. As already said, the difference in time between UT, or MST, and TST depends on the day; it is not constant. The only solution would be to express time only in true solar time. Experience in the SoDa Service demonstrates clearly that though physically sound and recommended by WMO in measuring solar radiation, it was not a sustainable solution as it is conflicting with the current practices.

XML schema

There are several possible ways for encoding metadata. The choice determines how efficiently the collaborative system may exploit and compose web services. Tendancy in composition is to define very exhaustive and precise XML schema to increase the capabilities and accuracy in composition. Reversely, a too verbose schema will discourage the services providers of using it. A trade-off should be found. Defining an encoding is not an easy task. Obviously, it comprises an arbitrary part that depends on the choices made in implementation and exploitation. Besides the XML schema of W3C ( 2004) dealing with time, several XML schemas exist that are relating to meteorology and to the attributes listed above [START_REF] Bom | XML schema for WxML markup language (weather XML)[END_REF]GML 2005;NOAA 2007). To our surprise, only a little of these can be exploited in our application. We believe that this is due to the fact that we are very orientated to web services and their composition and that we are dealing presently only with time-series. Description of input and output messages is of paramount importance on the efficiency of methods for adaptative composition of web services [START_REF] Ponnekanti | SWORD: A developer toolkit for web service composition[END_REF][START_REF] Medjahed | Composing web services on the semantic web[END_REF]. Besides the input and output messages, the web service description language (WSDL) (W3C 2001) does not comprise efficient means to describe the service in a more semantic way, i.e., what does this service. One way to overcome this limitation is to increase the semantics of the input and output messages by defining types that convey part of the semantics of the service. For example, if we define a type irradiance, the message does not tell much whether the data are global or direct irradiance. Defining two types globalIrradiance and directIrradiance provides a means to distinguish between two services by their messages. This is the track we are following.

Three types of attributes should be represented as types in the schema:

• the radiation parameter: irradiance, irradiation; • the radiation component: global, direct, DNI, diffuse, reflected; • the summarization: 1min, 5min, 15min, hourly, daily, weekly, monthly, yearly. Our approach is to define a generic type for a time-series of radiation data sequenceOfRadiationValues, depicted in Fig. 1. Then this type is extended to describe the three levels (Fig. 2). An example is given by sequenceOfHourlyGlobalIrradiance that inherits from sequenceOfGlobalIrradiance that inherits from sequenceOfIrradiance that inherits itself from the generic type. Rather than this 3-levels cascade, it would have been more efficient to define a generic type for each of the three types of attributes and to create a new type describing a specific time-series by inheritance of three types. However, as discussed in the next section, the XML schema will be used in a certain environment in which Java is the preferred language. Java does not accept simultaneous inheritance and this solution cannot be retained.

Once the XML schema established, one possible approach to its exploitation for web services is as follows. We choose Java because we believe that it is the most appropriate tool for our development.

Firstly, the XML schema is written down with Eclipse as illustrated in the previous section. For a given service, one should define the inputs and outputs as well as the operations using the types present in the XML schema. From that, we create a WSDL file that imports the XML schema. Then, we generate the skeleton of the service in Java. Functions are implemented to complete the service. Then, it is deployed and finally, the WSDL is published for the use of the service by the collaborative information system.

Discussion

From 2000 to 2002, the partners in the SoDa consortium spent approximately 2.5 Meuro to build a working prototype of the SoDa Service. Then our team spent approximately 150 Keuro to make a truly operational SoDa Service with more than 20 000 users, a dozen of services providers and approximately 60 services, 10 among them being for pay. As a whole, the effort was very important [START_REF] Gschwind | Converting a successful research project into a sustainable service: the case of the SoDa Web service[END_REF]. The SoDa Intelligent System (SoDa-IS) was developed to handle messages from and to web services and to invoke them [START_REF] Wald | SoDa: a project for the integration and exploitation of networked solar radiation databases[END_REF][START_REF] Cros | The Availability of Irradiation Data[END_REF]. For that purpose, a SoDa XML schema was developed, comprising a very limited number of metadata. Each service is described by a descriptor using this schema. For example, it contains the temporal and geographical coverage of the service. The SoDa-IS has also the capability of dynamically building the GUI for each service by exploiting the service descriptor. The current applications for web services invocation, like Eclipse, do not permit to construct easily such a GUI-builder and we should spend efforts to create that application that may reach the current state of the SoDa-IS. In addition, the SoDa-IS permits to compose services in an easy way, where plans are manually built a priori in the same manner than BPEL (Van der [START_REF] Van Der Aalst | Life after BPEL?[END_REF]. Finally, the SoDa-IS understands a set of metadata that are devoted to the presentation of the results, e.g., tables or graphs. These metadata are not part of the service descriptor; they are in the output flow from the service. That means that though all SoDa results exhibit the same SoDa frame, some arrangements are possible at the will of each provider. This possibility is very convenient but is not included in the web services description by W3C. This discussion shows that metadata and their encoding are a major element in the SoDa-IS. Changing them will result in a in-depth re-engineering of the SoDa-IS, of message exchanges and on services provided by tiers. We are at the very beginning of this re-engineering process with many unknowns and little guidance. One of the many concerns is the relation with providers since it is the key to success for a collaborative information system. Are they ready to spend a large amount of effort to re-engineer their services? On the contrary, should we make efforts to create an interface between the legacy SoDa XML and the new one so that legacy services can be operated in the same way than before? We believe that the answer will depend upon the provider. Some of them will re-engineer their services. For the others, we may build pseudo-services, each of them encapsulating a legacy service.

The effort in re-engineering the SoDa-IS and making a new IS that is built on Open Source software, that uses known XML schemas and WSDL and is at least equivalent in functionalities to the current SoDa-IS overpasses what has been already done for the SoDa-IS in the past years. Nevertheless, it is worth making it. As the SoDa Service brings answers that are appreciated by a large number of professionals, it must evolve to survive and continue to serve efficiently the community.

Bibliography

AMS (2007) Glossary of meteorology, American Meteorology Society. Available at amsglossary.allenpress.com/glossary.

Figure 1 .

 1 Figure 1. Schema of the generic type sequenceOfRadiationValues. Relations between attributes and types are shown.

Figure 2 .

 2 Figure 2. Diagram of inheritance of types describing the time-series of irradiance

Ecole des Mines de Paris / Armines, BP

207, 06904 Sophia Antipolis cedex, France. Email: benoit.gschwind@ensmp.fr 2 NASA Langley Research Center, Hampton, VA, USA


Abdelmajid Ben

Hamadou Miracl

Odile Piton

Héla Fehri

Recognition and translation Arabic-French of Named Entities: case of the Sport places

Keywords: Named Entities (NE), Typological Model for NE, EN retrieval, Automatic Translation of NE, Morpho-Syntactic Analysis

The recognition of Arabic Named Entities (NE) is a problem in different domains of Natural Language Processing (NLP) like automatic translation. Indeed, NE translation allows the access to multilingual information. This translation doesn't always lead to expected result especially when NE contains a person name. For this reason and in order to ameliorate translation, we can transliterate some part of NE. In this context, we propose a method that integrates translation and transliteration together. We used the linguistic NooJ platform that is based on local grammars and transducers.

In this paper, we focus on sport domain. We will firstly suggest a refinement of the typological model presented at the MUC Conferences we will describe the integration of an Arabic transliteration module into translation system. Finally, we will detail our method and give the results of the evaluation.

Introduction

The recognition of named entities is an area of current research [START_REF] Ehrmann | Les Entites Nommées, de la Linguistique au Tal : Statut théorique et méthodes de désambiguïsation[END_REF] given the proliferation of electronic documents exchanged through Internet and the need to process them by means of NLP tools. In this context, several works for identification and marking have been performed especially for Latin languages, and for English (Daille 2000). Language platforms dedicated to specific domains such as the medical field are developed [START_REF] Hamon | A Robust Linguistic Platform for Efficient and Domain specific Web Content Analysis[END_REF]. On the other hand, the translation of named entities from one language to another [START_REF] Piton | Linguistic Resource for NLP: Ask for "Die Drei Musketiere" and meet "Les Trois Mousquetaires[END_REF], [START_REF] Grass | Typologie et traductibilité des noms propres de l'allemand vers le français. Traitement automatique des langues, 3/2000[END_REF] [START_REF] Maurel | Prolex: a lexical model for translation of proper names. Application to French, Serbian and Bulgarian[END_REF]) opens new perspectives. It may be the basis of new applications such as, multilingual access to information (MAT), Document annotation/indexing and distance teaching of languages. Little work has been dedicated to Arabic NE [START_REF] Mesfar | Named Entity Recognition for Arabic Using Syntactic grammars[END_REF], [START_REF] Mesfar | Analyse morpho-syntaxique automatique et reconnaissance des entités nommées en arabe standard[END_REF], [START_REF] Fehri | Reconnaissance automatique et analyse sémantique d'entités nommées en Arabe[END_REF].

This article focuses on the recognition and translation from Arabic into French of NE. We are particularly interested in the names of athletic venues: stadiums, arenas, pools, tracks.... We propose a typological model specific to sport locations, refining the model presented at conferences MUC (MUC 6 and MUC 7) and an approach for recognition and translation from Arabic to French of the indicated NE. Based on rules, the implementation of this approach was performed using the NooJ platform [Silberstein 2005]. The rest of the article is organized as follows. We begin by detailing the typological model of NE of athletic venues. Then, we make a parallel between the grammars of NE in the two studied languages (Arabic and French). This parallel highlights the problems of Arabic-French translation for the context of study. Finally, we detail the approach proposed for the simultaneous extraction and translation of NE.

A typological model of NE of sport venues

Typing NE has been clearly specified for the first time at the conference MUC 6. The three basic types that have been defined under a hierarchy [START_REF] Poibeau | Sur le Statut référentiel des entités nommées[END_REF] are: ENAMEX, NUMEX and TIMEX. ENAMEX includes three subcategories of proper names: People, Organizations and Locations; NU-MEX includes of numerical expressions of percentages, quantities and monetary and TIMEX represents dates and durations.

Refinements have been proposed: Prolex project [START_REF] Tran | Un dictionnaire relationnel multilingue de noms propres[END_REF], whose purpose is to enable automatic processing of proper nouns, presented a modeling of ENAMEX type. This modeling has revealed the conceptual proper name and the prolexeme (i.e. a kind of super lemma of associated proper names) or family structured lexemes. Ontology has been specified taking into account the typology of Bauer [START_REF] Grass | Description of a Multilingual Database of Proper Names[END_REF]. This project has identified a two-level hierarchy with four selected hyper-types: Ethnonym (i.e. name of person, personality...), Toponym (i.e. place name : city, country ,..), Ergonym (i.e. article or manufactured product, ...) and Pragmonym (event and date,..). The names of athletic venues that we are dealing with are Toponyms.

The typological model that we propose is the result of a study of different forms of venues (stadiums, swimming pools, ice rink, ski slopes, ….) on corpus and lists of official names of sports venues available on the Internet for Arab countries (Tunisia, Algeria, Egypt, Saudi Arabia, Syria, ..) and Francophone countries (France, Belgium, Canada ,..). Our conclusion is that the typology proposed by the MUC conferences is unsuitable for our objective. We propose to refine it by adding new types related to the sub-category Locations (in MUC Hierarchy).

Figure1: The typological Model of NE sports venues

We particularly stress the compositionality and the recursivity of the NE of the sports venues. Indeed, a NE may include another one with which it is connected. This inclusion poses the problem of extracting the NE. Figure 3 gives two examples.

Agglutination problem

Arabic is an agglutinative language. Most words are formed by joining morphemes together. Indeed, textual forms are made up of the agglutination of prefixes (articles: definite article ال = the, prepositions: ل =for, conjunctions: و = and), and suffixes (linked pronouns) to the stems (inflected forms: ﻟﻌﺒﻮا = وا ﺐ+ ﻟﻌ = they play). In general, to obtain the different decompositions of a textual form, a morphological grammar is needed.

Determination problem

Some constituents of sports venues names are always determined (in the case of adjectives). Others may be determined or not determined without rules governing these situations. This is the case of toponyms.

City name directly following the category:

ﺻﻔﺎﻗﺲ ﻣﻠﻌﺐ = Sfax stadium where the name is not determined and اﻟﺮﻳﺎض ﻣﻠﻌﺐ = Stadium Riyadh where the name is determined.

It is the same for countries and regions such as:

اﻟﻤﻐﺮب ﻣﻠﻌﺐ = stadium of Morocco and ﻟﻴﺒﻴﺎ ﻣﻠﻌﺐ = Libya stadium This can also be met for anthroponyms:

ﻏﺮاف ﺷﺘﻴﻔﻲ ﻣﻠﻌﺐ = Steffi Graf Stadium: Undetermined زوﻳﺘﻦ اﻟﺸﺎذﻟﻲ ﻣﻠﻌﺐ Stadium = the Chadli Zouiten (Sport Tunisian): determined
The treatment of this problem requires the inclusion of a feature in the dictionary indicating that the noun is or not determined.

The problem of proper names

Unlike the Latin languages, Arabic proper names do not begin by capital letters (upper case does not exist in Arabic). They are therefore difficult to identify. Also, their length is not known in advance, and may depend on the traditions of the region in which the person was born. Thus, in sports venues names, they can be written as a single name اﻷﺳﺪ( ﻣﻠﻌﺐ = El-Asad stadium) or name and surname ( ﻣﻠﻌﺐ اﻟﻤﻬﻴﺮي =اﻟﻄﻴﺐ Taieb Mhiri stadium) or name and surname preceded by a title of nobility ( اﷲ ﻋﺒﺪ اﻟﻤﻠﻚ ﺳﺘﺎد = King Abdullah Stadium) or followed by "son of" )ﺑﻦ( of some regions ( ﺣﻤﺪ ﺑﻦ ﺳﺤﻴﻢ ﺳﺘﺎد = Sahim Bin Hamad Stadium). Furthermore, it is not possible to put in a dictionary all the names with all variants of writing. The transliteration could be a compromise solution because it is not easily to generalize.

The syntactic problems

The syntax of the NE in general, and those of sports venues in particular is rich and varied:

• The length of NE (or the number of components) cannot be known in advance and is variable.

To complete the sense and not remove ambiguity, we tend to add an adjective (Municipal, Olympic, National,...) or the town name or the city name followed by the country name, etc.. ﺑﺎﻟﻤﻨﺰﻩ اﻷوﻟﻤﺒﻲ اﻟﻤﻠﻌﺐ = Stade Elmenzah ﺑﺪرﻋﺎ اﻟﺮﻳﺎﺿﻴﺔ اﻟﺒﺎﺳﻞ ﻣﺪﻳﻨﺔ ﻣﻠﻌﺐ = Stadium of the sport city El-Bacelli in Deraa. • The same type of component can be found at different positions: it is mainly the case of the adjective that does not always follow the name to which it reports: اﻟﺪوﻟﻲ ﻋﻤﺎن ﺳﺘﺎد = Amman International Stadium ﺑﺎﻧﻜﻮك ﻓﻲ اﻟﻮﻃﻨﻲ اﻷﺳﺘﺎد = National Stadium in Bangkok.

• The position of Toponyms is also variable. It can follow the category of sport venue or be at the end. اﻟﺪوﻟﻲ ﺣﻠﺐ ﺳﺘﺎد = Aleppo International Stadium اﻟﺪوﻟﻲ ﻓﻬﺪ اﻟﻤﻠﻚ =اﺳﺘﺎد King Fahd International Stadium.

Problems of Arabic-French translation of NE

The translation of NE from Arabic into French is not a trivial task. Several problems must be treated to produce a valid translation. We try to summarize these issues in the following points:

• Triggers Ambiguities of the source language. Example the word "stadium" which is a trigger name of athletic venues is also used to name sport club like ﻲ اﻟﺘﻮﻧﺴ ﺐ اﻟﻤﻠﻌ = "Stade Tunisien" • The feature of gender (male and female) is not always the same for the Arabic word and its equivalent in French. These features have an influence on the agreement within the NE. Example: The word ﻣﺴﺒﺢ is masculine, while its translation "piscine" is feminine.

• The translation of proper names and city names from one language to another depends on the existence of an exonym (like "Londres" pour London); otherwise, we should transliterate.

• Ambiguity of country names and capital in Arabic: e.g. the toponym ﺗﻮﻧﺲ "Tunes" can be translated as "Tunisia" or "Tunis". It is also the case of اﻟﺠﺰاﺋﺮ which can be translated as "Algiers or Algeria".

• The place of adjectives in the NE is not the same for both Languages: Example ﻋﺒﺪ اﻟﻤﻠﻚ ﻣﻠﻌﺐ اﻷوﻟﻤﺒﻲ اﻟﻌﺰﻳﺰ (the adjective is at the end) which translated into French by: King Abdelaziz Olympic Stadium (the adjective is in the middle).

• The use of determiners and prepositions in the order of words is not always the same. For the Arabic language, if the name of cities follows the category directly, there is no particle ( ﻣﻠﻌﺐ ,)ﻣﻮﻧﺎآﻮ While in French we use 'of' better than 'in' (stadium of Monaco).

• The translation of dates is also problematic when it is expressed in the origin text as Hijri calendar (Hijri). Changes become necessary.

An approach to recognition and translation

Our approach of recognition and translation is rule oriented (an approach preferred to the statistical one when analysing texts). It is based on a balance between grammar and lexical resources. Te grammar indicates the composition rules of lexical components, in order to form a NE. The lexical resources correspond to one dictionary for each entity type indicated in the typological model pre-sented above. Each dictionary contains lemmas with the corresponding flexional model to generate all derived forms. The Arabic dictionaries entries contain, in addition, the corresponding French lemmas. This list of the dictionaries for each language is as follows (see samples in Table1): -Geographical names: City names and Country names -Geographical categories (republic, jamahiriya, kingdom...) -Adjectives associated with sports venues (e.g. olympic, national, municipal, sporting...).

-Personalities' names: Names of politicians, athletes... -Categories of sports venues (stadium, swimming pool, ice rink...) -Demonym (name/adjective for a resident of a locality or a country) -Common name associated with sports such as place (fraternity, freedom, progress...)

To each entry of the indicated dictionary, a set of features is associated. The Arabic dictionaries have the features needed to identify a NE: function, Cat_Geo, Toponym, City, Country, Perso, Sport venue. The 'Function' feature concerns the function occupied by a person: e.g. Amir, president or king; the 'Cat_geo' feature indicates a geographical category: e.g. republic, city, region, the 'Toponyme' feature indicates a geographical place (a second feature is added to precise whether it is a city or a country). The 'Perso' feature indicates that it is a name of personality that can be a leader or an athlete.

The features indicated in the French dictionary entries are useful for translating the recognized elements of the Arabic NE: besides the classical features such as gender and number, we find the feature DETZ which characterizes the names without determiner, and the Apostrophe feature concerns the entries beginning with a vowel or a silent 'h', and requiring the use of the apostrophe after 'de' or after a determiner: either 'd' or 'l' (l'amitié). The French dictionary entries contain also the inflections of French lemmas. The use of flexion is necessary to know the appropriate translation of a given Arabic word.

Arabic Dictionary

French Tunis,N+PR+DETZ+FLX=ABH-O201 ,أوﻟﻤﺒﻲA+FLX=A1+FR=olympique

Tunisie,N+PR+FLX=ABH-O201 ﺪي ,ﺑﻠA+FLX=A1+FR=municipal

Indonésie,N+apostrophe+PR+FLX=ABH-O201 ﻲ ,دوﻟA+FLX=A1+FR=international

Jakarta,N+PR+ DETZ+FLX=ABH-O201 # demonym adjectives Maroc,N+PR+FLX=ABH-O199 ﻲ ,ﺗﻮﻧﺴA+Toponyme+FLX=A1+FR=tunisien

Bangkok,N+PR+ DETZ+FLX=ABH-O199 ﺮي ,ﻣﺼA+Toponyme+FLX=A1+FR=égyptien

Jaka Baring,N+PR+ DETZ+FLX=ABH-O199 The local grammars for recognition and translation of sports venues use other more elementary grammars:

• Morphological Grammar for decomposition of Arabic agglutinated words (e.g. input : ,اﻷوﻟﻤﺒﻲ output : ال + أوﻟﻤﺒﻲ ) • Inflectional grammars for both languages • Grammar for recognizing dates that represent, in our context, historical events.

The process of recognition and translation of sports venues requires 3 basic steps: 1. Recognition of Arabic NE. 2. Translation (literally) of different components of the recognized NE into French and saving the generated associated features in a specific form. 3. Reorganisation of the generated components in accordance with the French grammar (possible change of word order, change / addition of specific connectors and agreement correction).

These steps can be implemented in two different ways: by executing them in cascade or by combining the three steps (1+2+3) into one. The advantage of the first alternative is that it is, linguistically, more portable than the second. But it requires the definition of an appropriate internal generic representation of the recognised NE. We chose the second alternative, particularly for reasons of implementation simplicity and our expertise of NooJ platform does not allow us to construct such representation and reuse it in the step 3.

The recognition and translation system that we propose is based on transducers implementing the grammars above indicated. The recognition process is directed by the existence of triggers which may be internal (i.e. part of the NE) or external (i.e. announcing a NE). The stop condition of the process is when it encountered a preposition ﻓﻲ( ب ، ) followed by a city name or an unknown word by the graph.

The main transducer for the recognition and translation is given in Figure 3. As we stated above, adjectives pose a problem for both recognition and translation. To resolve this problem, we devoted a special transducer. This transducer allows the translation of the adjective before all the components that precede it in the source NE in order to respect the position of adjectives in the French noun phrase (see Figure 4). The graph in Figure 5 shows an example of translating country names (Toponyms). This graph takes into account the presence / absence of determiner before the names of countries according to the gender (masc., fem.).

Experimentation and Evaluation

To enumerate different forms of Sports venues names (patterns) and gather the used vocabulary, we collected a corpus (i.e. learning corpus) made up of journalistic articles and lists of official sports venues names available on the Internet. This corpus is made of a hundred texts of which 200 are sports venues NE.

The implemented system is composed of one main graph and 20 sub-graphs. These grammars use some dictionaries. Among used dictionaries, we can cite the following: Let's note that we reused the Arabic dictionary of the first names [START_REF] Mesfar | Analyse morpho-syntaxique automatique et reconnaissance des entités nommées en arabe standard[END_REF]. This dictionary contains 11852 entries.

Dictionaries

For the system evaluation, we created a new corpus composed of the learning corpus and 200 pages from Wikipedia.

The figure 6 gives a sample execution of the proposed system given by Nooj platform on the indicated corpus. It represents the recognised Arabic sports venues NE with its corresponding French translation.

Figure 6: A sample of the concordance obtained for the evaluation corpus

The evaluation metrics we used are Recall, Precision and F_measure (2*P*R/(P+R)). Let's remember that the recall measures the quantity of relevant responses of the system compared to the ideal number of responses; Precision is the number of relevant responses of the system among all the responses he gave and the F-measure is a combination of Precision and Recall for penalizing the very large inequalities between these two measures. The values obtained in the evaluation of our work are:

Precision

Recall F-measure Sports venues 69% 67% 68%

The obtained result value can be explained by the lack of standards for writing proper names, especially those Transliterated from foreign proper names and the omission of triggers in some sports venues named entity. For example, in some cases, we find some sports venues preceded by a trigger word (e.g. اﻟﻤﻬﻴﺮي اﻟﻄﻴﺐ ﻣﻠﻌﺐ Taieb Mhiri stadium). Subsequently, in an other appearance of the same sport venue name, the trigger word is omitted (e.g. اﻟﻤﻬﻴﺮي اﻟﻄﻴﺐ Taieb Mhiri), for the reason to avoid repetition and long sentences.

Conclusion

In this article we have presented an approach for recognition and translation from Arabic into French of sports venues names. We have particularly noted the recognition problems of which some are spe-cific to the Arabic language. These problems have been largely resolved, but some merit special consideration. In particular, we stress on the transliteration of the proper names and the abbreviations and acronyms. Transliteration allows reducing the dictionary size of proper names. One solution has been proposed for this problem, but the results are not yet satisfactory because of the diversity of the transliteration standards and systems [START_REF] Fehri | Translation and Transliteration of Arabic Named Entities[END_REF].

About methodology, we are studying the separation of the recognition step from the translation step and defining an internal representation of the analysed NE. The objective is to reuse the recognition step for the translation of the Arabic EN into languages other than French.

Figure 2

 2 Figure 2 Two instances of the typological model

Figure 3 :

 3 Figure 3: Main transducer for the recognition and translation of names of sports venues

Figure 4 :

 4 Figure 4: Transducer treating adjectives

Figure 5 :

 5 Figure 5: Transducer of translation of names of countries

Table 1 :

 1 Extracts of French and Arabic dictionaries


Mikhail Zaidenberg
email: zaidenbe@ujf-grenoble.fr

Discrete convolution operators in positive characteristic: a variation on the Floquet-Bloch Theory

Keywords: 2010 Mathematics Subject Classification: 11C99, 11T99, 31C20, 37B15, 43A60 convolution operator, lattice, finite field, discrete Fourier transform, discrete harmonic function, pluriperiodic function

The classical Floquet theory deals with Floquet-Bloch solutions of periodic PDEs, see e.g. [Ku 3 ]. A discrete version of this theory for difference vector equations on lattices, including the Floquet theory on infinite periodic graphs, was developed by Peter Kuchment [Ku 1 , Ku 2 ].

Here we propose a variation on this theory for matrix convolution operators acting on vector functions on lattices with values in a field of positive characteristic.

Introduction

The classical Floquet theory founded in the work of Hill, Floquet, Lyapunov, and Felix Bloch, deals with different types of periodic ordinary differential equations. An advanced version of the theory applies to the periodic PDEs and deals with the Floquet-Bloch solutions [Ku 3 ]. A discrete analog appeals to the notion of a periodic graph, see e.g. [Co, vB]. This is an infinite graph equipped with a free action of a free abelian group (a lattice) Λ of finite rank. Peter Kuchment [Ku 1 ]-[Ku 2 ] adopted the Floquet theory for a periodic difference operator ∆ (e.g., the Laplace, Schrödinger, Markov operator, etc.) acting in a translation invariant function space on a periodic graph Γ; see also [KuPi], [KuVa]. Assume that a lattice Λ acts on Γ with a finite number of orbits. Then the following hold.

(1) Consider a periodic difference equation ∆(f ) = 0 on an infinite periodic graph Γ. There exists a sequence (f n ) of finite linear combinations of Floquet solutions such that every other solution f can be decomposed in a series f = ∞ n=1 a n f n with constant coefficients. (2) Every l 2 -solution can be approximated by solutions with finite support.

(3) A criterion is provided as to when this equation has no solution.

In these notes we propose a version of the discrete Floquet-Bloch theory in positive characteristic. Our approach is purely algebraic and ignores the analytic aspects, while preserving the main features of the classical theory. In some respect, the Floquet-Bloch theory for discrete operators gains a simplification when passing to a positive characteristic. In particular, the spectral theory occurs to be quite elementary. We consider matrix convolution operators acting on vector functions on a lattice Λ. Again, this includes the case of a periodic graph. As a motivation we address the survey [Za 3 ].

In positive characteristic, the traditional translation invariant function spaces of the Floquet-Bloch theory (e.g., the span of all Floquet functions) coincide with the space of all pluri-periodic vector functions (see 2.4 and 2.5). This issue, of course, simplifies things. However, in positive characteristic the latter space is not well adopted for applying the Fourier transform1 . More suitable in this respect is the subspace F p (Λ, K), though it is characteristic-dependent. It consists of all pluriperiodic vector functions on Λ with values in the base field K whose period sublattices Λ ′ ⊆ Λ are of finite indices coprime to p. The role of Bloch functions is played now by elementary functions. Such a function is a product of a constant vector and a character of Λ with values in the multiplicative group K × of K.

Besides this Introduction, the paper contains sections 2-5. After recalling in section 2 necessary preliminaries on harmonic analysis on lattices in positive characteristic, we introduce our principal function space and define the Fourier transform. The rest of the paper is devoted to spectral analysis of convolution operators. In section 3 we treat the scalar case, where such operators are semi-simple (i.e. diagonalizable, see Propositions 3.2 and 3.5). While in the vector case (see section 4) these operators are not any more semi-simple, in general. Given a convolution operator ∆ acting on vector functions, we construct in Theorems 4.2 and 4.7 a Jordan basis of ∆ consisting of elementary functions. Until subsection 4.3 the base field K is assumed being algebraically closed. In subsection 4.3 we deduce, for a generalized Laplace equation ∆(f ) = 0, the existence of a solution with values in a finite field assuming that there exists such a solution with values in its algebraic closure. In concluding section 5 we provide some examples.

The author is grateful to the referee for correcting an error in a formula in the first draft of the paper.

Preliminaries

2.1. Harmonic analysis on lattices. Let us recall some generalities; see e.g., [Ni, Za 2 ] for details.

Given a prime integer p > 0 we consider the finite Galois field F p = GF(p) and its algebraic closure K = K p . Recall that the multiplicative group K × of K is a torsion group. Moreover, every finite subgroup of K × is cyclic of order coprime to p, and every cyclic group Z/nZ of order coprime to p is isomorphic to a unique subgroup of K × ; see e.g., [LN].

2.1. Lattices and dual tori. Consider a lattice Λ of rank s > 0. By a character of Λ over K we mean a rational representation χ : Λ → GL(1, K) ∼ = K × . The image χ(Λ) ⊆ K × is a cyclic subgroup of order coprime to p. The dual group Λ ∨ of Λ over K is the group of all characters Λ → K × . It is isomorphic to the algebraic torus T s = (K × ) s . By the duality theorem (Λ ∨ ) ∨ ∼ = Λ. Indeed, the natural duality pairing Λ × Λ ∨ → K × is non-degenerate.

More specifically, given a base V = (v 1 , . . . , v s ) of Λ we can identify Λ with the standard integer lattice Z s by sending

v = s i=1 λ i v i ∈ Λ to λ(v) = (λ 1 , . . . , λ s ) ∈ Z s . The pairing becomes now Z s × T s → K × , (λ, z) -→ z λ = s i=1 z λi i for z = (z 1 , . . . , z n ) ∈ T s .
Fixing z ∈ T s gives a character Z s → K × , λ -→ z λ , and every character Z s → K × arises in this way. On the other hand, every character of the torus T s with values in K × is given by a Laurent monomial z -→ z λ . This yields an identification (Λ ∨ ) ∨ ∼ = Λ.

2.2. Convolution operators. Consider the group algebra K[Λ] over K i.e., the algebra of functions Λ → K with finite support endowed with the convolution

(f, g) -→ f * g, where (f * g)(u) = v∈Λ f (v)g(u -v) . A convolution operator ∆ a ∈ End(K[Λ]), ∆ a (f ) = a * f, where a ∈ K[Λ] , can be written as ∆ a = v∈Λ a(v)τ -v ,
where τ v denotes the shift by v:

τ v (f )(u) = f (u + v). Clearly, ∆ a commutes with shifts: [∆ a , τ v ] = 0 ∀v ∈ Λ. In fact, any endomorphism ∆ ∈ End K (K[Λ]
) commuting with shifts is a convolution operator with kernel a = ∆(δ 0 ), where

δ v ∈ K[Λ] stands for the delta-function concentrated on v ∈ Λ i.e., δ v (v) = 1 and δ v (u) = 0 ∀u = v . For a = δ v we obtain ∆ a = τ -v ; indeed, δ v * δ 0 = δ v = τ -v (δ 0 ). The K-algebra of convolution operators is naturally isomorphic to the group algebra K[Λ].
2.2. Translation invariant function spaces.

2.3. Some characteristic-free function spaces. Consider the space F = F(Λ, K) of all K-valued functions on Λ. This is a K[Λ]-module with respect to the natural action (i) The subspace K[Λ] ⊆ F of all functions with finite support. (ii) Given a sublattice Λ ′ ⊆ Λ, we let F Λ ′ denote the subspace of all Λ ′ -periodic functions i.e.,

K[Λ] × F → F, (a, f ) -→ a * f = ∆ a (f ). A subspace E ⊆ F is a K[Λ]-submodule if and only if it is translation invariant i.e., τ v (E) = E for all v ∈ Λ. A one-dimensional subspace of F is a K[Λ]-submodule if
F Λ ′ = {f ∈ F | Λ(f ) ⊇ Λ ′ } , where Λ(f ) = {v ∈ Λ | τ v (f ) = f }
stands for the period lattice of f . (iii) Given an isomorphism Λ ∼ = Z s we define the subspace E 1 ⊆ F of all traces of polynomial functions i.e.,

E 1 = {q|Z s ∈ F | q ∈ K[x 1 , . . . , x s ]} .
(iv) The subspace E 2 ⊆ F of all pluri-periodic functions,

E 2 = Λ ′ ⊆Λ, indΛΛ ′ <∞ F Λ ′ , is clearly translation invariant. (v)
The subspace E 3 ⊆ F of all polynomially periodic functions. Given an isomorphism Λ ∼ = Z s , a function g ∈ F is called polynomially periodic if there exists a sublattice Λ ′ ⊆ Λ of finite index and a set of polynomials q v ∈ K[x 1 , . . . , x s ], where v ∈ Λ/Λ ′ , such that

g(v) = q v (v) if v ∈ v .
(vi) The subspace E 4 ⊆ F of all Floquet functions:

E 4 = {f = n i=1 χ i g i ∈ F | χ i ∈ Λ ∨ = Char(Λ, K × ), g i ∈ E 3 } .
(vii) The subspace E 5 ⊆ F spanned by all Λ ′ -automorphic functions on Λ, where Λ ′ runs over the set of all finite index sublattices of Λ. Given a sublattice Λ

′ ⊆ Λ, a function f ∈ F is called Λ ′ -automorphic if, for some character χ of Λ ′ , (τ u f )(v) = χ(u)f (v) ∀u ∈ Λ ′ , ∀v ∈ Λ .
(viii) The subspace E 6 ⊆ F of all finite-valued functions on Λ, etc.

Due to the following proposition, there are just three different spaces among the function spaces E 1 , . . . , E 6 . In particular, in positive characteristic the Floquet functions are the same as the pluriperiodic functions.

Proposition 2.5. We have

E 1 E 2 = E 3 = E 4 = E 5 E 6 .
Proof. Letting p = Char(K) we observe that (x+pλ) n = x n for every monomial x n = s i=1 x ni i (regarded as a function in x ∈ Z s = Λ) and for every λ ∈ Z s . Hence every polynomial function on Λ is Λ ′ -periodic, where Λ ′ = pΛ. Therefore

E 1 ⊆ F Λ ′ ⊆ E 2 . By a similar reason, E 3 , E 4 ⊆ E 2 . For instance, if g ∈ E 3 is as in (v) then pΛ ′ ⊆ Λ(g). Indeed, for every v ∈ Λ and v ′ ∈ Λ ′ we have v + pv ′ + Λ ′ = v + Λ ′ . Hence g(v + pv ′ ) = q v+pv ′ (v + pv ′ ) = q v+pv ′ (v) = q v (v) = g(v)
.

Thus E 3 ⊆ E 2 .
It is easily seen that the sum and the product of pluri-periodic functions are again pluri-periodic. Since every character χ ∈ Λ ∨ is Λ 0 -periodic, where the sublattice Λ 0 = ker(χ) is of finite index in Λ, the inclusion

E 4 ⊆ E 2 holds. The inclusions E 2 ⊆ E 3 ⊆ E 4 are evident. It follows that E 1 ⊆ E 2 = E 3 = E 4 ⊆ E 6 .
Every pluri-periodic function f ∈ E 2 (in particular, every character of Λ) is Λ(f )-automorphic. Hence E 2 ⊆ E 5 . Let furthermore f ∈ E 5 be a Λ ′ -automorphic function as in (viii), where Λ ′ ⊆ Λ is a finite index sublattice. Since the period lattice Λ(f ) contains the finite index sublattice Λ 0 = ker(χ) ⊆ Λ ′ ⊆ Λ, f is pluri-periodic. Thus E 2 = E 5 and so

E 1 ⊆ E 2 = E 3 = E 4 = E 5 ⊆ E 6 .
It remains to show that E 1 = E 2 = E 6 . The latter assertion is easy and we leave it to the reader. As for the former, it is enough to consider the case of a lattice Λ ∼ = Z of rank 1. In this case, whenever p ≥ 3, a non-constant 2-periodic function f ∈ E 1 cannot be a trace of a polynomial. In other words, a 2-periodic trace of a polynomial q ∈ K[x] on Z must be constant. Indeed, since q(1) = q(1p) = q(0) we have q|2Z = q|(2Z + 1). In the remaining case p = 2, a 3-periodic function f on Z with f (0) = f (1) = 0 and f (2) = 1 cannot be a trace of a polynomial over K, since

f (0) = f (2). Thus indeed E 1 = E 2 .
2.6. The function space F p (Λ, K). In positive characteristic, the function space E 2 = E 3 = E 4 = E 5 of all pluri-periodic functions on Λ is not quite appropriate for defining the Fourier transform. More suitable is the translation invariant space

F p (Λ, K) = span(χ|χ ∈ Λ ∨ ) ⊆ F
spanned by all characters of Λ with values in K × . Of course, it depends on the characteristic p. In Proposition 2.11 below we characterize this subspace in terms of period lattices. To this point we need the following definitions.

Definition 2.7. Let Λ ′ ⊆ Λ be a sublattice of finite index. We say that Λ ′ is p-saturated if pv ∈ Λ ′ implies that v ∈ Λ ′ . This holds if and only if the index ind Λ (Λ ′ ) is coprime to p, or, equivalently, the quotient group G = Λ/Λ ′ of order ind Λ (Λ ′ ) has no p-torsion. Clearly, the intersection of two p-saturated sublattices is again p-saturated.

If Λ ′ is p-saturated then every bigger sublattice Λ ′′ ⊇ Λ ′ is, since ind Λ Λ ′′ |ind Λ Λ ′ . If Λ ′ is p-saturated then the dual group G ∨ of G is isomorphic to the group of characters Char(G, K × ). Otherwise Char(G, K × ) ∼ = G ∨ /G ∨ (p), where G ∨ (p) is the Sylow p-component of G ∨ (cf. [Za 2 , §1]).
2.8. Every character χ ∈ Λ ∨ regarded as a function in F p (Λ, K) is pluri-periodic, with the period lattice Λ(χ) = ker(χ). The quotient group

G(χ) = Λ/Λ(χ) ∼ = χ(Λ) ⊆ K ×
is a finite cyclic group of order ord(χ) coprime to p. Hence the period lattice Λ(χ) is p-saturated (see 2.7).

According to 2.6 any function

f ∈ F p (Λ, K) is a linear combination of characters: f = m i=1 α i χ i , where α i ∈ K, χ i ∈ Λ ∨ . Therefore the lattice of periods of f , Λ(f ) ⊇ m i=1 Λ(χ i ) is also p-saturated. Definition 2.9. Let f ∈ F be a pluri-periodic function, that is the period lattice Λ(f ) ⊆ Λ has finite index (see Example 2.4(iv)). We say that f is p-pure if Λ(f ) is p-saturated. We let F pp (Λ, K) denote the space of all p-pure pluri-periodic functions on Λ with values in K. This is indeed a linear space because Λ(f + g) ⊇ Λ(f ) ∩ Λ(g) is p-saturated if Λ(f ) and Λ(g) are, see 2.7. Furthermore, the space F pp (Λ, K) is translation invariant, because Λ(τ v (f )) = Λ(f ) ∀v ∈ Λ. So this is a convolution module over K[Λ].
Remark 2.10. We have shown in Example 2.4 that the trace on Λ of a polynomial q ∈ K[x 1 , . . . , x s ] is Λ ′ -periodic, where Λ ′ = pΛ = pv 1 , . . . , pv s . However, the sublattice Λ ′ ⊆ Λ of finite index is not p-saturated. The function q|Λ is p-pure if and only if this is a constant function.

Proposition 2.11.

F pp (Λ, K) = F p (Λ, K).
Proof. The inclusion F p (Λ, K) ⊆ F pp (Λ, K) is immediate from 2.8 and 2.9. It remains to show the converse inclusion. Let f be a pluri-periodic function with period lattice Λ(f ) ⊆ Λ of index coprime to p.

Then f = f • π is the pullback of a function f : G(f ) → K, where G(f ) = Λ/Λ(f ) is a finite abelian group of order coprime with p and π : Λ → G(f ) is the canonical surjection. The function space F(G(f ), K) being spanned by characters of G(f ) with values in K × (see [Za 2 , Lemma 2.1(a)]) there is a presentation f = n i=1 α i χ i with χ i ∈ Char(G(f ), K × ) and α i ∈ K . (1) Thus f = n i=1 α i χ i , where the characters χ i = χ i • π ∈ Λ ∨ are the pullbacks of χ i , i = 1, . . . , n.
This yields the desired conclusion.

Fourier transform.

2.12. The Fourier transform on K[Λ] sends the group ring K[Λ] isomorphically onto the coordinate ring of the torus O(Λ ∨ ). Given a base V of Λ and the identifications Λ ∼ = Z s and Λ ∨ ∼ = T s as above, F is given by

F : f -→ f (z) = λ∈Z s f (λ)z λ . It sends K[Λ] ∼ = K[Z s ] isomorphically onto the algebra of Laurent polynomials O(Λ ∨ ) ∼ = O(T s ) = K[z, z -1 ] = K[z 1 , . . . , z n , z -1 1 , . . . , z -1 n ] .
In particular, the delta-function

δ v ∈ K[Λ] is sent to the Laurent monomial δ v = z λ(v) ∈ O(T s ),
which is a character of Λ. Or, in coordinate-free form, δ v = eval v regarded as a function on the characters of Λ. The equality

δ v * δ w = δ v+w in K[Λ] amounts to z λ(v) z λ(w) = z λ(v)+λ(w) in O(T s ). The inverse Fourier transform F -1 : K[z, z -1 ] → K[Z s ] sends a Laurent polynomial λ∈Z s f (λ)z λ into its coefficient function f ∈ K[Z s ].
2.13. Fourier transform on F p (Λ, K). We let F fs (Λ ∨ , K) denote the space of all functions on Λ ∨ with finite support. It comes equipped with the structure of O(Λ ∨ )-module.

Our next goal is to define a Fourier transform on the space F p (Λ, K) ⊆ F so to obtain an isomorphism

F : K[Λ] ⊕ F p (Λ, K) ∼ = -→ O(Λ ∨ ) ⊕ F fs (Λ ∨ , K)
of K[Λ]and O(Λ ∨ )-modules, respectively. The following observations will be useful in the sequel.

2.14. Suppose that Λ ′ is p-saturated, and let π : Λ → G = Λ/Λ ′ be the canonical surjection. The dual group G ∨ ∼ = Char(G, K × ) of the finite group G = Λ/Λ ′ can be realized as the finite subgroup

Λ ′ ⊥ = {χ ∈ Λ ∨ | Λ ′ ⊆ ker χ} ⊆ Λ ∨ via the pullback π ∨ : G ∨ ∼ = -→ Λ ′ ⊥ , G ∨ ∋ χ -→ χ = π ∨ ( χ) = χ • π ∈ Λ ′ ⊥ . Letting f = f • π ∈ F Λ ′ (Λ, K) and χ = χ • π ∈ Λ ′⊥ from (1) we obtain a presentation f = χ∈Λ ′⊥ α(χ) • χ . (2)
Clearly, every function f ∈ F Λ ′ (Λ, K) admits such a presentation i.e., F Λ ′ (Λ, K) = span(χ|χ ∈ Λ ′⊥ ).

Definition 2.15. For a function f ∈ F p (Λ, K) we define its Fourier transform as

F : f = m i=1 α i χ i -→ f = m i=1 α i δ χ -1 i . (3) Since supp( f ) ⊆ Λ(f ) ⊥ (see 2.14) we have f ∈ F fs (Λ ∨ , K).
Thus the Fourier transform yields an isomorphism

F : F p (Λ, K) ∼ = -→ F fs (Λ ∨ , K), χ -→ δ χ -1 , with inverse F fs (Λ ∨ , K) ∋ ϕ = χ∈supp(ϕ) ϕ(χ) • δ χ -→ F -1 (ϕ) = χ∈supp(ϕ) ϕ(χ) • χ -1 ∈ F p (Λ, K) .
Proposition 2.16. For every a ∈ K[Λ] and for every f ∈ F p (Λ, K) we have

a * f = a • f . (4)
Proof. The space K[Λ] being spanned by delta functions and F p (Λ, K) by characters of Λ, and the Fourier transform being linear, it is enough to verify (4) in the particular case where a = δ v (v ∈ Λ) and f = χ ∈ Λ ∨ . We have

δ v * χ = τ -v (χ) = χ -1 (v) • χ = δ v (χ -1 ) • δ χ -1 = δ v • δ χ -1 = δ v • χ . Indeed, δ v = eval v ∈ F(Λ ∨ , K) . In particular χ -1 (v) = eval v (χ -1 ) = δ v (χ -1 ) . Now (4) follows.
3. Convolution operators: the scalar case 3.1. ∆ a -harmonic functions.

3.1. Let a ∈ K[Λ]. A function f ∈ F satisfying the equation ∆ a (f ) = a * f = 0
will be called ∆ a -harmonic. Choosing a base of Λ we identify Λ with Z s and Λ ∨ with the torus T s . With every convolution operator ∆ a on Λ = Z s we associate its symbolic variety Σ a = Σ ∆a . This is an affine hypersurface in the dual torus Λ ∨ ∼ = T s defined as

Σ a = {z ∈ T s | a(z -1 ) = 0} , where a = F (a) is a Laurent polynomial in z = (z 1 , . . . , z s ), see [Za 2 , 2.7]. Every character χ ∈ Σ a viewed as a function on Λ = Z s is ∆ a -harmonic. Indeed, for z ∈ Σ a we have ∆ a (z λ ) = v∈Λ a(v)τ -v (z λ ) = v∈Λ a(v)z λ-v = z λ a(z -1 ) = 0 .
The following proposition is an analog of Theorems 1-3 in [Ku 2 ] in the case of scalar functions. Proof. To show (a) suppose that f ∈ K[Λ] is ∆ a -harmonic. Then by Proposition 2.16 a • f = 0 and so a, f ∈ K[z, z -1 ] are zero divisors. However, the algebra K[z, z -1 ] of Laurent polynomials being an integral domain this implies that f = 0. Indeed, a = 0 by our assumption.

(b) If a = cδ v i.e., ∆ a is proportional to a shift then the only ∆ a -harmonic function in F is the zero function. Assume further that a = cδ v i.e., a is not a Laurent monomial and so Σ a = ∅. Let f ∈ F Λ ′ be ∆ a -harmonic and Λ ′ -periodic, where Λ ′ ⊆ Λ is a sublattice of a finite index coprime to p, see Proposition 2.11. Then f is the pullback of a function f : G = Λ/Λ ′ → K. We let a * : G → K denote the pushforward function defined by

a * (v + Λ ′ ) = v ′ ∈Λ ′ a(v + v ′ ) . This is a unique function in F(G, K) satisfying the condition a * • π = a * δ Λ ′ , where π : Λ ։ G is the canonical surjection and δ Λ ′ stands for the characteristic function of Λ ′ ⊆ Λ (see [Za 2 , (7)]). Since f is ∆ a -harmonic, by the Pushforward Lemma 1.1 in [Za 2 ], ∆ a * ( f ) = 0. It follows that f is a linear combination of a * -harmonic characters of G, see [Za 2 , Corollary 2.2].
Their pullbacks are ∆ a -harmonic characters of Λ, and so f is a linear combination of the latter characters, as stated in (b).

There are the easy equivalencies:

a = 0 ⇐⇒ Σ a = T s ⇐⇒ ker(∆ a |F p (Λ, K)) = F p (Λ, K) .
In the opposite direction, we have the following result (cf. [Ku 1 , Corollary 2]).

Corollary 3.3. There is no nonzero ∆ a -harmonic function on Λ if and only if Σ a = ∅, if and only if ∆ a is proportional to a shift, if and only if ∆ a is invertible.

3.2. The Floquet-Fermi hypersurfaces. This notion is borrowed in [START_REF] Kuchment | On the structure of eigenfunctions corresponding to embedded eigenvalues of locally perturbed periodic graph operators[END_REF]Definition 2].

Definition 3.4. For a convolution operator ∆ a , where a

∈ K[Λ], its Floquet-Fermi hypersurface of level µ ∈ K is Σ a,µ = {z ∈ T s | a(z -1 ) = µ} .
Actually Σ a,µ = Σ a-µδ0 is the symbolic hypersurface of the operator ∆ a -µId. We let

E a,µ = span(χ | χ ∈ Σ a,µ )
denote the eigenspace of ∆ a |F p (Λ, K) with eigenvalue µ.

The following proposition is straightforward. Nevertheless, we provide a short argument.

Proposition 3.5. We have

F p (Λ, K) = µ∈K E a,µ .
In particular, the convolution operator ∆ a on the space F p (Λ, K) is diagonalizable in the basis of characters.

Proof. Choosing a base (v 1 , . . . , v s ) of the lattice Λ, we identify Λ with Z s and Λ ∨ with the torus T s . Letting τ i denote the shift by -v i , the convolution operator ∆ a can be written as a Laurent polynomial in the basic shifts τ 1 , . . . , τ s . Namely,

∆ a = λ∈Z s a(λ)τ -λ = λ=(λ1,...,λs)∈Z s a(λ) s i=1 τ λi i = a(τ 1 , . . . , τ s ) .
Using the equalities

τ i (z λ ) = z -1 i • z λ , for every z ∈ K × we obtain ∆ a (z λ ) = a(τ 1 , . . . , τ s )(z λ ) = a(z -1 ) • z λ .
Now both assertions follow.

Remarks 3.6. 1. Here is an alternative approach. According to Proposition 2.16 the Fourier transform F sends the convolution operator ∆ a |F p (Λ, K) to the operator of multiplication by the function a on the space F fs (Λ ∨ , K) = F (F p (Λ, K)). The latter operator being semi-simple, ∆ a is semi-simple too.

2. Let us identify Λ with Z s and Λ ∨ with the torus T s . Notice that the spectrum of ∆ a |F p (Λ, K) coincides with the range of the Laurent polynomial

a(z -1 ) = λ∈Z n a(λ)z -λ . Hence • spec(∆ a ) = {µ} if and only if a = µδ 0 ; • spec(∆ a ) = K × if and only if a = αδ v for some α ∈ K × and some v ∈ Λ \ {0}; • spec(∆ a ) = K otherwise. Furthermore, if a = αδ v then E a,µ = span(z -λ | a(z) = µ) = f ∈ F p (Λ, K) | f (λ) = z∈T s α(z)z -λ : α ∈ F fs (T s , K) s.t. supp(α) ⊆ a -1 (µ) . (5)
If s = rank(Λ) > 1 then every level set a -1 (µ), where µ ∈ spec(∆ a ), is an infinite countable set (indeed, the algebraically closed field K = F p is infinite countable). Hence for every µ ∈ K the eigenspace E a,µ has a countable basis of characters; in particular dim(E a,µ ) = +∞. While for s = 1 all these eigenspaces are finite dimensional.

Convolution operators: the vector case

Letting A n = A n K be the affine n-space over K and (e 1 , . . . , e n ) be the canonical basis of A n , we consider the space F n = F(Λ, A n ) of all K-valued vector functions on Λ, and its subspaces K[Λ] n of all vector functions on Λ with finite support and F p (Λ, A n ) of all p-pure pluri-periodic vector functions on Λ. The vector functions on Λ = Z s of the form f (λ) = χ • u = z λ • u, where z ∈ T s = Λ ∨ and u ∈ A n , will be called elementary. These are analogs in positive characteristic of the classical Bloch functions. Thus any f ∈ F p (Λ, A n ) is a linear combination of elementary functions.

4.1. Identifying as before Λ with Z s and Λ ∨ with T s , the Fourier transform sends a vector function f ∈ K[Λ] n into the vector Laurent polynomial

f (z) = λ∈Z n f (λ)z λ , z ∈ T s ,
where f (λ) ∈ A n ∀λ ∈ Z s . In particular, a basic vector delta-function

δ i,λ = δ λ • e i ∈ K[Λ] n , where λ ∈ Λ = Z s , is sent to the vector Laurent monomial δ i,λ = z λ • e i (i = 1, . . . , n). A pluri-periodic vector function f = m i=1 α i χ i ∈ F p (Λ, A n ) ,
where α i ∈ A n and χ i ∈ Λ ∨ , is sent to the vector function on Λ ∨ with finite support

f = m i=1 α i δ χ -1 i ∈ F fs (Λ ∨ , A n ) .
4.1. ∆-harmonic vector functions. Consider an endomorphism ∆ ∈ End (K[Λ] n ) commuting with shifts on Λ. Letting ∆(δ i,0 ) = a i = (a i1 , . . . , a in ) ∈ K[Λ] n , i = 1, . . . , n , we get a square matrix A = (a ij ) of order n with entries in K[Λ]. The images of the remaining basic vector functions δ i,v can be recovered as suitable shifts of the vectors a i :

∆(δ i,v ) = ∆(τ -v δ i,0 ) = τ -v (∆(δ i,0 )) = τ -v (a i ) . If f = (f 1 , . . . , f n ) ∈ K[Λ] n and g = ∆(f ) = (g 1 , . . . , g n ) ∈ K[Λ] n then g = A * f i.e., g i = n i=1 a ij * f j , i = 1, . . . , n . (6)
In other words, ∆ acts on K[Λ] n as a square matrix of convolution operators ∆ A = (∆ aij ). Such operator ∆ can be applied to an arbitrary vector function f = (f 1 , . . . , f n ) ∈ F(Λ, A n ) = F n . This yields an extension of ∆ to F n , which we denote by the same letter. The extended endomorphism ∆ ∈ End(F n ) leaves invariant any translation invariant subspace. In particular, it acts on the subspace

F p (Λ, A n ) ⊆ F n .
The Fourier transform sends A into a matrix of Laurent polynomials A = ( a ij ). By Proposition 2.16 the relation g = A * f , where f, g ∈ F p (Λ, A n ), is transformed into

g = A • f , where f , g ∈ F fs (Λ ∨ , A n ).
The following is an analog of Theorems 1-3 in [Ku 1 ] for vector functions, with a similar proof (cf. also Theorem 8 in [Ku 2 ]).

Theorem 4.2. Let ∆ ∈ End (K[Λ] n ) be an endomorphism commuting with shifts. Consider the equation

∆(f ) = 0 , (7)
where ∆ acts on F n as in (6). Then the following hold.

(a) There exists a non-zero solution of ( 7) with finite support f ∈ K[Λ] n if and only if det A = 0. (b) Let Λ ′ ⊆ Λ be a sublattice of finite index coprime to p. There exists a Λ ′ -periodic solution f ∈ F Λ ′ (Λ, A n ) of ( 7) if and only if there exists a character χ ∈ Λ ′⊥ with det A(χ -1 ) = 0. Every such solution is a linear combination of elementary solutions

f = m i=1 χ i • u i , (8)
where χ i ∈ Λ ′⊥ with det A(χ -1 i ) = 0 and u i ∈ ker( A(χ -1 i )) ∀i = 1, . . . , m. Vice versa, any vector function as in ( 8) is a Λ ′ -periodic solution of (7).

Proof. (a) Choosing a base of Λ we identify Λ with Z s and Λ ∨ with T s . Applying the Fourier transform to (7) yields the equation

A • f = 0 . (9)
We can treat (9) as a linear system over the rational function field K(z). By the usual linear algebra argument, this system admits a rational solution f ∈ [K(z)] n = [K(z 1 , . . . , z s )] n if and only if det A = 0. Multiplying such a solution f by a suitable polynomial q ∈ K[z] we obtain a polynomial solution of (9), hence a solution in vector Laurent polynomials. In turn, (7) admits a solution with finite support.

(b) If f = (f 1 , . . . , f n ) is a nonzero Λ ′ -periodic solution of (7) then f = ( f 1 , . . . , f n ) is a nonzero solution of (9) supported on Λ ′ ⊥ . Hence f does not vanish at some point χ ∈ Λ ′ ⊥ and so (det A)(χ) = 0. However, any vector u ∈ ker( A(χ -1 )) yields an elementary solution f = χ • u of ( 7). Now the first assertion in (b) follows. The last assertion of (b) is evident.

To show the second assertion in (b), let us consider the finite abelian group G = Λ/Λ ′ of order coprime to p. Every Λ ′ -periodic vector function

f ∈ F Λ ′ (Λ, A n ) is pullback of a vector function f ∈ F(G, A n ). The image g = A * f being also Λ ′ -periodic, it is pullback of a function ḡ ∈ F(G, A n ). The endomorphism ∆ * : f -→ ḡ is given by the pushforward matrix A * = (a ij * ), where a ij * ∈ F(G, K) ∀(i, j).
A * • f = 0 . (10)
Any solution f of ( 7) gives a solution f of (10). Writing this solution as a linear combination of delta-functions yields a presentation of f as a linear combination of elementary solutions on G. The pullback of this presentation gives (8).

Definition 4.3. Consider as before an endomorphism ∆ ∈ End(K[Λ] n ) commuting with shifts, where n ∈ N. Similarly to the scalar case (where n = 1) we call the hypersurface

Σ ∆ = {z ∈ Λ ∨ | det A(z -1 ) = 0}
the symbolic variety of ∆ (cf. 3.1). A point z ∈ Σ ∆ corresponding to a character χ = z λ of Λ ∼ = Z s is called a multiplier of (7). In case (b) of Theorem 4.2 the multipliers run over the intersection Σ ∆ ∩ Λ ′ ⊥ . Thus every Λ ′ -periodic solution f of (7) as in ( 8) can be written as

f (λ) = z∈Σ∆∩Λ ′ ⊥ z λ • u(z) .
Corollary 4.4. Under the assumptions of Theorem 4.2 the equation ( 7) admits a nonzero solution f ∈ F p (Λ, K) if and only if it admits such an elementary solution, if and only if

Σ ∆ = ∅. Moreover, ker(∆) = span z λ • u | z ∈ Σ ∆ , u ∈ ker A(z -1 ) .
Remark 4.5. The finite subgroups Λ ′ ⊥ exhaust the dual torus Λ ∨ ∼ = T s when Λ ′ runs over all sublattices of Λ of finite indices coprime to p. Given ∆ ∈ EndK[Λ] n commuting with shifts, it would be interesting to find the counting function card(Σ ∆ ∩ Λ ′ ⊥ ) as a suitable analog of the Weil zeta-function.

4.2. The Jordan form of a matrix convolution operator. Over an algebraically closed field, every square matrix admits a Jordan basis [START_REF] Bourbaki | Éléments de mathématique[END_REF]Ch. VII,§5.2,Prop. 5]. We construct below such a basis for any matrix convolution operator.

Definition 4.6. Given an operator ∆ ∈ End(K[Λ]) commuting with shifts, for every µ ∈ K we consider its Floquet-Fermi hypersurface

Σ ∆,µ = {z ∈ T s | det( A(z -1 ) -µ • I n ) = 0} , the corresponding eigenspace E ∆,µ = ker((∆ -µ • Id)|F p (Λ, K)) ,
and the generalized eigenspace

E (µ) ∆ = ker((∆ -µ • Id) n |F p (Λ, K)) .
The proof of the following theorem is straightforward.

Theorem 4.7. Let ∆ ∈ End(K[Λ]) be an endomorphism commuting with shifts, extended via (6) to the space F p (Λ, K) as a matrix convolution operator. Then the following hold. (a) There is a decomposition

F p (Λ, A n ) = µ∈K E (µ) ∆ . (b) Every generalized eigenspace E (µ) ∆ ⊆ F p (Λ, K) is generated by elementary vector-functions. Namely, E (µ) ∆ = span z λ • u | z ∈ Σ ∆,µ , u ∈ ker(A(z -1 ) -µ • I n ) n = f ∈ F p (Λ, A n ) | f (λ) = z∈Σa,µ α(z)z λ , where α ∈ F fs (Λ ∨ , A n ) is s.t. α(z) ∈ ker( A(z -1 ) -µ • I n ) n ∀z ∈ supp(α) .
(c) The induced endomorphism ∆ ∈ End(F p (Λ, K)) admits a Jordan basis consisting of elementary vector functions. More precisely, fixing for every z ∈ T n a Jordan basis (u 1 (z), . . . , u n (z)) for A(z -1 ) in A n we obtain a Jordan basis

(z λ • u i (z) | z ∈ T n ) for ∆ in F p (Λ, A n ).
Remark 4.8. À priori, the choice of the vector functions u i (z) in (c) does not suppose any specific dependence on z = (z 1 , . . . , z s ). However, they can be chosen as (non-rational, in general) algebraic vector functions in z.

Convolution equations over finite fields.

Taking suitable traces we can obtain solutions of the linear equation ( 7) with values in a finite field. We discuss below this matter in more detail.

Given a square matrix function A = (a ij ) of order n with entries a ij ∈ K[Λ], we consider as before the matrix convolution equation

A * f = 0, where f = (f 1 , . . . , f n ) ∈ F p (Λ, A n ) . (11)
The proof of the following proposition follows the lines of the proof of Theorem 4.4 in [Za 2 ]. Proposition 4.9. Consider a finite Galois field GF (q) = F q ⊂ K, where q = p σ . Suppose that

a ij ∈ GF (q)[Λ] ∀i, j = 1, . . . , n. If (11) admits a nonzero solution f ∈ F p (Λ, A n ), then it admits also a nonzero solution f ∈ F p (Λ, A n ) with values in the field GF (q).
Proof. The equation ( 11) is equivalent to the system n j=1 a ij * f j = 0, i = 1, . . . , n .

Since GF (q) is the subfield of invariants of the Frobenius automorphism z -→ z q acting on K, applying this automorphism yields the equalities

n j=1 a ij * f q j = 0, i = 1, . . . , n .
That is f q = (f q 1 , . . . , f q n ) ∈ F p (Λ, A n ) is again a solution of (11). The function f j being pluri-periodic its image f j (Λ) ⊆ K is finite. Let q(f ) = p r(f ) be such that GF(q(f )) is the smallest subfield of K containing GF(q) and all the images f j (Λ), j = 1, . . . , n. We let Tr(f ) = (Tr(f 1 ), . . . , Tr(f n )), where

Tr(f j ) = Tr GF (q(f )):GF (q) (f j ) := f j + f q j + . . . + f q r(f )-1 j ∈ F p (G, K) .
The trace Tr(f ) is fixed by the Frobenius automorphism, hence it represents a solution of ( 11) with values in the finite field GF (q). It remains to show that such a solution can be chosen nonzero. Let ∆ ∈ End(F p (Λ, A n )) denote the matrix convolution operator ∆(f ) = A * f . By Corollary 4.4 ker(∆) is spanned by elementary solutions f = z λ • u, where z ∈ Σ ∆ ⊆ T s . By our assumption ker(∆) = (0), hence Σ ∆ = ∅. Choosing z ∈ Σ ∆ we let r(z) = min r | z λ , (z q ) λ , . . . , (z q r-1 ) λ are all distinct .

The entries of the matrix A(z -1 ) being Laurent polynomials with coefficients in GF(q), there exists a vector u ∈ ker( A(z -1 )), u = 0, with coordinates in the field GF(q r(z) ). Thus f = z λ •u is a nonzero elementary solution with values in the field GF (q r(z) ). Let j ∈ {1, . . . , n} be such that u j = 0. Then

f j = u j • z λ = 0. Moreover, Tr(f j ) = u j • z λ + u q j • (z q ) λ + . . . + u q r(f )-1 j • (z q r(f )-1 ) λ
is a non-trivial linear combination of pairwise distinct characters. Therefore Tr(f ) is a nonzero solution with values in the field GF (q), as required.

Remark 4.10. By Theorem 4.4 in [Za 2 ], in the scalar case the subspace ker(∆) ∩ F p (Λ, GF(q)) is spanned by suitable traces of characters (i.e., of elementary solutions).

Examples and applications

The constructions in 5.1-5.2 below are borrowed from [Ku 1 ].

5.1. Let Λ = Z s be a free abelian group acting on a countable set V with a finite quotient V /Λ of cardinality n. Choosing a fundamental domain Ω = {v 1 , . . . , v n } ⊆ V (i.e., a set of representatives of the orbits of Λ) we obtain a disjoint partition

V = v∈Λ τ v (Ω) .
According to this partition, every function f ∈ F(V, K) yields a vector function fragm(f ) ∈ F(Λ, A n K ). This provides an isomorphism of 'fragmentation' fragm :

F(V, K) ∼ = -→ F(Λ, A n ) .
Any endomorphism ∆ ∈ End (F(V, K)) commuting with the Λ-action on the space F(V, K) amounts to an endomorphism Fragm(∆) ∈ End (F(Λ, A n )) commuting with shifts. This yields a representation Fragm :

End Λ (F(V, K)) → End Λ (F(Λ, A n ))
, where End Λ stands for the set of endomorphisms commuting with the action of Λ. In 5.2 and 5.3 below we provide two particular occasions of this construction. 5.2. Covering graphs. Let Γ be a finite connected graph with n vertices. Consider the maximal abelian covering Γ → Γ, which corresponds to the commutator subgroup of the fundamental group π 1 (Γ). The deck transformation group (i.e., the Galois group) of the covering Γ → Γ is a free abelian group H 1 (Γ; Z) ∼ = Z s , where s = b 1 (Γ). It acts freely on Γ with quotient Γ = Γ/Z s . Let V be the set of vertices of the periodic graph Γ. Every convolution operator ∆ ∈ End (F(V, K)) gives rise to an operator Fragm(∆) ∈ End Λ (F(Z s , A n )) commuting with shifts. In particular, this applies to the Markov and the Laplace operators on Γ properly adopted to the case of positive characteristic. As before, this yields a representation of the algebra of convolution operators on Γ. The same construction works for any abelian covering of Γ.

To give further examples, let us consider the following toy model.

5.3.

Fragmentation: a toy model. Let Λ be a sublattice of finite index n in a bigger lattice Λ. Consider the action of Λ on the set V = Λ by shifts. Then any endomorphism ∆ ∈ End Λ (F( Λ, K)) commuting with shifts by Λ gives rise to an endomorphism Fragm Λ (∆) ∈ End Λ (F(Λ, A n )) commuting with shifts. In particular, for different choices of Λ this yields a collection of representations

Fragm Λ : K[ Λ] → End Λ (F(Λ, A n ))
of the convolution algebra on Λ.

New representations appear when restricting the morphism of fragmentation to a translation invariant subspace e.g., to the subspace F p (Λ, A n ) ⊆ F(Λ, A n ). We need the following simple lemma.

Lemma 5.4. In the notation as before, for any n coprime to p we have

fragm Λ : F p ( Λ, K) ∼ = -→ F p (Λ, A n ) . (12) Proof. For every f = (f 1 , . . . , f n ) ∈ F p (Λ, K) n , the finite index sublattice of Λ, n i=1 Λ(f i ) ⊆ Λ(f )
is p-saturated. Therefore by 2.7 Λ(f ) is p-saturated as well. This gives the inclusion F p (Λ, K) n ⊆ F p (Λ, A n ). The opposite inclusion is evident. Now the last equality in (12) follows.

Letting furthermore f = fragm Λ ( f ), where f ∈ F p ( Λ, K), it is easily seen that the sublattice of finite index

Λ(f ) ⊇ Λ ∩ Λ( f )
is p-saturated. Thus fragm Λ sends F p ( Λ, K) injectively to F p (Λ, K) n . In fact, this is a bijection. Indeed, let (v 1 , . . . , v n ) be a set of representatives of the cosets of Λ in Λ. For a vector function

f = (f 1 , . . . , f n ) ∈ F p (Λ, K) n we let f (v) = f i (v -v i ) if v -v i ∈ Λ .
It is easily seen that f = fragm Λ ( f ). Moreover, Λ( f ) ⊇ Λ(f ), where Λ(f ) is p-saturated in Λ. Hence Λ( f ) is also p-saturated and so fragm Λ in ( 12) is an isomorphism.

In 5.5-5.8 below we apply our toy model 5.3 in different concrete settings.

Example 5.5. Consider a lattice Λ = Z of rank s = 1 and the shift τ = τ -1 on Λ. By Proposition 3.5 the induced action of τ on the space F p ( Λ, K) = span(z λ | z ∈ K × ) can be diagonalized in the basis of characters. More precisely, τ (z λ ) = z -1 • z λ , so spec(τ ) = K × and

F p ( Λ, K) = µ∈K × E τ,µ , where E τ,µ = K • µ -λ .
The same is true for any convolution operator ∆ a on Λ, where a ∈ K[ Λ]. Indeed, we have ∆ a = a(τ ) and so ∆ a (z λ ) = a(z -1 ) • z λ ∀z ∈ K × .

Consider further a sublattice Λ = nZ of Λ = Z and the fragmentation Fragm(τ ) = Fragm n (τ ) ∈ End Λ (F(Λ, A n )). Since τ (δ k ) = δ k+1 ∀k ∈ Z = Λ, for the basic vector delta-functions δ i,λ = δ λ • e i on Λ we have Fragm(τ )(δ 0,k ) = δ 0,k+1 for k = 0, . . . , n -2, and Fragm(τ )(δ 0,n-1 ) = δ 1,0 .

The corresponding matrix of Laurent polynomials

A(z) = A Fragm(τ ) (z) its inverse matrix A(z) -1 = A Fragm(τ -1 ) (z) are A(z) =        0 0 . . . 0 z 1 0 . . . 0 0 0 1 . . . 0 0 . . . . . . . . . . . . . . . 0 0 . . . 1 0        resp. A(z) -1 =        0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 . . . 0 1 z -1 0 . . . 0 0        = A t (z -1 ) . Thus det(xI n -A(z)) = x n -z = n i=1 (x -ξ i ) , where {ξ 1 , . . . , ξ n } = { n √ z} = spec( A(z)) ⊆ K × .
Suppose that p ∤ n. Then for z ∈ K × we have ξ i = ξ j if i = j. So the matrix A(z -1 ) with eigenvalues ξ -1 1 , . . . , ξ -1 n can be diagonalized in the basis of eigenvectors

v i =      1 ξ i . . . ξ n-1 i      , i = 1, . . . , n , (13)
where

A(z -1 )(v i ) = ξ -1 i v i ∀i = 1, . . . , n . (14)
The collection of elementary vector functions

λ -→ v i • z λ | z ∈ K × , i = 1, . . . , n (15)
form a diagonalizing basis for the endomorphism Fragm

n (τ ) ∈ End Λ (F p (Λ, A n )) (cf. Proposition 4.7(c)). Actually v i • z λ = fragm n (ξ λ i )
, where λ -→ ξ λ is a character of Λ = Z. In conclusion, the isomorphism of fragmentation fragm n as in ( 12) sends the basis of characters in F p ( Λ, K) to a basis of elementary functions (15), which is diagonalizing for the endomorphism Fragm n (τ ) ∈ End Λ (F p (Λ, A n )).

Example 5.6. In the same setting as in 5.5, let us consider an endomorphism

∆ n,ϕ = ϕ(Fragm n (τ )) = Fragm n (ϕ(τ )) ∈ End Λ (F(Λ, A n ))
commuting with shifts, where ϕ ∈ K[t, t -1 ] is a Laurent polynomial. The matrix of Laurent polynomials that corresponds to ∆ n,ϕ is

A ∆n,ϕ = ϕ( A) = ϕ(A Fragm n (τ ) ) = A Fragm n (ϕ(τ )) ,
where A is as in 5.5. Recall that the equation ∆

n,ϕ (f ) = 0 for f ∈ F p (Λ, A n ) is equivalent to ϕ( A(z -1 ))( f (z)) = 0 ∀z ∈ K × .
By the Spectral Mapping Theorem, for every z ∈ K × we have spec(ϕ( A(z -1 ))) = ϕ(spec( A(z -1 ))) = {ϕ(ξ -1 1 ), . . . , ϕ(ξ -1 n )} , where as before {ξ 1 , . . . , ξ n } = { n √ z}. The basis ( 15) is diagonalizing for ∆ n,ϕ . Namely,

∆ n,ϕ (v i • z λ ) = ϕ(ξ -1 i ) • v i • z λ . Indeed, A ϕ(Fragm n (τ )) (z -1 ) • v i • z λ = A ϕ(Fragm n (τ )) (z -1 ) • v i • δ z = ϕ( A(z -1 ))(v i ) • δ z = ϕ(ξ -1 i ) • v i • δ z = ϕ(ξ -1 i ) • v i • z λ . The Floquet-Fermi levels of ∆ n,ϕ in T 1 = K × are Σ ∆n,ϕ,µ = {ξ n ∈ K × | ϕ(ξ -1 ) = µ} = ι ϕ -1 (µ) n = ϕ -1 (µ) -n .
In particular, the symbolic variety of ∆ n,ϕ is

Σ ∆n,ϕ = {ξ n ∈ K × | ϕ(ξ -1 ) = 0} . Letting ϕ = q/z β , where q = d j=1 (t -α j ) kj ∈ K[t] with q(0) = 0, we obtain 0 ∈ spec(ϕ( A)(z -1 )) ⇐⇒ ∃i : ϕ(ξ -1 i ) = 0 ⇐⇒ ∃i : q(ξ -1 i ) = 0 ⇐⇒ ∃i : ξ i = α -1 j
for some j ∈ {1, . . . , d} ⇐⇒ z ∈ {α -n 1 , . . . , α -n d } , where as before ξ n i = z ∈ K × , i = 1, . . . , n. Note that the sequence α j , α 2 j , . . . is periodic with period d j = ord K × (α j ) coprime to p.

The kernel ker(∆ n,ϕ ) is spanned by elementary vector functions v i • z λ as in ( 15) with z ∈ {α -n 1 , . . . , α -n d }. Choose l ∈ {0, . . . , d j -1} such that l ≡ n mod d i . Letting z jl = α -l j = ξ l i , such an elementary vector function is proportional to the vector function

f jl = z λ jl • v i = ( . . . , z -1 jl v i , v i , z jl v i , z 2 jl v i , . . . ) ∈ F p (Λ, A n ) ,
where v i ∈ A n is an eigenvector of the matrix A(z -1 jl ) as in ( 13) with eigenvalue α j = ξ -1 i . Actually f jl = fragm n (α -λ j ) , where the character α -λ j = ξ λ i : Λ → K × of order d j (equal to its period) does not depend on n.

Let us illustrate the latter issue on a concrete example.

Example 5.7. Suppose that p = 3. Consider the equation ∆ n,ϕ (f ) = ϕ(Fragm n (τ ))(f ) = Fragm n (ϕ(τ ))(f ) = 0 , (16) where ϕ(t) = t + 1 + t -1 . The roots α 1 = ω and α 2 = ω -1 of ϕ, where ω ∈ K × is a primitive cubic root of unity, have multiplicative orders d 1 = d 2 = 3. There exists an elementary solution z λ • v of ( 16) if and only if z ∈ {ω n , ω -n }, respectively ξ ∈ {ω -1 , ω}. Assuming that n ≡ 0 mod 3 we obtain l = 0 and z = 1. Letting ξ = ω -1 yields an elementary solution f = (. . . , v, v, v, . . .),

where v =            1 ω -1 ω 1 . . . ω -1 ω            ∈ A n .
This amounts to a 3-periodic solution f = ( . . . , 1, ω -1 , ω, 1, ω -1 , ω, . . . ) ∈ F p ( Λ, K) of the scalar equation

∆ a (f ) = ϕ(τ )(f ) = 0 with a = δ -1 + δ 0 + δ 1 ∈ K[ Λ] , (17)
where as before Λ = Z. The latter solution does not depend on n. Any other elementary solution can be obtained from this one by a shift and inversion ι : ω -→ ω -1 . Actually every elementary solution of ( 17) is proportional either to f (λ) or to f (λ -1 ). Thus the subspace of all ∆ a -harmonic functions ker(∆ a ) = span( f , f • ι) ⊆ F p ( Λ, K)

is two-dimensional. It is easy to check that the same holds for every p = 3 and n ≡ 0 mod p.

Example 5.8. For any p = 2 we consider the lattice Λ = Z 2 , its sublattice Λ = 2Z × 2Z ⊆ Λ of index 4, and the commuting basic shifts τ 1 = τ (-1,0) and τ 2 = τ (0,-1) on Λ. In the standard basis (e 00 , e 10 , e 01 , e 11 ) in A 4 the corresponding matrices of Laurent polynomials A i = A Fragm(τi) , i = 1, 2, are as follows:

A 1 (z -1 ) =     0 z -1 1 0 0 1 0 0 0 0 0 0 z -1 1 0 0 1 0     resp. A 2 (z -1 ) =     0 0 z -1 2 0 0 0 0 z -1 2 1 0 0 0 0 1 0 0     .
In the common basis of eigenvectors

v 1 =     1 x y xy     , v 2 =     -1 x -y xy     , v 3 =     -1 -x y xy     , v 4 =     1 -x -y xy    
these commuting matrices are reduced to the diagonal form diag x -1 , -x -1 , x -1 , -x -1 resp. diag y -1 , y -1 , -y -1 , -y -1 , where x 2 = z 1 and y 2 = z 2 . Consider further an endomorphism ρ commuting with shifts, where ρ = ϕ(Fragm(τ 1 ), Fragm(τ 2 )) = Fragm(ϕ(τ 1 , τ 2 )) ∈ End Λ (F(Λ, A 4 ))

and ϕ ∈ K[z 1 , z 2 , z -1 1 , z -1 2 ] is a Laurent polynomial. The same argument as in 5.6 above shows that the basis of elementary vector functions λ -→ v j (z) • z λ | z ∈ T 2 , j = 1, 2, 3, 4 is diagonalizing for ρ. More precisely, letting ϕ 1 (x, y) = ϕ(x, y), ϕ 2 (x, y) = ϕ(-x, y), ϕ 3 (x, y) = ϕ(x, -y), ϕ 4 (x, y) = ϕ(-x, -y) , by the Spectral Mapping Theorem we obtain ρ(v j • z λ ) = ϕ j (x -1 , y -1 ) • v j • z λ (cf. Theorem 4.7(c)). The Floquet-Fermi level-µ set of ρ is Σ ρ,µ = {z = (x 2 , y 2 ) ∈ T 2 | ∃j ∈ {1, 2, 3, 4} : ϕ j (x -1 , y -1 ) = µ} (see 4.6). The eigenspace of ρ with eigenvalue µ is E ρ,µ = span v j • z λ | z = (x 2 , y 2 ) ∈ T 2 : ϕ j (x -1 , y -1 ) = µ, j = 1, 2, 3, 4 .

Moreover,

F p (Λ, A 4 ) = µ∈K E ρ,µ .
In particular, the symbolic hypersurface of ρ is Σ ρ = {z = (x 2 , y 2 ) ∈ T 2 | ∃j ∈ {1, 2, 3, 4} : ϕ j (x -1 , y -1 ) = 0} .

The space E ρ,0 of all ρ-harmonic vector functions is ker(ρ) = span v j • z λ | z = (x 2 , y 2 ) ∈ T 2 : ϕ j (x -1 , y -1 ) = 0, j = 1, 2, 3, 4 .

  and only if it is spanned by a character χ ∈ Λ ∨ . The following function spaces are translation invariant. They arise naturally in the framework of the Floquet-Bloch Theory, cf. [Ku 1 , Ku 2 ].Examples 2.4.

  Proposition 3.2. (a) If a = 0 then a nonzero ∆ a -harmonic function on Λ cannot have finite support. (b) Every ∆ a -harmonic function f ∈ F p (Λ, K) is a linear combination of ∆ a -harmonic characters χ ∈ Σ a . In other words, ker(∆ a |F p (Λ, K)) = span(χ | χ ∈ Σ a ) .

a

  ij * * fj , i = 1, . . . , n (cf. the Pushforward Lemma 1.1 in [Za 2 ]). Since p ∤ ord G the Fourier transform is well defined on the space F(G, K) (cf. [Za 2 ]). Applying the Fourier transform on G yields a matrix function A * = ( a ij * ) on the dual group G ∨ which acts on vector functions on G ∨ via the usual matrix multiplication. Thus (7) leads to equation

Instead of the Floquet transform as exploited in [Ku 1 ], [Ku

], we apply the usual Fourier transform.