In a joint work with Daniel Fiorilli, we develop a new method to prove lower bounds of some moments related to the distribution of primes in arithmetic progressions. We shall present main results and explain some aspects of the proofs. To prove our results, we assume GRH but we succeed to avoid linearly independence on zeroes hypothesis.
The symmetric group Smn acts naturally on the collection of set partitions of a set of size mn into n sets each of size m. The irreducible constituents of the associated ordinary character are largely unknown; in particular, they are the subject of the longstanding Foulkes Conjecture. There are equivalent reformulations using polynomial representations of infinite general linear groups or using plethysms of symmetric functions. I will review plethysm from these three perspectives before presenting a new approach to studying plethysm: using the Schur-Weyl duality between the symmetric group and the partition algebra. This method allows us to study stability properties of certain plethysm coefficients. This is joint work with Chris Bowman. If time permits, I will also discuss some new results with Chris Bowman and Mark Wildon.
We discuss some recent progress on the model-theoretic problem of classifying the reducts of the complex field (with named parameters and up to interdefinability). The tools we use include Castle’s recent solution of the Restricted Trichotomy Conjecture in characteristic 0 and a generalized sumproduct result from additive combinatorics.
The classical shuffle theorem states that the Frobenius character of the space of diagonal harmonics is given by a certain combinatorial sum indexed by parking functions on square lattice paths. The rational shuffle theorem, conjectured by Gorsky-Negut and proven by Mellit, states that the geometric action on symmetric functions (described by Schiffmmann-Vasserot) of certain elliptic Hall algebra elements P(m,n) yield the bigraded Frobenius character of a certain Sn representation. This character is known as the Hikita polynomial. In this talk I will introduce the higher-rank rational (q,t)-Catalan polynomials and show these are equal to finite truncations of the Hikita polynomial. By generalizing results of Gorsky-Mazin-Vazirani and constructing an explicit bijection between rational semistandard parking functions and affine compositions, I will derive a finite analogue of the rational shuffle theorem in the context of spherical double affine Hecke algebras.
A set of integers greater than 1 is primitive if no member in the set divides another. Erdős proved in 1935 that the sum of 1/(a log a), ranging over a in A, is uniformly bounded over all choices of primitive sets A. In 1986 he asked if this bound is attained for the set of prime numbers. In this talk we describe recent work which answers Erdős’ conjecture in the affirmative. We will also discuss applications to old questions of Erdős, Sárközy, and Szemerédi from the 1960s.
Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering in particular a question posed by Chapman, Linial and Peled positively.
This talk is based on joint work with Marston Conder, Alexander Lubotzky and Francois Thilmany.
This video was produced by the Sydney Mathematical Research Institute, as part of their SMRI seminar series.
In late 2021, Bloom resolved an old conjecture of Erdős and Graham, showing that in any subset of the positive integers of positive density, there exists a solution to 1/n1 + 1/n2 + ... + 1/nk = 1 with all ni distinct. We discuss the formal verification of this proof in the Lean theorem prover, including prerequisites from analytic number theory and Fourier analysis, and an instance of the circle method. This is joint work with Thomas Bloom.
Given several real numbers α1,...,αk, how well can you simultaneously approximate all of them by rationals which each have the same square number as a denominator? Schmidt gave a clever iterative argument which showed that this can be done moderately well.
By using a general principle of 'little non-trivial additive structure in rationals' and some ideas from additive combinatorics and the geometry of numbers, I'll describe how this can be improved to give a close-to-optimal answer when k is large.
A famous conjecture of Littlewood states that the Fourier transform of every set of N integers has l1 norm at least log(N), up to a constant multiplicative factor. This was proved independently by McGehee-Pigno-Smith and Konyagin in the 1980s. This lower bound is the best possible, as it is achieved by an arithmetic progression. An interesting question, especially from the perspective of additive combinatorics, is the 'inverse problem': what can we say about sets which are close to optimal, say with l1 norm at most 100 log(N)? I will discuss can inverse result of this type, showing that (in a certain sense) such sets are approximately the union of O(1) sets with small doubling.
Computing many-body ground state energies and resolving electronic structure calculations are fundamental problems for fields such as quantum chemistry or condensed matter. Several quantum computing algorithms that address these problems exist, although it is often challenging to establish rigorous bounds on their performances. I shall first consider the general task of approximating the ground state energy of quantum Hamiltonians on bounded-degree graphs. I will discuss our approach to go beyond product state approximations for a quantum analog of the Max Cut problem, where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case - and more recent work by others has improved on this strategy further. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation). Then, I will describe our more recent work to generalize this approach to other bounded-degree local Hamiltonians, where we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. Finally, I will discuss results demonstrating the performance of these algorithms via numerical experiments on a 2-dimensional Hubbard model, starting from a checkerboard product state, as well as on some chemistry Hamiltonians, using the Hartree-Fock state as reference. In both cases, we show that the approximate energies produced are close to the exact ones. These algorithms provide a way to systematically improve the estimation of ground state energies and can be used stand-alone or in conjunction with existing quantum algorithms for ground states.
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any non-trivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold.
I will discuss the dictionary between the algebraic structure of a right-angled Artin group and the combinatorics of the defining graph. I will then use the cohomology of a right-angled Artin group to provide a characterization of Hamiltonicity of the underlying graph. Along the way, I will describe some linear algebraic facts which appear to have been previously unknown.
It is well known that if a finite set of integers A tiles the integers by translations, then the translation set must be periodic, so that the tiling is equivalent to a factorization A+B=ZM of a finite cyclic group. Coven and Meyerowitz (1998) proposed a characterization of all finite tiles in terms of the cyclotomic divisors of associated mask polynomials, and proved it when the tiling period M has at most two distinct prime factors. In joint work with Itay Londner, we extended it to the case when M=(pqr)2, where p,q,r are distinct primes. The methods we developed can be applied to other questions that hinge on cyclotomic divisibility, ranging from number theory to harmonic analysis and geometric measure theory. In particular, Caleb Marshall and I were able to use cyclotomic divisibility methods to prove new Favard length estimates for product Cantor sets. The talk will provide an introduction to this group of problems.
I will review two combinatorial constructions of integrable systems: Goncharov-Kenyon construction based on counting perfect matchings in bipartite graphs, and Gekhtman-Shapiro-Tabachnikov-Vainshtein construction based on counting paths in networks. After that I will outline my proof of equivalence of those constructions.
In many recent works, analysis and number theory go beyond working side by side and team up in an interconnected back and forth interplay to become a powerful force. Here I describe two distinct meetings of the pair, which result in sharp counts for equilateral triangles in Euclidean space and statistics for how often a random polynomial has Galois group not isomorphic to the full symmetric group.
In Bernoulli bond percolation, one defines a random subgraph of a given connected graph G by deleting or retaining edges of G independently at random, each edge being retained with the same probability p. When G is infinite, a central and classical question is whether there exists a choice of p strictly less than 1 such that this random subgraph has infinite connected components. When G is finite, a natural analogue is to ask whether there exists a choice of p bounded away from 1 such that the random subgraph contains a connected component containing at least half (or 1% or 99%) of the vertices of G. Tom Hutchcroft and I recently showed that such a p exists provided G is not close to a cycle in some sense, confirming most cases of a conjecture of Benjamini (2001). I will give an overview of the proof, and go into some detail on certain aspects of it that have a distinctly additive combinatorial flavour.
We prove that the size of the product set of any finite arithmetic progression A in integers of size N is at least N2/(log N)c+o(1), where c=1-(1+loglog 2)/(log 2). This matches the bound in the celebrated Erdos multiplication table problem, up to a factor of (log N)o(1) and thus confirms a conjecture of Elekes and Ruzsa. If instead A is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that the size of the product set is at least N2/(log N)2log2-1 + o(1). This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set A whose sum set is of size O(|A|).This is joint work with Yunkun Zhou.
(Joint with Jacob Fox, Matthew Kwan) Classical anti-concentration results show "random walks in ℝd with BIG independent steps can't concentrate in balls much better than they can concentrate on individual points". Model-theoretic definable sets include boolean combinations of subsets of ℝd defined using equalities and inequalities of arbitrary compositions of polynomials, ex, ln(x) and analytic functions restricted to compact boxes. For example, the intersection of esin(1/(1+(xyz)2))+x2y+zy ≥ 0 and xyz=5 in ℝ3. In this talk, I will discuss recent results which show "random walks in ℝd with ARBITRARY independent steps can't concentrate in definable sets not containing line segments much better than they can concentrate on individual points". Time permitting, I will discuss how these results extend to other groups like GLd(ℝ).
In 2001 Croot resolved an old conjecture of Erdős and Graham, proving that in any finite colouring of the positive integers there is a (non-trivial) monochromatic solution to 1/n1+...+1/nk = 1 with all ni distinct. A natural generalisation, also conjectured by Erdos and Graham, is that in fact any set of positive density contains such a solution. We will discuss the proof of this conjecture, which extends Croot's method, and uses Fourier analysis coupled with elementary number theoretic and combinatorial arguments.
The Graph Isomorphism (GI) problem is arguably the most widely known problem whose membership in P is unknown, but which is not believed to be NP-hard. While the existence of a polynomial-time algorithm on general graphs is still elusive, the complexity of Graph Isomorphism has been well understood on several classes of graphs, where structural properties of graphs in question have been used to design polynomial-time procedures solving the problem. In this talk we will look at some of these algorithms for Graph Isomorphism through the perspective of contributions of the speaker.
