Test Your Intuition (or simply guess) 37: Arithmetic Progressions for Brownian Motion in Space

 

Consider a Brownian motion in three dimensional space. What is the largest number of points on the path described by the motion which form an arithmetic progression? (Namely, x_1,x_2, x_t, so that all x_{i+1}-x_i are equal.)

 

A 2-D picture; In two dimension the answer is [infinity: oops my mistake] that there is an AP of arbitrary large length almost surely.  Source: Raissa D’Souza

Advertisements
Posted in Probability, Test your intuition | Tagged , | 7 Comments

Test Your Intuition (or knowledge, or programming skills) 36

How much is

 

The product ranges over all primes. In other words,

Just heard it from Avinoam Mann.

 

Posted in Number theory, Test your intuition | Tagged | 12 Comments

Bob Sedgewick’s Free Online Courses on Analysis of Algorithms and Analytic Combinatorics.

Philippe Flajolet 1948-2011

 

I am  happy to forward the announcement on two free online courses (Mooks) by Bob Sedgewick  Analysis of Algorithms and Analytic Combinatorics.

Analysis of Algorithms  page provides access to online lectures, lecture slides, and assignments for use in teaching and learning from the book An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet

Analytic Combinatorics page provides access to online lectures, lecture slides, and assignments for use in teaching and learning from the (famous) book Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick.

Both courses are appropriate for use by instructors as the basis for a “flipped” class on the subject, or for self-study by individuals. Are these courses for you? The short answer is YES, but for a longer answer below are introductory slide for both courses.

To read more on Philippe Flajolet, see, Wikipedea; Obituary on GLL ).

Posted in Combinatorics, Computer Science and Optimization, Teaching, Updates | Tagged , | Leave a comment

Dan Romik Studies the Riemann’s Zeta Function, and Other Zeta News.

Updates to previous posts: Karim Adiprasito expanded in a comment to his post on the g-conjecture on how to move from vertex-decomposable spheres to general spheres. Some photos were added to the post: Three pictures.

Dan Romik on the Zeta function and its hypergeometric expansions

My friend Dan Romik wrote an impressive paper Orthogonal polynomial expansions for the Riemann xi function about expansion of the Riemann Zeta function. (I thank Dan for telling me about it.) Dan kindly agreed to write a blog post about his work in May 2019.

 

Dan Romik (click once to enlarge, twice to enlarge further)

Michel Griffin, Ken Ono, Larry Rolen, and Don Zagier on Zeta and the hyperbolicity of Jensen polynomials in low degrees

Let me mention also another impressive paper by Michael Griffin, Ken Ono, Larry Rolen and Dan Zagier: Jensen polynomials for the Riemann zeta function and other sequences. (I learned about it from Ken Ono over Facebook. Ken writes: “After almost 2 years and 83 drafts, I am happy to share this paper on the Riemann Hypothesis. Amazingly, this paper has been recommended for publication 6 days after submission!” ). Here is a MO question regarding this development.

(Belated news) Polymath15 over Terry Tao’s blog on Noising and Denoising of the Riemann Zeta Function.

It is now the 10 year anniversary of polymath projects and let me belatedly mention a successful project polymath15 that took place over Terry Tao blog. The problem is related to the Hermite expansion of the Zeta function. Roughly speaking you can apply a noise operator on Zeta that causes higher degrees to decay exponentially. (The noise can be “negative” and then the higher degrees explode exponentially.) The higher the amount  t of noise the easier the assertion of the Riemann Hypothesis (RH) becomes. Let \Lambda, the de Bruijn-Newman constant, be the smallest amount of noise under which the assertion of RH is correct.  It was conjectured that \Lambda \ge 0 namely the assertion of the RH fails when you apply negative noise no matter how small. This follows from known conjectures on the spacing between zeroes of the Zeta function since when the assertion of RH is known for some level (positive or negative) of noise, then with a higher level of noise spacing between zeroes become more boring. The conjecture was settled by Brad Rodgers and Terry Tao. (See this blog post by Terry Tao.)

The task of polymath15 (proposed here, launched here, last (11th) post here) was to use current analytic number theory technology that already has yielded information on the zeroes of the zeta function (in the direction of RH and related conjectures) to deduce sharper upper bounds for \Lambda than the previously known 0.5 value. The collaborative efforts led to

Theorem (Polymath 15): \Lambda \le 0.22

A remarkable success! (Of course, proving RH was not an objective of polymath15.) There were also  interesting comments of general nature regarding the RH and other big conjectures like this nice comment by anonymous.

