Giuseppe Di Liberti, « Universitas rerum. Sulla costituzione di un archivio di immagini », in Federico Lupo, Antologia minima, Catania, Baloon Publishing.

PREPRINT VERSION Universitas rerum. Sulla costituzione di un archivio di immagini di Giuseppe Di Liberti Il vincolo e il soggetto La costituzione di un archivio, qualunque sia la sua origine e il suo fine, dipende da un vincolo, da un nesso necessario tra i documenti. Tale vincolo -così si legge in qualunque manuale introduttivo all'archivistica -possiede due caratteristiche: deve essere naturale e originario. In questa accezione, naturale è sinonimo di involontario: l'archivio registra in modo neutro l'attività di un soggetto, senza operare una selezione, senza agire sulle funzioni svolte dai documenti.

Originario, perché tale vincolo naturale è adottato fin dall'inizio della costituzione dell'archivio e dunque i documenti in esso contenuti non possono essere aggiunti a posteriori o essere frutto di scelte volontarie di un soggetto estraneo al soggetto "produttore". I singoli documenti assumono allora il loro valore proprio in virtù delle loro reciproche relazioni, in quanto parti di un tutto, in quanto organi di un organismo complesso. Proprio tale vincolo archivistico, con queste due caratteristiche, permette di distinguere l'archivio da altre forme di raccolta di documenti, di collezioni, di biblioteche. In un saggio del 1937 che fa tutt'oggi giurisprudenza e a cui ho rubato il titolo, Giorgio Cencetti scrive: «I singoli componenti della universalità biblioteca, i libri, oltre ad avere ciascuno la sua origine in un autore, un editore, un libraio che, di regola, sono diversi, hanno altresì fine proprio, raggiungibile con mezzi propri: hanno, cioè, una loro autonomia originaria. […] Ben diversamente stanno le cose per ciò che riguarda l'archivio. Qui i singoli componenti, le carte (sarebbe forse più esatto dire franciosamente pezzi per non far distinzioni tra documenti diplomatici, registri, carte di corredo, etc.) non solo provengono dal medesimo individuo, aggregato familiare o ente (o dai suoi organi, che torna lo stesso), ma poiché costituiscono niente altro che uno fra i mezzi usati dall'ente o individuo per raggiungere i propri scopi, portano in loro stessi fin dall'origine il vincolo della destinazione comune, sintetizzato nell'adempimento delle funzioni dell'ente o individuo medesimo» 1 . L'archivio è un essere vivente e la metafora biologica è quanto mai adeguata: l'archivio funziona come un organismo, i cui organi concorrono allo stesso fine e proprio in virtù di questo tessono relazioni mutuali. Se pensiamo l'archivio come organismo, esso non può soltanto essere -in questo seguo ancora Cencetti -una sorta di rispecchiamento, di immagine riflessa, di un soggetto, bensì parte integrante del soggetto produttore, una sua memoria involontaria la cui esistenza è condizione identitaria per il soggetto. Se a fondamento di ogni archivio c'è un atto volontario di un soggetto che decide di conservare la traccia delle proprie azioni, ciò che viene conservato non sono soltanto i documenti volontari, ma anche -e forse soprattutto -i nessi involontari nonché l'attività stessa dell'archiviare come funzione vitale del soggetto, come attività costitutiva del soggetto. Ne conseguono almeno tre movimenti paradossali, che l'archivista conosce bene. Il primo è quello che va senza tregua dall'oggettività alla soggettività: l'archivio -e in modo particolare l'archivio privato di una singola persona -da un lato neutralizza la soggettività, la reifica in una serie di documenti, dall'altro introduce all'intimità del soggetto, ne restituisce -fosse solo per contatto -la corporeità.

L'archivio non è mai neutro, ma una forma in apparenza neutra delle scelte di un soggetto. «L'archivio è anzitutto la legge di ciò che può essere detto, il sistema che governa l'apparizione degli enunciati come avvenimenti singoli» 2 scriveva Foucault, nelle pagine de L'archeologia del sapere consacrate all'archivio. La neutralità non è che una strategia discorsiva per affermare la validità di un documento, così come una strategia è la sua presunta totalità. Colui che poi attraverserà un archivio non può sfuggire ad un'analisi critica delle modalità discorsive adottate: considerare la frammentarietà inevitabile dell'archivio, cogliere i nessi -il sistema discorsivo capace di attualizzare i documenti -, riconoscere e descrivere emergenze e scomparse. Il secondo movimento è dato dall'oscillazione tra l'anonimato e la proliferazione di individui. Arlette Farge, storica di un Settecento di uomini infami [START_REF]Per Foucault gli uomini infami sono coloro le cui vite «erano destinate a passare al di sotto di ogni discorso e a sparire senza essere mai state dette» e che non avrebbero lasciato traccia alcuna se non si fossero scontrate col potere[END_REF] , scrive: «L'archivio abbonda di personaggi, ben più di qualunque testo o romanzo. Questo inusuale popolamento di uomini e donne, il cui nome svelato non riduce affatto l'anonimato, rinforza nel lettore un'impressione di isolamento. L'archivio impone fin da subito una contraddizione stupefacente; nel momento stesso in cui invade e immerge, rinvia, per via della sua smisuratezza, alla solitudine. Una solitudine nella quale brulicano così tanti esseri "viventi" che sembra del tutto impossibile renderne conto» [START_REF] Farge | Le goût de l'archive[END_REF] . Un archivio, che sia esso di un'istituzione o di un privato, ci restituisce una folla di storie minime, magari accanto a frammenti di storie maggiori. La distinzione tra questi due piani discorsivi potrebbe essere quasi banale: laddove le storie maggiori proseguono e si diramano al di fuori dell'archivio, l'esistenza delle storie minime è garantita esclusivamente dall'archivio stesso. Da questo forse deriva la vertigine provata dall'archivista e una conseguente etica della delicatezza: tracciare una storia minima a partire da un singolo oggetto, un nome, un viso, sapendo che tutto ciò che resta di un'esistenza è lì e nelle relazioni che un documento istaura con altri documenti. Infine, un terzo paradosso concerne lo statuto del soggetto "produttore" dei documenti archiviati. Il soggetto è origine o conseguenza dell'archivio? È un criterio costitutivo, un'etichetta per un insieme eterogeneo di documenti, un nesso? Cosa può sfuggire alla sua selezione volontaria e rivelare così emergenze che sfuggono al suo controllo? In altri termini, l'archivio è semplicemente una protesi [START_REF] Cfr | Mal d'archive. Une impression freudienne[END_REF] di una memoria volontaria o (anche) una forma della memoria involontaria? Tutte queste questioni rimandano, in fondo, alla natura organica dell'archivio e al suo essere un sistema autopoietico.

Proprio in virtù di questo, possiamo, percorrendo un archivio, scoprire un'emergenza di senso che si oppone al potere del soggetto produttore. E se da un lato il sistema discorsivo del soggetto incorpora il sistema autopoietico dell'archivio esercitando su di esso un potere di controllo, dall'altro garantisce una mediazione tra la folla di uomini infami celata nei documenti e quella storia maggiore a cui il soggetto produttore prende parte.

Il gesto dell'archivio e la grana delle immagini L'archivio è, a pieno titolo, una forma simbolica [START_REF]Lev Manovich considera il database come forma simbolica propria all'era digitale (Cfr. Lev Manovich, "Database as Symbolic Form[END_REF] , cioè una modalità per organizzare e strutturare l'esperienza de mondo, per costruire l'esperienza come esperienza di senso, per abitare e umanizzare il mondo. Fino a due decenni fa, i soggetti "produttori" di archivi erano piuttosto rari: istituzioni oppure produttori di oggetti culturali -scrittori, ad esempio -che avvertivano la necessità di conservare traccia delle fasi del proprio lavoro per potervi ritornare 7 . Soltanto in questi casi, alla volontà di conservare tracce si affiancava la necessità di istaurare dei criteri di classificazione e quindi di ricerca e di mantenere dunque il vincolo naturale e originario. Già la diffusione della fotografia e soprattutto il passaggio dalla fotografia esclusivamente professionale alla fotografia amatoriale (prima con la Kodak n. 1 nel 1888, poi, negli anni Trenta con l'Ermanox, la Leica e la Polaroid) avevano trasformato un pubblico recettore in un pubblico produttore di immagini, ma avevano altresì allargato considerevolmente il numero degli archivisti. La necessità di archiviare le immagini non rappresenta un effetto secondario, ma un gesto rivelatore di un aspetto dell'immagine fotografica: l'essere traccia -e talora indizio -iscritta in una rete di nessi, in una serie di nessi che ne determinano il valore. In tal senso, l'avvento della fotografia digitale e lo sviluppo di tecnologie informatiche di archiviazione impongono un nuovo movimento paradossale. Il cassetto dei ricordi è esploso. La deflagrazione comporta il bisogno di fare ordine, di produrre criteri di classificazione e allo stesso tempo induce la paura di perdere i vincoli, le relazioni che rendono un archivio un organismo vivente. In risposta, costruiamo database -e basti osservare la proliferazione di software per l'archiviazione (in senso largo) e lo stoccaggio di dati -, ma i database non sono archivi e almeno per tre ragioni. La prima: l'accesso al database è random mentre l'accesso all'archivio è lineare, cioè deve sempre mantenere i legami originari di un documento con gli altri documenti. La seconda, conseguente alla prima: ogni forma di narratività a partire dal database è in post-produzione, mentre la costruzione di una storia a partire da un archivio consiste esattamente nel delicato equilibrio tra pre-produzione e post-produzione. La terza: l'eterna polarità tra valori ottici e valori aptici dell'immagine. L'archivio ci ricorda costantemente che anche le immagini sono cose dotate di una loro tattilità, di una necessaria tattilità. La stessa autenticità dell'immagine dipende dal suo essere un oggetto concreto, deperibile e quindi in una relazione necessaria con la storia. Hal Foster sintetizza così la differenza tra opere d'arte che lavorano l'archivio e opere di net-art che costituiscono database: «In most archival art the actual means applied to these "relational" ends are far more tactile and face-to-face than any Web interface. The archives at issue here are not databases in this sense; they are recalcitrantly material, fragmentary rather than fungible, and as such they call out for human interpretation, not machinic reprocessing» 8 . Salvaguardare l'essere-cosa dell'immagine significa mantenere la natura organica dell'immagine e con essa la sua stratificazione morfologica. Il database non conserva la stratificazione, l'archivio sì. L'immagine, in quanto documento, mantiene alcuni vincoli con altri documenti e integra (e produce) delle stratificazioni anche grazie alla sua materialità. Il suo valore documentario -al di là di ogni questione ontologica sulla natura dell'Immagine, le immagini d'archivio devono essere necessariamente interrogate per il loro valore documentario -dipende dal supporto, talora fragile, talora volatile, talora lacunoso e frammentario. Come qualsiasi altro documento. L'archivio ha questo ulteriore vantaggio: annullare la gerarchia data dai valori intrinsechi delle cose per valorizzare le relazioni tra le cose. Le immagini di archivio sono pezzi di reale e non riflessi del reale. Nell'epoca della riproducibilità digitale, ritroviamo nell'archivio immagini autentiche, cioè integrate in una rete di nessi e portatrici di una specifica materialità. Proprio questi due piani sollecitano molta ricerca artistica contemporanea e i lavori di Bill Morrison, Ricci Lucchi e Gianikian, Tacita Dean, Gustav Deutsh, Stan Douglas, Harun Farocki, Rodney Graham 9 , del gruppo IRWIN o nell'Atlas di Gerhard Richter 10 -giusto per citare dei casi esemplari -ne sono la testimonianza. Tra i tanti fili rossi che attraversano l'eterogeneità di queste ricerche, mi preme segnalarne almeno due, presenti anche nel lavoro di Federico Lupo. Anzitutto la corrispondenza tra grana delle immagini e grana della memoria. Chris Marker in Sans soleil, essai cinématographique del 1983, si chiedeva: «Come fanno a ricordare coloro che non filmano, non fotografano, non videoregistrano, come faceva l'umanità a ricordare?» [T.d.A]. Aggiungo : come separare la consistenza materiale delle immagini fotografiche o filmate dalle modalità del nostro ricordo? Se è possibile pensare ad una storicità dello sguardo, di conseguenza dobbiamo considerare una storicità della memoria che muta attraverso le forme che adottiamo per la rammemorazione. Nel momento in cui consegniamo a dei supporti la nostra memoria, esteriorizziamo i nostri ricordi sulla carta, sulla pellicola, su un nastro magnetico o in picture element, introiettiamo certe proprietà dell'immagine dipendenti dal supporto. Forse tra qualche anno avremo ricordi pixelati così come oggi le generazioni nate negli anni Sessanta e Settanta hanno ricordi virati, vignettati, "polarizzati" (e non a caso, Instagram o centinaia di applicazioni di fotoritocco ripropongono immagini "vintage"). I supporti delle immagini sono parte integrante del nostro reale e quindi della nostra memoria. Il secondo filo rosso riguarda la relazione tra alcune immagini di archivio e la formazione di tipologie socio-culturali. Tipologie di corpi individuali e sociali allo stesso tempo [START_REF] Cfr | Body and the Archive[END_REF] . Un esempio su tutti: le foto segnaletiche degli archivi giudiziari hanno costruito un genere di ritratto che pervade la costruzione dell'immagine che ognuno ha di se stesso. Molte immagini educano nel senso che ci spingono all'adesione a tipologie. L'archivio ci impone l'essere critici, ci offre l'antidoto alle mitologie. Oggi, in una pubblicità nella metropolitana parigina leggo: « Aux Archives, Citoyens!». Si tratta di un evento degli archivi nazionali francesi in occasione dell'apertura del nuovo sito di Pierrefitte-sur-Seine. Ritornare agli archivi implica non solo la conservazione e l'interpretazione storica, ma la nostra stessa appartenenza ad una comunità sensibile.


