Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science
Fourier analysis has been used for over one hundred years as a tool to study certain additive patterns. For example, Vinogradov used Fourier-analytic techniques (known in this context as the Hardy-Littlewood circle method) to show that every sufficiently-large odd integer can be written as the sum o...
Main Author: | |
---|---|
Other Authors: | |
Format: | Thesis |
Published: |
Massachusetts Institute of Technology
2022
|
Online Access: | https://hdl.handle.net/1721.1/145125 |
_version_ | 1811082712483627008 |
---|---|
author | Tidor, Jonathan |
author2 | Zhao, Yufei |
author_facet | Zhao, Yufei Tidor, Jonathan |
author_sort | Tidor, Jonathan |
collection | MIT |
description | Fourier analysis has been used for over one hundred years as a tool to study certain additive patterns. For example, Vinogradov used Fourier-analytic techniques (known in this context as the Hardy-Littlewood circle method) to show that every sufficiently-large odd integer can be written as the sum of three primes, while van der Corput similarly showed that the primes contain infinitely-many three-term arithmetic progressions.
Over the past two decades, a theory of higher-order Fourier analysis has been developed to study additive patterns which are not amenable to classical Fourier-analytic techniques. For example, while three-term arithmetic progressions can be studied with Fourier analysis, all longer arithmetic progressions require higher-order techniques. These techniques have led to a new proof of Szemerédi's theorem in addition to results such as counts of k-term arithmetic progressions in the primes.
This thesis contains five results in the field of higher-order Fourier analysis. In the first half, we use these techniques to give applications in additive combinatorics and theoretical computer science. We prove an induced arithmetic removal lemma first in complexity 1 and then for patterns of all complexities. This latter result solves a central problem in property testing known as the classification of testable arithmetic properties. We then study a class of multidimensional patterns and show that many of them satisfy the popular difference property analogously to the one-dimensional case. However there is a surprising spectral condition which we prove necessarily appears in higher dimensions that is not present in the one-dimensional problem.
In the second half of this thesis, we further develop the foundations of higher-order Fourier analysis. We determine the set of higher-order characters necessary over [mathematical notation], showing that classical polynomials suffice in the inverse theorem for the Gowers Uᵏ-norm when k≤p+1, but that non-classical polynomials are necessary whenever k>p+1. Finally, we prove the first quantitative bounds on the U⁴-inverse theorem in the low-characteristic regime p<5. |
first_indexed | 2024-09-23T12:07:45Z |
format | Thesis |
id | mit-1721.1/145125 |
institution | Massachusetts Institute of Technology |
last_indexed | 2024-09-23T12:07:45Z |
publishDate | 2022 |
publisher | Massachusetts Institute of Technology |
record_format | dspace |
spelling | mit-1721.1/1451252022-08-30T03:36:17Z Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science Tidor, Jonathan Zhao, Yufei Massachusetts Institute of Technology. Department of Mathematics Fourier analysis has been used for over one hundred years as a tool to study certain additive patterns. For example, Vinogradov used Fourier-analytic techniques (known in this context as the Hardy-Littlewood circle method) to show that every sufficiently-large odd integer can be written as the sum of three primes, while van der Corput similarly showed that the primes contain infinitely-many three-term arithmetic progressions. Over the past two decades, a theory of higher-order Fourier analysis has been developed to study additive patterns which are not amenable to classical Fourier-analytic techniques. For example, while three-term arithmetic progressions can be studied with Fourier analysis, all longer arithmetic progressions require higher-order techniques. These techniques have led to a new proof of Szemerédi's theorem in addition to results such as counts of k-term arithmetic progressions in the primes. This thesis contains five results in the field of higher-order Fourier analysis. In the first half, we use these techniques to give applications in additive combinatorics and theoretical computer science. We prove an induced arithmetic removal lemma first in complexity 1 and then for patterns of all complexities. This latter result solves a central problem in property testing known as the classification of testable arithmetic properties. We then study a class of multidimensional patterns and show that many of them satisfy the popular difference property analogously to the one-dimensional case. However there is a surprising spectral condition which we prove necessarily appears in higher dimensions that is not present in the one-dimensional problem. In the second half of this thesis, we further develop the foundations of higher-order Fourier analysis. We determine the set of higher-order characters necessary over [mathematical notation], showing that classical polynomials suffice in the inverse theorem for the Gowers Uᵏ-norm when k≤p+1, but that non-classical polynomials are necessary whenever k>p+1. Finally, we prove the first quantitative bounds on the U⁴-inverse theorem in the low-characteristic regime p<5. Ph.D. 2022-08-29T16:34:45Z 2022-08-29T16:34:45Z 2022-05 2022-06-07T15:34:05.800Z Thesis https://hdl.handle.net/1721.1/145125 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
spellingShingle | Tidor, Jonathan Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title | Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title_full | Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title_fullStr | Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title_full_unstemmed | Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title_short | Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science |
title_sort | higher order fourier analysis with applications to additive combinatorics and theoretical computer science |
url | https://hdl.handle.net/1721.1/145125 |
work_keys_str_mv | AT tidorjonathan higherorderfourieranalysiswithapplicationstoadditivecombinatoricsandtheoreticalcomputerscience |