[Theory] Re: Manners logic seminar on Thursday

Mon Feb 3 19:34:38 CST 2025

Dear all,

Complementing this week's math colloquium announced below, the following talk by the same speaker on Thursday (in the logic seminar) may also be of interest to people on this list.

MM

------
F. Manners logic seminar title and abstract: Thursday 5-6pm Eckhart 202
-------
Title: The "true complexity" of linear equations, and elementary Cauchy--Schwarz proofs

Abstract: Suppose f : G -> R is a function on a finite abelian group.  It is common in additive combinatorics to consider multilinear averages of f, such as
   \[ \mathbb{E}_{a,b in G} f(a) f(a+b) f(a+2b); \]
   if f is the indicator function of a set, this counts 3-term arithmetic progressions (a, a+b, a+2b) in the set.  It is also very useful to know when inequalities hold between different multilinear averages: for instance, the expression above is bounded by the fourth root of the average
  \[ \mathbb{E}_{x,r,s} f(x) f(x+r) f(x+s) f(x+r+s) \]
better known as the Gowers $U^2$-norm, and such arguments (while simple to prove, just using Cauchy--Schwarz) play a crucial role in Gowers' proof of Szemer\'edi's theorem and related results.

For more complicated averages, the following questions appear to become quite hard: does one multilinear average control another, up to some power?  If so, can you prove it just using the Cauchy--Schwarz inequality lots of times?I will try to explain how, in some cases of interest, the answers are yes, but finding the correct sequence of Cauchy--Schwarz inequalities is (currently) outlandishly complicated and has something to do with encoding first-order proofs.

________________________________
From: Theory <theory-bounces at mailman.cs.uchicago.edu> on behalf of Alexander Razborov via Theory <Theory at mailman.cs.uchicago.edu>
Sent: Monday, February 3, 2025 17:38
To: Theory at mailman.cs.uchicago.edu <Theory at mailman.cs.uchicago.edu>
Subject: [Theory] Fwd: Colloquium: Frederick Manners (UCSD)

This may be of interest to many on this list.

Begin forwarded message:

From: Audra Herman <audrah1 at uchicago.edu>
Date: February 3, 2025 at 4:21:14 PM CST
To: razborov at uchicago.edu
Subject: Colloquium: Frederick Manners (UCSD)
Reply-To: Audra Herman <audrah1 at uchicago.edu>

[Mehtaab Sawhney]

Frederick Manners

University of California San Diego

Marton's Polynomial Freiman--Ruzsa conjecture
Abstract:

A function $f : \mathbb{F}_2^n \to \mathbb{F}_2^n$ is linear if $f(x+y)=f(x)+f(y)$ for all pairs $(x,y)$.

Now suppose $f$ is "a little bit linear" -- say, $f(x+y)=f(x)+f(y)$ for a 1% fraction of pairs $(x,y)$.  What can you say about $f$?  Must it be closely related to an actually linear function?  If so, how closely?

This question turns out to be equivalent to asking for good quantitative bounds in the Freiman--Ruzsa theorem, a foundational result in additive combinatorics.  Marton gave a formulation, equivalent to the statement above, which she conjectured should have polynomial bounds.  I will discuss this conjecture, and its (comparatively) recent proof (joint with Timothy Gowers, Ben Green and Terence Tao).

Details:

[https://d15k2d11r6t6rl.cloudfront.net/pub/bfra/ewlkbmtv/jw4/w4x/jup/calendar-months-days-date-dates-2247443.jpg]
[Location:]

[https://d15k2d11r6t6rl.cloudfront.net/pub/bfra/ewlkbmtv/i7k/dz9/mni/chronometer-time-timer-stopwatch-153975.jpg]

February 5th, 2025

Eckhart 202

*3:00-4:00PM* Central

Date: February 5th, 2025

Time: 3:00-4:00 PM Central

Location: Eckhart 202

Add to Outlook<https://uchicago.us2.list-manage.com/track/click?u=350fc31a7f826e3b52544f33a&id=dd583d14cc&e=d7c93c8cdd>
Add to Google<https://uchicago.us2.list-manage.com/track/click?u=350fc31a7f826e3b52544f33a&id=f83c1cf2e3&e=d7c93c8cdd>

Department of Mathematics
5734 S University Ave
Chicago, IL 60637

Connect with Us
[Facebook]<https://uchicago.us2.list-manage.com/track/click?u=350fc31a7f826e3b52544f33a&id=a94f982d6e&e=d7c93c8cdd>     [Linkedin] <https://uchicago.us2.list-manage.com/track/click?u=350fc31a7f826e3b52544f33a&id=4bd8cd096f&e=d7c93c8cdd>    [YouTube] <https://uchicago.us2.list-manage.com/track/click?u=350fc31a7f826e3b52544f33a&id=c29f692ce5&e=d7c93c8cdd>

This email was sent to razborov at uchicago.edu<mailto:razborov at uchicago.edu>
why did I get this?<https://uchicago.us2.list-manage.com/about?u=350fc31a7f826e3b52544f33a&id=79c92b99c0&e=d7c93c8cdd&c=f0e0a26fb9>    unsubscribe from this list<https://uchicago.us2.list-manage.com/unsubscribe?u=350fc31a7f826e3b52544f33a&id=79c92b99c0&t=b&e=d7c93c8cdd&c=f0e0a26fb9>    update subscription preferences<https://uchicago.us2.list-manage.com/profile?u=350fc31a7f826e3b52544f33a&id=79c92b99c0&e=d7c93c8cdd&c=f0e0a26fb9>
Math Department · 5734 S University Ave Ste 108 · Chicago, IL 60637-1501 · USA

 ͏  ͏  ͏  ͏ ͏  ͏  ͏  ͏ ͏  ͏  ͏  ͏ ͏  ͏  ͏  ͏ ͏  ͏  ͏  ͏ ͏  ͏  ͏  ͏

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250204/a0785109/attachment-0001.html>