Theorems List

This page contains list of mathematical Theorems which are at the same time (a) great, (b) easy to understand, and (c) published in the 21st century. See here for more details about these criteria. Click on any theorem to see the exact formulation, or click here for the formulations of all theorems. You can also view theorems by broad subject category: combinatorics, number theory, analysis, algebra, geometry and topology, logic and foundations, probability and statistics, mathematics of computation, and applications of mathematics.

On this page, the theorems are sorted by submission date (to arxiv or journal, whichever is first), not in the order added to the website. Also, you can download the excel document with the full list of Theorems, where you can search, sort, and filter them by date, paper title, author, journal, or subject category.

The website covers Theorems in the period 2001-2020. From 2021, I stopped updating the website. Instead, I wrote book “Landscape of 21st Century Mathematics” that collects all these theorems by topics and, for many Theorems, provides more details and context. The book is published by Springer in 2021, see here .

Theorems submitted in 2020

29.09.2020 MIP*=RE

07.07.2020 The size of A\subset \{1,...,N\} without 3-term progressions is O\left(\frac{N}{\log^{1+c} N}\right), \, c>0

02.07.2020 Approximation ratio 3/2 for the metric TSP is not optimal

13.03.2020 For every Banach space, its Rademacher type and Enflo type coincide

Theorems submitted in 2019

28.12.2019 The Schinzel-Zassenhaus conjecture on integer polynomials is true

08.09.2019 Almost all orbits of the Collatz map attain almost bounded values

01.09.2019 Size of A\subset [N] without distincts degree polynomial progressions is \leq\frac{N}{(\log\log N)^c}

25.08.2019 Hyperbolic motions of any shape exist in the Newtonian N-body problem

31.07.2019 There are at most B_n X^{C\log^3 n} degree n number fields with discriminant \leq X

22.07.2019 Flat Littlewood polynomials exist

10.07.2019 The Duffin–Schaeffer conjecture is true

01.07.2019 The Sensitivity Conjecture is true

27.06.2019 Chromatic number of G(n,\frac{1}{2}) is not concentrated on n^{\frac{1}{4}-\epsilon} consecutive values

06.05.2019 The Hedetniemi’s conjecture is false: \exists G, H \,:\,\chi(G \times H) < \min\{\chi(G), \chi(H)\}

18.03.2019 n-digit integers can be multiplied in O(n\log n) operations

04.03.2019 Explicit examples of degree N polynomials with condition numbers O(\sqrt{N})

12.02.2019 All but finitely many of degree-d Jensen polynomials for \zeta(s) are hyperbolic

01.02.2019 The number of n-faces genus-g triangulations if g/n converges to a constant

Theorems submitted in 2018

21.12.2018 Random Bernoulli n\times n matrix is singular with probability \left(\frac{1}{2}+o(1)\right)^n

08.12.2018 A universally measurable Polish groups homomorphism is continuous

04.12.2018 Local Fourier uniformity conjecture is true for s=1 at scale X^\theta

19.11.2018 The Szemerédi–Trotter estimate holds for hypersurfaces in {\mathbb R}^d

11.11.2018 There exist full-sized groups that are profinitely rigid in the absolute sense

06.11.2018 The Weyl-type bound holds for Dirichlet L-functions of cube-free conductor

05.11.2018 Mason’s ultra-log-concavity conjecture for matroids independent sets is true

30.10.2018 The group of boundary fixing disk homeomorphisms is not left-orderable

21.10.2018 Bernoulli convolution \nu_\lambda has dimension 1 for all transcendental \lambda \in (1/2,1)

25.09.2018 K_{d,d} maximises the normalised number of q-colorings over d-regular graphs

18.09.2018 There is a one-relator inverse monoid with undecidable word problem

28.08.2018 If E\subset {\mathbb R}^2 is compact, \text{dim}(E)>\frac{5}{4}, then set \{|x-y|\}_{x,y\in E} has positive measure

14.08.2018 Probabilistic Waring problem for finite simple groups has positive solution

08.08.2018 The Conway knot is not slice

17.07.2018 There exist finitely generated infinite simple left orderable groups

31.05.2018 There exists an oracle A relative to which \text{BQP}^A \not\subseteq \text{PH}^A

10.04.2018 The u-invariant of any field of transcendence degree 2 over {\mathbb R} is at most 4

08.04.2018 The chromatic number of the plane is at least 5

01.03.2018 Every A\subset {\mathbb N} with positive density contains B+C for some infinite B,C\subset {\mathbb N}

25.02.2018 The volume exponent of the first Grigorchuk group is equal to \alpha_0=0.7674...

06.02.2018 The hot spots conjecture is true for all triangles in the plane

03.02.2018 There exist lattices with exponentially large kissing numbers

22.01.2018 The k=2 case of the Pólya conjecture for the Neumann eigenvalues is true

18.01.2018 The De Bruijn-Newman constant is non-negative

10.01.2018 The 2-to-2-Games Conjecture with imperfect completeness is true

02.01.2018 The set of non-weakly mixing IETs has Hausdorff codimension at most 1/2

Theorems submitted in 2017

22.12.2017 The Julia set of the Feigenbaum polynomial has zero Lebesgue measure

22.12.2017 The Strassen’s direct sum conjecture is false

19.12.2017 Typical 1-Lipschitz image of a purely n-unrectiable set in {\mathbb R}^k has H^n measure 0

02.12.2017 The h^*-bound for the min number of K_3 in (n,e)-graph is tight if e\leq {{n}\choose{2}}-\epsilon n^2

09.11.2017 Systems of polynomial equations can be solved in expected quasilinear time

07.11.2017 The Benjamini-Schramm conjecture is true for nonunimodular graphs

04.09.2017 If k large, p prime, \text{gcd}(n,d)=1, and \prod\limits_{i=0}^{k-1}(n+id)=y^p, then yd=0 or p\leq \exp(10^k)

