Papers

We characterize the arithmetical categories - the exact Mal'tsev categories whose lattices of congruences are distributive - by a simple condition on some suitable pushouts and a finite limit: a regular category is exact arithmetical if and only if, for every triple of regular epimorphisms with common domain, the pairwise pushouts exist and the comparison morphism to the limit of the diagram they form is a regular epimorphism. For a regular category, the validity of this condition for pairs and for triples is equivalent to its validity for $n$-tuples for all $n \ge 2$, and characterizes arithmetical categories among regular ones. For pairs alone the condition reduces to the characterization of exact Mal'tsev categories among regular ones, due to Carboni, Kelly and Pedicchio. For $n$-tuples with $n \ge 4$ nothing further is obtained: arithmeticity is the third and last rung of that ladder. The proof rests on a categorical form of the Chinese Remainder Theorem; in the exact Mal'tsev context this form of the theorem lies close to results of Hoefnagel on majority categories. As a direct application, we give a new proof of Pixley's characterization of arithmetical varieties using a suitable diagram of free algebras.

In earlier work, the authors gave a construction and description of an amalgamated free product of filtered Lie algebras within a fixed nilpotency class, based on an intricate induction rooted in the work of Maier and of Higman. In this paper, the authors give a new description of this amalgam, adopting the viewpoint and methods from the work of A. I. Shirshov on amalgamation of Lie algebras, substantially simplifying their previous approach. This new description yields both group-theoretic and descriptive set-theoretic applications. A $c$-nilpotent group is called UL-equivalent if its lower and upper central series coincide. We prove that every finite $c$-nilpotent group of prime exponent $p$ with $p>c$ embeds in a finite UL-equivalent $c$-nilpotent group of exponent $p$. This recovers a result due to Ivanov and Majcher that the Polish space of enumerated $c$-nilpotent groups of exponent $p>c$ has a comeager orbit. Our result also has the following consequences. First, the class of finite $c$-nilpotent groups of exponent $p>c$ has the cofinal amalgamation property (answering a question of Ivanov and Majcher, who showed that it has the weak amalgamation property). Second, the reduct of the Fraïssé limit of $c$-Lazard groups of exponent $p>c$ to the group language is generic in the space of enumerated groups. Finally, we prove analogues of these results also for torsion-free $c$-nilpotent groups.

We construct a simple expansion of the theory of nonabelian free groups in which the group admits a global type with bounded left-translation orbit but is not definably amenable. This extends the construction of Chernikov, Hrushovski, Kruckman, Krupiński, Moconja, Pillay, and Ramsey, and gives a counterexample to Petrykowski's conjecture.

Finite model finders cannot witness an Austin law: an identity whose finite models are all trivial but which has a nontrivial infinite model. We introduce rank-decreasing sparse trace-tree magmas, finitely presented total operations on a countably infinite constructor-tree carrier. The default product pairs its arguments; finitely many positive Horn clauses define exceptions. Our main procedure derives clauses from symbolic evaluation traces. For every model found, it proves functionality of the exceptional relation by descent on constructor size, proves the identity by exhaustive symbolic case analysis, and emits a self-contained Lean 4 certificate. A least simultaneous fixed point gives an implementation-independent semantics, so bounded search may miss models but cannot invalidate certified results. On ETP's 96 order-five Austin candidates, we discover and Lean-verify infinite countermodels for 28 identities with no prior public classification in our audit. They form 14 duality classes and establish 28 new Austin classifications. Four ALPS-known cases bring the total to 32 certified candidates. On Canonical-4187, the deduplicated union of Order5-130 and the 4,141-row ALPS pool, a fresh trace run produces 636 certificates, all accepted by Judge v3. At equal resource limits, Vampire 5.0.1, E 3.5.1, and complete Twee 2.6.1 jointly prove implications in 94 canonical classes. Only Twee returns trusted counter-satisfiable outcomes, for 18 classes; independent finite-side certificates force 16 to be infinite. None of these ATPs emits an explicit model or Lean certificate, and none decides the 28 new classifications. To the best of our audit, this is the first automated system to synthesize this trace-tree model family, generate well-founded inversion proofs, and emit self-contained Lean 4 certificates.

In the context of constructive reverse mathematics, we show that Brouwer's fixed-point theorem and weak König's lemma (WKL) are equivalent. To derive WKL from Brouwer's fixed-point theorem, the construction of a continuous function on the unit square without fixed points due to Orevkov [Soviet Math. Doklady (1963), 1253–1256] is generalised to yield a uniformly continuous function on the unit square whose fixed points encode information about infinite paths of a given infinite tree.

