National Center for Supercomputing Applications WordPress Master Calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email newsdesk@ncsa.illinois.edu.

Zander Kelley "Strong Bounds for 3-Progressions"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
3401 Siebel Center for Computer Science or Online
Virtual
wifi event
Date
Apr 3, 2023   11:00 am  
Speaker
Zander Kelley, UIUC
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
11
Originating Calendar
Computer Science Speakers Calendar

We look forward to you joining us in 3401 Siebel Center for Computer Science or online on Monday, April 3 for the Theory Seminar Series. 

Abstract: 

Suppose you have a set A of integers from {1, 2, ...N} that contains at least N / C elements. Then for large enough N, must A contain three equally spaced numbers (i.e., a 3-term arithmetic progression)? 

In 1953, Roth showed that this is indeed the case with C ≈ log log N, while Behrend in 1946 showed that C can be at most 2^√log(N) by giving an explicit construction of a large set with no 3-term progressions. 

Since then, the problem has been a cornerstone of the area of additive combinatorics.

Following a series of remarkable results, a celebrated paper from 2020 due to Bloom and Sisask improved the lower bound on C to C = (log N)^(1 + c), for some constant c > 0.

This talk will describe a new work which shows that the same holds when C ≈ 2^(log N)^(1/11), thus getting closer to Behrend's construction.

Joint work with Raghu Meka.  https://arxiv.org/abs/2302.05537 .


link for robots only