02.08.2017 The Liouville function has super-linear block growth

01.08.2017 There are fifteen types of convex pentagons that can tile the plane

18.05.2017 There is no coarsely minimal infinite-dimensional Banach space

15.05.2017 There are \sim C_pN^{2p-4} meanders with at most 2N crossings and p minimal arcs

08.05.2017 A version of the OSSS inequality holds for monotonic probability measures

24.04.2017 Every Besicovitch set in {\mathbb R}^3 has dimension at least \frac{5}{2}+\epsilon _0 for some \epsilon _0>0

20.03.2017 For Steinhaus random multiplicative function f, {\mathbb E}\left|\sum\limits_{n\leq x}f(n)\right|\sim\frac{\sqrt{x}}{(\log \log x)^{1/4}}

08.03.2017 The Dichotomy conjecture is true: every CSP is either in P or is NP-complete

08.02.2017 The set of congruent numbers equal to 1, 2, or 3 mod 8 has density zero

10.01.2017 Elliptic curve with discriminant \Delta has at most O_\epsilon(|\Delta|^{0.1117...+\epsilon}) integer points

03.01.2017 Vertical vs horizontal isoperimetric inequality holds in Heisenberg groups

01.01.2017 Schwartz functions on the real line have explicit Fourier interpolation

Theorems submitted in 2016

17.12.2016 For Lagrange spectrum L, \text{dim}(L \cap (-\infty, t)) may assume any value in [0,1]

17.12.2016 Tarski’s circle squaring problem has a constructive solution

13.10.2016 There is no Diophantine quintuple

05.10.2016 The elliptic Harnack inequality on a graph is stable under rough isometries

25.09.2016 The Furstenberg’s conjecture on the intersections of invariant sets is true

12.08.2016 The Pomerance conjecture is true: the threshold for making squares is sharp

21.06.2016 For all n\geq n_\theta, there are at most 2n-2 lines in {\mathbb R}^n with common angle \theta

30.05.2016 The cap set conjecture is true: if A \subseteq {\mathbb F}_3^n is a cap set, then |A|=o(2.756^n)

09.05.2016 The Nadirashvili’s conjecture is true

09.05.2016 A properly embedded minimal surface of genus g has \infty or at most C_g ends

05.05.2016 Progression-free sets in {\mathbb Z}_4^n are exponentially small

04.05.2016 The family \{x,xy,x+y\} is Ramsey

03.05.2016 The boolean Pythagorean Triples problem has a positive answer

29.04.2016 Upper bound 2^{n+o(n)} holds in the Erdős-Szekeres “Happy Ending” conjecture

13.04.2016 There exists a discrete bounded envy-free cake cutting protocol for n agents

04.04.2016 For any digit d, infinitely many primes have no d in their decimal expansion

25.03.2016 The primes contain arbitrarily long multivariate polynomial progressions

21.03.2016 The highest sphere packing density in {\mathbb R}^{24} is \frac{\pi^{12}}{12!}

20.03.2016 The Markoff-Hurwitz equation has (c+o(1))(\log R)^\beta integer solutions up to R

14.03.2016 The highest sphere packing density in {\mathbb R}^8 is \frac{\pi^4}{384}

14.03.2016 The restriction conjecture for paraboloids is true for p>2\frac{3n+1}{3n-3}, n\geq 2

16.02.2016 For all irrational \alpha, one has \liminf\limits_{n\to\infty}\max\limits_{|z|=1}\prod\limits_{k=1}^n\left|z-e^{2\pi i k \alpha}\right|<\infty

31.01.2016 Bernoulli convolution is absolutely continuous for \lambda=1-10^{-50} and \frac{1}{4}\leq p \leq \frac{3}{4}

13.01.2016 If 2<q<p, the maximal \theta for which \theta-snowflake of L_q embeds into L_p is \theta=\frac{q}{p}

08.01.2016 Any finite subgroup of \text{GL}_n({\mathbb C}) has a semi-invariant of degree at most Cn

06.01.2016 There exist finitely generated simple groups of intermediate growth

Theorems submitted in 2015

18.12.2015 All Robbin’s conjectures on the number of ASMs with symmetries are true

11.12.2015 The graph isomorphism problem can be solved in quasipolynomial time

04.12.2015 The main conjecture in Vinogradov’s Mean Value Theorem is true

09.11.2015 Rota’s and Mason’s log-concavity conjectures are true for all matroids

27.10.2015 Amir’s conjecture for random walks on groups is true

17.09.2015 The discrepancy \sup\limits_{n,d\in{\mathbb N}}\left|\sum\limits_{j=1}^n f(jd)\right| of any f:{\mathbb N}\to\{-1,+1\} is infinite

17.09.2015 The logarithmically averaged Chowla conjecture is true for k=2

17.07.2015 For any non-square a, x^4-ay^4+4axy^2z-2ax^2z^2+a^2z^4 is prime infinitely often

14.06.2015 An explicit construction of a 2^{(\log \log n)^c}-Ramsey graph over n vertices

18.05.2015 The Ramsey number of any n-vertex d-degenerate graph is at most c_dn

01.05.2015 If N=p^aq^b, map (x,y)\to x^Ny^N is surjective on finite non-abelian simple groups

01.02.2015 The topological Tverberg conjecture is false

25.01.2015 Tarski’s circle squaring problem can be solved with only measurable pieces

19.01.2015 Short and long averages of a multiplicative function are effectively related

Theorems submitted in 2014

16.12.2014 Let G(X)=\sup\limits_{p_n \leq X}(p_{n+1}-p_n). Then G(X)\geq c\frac{\log X \log \log X \log \log \log \log X}{\log \log \log X} for some c>0

17.11.2014 A compact, embedded self-similar shrinker in {\mathbb R}^3 of genus 0 is a round sphere

