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.
The first part of the claim follows for the fact that the spectrum of such a matrix is {m+1, 1, 1, …, 1}, since it’s obtained from a matrix of all ones (which has spectrum {m, 0, 0, …, 0}) by adding the identity matrix, and hence shifting the spectrum by 1. For the second part observe that treating all the changes as a (2-adic) perturbation, since we are concerned with the result modulo 16 and the perturbation is divisible by 8, it suffices to look only at the term of the Taylor expansion of det(A+[perturbation]) which is linear in the whole perturbation. Perturbing a matrix A by some matrix X, the linear term in the expansion of det(A+X) in x_ij is going to be the minor of A corresponding to the entry a_ij. The diagonal perturbation x_ii is zero (modulo 16) in the first place, and off-diagonal perturbation being symmetric and 0 modulo 8 comes in pairs (x_ij, x_ji) contributing together 0 modulo 16 since parities of minors of A corresponding to a_ij and a_ji are clearly the same. See [2] for an explicit computation which I found less enlightning.
This claim already gives one part of the theorem: Assuming a set of n+2 points in \R^n at odd distances exists, we arrive at an n+1 by n+1 matrix with zero determinant which must also be congruent to (n+1)+1 modulo 16. Hence, n itself must be 14 modulo 16.
When n is 14 modulo 16 an example of n+2 points at odd distances is rather boring: Take a hyperplane H in \R^n and choose, inside H, a regular simplex with n vertices all at distances n/2 from each other. Then choose the last two points symmetric to each other with respect to H and at distance (n-2)/4 from each other. A simple computation then shows that these two points are at distance (3n-2)/8 from the vertices of the simplex.
[1]https://arxiv.org/pdf/2401.10821
[2]https://mathweb.ucsd.edu/~ronspubs/74_02_odd_distance.pdf
This claim already gives one part of the theorem: Assuming a set of n+2 points in \R^n at odd distances exists, we arrive at an n+1 by n+1 matrix with zero determinant which must also be congruent to (n+1)+1 modulo 16. Hence, n itself must be 14 modulo 16.
When n is 14 modulo 16 an example of n+2 points at odd distances is rather boring: Take a hyperplane H in \R^n and choose, inside H, a regular simplex with n vertices all at distances n/2 from each other. Then choose the last two points symmetric to each other with respect to H and at distance (n-2)/4 from each other. A simple computation then shows that these two points are at distance (3n-2)/8 from the vertices of the simplex.
[1]https://arxiv.org/pdf/2401.10821
[2]https://mathweb.ucsd.edu/~ronspubs/74_02_odd_distance.pdf
Here is a nice math/programming problem (the use of a computer is allowed, of course):
How many integers N satisfying 10^19 <= N <= 10^19 + 10^4 can be written in the form N = x^3 + 2y^3 + 4z^3 - 6xyz for some integer values of x, y, z?
(It's used in the application process for Epoch AI, so I won't comment on the solution.)
How many integers N satisfying 10^19 <= N <= 10^19 + 10^4 can be written in the form N = x^3 + 2y^3 + 4z^3 - 6xyz for some integer values of x, y, z?
(It's used in the application process for Epoch AI, so I won't comment on the solution.)
If x, y, z are i.i.d. Uniform[0, 1] then (xy)^z is also Uniform[0, 1]. Why?
(Question by Grant Sanderson)
(Question by Grant Sanderson)
On a related note, if x\sim Uniform [0, 1], then the random variable z=x^2-1/3, i.e. x^2 shifted to have zero mean, satisfies \E[z^3]=\E[z^4] (=16/945)
Is there a short explanation for this? Or is it just a coincidence somehow?
Is there a short explanation for this? Or is it just a coincidence somehow?
Spanning trees of planar graphs:
For a simple graph G let \tau(G) be the number of spanning trees of G. Let T(n) be the size of the image of \tau on the set of planar graphs with n vertices. Clearly, any planar graph with n vertices has at most 3n edges and hence at most 8^n spanning trees (exercise: use AM-GM to show a bound of 6^n), so T(n) grows at most exponentially. It is reasonable to assume that T(n) does grow exponentially fast:
Thm: There exists c>1 such that T(n)>c^n for n>2.
This was recently proved in [1] using ideas borrowed from the Annals of Maths paper of Bourgain and Kontorovich [2] on Zaremba’s conjecture.
The starting point is the following simple observation. For a graph G and an edge e of G let v(G, e) be a two-dimensional vector with entries \tau(G-e) and \tau(G/e), where G-e is the graph G with the edge e removed and G/e is the graph G with the end-points of e contracted. Clearly, \tau(G) can be recovered from these values: \tau(G)=\tau(G-e)+\tau(G/e) since \tau(G-e) is the number of spanning trees of G which do not contain e and \tau(G/e) is the number of spanning trees of G which do contain e.
An advantage of looking at both \tau(G-e) and \tau(G/e) simultaneously is that now we can control how these values change under some local modifications of G. For instance, if for some positive integer k one considers a graph G’ obtained from G by adding a chain of k+1 edges between the end-points of e, then with e’ being an arbitrary edge of this chain, one has v(G’, e’)=\Gamma(k)*v(G, e), where \Gamma(k) = (1, k // 1 k+1) is a fixed 2 by 2 matrix. Note that this procedure preserves the property of being planar.
In fact, this observation alone suffices to show an exponential lower bound for T(n): starting from a graph with one edge, let us perform the procedure of inserting a chain of edges sequentially n times, each time taking k_i=1 or k_i=3, say. Then all resulting 2^n vectors v(G, e) will be distinct because of the connection with continued fractions: The matrix \Gamma(k) is equal to the product (0 1 // 1 1)*(0 1 // 1 k) and so the resulting vector v(G, e) is essentially given by a fraction which has continued fraction expansion [0; 1, k_1, 1, k_2, \dots, k_n, 1] which are all distinct. Having 2^n distinct fractions we ensure that we have at least 2^{n/2} numerators or denominators and hence at least 2^{n/2} district values of \tau on the set of planar graphs with O(n) vertices.
The work [1] seemingly conceals the existence of this short argument and uses much heavier machinery to prove that, in fact, for some c>1 the image of \tau on the set of planar graphs with n vertices contains a positive proportion of numbers among {1, 2, …, c^n}. The proof is similar to that of the main theorem in [2]:
Thm: For almost all positive integers n there exists a<n coprime to n such that the continued fraction of a/n has all entries smaller than 50.
Zaremba’s conjecture states that there exists an absolute constant A such that all positive integers n have a corresponding irreducible fraction a/n with all entries in its continued fraction not exceeding A. Zaremba further speculated that A=5 suffices.
[1] “Spanning Trees and Continued Fractions” https://arxiv.org/abs/2411.18782
[2] “On Zaremba’s Conjecture” https://arxiv.org/abs/1107.3776
For a simple graph G let \tau(G) be the number of spanning trees of G. Let T(n) be the size of the image of \tau on the set of planar graphs with n vertices. Clearly, any planar graph with n vertices has at most 3n edges and hence at most 8^n spanning trees (exercise: use AM-GM to show a bound of 6^n), so T(n) grows at most exponentially. It is reasonable to assume that T(n) does grow exponentially fast:
Thm: There exists c>1 such that T(n)>c^n for n>2.
This was recently proved in [1] using ideas borrowed from the Annals of Maths paper of Bourgain and Kontorovich [2] on Zaremba’s conjecture.
The starting point is the following simple observation. For a graph G and an edge e of G let v(G, e) be a two-dimensional vector with entries \tau(G-e) and \tau(G/e), where G-e is the graph G with the edge e removed and G/e is the graph G with the end-points of e contracted. Clearly, \tau(G) can be recovered from these values: \tau(G)=\tau(G-e)+\tau(G/e) since \tau(G-e) is the number of spanning trees of G which do not contain e and \tau(G/e) is the number of spanning trees of G which do contain e.
An advantage of looking at both \tau(G-e) and \tau(G/e) simultaneously is that now we can control how these values change under some local modifications of G. For instance, if for some positive integer k one considers a graph G’ obtained from G by adding a chain of k+1 edges between the end-points of e, then with e’ being an arbitrary edge of this chain, one has v(G’, e’)=\Gamma(k)*v(G, e), where \Gamma(k) = (1, k // 1 k+1) is a fixed 2 by 2 matrix. Note that this procedure preserves the property of being planar.
In fact, this observation alone suffices to show an exponential lower bound for T(n): starting from a graph with one edge, let us perform the procedure of inserting a chain of edges sequentially n times, each time taking k_i=1 or k_i=3, say. Then all resulting 2^n vectors v(G, e) will be distinct because of the connection with continued fractions: The matrix \Gamma(k) is equal to the product (0 1 // 1 1)*(0 1 // 1 k) and so the resulting vector v(G, e) is essentially given by a fraction which has continued fraction expansion [0; 1, k_1, 1, k_2, \dots, k_n, 1] which are all distinct. Having 2^n distinct fractions we ensure that we have at least 2^{n/2} numerators or denominators and hence at least 2^{n/2} district values of \tau on the set of planar graphs with O(n) vertices.
The work [1] seemingly conceals the existence of this short argument and uses much heavier machinery to prove that, in fact, for some c>1 the image of \tau on the set of planar graphs with n vertices contains a positive proportion of numbers among {1, 2, …, c^n}. The proof is similar to that of the main theorem in [2]:
Thm: For almost all positive integers n there exists a<n coprime to n such that the continued fraction of a/n has all entries smaller than 50.
Zaremba’s conjecture states that there exists an absolute constant A such that all positive integers n have a corresponding irreducible fraction a/n with all entries in its continued fraction not exceeding A. Zaremba further speculated that A=5 suffices.
[1] “Spanning Trees and Continued Fractions” https://arxiv.org/abs/2411.18782
[2] “On Zaremba’s Conjecture” https://arxiv.org/abs/1107.3776
#topological_aspects_of_algebraic_geometry
Next several posts will be about the topological aspects of algebraic geometry, mostly concerned with the following question: Given a homogeneous non-singular polynomial f(x, y, z) of degree d, consider the zero set of this polynomial in \RP^2, what sort of pictures can we see?
We will be following the course given by Ilia Itenberg, here are YouTube videos
Set-up: Looking at homogeneous polynomials of degree d with real coefficients, non-singular over \C. We want to classify the topological pairs (\RP^2, \R A), where \R A is the zero set of the polynomials over \R. That’s Hilbert’s 16th problem (part of it).
Connected components are circles embedded in \RP^2. There are two different ways to embed a circle: as a pseudo-line (the complement has one connected component which is topologically a disc; it is the non-trivial element in H_1(\RP^2)) or as an oval (the complement has two connected components: a disc and a möbius band; zero element of H_1(\RP^2)).
Claim: if d is odd then we have exactly 1 pseudo-line, if d is even, we have ovals only.
Proof: If d is odd, we must have at least one pseudo-line, indeed, any line should intersect the zero set in odd number of points (since the restriction of the polynomial to a line is just a degree d polynomial of one variable), but an oval intersects a (generic) line at even number of points. Having two pseudo-lines is impossible as they must intersect which creates a singular point of the polynomial at the intersection point. For d even the same argument works but also for d even every “value” of f at a point of \RP^2 has a sign, this precludes the existence of a pseudo-line (as two sides of the pseudo-line are in the same connected component, hence no change of sign).
Some answers for our question for small d:
For d=2 you can have one oval or an empty set.
For d=3 you can have a pseudo-line or a pseudo-line with an oval.
Proof: A line intersects the zero set at at most d<4 points so having two ovals is impossible (choose a point in each oval to create 2 intersections per oval). To give an example for d=3: multiply a line by a circle that doesn’t intersect in \RP^2 and perturb slightly.
d=4: empty set, an oval, two ovals (again, multiply two circles and perturb) either nested or not, three ovals (not nested), four ovals (not nested).
Proof: two nested ovals exclude the possibility of other ovals since otherwise a line can intersect the zero set in 6 points. Now, 5 ovals is impossible since we can choose 5 points inside them and draw a conic through them getting 10>4*2 intersection, leading to a contradiction. To realize 4 ovals, choose a product of two intersecting ovals and then perturb to create four ovals (perturb by subtracting \eps(x_0^4+x_1^4+x_2^4) so that the four “positive” regions shrink). Similarly for 3 ovals by considering a different perturbation.
Rem: The space of all degree d polynomials is linear of dimension d(d+3)/2. Hence, in particular, a conic exists through generic 5 points.
For d=5 everything is still easy but for d=6 things become tricky! Even with the maximal number of ovals, which is eleven, there are three arrangements (though Hilbert apparently thought there are only two). (1<1>, 9), (1<5>, 5), and (1<9>, 1). The reason is a congruence modulo 8 which we will discuss later!
Next several posts will be about the topological aspects of algebraic geometry, mostly concerned with the following question: Given a homogeneous non-singular polynomial f(x, y, z) of degree d, consider the zero set of this polynomial in \RP^2, what sort of pictures can we see?
We will be following the course given by Ilia Itenberg, here are YouTube videos
Set-up: Looking at homogeneous polynomials of degree d with real coefficients, non-singular over \C. We want to classify the topological pairs (\RP^2, \R A), where \R A is the zero set of the polynomials over \R. That’s Hilbert’s 16th problem (part of it).
Connected components are circles embedded in \RP^2. There are two different ways to embed a circle: as a pseudo-line (the complement has one connected component which is topologically a disc; it is the non-trivial element in H_1(\RP^2)) or as an oval (the complement has two connected components: a disc and a möbius band; zero element of H_1(\RP^2)).
Claim: if d is odd then we have exactly 1 pseudo-line, if d is even, we have ovals only.
Proof: If d is odd, we must have at least one pseudo-line, indeed, any line should intersect the zero set in odd number of points (since the restriction of the polynomial to a line is just a degree d polynomial of one variable), but an oval intersects a (generic) line at even number of points. Having two pseudo-lines is impossible as they must intersect which creates a singular point of the polynomial at the intersection point. For d even the same argument works but also for d even every “value” of f at a point of \RP^2 has a sign, this precludes the existence of a pseudo-line (as two sides of the pseudo-line are in the same connected component, hence no change of sign).
Some answers for our question for small d:
For d=2 you can have one oval or an empty set.
For d=3 you can have a pseudo-line or a pseudo-line with an oval.
Proof: A line intersects the zero set at at most d<4 points so having two ovals is impossible (choose a point in each oval to create 2 intersections per oval). To give an example for d=3: multiply a line by a circle that doesn’t intersect in \RP^2 and perturb slightly.
d=4: empty set, an oval, two ovals (again, multiply two circles and perturb) either nested or not, three ovals (not nested), four ovals (not nested).
Proof: two nested ovals exclude the possibility of other ovals since otherwise a line can intersect the zero set in 6 points. Now, 5 ovals is impossible since we can choose 5 points inside them and draw a conic through them getting 10>4*2 intersection, leading to a contradiction. To realize 4 ovals, choose a product of two intersecting ovals and then perturb to create four ovals (perturb by subtracting \eps(x_0^4+x_1^4+x_2^4) so that the four “positive” regions shrink). Similarly for 3 ovals by considering a different perturbation.
Rem: The space of all degree d polynomials is linear of dimension d(d+3)/2. Hence, in particular, a conic exists through generic 5 points.
For d=5 everything is still easy but for d=6 things become tricky! Even with the maximal number of ovals, which is eleven, there are three arrangements (though Hilbert apparently thought there are only two). (1<1>, 9), (1<5>, 5), and (1<9>, 1). The reason is a congruence modulo 8 which we will discuss later!
Now, what is the possible number of connected components? (Equivalently, what is the topology of \R A itself?) The answer is given by:
Harnack theorem: The number \ell of the connected components is at most (d-1)(d-2)/2+1. Moreover, all numbers from 0 (or 1 for odd d) are realized!
Elementary proof of the inequality (by Harnack): Simply generalize the proof for d=3 (draw a line and get a contradiction with too many intersections) and for d=4 (draw a conic and again get too many intersections). Now we draw a curve of degree d-2 which is possible to do through (d-2)(d+1)/2 points, see the remark above about the dimension of the space of polynomials.
Now, assume that we have more than (d-1)(d-2)/2+1 connected components of \R A. Then we have (d-1)(d-2)/2+1 ovals plus some other connected components. Choose a point on each of the (d-1)(d-2)/2+1 ovals and d-3 points on one other connected component (the total is (d-2)(d+1)/2+1, hopefully), draw a new red curve through all these points of degree d-2. It intersects each oval at least twice, so the total number of intersections is at least 2((d-1)(d-2)/2+1) + (d-3) = d(d-2) + 1 leading to a contradiction!
Remark: we chose points on the ovals since the red curve need not be connected so had we chosen the points inside the ovals, we wouldn’t be able to ensure any intersections with the ovals.
Definition: A maximal curve is a curve with the maximal, i.e. (d-1)(d-2)/2+1 number of connected components.
Remark: Harnack gave an example of a maximal curve of any degree by induction. Once you know how to contract a maximal curve and a curve with 0/1 connected components, every value of \ell can be realised by transforming one curve into another continuously in the space of curves, just make sure we never cross the surface “discriminant = 0" (i.e. singular curves) at the corners.
Another proof of the Harnack inequality (by Klein?): Look at the complex zeroes of the polynomial in \CP^2. The zero set is a smooth (complex) curve of genus g=(d-1)(d-2)/2 [Rem: the complement of “discriminant=0” is now connected so all curves are the same in the complex world. For the x_0^d+x_1^d+x_2^d=0 curve, look at \C A as a ramified covering of \CP^1 (projecting \CP^2 from a given point, say, (0, 0, 1) and use a lift of a triangulation to compute the Euler characteristic of \C A. Also, instead of x_0^d+x_1^d+x_2^d one can take a perturbation of a product of lines.]
Now, we have \R A inside \C A and we also have (since our polynomial is real) an involution on \CA, given by complex conjugation, which has the fixed point set \R A and reverses the orientation.
Claim: For any orientation-reversing involution on a (smooth, orientable) curve of genus g, the number of connected components of the fixed point set is at most g+1.
Proof: Look at the quotient \C A / c by the involution c, glue \ell discs along boundary components. We get a surface which may be non-orientable. The Euler characteristic of this quotient with the glued discs is at most 2 (as for any surface), so \chi(S/ c) + \ell <= 2. Which means that \chi(S)/2 + \ell <=2, or, in terms of the genus, we have 1-g + \ell <=2, leading to the desired \ell<=g+1 bound!
Definition: Type I curve is a curve for which S/c is orientable (equivalently, \C A \setminus \R A has two connected components); Type II curve is a curve for which S/c is non-orientable (equivalently, \C A \setminus \R A has one connected component).
Remark: Any maximal curve has type I. Indeed, we have equalities in the Klein's proof everywhere, so \chi(S/c with glued discs)=2, hence S/c is a sphere with holes, hence, it is orientable.
Claim (Klein's congruence): If A is of type I, then \ell (the number of connected components of \R A) has the same parity as the maximal possible value, i.e. (d-1)(d-2)/2+1.
Proof: Orientability means that the Euler characteristics is even.
Harnack theorem: The number \ell of the connected components is at most (d-1)(d-2)/2+1. Moreover, all numbers from 0 (or 1 for odd d) are realized!
Elementary proof of the inequality (by Harnack): Simply generalize the proof for d=3 (draw a line and get a contradiction with too many intersections) and for d=4 (draw a conic and again get too many intersections). Now we draw a curve of degree d-2 which is possible to do through (d-2)(d+1)/2 points, see the remark above about the dimension of the space of polynomials.
Now, assume that we have more than (d-1)(d-2)/2+1 connected components of \R A. Then we have (d-1)(d-2)/2+1 ovals plus some other connected components. Choose a point on each of the (d-1)(d-2)/2+1 ovals and d-3 points on one other connected component (the total is (d-2)(d+1)/2+1, hopefully), draw a new red curve through all these points of degree d-2. It intersects each oval at least twice, so the total number of intersections is at least 2((d-1)(d-2)/2+1) + (d-3) = d(d-2) + 1 leading to a contradiction!
Remark: we chose points on the ovals since the red curve need not be connected so had we chosen the points inside the ovals, we wouldn’t be able to ensure any intersections with the ovals.
Definition: A maximal curve is a curve with the maximal, i.e. (d-1)(d-2)/2+1 number of connected components.
Remark: Harnack gave an example of a maximal curve of any degree by induction. Once you know how to contract a maximal curve and a curve with 0/1 connected components, every value of \ell can be realised by transforming one curve into another continuously in the space of curves, just make sure we never cross the surface “discriminant = 0" (i.e. singular curves) at the corners.
Another proof of the Harnack inequality (by Klein?): Look at the complex zeroes of the polynomial in \CP^2. The zero set is a smooth (complex) curve of genus g=(d-1)(d-2)/2 [Rem: the complement of “discriminant=0” is now connected so all curves are the same in the complex world. For the x_0^d+x_1^d+x_2^d=0 curve, look at \C A as a ramified covering of \CP^1 (projecting \CP^2 from a given point, say, (0, 0, 1) and use a lift of a triangulation to compute the Euler characteristic of \C A. Also, instead of x_0^d+x_1^d+x_2^d one can take a perturbation of a product of lines.]
Now, we have \R A inside \C A and we also have (since our polynomial is real) an involution on \CA, given by complex conjugation, which has the fixed point set \R A and reverses the orientation.
Claim: For any orientation-reversing involution on a (smooth, orientable) curve of genus g, the number of connected components of the fixed point set is at most g+1.
Proof: Look at the quotient \C A / c by the involution c, glue \ell discs along boundary components. We get a surface which may be non-orientable. The Euler characteristic of this quotient with the glued discs is at most 2 (as for any surface), so \chi(S/ c) + \ell <= 2. Which means that \chi(S)/2 + \ell <=2, or, in terms of the genus, we have 1-g + \ell <=2, leading to the desired \ell<=g+1 bound!
Definition: Type I curve is a curve for which S/c is orientable (equivalently, \C A \setminus \R A has two connected components); Type II curve is a curve for which S/c is non-orientable (equivalently, \C A \setminus \R A has one connected component).
Remark: Any maximal curve has type I. Indeed, we have equalities in the Klein's proof everywhere, so \chi(S/c with glued discs)=2, hence S/c is a sphere with holes, hence, it is orientable.
Claim (Klein's congruence): If A is of type I, then \ell (the number of connected components of \R A) has the same parity as the maximal possible value, i.e. (d-1)(d-2)/2+1.
Proof: Orientability means that the Euler characteristics is even.
For d =1, 2, 3 clearly max curves are type I and others are type II (because of Klein’s congruence). For d=4 we can classify everything except for 2 ovals case (nested or not) by same simple arguments. Two nested ovals form a curve of type I (in fact, max nest (nest=nested ovals) with d/2 ovals is always of type I, which isn’t hard to see). But two non-nested ovals is of type II, which is less obvious. [follows from the formula for complex orientations discussed below]
For d=5 we finally see that the real picture, i.e. the topological pair (\RP^2, \R A) is not enough to determine the type of the curve! (Example being a pseudo-line with four ovals).
For type I curves (in particular, for the maximal curves), we have an orientation of S/c, which induces an orientation on the connected components of \R A. These orientations are defined up to the reversal of all orientations simultaneously. We call it complex orientations.
Definition: An injective pair of ovals is simply one oval inside the other. A pair is negative if the complex orientations of the two ovals are the same (i.e. orientations can be induced by an orientation of the annulus between two ovals), and positive otherwise.
Formula for complex orientations (Rokhlin): Take even d=2k and assume the curve is of type I. Then the number \Pi^+ of positive pairs and \Pi^- of negative pairs satisfy 2(\Pi^+ - \Pi^-) = \ell -k^2, where \ell is the number of connected components of \R A (ovals).
Remark: If you have, say, four non-nested ovals for d=4, the orientations do not make sense. Since \RP^2 is non-orientable then we can move around the oval changing the orientation. The orientations really only make sense (i.e. different orientations give different topological pictures) when one oval is inside the other.
Formula for complex orientations (Rokhlin and Mishachev): Take d=2k+1, and assume the curve is of type I. Then the number \Pi^+ of positive pairs and \Pi^- of negative pairs satisfy
2(\Pi^+ - \Pi^-) + (\Lambda^+ - \Lambda^-)= \ell - 1 - k(k+1).
Here \Lambda^+ is the number of positive ovals (i.e. oriented “the same way” as the pseudo-line of \R A; formally, in the mobius band cut by the oval, twice the pseudo-line is minus the oval in the fist homology) and \Lambda^- is the number of negative ovals.
Claim: Hyperbolic curve (i.e. a curve with a maximal nest) is of type I, as discussed, and all orientations are the same, so all pairs are negative. Any curve with smaller number of ovals is always of type II.
Proof: trivial from the formula for complex orientations.
Assume d=2k is even. Let p be the number of even oval (located inside an even number of ovals) and n the number of odd ovals (located inside odd number of ovals). Actually, p is the number of connected components of \RP^2_+ (the set of points where the polynomial is positive, which does not include the outer, non-orientable, connected component), and n+1 is the number of connected components of \RP^2_-. Also, p-n = \chi (\RP^2_+), n+1-p = \chi (\RP^2_-).
Arnold congruence: p-n \equiv k^2 mod 4 for any type I course of degree d=2k.
Proof (assuming the formula for complex orientations): modulo 4 we have
2(\Pi^+ - \PI^-) = 2(\Pi^+ + \Pi^-) = 2n (for the last equality, each even oval contributes zero mod 4 to the sum 2(\Pi^+ + \Pi^-) and every odd oval contributes 2 mod 4). Also, \ell-k^2 = p+n-k^2. Putting these together gives the result: p-n = k^2 mod 4.
Alternations of complex orientations (Fiedler): Consider type I curve of degree d. Take a point P with a line swiping through it, assume that passing from one oval (touching the oval) to the next oval (i.e. till it touches it) the line has d-2 points of \RA^2 (so when it starts crossing the oval twice, it has the maximal d number of points, same when it crossed the first oval). Then the orientations of two ovals, the one we started from and the one we are going to, are opposite to each other.
For d=5 we finally see that the real picture, i.e. the topological pair (\RP^2, \R A) is not enough to determine the type of the curve! (Example being a pseudo-line with four ovals).
For type I curves (in particular, for the maximal curves), we have an orientation of S/c, which induces an orientation on the connected components of \R A. These orientations are defined up to the reversal of all orientations simultaneously. We call it complex orientations.
Definition: An injective pair of ovals is simply one oval inside the other. A pair is negative if the complex orientations of the two ovals are the same (i.e. orientations can be induced by an orientation of the annulus between two ovals), and positive otherwise.
Formula for complex orientations (Rokhlin): Take even d=2k and assume the curve is of type I. Then the number \Pi^+ of positive pairs and \Pi^- of negative pairs satisfy 2(\Pi^+ - \Pi^-) = \ell -k^2, where \ell is the number of connected components of \R A (ovals).
Remark: If you have, say, four non-nested ovals for d=4, the orientations do not make sense. Since \RP^2 is non-orientable then we can move around the oval changing the orientation. The orientations really only make sense (i.e. different orientations give different topological pictures) when one oval is inside the other.
Formula for complex orientations (Rokhlin and Mishachev): Take d=2k+1, and assume the curve is of type I. Then the number \Pi^+ of positive pairs and \Pi^- of negative pairs satisfy
2(\Pi^+ - \Pi^-) + (\Lambda^+ - \Lambda^-)= \ell - 1 - k(k+1).
Here \Lambda^+ is the number of positive ovals (i.e. oriented “the same way” as the pseudo-line of \R A; formally, in the mobius band cut by the oval, twice the pseudo-line is minus the oval in the fist homology) and \Lambda^- is the number of negative ovals.
Claim: Hyperbolic curve (i.e. a curve with a maximal nest) is of type I, as discussed, and all orientations are the same, so all pairs are negative. Any curve with smaller number of ovals is always of type II.
Proof: trivial from the formula for complex orientations.
Assume d=2k is even. Let p be the number of even oval (located inside an even number of ovals) and n the number of odd ovals (located inside odd number of ovals). Actually, p is the number of connected components of \RP^2_+ (the set of points where the polynomial is positive, which does not include the outer, non-orientable, connected component), and n+1 is the number of connected components of \RP^2_-. Also, p-n = \chi (\RP^2_+), n+1-p = \chi (\RP^2_-).
Arnold congruence: p-n \equiv k^2 mod 4 for any type I course of degree d=2k.
Proof (assuming the formula for complex orientations): modulo 4 we have
2(\Pi^+ - \PI^-) = 2(\Pi^+ + \Pi^-) = 2n (for the last equality, each even oval contributes zero mod 4 to the sum 2(\Pi^+ + \Pi^-) and every odd oval contributes 2 mod 4). Also, \ell-k^2 = p+n-k^2. Putting these together gives the result: p-n = k^2 mod 4.
Alternations of complex orientations (Fiedler): Consider type I curve of degree d. Take a point P with a line swiping through it, assume that passing from one oval (touching the oval) to the next oval (i.e. till it touches it) the line has d-2 points of \RA^2 (so when it starts crossing the oval twice, it has the maximal d number of points, same when it crossed the first oval). Then the orientations of two ovals, the one we started from and the one we are going to, are opposite to each other.
Proof: swipe the line, we have d-2 real points and so 2 complex conjugate points. In one part of \C A \setminus \R A we have one of these complex points. So we have a path of these points, connecting, in \C A \subset \C P^2, the points of touch from P of one oval and the other. When P is perturbed slightly, we get a rectangle given by the union of the paths and the orientations on the ovals are induced by the orientation of the rectangle. It's then easy to see that the orientations are opposite.
[Lecture 4]
Application of Fiedler’s observation: consider a maximal curve of degree d=6, so-called Hilbert curve, in which \R A has an “empty” oval and an oval with 9 ovals inside. Let P be a point inside the empty oval. Then going through the pencil of lines through P to cross the nine ovals inside, we will have always four points on the line and two more when we cross an inner oval. This means that the orientations of the 9 ovals alternate.
Proof of the Formula for complex orientations. We prove it in the form k^2=\ell+2*(\Pi^- - \Pi^+). We count the same thing in two different ways to prove the equality. Again, look at \C A \subset \CP^2. Look at one half of \C A given by the involution with the discs glued to it along the boundaries (the discs bounded by the corresponding ovals of \R A), call this A_+. Similarly, A_- for the second half with the glued discs. They represent homology classes in H_2(\CP^2, \Z) = \Z. Question is, what is the intersection form on A_+, A_-?
Homological approach: complex conjugation induces multiplication by -1 in H_2. Also, glued discs are in \RP^2 and so when we apply conjugation to class [A_+] we get -[A_-] (since A_+ is mapped to A_- but with opposite orientation). This means that, in fact, [A_+] = [A_-] in H_2(\CP^2, \Z). On the other hand, in the sum [A_+ + A_-] all discs cancel as they come with opposite orientation and so we are left with [\C A], which is d*[\CP^1]. Which means that [A_+]=[A_-]=k (if we identify [CP^1] with 1) and so [A_+]*[A_-] = k^2.
Geometric approach: We would like to have transversal intersections only, but of course as is, A_+ and A_- intersect by the real discs (and they are not really embedded in \CP^2 nicely), so we want to push A_+ along some vector field slightly. First, consider a vector field in \RP^2 with isolated zeroes outside of \R A which is tangent to the ovals, with a direction given by the orientation of the oval: start from the vector field on \R A and then extend it to the areas between ovals (with negative pair it is obvious, with positive also possible without the zeros; inside an inner oval you create one zero; for many ovals inside an oval, one needs to also create zeros). In every connected component of the complement of \R A, the sum of indices of the zeroes of the vector field is the Euler characteristics of the connected component.
With this vector field v constructed, consider the vector field i*v (clearly we don’t want to push discs in the real direction, we want it to move away from \RP^2 to get transversal intersections) and extend it to the plus part of \C A. Then we push A_+ along this vector field i*v to get some A’_+. Then A’_+ intersects A_- only at the zeros of the vector field and the sign of the intersection is minus the index of the vector field v at the zero. So each negative injective pair of ovals contributes +2 (cause we can take the disc of outer oval in A'_+ and the disc of inner oval in A_- or vice versa) and each positive injective pair of ovals contributes -2. Finally, every oval contributes +1 (from the corresponding disc taken in both A'_+ and A_-). Hence, the intersection is 2(\Pi^- - \Pi^+) + \ell.
Remark: for odd degree one can cheat by considering a perturbation of f^2 to use the result for even degree.
Claim: For d=6 the maximal curve cannot have all 11 ovals outside of each other.
Proof: Indeed, 2(\Pi^+ - \Pi^-)=\ell-k^2=11-9=2. So we must have at least one injective pair. Also follows from the Arnold’s congruence; p-n = k^2 = 1 mod 4, so we cannot have all ovals even.
Ragsdale conjecture: For a curve of degree d=2k, one has p<= 3k(k-1)/2+1 and n<=3k(k-1)/2. This was disproved by Viro (and then by Itenberg) using patchworking, which we will discuss later. An important open question is whether the conjecture is true for maximal curves. See this review.
Application of Fiedler’s observation: consider a maximal curve of degree d=6, so-called Hilbert curve, in which \R A has an “empty” oval and an oval with 9 ovals inside. Let P be a point inside the empty oval. Then going through the pencil of lines through P to cross the nine ovals inside, we will have always four points on the line and two more when we cross an inner oval. This means that the orientations of the 9 ovals alternate.
Proof of the Formula for complex orientations. We prove it in the form k^2=\ell+2*(\Pi^- - \Pi^+). We count the same thing in two different ways to prove the equality. Again, look at \C A \subset \CP^2. Look at one half of \C A given by the involution with the discs glued to it along the boundaries (the discs bounded by the corresponding ovals of \R A), call this A_+. Similarly, A_- for the second half with the glued discs. They represent homology classes in H_2(\CP^2, \Z) = \Z. Question is, what is the intersection form on A_+, A_-?
Homological approach: complex conjugation induces multiplication by -1 in H_2. Also, glued discs are in \RP^2 and so when we apply conjugation to class [A_+] we get -[A_-] (since A_+ is mapped to A_- but with opposite orientation). This means that, in fact, [A_+] = [A_-] in H_2(\CP^2, \Z). On the other hand, in the sum [A_+ + A_-] all discs cancel as they come with opposite orientation and so we are left with [\C A], which is d*[\CP^1]. Which means that [A_+]=[A_-]=k (if we identify [CP^1] with 1) and so [A_+]*[A_-] = k^2.
Geometric approach: We would like to have transversal intersections only, but of course as is, A_+ and A_- intersect by the real discs (and they are not really embedded in \CP^2 nicely), so we want to push A_+ along some vector field slightly. First, consider a vector field in \RP^2 with isolated zeroes outside of \R A which is tangent to the ovals, with a direction given by the orientation of the oval: start from the vector field on \R A and then extend it to the areas between ovals (with negative pair it is obvious, with positive also possible without the zeros; inside an inner oval you create one zero; for many ovals inside an oval, one needs to also create zeros). In every connected component of the complement of \R A, the sum of indices of the zeroes of the vector field is the Euler characteristics of the connected component.
With this vector field v constructed, consider the vector field i*v (clearly we don’t want to push discs in the real direction, we want it to move away from \RP^2 to get transversal intersections) and extend it to the plus part of \C A. Then we push A_+ along this vector field i*v to get some A’_+. Then A’_+ intersects A_- only at the zeros of the vector field and the sign of the intersection is minus the index of the vector field v at the zero. So each negative injective pair of ovals contributes +2 (cause we can take the disc of outer oval in A'_+ and the disc of inner oval in A_- or vice versa) and each positive injective pair of ovals contributes -2. Finally, every oval contributes +1 (from the corresponding disc taken in both A'_+ and A_-). Hence, the intersection is 2(\Pi^- - \Pi^+) + \ell.
Remark: for odd degree one can cheat by considering a perturbation of f^2 to use the result for even degree.
Claim: For d=6 the maximal curve cannot have all 11 ovals outside of each other.
Proof: Indeed, 2(\Pi^+ - \Pi^-)=\ell-k^2=11-9=2. So we must have at least one injective pair. Also follows from the Arnold’s congruence; p-n = k^2 = 1 mod 4, so we cannot have all ovals even.
Ragsdale conjecture: For a curve of degree d=2k, one has p<= 3k(k-1)/2+1 and n<=3k(k-1)/2. This was disproved by Viro (and then by Itenberg) using patchworking, which we will discuss later. An important open question is whether the conjecture is true for maximal curves. See this review.
[Lecture 5]
Rigit isotopies. For now we were interested in the topological classification of (\RP^2, \R A), which is also called an isotopy classification. Two subsets C_0, C_1 of \RP^2 are isotopic if there exists a homeomorphism h of \RP^2 such that h(C_0)=C_1 and h is isotopic to identity (in the case of \RP^2 the last part is redundant as every homeomorphism is isotopic to identity). That’s why classification up to isotopy is just the topological classification of (\RP^2, \R A).
Rigit isotopy requires that in the isotopy the intermediate sets are also zero sets of non-singular polynomials of degree d. Curves \R A and \R B are rigitly isotopic iff A and B are in the same connected component of \RC_d\setminus \D, where \D is the set of polynomials with zero discriminant.
Rigit isotopy classification differs (it is strictly stronger) from the isotopy classification for d>=5. We have already kind of seen it with d=5, as for the real scheme with a pseudo-line and four ovals the curve can be both of type I and type II and clearly rigitly isotopic curves have the same type. For d<=6 it’s true that rigit isotopy class can be determined by the real scheme plus the type but this is false starting from d=7.
For d=5 and four ovals, if ovals are in convex positions then by Fiedler’s observations, the orientation of ovals should alternate, so two ovals are oriented in one direction and two in the opposite direction, this would contradict the formula for complex orientations, thus implying that this curve is of type II. For non-convex position the curve is of type I (and the oval in the center is orriented differently from the three other ovals).
We now discuss a powerful tool for constructing various topological pairs (\RP^2, \R A) for an algebraic curve of degree d. The method is called combinatorial patchworking and is due to O. Viro.
Construction: Take a triangle with vertices (0, 0), (d, 0), (0, d) on the square grid. Choose a triangulation T of this triangle with integer vertices. Then choose signs at the vertices of the triangulation (i.e. assign plusses and minuses to the vertices of T). Now, symmetrize the triangle together with the triangulation with respect to the axes, obtaining a triangulation of the square (0, d), (d, 0), (0, -d), (-d, 0). To understand what we do with signs, let’s go back to what we’re doing:
We are trying to construct a (non-homogeneous) polynomial f(x, y) of degree d, and the triangulation T will correspond to the Newton polygon of the polynomial. So, vertices of T will correspond to the monomials of f(x, y) = \sum a_{i,j}x^i*y^j, and the signs are the signs of the corresponding a_{i,j}. When we look at the point (-i, j) from the symmetric copy of T, the symmetry corresponds to the change x\maps to -x. So the sign at (-i, j) is the sign at (i, j) if i is even and the opposite if i is odd. Similarly for a points (i, -j) and (-i, -j).
Now, we consider all triangles of the triangulation (of the square) and in each triangle which has both plusses and minuses we draw a middle line in red, separating plusses from minuses. The claim is: topologically, the red broken lines form a real algebraic curve of degree d. In the following, we denote the triangulation of the square by T^* and the union of red broken lines by L.
Thm (Viro): If the triangulation T is convex, then there exists a non-singular curve f(x, y)=0 of degree d, such that (\RP^2, \R A) is isomorphic to (T^*, L), where L is the union of red broken lines.
To get the analogous statement for the projective plane, consider the quotient of T^* (and L) by (x\sim y) if x, y are on the boundary of T^* symmetric with respect to the origin. Note that T^* is homeomorphic to a disc, so this identification of opposite points makes it homeomorphic to the projective plane indeed.
Rem: the discrete picture also captures the position of the real algebraic curve with respect to the axis.
Rigit isotopies. For now we were interested in the topological classification of (\RP^2, \R A), which is also called an isotopy classification. Two subsets C_0, C_1 of \RP^2 are isotopic if there exists a homeomorphism h of \RP^2 such that h(C_0)=C_1 and h is isotopic to identity (in the case of \RP^2 the last part is redundant as every homeomorphism is isotopic to identity). That’s why classification up to isotopy is just the topological classification of (\RP^2, \R A).
Rigit isotopy requires that in the isotopy the intermediate sets are also zero sets of non-singular polynomials of degree d. Curves \R A and \R B are rigitly isotopic iff A and B are in the same connected component of \RC_d\setminus \D, where \D is the set of polynomials with zero discriminant.
Rigit isotopy classification differs (it is strictly stronger) from the isotopy classification for d>=5. We have already kind of seen it with d=5, as for the real scheme with a pseudo-line and four ovals the curve can be both of type I and type II and clearly rigitly isotopic curves have the same type. For d<=6 it’s true that rigit isotopy class can be determined by the real scheme plus the type but this is false starting from d=7.
For d=5 and four ovals, if ovals are in convex positions then by Fiedler’s observations, the orientation of ovals should alternate, so two ovals are oriented in one direction and two in the opposite direction, this would contradict the formula for complex orientations, thus implying that this curve is of type II. For non-convex position the curve is of type I (and the oval in the center is orriented differently from the three other ovals).
We now discuss a powerful tool for constructing various topological pairs (\RP^2, \R A) for an algebraic curve of degree d. The method is called combinatorial patchworking and is due to O. Viro.
Construction: Take a triangle with vertices (0, 0), (d, 0), (0, d) on the square grid. Choose a triangulation T of this triangle with integer vertices. Then choose signs at the vertices of the triangulation (i.e. assign plusses and minuses to the vertices of T). Now, symmetrize the triangle together with the triangulation with respect to the axes, obtaining a triangulation of the square (0, d), (d, 0), (0, -d), (-d, 0). To understand what we do with signs, let’s go back to what we’re doing:
We are trying to construct a (non-homogeneous) polynomial f(x, y) of degree d, and the triangulation T will correspond to the Newton polygon of the polynomial. So, vertices of T will correspond to the monomials of f(x, y) = \sum a_{i,j}x^i*y^j, and the signs are the signs of the corresponding a_{i,j}. When we look at the point (-i, j) from the symmetric copy of T, the symmetry corresponds to the change x\maps to -x. So the sign at (-i, j) is the sign at (i, j) if i is even and the opposite if i is odd. Similarly for a points (i, -j) and (-i, -j).
Now, we consider all triangles of the triangulation (of the square) and in each triangle which has both plusses and minuses we draw a middle line in red, separating plusses from minuses. The claim is: topologically, the red broken lines form a real algebraic curve of degree d. In the following, we denote the triangulation of the square by T^* and the union of red broken lines by L.
Thm (Viro): If the triangulation T is convex, then there exists a non-singular curve f(x, y)=0 of degree d, such that (\RP^2, \R A) is isomorphic to (T^*, L), where L is the union of red broken lines.
To get the analogous statement for the projective plane, consider the quotient of T^* (and L) by (x\sim y) if x, y are on the boundary of T^* symmetric with respect to the origin. Note that T^* is homeomorphic to a disc, so this identification of opposite points makes it homeomorphic to the projective plane indeed.
Rem: the discrete picture also captures the position of the real algebraic curve with respect to the axis.