Design a site like this with
Get started

Welcome to My New Blog

Hi all! I finally decided to have some blog with mathematical notes (I do not want to publish anything not concerning mathematics here, in particular this is why everything is assumed to be in “English”). I would continue on, but unfortunately livejournal does not support formulae and the easiest way to fix it seems to crosspost from here.


Approximation of a symmetric convex body by polytopes

Let K be an origin-symmetric symmetric convex body in \mathbb{R}^d, \varepsilon>0. What is the optimal upper bound for the number of vertices of the convex polytope L satisfying K\subset L\subset (1+\varepsilon)K? Here we may consider both large d and small \varepsilon. As far as I understand, in full generality the 2-parametric asymptotic is still open, see some recent results and a survey in the paper of Alexander Barvinok. UPDATE: Sasha Polyanskii immediately informed me about the result by Fedja Nazarov, Dima Ryabogin and Márton Naszódi where the sharp estimate is obtained.

Consider the fixed d regime. Recently I asked the participants of Online IMC 2020 to prove the O(\varepsilon^{1-d}) bound and I found out from the discussions after the contest that the sharp order is \varepsilon^{(1-d)/2}. The goal of this post is to share a nice argument for that borrowed from the paper by Bronstein and Ivanov (Siberian Math. Journal 1975), and a bit simplified. The lower bound is realised already for the Euclidean sphere, it is easy (each vertex a of L can see only O(\varepsilon^{(d-1)/2}) part of \partial K).

First of all, we make a linear transform so that the John ellipsoid of K is a unit ball B, now B\subset K\subset \sqrt{d}B.

K+\varepsilon B is contained in (1+\varepsilon)K and thus it suffices to find O(\varepsilon^{(1-d)/2}) points in K+\varepsilon B whose convex hull contains K. The idea is to use the parallel surface.

Namely, consider the boundary \Gamma of the set K+B and choose a minimal (by cardinality) \sqrt{\varepsilon}-net on \Gamma, denote it by T. We have |T|=O(\varepsilon^{(1-d)/2}) (since \Gamma is bi-Lipschitz equivalent to the surface of the unit cube, for example). For a\in T denote by n_a the outer normal to K+B at x (it is unique, but we do not use this), that is, such a unit vector that

\langle a,n_a\rangle=\max_{K+B} \langle \cdot,n_a\rangle= \max_{K} \langle \cdot,n_a\rangle +\max_{B} \langle \cdot,n_a\rangle=\max_{K} \langle \cdot,n_a\rangle+1.

It means that a=x_a+n_a, where n_a is an outer normal at x_a for the set K (there may exist other outer normals at x_a). The point f(a):=x_a+\varepsilon n_a belongs to K+\varepsilon B. Define L={\rm conv} \{f(a):a\in T\}. It suffices to prove that K\subset L if we assume \varepsilon<1/4. By convex duality, K\subset L is equivalent to

\max_L \langle \cdot,n\rangle \geqslant \max_K \langle \cdot,n\rangle\quad\quad (1)

for any unit vector n. For fixed n let x be a point on \partial K such that \langle x,n\rangle is maximal. We have x+n\in \Gamma, thus there exists a=x_a+n_a\in T such that

\varepsilon\geqslant |(x+n)-(x_a+n_a)||^2=\|x-x_a\|^2+\|n-n_a\|^2+2\langle x-x_a,n\rangle+2\langle x_a -x,n_a\rangle.

We have \langle x-x_a,n\rangle\geqslant 0 and \langle x_a-x,n_a\rangle\geqslant 0, thus

\varepsilon\geqslant \varepsilon+ 2\langle x_a-x,n\rangle \geqslant |n-n_a|^2 \geqslant 0,

in particular |n-n_a|\leqslant \sqrt{\varepsilon}<1/2 since \varepsilon<1/4. Thus for f(a)=x_a+\varepsilon n_a\in L we have

\langle f(a),n\rangle=\langle x_a+\varepsilon n_a,n\rangle=\langle x,n\rangle+\langle x_a-x,n\rangle +\varepsilon+\varepsilon\langle n_a-n,n\rangle \geqslant \langle x,n\rangle+\varepsilon/2+\varepsilon\langle n_a-n,n\rangle\geqslant \langle x,n\rangle

and (1) for n is proved.


Hi there!

Today we prove that A_1A_2+A_3A_4=A_2A_3+A_1A_4
in an arbitrary tetrahedron A_1A_2A_3A_4.

Draw three planes: through A_2 orthogonal to the external bisector of \angle A_1A_2A_3, through A_3 orthogonal to the external bisector of \angle A_2A_3A_4, through A_4 orthogonal to the external bisector of \angle A_3A_4A_1.

Let them meet at point I, and let Q_1,Q_2,Q_3,Q_4 be projections of I onto lines A_1A_2,A_2A_3,A_3A_4,A_4A_1 respectively (see the picture).