13.10.2014 Characterisation of polyhedral types inscribed in the hyperboloid or cylinder

29.08.2014 Non-collision singularities exist in a planar Newtonian 4-body problem

25.08.2014 If 2<q<p, and the \theta-snowflake of L_q embeds into L_p, then \theta \leq 1-\frac{(p-q)(q-2)}{2p^3}

20.08.2014 Let G(X)=\sup\limits_{p_n \leq X}(p_{n+1}-p_n). Then \lim\limits_{X\to\infty} G(X)\frac{(\log \log \log X)^2}{\log X \log \log X \log \log \log \log X}=\infty

05.08.2014 The Gaussian correlation conjecture is true

10.07.2014 The set of points in a rational polygon P not illuminated by any x\in P is finite

19.06.2014 There exist coarsely non-amenable group that is coarsely embeddable into l^2

17.04.2014 Fast (1-1/e-\epsilon)-approximation for the infuence maximization problem

11.03.2014 There exist 1-dependent 4-colouring and 2-dependent 3-colouring of {\mathbb Z}

04.03.2014 If a, b, c, a+b are squares, then equation ax^2 + by^2 = c\lambda^2 is partition regular

15.01.2014 The existence conjecture for combinatorial designs is true

Theorems submitted in 2013

30.12.2013 Every odd integer n>5 is the sum of three primes

16.12.2013 Every point in an nd-polytope is the barycenter of n points in its d-faces

19.11.2013 For any k, p_{n+k}-p_n\leq C_k infinitely often, where p_n is the n-th prime

11.11.2013 The perfect matching polytope has exponential extension complexity

01.11.2013 No algorithm can decide if a finitely presented group has a finite quotient

17.10.2013 Replica prediction holds for independence ratio in random regular graphs

12.09.2013 Integer superharmonic matrices have the Apollonian structure

02.07.2013 The least modulus of a distinct covering system is at most 10^{16}

20.06.2013 Properly embedded genus-g minimal surfaces with one end exist for all g

17.06.2013 The Kadison-Singer problem has a positive solution

20.05.2013 For any C, not every finite metric space of negative type C-embeds into l^1

07.05.2013 Finitely many rotations of any pyjama stripe can cover the plane

25.04.2013 For any finite S\subset {\mathbb R}^n, there exists a quasiregular map from {\mathbb R}^n onto {\mathbb R}^n \setminus S

25.04.2013 The converse to the Rademacher theorem holds if and only if m\geq n

17.04.2013 p_{n+1}-p_n < 7\cdot 10^7 infinitely often, where p_n is the n-th prime

15.04.2013 There exist regular bipartite Ramanujan graphs of every degree d\geq 3

04.04.2013 There exist nontrivial q-Steiner systems with t\geq 2

02.04.2013 Multidimensional generalisation of the Schmidt conjecture is true

10.03.2013 The Triangulation Conjecture is false in all dimensions n\geq 5

01.02.2013 Most odd degree hyperelliptic curves have no finite rational points

01.02.2013 (236 c)^{11} Reidemeister moves turn a c-crossing unknot diagram into trivial one

19.01.2013 For every \epsilon>0, exists set of n integers with no sum-free subset of size \left(\frac{1}{3}+\epsilon\right)n

Theorems submitted in 2012

09.12.2012 Bernoulli convolution \nu_\lambda has dimension 1 outside a set of \lambda of dimension 0

19.11.2012 Kesten’s theorem holds for random Kronecker sequences on the torus T^d

26.10.2012 Fast 1.488-approximation for the uncapacitated facility location problem

23.10.2012 Any finite union of intervals supports a Riesz basis of exponentials

27.08.2012 Cardinal numbers \textbf{p} and \textbf{t} are equal

02.07.2012 The Waring rank of any monomial x_1^{a_1}\dots x_n^{a_n} with a_1 \leq \dots \leq a_n is \prod\limits_{i=2}^n(1+a_i)

22.06.2012 Unitary perturbation of any matrix is well invertible with high probability

09.06.2012 Random n \times n matrix with E[\xi_{ij}^k]=E[N(0,1)^k], k\leq 4 has \approx\sqrt{\frac{2n}{\pi}} real eigenvalues

04.06.2012 P(random walk in bounded degree planar graph avoids v_0 for T steps) \leq\frac{C}{\log T}

20.05.2012 Density one local-global conjecture for integral Apollonian packings is true

30.04.2012 The log-Brunn-Minkowski inequality holds for two convex bodies in {\mathbb R}^2

30.04.2012 The list chromatic number of graph with average degree d is \geq (1+o(1))\log_2 d

29.04.2012 Sparse analog of Szemerédi’s theorem is true

10.04.2012 There exist finitely generated simple groups that are infinite and amenable

29.03.2012 Every embedded minimal torus in {\mathbb S}^3 is congruent to the Clifford torus

27.02.2012 Integral of the square of the mean curvature of a torus in {\mathbb R}^3 is at least 2\pi^2

24.02.2012 Every position of Rubik’s Cube can be solved in 20 moves or less

15.02.2012 Every measure preserving word is primitive

19.01.2012 The clique density conjecture of Lovász and Simonovits is true

01.01.2012 If d\geq 3, exists convex body in {\mathbb R}^d, not a ball, with same-volume max sections

Theorems submitted in 2011

16.12.2001 Erdős conjecture on square-free values of f(p), f cubic, p prime, is true

14.11.2011 Two n\times n matrices can be multiplied using O(n^{2.3737}) operations

16.09.2011 The diameter of the symmetric group \text{Sym}(n) is at most \exp(O((\log n)^4\log\log n))

01.09.2011 Fast recovery of x\in{\mathbb C}^n from m=O(n\log n) random magnitude measurements

08.08.2011 The chromatic threshold of a graph H with \chi(H)=r \geq 3 can be \frac{r-3}{r-2}, \frac{2r-5}{2r-3}, or \frac{r-2}{r-1}

