Математические байки

А если атлет начинал и закончил путь на разных дугах — то если добавить к пути замыкание "в положительном направлении", после которого суммы у арбитров совпадут, то один из двух арбитров его увидит, а другой нет. И уже совсем легко увидеть, что общий ответ такой: число пересечений (с учётом знака) для арбитра A1 минус число пересечений (с учётом знака) для арбитра А2 = F(начала пути)-F(конца пути), где F это 1, если мы начали на дуге от A2 к A1 (обозначенной тут +-), и 0 иначе.

Если по окружности-стадиону бежит атлет и возвращается в итоге в начальную точку — число кругов, которые он пробежал, можно посчитать, встав в любую точку стадиона и считая пересечения (если он пробежал куда надо, то с плюсом, а если обратно, то с минусом). А если траектория атлета незамкнута — то арбитры, стоящие в разных точках круга, могут получить разные суммы. Но не сильно: если атлет начал и закончил бежать на одной и той же дуге, то их результаты совпадут — потому что он после этого может пройтись от конца своего пути к началу, не проходя мимо арбитров, и получить уже замкнутый путь.

Уже звучит очень естественно, что важно, пересекут ли в процессе поворота (кривой или системы координат — кому как удобнее) концы кривой ось ординат, пересечения с которой мы считаем. Но проще всего в этом убедиться, уронив всю ситуацию обратно на проективную прямую (= окружность, образуемую всеми прямыми через ноль).

А вот на операциях "повернуть" — можем поменять. Потому что сначала мы считали (с учётом знака) пересечения с одной прямой, а потом с другой. Если бы мы работали с замкнутой кривой, то мы бы считали буквально степень отображения окружности, и ничего поменяться бы не могло, потому что при повороте прямой прообразы бы только сливались "плюс с минусом", и ничего бы не менялось. Но если мы работаем с отрезком [a,b] параметров — то у отрезка кривой есть концы. И вот тут-то мы с числом перемен знака и столкнёмся!

После чего продолжили в том же духе. Так вот — на операциях "добавить" мы пересечения с осью ординат не меняем (потому что добавляем первую координату, на что-то там умноженную). И их тип (по или против часовой стрелки) тоже.

И добавили ко второй координате первую, умноженную на Q_1 — из (P_2,-P_1) получив (P_2,P_3).

Его повернули

Был отрезок кривой

На самом деле, история довольно простая — и параллельная тому, что мы уже делали. А именно — разложение рациональной функции R=P_1/P_2 в цепную дробь Хирцебруха ("с минусами") разбивается в череду операций: *) повернуть картинку на 90 градусов (P_1,P_2) -> (P_2,-P_1) *) добавить к второй координате первую, умноженную на Q_1 (P_2,-P_1) -> (P_2, Q_1*P_2-P_1) = (P_2,P_3) *) повернуть картинку на 90 градусов (P_2,P_3) -> (P_3,-P_2) *) добавить к второй координате первую, умноженную на Q_2 (P_3,-P_2) -> (P_3, Q_2*P_3-P_2) = (P_3,P_4) *) и так далее.

Понять, что выкладки через цепную дробь приводят к тому же результату, не очень сложно. Действительно, когда мы делим с остатком, то знаки P_j и P_{j+1} отличаются на знак неполного частного Q_j (а P_{j+1} слишком мал, и ни на что не влияет). Соответственно, если многочлен Q_j в данной (плюс или минус) бесконечности отрицателен, то перемена знака между P_j и P_{j+1} там есть, а если положителен, то нет. Вот и получается, что когда мы считаем разницу между числом перемен знака в минус и в плюс бесконечности, то Q_j чётной степени вклада не дают (ибо они в бесконечностях одного знака), а Q_j нечётной степени дают вклад, равный знаку старшего коэффициента. Так что ответы "через цепную дробь" и "через перемены знаков" для числа всех вещественных нулей (и для топологической степени рациональной функции R=P_1/P_2) совпадают. Уже хорошо. Но хотелось бы как-то понять, как о переменах знака думать в топологических терминах — при том, что для отображения отрезка о степени уже говорить нельзя, у него концы есть.

