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.
Def: A triangulation is convex, is there exists a piece-wise linear convex function f whose domain of linearity is exactly the triangulation, i.e. the function is linear on each triangle but not linear on any union of two triangles. We say that the triangulation is realized by f.
Example of a non-convex triangulation: Triangle ABC, an auxiliary point X which is the center of the triangle (not used in the triangulation), triangle PQR formed by the mid-points of AX, BX, CX. The triangulation has triangles PQR, APB, BPQ, QBC, CQR, CRA, RAP.
Thm (Viro): If T is convex, realised by a function f, then the polynomial P_t(x, y) = \sum_{(i, j)\in V} \sigma_{i, j}*t^{f(i, j)}* x^i*y^j, for t sufficiently small and positive, defines a non-singular curve with real scheme equivalent to the union of red broken lines.
Example of a non-convex triangulation: Triangle ABC, an auxiliary point X which is the center of the triangle (not used in the triangulation), triangle PQR formed by the mid-points of AX, BX, CX. The triangulation has triangles PQR, APB, BPQ, QBC, CQR, CRA, RAP.
Thm (Viro): If T is convex, realised by a function f, then the polynomial P_t(x, y) = \sum_{(i, j)\in V} \sigma_{i, j}*t^{f(i, j)}* x^i*y^j, for t sufficiently small and positive, defines a non-singular curve with real scheme equivalent to the union of red broken lines.
[Lecture 6]
Now, let’s use patchworking to construct a maximal curve of degree d. Take a convex primitive triangulation (primitive means each triangle has area 1/2, on the plane it’s equivalent to having all integer points as vertices, in higher dimension it’s not equivalent, so we use the definition with the area equal to 1/2). For concreteness, let’s take a triangulation obtained by drawing all lines of the form {x=const}, {y=const}, {x+y=const}, where const varies from 0 to d. Choose the distribution of signs as follows, (i,j) (in the first quadrant) has sign + iff both i and j are even.
Claim: Using combinatorial patchworking construction, this data produces a maximal curve of degree d.
Proof: First, let’s check that the triangulation is convex. Indeed, the corresponding function can be constructed by looking at f(x, y)=x*[x]+y*[y]+(x+y)*[x+y]. To check that the curve is maximal, we need to see that there are 1+(d-1)(d-2)/2 ovals.
For a point (i, j) in the first quadrant with a plus sign, its neighbors in the triangulation are minuses, so we get a small cycle or red edges surrounding it. Similarly, for other three parities of (i, j) we have a surrounding cycle around exactly one of the points (\pm i, \pm j). The total number of integer points in the interior of T is exactly (d-1)(d-2)/2. These ovals do not cross the coordinate axis but it’s clear that we have a red segment touching the OX axis, which ensures that we must have (at least one) additional oval. For d=2k, this construction always produces a scheme with one non-empty oval with (k-1)(k-2)/2 ovals inside and 3k(k-1)/2 ovals outside, same as in the construction of Harnack. For d=2k+1 we get a psuedo-line and (d-1)(d-2)/2 empty ovals. These curves are called simple Harnack curves. See also the photo below.
Rem: Patchworking can also be used to construct algebraic curves in \P^1\times \P^1, i.e. the zero locus of a polynomials of bi-degree (a,b) in \RP^1\times \RP^1. For this one uses a similar construction but in an a \times b rectangle (together with three mirror images thereof).
Now, let’s use patchworking to construct a maximal curve of degree d. Take a convex primitive triangulation (primitive means each triangle has area 1/2, on the plane it’s equivalent to having all integer points as vertices, in higher dimension it’s not equivalent, so we use the definition with the area equal to 1/2). For concreteness, let’s take a triangulation obtained by drawing all lines of the form {x=const}, {y=const}, {x+y=const}, where const varies from 0 to d. Choose the distribution of signs as follows, (i,j) (in the first quadrant) has sign + iff both i and j are even.
Claim: Using combinatorial patchworking construction, this data produces a maximal curve of degree d.
Proof: First, let’s check that the triangulation is convex. Indeed, the corresponding function can be constructed by looking at f(x, y)=x*[x]+y*[y]+(x+y)*[x+y]. To check that the curve is maximal, we need to see that there are 1+(d-1)(d-2)/2 ovals.
For a point (i, j) in the first quadrant with a plus sign, its neighbors in the triangulation are minuses, so we get a small cycle or red edges surrounding it. Similarly, for other three parities of (i, j) we have a surrounding cycle around exactly one of the points (\pm i, \pm j). The total number of integer points in the interior of T is exactly (d-1)(d-2)/2. These ovals do not cross the coordinate axis but it’s clear that we have a red segment touching the OX axis, which ensures that we must have (at least one) additional oval. For d=2k, this construction always produces a scheme with one non-empty oval with (k-1)(k-2)/2 ovals inside and 3k(k-1)/2 ovals outside, same as in the construction of Harnack. For d=2k+1 we get a psuedo-line and (d-1)(d-2)/2 empty ovals. These curves are called simple Harnack curves. See also the photo below.
Rem: Patchworking can also be used to construct algebraic curves in \P^1\times \P^1, i.e. the zero locus of a polynomials of bi-degree (a,b) in \RP^1\times \RP^1. For this one uses a similar construction but in an a \times b rectangle (together with three mirror images thereof).
The proof of patchworking construction that we discuss below is due to Viro but it was suggested much later than the original paper was published. It follows the ideas from tropical geometry (apparently, patchworking was one of the motivations for tropical geometry).
For a second let’s consider polynomials of one variable P(x)=\sum_k a_k*x^k. Assume x is positive (recall that in patchworking we claim the result quadrant by quadrant) and moreover that a_k's are positive. Draw a graph of P(x) on log-paper, we get L_p(u)=log(\sum_k e^{k*u+b_k}), which is linear if we only have one monomial but isn’t simpler than P(x) itself when we have at least two monomials. Still, we have an easy lower bound: L_p(u) >=\max_k {k*u+b_k}. We also have an upper bound L_p(u)<= \max_k {k*u+b_k} + log(number of monomials). Now, if we replace natural log by a log with base e^{1/h} with h very small (i.e. the base of log is very large), then the two bounds become close to each other and in the limit we obtain the piece-wise linear function \max_k {k*u+b_k}.
Rem: In fact, the convergence also holds in C^1, not only in C^0.
Essentially the same mechanism allows one to go from piece-wise linear curve in the patchworking construction to an algebraic curve of non-singular curve of degree d. Of course there are several obstacles to overcome. First, coefficients can be negative… The solution will be to separately look at positive and negative coefficients, i.e. write our polynomial as a difference of two polynomials with positive coefficients and apply the procedure to each of them, we will then be interested in the intersection of two piece-wise linear surfaces (cause we have polynomials of two variables).
Rem: A similar thing appears in Maslov’s dequantization of positive real numbers. A map h*log(\cdot): \R_+ —> \R gives a structure of semi-field on \R (obtained from the structure of semi-field on \R_+). In the limit h—>0, we obtain so-called tropical operations *’ and +’ on \R given by a *’ b = a + b and a +’ b = \max{a, b}. Tropical geometry is then algebraic geometry over the tropical semi-field (\R, +’, *’), and algebraic curves are now just broken lines. Applying Maslow’s dequantization to P(x)=\sum_k a_k*x^k we get exactly \max_k {k*u+b_k} as above.
For a second let’s consider polynomials of one variable P(x)=\sum_k a_k*x^k. Assume x is positive (recall that in patchworking we claim the result quadrant by quadrant) and moreover that a_k's are positive. Draw a graph of P(x) on log-paper, we get L_p(u)=log(\sum_k e^{k*u+b_k}), which is linear if we only have one monomial but isn’t simpler than P(x) itself when we have at least two monomials. Still, we have an easy lower bound: L_p(u) >=\max_k {k*u+b_k}. We also have an upper bound L_p(u)<= \max_k {k*u+b_k} + log(number of monomials). Now, if we replace natural log by a log with base e^{1/h} with h very small (i.e. the base of log is very large), then the two bounds become close to each other and in the limit we obtain the piece-wise linear function \max_k {k*u+b_k}.
Rem: In fact, the convergence also holds in C^1, not only in C^0.
Essentially the same mechanism allows one to go from piece-wise linear curve in the patchworking construction to an algebraic curve of non-singular curve of degree d. Of course there are several obstacles to overcome. First, coefficients can be negative… The solution will be to separately look at positive and negative coefficients, i.e. write our polynomial as a difference of two polynomials with positive coefficients and apply the procedure to each of them, we will then be interested in the intersection of two piece-wise linear surfaces (cause we have polynomials of two variables).
Rem: A similar thing appears in Maslov’s dequantization of positive real numbers. A map h*log(\cdot): \R_+ —> \R gives a structure of semi-field on \R (obtained from the structure of semi-field on \R_+). In the limit h—>0, we obtain so-called tropical operations *’ and +’ on \R given by a *’ b = a + b and a +’ b = \max{a, b}. Tropical geometry is then algebraic geometry over the tropical semi-field (\R, +’, *’), and algebraic curves are now just broken lines. Applying Maslow’s dequantization to P(x)=\sum_k a_k*x^k we get exactly \max_k {k*u+b_k} as above.
[Lecture 7] [Rem: the video quality is terrible for some reason]
So, we continue with (sketch of) the proof for the patchworking construction. Split the polynomial we have, i.e. P_t(x, y) = \sum_{(i, j)\in V} \sigma_{i,j}*t^{f(i, j)}* x^i*y^j with small t>0, into two parts corresponding to positive and negative coefficients, P^+ and P^-. The intersection of their graphs, projected on the (x, y) plane, gives us the zero set of P. Now, in the t—>0 limit we get the tropical curves for P^+ and P^- (a tropic curve is a max of a collection of affine functions, so it’s a convex piece-wise linear shape).
For the convergence (of the intersection of graphs of P^+, P^_ to the intersection of corresponding tropical surfaces) to hold, we need to impose some genericity condition on the arrangement of planes in the tropical limit, for instance, that no four planes (of P^+ and P^+) meet at the same point of the graph. When we project the intersections of planes of (tropical) P^+\cup P^_ (i.e. edges of the union of two graphs together with the intersections of two graphs) onto the (x, y) plane we get a corner locus of our function, which is \max_{(i, j)\in V^+} i*u+j*v - f(i,j), the projection looks like a tropical curve (well, it is a tropical curve!) and it is, in fact, dual to the triangulation T we start from. See also the photo below.
This is just a general statement that the Newton polygon, i.e. a convex hull of points (i, j, f(i,j)), projects into the plane forming a picture dual to the corner locus (see the photo). The fact that we started from a triangulation ensures the genericity condition needed for convergence. The red lines from the statement of patchworking are just the intersection lines of P^+ and P^- (i.e. every face of the corner locus diagram comes with a sign depending on whether it is obtained from projecting a face of P^+ and P^- and edges of intersection of P^+ and P^- are exactly the edges separating the plus domain from the minus domain).
What remains is to patch (!) the four pictures corresponding to four different quadrants. See the second picture.
So, we continue with (sketch of) the proof for the patchworking construction. Split the polynomial we have, i.e. P_t(x, y) = \sum_{(i, j)\in V} \sigma_{i,j}*t^{f(i, j)}* x^i*y^j with small t>0, into two parts corresponding to positive and negative coefficients, P^+ and P^-. The intersection of their graphs, projected on the (x, y) plane, gives us the zero set of P. Now, in the t—>0 limit we get the tropical curves for P^+ and P^- (a tropic curve is a max of a collection of affine functions, so it’s a convex piece-wise linear shape).
For the convergence (of the intersection of graphs of P^+, P^_ to the intersection of corresponding tropical surfaces) to hold, we need to impose some genericity condition on the arrangement of planes in the tropical limit, for instance, that no four planes (of P^+ and P^+) meet at the same point of the graph. When we project the intersections of planes of (tropical) P^+\cup P^_ (i.e. edges of the union of two graphs together with the intersections of two graphs) onto the (x, y) plane we get a corner locus of our function, which is \max_{(i, j)\in V^+} i*u+j*v - f(i,j), the projection looks like a tropical curve (well, it is a tropical curve!) and it is, in fact, dual to the triangulation T we start from. See also the photo below.
This is just a general statement that the Newton polygon, i.e. a convex hull of points (i, j, f(i,j)), projects into the plane forming a picture dual to the corner locus (see the photo). The fact that we started from a triangulation ensures the genericity condition needed for convergence. The red lines from the statement of patchworking are just the intersection lines of P^+ and P^- (i.e. every face of the corner locus diagram comes with a sign depending on whether it is obtained from projecting a face of P^+ and P^- and edges of intersection of P^+ and P^- are exactly the edges separating the plus domain from the minus domain).
What remains is to patch (!) the four pictures corresponding to four different quadrants. See the second picture.
Now, a short discussion of tropical curves. So we have tropical numbers \T=\R\cup {-\infty}, operations are a+b (for the product) and \max{a, b} (for the sum). We have a polynomial of degree d, which is \max_{k=0, …, d} (k*x+b_k) (really the \max is only over the subset of 0,…, d for which we have monomials). A root of the polynomial is a point at which the slope of the graph changes. -\infty is a root if the slope at -\infty is not zero. Each root comes with multiplicity corresponding to the increase of the slope. Then one sees that since we start form slope 0 and end with slope d the total number of roots with multiplicities is always d. So the tropical semi-field \T should be thought of as an analogue of \C, not \R. Then \R\subset \T should be an analogue of \C^* (i.e. we remove -\infty from \T which is like removing 0 from \C).
For a tropical polynomial of two variables P(x, y)=“\sum_{(i, j)\in V} c_{i, j} x^i*y^j” = \max_{(i, j)\in V} c_{i, j} + i*x + j*y, the graph is a piece-wise linear function, it has a corner locus in \R^2 = (\T^*)^2 which is called a tropical curve (see the picture with a corner locus above). The dual to this curve is a subdivision given by a Newton polygon (the projection thereof), i.e. a convex hull of points (i, j, -c_{i, j}). For instance, a linear tropical curve looks like a tripod (with beams in the directions of (-1, 0), (0,-1) and (1, 1)): we have three planes corresponding to monomials const, x, y and the corresponding intersections project onto the beams. The role of multiplicity is now played by numbers assigned to edges of the tropical curve which correspond to the length (measured by the number of integer points minus 1) of the corresponding dual segment in the subdivision of the triangle. So the tropical curve is, in fact, the corner locus + the weights on the edges.
For a tropical polynomial of two variables P(x, y)=“\sum_{(i, j)\in V} c_{i, j} x^i*y^j” = \max_{(i, j)\in V} c_{i, j} + i*x + j*y, the graph is a piece-wise linear function, it has a corner locus in \R^2 = (\T^*)^2 which is called a tropical curve (see the picture with a corner locus above). The dual to this curve is a subdivision given by a Newton polygon (the projection thereof), i.e. a convex hull of points (i, j, -c_{i, j}). For instance, a linear tropical curve looks like a tripod (with beams in the directions of (-1, 0), (0,-1) and (1, 1)): we have three planes corresponding to monomials const, x, y and the corresponding intersections project onto the beams. The role of multiplicity is now played by numbers assigned to edges of the tropical curve which correspond to the length (measured by the number of integer points minus 1) of the corresponding dual segment in the subdivision of the triangle. So the tropical curve is, in fact, the corner locus + the weights on the edges.