01.08.2011 There exist groups of oscillating intermediate growth

25.07.2011 The BMV (Bessis-Moussa-Villani) conjecture is true

19.07.2011 Zaremba’s conjecture is true for a set of density one

01.05.2011 The Hanna Neumann conjecture is true

17.04.2011 A fixed point theorem holds for \alpha–\psi-contractive type mappings

31.03.2011 The Grothendieck constant is strictly smaller than Krivine’s bound

15.03.2011 The Szemerédi–Trotter estimate holds for subspaces in {\mathbb R}^d, with \epsilon loss

03.03.2011 \zeta(2,\dots,2,3,2,\dots,2) is a rational linear combination of products \zeta(m)\pi^{2n}

31.01.2011 There exist an \epsilon>0 and C<\infty such that if A \subseteq {\mathbb F}_3^N is a cap set, then \frac{|A|}{3^N} \leq \frac{C}{N^{1+\epsilon}}

Theorems submitted in 2010

21.12.2010 A convergent algorithm for non-smooth convex saddle-point problems

07.12.2010 For bounded A\subset L^1, exists x\in L^1 fixed by every isometry of L^1 preserving A

03.12.2010 Main conjecture in Vinogradov’s Mean Value Theorem is true if s\geq k(k+1)

18.11.2010 Szemerédi’s theorem holds almost surely inside sparse random sets

17.11.2010 A set of N points in the plane determines at least c\frac{N}{\log N} distinct distances

15.11.2010 {\mathbb Z} is definable in {\mathbb Q} by a universal first-order formula in the language of rings

07.11.2010 There is a HAPpy Banach space, other than l_2, which has a symmetric basis

30.10.2010 The size of subset of \{1,...,N\} without 3-term progressions is O\left(\frac{N}{\log^{1-o(1)} N}\right)

12.10.2010 Internal DLA process converges to disk with at most logarithmic discrepancy

10.10.2010 The distortion of a knot in {\mathbb R}^3 can be arbitrary large

22.09.2010 For each N\geq c_d t^d, there exists an N-point spherical t-design in the sphere S^d

21.09.2010 There are (C_k+o(1))\frac{N^2}{\log^k N} k-term arithmetic progressions of primes at most N

27.08.2010 If \sum\limits_{k=0}^n c_k q^k is chromatic polynomial, then |c_k| form a log-concave sequence

06.08.2010 For a>b>0, \lim\limits_{n\to\infty}\frac{P(a^n-b^n)}{n}=\infty, where P(m) is the greatest prime factor of m

27.07.2010 The least squares mean for positive definite matrices is monotone

04.07.2010 The connective constant of the honeycomb lattice is equal to \sqrt{2+\sqrt{2}}

01.07.2010 A positive proportion of elliptic curves over {\mathbb Q} ordered by height have rank 0

16.06.2010 For most cubic forms F, solution set of F(x,y)=z^l, \,\text{gcd}(x,y)=1,\,  l\geq 4 is finite

14.06.2010 The Hirsch Conjecture is false

04.06.2010 The average rank of elliptic curves over {\mathbb Q} ordered by height is at most 1.5

25.04.2010 The Hoeffding inequality holds for semidefinitely upper bounded matrices

25.04.2010 For any graph, the blanket and cover times are within an O(1) factor

10.02.2010 w_1(G)w_2(G)=G for any group words w_{1,2}\neq 1 and large finite simple group G

21.01.2010 The positive density conjecture for integer Apollonian circle packings is true

15.01.2010 The Schmidt conjecture in simultaneous Diophantine approximation is true

10.01.2010 Graph removal lemma holds with \delta^{-1} being a tower type function of \log(\epsilon^{-1})

Theorems submitted in 2009

27.12.2009 Regular tetrahedra can be packed in {\mathbb R}^3 with density \frac{4000}{4671}=0.856347\dots

18.12.2009 Principal component analysis with sparse perturbation can be done fast

14.12.2009 When n \geq 5, the Dehn function of SL(n;{\mathbb Z}) is quadratic

04.11.2009 For d\geq 19, the one-arm exponent for critical bond percolation in {\mathbb Z}^d is \frac{1}{2}

20.10.2009 The density Hales-Jewett theorem holds with an explicit bound

16.10.2009 The threshold conjecture of Turán properties for random graphs is true

11.10.2009 The Furstenberg’s conjecture on dimension of sum of invariant sets in true

15.09.2009 The critical bias for the Hamiltonicity Maker-Breaker game is (1+o(1))\frac{n}{\log n}

11.09.2009 Systems of polynomial equations can be solved in average time N^{O(\log\log N)}

01.07.2009 Replica predictions hold for dimension d\geq 1 mean-field minimum matching

22.06.2009 The Khorunzhiy conjecture on the norms of random band matrices is true

18.06.2009 Every element of every finite non-abelian simple group is a commutator

02.06.2009 Wigner Hermitian matrices have universal eigenvalue gap distribution

31.05.2009 There exists a fully homomorphic encryption scheme

20.05.2009 Polynomial maps with only real critical points have connected isentropes

14.05.2009 The product of typical interval exchange transformations is uniquely ergodic

21.04.2009 Any semigroup in {\mathbb Z}^n is asymptotically approximated by its regularisation

02.04.2009 Any analytic submanifold of {\mathbb R}^n, n\geq 2, is of Khintchine type for divergence

10.03.2009 Every tensor has a tensor-train decomposition

09.03.2009 For large n, if set of permutations I \subset S_n is k-intersecting, then |I| \leq (n-k)!

04.03.2009 An explicit construction of a 2^{(\log n)^{o(1)}}-Ramsey graph over n vertices

03.03.2009 Algorithmic version of general Lovász local lemma is true

Theorems submitted in 2008

