2025-07-18 | | Total: 6
We consider the following property of a first order theory T with a distinguished unary predicate P: every model of the theory of P occurs as the P-part of some model of T. We call this property the Gaifman property. Gaifman conjectured that if T is relatively categorical over P, then it has the Gaifman property. We propose a generalized version of this conjecture: if T fails the Gaifman property, then it exhibits non-structure over P, i.e., has many non-isomorphic models over P in many cardinalities. We address this conjecture for countable theories. Motivated by ideas from Classification Theory, we separate this conjecture into two parts: 1) stability over P (a structure property of theories) implies the Gaifman property, and 2) instability over P implies non-structure. In this paper prove the first part of this conjecture. In fact, we prove a stronger statement: an appropriate version of stability implies higher stable amalgamation properties.
We study projective functions. We prove that projective functions generalise lower and upper-semianalytic ones while being stable by composition and difference. We show that the class of projective functions is closed under sums, differences, products, finite suprema and infima, sections and compositions. Assuming the set-theoretical axiom of Projective Determinacy, we also prove measurable selection results, stability under integration, and the existence of $\epsilon$-optimal selectors. Finally, we illustrate how these results are important in the context of model uncertainty.
Frontier AI models demonstrate formidable breadth of knowledge. But how close are they to true human -- or superhuman -- expertise? Genuine experts can tackle the hardest problems and push the boundaries of scientific understanding. To illuminate the limits of frontier model capabilities, we turn away from contrived competitive programming puzzles, and instead focus on real-life research problems. We construct FormulaOne, a benchmark that lies at the intersection of graph theory, logic, and algorithms, all well within the training distribution of frontier models. Our problems are incredibly demanding, requiring an array of reasoning steps. The dataset has three key properties. First, it is of commercial interest and relates to practical large-scale optimisation problems, such as those arising in routing, scheduling, and network design. Second, it is generated from the highly expressive framework of Monadic Second-Order (MSO) logic on graphs, paving the way toward automatic problem generation at scale; ideal for building RL environments. Third, many of our problems are intimately related to the frontier of theoretical computer science, and to central conjectures therein, such as the Strong Exponential Time Hypothesis (SETH). As such, any significant algorithmic progress on our dataset, beyond known results, could carry profound theoretical implications. Remarkably, state-of-the-art models like OpenAI's o3 fail entirely on FormulaOne, solving less than 1% of the questions, even when given 10 attempts and explanatory fewshot examples -- highlighting how far they remain from expert-level understanding in some domains. To support further research, we additionally curate FormulaOne-Warmup, offering a set of simpler tasks, from the same distribution. We release the full corpus along with a comprehensive evaluation framework.
We introduce a partial decidability protocol for the Wang tiling problem (which is the prototype of undecidable problems in combinatorics and statistical physics) by constructing a suitable mapping from tilings of finite squares of different sizes. Such mapping depends on the initial family of Wang tiles (the alphabet) with which one would like to tile the plane. This allows to define effective entropy and temperature associated to the alphabet (together with the corresponding partition function). We identify a subclass of good alphabets by observing that when the entropy and temperature of a given alphabet are well-behaved in the thermodynamical sense then such alphabet can tile the infinite two-dimensional plane. Our proposal is tested successfully with the known available good alphabets (which produce periodic tilings, aperiodic but self-similar tilings as well as tilings which are neither periodic nor self-similar). Our analysis shows that the Kendall Tau coefficient is able to distinguish alphabets with a good thermodynamical behavior from alphabets with bad thermodynamical behavior. The transition from good to undecidable behavior is related to a transition from non-chaotic to chaotic regime in discrete dynamical systems of logistic type.
The combination of higher-order theories and fuzzy logic can be useful in decision-making tasks that involve reasoning across abstract functions and predicates, where exact matches are often rare or unnecessary. Developing efficient reasoning and computational techniques for such a combined formalism presents a significant challenge. In this paper, we adopt a more straightforward approach aiming at integrating two well-established and computationally well-behaved components: higher-order patterns on one side and fuzzy equivalences expressed through similarity relations based on minimum T-norm on the other. We propose a unification algorithm for higher-order patterns modulo these similarity relations and prove its termination, soundness, and completeness. This unification problem, like its crisp counterpart, is unitary. The algorithm computes a most general unifier with the highest degree of approximation when the given terms are unifiable.
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing its structure and label set. We consider classes where permutations move only finitely many vertices. Our main result shows that PAC learnability of all such finite-support copies implies online learnability of the full isomorphism type of G, and is equivalent to the condition of automorphic triviality. We also characterize graphs where copies induced by swapping two vertices are not learnable, using a relaxation of the extension property of the infinite random graph. Finally, we show that, for all G and k>2, learnability for k-vertex permutations is equivalent to that for 2-vertex permutations, yielding a four-class partition of infinite graphs, whose complexity we also determine using tools coming from both descriptive set theory and computability theory.