Back to more reasonable mathematics.
One of the beautiful and fascinating things about planar percolation is the existence of rational critical exponents, i.e. powers in the polynomial decay of quantities at criticality. For instance, consider this statement:
Theorem: On the hexagonal grid, color each cell black or white with probability 1/2. Then the probability that the origin is connected to a cell at distance N from it decays as N^{-5/48+o(1)}.
This result was first proved here as a consequence of conformal invariance (e.g. Cardy's formula) proved by Smirnov (here is a modern exposition of his proof). Some other exponents, for example, the full-plane two-arm exponent (corresponding to the probability of having both a white and a black path of cells to distance N), are easier to compute, see this paper. All computations of arm exponents followed the same strategy: use Cardy's formula to show SLE_6 convergence of interfaces and then compute the corresponding "continuous" version of exponents for the SLE_6 process. At this point it usually doesn't matter if \kappa=6 or not.
The question then boils down to some PDE computation which an observable of SLE_\kappa satisfies. One prominent exponent which was not computed in this way is the so-called backbone exponent: corresponding to the probability of having two disjoint arms to distance N. The problem isn't that the stochastic calculus is harder for this case but rather that the PDE question couldn't be answered. Here is the PDE question (see page 16 here):
Let T be the triangle given by {x>0, y>0, x+y<2*\pi}. Consider an operator
D:=3(\partial_x^2-2\partial_x\partial_y+\partial_y^2)+\cot{(x/2)}\partial_x-\cot{(y/2)}\partial_y
Then the backbone exponent is the unique \lambda > 0 such that -\lambda is the eigenvalue corresponding to a non-negative function G(x, y) on T with boundary conditions
G(x, 2*\pi-x) = 0, G(0, y) = 1, \partial_y G(x, 0) = 0.
==================
The authors, smart as they are, couldn't solve this PDE explicitly and so no formula for the backbone exponent was known. It had been assumed to be 6/17 (though I struggle to find any explicit conjectures about it from mathematicians, only from some physicists from 80's and 90's) but later simulations showed this is likely not the case. Very recently the following result was proved using Liouville quantum gravity (LQG) techniques:
Theorem: Backbone exponent is equal to (x^2-1)/12, where x \in (2, 3) is the unique root of
\sqrt{3}*x/4+\sin(2\pi x / 3) = 0.
Given how complicated the proof is, a natural question to ask is: Could this implicitly given value suggest something about the solution of the PDE, leading to a much simpler derivation of the exponent?
One of the beautiful and fascinating things about planar percolation is the existence of rational critical exponents, i.e. powers in the polynomial decay of quantities at criticality. For instance, consider this statement:
Theorem: On the hexagonal grid, color each cell black or white with probability 1/2. Then the probability that the origin is connected to a cell at distance N from it decays as N^{-5/48+o(1)}.
This result was first proved here as a consequence of conformal invariance (e.g. Cardy's formula) proved by Smirnov (here is a modern exposition of his proof). Some other exponents, for example, the full-plane two-arm exponent (corresponding to the probability of having both a white and a black path of cells to distance N), are easier to compute, see this paper. All computations of arm exponents followed the same strategy: use Cardy's formula to show SLE_6 convergence of interfaces and then compute the corresponding "continuous" version of exponents for the SLE_6 process. At this point it usually doesn't matter if \kappa=6 or not.
The question then boils down to some PDE computation which an observable of SLE_\kappa satisfies. One prominent exponent which was not computed in this way is the so-called backbone exponent: corresponding to the probability of having two disjoint arms to distance N. The problem isn't that the stochastic calculus is harder for this case but rather that the PDE question couldn't be answered. Here is the PDE question (see page 16 here):
Let T be the triangle given by {x>0, y>0, x+y<2*\pi}. Consider an operator
D:=3(\partial_x^2-2\partial_x\partial_y+\partial_y^2)+\cot{(x/2)}\partial_x-\cot{(y/2)}\partial_y
Then the backbone exponent is the unique \lambda > 0 such that -\lambda is the eigenvalue corresponding to a non-negative function G(x, y) on T with boundary conditions
G(x, 2*\pi-x) = 0, G(0, y) = 1, \partial_y G(x, 0) = 0.
==================
The authors, smart as they are, couldn't solve this PDE explicitly and so no formula for the backbone exponent was known. It had been assumed to be 6/17 (though I struggle to find any explicit conjectures about it from mathematicians, only from some physicists from 80's and 90's) but later simulations showed this is likely not the case. Very recently the following result was proved using Liouville quantum gravity (LQG) techniques:
Theorem: Backbone exponent is equal to (x^2-1)/12, where x \in (2, 3) is the unique root of
\sqrt{3}*x/4+\sin(2\pi x / 3) = 0.
Given how complicated the proof is, a natural question to ask is: Could this implicitly given value suggest something about the solution of the PDE, leading to a much simpler derivation of the exponent?
Some news from the world of additive combinatorics: polynomial Freiman–Ruzsa conjecture in \F_2^n was recently proved by Timothy Gowers, Ben Green, Freddie Manners, and Terrence Tao. Moreover, the constants are very explicit; they prove that
If a set A\subset \F_2^n has doubling constant at most K (i.e. |A+A| <= K|A|) then A can be covered by at most 2*K^12 cosets of some subgroup H\subset \F_2^n of size at most |A|.
If a set A\subset \F_2^n has doubling constant at most K (i.e. |A+A| <= K|A|) then A can be covered by at most 2*K^12 cosets of some subgroup H\subset \F_2^n of size at most |A|.
See also a paper A Counterexample to a Strong Variant of the Polynomial Freiman-Ruzsa Conjecture in Euclidean Space for a discussion of the analogous conjecture in \R^n.
Given an n-dimensional cube, any k-dimensional central section which is close to being a sphere (I.e sandwiched between a sphere and its dilate by a factor of 1.1 say) must have k<5*log(n)
Proof sketch: Let T: L^2(\R^k) --> L^\infty (\R^n) be the embedding together with a dilation mapping the boundary of the section to almost the unit sphere of \R^k. Then |x|_{L^2(\R^k)} and |Tx|_{L^\infty(\R^n)} are within 1.1 factor from each other for any vector x in the section. Consider T*, a mapping from the dual spaces, i.e. T*: L^1 (\R^n) --> L^2(\R^k). Then e_j\in L^1 (\R^n) is mapped to some vector y_j\in L^2(\R^k) which is almost of norm 1. We claim that any point y in the unit sphere of L^2(\R^k) is close to one of \pm y_j which ensures that n (half of the number of points \pm y_j) is exponentially large in terms of k.
Indeed, any point x on the boundary of the section has one coordinate (in \R^n) equal to \pm 1, which means that |<x, e_j>|=1. Since T is almost an isometry, Tx has large L^2 scalar product with \pm y_j, which implies that Tx is close to \pm y_j. Since Tx can approximate, within a factor of 1.1, any point on the unit sphere of L^2(\R^k), this completes the proof.
=========
This shows that cubes are asymptotically the worst for Dvoretzky's theorem: Any centrally symmetric convex body in \R^n has a section of dimention at least C(\eps)*log(n) which is 1+\eps close to a sphere (This quantitative version was only later shown by Milman, who also showed that a random section works).
In some sense a cube is a fundamental counterexmaple: If you're OK with the section being close to either a sphere or a cube (i.e. to an L^2 or an L^\infty unit sphere) then N.Alon and Milman show that a much large dimensional section (with dimension k=e^{C(\eps)*\sqrt{\log{n}}}) is possible.
Proof sketch: Let T: L^2(\R^k) --> L^\infty (\R^n) be the embedding together with a dilation mapping the boundary of the section to almost the unit sphere of \R^k. Then |x|_{L^2(\R^k)} and |Tx|_{L^\infty(\R^n)} are within 1.1 factor from each other for any vector x in the section. Consider T*, a mapping from the dual spaces, i.e. T*: L^1 (\R^n) --> L^2(\R^k). Then e_j\in L^1 (\R^n) is mapped to some vector y_j\in L^2(\R^k) which is almost of norm 1. We claim that any point y in the unit sphere of L^2(\R^k) is close to one of \pm y_j which ensures that n (half of the number of points \pm y_j) is exponentially large in terms of k.
Indeed, any point x on the boundary of the section has one coordinate (in \R^n) equal to \pm 1, which means that |<x, e_j>|=1. Since T is almost an isometry, Tx has large L^2 scalar product with \pm y_j, which implies that Tx is close to \pm y_j. Since Tx can approximate, within a factor of 1.1, any point on the unit sphere of L^2(\R^k), this completes the proof.
=========
This shows that cubes are asymptotically the worst for Dvoretzky's theorem: Any centrally symmetric convex body in \R^n has a section of dimention at least C(\eps)*log(n) which is 1+\eps close to a sphere (This quantitative version was only later shown by Milman, who also showed that a random section works).
In some sense a cube is a fundamental counterexmaple: If you're OK with the section being close to either a sphere or a cube (i.e. to an L^2 or an L^\infty unit sphere) then N.Alon and Milman show that a much large dimensional section (with dimension k=e^{C(\eps)*\sqrt{\log{n}}}) is possible.
Let {x} denote the fractional part of x. Then for any positive real numbers x_1,\dots, x_n one has
\sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp.
The inequality is taken from here, an elementary proof is given by Fedya, and a different approach which leads to a weaker bound is outlined by another Fedya.
\sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp.
The inequality is taken from here, an elementary proof is given by Fedya, and a different approach which leads to a weaker bound is outlined by another Fedya.
Math from Krach
Let {x} denote the fractional part of x. Then for any positive real numbers x_1,\dots, x_n one has \sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp. The inequality is taken from here, an elementary proof is given by Fedya, and…
Here is a question related to the approach with Bochner’s theorem (see Fedya’s comment): Is it possible to find a positive majorant g(t)>=({e^t}+{e^(-t)})/2 such that it’s a Fourier transform of a signed measure \mu with \mu_+(\R) exactly equal to 9/14?
A conference is happening in Geneva right now with the usual crowd (+Michael Aizenman). Listening to a talk by Gady Kozma right now. He formulates the following very general conjecture:
Given a finite graph G and a collection of probabilities p_e\in (0, 1) indexed by edges of G, for the (edge) Bernoulli percolation with these probabilities, for any two vertices v, b and a set of vertices A\subset V(G) the following inequality for connection probabilities holds:
P(v <---> b) \geq P(v <---> A)*min_{a\in A} P(a<-->b).
The main theorem of his talk is then
Theorem: Conjecture above implies that \theta(p_c)=0 on \Z^d for any d>=2, i.e. there is no infinite cluster at criticality for the Bernoulli percolation on \Z^d.
Note that this is known for d=2 (via RSW theory) and d>=10 (via lace expansion) and the specific case d=3 remains one of the most prominent open problems in probability.
Given a finite graph G and a collection of probabilities p_e\in (0, 1) indexed by edges of G, for the (edge) Bernoulli percolation with these probabilities, for any two vertices v, b and a set of vertices A\subset V(G) the following inequality for connection probabilities holds:
P(v <---> b) \geq P(v <---> A)*min_{a\in A} P(a<-->b).
The main theorem of his talk is then
Theorem: Conjecture above implies that \theta(p_c)=0 on \Z^d for any d>=2, i.e. there is no infinite cluster at criticality for the Bernoulli percolation on \Z^d.
Note that this is known for d=2 (via RSW theory) and d>=10 (via lace expansion) and the specific case d=3 remains one of the most prominent open problems in probability.
In fact, the following weaker conjecture suffices for the \theta(p_c) result:
For any \eps>0 there exists \delta>0 such that if P(v<--->A)>1-\delta and P(a<--->b)>1-\delta for each a\in A, then P(v<--->b)>1-\eps.
For any \eps>0 there exists \delta>0 such that if P(v<--->A)>1-\delta and P(a<--->b)>1-\delta for each a\in A, then P(v<--->b)>1-\eps.
A Phase Transition for Repeated Averages
Take a vector (x_1,...,x_n) of real numbers (with n large) and at each step take two uniformly chosen indices i, j and replace both x_i and x_j with (x_i+x_j)/2. How fast does the process converge to the vector with all coordinates (x_1+...+x_n)/n in L^1?
It sort of depends on the vector, so let's think about the worst case (1, 0, ..., 0). Turns out the answer is n\log_2{n}/2 with a threshold window of order n\sqrt{\log{n}}, which is rather large
Take a vector (x_1,...,x_n) of real numbers (with n large) and at each step take two uniformly chosen indices i, j and replace both x_i and x_j with (x_i+x_j)/2. How fast does the process converge to the vector with all coordinates (x_1+...+x_n)/n in L^1?
It sort of depends on the vector, so let's think about the worst case (1, 0, ..., 0). Turns out the answer is n\log_2{n}/2 with a threshold window of order n\sqrt{\log{n}}, which is rather large
I was creating an Olympiad maths problem recently, it was “something something if both q and 2q^2+7 are prime” and was completely sure that q=5 works…
Some people never learn from other people’s mistakes, I guess!
Some people never learn from other people’s mistakes, I guess!
Asymptotic spectra: Theory, applications and extensions a survey by Avi Wigderson and Jeroen Zuiddam
I learned about it from an abstract of a talk which is to be given soon at Princeton by Daniel Zhu.
Here is the abstract:
What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.
What does all of this have to do with affine schemes you may ask. The answer is: Let's find out!
I learned about it from an abstract of a talk which is to be given soon at Princeton by Daniel Zhu.
Here is the abstract:
What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.
What does all of this have to do with affine schemes you may ask. The answer is: Let's find out!
Alon–Krivelevich–Sudakov Conjecture (paper):
For every fixed graph H there exists a positive constant c_H such that the chromatic number of any graph G with maximum degree d that contains no copy of H is at most c_H*d/log(d).
For every fixed graph H there exists a positive constant c_H such that the chromatic number of any graph G with maximum degree d that contains no copy of H is at most c_H*d/log(d).
Suppose a function f: \Z^d --> \F_2 is discrete harmonic. What is the smallest possible dimension of the support of this function?
Equivalently, what is the smallest possible dimension of a set X\subset \Z^d such that any y\in \Z^d has even number of neighbours in X? (equivalence is given by passing to the support of the function)
Here is a cool example of such a set of dimension 1+\log_2{d} from Stanislav Krymskii (paper):
Consider sets T_k:={ \pm 2^k e_1, \pm 2^k e_2, ..., \pm 2^k e_d} consisting of all the basis vectors and their opposites scaled by a factor of 2^k. Then let X_k=T_0+...+T_k be the Minkowski sum of the first k+1 of T_i's. Sets X_k are nested (i.e. X_k\subset X_{k+1}, as follows from the observation that \pm 2^k e_i = \mp 2^k e_i + \pm 2^{k+1} e_i) and their union X_\infity provides an example of an \F_2-valued harmonic function on \Z^d with support of dimnesion 1+log_2(d).
To see that the characteristic function of X is indeed discrete harmonic (as a function in \F_2), we need a simple observation that X_{k+1}\setminus X_k only contains points far from the origin together with the fact that \Delta X_{k-1} = T_k, i.e. the only points y\in \Z^d which have odd number of neighbours in X_{k-1} are precisely the points of T_k.
This latter fact can be most elegantly proved by looking at Laurent polynomials over \F_2 corresponding to sets, i.e. given a finite set X look at the Laurent polynomial in variables x_1,..., x_d with a monomial \prod x_i^{t_i} corresponding to a point (t_1,...t_n)\in X. Then looking at the Laplacian corresponds to the multiplication by the polynomial S := (x_1+...+x_n + 1/x_1+...+1/x_n) and the set X_k is constructed precisely to correspond to S^{2^k-1}, so that it's Laplacian corresponds to S^{2^k} = \sum_i x_i^{2^k}+x_i^{-2^k} (squaring polynomials over \F_2 is easy!). This also explains how to come up with the example of X_\infty.
Estimating the dimension of X_\infty is also easy: Roughly speaking, points of X_\infty inside [-n, n]^d are already present in the sum of ~log_2{n}+C+1 terms T_0+T_1+...T_{log_2{n}+C} which has at most (2d)^{log_2{n}+C+1} = C_d*n^{log_2{2d}} points.
It is also proved in the paper that the dimension cannot be smaller than log_2{d}, still leaving a gap of 1 for the smallest possible dimension.
Equivalently, what is the smallest possible dimension of a set X\subset \Z^d such that any y\in \Z^d has even number of neighbours in X? (equivalence is given by passing to the support of the function)
Here is a cool example of such a set of dimension 1+\log_2{d} from Stanislav Krymskii (paper):
Consider sets T_k:={ \pm 2^k e_1, \pm 2^k e_2, ..., \pm 2^k e_d} consisting of all the basis vectors and their opposites scaled by a factor of 2^k. Then let X_k=T_0+...+T_k be the Minkowski sum of the first k+1 of T_i's. Sets X_k are nested (i.e. X_k\subset X_{k+1}, as follows from the observation that \pm 2^k e_i = \mp 2^k e_i + \pm 2^{k+1} e_i) and their union X_\infity provides an example of an \F_2-valued harmonic function on \Z^d with support of dimnesion 1+log_2(d).
To see that the characteristic function of X is indeed discrete harmonic (as a function in \F_2), we need a simple observation that X_{k+1}\setminus X_k only contains points far from the origin together with the fact that \Delta X_{k-1} = T_k, i.e. the only points y\in \Z^d which have odd number of neighbours in X_{k-1} are precisely the points of T_k.
This latter fact can be most elegantly proved by looking at Laurent polynomials over \F_2 corresponding to sets, i.e. given a finite set X look at the Laurent polynomial in variables x_1,..., x_d with a monomial \prod x_i^{t_i} corresponding to a point (t_1,...t_n)\in X. Then looking at the Laplacian corresponds to the multiplication by the polynomial S := (x_1+...+x_n + 1/x_1+...+1/x_n) and the set X_k is constructed precisely to correspond to S^{2^k-1}, so that it's Laplacian corresponds to S^{2^k} = \sum_i x_i^{2^k}+x_i^{-2^k} (squaring polynomials over \F_2 is easy!). This also explains how to come up with the example of X_\infty.
Estimating the dimension of X_\infty is also easy: Roughly speaking, points of X_\infty inside [-n, n]^d are already present in the sum of ~log_2{n}+C+1 terms T_0+T_1+...T_{log_2{n}+C} which has at most (2d)^{log_2{n}+C+1} = C_d*n^{log_2{2d}} points.
It is also proved in the paper that the dimension cannot be smaller than log_2{d}, still leaving a gap of 1 for the smallest possible dimension.
Math from Krach
Suppose a function f: \Z^d --> \F_2 is discrete harmonic. What is the smallest possible dimension of the support of this function? Equivalently, what is the smallest possible dimension of a set X\subset \Z^d such that any y\in \Z^d has even number of neighbours…
Notice that the set of points on the “diagonal” x_1=x_2, x_3=x_4… also leads to an \F_2-valued harmonic function on \Z^d and has dimension [(d+1)/2] ([.] stands for the integer part)
This example has dimension smaller than the example above for d<=7 (and the same dimension 4 when d=8)
This example has dimension smaller than the example above for d<=7 (and the same dimension 4 when d=8)
I will be giving a talk in 5 minutes. Zoom link. Will talk (in Russian) about the paper
Almost all orbits of the Collatz map attain almost bounded values by Terrence Tao
Almost all orbits of the Collatz map attain almost bounded values by Terrence Tao
Apparently, the fact that any convex body can be well-approximated by an ellipsoid is rather simple to prove. Here is the statement, first proved by Fritz John in 1948.
Thm 1: Given a convex body K in \R^n, there exists an ellipsoid E(K) cotained in K such that its dilation by a factor of n contains K.
Let's prove a slightly different statement, which is technically easier, a similar argument should prove John's theorem. See this exposition for details.
Thm 2: Given a convex body K \subset \R^n symmetric about the origin, there exists an ellipsoid E(K), also symmetric about the origin, which is contained in K and such that its dilation by a factor of \sqrt{n} contains K.
I am not sure where Thm 2 was first proved. Neither am I sure what the original proof of John is for Thm 1. Anyway, here is
Proof sketch for Thm 2: We will prove that centrally symmetric ellipsoid of maximal volume inside K satisfies the desired condition. Let E be the centrally symmetric ellipsoid of maximal volume inside K. By affine transformation we may assume that E is the unit ball. Arguing by contradiction, assume that K is not contained in the ball of radius \sqrt{n} centered at the origin. Without loss of generality this means that the point P:=(\sqrt{n}+\eps, 0, 0, ...0) is in K. By symmetry, so is -P. To get a contradiction we need to show that the convex hull of the unit ball with P and -P, i.e. the set Conv(B(1), P, -P), which is a subset of K by convexity, contains an ellipsoid of volume larger than that of the unit ball.
Well, since the picture is rotationaly symmetric with respect to the Ox axis, it is only natural to look at the elliposid E_t:={x_1^2/t^{n-1}+t(x_2^2+...+x_n^2)=1} with t slightly larger than 1, or rather a slight dilate thereof to increase its volume.
To show that E_t is strictly contained in Conv(B(1), P, -P) for t close enough to 1 (depending on \eps), first note that, for the sake of simplicity, we can quotient by the O(n-1) symmetry (w.r.t. the Ox axis) and look at the two dimensional picture. With a slight abuse of notation we still write E_t for {x^2/t^{n-1}+ty^2=1} and P for the point (\sqrt{n}+\eps, 0).
Since everything is symmetric w.r.t. Ox and Oy axes, we will only look at the positive quadrant. Now, as t tends to 1, the intersection E_t\cap B(1) tends to the point T:=(sqrt{1/n}, \sqrt{(n-1)/n}). Indeed, {x^2/t^{n-1}+ty^2=1 & x^2+y^2=1} implies y^2/x^2 = (1-t^{1-n})/(t-1) --> n-1 as t --> 1. So for t sufficiently close to 1, the intersection point is below the tangent point from P to the unit circle (which is positioned slightly above T for any fixed \eps). Hence, E_t does not intersect the arcs of the convex hull Conv(B(1), P, -P) and it remains to prove that E_t does not intersect the tangent segment from P to the unit circle.
For that note that not only does the intersection point E_t\cap B(1) tend to T:=(sqrt{1/n}, \sqrt{(n-1)/n}), but also the tangent line to E_t at this intersection point tends to the tangent line to the unit circle at T (in the sense of the slope). Hence, for t sufficiently close to 1 we have E_t below the tangent line to the unit circle at T up to a o(1) error, which implies that it is below the tangent line from P to the unit circle for t sufficiently close to 1.
Thm 1: Given a convex body K in \R^n, there exists an ellipsoid E(K) cotained in K such that its dilation by a factor of n contains K.
Let's prove a slightly different statement, which is technically easier, a similar argument should prove John's theorem. See this exposition for details.
Thm 2: Given a convex body K \subset \R^n symmetric about the origin, there exists an ellipsoid E(K), also symmetric about the origin, which is contained in K and such that its dilation by a factor of \sqrt{n} contains K.
I am not sure where Thm 2 was first proved. Neither am I sure what the original proof of John is for Thm 1. Anyway, here is
Proof sketch for Thm 2: We will prove that centrally symmetric ellipsoid of maximal volume inside K satisfies the desired condition. Let E be the centrally symmetric ellipsoid of maximal volume inside K. By affine transformation we may assume that E is the unit ball. Arguing by contradiction, assume that K is not contained in the ball of radius \sqrt{n} centered at the origin. Without loss of generality this means that the point P:=(\sqrt{n}+\eps, 0, 0, ...0) is in K. By symmetry, so is -P. To get a contradiction we need to show that the convex hull of the unit ball with P and -P, i.e. the set Conv(B(1), P, -P), which is a subset of K by convexity, contains an ellipsoid of volume larger than that of the unit ball.
Well, since the picture is rotationaly symmetric with respect to the Ox axis, it is only natural to look at the elliposid E_t:={x_1^2/t^{n-1}+t(x_2^2+...+x_n^2)=1} with t slightly larger than 1, or rather a slight dilate thereof to increase its volume.
To show that E_t is strictly contained in Conv(B(1), P, -P) for t close enough to 1 (depending on \eps), first note that, for the sake of simplicity, we can quotient by the O(n-1) symmetry (w.r.t. the Ox axis) and look at the two dimensional picture. With a slight abuse of notation we still write E_t for {x^2/t^{n-1}+ty^2=1} and P for the point (\sqrt{n}+\eps, 0).
Since everything is symmetric w.r.t. Ox and Oy axes, we will only look at the positive quadrant. Now, as t tends to 1, the intersection E_t\cap B(1) tends to the point T:=(sqrt{1/n}, \sqrt{(n-1)/n}). Indeed, {x^2/t^{n-1}+ty^2=1 & x^2+y^2=1} implies y^2/x^2 = (1-t^{1-n})/(t-1) --> n-1 as t --> 1. So for t sufficiently close to 1, the intersection point is below the tangent point from P to the unit circle (which is positioned slightly above T for any fixed \eps). Hence, E_t does not intersect the arcs of the convex hull Conv(B(1), P, -P) and it remains to prove that E_t does not intersect the tangent segment from P to the unit circle.
For that note that not only does the intersection point E_t\cap B(1) tend to T:=(sqrt{1/n}, \sqrt{(n-1)/n}), but also the tangent line to E_t at this intersection point tends to the tangent line to the unit circle at T (in the sense of the slope). Hence, for t sufficiently close to 1 we have E_t below the tangent line to the unit circle at T up to a o(1) error, which implies that it is below the tangent line from P to the unit circle for t sufficiently close to 1.
Given an arbitrary simple graph on n vertices, asymptotically the fastest algorithm which finds a triangle (i.e. 3 vertices connected by edges) takes O(n^\omega) time, where \omega is the matrix multiplication exponent. An algorithm is very simple: If one squares the adjacency matrix A of the graph one gets numbers A^2[i, j] which precisely count the number of paths of length two between vertices, it then remains to check if for some i, j connected by an edge one has A^2[i, j]>0.
It is widely believed that two matrices of size n by n can be multiplied in time O(n^{2+o(1)}), which means that \omega=2, but the best currently known upper bound is \omega < 2.23716.
Finding larger cliques is seemingly more difficult: Even if \omega=2 it is believed that detecting a clique on 4 vertices takes at least cubic time O(n^3), and the best known result is somewhat worse: O(n^{3.257}). Recall that finding the largest clique is well-known to be NP-complete so it is unlikely to be solvable in polynomial time.
Around ten years ago, Virginia Vassilevska Williams with her husband and some PhD students realized [1] that detecting any induced subgraph on four vertices other than the clique (or the empty graph) is possible in time O(n^{\omega+o(1)}) by a randomized algorithm, which is as fast as finding a triangle! The argument is very short:
Step 0: Finding a subgraph is not much harder than detecting it (i.e. understanding if an induced subgraph exists). Indeed, given a graph H on 4 vertices, split vertices of our graph G into five roughly equal parts, then G contains a copy of H if and only if a union of some 4 parts out of 5 contains H. So by checking detection five times we reduce the number of vertices by a factor of 4/5, so with an additional log{n} factor (update: seems like no log{n} factor is needed since the graph is shrinking at each step) we can find the subgraph w.h.p. if it exists.
Step 1: For simplicity, we consider the case when H is a diamond, i.e. a graph on 4 vertices with 5 edges, where only the second and the fourth vertices are not connected. Let’s initially try not only to detect H but to count the number of occurrences of H in G. A natural way to do so is to sum over vertices i, j connected by an edge (which correspond to vertices 1, 3 in H), and then with the square of the adjacency matrix at hand compute the number of pairs of paths 1-2-3 and 1-4-3 between i and j. So what we are computing is S:=\sum_{i \sim j} \binom{A^2[i, j]}{2}. This sum does not quite disambiguate between diamonds and cliques K_4 since vertices 2 and 4 can be connected or not. Yet, because of additional symmetries in K_4 the sum S counts every diamond exactly once and every clique K_4 six times. So if the number of diamonds were not divisible by 6 then we would detect it in time O(n^\omega)…
Step 2: To overcome the divisibility by 6 issue, simply use (a variant of) Schwartz-Zippel lemma to argue that if G has at least one induced copy of the diamond, then with probability at least 1/16 a random graph obtained from G by removing vertices independently with probability 1/2 has non-zero number of diamonds modulo 6.
[1]https://www.cs.princeton.edu/~hy2/files/graph-cr.pdf
It is widely believed that two matrices of size n by n can be multiplied in time O(n^{2+o(1)}), which means that \omega=2, but the best currently known upper bound is \omega < 2.23716.
Finding larger cliques is seemingly more difficult: Even if \omega=2 it is believed that detecting a clique on 4 vertices takes at least cubic time O(n^3), and the best known result is somewhat worse: O(n^{3.257}). Recall that finding the largest clique is well-known to be NP-complete so it is unlikely to be solvable in polynomial time.
Around ten years ago, Virginia Vassilevska Williams with her husband and some PhD students realized [1] that detecting any induced subgraph on four vertices other than the clique (or the empty graph) is possible in time O(n^{\omega+o(1)}) by a randomized algorithm, which is as fast as finding a triangle! The argument is very short:
Step 0: Finding a subgraph is not much harder than detecting it (i.e. understanding if an induced subgraph exists). Indeed, given a graph H on 4 vertices, split vertices of our graph G into five roughly equal parts, then G contains a copy of H if and only if a union of some 4 parts out of 5 contains H. So by checking detection five times we reduce the number of vertices by a factor of 4/5, so with an additional log{n} factor (update: seems like no log{n} factor is needed since the graph is shrinking at each step) we can find the subgraph w.h.p. if it exists.
Step 1: For simplicity, we consider the case when H is a diamond, i.e. a graph on 4 vertices with 5 edges, where only the second and the fourth vertices are not connected. Let’s initially try not only to detect H but to count the number of occurrences of H in G. A natural way to do so is to sum over vertices i, j connected by an edge (which correspond to vertices 1, 3 in H), and then with the square of the adjacency matrix at hand compute the number of pairs of paths 1-2-3 and 1-4-3 between i and j. So what we are computing is S:=\sum_{i \sim j} \binom{A^2[i, j]}{2}. This sum does not quite disambiguate between diamonds and cliques K_4 since vertices 2 and 4 can be connected or not. Yet, because of additional symmetries in K_4 the sum S counts every diamond exactly once and every clique K_4 six times. So if the number of diamonds were not divisible by 6 then we would detect it in time O(n^\omega)…
Step 2: To overcome the divisibility by 6 issue, simply use (a variant of) Schwartz-Zippel lemma to argue that if G has at least one induced copy of the diamond, then with probability at least 1/16 a random graph obtained from G by removing vertices independently with probability 1/2 has non-zero number of diamonds modulo 6.
[1]https://www.cs.princeton.edu/~hy2/files/graph-cr.pdf
From [1]: Given an n by n matrix with positive entries, scale the rows so that each row sum is 1. Then scale the columns so that each column sum is 1; generically, this changes the row sums. To restore the row sums 1, scale the rows again, then scale the columns, and so on. Sinkhorn showed that the sequence of matrices obtained through this process converges to a matrix whose row and column sums are 1 (in other words, a doubly stochastic matrix). We call this matrix the Sinkhorn limit of A and denote it Sink(A). Sinkhorn also showed that Sink(A) is the unique doubly stochastic matrix S with the same size as A such that S = RAC for some diagonal matrices R and C with positive diagonal entries. Here R can be taken to be the product of the row-scaling matrices and C the product of the column-scaling matrices.
Conjecture: If the entries of A are rational then the entries of Sink(A) are algebraic of degree at most \binom{2n-2}{n-1}. Moreover, a polynomial equation satisfied by the top-left entry of Sink(A) can be written explicitly with coefficients expressible as linear combinations of minors of A.
For the explicit expressions for the coefficients, see [1, Conjecture 2]. Though the notation used in the conjecture is quite cumbersome and spans more than three pages. Perhaps it is easier to watch the video [2] (in the 3Blue1Brown style) provided by the authors, where some examples are given. (NB: First six minutes aren’t that relevant, next two and a half minutes discuss the n=2 case which is rather simple.)
They prove the conjecture for n=3 which follows from the Sinkhorn observation about Sink(A) being the unique doubly stochastic matrix of the form RAC by some tedious Grobner basis computations. By tedious I mean, quoting the paper, Mathematica’s GroebnerBasis function with certain settings computes a single polynomial in a couple seconds. If I understood correctly, to formulate the general conjecture for larger values of n, they compute numerically Sink(A) for some matrices, then use PSLQ algorithm to compute the minimal polynomial of the top-left entry, and then given several matrices they find suitable linear combinations of minors to fit the coefficients.
[1] https://arxiv.org/pdf/2409.02789
[2] https://www.youtube.com/watch?v=-uIwboK4nwE&t=515s
Conjecture: If the entries of A are rational then the entries of Sink(A) are algebraic of degree at most \binom{2n-2}{n-1}. Moreover, a polynomial equation satisfied by the top-left entry of Sink(A) can be written explicitly with coefficients expressible as linear combinations of minors of A.
For the explicit expressions for the coefficients, see [1, Conjecture 2]. Though the notation used in the conjecture is quite cumbersome and spans more than three pages. Perhaps it is easier to watch the video [2] (in the 3Blue1Brown style) provided by the authors, where some examples are given. (NB: First six minutes aren’t that relevant, next two and a half minutes discuss the n=2 case which is rather simple.)
They prove the conjecture for n=3 which follows from the Sinkhorn observation about Sink(A) being the unique doubly stochastic matrix of the form RAC by some tedious Grobner basis computations. By tedious I mean, quoting the paper, Mathematica’s GroebnerBasis function with certain settings computes a single polynomial in a couple seconds. If I understood correctly, to formulate the general conjecture for larger values of n, they compute numerically Sink(A) for some matrices, then use PSLQ algorithm to compute the minimal polynomial of the top-left entry, and then given several matrices they find suitable linear combinations of minors to fit the coefficients.
[1] https://arxiv.org/pdf/2409.02789
[2] https://www.youtube.com/watch?v=-uIwboK4nwE&t=515s
A tale of many distances:
Let us start from the very end, from the answer, the ultimate law of nature if you wish, and then gradually descend from the summit observing the views around.
Theorem: There exists a set of n+2 points in \R^n such that all pairwise distances between them are odd integers if and only if n is congruent to 14 modulo 16.
Arguably, looking at fourteen dimensions is somewhat justifiable given this is the answer, yet same cannot be said of distances being odd integers, for this restriction is, you know, odd. Hence, one might wonder if similar laws of nature exist in the realms less artificial, perhaps where all integers are treated with equal respect. It so happens that the answer is no, such a realm has infinitely many possibilities and virtually no restrictions, as seen by the following theorem.
Theorem: There exist arbitrary large non-trivial finite sets of points on the plane with all pairwise distances being integer. No such infinite set of points exists.
There is no cheating allowed, one could, of course, take all the points on the same line and claim the victory, so we deem all such examples trivial and concentrate on non-trivial ones. Ruling out the possibility of an infinite number of points is left to the reader and we briefly discuss the first half of the theorem.
The key to the construction lies in the famous theorem of Ptolemy giving a relation between the four sides and two diagonals of a cyclic quadrilateral and hence ensuring that if five distances between four points on a circle are rational, then so is the sixth one. We note in passing that by scaling we can indeed think of rational distances rather than integer ones. With such a hint we are naturally led to consider a circle with diameter AB of unit length and an infinitude of points C_k on the circle at rational distances both from A and B given by various Pythagorean triples. Then |AC_k|, |BC_k|, |AB| are all rational by construction and |C_iC_j| are rational by the aforementioned theorem of Ptolemy. There are reasons to believe that possibilities are rather limited without Ptolemy, see [1, Theorem 1.1].
Having observed how dull the world of integer distances is, we return to the artificial world of odd restrictions to see how this world works. In spaces such as \R^n one has the benefit of scalar products, and so one natural step is to look at scalar products rather than distances: With n+2 points at odd distances in \R^n in mind we harmlessly assume that one of them, say A_0, is at the origin and look at scalar products <A_0A_i, A_0A_j>. Matrix with such entries, called Gramm matrix, has rank at most n (since all points are in \R^n) and hence zero determinant. Multiplying all entries by 2 and using the identity 2<a, b>=|a|^2+|b^2|-|a-b|^2, we see that 2<A_0A_i, A_0A_j> is congruent to 1 modulo 8 (recall that odd squares are congruent to 1 modulo 8 ) when i and j are distinct, whereas 2<A_0A_i, A_0A_i> = 2|A_0A_i|^2 is congruent to 2 modulo 16.
Claim: A symmetric m by m matrix with entries 2 on the diagonal and all other entries equal to 1 has determinant m+1. Modulo 16 the determinant does not change if one adds a symmetric matrix with all off-diagonal entries divisible by 8 and all diagonal entries divisible by 16.
Let us start from the very end, from the answer, the ultimate law of nature if you wish, and then gradually descend from the summit observing the views around.
Theorem: There exists a set of n+2 points in \R^n such that all pairwise distances between them are odd integers if and only if n is congruent to 14 modulo 16.
Arguably, looking at fourteen dimensions is somewhat justifiable given this is the answer, yet same cannot be said of distances being odd integers, for this restriction is, you know, odd. Hence, one might wonder if similar laws of nature exist in the realms less artificial, perhaps where all integers are treated with equal respect. It so happens that the answer is no, such a realm has infinitely many possibilities and virtually no restrictions, as seen by the following theorem.
Theorem: There exist arbitrary large non-trivial finite sets of points on the plane with all pairwise distances being integer. No such infinite set of points exists.
There is no cheating allowed, one could, of course, take all the points on the same line and claim the victory, so we deem all such examples trivial and concentrate on non-trivial ones. Ruling out the possibility of an infinite number of points is left to the reader and we briefly discuss the first half of the theorem.
The key to the construction lies in the famous theorem of Ptolemy giving a relation between the four sides and two diagonals of a cyclic quadrilateral and hence ensuring that if five distances between four points on a circle are rational, then so is the sixth one. We note in passing that by scaling we can indeed think of rational distances rather than integer ones. With such a hint we are naturally led to consider a circle with diameter AB of unit length and an infinitude of points C_k on the circle at rational distances both from A and B given by various Pythagorean triples. Then |AC_k|, |BC_k|, |AB| are all rational by construction and |C_iC_j| are rational by the aforementioned theorem of Ptolemy. There are reasons to believe that possibilities are rather limited without Ptolemy, see [1, Theorem 1.1].
Having observed how dull the world of integer distances is, we return to the artificial world of odd restrictions to see how this world works. In spaces such as \R^n one has the benefit of scalar products, and so one natural step is to look at scalar products rather than distances: With n+2 points at odd distances in \R^n in mind we harmlessly assume that one of them, say A_0, is at the origin and look at scalar products <A_0A_i, A_0A_j>. Matrix with such entries, called Gramm matrix, has rank at most n (since all points are in \R^n) and hence zero determinant. Multiplying all entries by 2 and using the identity 2<a, b>=|a|^2+|b^2|-|a-b|^2, we see that 2<A_0A_i, A_0A_j> is congruent to 1 modulo 8 (recall that odd squares are congruent to 1 modulo 8 ) when i and j are distinct, whereas 2<A_0A_i, A_0A_i> = 2|A_0A_i|^2 is congruent to 2 modulo 16.
Claim: A symmetric m by m matrix with entries 2 on the diagonal and all other entries equal to 1 has determinant m+1. Modulo 16 the determinant does not change if one adds a symmetric matrix with all off-diagonal entries divisible by 8 and all diagonal entries divisible by 16.