[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.
Here is everything I've written up about the topological aspects of algebraic geometry in a single post:
https://telegra.ph/Topological-aspects-of-algebraic-geometry-02-28
https://telegra.ph/Topological-aspects-of-algebraic-geometry-02-28
Telegraph
Topological aspects of algebraic geometry
These unproofread notes follow the first 7 lectures of the course given by Ilia Itenberg in Geneva in the fall of 2016; videos of lectures are here. The general question we will have in mind is the following: Given a homogeneous non-singular polynomial f(x…
Starting from Lecture 8, the number of variables increased by 1: Now one considers surfaces in \RP^3 given by a homogeneous polynomial f(x, y, z, t) of degree d. Many things change and become more complicated:
-- The topology of \R A itself (i.e. topology of connected components of the surface) can be non-trivial.
-- For d even, the surface is orientable since \RP^3 is orientable and the paritition of \RP^3 into "positive" and "negative" part induces a co-orientation of the surface.
-- The topology cannot be too crazy, for instance, Klein bottle cannot be embedded into \RP^3. Also, there can be at most one non-orientable component since any two non-orientable surfaces in \RP^3 must intersect each other!
-- For d=3 we can have: \RP^2 union with S^2, or a connected sum of k projective planes with k=1, 3, 5, 7.
-- The Harnack bound (for the number of ovals) now gets replaced with the Smith-Thom inequality: the total Betti number (with Z/2 coefficients) is upper-bounded by the total Betti number of the complex surface \C A, which is a function of d, namely d^3-4d^2+4d. This bound is known to be sharp, for instance, using patchworking construction. On the other hand, the maximal number of connected components (i.e. b_0) is not known even for d=5: it's known to be 23, 24 or 25.
-- The topology of \R A itself (i.e. topology of connected components of the surface) can be non-trivial.
-- For d even, the surface is orientable since \RP^3 is orientable and the paritition of \RP^3 into "positive" and "negative" part induces a co-orientation of the surface.
-- The topology cannot be too crazy, for instance, Klein bottle cannot be embedded into \RP^3. Also, there can be at most one non-orientable component since any two non-orientable surfaces in \RP^3 must intersect each other!
-- For d=3 we can have: \RP^2 union with S^2, or a connected sum of k projective planes with k=1, 3, 5, 7.
-- The Harnack bound (for the number of ovals) now gets replaced with the Smith-Thom inequality: the total Betti number (with Z/2 coefficients) is upper-bounded by the total Betti number of the complex surface \C A, which is a function of d, namely d^3-4d^2+4d. This bound is known to be sharp, for instance, using patchworking construction. On the other hand, the maximal number of connected components (i.e. b_0) is not known even for d=5: it's known to be 23, 24 or 25.
Let's switch gears. A famous Furstenberg–Sárközy theorem states that any square-difference-free set (i.e. set of numbers such that no difference of two numbers from the set is a perfect square) has density zero. The proof is Fourier analysis quite similar to the proof of Roth's theorem about sets without a 3-term arithmetic progression. See this explanation by Tao, for instance.
Today I leared a simple construction showing a lower bound for the size of a subset of [1...N] without pairs a, b such that b-a is a square. Apparently, Erdös thought that the bound O(n^{1/2}*polylog{n}) should hold true, but it turns out that even a weaker bound of O(n^{1/2+\eps}) is false:
Consider a set S of numbers which, in base 5, have arbitrary digits at even places (from the right), and only digits 0, 2 at odd places. Since 2-0 and 0-2 are not squares modulo 5, one sees that for a, b\in S the number b-a cannot be a square (proof: consider the first place from the right in base 5 where a & b differ). This set, when restricted to [1...N] has size \Omega(N^\alpha) with \alpha=1/2*(1+log(2)/log(5))\approx 0.7153
On can improve the lower bound by considering different sets of digits modulo some large base number b. With b=205 a suitable set of 12 numbers exists leading to \alpha=0.7334..., see here. This is best known, as far as I understand. The argument is due to Ruzsa who used a set of 7 numbers modulo 65 to get exponent \alpha=0.7331...
Today I leared a simple construction showing a lower bound for the size of a subset of [1...N] without pairs a, b such that b-a is a square. Apparently, Erdös thought that the bound O(n^{1/2}*polylog{n}) should hold true, but it turns out that even a weaker bound of O(n^{1/2+\eps}) is false:
Consider a set S of numbers which, in base 5, have arbitrary digits at even places (from the right), and only digits 0, 2 at odd places. Since 2-0 and 0-2 are not squares modulo 5, one sees that for a, b\in S the number b-a cannot be a square (proof: consider the first place from the right in base 5 where a & b differ). This set, when restricted to [1...N] has size \Omega(N^\alpha) with \alpha=1/2*(1+log(2)/log(5))\approx 0.7153
On can improve the lower bound by considering different sets of digits modulo some large base number b. With b=205 a suitable set of 12 numbers exists leading to \alpha=0.7334..., see here. This is best known, as far as I understand. The argument is due to Ruzsa who used a set of 7 numbers modulo 65 to get exponent \alpha=0.7331...
Today I learned what the size of the A4 paper is! Three fundamental facts (of which I had previously only known the first two) are:
-- A0, A1, A2, A3, etc all have the same aspect ratio;
-- A[k+1] is simply one half of the A[k] paper;
-- A0 paper has area 1 square meter.
From the first two properties it's easy to see that the aspect ratio is always 1:sqrt{2}. From the last fact we deduce that A0 paper is 2^{1/4} by 2^{-1/4}, and A4, having area 1/16 of a square meter, has size 2^{1/4}/4 by 2^{-1/4}/4 which is roughly 210mm by 297mm.
-- A0, A1, A2, A3, etc all have the same aspect ratio;
-- A[k+1] is simply one half of the A[k] paper;
-- A0 paper has area 1 square meter.
From the first two properties it's easy to see that the aspect ratio is always 1:sqrt{2}. From the last fact we deduce that A0 paper is 2^{1/4} by 2^{-1/4}, and A4, having area 1/16 of a square meter, has size 2^{1/4}/4 by 2^{-1/4}/4 which is roughly 210mm by 297mm.
Call a set S of positive integers massive if 1 can be written as a sum of reciprocals of some of the elements of S.
Conjecture: If the set of all positive integers is partitioned into finite number of sets, then one of them is massive.
The conjecture is due to Erdös and Graham, and was proved by Croot (paper) in 2003. The proof is technically complicated and delicate but mostly elementary: one needs to know Dickman's result about the number of N^\theta-smooth numbers up to N, some results about distribution of primes and prime divisors (like prime number theorem and the fact that almost every number n has \log\log n prime divisors), and some basics about the exponential sums.
Interestingly, this problem was proposed to me and my fellow math circle attendees when I was in the 9th grade...
Conjecture: If the set of all positive integers is partitioned into finite number of sets, then one of them is massive.
The conjecture is due to Erdös and Graham, and was proved by Croot (paper) in 2003. The proof is technically complicated and delicate but mostly elementary: one needs to know Dickman's result about the number of N^\theta-smooth numbers up to N, some results about distribution of primes and prime divisors (like prime number theorem and the fact that almost every number n has \log\log n prime divisors), and some basics about the exponential sums.
Interestingly, this problem was proposed to me and my fellow math circle attendees when I was in the 9th grade...
Suppose that P is a finite set of points in the plane, not all on one line. Then there is an ordinary line spanned by P, that is to say a line in P containing exactly two points.
This is a famous Sylvester-Gallai theorem. The problem was apparently first proposed by Sylvester in 1893. Before explaining the proof as well as various generalizations, let me advertise the website https://woollymathematics.com/ where this problem appears among many others (see problem 11851, NB: solution provided is complete nonsense).
The proof of the theorem is elegant and short: take three points A, B, C from the configuration not on the same line such that the distance dist(C, AB) from point C to the line AB is the smallest possible. It's easy to see that AB is then an ordinary line for otherwise there would be a smaller distance.
Dirac-Motzkin conjecture states that, in fact, one always has at least n/2 ordinary lines. This was proved by Green and Tao (see this paper) for all sufficiently large n as a consequence of the following structural theorem: If a configuration P of n points on the plane spans at most K*n ordinary lines, then all but O_K(1) points of the configuration lie on an algebraic curve of degree at most 3. In the opposite direction, note that since points on an elliptic curve form an Abelian group isomorphic to \R/\Z (or that times \Z/2\Z), we can choose a cyclic subgroup of order n which creates a configuration with only n+O(1) ordinary lines.
I recently learned that Sylvester-Gallai theorem is false in the complex plane. Here is a counterexample: Take an auxiliary triangle ABC and some positive integer n\geq 3. For each z\in \C satisfying z^n=1 add to the configuration the following three points: X_c on the line AB such that AX/XB = z as well as similarly-defined points X_a on the line BC and X_b on the line AC. Menelaus's theorem readily implies that any line passing through two points of the configuration also passes through a third point. Note that we need n\geq 3 so that each side of the original auxiliary triangle contains at least three points.
Here are some (likely open) questions:
Is there a counterexample over \Q[\sqrt{-2}]?
Is it true that any counterexample over \C has a subset in the form described above?
This is a famous Sylvester-Gallai theorem. The problem was apparently first proposed by Sylvester in 1893. Before explaining the proof as well as various generalizations, let me advertise the website https://woollymathematics.com/ where this problem appears among many others (see problem 11851, NB: solution provided is complete nonsense).
The proof of the theorem is elegant and short: take three points A, B, C from the configuration not on the same line such that the distance dist(C, AB) from point C to the line AB is the smallest possible. It's easy to see that AB is then an ordinary line for otherwise there would be a smaller distance.
Dirac-Motzkin conjecture states that, in fact, one always has at least n/2 ordinary lines. This was proved by Green and Tao (see this paper) for all sufficiently large n as a consequence of the following structural theorem: If a configuration P of n points on the plane spans at most K*n ordinary lines, then all but O_K(1) points of the configuration lie on an algebraic curve of degree at most 3. In the opposite direction, note that since points on an elliptic curve form an Abelian group isomorphic to \R/\Z (or that times \Z/2\Z), we can choose a cyclic subgroup of order n which creates a configuration with only n+O(1) ordinary lines.
I recently learned that Sylvester-Gallai theorem is false in the complex plane. Here is a counterexample: Take an auxiliary triangle ABC and some positive integer n\geq 3. For each z\in \C satisfying z^n=1 add to the configuration the following three points: X_c on the line AB such that AX/XB = z as well as similarly-defined points X_a on the line BC and X_b on the line AC. Menelaus's theorem readily implies that any line passing through two points of the configuration also passes through a third point. Note that we need n\geq 3 so that each side of the original auxiliary triangle contains at least three points.
Here are some (likely open) questions:
Is there a counterexample over \Q[\sqrt{-2}]?
Is it true that any counterexample over \C has a subset in the form described above?
Not immediately clear what it's good for but Evan Chen is writing an introduction to university-level mathematics, a project known under the name of Napkin.
Reading merely 1050 pages you can learn about some (mostly basic) mathematics.
https://venhance.github.io/napkin/Napkin.pdf
Reading merely 1050 pages you can learn about some (mostly basic) mathematics.
https://venhance.github.io/napkin/Napkin.pdf
While his son was doing God knows what, Yan Fyodorov conjectured the behaviour of the Riemman zeta function on the critical line. Here is the conjecture:
Take T large and sample a uniform random variable \tau\in [T, 2T]. Let f(\tau) be the maximum of the log|\zeta(1/2+i*u)| in the 1-neighbourhood of \tau, i.e for u \in [\tau-1, \tau+1], then
f(\tau) = \log\log T - 3/4*\log\log\log T + X + o_P(1),
where X is some explicit random variable and o_P(1) is a random variable converging to zero in probability as T tends to infinity.
This conjecture, known as FHK conjecture (Fyodorov-Hiary-Keating) comes from the idea of universality, which I dearly love. Fyodorov and Keating being mathematical physicists (I am not sure about Hiary) roughly speaking say that \log\zeta on the critical line should behave as any other log-correlated field and hence it suffices to look at the simpliest model in the same universality class to understand its behaviour. Note that a bit of care is needed as the precise random variable X in the conjecture is not universal, while the first two terms, including the 3/4 coefficients, are universal.
Before getting to the FHK conjecture, let's discuss how it all started. The story of estimating |\zeta(1/2+it)| satistically (i.e. for typical large t) perhaps starts from celebrated Selberg's CLT:
With \tau again uniform on [T, 2T] one has \log|\zeta(1/2+it)|/sqrt{1/2*\log\log T} --> \N(0, 1),
where convergence to the normal random variable is in distribution as T tends to infinity.
The proof is quite technical but the main idea is not so difficult to grasp. One should approximate the value \zeta(1/2+i*t) by truncated Euler product \prod_{p<X} (1-p^{-1/2-i*t})^{-1}. To make this rigorous one would like to move slightly away from the critical line (by distance a bit more than 1/log{T}), and also carefully choose a truncation parameter X at roughly T^{o(1)} but it somehow works. The rest is just an intuition saying that p^{-1/2-i*t}=e^{-i*log{p}*t}/sqrt(p) and since log p's are linearly independent over \Q, one should think of each term as being U_p/sqrt(p), where U_p's are roughly i.i.d uniform random variables on the unit circle.
Now, when we look at \log|\zeta(1/2+i*t)| we get a sum \sum_{p<X} \Re log(1-e^{-i*log{p}*t}/sqrt(p)), so taking first order Taylor approximation for log, we get \sum_{p<X} -\Re U_p/sqrt(p). Assuming independence of U_p's and the fact that they are uniform, we have zero mean and variance
\sum_{p<X} 1/p*\E[(\Re U_p)^2].
What is the expectation of the square of the first coordinate of a point chosen uniformly on a unit circle? Well, we have two coordinates, their sum of squares is 1, and they play symmetric roles, so the answer must be 1/2. Merten's theorem (which is elementary) says that \sum_{p<X} 1/p = \log\log X +O(1) which is multiplicatively very close to \log\log T with our choice of X. Selberg's CLT then follows.
If I understood correctly, approximate independence of U_p's is quite easy and technically trickier part is to approximate the value at a point (1/2+i*t) by truncated Euler product.
Okay, so what's the deal with FHT conjecture? Using similar heuristics, if we look at two values \log|\zeta(1/2+i*(\tau+h_1))| and \log|\zeta(1/2+i*(\tau+h_2))|, then they will be quite strongly correlated for |h_1-h_2|<<1/log{T} and rather uncorrelated otherwise. To see this note that we have e^{-i*log{p}*t} appearing which does not change much precisely when we shift t by something much smaller than 1/log T. So at each point 1/2+i(\tau+h), where h runs from -1 to 1, we have \log|\zeta(1/2+i*(\tau+h))| being Gaussian but these Gaussians are strongly correlated at spacing smaller than 1/\log T (notice that this is also the typical spacing between zeroes of the zeta function on the critical line, this is related to the, now proved, Montgomery's pair correlation conjecture, hearing which Freeman Dyson famously replied that the same pair correlations appear in random matrix theory, this all happened at IAS in Princeton, of course).
Take T large and sample a uniform random variable \tau\in [T, 2T]. Let f(\tau) be the maximum of the log|\zeta(1/2+i*u)| in the 1-neighbourhood of \tau, i.e for u \in [\tau-1, \tau+1], then
f(\tau) = \log\log T - 3/4*\log\log\log T + X + o_P(1),
where X is some explicit random variable and o_P(1) is a random variable converging to zero in probability as T tends to infinity.
This conjecture, known as FHK conjecture (Fyodorov-Hiary-Keating) comes from the idea of universality, which I dearly love. Fyodorov and Keating being mathematical physicists (I am not sure about Hiary) roughly speaking say that \log\zeta on the critical line should behave as any other log-correlated field and hence it suffices to look at the simpliest model in the same universality class to understand its behaviour. Note that a bit of care is needed as the precise random variable X in the conjecture is not universal, while the first two terms, including the 3/4 coefficients, are universal.
Before getting to the FHK conjecture, let's discuss how it all started. The story of estimating |\zeta(1/2+it)| satistically (i.e. for typical large t) perhaps starts from celebrated Selberg's CLT:
With \tau again uniform on [T, 2T] one has \log|\zeta(1/2+it)|/sqrt{1/2*\log\log T} --> \N(0, 1),
where convergence to the normal random variable is in distribution as T tends to infinity.
The proof is quite technical but the main idea is not so difficult to grasp. One should approximate the value \zeta(1/2+i*t) by truncated Euler product \prod_{p<X} (1-p^{-1/2-i*t})^{-1}. To make this rigorous one would like to move slightly away from the critical line (by distance a bit more than 1/log{T}), and also carefully choose a truncation parameter X at roughly T^{o(1)} but it somehow works. The rest is just an intuition saying that p^{-1/2-i*t}=e^{-i*log{p}*t}/sqrt(p) and since log p's are linearly independent over \Q, one should think of each term as being U_p/sqrt(p), where U_p's are roughly i.i.d uniform random variables on the unit circle.
Now, when we look at \log|\zeta(1/2+i*t)| we get a sum \sum_{p<X} \Re log(1-e^{-i*log{p}*t}/sqrt(p)), so taking first order Taylor approximation for log, we get \sum_{p<X} -\Re U_p/sqrt(p). Assuming independence of U_p's and the fact that they are uniform, we have zero mean and variance
\sum_{p<X} 1/p*\E[(\Re U_p)^2].
What is the expectation of the square of the first coordinate of a point chosen uniformly on a unit circle? Well, we have two coordinates, their sum of squares is 1, and they play symmetric roles, so the answer must be 1/2. Merten's theorem (which is elementary) says that \sum_{p<X} 1/p = \log\log X +O(1) which is multiplicatively very close to \log\log T with our choice of X. Selberg's CLT then follows.
If I understood correctly, approximate independence of U_p's is quite easy and technically trickier part is to approximate the value at a point (1/2+i*t) by truncated Euler product.
Okay, so what's the deal with FHT conjecture? Using similar heuristics, if we look at two values \log|\zeta(1/2+i*(\tau+h_1))| and \log|\zeta(1/2+i*(\tau+h_2))|, then they will be quite strongly correlated for |h_1-h_2|<<1/log{T} and rather uncorrelated otherwise. To see this note that we have e^{-i*log{p}*t} appearing which does not change much precisely when we shift t by something much smaller than 1/log T. So at each point 1/2+i(\tau+h), where h runs from -1 to 1, we have \log|\zeta(1/2+i*(\tau+h))| being Gaussian but these Gaussians are strongly correlated at spacing smaller than 1/\log T (notice that this is also the typical spacing between zeroes of the zeta function on the critical line, this is related to the, now proved, Montgomery's pair correlation conjecture, hearing which Freeman Dyson famously replied that the same pair correlations appear in random matrix theory, this all happened at IAS in Princeton, of course).
So, a naive guess for the maximum of \log{\zeta(1/2+i*t)} on a typical interval of length 1 would be to compare it with a maximum of \log{T} random variables, which are independent and each of which has \N(0, 1/2*\log\log T) distribution.
Classical back-of-the-envelope calculation (matching the tail probability e^{-K^2/2}/K to 1/M) says that maximum of M i.i.d N(0, 1) random variables is \sqrt(2*\log M)-\log\log M / (2*sqrt(2*log(M)))*(1+o(1)) with high probability. More precise computation leads to the Gumbel distribution with density e^{-e^{-x}} appearing. Okay, we now need to plug in M=\log T for the number of samples and then multiply it by \sigma=sqrt(1/2*\log\log T) for the variance of each value. Well, we just put additional \log in front of M which we replace with T, and multiply by \sigma to get
[\sqrt(2*\log \log T)-\log\log \log T / (2*sqrt(2*\log\log T)))] * sqrt(1/2*\log\log T)
The first term then becomes \log\log T, while the second term becomes -1/4*\log\log\log T, which looks similar to the FHT conjecture except for the fact that we have 1/4 rather than 3/4, so this heuristics gives larger maximum.
The reason is that values at distance larger than \log{T} are still correlated, even if weakly. So a better way of modeling this situation is branching Brownian motion (or random walk):
Consider the following model of branching Brownian motion: Take usual BM which starts and after random time with exponential distribution it splits into two, then each of them again splits into two after independed exponentially distiuted time, etc. By time t we expect to have e^t particles (this can be seen by solving a differential equation for this expectation: d\E[N(t)]/dt = \E[N(t)] as at any time within infinitesimal time \eps each particle splits with probability \eps). At the end, each particle has hight distributed as N(0, t/2), just as the end point of a BM up to time t. If we modeled these particles as independent, using the computation above with M=e^t and \sigma=sqrt(t/2), we would expect the maximal hight to roughly be
sqrt(t/2)*(\sqrt(2*t)-\log t / (2*sqrt(2t))) = t - 1/4*log t,
similarly to the above. Yet, a theorem of Bramson says that the reality should be t - 3/4 * log(t).
I struggle to find a nice one-line heuristics why we should expect 3/4 appearing. Heauristics in the paper of Bramson is more like a one-page heuristics. What is clear is that because of the positive correlation the maximum should be lower: If one particle gets to some hight then many other articles get to almost the same hight, so the expected number of particles close to the maximum should be larger than 1.
So FHT conjecture is a refined version of the prediction that the behaviour of the Riemann zeta function on the critical line falls into the universality class of these log-correlated fields. In fact, 2D discrete GFF and spectrum of a random CUE matrix are also in the same universality class. In the latter case one does not look at the spectrum directly but rather at the behaviour of the characteristic polynomial on the unit circle, then maximum of the log of the absolute value should also be \log N - 3/4*\log\log N + Y+ o_P(1) for some random variable Y. I think the progress on the random matrix side is more substential but the whole conjecture has not been resolved yet.
Let me mention that though FHK for the Riemann zeta function has not yet been proved, it has been proved that the coefficient should be 3/4 and perhaps it is even shown that after substracting first two terms we get a tight sequence of random variables.
Here are slides discussing this story. Most of these things were explained to me today by Ansh Saxena.
Classical back-of-the-envelope calculation (matching the tail probability e^{-K^2/2}/K to 1/M) says that maximum of M i.i.d N(0, 1) random variables is \sqrt(2*\log M)-\log\log M / (2*sqrt(2*log(M)))*(1+o(1)) with high probability. More precise computation leads to the Gumbel distribution with density e^{-e^{-x}} appearing. Okay, we now need to plug in M=\log T for the number of samples and then multiply it by \sigma=sqrt(1/2*\log\log T) for the variance of each value. Well, we just put additional \log in front of M which we replace with T, and multiply by \sigma to get
[\sqrt(2*\log \log T)-\log\log \log T / (2*sqrt(2*\log\log T)))] * sqrt(1/2*\log\log T)
The first term then becomes \log\log T, while the second term becomes -1/4*\log\log\log T, which looks similar to the FHT conjecture except for the fact that we have 1/4 rather than 3/4, so this heuristics gives larger maximum.
The reason is that values at distance larger than \log{T} are still correlated, even if weakly. So a better way of modeling this situation is branching Brownian motion (or random walk):
Consider the following model of branching Brownian motion: Take usual BM which starts and after random time with exponential distribution it splits into two, then each of them again splits into two after independed exponentially distiuted time, etc. By time t we expect to have e^t particles (this can be seen by solving a differential equation for this expectation: d\E[N(t)]/dt = \E[N(t)] as at any time within infinitesimal time \eps each particle splits with probability \eps). At the end, each particle has hight distributed as N(0, t/2), just as the end point of a BM up to time t. If we modeled these particles as independent, using the computation above with M=e^t and \sigma=sqrt(t/2), we would expect the maximal hight to roughly be
sqrt(t/2)*(\sqrt(2*t)-\log t / (2*sqrt(2t))) = t - 1/4*log t,
similarly to the above. Yet, a theorem of Bramson says that the reality should be t - 3/4 * log(t).
I struggle to find a nice one-line heuristics why we should expect 3/4 appearing. Heauristics in the paper of Bramson is more like a one-page heuristics. What is clear is that because of the positive correlation the maximum should be lower: If one particle gets to some hight then many other articles get to almost the same hight, so the expected number of particles close to the maximum should be larger than 1.
So FHT conjecture is a refined version of the prediction that the behaviour of the Riemann zeta function on the critical line falls into the universality class of these log-correlated fields. In fact, 2D discrete GFF and spectrum of a random CUE matrix are also in the same universality class. In the latter case one does not look at the spectrum directly but rather at the behaviour of the characteristic polynomial on the unit circle, then maximum of the log of the absolute value should also be \log N - 3/4*\log\log N + Y+ o_P(1) for some random variable Y. I think the progress on the random matrix side is more substential but the whole conjecture has not been resolved yet.
Let me mention that though FHK for the Riemann zeta function has not yet been proved, it has been proved that the coefficient should be 3/4 and perhaps it is even shown that after substracting first two terms we get a tight sequence of random variables.
Here are slides discussing this story. Most of these things were explained to me today by Ansh Saxena.
Anyone interested in improving the state-of-the-art result for the lonely runner conjecture?
Lonely runner conjecture states that if k+1 runners start a race running on a circle of unit length with distinct speeds v_1, v_2, ..., v_{k+1} then for each index i there exists time t such that at time t the i-th runner is at least 1/(k+1) far away from all other runners. By substracting the speed of the i-th runner this can be formulated as:
Given non-zero real numbers v_1, ..., v_k there exists t such that t*v_j is at least 1/(k+1) far away from any integer for all j.
This conjecture remains wide open but it was resolved for 2, 3, 4, 5, 6, 7, and, very recently, for 8 runner. The result for 8 runners is in [1]. Here is the outline of the proof:
First, if speeds are just some generic real numbers, then conjecture is easy since one can ensure that all runners have fractional part close to 1/2 simultaneously. Thinking about this carefully one ends up showing that one only needs to show this conjecture for rational speeds which we can then scale to get integer speeds. Moreover, if speeds are super large, then we can sort of treat them as generic reals easily solving the problem again. This line of thoughts leads to the claim that the Lonely runner conjecture for n runners is true as long it is true for integer speeds not exceeding some value f(n). Doing this more carefully leads to a n^{Cn^2} bound, see this post by Terry Tao [2]. This was subsequently improved and made explicit with the bound (roughly for the sum of speeds) of (k+1 \choose 2)^{k-1}.
Of course, checking all possible speeds summing to something less than (k+1 \choose 2)^{k-1} is infeasible even for k=5, so one should be smarter. An outline of the proof for 8 runners (k=7) from [1] is as follows. If a counterexmaple exists, sum of speeds v_1+...+v_7 should be at most 28^6. Now, if none of v_j are divisible by 6, say, then at time t=1/6 all runners are 1/6 far from the origin. Hence, we have v_1*v_2*...*v_7 divisible by lcm{2, 3, 4, 5, 6, 7 ,8}. We now want to show that this product must also be divisible by larger primes, once we find many primes with product exceeding (28^6/7)^7/lcm{2, 3, 4, 5, 6, 7 ,8} we get a contradiction.
For a fixed prime p, assuming none of v_j's are divisible by p we can essentially argue that one of the times j/(p*(k+1)) works for some j\in \Z/p(k+1)\Z. To show this claim it suffices to do some finite check depending on the set of speeds modulo p*(k+1). This discretized version of lonely runner, see Lemma 6 [1], is roughly equivalent to some cover problem: Given several subsets of the ground set, find the smallest collection of subsets which union covers the whole ground set. This is known to be NP complete but for the problem at hand we have not so large of numbers: it is enough to check primes up to 163 (of which all numbers from 31 work except for 41), so our ground set is of size at most 8*163=1304. Moreover, it's not surprizing that if the Lonely runner conjecture is true then its discretized version with prime p should also work with few exceptions.
The author of [1] implements some backtracking algorithm for solving this cover problem, which takes 32 hours, but he himself says that SAT solvers should do better, and likely even be enough to cover the k=8 case (i.e. 9 runners). I did some back of the envelope computation for the number of clauses and it seems that SAT solvers should basically solve this problem instantly for k=9 if they are as good as they are advertized.
Maybe ask chatGPT to write the code and then boast about how AI solved a math problem?..
By the way, there is a nice recent overview, "The Lonely Runner Conjecture turns 60" [4] which discusses the results concerning the lonely runner conjecture and gives several elegant reformulations of the conjecture, mostly in geometric terms, which look somewhat similar to the Bang's conjecture about covering a convex polytope with planks.
Lonely runner conjecture states that if k+1 runners start a race running on a circle of unit length with distinct speeds v_1, v_2, ..., v_{k+1} then for each index i there exists time t such that at time t the i-th runner is at least 1/(k+1) far away from all other runners. By substracting the speed of the i-th runner this can be formulated as:
Given non-zero real numbers v_1, ..., v_k there exists t such that t*v_j is at least 1/(k+1) far away from any integer for all j.
This conjecture remains wide open but it was resolved for 2, 3, 4, 5, 6, 7, and, very recently, for 8 runner. The result for 8 runners is in [1]. Here is the outline of the proof:
First, if speeds are just some generic real numbers, then conjecture is easy since one can ensure that all runners have fractional part close to 1/2 simultaneously. Thinking about this carefully one ends up showing that one only needs to show this conjecture for rational speeds which we can then scale to get integer speeds. Moreover, if speeds are super large, then we can sort of treat them as generic reals easily solving the problem again. This line of thoughts leads to the claim that the Lonely runner conjecture for n runners is true as long it is true for integer speeds not exceeding some value f(n). Doing this more carefully leads to a n^{Cn^2} bound, see this post by Terry Tao [2]. This was subsequently improved and made explicit with the bound (roughly for the sum of speeds) of (k+1 \choose 2)^{k-1}.
Of course, checking all possible speeds summing to something less than (k+1 \choose 2)^{k-1} is infeasible even for k=5, so one should be smarter. An outline of the proof for 8 runners (k=7) from [1] is as follows. If a counterexmaple exists, sum of speeds v_1+...+v_7 should be at most 28^6. Now, if none of v_j are divisible by 6, say, then at time t=1/6 all runners are 1/6 far from the origin. Hence, we have v_1*v_2*...*v_7 divisible by lcm{2, 3, 4, 5, 6, 7 ,8}. We now want to show that this product must also be divisible by larger primes, once we find many primes with product exceeding (28^6/7)^7/lcm{2, 3, 4, 5, 6, 7 ,8} we get a contradiction.
For a fixed prime p, assuming none of v_j's are divisible by p we can essentially argue that one of the times j/(p*(k+1)) works for some j\in \Z/p(k+1)\Z. To show this claim it suffices to do some finite check depending on the set of speeds modulo p*(k+1). This discretized version of lonely runner, see Lemma 6 [1], is roughly equivalent to some cover problem: Given several subsets of the ground set, find the smallest collection of subsets which union covers the whole ground set. This is known to be NP complete but for the problem at hand we have not so large of numbers: it is enough to check primes up to 163 (of which all numbers from 31 work except for 41), so our ground set is of size at most 8*163=1304. Moreover, it's not surprizing that if the Lonely runner conjecture is true then its discretized version with prime p should also work with few exceptions.
The author of [1] implements some backtracking algorithm for solving this cover problem, which takes 32 hours, but he himself says that SAT solvers should do better, and likely even be enough to cover the k=8 case (i.e. 9 runners). I did some back of the envelope computation for the number of clauses and it seems that SAT solvers should basically solve this problem instantly for k=9 if they are as good as they are advertized.
Maybe ask chatGPT to write the code and then boast about how AI solved a math problem?..
By the way, there is a nice recent overview, "The Lonely Runner Conjecture turns 60" [4] which discusses the results concerning the lonely runner conjecture and gives several elegant reformulations of the conjecture, mostly in geometric terms, which look somewhat similar to the Bang's conjecture about covering a convex polytope with planks.
At the end, let me mention that I believe lonely runner conjecture to be wrong with a huge margin. Taking a random time it's easy to see that a gap of 1/(2k) always exists and I believe that for large k, even the bound of 1/(1.99*k) is wrong. See also this post [3] of Tao where he explains how to improve 1/(2k) by something of the order of log{k}/k^2.
[1] https://www.arxiv.org/pdf/2509.14111
[2] https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-conjecture/
[3] https://terrytao.wordpress.com/2017/01/10/some-remarks-on-the-lonely-runner-conjecture/
[4] https://arxiv.org/pdf/2409.20160
[1] https://www.arxiv.org/pdf/2509.14111
[2] https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-conjecture/
[3] https://terrytao.wordpress.com/2017/01/10/some-remarks-on-the-lonely-runner-conjecture/
[4] https://arxiv.org/pdf/2409.20160
Here is one interesting fact.
When you have a Markov chain (think of a random walk on a finite graph) an important quantity to look at is mixing time: How many steps does one need to take so that the distribution becomes close to the stationary distribution of the Markov chain? One instance of this problem is: How many shuffles are required to mix a deck of card?
There are several ways to measure closeness but people typically use total variation distance, and define close to be “TV distance at most 1/4” (any smaller constant changes mixing time by at most a constant factor and usually even less).
Often one wants to sample from the stationary distribution by running the Markov chain. A natural question then arises: can we define a stopping time (a decision process for deciding when to stop the Markov chain, possibly depending on its trajectory) so that the end point distribution is approximating stationary measure much better than naive stopping at deterministic time T?
There may be periodicity issues (like random walk on a bipartite graph) when the measure coming from stopping at time T just does not converge. So one would rather want to stop and random time, let’s say uniformly random from 1 to T (from T/2 to T would also work).
Turns out, you cannot do much better: if you have a stopping time which, in expectation, is at most \eps*T, then the distance to the stationary measure you can get is at least the one from the Uniform(1…T) stopping time minus \eps. Meaning that up to constant factors, stopping at uniformly random time is at least as good as stopping at some carefully chosen time which depends on the trajectory.
When you have a Markov chain (think of a random walk on a finite graph) an important quantity to look at is mixing time: How many steps does one need to take so that the distribution becomes close to the stationary distribution of the Markov chain? One instance of this problem is: How many shuffles are required to mix a deck of card?
There are several ways to measure closeness but people typically use total variation distance, and define close to be “TV distance at most 1/4” (any smaller constant changes mixing time by at most a constant factor and usually even less).
Often one wants to sample from the stationary distribution by running the Markov chain. A natural question then arises: can we define a stopping time (a decision process for deciding when to stop the Markov chain, possibly depending on its trajectory) so that the end point distribution is approximating stationary measure much better than naive stopping at deterministic time T?
There may be periodicity issues (like random walk on a bipartite graph) when the measure coming from stopping at time T just does not converge. So one would rather want to stop and random time, let’s say uniformly random from 1 to T (from T/2 to T would also work).
Turns out, you cannot do much better: if you have a stopping time which, in expectation, is at most \eps*T, then the distance to the stationary measure you can get is at least the one from the Uniform(1…T) stopping time minus \eps. Meaning that up to constant factors, stopping at uniformly random time is at least as good as stopping at some carefully chosen time which depends on the trajectory.