Fix a word w in a free group on r generators. A w-random permutation in the symmetric group SN is obtained by sampling r independent uniformly random permutations σ1, . . .,σr ∈ SN and evaluating w(σ1, . . .,σr). Such w-random permutations have surprisingly rich structure with relation to deep results in geometric group theory. I'll survey some of this structure, state some conjectures, and explain how it is related to evaluating the spectral gap of random Schreier graphs of SN.
Let G1, . . ., Gk be vector spaces over a prime field 𝔽p. We say that a map Φ defined on a subset of the product G1 × . . . × Gk is a Freiman multi-homomorphism if Φ is a Freiman homomorphism in every principal direction (i.e. when xi in Gi is fixed for each i except one direction d, the map that sends element xd to Φ(x1,..., xk) is a Freiman homomorphism, where we allow those xd for which (x1,..., xk) is in the domain of Φ). It turns out that a Freiman multi-homomorphism defined on a dense subset of G1 × . . . × Gk necessarily coincides with a global multiaffine map at many points. In this talk we discuss the proof of this fact and some applications, which include a quantitative inverse theorem for the Gowers uniformity norms (in finite vector spaces in the case of large characteristic).
We show that the set of integers n for which n | (2n)!/(n!)2 has a positive asymptotic density, answering a question of Pomerance. The proof uses a mix of ideas from harmonic analysis and the anatomy of integers, and is joint work with Sergei Konyagin.
This video is part of the Webinar in Additive Combinatorics series, and this is their YouTube channel.
A subspace of 𝔽2n is called cyclically covering if every vector in 𝔽2n has a cyclic shift which is inside the subspace. Let h2(n) denote the largest possible codimension of a cyclically covering subspace of 𝔽2n. We show that h2(p) = 2 for every prime p such that 2 is a primitive root modulo p, which, assuming Artin’s conjecture, answers a question of Peter Cameron from 1991. In this talk, I will try to explain how we reduce the problem to a problem on finding odd subgraphs in which each vertex has odd outdegree in directed Cayley graphs, how additive combinatorics comes to the rescue and which open problems I would like to see solved. This is joint work with James Aaronson and Tom Johnston.
Hardy and Littlewood (1923) conjectured that for any integers x, y ≥ 2,
π(x + y) ≤ π(x) + π(y). (1)
Let us call a set {b1, . . . , bk} of integers admissible if for each prime p there is some congruence class mod p which contains none of the integers bi. The prime k-tuple conjecture states that if a set {b1, . . . , bk} is admissible, then there exist infinitely many integers n for which all the numbers n + b1, . . . , n + bk are primes.
Let x be a positive integer and ρ*(x) be the maximum number of integers in any interval (y, y +x] (with no restriction on y) that are relatively prime to all positive integers ≤ x. The prime k-tuple conjecture implies that
maxy≥x (π(x + y) − π(y)) = lim supy≥x (π(x + y) − π(y)) = ρ*(x).
Hensley and Richards (1974) proved that
ρ*(x) − π(x) ≥ (log 2 − o(1)) x (log x)−2 (x → ∞).
Therefore, (1) is not compatible with the prime k-tuple conjecture. Using a construction of Schinzel we show that
ρ*(x) − π(x) ≥ (log 2 − o(1)) x (log x)−2 log log log x (x → ∞).
We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include:
• Every n-vertex graph with no 5-cycle can be made triangle-free by deleting o(n3/2) edges.
• For r ≥ 3, every n-vertex r-graph with girth greater than 5 has o(n3/2) edges.
• Every subset of [n] without a non-trivial solution to the equation x1 + x2 + 2x3 = x4 + 3x5 has size o(√n).
In 2016, Tao formulated a conjecture on the Gowers uniformity of the Möbius function in short intervals, which he showed to be equivalent to both the (logarithmic) Chowla and Sarnak conjectures. I will discuss work where we prove this conjecture for intervals of length X𝜺. I will then discuss applications to superpolynomial word complexity for the Liouville sequence and to a new averaged version of Chowla's conjecture.
Zaremba's conjecture belongs to the area of continued fractions. It predicts that for any given positive integer q there is a positive a, a less than q, (a,q)=1 such that all partial quotients bj in its continued fractions expansion a/q = 1/b1+1/b2 +... + 1/bs are bounded by five. At the moment the question is widely open although the area has a rich history of works by Korobov, Hensley, Niederreiter, Bourgain and many others. We survey certain results concerning this hypothesis and show how growth in groups helps to solve different relaxations of Zaremba's conjecture. In particular, we show that a deeper hypothesis of Hensley concerning some Cantor-type set with the Hausdorff dimension strictly greater than 1/2 takes place for the so-called modular form of Zaremba's conjecture.
Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will survey some recent progress on these problems in three settings: the Extremal Combinatorics setting of the discrete cube (joint with Eoin Long), the Additive Combinatorics setting of Cayley digraphs on lattices (joint with Ben Barber, Joshua Erde and Alexander Roberts) and the Discrete Analysis setting of Boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).
A subset D of a finite cyclic group ℤ/mℤ is called a perfect difference set if every nonzero element of ℤ/mℤ can be written uniquely as the difference of two elements of D. If such a set exists, then a simple counting argument shows that m=n2+n+1 for some non-negative integer n. Singer constructed examples of perfect difference sets in ℤ/(n2+n+1)ℤ whenever n is a prime power, and it is an old conjecture that these are the only such n for which a perfect difference set exists. In this talk, I will discuss a proof of an asymptotic version of this conjecture: the number of n<N for which ℤ/(n2+n+1)ℤ contains a perfect difference set is ~N/log(N).
You must be logged in to post a comment.