Name: Logical methods in Ramsey theory and related topics
Start: 2023-07-10T00:10:00+02:00
End: 2023-07-11T23:00:00+02:00
Location: Dipartimento di Matematica

Logical methods in Ramsey theory and related topics

from Monday, 10 July 2023 (00:10) to Tuesday, 11 July 2023 (23:00)

Monday, 10 July 2023

09:00 Registration
Registration
09:00 - 09:20
Room: Aula Magna
09:30 Continuous reducibility is a well-quasi-order on continuous functions with Polish 0-dimensional domains - Raphael Carroy (Università di Torino)
Continuous reducibility is a well-quasi-order on continuous functions with Polish 0-dimensional domains
- Raphael Carroy (Università di Torino)
09:30 - 10:15
Room: Aula Magna Given topological spaces $X,X',Y,Y'$, and two functions $f:X\to Y$ and $f':X'\to Y'$, we say that $f$ reduces continuously to $f'$ when there is a pair $(\sigma,\tau)$ of continuous functions such that $f=\tau\circ f'\circ\sigma$. This quasi-order has first been introduced by Weihrauch in the context of Computable Analysis at the beginning of the 1990s. It has recently received interest in Descriptive Set Theory. With Yann Pequignot, we proved that on the class of continuous functions with Polish 0-dimensional domains, there are no infinite antichains and no infinite strictly descending chains for continuous reducibility. In other words, continuous reducibility is a well-quasi-order on this class of functions. I will give some context for this result and outline the proof.
10:20 Capturing convergence through changing the logic - Mirna Džamonja (CNRS - Université de Paris)
Capturing convergence through changing the logic
- Mirna Džamonja (CNRS - Université de Paris)
10:20 - 11:05
Room: Aula Magna In recent years we have witnessed an unprecedented confluence of methods from discrete and continuous mathematics, especially in subjects having to do with logic and topology. One can cite fields such as continuous model theory, homotopy type theory and, most relevant to this talk, combinatorial limits. The latter have started from the notion of graphons and have been generalised to other objects, including the very general Stone pairings. In this subject one looks at uncountable limits of a countable sequence of finite objects, with various logical properties that carry through. In the context of first order logic, one can think of Los’s theorem for ultraproducts, but various other transfer theorems have been obtained in this other contexts. In this talk we shall review some of these notions, including a Ramsey theorem about ultraproducts, and then connect them with the study of abstract logics through new satisfaction relations.
11:10 Coffee break
Coffee break
11:10 - 11:40
11:40 Numerical Non-standard Calculus: Applications and Software Implementation - Lorenzo Fiaschi (Università di Pisa)
Numerical Non-standard Calculus: Applications and Software Implementation
- Lorenzo Fiaschi (Università di Pisa)
11:40 - 12:05
Room: Aula Magna Non standard analysis and engineering applications have long remained two separate things. More recently, new computational paradigms have been proposed that seem able to close this gap. One of them is the non standard model built upon Benci and Di Nasso’s Alpha Theory, within which in 2021 Benci and Cococcioni introduced a fixed length binary encoding (along with truncation operators) for non standard numbers [1]. This achievement paved the way for an efficient implementation of non standard computations within computers, that is the numerical representation and manipulation of non standard numbers. Even if the journey through numerical, non standard computations is still at the beginning, the research has already showed encouraging benefits of their application, especially in the context of deterministic and stochastic multi objective lexicographic optimization. The present talk will provide an overview of them, focusing on two relevant engineering applications where the efficacy of a non standard computational framework has already been tested: multi objective convex quadratic programming based on the interior point method [2] and deep reinforcement learning. Work partially funded by the Italian Ministry of Education and Research (MUR), ForeLab project (Departments of Excellence), and by PNRR M4C2 Investimento 1.3, Partenariato Esteso PE00000013 ”FAIR Future Artificial Intelligence Research” [1] Benci, V. and Cococcioni, M. (2021) “The Algorithmic Numbers in Non Archimedean Numerical Computing Environments”, Descrete And Continuous Dynamical Systems Series S, 14(5):1673 1692, https://doi.org/10.3934/dcdss.2020449 [2] Fiaschi, L. and Cococcioni, M. (2022) “A Non Archimedean Interior Point Method and Its Application to the Lexicographic Multi Objective Quadratic Programming”, Mathematics, 10(23):4536, https://doi.org/10.3390/math10234536
12:10 Initial Applications of Alpha Theory in Telecommunication Engineering - Francesco Fiorini (Università di Pisa)
Initial Applications of Alpha Theory in Telecommunication Engineering
- Francesco Fiorini (Università di Pisa)
12:10 - 12:30
Room: Aula Magna Heavy-tailed distributions with infinite variance are crucial in telecommunication engineering as they can model real-world phenomena accurately. They describe various traffic characteristics, such as file sizes on web servers and corresponding transmission times, CPU times, idle times, peak rates and connection times. However, simulating these distributions presents numerical challenges due to infinite variance and slow convergence. To address these issues, we developed a Matlab toolbox based on the Alpha Theory developed by Benci and Di Nasso (and the associated concept of Euclidean numbers). This approach allows for a new Euclidean Heavy-Tailed Lognormal distribution with finite mean and numerically verifiable infinite variance, recently appeared in [1]. Finally we will discuss its use in Queueing Theory, where numerous estimation and performance prediction formulations for queues have inherent mathematical limitations when considering infinite or infinitesimal values. As an example, we will show how the Euclidean LogNormal distribution could be used in combination with the Pollaczek-Khinchin formula in M/G/1 queues, even when the variance is infinite, provided that it is a computable value (and not a value diverging towards $+\infty$). We expect that this will also allow us to perform asymptotic analyses numerically in Matlab (instead of using paper and pencil or symbolic software like Mathematica). Work partially funded by the Italian Ministry of Education and Research (MUR), ForeLab project (Departments of Excellence), and by PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - ”FAIR - Future Artificial Intelligence Research” - Spoke 1 ”Human-centered AI” (the PNRR program is funded by the European Commission under the NextGeneration EU programme). [1] Cococcioni, M., Fiorini, F. and Pagano, M. (2023) “Modelling Heavy Tailed Phenomena Using a LogNormal Distribution Having a Numerically Verifiable Infinite Variance”, Mathematics, 11(7):1758, https://doi.org/10.3390/math11071758
12:30 Conference photo
Conference photo
12:30 - 12:35
14:30 The complexity of proving Ramsey principles - Nicola Galesi (Sapienza Università di Pisa)
The complexity of proving Ramsey principles
- Nicola Galesi (Sapienza Università di Pisa)
14:30 - 15:15
Room: Aula Magna We say that a graph with $n$ vertices is $c$-Ramsey if there is no set of $c \log n$ vertices which form in $G$ either a clique or an independent set. In other words a $c$-Ramsey graph over $n$ nodes is a witness of the fact that $r(c\log n) > n$, where $r(k)$ is the least $N$ such that every graph of size at least $N$ contains a clique or independent set of size $k$. In searching for hard formulas to prove, proof complexity has often focused on Ramsey principles, by studying upper bounds for $r(k)$, that is on the complexity of certifying that a graph $G$ of size $n$ is $c$-Ramsey. After reviewing what is known about the complexity of proving Ramsey principles we discuss the case the of $k$-clique Principle, an instantiation of Ramsey principles stating the a graph on $n$ vertices does not contain a $k$-clique. We will present a recent result of ours on the complexity of proving such principle in systems related to the Resolution and when the graph $G$ is a random graph and we discuss why its exact proof complexity in Resolution represents a major open problem.
15:20 Problem session
Problem session
15:20 - 16:05
Room: Aula Magna
Tuesday, 11 July 2023
09:30 Numbers and numerosities - Vieri Benci (Università di Pisa)
Numbers and numerosities
- Vieri Benci (Università di Pisa)
09:30 - 10:15
Room: Aula Magna In this talk we analyze the notion of number and we define the structure of counting system. In this context, we present the notion of numerosity as a natural extension of the cardinality. This presentation is possible thanks to a theorem which has been recently proved.
10:20 Applications of nonstandard methods to partition regularity - Martino Lupini (Università di Bologna)
Applications of nonstandard methods to partition regularity
- Martino Lupini (Università di Bologna)
10:20 - 11:05
Room: Aula Magna In this talk, I will give an overview of applications of nonstandard methods to partition regularity for solutions to Diophantine equations and other combinatorial configurations.
11:10 Coffee break
Coffee break
11:10 - 11:40
11:40 Euclidean integers, Eucledean ultrafilters, and Euclidean numerosities - Marco Forti (Università di Pisa)
Euclidean integers, Eucledean ultrafilters, and Euclidean numerosities
- Marco Forti (Università di Pisa)
11:40 - 12:25
Room: Aula Magna We introduce axiomatically, for any cardinal $\kappa$, the ordered domain $\mathbf{Z}_\kappa$ of the _Euclidean integers_, characterized as the collection of the transfinite sums of all $\kappa$-sequences of integers. Most relevant is the _algebraic_ characterization of the ordering: a Euclidean integer is _positive_ if and only if it is _the transfinite sum of natural numbers_. The ring $\mathbf{Z}_\kappa$ is obtained by taking the _ultrapower of the ring of all finite partial sums_ modulo special ultrafilters (also named _Euclidean_ ), here introduced to this end. (So $\mathbf{Z}_\kappa$ is actually a ring of _hyperintegers_.) The existence of Euclidean ultrafilters follows from a new form of the Erdős-Dushmill-Miller partition property $\kappa\to(\omega,\kappa)$, namely $\ [A^{<\omega}]^2_\subset \to(\omega,\text{cofinal})^2_\subset,\ $ meaning that _"for every 2-partition $G:[A^{<\omega}]^2_\subset\to\{0,1\}$ of all $\subset$-comparable pairs of finite subsets of $A$, there exists a $0$-homogeneous countable $\subset$-increasing sequence $C\subset A^{<\omega}$,or there exists a $\subset$-cofinal set $H\subset A^{<\omega}$ such that $[H]^2_\subset=\{(b,c)\in H^2\mid b\subset c\}$ is $1$-homogeneous for $G$.''_ We call $\mathbf{Z}_\kappa$ the ring of the Euclidean integers because it arises in a theory of size of sets (_"numerosity''_), whose main aim is to save all the Euclidean common notions, including the fifth _"the whole is greater than the part''_, but still maintaining the Cantorian definitions of _ordering, addition and multiplication_ of sets. Having at disposal transfinite sums of integers, the numerosity of a set may be the transfinite sums of its characteristic function, which is an Euclidean integer after an appropriate labelling of sets by ordinals. Then, in contrast to the awkward Cantorian cardinal arithmetic, numerosities are a positive semiring of _hypernatural numbers_, the non-negative part of the ring $\mathbf{Z}_\kappa$. In particular, the algebraic order of $\mathbf{Z}_\kappa$ yields the _"difference property''_ asserting that the difference of the numerosities of any two sets is itself the numerosity of some set. This property has been the ``most wanted'' property of the Euclidean theory of size since its origin at the beginning of the century. Moreover one obtains the supplementary benefits that every set is equinumerous to a set of ordinals, and conversely that every nonnegative Euclidean integer is the numerosity of a set $X$ of ordinals, namely the transfinite sum of the characteristic function $\chi_X$.
14:30 Many Levels of Infinities and Multidimensional van der Waerden's Theorem - Renling Jin (College of Charleston)
Many Levels of Infinities and Multidimensional van der Waerden's Theorem
- Renling Jin (College of Charleston)
14:30 - 15:15
Room: Aula Magna There could be more than one elementary embedding between a model and its elementary extension. We develop a nonstandard analysis framework by iterating ultrapower constructions and present two different elementary embeddings at each stage. We hope that this framework gives powerful tools in applications. As a testing case we give a nonstandard proof of multidimensional van der Waerden's theorem by a single induction within this framework.
15:20 More thoughts on the use of nonstandard methods to extend Roth's Theorem - Steven Leth (University of Northern Colorado)
More thoughts on the use of nonstandard methods to extend Roth's Theorem
- Steven Leth (University of Northern Colorado)
15:20 - 16:05
Room: Aula Magna In this talk I will continue to explore some possibilities and some challenges in attempting to use nonstandard methods to extend Roth's theorem to sparser sets. Jin's recent proof of Roth's and Szemerédi's theorem provided new clarity on the combinatorial methods used by Szemerédi, and it is still unclear whether these techniques can be used to obtain stronger results. Meanwhile, some amazing new developments have taken place in regard to generalizations of Roth's Theorem. Recently Bloom and Sisask showed that any subset of the natural numbers with no 3-term arithmetic progression must have asymptotic density less than $\frac{1}{\log(n)^{1+c}}$ for some constant $c>0$. Then, in the last few months, this bound was significantly improved by Kelley and Meka, who showed that much sparser sets than this must contain 3-term arithmetic progressions, and their result is in close to "best possible." While I will discuss these results, I will not attempt to provide any insight into these groundbreaking proofs.
16:10 Coffee break
Coffee break
16:10 - 16:40
16:40 Nonstandard methods without the axiom of choice - Karel Hrbáček (City College of New York)
Nonstandard methods without the axiom of choice
- Karel Hrbáček (City College of New York)
16:40 - 17:25
Room: Aula Magna Model-theoretic frameworks for nonstandard methods entail the existence of nonprincipal ultrafilters over $\mathbb{N}$, a strong version of the Axiom of Choice ($\mathbf{AC}$). While $\mathbf{AC}$ is instrumental in many abstract areas of mathematics, such as general topology or functional analysis, its use in infinitesimal calculus or number theory should not be necessary. In [1], Mikhail Katz and I have formulated a set theory $\mathbf{SPOT}$ in the $\mathbf{st}$-$\in$-language. The theory has three simple axioms, Transfer, Nontriviality and Standard Part. It is a subtheory of the nonstandard set theories $\mathbf{IST}$ and $\mathbf{HST}$, but unlike them, it is a conservative extension of $\mathbf{ZF}$. Arguments carried out in $\mathbf{SPOT}$ thus do not depend on any form of $\mathbf{AC}$. Infinitesimal calculus can be developed in $\mathbf{SPOT}$ as far as the global version of Peano's Theorem (the usual proofs of which use $\mathbf{ADC}$, the Axiom of Dependent Choice). The existence of upper Banach densities can be proved in $\mathbf{SPOT}$. The conservativity of $\mathbf{SPOT}$ over $\mathbf{ZF}$ is established by a construction that combines and extends the methods of forcing developed by A. Enayat and M. Spector. A stronger theory $\mathbf{SCOT}$ is a conservative extension of $\mathbf{ZF} + \mathbf{ADC}$. It is suitable for handling such features as an infinitesimal approach to the Lebesgue measure. I will also explore the possibilities for extending these theories to multiple levels of standardness and the relevance of such extensions to infinitesimal calculus and R. Jin's proof of Szemerédi's Theorem. [1] K. Hrbacek and M. G. Katz, Infinitesimal analysis without the Axiom of Choice, Ann. Pure Appl. Logic 172, 6 (2021). https://doi.org/10.1016/j.apal.2021.102959 https://arxiv.org/abs/2009.04980