Retour à la page du séminaire général. Archives: Années 00-01, 01-02, 02-03, 03-04, 04-05, 05-06, 06-07, 07-08, 08-09, 09-10, 10-11, 11-12, 12-13, 13-14.

### UNIVERSITE DE PARIS VII, UFR DE MATHEMATIQUES   Séminaire général de Logique - Année 2014 - 2015

Résumés
(Ordre chronologique inverse)

15 juin 2015 : Guillaume Malod ( Equipe de Logique Mathématique, IMJ-PRG) Bornes inférieures pour les circuits skew non-commutatifs

Nisan (STOC 1991) a donné un exemple de polynôme calculable par un circuit non-commutatif de taille linéaire mais nécessitant un branching program non-commutatif de taille exponentielle. Cet exemple est en fait calculable par un circuit skew (où chaque porte de multiplication a un argument qui est réduit à une variable ou à une constante). Nous montrons que tout circuit skew calculant le carré du polynôme de Nisan doit voir une taille exponentielle et généralisons ce résultat aux circuits où toute porte de multiplication a un argument de degré au plus d/5, si d est le degré du polynôme calculé. Ces modèles non-commutatifs deviennent ainsi les plus forts pour lesquels nous ayons des bornes inférieures super-polynomiales. L'exposé ne suppose aucune connaissance particulière en complexité algébrique et les techniques employées sont élémentaires. (Travail en commun avec Nutan Limaye et Srikanth Srinivasan)

8 juin 2015 : Didier Caucal (CNRS et Université Paris-Est Marne la Vallée) Recognizability for infinite automata

The recognizability by inverse morphism defined by Eilenberg is extended to infinite automata. Given an automaton family F and an automaton H, we recognize the set of languages accepted by all possible automata of F that can be mapped by morphism into H. We introduce restrictions on morphisms to get various boolean algebras of context-free languages, (higher-order) indexed languages and contextual languages. It is a joint work with Chloé Athenosy.

1er juin 2015 : Michał Skrzypczak ( LIAFA, Université Paris 7, et Université de Varsovie, Pologne ) On uniformisability in monadic second-order logic