It is even possible that \Lambda =0 (i.e. RH is true) and for each t >0 there is a simple Hermitian operator (possibly related to a probabilistic interpretation of H_t) having H_t zeros as its spectrum (i.e. realizing Hilbert-Polya approach for H_t) but no such operator for t=0 (which may explain the failed attempts so far to find it). Since the zeros of H_t converge to that of H_0, it is possible that there is a proof of RH via the functions H_t (whose zeros are more regularly distributed) but not via direct attack on H_0 itself!
Such “homotopic approach” to study H_0 via H_t reminds similar methods used in the past to solve big problems (e.g. de Branges solution – via Loewner’s PDE with flow parameter – of the Bieberbach conjecture, and Perelman’s solution – via Hamilton’s Ricci flow PDE – of the Poincare conjecture).

 

Posted in Number theory, Updates | Tagged , , , , , , , , | 2 Comments

Karim Adiprasito: The g-Conjecture for Vertex Decomposible Spheres

J Scott Provan (site)

The following post was kindly contributed by Karim Adiprasito. (Here is the link to Karim’s paper.) Update: See Karim’s comment on the needed ideas for extend the proof to the general case. See also  in the comment section references to papers by Balin and Fleming and by Jensen and Yu.

So, Gil asked me to say a little bit about my proof of the g-conjecture (and some other conjectures in discrete geometry) on his blog, and since he bought me many  coffees to explain it to him (or if he is to be believed, the department paid), I am happy to oblige.

So, I want to explain a special, but critical case to the proof. It contains the some shadow of the core ideas necessary, but needs some more tricks I will remark on afterwards.

Also, I wanted to take this opportunity to mention something marvelous that I learned from Leonid Gurvits recently that increased my own understanding of one of the key tricks used indefinitely. That trick is the following cool lemma.

Leonid Gurvits

Perturbation lemma

PERTURBATION LEMMA: Consider two linear maps

\alpha, \beta: X\ \longrightarrow\ Y

of two real vector spaces X and Y. Assume that

\beta (\ker \alpha ) \cap \rm{im}~ \alpha =\{0\} \subset Y.

Then a generic linear combination \alpha ``+"\beta of \alpha and \beta  has kernel
\ker (\alpha  ``+" \beta )= \ker \alpha \cap \ker \beta.

Cool, no? Proof, then: Find a subspace A of X such that

\alpha A\ =\ \alpha X\quad \text{and}\ \quad X\ \cong\ A \oplus \ker\alpha

so that in particular \alpha is injective on A. Then, for \epsilon \ge 0 small enough, the image of

\alpha\ +\ \epsilon \beta{:}\ X\ \longrightarrow\ Y

is

(\alpha\ +\ \epsilon \beta)(A)\ +\ \beta\ker\alpha\ \subset\ Y.

But if we norm Y in any way, then (\alpha+\epsilon \beta)(A) approximates \alpha A as \epsilon tends to zero, which is linearly independent from \beta\, \ker\alpha by assumption. WALLA

Now, how is this used.

Face rings

Let me set up some of the basic objects.

If \Delta is an abstract simplicial complex on ground-set [n]:= \{1,\cdots,n\}, let I_\Delta := \langle \textbf{x}^{\textbf{a}}: supp (\textbf{a})\notin\Delta\rangle denote the nonface ideal in \mathbb{R}[\mathbf{x}], where \mathbb{R}[\mathbf{x}]=\mathbb{R}[x_1,\cdots,x_n].

Let \mathbb{R}^\ast[\Delta]:= \mathbb{R}[\mathbf{x}]/I_\Delta denote the face ring of \Delta. A collection of linear forms \Theta=(\theta_1,\cdots,\theta_l) in the polynomial ring \mathbb{R}[\textbf{x}] is a partial linear system of parameters if

\dim_{\rm{Krull}} {\mathbb{R}^\ast[\Delta]} {\Theta \mathbb{R}^\ast[\Delta]} =\dim_{\rm{Krull}} \mathbb{R}^\ast[\Delta]-l,

for \dim_{\rm{Krull}} the Krull dimension. If l=\dim_{\rm{Krull}} \mathbb{R}^\ast[\Delta] = \dim \Delta +1, then \Theta is simply a linear system of parameters, and the corresponding quotient A(\Delta)={\mathbb{R}^\ast[\Delta]}/{\Theta \mathbb{R}^\ast[\Delta]} is called an Artinian reduction of \mathbb{R}^\ast[\Delta].

The g-conjecture

The g-conjecture (as described earlier  in Gil’s blog) is implied by the following property:

(HL) For every sphere S of even dimension d-1=2k, there is an Artinian reduction A(S) and a degree one element \ell such that the map

A^k(S) \ \xrightarrow{\ \cdot \ell\ }\ A^{k+1}(S)

is an isomorphism.

This is quite a reasonable demand. Indeed, Graebe proved that A^d(S) \cong \mathbb{R} and that the resulting pairing

A^k(S) \times A^{k+1}(S)\rightarrow \mathbb{R}

is perfect, so A^k(S) and A^{k+1}(S) are isomorphic as vector spaces. We shall call this property (PD), because it is a special case of Poincaré pairing.

(HL) is a special case of the Hard Lefschetz Theorem I prove in my paper, and we will prove it for a subset of all triangulated spheres here. Proving it for all spheres implies the g-conjecture (and other conjectures, such as the Grünbaum conjecture), and proving the hard Lefschetz theorem in full generality is not much harder.

Lou Billera

Vertex-decomposable spheres

Lets recall a cool notion due to Provan and Billera: A pure simplicial d-complex is vertex decomposable if it is a simplex, or there exists a vertex whose link is vertex decomposable of dimension d-1 and its deletion is vertex decomposable of dimension d.

We restrict our attention to vertex decomposable spheres and disks and assume the boundary of the link is vertex decomposable as well in every step.

THEOREM: Vertex decomposable spheres satisfy (HL).

We prove this theorem by induction on dimension, the base case of zero-dimensional spheres (k=0) being clear.

Lets label the vertices of S in order of their vertex decomposition, from 1 to n. Now, \ell will be a linear combination of indeterminates, so lets assume we have constructed an element \ell_i that uses just the first i of them, and such that \ell_i itself is as close to a Lefschetz element as possible for its kind, that is, the kernel of

A^k(S) \ \xrightarrow{\ \cdot \ell_i\ }\ A^{k+1}(S)

is the intersection of kernels of the maps

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S)

