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

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

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

The concept of a "transseries" is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have pursued a program to understand the algebraic and model-theoretic aspects of this intricate but fascinating mathematical object. A differential analogue of "henselianity" is central to this program. Last year we were able to make a significant step forward, and established a quantifier elimination theorem for the differential field of transseries in a natural language. My goal for this talk is to introduce transseries without prior knowledge of the subject, and to explain our recent work. The concept of a "transseries" is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have ...

03C10 ; 03C64 ; 26A12

Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given finitely presented group $0$, is there an algorithm that determines if the group $G$ is tilable with a finite set of tiles? In this lecture I will start with a presentation of two different proofs of the undecidability of the domino problem on $Z^2$. Then we will discuss the case of finitely generated groups. Finally, the emptiness problem for general subshifts will be tackled. Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given ...

68Q45 ; 03B25 ; 37B50

Multi angle  Independence of normal words
Becher, Verónica (Auteur de la Conférence) | CIRM (Editeur )

Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).
Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has ...

68R15 ; 11K16 ; 03D32

Quelle est la puissance des machines de calculs analogiques (vs digitales)? Que peut-on calculer avec des équations différentielles ? Que cela nous apprend-t'il sur la physique et ses modèles de notre monde physique ?

03Dxx ; 68Q05 ; 68Q15

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

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

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

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

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.

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 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

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

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

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

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

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

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

Nuage de mots clefs ici

Z