Fedya Petrov's blog

Featured

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 rus4.livejournal.com, 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.

Euler’s proof of pentagonal theorem

tetrahedron

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

$A_1A_2+A_3A_4=A_1Q_1+A_2Q_1+A_3Q_3+A_4Q_3=A_1Q_4+A_2Q_2+A_3Q_2+A_4Q_4=A_1A_4+A_2A_3.$

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

e⩽π

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

$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 $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

$\sqrt{n}(\sqrt{n}f(0x)-\sum_{i=1}^{n-1}w_i(x)f(0T_ix))+\sum_{i=1}^{n-1}w_i(x)(\sqrt{n}f(0T_ix)-\sum_{j=1}^{n-1}w_j(T_ix)f(0T_jT_ix)).$

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.