14.11.2008 The Bennett–Carbery–Tao multilinear Kakeya conjecture is true

14.11.2008 Any bounded Apollonian circle packing has \sim cT^\alpha circles of radius \geq\frac{1}{T}

03.11.2008 The threshold for making squares is sharp up to a factor of \frac{4}{\pi}

14.10.2008 For almost all \alpha,\beta \in {\mathbb R}, and all \gamma,\delta \in {\mathbb R}, \liminf\limits_{|n|\to\infty}|n|\,\,||n\alpha-\gamma||\,\,||n\beta-\delta||=0

02.09.2008 Fast \left(1-\frac{1}{e}\right)-approximation to \max\limits_{S \in I}f(S) for submodular f and matroid I

27.08.2008 The hypergraph Ramsey numbers r_3(s,n) are at most 2^{n^{s-2}\log n}

30.07.2008 The circular law conjecture is true

29.05.2008 Fast recovery of size-n rank-r random matrix from m\approx rn^{5/4} random entries

11.05.2008 Centered Hardy–Littlewood maximal inequality in {\mathbb R}^d has no uniform bound

03.04.2008 The cost L_n of the mean-field TSP on n-vertex graph converges to L^*=2.04...

16.03.2008 The size of every Kakeya set in {\mathbb F}^n, where {\mathbb F} is a finite field, is at least C_n|{\mathbb F}|^n

23.01.2008 De Giorgi’s conjecture fails in dimensions n\geq 9

01.01.2008 Undirected connectivity is in log-space

Theorems submitted in 2007

27.12.2007 n-digit integers can be multiplied in n\log n 2^{O(\log^*(n))} operations

26.12.2007 For log-concave \mu, the first moment concentration implies exponential one

30.11.2007 The Riemann zeta function \zeta\left(\frac{1}{2}+it\right) can be computed to \pm t^{-\lambda} in time t^{\frac{4}{13}+o_\lambda(1)}

08.11.2007 The full list of connected properly embedded minimal planar domains in {\mathbb R}^3

15.10.2007 \liminf\limits_{n\to\infty}\frac{p_{n+1}-p_n}{\sqrt{\log p_n}(\log \log p_n)^2}<\infty, where p_n denotes the n-th prime

11.10.2007 The Alon-Yuster conjecture on factors in random graphs is true

27.09.2007 The Hausdorff dimension of the set of singular pairs is \frac{4}{3}

08.09.2007 Every triangle with all angles at most 100^\circ has a periodic billiard path

05.07.2007 Equation x^2-dy^2=-1 is solvable for \Theta\left(\frac{X}{\sqrt{\log X}}\right) squarefree d, 0<d<X

18.06.2007 If A is a finite subset of free group, and \exists a,b \in A: ab \neq ba, then |A^3| \geq \frac{|A|^2}{(\log|A|)^{O(1)}}

14.05.2007 Polynomials with infinite orbit intersection must have a common iterate

01.05.2007 Any order-reversing involution on convex functions is Legendre transform

24.04.2007 Entire function whose escaping set has only bounded path-components

12.04.2007 The problem of computing two-player Nash equilibrium is PPAD-complete

01.04.2007 O(\sqrt{\log n})-approximation for the sparsest cut can be done in polynomial time

16.03.2007 P\left(||A^{-1}||\geq \frac{\sqrt{n}}{\epsilon}\right)\leq C\epsilon+c^n if A is n\times n matrix with i.i.d. subgaussian a_{ij}, \epsilon \geq 0

07.03.2007 Entropies of multidimensional shifts of finite type may be noncomputable

03.02.2007 There exists an outer billiards system with an unbounded orbit

11.01.2007 w_1(A_n)w_2(A_n)=A_n for any group words w_{1,2}\neq 1 and large alternating group A_n

Theorems submitted in 2006

04.12.2006 Moments M_k(T) of the Riemann zeta function are at most C_{k,\epsilon}T(\log T)^{k^2+\epsilon}

26.11.2006 Equation \sum\limits_{i=1}^N \cos(n_i x)=0 can have less than CN^{5/6}\log N solutions in [0,2\pi)

07.11.2006 Approximating max clique and chromatic number to within n^{1-\epsilon} are NP-hard

02.11.2006 Systems of polynomial equations can be solved in expected polynomial time

01.10.2006 The primes contain arbitrarily long polynomial progressions

22.09.2006 Computing forth moment of L(\frac{1}{2},\chi) for prime moduli q with O(q^{-\frac{5}{512}}) error

16.08.2006 The kissing numbers in dimensions 5,6,7,9,10 are at most 45,78,135,366,567

15.08.2006 The variance of the current across the characteristic in ASEP is of order t^{2/3}

24.07.2006 Solving symmetric diagonally dominant linear systems in near linear time

18.07.2006 Characterization of stability-preserving linear operators on polynomials

11.07.2006 The diagonal Ramsey numbers r(k+1,k+1) do not exceed k^{-C\frac{\log k}{\log \log k}}{2k\choose k}

05.07.2006 Exists infinitely many groups G with no product-free subset of size 2|G|^{8/9}

05.07.2006 The set of n=d \exp(cd) i.i.d Gaussian points in {\mathbb R}^d is linearly separable

08.06.2006 Every cubic form over integers in n\geq 14 variables has a non-trivial zero

04.06.2006 There are \sim C\frac{N^2}{\log^4 N}, \, C=0.4764... 4-term progressions of primes at most N

18.05.2006 There exist quadratic polynomials that have a Julia set of positive area

29.04.2006 A version of the central limit theorem holds for convex sets

27.01.2006 There exists an exhaustive submeasure that is not equivalent to a measure

24.01.2006 w(G)^3=G for every group word w\neq 1 and every large finite simple group G

16.01.2006 The set of all integer solutions of ad-bc=1 is a polynomial family