Tingxiang Zou
email: zou@math.univ-lyon1.fr

Pseudofinite Difference Fields

come

Introduction

The class of various expansions of fields is one of the key objects of study in model theory. Examples are differentially closed fields, Henselian valued fields, algebraically closed fields with a generic automorphism, etc. There are lots of natural examples of such structures that are intensively investigated in other areas of mathematics, while the model theories of them often extends well-known results to a wider context and sometimes, model theoretic techniques can help to discover new phenomenons.

We will consider expansions of pseudofinite fields with a distinguished automorphism. The model theory of pseudofinite fields has been initiated by J. Ax in [START_REF] Ax | The elementary theory of finite fields[END_REF] and subsequently developed in [START_REF] Duret | Les corps faiblement algébriquement clos non séparablement clos ont la propriété dindépendance[END_REF], [START_REF] Chatzidakis | Definable sets over finite fields[END_REF], [START_REF] Hrushovski | Groups definable in local fields and pseudofinite fields[END_REF]. On the other hand, the model theory of fields with a distinguished automorphism has also been investigated. The best understood one is possibly ACFA: the theory of algebraically closed fields with a generic automorphism, developed notably in [START_REF] Chatzidakis | Model theory of difference fields[END_REF], [START_REF] Chatzidakis | acov Peterzil. Model theory of difference fields, ii: Periodic ideals and the trichotomy in all characteristics[END_REF]. It is the model companion of the theory of difference fields and, interestingly, the fixed field of any model of ACFA is a pseudofinite field. Based on these, one might expect a theory of pseudofinite difference fields which is a mixture of PSF (the theory of pseudofinite fields) and ACFA.

M. Ryten has studied a specific class of pseudofinite difference fields with the motivation of understanding the asymptotic behaviour of Suzuki groups and Ree groups. In [START_REF] Jonathan | Model theory of finite difference fields and simple groups[END_REF], he showed that given any prime p and a pair of coprime numbers m, n > 1, the class {(F p kp•m+n , Frob p kp ) : k p ∈ N} is a one-dimensional asymptotic class. He also gave a recursive axiomatization of asymptotic theories of such structures: P SF (m,n,p) . In a sense, P SF (m,n,p) is a mixture of PSF and ACFA. In fact, any model of P SF (m,n,p) can be obtained as a definable substructure of some model of ACFA 1 , and the onedimensional asymptotic class result is based on the uniform estimate of the number of solutions of definable sets of finite σ-degree in some model of ACFA in [START_REF] Ryten | Acfa and measurability[END_REF].

However P SF (m,n,p) is a bit restricted in the sense that in no model of P SF (m,n,p) there are transformally transcendental elements, elements that satisfy no non-trivial 1 difference polynomial. Our aim in this paper is to study a class of pseudofinite difference fields with transformally transcendental elements.

Another class of closely related structures is the class of pairs of pseudofinite fields, as the fixed field of a pseudofinite difference field is finite or pseudofinite. As noticed by Macintyre and Cherlin, there are pairs of pseudofinite fields whose theory is not decidable. This wild phenomenon also occurs in the structures that we study, but we also gain some tameness properties of definable sets, see Theorem 9. We think it is possible to have pseudofinite difference fields with transformally transcendental elements whose theory is still decidable. But it is not clear what kind of theories they are.

Acknowledgement: the author wants to thank her supervisor Frank Wagner for initiating this interesting project and contributing lots of valuables ideas. She also wants to thank Zoé Chatzidakis for answering various questions about pseudofinite fields and ACFA, and Dario Garcia for suggestions of corrections on the previous version of this paper.

Pseudofinite coarse dimension

We begin with some preliminaries of difference fields. Definition 1. A difference field is a field (F, +, •, 0, 1) together with a field automorphism σ which is surjective.

The language of difference rings L σ is the language of rings augmented by a unary function symbol σ. Definition 2. We fix an ambient difference field L.

• Let A be a subset. We denote by A σ to be the smallest difference subfield containing A and closed under σ and σ -1 .

• Let E be a difference subfield and a be a tuple. The σ-degree, deg σ (a/E), is the transcendence degree of (E, a) σ over E.

• Let E be a difference subfield. If there is no non-zero difference polynomial over E vanishing on a, then we say a is transformally transcendental over E if a is an element in L and a is transformally independent over E if a is a tuple in L.

• Let E be a difference subfield and a be a tuple. The transformal transcendence degree of a over E is defined as the maximal length of a transformally independent subtuple of a over E.

We now give the definition of pseudofinite coarse dimension.

Definition 3. Let M be a pseudofinite structure over some non-principal ultrafilter U and R * be the ultrapower of R along U. Then any pseudofinite set D ⊆ M n has a non-standard cardinality |D| ∈ R * . Let α ∈ R * .

• The coarse dimension on M normalised by α, denoted δ δ δ α , is a function from definable sets of M to R ≥0 ∪ {∞}, defined as

δ δ δ α (A) := st( log |A| α ),
for A ⊆ M n definable. When α := log |X| for some pseudofinite set X, we also write δ δ δ α as δ δ δ X .

• We say δ δ δ α is continuous if for any ∅-definable formula φ(x, y), for any r 1 < r 2 ∈ R, there is some ∅-definable set D with

{a ∈ M |y| : δ δ δ α (φ(M |x| , a)) ≤ r 1 } ⊆ D ⊆ {a ∈ M |y| : δ δ δ α (φ(M |x| , a)) < r 2 }.
• We say δ δ δ α is definable if δ δ δ α is continuous and the set {δ δ δ α (φ(M |x| , a)) : a ∈ M |ȳ| } is finite for any ∅-definable formula φ(x, y). By compactness, it is equivalent to the following: for any ∅-definable formula φ(x, y) and a ∈ M |y| , there is ξ(y) ∈ tp(a) such that

M |= ξ(b) if and only if δ δ δ α (φ(M |x| , b)) = δ δ δ α (φ(M |x| , a)).
Definition 4. Let M be a pseudofinite structure and α ∈ R * . Let a be a tuple in M and A ⊆ M . Define

δ δ δ α (a/A) := inf δ δ δ α (ϕ(M |x| )), ϕ(x) ∈ tp(a/A) . Fact 5. [8, Lemma 2.10] If δ δ δ α is continuous, then δ δ δ α is additive, i.e., for any a, b, A ⊆ M we have δ δ δ α (a, b/A) = δ δ δ α (a/A, b) + δ δ δ α (b/A).
Remark: There is always a way to make δ δ δ α continuous by expanding the language of the structure M . However, this might add new definable sets to M , which could be an inconvenience.

The following fact is a well-known result in the class of finite fields, which gives a uniform estimate of number of solutions of definable sets in all finite fields. Our main result will be based on it. Fact 6. [START_REF] Chatzidakis | Definable sets over finite fields[END_REF] Let L be the language of rings. For every formula ϕ(x, y) ∈ L with |x| = n, |y| = m there are a constant C ϕ > 0 and a finite set D ϕ ⊂ {0, . . . , n} × R >0 such that the following holds:

For any finite field F q and a ∈ (F q ) m , if ϕ((F q ) n , a) = ∅, then there is some

(d, µ) ∈ D such that ||ϕ((F q ) n , a)| -µ • q d | ≤ C ϕ • q d-1 2 .
Now we start to define a special class of pseudofinite difference fields and study the model theoretic properties of them. Definition 7. Let L σ be the language of difference rings. Let ϕ(x, y) be a formula defined in L σ without parameters. For any prime p, define ϕ p (x, y) as the result of replacing all occurrence of σ(t) by t p . Clearly, ϕ p (x, y) is a formula in the language of rings L.

Let P be the set of all primes. For any formula ϕ(x, y) in L σ and p ∈ P, consider ϕ p (x, y) ∈ L. There are C ϕp and the finite set D ϕp as stated in Fact 6. Let

E ϕp := 0≤d≤|x| {µ : (d, µ) ∈ D ϕp }.
C ϕp • p kp(d-1 2 ) ≤ 1 2 µ kp • p kp•d . Therefore, 1 2 µ kp • p kp•d ≤ |ϕ p ((F p kp ) |x| , a p )| ≤ 3 2 µ kp • p kp•d .
Furthermore, by the definition of k p , we have Remark: This proof works also for pseudofinite difference fields of characteristic p > 0, that is, for i∈I (F p k i , Frob p t i )/U provided k i >> t i for almost all i.

In the following, we will show that the coarse dimension δ δ δ F is definable using the field structure. To prove this, we first need a lemma. Lemma 10. Let M be a pseudofinite structure in the language L M and X be a pseudofinite subset of M . Let ϕ(x, y) be an L M -formula with |x| = m and |y| = n. Suppose there is some r ∈ R ≥0 such that for all b ∈ M m we have δ δ δ

X (ϕ(M n , b)) = r whenever ϕ(M n , b) = ∅. Then δ δ δ X (ϕ(M n+m )) = r + δ δ δ X (∃xϕ(x, M m )).
Proof. Suppose (M, X) = i∈I (M i , X i )/U for some ultrafilter U on an index set I and

X i ⊆ M i finite sets. For each i ∈ I pick b max i and b min i in (M i ) m such that |ϕ((M i ) n , b max i )| is maximal and |ϕ((M i ) n , b min i )| is minimal non-zero respectively. Clearly, we have |ϕ((M i ) n , b min i )| • |∃xϕ(x, (M i ) m )| ≤ |ϕ((M i ) n+m )| ≤ ϕ((M i ) n , b max i )| • |∃xϕ(x, (M i ) m )|. Let b max := (b max i ) i∈I /U ∈ M and b min := (b min i ) i∈I /U ∈ M respectively. By assump- tion, δ δ δ X (ϕ(M n , b max )) = δ δ δ X (ϕ(M n , b min )) = r.
Therefore, for any > 0, there is some J ∈ U such that for all i ∈ J, we have

