SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Terence Tao is an Australian-American mathematician renowned for his extraordinary contributions to various fields of mathematics. Born on July 17, 1975, in Adelaide, Australia, Tao displayed exceptional mathematical talent from a young age. He participated in the International Mathematical Olympiad (IMO) at ages 10, 11, and 12, winning bronze, silver, and gold medals respectively, and went on to achieve two more gold medals with perfect scores at ages 14 and 15.

Education and Career:

  • Ph.D. at a Young Age: Tao earned his bachelor’s and master’s degrees from Flinders University by the age of 16. He then received his Ph.D. from Princeton University at 21 under the supervision of Elias Stein.
  • Professor at UCLA: He joined the faculty of the University of California, Los Angeles (UCLA) and became a full professor at just 24 years old.

Contributions to Mathematics:

Terence Tao’s work spans a broad spectrum of mathematical fields, including:

  • Harmonic Analysis
  • Partial Differential Equations
  • Additive Combinatorics
  • Analytic Number Theory
  • Random Matrix Theory
  • Compressed Sensing

Notable Achievements:

  • Fields Medal (2006): Often called the “Nobel Prize of Mathematics,” Tao received this prestigious award for his contributions to partial differential equations, combinatorics, harmonic analysis, and additive number theory.
  • Breakthroughs in Number Theory: Along with mathematician Ben Green, he proved the Green-Tao Theorem, which states that there are arbitrarily long arithmetic progressions of prime numbers.
  • Royal Society Fellowship: Elected as a Fellow of the Royal Society (FRS) in 2007.
  • MacArthur Fellowship: Received the “Genius Grant” in 2006.
  • Royal Medal (2014): Awarded by the Royal Society for his contributions to mathematics.

Publications and Outreach:

  • Research Papers and Books: Tao has authored hundreds of research papers and several influential books that are highly regarded in the mathematical community.
  • Educational Blog: He maintains a popular mathematical blog where he writes about various topics, providing insights and fostering education and collaboration.

Recognition:

Terence Tao is widely respected not only for his profound research contributions but also for his ability to explain complex mathematical concepts with clarity. His work has had a significant impact on modern mathematics, inspiring both contemporaries and the next generation of mathematicians.

Personal Attributes:

Colleagues often describe Tao as humble and approachable, despite his towering achievements. He is known for his collaborative spirit, having worked with over 30 co-authors on various mathematical papers.

Current Work:

As of my knowledge cutoff in September 2021, Terence Tao continues to teach and conduct research at UCLA, contributing to advancements in mathematics and mentoring students.

Ask a Question About This Mathematician

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

2006-01-25
Emmanuel J. Candès , Justin Romberg , Terence Tao
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. … This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.
View PDF Chat

Decoding by Linear Programming

2005-11-22
Emmanuel J. Candès , Terence Tao
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an … This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.
View PDF Chat

Stable signal recovery from incomplete and inaccurate measurements

2006-03-01
Emmanuel J. Candès , Justin Romberg , Terence Tao
Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + … Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + e ; A is an 𝓃 × 𝓂 matrix with far fewer rows than columns (𝓃 ≪ 𝓂) and e is an error term. Is it possible to recover x 0 accurately based on the data y ? To recover x 0 , we consider the solution x # to the 𝓁 1 ‐regularization problem where ϵ is the size of the error term e . We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x 0 is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A 's provided that the number of nonzeros of x 0 is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x 0 ; then stable recovery occurs for almost any set of 𝓃 coefficients provided that the number of nonzeros is of the order of 𝓃/(log 𝓂) 6 . In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.
View PDF Chat

Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

2006-12-01
Emmanuel J. Candès , Terence Tao
<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> Suppose we are given a vector &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$f$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; in a class &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;${\cal F} \subset{\BBR}^N$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;, e.g., a class of digital signals or digital images. How … <para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> Suppose we are given a vector &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$f$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; in a class &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;${\cal F} \subset{\BBR}^N$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;, e.g., a class of digital signals or digital images. How many linear measurements do we need to make about &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$f$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; to be able to recover &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$f$&lt;/tex&gt; &lt;/formula&gt;&lt;/emphasis&gt; to within precision &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$\epsilon$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; in the Euclidean &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$(\ell_2)$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$f$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$n$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;th largest entry of the vector &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$\vert f\vert$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; (or of its coefficients in a fixed basis) obeys &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$\vert f\vert _{(n)} \le R \cdot n^{-1/p}$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;, where &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$R &gt; 0$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; and &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$p &gt; 0$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;. Suppose that we take measurements &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$y_k = \langle f, X_k\rangle, k = 1, \ldots, K$&lt;/tex&gt; &lt;/formula&gt;&lt;/emphasis&gt;, where the &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$X_k$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; are &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$N$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;-dimensional Gaussian vectors with independent standard normal entries. Then for each &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$f$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; obeying the decay estimate above for some &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$0 &lt; p &lt; 1$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; and with overwhelming probability, our reconstruction &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$f^\sharp$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt;, defined as the solution to the constraints &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$y_k = \langle f^\sharp, X_k \rangle$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; with minimal &lt;emphasis&gt;&lt;formula formulatype="inline"&gt; &lt;tex&gt;$\ell_1$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; norm, obeys &lt;emphasis&gt; &lt;formula formulatype="display"&gt;&lt;tex&gt;$$ \Vert f - f^\sharp\Vert _{\ell_2} \le C_p \cdot R \cdot (K/\log N)^{-r}, \quad r = 1/p - 1/2. $$&lt;/tex&gt; &lt;/formula&gt;&lt;/emphasis&gt;There is a sense in which this result is optimal; it is generally impossible to obtain a higher accuracy from any set of &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$K$&lt;/tex&gt;&lt;/formula&gt;&lt;/emphasis&gt; measurements whatsoever. The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes a few randomly sampled Fourier coefficients of &lt;emphasis&gt;&lt;formula formulatype="inline"&gt;&lt;tex&gt;$f$&lt;/tex&gt; &lt;/formula&gt;&lt;/emphasis&gt;. In fact, the results are quite general and require only two hypotheses on the measurement ensemble which are detailed. </para>
View PDF Chat

The Dantzig selector: Statistical estimation when p is much larger than n

2007-12-01
Emmanuel J. Candès , Terence Tao
In many important statistical applications, the number of variables or parameters p is much larger than the number of observations n. Suppose then that we have observations y=Xβ+z, where β∈Rp … In many important statistical applications, the number of variables or parameters p is much larger than the number of observations n. Suppose then that we have observations y=Xβ+z, where β∈Rp is a parameter vector of interest, X is a data matrix with possibly far fewer rows than columns, n≪p, and the zi’s are i.i.d. N(0, σ2). Is it possible to estimate β reliably based on the noisy data y? To estimate β, we introduce a new estimator—we call it the Dantzig selector—which is a solution to the ℓ1-regularization problem $$\min_{\tilde{\beta}\in\mathbf{R}^{p}}\|\tilde{\beta}\|_{\ell_{1}}\quad\mbox{subject to}\quad \|X^{*}r\|_{\ell_{\infty}}\leq(1+t^{-1})\sqrt{2\log p}\cdot\sigma,$$ where r is the residual vector y−Xβ̃ and t is a positive scalar. We show that if X obeys a uniform uncertainty principle (with unit-normed columns) and if the true parameter vector β is sufficiently sparse (which here roughly guarantees that the model is identifiable), then with very large probability, ‖β̂−β‖ℓ22≤C2⋅2log p⋅(σ2+∑imin(βi2, σ2)). Our results are nonasymptotic and we give values for the constant C. Even though n may be much smaller than p, our estimator achieves a loss within a logarithmic factor of the ideal mean squared error one would achieve with an oracle which would supply perfect information about which coordinates are nonzero, and which were above the noise level. In multivariate regression and from a model selection viewpoint, our result says that it is possible nearly to select the best subset of variables by solving a very simple convex program, which, in fact, can easily be recast as a convenient linear program (LP).
View PDF Chat

The Power of Convex Relaxation: Near-Optimal Matrix Completion