Собственно, это буквально соответствует вычислению части суммы для топологической степени deg_{top} P_1/P_2 по прообразу нуля (то есть по пересечению с вертикальной прямой на плоскости (P_1,P_2)), когда мы ограничиваемся прообразами из отрезка параметров [a,b].

Да, если P_1 и P_2 произвольные без общих корней, то большая часть рассуждения выше тоже работает. Только разница в числе перемен знака на отрезке [a,b] считает не просто корни P_1 — а корни P_1 со знаком: если в корне P_1' и P_2 одного знака, то мы его считаем с плюсом, а если разного, то с минусом. (Потому что именно так пересечение корня P_1 меняет число перемен знака — а пересечение корней всех остальных P_j, как и раньше, ничего не меняет.)

Так что переходы значений "внутренних" полиномов через ноль на число перемен знака не влияют. P_n=1 через ноль перейти вообще не может, это константа. Остаётся только P_1. А значение многочлена P переходит через ноль — правее корня знак у P такой же, как у его производной P' в этом корне, а левее корня противоположный. Поэтому как раз при переходе через ноль P (и только там) число перемен знака уменьшается на единицу. Теорема Штурма доказана. Осталось это склеить с тем взглядом, который у нас был раньше.

Посмотрим сначала на классическое доказательство теоремы Штурма. Если мы говорим о том, что число корней P на отрезке [a,b] выражается через изменение на этом отрезке числа перемен знака — так очень естественно спросить себя, а как вообще число перемен знака N(x) меняется, когда меняется x? Естественно, что меняться оно может только если меняет знак какой-то из многочленов P_j. Но — и это замечательно — если меняет знак (переходя через ноль) любой P_j, кроме P_1, то число перемен знака не меняется. Действительно, пусть в точке x_0 обращается в ноль какой-то P_j, и j>1. Его соседи тогда в этой точке не обращаются в ноль: иначе там обратились бы в ноль и все полиномы вообще, а у P_1 и P_2 нет общих корней. Но заметим, что его соседи противоположного знака: ведь P_{j-1} + P_{j+1} = P_j * Q_{j-1}, раз правая часть обратилась в ноль, то и сумма соседей P_{j-1}+P_{j+1} в точке x_0 обращается в ноль. А тогда неважно, какой у P_j рядом с x_0 знак — всё равно на P_{j-1},P_j,P_{j+1} приходится ровно одна перемена знака! И мы, собственно, такое уже видели, когда смотрели на пример P(x)=x^2: рядом с x_0=0, где обращается в ноль производная P_2=2x, число перемен знака не менялось: === -0.1: -,-,+; 1 перемена; 0.1: -,+,+; 1 перемена; ===

если хочется объяснения и/или еще формул — можно заглянуть в калейдоскоп

И калейдоскоп тоже очень хорош!

а про формулу Валлиса для π и про появление π в комбинаторике лет 10 назад интересно рассказывал Д.Кнут — можно посмотреть видео или почитать конспект

К прошедшему вчера Pi Day хочется вспомнить несколько видео: три видео 3Blue1Brown, *) https://www.youtube.com/watch?v=d-o3eB9sfls — очень классное доказательство формулы для суммы обратных квадратов, где окружность с расставленными на ней маяками появляется явно; *) https://www.youtube.com/watch?v=8GPy_UMV-08 — а это формула Валлиса (произведение 2/1 * 2/3 * 4/3 * 4/5 * ... = π/2); опять окружность, выход в комплексные числа, многочлены, произведение расстояний — и всё получается; *) https://www.youtube.com/watch?v=NaL_Cb42WyY — как связать сумму 1 - 1/3 + 1/5 - 1/7 + ... = π/4 с окружностью (спойлер: никакого Тейлора и арктангенса! Разложение чисел в сумму квадратов, характеры, подсчёт числа целых точек). И рождественскую лекцию Дональда Кнута в Стенфорде, "Why Pi": https://www.youtube.com/watch?v=cI6tt9QfRdo (которая, на самом деле, заслуживает отдельного пересказа).