F Nous contacter


0

Logic and Foundations  | enregistrements trouvés : 24

O

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

Post-edited  Wrapping in exact real arithmetic
Müller, Norbert (Auteur de la Conférence) | CIRM (Editeur )

A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered explicitly, as they use would not change the induced computability, already established using ordinary interval computations. However for the viewpoint of efficiency, they lead to significant improvements.
In the talk we report on recent improvements on the iRRAM software for exact real arithmetic (ERA) based on Taylor models. The techniques discussed should also easily be applicable to other software for exact real computations as long as they also are based on interval arithmetic.
As instructive examples we consider the one-dimensional logistic map and a few further discrete dynamical systems of higher dimensions
Joint work with Franz Brauße, Trier, and Margarita Korovina, Novosibirsk.
A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered ...

68Q25 ; 03D60 ; 65Y15

In recent papers by Alon et al. and Fox et al. it is demonstrated that families of graphs with a semialgebraic edge relation of bounded complexity have strong regularity properties and can be decomposed into very homogeneous semialgebraic pieces up to a small error (typical example is the incidence relation between points and lines on a real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of graphs definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of measures (this applies in particular to graphs definable in arbitrary o-minimal theories and in p-adics). (Joint work with Sergei Starchenko.) In recent papers by Alon et al. and Fox et al. it is demonstrated that families of graphs with a semialgebraic edge relation of bounded complexity have strong regularity properties and can be decomposed into very homogeneous semialgebraic pieces up to a small error (typical example is the incidence relation between points and lines on a real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of ...

03C45 ; 03C60 ; 03C64

Diophantine properties of subsets of $\mathbb{R}^n$ definable in an o-minimal expansion of the ordered field of real numbers have been much studied over the last few years and several applications to purely number theoretic problems have been made. One line of inquiry attempts to characterise the set of definable functions $f : \mathbb{R} \to \mathbb{R}$ having the property that $f(\mathbb{N}) \subset \mathbb{N}$. For example, a result of Thomas, Jones and myself shows that if the structure under consideration is $\mathbb{R}_{exp}$ (the real field expanded by the exponential function) and if, for all positive $r, f(x)$ eventually grows more slowly than $exp(x^r)$, then $f$ is necessarily a polynomial with rational coefficients. In this talk I shall improve this result in two directions. Firstly, I take the structure to be $\mathbb{R}_{an,exp}$ (the expansion of $\mathbb{R}_{exp}$ by all real analytic functions defined on compact balls in $\mathbb{R}^n$) and secondly, I allow the growth rate to be $x^N \cdot 2^x$ for arbitrary (fixed) $N$. The conclusion is that $f(x) = p(x) \cdot 2^x + q(x)$ for sufficiently large $x$, where $p$ and $q$ are polynomials with rational coefficients.

I should mention that over ninety years ago Pólya established the same result for entire functions $f : \mathbb{C} \to \mathbb{C}$ and that in 2007 Langley weakened this assumption to $f$ being regular in a right half-plane of $\mathbb{C}$. I follow Langley's method, but first we must consider which $\mathbb{R}_{an,exp}$-definable functions actually have complex continuations to a right half-plane and, as it turns out, which of them have a definable such continuation.
Diophantine properties of subsets of $\mathbb{R}^n$ definable in an o-minimal expansion of the ordered field of real numbers have been much studied over the last few years and several applications to purely number theoretic problems have been made. One line of inquiry attempts to characterise the set of definable functions $f : \mathbb{R} \to \mathbb{R}$ having the property that $f(\mathbb{N}) \subset \mathbb{N}$. For example, a result of ...

03C64 ; 26E05

The field of Laurent series (with real coefficients, say) has a natural derivation but is too small to be closed under integration and other natural operations such as taking logarithms of positive elements. The field has a natural extension to a field of generalized series, the ordered differential field of transseries, where these defects are remedied in a radical way. I will sketch this field of transseries. Recently it was established (Aschenbrenner, Van der Hoeven, vdD) that the differential field of transseries also has very good model theoretic properties. I hope to discuss this in the later part of my talk. The field of Laurent series (with real coefficients, say) has a natural derivation but is too small to be closed under integration and other natural operations such as taking logarithms of positive elements. The field has a natural extension to a field of generalized series, the ordered differential field of transseries, where these defects are remedied in a radical way. I will sketch this field of transseries. Recently it was established ...

12L12 ; 12H05 ; 03C60 ; 03C64

On introduira la logique modale épistémique avec des exemples (enfants sales, etc.). On abordera la notion de logique modale et de structure de Kripke. On évoquera le problème de satisfiabilité et la méthode de tableau. Ensuite, nous verrons comment mettre à jour un modèle de Kripke. Nous verrons d'abord les annonces publiques. Puis nous verrons comment modéliser quelques actes de communications à l'aide des modèles d'actions. Une démonstration des enfants sales et du puzzle des prisonniers avec des "agents intelligents" sera présentée. On introduira la logique modale épistémique avec des exemples (enfants sales, etc.). On abordera la notion de logique modale et de structure de Kripke. On évoquera le problème de satisfiabilité et la méthode de tableau. Ensuite, nous verrons comment mettre à jour un modèle de Kripke. Nous verrons d'abord les annonces publiques. Puis nous verrons comment modéliser quelques actes de communications à l'aide des modèles d'actions. Une démonstration ...

O-minimalism is the first-order theory of o-minimal structures, an important class of models of which are the ultraproducts of o-minimal structures. A complete axiomatization of o-minimalism is not known, but many results are already provable in the weaker theory DCTC given by definable completeness and type completeness (a small extension of local o-minimality). In DCTC, we can already prove how many results from o-minimality (dimension theory, monotonicity, Hardy structures) carry over to this larger setting upon replacing 'finite' by 'discrete, closed and bounded'. However, even then cell decomposition might fail, giving rise to a related notion of tame structures. Some new invariants also come into play: the Grothendieck ring is no longer trivial and the definable, discrete subsets form a totally ordered structure induced by an ultraproduct version of the Euler characteristic. To develop this theory, we also need another first-order property, the Discrete Pigeonhole Principle, which I cannot yet prove from DCTC. Using this, we can formulate a criterion for when an ultraproduct of o-minimal structures is again o-minimal. O-minimalism is the first-order theory of o-minimal structures, an important class of models of which are the ultraproducts of o-minimal structures. A complete axiomatization of o-minimalism is not known, but many results are already provable in the weaker theory DCTC given by definable completeness and type completeness (a small extension of local o-minimality). In DCTC, we can already prove how many results from o-minimality (dimension theory, ...

03C64

Multi angle  On centauric subshifts
Romashchenko, Andrei (Auteur de la Conférence) | CIRM (Editeur )

We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other hand, these subshifts are complex in the sense of computability theory: all their configurations are non periodic or even non-computable, or all their finite patterns have high Kolmogorov complexity, the Turing degree spectrum is rather sophisticated, etc.
We start with the simplest example of such centaurisme with an SFT that is minimal and contains only aperiodic (and quasiperiodic) configurations. Then we discuss how far these heterogeneous properties can be strengthened without getting mutually exclusive.
This is a joint work with Bruno Durand (Univ. de Montpellier).
We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other ...

68Q30 ; 03B80

I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics. I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of ...

03D25 ; 03D32 ; 03F60 ; 68Q30

In 1971 Baumgartner showed it is consistent that any two $\aleph_1$-dense subsets of the real line are order isomorphic. This was important both for the methods of the proof and for consequences of the result. We introduce methods that lead to an analogous result for $\aleph_2$-dense sets.

Keywords : forcing - large cardinals - Baumgartner isomorphism - infinitary Ramsey principles - reflection principles

03E35 ; 03E05 ; 03E50 ; 03E55 ; 03E57

If CCM denotes the theory of compact complex spaces in the langauge of complex-analytic sets, then the theory of models of CCM equipped with an automorphism has a model companion, denoted by CCMA. The relationship to meromorphic dynamical systems is the same as that of ACFA to rational dynamical systems. I will discuss recent joint work with Martin Bays and Martin Hils that begins a systematic study of CCMA as an expansion of ACFA. Particular topics we consider include: stable embeddedness, imaginaries, and the Zilber dichotomy. If CCM denotes the theory of compact complex spaces in the langauge of complex-analytic sets, then the theory of models of CCM equipped with an automorphism has a model companion, denoted by CCMA. The relationship to meromorphic dynamical systems is the same as that of ACFA to rational dynamical systems. I will discuss recent joint work with Martin Bays and Martin Hils that begins a systematic study of CCMA as an expansion of ACFA. Particular ...

03C60 ; 03C45 ; 03C65 ; 32Jxx

Multi angle  A derivation on the field of d.c.e.reals
Miller, Joseph (Auteur de la Conférence) | CIRM (Editeur )

Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that $\partial\alpha/\partial\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\partial\alpha/\partial\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\partial\alpha/\partial\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.

We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let
\[
\partial\alpha = \frac{\partial\alpha}{\partial\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}.
\]
As above, the limit exists and is independent of the choice of approximations. Now $\partial\alpha=0$ if and only if $\alpha$ is nonrandom; $\partial\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\partial\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.

As we have telegraphed by our choice of notation, $\partial$ is a derivation on the field of d.c.e. reals. In other words, $\partial$ preserves addition and satisfies the Leibniz law:
\[
\partial(\alpha\beta) = \alpha\,\partial\beta + \beta\,\partial\alpha.
\]
(However, $\partial$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\partial$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\partial f(\alpha) = f'(\alpha)\,\partial\alpha$. This allows us to apply basic identities from calculus, so for example, $\partial\alpha^n = n\alpha^{n-1}\,\partial\alpha$ and $\partial e^\alpha = e^\alpha\,\partial\alpha$. Since $\partial\Omega=1$, we have $\partial e^\Omega = e^\Omega$.

Given a derivation on a field, the elements that it maps to zero also form a field: the $ \textit {field of constants}$. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a $ \textit {real closed field}$. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of [1] from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition (Demuth [2] and Downey, Hirschfeldt, and Nies [3]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.
Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that ...

03D28 ; 03D80 ; 03F60 ; 68Q30

It is by now well known that collections of compact (real-)analytic vector fields and locally connected trajectories thereof are mutually well behaved in a way that can be made precise via notions from mathematical logic, namely, by saying that the structure on the real field generated by the collection is o-minimal (that is, every subset of the real numbers definable in the structure is a finite union of points and open intervals). There are also many examples known where the assumption of analyticity or compactness can be removed, yet o-minimality still holds. Less well known is that there are examples where o-minimality visibly fails, but there is nevertheless a well-defined notion of tameness in place. In this talk, I will: (a) make this weaker notion of tameness precise; (b) describe a class of examples where the weaker notion holds; and (c) present evidence for conjecturing that there might be no other classes of examples of "non-o-minimal tameness". (Joint work with Patrick Speissegger.)
A few corrections and comments about this talk are available in the PDF file at the bottom of the page.
It is by now well known that collections of compact (real-)analytic vector fields and locally connected trajectories thereof are mutually well behaved in a way that can be made precise via notions from mathematical logic, namely, by saying that the structure on the real field generated by the collection is o-minimal (that is, every subset of the real numbers definable in the structure is a finite union of points and open intervals). There are ...

03C64 ; 34E05

The Pila-Wilkie theorem gives a bound on the number of rational points of bounded height lying on the transcendental part of a set definable in an o-minimal expansion of the real field. After discussing this result, I'll describe various classes of curves for which the Pila-Wilkie bound can be improved. I'll also give some examples and perhaps some applications.

03C64 ; 26E05

Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ is not Schnorr random, then there is a computable function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ whose Fourier series diverges at $t_0$.
This is joint work with Timothy H. McNicholl, and Jason Rute.
Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ i...

03D32 ; 42A20 ; 03D78 ; 68Q30

The "untwisted" Anosov-Katok diffeomorphisms of the torus or the disk are a source of interesting and counterintuitive measure preserving diffeomorphisms. This talk will present work showing just how broad this class is by giving a general symbolic representation of the AK diffeomorphisms that encodes, for example, all odometer based diffeomorphisms.

The combinatorics of successors of singular cardinals presents a number of interesting open problems. We discuss the interactions at successors of singular cardinals of two strong combinatorial properties, the stationary set reflection and the tree property. Assuming the consistency of infinitely many supercompact cardinals, we force a model in which both the stationary set reflection and the tree property hold at $\aleph_{\omega^2+1}$. Moreover, we prove that the two principles are independent at this cardinal, indeed assuming the consistency of infinitely many supercompact cardinals it is possible to force a model in which the stationary set reflection holds, but the tree property fails at $\aleph_{\omega^2+1}$. This is a joint work with Menachem Magidor.
Keywords : forcing - large cardinals - successors of singular cardinals - stationary reflection - tree property
The combinatorics of successors of singular cardinals presents a number of interesting open problems. We discuss the interactions at successors of singular cardinals of two strong combinatorial properties, the stationary set reflection and the tree property. Assuming the consistency of infinitely many supercompact cardinals, we force a model in which both the stationary set reflection and the tree property hold at $\aleph_{\omega^2+1}$. ...

03E05 ; 03E35 ; 03E55

Multi angle  Sets with few rational points
Comte, Georges (Auteur de la Conférence) | CIRM (Editeur )

In the spirit of famous papers by Pila & Bombieri and Pila & Wilkie, I will explain how to bound the number of rational points, with respect to their height, in various kinds of sets, such as transcendental sets definable in some o-minimal - or even not o-minimal - structure over the real field. I will emphazise the role played by bounds on derivatives and on sets of zeroes in this context.

03C98 ; 11D88 ; 14G05

We will present some of the original definitions, results, and proof techniques about Pfaffian functions on the reals by Khovanskii.
A simple example of a Pfaffian function is an analytic function $f$ in one variable $x$ satisfying a differential equation $f^\prime = P(x,f)$ where $P$ is a polynomial in two variables. Khovanskii gives a notion of complexity of Pfaffian functions which in the example is just the degree of $P$. Using this complexity, he proves analogues of Bézout's theorem for Pfaffian curves (say, zero loci of Pfaffian functions in two variables), with explicit upper bounds in terms of the ocurring complexities.
We explain a recent application by J. Pila and others to a low-dimensional case of Wilkie's conjecture on rational points of bounded height on restricted Pfaffian curves. The result says that the number of rational points of height bounded by $T$, on a transcendental restricted Pfaffian curve, grows at most as a power of log$(T)$ as $T$ grows. This improves the typical upper bound $T^\epsilon$ in Pila-Wilkie's results in general o-minimal structures, the improvement being due to extra geometric Bézout-like control.
In the non-archimedean setting, I will explain analogues of some of these results and techniques, most of which are (emerging) work in progress with L. Lipshitz, F. Martin and A. Smeets. Some ideas in this case come from work by Denef and Lipshitz on variants of Artin approximation in the context of power series solution.
We will present some of the original definitions, results, and proof techniques about Pfaffian functions on the reals by Khovanskii.
A simple example of a Pfaffian function is an analytic function $f$ in one variable $x$ satisfying a differential equation $f^\prime = P(x,f)$ where $P$ is a polynomial in two variables. Khovanskii gives a notion of complexity of Pfaffian functions which in the example is just the degree of $P$. Using this ...

03C98 ; 14G05 ; 14H05 ; 58A17

The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to $b$-automatic sequences. Then I will move to $b$-regular sequences, which can be viewed as a generalization of $b$-automatic sequences to integer-valued sequences. I will explain bow first-order logic can be used to show that many enumeration problems of $b$-automatic sequences give rise to corresponding $b$-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain. The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its ...

68R15 ; 11B85 ; 68Q45 ; 03B25

Nuage de mots clefs ici

Z