We have IQ_1=IQ_2=IQ_3=IQ_4 and also A_2Q_1=A_2Q_2, A_3Q_2=A_3Q_3, A_4Q_3=A_4Q_4 by construction (the segments are directed in the natural sense: either Q_1,Q_2 both belong to rays A_2A_1,A_2A_3 respectively, or both do not, and so on). Also the right triangles \triangle A_1IQ_1,\triangle A_1IQ_4 are equal by hypotenuse and cathetus. Thus A_1Q_1=A_1Q_4 and


Well, possibly our three planes do not have a common point, that is, the external bisectors of angles \angle A_1A_2A_3, \angle A_2A_3A_4, \angle A_3A_4A_1 are complanar? Then start with arbitrary point Q_1\in A_1A_2, choose Q_2\in A_2A_3, Q_3\in A_3A_4 so that A_2Q_1=A_2Q_2, A_3Q_2=A_3Q_3, A_4Q_3=A_4Q_4. The lines Q_1Q_2,Q_2Q_3,Q_3Q_4 are parallel to aforementioned three external bisectors, thus the points Q_1,Q_2,Q_3,Q_4 are complanar and again A_1Q_1=A_1Q_4, now due to Menelaus theorem for this plane \alpha:

\frac{A_1Q_1}{A_1Q_4} =\frac{A_1Q_1}{A_2Q_1}\cdot \frac{A_2Q_2}{A_3Q_2}\cdot \frac{A_3Q_3}{A_4Q_3}\cdot \frac{A_4Q_4}{A_1Q_4}=\frac{d(A_1,\alpha)}{d(A_2,\alpha)}\cdot \frac{d(A_2,\alpha)}{d(A_3,\alpha)}\cdot \frac{d(A_3,\alpha)}{d(A_4,\alpha)}\cdot \frac{d(A_4,\alpha)}{d(A_1,\alpha)}=1.

UPDATE: the real tetrahedron stuff is discussed here


Mathematicians do like giving proofs of known results from some specific point of view.

Here goes the combinatorial proof of the inequality

e\leqslant \pi. \quad \quad (1)

To be precise, I define our heroes. \pi is a length of a half-circle of the unit radius, and e is the common point of the segments [(1+1/n)^n,(1+1/n)^{n+1}], n=1,2,\ldots

The idea is that for a positive integer n and a complex q, |q|\leqslant 1, we have

{\displaystyle A:=\left|1\cdot (1+q)(1+q+q^2)\cdot \ldots  \cdot (1+q+\ldots+q^{n-1})\right| \leqslant n!\leqslant n^2(n/e)^{n-1}.}

The latter inequality is obtained by multiplying the definitive inequalities e\leqslant (1+1/k)^{k+1} for k=1,2,\ldots,n-1.

We apply it for q=e^{i\pi/n}, the primitive root of unity of degree 2n.

Note that |1-q|< \pi/n, since the chord of the unit circle joining 1 and q is shorter than the arc between these two points (which equals \pi/n, since the whole circle is a union of 2n congruent arcs.)

