Daniel Altman

A system of linear equations in $\mathbb {F}_p^n$ is Sidorenko if any subset of $\mathbb {F}_p^n$ contains at least as many solutions to the system as a random set of the same density, asymptotically as $n\to \infty $ . A system of linear equations is common if any two-colouring of $\mathbb {F}_p^n$ yields at least as many monochromatic solutions to the system of equations as a random 2-colouring, asymptotically as $n\to \infty $ . Both classification problems remain wide open despite recent attention. We show that a certain generic family of systems of two linear equations is not Sidorenko. In fact, we show that systems in this family are not locally Sidorenko, and that systems in this family which do not contain additive tuples are not weakly locally Sidorenko. This endeavour answers a conjecture and question of Kamčev–Liebenau–Morrison. Insofar as methods, we observe that the true complexity of a linear system is not maintained under Fourier inversion; our main novelty is the use of higher-order methods in the frequency space of systems which have complexity one. We also give a shorter proof of the recent result of Kamčev–Liebenau–Morrison and independently Versteegen that any linear system containing a four-term arithmetic progression is uncommon.

Designing a deterministic polynomial time algorithm for factoring univariate polynomials over finite fields remains a notorious open problem. In this paper, we present an unconditional deterministic algorithm that takes as input an irreducible polynomial $f \in \mathbb{Z}[x]$, and computes the factorisation of its reductions modulo $p$ for all primes $p$ up to a prescribed bound $N$. The \emph{average running time per prime} is polynomial in the size of the input and the degree of the splitting field of $f$ over $\mathbb{Q}$. In particular, if $f$ is Galois, we succeed in factoring in (amortised) deterministic polynomial time.

We prove new cases of reasonable bounds for the polynomial Szemerédi theorem both over $\mathbb{Z}/N\mathbb{Z}$ with $N$ prime and over the integers. In particular, we prove reasonable bounds for Szemerédi's theorem in the integers with fixed polynomial common difference. That is, we prove for any polynomial $P(y)\in \mathbb{Z}[y]$ with $P(0) = 0$, that the largest subset $A\subseteq [N]$ avoiding the pattern \[x, x+P(y),\ldots, x+ kP(y)\] has size bounded by $\ll_{P,k}N(\log\log\log N)^{-Ω_{P,k}(1)}.$

We prove that any increasing sequence of real numbers with average gap $1$ and Poisson pair correlations has some gap that is at least $3/2+10^{-9}$ . This improves upon a result of Aistleitner, Blomer, and Radziwiłł.

A system of linear equations in \(\mathbb{F}_p^n\) is common if every two-colouring of \(\mathbb{F}_p^n\) yields at least as many monochromatic solutions as a random two-colouring, asymptotically as \(n \to \infty\). By analogy to the graph-theoretic setting, Alon has asked whether any (non-Sidorenko) system of linear equations can be made uncommon by adding sufficiently many free variables. Fox, Pham and Zhao answered this question in the affirmative among systems which consist of a single equation. We answer Alon's question in the negative.We also observe that the property of remaining common despite that addition of arbitrarily many free variables is closely related to a notion of commonness in which one replaces the arithmetic mean of the number of monochromatic solutions with the geometric mean, and furthermore resolve questions of Kamčev-Liebenau-Morrison.Mathematics Subject Classifications: 05D10, 11B30Keywords: Sidorenko's conjecture, Sidorenko and common linear patterns

We consider, over both the integers and finite fields, Szemerédi’s theorem on $k$-term arithmetic progressions where the set $S$ of allowed common differences in those progressions is restricted and random. Fleshing out a line of enquiry suggested by Fran

Let $\mathcal{G}(n,r,s)$ denote a uniformly random $r$-regular $s$-uniform hypergraph on $n$ vertices, where $s$ is a fixed constant and $r=r(n)$ may grow with $n$. An $\ell$-overlapping Hamilton cycle is a Hamilton cycle in which successive edges overlap in precisely $\ell$ vertices, and 1-overlapping Hamilton cycles are called loose Hamilton cycles. When $r,s\geq 3$ are fixed integers, we establish a threshold result for the property of containing a loose Hamilton cycle. This partially verifies a conjecture of Dudek, Frieze, Rucinski and Sileikis (2015). In this setting, we also find the asymptotic distribution of the number of loose Hamilton cycles in $\mathcal{G}(n,r,s)$. Finally we prove that for $\ell = 2,\ldots, s-1$ and for $r$ growing moderately as $n\to\infty$, the probability that $\mathcal{G}(n,r,s)$ has a $\ell$-overlapping Hamilton cycle tends to zero.

We consider, over both the integers and finite fields, Szemer\'{e}di's theorem on $k$-term arithmetic progressions where the set $S$ of allowed common differences in those progressions is restricted and random. Fleshing out a line of enquiry suggested by Frantzikinakis et al, we show that over the integers, the conjectured threshold for $\mathbb{P}(d \in S)$ for Szemer\'{e}di's theorem to hold a.a.s follows from a conjecture about how so-called dual functions are approximated by nilsequences. We also show that the threshold over finite fields is different to this threshold over the integers.