Search

The Ceresa cycle is an algebraic 1-cycle on the Jacobian of an algebraic curve. Although it is homologically trivial, Ceresa famously proved that for a very general complex curve of genus at least 3, it is non-trivial in the Chow group. In this paper we study the Ceresa cycle attached to the complete modular curve $X_{0}(N)$. For prime level $p$ we give a complete description, namely we prove that if $X_{0}(p)$ is not hyperelliptic, then its Ceresa cycle is non-torsion. For general level $N$, we prove that there are finitely many $X_{0}(N)$ with torsion Ceresa cycle. Our method relies on the relationship between the vanishing of the Ceresa cycle and Chow-Heegner points on the Jacobian. We use the geometry and arithmetic of modular Jacobians to prove that such points are of infinite order and therefore deduce non-vanishing of the Ceresa cycle., Comment: comments welcome!

Automated reasoners, such as SAT/SMT solvers and first-order provers, are becoming the backbones of rigorous systems engineering, being used for example in applications of system verification, program synthesis, and cybersecurity. Automation in these domains crucially depends on the efficiency of the underlying reasoners towards finding proofs and/or counterexamples of the task to be enforced. In order to gain efficiency, automated reasoners use dedicated proof rules to keep proof search tractable. To this end, (variants of) subsumption is one of the most important proof rules used by automated reasoners, ranging from SAT solvers to first-order theorem provers and beyond. It is common that millions of subsumption checks are performed during proof search, necessitating efficient implementations. However, in contrast to propositional subsumption as used by SAT solvers and implemented using sophisticated polynomial algorithms, first-order subsumption in first-order theorem provers involves NP-complete search queries, turning the efficient use of first-order subsumption into a huge practical burden. In this paper we argue that the integration of a dedicated SAT solver opens up new venues for efficient implementations of first-order subsumption and related rules. We show that, by using a flexible learning approach to choose between various SAT encodings of subsumption variants, we greatly improve the scalability of first-order theorem proving. Our experimental results demonstrate that, by using a tailored SAT solver within first-order reasoning, we gain a large speedup in solving state-of-the-art benchmarks.

Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal message passing mechanisms from literature into two main types: global and local, and establish Weisfeiler-Leman characterisations for both. This allows us to formally analyse expressive power of temporal message-passing models. We show that global and local temporal message-passing mechanisms have incomparable expressive power when applied to arbitrary temporal graphs. However, the local mechanism is strictly more expressive than the global mechanism when applied to colour-persistent temporal graphs, whose node colours are initially the same in all time points. Our theoretical findings are supported by experimental evidence, underlining practical implications of our analysis., Comment: 18 pages

The distribution of degree $d$ points on curves is well understood, especially for low degrees. We refine this study to include information on the Galois group in the simplest interesting case: $d = 3$. For curves of genus at least 5, we show cubic points with Galois group $C_3$ arise from well-structured morphisms, along with providing computable tests for the existence of such morphisms. We prove the same for curves of lower genus under some geometric or arithmetic assumptions., Comment: Comments welcome (14 pages)

We present the CheckMate tool for automated verification of game-theoretic security properties, with application to blockchain protocols. CheckMate applies automated reasoning techniques to determine whether a game-theoretic protocol model is game-theoretically secure, that is, Byzantine fault tolerant and incentive compatible. We describe CheckMate's input format and its various components, modes, and output. CheckMate is evaluated on 15 benchmarks, including models of decentralized protocols, board games, and game-theoretic examples.

Bjorn Poonen asked whether there exists a polynomial giving a surjection $\mathbb{Z} \times \mathbb{Z} \to \mathbb{N}$. We answer this question in the negative, conditional on a conjecture of Vojta. More precisely, we show that if such a function exists, there is a family of open surfaces with dense integral points despite the surfaces being of log general type., Comment: 11 pages, 1 figure. Comments welcome!

Classically, in saturation-based proof systems, unification has been considered atomic. However, it is also possible to move unification to the calculus level, turning the steps of the unification algorithm into inferences. For calculi that rely on unification procedures returning large or even infinite sets of unifiers, integrating unification into the calculus is an attractive method of dovetailing unification and inference. This applies, for example, to AC-superposition and higher-order superposition. We show that first-order superposition remains complete when moving unification rules to the calculus level. We discuss some of the benefits this has even for standard first-order superposition and provide an experimental evaluation., Comment: 16 pages, 0 figures, 1 table

Rewriting techniques based on reduction orderings generate "just enough" consequences to retain first-order completeness. This is ideal for superposition-based first-order theorem proving, but for at least one approach to inductive reasoning we show that we are missing crucial consequences. We therefore extend the superposition calculus with rewriting-based techniques to generate sufficient consequences for automating induction in saturation. When applying our work within the unit-equational fragment, our experiments with the theorem prover Vampire show significant improvements for inductive reasoning.