where j ranges from 1 to i.

We want to construct a map \ell_{i+1} with this property (which I call the transversal prime property}. To this effect, we want to apply the perturbation lemma to the maps \beta x_{i+1}, \alpha=\ell_i, and with respect to the spaces X=A^k(S) and Y=A^{k+1}(S). Let us denote by D the ball given as the union of neighborhoods of the first i vertices.

For this, we have to find out the kernel of \ell_i. But this is the the ideal in A(S) generated by the monomials of faces which are not in the neighborhood of any of the first i vertices. Lets call it K. Lets also look at the image I of \ell_i, which by Graebe’s theorem is exactly the span of the images of the maps the maps

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S)

where j ranges from 1 to i.

But then, x_{i+1}K \cap I is 0 in degree k+1 if and only if A(st_{i+1} \partial D) is 0 in degree k. Why is that? Because with respect to the Poincaré pairing, x_{i+1}K \cap I (in degree k+1) and A(st_{i+1} \partial D) (in degree k) are dual.
The ring A(st_{i+1} \partial D) is obtained by taking \mathbb{R}[st_{i+1} \partial D], seen as a quotient of \mathbb{R}[S] and modding out by the ideal generated by the linear system \Theta. But that is of length d, even though st_{i+1} \partial D is only of dimension d-2. We can remove the vertex i+1 for the price of removing one of the linear forms, but then we have the same issue, having a (d-3)-sphere st_{i+1} \partial D and a system \Theta' of length d-1. Still, one too many! Taking a subsystem of length d-2, we obtain an Artinian reduction for \mathbb{R}[lk_{i+1} \partial D] via a linear system \Theta'', but what happens to the additional linear form of \Theta' not in \Theta''? It has to act as a Lefschetz element on \mathbb{R}[lk_{i+1} \partial D]/\Theta''\mathbb{R}[lk_{i+1} \partial D] if we want

A(st_{i+1} \partial D)\ \cong\ \mathbb{R}[lk_{i+1} \partial D]/\Theta'\mathbb{R}[lk_{i+1} \partial D]

to be trivial in degree k. But we may assume so by induction! Hence, we can choose \ell_{i+1} as the generic sum of \ell_i and x_{i+1} by the perturbation lemma.

So, ultimately, we can construct a map \ell_n with the transversal prime property. But then its kernel is the intersection of the kernels of

A^k(S) \ \xrightarrow{\ \cdot x_j\ }\ A^{k+1}(S) ,

where j ranges from 1 to n. But that is 0SABABA.

And beyond?

Now, we have the Lefschetz theorem for a special class, but that is less than what we want in the end, since vertex decomposable spheres are few and in between (do you see a reason why? there are many). So, what do we do? For a long time, I tried to extend the perturbation lemma to combine more than two maps.
Recently (depending on when Gil puts this post on the blog), I met Leonid Gurvits for the first time on a marvelous little conference at the Simons Institute. I knew that the problem is related to Hall’s Marriage Theorem for operators (I explain this connection a bit further in my paper), but Leonid enlightened this further by pointing me towards several nice papers, starting with his work on Quantum Matching Theory. Indeed, finding a good extension to three and more maps would essentially mean that we could also find Hall Marriage Type Theorems for 3-regular hypergraphs, which we know for complexity reasons to be unlikely.

So what can we do instead? Well, it turns out that I only really needed to look at the k-skeleton of S above, and there is no need to be vertex decomposable. It is enough to find another nicely decomposable d-1-manifold that contains it the k-skeleton of S, and then use some technical topological tricks to connect the local picture to global homological properties.

 

 

 