|X i | r-≤ |ϕ((M i ) n , b min i )| ≤ |ϕ((M i ) n , b max i )| ≤ |X i | r+ .
Multiplying each term by |∃xϕ(x, (M i ) m )| and combining the inequality before, we get

|X i | r-• |∃xϕ(x, (M i ) m )| ≤ ϕ((M i ) n+m ) ≤ |X i | r+ • |∃xϕ(x, (M i ) m )|. Therefore, r -+ log |∃xϕ(x, (M i ) m )| log |X i | ≤ log |ϕ((M i ) n+m )| log |X i | ≤ r + + log |∃xϕ(x, (M i ) m )| log |X i | .
By the definition of δ δ δ X we conclude that

r + + δ δ δ X (∃xϕ(x, M m )) ≤ δ δ δ X (ϕ(M n+m )) ≤ r -+ δ δ δ X (∃xϕ(x, M m )).
Since is arbitrary, we get the desired result.

Corollary 11. Let M be a pseudofinite structure in the language L and let X ⊆ M n be a pseudofinite subset. Suppose there is some r ∈ N such that for any L-formula ϕ(x, y) with |x| = 1 over ∅ and any b ∈ M |y| , we have δ δ δ X (ϕ(M, b)) ∈ {0, 1, . . . , r} and for each i ≤ r, the set

{b ∈ M |y| : δ δ δ X (ϕ(M, b)) = i} is ∅-definable.
Then for any formula ψ(x, y) and any tuple c ∈ M |y| , we have

δ δ δ X (ψ(M |x| , c)) ∈ {0, . . . , |x| • r}.
Moreover, δ δ δ X is definable.

Proof. We use induction on the length of |x|. The case |x| = 1 is given by assumption. Suppose the conclusion holds for |x| = n, we prove it for |x| = n + 1. Let ψ(x 0 , . . . , x n , y) be a formula with |x i | = 1 for 0 ≤ i ≤ n. We know that there are ∅-definable θ (x 1 , . . . , x n , y) with ∈ {0, 1, . . . , r} which define respectively the sets

{(x 1 , . . . , x n , y) ∈ M n+|y| : δ δ δ M (ψ(M, x 1 , . . . , x n , y)) = and ψ(M, x 1 , . . . , x n , y) = ∅}. For any c ∈ M |y| , note that ψ(M n+1 , c) is the disjoint union of {ψ(M n+1 , c) ∧ θ i (M n , c) : i ∈ {0, 1, . . . , r}},
and Lemma 10 applies to each of the formulas. Hence,

δ δ δ X (ψ(M n+1 , c) ∧ θ i (M n , c)) = i +δ δ δ X (∃x 0 (ψ(x 0 , M n , c) ∧ θ i (M n , c)) = i +δ δ δ X (θ i (M n , c)). By induction hypothesis, δ δ δ X (θ i (M n , c)) ∈ {0, . . . , r • n}. Therefore, δ δ δ X (ψ(M n+1 , c)) = max{i + δ δ δ X (θ i (M n , c)) : 0 ≤ i ≤ r} ∈ {0, . . . , r • (n + 1)}.
Again by induction hypotheses, for any k ∈ {0, . . . , r • n} there are ∅-definable ξ k i (y) with i ∈ {0, . . . , r}, which define the corresponding sets For any ψ(x, y), let

{y ∈ F |y| : δ δ δ X (θ i (M n , y)) = k and θ i (M n , y) = ∅}.
θ ψ (y) := ∀z∃x 1 ∃x 2 ∃x 3 ∃x 4 ( 1≤i≤4 ψ(x i , y) ∧ x 3 = x 4 ∧ z = (x 1 -x 2 ) • (x 3 -x 4 ) -1 ).
We claim that θ ψ (c) if and only if δ δ δ F (ψ(F, c)) = 1 for all c ∈ F |y| . Suppose θ ψ (c) holds, then clearly there is a surjection from (ψ(F, c))

4 to F . Therefore, δ δ δ F (ψ(F, c)) ≥ 1 4 . By assumption, δ δ δ F (ψ(F, c)) ∈ {0, 1}. Hence, δ δ δ F (ψ(F, c)) = 1. On the other hand, if ¬θ ψ (c) holds, there is a ∈ F such that for any x 1 , x 2 , x 3 , x 4 ∈ ψ(F, c) we have a = (x 1 -x 2 )(x 3 - x 4 ) -1 whenever x 3 = x 4 . Let f : (ψ(F, c)) 2 → F be defined as f (x 1 , x 2 ) := x 1 + ax 2 . Then f is an injection. Therefore, δ δ δ F (ψ(F, c)) ≤ 1 2 . We conclude that δ δ δ F (ψ(F, c)) = 0.
Hence, the set

{c ∈ F |y| : δ δ δ F (ψ(F, c)) = 0 and ψ(F, c) = ∅}
is defined by ¬θ ψ (y) ∧ ∃xψ(x, y). And θ ψ (y) defines the set

{c ∈ F |y| : δ δ δ F (ψ(F, y)) = 1}.
Corollary 13. For any pseudofinite difference field (F, Frob) ∈ S, the coarse dimension δ δ δ F is definable and integer-valued for all L σ -definable sets. Moreover, δ δ δ F is additive in the language L σ .

Proof. By Theorem 9, for any L σ -formula ψ(x, y) with |x| = 1, any b ∈ F |y| we have

δ δ δ F (ψ(F, b)) ∈ {0, 1}.
Applying Lemma 12 we get the desired result.

Remark: In general, the coarse dimension does not have the property that a definable set has dimension 0 if only if it is finite. Similarly, in a group, we don't necessarily have that a subgroup of infinite index will have smaller dimension.

Example 14. Let (F, Frob) = p∈P (F p kp , Frob p )/U ∈ S. Define a function f : F × → F × as f (x) := x -1 • Frob(x).
It is easy to see that f is a group homomorphism. Therefore, the image T := f (F × ) is a definable subgroup of F × . There is a corresponding f p : (F p kp ) × → (F p kp ) × and T p := f p ((F p kp ) × ) for any p ∈ P. Since the kernel of f p is (F p ) × , we get [(F p kp ) × :

T p ] = p -1.
Hence, T has infinite index in F × , though δ δ δ F (T ) = δ δ δ F (F × ).

Coarse dimension and transformal transcendence degree

In the following, we will try to understand whether there are some algebraic properties of difference fields that are intrinsic to the coarse dimension δ δ δ F . Let us start with an observation. Given (

F, Frob) = (F p kp , Frob p )/U ∈ S. Let ( F , Frob) := p∈P ( Fp , Frob p )/U, then ( F , Frob
) is a model of ACFA, which contains (F, Frob) as a substructure.

In ACFA, there is a notion of dimension which is also integer-valued, and it is induced by SU-rank.

Let k be a saturated model of ACFA.

Definition 15. Let a be a finite tuple in k and A ⊆ k. Then SU (a/A) = ω • k + n for some 0 ≤ k ≤ |a|. Define the rank-dimension dim rk of tp(a/A) as dim rk (a/A) := k.

Remark: dim rk (a/A) coincides with the transformal transcendence degree of a over A σ (the difference field generated by A).

Now we have two integer-valued additive dimensions on definable sets: dim rk and the coarse dimension δ δ δ F . Note further that dim rk (F ) = δ δ δ F (F ) = 1 and dim rk (Fix(F )) = δ δ δ F (Fix(F )) = 0. It is natural to ask whether they coincide on all definable sets.

One of the inequalities is obvious.

Lemma 16. Let (F, Frob) ∈ S. For any tuple a ∈ F and subset A ⊆ F we have δ δ δ F (a/A) ≤ dim rk (a/A).

Proof. Note that by the additivity of both dim rk and δ δ δ F , we only need to prove the inequality when a is a single element. We may assume that A = A σ . By [START_REF] Chatzidakis | Model theory of difference fields[END_REF], we know that SU (a/A) = ω if and only if a is transformally transcendental over A if and only if

deg σ (a/A) = ∞. Therefore, we need to show that if deg σ (a/A) < ∞ then δ δ δ F (a/A) = 0. Suppose deg σ (a/A) < ∞.
Then there is some m and a non-trivial polynomial f (x; y 1 , . . . , y m ) with parameters in A, such that f (σ m (a); σ m-1 (a), . . . , a) = 0. Take any prime p ∈ P and let

g p (x) := f (x p m ; x p m-1 , . . . , x). Then |g p (F p kp ) = 0| ≤ p C•m for some constant C depending on f . Let ϕ(x) := f (σ m (x); σ m-1 (x), . . . , x) = 0. Then ϕ(x) defines exactly the set g p (F p kp ) = 0 in (F p kp , Frob p ). Therefore, δ δ δ F (ϕ(F )) = 0. As a ∈ ϕ(F ), we get δ δ δ F (a/A) = 0.
We conjecture that in general the two dimensions coinside. But at the moment, we can only prove the case for existential formulas. To prove this, we will use the estimation of the number of solutions of formulas in ACFA, which is given in [START_REF] Ryten | Acfa and measurability[END_REF] based on Hrushovski's twisted Lang-Weil estimate.

Definition 17. Let ϕ(x) be a difference formula with parameters A. We define deg σ (ϕ(x)) := max{deg σ (a/A σ ) : ϕ(a) holds}.

Remark: Given a formula ϕ(x, y), seen as a family of definable sets parametrised by the variable y, by [4, Section 7], the set {y : deg σ (ϕ(x, y)) = d} is definable.

Fact 18. [11, Theorem 1.1] and [12, Theorem 2.1.1] Let K q := ( Fp , Φ q : x → x q ) where q is a power of the prime number p. Let ϕ(x, y) be a formula in the language of difference rings, with x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y m ). Then there is a positive constant C and a finite set D of pairs (d, µ) with D ⊆ Z and µ ∈ Q + , such that in each field K q and each y 0 ∈ K m q , one of the following happens:

1. There are some (d, µ) ∈ D such that deg σ (ϕ(x, y 0 )) = d, and we have the estimate

||ϕ(K n q , y 0 )| -µq d | ≤ Cq d-1 2 . 2. deg σ (ϕ(x, y 0 )) = ∞ and |ϕ(K n q , y 0 )| = ∞.
Lemma 19. Let a be a tuple in F and A ⊆ F . Suppose the coarse dimension δ δ δ F (a/A) is witnessed by an existential formula, that is, there is some formula ∃yψ(x, y) with ψ(x, y) quantifier-free (possibly with parameters), such that δ δ δ F (∃yψ(F |x| , y)) = δ δ δ F (a/A) and ∃yψ(x, y) ∈ tp(a/A). Then δ δ δ F (a/A) = dim rk (a/A).

Proof. We can write a = a 1 a 2 where δ δ δ F (a/A) = δ δ δ F (a 1 /A) = |a 1 |. Suppose that (F, Frob) |= ϕ(a 1 , a 2 , a ) with a ⊆ A witnesses the coarse dimension of a over A and that ϕ(x 1 , x 2 , y) := ∃zψ(x 1 , x 2 , y, z), where ψ(x 1 , x 2 , y, z) is quantifier-free. We claim that δ δ δ

F (ϕ(a 1 , F |x 2 | , a )) = 0. If not, then let b ∈ F |x 2 | such that (F, Frob) |= ϕ(a 1 , b, a ) and δ δ δ F (b/a , a 1 ) = δ δ δ F (ϕ(a 1 , F |x 2 | , a )) > 0. Then δ δ δ F (a 1 , b/a ) = δ δ δ F (a 1 /a ) + δ δ δ F (b/a , a 1 ) > δ δ δ F (a 1 /a ) = δ δ δ F (a/a ). Since (F, Frob) |= ϕ(a 1 , b, a ), we get δ δ δ F (ϕ(F |x 1 x 2 | , a )) ≥ δ δ δ F (a 1 , b/a ) > δ δ δ F (a/a
). This contradicts our assumption that ϕ(x 1 , x 2 , a ) witnesses δ δ δ F (a/a ). By Lemma 16, we have Suppose a = (a p ) p∈P /U and b = (b p ) p∈P /U. Let ϕ p (x, y) be defined as in Definition 7. As δ δ δ F (a/A) = 0, by our construction, there is some V in the ultrafilter U which has the following property: for all p ∈ V , there is a constant C p such that for all k with b p ∈ F p k , we have