We develop an effective algorithm to compute the derivative of a Bianchi modular form with respect to weight space as it varies in a $p$-adic family. This method is entirely local at the modular form, and does not compute the family anywhere outside an infinitesimal neighbourhood. We numerically verify some conjectures surrouding smoothness of the eigenvariety (equivalently, uniqueness of families) and the ``direction over weight space'' of the family. The methods are also applied to study elliptic modular forms and their $\mathcal{L}$-invariants., Comment: 15 pages. Comments welcome!

We propose a new encoding of the first-order connection method as a Boolean satisfiability problem. The encoding eschews tree-like presentations of the connection method in favour of matrices, as we show that tree-like calculi have a number of drawbacks in the context of satisfiability solving. The matrix setting permits numerous global refinements of the basic connection calculus. We also show that a suitably-refined calculus is a decision procedure for the Bernays-Sch\"onfinkel class.

Subsumption resolution is an expensive but highly effective simplifying inference for first-order saturation theorem provers. We present a new SAT-based reasoning technique for subsumption resolution, without requiring radical changes to the underlying saturation algorithm. We implemented our work in the theorem prover Vampire, and show that it is noticeably faster than the state of the art.

In this paper we give an algorithm to find the 3-torsion subgroup of the Jacobian of a smooth plane quartic curve. We describe $3-$torsion points in terms of cubics which triply intersect the curve, and use this to define a system of equations whose solution set corresponds to the coefficients of these cubics. We compute the points of this zero-dimensional, degree $728$ scheme first by approximation, using homotopy continuation and Newton-Raphson, and then using lattice reduction or continued fractions to obtain accurate expressions for these points. We describe how the Galois structure of the field of definition of the $3$-torsion subgroup can be used to compute local conductor exponents, including at $p=2$., Comment: 18 pages, comments welcomed

Hyperspectral measurements from long range sensors can give a detailed picture of the items, materials, and chemicals in a scene but analysis can be difficult, slow, and expensive due to high spatial and spectral resolutions of state-of-the-art sensors. As such, sparsity is important to enable the future of spectral compression and analytics. It has been observed that environmental and atmospheric effects, including scattering, can produce nonlinear effects posing challenges for existing source separation and compression methods. We present a novel transformation into Hilbert spaces for pruning and constructing sparse representations via non-negative least squares minimization. Then we introduce max likelihood compression vectors to decrease information loss. Our approach is benchmarked against standard pruning and least squares as well as deep learning methods. Our methods are evaluated in terms of overall spectral reconstruction error and compression rate using real and synthetic data. We find that pruning least squares methods converge quickly unlike matching pursuit methods. We find that Hilbert space pruning can reduce error by as much as 40% of the error of standard pruning and also outperform neural network autoencoders.

There is increasing focus on analyzing data represented as hypergraphs, which are better able to express complex relationships amongst entities than are graphs. Much of the critical information about hypergraph structure is available only in the intersection relationships of the hyperedges, and so forming the "intersection complex" of a hypergraph is quite valuable. This identifies a valuable isomorphism between the intersection complex and the "concept lattice" formed from taking the hypergraph's incidence matrix as a "formal context": hypergraphs also generalize graphs in that their incidence matrices are arbitrary Boolean matrices. This isomorphism allows connecting discrete algorithms for lattices and hypergraphs, in particular s-walks or s-paths on hypergraphs can be mapped to order theoretical operations on the concept lattice. We give new algorithms for formal concept lattices and hypergraph s-walks on concept lattices. We apply this to a large real-world dataset and find deep lattices implying high interconnectivity and complex geometry of hyperedges.

Cryptographic protocols are hard to design and prove correct, as witnessed by the ever-growing list of attacks even on protocol standards. Symbolic models of cryptography enable automated formal security proofs of such protocols against an idealized model, which abstracts away from the algebraic properties of cryptographic schemes and thus misses attacks. Computational models yield rigorous guarantees but support at present only interactive proofs and/or restricted classes of protocols. A promising approach is given by the computationally complete symbolic attacker (CCSA), formalized in the BC Logic, which aims at bridging and getting the best of the two worlds, obtaining cryptographic guarantees by symbolic analysis. The BC Logic is supported by a recently developed interactive theorem prover, Squirrel, which enables machine-checked interactive security proofs, as opposed to automated ones, thus requiring expert knowledge. We introduce the CryptoVampire cryptographic protocol verifier, which for the first time fully automates proofs of trace properties in the BC Logic. The key technical contribution is a first-order (FO) formalization of protocol properties with tailored handling of subterm relations. We overcome the burden of interactive proving in higher-order (HO) logic and automatically establish soundness of cryptographic protocols using only FO reasoning. On the theoretical side, we restrict full FO logic with cryptographic axioms to ensure that, by losing the expressivity of the HO BC Logic, we do not lose soundness. On the practical side, CryptoVampire integrates dedicated proof techniques using FO saturation algorithms and heuristics, which enable leveraging the state-of-the-art Vampire FO theorem prover as the underlying proving engine. Our experimental results show CryptoVampire's effectiveness of as a standalone verifier and in terms of automation support for Squirrel.