Posted in Combinatorics, Convex polytopes, Geometry, Guest blogger | Tagged , , , , | 9 Comments

Fix a Horse Race…

GK (2019): Can you base world economy on horse races? Here is an old unpublished draft from 2008 that I did not complete, which was  inspired by the  economic crisis at that time. (It also felt a little over the top, but my standards since then have relaxed somewhat.)

Another opportunity to be reminded with this old post came in a recent conference at Pittsburgh where I had an interesting conversation over lunch with Bill Benter whose company uses statistical methods to get ahead of Horse race gambling.  

Continue reading

Posted in Economics, Games, Rationality, Taxi-and-other-stories | Tagged , , , | Leave a comment

Attila Por’s Universality Result for Tverberg Partitions

In this post  I would like to tell you about three papers and three theorems. I am thankful to Moshe White and Imre Barany for helpful discussions.

a) Universality of vector sequences and universality of Tverberg partitions, by Attila Por;

Theorem (Por’s universality result, 2018): Every long enough sequence of points in general position in \mathbb R^d  contains a subsequence of length n whose Tverberg partitions are exactly the so called rainbow partitions.

b) Classifying unavoidable Tverberg partitions, by Boris BukhPo-Shen LohGabriel Nivasch

Theorem (Bukh, Loh, and Nivasch, 2017): Let H be a tree-like r-uniform simple hypergraph with d+1 edges and n=(d+1)(r-1)+1 edges. It is possible to associate to the vertices of each such hypergraph H a set X of n points in \mathbb R^d so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is (r-1)!^d. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

c) On Tverberg partitions, by Moshe White

Theorem (White, 2015): For any partition a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1 of n, there exists a set X \subset \mathbb R^d of n  points, such that every Tverberg partition of X  induces the same partition on n given by the parts a_1,\dots,a_r. Moreover, the number of Tverberg’s partitions of X is (r-1)!^d

See the original abstracts for the papers at the end of the post.

Radon’s and Tverberg’s theorems and Sierksma’s conjecture

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

Tverberg Theorem (1965): Let x_1,x_2,\dots, x_m be points in R^d, m \ge (r-1)(d+1)+1. Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

The (much easier) case r=2 of Tverberg’s theorem is Radon’s theorem.

We devoted a post to seven open problems related to Tverberg’s theorem, and one of them was:

Sierksma Conjecture: The number of Tverberg’s r-partitions of a set of (r-1)(d+1)+1 points in R^d is at least ((r-1)!)^d.

Gerard Sierksma’s construction with (r-1)!^d Tverberg’s partition is obtained by taking (r-1) copies of each vertex of a simplex containing the origin in its interior, and adding the origin itself. A configuration of (r-1)(d+1)+1 points in R^d with precisely ((r-1)!)^d Tverberg partitions to r parts is called a Sierksma Configuration.

White’s Theorem

In 2015 Moshe White proved the following theorem which was an open problem for many years. White’s construction was surprisingly simple.

Theorem 1 (White, 2015):  For any partition a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1 of n, there exists a set X \subset \mathbb R^d of n  points, such that every Tverberg partition of X  induces the same partition on n given by the parts a_1,\dots,a_r. Moreover, the number of Tverberg’s partitions of X is (r-1)!^d

Bukh, Loh, and Nivasch’s  examples via staircase convexity.

Five tree-like simple hypergraphs that correspond to configurations of 11 points in 4-dimensional space.

Start with a tree-like hypergraph H of d+1 blocks of size r like the five examples in the Figure above. The intersection of every two blocks has at most one element. The union of all blocks has n=(d+1)(r-1)+1 elements.

A rainbow coloring of a r-uniform hypergraph H is a coloring of the vertices of H with r colors so that the vertices of every edge is colored by all r colors.

Theorem 2 (Bukh, Loh, and Nivasch): It is possible to associate to the vertices of each such hypergraph H a set X of n points in \mathbb R^d so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is (r-1)!^d. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

For a star-like hypergraph where all blocks have a vertex in common we get the original Sierksma’s example. (Example (d) above.) White’s examples are obtained by considering such hypergraphs where there exists an edge A such that all edges have non empty intersection with A. (Examples (c), (d), and (e) above).

Rainbow colorings of our five examples 

Tverberg’s partitions for stretched points on the moment curve

It is natural to consider $n$ points on the moment curve x(t)=(t,t^2,\dots, t^d). It turns out that the set of Tverberg’s partitions for points on the moment curve depend on the precise location of the points. By stretched points on the moment curve I mean that  you take the points x(t_1), x(t_2), \dots x(t_n) where t_1 << t_2 << \dots t_n, namely $t_2$ is much much larger than t_1 and t_3 is much much much much larger than t_2, etc. etc. In this case, the configuration corresponds to a path H: you let the vertices be \{1,2,\dots,n\} and the edges are sets of the form \{(k-1)(r-1)+1, (k-1)(r-1)+2,\dots , k(r-1)+1\}. A stretched configuration of points on the moment curve has the property that every subset is also a stretched configuration of points on the moment curve.