2010-04-26
Emmanuel J. Candès , Terence Tao
This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">matrix completion</i> problem, and … This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">matrix completion</i> problem, and comes up in a great number of applications, including the famous <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Netflix Prize</i> and other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible, but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solutions meaningful. This paper presents optimality results quantifying the minimum number of entries needed to recover a matrix of rank <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> exactly by any method whatsoever (the information theoretic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theoretic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">nr</i> log( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ) samples are needed to recover a random <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> x <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> matrix of rank <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> by any method, and to be sure, nuclear norm minimization succeeds as soon as the number of entries is of the form <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">nr</i> polylog( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ).
View PDF Chat

Endpoint Strichartz estimates

1998-10-01
M. Keel , Terence Tao
We prove an abstract Strichartz estimate, which implies previously unknown endpoint Strichartz estimates for the wave equation (in dimension n ≥ 4) and the Schrödinger equation (in dimension n ≥ … We prove an abstract Strichartz estimate, which implies previously unknown endpoint Strichartz estimates for the wave equation (in dimension n ≥ 4) and the Schrödinger equation (in dimension n ≥ 3). Three other applications are discussed: local existence for a nonlinear wave equation; and Strichartz-type estimates for more general dispersive equations and for the kinetic transport equation.
View PDF Chat

Nonlinear Dispersive Equations

2006-06-08
Terence Tao
Ordinary differential equations Constant coefficient linear dispersive equations Semilinear dispersive equations The Korteweg de Vries equation Energy-critical semilinear dispersive equations Wave maps Tools from harmonic analysis Construction of ground states … Ordinary differential equations Constant coefficient linear dispersive equations Semilinear dispersive equations The Korteweg de Vries equation Energy-critical semilinear dispersive equations Wave maps Tools from harmonic analysis Construction of ground states Bibliography.

Topics in Random Matrix Theory

2012-03-21
Terence Tao
The field of random matrix theory has seen an explosion of activity in recent years, with connections to many areas of mathematics and physics. However, this makes the current state … The field of random matrix theory has seen an explosion of activity in recent years, with connections to many areas of mathematics and physics. However, this makes the current state of the field almost too large to survey in a single book. In this graduate text, we focus on one specific sector of the field, namely the spectral distribution of random Wigner matrix ensembles (such as the Gaussian Unitary Ensemble), as well as iid matrix ensembles. The text is largely self-contained and starts with a review of relevant aspects of probability theory and linear algebra. With over 200 exercises, the book is suitable as an introductory text for beginning graduate students seeking to enter the field.
View PDF Chat

The primes contain arbitrarily long arithmetic progressions

2008-03-01
Benjamin Green , Terence Tao
We prove that there are arbitrarily long arithmetic progressions of primes.There are three major ingredients.The first is Szemerédi's theorem, which asserts that any subset of the integers of positive density … We prove that there are arbitrarily long arithmetic progressions of primes.There are three major ingredients.The first is Szemerédi's theorem, which asserts that any subset of the integers of positive density contains progressions of arbitrary length.The second, which is the main new ingredient of this paper, is a certain transference principle.This allows us to deduce from Szemerédi's theorem that any subset of a sufficiently pseudorandom set (or measure) of positive relative density contains progressions of arbitrary length.The third ingredient is a recent result of Goldston and Yıldırım, which we reproduce here.Using this, one may place (a large fraction of) the primes inside a pseudorandom set of "almost primes" (or more precisely, a pseudorandom measure concentrated on almost primes) with positive relative density.
View PDF Chat

Orthogonal polynomials

2022-05-19
T. W. Körner , Terence Tao

The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture

1999-04-13
Allen Knutson , Terence Tao
Recently Klyachko has given linear inequalities on triples $(\lambda ,\mu ,\nu )$ of dominant weights of $GL_n(\mathbb {C})$ necessary for the corresponding Littlewood-Richardson coefficient $\dim (V_\lambda \otimes V_\mu \otimes V_\nu … Recently Klyachko has given linear inequalities on triples $(\lambda ,\mu ,\nu )$ of dominant weights of $GL_n(\mathbb {C})$ necessary for the corresponding Littlewood-Richardson coefficient $\dim (V_\lambda \otimes V_\mu \otimes V_\nu )^{GL_n(\mathbb {C})}$ to be positive. We show that these conditions are also sufficient, which was known as the saturation conjecture. In particular this proves Horn’s conjecture from 1962, giving a recursive system of inequalities. Our principal tool is a new model of the Berenstein-Zelevinsky cone for computing Littlewood-Richardson coefficients, the honeycomb model. The saturation conjecture is a corollary of our main result, which is the existence of a particularly well-behaved honeycomb associated to regular triples $(\lambda ,\mu ,\nu )$.
View PDF Chat

Sharp global well-posedness for KdV and modified KdV on ℝ and 𝕋

2003-01-29
J. Colliander , M. Keel , Gigliola Staffilani +2 more
The initial value problems for the Korteweg-de Vries (KdV) and modified KdV (mKdV) equations under periodic and decaying boundary conditions are considered. These initial value problems are shown to be … The initial value problems for the Korteweg-de Vries (KdV) and modified KdV (mKdV) equations under periodic and decaying boundary conditions are considered. These initial value problems are shown to be globally well-posed in all<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L squared"><mml:semantics><mml:msup><mml:mi>L</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:annotation encoding="application/x-tex">L^2</mml:annotation></mml:semantics></mml:math></inline-formula>-based Sobolev spaces<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H Superscript s"><mml:semantics><mml:msup><mml:mi>H</mml:mi><mml:mi>s</mml:mi></mml:msup><mml:annotation encoding="application/x-tex">H^s</mml:annotation></mml:semantics></mml:math></inline-formula>where local well-posedness is presently known, apart from the<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H Superscript one fourth Baseline left-parenthesis double-struck upper R right-parenthesis"><mml:semantics><mml:mrow><mml:msup><mml:mi>H</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mfrac><mml:mn>1</mml:mn><mml:mn>4</mml:mn></mml:mfrac></mml:mrow></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">R</mml:mi></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">H^{\frac {1}{4}} (\mathbb {R} )</mml:annotation></mml:semantics></mml:math></inline-formula>endpoint for mKdV and the<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H Superscript negative three fourths"><mml:semantics><mml:msup><mml:mi>H</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−<!-- − --></mml:mo><mml:mfrac><mml:mn>3</mml:mn><mml:mn>4</mml:mn></mml:mfrac></mml:mrow></mml:msup><mml:annotation encoding="application/x-tex">H^{-\frac {3}{4}}</mml:annotation></mml:semantics></mml:math></inline-formula>endpoint for KdV. The result for KdV relies on a new method for constructing almost conserved quantities using multilinear harmonic analysis and the available local-in-time theory. Miura’s transformation is used to show that global well-posedness of modified KdV is implied by global well-posedness of the standard KdV equation.

Global well-posedness and scattering for the energy-critical Schrödinger equation in ℝ<sup>3</sup>

2008-05-01
J. Colliander , M. Keel , Gigliola Staffilani +2 more
We obtain global well-posedness, scattering, and global L 10 t,x spacetime bounds for energy-class solutions to the quintic defocusing Schrödinger equation in R 1+3 , which is energy-critical.In particular, this … We obtain global well-posedness, scattering, and global L 10 t,x spacetime bounds for energy-class solutions to the quintic defocusing Schrödinger equation in R 1+3 , which is energy-critical.In particular, this establishes global existence of classical solutions.Our work extends the results of Bourgain [4] and Grillakis [20], which handled the radial case.The method is similar in spirit to the induction-on-energy strategy of Bourgain [4], but we perform the induction analysis in both frequency space and physical space simultaneously, and replace the Morawetz inequality by an interaction variant (first used in [12], [13]).The principal advantage of the interaction Morawetz estimate is that it is not localized to the spatial origin and so is better able to handle nonradial solutions.In particular, this interaction estimate, together with an almost-conservation argument controlling the movement of L 2 mass in frequency space, rules out the possibility of energy concentration.
View PDF Chat

Random matrices: Universality of local eigenvalue statistics

2011-01-01
Terence Tao , Van Vu
In this paper, we consider the universality of the local eigenvalue statistics of random matrices. Our main result shows that these statistics are determined by the first four moments of … In this paper, we consider the universality of the local eigenvalue statistics of random matrices. Our main result shows that these statistics are determined by the first four moments of the distribution of the entries. As a consequence, we derive the universality of eigenvalue gap distribution and k-point correlation, and many other statistics (under some mild assumptions) for both Wigner Hermitian matrices and Wigner real symmetric matrices.
View PDF Chat

Random matrices: Universality of ESDs and the circular law

2010-08-17
Terence Tao , Van Vu , Manjunath Krishnapur
Given an n×n complex matrix A, let $$\mu_{A}(x,y):=\frac{1}{n}|\{1\le i\le n,\operatorname{Re}\lambda_{i}\le x,\operatorname{Im}\lambda_{i}\le y\}|$$ be the empirical spectral distribution (ESD) of its eigenvalues λi∈ℂ, i=1, …, n. We consider the limiting distribution … Given an n×n complex matrix A, let $$\mu_{A}(x,y):=\frac{1}{n}|\{1\le i\le n,\operatorname{Re}\lambda_{i}\le x,\operatorname{Im}\lambda_{i}\le y\}|$$ be the empirical spectral distribution (ESD) of its eigenvalues λi∈ℂ, i=1, …, n. We consider the limiting distribution (both in probability and in the almost sure convergence sense) of the normalized ESD $\mu_{{1}/{\sqrt{n}}A_{n}}$ of a random matrix An=(aij)1≤i, j≤n, where the random variables aij−E(aij) are i.i.d. copies of a fixed random variable x with unit variance. We prove a universality principle for such ensembles, namely, that the limit distribution in question is independent of the actual choice of x. In particular, in order to compute this distribution, one can assume that x is real or complex Gaussian. As a related result, we show how laws for this ESD follow from laws for the singular value distribution of $\frac{1}{\sqrt{n}}A_{n}-zI$ for complex z. As a corollary, we establish the circular law conjecture (both almost surely and in probability), which asserts that $\mu_{{1}/{\sqrt{n}}A_{n}}$ converges to the uniform measure on the unit disc when the aij have zero mean.
View PDF Chat

Multilinear weighted convolution of L 2 functions, and applications to nonlinear dispersive equations

2001-10-01
Terence Tao
The X s,b spaces, as used by Beals, Bourgain, Kenig-Ponce-Vega, Klainerman-Machedon and others, are fundamental tools to study the low-regularity behavior of nonlinear dispersive equations. It is of particular interest … The X s,b spaces, as used by Beals, Bourgain, Kenig-Ponce-Vega, Klainerman-Machedon and others, are fundamental tools to study the low-regularity behavior of nonlinear dispersive equations. It is of particular interest to obtain bilinear or multilinear estimates involving these spaces. By Plancherel's theorem and duality, these estimates reduce to estimating a weighted convolution integral in terms of the L 2 norms of the component functions. In this paper we systematically study weighted convolution estimates on L 2 . As a consequence we obtain sharp bilinear estimates for the KdV, wave, and Schrödinger X s,b spaces.
View PDF Chat

Linear equations in primes

2010-04-25
Ben Green , Terence Tao
Consider a system ‰ of nonconstant affine-linear forms 1 ; : : : ; t W ‫ޚ‬ d !‫,ޚ‬ no two of which are linearly dependent.Let N be a large … Consider a system ‰ of nonconstant affine-linear forms 1 ; : : : ; t W ‫ޚ‬ d !‫,ޚ‬ no two of which are linearly dependent.Let N be a large integer, and let K Â OE N; N d be convex.A generalisation of a famous and difficult open conjecture of Hardy and Littlewood predicts an asymptotic, as N ! 1, for the number of integer points n 2 ‫ޚ‬ d \ K for which the integers 1 .n/;: : : ; t .n/are simultaneously prime.This implies many other well-known conjectures, such as the twin prime conjecture and the (weak) Goldbach conjecture.It also allows one to count the number of solutions in a convex range to any simultaneous linear system of equations, in which all unknowns are required to be prime.In this paper we (conditionally) verify this asymptotic under the assumption that no two of the affine-linear forms 1 ; : : : ; t are affinely related; this excludes the important "binary" cases such as the twin prime or Goldbach conjectures, but does allow one to count "nondegenerate" configurations such as arithmetic progressions.Our result assumes two families of conjectures, which we term the inverse Gowersnorm conjecture (GI.s/) and the Möbius and nilsequences conjecture (MN.s/),where s 2 f1; 2; : : : g is the complexity of the system and measures the extent to which the forms i depend on each other.The case s D 0 is somewhat degenerate, and follows from the prime number theorem in APs.Roughly speaking, the inverse Gowers-norm conjecture GI.s/ asserts the Gowers U sC1 -norm of a function f W OEN !OE 1; 1 is large if and only if f correlates with an s-step nilsequence, while the Möbius and nilsequences conjecture MN.s/ asserts that the Möbius function is strongly asymptotically orthogonal to s-step nilsequences of a fixed complexity.These conjectures have long been known to be true for s D 1 (essentially by work of Hardy-Littlewood and Vinogradov), and were established for s D 2 in two papers of the authors.Thus our results in the case of complexity s 6 2 are unconditional.In particular we can obtain the expected asymptotics for the number of 4-term progressions p 1 < p 2 < p 3 < p 4 6 N of primes, and more generally for any (nondegenerate) problem involving two linear equations in four prime unknowns.
View PDF Chat

Fuglede’s conjecture is false in 5 and higher dimensions

2004-01-01
Terence Tao
We give an example of a set Ω ⊂ R 5 which is a finite union of unit cubes, such that L 2 (Ω) admits an orthonormal basis of exponentials … We give an example of a set Ω ⊂ R 5 which is a finite union of unit cubes, such that L 2 (Ω) admits an orthonormal basis of exponentials { 1 |Ω| 1/2 e 2πiξ j •x : ξ j ∈ Λ} for some discrete set Λ ⊂ R 5 , but which does not tile R 5 by translations.This answers (one direction of) a conjecture of Fuglede [1] in the negative, at least in 5 and higher dimensions.
View PDF Chat

A sum-product estimate in finite fields, and applications

2004-02-01
Jean Bourgain , Nets Hawk Katz , Terence Tao
View PDF Chat

On the multilinear restriction and Kakeya conjectures

2006-01-01
Jonathan Bennett , Anthony Carbery , Terence Tao
We prove d-linear analogues of the classical restriction and Kakeya conjectures in Rd. Our approach involves obtaining monotonicity formulae pertaining to a certain evolution of families of gaussians, closely related … We prove d-linear analogues of the classical restriction and Kakeya conjectures in Rd. Our approach involves obtaining monotonicity formulae pertaining to a certain evolution of families of gaussians, closely related to heat flow. We conclude by giving some applications to the corresponding variable-coefficient problems and the so-called "joints" problem, as well as presenting some n-linear analogues for n < d.
View PDF Chat

An Introduction to Measure Theory

2011-09-14
Terence Tao
This is a graduate text introducing the fundamentals of measure theory and integration theory, which is the foundation of modern real analysis. The text focuses first on the concrete setting … This is a graduate text introducing the fundamentals of measure theory and integration theory, which is the foundation of modern real analysis. The text focuses first on the concrete setting of Lebesgue measure and the Lebesgue integral (which in turn is motivated by the more classical concepts of Jordan measure and the Riemann integral), before moving on to abstract measure and integration theory, including the standard convergence theorems, Fubini's theorem, and the Caratheodory extension theorem. Classical differentiation theorems, such as the Lebesgue and Radamacher differentiation theorems, are also covered, as are connections with probability theory. The material is intended to cover a quarter or semester's worth of material for a first graduate course in real analysis. There is an emphasis in the text on tying together the abstract and the concrete sides of the subject, using the latter to illustrate and motivate the former. The central role of key principles (such as Littlewood's three principles) as providing guiding intuition to the subject is also emphasised. There are a large number of exercises throughout that develop key aspects of the theory, and are thus an integral component of the text. As a supplementary section, a discussion of general problem-solving strategies in analysis is also given. The last three sections discuss optional topics related to the main matter of the book.

A bilinear approach to the restriction and Kakeya conjectures

1998-01-01
Terence Tao , Ana Vargas , Luis Vega
Bilinear restriction estimates have appeared in work of Bourgain, Klainerman, and Machedon. In this paper we develop the theory of these estimates (together with the analogues for Kakeya estimates). As … Bilinear restriction estimates have appeared in work of Bourgain, Klainerman, and Machedon. In this paper we develop the theory of these estimates (together with the analogues for Kakeya estimates). As a consequence we improve the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper L Superscript p Baseline comma upper L Superscript p Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(L^p,L^p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> spherical restriction theorem of Wolff from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p greater-than 42 slash 11"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>42</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>11</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p &gt; 42/11</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p greater-than 34 slash 9"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>34</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>9</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p &gt; 34/9</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and also obtain a sharp <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper L Superscript p Baseline comma upper L Superscript q Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>q</mml:mi> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(L^p,L^q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> spherical restriction theorem for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q greater-than 4 minus five twenty-sevenths"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>4</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mfrac> <mml:mn>5</mml:mn> <mml:mn>27</mml:mn> </mml:mfrac> </mml:mrow> <mml:annotation encoding="application/x-tex">q&gt; 4 - \frac {5}{27}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

The Brascamp–Lieb Inequalities: Finiteness, Structure and Extremals

2007-08-29
Jonathan Bennett , Anthony Carbery , Michael Christ +1 more
View PDF Chat

AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

2008-02-01
Ben Green , Terence Tao
Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool … Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool in these developments has been the sequence of Gowers uniformity norms $U^d(G)$, $d=1,2,3,\dots$, on a finite additive group $G$; in particular, to detect arithmetic progressions of length $k$ in $G$ it is important to know under what circumstances the $U^{k-1}(G)$ norm can be large. The $U^1(G)$ norm is trivial, and the $U^2(G)$ norm can be easily described in terms of the Fourier transform. In this paper we systematically study the $U^3(G)$ norm, defined for any function $f:G\to\mathbb{C}$ on a finite additive group $G$ by the formula \begin{multline*} \qquad\|f\|_{U^3(G)}:=|G|^{-4}\sum_{x,a,b,c\in G}(f(x)\overline{f(x+a)f(x+b)f(x+c)}f(x+a+b) \\ \times f(x+b+c)f(x+c+a)\overline{f(x+a+b+c)})^{1/8}.\qquad \end{multline*} We give an inverse theorem for the $U^3(G)$ norm on an arbitrary group $G$. In the finite-field case $G=\mathbb{F}_5^n$ we show that a bounded function $f:G\to\mathbb{C}$ has large $U^3(G)$ norm if and only if it has a large inner product with a function $e(\phi)$, where $e(x):=\mathrm{e}^{2\pi\ri x}$ and $\phi:\mathbb{F}_5^n\to\mathbb{R}/\mathbb{Z}$ is a quadratic phase function. In a general $G$ the statement is more complicated: the phase $\phi$ is quadratic only locally on a Bohr neighbourhood in $G$. As an application we extend Gowers's proof of Szemerédi's theorem for progressions of length four to arbitrary abelian $G$. More precisely, writing $r_4(G)$ for the size of the largest $A\subseteq G$ which does not contain a progression of length four, we prove that $$ r_4(G)\ll|G|(\log\log|G|)^{-c}, $$ where $c$ is an absolute constant. We also discuss links between our ideas and recent results of Host, Kra and Ziegler in ergodic theory. In future papers we will apply variants of our inverse theorems to obtain an asymptotic for the number of quadruples $p_1\ltp_2\ltp_3\ltp_4\leq N$ of primes in arithmetic progression, and to obtain significantly stronger bounds for $r_4(G)$.
View PDF Chat

Random Matrices: Universality of Local Eigenvalue Statistics up to the Edge

2010-04-02
Terence Tao , Van Vu
This is a continuation of our earlier paper on the universality of the eigenvalues of Wigner random matrices. The main new results of this paper are an extension of the … This is a continuation of our earlier paper on the universality of the eigenvalues of Wigner random matrices. The main new results of this paper are an extension of the results in that paper from the bulk of the spectrum up to the edge. In particular, we prove a variant of the universality results of Soshnikov for the largest eigenvalues, assuming moment conditions rather than symmetry conditions. The main new technical observation is that there is a significant bias in the Cauchy interlacing law near the edge of the spectrum which allows one to continue ensuring the delocalization of eigenvectors.
View PDF Chat

A sharp bilinear restriction estimate for paraboloids

2003-12-01
Terence Tao
View PDF Chat

Error correction via linear programming

2005-01-01
Emmanuel J. Candès , Mark Rudelson , Terence Tao +1 more
Suppose we wish to transmit a vector f ϵ R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. … Suppose we wish to transmit a vector f ϵ R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?
View PDF Chat

RANDOM MATRICES: THE CIRCULAR LAW

2008-04-01
Terence Tao , Van Vu
Let x be a complex random variable with mean zero and bounded variance σ 2 . Let N n be a random matrix of order n with entries being i.i.d. … Let x be a complex random variable with mean zero and bounded variance σ 2 . Let N n be a random matrix of order n with entries being i.i.d. copies of x. Let λ 1 , …, λ n be the eigenvalues of [Formula: see text]. Define the empirical spectral distributionμ n of N n by the formula [Formula: see text] The following well-known conjecture has been open since the 1950's: Circular Law Conjecture: μ n converges to the uniform distribution μ ∞ over the unit disk as n tends to infinity. We prove this conjecture, with strong convergence, under the slightly stronger assumption that the (2 + η)th-moment of x is bounded, for any η &gt; 0. Our method builds and improves upon earlier work of Girko, Bai, Götze–Tikhomirov, and Pan–Zhou, and also applies for sparse random matrices. The new key ingredient in the paper is a general result about the least singular value of random matrices, which was obtained using tools and ideas from additive combinatorics.
View PDF Chat

The honeycomb model of 𝐺𝐿_{𝑛}(ℂ) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone

2003-10-14
Allen Knutson , Terence Tao , Christopher T. Woodward
The set of possible spectra <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis lamda comma mu comma nu right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>λ<!-- λ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>μ<!-- μ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>ν<!-- ν … The set of possible spectra <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis lamda comma mu comma nu right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>λ<!-- λ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>μ<!-- μ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>ν<!-- ν --></mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(\lambda ,\mu ,\nu )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of zero-sum triples of Hermitian matrices forms a polyhedral cone, whose facets have been already studied by Knutson and Tao, Helmke and Rosenthal, Totaro, and Belkale in terms of Schubert calculus on Grassmannians. We give a complete determination of these facets; there is one for each triple of Grassmannian Schubert cycles intersecting in a unique point. In particular, the list of inequalities determined by Belkale to be sufficient is in fact minimal. We introduce <italic>puzzles</italic>, which are new combinatorial gadgets to compute Grassmannian Schubert calculus, and seem to have much interest in their own right. As the proofs herein indicate, the Hermitian sum problem is very naturally studied using puzzles directly, and their connection to Schubert calculus is quite incidental to our approach. In particular, we get new, puzzle-theoretic, proofs of the results of Horn, Klyachko, Helmke and Rosenthal, Totaro, and Belkale. Along the way we give a characterization of “rigid” puzzles, which we use to prove a conjecture of W. Fulton: “if for a triple of dominant weights <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda comma mu comma nu"> <mml:semantics> <mml:mrow> <mml:mi>λ<!-- λ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>μ<!-- μ --></mml:mi> <mml:mo>,</mml:mo> <mml:mi>ν<!-- ν --></mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda ,\mu ,\nu</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G upper L Subscript n Baseline left-parenthesis double-struck upper C right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">C</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">GL_n({\mathbb C})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> the irreducible representation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript nu"> <mml:semantics> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>ν<!-- ν --></mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">V_\nu</mml:annotation> </mml:semantics> </mml:math> </inline-formula> appears exactly once in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript lamda Baseline circled-times upper V Subscript mu"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>λ<!-- λ --></mml:mi> </mml:msub> <mml:mo>⊗<!-- ⊗ --></mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>μ<!-- μ --></mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">V_\lambda \otimes V_\mu</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N element-of double-struck upper N"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">N\in {\mathbb N}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript upper N lamda"> <mml:semantics> <mml:msub> <mml:mi>V</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>N</mml:mi> <mml:mi>λ<!-- λ --></mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">V_{N\lambda }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> appears exactly once in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript upper N lamda Baseline circled-times upper V Subscript upper N mu"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>V</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>N</mml:mi> <mml:mi>λ<!-- λ --></mml:mi> </mml:mrow> </mml:msub> <mml:mo>⊗<!-- ⊗ --></mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>N</mml:mi> <mml:mi>μ<!-- μ --></mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">V_{N\lambda }\otimes V_{N\mu }</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.”

Puzzles and (equivariant) cohomology of Grassmannians

2003-08-15
Allen Knutson , Terence Tao
The product of two Schubert cohomology classes on a Grassmannian ${\rm Gr}_k (\mathbb{c}^n)$ has long been known to be a positive combination of other Schubert classes, and many manifestly positive … The product of two Schubert cohomology classes on a Grassmannian ${\rm Gr}_k (\mathbb{c}^n)$ has long been known to be a positive combination of other Schubert classes, and many manifestly positive formulae are now available for computing such a product (e.g., the Littlewood-Richardson rule or the more symmetric puzzle rule from A. Knutson, T. Tao, and C. Woodward [KTW]). Recently, W.~Graham showed in [G], nonconstructively, that a similar positivity statement holds for {\em $T$-equivariant} cohomology (where the coefficients are polynomials). We give the first manifestly positive formula for these coefficients in terms of puzzles using an ``equivariant puzzle piece.'' The proof of the formula is mostly combinatorial but requires no prior combinatorics and only a modicum of equivariant cohomology (which we include). As a by-product the argument gives a new proof of the puzzle (or Littlewood-Richardson) rule in the ordinary-cohomology case, but this proof requires the equivariant generalization in an essential way, as it inducts backwards from the ``most equivariant'' case. This formula is closely related to the one in A. Molev and B. Sagan [MS] for multiplying factorial Schur functions in three sets of variables, although their rule does not give a positive formula in the sense of [G]. We include a cohomological interpretation of their problem and a puzzle formulation for it.
View PDF Chat

The Nonlinear Schrödinger Equation with Combined Power-Type Nonlinearities

2007-08-08
Terence Tao , Monica Vişan , Xiaoyi Zhang
We undertake a comprehensive study of the nonlinear Schrödinger equation where u(t, x) is a complex-valued function in spacetime , λ1 and λ2 are nonzero real constants, and . We … We undertake a comprehensive study of the nonlinear Schrödinger equation where u(t, x) is a complex-valued function in spacetime , λ1 and λ2 are nonzero real constants, and . We address questions related to local and global well-posedness, finite time blowup, and asymptotic behaviour. Scattering is considered both in the energy space H 1(ℝ n ) and in the pseudoconformal space Σ := {f ∈ H 1(ℝ n ); xf ∈ L 2(ℝ n )}. Of particular interest is the case when both nonlinearities are defocusing and correspond to the -critical, respectively -critical NLS, that is, λ1, λ2 > 0 and , . The results at the endpoint are conditional on a conjectured global existence and spacetime estimate for the -critical nonlinear Schrödinger equation, which has been verified in dimensions n ≥ 2 for radial data in Tao et al. (Tao et al. to appear a,b) and Killip et al. (preprint). As an off-shoot of our analysis, we also obtain a new, simpler proof of scattering in for solutions to the nonlinear Schrödinger equation with , which was first obtained by Ginibre and Velo (1985 Ginibre , J. , Velo , G. ( 1985 ). Scattering theory in the energy space for a class of nonlinear Schrödinger equations . J. Math. Pure. Appl. 64 : 363 – 401 .[Web of Science ®] , [Google Scholar]).
View PDF Chat

Inverse Littlewood–Offord theorems and the condition number of random discrete matrices

2009-03-01
Terence Tao , Van Vu
Consider a random sum η 1 v 1 + • • • + η n v n , where η 1 , . . ., η n are independently and … Consider a random sum η 1 v 1 + • • • + η n v n , where η 1 , . . ., η n are independently and identically distributed (i.i.d.) random signs and v 1 , . . ., v n are integers.The Littlewood-Offord problem asks to maximize concentration probabilities such as P(ηIn this paper we develop an inverse Littlewood-Offord theory (somewhat in the spirit of Freiman's inverse theory in additive combinatorics), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the v 1 , . . ., v n are efficiently contained in a generalized arithmetic progression.As an application we give a new bound on the magnitude of the least singular value of a random Bernoulli matrix, which in turn provides upper tail estimates on the condition number.
View PDF Chat

Global existence and scattering for rough solutions of a nonlinear Schrödinger equation on ℝ<sup>3</sup>

2004-05-25
J. Colliander , M. Keel , Gigliola Staffilani +2 more
Abstract We prove global existence and scattering for the defocusing, cubic, nonlinear Schrödinger equation in $H^{\scriptscriptstyle S}$ (ℝ 3 ) for s &gt; ${4 \over 5}$ . The main new … Abstract We prove global existence and scattering for the defocusing, cubic, nonlinear Schrödinger equation in $H^{\scriptscriptstyle S}$ (ℝ 3 ) for s &gt; ${4 \over 5}$ . The main new estimate in the argument is a Morawetz‐type inequality for the solution ϕ. This estimate bounds whereas the well‐known Morawetz‐type estimate of Lin‐Strauss controls © 2004 Wiley Periodicals, Inc.

GLOBAL WELL-POSEDNESS OF THE BENJAMIN–ONO EQUATION IN H<sup>1</sup>(<b>R</b>)

2004-03-01
Terence Tao
We show that the Benjamin–Ono equation is globally well-posed in H s (R) for s≥1. This is despite the presence of the derivative in the nonlinearity, which causes the solution … We show that the Benjamin–Ono equation is globally well-posed in H s (R) for s≥1. This is despite the presence of the derivative in the nonlinearity, which causes the solution map to not be uniformly continuous in H s for any s [18]. The main new ingredient is to perform a global gauge transformation which almost entirely eliminates this derivative.
View PDF Chat

Almost Conservation Laws and Global Rough Solutions to a Nonlinear Schrödinger Equation

2002-01-01
J. Colliander , M. Keel , Gigliola Staffilani +2 more
We prove an "almost conservation law" to obtain global-in-time wellposedness for the cubic, defocussing nonlinear Schrödinger equation in H s (R We prove an "almost conservation law" to obtain global-in-time wellposedness for the cubic, defocussing nonlinear Schrödinger equation in H s (R
View PDF Chat

Product set estimates for non-commutative groups

2008-08-12
Terence Tao
View PDF Chat

The cubic nonlinear Schrödinger equation in two dimensions with radial data

2009-12-23
Rowan Killip , Terence Tao , Monica Vişan
We establish global well-posedness and scattering for solutions to the mass-critical nonlinear Schrödinger equation iu_t + \Delta u= ±|u|^2 u for large spherically symmetric L_x^2(ℝ^2) initial data; in the focusing … We establish global well-posedness and scattering for solutions to the mass-critical nonlinear Schrödinger equation iu_t + \Delta u= ±|u|^2 u for large spherically symmetric L_x^2(ℝ^2) initial data; in the focusing case we require, of course, that the mass is strictly less than that of the ground state. As a consequence, we deduce that in the focusing case, any spherically symmetric blowup solution must concentrate at least the mass of the ground state at the blowup time. We also establish some partial results towards the analogous claims in other dimensions and without the assumption of spherical symmetry.
View PDF Chat

The quantitative behaviour of polynomial orbits on nilmanifolds

2012-01-31
Ben Green , Terence Tao
A theorem of Leibman asserts that a polynomial orbit (g(n)Γ) n∈Z on a nilmanifold G/Γ is always equidistributed in a union of closed subnilmanifolds of G/Γ.In this paper we give … A theorem of Leibman asserts that a polynomial orbit (g(n)Γ) n∈Z on a nilmanifold G/Γ is always equidistributed in a union of closed subnilmanifolds of G/Γ.In this paper we give a quantitative version of Leibman's result, describing the uniform distribution properties of a finite polynomial orbit (g(n)Γ) n∈[N ] in a nilmanifold.More specifically we show that there is a factorisation g = εg γ, where ε(n) is "smooth," (γ(n)Γ) n∈Z is periodic and "rational," and (g (n)Γ)n∈P is uniformly distributed (up to a specified error δ) inside some subnilmanifold G /Γ of G/Γ for all sufficiently dense arithmetic progressions P ⊆ [N ].Our bounds are uniform in N and are polynomial in the error tolerance δ.
View PDF Chat

An uncertainty principle for cyclic groups of prime order

2005-01-01
Terence Tao
Let G be a finite abelian group, and let f : G → C be a complex function on G.The uncertainty principle asserts that the support supp(fwhere |X| denotes the … Let G be a finite abelian group, and let f : G → C be a complex function on G.The uncertainty principle asserts that the support supp(fwhere |X| denotes the cardinality of X.In this note we show that when G is the cyclic group Z/pZ of prime order p, then we may improve this toand show that this is absolutely sharp.As one consequence, we see that a sparse polynomial in Z/pZ consisting of k + 1 monomials can have at most k zeroes.Another consequence is a short proof of the well-known Cauchy-Davenport inequality.
View PDF Chat

Norm convergence of multiple ergodic averages for commuting transformations

2008-04-01
Terence Tao
Abstract Let T 1 ,…, T l : X → X be commuting measure-preserving transformations on a probability space $(X, \mathcal {X}, \mu )$ . We show that the multiple … Abstract Let T 1 ,…, T l : X → X be commuting measure-preserving transformations on a probability space $(X, \mathcal {X}, \mu )$ . We show that the multiple ergodic averages $\bfrac {1}{N} \sum _{n=0}^{N-1} f_1(T_1^n x) \cdots f_l(T_l^n x)$ are convergent in $L^2(X,\mathcal {X},\mu )$ as $N \to \infty $ for all $f_1,\ldots ,f_l \in L^\infty (X,\mathcal {X},\mu )$ ; this was previously established for l =2 by Conze and Lesigne [J. P. Conze and E. Lesigne. Théorèmes ergodique por les mesures diagonales. Bull. Soc. Math. France 112 (1984), 143–175] and for general l assuming some additional ergodicity hypotheses on the maps T i and T i T j −1 by Frantzikinakis and Kra [N. Frantzikinakis and B. Kra. Convergence of multiple ergodic averages for some commuting transformations. Ergod. Th. &amp; Dynam. Sys. 25 (2005), 799–809] (with the l =3 case of this result established earlier by Zhang [Q. Zhang. On the convergence of the averages $\bfrac {1}{N} \sum _{n=1}^N f_1(R^n x) f_2(S^n x) f_3(T^n x)$ . Mh. Math. 122 (1996), 275–300]). Our approach is combinatorial and finitary in nature, inspired by recent developments regarding the hypergraph regularity and removal lemmas, although we will not need the full strength of those lemmas. In particular, the l =2 case of our arguments is a finitary analogue of those by Conze and Lesigne.
View PDF Chat

Approximate Subgroups of Linear Groups

2011-07-09
Emmanuel Breuillard , Ben Green , Terence Tao
View PDF Chat

On the singularity probability of random Bernoulli matrices

2007-02-06
Terence Tao , Van Vu
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a large integer and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> … Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a large integer and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">M_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrix whose entries are i.i.d. Bernoulli random variables (each entry is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash 2"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>). We show that the probability that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">M_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is singular is at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 3 slash 4 plus o left-parenthesis 1 right-parenthesis right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">(3/4 +o(1))^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, improving an earlier estimate of Kahn, Komlós and Szemerédi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman-type inverse theorems and other tools from additive combinatorics.
View PDF Chat

The Bochner-Riesz conjecture implies the restriction conjecture

1999-02-01
Terence Tao

The Möbius function is strongly orthogonal to nilsequences

2012-01-31
Ben Green , Terence Tao
We show that the Möbius function µ(n) is strongly asymptotically orthogonal to any polynomial nilsequence (F (g(n)Γ)) n∈N .Here, G is a simply-connected nilpotent Lie group with a discrete and … We show that the Möbius function µ(n) is strongly asymptotically orthogonal to any polynomial nilsequence (F (g(n)Γ)) n∈N .Here, G is a simply-connected nilpotent Lie group with a discrete and cocompact subgroup Γ (so G/Γ is a nilmanifold ), g : Z → G is a polynomial sequence, andIn particular, this implies the Möbius and Nilsequence conjecture MN(s) from our earlier paper for every positive integer s.This is one of two major ingredients in our programme to establish a large number of cases of the generalised Hardy-Littlewood conjecture, which predicts how often a collection ψ1, . . ., ψt : Z d → Z of linear forms all take prime values.The proof is a relatively quick application of the results in our recent companion paper.We give some applications of our main theorem.We show, for example, that the Möbius function is uncorrelated with any bracket polynomial such as n √ 3 n √ 2 .We also obtain a result about the distribution of nilsequences (a n xΓ) n∈N as n ranges only over the primes.
View PDF Chat

A Refined Global Well-Posedness Result for Schrödinger Equations with Derivative

2002-01-01
J. Colliander , M. Keel , G. Staffilani +2 more
In this paper we prove that the one-dimensional Schrödinger equation with derivative in the nonlinear term is globally well-posed in Hs for $s > \frac12$ for data small in L2 … In this paper we prove that the one-dimensional Schrödinger equation with derivative in the nonlinear term is globally well-posed in Hs for $s > \frac12$ for data small in L2 . To understand the strength of this result one should recall that for $s < \frac12$ the Cauchy problem is ill-posed, in the sense that uniform continuity with respect to the initial data fails. The result follows from the method of almost conserved energies, an evolution of the "I-method" used by the same authors to obtain global well-posedness for $s >\frac23$. The same argument can be used to prove that any quintic nonlinear defocusing Schrödinger equation on the line is globally well-posed for large data in Hs for $s>\frac12$.
View PDF Chat

Multi-linear operators given by singular multipliers

2001-12-10
Camil Muscalu , Terence Tao , Christoph Thiele
We prove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Superscript p"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">L^p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> estimates for a large class of multi-linear operators, which includes … We prove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Superscript p"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">L^p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> estimates for a large class of multi-linear operators, which includes the multi-linear paraproducts studied by Coifman and Meyer (1991), as well as the bilinear Hilbert transform and other operators with large groups of modulation symmetries.

The structure of approximate groups

2012-10-19
Emmanuel Breuillard , Ben Green , Terence Tao
View PDF Chat

Sharp well-posedness and ill-posedness results for a quadratic non-linear Schrödinger equation

2005-09-24
Ioan Bejenaru , Terence Tao
View PDF Chat

Multilinear estimates for periodic KdV equations, and applications

2003-09-12
J. Colliander , M. Keel , Gigliola Staffilani +2 more
View PDF Chat

On several irrationality problems for Ahmes series

2025-05-01
Vjekoslav Kovač , Terence Tao

On a conjecture of Marton

2025-03-01
W. T. Gowers , Ben Green , Freddie Manners +1 more

New exponent pairs, zero density estimates, and zero additive energy estimates: a systematic approach

2025-01-28
Terence Tao , Tim Trudgian , Andrew Yang
We obtain several new bounds on exponents of interest in analytic number theory, including four new exponent pairs, new zero density estimates for the Riemann zeta-function, and new estimates for … We obtain several new bounds on exponents of interest in analytic number theory, including four new exponent pairs, new zero density estimates for the Riemann zeta-function, and new estimates for the additive energy of zeroes of the Riemann zeta-function. These results were obtained by creating the Analytic Number Theory Exponent Database (ANTEDB) to collect results and relationships between these exponents, and then systematically optimising these relationships to obtain the new bounds. We welcome further contributions to the database, which aims to allow easy conversion of new bounds on these exponents into optimised bounds on other related exponents of interest.
View PDF Chat

EVA-S2PLoR: A Secure Element-wise Multiplication Meets Logistic Regression on Heterogeneous Database

2025-01-09
Terence Tao , S. Andrew Peng , Tianyu Mei +2 more
Accurate nonlinear computation is a key challenge in privacy-preserving machine learning (PPML). Most existing frameworks approximate it through linear operations, resulting in significant precision loss. This paper proposes an efficient, … Accurate nonlinear computation is a key challenge in privacy-preserving machine learning (PPML). Most existing frameworks approximate it through linear operations, resulting in significant precision loss. This paper proposes an efficient, verifiable and accurate security 2-party logistic regression framework (EVA-S2PLoR), which achieves accurate nonlinear function computation through a novel secure element-wise multiplication protocol and its derived protocols. Our framework primarily includes secure 2-party vector element-wise multiplication, addition to multiplication, reciprocal, and sigmoid function based on data disguising technology, where high efficiency and accuracy are guaranteed by the simple computation flow based on the real number domain and the few number of fixed communication rounds. We provide secure and robust anomaly detection through dimension transformation and Monte Carlo methods. EVA-S2PLoR outperforms many advanced frameworks in terms of precision (improving the performance of the sigmoid function by about 10 orders of magnitude compared to most frameworks) and delivers the best overall performance in secure logistic regression experiments.
View PDF Chat

On the distribution of eigenvalues of GUE and its minors at fixed index

2024-12-14
Terence Tao
We obtain bounds on the distribution of normalized gaps of eigenvalues of $N \times N$ GUE matrix in the bulk, that do not lose logarithmic factors of $N$ in the … We obtain bounds on the distribution of normalized gaps of eigenvalues of $N \times N$ GUE matrix in the bulk, that do not lose logarithmic factors of $N$ in the limit $N \to \infty$. As an application, we obtain fixed index universality results for the GUE minor process, which in turn are useful for establishing limiting results for random hives with GUE boundary data.
View PDF Chat

Higher uniformity of arithmetic functions in short intervals II. Almost all intervals

2024-11-08
Kaisa Matomäki , Maksym Radziwiłł , Xuancheng Shao +2 more
We study higher uniformity properties of the von Mangoldt function $\Lambda$, the M\"obius function $\mu$, and the divisor functions $d_k$ on short intervals $(x,x+H]$ for almost all $x \in [X, … We study higher uniformity properties of the von Mangoldt function $\Lambda$, the M\"obius function $\mu$, and the divisor functions $d_k$ on short intervals $(x,x+H]$ for almost all $x \in [X, 2X]$. Let $\Lambda^\sharp$ and $d_k^\sharp$ be suitable approximants of $\Lambda$ and $d_k$, $G/\Gamma$ a filtered nilmanifold, and $F\colon G/\Gamma \to \mathbb{C}$ a Lipschitz function. Then our results imply for instance that when $X^{1/3+\varepsilon} \leq H \leq X$ we have, for almost all $x \in [X, 2X]$, \[ \sup_{g \in \text{Poly}(\mathbb{Z} \to G)} \left| \sum_{x < n \leq x+H} (\Lambda(n)-\Lambda^\sharp(n)) \overline{F}(g(n)\Gamma) \right| \ll H\log^{-A} X \] for any fixed $A>0$, and that when $X^{\varepsilon} \leq H \leq X$ we have, for almost all $x \in [X, 2X]$, \[ \sup_{g \in \text{Poly}(\mathbb{Z} \to G)} \left| \sum_{x < n \leq x+H} (d_k(n)-d_k^\sharp(n)) \overline{F}(g(n)\Gamma) \right| = o(H \log^{k-1} X). \] As a consequence, we show that the short interval Gowers norms $\|\Lambda-\Lambda^\sharp\|_{U^s(X,X+H]}$ and $\|d_k-d_k^\sharp\|_{U^s(X,X+H]}$ are also asymptotically small for any fixed $s$ in the same ranges of $H$. This in turn allows us to establish the Hardy-Littlewood conjecture and the divisor correlation conjecture with a short average over one variable. Our main new ingredients are type $II$ estimates obtained by developing a "contagion lemma" for nilsequences and then using this to "scale up" an approximate functional equation for the nilsequence to a larger scale. This extends an approach developed by Walsh for Fourier uniformity.
View PDF Chat

EVA-S3PC: Efficient, Verifiable, Accurate Secure Matrix Multiplication Protocol Assembly and Its Application in Regression

2024-11-05
S. Andrew Peng , Tianrui Liu , Terence Tao +3 more
Efficient multi-party secure matrix multiplication is crucial for privacy-preserving machine learning, but existing mixed-protocol frameworks often face challenges in balancing security, efficiency, and accuracy. This paper presents an efficient, verifiable … Efficient multi-party secure matrix multiplication is crucial for privacy-preserving machine learning, but existing mixed-protocol frameworks often face challenges in balancing security, efficiency, and accuracy. This paper presents an efficient, verifiable and accurate secure three-party computing (EVA-S3PC) framework that addresses these challenges with elementary 2-party and 3-party matrix operations based on data obfuscation techniques. We propose basic protocols for secure matrix multiplication, inversion, and hybrid multiplication, ensuring privacy and result verifiability. Experimental results demonstrate that EVA-S3PC achieves up to 14 significant decimal digits of precision in Float64 calculations, while reducing communication overhead by up to $54.8\%$ compared to state of art methods. Furthermore, 3-party regression models trained using EVA-S3PC on vertically partitioned data achieve accuracy nearly identical to plaintext training, which illustrates its potential in scalable, efficient, and accurate solution for secure collaborative modeling across domains.
View PDF Chat

Pointwise convergence of bilinear polynomial averages over the primes

2024-09-16
Ben Krause , Hamed Mousavi , Terence Tao +1 more
We show that on a $\sigma$-finite measure preserving system $X = (X,\nu, T)$, the non-conventional ergodic averages $$ \mathbb{E}_{n \in [N]} \Lambda(n) f(T^n x) g(T^{P(n)} x)$$ converge pointwise almost everywhere … We show that on a $\sigma$-finite measure preserving system $X = (X,\nu, T)$, the non-conventional ergodic averages $$ \mathbb{E}_{n \in [N]} \Lambda(n) f(T^n x) g(T^{P(n)} x)$$ converge pointwise almost everywhere for $f \in L^{p_1}(X)$, $g \in L^{p_2}(X)$, and $1/p_1 + 1/p_2 \leq 1$, where $P$ is a polynomial with integer coefficients of degree at least $2$. This had previously been established with the von Mangoldt weight $\Lambda$ replaced by the constant weight $1$ by the first and third authors with Mirek, and by the M\"obius weight $\mu$ by the fourth author. The proof is based on combining tools from both of these papers, together with several Gowers norm and polynomial averaging operator estimates on approximants to the von Mangoldt function of ''Cram\'er'' and ''Heath-Brown'' type.
View PDF Chat

Adjoint Brascamp–Lieb inequalities

2024-09-14
Jonathan Bennett , Terence Tao
Abstract The Brascamp–Lieb inequalities are a generalization of the Hölder, Loomis–Whitney, Young, and Finner inequalities that have found many applications in harmonic analysis and elsewhere. In this paper, we introduce … Abstract The Brascamp–Lieb inequalities are a generalization of the Hölder, Loomis–Whitney, Young, and Finner inequalities that have found many applications in harmonic analysis and elsewhere. In this paper, we introduce an “adjoint” version of these inequalities, which can be viewed as an version of the entropic Brascamp–Lieb inequalities of Carlen and Cordero–Erausquin. As applications, we reprove a log‐convexity property of the Gowers uniformity norms, and establish some reverse inequalities for various tomographic transforms. We conclude with some open questions.

Planar point sets with forbidden $4$-point patterns and few distinct distances

2024-09-02
Terence Tao
We show that for any large $n$, there exists a set of $n$ points in the plane with $O(n^2/\sqrt{\log n})$ distinct distances, such that any four points in the set … We show that for any large $n$, there exists a set of $n$ points in the plane with $O(n^2/\sqrt{\log n})$ distinct distances, such that any four points in the set determine at least five distinct distances. This answers (in the negative) a question of Erd\H{o}s. The proof combines an analysis by Dumitrescu of forbidden four-point patterns with an algebraic construction of Thiele and Dumitrescu (to eliminate parallelograms), as well as a randomized transformation of that construction (to eliminate most other forbidden patterns).
View PDF Chat

Sumsets and entropy revisited

2024-07-31
Ben Green , Freddie Manners , Terence Tao
Abstract The entropic doubling of a random variable taking values in an abelian group is a variant of the notion of the doubling constant of a finite subset of , … Abstract The entropic doubling of a random variable taking values in an abelian group is a variant of the notion of the doubling constant of a finite subset of , but it enjoys somewhat better properties; for instance, it contracts upon applying a homomorphism. In this paper we develop further the theory of entropic doubling and give various applications, including: (1) A new proof of a result of Pálvölgyi and Zhelezov on the “skew dimension” of subsets of with small doubling; (2) A new proof, and an improvement, of a result of the second author on the dimension of subsets of with small doubling; (3) A proof that the Polynomial Freiman–Ruzsa conjecture over implies the (weak) Polynomial Freiman–Ruzsa conjecture over .
View PDF Chat

Dense sets of natural numbers with unusually large least common multiples

2024-07-04
Terence Tao
We construct a set $A \subset \mathbf{N}$ such that one has $$ \sum_{n \in A: n \leq x} \frac{1}{n} = \exp\left(\left(\frac{1}{2}+o(1)\right) (\log\log x)^{1/2} \log\log\log x \right)$$ and $$ \frac{1}{(\sum_{n \in … We construct a set $A \subset \mathbf{N}$ such that one has $$ \sum_{n \in A: n \leq x} \frac{1}{n} = \exp\left(\left(\frac{1}{2}+o(1)\right) (\log\log x)^{1/2} \log\log\log x \right)$$ and $$ \frac{1}{(\sum_{n \in A: n \leq x} \frac{1}{n})^2} \sum_{n,m \in A: n < m \leq x} \frac{1}{\operatorname{lcm}(n,m)} \asymp 1$$ for sufficiently large $x$. The exponent $\frac{1}{2}$ can replaced by any other positive constant, but the growth rate is otherwise optimal. This answers in the negative a question of Erd\H{o}s and Graham.
View PDF Chat

A counterexample to the periodic tiling conjecture

2024-07-01
Rachel Greenfeld , Terence Tao
The periodic tiling conjecture asserts that any finite subset of a lattice $\mathbb{Z}^d$ that tiles that lattice by translations, in fact tiles periodically. In this work we disprove this conjecture … The periodic tiling conjecture asserts that any finite subset of a lattice $\mathbb{Z}^d$ that tiles that lattice by translations, in fact tiles periodically. In this work we disprove this conjecture for sufficiently large $d$, which also implies a disproof of the corresponding conjecture for Euclidean spaces $\mathbb{R}^d$. In fact, we also obtain a counterexample in a group of the form $\mathbb{Z}^2 \times G_0$ for some finite abelian $2$-group $G_0$. Our methods rely on encoding a "Sudoku puzzle" whose rows and other non-horizontal lines are constrained to lie in a certain class of "$2$-adically structured functions," in terms of certain functional equations that can be encoded in turn as a single tiling equation, and then demonstrating that solutions to this Sudoku puzzle exist, but are all non-periodic.
View PDF Chat

A lower bound on the mean value of the Erdős–Hooley Delta function

2024-06-30
Kevin Ford , Dimitris Koukoulopoulos , Terence Tao
Abstract We give an improved lower bound for the average of the Erdős–Hooley function , namely for all and any fixed , where is an exponent previously appearing in work … Abstract We give an improved lower bound for the average of the Erdős–Hooley function , namely for all and any fixed , where is an exponent previously appearing in work of Green and the first two authors. This improves on a previous lower bound of of Hall and Tenenbaum, and can be compared to the recent upper bound of of the second and third authors.
View PDF Chat

Monotone Nondecreasing Sequences of the Euler Totient Function

2024-05-23
Terence Tao
Abstract Let M ( x ) denote the largest cardinality of a subset of $$\{n \in \mathbb {N}: n \le x\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> <mml:mo>:</mml:mo> <mml:mi>n</mml:mi> … Abstract Let M ( x ) denote the largest cardinality of a subset of $$\{n \in \mathbb {N}: n \le x\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> <mml:mo>:</mml:mo> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>x</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> on which the Euler totient function $$\varphi (n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>φ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is nondecreasing. We show that $$M(x) = \left( 1+O\left( \frac{(\log \log x)^5}{\log x}\right) \right) \pi (x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mfenced> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mfrac> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>5</mml:mn> </mml:msup> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>x</mml:mi> </mml:mrow> </mml:mfrac> </mml:mfenced> </mml:mfenced> <mml:mi>π</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for all $$x \ge 10$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>10</mml:mn> </mml:mrow> </mml:math> , answering questions of Erdős and Pollack–Pomerance–Treviño. A similar result is also obtained for the sum of divisors function $$\sigma (n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .
View PDF Chat

Marton's Conjecture in abelian groups with bounded torsion

2024-04-02
W. T. Gowers , Ben Green , Freddie Manners +1 more
We prove a Freiman--Ruzsa-type theorem with polynomial bounds in arbitrary abelian groups with bounded torsion, thereby proving (in full generality) a conjecture of Marton. Specifically, let $G$ be an abelian … We prove a Freiman--Ruzsa-type theorem with polynomial bounds in arbitrary abelian groups with bounded torsion, thereby proving (in full generality) a conjecture of Marton. Specifically, let $G$ be an abelian group of torsion $m$ (meaning $mg=0$ for all $g \in G$) and suppose that $A$ is a non-empty subset of $G$ with $|A+A| \leq K|A|$. Then $A$ can be covered by at most $(2K)^{O(m^3)}$ translates of a subgroup of $H \leq G$ of cardinality at most $|A|$. The argument is a variant of that used in the case $G = \mathbf{F}_2^n$ in a recent paper of the authors.
View PDF Chat

The structure of arbitrary Conze–Lesigne systems

2024-02-21
Asgar Jamneshan , Or Shalom , Terence Tao
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a countable abelian group. An (abstract) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal … Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a countable abelian group. An (abstract) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-system <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper X"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">X</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {X}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> - that is, an (abstract) probability space equipped with an (abstract) probability-preserving action of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> - is said to be a <italic>Conze–Lesigne system</italic> if it is equal to its second Host–Kra–Ziegler factor <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Z squared left-parenthesis normal upper X right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">Z</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">X</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {Z}^2(\mathrm {X})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The main result of this paper is a structural description of such Conze–Lesigne systems for arbitrary countable abelian <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, namely that they are the inverse limit of translational systems <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript n Baseline slash normal upper Lamda Subscript n"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msub> <mml:mi mathvariant="normal">Λ<!-- Λ --></mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">G_n/\Lambda _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> arising from locally compact nilpotent groups <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript n"> <mml:semantics> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">G_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of nilpotency class <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2"> <mml:semantics> <mml:mn>2</mml:mn> <mml:annotation encoding="application/x-tex">2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, quotiented by a lattice <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Lamda Subscript n"> <mml:semantics> <mml:msub> <mml:mi mathvariant="normal">Λ<!-- Λ --></mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\Lambda _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Results of this type were previously known when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ<!-- Γ --></mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> was finitely generated, or the product of cyclic groups of prime order. In a companion paper, two of us will apply this structure theorem to obtain an inverse theorem for the Gowers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper U cubed left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>U</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">U^3(G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> norm for arbitrary finite abelian groups <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

The convergence of an alternating series of Erdős, assuming the Hardy–Littlewood prime tuples conjecture

2024-02-01
Terence Tao
It is an open question of Erdős as to whether the alternating series $\sum _{n=1}^\infty \frac {(-1)^n n}{p_n}$ is (conditionally) convergent, where $p_n$ denotes the $n{\mathrm {th}}$ prime. By using … It is an open question of Erdős as to whether the alternating series $\sum _{n=1}^\infty \frac {(-1)^n n}{p_n}$ is (conditionally) convergent, where $p_n$ denotes the $n{\mathrm {th}}$ prime. By using a random sifted model of the primes recently introduced by Banks, Ford, and the author, as well as variants of a well known calculation of Gallagher, we show that the answer to this question is affirmative assuming a suitably strong version of the Hardy–Littlewood prime tuples conjecture.
View PDF Chat

1. Does One Have to be a Genius to Do Maths? by Terence Tao

2024-01-01
Terence Tao

Sums of GUE matrices and concentration of hives from correlation decay of eigengaps

2023-12-28
Hariharan Narayanan , Scott Sheffield⋆ , Terence Tao

Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions

2023-12-12
Terence Tao , Joni Teräväinen
We establish quantitative bounds on the U^{k}[N] Gowers norms of the Möbius function \mu and the von Mangoldt function \Lambda for all k , with error terms of the shape … We establish quantitative bounds on the U^{k}[N] Gowers norms of the Möbius function \mu and the von Mangoldt function \Lambda for all k , with error terms of the shape O((\log\log N)^{-c}) . As a consequence, we obtain quantitative bounds for the number of solutions to any linear system of equations of finite complexity in the primes, with the same shape of error terms. We also obtain the first quantitative bounds on the size of sets containing no k -term arithmetic progressions with shifted prime difference.
View PDF Chat

Infinite partial sumsets in the primes

2023-12-01
Terence Tao , Tamar Ziegler

An upper bound on the mean value of the Erdős–Hooley Delta function

2023-11-09
Dimitris Koukoulopoulos , Terence Tao
Abstract The Erdős–Hooley Delta function is defined for as . We prove that for all . This improves on earlier work of Hooley, Hall–Tenenbaum, and La Bretèche–Tenenbaum. Abstract The Erdős–Hooley Delta function is defined for as . We prove that for all . This improves on earlier work of Hooley, Hall–Tenenbaum, and La Bretèche–Tenenbaum.
View PDF Chat

Perfectly Packing a Square by Squares of Nearly Harmonic Sidelength

2023-07-01
Terence Tao
Abstract A well-known open problem of Meir and Moser asks if the squares of sidelength 1/ n for $$n\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> can be … Abstract A well-known open problem of Meir and Moser asks if the squares of sidelength 1/ n for $$n\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> can be packed perfectly into a rectangle of area $$\sum _{n=2}^\infty n^{-2}=\pi ^2/6-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mi>∞</mml:mi> </mml:msubsup> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>π</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>/</mml:mo> <mml:mn>6</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . In this paper we show that for any $$1/2&lt;t&lt;1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>&lt;</mml:mo> <mml:mi>t</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , and any $$n_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>n</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> that is sufficiently large depending on t , the squares of sidelength $$n^{-t}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msup> </mml:math> for $$n\ge n_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:msub> <mml:mi>n</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> </mml:math> can be packed perfectly into a square of area $$\sum _{n=n_0}^\infty n^{-2t}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>n</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:mi>∞</mml:mi> </mml:msubsup> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mi>t</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> . This was previously known (if one packs a rectangle instead of a square) for $$1/2&lt;t\le 2/3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>&lt;</mml:mo> <mml:mi>t</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> (in which case one can take $$n_0=1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>n</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> ).
View PDF Chat

Large prime gaps and probabilistic models

2023-06-14
William D. Banks , Kevin Ford , Terence Tao
Abstract We introduce a new probabilistic model of the primes consisting of integers that survive the sieving process when a random residue class is selected for every prime modulus below … Abstract We introduce a new probabilistic model of the primes consisting of integers that survive the sieving process when a random residue class is selected for every prime modulus below a specific bound. From a rigorous analysis of this model, we obtain heuristic upper and lower bounds for the size of the largest prime gap in the interval $[1,x]$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>[</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>x</mml:mi> <mml:mo>]</mml:mo> </mml:math> . Our results are stated in terms of the extremal bounds in the interval sieve problem. The same methods also allow us to rigorously relate the validity of the Hardy-Littlewood conjectures for an arbitrary set (such as the actual primes) to lower bounds for the largest gaps within that set.
View PDF Chat

Measurable Tilings by Abelian Group Actions

2023-03-23
Jan Grebík , Rachel Greenfeld , Václav Rozhoň +1 more
Abstract Let $X$ be a measure space with a measure-preserving action $(g,x) \mapsto g \cdot x$ of an abelian group $G$. We consider the problem of understanding the structure of … Abstract Let $X$ be a measure space with a measure-preserving action $(g,x) \mapsto g \cdot x$ of an abelian group $G$. We consider the problem of understanding the structure of measurable tilings $F \odot A = X$ of $X$ by a measurable tile $A \subset X$ translated by a finite set $F \subset G$ of shifts, thus the translates $f \cdot A$, $f \in F$ partition $X$ up to null sets. Adapting arguments from previous literature, we establish a “dilation lemma” that asserts, roughly speaking, that $F \odot A = X$ implies $F^{r} \odot A = X$ for a large family of integer dilations $r$, and use this to establish a structure theorem for such tilings analogous to that established recently by the second and fourth authors. As applications of this theorem, we completely classify those random tilings of finitely generated abelian groups that are “factors of iid”, and show that measurable tilings of a torus ${\mathbb{T}}^{d}$ can always be continuously (in fact linearly) deformed into a tiling with rational shifts, with particularly strong results in the low-dimensional cases $d=1,2$ (in particular resolving a conjecture of Conley, the first author, and Pikhurko in the $d=1$ case).
View PDF Chat

Higher uniformity of bounded multiplicative functions in short intervals on average

2023-02-03
Kaisa Matomäki , Maksym Radziwiłł , Terence Tao +2 more
Let $\lambda$ denote the Liouville function. We show that, as $X \rightarrow \infty$, $$\int_{X}^{2X} \sup_{\substack{P(Y)\in \mathbb{R}[Y]\\ deg(P)\leq k}} \Big | \sum_{x \leq n \leq x + H} \lambda(n) e(-P(n)) \Big … Let $\lambda$ denote the Liouville function. We show that, as $X \rightarrow \infty$, $$\int_{X}^{2X} \sup_{\substack{P(Y)\in \mathbb{R}[Y]\\ deg(P)\leq k}} \Big | \sum_{x \leq n \leq x + H} \lambda(n) e(-P(n)) \Big |\ dx = o ( X H)$$ for all fixed $k$ and $X^{\theta} \leq H \leq X$ with $0 < \theta < 1$ fixed but arbitrarily small. Previously this was only established for $k \leq 1$. We obtain this result as a special case of the corresponding statement for (non-pretentious) $1$-bounded multiplicative functions that we prove. In fact, we are able to replace the polynomial phases $e(-P(n))$ by degree $k$ nilsequences $\overline{F}(g(n) \Gamma)$. By the inverse theory for the Gowers norms this implies the higher order asymptotic uniformity result $$\int_{X}^{2X} \| \lambda \|_{U^{k+1}([x,x+H])}\ dx = o ( X )$$ in the same range of $H$. We present applications of this result to patterns of various types in the Liouville sequence. Firstly, we show that the number of sign patterns of the Liouville function is superpolynomial, making progress on a conjecture of Sarnak about the Liouville sequence having positive entropy. Secondly, we obtain cancellation in averages of $\lambda$ over short polynomial progressions $(n+P_1(m),\ldots, n+P_k(m))$, which in the case of linear polynomials yields a new averaged version of Chowla's conjecture. We are in fact able to prove our results on polynomial phases in the wider range $H\geq \exp((\log X)^{5/8+\varepsilon})$, thus strengthening also previous work on the Fourier uniformity of the Liouville function.
View PDF Chat

Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile

2023-01-04
Rachel Greenfeld , Terence Tao
Abstract We construct an example of a group $$G = \mathbb {Z}^2 \times G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>×</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow></mml:math> for a finite abelian group $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> , a subset E of $$G_0$$ … Abstract We construct an example of a group $$G = \mathbb {Z}^2 \times G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>×</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow></mml:math> for a finite abelian group $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> , a subset E of $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> , and two finite subsets $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> of G , such that it is undecidable in ZFC whether $$\mathbb {Z}^2\times E$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>×</mml:mo><mml:mi>E</mml:mi></mml:mrow></mml:math> can be tiled by translations of $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> . In particular, this implies that this tiling problem is aperiodic , in the sense that (in the standard universe of ZFC) there exist translational tilings of E by the tiles $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup></mml:math> ). A similar construction also applies for $$G=\mathbb {Z}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mi>d</mml:mi></mml:msup></mml:mrow></mml:math> for sufficiently large d . If one allows the group $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F . The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.
View PDF Chat

Infinite partial sumsets in the primes

2023-01-01
Terence Tao , Tamar Ziegler
We show that there exist infinite sets $A = \{a_1,a_2,\dots\}$ and $B = \{b_1,b_2,\dots\}$ of natural numbers such that $a_i+b_j$ is prime whenever $1 \leq i < j$. We show that there exist infinite sets $A = \{a_1,a_2,\dots\}$ and $B = \{b_1,b_2,\dots\}$ of natural numbers such that $a_i+b_j$ is prime whenever $1 \leq i < j$.
View PDF Chat

The structure of totally disconnected Host--Kra--Ziegler factors, and the inverse theorem for the $U^k$ Gowers uniformity norms on finite abelian groups of bounded torsion

2023-01-01
Asgar Jamneshan , Or Shalom , Terence Tao
Let $\Gamma$ be a countable abelian group, let $k\geq 1$, and let $\mathrm{X}=(X,\mathcal{X},\mu,T)$ be an ergodic $\Gamma$-system of order $k$ in the sense of Host--Kra--Ziegler. The $\Gamma$-system $\mathrm{X}$ is said … Let $\Gamma$ be a countable abelian group, let $k\geq 1$, and let $\mathrm{X}=(X,\mathcal{X},\mu,T)$ be an ergodic $\Gamma$-system of order $k$ in the sense of Host--Kra--Ziegler. The $\Gamma$-system $\mathrm{X}$ is said to be totally disconnected if all its structure groups are totally disconnected. We show that any totally disconnected $\Gamma$-system of order $k$ is a generalized factor of a $\mathbb{Z}^\omega$-system with the structure of a Weyl system. As a consequence of this structure theorem, we show that totally disconnected $\Gamma$-systems of order $k$ are represented by translations on double cosets of nilpotent Polish groups. By a correspondence principle of two of us, we can use this representation to establish a (weak) inverse theorem for the $U^k$ Gowers uniformity norms on finite abelian groups of bounded torsion.
View PDF Chat

A Host--Kra ${\mathbf F}_2^ω$-system of order $5$ that is not Abramov of order $5$, and non-measurability of the inverse theorem for the $U^6({\mathbf F}_2^n)$ norm

2023-01-01
Asgar Jamneshan , Or Shalom , Terence Tao
It was conjectured by Bergelson, Tao, and Ziegler that every Host--Kra ${\mathbf F}_p^\omega$-system of order $k$ is an Abramov system of order $k$. This conjecture has been verified for $k … It was conjectured by Bergelson, Tao, and Ziegler that every Host--Kra ${\mathbf F}_p^\omega$-system of order $k$ is an Abramov system of order $k$. This conjecture has been verified for $k \leq p+1$. In this paper we show that the conjecture fails when $k=5, p=2$. We in fact establish a stronger (combinatorial) statement, in that we produce a bounded function $f: {\mathbf F}_2^n \to {\mathbf C}$ of large Gowers norm $\|f\|_{U^6({\mathbf F}_2^n)}$ which (as per the inverse theorem for that norm) correlates with a non-classical quintic phase polynomial $e(P)$, but with the property that all such phase polynomials $e(P)$ are ``non-measurable'' in the sense that they cannot be well approximated by functions of a bounded number of random translates of $f$.
View PDF Chat

An upper bound on the mean value of the Erdős-Hooley Delta function

2023-01-01
Dimitris Koukoulopoulos , Terence Tao
The Erd\H{o}s-Hooley Delta function is defined for $n\in\mathbb{N}$ as $\Delta(n)=\sup_{u\in\mathbb{R}} \#\{d|n : e^u<d\le e^{u+1}\}$. We prove that $\sum_{n\le x} \Delta(n) \ll x(\log\log x)^{11/4}$ for all $x\ge100$. This improves on earlier … The Erd\H{o}s-Hooley Delta function is defined for $n\in\mathbb{N}$ as $\Delta(n)=\sup_{u\in\mathbb{R}} \#\{d|n : e^u<d\le e^{u+1}\}$. We prove that $\sum_{n\le x} \Delta(n) \ll x(\log\log x)^{11/4}$ for all $x\ge100$. This improves on earlier work of Hooley, Hall--Tenenbaum and La Bret\`eche-Tenenbaum.
View PDF Chat

Sums of GUE matrices and concentration of hives from correlation decay of eigengaps

2023-01-01
Hariharan Narayanan , Scott Sheffield⋆ , Terence Tao
Associated to two given sequences of eigenvalues $\lambda_1 \geq \dots \geq \lambda_n$ and $\mu_1 \geq \dots \geq \mu_n$ is a natural polytope, the polytope of augmented hives with the specified … Associated to two given sequences of eigenvalues $\lambda_1 \geq \dots \geq \lambda_n$ and $\mu_1 \geq \dots \geq \mu_n$ is a natural polytope, the polytope of augmented hives with the specified boundary data, which is associated to sums of random Hermitian matrices with these eigenvalues. As a first step towards the asymptotic analysis of random hives, we show that if the eigenvalues are drawn from the GUE ensemble, then the associated augmented hives exhibit concentration as $n \rightarrow \infty$. Our main ingredients include a representation due to Speyer of augmented hives involving a supremum of linear functions applied to a product of Gelfand--Tsetlin polytopes; known results by Klartag on the KLS conjecture in order to handle the aforementioned supremum; covariance bounds of Cipolloni--Erd\H{o}s--Schr\"oder of eigenvalue gaps of GUE; and the use of the theory of determinantal processes to analyze the GUE minor process.
View PDF Chat

Sumsets and entropy revisited

2023-01-01
Ben Green , Freddie Manners , Terence Tao
The entropic doubling $\sigma_{\operatorname{ent}}[X]$ of a random variable $X$ taking values in an abelian group $G$ is a variant of the notion of the doubling constant $\sigma[A]$ of a finite … The entropic doubling $\sigma_{\operatorname{ent}}[X]$ of a random variable $X$ taking values in an abelian group $G$ is a variant of the notion of the doubling constant $\sigma[A]$ of a finite subset $A$ of $G$, but it enjoys somewhat better properties; for instance, it contracts upon applying a homomorphism. In this paper we develop further the theory of entropic doubling and give various applications, including: (1) A new proof of a result of P\'alv\"olgyi and Zhelezov on the ``skew dimension'' of subsets of $\mathbf{Z}^D$ with small doubling; (2) A new proof, and an improvement, of a result of the second author on the dimension of subsets of $\mathbf{Z}^D$ with small doubling; (3) A proof that the Polynomial Freiman--Ruzsa conjecture over $\mathbf{F}_2$ implies the (weak) Polynomial Freiman--Ruzsa conjecture over $\mathbf{Z}$.
View PDF Chat

Adjoint Brascamp-Lieb inequalities

2023-01-01
Jonathan Bennett , Terence Tao
The Brascamp-Lieb inequalities are a generalization of the Hölder, Loomis-Whitney, Young, and Finner inequalities that have found many applications in harmonic analysis and elsewhere. In this paper we introduce an … The Brascamp-Lieb inequalities are a generalization of the Hölder, Loomis-Whitney, Young, and Finner inequalities that have found many applications in harmonic analysis and elsewhere. In this paper we introduce an "adjoint" version of these inequalities, which can be viewed as an $L^p$ version of the entropy Brascamp-Lieb inequalities of Carlen and Cordero-Erausquin. As applications, we reprove a log-convexity property of the Gowers uniformity norms, and establish some reverse $L^p$ inequalities for various tomographic transforms. We conclude with some open questions.
View PDF Chat

The convergence of an alternating series of Erdős, assuming the Hardy--Littlewood prime tuples conjecture

2023-01-01
Terence Tao
It is an open question of Erd\H{o}s as to whether the alternating series $\sum_{n=1}^\infty \frac{(-1)^n n}{p_n}$ is (conditionally) convergent, where $p_n$ denotes the $n^{\mathrm{th}}$ prime. By using a random sifted … It is an open question of Erd\H{o}s as to whether the alternating series $\sum_{n=1}^\infty \frac{(-1)^n n}{p_n}$ is (conditionally) convergent, where $p_n$ denotes the $n^{\mathrm{th}}$ prime. By using a random sifted model of the primes recently introduced by Banks, Ford, and the author, as well as variants of a well known calculation of Gallagher, we show that the answer to this question is affirmative assuming a suitably strong version of the Hardy--Littlewood prime tuples conjecture.

A lower bound on the mean value of the Erdős-Hooley Delta function

2023-01-01
Kevin R. Ford , Dimitris Koukoulopoulos , Terence Tao
We give an improved lower bound for the average of the Erd\H{o}s-Hooley function $\Delta(n)$, namely $\sum_{n\le x} \Delta(n) \gg_\varepsilon x(\log\log x)^{1+\eta-\varepsilon}$ for all $x\geqslant100$ and any fixed $\varepsilon$, where $\eta … We give an improved lower bound for the average of the Erd\H{o}s-Hooley function $\Delta(n)$, namely $\sum_{n\le x} \Delta(n) \gg_\varepsilon x(\log\log x)^{1+\eta-\varepsilon}$ for all $x\geqslant100$ and any fixed $\varepsilon$, where $\eta = 0.3533227\dots$ is an exponent previously appearing in work of Green and the first two authors. This improves on a previous lower bound of $\gg x \log\log x$ of Hall and Tenenbaum, and can be compared to the recent upper bound of $x (\log\log x)^{11/4}$ of the second and third authors.
View PDF Chat

Monotone non-decreasing sequences of the Euler totient function

2023-01-01
Terence Tao
Let $M(x)$ denote the largest cardinality of a subset of $\{n \in \mathbf{N}: n \leq x\}$ on which the Euler totient function $\varphi(n)$ is non-decreasing. We show that $M(x) = … Let $M(x)$ denote the largest cardinality of a subset of $\{n \in \mathbf{N}: n \leq x\}$ on which the Euler totient function $\varphi(n)$ is non-decreasing. We show that $M(x) = (1+O(\frac{(\log\log x)^5}{\log x})) \pi(x)$ for all $x \geq 10$, answering questions of Erd\H{o}s and Pollack--Pomerance--Trevi\~no. A similar result is also obtained for the sum of divisors function $\sigma(n)$.

Undecidability of translational monotilings

2023-01-01
Rachel Greenfeld , Terence Tao
In the 60's, Berger famously showed that translational tilings of $\mathbb{Z}^2$ with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a … In the 60's, Berger famously showed that translational tilings of $\mathbb{Z}^2$ with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a single tile) in $\mathbb{Z}^2$. The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa and Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually $\mathbb{Z}^2$ spaces, namely, spaces of the form $\mathbb{Z}^2\times G_0$, where $G_0$ is a finite Abelian group. This also implies the undecidability of translational monotilings in $\mathbb{Z}^d$, $d\geq 3$.
View PDF Chat

A Maclaurin type inequality

2023-01-01
Terence Tao
The classical Maclaurin inequality asserts that the elementary symmetric means $$ s_k(y) = \frac{1}{\binom{n}{k}} \sum_{1 \leq i_1 < \dots < i_k \leq n} y_{i_1} \dots y_{i_k}$$ obey the inequality $s_\ell(y)^{1/\ell} … The classical Maclaurin inequality asserts that the elementary symmetric means $$ s_k(y) = \frac{1}{\binom{n}{k}} \sum_{1 \leq i_1 < \dots < i_k \leq n} y_{i_1} \dots y_{i_k}$$ obey the inequality $s_\ell(y)^{1/\ell} \leq s_k(y)^{1/k}$ whenever $1 \leq k \leq \ell \leq n$ and $y = (y_1,\dots,y_n)$ consists of non-negative reals. We establish a variant $$ |s_\ell(y)|^{\frac{1}{\ell}} \ll \frac{\ell^{1/2}}{k^{1/2}} \max (|s_k(y)|^{\frac{1}{k}}, |s_{k+1}(y)|^{\frac{1}{k+1}})$$ of this inequality in which the $y_i$ are permitted to be negative. In this regime the inequality is sharp up to constants. Such an inequality was previously known without the $k^{1/2}$ factor in the denominator.
View PDF Chat

Higher uniformity of arithmetic functions in short intervals I. All intervals

2023-01-01
Kaisa Matomäki , Xuancheng Shao , Terence Tao +1 more
Abstract We study higher uniformity properties of the Möbius function $\mu $ , the von Mangoldt function $\Lambda $ , and the divisor functions $d_k$ on short intervals $(X,X+H]$ with … Abstract We study higher uniformity properties of the Möbius function $\mu $ , the von Mangoldt function $\Lambda $ , and the divisor functions $d_k$ on short intervals $(X,X+H]$ with $X^{\theta +\varepsilon } \leq H \leq X^{1-\varepsilon }$ for a fixed constant $0 \leq \theta &lt; 1$ and any $\varepsilon&gt;0$ . More precisely, letting $\Lambda ^\sharp $ and $d_k^\sharp $ be suitable approximants of $\Lambda $ and $d_k$ and $\mu ^\sharp = 0$ , we show for instance that, for any nilsequence $F(g(n)\Gamma )$ , we have $$\begin{align*}\sum_{X &lt; n \leq X+H} (f(n)-f^\sharp(n)) F(g(n) \Gamma) \ll H \log^{-A} X \end{align*}$$ when $\theta = 5/8$ and $f \in \{\Lambda , \mu , d_k\}$ or $\theta = 1/3$ and $f = d_2$ . As a consequence, we show that the short interval Gowers norms $\|f-f^\sharp \|_{U^s(X,X+H]}$ are also asymptotically small for any fixed s for these choices of $f,\theta $ . As applications, we prove an asymptotic formula for the number of solutions to linear equations in primes in short intervals and show that multiple ergodic averages along primes in short intervals converge in $L^2$ . Our innovations include the use of multiparameter nilsequence equidistribution theorems to control type $II$ sums and an elementary decomposition of the neighborhood of a hyperbola into arithmetic progressions to control type $I_2$ sums.
View PDF Chat

On a conjecture of Marton

2023-01-01
W. T. Gowers , Ben Green , Freddie Manners +1 more
We prove a conjecture of K. Marton, widely known as the polynomial Freiman--Ruzsa conjecture, in characteristic $2$. The argument extends to odd characteristic, with details to follow in a subsequent … We prove a conjecture of K. Marton, widely known as the polynomial Freiman--Ruzsa conjecture, in characteristic $2$. The argument extends to odd characteristic, with details to follow in a subsequent paper.
View PDF Chat

Homogenization of iterated singular integrals with applications to random quasiconformal maps

2022-12-22
Kari Astala , Steffen Rohde , Eero Saksman +1 more
We study homogenization of iterated randomized singular integrals and homeomorphic solutions to the Beltrami differential equation with a random Beltrami coefficient. More precisely, let $(F_j)_{j \geq 1}$ be a sequence … We study homogenization of iterated randomized singular integrals and homeomorphic solutions to the Beltrami differential equation with a random Beltrami coefficient. More precisely, let $(F_j)_{j \geq 1}$ be a sequence of normalized homeomorphic solutions to the planar Beltrami equation $\overline{\partial} F_j (z)=\mu_j(z,\omega) \partial F_j(z),$ where the random dilatation satisfies $|\mu_j|\leq k<1$ and has locally periodic statistics, for example of the type $$\mu_j (z,\omega)=\phi(z)\sum_{n\in \mathbf{Z}^2}g(2^j z-n,X_{n}(\omega)), $$ where $g(z,\omega)$ decays rapidly in $z$, the random variables $X_{n}$ are i.i.d., and $\phi\in C^\infty_0$. We establish the almost sure and local uniform convergence as $j\to\infty$ of the maps $F_j$ to a deterministic quasiconformal limit $F_\infty$. This result is obtained as an application of our main theorem, which deals with homogenization of iterated randomized singular integrals. As a special case of our theorem, let $T_1,\ldots , T_{m}$ be translation and dilation invariant singular integrals on ${\bf R}^d, $ and consider a $d$-dimensional version of $\mu_j$, e.g., as defined above or within a more general setting. We then prove that there is a deterministic function $f$ such that almost surely as $j\to\infty$, $$ \mu_j T_{m}\mu_j\ldots T_1\mu_j\to f \quad \textrm{weakly in } L^p,\quad 1 < p < \infty\ . $$
View PDF Chat

Foundational aspects of uncountable measure theory: Gelfand duality, Riesz representation, canonical models, and canonical disintegration

2022-10-10
Asgar Jamneshan , Terence Tao
We collect several foundational results regarding the interaction between locally compact spaces, probability spaces and probability algebras, and commutative $C^*$-algebras and von Neumann algebras equipped with traces, in the “uncountable” … We collect several foundational results regarding the interaction between locally compact spaces, probability spaces and probability algebras, and commutative $C^*$-algebras and von Neumann algebras equipped with traces, in the “uncountable” setting in wh
View PDF Chat

The Hardy–Littlewood–Chowla conjecture in the presence of a Siegel zero

2022-07-11
Terence Tao , Joni Teräväinen
Assuming that Siegel zeros exist, we prove a hybrid version of the Chowla and Hardy–Littlewood prime tuples conjectures. Thus, for an infinite sequence of natural numbers x $x$ , and … Assuming that Siegel zeros exist, we prove a hybrid version of the Chowla and Hardy–Littlewood prime tuples conjectures. Thus, for an infinite sequence of natural numbers x $x$ , and any distinct integers h 1 , ⋯ , h k , h 1 ′ , ⋯ , h ℓ ′ $h_1,\dots ,h_k,h^{\prime }_1,\dots ,h^{\prime }_\ell$ , we establish an asymptotic formula for ∑ n ⩽ x Λ ( n + h 1 ) ⋯ Λ ( n + h k ) λ ( n + h 1 ′ ) ⋯ λ ( n + h ℓ ′ ) \begin{equation*} \hspace*{13pt}\sum _{n\leqslant x}\Lambda (n+h_1)\cdots \Lambda (n+h_k)\lambda (n+h_{1}^{\prime })\cdots \lambda (n+h_{\ell }^{\prime })\hspace*{-13pt} \end{equation*} for any 0 ⩽ k ⩽ 2 $0\leqslant k\leqslant 2$ and ℓ ⩾ 0 $\ell \geqslant 0$ . Specializing to either ℓ = 0 $\ell =0$ or k = 0 $k=0$ , we deduce the previously known results on the Hardy–Littlewood (or twin primes) conjecture and the Chowla conjecture under the existence of Siegel zeros, due to Heath-Brown and Chinis, respectively. The range of validity of our asymptotic formula is wider than in these previous results.
View PDF Chat

Orthogonal polynomials

2022-05-19
T. W. Körner , Terence Tao

Primes in general arithmetical progressions

2022-05-19
T. W. Körner , Terence Tao

Differentiation under the integral

2022-05-19
T. W. Körner , Terence Tao

The isoperimetric problem I

2022-05-19
T. W. Körner , Terence Tao

Mean square approximation I

2022-05-19
T. W. Körner , Terence Tao
Coauthor Papers Together
Ben Green 62
Van Vu 57
Christoph Thiele 40
Camil Muscalu 26
Tamar Ziegler 25
M. Keel 22
J. Colliander 22
T. W. Körner 20
Hideo Takaoka 19
Emmanuel Breuillard 18
Kaisa Matomäki 17
Gigliola Staffilani 17
Joni Teräväinen 17
Maksym Radziwiłł 15
James Wright 13
Emmanuel J. Candès 13
Andreas Seeger 13
Asgar Jamneshan 12
Monica Vişan 12
Allen Knutson 12
Michael Christ 11
Van H. Vu 11
Nets Hawk Katz 11
T. W. Körner 11
Rachel Greenfeld 9
Kevin Ford 9
Ciprian Demeter 8
Igor Rodnianski 7
Izabella Łaba 7
Jonathan Bennett 7
Andrew Hassell 7
Xuancheng Shao 6
Vitaly Bergelson 6
Anthony Carbery 6
Michael T. Lacey 6
Xiaoyi Zhang 6
Freddie Manners 5
Christopher T. Woodward 5
Jill Pipher 5
Or Shalom 5
Sergeĭ Konyagin 4
Dimitris Koukoulopoulos 4
Assaf Naor 4
Jared Wunsch 4
Loukas Grafakos 4
Richard Oberlin 4
Robert M. Guralnick 4
James Maynard 4
Tanja Eisner 4
Tim Austin 4

A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four

1998-07-01
W. T. Gowers

Endpoint Strichartz estimates

1998-10-01
M. Keel , Terence Tao
We prove an abstract Strichartz estimate, which implies previously unknown endpoint Strichartz estimates for the wave equation (in dimension n ≥ 4) and the Schrödinger equation (in dimension n ≥ … We prove an abstract Strichartz estimate, which implies previously unknown endpoint Strichartz estimates for the wave equation (in dimension n ≥ 4) and the Schrödinger equation (in dimension n ≥ 3). Three other applications are discussed: local existence for a nonlinear wave equation; and Strichartz-type estimates for more general dispersive equations and for the kinetic transport equation.
View PDF Chat

The primes contain arbitrarily long arithmetic progressions

2008-03-01
Benjamin Green , Terence Tao
We prove that there are arbitrarily long arithmetic progressions of primes.There are three major ingredients.The first is Szemerédi's theorem, which asserts that any subset of the integers of positive density … We prove that there are arbitrarily long arithmetic progressions of primes.There are three major ingredients.The first is Szemerédi's theorem, which asserts that any subset of the integers of positive density contains progressions of arbitrary length.The second, which is the main new ingredient of this paper, is a certain transference principle.This allows us to deduce from Szemerédi's theorem that any subset of a sufficiently pseudorandom set (or measure) of positive relative density contains progressions of arbitrary length.The third ingredient is a recent result of Goldston and Yıldırım, which we reproduce here.Using this, one may place (a large fraction of) the primes inside a pseudorandom set of "almost primes" (or more precisely, a pseudorandom measure concentrated on almost primes) with positive relative density.
View PDF Chat

Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions

1977-12-01
Harry Furstenberg

A new proof of Szemerédi's theorem

2001-08-15
W. T. Gowers

Linear equations in primes

2010-04-25
Ben Green , Terence Tao
Consider a system ‰ of nonconstant affine-linear forms 1 ; : : : ; t W ‫ޚ‬ d !‫,ޚ‬ no two of which are linearly dependent.Let N be a large … Consider a system ‰ of nonconstant affine-linear forms 1 ; : : : ; t W ‫ޚ‬ d !‫,ޚ‬ no two of which are linearly dependent.Let N be a large integer, and let K Â OE N; N d be convex.A generalisation of a famous and difficult open conjecture of Hardy and Littlewood predicts an asymptotic, as N ! 1, for the number of integer points n 2 ‫ޚ‬ d \ K for which the integers 1 .n/;: : : ; t .n/are simultaneously prime.This implies many other well-known conjectures, such as the twin prime conjecture and the (weak) Goldbach conjecture.It also allows one to count the number of solutions in a convex range to any simultaneous linear system of equations, in which all unknowns are required to be prime.In this paper we (conditionally) verify this asymptotic under the assumption that no two of the affine-linear forms 1 ; : : : ; t are affinely related; this excludes the important "binary" cases such as the twin prime or Goldbach conjectures, but does allow one to count "nondegenerate" configurations such as arithmetic progressions.Our result assumes two families of conjectures, which we term the inverse Gowersnorm conjecture (GI.s/) and the Möbius and nilsequences conjecture (MN.s/),where s 2 f1; 2; : : : g is the complexity of the system and measures the extent to which the forms i depend on each other.The case s D 0 is somewhat degenerate, and follows from the prime number theorem in APs.Roughly speaking, the inverse Gowers-norm conjecture GI.s/ asserts the Gowers U sC1 -norm of a function f W OEN !OE 1; 1 is large if and only if f correlates with an s-step nilsequence, while the Möbius and nilsequences conjecture MN.s/ asserts that the Möbius function is strongly asymptotically orthogonal to s-step nilsequences of a fixed complexity.These conjectures have long been known to be true for s D 1 (essentially by work of Hardy-Littlewood and Vinogradov), and were established for s D 2 in two papers of the authors.Thus our results in the case of complexity s 6 2 are unconditional.In particular we can obtain the expected asymptotics for the number of 4-term progressions p 1 < p 2 < p 3 < p 4 6 N of primes, and more generally for any (nondegenerate) problem involving two linear equations in four prime unknowns.
View PDF Chat

Nonconventional ergodic averages and nilmanifolds

2005-01-01
Bernard Host , Bryna Kra
We study the L 2 -convergence of two types of ergodic averages.The first is the average of a product of functions evaluated at return times along arithmetic progressions, such as … We study the L 2 -convergence of two types of ergodic averages.The first is the average of a product of functions evaluated at return times along arithmetic progressions, such as the expressions appearing in Furstenberg's proof of Szemerédi's theorem.The second average is taken along cubes whose sizes tend to +∞.For each average, we show that it is sufficient to prove the convergence for special systems, the characteristic factors.We build these factors in a general way, independent of the type of the average.To each of these factors we associate a natural group of transformations and give them the structure of a nilmanifold.From the second convergence result we derive a combinatorial interpretation for the arithmetic structure inside a set of integers of positive upper density.* .By Proposition 3.4, this set depends only on the first coordinate.This means that there exists a subset B of X with X × A = B × X [k] * , up to a subset of X [k] of µ [k] -measure zero.That is, 1 A (x) = 1 B (x 0 ) for µ [k] -almost every x = (x 0 , x) ∈ X [k] .(12)
View PDF Chat

A bilinear approach to the restriction and Kakeya conjectures

1998-01-01
Terence Tao , Ana Vargas , Luis Vega
Bilinear restriction estimates have appeared in work of Bourgain, Klainerman, and Machedon. In this paper we develop the theory of these estimates (together with the analogues for Kakeya estimates). As … Bilinear restriction estimates have appeared in work of Bourgain, Klainerman, and Machedon. In this paper we develop the theory of these estimates (together with the analogues for Kakeya estimates). As a consequence we improve the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper L Superscript p Baseline comma upper L Superscript p Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(L^p,L^p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> spherical restriction theorem of Wolff from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p greater-than 42 slash 11"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>42</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>11</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p &gt; 42/11</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p greater-than 34 slash 9"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>34</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>9</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p &gt; 34/9</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and also obtain a sharp <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper L Superscript p Baseline comma upper L Superscript q Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>q</mml:mi> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(L^p,L^q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> spherical restriction theorem for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q greater-than 4 minus five twenty-sevenths"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>4</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mfrac> <mml:mn>5</mml:mn> <mml:mn>27</mml:mn> </mml:mfrac> </mml:mrow> <mml:annotation encoding="application/x-tex">q&gt; 4 - \frac {5}{27}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

2008-02-01
Ben Green , Terence Tao
Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool … Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool in these developments has been the sequence of Gowers uniformity norms $U^d(G)$, $d=1,2,3,\dots$, on a finite additive group $G$; in particular, to detect arithmetic progressions of length $k$ in $G$ it is important to know under what circumstances the $U^{k-1}(G)$ norm can be large. The $U^1(G)$ norm is trivial, and the $U^2(G)$ norm can be easily described in terms of the Fourier transform. In this paper we systematically study the $U^3(G)$ norm, defined for any function $f:G\to\mathbb{C}$ on a finite additive group $G$ by the formula \begin{multline*} \qquad\|f\|_{U^3(G)}:=|G|^{-4}\sum_{x,a,b,c\in G}(f(x)\overline{f(x+a)f(x+b)f(x+c)}f(x+a+b) \\ \times f(x+b+c)f(x+c+a)\overline{f(x+a+b+c)})^{1/8}.\qquad \end{multline*} We give an inverse theorem for the $U^3(G)$ norm on an arbitrary group $G$. In the finite-field case $G=\mathbb{F}_5^n$ we show that a bounded function $f:G\to\mathbb{C}$ has large $U^3(G)$ norm if and only if it has a large inner product with a function $e(\phi)$, where $e(x):=\mathrm{e}^{2\pi\ri x}$ and $\phi:\mathbb{F}_5^n\to\mathbb{R}/\mathbb{Z}$ is a quadratic phase function. In a general $G$ the statement is more complicated: the phase $\phi$ is quadratic only locally on a Bohr neighbourhood in $G$. As an application we extend Gowers's proof of Szemerédi's theorem for progressions of length four to arbitrary abelian $G$. More precisely, writing $r_4(G)$ for the size of the largest $A\subseteq G$ which does not contain a progression of length four, we prove that $$ r_4(G)\ll|G|(\log\log|G|)^{-c}, $$ where $c$ is an absolute constant. We also discuss links between our ideas and recent results of Host, Kra and Ziegler in ergodic theory. In future papers we will apply variants of our inverse theorems to obtain an asymptotic for the number of quadruples $p_1\ltp_2\ltp_3\ltp_4\leq N$ of primes in arithmetic progression, and to obtain significantly stronger bounds for $r_4(G)$.
View PDF Chat

Fourier transform restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations

1993-05-01
Jean Bourgain

Universal characteristic factors and Furstenberg averages

2006-03-17
Tamar Ziegler
Let X=(X^0,\mu,T) be an ergodic measure preserving system. For a natural number k we consider the averages (*) 1/N \sum_{n=1}^N \prod_{j=1}^k f_j(T^{n a_j}x) where the functions f_j are bounded, and … Let X=(X^0,\mu,T) be an ergodic measure preserving system. For a natural number k we consider the averages (*) 1/N \sum_{n=1}^N \prod_{j=1}^k f_j(T^{n a_j}x) where the functions f_j are bounded, and a_j are integers. A factor of X is characteristic for averaging schemes of length k (or k-characteristic) if for any non zero distinct integers a_1,...,a_k, the limiting L^2(\mu) behavior of the averages in (*) is unaltered if we first project the functions f_j onto the factor. A factor of X is a k-universal characteristic factor (k-u.c.f)} if it is a k-characteristic factor, and a factor of any k-characteristic factor. We show that there exists a unique k-u.c.f, and it has a structure of a (k-1)-step nilsystem, more specifically an inverse limit of (k-1)-step nilflows. Using this we show that the averages in (*) converge in L^2(\mu). This provides an alternative proof to the one given by Host and Kra in 2002.
View PDF Chat

On Triples in Arithmetic Progression

1999-12-01
Jean Bourgain

Besicovitch type maximal operators and applications to fourier analysis

1991-06-01
Jean Bourgain

On sets of integers containing k elements in arithmetic progression

1975-01-01
Endre Szemerédi
View PDF Chat

Space‐time estimates for null forms and the local existence theorem

1993-10-01
Sergiù Klainerman , Matei Machedon

Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes

1923-01-01
G. H. Hardy , J. E. Littlewood
z.I.It was asserted by GOLDBACH, in a letter to "EuLER dated 7 June, 1742 , that every even number 2m is the sum o/two odd primes, ai~d this propos ition … z.I.It was asserted by GOLDBACH, in a letter to "EuLER dated 7 June, 1742 , that every even number 2m is the sum o/two odd primes, ai~d this propos ition has generally been described as 'Goldbach's Theorem'.There is no reasonable doubt that the theorem is correct, and that the number of representations is large when m is large; but all attempts to obtain a proof have been completely unsuccessful.Indeed it has never been shown that every number (or every large number, any number, that is to say, from a certain point onwards) is the sum of xo primes, or of i oooooo; and the problem was quite recently classified as among those 'beim gegenwiirtigen Stande der Wissensehaft unangreifbar'.~In this memoir we attack the problem with the aid of our new transcendental method in 'additiver Zahlentheorie'.~ We do not solve it: we do not
View PDF Chat

On Certain Sets of Integers

1953-01-01
K. F. Roth

Recurrence in Ergodic Theory and Combinatorial Number Theory

1981-12-31
Harry Furstenberg
Topological dynamics and ergodic theory usually have been treated independently. H. Furstenberg, instead, develops the common ground between them by applying the modern theory of dynamical systems to combinatories and … Topological dynamics and ergodic theory usually have been treated independently. H. Furstenberg, instead, develops the common ground between them by applying the modern theory of dynamical systems to combinatories and number theory. Originally published in 1981. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

A statistical theorem of set addition

1994-09-01
Antal Balog , Endre Szemer�di

Freiman's theorem in an arbitrary abelian group

2007-01-29
Ben Green , Imre Z. Ruzsa
A famous result of Freiman describes the structure of finite sets A ⊆ ℤ with small doubling property. If |A + A| ⩽ K|A|, then A is contained within a … A famous result of Freiman describes the structure of finite sets A ⊆ ℤ with small doubling property. If |A + A| ⩽ K|A|, then A is contained within a multidimensional arithmetic progression of dimension d(K) and size f(K)|A|. Here we prove an analogous statement valid for subsets of an arbitrary abelian group.
View PDF Chat

On the Dimension of Kakeya Sets and Related Maximal Inequalities

1999-06-01
Jean Bourgain

The quantitative behaviour of polynomial orbits on nilmanifolds

2012-01-31
Ben Green , Terence Tao
A theorem of Leibman asserts that a polynomial orbit (g(n)Γ) n∈Z on a nilmanifold G/Γ is always equidistributed in a union of closed subnilmanifolds of G/Γ.In this paper we give … A theorem of Leibman asserts that a polynomial orbit (g(n)Γ) n∈Z on a nilmanifold G/Γ is always equidistributed in a union of closed subnilmanifolds of G/Γ.In this paper we give a quantitative version of Leibman's result, describing the uniform distribution properties of a finite polynomial orbit (g(n)Γ) n∈[N ] in a nilmanifold.More specifically we show that there is a factorisation g = εg γ, where ε(n) is "smooth," (γ(n)Γ) n∈Z is periodic and "rational," and (g (n)Γ)n∈P is uniformly distributed (up to a specified error δ) inside some subnilmanifold G /Γ of G/Γ for all sufficiently dense arithmetic progressions P ⊆ [N ].Our bounds are uniform in N and are polynomial in the error tolerance δ.
View PDF Chat

On Certain Sets of Positive Density

1959-07-01
P. Varnavides

L p Estimates on the Bilinear Hilbert Transform for 2 &lt; p &lt; &amp;#8734

1997-11-01
Michael T. Lacey , Christoph Thiele

Nonlinear Dispersive Equations

2006-06-08
Terence Tao
Ordinary differential equations Constant coefficient linear dispersive equations Semilinear dispersive equations The Korteweg de Vries equation Energy-critical semilinear dispersive equations Wave maps Tools from harmonic analysis Construction of ground states … Ordinary differential equations Constant coefficient linear dispersive equations Semilinear dispersive equations The Korteweg de Vries equation Energy-critical semilinear dispersive equations Wave maps Tools from harmonic analysis Construction of ground states Bibliography.

Applications of the regularity lemma for uniform hypergraphs

2006-03-01
Vojtěch Rödl , Jozef Skokan
In this article we discuss several combinatorial problems that can be addressed by the Regularity Method for hypergraphs. Based on the recent results of Nagle, Schacht, and the authors, we … In this article we discuss several combinatorial problems that can be addressed by the Regularity Method for hypergraphs. Based on the recent results of Nagle, Schacht, and the authors, we give here solutions to these problems.In particular, we prove the following: Let F be a k-uniform hypergraph on t vertices and suppose an n-vertex k-uniform hypergraph H contains only o(nt) copies of F. Then one can delete o(nk) edges of H to make it F-free.Similar results were recently obtained by W. T. Gowers. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006

Spectral Analysis of Large Dimensional Random Matrices

2009-12-09
Zhidong Bai , Jack W. Silverstein
View PDF Chat

Multilinear weighted convolution of L 2 functions, and applications to nonlinear dispersive equations

2001-10-01
Terence Tao
The X s,b spaces, as used by Beals, Bourgain, Kenig-Ponce-Vega, Klainerman-Machedon and others, are fundamental tools to study the low-regularity behavior of nonlinear dispersive equations. It is of particular interest … The X s,b spaces, as used by Beals, Bourgain, Kenig-Ponce-Vega, Klainerman-Machedon and others, are fundamental tools to study the low-regularity behavior of nonlinear dispersive equations. It is of particular interest to obtain bilinear or multilinear estimates involving these spaces. By Plancherel's theorem and duality, these estimates reduce to estimating a weighted convolution integral in terms of the L 2 norms of the component functions. In this paper we systematically study weighted convolution estimates on L 2 . As a consequence we obtain sharp bilinear estimates for the KdV, wave, and Schrödinger X s,b spaces.
View PDF Chat

On the probability that a random ±1-matrix is singular

1995-01-01
Jeff Kahn , János Komlós , Endre Szemerédi
We report some progress on the old problem of estimating the probability, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> … We report some progress on the old problem of estimating the probability, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, that a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n \pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-matrix is singular: <bold>Theorem</bold>. <italic>There is a positive constant</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi>ε<!-- ε --></mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <italic>for which</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline greater-than left-parenthesis 1 minus epsilon right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>ε<!-- ε --></mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} &gt; {(1 - \varepsilon )^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This is a considerable improvement on the best previous bound, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals upper O left-parenthesis 1 slash StartRoot n EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = O(1/\sqrt n )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, given by Komlós in 1977, but still falls short of the often-conjectured asymptotical formula <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals left-parenthesis 1 plus o left-parenthesis 1 right-parenthesis right-parenthesis n squared 2 Superscript 1 minus n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = (1 + o(1)){n^2}{2^{1 - n}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The proof combines ideas from combinatorial number theory, Fourier analysis and combinatorics, and some probabilistic constructions. A key ingredient, based on a Fourier-analytic idea of Halász, is an inequality (Theorem 2) relating the probability that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a underbar element-of bold upper R Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>a</mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">R</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline a \in {{\mathbf {R}}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is orthogonal to a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar element-of left-brace plus-or-minus 1 right-brace Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline \varepsilon \in {\{ \pm 1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to the corresponding probability when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar"> <mml:semantics> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:annotation encoding="application/x-tex">\underline \varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is random from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-brace negative 1 comma 0 comma 1 right-brace Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\{ - 1,0,1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P r left-parenthesis epsilon Subscript i Baseline equals negative 1 right-parenthesis equals upper P r left-parenthesis epsilon Subscript i Baseline equals 1 right-parenthesis equals p"> <mml:semantics> <mml:mrow> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">Pr({\varepsilon _i} = - 1) = Pr({\varepsilon _i} = 1) = p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon Subscript i"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\varepsilon _i}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>’s chosen independently.
View PDF Chat

A variant of the hypergraph removal lemma

2006-01-11
Terence Tao
View PDF Chat

Multiple recurrence and nilsequences

2005-02-28
Vitaly Bergelson , Bernard Host , Bryna Kra +1 more
View PDF Chat

On random ±1 matrices: Singularity and determinant

2006-01-01
Terence Tao , Van Vu
This papers contains two results concerning random n × n Bernoulli matrices. First, we show that with probability tending to 1 the determinant has absolute value $\sqrt{n!}\exp(O(\sqrt{n \ln n}))$. Next, … This papers contains two results concerning random n × n Bernoulli matrices. First, we show that with probability tending to 1 the determinant has absolute value $\sqrt{n!}\exp(O(\sqrt{n \ln n}))$. Next, we prove a new upper bound 0.958n on the probability that the matrix is singular.© 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006

A Quantitative Ergodic Theory Proof of Szemerédi's Theorem

2006-11-06
Terence Tao
A famous theorem of Szemerédi asserts that given any density $0 &lt; \delta \leq 1$ and any integer $k \geq 3$, any set of integers with density $\delta$ will contain … A famous theorem of Szemerédi asserts that given any density $0 &lt; \delta \leq 1$ and any integer $k \geq 3$, any set of integers with density $\delta$ will contain infinitely many proper arithmetic progressions of length $k$. For general $k$ there are essentially four known proofs of this fact; Szemerédi's original combinatorial proof using the Szemerédi regularity lemma and van der Waerden's theorem, Furstenberg's proof using ergodic theory, Gowers' proof using Fourier analysis and the inverse theory of additive combinatorics, and the more recent proofs of Gowers and Rödl-Skokan using a hypergraph regularity lemma. Of these four, the ergodic theory proof is arguably the shortest, but also the least elementary, requiring passage (via the Furstenberg correspondence principle) to an infinitary measure preserving system, and then decomposing a general ergodic system relative to a tower of compact extensions. Here we present a quantitative, self-contained version of this ergodic theory proof, and which is "elementary" in the sense that it does not require the axiom of choice, the use of infinite sets or measures, or the use of the Fourier transform or inverse theorems from additive combinatorics. It also gives explicit (but extremely poor) quantitative bounds.
View PDF Chat

The cauchy problem for the critical nonlinear Schrödinger equation in Hs

1990-01-01
Thierry Cazenave , Fred B. Weissler

On the asymptotic behavior of large radial data for a focusing non-linear Schrödinger equation

2004-01-01
Terence Tao
We study the asymptotic behavior of large data radial solutions to the focusing Schrödinger equation iut +∆u = -|u| 2 u in R 3 , assuming globally bounded H 1 … We study the asymptotic behavior of large data radial solutions to the focusing Schrödinger equation iut +∆u = -|u| 2 u in R 3 , assuming globally bounded H 1 (R 3 ) norm (i.e.no blowup in the energy space).We show that as t → ±∞, these solutions split into the sum of three terms: a radiation term that evolves according to the linear Schrödinger equation, a smooth function localized near the origin, and an error that goes to zero in the Ḣ1 (R 3 ) norm.Furthermore, the smooth function near the origin is either zero (in which case one has scattering to a free solution), or has mass and energy bounded strictly away from zero, and obeys an asymptotic Pohozaev identity.These results are consistent with the conjecture of soliton resolution.
View PDF Chat

Pointwise Convergence of Fourier Series

1973-11-01
Charles Fefferman
In this paper, we present a new proof of a theorem of Carleson and Hunt: The Fourier series of an LP function on [0, 2J] converges almost everywhere (p > … In this paper, we present a new proof of a theorem of Carleson and Hunt: The Fourier series of an LP function on [0, 2J] converges almost everywhere (p > 1). (See [1], [51.) Our proof is very much in the spirit of the classical theorem of Kolmogoroff-Seliverstoff-Plessner [8]. Unlike Carleson's proof, which makes a careful analysis of the structure of an L2 function f, our arguments essentially ignore f, and concentrate instead on building up a basic partial sum operator from simpler pieces. Our methods are (almost) entirely L2. Sections 1-7 of this paper contain a proof of pointwise convergence for L2 functions; Section 8 contains the modifications necessary to handle LP, and includes various further comments.

An improved bound for Kakeya type maximal functions

1995-12-31
Thomas Wolff
The purpose of this paper is to improve the known results (specifically [1]) concerning Lp boundedness of maximal functions formed using 1 x d x ... x d tubes. The purpose of this paper is to improve the known results (specifically [1]) concerning Lp boundedness of maximal functions formed using 1 x d x ... x d tubes.
View PDF Chat

Recent work connected with the Kakeya problem

2003-09-17
Thomas Wolff
where Sn−1 is the unit sphere in R. This paper will be mainly concerned with the following issue, which is still poorly understood: what metric restrictions does the property (1) … where Sn−1 is the unit sphere in R. This paper will be mainly concerned with the following issue, which is still poorly understood: what metric restrictions does the property (1) put on the set E? The original Kakeya problem was essentially whether a Kakeya set as defined above must have positive measure, and as is well-known, a counterexample was given by Besicovitch in 1920. A current form of the problem is as follows:
View PDF Chat

Multi-linear operators given by singular multipliers

2001-12-10
Camil Muscalu , Terence Tao , Christoph Thiele
We prove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Superscript p"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">L^p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> estimates for a large class of multi-linear operators, which includes … We prove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Superscript p"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">L^p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> estimates for a large class of multi-linear operators, which includes the multi-linear paraproducts studied by Coifman and Meyer (1991), as well as the bilinear Hilbert transform and other operators with large groups of modulation symmetries.

Regularity Lemma for k‐uniform hypergraphs

2004-06-09
Vojtěch Rödl , Jozef Skokan
Abstract Szemerédi's Regularity Lemma proved to be a very powerful tool in extremal graph theory with a large number of applications. Chung [Regularity lemmas for hypergraphs and quasi‐randomness, Random Structures … Abstract Szemerédi's Regularity Lemma proved to be a very powerful tool in extremal graph theory with a large number of applications. Chung [Regularity lemmas for hypergraphs and quasi‐randomness, Random Structures Algorithms 2 (1991), 241–252], Frankl and Rödl [The uniformity lemma for hypergraphs, Graphs Combin 8 (1992), 309–312; Extremal problems on set systems, Random Structures Algorithms 20 (2002), 131–164] considered several extensions of Szemerédi's Regularity Lemma to hypergraphs. In particular, [Extremal problems on set systems, Random Structures Algorithms 20 (2002), 131–164] contains a regularity lemma for 3‐uniform hypergraphs that was applied to a number of problems. In this paper, we present a generalization of this regularity lemma to k ‐uniform hypergraphs. Similar results were recently independently and alternatively obtained by W. T. Gowers. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

Generalized arithmetical progressions and sumsets

1994-12-01
Imre Z. Ruzsa

Well‐posedness and scattering results for the generalized korteweg‐de vries equation via the contraction principle

1993-04-01
Carlos E. Kenig , Gustavo Ponce , Luis Vega

Wegner Estimate and Level Repulsion for Wigner Random Matrices

2009-08-29
László Erdős , Benjamin Schlein , Horng‐Tzer Yau
We consider N × N Hermitian random matrices with independent identically distributed entries (Wigner matrices). The matrices are normalized so that the average spacing between consecutive eigenvalues is of order … We consider N × N Hermitian random matrices with independent identically distributed entries (Wigner matrices). The matrices are normalized so that the average spacing between consecutive eigenvalues is of order 1/ N. Under suitable assumptions on the distribution of the single matrix element, we first prove that, away from the spectral edges, the empirical density of eigenvalues concentrates around the Wigner semicircle law on energy scales η ≫ N−1. This result establishes the semicircle law on the optimal scale and it removes a logarithmic factor from our previous result [6]. We then show a Wegner estimate, i.e., that the averaged density of states is bounded. Finally, we prove that the eigenvalues of a Wigner matrix repel each other, in agreement with the universality conjecture.
View PDF Chat

The Bochner-Riesz conjecture implies the restriction conjecture

1999-02-01
Terence Tao

On Calderon's Conjecture

1999-03-01
Michael T. Lacey , Christoph Thiele
with constants Cfi;p1;p2 depending only on fi;p1;p2 and p := p1p2 p1+p2 hold. The flrst result of this type is proved in [4], and the purpose of the current paper … with constants Cfi;p1;p2 depending only on fi;p1;p2 and p := p1p2 p1+p2 hold. The flrst result of this type is proved in [4], and the purpose of the current paper is to extend the range of exponents p1 and p2 for which (2) is known. In particular, the case p1 =2 ,p2 = 1 is solved to the a‐rmative. This was

Groups of polynomial growth and expanding maps

1981-12-01
Mikhael Gromov

Some Maximal Inequalities

1971-01-01
Charles Fefferman , E. M. Stein

The Concentration of Measure Phenomenon

2005-02-14
Michel Ledoux
Concentration functions and inequalities Isoperimetric and functional examples Concentration and geometry Concentration in product spaces Entropy and concentration Transportation cost inequalities Sharp bounds of Gaussian and empirical processes Selected applications … Concentration functions and inequalities Isoperimetric and functional examples Concentration and geometry Concentration in product spaces Entropy and concentration Transportation cost inequalities Sharp bounds of Gaussian and empirical processes Selected applications References Index.
View PDF Chat

The counting lemma for regular k-uniform hypergraphs

2006-03-01
Brendan Nagle , Vojtěch Rödl , Mathias Schacht
Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory. Many of its applications are based on its accompanying Counting Lemma: If G is … Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory. Many of its applications are based on its accompanying Counting Lemma: If G is an e-partite graph with V (G) = V1 ∪ … ∪ Ve and sVis = n for all i ∈ [e], and all pairs (Vi, Vj) are e-regular of density d for 1 ≤ i ≤ j ≤ e and e L d, then G contains $(1\pm f_{\ell}(\varepsilon))d^{\ell \choose 2}\times n^{\ell}$ cliques Ke, where fe(e) → 0 as e → 0.Recently, Rodl and Skokan generalized Szemeredi's Regularity Lemma from graphs to k-uniform hypergraphs for arbitrary k ≥ 2. In this paper we prove a Counting Lemma accompanying the Rodl–Skokan hypergraph Regularity Lemma. Similar results were independently obtained by Gowers.Such results give combinatorial proofs to the density result of Szemeredi and some of the density theorems of Furstenberg and Katznelson. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006

Low-degree tests at large distances

2007-06-11
Alex Samorodnitsky
We define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. The tests have optimal … We define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. The tests have optimal or nearly optimal trade-offs between soundness and the number of queries.
View PDF Chat