Linear neural network layers that are either equivariant or invariant to permutations of their inputs form core building blocks of modern deep learning architectures. Examples include the layers of DeepSets, as well as linear layers occurring in attention blocks of transformers and some graph neural networks. The space of permutation equivariant linear layers can be identified as the invariant subspace of a certain symmetric group representation, and recent work parameterized this space by exhibiting a basis whose vectors are sums over orbits of standard basis elements with respect to the symmetric group action. A parameterization opens up the possibility of learning the weights of permutation equivariant linear layers via gradient descent. The space of permutation equivariant linear layers is a generalization of the partition algebra, an object first discovered in statistical physics with deep connections to the representation theory of the symmetric group, and the basis described above generalizes the so-called orbit basis of the partition algebra. We exhibit an alternative basis, generalizing the diagram basis of the partition algebra, with computational benefits stemming from the fact that the tensors making up the basis are low rank in the sense that they naturally factorize into Kronecker products. Just as multiplication by a rank one matrix is far less expensive than multiplication by an arbitrary matrix, multiplication with these low rank tensors is far less expensive than multiplication with elements of the orbit basis. Finally, we describe an algorithm implementing multiplication with these basis elements., Comment: Comments welcome!

Noting that lemmas are a key feature of mathematics, we engage in an investigation of the role of lemmas in automated theorem proving. The paper describes experiments with a combined system involving learning technology that generates useful lemmas for automated theorem provers, demonstrating improvement for several representative systems and solving a hard problem not solved by any system for twenty years. By focusing on condensed detachment problems we simplify the setting considerably, allowing us to get at the essence of lemmas and their role in proof search., Comment: Extended version of the TABLEAUX 2023 contribution

Concurrent programming is used in all large and complex computer systems. However, concurrency errors and system failures (ex: crashes and deadlocks) are common. We find that Petri nets can be used to model concurrent systems and find and remove errors ahead of time. We introduce a novel generalization of Petri nets with nondeterministic transition nodes to match real systems. These allow for a compact way to construct, optimize, and prove computer programs at the concurrency level. Petri net programs can also be optimized by automatically solving for maximal concurrency, where the maximum number of valid threads is determined by the structure of the Petri net prior to execution. We discuss an algorithm to compute the state graph of a given Petri net start state pair. We introduce our open source software framework which implements this theory as a general purpose concurrency focused middle-ware.

It is known that for a curve defined over $\mathbb{Q}$ of genus $g \leq 4$, there exists a point on the curve defined over a solvable extension of $\mathbb{Q}$. We relate points on curves of genus $g \geq 5$ over solvable extensions to the Bombieri-Lang conjecture. Specifically, it shows that varieties parameterising points defined over extensions with a fixed solvable Galois group are of general type. Moreover, we show the existence of certain subvarieties in these varieties imply the existence of solvable morphisms from the curve.

Purpose To develop and evaluate a deep learning-based method (MC-Net) to suppress motion artifacts in brain magnetic resonance imaging (MRI). Methods MC-Net was derived from a UNet combined with a two-stage multi-loss function. T1-weighted axial brain images contaminated with synthetic motions were used to train the network. Evaluation used simulated T1 and T2-weighted axial, coronal, and sagittal images unseen during training, as well as T1-weighted images with motion artifacts from real scans. Performance indices included the peak signal to noise ratio (PSNR), structural similarity index measure (SSIM), and visual reading scores. Two clinical readers scored the images. Results The MC-Net outperformed other methods implemented in terms of PSNR and SSIM on the T1 axial test set. The MC-Net significantly improved the quality of all T1-weighted images (for all directions and for simulated as well as real motion artifacts), both on quantitative measures and visual scores. However, the MC-Net performed poorly on images of untrained contrast (T2-weighted). Conclusion The proposed two-stage multi-loss MC-Net can effectively suppress motion artifacts in brain MRI without compromising image context. Given the efficiency of the MC-Net (single image processing time ~40ms), it can potentially be used in real clinical settings. To facilitate further research, the code and trained model are available at https://github.com/MRIMoCo/DL_Motion_Correction.