We solve an open problem posed by Peter Fritz in \cite{Fritz} by proving that there are uncountably many C-Post complete congruential modal logics which are neighborhood complete. The method is algebraic: we construct an uncountable sequence of varieties of modal algebras which are minimal in the lattice of all subvarieties of modal algebras and are generated by a single complete and atomic modal algebra.

We prove that for any cocompact Fuchsian group the class of Medvedev degrees attained by subshifts of finite type is the class of $\Pi_1^0$ degrees. This result relies on the construction of a rigid hierarchical structure in a graph model of the hyperbolic plane, and on the fact that every such group admits a representation in $\operatorname{PSL}_2(\mathbb{R})$ such that the matrices in the image have coefficients that are computable real numbers.

Given a finite family $\mathcal F$ of forbidden $r$-graphs, the Turán problem asks for the maximum asymptotic edge density of $\mathcal F$-free $r$-graphs and the structure of near-extremal examples. We show that both questions can encode arbitrary computation. Fix a universal Turing machine $\mathsf U$. For every sufficiently large fixed $r$, there is a rational $\tau_r\in(0,1)$ such that, from each binary word $\beta$, one can construct a finite family $\mathcal F_{r,\beta}$ with $\pi(\mathcal F_{r,\beta})=\tau_r$ if $\mathsf U$ does not halt on $\beta$, and $\pi(\mathcal F_{r,\beta})>\tau_r$ otherwise. The same dichotomy governs extremal structure. We construct finite families $\mathcal G_{r,\beta}$ such that nonhalting gives a unique extremal limit and Erdős–Simonovits stability, whereas halting gives two nonempty compact extremal phases separated by the sign of a fixed continuous statistic. Hence uniqueness and connectedness of the extremal space, symmetry breaking, two-phase behavior, and stability are all undecidable. The reductions are effective and verifiable in ZFC by finite certificates. Consequently, for every consistent computably axiomatized extension of ZFC and every sufficiently large fixed $r$, there is a finite family $\mathcal F$ for which the true equality $\pi(\mathcal F)=\tau_r$ is neither provable nor refutable; analogous independence holds for the five structural properties above. We also obtain effective approximation, classify exact comparison complexity, and show that the smallest improvement witnesses have Busy-Beaver growth, with no uniform computable positive lower bound on the density gain.

Let $G$ be a definable group in an NIP theory. We prove that every minimal proximal definable $G$-flow is strongly proximal. Consequently, the universal minimal proximal definable $G$-flow $\Pi^{\mathrm{def}}(G)$ coincides with the minimal strongly proximal definable $G$-flow $\Pi^{\mathrm{def}}_{\mathrm{s}}(G)$. Furthermore, for a $p$-adic definable group $G$, we can compute $\Pi^{\mathrm{def}}(G)$ explicitly. We show that $\Pi^{\mathrm{def}}(G)$ is exactly $\Pi^{\mathrm{def}}(S)$ where $S$ is the semisimple part of the definably amenable-semisimple decomposition of $G$. In addition, $\Pi^{\mathrm{def}}(S)\cong S^*_\mathcal{F}(\mathbb{Q}_p)$, the space of types of full dimension on $\mathbf{F}$, where $\mathcal{F}=\mathbf{F}(\mathbb{Q}_p)$ for a flag variety $\mathbf{F}$ constructed from $S$.

For categories, being balanced (meaning that every arrow that is both epic and monic is an isomorphism) can be regarded as a strong tameness property which plays an important role, for example, in algebra and logic. We study the problem of associating a balanced companion category, called a Beth companion, to a locally finitely presentable category (equivalently, the category of models of a finitary essentially algebraic theory). We show that, if it exists, the Beth companion is unique and can be described in terms of saturated objects. Under additional assumptions, we prove that Beth companions can be computed as orthogonality classes, and admit a syntactic presentation via Gabriel–Ulmer duality. Furthermore, we establish conditions for the transfer of properties from a category to its Beth companion. A number of examples of categories that do or do not admit a Beth companion are provided. In particular, we show that the category of commutative rings does not admit a Beth companion, and employ Pierce sheaf representations to describe the Beth companion of other classes of rings.

Combinatorial set theory provides several tools to study derived limits of certain inverse systems of abelian groups. Most known nonvanishing results for $\lim^n$ with $n>1$ depend on some guessing principles of the form $\mathrm{w}\lozenge(S)$ called weak diamonds. In this paper, we explore some applications of the guessing principle $\clubsuit(S)$ and its weakenings instead.

We show that finite-index extensions of essentially free countable Borel equivalence relations are essentially free, answering a question of Kechris.