We have {\displaystyle B:=(1-q)(1-q^2)\cdot \ldots \cdot(1-q^{2n-1})=\prod_{w^{2n}-1=0, w\ne 1} (1-w)=(z^{2n}-1)'|_{z=1}=2n.}

On the other hand, since q^n=-1 and 1-q^{n+k} is the complex conjugate to 1-q^{n-k} for k=1,\ldots,n-1, we get

2n=B=2\left|(1-q)(1-q^2)\ldots (1-q^{n-1})\right|^2 =2|1-q|^{2n-2}A^2\leqslant 2(\pi/n)^{2n-2}n^4(n/e)^{2n-2}.

Thus (e/\pi)^{2n-2}\leqslant n^{3} that yields (1) as (e/\pi)^{2n-2} would grow exponentially fast if e>\pi.

Well, if you really prefer combinatorial proofs, here is a variant of the above argument for you. Although I do not provide any combinatorial quantity counted by \pi-e (that what we expect from a combinatorial proof of inequality (1)), I instead do this for something like (n/e)^n-(n/\pi)^n.

Count the number N of permutations of 1,\ldots,n for which the number of inversions is divisible by 2n. Since

\sum_{\pi\in S_n} x^{inv(\pi)}=1\cdot (1+x)(1+x+x^2)\cdot \ldots  \cdot (1+x+\ldots+x^{n-1})

is a generating polynomial for the number of permutations with the given number of inversions, by the polarization formula

[x^a]f+[x^{a+m}]f+[x^{a+2m}]f+\ldots=m^{-1}\sum\limits_{w^m=1} w^{-a}f(w), 0\leqslant a<m, f(x)\in\mathbb{C}[x],

for a=0,m=2n we get

N=(2n)^{-1}\sum_{w:w^{2n}=1} 1\cdot (1+w)(1+w+w^2)\cdot \ldots  \cdot (1+w+\ldots+w^{n-1}).

If e>\pi, we see that the summands corresponding to w=e^{\pm i\pi/n} are negative reals provided that n=8k+5 (this follows from evaluating the argument of 1+q+\ldots+q^{\ell}, which equals \frac{\ell\pi}{2n}, and summing over \ell=1,2,\ldots,n-1: we get \frac{(n-1)n\pi}{4n} that is \pi modulo 2\pi for n=8k+5). By absolute value they are exponentially greater both than n! (which corresponds to w=1, see the explanation above) and all other summands (since say |1-w|>(3/2)|1-q| for other roots, and |(1-w)(1-w^2)\ldots (1-w^n)| is either 0 or the same as |(1-q)(1-q^2)\ldots(1-q^n)|. So we get N<0 that is absurd.

Low-level variant of Huang’s argument for sensitivity conjecture

Consider the set \Omega_n of all 2^n words t_1t_2\ldots t_n,\, t_i\in \{0,1\}, over the alphabet \{0,1\} (the vertices of Boolean cube). We naturally multiply the words by concatenation: if x\in \Omega_n, y\in \Omega_k, then xy\in \Omega_{n+k}. For i=1,2,\ldots,n and x\in \Omega_n denote by T_ix the word which differs from T_ix only in i-th position. Clearly the operators T_i,i=1,\ldots,n are involutive and mutually commute. We further use the same notations T_i for different values of n (namely, both for n and n-1.) We say that x,y are joined by an edge if y=T_ix for some i=1,\ldots,n. This graph (the skeleton of the Boolean cube) is bipartite by the chessboard coloring. In particular, it contains an independent subset of size 2^{n-1}.

The recent sensational result by Hao Huang is that if we take a subset A\subset \Omega_n, |A|=2^{n-1}+1, the induced subgraph on this subset already contains a vertex of degree at least \sqrt{n}. That is sharp by the earlier example of F. R. K. Chung, Z. Füredi, R. L. Graham and P. Seymour.

Everybody is very excited since this estimate settles the so called sensitivity conjecture, and this is not what I am going to tell about (cause of complete ignorance.)

The aim of this post is to give an explicit exposition of Huang’s argument without using any theorems but the following: the linear system of m equations and m+1 variables has a non-trivial solution.

Following Huang, we take a not-everywhere-zero function f:\Omega_n\to \mathbb{R} which vanishes outside A and satisfies some (other) 2^{n-1} linear relations. Such a function exists by the aforementioned theorem. For describing these relations, we define w_i(x)=(-1)^{t_1+\ldots+t_{i-1}} for x=t_1\ldots t_k\in \Omega_{k},i=1,\ldots,k. Clearly w_i(x)=w_i(T_ix) and the straightforward but crucial property is

\displaystyle w_i(x)w_j(x)w_j(T_ix)w_i(T_jx)=-1\,\,\text{for}\,i\ne j. \quad \quad\quad (\star)

Now we are ready to formulate the 2^{n-1} relations on f, they are the following:

\displaystyle \sqrt{n}f(y)=\sum_{i=1}^{n}w_i(y)f(T_i y),\,\,\text{for all}\, y\in \Omega_{n}.\quad (1)

You may say that the number of relations is 2^{n}, but actually the relations (1) for y starting from 0, say y=0x,x\in \Omega_{n-1}, which read as:

\displaystyle f(1x)=\sqrt{n}f(0x)-\sum_{i=1}^{n-1}w_i(x)f(0T_ix),x\in \Omega_{n-1},\quad (2)

imply relations (1) for y=1x,x\in \Omega_{n-1}:

\displaystyle f(0x)=\sqrt{n}f(1x)+\sum_{i=1}^{n-1}w_i(x)f(1T_ix),x\in \Omega_{n-1}.\quad (3)

This reduces to (\star) after we express f(1x),f(1T_ix) via the values f(0T_iT_jx). Indeed, Right Hand Side of (3) reads as


the coefficient of f(0x) in this expression equals \sqrt{n}\cdot \sqrt{n}-\sum_{i=1}^{n-1} w_i(x)w_i(T_ix)=1. The coefficient of f(0T_ix) is -\sqrt{n}w_i(x)+\sqrt{n}w_i(x)=0 for all i=1,\ldots,n-1. Finally for i\ne j the coefficient of f(0T_iT_jx) equals -w_i(x)w_j(T_ix)-w_j(x)w_i(T_jx)=0 by (\star).

Now if y\in \Omega_n is chosen so that |f(y)| is maximal, we have y\in A and looking at the right hand side we conclude that at least \sqrt{n} words of the form T_i y must belong to the support of f, thus to A. The proof is complete.

Of course the reason why 2^{n-1} equations (2) imply the other 2^{n-1} equations (3) is that the corresponding to (1) operator f(y)\mapsto \sum_{i=1}^{n}w_i(y)f(T_i y) has an eigensubspace of dimension 2^{n-1} for the eigenvalue \sqrt{n}. Or viceversa, if you prefer. I cannot say that I understand well where does this operator come from.