The property of uniformisation is one of the important concepts studied in the classical descriptive set theory. From the point of view of definability, it can be seen as a possibility to choose unique witnesses. During this talk I will focus on the uniformisation property for first-order (FO) logic and monadic second-order (MSO) logic. I will try to provide a summary of known results for various classes of structures; mainly finite and infinite words and trees. One of the crucial results in this area is the negative answer given by Gurevich and Shelah to the question of uniformisability in MSO over infinite trees (called Rabin's uniformisation question). Along with the overview of the classical results, I plan to present some recent advances and open questions. Probably the most intriguing of them is the question of MSO-definability of a choice function without parameters over scattered trees (i.e. trees having only countably manybranches).

11 mai 2015: Eugène Asarin ( LIAFA, Université Paris 7 ) Entropy of regular timed languages

Recall first that a timed word is constituted by letters and time delays (e.g. 2.43 a 1.17 b 5.112 a), a timed language is a set of timed words; and timed automata and timed regular languages are studied since early 90s. In this work, in order to study the size of regular timed languages, we generalize a classical approach introduced by Chomsky and Miller for discrete automata: count words having n symbols, and compute the exponential growth rate of their number (entropy). For timed automata, we replace cardinality by volume and define (volumetric) entropy similarly. It represents the average quantity of information per event in a timed word of the language. We exhibit a criterion for telling apart “thick” timed automata with non-vanishing entropy, for which typical runs are non-Zeno and discretizable, from “thin” automata for which all runs behave in a Zeno-like way, implying a quick volume collapse. The main technical tool comes from the functional analysis: we associate to every timed automaton a positive integral operator; the entropy equals the logarithm of its spectral radius. This operator has a spectral gap, thus allowing for fast converging numerical procedures to approximate entropy. In a special case, entropy is even characterized symbolically. (joint work with A. Degorre and N. Basset).

13 avril 2015 : Phillip Wesolek ( Université Catholique de Louvain-la-Neuve, Belgique ) Elementary totally disconnected locally compact Polish groups

The class of elementary groups is the smallest class of totally disconnected locally compact Polish groups that contains the profinite Polish groups and the countable discrete groups, that is closed under group extensions, and that is closed under countable increasing unions. In this talk, we discuss the permanence properties of the class of elementary groups and a characterization of elementary groups. As an application, we show that all compactly generated t.d.l.c. Polish groups can be decomposed into finitely many elementary groups and topologically characteristically simple groups via group extension. We conclude by considering a number of open questions related to elementary groups.

30 mars 2015: André Nies ( University of Auckland, New Zealand ) Descriptions de structures au sein d'une classe

We want to describe a structure in a class up to isomorphism, using an appropriate formal language. Containment in the class is given as an additiona (external) condition. For finite structures in a fixed finite signature, there is always a description in first-order logic of length comparable to the size of the structure. An interesting question is how short such a description can be. In joint work with Katrin Tent we answer this question for groups, compressing the group to a description of length polylogarithmic in the size of the group. Within the class of finitely generated groups, an interesting question is whether a group can be described at all by a single first-order sentence. For instance, this is the case for the Heisenberg group over $\mathbb Z$, and for the restricted wreath product of a finite cyclic group with $\mathbb Z$ (the latter example is not finitely presented). Within the class of countable structures over a countable signature $S$, there is always a description in $L_{\omega_1, \omega}(S)$, the extension of first-order language that allows countable disjunctions over a set of formulas with a shared finite reservoir of free variables (Scott). For the class of separable complete metric spaces, a similar result holds. The most natural language here is an extension of continuous logic for $S$ that allows countable disjunctions.

23 mars 2015 : Laura Fontanella ( Hebrew University of Jerusalem, Israel ) Generalized compactness and large cardinals

Applications of large cardinals arise in many fields, including group theory, general topology and others. Some of these results follow from various generalizations of Compactness theorem to infinitary logics. We discuss a particular principle, called Delta-reflection, that entails a version of this generalized compactness. We will investigate some of its applications to the study of abelian groups, Hausdorff spaces and others, and we will show that, despite its strength, the Delta-reflection can consistently hold even at small cardinals together with another compactness principle known as the tree property. This is a joint work with M. Magidor

16 mars 2015 : Rizos Sklinos ( Université de Lyon 1 ) Some model theory of torsion-free hyperbolic groups

The profound work of Z.Sela has radically changed the picture concerning stable groups. In a series of papers of great volume and complexity he proved that every non-cyclic torsion-free hyperbolic group is stable. The only families of groups whose members were already known to be stable were the family of algebraic groups (over algebraically closed fields) and the family of Abelian groups. In this talk I will survey recent results about the first order theories of torsion-free hyperbolic groups as to give our current understanding of their model theory. I will give the ideas of the proofs of the most important results without the technical details in order to reveal the beautiful interplay between logic and geometric group theory. No prior knowledge of stability or geometric group theory will be assumed. "

9 mars 2015 : Nathanael Mariaule ( Université de Naples, Italie ) Le corps des nombres p-adiques avec un prédicat pour les puissances d'un nombre entier

Dans un article datant de 1985, L. van den Dries axiomatise la théorie du corps des réels avec un prédicat pour les puissances d'un entier n. Dans cet exposé, je vais présenter une version p-adique de ce résultat. En particulier, nous verrons que les méthodes à utiliser sont différentes selon l'entier choisi: Si la valuation p-adique de n est non-nulle, le groupe multiplicatif généré par n est discret et ce cas s'approche de celui étudié par van den Dries. Dans le cas contraire, le groupe est dense dans une partie (définissable) du corps des nombres p-adiques et de nouvelles idées sont nécessaires comparé au cas réel.

2 mars 2015 : Daniel Palacin (Université de Münster, Allemagne) Stabilité, groupes et internalité

Dans cet exposé, je vais faire une introduction à la théorie de la stabilité et des groupes définissables dans ce contexte. Je donnerai des exemples et définitions de base, et aussi des notions plus élaborées comme monobasé et internalité. Enfin, je vais prouver un résultat en collaboration avec Rizos Sklinos sur des expansions de la théorie des nombres entiers.

16 février 2015 : Martino Lupini (York University, Toronto, Canada) Generic spaces of operators

We will present an overview of the construction and study of canonicalgeneric objects in the categories of operator spaces, operator systems, and operator algebras from the perspective of Fraisse theory and model theory for metric structures.

9 février 2015 : Olivia Caramello ( Université Paris 7) Les topos de Grothendieck comme ponts unifiants en logique et mathématiques

On présentera une nouvelle vision des topos de Grothendieck comme des espaces capables de servir efficacement de 'ponts' pour transférer des concepts et résultats entre différentes théories mathématiques. Cette approche a déjà engendré plusieurs applications dans différents domaines des mathématiques et le potentiel de cette théorie a juste commencé à être exploré. On expliquera les principes fondamentaux qui caractérisent cette vision des topos comme 'ponts unifiants' et on illustrera l'utilité technique de ces méthodologies en discutant quelques applications en logique, algèbre et topologie.

2 février 2015 : Veronica Becher ( Université de Buenos Aires & CONICET, Argentine) On normal numbers

Flip a coin a large number of times and roughly half of the flips will come up heads and half will come up tails. Normality makes similar assertions about the sequences of digits in the expansions of a real number. For b an integer greater than or equal to 2, a real number x is simply normal to base b if every digit d in {0, 1, . . . , b-1} occurs in the base b expansion of x with asymptotic frequency 1/b; a real number x is normal to base b if it is simply normal to all powers of b; and a real number x is absolutely normal if it is simply normal to all integer bases greater than or equal to 2. More than one hundred years ago E. Borel showed that almost all real numbers are absolutely normal, and he asked for one example. He would have liked some fundamental mathematical constant such as pi or e, but this remains as the most famous open problem on normality. As for other examples, there have been several constructions of normal numbers since Borel's time, with varying levels of effectivity (computability). I will summarize the latest results, including our constructions of numbers normal to selected bases, a fast algorithm to compute an absolutely normal number which runs in nearly quadratic time, and an algorithm to compute an absolutely normal Liouville number. This is joint work with Theodore Slaman and Pablo Heiber. Verónica Becher is an Associate Professor at the University of Buenos Aires and researcher at CONICET. She is part of the Laboratoire International Associé INFINIS Universidad de Buenos Aires-CONICET/Université Paris Diderot-CNRS.

19 janvier 2015 : François Le Maître ( Université Catholique de Louvain-la-Neuve, Belgique ) Propriété de petit indice et groupes localement compacts

Un groupe topologique satisfait la propriété de petit indice si tous ses sous-groupes d'indice dénombrable sont ouverts. Dans le cas d'un groupe polonais non archimédien, les sous-groupes ouverts sont tous d'indice dénombrable et forment une base voisinages de l'identité: la propriété de petit indice garantit alors que la topologie du groupe est alors encodée algébriquement. D'après un résultat de Dixon-Neumann-Thomas, le groupe des permutations des entiers satisfait la propriété de petit indice. Leur résultat a ensuite été étendu à des groupes d'automorphismes de structures dénombrables plus riches, comme les groupes d'automorphismes de structures dénombrables omega-stables et omega-catégoriques. On s'intéresse ici à l'existence de groupes localement compacts satisfaisant la propriété de petit indice, et on donnera des exemples de groupes d'automorphismes de l'arbre n-régulier qui la vérifient. Ce résultat a été obtenu en collaboration avec Wesolek.

12 janvier 2015 : Vincenzo Mantova (University of Camerino, Italie) Surreal numbers, derivations and transseries

Conway's surreal numbers are a class "No" of inductive objects, originally thought as moves in a game, possessing a natural structure of ordered field and an exponential function which make it a monster model of the theory of (R,exp). It has been conjectured several times that No has also a derivation mimicking the differential structure of Hardy fields, and that No could be described, in some appropriate sense, as a field of transseries. I will discuss the interplay between surreal numbers, derivations of Hardy fields and transseries, and the most recent results regarding the above conjectures. This is joint work with A. Berarducci.

1er décembre 2014 : Jérémie Cabessa (Université Panthéon-Assas Paris II) Computational capabilities of recurrent neural networks

We provide a survey of major results concerning the computational capabilities of recurrent neural networks. In particular, we show that some basic neural models happen to be computationally equivalent to finite automata, Turing machines, probabilistic Turing machines with logarithmic advice, or Turing machines with polynomial advice.

24 novembre 2014 : Friedrich Martin Schneider ( Université de Dresde, Allemagne ) Invariants of group actions and their connection to amenability

Having its roots in the beginnings of modern measure theory, the concept of amenability has become of central importance to topological group theory and topological dynamics. The class of amenable topological groups is vast and allows to define dynamical invariants by means of a well-behaved averaging process. We will present characterizations of amenability in terms of several novel invariants for continuous group actions and discuss some related problems.

10 novembre 2014 : Eli Glasner (Tel-Aviv University) On tame dynamical systems

According to a dynamical version of the Bourgain-Fremlin-Talagrand dichotomy, an enveloping semigroup of a dynamical system is either tame: has cardinality $\le 2^{\aleph_0}$, or it is topologically wild and contains a copy of $\beta\mathbb{N}$, the \v{C}ech-Stone compactificaltion of a discrete countable set. As a general principle one can measure the usefulness of a new mathematical notion by the number of seemingly unrelated ways by which it can be characterized. According to this principle the notion of tameness stands rather high. Tameness can also be characterized by the lack of a certain independence property --- where combinatorial Ramsey type arguments take a leading role --- by the fact that the elements of the enveloping semigroup of a tame system are Baire class 1 maps, and, in terms of eventual non-sensitivity".As an application of the latter we obtain the following characterization of tame subshifts $X \subset \{0,1\}^{\mathbb Z}$: for every infinite subset $L \subseteq {\mathbb Z}$ there exists an infinite subset $K \subseteq L$ such that $\pi_{K}(X)$ is a countable subset of $\{0,1\}^K$. Finally, a dynamical system is tame iff it can be represented on a Banach space which does not contain an isomorphic copy of $\ell_1$. I will review some of these results and indicate some applications. Mostly these are joint works with Michael Megrelishvily.

3 novembre 2014 : Silvain Rideau (ENS Paris et Paris-Sud Orsay) Comptage en théorie des groupes et imaginaires p-adiques

Soit G un groupe nilpotent sans torsion finiment engendré. Le nombre de sous-groupes de G d'indice donné $p^n$ est fini et on le note a_n. Pour étudier le comportement des a_n, on s’intéresse à la série $\zeta_{p,G}(s) = \sum_n a_n t^n$ dont la rationalité a été démontrée par Grunewald, Segal et Smith (1988). Leur preuve consiste à réécrire cette somme comme une intégrale p-adique à paramètres et à utiliser un résultat de Denef (1984) sur la rationalité des telles intégrales. On peut aussi démontrer que de tels résultats de rationalité sont uniformes en p. Le but de cet exposé sera d'exposer une méthode générale pour démontrer de tels résultats de comptage qui permet de retrouver les résultats connus en en simplifiant la preuve et de prouver de nouveaux résultats. Cette méthode générale utilise toujours le résultat de rationalité de Denef et un nouvel ingrédient modèle théorique: l'élimination des imaginaires p-adiques. Tous les objets dont il est question dans ce résumé seront redéfinis. (En commun avec Ehud Hrushovski et Ben Martin.)

29 septembre 2014 : Ivan Tomasic (University of London) Applications of difference algebraic geometry

The term Difference algebraic geometry' refers to the range of methods of difference algebra and the corresponding geometry', originally developed to study definable sets in ACFA (the theory of existentially closed difference fields), as well as sets definable over fields with powers of Frobenius. We will apply these tools in the discussion of a class of exceptionally nice difference polynomials.

22 septembre 2014 : Joerg Brendle ( Kobe University ) Ultrafilters on the natural numbers

Various classes of ultrafilters on the natural numbers, like the P-points or the Ramsey ultrafilters, have found important applications in other areas of mathematics, like combinatorics or topology. We will present a unified treatment of such classesof ultrafilters, in terms of ideals on countable sets, and then discuss the problem of existence and that of generic existence of ultrafilters in these classes. Here we say that ultrafilters in a class exist generically if every filter base of size less than continuum can be extended to an ultrafilter in the class.