The importance of Tverberg’s partitions for stretched points on the moment curve was realized by Barany and Por, by Bukh, Loh, and Nivasch, and by Perles and Sidron (See their paper Tverberg Partitions of Points on the Moment Curve), and perhaps by others as well.

Por’s universality result

Por’s universality theorem asserts that in terms of Tverberg partitions every large enough configuration of points in general position in R^d contains a configuration whose Tverberg partitions are those of a stretched configuration of n points on the moment curve! Por’s  universality result was conjectured independently by Bukh, Loh, and Nivasch, (and they gave some partial results) and by Por himself.

Theorem 3 (Por’s universality result, 2018): Every long enough sequence of points in \mathbb R^d in general position contains a subsequence  of length n whose Tverberg partitions are exactly the so called rainbow partitions.

Por actually proved an apparently stronger statement: We can find a subsequence Y so the conclusion holds not only for Y but also for every subsequence Z of Y

Staircase Convexity

The work of Bukh, Loh, and Nivasch relied on an important method of “staircase convexity”. An earlier 2001 application of the method (where it was introduced) was for lower bounds on weak epsilon nets by Bukh, Matousek, and Nivasch (Here are links to the paper, and to slides from a talk by Boris Bukh. See also this post and this one of the weak epsilon net problem.) Roughly the idea is this: consider a stretched grid where the sequence of coordinates are very very fast growing. When you choose configuration of points in such a grid, questions regarding their convex hulls translate to purely combinatorial problems.

Stairconvex sets explained by Boris Bukh

Erdos Szekeres in the plane and higher dimensions

The planar case

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that ES(n) is finite.

The finiteness of ES(n) can be stated as follows: Given a sequence of N points in general position in the plane x_1,x_2, \dots , x_N  there is a subsequence 1_i,x_2, \dots , x_n such that the line segments [x_i,x_k] and [x_j,x_\ell ] intersect. With this statement, the Erdős and Szekeres’ theorem can be seen as identifying a universal set of points in term of its Radon partitions (or equivalently in terms of its order type).

In high dimensions

In higher dimensions we can define ES_d(n) and replace “in convex position” by “in cyclic position”. The finiteness of ES_d(n) (with terrible bounds) follows easily from various Ramsey results. In a series of papers very good lower and upper bounds where obtained:  Imre BaranyJiri MatousekAttila Por: Curves in R^d intersecting every hyperplane at most d+1 timesMarek EliášJiří MatoušekEdgardo Roldán-PensadoZuzana Safernová: Lower bounds on geometric Ramsey functions; Marek Elias, Jiri Matousek: Higher-order Erdos–Szekeres theorems .

Por’s result

Por’s result can be seen as a far-reaching strengthening of the finiteness of ES_d(n).

Further Discussion:

High order order types?

Can you base a higher-order notion of “order types” on Tverberg partitions?

The order type of a sequence of n points affinely spanning R^d, is the described by the vector of signs (0, 1 or -1) of volume of simplices described by subsequences of length d+1. Equivalently the order type can be described by the minimal Radon partitions of the points.

  1. We can first ask if we can base a notion of higher order types on Tverberg’s partitions to r parts where r>2.
  2. Next we can ask for an associated notion of “higher order oriented matroids.” (Oriented matroids in the usual sense are abstract order types which coincide with Euclidean order types for every subsequence of d+3 points.)
  3. A natural question regarding these “higher order types is: If a sequence of points in strong general position is Tverberg-equivalent to stretched points on the moment curve, does it apply to all of its subsequences?

Another way to consider “higher” order types is to enlarge the family by to start with a family of points add to it all Radon points of minimal Radon’s partition and consider the order type of the new configuration. (This operation can be repeated r times.) See this paper of Michael Kallay on point sets which contain their Radon points.

Staircase convexity order types

Understanding order types of configuration of points on stretched grids of Bukh et al. is a very interesting problem. It is interesting to understand such configurations that are not in general position as well. (In particular, which matroids are supported on the stretched grid?) Of course, the method may well have many more applications.

Fantastically strong forms of Sierksma’s conjecture

Is the following true: For every sequence T of n=(r-1)(d+1)+1 points in R^d there is a Sierksma’s configuration S of $n$ points so that every Tverberg’s partition of  S is a Tverberg’s partition of T?

An even stronger version is:

Does every sequence T of (r-1)(d+1)+1 points in R^d there is a tree-like simple hypergraph so that all the rainbow coloring of H correspond to Tverberg partitions of the sequence? If true this will be a fantastically strong version of Sierksma’s conjecture.

Is the Erdős-Szekeres’ conjecture outrageous?

