Réunion d'été du 75e+1 anniversaire de la SMC

Ottawa, 7 - 11 juin 2021

Théorie additive des nombres et la combinatoire arithmétique
Org: Jozsef Solymosi (UBC) et Jacques Verstraete (UC San Diego)
[PDF]

THOMAS BLOOM, University of Oxford
Structure of large spectra: problems and constructions  [PDF]

Given a subset of a finite abelian group, its large spectrum is the set of Fourier coefficients which are unusually large in absolute value. Obtaining a deeper understanding of such sets, in particular how much additive structure they must have, has been at the heart of many of the advances in additive combinatorics in recent years.

For example, in recent joint work with Olof Sisask, building upon ideas of Bateman and Katz, we proved a particularly strong structural result about certain kinds of large spectrum, which allowed us to obtain new bounds for sets without three-term arithmetic progressions.

In this talk I will give a survey of our current understanding of such sets, what they can look like, and will highlight some of the gaps in our knowledge, in particular some conjectures that, if solved, should yield further progress on the bounds for sets without three-term arithmetic progressions.

ERNIE CROOT, Georgia Tech
On a problem of Graham, Erdos, and Pomerance on the p-divisibility of central binomial coefficients  [PDF]

This is joint work with Hamed Mousavi and Maxie Schmidt. We show that for any set of $r \geq 1$ sufficiently large primes $p_1,...,p_r$, there are infinitely many integers $n$, such that ${2n \choose n}$ is divisible by these primes with multiplicity of size at most $o(\log n)$. This is equivalent to saying we can find integers $n$ whose base $p_1$, base $p_2$, ..., and base $p_r$ expansions all simultaneously have almost all their digits small''. Doing this for 2 primes at once (the case r=2) is not difficult (Erdos proved this version); but it is significantly more challenging to prove it for $r \geq 3$; in fact, Graham offered a large sum of money -- and considered it to be one of his favorite problems -- to solve the case r=3 for the primes $3,5,$ and $7$. Our proof involves bypassing a deep, unsolved problem in diophanine approximation and algebraic number theory, called Schanuel's Conjecture, through the use of a number of methods from analytic number theory and additive combinatorics (and properties of generalized Vandermonde and totally positive matrices).

BRANDON HANSON, University of Maine
Higher order convexity and iterated convolution  [PDF]

We discuss recent progress on how the additive structure of a set of real numbers is perturbed by functions with non-vanishing derivatives. In particular, if a set $A$ has sufficient additive structure and $f$ is a sufficiently convex function, then there are relatively few solutions to $f(a_1)+...+f(a_k)=f(a_1')+...+f(a_k')$ for appropriate ranges of $k$. This is joint work with P. Bradshaw and M. Rudnev.

ALEX IOSEVICH, University of Rochester
Point configurations and applications  [PDF]

We are going to discuss some recent results pertaining to the analytic and combinatorial aspects of finite point configurations. We shall discuss some applications of these ideas in frame theory and related areas.

AKOS MAGYAR, University of Georgia
Distance graphs in sets of positive density  [PDF]

A distance graph is a graph with vertices in a Euclidean space. Two graphs are called isometric if there is a one to one correspondence between their vertices which keeps the length of the corresponding edges. We study distance graphs, as well as their dilates, that can be embedded into sets of positive density of Euclidean spaces or the integer lattice.

MELVYN NATHANSON, LEHMAN COLLEGE (CUNY)
Sidon sets for linear forms  [PDF]

Let $\varphi(x_1,\ldots, x_h) = c_1 x_1 + \cdots + c_h x_h$ be a linear form with coefficients in a field $\mathbf{F}$ and let $V$ be a vector space over $\mathbf{F}$. A nonempty subset $A$ of $V$ is a \textit{$\varphi$-Sidon set} if $\varphi(a_1,\ldots, a_h) = \varphi(a'_1,\ldots, a'_h)$ implies $(a_1,\ldots, a_h) = (a'_1,\ldots, a'_h)$ for all $h$-tuples $(a_1,\ldots, a_h) \in A^h$ and $(a'_1,\ldots, a'_h) \in A^h$. There exist infinite Sidon sets for the linear form $\varphi$ if and only if the set of coefficients of $\varphi$ has distinct subset sums. In a normed vector space with $\varphi$-Sidon sets, every infinite sequence of vectors is asymptotic to a $\varphi$-Sidon set of vectors. Results on $p$-adic perturbations of $\varphi$-Sidon sets of integers and bounds on the growth of $\varphi$-Sidon sets of integers are also obtained.

SARAH PELUSE, IAS/Princeton
Modular zeros in the character table of the symmetric group  [PDF]

In 2017, Miller conjectured, based on computational evidence, that for any fixed prime $p$ the density of entries in the character table of $S_n$ that are divisible by $p$ goes to $1$ as $n$ goes to infinity. I’ll describe a proof of this conjecture, which is joint work with K. Soundararajan. I will also discuss the (still open) problem of determining the asymptotic density of zeros in the character table of $S_n$, where it is not even clear from computational data what one should expect.

GIORGIS PETRIDIS, The University of Georgia
Almost orthogonal sets over finite fields  [PDF]

The talk will be on joint work with Ali Mohammadi on the proof of a conjecture of Ahmadi and Mohammadian who studied a question of Erdos in the setting of vector spaces over finite fields: How large can a subset of $\mathbb{F}_q^n$ be with the property that among any three vectors there is an orthogonal pair?

COSMIN POHOATA, Yale University
Perfect $k$-hash codes  [PDF]

