VT Algebra Seminar — Spring 2023

Hilbert's tenth problem was to give an algorithm which took as input a polynomial with integer coefficients and would output YES if that polynomial had an integer zero and NO otherwise. Matiyasevich, building on work of Davis, Putnam, and Robinson, showed that no such algorithm can exist. One can rephrase H10 then over other rings, such as the rationals. It is not known whether there exists an algorithm which takes a rational polynomial as input and decides whether it has a rational zero. If the integers were diophantine over the rationals (i.e. cut out by polynomial equations or, to be precise, defined by a first order existential formula) then H10 over the rationals would also be undecidable. While it is generally not believed that the integers are diophantine over the rationals, studying the diophantine sets still sheds light on the first order theory of these rings. If Z were not diophantine over Q, we may still hope to give a first order definition of it. Robinson gave the first, which was improved by Poonen. Koenigsmann showed the integers are defined by a universal formula; equivalently, the non-integral rationals are diophantine! In this talk, I will give an introduction to decidability and definability in number theory and discuss some of my work in this area, namely on first-order universal definitions of S-integers in global function fields and on the diophantineness of some quirky sets, like the collection of non-nth powers in a global field (originally a result of Colliot-Thelene and Van Geel, which we recover by showing that the non-norms of a cyclic extension are diophantine).

To prevent timing attacks, cryptographic protocols are usually implemented using constant-time algorithms; that is, algorithms whose running time is independent of any secret information. Often, these constant-time algorithms are implemented using dummy operations: operations which are performed but whose results are discarded. Dummy operations can lead to fault attacks: attacks which are designed to learn secret information by creating errors during computations. In this talk, I will discuss the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) key establishment protocol, how naïve constant-time implementations could be vulnerable to fault attacks, and several techniques from the literature which can be used to combat those attacks.

In 1977, Solomon defined a lattice zeta function counting the number of full-rank sublattices of Z^d of any given index, and found a “rational" formula in terms of the Riemann zeta function. We study a “singular" analog of the lattice zeta function by replacing Z by Fq[[T^2,T^3]], the ring of a cusp singularity, and we prove a rationality result. One important ingredient involves introducing a fun combinatorial construction, which is some ``spiral shifting'' operators acting on the set of d-tuples of nonnegative integers. I will use concrete examples to demonstrate several nice properties of these operators, hopefully interactively. I will then explain how this construction is applied to the rationality of the lattice zeta function. This talk is based on joint work with Ruofan Jiang.

Using equivariant Todd (resp. Hirzebruch) classes of toric varieties, we translate the equivariant Hirzebruch-Riemann-Roch theorem for simplicial projective toric varieties into various (weighted) Euler-Maclaurin type formulae for simple lattice polytopes. This is joint work with S. Cappell, L. Maxim and J. Shaneson.

This talk explores the connections between the maximum number of zeros of equations over finite fields and generalized Hamming weights. We show how the two problems are related and present different approaches used to solve them. Specifically, we discuss how to compute the maximum number of zeros, provide bounds, and design algorithms. We illustrate these approaches with examples and discuss open problems and future directions for research.

Zero-knowledge proof (ZKP) systems allow a prover holding some secret witness w for a statement x satisfying some NP relation R, to prove knowledge of w to a verifier (the soundness property), without revealing any information on w to the verifier (the zero-knowledge property). ZKPs have applications in privacy-preserving cryptographic protocols. However, for statements with large witnesses w, the main limitation of classical ZKPs is that their proof size is proportional to the witness size. To support several applications, it is desirable to have succinct ZKPs in which the proof size is only polylogarithmic in the witness size. In this talk I’ll discuss our construction of a lattice-based Zero-Knowledge Succinct Non-interactive Argument of Knowledge (ZK-SNARK) for NP languages addressing some challenges during the construction and present some open questions.

I will explain how certain questions from enumerative geometry lead to the of definition the quantum cohomology ring, which deforms the ordinary cohomology ring. The structure constants of the quantum ring are called Gromov-Witten invariants, and count rational curves intersecting several subvarieties. If time permits, I will explain how the `quantum = classical' statement gives an algorithm calculating the Gromov-Witten invariants for Grassmannians.

TBA

TBA