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.
Here is a proof: suppose some stopping time S achieves very small distance to the stationary. Let’s run additional Uniform(1..T) steps on top of S steps. The measure of the end point is still very close to stationary since running a fixed number of steps from the stationary measure still gives you a stationary measure. Now, we claim that the end point after S+Uniform(1…T) steps can be coupled with the end point after Uniform(1…T) steps with error at most O(eps) (recall that \E[S]<=eps*T). This would solve the problem as coupling with probability 1-eps means that TV distance is at most eps hence ensuring that Uniform(1..T) stopping time is almost as good.
For the coupling first sample an infinite trajectory and run S steps (the number S depends on the trajectory) and then Uniform(1..T) steps. For fixed number k at most eps*T it’s easy to couple k+Uniform(1..T) with Uniform(1..T) with error eps (explicit construction: take k+Uniform(T) modulo T) and so we use this coupling to construct Uniform(1..T) stopping time on the same trajectory.
Here we pretended that S is at most eps*T a.s. But carefully looking at the argument one realises that it works for \E[S]<=eps*T as well.
For the coupling first sample an infinite trajectory and run S steps (the number S depends on the trajectory) and then Uniform(1..T) steps. For fixed number k at most eps*T it’s easy to couple k+Uniform(1..T) with Uniform(1..T) with error eps (explicit construction: take k+Uniform(T) modulo T) and so we use this coupling to construct Uniform(1..T) stopping time on the same trajectory.
Here we pretended that S is at most eps*T a.s. But carefully looking at the argument one realises that it works for \E[S]<=eps*T as well.
Here is a surprising neat connection between communication complexity and additive combinatorics.
Communication complexity problem: suppose Alice, Bob, and Charlie each have a number written on their hat: a, b, c, all three from 1 to N; so that each knowns the other two numbers. Sending bits of information between each other, they want to decide whether a+b+c=N. How many bits do they need to send?
Trivially, having log N bits of communication suffices: Alice can send the number b to Bob and then Bob knows everything and can decide on whether a+b+c=N or not. But can they do significantly better?
Additive combinatorics: What is the largest size of a subset of [N]^2 which does not contain a “corner”, i.e. a triple of points (x, y), (x+d, y), (x, y+d)? This problem can be thought of as a more difficult version of no-3AP problem which asks for the largest subset of [1…N] without a three term arithmetic progression. Indeed, given any set B\subset [1…N] without 3APs, the preimage of B under the map f:[N]^2—>\Z sending (x, y) to x+2y-N has no corners and almost the same density.
Now, what’s the connection? If for the corner problem one considers a colouring version (i.e. what is the smallest number of colours needed to colour [N]^2 so that we avoid monochromatic corner), then it turns out that the communication complexity is more or less equal to the logarithm of the number of colours needed. Before showing the reductions in both directions, let me mention that the upper bound on the density of the set without corners immediately implies a lower bound on the number of colours and in the opposite direction, given a corner-free set of size \alpha*N^2, taking roughly log(N)/\alpha random shifts of this set with cover [N]^2 with high probability which, upon easing intersections, leads to a colouring with log(N)/\alpha colours.
So, reduction. First, suppose a colouring of [N]^2 with C colours that avoids monochromatic corners exists. At the preprocessing step, Alice and Bob using 2 bits of communication make sure that both b+c and a+c are at most N (if not then clearly a+b+c>N). Then Charlie sends log_2(C) bits that encode the colour of (a, b)\in [N]^2. Finally, Alice checks that (N-b-c, b) \in [N]^2 has the colour that Charlie announced, and Bob checks that (a, N-a-c) \in [N]^2 has the colour that Charlie announced. All three claim that a+b+c=N iff the colours match both for Alice and Bob. In total, 4+log_2(C) bits of communication are used. Why does this work?
In the YES case, when a+b+c=N, the points (a, b), (N-b-c, b), and (a, N-a-c) coincide and hence have the same colour. Otherwise, if a+b+c is not equal to N, these three points are distinct and form a corner, hence they cannot be of the same colour!
This reduction together with a construction of Behrend already gives a communication protocol with just log(N)^{1/2} bits (recall that the density of a set in Behrend construction is of the order exp(-log(N)^{1/2}).
What about the opposite direction. Given a communication protocol, how can me convert it into a colouring?! Well, suppose a communication protocol with log_2(C) bits of communication exists. Then there are at most \Omega(C) different transcripts of the communication possible. Let’s colour a point (x, y)\in [N/2]^2 into the colour corresponding to the transcript of the communication with input (x, y, N-x-y), which is clearly a YES instance. What would it mean to have a monochromatic corner? This would mean that (x, y), (x+d, y), and (x, y+d) are all coloured in the same colour and so transcripts for
(x, y, N-x-y)
(x+d, y, N-x-y-d)
(x, y+d, N-x-y-d)
are all the same. We claim that then the transcript for (x+d, y+d, N-x-y-d) is also the same. Indeed, if, say, Alice speaks first then she cannot distinguish between instance (x+d, y+d, N-x-y-d) and the third instance above so she will send the same bit. If, say, Bob speaks next, he cannot differentiate between (x+d, y+d, N-x-y-d) and the second instance above since he sees x+d, N-x-y-d in both cases and also heard the same message from Alice.
Communication complexity problem: suppose Alice, Bob, and Charlie each have a number written on their hat: a, b, c, all three from 1 to N; so that each knowns the other two numbers. Sending bits of information between each other, they want to decide whether a+b+c=N. How many bits do they need to send?
Trivially, having log N bits of communication suffices: Alice can send the number b to Bob and then Bob knows everything and can decide on whether a+b+c=N or not. But can they do significantly better?
Additive combinatorics: What is the largest size of a subset of [N]^2 which does not contain a “corner”, i.e. a triple of points (x, y), (x+d, y), (x, y+d)? This problem can be thought of as a more difficult version of no-3AP problem which asks for the largest subset of [1…N] without a three term arithmetic progression. Indeed, given any set B\subset [1…N] without 3APs, the preimage of B under the map f:[N]^2—>\Z sending (x, y) to x+2y-N has no corners and almost the same density.
Now, what’s the connection? If for the corner problem one considers a colouring version (i.e. what is the smallest number of colours needed to colour [N]^2 so that we avoid monochromatic corner), then it turns out that the communication complexity is more or less equal to the logarithm of the number of colours needed. Before showing the reductions in both directions, let me mention that the upper bound on the density of the set without corners immediately implies a lower bound on the number of colours and in the opposite direction, given a corner-free set of size \alpha*N^2, taking roughly log(N)/\alpha random shifts of this set with cover [N]^2 with high probability which, upon easing intersections, leads to a colouring with log(N)/\alpha colours.
So, reduction. First, suppose a colouring of [N]^2 with C colours that avoids monochromatic corners exists. At the preprocessing step, Alice and Bob using 2 bits of communication make sure that both b+c and a+c are at most N (if not then clearly a+b+c>N). Then Charlie sends log_2(C) bits that encode the colour of (a, b)\in [N]^2. Finally, Alice checks that (N-b-c, b) \in [N]^2 has the colour that Charlie announced, and Bob checks that (a, N-a-c) \in [N]^2 has the colour that Charlie announced. All three claim that a+b+c=N iff the colours match both for Alice and Bob. In total, 4+log_2(C) bits of communication are used. Why does this work?
In the YES case, when a+b+c=N, the points (a, b), (N-b-c, b), and (a, N-a-c) coincide and hence have the same colour. Otherwise, if a+b+c is not equal to N, these three points are distinct and form a corner, hence they cannot be of the same colour!
This reduction together with a construction of Behrend already gives a communication protocol with just log(N)^{1/2} bits (recall that the density of a set in Behrend construction is of the order exp(-log(N)^{1/2}).
What about the opposite direction. Given a communication protocol, how can me convert it into a colouring?! Well, suppose a communication protocol with log_2(C) bits of communication exists. Then there are at most \Omega(C) different transcripts of the communication possible. Let’s colour a point (x, y)\in [N/2]^2 into the colour corresponding to the transcript of the communication with input (x, y, N-x-y), which is clearly a YES instance. What would it mean to have a monochromatic corner? This would mean that (x, y), (x+d, y), and (x, y+d) are all coloured in the same colour and so transcripts for
(x, y, N-x-y)
(x+d, y, N-x-y-d)
(x, y+d, N-x-y-d)
are all the same. We claim that then the transcript for (x+d, y+d, N-x-y-d) is also the same. Indeed, if, say, Alice speaks first then she cannot distinguish between instance (x+d, y+d, N-x-y-d) and the third instance above so she will send the same bit. If, say, Bob speaks next, he cannot differentiate between (x+d, y+d, N-x-y-d) and the second instance above since he sees x+d, N-x-y-d in both cases and also heard the same message from Alice.
Proceeding further following the transcript we see that Alice, Bob, and Charlie must also identify (x+d, y+d, N-x-y-d) as a YES instance, leading to a contradiction!
Now, what can be said about an upper bound for the size of a set avoiding corners and hence a lower bound for the number of colours needed which implies a lower bound on the communication complexity? Even the bound of o(N^2), which translates into super constant commutation lower bound, is nontrivial. The original proof uses triangle removal lemma and hence leads to a N^2/log^*N bound at best.
The first quantitatively reasonable bound was obtained by Shkredov (in 2006, it was his PhD thesis if I’m not mistaken), who proved an N^2/(loglogN)^c upper bound. Surprisingly, unlike in the case of 3AP, no improvements were obtained until this year when a quasi-polynomial bound of N^2*exp(-(logN)^{1/600}) was obtained [https://arxiv.org/pdf/2504.07006 ] which almost matches the Behrend’s construction and leads to a (logN)^{1/600} lower bound for the communication complexity.
This work builds on the ideas from the breakthrough of Kelley and Meka who proved a similar N*exp(-(logN)^{1/12}) upper bound for the size of a subset of [N] avoiding 3APs. The work of Kelley and Meka, in turn, is, apparently, inspired by the amazing (2.76)^n upper bound for the cap set size (a subset of \F_3^n avoiding three points on a line) due to Ellenberg and Gijswijt improving the polynomial method of Croot, Lev, Pach.
Now, what can be said about an upper bound for the size of a set avoiding corners and hence a lower bound for the number of colours needed which implies a lower bound on the communication complexity? Even the bound of o(N^2), which translates into super constant commutation lower bound, is nontrivial. The original proof uses triangle removal lemma and hence leads to a N^2/log^*N bound at best.
The first quantitatively reasonable bound was obtained by Shkredov (in 2006, it was his PhD thesis if I’m not mistaken), who proved an N^2/(loglogN)^c upper bound. Surprisingly, unlike in the case of 3AP, no improvements were obtained until this year when a quasi-polynomial bound of N^2*exp(-(logN)^{1/600}) was obtained [https://arxiv.org/pdf/2504.07006 ] which almost matches the Behrend’s construction and leads to a (logN)^{1/600} lower bound for the communication complexity.
This work builds on the ideas from the breakthrough of Kelley and Meka who proved a similar N*exp(-(logN)^{1/12}) upper bound for the size of a subset of [N] avoiding 3APs. The work of Kelley and Meka, in turn, is, apparently, inspired by the amazing (2.76)^n upper bound for the cap set size (a subset of \F_3^n avoiding three points on a line) due to Ellenberg and Gijswijt improving the polynomial method of Croot, Lev, Pach.
Looking again at the article about the Lonely Runner Conjecture for 8 runners [2], I noticed that the author also proves an improved version of the statement "if the set of speeds forms a lacunary (enough) sequence then there exists a time when the runner whose speed is set to zero is lonely". Lacunary sequence in general means that v_{j+1}/v_j>1+\eps for some \eps>0 and all j, and in this particular setting \eps is of the order of 3e*log(k)/k for k+1 runners.
Though I don't think this statement sheds light on the LR conjecture in general (again, I believe the general conjecture to be false for large k), this line of works is interesting in its own way. The proof relies on a recent paper by the author and A. Shen [1], which gives nice proofs and improved bounds for some related results. The general pattern of the proofs is the use of the following lemma about a game between Alice and Bob.
Given an infinite k-ary rooted tree, consider the following game. Initially Bob is at the root of the tree. At each step Alice adds some vertices of the tree to a forbidden set \F, and then Bob moves to one of the children of the current vertex. Alice wins if Bob is forced to step onto a forbidden vertex and Bob wins if this never happens. Of course, some restriction is needed on how many vertices Alice is allowed to add to \F, as otherwise she would always be winning.
To formulate the restriction, consider a weight function on a tree given by \beta^{-t} for the vertices at level t, i.e. the root has weight 1, its children have weight 1/beta, etc. Here \beta \in (1, k). The restriction for Alice is as follows: for every move the total weight of the newly forbidden vertices, measured in the current subtree, does not exceed some constant \omega. For all practiacal purposes let's assume further that Alice cannot add the current vertex where Bob is to the forbidden set. Note that we may assume that Alice is only adding vertices in the subtree of the Bob's current position. So here is the lemma:
Lemma: Assume that for some integer k > 1, some \beta\in (1,k) and some \omega > 0, the inequality \beta*(1+\omega) <= k holds. Then Bob has a winning strategy in the (β,ω,k)-game.
Proof: Bob simply maintains an invariant "total weight of all currently forbidden vertices in a subtree is less than 1". Initially it's true, as the total weight is zero, and when Alice adds some forbidden vertices the total weight in the current subtree becomes smaller than 1+\omega. Choosing a child as to minimize the invariant, Bob can find one with the total wight smaller than (1+\omega)/k*beta (1/k factor comes from having k children and \beta comes from the fact that in the new subtree all weights are larger by a factor of \beta). By assumption we have (1+\omega)/k*beta<=1 and so the invariant remains smaller than 1. It remains to note that invariant being smaller than 1 ensures that Bob is not stepping on a forbidden vertex.
Many problems can be solved with ease using this game and, in fact, may examples are given in [1] (the article is in general very easy to read). Let me state two of these problems which admit strengthenings which are conjectured to be true but still open:
Problem 1: We say that a string of symbols w (over some alphabet S) is square-free if it does not contain substrings uu for non-empty strings u.
Theorem: Let S be an alphabet with at least 4 letters, possibly infinite one. Given a function f: \N --> S\choose 4, which assigns to each positive integer a set of 4 letters allowed at the corresponding position, it is possible to choose one letter (out of the allowed four) for each position to form a square-free sequence.
The same is believed to be true when each position only has 3 allowed letters. The case when the function f is constant (i.e. we just work over an alphabet with three letters) was resolved by Thue who constructed an infinite sequence over {1, 2, 3} which is square -free.
Though I don't think this statement sheds light on the LR conjecture in general (again, I believe the general conjecture to be false for large k), this line of works is interesting in its own way. The proof relies on a recent paper by the author and A. Shen [1], which gives nice proofs and improved bounds for some related results. The general pattern of the proofs is the use of the following lemma about a game between Alice and Bob.
Given an infinite k-ary rooted tree, consider the following game. Initially Bob is at the root of the tree. At each step Alice adds some vertices of the tree to a forbidden set \F, and then Bob moves to one of the children of the current vertex. Alice wins if Bob is forced to step onto a forbidden vertex and Bob wins if this never happens. Of course, some restriction is needed on how many vertices Alice is allowed to add to \F, as otherwise she would always be winning.
To formulate the restriction, consider a weight function on a tree given by \beta^{-t} for the vertices at level t, i.e. the root has weight 1, its children have weight 1/beta, etc. Here \beta \in (1, k). The restriction for Alice is as follows: for every move the total weight of the newly forbidden vertices, measured in the current subtree, does not exceed some constant \omega. For all practiacal purposes let's assume further that Alice cannot add the current vertex where Bob is to the forbidden set. Note that we may assume that Alice is only adding vertices in the subtree of the Bob's current position. So here is the lemma:
Lemma: Assume that for some integer k > 1, some \beta\in (1,k) and some \omega > 0, the inequality \beta*(1+\omega) <= k holds. Then Bob has a winning strategy in the (β,ω,k)-game.
Proof: Bob simply maintains an invariant "total weight of all currently forbidden vertices in a subtree is less than 1". Initially it's true, as the total weight is zero, and when Alice adds some forbidden vertices the total weight in the current subtree becomes smaller than 1+\omega. Choosing a child as to minimize the invariant, Bob can find one with the total wight smaller than (1+\omega)/k*beta (1/k factor comes from having k children and \beta comes from the fact that in the new subtree all weights are larger by a factor of \beta). By assumption we have (1+\omega)/k*beta<=1 and so the invariant remains smaller than 1. It remains to note that invariant being smaller than 1 ensures that Bob is not stepping on a forbidden vertex.
Many problems can be solved with ease using this game and, in fact, may examples are given in [1] (the article is in general very easy to read). Let me state two of these problems which admit strengthenings which are conjectured to be true but still open:
Problem 1: We say that a string of symbols w (over some alphabet S) is square-free if it does not contain substrings uu for non-empty strings u.
Theorem: Let S be an alphabet with at least 4 letters, possibly infinite one. Given a function f: \N --> S\choose 4, which assigns to each positive integer a set of 4 letters allowed at the corresponding position, it is possible to choose one letter (out of the allowed four) for each position to form a square-free sequence.
The same is believed to be true when each position only has 3 allowed letters. The case when the function f is constant (i.e. we just work over an alphabet with three letters) was resolved by Thue who constructed an infinite sequence over {1, 2, 3} which is square -free.
Problem 2: This is a problem from Erdös. Let n_k be a lacunary sequence of positive integers, i.e., n_{k+1} > (1 + \eps)*n_k for some \eps>0. Can we find a real \theta such that all distances from n_k*\theta to the nearest integer are separated from 0 (exceed some positive \delta for all k)?
This question has been answered positively, the bound for \delta in terms of \eps has been improving over time with the best known bound of the form delta=\Omega(\eps/\log (1/\eps)), the result originally proved in [3]. In [1], again using the game described above, the authors provide a simplier proof which also leads to a better implied constant in the bound. As shown in [3], it's not possible to take \delta larger than \Omega(\eps) but it remains an open problem as to whether \delta=c*\eps with some absolute constant c>0 works.
[1] Local obstructions in sequences revisited, https://arxiv.org/pdf/2503.20529
[2] The lonely runner conjecture holds for eight runners, https://arxiv.org/pdf/2509.14111
[3] https://arxiv.org/pdf/0706.0223
This question has been answered positively, the bound for \delta in terms of \eps has been improving over time with the best known bound of the form delta=\Omega(\eps/\log (1/\eps)), the result originally proved in [3]. In [1], again using the game described above, the authors provide a simplier proof which also leads to a better implied constant in the bound. As shown in [3], it's not possible to take \delta larger than \Omega(\eps) but it remains an open problem as to whether \delta=c*\eps with some absolute constant c>0 works.
[1] Local obstructions in sequences revisited, https://arxiv.org/pdf/2503.20529
[2] The lonely runner conjecture holds for eight runners, https://arxiv.org/pdf/2509.14111
[3] https://arxiv.org/pdf/0706.0223
Let A be a triangle. Suppose points of a circle are coloured in two colours, is it always possible to find a monochromatic triangle similar to A? Turns out, that the answer is yes if and only if A has angles (pi/7, 2pi/7, 4pi/7).
More generally, Stromquist conjectures that for any two-colouring of a circle with unit circumference, one can find a monochromatic d-gon with arc-length equal to 1/(2^k-1), 2/(2^k-1), \dots, 2^{k-1}/(2^k-1) in some order. It's not difficult to see that this conjecture is equivalent to the same assertion for a two-colouring of the vertices of a regular polygon with 2^k-1 vertices. This conjecture is known for k=1, 2, .., 7 but is open in general, the case k=7 was resolved in [1] using a SAT solver.
Remarkably, in a recent paper [1], it is proved that no other k-tuple of numbers satisfies the same property, i.e. for any other k-tuple of positive real numbers (d_1, ..., d_k) summing to one, it is possible to construct a two-colouring of a circle avoiding a monochromatic polygon with arcs of lengths d_1, ..., d_k in some order.
If I understood correctly, in the case when the colouring is given by alternating white and black arcs of fixed length 1/2t, the conjecture of Stromquist is equivalent to the following statement, see Conjecture 3.1. in [1]:
Let -1< x_1, x_2, \dots x_k < 1 be a sequence of real numbers satisfying x_{j+1}=2x_j mod 2 for each j=1, 2, ..., k with cyclic indexing, i.e. x_{k+1}:=x_1. Then it's possible to rearrange the sequence in such a way that the sum of all prefixes is in [0, 1).
Note that x_1+...+x_k=0 for any such sequence.
[1] https://arxiv.org/pdf/2504.10687
More generally, Stromquist conjectures that for any two-colouring of a circle with unit circumference, one can find a monochromatic d-gon with arc-length equal to 1/(2^k-1), 2/(2^k-1), \dots, 2^{k-1}/(2^k-1) in some order. It's not difficult to see that this conjecture is equivalent to the same assertion for a two-colouring of the vertices of a regular polygon with 2^k-1 vertices. This conjecture is known for k=1, 2, .., 7 but is open in general, the case k=7 was resolved in [1] using a SAT solver.
Remarkably, in a recent paper [1], it is proved that no other k-tuple of numbers satisfies the same property, i.e. for any other k-tuple of positive real numbers (d_1, ..., d_k) summing to one, it is possible to construct a two-colouring of a circle avoiding a monochromatic polygon with arcs of lengths d_1, ..., d_k in some order.
If I understood correctly, in the case when the colouring is given by alternating white and black arcs of fixed length 1/2t, the conjecture of Stromquist is equivalent to the following statement, see Conjecture 3.1. in [1]:
Let -1< x_1, x_2, \dots x_k < 1 be a sequence of real numbers satisfying x_{j+1}=2x_j mod 2 for each j=1, 2, ..., k with cyclic indexing, i.e. x_{k+1}:=x_1. Then it's possible to rearrange the sequence in such a way that the sum of all prefixes is in [0, 1).
Note that x_1+...+x_k=0 for any such sequence.
[1] https://arxiv.org/pdf/2504.10687