01.01.2006 The Bobkov–Nazarov estimate holds true for all isotropic convex bodies

Theorems submitted in 2005

17.12.2005 The optimal exponent in the quantitative isoperimetric inequality is \frac{1}{2}

14.12.2005 The B. and M. Shapiro conjecture in real algebraic geometry is true

13.12.2005 Any C^{(2)} nondegenerate planar curve is of Khintchine type for convergence

10.11.2005 Half of primes have the even sum of digits

08.11.2005 \forall C>0 \, \exists B: P\left(||A^{-1}||\geq n^B\right)\leq n^{-C} if A is n\times n matrix with i.i.d. Bernoulli a_{ij}

03.11.2005 The Cayley graphs of \text{SL}_2({\mathbb F}_p) with random generators are expanders

17.10.2005 The limit \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^N e^{2\pi i u(n)} exists for any bounded generalized polynomial u

10.10.2005 Dyson’s rank partition functions satisfy congruences of Ramanujan type

06.10.2005 Fast algorithm to approximately fit a C^m-smooth function to data

18.09.2005 Menger’s theorem holds for infinite digraphs

01.09.2005 Elements of \text{SL}_2({\mathbb F}_p) have representations of length O((\log p)^c)

10.08.2005 For any \epsilon>0, p_{n+1}-p_n <\epsilon\log n infinitely often, where p_n is the n-th prime

08.08.2005 Any n-point metric space of negative type O(\sqrt{\log n}\log\log n)-embeds into {\mathbb R}^d

07.07.2005 The edge-deletion problem can be \epsilon n^2-approximated in linear time

30.06.2005 P\left(||A^{-1}||\leq \frac{Cn^{3/2}}{\epsilon}\right)>1-\epsilon if A is n\times n matrix with i.i.d. subgaussian a_{ij}, \epsilon>\frac{c}{\sqrt{n}}

10.06.2005 For p, q > 0, L^p embeds uniformly into L^q if and only if p \leq q or q \leq p \leq 2

08.06.2005 (1,p)-Poincaré inequality implies (1,p-\epsilon)-Poincaré inequality for some \epsilon>0

05.06.2005 Dantzig selector recovers sparse x\in{\mathbb R}^m from n \ll m noisy measurements

28.05.2005 Cayley graphs of symmetric groups can form explicit family of expanders

25.05.2005 If \sum\limits_{n\in S}\frac{1}{n} is bounded for covering system S, then \min\limits_{n\in S}n is also bounded

06.05.2005 Nevanlinna characteristic T(r,f(z+z_0)) grows as T(r,f(z)) for finite order f

29.04.2005 Dynamical critical site percolation on triangular grid has exceptional times

25.04.2005 Multidimensional Szemeredi’s theorem holds with an explicit bound

14.04.2005 The Hasse principle holds for the systems \sum\limits_{i=1}^sa_ix_i^3 = \sum\limits_{i=1}^sb_ix_i^3 = 0 if s \geq 13

05.04.2005 The sequence of perfect squares 1,4,9,\dots,n^2,\dots is L1-universally bad

23.03.2005 The “Majority Is Stablest” conjecture is true

17.03.2005 The spectrum of the almost Mathieu operator is a Cantor set for irrational \alpha

03.03.2005 L1-regularisation recovers sparse x\in{\mathbb R}^m from n \ll m inexact measurements

02.03.2005 Pólya-Vinogradov bound is not tight for characters of odd, bounded order

18.01.2005 There are g(n) \sim C n^{-7/2}\gamma^n n! labelled planar graphs on n vertices

Theorems submitted in 2004

08.11.2004 The Grothendieck constant of the complete n-vertex graph is at least c\log n

05.11.2004 Random Bernoulli n\times n matrix is singular with probability at most \left(\frac{3}{4}+o(1)\right)^n

02.11.2004 Uncountable set of 2-generated groups with exactly 2 conjugacy classes

29.09.2004 Linear growth of the number of quintic fields with bounded discriminant

18.09.2004 l_p-sparse x\in{\mathbb R}^m can be O(N^{\frac{1}{2}-\frac{1}{p}})-approximated in O(N\log m) measurements

27.08.2004 For any unimodular lattice L \subset {\mathbb R}^6, we have \sup\limits_{x\in {\mathbb R}^6} \inf\limits_{y\in L} \left|\prod\limits_{i=1}^6(x_i-y_i)\right|\leq 2^{-6}

06.08.2004 Any real polynomial can be approximated by hyperbolic real polynomials

01.08.2004 If u\in L^{\frac{2n}{n-\alpha}}({\mathbb R}^n), u>0, and u(x) = \int_{{\mathbb R}^n}\frac{1}{|x-y|^{n-\alpha}}u(y)^{\frac{n+\alpha}{n-\alpha}}dy, then u(x) = c\left(\frac{t}{t^2+|x-x_0|^2}\right)^{\frac{n-\alpha}{2}}

12.07.2004 The number of relative equilibria of the Newtonian 4-body problem is finite

16.06.2004 Typical interval exchange transformation is either rotation or weakly mixing

07.06.2004 Linear growth of the number of quartic fields with bounded discriminant

02.06.2004 The Duffin–Schaeffer conjecture implies its Hausdorff measure version

01.06.2004 No arithmetic sequence is very well-distributed

30.05.2004 The complexity of every irrational algebraic number has superlinear growth

11.05.2004 Elliptic curve with discriminant \Delta has at most O_\epsilon(|\Delta|^{0.2007...+\epsilon}) integer points

09.04.2004 Calabi-Yau conjectures are true for embedded surfaces with finite topology

08.04.2004 The primes contain arbitrarily long arithmetic progressions

16.03.2004 The highest density of lattice sphere packing in {\mathbb R}^{24} is \frac{\pi^{12}}{12!}

29.02.2004 Quartic rings can be explicitly parametrized