|a 1 | = δ δ δ F (a 1 /a ) ≤ dim rk (a 1 /a ) ≤ |a 1 |. Therefore, dim rk (a 1 /a ) = δ δ δ F (a 1 /a ) = δ δ δ F (a/
|ϕ p (F p k , b p )| ≤ C p .
We claim that |ϕ p ( Fp , b p )| ≤ C p . Suppose not, then take {a 0 , a 1 , . . . , a Cp } ⊆ ϕ p (( Fp ) |x| , b p ). As ϕ(x, y) is existential, so is ϕ p (x, y). We may suppose ϕ p (x, y) = ∃zψ p (x, y, z). For each a i , pick some e i ∈ ( Fp ) |z| such that Fp |= ψ p (a i , b p , e i ). Let F p k be a large finite field contains all the points {a 0 , . . . , a Cp , e 0 , . . The previous Lemma says essentially that if a set is definable by a pure existential formula, then all the elements of maximal coarse dimension, the "generic elements", can be controlled by their quantifier-free type. It would be nice to also have some control over those "non-generic" elements. It turned out that this can be done.

Lemma 20. Let ϕ(x) := ∃yψ(x, y) be an L σ -formula such that ψ(x, y) is quantifier-free with parameters in the finite set A ⊆ F . Then for any a ∈ F |x| with (F, Frob) |= ϕ(a), we have dim rk (a/A) ≤ δ δ δ F (ϕ(F |x| )).

Proof. Let n be the length of the tuple x in ϕ(x). Suppose a ∈ F n and (F, Frob) |= ϕ(a). Denote the set of complete quantifier-free n-types over A as S qf n (A). Hence, there is some p ∈ S qf n (A) such that (F, Frob) |= ϕ(a) ∧ p(a). Clearly,

t := δ δ δ F ({ϕ} ∪ p) := min{δ δ δ F (ψ(F n ) ∧ ϕ(F n )) : ψ ∈ p} ≤ δ δ δ F (ϕ(F n )).
By the extension property (every partial type extents to a complete type of the same coarse dimension) and ω-saturation of (F, Frob), there is some a ∈ F n such that

δ δ δ F (a /A) = δ δ δ F ({ϕ} ∪ p) = t. Hence, δ δ δ F (a /A) = δ δ δ F (ϕ(F n ) ∧ ψ(F n )) for some ψ(x) ∈ p.
As p is quantifier-free, by Lemma 19, we have dim rk (a /A) = t. Since a and a have the same quantifier-free type p over A, we must have

dim rk (a/A) = dim rk (a /A) = t ≤ δ δ δ F (ϕ(F n )).
This partial connection between dim rk and δ δ δ F already can help us to establish more properties of (F, Frob). The strategy is the following: we start with a definable object in (F, Frob). If we have the control over dim rk of elements in it, then we work in ( F , Frob). As it is a model of ACFA, we can use all the model theoretic tools there. In the end, we transfer the results in ( F , Frob) back to those in (F, Frob).

Fact 21. Let (k, σ) be a model of ACFA. Let G be a definable subgroup of some algebraic group H(k). Let acl σ denote the algebraic closure in ACFA. Suppose G is definable over E = acl σ (E). Then G is contained in a group G which is quantifier-free definable over E and has the same SU-rank as G.

Remark: This statement can be found in [3, Section 6.5]. Notation: For a difference formula ϕ(x) with parameters in A ⊆ ( F , Frob). Let

d = max{n ≤ |x| : SU (a/A) = ω • n + m, for some a ∈ ϕ(( F ) |x| )}.
We define dim rk (ϕ(x)) := d. Lemma 22. Let (F, Frob) ∈ S. Given a ∈ F n and A ⊆ F . Suppose dim rk (a/A) = k. Then there is a finite set {P 1 (x), . . . , P m (x)} of difference polynomials with parameters in A such that (F, Frob) |= i≤m P i (a) = 0 and dim rk ( i≤m P i (x) = 0) = k.

Proof. We may write a into two parts a 1 and a 2 where dim rk (a 1 /A) = |a 1 | = k, and dim rk (a 2 /Aa 1 ) = 0. Let (Aa 1 ) σ be the difference field generated by A ∪ {a 1 }. Suppose

a 2 := a 1 2 • • • a m 2 with each |a i 2 | = 1. Since dim rk (a i 2 /Aa 1 ) = 0 for each i ≤ m, we get deg σ (a i 2 /(Aa 1 ) σ ) < ∞. Therefore, there is a difference polynomial P i (y i , b i ) with b i ⊆ (Aa 1 ) σ such that a i 2 vanishes on it. Write b i = f i (a 1 )
where f i is a difference polynomial with parameters in A. We should rearrange the order of variables such that x 0 , . . . , x |a|-1 corresponds to the order of a. Suppose

a 1 = a l 1 • • • a l |a 1 | and a 2 = a t 1 • • • a t |a 2 |
where a j is the j th digit of a. Now it is easy to see that a satisfies the formula

i≤m P i (x t i , f i (x l 1 , . . . , x l |a 1 | )) = 0, and dim rk ( i≤m P i (x t i , f i (x l 1 , . . . , x l |a 1 | )) = 0) = k.
Corollary 23. Let (F, Frob) ∈ S. Suppose G is a definable (possibly with parameters in F ) subgroup of some algebraic group H(F ) ⊆ F t . If G is defined by some existential formula, then there is a quantifier-free definable group Ḡ ≥ G (defined with parameters in F ), such that δ δ δ F ( Ḡ) = δ δ δ F (G).

Proof. Suppose G is defined over the finite set A ⊆ F with the formula ϕ G . Let k := δ δ δ F (G).

Let Π A be the set of difference polynomials in t-variables with coefficients in A.

By Lemma 22, for any element a ∈ G, there are some {P a,i (x) :

1 ≤ i ≤ m a } ⊂ Π A such that (F, Frob) |= i≤ma P a,i (a) = 0 and dim rk ( i≤ma P a,i (x) = 0) = dim rk (a/A). By Lemma 20, dim rk (a/A) ≤ δ δ δ F (G) = k.
Therefore, ϕ G (x) |= a∈G ( i≤ma P a,i (x) = 0). (The right hand-side is a countable disjunction, since P a,i (x) = 0 are in L σ ∪ {A} and A is a finite set.) By compactness, there is some finite set a 0 , . . . , a l such that

ϕ G (x) |= j≤ ( i≤ma j P a j ,i (x) = 0). As dim rk ( i≤ma j P a j ,i (x) = 0) ≤ k for each j ≤ , we get dim rk ( j≤ ( i≤ma j P a j ,i (x) = 0)) ≤ k.
Write the formula j≤ ( i≤ma j P a j ,i (x) = 0) into the conjunctive normal form u≤N v≤Mu

(P u,v (x) = 0),
for some natural numbers N, M u , and each P u,v (x) ∈ {P a j ,i (x) : j ≤ , i ≤ m a j }. Hence, for each u ≤ N , we have ϕ G (x) |= ( v≤Mu P u,v (x)) = 0. Let G F be closure of G under the σ-Zariski topology in ( F , Frob), that is, if we define I F (G) = {p ∈ F [x] σ : p(g) = 0 for all g ∈ G}, then

G F := {h ∈ H( F ) : p(h) = 0 for all p ∈ I F (G)}.
As prime σ-ideals are finitely generated, G F is quantifier-free definable. Note that

v≤Mu P u,v (x) ∈ I F (G) for each u ≤ N . Since dim rk ( u≤N ( v≤Mu P u,v (x) ) = 0 ) = dim rk ( j≤ ( i≤ma j P a j ,i (x) = 0) ) ≤ k, we get dim rk (G F ) ≤ k.
Take an automorphism δ of ( F , Frob) fixing

F . Then G = δ(G) ⊆ δ(G F ). As δ(G F ) is also closed under the σ-Zariski topology in ( F , Frob), we get G F ⊆ δ(G F ) which implies G F = δ(G F ).
Therefore, G F is invariant under automorphisms fixing F , hence it is definable over F . Let E = acl σ (F ) = F alg , then by Fact 21, there is G E which contains G F , has the same SU -rank as G E and is quantifier-free definable over E. In fact, G E is the smallest closed set containing G F in the σ-Zariski topology in (F alg , Frob F alg ).

Suppose G E is defined by 0≤j≤ P j (x, σ(x), . . . , σ m (x), a j ) = 0, where P j are polynomials in the language of rings and a j ⊆ F alg . For any 0 ≤ j ≤ , let {a 0 j , . . . , a N j j } ⊆ (F alg ) |a j | be the set of all field conjugates of a j over F . Note that for any g ∈ G we have g, σ(g), . . . , σ m (g) ⊆ F . Hence, P j (g, σ(g), . . . , σ m (g), a j ) = 0 if and only if P j (g, σ(g), . . . , σ m (g), a i j ) = 0 for any g ∈ G and 0 ≤ i ≤ N j . Let B j be the set in H( F ) vanishing on {P j (x, σ(x), . . . , σ m (x), a i j ) : 0 ≤ i ≤ N j }. Then from the above argument, we know B j ⊇ G. As B j is closed under the σ-Zariski topology in ( F , Frob), we get B j ⊇ G F . Similarly, by B j being closed under the σ-Zariski topology in (F alg , Frob F alg ), we get B j ⊇ G E . Now consider the following formula 0≤j≤ 0≤i≤N j P j (x, . . . , σ m (x), a i j ) = 0.

It defines j≤ B j . By the argument above, we know that j≤ B j ⊇ G E . Clearly, we also have j≤ B j ⊆ G E . Hence, the formula above also defines G E in H( F ). Now we show that G E can be made quantifier-free definable over F . Fix 0 ≤ j ≤ , consider the formula 0≤i≤N j P j (x, x 1 , . . . , x m , a i j ) = 0, where x 1 , . . . , x m are distinct tuples of variables all have the same length as x. For 1 ≤ k ≤ N l + 1, let e k (t 0 , . . . , t N j ) be the k-elementary symmetric polynomials in N j + 1-variables, i.e., e k (t 0 , . . . , t N j ) :=

0≤i 1 <•••<i k ≤N j t i 1 • • • t i k .
Then we have 0≤i≤N j P j (x, x 1 , . . . , x m , a i j ) = 0 if and only if

1≤k≤N j +1
e k (P j (x, x 1 , . . . , x m , a 0 j ), . . . , P j (x, x 1 , . . . , x m , a

N j j ) = 0.
For each 1 ≤ k ≤ N j + 1, as {a i j : 0 ≤ j ≤ N j } is the set of all field conjugates of a j in F alg over F and that e k is symmetric, we get Q k j (x, . . . , x m , b k j ) := e k (P j (x, x 1 , . . . , x m , a 0 j ), . . . , P j (x, x 1 , . . . , x m , a

N j j )
is invariant under field automorphisms Gal(F alg /F ). Therefore, b k j ⊆ F (since F is perfect).

Let ϕ H (x) be the quantifier-free formula with parameters in A that defines the algebraic group H. Now consider

ψ(x) := ϕ H (x) ∧ ( 0≤j≤ 1≤k≤N j +1 Q k j (x, σ(x), . . . , σ m (x), b k j )).
It is easy to see that ψ(x) defines G E in ( F , Frob). As ψ(x) is quantifier-free and defined over F , we can consider Ḡ := {g ∈ F t : (F, Frob) |= ψ(g)}. As H(F ) is an algebraic group and F is definably closed in F in the language of rings, Ḡ is a quantifier-free definable group in (F, Frob) and contains G.

Note that dim rk (G E ) = dim rk (G F ) ≤ k. Hence, δ δ δ F ( Ḡ) ≤ dim rk (ψ(x)) = dim rk (G E ) ≤ k. On the other hand, since Ḡ ⊇ G and δ δ δ F (G) = k, we get δ δ δ F ( Ḡ) ≥ k. Therefore, δ δ δ F ( Ḡ) = δ δ δ F (G) = k.

Non-tameness

This section investigates whether this family of difference fields is tame in terms of Shelah's classification. It turns out that the answer is negative.

In the following, we will prove that if a structure expands a pseudofinite field with a "logarithmically small" definable subset, then the theory has TP2 and the strict order property and is not decidable. This result is known among experts. As we could not find a proof in the literature, we include it here for completeness.

The proof is based on the result that the theory of pseudofinite fields has the independence property in [START_REF] Duret | Les corps faiblement algébriquement clos non séparablement clos ont la propriété dindépendance[END_REF]. The strategy is to modify Duret's proof to show that when a pseudofinite set is very small compared to the size of the field, then every pseudofinite subset of it can also be coded uniformly.

Fact 24. ([7, Proposition 4.3]) Let k is a field and p a prime different from char(k) such that k contains a p th -root of unity. Let k be the algebraic closure of k. Suppose

f i ∈ k[Y 1 , • • • , Y m ] and F i = X p -f i ∈ k[Y 1 , • • • , Y m , X] for 1 ≤ i ≤ n. If there exist g i , h i ∈ k[Y 1 , • • • , Y m ] and q i ∈ N such that: • for all i, f i = g q i i h i ; • for all i, g i is prime in k[Y 1 , • • • , Y m ]
• for all i = j, g i = g j

• for all i and j, g i does not divide h j

• for all i, p does not divide q i .

Then the ideal J in k[Y 1 , • • • , Y m , X 1 , • • • , X n ] generated by {F i (X i ) : 1 ≤ i ≤ n} is absolutely prime, and does not contain any non-zero element in k[Y 1 , • • • , Y m ].
Fact 25. ([2, Theorem 7.1]) Let V ⊆ ( Fq ) n be an absolutely irreducible F q -variety of dimension r > 0 and degree δ. If q > 2(r + 1)δ 2 , then the following estimate holds:

||(V ∩ (F q ) n )| -q r | ≤ (δ -1)(δ -2)q r-1 2 + 5δ 13 3 q r-1 .
Theorem 26. Let F = i∈I F p i n i /U be a pseudofinite field and A = i∈I A i /U a infinite pseudofinite subset of F . Suppose there is a constant C such that |A i | ≤ Cn i for any i ∈ I. Then all pseudofinite subsets of A are uniformly definable.

Proof. Consider the finite algebraic extension F of F of degree 14C. As F is pseudofinite, there is only one such extension and is definable. To see the definability, suppose F = F (α). Let f be the minimal polynomial of α over F . Then we can define F as the 14C-dimensional vector space over F with multiplication defined according to the minimal polynomial f . We distinguish two cases according to p i . Suppose p i = 2. Since x p 14Cn i i -1 = 1 for all x ∈ F p 14Cn i i , the square root of unity exists in F p 14Cn i i . As the multiplicative group of F p 14Cn i i is cyclic, take δ i ∈ F p 14Cn i i a generator, then δ i is not a square in F p 14Cn i i .

Claim 27. Let ϕ(y, u) be the formula:

∃x(x 2 = y + u).
Then for all i ∈ I with p i = 2 and for all C i ⊆ A i , there is y i ∈ F p 14Cn i i such that

C i = ϕ(y i , F p 14Cn i i ) ∩ A i . Proof. Given i ∈ I with p i = 2 and C i ⊆ A i . Let J be the ideal in F p 14Cn i i [X 1 , • • • , X t i , Y ] generated by {X 2 j -(Y + c j ) : c j ∈ C i } ∪ {X 2 j -δ i (Y + d j ) : d j ∈ A i \ C i },
where δ i is a generator of F * p 14Cn i i as defined before. Let V (J) be the corresponding

F p 14Cn i i
-variety. Then V (J) is absolutely irreducible by Fact 24, Suppose V (J) ∩ (F p 14Cn i i

) t i +1 = ∅. Let (x 1 , • • • , x t i , y i ) be a solution. Then clearly C i ⊆ ϕ(y i , F p 14Cn i i
). On the other hand, if there is d ∈ A i \ C i , such that ϕ(y i , d). Then there are x j , x ∈ F p 14Cn i i such that:

x 2 j = δ i (y i + d); x 2 = y i + d; y i -d = 0,
where the last inequality follows from Fact 24 since Y -d ∈ J) Hence, δ i = (x j /x) 2 , contradicting that δ i is not a square root. Therefore,

C i = ϕ(y i , F p 14Cn i i ) ∩ A i .
So we only need to show V (J) ∩ F p 14Cn i i = ∅.

Let |A i | = t i ≤ Cn i .
We calculate the dimension and the degree of V (J). It is clear that the dimension of V (J) is 1, as all X j are algebraic over Y . Let c 1 , • • • , c t i be a list of elements in A i . And for 1 ≤ j ≤ t i , let V j be the variety defined as the set of solutions of X 2 j -(Y + c j ) if c j ∈ C i , and of X 2 j -δ i (Y + c j ) if c j ∈ C i . Then V (J) = 1≤j≤t i V j and each V j has degree 2. Therefore, by the Bézout inequality, the degree of V (J) is less than or equal to 2 t i .

Proof. For each

i ∈ I, pick Y i ⊆ B i such that |B i | 1 4 ≤ |Y i | ≤ |B i | 1 3 . Let Y = i∈I Y i /U.
By Theorem 26, Y is definable and all subsets of Y i are uniformly definable by some ψ 1 (y, u). For each i ∈ I, consider the set

Y i -Y i Y i -Y i := { y 1 -y 2 y 3 -y 4 : y 1 , y 2 , y 3 , y 4 ∈ Y i , y 3 = y 4 }.
It has size at most

|Y i | 4 << |F p n i i |. Take any a ∈ Y i -Y i Y i -Y i ∪ {0}.
Then the set T i := {y 1 + ay 2 : y 1 , y 2 ∈ Y i } is in definable bijection with Y i × Y i and of size less than n i . By Theorem 26, all subsets of T i , hence of Y i × Y i , are uniformly definable by some ψ 2 (y, u). Similarly, we can show that all subsets of Y i × Y i × Y i are uniformly definable by some ψ 3 (y, u).

We may assume that all subsets of Y i (and

Y i × Y i , Y i × Y i × Y i ) can be defined uniformly by parameters in F p n i i . For a ∈ F p n i i , we write S 1 a ⊆ Y i for the set ψ 1 (a, F p n i i ) and S 2 a ⊆ Y i × Y i , S 3 a ⊆ Y i × Y i × Y i for ψ 2 (a, F p n i i ), ψ 3 (a, F p n i i ) respectively. Now define a relation R + ⊆ (F p n i i ) 3 by: R + (a, b, c) if there exist g ∈ F p n i i and y = y ∈ Y i such that • either S 3 g is the graph of a bijective function from (S 1 a × {y}) ∪ (S 1 b × {y }) to S 1 c ; • or S 1 c = Y i and S 3 g is the graph of a surjective function from (S 1 a ×{y})∪(S 1 b ×{y }) to Y i ; Similarly, we define R × ⊆ (F p n i i ) 3 by: R × (a, b, c) if there exists g ∈ F p n i i such that • either S 3
g is the graph of a bijective function from S 1 a × S 1 b to S 1 c ;

• or S 1 c = Y i and S 3 g is the graph of a surjective function from S 1 a × S 1 b to Y i ;

We also define an equivalence relation E ⊆ (F p n i i ) 2 by: E(a, b) if and only if there exists g ∈ F p n i i such that S 2 g is the graph of a bijective function from S 1 a to S 1 b . It is easy to see then that R + , R × respect the equivalence relation E and

(|Y i |, +, ×) ((F p n i i ) 2 /E, R + /E, R × /E).
Corollary 30. Let (F, Frob) ∈ S and T := T h(F, Frob). Then T has the strict order property and TP2. Moreover, T is not decidable.

Proof. As the fixed field Fix(F ) := {x ∈ F : σ(x) = x} is definable and satisfies the condition in Theorem 26, every pseudofinite subset of Fix(F ) can be coded uniformly by some formula ϕ(x, t). In particular, it will code some infinite strictly increasing chain A 1 A 2 A 3 • • • of subsets of Fix(F ). Therefore, T has the strict order property.

Let ϕ(x, t) be the same formula. To see that T has TP2, by compactness, we only need to show that given any n ∈ N, there is some (a ij ) 1≤i,j≤n such that for any 1 ≤ i ≤ n, we have {ϕ(x, a ij ) : 1 ≤ j ≤ n} is 2-inconsistent and {ϕ(x, a if (i) ) : 1 ≤ i ≤ n} is consistent for any f : {1, . . . , n} → {1, . . . , n}.

Given n ∈ N, let A n ⊆ Fix(F ) be a set with n n -many elements. Fix a bijection η : A n → {1, . . . , n} {1,...,n} where {1, . . . , n} {1,...,n} is the set of all functions from {1, . . . , n} to itself. Let (a ij ) 1≤i,j≤n be such that ϕ(x, a ij ) codes the set

B ij := {a ∈ A n : η(a)(i) = j} ⊆ A n .
For any 1 ≤ i ≤ n, as B i1 , . . . , B in form a complete partition of A n , we get {ϕ(x, a ij ) : 1 ≤ j ≤ n} is 2-inconsistent. On the other hand, for any f : {1, . . . , n} → {1, . . . , n} the element η -1 (f ) ∈ A n witnesses that {ϕ(x, a if (i) ) : 1 ≤ i ≤ n} is consistent.

As (F, Frob) interprets ultraproducts of initial segments of natural numbers with truncated addition and multiplication by Corollary 30, the undecidability follows from [10, Section 4].

The following part concerns the algebraic closure in (F, Frob) ∈ S. Let F be a pseudofinite field and F alg be the smallest algebraically closed field containing F . Take a tuple a ∈ F . Then the algebraic closure in the pseudofinite field acl F (a) is simply the algebraic closure in F alg intersected with F , i.e., acl (a) = acl F alg (a) ∩ F .

As ACFA is the model companion of the theory of difference fields, we can embed (F, Frob) into some (K, σ) |= ACF A. We might wonder if similarly, the algebraic closure in the theory of (F, Frob) is the same as the algebraic closure in (K, σ) intersected with F . But the answer is negative. In fact, we have the following.

Lemma 31. For any n > 0, there is some (F, Frob) ∈ S and element a n ∈ F such that a n is in the definable closure of tuple b n in (F, Frob), but deg σ (a n /b n ) = n.

We need a small lemma first. There is C n ∈ R such that for any F q with char(F q ) = 2 and b 1 , • • • , b n distinct nelements in F q , we have

||ϕ(F q , b 1 , • • • , b n )| - q 2 n | ≤ C n • q 1 2 .
Proof. Given distinct elements b 1 , • • • , b n ∈ F q . Take an element a ∈ F q such that b is not a square. Let J be the ideal in F q [X, X 1 , • • • , X n ] generated by

{X 2 1 -(X + b 1 )} ∪ {X 2 i -a(X + b i ) : 2 ≤ i ≤ n}.
By Fact 24, J is absolutely prime, whence V (J) is an absolutely irreducible variety. By the Lang-weil estimate

||V (J) ∩ (F q ) n+1 -q| ≤ N n • q 1 2 ,
where N n is a constant only depends on the degree and dimension of the variety, which in our case is independent with b 1 , • • • , b n , a and F q and only depends on n. Let π : V (J) ∩ (F q ) n+1 → F q be the projection on the the first coordinate. Clearly, π is a 2 n -to-one function. Therefore,

|ϕ(F q , b 1 , • • • , b n )| = |π(V (J) ∩ (F q ) n+1 )| = 1 2 n • |V (J) ∩ (F q ) n+1 |.
Let C n := Nn 2 n . We conclude that

||ϕ(F q , b 1 , • • • , b n )| - q 2 n | ≤ C n • q 1 2 .
Now we prove Lemma 31.

Proof. Given n ∈ N, for each p ∈ P, let k p ∈ N be such that

• k p > max{f (p, p), 14p n } where f (p, p) is given by Equation 1;

• n! divides k p ;

• p kp 2 p n > 2C p n • p Take an element b n ∈ Y n such that δ δ δ F (b n ) > 0. Note that a n ∈ dcl(b n ) and δ δ δ F (a n ) = 0. Thus,

δ δ δ F (b n /a n ) = δ δ δ F (a n , b n ) -δ δ δ F (a n ) = δ δ δ F (b n ) + δ δ δ F (a n /b n ) -δ δ δ F (a n ) = δ δ δ F (b n ) > 0.
Therefore, SU ACF A (b n /a n ) = ω. By our choice, we also have SU ACF A (b n ) = ω. Hence, a n is independent with b n in ( F , Frob). Again, by our choice, deg σ (a n ) = n. But if deg σ (a n /b n ) < n, then a n and b n will not be independent in ( F , Frob) in the theory of ACFA. We conclude that deg σ (a n /b n ) = n and a n is in the definable closure of b n .

  {y ∈ M n+1 : δ δ δ M (ψ(M n+1 , y)) = t and ψ(M n+1 , y) = ∅} for any t ∈ {0, . . . , r • (n + 1)}. Lemma 12. Let M = (F, +, •, 0, 1, . . .) be a pseudofinite field with some extra structures. Let δ δ δ F be the pseudofinite coarse dimension normalised by |F |. Suppose for any formula ϕ(x, y) with |x| = 1 we have δ δ δ F (ϕ(F, b)) ∈ {0, 1} for any tuple b ∈ F |y| . Then δ δ δ F is definable and for any formula ψ(x, y) and any tuple c ∈ F |y| , we have δ δ δ F (ψ(F |x| , c)) ∈ {0, . . . , |x|}. Proof. By Corollary 11, we only need to show definability when |x| = 1.

  a ). To show that dim rk (a/a ) = δ δ δ F (a/a ), we only need to show that dim rk (a 2 /a , a 1 ) = 0. Therefore, we need to prove the following claim:Let ϕ(x, b) (with b ∈ F a tuple) be an existential formula in the language of diffence rings such that δ δ δ F (ϕ(x, b)) = 0. Then for any tuple a ∈ F with (F, Frob) |= ϕ(a, b), we have deg σ (a/b) < ∞.

  . , e Cp , b p }, then we have card(ϕ p (F p k , b p )) ≥ C p + 1 > C p , contradiction. Let K p := ( Fp , Φ p : x → x p ). Note that ϕ p ( Fp , b p ) is exactly the set ϕ(K p , b p ). Then by Fact 18 and that |ϕ(K p , b p )| = |ϕ p ( Fp , b p )| < ∞ for each b p , we get a finite set D of pairs (d, µ) ∈ N × Q + such that for any b p , there is some (d, µ) ∈ D and the following holds: ||ϕ(K p , b p )| -µp d | ≤ Cp d-1 2 . Therefore, there is some J ∈ U and one particular pair (d, µ) ∈ D such that for any p ∈ J, we have |card(ϕ(K p , b p ))-µp d | ≤ Cp d-1 2 . By Fact 18 we know that deg σ (ϕ(x, b p )) = d for any b p ∈ J. By the subsequent remark, we know there is some formula ϕ d (y), such that ϕ d (y) holds if and only if deg σ (ϕ(x, y)) = d in a difference field. Therefore, ϕ d (b p ) holds in each K p with p ∈ J, hence ϕ d (b) holds in ( F , Frob). As ϕ(x, y) is an existential formula, (F, Frob) |= ϕ(a, b) implies ( F , Frob) |= ϕ(a, b). We conclude that deg σ (a/b) ≤ deg σ (ϕ(x, b)) = d.

Lemma 32 .

 32 Let ϕ(x; y 1 , • • • , y n ) := ∃z(z 2 = x + y 1 ) ∧ 2≤i≤n ∀z¬(z 2 = x + y i ).

kp 2 .p p kp 2 ,

 22 Let (F, Frob) := p∈P (F p kp , Frob p )/U where U is a non-principal ultrafilter on P. Clearly, (F, Frob) ∈ S and Fix(σn ) := {x ∈ F : σ n (x) = x} = Fix(σ k ) for any k < n. Take an element a n ∈ Fix(σ n ) such that deg σ (a n ) = n. Let ξ(x, a n ) := ∃z(z 2 = a n + x) ∧ ∀y(σ n (y) = y ∧ (y = a n → ¬∃z(z 2 = y + x))).As p > 14p n for each p ∈ N, by Theorem 26 and the subsequent remark, we know thatY n := ξ((F, Frob), a n ) = ∅. We claim that δ δ δ F (Y n ) = 1. Suppose a n = (a p ) p∈P /U. For each p ∈ P, let a p , b 1 , • • • , b p n -1 be a list of all elements in F p n ⊆ F p kp . Let ϕ(x, y 1 , • • • , y p n ) := ∃z(z 2 = x + y 1 ) ∧ 2≤i≤p n ∀z¬(z 2 = x + y i ).Note that for any b ∈ F p kp we haveξ((F p kp , Frob p ), a p ) = ϕ(F p k+p , a p , b 1 , • • • , b p n -1 ). By Lemma 32, ||ϕ(F p k+p , a p , b 1 , • • • , b p n -1 )| -p kp 2 p n | ≤ C p n • for all p > 2. Therefore, |Y n | ≥ p kp 2 p n -C p n • p kp /2 • 2 p n ) log p kp = 1,we get δ δ δ F (Y n ) = 1.

  Frob) := p∈P (F p kp , Frob p )/U ∈ S. Then δ δ δ F , the pseudofinite coarse dimension normalised by |F |, is integer-valued on all L σ -definable set .Proof. Let ϕ(x, y) be an L σ -formula. Consider a parameter a = (a p ) p∈P /U ∈ F |y| . For any p ∈ P, we know that there are (d kp , µ kp ) ∈ {0, . . . , |x|} × R >0 and C ϕp ≥ 0 such that for a p ∈ (F p kp ) |y| , we have||ϕ p ((F p kp ) |x| , a p )| -µ kp • p kp•d kp | ≤ C ϕp • p kp(d kp -1 2 ). say that ϕ p (x, a p ) has dimension d kp in F p kp . As d kp ≤ |x|, there is exactly one d ∈ {0, . . . , |x|} with {p ∈ P :ϕ p (x, a p ) has dimension d in F p kp } ∈ U. We claim that δ δ δ F (ϕ(F |x| , a)) = d.Proof of the claim: Note that for any p ∈ P and c ∈ (F p kp ) |x| , we have F p kp |= ϕ p (c, a p ) if and only if (F p kp , Frob p ) |= ϕ(c, a p ). Let I = {p ∈ P : p > |ϕ(x, y)| and ϕ p (x, a p ) has dimension d in F p kp }. Clearly, I ∈ U. Then for any p ∈ I, ||ϕ p ((F p kp ) |x| , a p )| -µ kp • p kp•d | ≤ C ϕp • p kp(d-1 2 ) ,

	Define		N p ϕ(x,y) := max µ,	1 µ	, 2 log p	2C ϕp µ	: µ ∈ E ϕp .
	Let
				f ( , p) := max{N p ϕ(x,y) : |ϕ(x, y)| ≤ }.	(1)
	Definition 8. Define the family S of pseudofinite difference fields as
							
	S :=		(F p kp , Frob p )/U : k p ≥ f (p, p) for all p ∈ P, U a non-principal ultrafilter		.
		 p∈P					
	Theorem 9. Let (F, We and k p ≥ f (p, p) ≥ max{µ kp , 1 µ kp , 2 log p	2Cϕ p µ kp }.
	As k p ≥ 2 log p	2Cϕ p µ kp , we get

  ≤ |ϕ p ((F p kp ) |x| , a p )| ≤ 2k p • p kp•d .

	Obviously, we have
		lim p→∞, p∈I	log |ϕ p ((F p kp ) |x| , a p )| log(p kp )	= d.
	Therefore, δ δ δ F (ϕ(F |x| , a)) = d.
					1 kp < µ kp < k p . Hence,
	1 2k p • p kp•d This implies
	d -	log(2k p ) k p • log p	≤	log |ϕ p ((F p kp ) |x| , a p )| log(p kp )	≤ d +	log(2k p ) k p • log p	.

This author is supported by the China Scholarship Council and partially supported by ValCoMo (ANR-13-BS01-0006).

1 See [12, Lemma 3.3.6].

Suppose, towards a contradiction, that V (J) ∩ (F p 14Cn i i ) t i +1 = ∅. Then by Fact 25,

The case p i = 2 is similar. Since 3 divides 2 14Cn i -1 for each i, there exists x ∈ F 2 14Cn i such that x 3 = 1. Take δ i be the generator of the multiplicative group of F 2 14Cn i . Then there is no y ∈ F 2 14Cn i such that y 3 = δ i .

Claim 28. Let ψ(y, u) be the formula:

Then for all i ∈ I and

As the argument before, the variety V (J) is absolutely irreducible of dimension 1 and of degree less than or equal to 3 t i . To prove the claim, we only need to show that V (J) ∩ (F 2 14Cn i ) t i +1 = ∅. Suppose not, then by Fact 25,

Let A = i∈I A i /U. Assume A is defined by χ(x). Define φ(x, y) := ψ(y, x) ∧ χ(x) if the characteristic of F is 2, and φ(x, y) := ϕ(y, x) ∧ χ(x) otherwise. Let C = i∈I C i /U ⊆ A be any pseudofinite subset. By the previous two claims, there is y C ∈ F such that C = φ(F , y C ) in F . As F is definable in F , let φ (x, ȳ) be the corresponding translation of φ(x, y) in F . Remember that we regard x, ȳ ∈ F as 14C-dimensional vector space over F and A ⊆ F . Let θ(x, ȳ) := φ (x, 0, . . . , 0, ȳ). We see that θ(x, ȳ) codes uniformly all pseudofinite subsets of A.

Remark: From the proof we know that if char(F ) = 2 and n i ≥ 14|A i | for all large enough i, then we can take θ(x, ȳ) := ∃z 2 (z 2 = x + y) ∧ χ(x) where x, y are single variables and χ(x) is the formula defining A.

Corollary 29. Let F = i∈I F p i n i /U be a pseudofinite field and B = i∈I B i /U an infinite pseudofinite subset of F . Suppose there is a constant C such that |B i | ≤ Cn i for all i ∈ I. Then (F, B) interprets the structural N = i∈I (N i , +, ×)/U, where N i = {j ∈ N : 0 ≤ j ≤ m i } for some m i ∈ N, and +, × the addition and multiplication truncated on N i respectively.


An Interval Observer for Discrete-Time SEIR Epidemic Models

Kwassi H. Degue and Jerome Le Ny

Abstract-This paper focuses on designing a state estimator for a discrete-time SEIR epidemic model of an influenzalike illness. It is assumed that only sets of admissible values are known for the model's disturbances, uncertainties and parameters, except for the time-varying transmission rate from the "susceptible" to the "exposed" stage, whose bounding values are unavailable. An interval observer is designed to estimate the set of possible values of the state, and a sufficient condition guaranteeing the asymptotic stability of the proposed estimator is formulated in terms of a linear matrix inequality. The performance of the proposed approach is demonstrated by numerical simulations.

I. INTRODUCTION

Seasonal influenza epidemics usually cause three to five million cases of severe illness and result in about 250,000 to 500,000 deaths worldwide every year, according to the World Health Organization [START_REF] Vaillant | Epidemiology of fatal cases associated with pandemic H1N1 influenza 2009[END_REF]. Infectious disease surveillance plays a major role in analyzing epidemics' causes, dynamics and spread. Public Health Services (PHS) rely on surveillance data collected by agencies such as the Centers for Disease Control and Prevention in the United States to estimate these infectious diseases' activity levels, prepare intervention strategies and design policy recommendations.

Mathematical modelling of epidemics has become an essential part in the sentinel role played by public health response planning and early outbreak detection systems [START_REF] Fallas-Monge | Combinatorial metaheuristics applied to infectious disease models[END_REF]- [START_REF] Kaplan | Emergency response to a smallpox attack: The case for mass vaccination[END_REF]. Kermack and McKendrick proposed the first modern mathematical epidemiology models in [START_REF] Kermack | A contribution to the mathematical theory of epidemics[END_REF]: a Susceptible-Infectious-Recovered (SIR) model was used to model the plague (London 1665-1666, Bombay 1906) and cholera (London 1865) epidemics. The basic SIR model assumes that a fixed population, at any time, can be divided into three compartments: susceptible people (those who are not infected but could become infected), infectious people (those who have the disease and are able to infect others), and recovered people (those who were infected by the disease and are now immune). It is assumed that the total number of people, N , is constant. Homogeneous mixing is also assumed by these models. That is, each individual is equally likely to come in contact with any other [START_REF] Dukic | Tracking epidemics with google flu trends data and a state-space SEIR model[END_REF].

This work was supported by NSERC under Grant RGPIN 435905-13 and by the Fonds de recherche du Québec -Nature et technologies (FRQNT) international internships fellowship (Energy/Digital/Aerospace).

The authors are with the department of Electrical Engineering, Polytechnique Montreal and with GERAD, QC H3T-1J4, Montreal, Canada. kwassi-holali.degue,jerome.le-ny@polymtl.ca

In the case of influenza, one needs to extend the standard SIR model and introduce a fourth compartment corresponding to the disease's latency period, when a person is infected but not yet able to infect others. This extension is called the Susceptible-Exposed-Infected-Recovered (SEIR) model [START_REF] Hethcote | The mathematics of infectious diseases[END_REF]. Several estimators have been previously designed for SEIR models [START_REF] Dukic | Tracking epidemics with google flu trends data and a state-space SEIR model[END_REF], [START_REF] Ibeas | Observer design for seir discrete-time epidemic models[END_REF], [START_REF] Alonso-Quesada | An observer-based vaccination control law for an SEIR epidemic model based on feedback linearization techniques for nonlinear systems[END_REF]. In the existing literature, strong assumptions on the disturbances or uncertain parameters in these models can enable the design of estimators converging to the true state values. However, the problem of observer design for SEIR models becomes very challenging when one has to take into account the presence of disturbances or uncertain parameters whose values are only known to belong to an interval or polytope. Such issues can be addressed by an interval estimation approach [START_REF] Efimov | Control of nonlinear and LPV systems: interval observer-based framework[END_REF]- [START_REF] Efimov | On interval observer design for time-invariant discrete-time systems[END_REF]. Using input-output measurements, an observer has to estimate the set of admissible values (interval) for the state at each instant of time [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF]. A major advantage of interval estimation is that it allows many types of uncertainties to be taken into account in the system [START_REF] Efimov | Design of interval observers for uncertain dynamical systems[END_REF].

This paper presents an interval estimator for a discretetime SEIR epidemic model of an Influenza-Like Illness (ILI). We are interested in estimating the four compartment states, to support the prediction of epidemic outbreaks. An interval observer design was proposed for the first time for an epidemic model in [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF]. However, it applies to SIR rather than SEIR models, and so it does not consider the fourth compartment of the population that corresponds to the incubation stage for diseases such as influenza. Furthermore, it assumes continuous-time dynamics, whereas we focus on discrete-time epidemic models, which have gained substantial importance during the last decade [START_REF] Hu | Stability analysis in a class of discrete sirs epidemic models[END_REF], [START_REF] Mickens | Numerical integration of population models satisfying conservation laws: Nsfd methods[END_REF]. We also assume that the PHS have only access to noisy measurements, whereas [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF] considered that perfect measurements were available. Importantly, [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF] assumed that the time-varying transmission rate β(t) from the "susceptible" to the "exposed" stage is bounded by two functions β(t) and β(t), available to the PHS in real-time. The time-varying observer proposed in [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF] provided accurate results in simulated models, but the transmission rate β(t) is a highly uncertain parameter that cannot be estimated by biological considerations [START_REF] Bichara | On the estimation of sequestered infected erythrocytes in plasmodium falciparum malaria patients[END_REF], [START_REF] Hooker | Parameterizing state-space models for infectious disease dynamics by generalized profiling: measles in Ontario[END_REF] and its bounds are generally unknown in epidemiology models [START_REF] Degue | Interval estimation of sequestered infected erythrocytes in malaria patients[END_REF]. Here, we assume that neither the value of β(t) nor its bounding values are available, which makes the estimation problem more complicated. Finally, [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF] assumed that the recovery rate γ t is constant, whereas in our work it is time-varying and only its interval of admissible values is available. On the other hand, one drawback of our observer is that it is not perfectly causal, namely, it produces state estimates with a delay of two periods. The interval estimation approach described in this paper can be extended to higher/lower order discrete-time epidemic models, when the model has more/less than 4 compartments, such as SEIR and SIR models with several parallel infective stages [START_REF] Korobeinikov | Global properties of SIR and SEIR epidemic models with multiple parallel infectious stages[END_REF].

In Section II, we present the problem statement and some results from interval estimation theory. Section III describes the application of these results to design an interval observer for a discrete-time SEIR epidemic model. Input-to-state stability of the proposed interval observer is also proven in order to guarantee that it has bounded solutions for any bounded input. Finally, numerical simulations demonstrating the performance of the the observer are presented in Section IV.

Notation: The real numbers are denoted by R, the integers by

Z, R + = {τ ∈ R : τ ≥ 0} and Z + = Z ∩ R + . For a vector-valued signal u : Z + → R n , the L ∞ norm ||u|| L∞ is defined as ||u|| L∞ = sup t∈[0,+∞] u t ∞ , where u t ∞ := max i∈{1,...,n} |u t,i |. We denote by L n ∞ the set of such signals u with the property ||u|| L∞ < ∞. We denote the p -norm of a vector x ∈ R k by |x| p := ( k i=1 |x i | p ) 1/p , for p ∈ [1, ∞].
The symbols I n , Λ n×m and Λ p denote the n × n identity matrix and the matrices with all elements equal to 1 and dimensions n × m and p × 1, respectively. For two vectors x 1 , x 2 ∈ R n or matrices A 1 , A 2 ∈ R n×n , the relations x 1 ≤ x 2 and A 1 ≤ A 2 are understood elementwise. The notation P ≺ 0 (P 0) means that the matrix P ∈ R n×n is symmetric and negative (positive) definite. A matrix A ∈ R n×n is called Schur stable if all its eigenvalues have absolute value less than one. It is called nonnegative if all its elements are nonnegative, i.e., if A ≥ 0.

II. PROBLEM STATEMENT AND PRELIMINARY RESULTS

Fig. 1 illustrates the discrete-time SEIR epidemic model, a discretization of the classic influenza continuous-time dynamics proposed in [START_REF] Hethcote | The mathematics of infectious diseases[END_REF]

S t+1 = (1 -µ t )S t -β t S t I t + µ t , E t+1 = (1 -α t -µ t )E t + β t S t I t , (1)
I t+1 = (1 -γ t -µ t )I t + α t E t , R t+1 = (1 -µ t )R t + γ t I t ,
where S t , E t , I t , R t are nonnegative state variables, α : parameter β : Z + → R is highly uncertain and timevarying. Note that we achieve non-dimensionalization by setting the population size N = 1 in the model [START_REF] Vaillant | Epidemiology of fatal cases associated with pandemic H1N1 influenza 2009[END_REF]. It is assumed that all the four compartments experience the same constant death rate, equal to the birth rate µ t . Indeed,

Z + → [α, α] with α > 0, γ : Z + → [γ, γ]
S t+1 + E t+1 + I t+1 + R t+1 = (1 -µ t )(S t + E t + I t + R t ) + µ t = (1 -µ t ) + µ t = 1.
The parameters α t , β t and γ t stand for the time-varying transition rates from one disease stage to the next, while µ t represents the time-varying natural birth and death rate. The disease transmissions that arise from contacts between susceptible and infectious people is described by the first equation of (1). In the original continuous-time SEIR model [START_REF] Hethcote | The mathematics of infectious diseases[END_REF], the pathogen is transmitted by each infectious individual to β individuals per unit time. However, a new disease case occurs only if the contact is made with a susceptible person, with probability S t . Hence, at time t, people in the compartment S migrate to the "susceptible but not yet infectious" compartment E at the rate β t I t . People in compartment E move to the infectious compartment I at the rate α t per unit time, while infectious individuals migrate to the recovered compartment R at the rate γ t per unit time.

The measured output consists of noisy counts of ILI visits at emergency departments

y t = I t + v t , (2)
where v ∈ L ∞ is the measurement noise, with ||v|| L∞ ≤ V for some known V > 0. The dynamics of system ( 1)-( 2) can be rewritten as follows

x t+1 = A t x t + F ζ t + Hµ t , y t = Cx t + v t , (3)
where

x t = S t E t I t R t T ∈ R 4
+ is the state vector and ζ t := β t S t I t is an uncertain input. In contrast to [START_REF] Gucik-Derigny | A note on interval observer design for unknown input estimation[END_REF] and [START_REF] Robinson | Interval observer design for unknown input estimation of linear time-invariant discrete-time systems[END_REF], the matrix A t is time-varying in this paper. Moreover, it should be pointed out that only unknown inputs that have no impact on the output are considered in [START_REF] Robinson | Interval observer design for unknown input estimation of linear time-invariant discrete-time systems[END_REF]. Since the uncertain input of (3) can be rewritten as ζ t = β t S t (y t -v t ), we consider here unknown inputs that affect the output. The time-varying matrix A t and constant matrices C, F and H are defined as follows

C = 0 0 1 0 , F = -1 1 0 0 T , H = 1 0 0 0 T , A t =     1 -µ t 0 0 0 0 1 -α t -µ t 0 0 0 α t 1 -µ t -γ t 0 0 0 γ t 1 -µ t     .
For different ILIs, the values of the parameters α t , β t and γ t are different and vary with time for a patient. No given confidence interval is assumed for β t . The instant value of A t is also unavailable, but we have the the bounds

A ≤ A t ≤ A, ∀t ≥ 0, for A =     1 -µ 0 0 0 0 1 -α -µ 0 0 0 α 1 -γ -µ 0 0 0 γ 1 -µ     , A =     1 -µ 0 0 0 0 1 -α -µ 0 0 0 α 1 -γ -µ 0 0 0 γ 1 -µ     .
The goal of this paper is to design an interval observer, i.e., state signal bounds x t ≤ x t ≤ x t , which can contribute to design a decision rule for disease outbreak detection in an interval approach framework. Note that at the disease-free equilibrium (when I t = 0), the system (1) is detectable, but not observable (we refer the reader to [START_REF] Sontag | Output-to-state stability and detectability of nonlinear systems[END_REF] for the definition of detectability of nonlinear systems). An advantage of interval observers is that they can be designed even if the system is only detectable. Next, we review some basic facts from the theory of interval estimation.

A. Interval relations

Given a matrix A ∈ R m×n , let us define A + = max{0, A} applied elementwise, A -= A + -A (the same for vectors) and denote the matrix of absolute values of all elements by |A| = A + + A -. Lemma 1. [START_REF] Efimov | Interval estimation for LPV systems applying high order sliding mode techniques[END_REF] Let x ∈ R n be a vector with x ≤ x ≤ x for some x, x ∈ R n . If A ∈ R m×n is a matrix, then

A + x -A -x ≤ Ax ≤ A + x -A -x. (4)

B. Nonnegative discrete-time linear systems

A system

x t+1 = Ax t + Bω t , ω : Z + → R m + , t ∈ Z + , y t = Cx t + Dω t , with x t ∈ R n , y ∈ R p and nonnegative matrices A ∈ R n×n + and B ∈ R n×m +
is called cooperative or nonnegative [START_REF] Hirsch | Systems of differential equations that are competitive or cooperative II: Convergence almost everywhere[END_REF]. Its solution is elementwise nonnegative for all t ∈ Z + provided that x 0 ≥ 0 [START_REF] Hirsch | Monotone maps: a review[END_REF]. Also, the output solution y t of such a system is nonnegative if

C ∈ R p×n + and D ∈ R p×q + . Lemma 2. [30] A matrix A ∈ R n×n +
is Schur stable if and only if there exists a diagonal matrix P with positive diagonal elements such that A T P A -P ≺ 0.

III. INTERVAL OBSERVER DESIGN

In this section we design an interval observer for the SEIR model ( 1)-( 2). We assume here that neither β t nor its bounding values are available, which makes the estimation problem more complicated than in [START_REF] Bliman | Interval observer for SIR epidemic model subject to uncertain seasonality[END_REF] but more realistic [START_REF] Degue | Interval estimation of sequestered infected erythrocytes in malaria patients[END_REF], [START_REF] Bichara | On the estimation of sequestered infected erythrocytes in plasmodium falciparum malaria patients[END_REF], [START_REF] Hooker | Parameterizing state-space models for infectious disease dynamics by generalized profiling: measles in Ontario[END_REF]. First, we determine upper and lower bounds for the uncertain input ζ t . Next we design an interval observer for the system (1)-( 2). We prove the inclusion relation 0 ≤ x t ≤ x t ≤ x t , ∀t ≥ 0, and the asymptotic stability of the error bounds. Finally, the boundedness of the interval observer's solutions is proven.

Using equation ( 3), one can write

y t+2 = Cx t+2 + v t+2 , = CA t+1 A t x t + CA t+1 F ζ t + CF ζ t+1 + CA t+1 Hµ t + CHµ t+1 + v t+2 ,
so that we have

CA t+1 F ζ t = -CA t+1 A t x t -CF ζ t+1 -CHµ t+1 -CA t+1 Hµ t -v t+2 + y t+2 .
The structure of the model ( 1)-( 2) implies that CF = 0, CA t+1 H = 0 and CA t+1 F = α t+1 . Hence, we have

α t+1 ζ t = y t+2 -CA t+1 A t x t -v t+2 . Suppose 0 ≤ x t ≤ x t ≤ x t , ∀t ≥ 0, for some x t , x t ∈ R 4 . Notice that A t+1 A t -A t+1 A t ≥ 0, A t+1 A t -A t+1 A t ≥ 0 with A t+1 A t = A 2 and A t+1 A t = A 2 .
Hence using the inequality (4) of Lemma 1, we get the following relations for all t ≥ 0

(A 2 ) + x t -(A 2 ) -x t ≤ A 2 x t ≤ A t+1 A t x t and A t+1 A t x t ≤ A 2 x t ≤ (A 2 ) + x t -(A 2 ) -x t .
We then obtain the following relations

ζ t ≤ ζ t ≤ ζ t ,
for all t ≥ 0, where

ζ t = α -1 (y t+2 -V -(CA 2 ) + x t + (CA 2 ) -x t ), ζ t = α -1 (y t+2 + V -(CA 2 ) + x t + (CA 2 ) -x t ).
An interval estimator's equations for (3) takes the form

χ t+1 = Aχ t + F + ζ t -F -ζ t + Hµ t +L(y t -Cχ t ) -L V, χ t+1 = Aχ t + F + ζ t -F -ζ t + Hµ t (5)
+L(y t -Cχ t ) + L V,

x t = max{0, χ t },

x t = max{0, χ t },
where x t ∈ R 4 and x t ∈ R 4 are respectively the lower and the upper interval estimates for the state x t , χ t , χ t ∈ R 4 is the state of ( 5), L and L are some matrices, L = |L|Λ p×1 and L = |L|Λ p×1 .

Assumption 1. There exist matrices L ∈ R 4×1 , L ∈ R 4×1 such that the matrices (A -LC) and (A -LC) are nonnegative.

Assumption 2. The state x(t) is bounded (i.e., x ∈ L 4 ∞ ) for x(0) ∈ [x(0), x(0)], and x(0), x(0) ∈ R 4 are given constants.

We take matrices L and L satisfying Assumption 1 in order to enforce the positivity of the interval observer's error dynamics. Assumption 2 is common in the interval observer design literature and is satisfied here since the state components belong to [0, 1]. Theorem 1. Let Assumptions 1 and 2 be satisfied. Then the estimates x t and x t given by (5) yield the relations

0 ≤ x t ≤ x t ≤ x t ∀t ≥ 0, (6)
provided that 0 ≤ x 0 ≤ x 0 ≤ x 0 .
Proof. Notice that x t ≥ 0 for all t ≥ 0 and x t is also bounded since it represents population proportions. We can rewrite the equation (3) as follows

x t+1 = (A -LC)x t +(A t -A )x t +F ζ t +Hµ t +Ly t -Lv t
for A equal to A or A and L equal to L or L. Hence, the interval observer's errors e t = x t -χ t , e t = χ t -x t satisfy the equations

e t+1 = (A -LC)e t + φ t , e t+1 = (A -LC)e t + φ t , (7)
where

φ t = (A t -A)x t + F ζ t -F + ζ t + F -ζ t -Lv t + L V, φ t = (A -A t )x t + F + ζ t -F -ζ t -F ζ t +Lv t + L V.
Under the introduced conditions, it can be inferred from Lemma 1 that φ t ≥ 0 and φ t ≥ 0, ∀t ≥ 0. Therefore one deduces from Assumption 1 that e t ≥ 0 and e t ≥ 0 since e 0 ≥ 0 and e 0 ≥ 0 (the system ( 7) is cooperative). This implies that the order relation χ t ≤ x t ≤ χ t is satisfied for all t ≥ 0. Hence the inequality ( 6) is true by construction of x, x and due to the non-negativity of x.

To state the next theorem, we introduce the notation

J = J 11 J 12 J 21 J 22
, where

J 11 = α -1 F + (CA 2 ) -+ α -1 F -(CA 2 ) + , J 12 = -α -1 F + (CA 2 ) + -α -1 F -(CA 2 ) -, J 21 = -α -1 F + (CA 2 ) + -α -1 F -(CA 2 ) -, J 22 = α -1 F + (CA 2 ) -+ F -α -1 (CA 2 ) + .
and let η = J 2 , the induced 2-norm of J.

Theorem 2. Let Assumptions 1 and 2 be satisfied. Suppose there exists a diagonal matrix P ∈ R 8×8 with positive diagonal entries, two symmetric positive definite matrices Q, K ∈ R 8×8 , and a constant γ > 0 such that

Ξ =   A T P A -P + Q + γη 2 I 8 A T P A T P P A P -γI 8 P P A P P -K   0, (8) for
A = (A -LC) 0 0 (A -LC) .
Then χ, χ ∈ L 4 ∞ and so x, x ∈ L 4 ∞ . Proof. Let us define

χ t = [χ t T χ t T ] T , t = [ t T t T ] T , t = α -1 F + (y t+2 -V ) -α -1 F -(y t+2 + V ) + Hµ + Ly t -L V, t = α -1 F + (y t+2 + V ) -α -1 F -(y t+2 -V ) + Hµ + Ly t + L V.
The dynamics of the interval observer can be rewritten as

χ t+1 = Aχ t + J max{0, χ t } + t , (9)
where the matrix A is defined in the theorem. Consider a Lyapunov function V(χ t ) = χ T t P χ t (By using Lemma 2, the matrix P can be chosen diagonal since the matrix A is non-negative), and let τ = V(χ t+1 ) -V(χ t ). We have [START_REF] Hethcote | The mathematics of infectious diseases[END_REF]. This inequality shows that the system ( 9) is input-to-state stable from to χ [START_REF] Khalil | Nonlinear Systems[END_REF], [START_REF] Efimov | Design of interval observers for estimation and stabilization of discretetime LPV systems[END_REF], hence from y to χ. Since ∈ L 8

τ = χ T t (A T P A -P )χ t + χ T t A T P J max{0, χ t } + max{0, χ t } T J T P Aχ t + max{0, χ t } T J T P J max{0, χ t } + 2χ T t A T P t + 2 T t P J max{0, χ t } + T t P t . Taking into account that |J max{0, χ t }| 2 ≤ η|χ t | 2 , we get τ ≤ χ T t (A T P A -P )χ t + χ T t A T P J max{0, χ t } + max{0, χ t } T J T P Aχ t + max{0, χ t } T J T P J max{0, χ t } + 2χ T t A T P t + 2 T t P J max{0, χ t } + T t (P -K) t + T t K t + γη 2 χ T t χ t -γ max{0, χ t } T J T J max{0, χ t } + χ T t Qχ t -χ T t Qχ t , ≤   χ t J max{0, χ t } t   T Ξ   χ t J max{0, χ t } t   -χ T t Qχ t + T t K t , ≤ -χ T t Qχ t + T t K t , because of
∞ by construction, χ and χ stay bounded for all t ≥ 0.

In this paper, we select the observer gains L, L manually. However, because of the diagonal structure of P , one can in fact also optimize the observer gains L, L using semidefinite-programming to improve the observer's accuracy, following the approach of [START_REF] Efimov | Design of interval observers for estimation and stabilization of discretetime LPV systems[END_REF] to reformulate the matrix inequality [START_REF] Hethcote | The mathematics of infectious diseases[END_REF].

IV. SIMULATIONS

In this section, we illustrate the performance of the proposed interval observer. Consider a scenario where shows the results of the interval estimation for = 1 10 , where the solid lines represent the states x k , k = 1, 2, 3, 4 and the dash lines are used for the interval estimates x k and x k . Notice that the dynamics of S t and its estimates can be deduced from Fig. 2 by using the relation S t = 1 -E t -I t -R t .

µ t = µ 0 + 0.05 sin( π 4 t),α t = 0.2 + 0.1 sin 2 ( π 4 t), γ t = γ 0 + 0.1 sin( π 4 t),β t = β 0 (1 + κ cos( π 4

V. CONCLUSION

The problem of state-observer design for a discrete-time SEIR epidemic model of ILI has been considered in this paper. The proposed approach only requires sets of admissi-ble values for the model's disturbances or uncertainties and parameters, and no information about the bounding values of the time-varying transmission rate from the "susceptible" to the "infected" stage. A new approach for the estimation of the the four compartments' state is proposed, where an interval observer is used instead of a point-wise one. Its performance is illustrated in simulation. Future work can focus on performance evaluation for real data collected by the Public health services.

  and µ : Z + → [µ, µ] are unknown signals taking values in known intervals (i.e., the parameters α, α, γ, γ, µ, µ ∈ R + are given). The

Fig. 1 .

 1 Fig. 1. The non-dimensionalized (N = 1) classic time-varying Susceptible-Exposed-Infected-Recovered (SEIR) model.

  t)), with µ 0 = 0.4/year, γ 0 = 0.4/year, β 0 = 0.5/year and the degree of seasonality κ = 0.4. The output measurements y t are corrupted by noise such that v t = V cos( π 4 t) with V = 0.1 1000 . The state's initial conditions are S 0 = 852 1000 , E 0 = 120 1000 , I 0 = 5 1000 and R 0 = 23 1000 . We selectL = (1 -) [0 0 l 0 0] T , L = (1 + ) [0 0 l 0 0] T , with l = 1 20. Assumption 1 holds for these choices of L and L and all conditions of Theorem 1 are satisfied.

  Fig.2

Fig. 2 .

 2 Fig. 2. Evolution of the actual state and the observed bounds.