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 be an origin-symmetric symmetric convex body in , What is the optimal upper bound for the number of vertices of the convex polytope satisfying ? Here we may consider both large and small . 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 regime. Recently I asked the participants of Online IMC 2020 to prove the bound and I found out from the discussions after the contest that the sharp order is . 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 of can see only part of ).

First of all, we make a linear transform so that the John ellipsoid of is a unit ball , now .

is contained in and thus it suffices to find points in whose convex hull contains . The idea is to use the *parallel surface*.

Namely, consider the boundary of the set and choose a minimal (by cardinality) -net on , denote it by . We have (since is bi-Lipschitz equivalent to the surface of the unit cube, for example). For denote by the outer normal to at (it is unique, but we do not use this), that is, such a unit vector that

It means that , where is an outer normal at for the set (there may exist other outer normals at ). The point belongs to . Define It suffices to prove that if we assume . By convex duality, is equivalent to

for any unit vector . For fixed let be a point on such that is maximal. We have , thus there exists such that

We have and , thus

in particular since . Thus for we have

and (1) for is proved.

## Euler’s proof of pentagonal theorem

## tetrahedron

Hi there!

Today we prove that

in an arbitrary tetrahedron .

Draw three planes: through orthogonal to the external bisector of , through orthogonal to the external bisector of , through orthogonal to the external bisector of .

Let them meet at point , and let be projections of onto lines respectively (see the picture).

We have and also , , by construction (the segments are directed in the natural sense: either both belong to rays respectively, or both do not, and so on). Also the right triangles are equal by hypotenuse and cathetus. Thus and

Well, possibly our three planes do not have a common point, that is, the external bisectors of angles are complanar? Then start with arbitrary point , choose , so that , , . The lines are parallel to aforementioned three external bisectors, thus the points are complanar and again , now due to Menelaus theorem for this plane :

.

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

To be precise, I define our heroes. is a length of a half-circle of the unit radius, and is the common point of the segments

The idea is that for a positive integer and a complex , , we have

The latter inequality is obtained by multiplying the definitive inequalities for

We apply it for , the primitive root of unity of degree .

Note that since the chord of the unit circle joining 1 and is shorter than the arc between these two points (which equals , since the whole circle is a union of congruent arcs.)

We have

On the other hand, since and is the complex conjugate to for , we get

Thus that yields (1) as would grow exponentially fast if .

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 (that what we expect from a combinatorial proof of inequality (1)), I instead do this for something like .

Count the number of permutations of for which the number of inversions is divisible by . Since

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

for we get

If , we see that the summands corresponding to are negative reals provided that (this follows from evaluating the argument of , which equals , and summing over : we get that is modulo for ). By absolute value they are exponentially greater both than (which corresponds to , see the explanation above) and all other summands (since say for other roots, and is either 0 or the same as . So we get that is absurd.

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

Consider the set of all words , over the alphabet (the vertices of Boolean cube). We naturally multiply the words by concatenation: if , then . For and denote by the word which differs from only in -th position. Clearly the operators are involutive and mutually commute. We further use the same notations for different values of (namely, both for and .) We say that are joined by an edge if for some . This graph (the skeleton of the Boolean cube) is bipartite by the chessboard coloring. In particular, it contains an independent subset of size .

The recent sensational result by Hao Huang is that if we take a subset , the induced subgraph on this subset already contains a vertex of degree at least . 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 equations and variables has a non-trivial solution.

Following Huang, we take a not-everywhere-zero function which vanishes outside and satisfies some (other) linear relations. Such a function exists by the aforementioned theorem. For describing these relations, we define for . Clearly and the straightforward but crucial property is

Now we are ready to formulate the relations on , they are the following:

You may say that the number of relations is , but actually the relations (1) for starting from 0, say , which read as:

imply relations (1) for :

This reduces to () after we express via the values . Indeed, Right Hand Side of (3) reads as

the coefficient of in this expression equals . The coefficient of is for all . Finally for the coefficient of equals by .

Now if is chosen so that is maximal, we have and looking at the right hand side we conclude that at least words of the form must belong to the support of , thus to . The proof is complete.

Of course the reason why equations (2) imply the other equations (3) is that the corresponding to (1) operator has an eigensubspace of dimension for the eigenvalue . Or viceversa, if you prefer. I cannot say that I understand well where does this operator come from.