A code of length $n$ over an alphabet of size $k \geq 3$ is a subset $\mathcal{F}$ of $\left\{0,1,\ldots,k-1\right\}^n$. Such a code is called a perfect $k$-hash code if for every subset of $k$ distinct elements (or "codewords") of $\mathcal{F}$, say $\left\{c^{(1)},\ldots,c^{(k)}\right\}$, there exists a coordinate $i$ such that all these elements differ in this coordonate, namely $\left\{c^{(1)}_{i},\ldots,c^{(k)}_{i}\right\}=\left\{0,1,\ldots,k-1\right\}$. The problem of finding the maximum size of perfect $k$-hash codes is a fundamental problem in theoretical computer science, which turns out to be related with multiple famous questions in extremal and additive combinatorics. In this talk, we will quickly survey the state of the art and discuss some of these intriguing connections (and various natural open questions which arise).

OLIVER ROCHE-NEWTON, RICAM
Additive and Multiplicative Sidon Sets  [PDF]

An additive Sidon set is a set which contains no non-trivial solutions to the equation $a+b=c+d$. Multiplicative Sidon sets are defined analogously. This talk considers a problem about Sidon sets with a sum-product flavour: for an arbitrary set of real numbers $A$, is it guaranteed that $A$ contains a large additive or multiplicative Sidon set? In joint work with Audie Warren, we constructed a set which does not contain very large additive or multiplicative Sidon sets. I will discuss this construction and some other thoughts concerning this problem and similar ones.

LISA SAUERMANN, Institute for Advanced Study
Finding solutions with distinct variables to systems of linear equations over $\mathbb{F}_p$  [PDF]

Let us fix a prime $p$ and a homogeneous system of $m$ linear equations $a_{j,1}x_1+\dots+a_{j,k}x_k=0$ for $j=1,\dots,m$ with coefficients $a_{j,i}\in\mathbb{F}_p$. Suppose that $k\geq 3m$, that $a_{j,1}+\dots+a_{j,k}=0$ for $j=1,\dots,m$ and that every $m\times m$ minor of the $m\times k$ matrix $(a_{j,i})_{j,i}$ is non-singular. Then we prove that for any (large) $n$, any subset $A\subseteq\mathbb{F}_p^n$ of size $|A|> C\cdot \Gamma^n$ contains a solution $(x_1,\dots,x_k)\in A^k$ to the given system of equations such that the vectors $x_1,\dots,x_k\in A$ are all distinct. Here, $C$ and $\Gamma$ are constants only depending on $p$, $m$ and $k$ such that $\Gamma<p$.

The crucial point here is the condition for the vectors $x_1,\dots,x_k$ in the solution $(x_1,\dots,x_k)\in A^k$ to be distinct. If we relax this condition and only demand that $x_1,\dots,x_k$ are not all equal, then the statement would follow easily from Tao's slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

ILYA SHKREDOV, Steklov Mathematical Institute
On an application of higher energies to Sidon sets  [PDF]

We show that for any finite set $A$ and an arbitrary $\varepsilon>0$ there is $k=k(\varepsilon)$ such that the higher energy $\mathrm{E}_{k}(A)$ is at most $|A|^{k+\varepsilon}$ unless $A$ has a very specific structure. As an application we obtain that any finite subset $A$ of the real numbers or the prime field either contains an additive Sidon-type subset of size $|A|^{1 / 2+c}$ or a multiplicative Sidon-type subset of size $|A|^{1 / 2+c}$.

Attaining the exponent 5/4 for the sum product problem in finite fields  [PDF]

The sum-product problem is to show, for any finite set $A$, that one of the sum set $A+A$ or product set $AA$ must be large in cardinality. Progress on this problem over finite fields lags behind its counterpart in the reals, where notably in 1997 Elekes used the Szemerédi-Trotter theorem to obtain the exponent $5/4$; this exponent has since advanced in the reals. In a joint work with Ali Mohammadi, we show that if $A\subseteq \mathbb{F}_p$ has cardinality $|A| \ll p^{1/2}$ then we match Elekes' bound. That is, we show that $\max\{|A \pm A|, |AA|\} \lesssim |A|^\frac54\,.$

This improves the exponent of $11/9$ by Rudnev, Shakan and Shkredov from 2018.

ETHAN WHITE, UBC
The number of directions determined by a Cartesian product in finite fields  [PDF]

The directions determined by a subset $U \subset{\mathbb{F}_p^2}$ is the set of slopes formed by pairs of points from $U$. Seminal results of R\'edei and Sz\H{o}nyi show that $U$ determines at least $(|U|+3)/2$ directions. In the case when $U = A \times B$, a Cartesian product, we improve the multiplicative constant and show that at least $|A||B|-|A|+2$ directions are determined. When $A=B$ is an arithmetic progression, we further improve the multiplicative constant and give a precise asymptotic formula for the number of directions. Joint work with Daniel Di Benedetto, Greg Martin, Jozsef Solymosi, and Chi Hoi Yip.

CHI HOI YIP, University of British Columbia
Gauss sums and the maximum cliques in generalized Paley graphs of square order  [PDF]

Let $GP(q,d)$ be the $d$-Paley graph defined on the finite field $\mathbb{F}_q$. It is notoriously difficult to improve the trivial upper bound $\sqrt{q}$ on the clique number of $GP(q,d)$. In this talk, we will investigate the connection between Gauss sums over a finite field and maximum cliques of their corresponding generalized Paley graphs. In particular, we show that the trivial upper bound on the clique number of $GP(q,d)$ attains if and only if $d \mid (\sqrt{q}+1)$, which strengthens the previous related results by Broere-D\"oman-Ridley and Schneider-Silva, as well as improves the trivial upper bound on the clique number of $GP(q,d)$ when $d \nmid (\sqrt{q}+1)$.