#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Next meeting of the seminar will happen in unusual day/time: Tuesday 5 may 17:00 Moscow time

LINES AND POINTS (discussion)

An effective dimension of a point in a plane is the liminf of the Kolmogorov complexity of its $2^{-n}$ approximations divided by $n$. The dimension of a line is defined similary (lines are dual to points). It turns out that if a line has dimension d<1, then its points have all dimension in the interval [d,d+1], and for d>=1 the interval is [1,2]. Trying to understand this result, I thought that it would be instructive to consider the finite case (of lines and points over a finite field with $2^n$ elements - there is another finite version, with approximations to reals, but this is another story). Indeed, Don Stull (who will come to the meeting, I hope) managed to prove the first part (for lines of small complexity), whilt the second case remains open (AFAIK). We will try to discuss his argument (starting with simpler result about the maximal complexity of line points).

📝 lines.pdf