26.01.2004 Metric entropy is equivalent to combinatorial dimension, under regularity

18.01.2004 There are \sim\frac{N^2}{(\log N)^{0.086...}(\log\log N)^{3/2}} distinct products in N\times N multiplication table

08.01.2004 There exists an embedded genus-one helicoid in {\mathbb R}^3

01.01.2004 There is a convergent algorithm for minimising the total variation

Theorems submitted in 2003

31.12.2003 Shape theorem holds in Kesten-Sidoravicius model for the infection spread

18.12.2003 The Füredi-Hajnal Conjecture and the Stanley–Wilf Conjecture are true

17.12.2003 Translation invariant \text{SL}(n) equivariant valuations are difference operators

24.11.2003 The only perfect powers in the Fibonacci sequence are 0,1,8, and 144

09.11.2003 The chromatic number of a random graph G\left(n,\frac{d}{n}\right) is k_d=\min\limits_{k \in {\mathbb Z}:\,2k\log k>d}k or k_d+1

02.10.2003 Lehmer’s conjecture is true for polynomials with odd coefficients

26.09.2003 The kissing number in dimension four is 24

25.09.2003 Trudinger-Moser inequality with Sobolev norm holds for all domains in {\mathbb R}^2

24.09.2003 Any C^{(3)} nondegenerate planar curve is of Khintchine type for divergence

23.09.2003 Every separable infinite dimensional Banach space has infinite diameter

11.09.2003 The Hopf condition for bilinear forms holds over arbitrary fields

08.09.2003 There are at most B_n X^{e^{C\sqrt{\log n}}} degree n number fields with discriminant \leq X

05.09.2003 Littlewood conjecture holds outside of a set of Hausdorff dimension 0

04.09.2003 An asymptotic form of the Satisfiability Threshold Conjecture is true

04.09.2003 The Lieb conjecture on the monotonicity of Shannon’s entropy is true

03.09.2003 For any b>0 exists k> 0 such that \max(|kA|,|A^k|)\geq|A|^b holds for any A \subset {\mathbb Z}

01.08.2003 There exists FPRAS for the permanent of a matrix with nonnegative entries

17.07.2003 Poincaré conjecture is true: simply connected closed 3-manifold is a sphere

29.05.2003 Duality conjecture for entropy numbers is true if one of the bodies is a ball

28.05.2003 Vertex cover is unique-games-hard to approximate within any factor c < 2

14.05.2003 Whitney extension theorem holds with C^{m-1,1}({\mathbb R}^n) in place of C^m({\mathbb R}^n)

25.04.2003 The weak form of De Giorgi’s conjecture is true in dimensions n\leq 8

26.03.2003 The set of nowhere monotone differentiable functions on \mathbb R is lineable

19.03.2003 \exists c>0 such that every set of natural numbers of density c\sqrt{n} is subcomplete

28.02.2003 For any convex domain \Omega, Poincaré inequality holds with constant \frac{\text{diam}(\Omega)}{\pi}

26.02.2003 Perfect graphs can be recognised in polynomial time

25.02.2003 Any positive proportion of primes contains a 3-term arithmetic progression

29.01.2003 The Erdős–Szemerédi sum-product theorem holds in finite fields

24.01.2003 Primality testing can be done in deterministic polynomial time

Theorems submitted in 2002

04.12.2002 The strong perfect graph conjecture is true: all Berge graphs are perfect

04.12.2002 All n-point metric spaces have subsets of size n^{1-C \frac{log(2\alpha)}{\alpha}} \alpha-embeddable into {\mathbb R}^d

22.11.2002 Degree n polynomials small at N points on (-1,1) are small for |x|<\sqrt{1-\frac{n^2}{N^2}}

08.11.2002 Fast algorithm for the number of solutions in the coin problem with fixed n

11.10.2002 The \tau_n=n conjecture in approximation by algebraic integers is false: \tau_3=\frac{3+\sqrt{5}}{2}

07.10.2002 Minimum vertex cover is NP-hard to approximate within factor c < 10\sqrt{5}-21

22.09.2002 For partition function p(.), no prime q \neq 5,7,11 divides p(qn+b) for all n

15.09.2002 Zero-divisor graph of a local ring with at least 33 elements is not planar

09.09.2002 The Catalan’s conjecture is true: if x^a-y^b=1, then x=3, a=2, y=2, b=3

22.06.2002 A group with exponential growth but not uniform exponential growth

19.06.2002 A version of Banach’s fixed point theorem holds for partially ordered sets

16.06.2002 Ergodic averages taken along cubes whose sizes tend to +\infty converge in L^2

29.05.2002 (2+\epsilon)n Steiner symmetrizations transform convex body in {\mathbb R}^n into near ball

27.03.2002 The Alon’s second eigenvalue conjecture is true

04.03.2002 In Vicsek model, all agents will eventually move in the same direction

31.01.2002 (\log t)^{2/3} law holds for the 2D asymmetric simple exclusion process

Theorems submitted in 2001

17.12.2001 The hot spots conjecture is true for Lip domains

10.12.2001 Covering number of a bounded set is exponential in its shattering dimension

28.11.2001 Probability that Wiener sausages intersection volume is large decays fast

27.11.2001 The size of set of simple sums and products of k distinct integers exceeds k^d

19.11.2001 The simplex algorithm has polynomial smoothed complexity

12.11.2001 Characterisation of linear recurrences whose ratio is integer infinitely often

01.10.2001 Any sphere packing in {\mathbb R}^8 has density at most 1.000001\frac{\pi^4}{384}

13.09.2001 The analytic capacity is semiadditive

13.09.2001 5n Minkowski symmetrizations transform convex body in {\mathbb R}^n into near ball

06.09.2001 Instance optimal algorithm for aggregation in multimedia databases

23.08.2001 Linear groups of exponential growth have uniform exponential growth