Erdős and Szekeres proved in 1935 that ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}, and in 1960, they showed that ES(n) \ge 2^{n-2}+1, and conjectured this to be optimal. Despite the efforts of many researchers, until recently no improvement in the order of magnitude has ever been made on the upper bound over  81 years. A  recent breakthrough result by Andrew Suk (Here are links to the paper, and to our post discussing the result) asserts that ES(n)=2^{n+o(n)}. Sometime ago I asked over MO a question on outrageous mathematical conjectures and perhaps the conjecture that  ES(n) = 2^{n-2}+1 on the nose is an example.

Original Abstracts

Continue reading

Posted in Combinatorics, Convexity | Tagged , , , , , , , | 6 Comments

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska: Universal optimality of the E8 and Leech lattices and interpolation formulas

Henry Cohn

A follow up paper on the tight bounds for sphere packings in eight and 24 dimensions. (Thanks, again, Steve, for letting me know.)

For the 2016 breakthroughs see this post, this post of John Baez, this article by Erica Klarreich on Quanta Magazine, and a Notices AMS article by  Henry Cohn   A conceptual breakthrough in sphere packing. See also, Henry Cohn’s 2010 paper Order and disorder in energy minimization, and Maryna Viazovska’s ICM 2018 videotaped lecture.

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska: Universal optimality of the E8 and Leech lattices and interpolation formulas

Abstract: We prove that the E_8 root lattice and the Leech lattice are universally optimal among point configurations in Euclidean spaces of dimensions 8 and 24, respectively. In other words, they minimize energy for every potential function that is a completely monotonic function of squared distance (for example, inverse power laws or Gaussians), which is a strong form of robustness not previously known for any configuration in more than one dimension. This theorem implies their recently shown optimality as sphere packings, and broadly generalizes it to allow for long-range interactions.

The proof uses sharp linear programming bounds for energy. To construct the optimal auxiliary functions used to attain these bounds, we prove a new interpolation theorem, which is of independent interest. It reconstructs a radial Schwartz function f from the values and radial derivatives of f and its Fourier transform \hat f at the radii √2π for integers n ≥ 1 in R^8 and n ≥ 2 in R^{24}. To prove this theorem, we construct an interpolation basis using integral transforms of quasimodular forms, generalizing Viazovska’s work on sphere packing and placing it in the context of a more conceptual theory.

Posted in Algebra, Combinatorics, Geometry, Number theory | Tagged , , , , , , , | Leave a comment

Extremal Combinatorics V: POSETS

This is the remaining post V on partially ordered sets of my series on extremal combinatorics (I,II,III,IV,VI). 

We will talk here about POSETS – partially ordered sets. The study of order is very important in many areas of mathematics starting with the order relation on the integers and reals in algebra and in Euclidean geometry. The set of all subsets of a set can be partially ordered by inclusion and this is a very basic example of posets. While the study of order and posets is a separate area on its own, parts of it are very important in extremal combinatorics and we will give a little taste here.

Dear readers, please contribute your favorite result or problem on partially ordered sets (or Sorting) in the comment session.

A chain C \subset P in a POSET is a set of elements so that every two of them are comparable. An antichain $A \subset P$ is a set of elements so that every two distinct elemenאs in A are incomparable.  (Antichains are also called independent sets.) An immediate but important Lemma is:

The immediate lemma: The intersection of a chain A and an antichain C contains at most one element. Walla!

Dilworth’s theorem

Dilworth’s theorem (DT): Every finite partially ordered P set can be covered by a(P) chains.

(By the immediate lemma, at least a(P) chains are needed.)

Dual Dilworth theorem: Every partially ordered sets can be covered by c(P) antichains.

(By the immediate lemma, at least c(P) antichains are needed.)

The proof of the dual Dilworth theorem is easy. Note that the set A_1=MIN(P) of minimal elements of P is an antichain. Let A_k = MIN (P\backslash (A_1 \cup A_2 \cup \dots A_{k-1})). We need two easy observations. First, A_k is an antichain and second: If A_k \ne \emptyset then there is a chain with one element from A_i: 1 \le i\le k. Walla!

The proof of Dilworth’s theorem is by induction on $|P|$. For the induction step you first consider the case where every antichain of maximal size is either MAX(P) or MIN (P). In this case you consider a chain with one element in MAX(P) and one element in MIN (P) and delete these elements from P. For the resulting post Q, a(Q)=a(P)-1 and we can use the induction hypothesis.

Otherwise there is an antichain A of maximum size t=a(P) which is not MAX(P) or MIN(P).  Put A=\{a_1,a_2,\dots,a_t\}. Let P^+ be the set of elements in P which are larger or equal some element in A, and let P^- be the set of elements in P which are smaller or equal some element in A.

Now,

  1. P^+ \cup P^-=P. Otherwise we could add an element to A to form a larger antichain.
  2. P^+ \cap P^- = A. Otherwise, there will be two elements of A which are comparable.