The Erdős–Dushnik–Miller theorem states that for every aleph $\kappa$, \[ \kappa\to(\kappa,\omega); \] that is, every coloring $c:[\kappa]^2\to2$ has either a $0$-homogeneous set of cardinality $\kappa$ or a $1$-homogeneous set of cardinality $\omega$. In this article, we present a purely combinatorial proof of this theorem in $\mathsf{ZF}$ (i.e., Zermelo–Fraenkel set theory without the axiom of choice), avoiding any metamathematical considerations.

We show that the first-order theory of the Farey graph is $1$-ample but not $2$-ample. Along the way, we prove that it weakly eliminates imaginaries and observe that forking is trivial.

We show that every faithful, transitive, and generically $(n+2)$-transitive action of a connected group $G$ on an irreducible variety $X$ of dimension $n > 0$, all defined over an algebraically closed field $F$, is isomorphic to the natural action of the projective linear group $PGL_{n+1}(F)$ on the projective space $\mathbb{P}^n(F)$. More precisely, we establish the Borovik-Cherlin conjecture for permutation groups $(G,X)$ definable in models of $ACF$.

We prove that if a group $G$ contains a Baumslag-Solitar group $\mathrm{BS}(m,n)$, with $mn\neq0$, then the theory of fields with a $G$-action has no model companion. In particular, every group containing $\mathbb{Z}^2\cong\mathrm{BS}(1,1)$ has no model companion for its field actions, resolving a conjecture of Beyarslan and Kowalski. Consequently, there are no model companions for field actions of $\mathbb{Q}^2$, Thompson's groups $F,T,V$, or Higman's group. Our argument adapts Hrushovski's method for two commuting automorphisms. The key modification is the cyclotomic condition $\theta_q$, which removes the need to prescribe a non-trivial action on a root of unity and thereby makes Hrushovski's method applicable after passing from a subgroup to an ambient group.

In his 1994 doctoral thesis, Bossard introduced the notion of the non-universal tree $T_{NU}(X)$ associated with each separable Banach space $X$ which does not contain an isomorphic copy of $C(2^\mathbb{N})$. Together with the order operation defined on well-founded trees, we obtain a method of classifying the complexity of separable Banach spaces by the degree of isomorphism of finite-dimensional subspaces of $C(2^\mathbb{N})$. Despite further refinement of this concept in later years, we are unaware of any specific instances of direct exhibitions of the order of the non-universal tree for a concrete space and basis. We show that if $H$ is any separable Hilbert space, then $o(T_{NU}(H)) = {\omega} + 1$ when taken with respect to the Haar basis for $C(2^\mathbb{N})$, demonstrating that the class of Hilbert spaces is the least complex class with respect to this measurement when considering this basis.

Hilbert's Tenth Problem over the integers was solved negatively by Y. Matiyasevich in 1970. In this paper, we prove that there is no algorithm to determine for any polynomial equation $P(z_1,\ldots,z_{10})=0$ (with integer coefficients and ten unknowns) whether it has integer solutions. This improves the previous 11 unknowns theorem.

Global representations are subdirect representations satisfying a sheaf-like local-to-global patching principle. We develop a unified and simplified theory of such representations. For quasivarieties with a near-unanimity term, this framework recovers the main classical representation theorems through a common argument and yields a general representation by factors of bounded subdirect width. When the relatively subdirectly irreducible members form a universal class, we obtain an optimal result: every relatively congruence-distributive algebra admits a global representation by relatively globally indecomposable factors, which we characterize explicitly. We also provide a converse: global representations by factors of bounded relative subdirect width force the existence of a near-unanimity term. Adding semisimplicity to the hypotheses of the main theorem yields optimal representation results for filtral quasivarieties and dual discriminator varieties, together with a simple description of the globally indecomposable algebras. The technical engine behind these results is a new infinitary extension of the congruence-system component of the Baker–Pixley theorem.

We prove that a relation obtained by composing arbitrary functions of arity $\leq k$ with a relation definable in an $n$-dependent structure is $kn$-dependent. This confirms a conjecture of Chernikov and Hempel. We also demonstrate optimality of the result.

Factorization in rings of the form $K((G^{\le 0} )) $ exhibits pathological behavior due to divisibility by monomials. It remains open whether this is the only obstruction and whether the quotient by the ideal generated by all monomials is a unique factorization domain. Prior to this work, the only instances of unique factorization beyond the irreducible elements followed directly from the primality of elements which aren't divisible by any monomial and whose support has order type $\omega$ or $\omega+1$. Using the $RV$ tool from valuation theory as a key ingredient, we establish unique factorization for elements of $ K((\mathbb{R}^{\le 0}))$ which aren't divisible by any monomial and whose support has order type $\omega^{\alpha} $ or $\omega^{\alpha}+1 $ for a large class of non additively principal ordinals $\alpha$.