16.08.2001 The best constant in centered Hardy–Littlewood maximal inequality is \frac{11+\sqrt{61}}{12}

31.07.2001 A polynomial is matrix-positive if and only if it is the sum of squares

26.07.2001 The simple random walk covers all points of {\mathbb Z}_n^2 in \left(\frac{4}{\pi}+o(1)\right)n^2(\log n)^2 steps

23.07.2001 Rational polygon whose set of non-ergodic directions has dimension 1/2

19.07.2001 Two components of the USF in {\mathbb Z}^d are adjacent a.s. if 5 \leq d \leq 8, but not if d \geq 9

25.05.2001 Regular n-gon minimizes logarithmic capacity among all n-gons with area S

22.05.2001 Any sequence of Lipschitz maps has a common point of differentiability

19.05.2001 There exist non-isotrivial elliptic curves over {\mathbb F}_p(t) with arbitrarily large rank

16.05.2001 For any r-colouring of integers, there is a monochromatic set S with \sum\limits_{n\in S}\frac{1}{n}=1

30.03.2001 Any non-trivial knot has ropelength at least 2\pi(2+\sqrt{2}) \approx 21.45

13.03.2001 Properly embedded simply connected minimal surface is plane or helicoid

14.02.2001 There is a set S \subset {\mathbb R}^2 such that |S \cap L|=1  for every isometric copy L of {\mathbb Z}^2

13.02.2001 In any infinite sequence G_1, G_2, \dots of graphs, some G_i is a minor of some G_j

08.02.2001 A finitely presented non-amenable group without free non-cyclic subgroups

Theorems submitted in the 20th century and published in the 21st century

12.12.2000 Ellipsoid rE in {\mathbb R}^d, d\geq 5, contains \text{Vol}(rE)+O(r^{d-2}) lattice points, as r\to\infty

28.11.2000 If m\mid n(2n+1), complete graph K_{2n+1} can be decomposed into length m cycles

17.11.2000 Irreducible form F(x,y,z) of degree d has at most  O(B^{2/d+\epsilon}) B-bounded roots

06.10.2000 Sinai conjecture on orbit recurrence of nonregular quadratic maps is true

25.09.2000 Betweenness centrality of all graph vertices can be computed in O(nm) time

24.08.2000 Robbins conjecture on the number of vertically symmetric ASMs is true

17.08.2000 Julia set of typical quadratic map is locally connected and has measure zero

01.08.2000 Largest eigenvalue of X'X, with x_{ij} i.i.d. normal, approaches Tracy–Widom

25.07.2000 Set of m n-variate degree-d polynomials has at most \left(\frac{emd}{n}\right)^n zero patterns

11.07.2000 The Lagarias-Wang finiteness conjecture is false

10.07.2000 Constant-degree expanders construction based on zig-zag product

02.06.2000 The norms of bilinear Hilbert transforms are uniformly bounded

30.05.2000 Random polynomial of degree n has no real zeros with probability n^{-b+o(1)}

10.05.2000 Pair correlation density of sequence (m-\alpha)^2 + (n-\beta)^2 on [a,b] is \pi(b-a)

03.05.2000 For all large x, there is a prime number between x - x^{0.525} and x

30.03.2000 The only Banach space isomorphic to each of its subspaces is l^2

27.03.2000 The intersection exponent for two simple random walks on the plane is 5/8

22.03.2000 Least-area way to enclose and separate two regions of given volumes in {\mathbb R}^3

11.03.2000 All braid groups are linear

01.03.2000 Szemeredi’s theorem holds with doubly exponential bound

28.02.2000 The modularity theorem: every elliptic curve over Q is modular

24.02.2000 Small set of initial points for Newton’s method to find all polynomials roots

28.01.2000 Polynomial minimisation can be reduced to LMI problem

25.01.2000 All critical points of a rational function f are real only if f is equivalent to real

24.01.2000 Inequality \left|\prod\limits_{i=1}^d\left(\sum\limits_{j=1}^n a_{ij}x_j\right)\right|\leq m has \infty or O\left(m^{n/d}\right) integer solutions

04.01.2000 There exists a field with u-invariant 9

30.12.1999 There are three nonempty phases for percolation on planar hyperbolic graph

28.10.1999 Elements of finite simple groups have short normal subsets representations

15.09.1999 There exist two different finite groups with isomorphic integral group rings

08.09.1999 The asymptotic mean of bounded multiplicative function is \geq -0.656999...

05.07.1999 Moderate deviations probability for the Wiener Sausage volume decays fast

08.06.1999 The honeycomb conjecture is true

10.05.1999 Erdős-Taylor conjecture on most visited point of random walk in {\mathbb Z}^2 is true

29.04.1999 There are infinitely many primes of the form x^3+2y^3

09.02.1999 For every n>30, n-th Lehmer number has a primitive divisor

11.11.1998 The dodecahedral conjecture on the smallest volume of Voronoi cell is true

04.09.1998 The Kepler conjecture is true: the highest sphere packing density in {\mathbb R}^3 is \frac{\pi}{3\sqrt{2}}

31.07.1998 Palis conjecture on the arithmetic difference of regular Cantor sets is true

29.07.1998 Zagier conjecture is true: \zeta(\{1, 3\}^n) = \frac{2\pi^{4n}}{(4n+2)!}

20.04.1998 Characterisation of finitely generated groups with word problem in NP

01.08.1997 For any k\geq 3, optimal approximation ratio for Max-Ek-Sat is 1-2^{-k}

15.07.1997 Almost every real quadratic polynomial is either regular or stochastic

24.05.1997 A finitely presented group can have NP-complete word problem

—————————————————————————————-

I thank my MSc student, Adam Smith, for a help with the website and Excel document.

Bogdan Grechuk

2 thoughts on “Theorems List”

Leave a reply to New York Cancel reply