So by the induction hypothesis P^+ can be covered by t chains C_1^+, C_2^+, \dots, C_t^+ and P^- can be covered by a(P$ chains C_1^-, C_2^-, \dots, C_t^-. Bu re-indexing we can assume that both C_i^+ and C_i^- contains a_i. It follows that a_i is the minimal element in $C_i^+$ and the maximal element in $C_i^-$ and hence C_i=:C_i^+ \cup C_i^- is a chain. The t chains C_1, C_2, \dots, C_t cover P. Sababa!

An important Corollary both from Dilworth’s theorem and its dual is that

a(P) c(P) \ge |P|.

Erdos-Szekeres theorem

The fundamental Erdos Szekeres theorem asserts that if n=ab+1 then every sequence a_1,a_2,\dots ,a_n of different real numbers contains a monotone increasing sequence of length a+1 or a monotone decreasing sequence of length b+1.

There are simple proofs. For example, associate to every k a pair (I_k,D_k) of integers where  I_k is the maximum length of the increasing subsequence starting with a_k and D_k is the maximum length of the deccreasing subsequence starting with a_k. The result follows from the easy observation that all these pairs are different.

Both Dilworth’ theorem and its easy dual imply easily (in fact we need only the important corollary) the Erdos Szekeres theorem when we define the following partial order: i < k if both i<k and a_i < a_k.

Looking at Sperner’s theorem again

Sperner’s theorem asserts that the maximal size of an antichain of subsets of an n elements set is {{n} \choose {[n/2]}}. By Dilworth’s theorem it follows that we can cover all sets by {{n} \choose {[n/2]}} chains (and, of course when we exhibit such a covering it reproves Sperner’s theorem). A symmetric saturated chain decomposition is a partition of P(n) (=all subsets of [n]) to saturated chains where each chain has, for some k, sets of sizes $k,k+1,\dots,d-k$. You can build such a decomposition inductively.

Start with a decomposition for n for each chain C_i create a new chain C'_i by adding the element n+1 to every set. And then move the top set in C'_i to C_iWalla!

This is the beginning of a very beautiful story related also to the Dedekind Problem about  number of antichains in P(n).

Curtis Greene and Danny Kleitman

The Greene-Kleitman theorem

Let a_k(P) be the maximum size of the union X of k antichains in a poset P. For every chain For every chain C we have |C \cap X| \le \min\{|C|,k\}. Therefore for a partition of P to chains C_1,C_2,\dots,C_t we   have \sum\min\{|C_i|,k\ge |X|. The Greene-Kleitman theorem asserts that there is always  a decomposition into chains with \sum\min\{|C_i|,k\}=a_k(P).

The perfect graph theorem.

What is the relation between the very easy dual Dilworth theorem and the harder Dilworth theorem? As it turns out there is a very general theorem, Lovasz’ perfect graph theorem, that shows that these two theorems are equivalent.

A graph G is perfect if for every induced subgraph H, the chromatic number equals the clique number. Lovasz’ theorem  (conjectured by Claude Berge) asserts that complements of perfect graphs are perfect. The perfectness of the comparability graph of a poset amounts to the dual Dilworth theorem, and for its complement it is the Dilworth theorem. Lovasz in fact proved that perfectness is equivalent to the relation $\latex \omega(H)\cdot \alpha (H) \ge |H|$ for every induced subgraph H. (For posets this is our important corollary above.)

Jeff Kahn and Jake Baron (see here on their 2016 asymptotic solution to Tusza’s conjecture), Mike Saks, and Nati Linial

Startling theorems on POSETS: Kahn-Saks,  Linial-Saks, Linial-Kahn, and Kahn-Saks

Here  are some beautiful and important theorems on posets. An order ideas I of a post is a set of elements so that if x in I and y < x then y \in I.

Theorem (Linial-Saks, 1985): In every poset P there is an element which is contained in more than δ and less than 1-δ order ideas of P.  (Paper)

Theorem (Kahn-Saks, 1984): For every Poset P which is not a chain there are two incomparable elements x,y such that the number of linear extensions of P for which x<y is between 3/11 and 8/11. (Paper)

A simpler proof was found in the late 80s by Kahn and Linial and by Karzanov and Khachiyan. It  is  based on the Brunn Minkowski theorem and gives a weaker constant 1/2e .

Theorem (Kahn-Saks, 1987): For every finite distributive lattice L the maximum antichain is of size o(|L|). (Paper)

Lattices are special types of posets with the property that for every set of elements (pairs \{x,y\} suffice in the finite case), there is a unique minimal elements above them all (denoted for pairs by x ∧ y) and a unique maximal element (denoted for pairs by x ∨ y) below them all.

A distributive lattice is a lattice that satisfies for every x, y and z, the relation

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Birkhoff’s representation theorem asserts that finite distributive lattices can be represented as order ideals of posets (ordered by inclusion).

 

 

Posted in Combinatorics | Tagged , , , , , , , , , | 6 Comments

Konstantin Tikhomirov: The Probability that a Bernoulli Matrix is Singular

Konstantin Tikhomirov

An old problem in combinatorial random matrix theory is cracked!

Singularity of random Bernoulli matrices by Konstantin Tikhomirov

Abstract: For each n, let M_n be an n×n random matrix with independent ±1 entries. We show that

P(M_n is singular}=(1/2+o_n(1))^n,

which settles an old problem. Some generalizations are considered.

János Komlós

Background and discussion

What is the probability s(n) that a random n by n matrix with \pm 1 entries is singular? Well, it can be singular if either two rows are identical, or if two columns are identical. This happens with probability

n(n-1)(1+0(1)) \cdot 2^{-n}.

Are there other more dominant reasons for singularity? Are most \pm 1 matrices nonsingular as n tends to infinity? The first results in this direction are by Janos Komlos who first proved in 1968 that s(n)=o(1) and later that s(n)=O(1/\sqrt n). A major breakthrough came in 1995 when  Kahn , Komlos, and Szemeredi proved that s(n) \le 0.999^n. Terry Tao and Van Vu improved in 2006 the constant to 0.939 and then to (3/4+o(1)) and the, now broken, world record from 2010 was (1/\sqrt 2)+o(1))^n  by Jean Bourgain, Van Vu and Philip Wood. Congratulations Konstantin!

If you want to tease the Gods of Mathematics you can try to prove that s(n) =n(n-1)(1+o(1)) \cdot 2^{-n}? and, as suggested in the Kahn-Komlós-Szemerédi paper,  even prove an expansion  s(n) = 2{{n} \choose {2}}(\frac{1}{2})^{n}+2{{n}\choose {4}} (\frac{3}{8})^n\cdots based on dependencies between k-tuples of rows and columns.

Let me mention that  Kevin Costello, Tao, and Vu, proved in 2005 that  random symmetric matrices are almost surely non-singular.  This is related to beautiful mathematics.  Tao and Vu also proved that the probability for vanishing of the permanent of a Bernoulli matrix is o(1). I am not sure what the proven behavior for permanents is and one may expect that vanishing of the permanent occurs in probability which is super exponentially small. (Perhaps C/\sqrt {n!}.)

Here are related posts on Tao’s blog What’s New. A post on Tao’s Milliman’s lecture on the additive combinatorics and random matrices; On the permanent of random Bernoulli matrix;

Determinants and the guaranteed cancellation phenomenon

The value of the determinant of a Bernoulli matrix is the sum of n! ±1 terms. So we can guess that the expected value will be around \sqrt {n!}, and with high probability it is near the expected value. There is something special about the determinant which we can call the Guaranteed Cancellation Phenomenon (GCP). The value of the determinant of a Bernoulli  matrix is at most n^{n/2} which is not that much larger than \sqrt {n!}. (GCP applies to matrices with real or complex variables with rows with prescribed  \ell_2 norms.)  Guaranteed cancellation is a very interesting mathematical phenomenon in various contexts. (For example, the prime number theorem and the Riemann hypothesis are about guaranteed cancellation.) The determinant itself is a polynomial of degree n with n^2 variables , and GCP for determinants was one of the starting points in a paper that I wrote with Leonard Schulman on quasi-random multilinear polynomials. (For other examples of GCP see also this MO question and various posts  on Mobius randomness.) Maybe it is time to ask on MathOverflow for a list of places were GCP  is expected or proven.)