Many statements studied in reverse mathematics can be seen as mathematical problems, formulated in terms of instances and solutions. We develop a framework of typicality encompassing measure and genericity, and we classify the reverse mathematics zoo in terms of which problems admit typical solutions. It turns out that even very weak problems do not admit typical solutions.

A classical result in modal logic states that $\mathsf{S4}$ has $14$ modalities, that is, every sequence of negations, boxes, and diamonds is equivalent to one in a set of $14$ such sequences. We study analogous results for the non-classical analogues $\mathsf{CS4}$, $\mathsf{IS4}$, $\mathsf{GS4}$, and $\mathsf{GS4^c}$ of $\mathsf{S4}$. First, we show that, while all these logics have finitely many $\{\Box,\Diamond\}$- and $\{\neg,\Box\}$-modalities, the logic $\mathsf{CS4}$ has infinitely many $\{\neg,\Diamond\}$-modalities. Second, we show that $\mathsf{IS4}$ and $\mathsf{GS4}$ have finitely many $\{\neg,\Diamond\}$-modalities, but they have infinitely many $\{\neg,\Box,\Diamond\}$-modalities. At last, we show that $\mathsf{GS4^c}$ has finitely many $\{\neg,\Box,\Diamond\}$-modalities.

We characterize the Borel sets with an infinite version of Karchmer and Wigderson's game linking finite circuit complexity to communication complexity. To this end, we formulate an infinite version of communication complexity and prove that a given subset of the Cantor space is Borel if and only if a certain infinite communication game is solvable. We utilize this connection to provide new elementary and purely combinatorial proofs of some classical results in descriptive set theory, including the analytic separation theorem and the equivalence of monotone and positive Borel sets. Another consequence is a characterization of Borel separability via the winner of a certain "cut-and-choose" game, which we use to obtain new combinatorial proofs that neither the set of ill-founded trees nor any infinite parity function is Borel.

We establish the cardinal inequality \(|X|\leq 2^{t(X)H\psi(X)}\) for every Hausdorff SDL space \(X\), where \(t(X)\) and \(H\psi(X)\) denote the tightness and the Hausdorff pseudocharacter of \(X\), respectively. Since both invariants are bounded by \(\chi(X)\), this yields \(|X|\leq 2^{\chi(X)}\). As a consequence, every first-countable Hausdorff strongly cellular–Lindelöf space has cardinality at most the continuum. These results answer Questions~2.1 and~2.2 of Bella and Spadaro. An intermediate result is a uniform bounded-decomposition property for SDL spaces; in particular, their strict quasi–Lindelöf number satisfies \(\sqL(X)\leq t(X)\).

For all $n \ge 2$, we obtain a homeomorphism of Cantor space that has a distributionally $n$-scrambled Cantor set containing a distributionally $(n+1)$-scrambled uncountable set, but does not have an $(n+1)$-scrambled Cantor set.

We study the Gödel–Löb provability logic $\mathbf{GL}$ for finite derived topologies on the ordinals. Assuming GCH and the existence of a measurable cardinal $\kappa$ which carries a coherent sequence of normal measures $\vec{U}$ with $o^{\vec{U}}(\kappa)\geq\kappa$, we obtain a cofinality and GCH preserving generic extension in which $\text{Log}_d(\kappa,\tau_n)=\mathbf{GL}$ for every $n<\omega$, where $\tau_n$ is the $n$-th derived topology. The result answers a well-know open question. Extending Beklemishev's theorem, we show that in the same model, for every $k<\omega$, $ \text{Log}_d(\kappa;\tau_{2k},\tau_{2k+1})=\mathbf{GLP}_2, $ where the two modalities of $\mathbf{GLP}_2$ are interpreted respectively by $d_{2k}$ and $d_{2k+1}$.

We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs–a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours–despite being unable to canonise such graphs.

Using ChatGPT 5.6, we find a counterexample to the stable forking conjecture. This answers a long-standing open question of Hart, Kim and Pillay (1996).

In this paper, we establish exponential separations between Extended Frege systems for a range of intuitionistic substructural and linear logics. More precisely, for any logic $L$ below the intuitionistic logic obtained by extending $\mathbf{ILL}$ with structural rules, and any logic $M$ not contained in $L$, we construct a family of $\mathsf{FL_e}$-provable formulas that have short proofs in $M$-Frege but require proofs of exponential size in $L$-Extended Frege. The same result holds in the $!$-free settings, using $\mathbf{IMALL}$ and $\mathbf{FL_e}$ in place of $\mathbf{ILL}$. The key ingredient in proving these separations is a variant of the feasible disjunction property for $L$-Frege, which may be of independent interest.