Sperner, the Littlewood-Offord problem, and additive combinatorics

The determinant of a \pm 1 matrix is the signed sum of n minors. It follows from Sperner’s theorem that if m of these minors are non-zero then the probability that the sum vanishes is O(1/\sqrt m). This is the idea behind Komlos’ second proof. The relevant general question (backward Littlewood Offord  problem) which is of much independent interest is “Under which conditions on a sequence a_1,a_2, \dots, a_n we can guarantee that the probability that a signed sum of the sequence vanished (or has a small absolute value) is small.” The famous Erdos-Moser conjecture (solved on the nose by Stanley using the Hard Lefschetz theorem, sharpening a result by Sárközy and Szemerédi) asserts that if the elements of the sequence are distinct then the larger vanishing probability is attained by the sequence of integers between -[n/2] and +[n/2]. In this case (like for any arithmetic progression) the vanishing probability is n^{-3/2}.  Kahn, Komlos and Szemeredi relied on (and extended)  a theory by  Gábor Halász for guaranteeing that the vanishing probability is small (exponentially small) and, of course, much work is needed to prove that Halász-type conditions are satisfied.

I was excited by the 2005 solution for symmetric matrices also because it involved a quadratic version of Littlewood-Offord type results which are of much independent interest. I think that there are many interesting remaining open problems.

 

Posted in Combinatorics, Probability | Tagged | 2 Comments