Матем из ЖЖ

Поскольку ЖЖ потихонечку умирает, а мой личный ЖЖ умирает под моим скальпелем быстро и неотвратимо, уношу всю математику оттуда.

6.9. (2005-03-23)

В далекие школьные времена, когда меня еще не тошнило от математики, я решал задачки. Иногда на задачу уходил день. Иногда неделя. Все из Д02 помнят, конечно же, задачу 6.9. с невинной формулировкой: на плоскости расположено n точек, не все из которых лежат на одной прямой, доказать что через них проходит по крайней мере n прямых. Но тупая индукция не помогает. Я возился с этой задачей регулярно целый месяц, но не решил. Помнится, ее сделали только 4 человека: естественно Петр; Ермак, Лебедев и Федоров (кто-то еще??).

Потом на какое-то время я забил на нее. Потом опять стал решать. Много раз находил решения, каждый раз неверные. Помню, пошел гулять с листком бумаги и ручкой и решал по пути. До сих пор точно помню место, где придумал решение (какую-то <вырезано цензурой> дважды бесконечную последовательность треугольников). На ближайшем матане гордо сдал решение Городенцеву. Каноническое решение оказалось обидно коротким, в две строчки, но додуматься до него было невозможно (хотя Олег это сделал).

Для меня эта задача пока остается самым большим достижением (несмотря на то, что решение ее было общеизвестно). Я действительно сильно сомневаюсь в том, что она им не останется. У моего отца, по его мнению, таким достижением было решение задачи из общей топологии (обязательно ли в секвенциальном компакте есть точки счетного характера), которую ведущий мировой общий тополог Архангельский ставил второй в своем списке. Отец помнит кучу подробностей про то, как он решал эту проблему.

Здесь я собрал всякие задачки по математике, разбросанные по моему ЖЖ.

1. Пусть F дифференцируема всюду на [a,b] и монотонна. Верно ли, что F абсолютно непрерывна на [a,b]?

2. Пусть F непрерывна на [a,b], дифференцируема на [a,b] всюду, за исключением счетного числа точек, и ее производная равна нулю (там где она есть). Тогда F постоянна. Описать все множества с таким свойством.

3. Построим последовательность по правилу x_0=1, x_{n+1}=sin(x_n). Найти асимтотику (асимптотическое разложение) x_n.

4. Пусть Q=(q_{i,j}), i=1..n,\,j=1..n — ортогональная матрица с det Q=1. Пусть
A=(q_{i,j}), i=1..k,\,j=1..k; B=(q_{i,j}), i=k+1..n,\,j=k+1..n — угловые подматрицы. Доказать геометрически, что det A=det B.

5. Ввести адекватную структуру на семействе функций распределения (ф.р.) (aka борелевских мерах). Например, ф.р. можно складывать и умножать: F_1 + F_2 есть ф.р. суммы двух независимых случайных величин с распределениями F_1 и F_2, аналогично с произведением. К сожалению, с такими операциями ф.р. не образуют кольца. А еще можно ф.р. возводить в квадрат и вообще брать от них любую борелевскую функцию: g(F) есть ф.р. величины g(x), где x имеет ф.р. F.

6. Рассмотрим последовательность (3/2)^n по модулю 1. Открытый вопрос, будет ли она равномерно распределена на [0,1]. А будет ли она плотна?

7. Как строго сформулировать, что нет канонического изоморфизма V и V^* (V — конечномерное векторное пространство)?

8. Верно ли, что всякое неограниченное выпуклое множество на плоскости (более общо, в конечномерном пространстве) содержит полупрямую? Что получится в бесконечномерном случае?
А верно ли, что если выпуклое подмножество W линейного пространства V не содержит полупрямых, то в V можно так ввести норму, что по ней W будет ограничено?

9. Существует ли непрерывная инволюция \mathbb R^n без неподвижных точек? Инволюция X — это отображение f:X->X, для которого f○f=id.

10. Пусть X — бесконечномерное банахово пространство. Гомеорморфны ли X и X\{0}?

11. Рассмотрим пространство Rn с какой-нибудь нормой. Пусть c>1. Верно ли, что всегда найдутся по крайней мере a^n точек, a=a(c)>1, с попарными расстояниями от 1 до с?

Добавил сюда мои записи в сообществе ru_math:

12. N раз бросили монетку

13. Кривая Пеано-Гильберта

14. Куб {0,1}^2n раскрасили в три цвета

Решение задачи 9 (Андрей Кустарёв). Ответ: не существует. Решение использует на всю катушку алгебраическую топологию (не знаю, есть ли более простое, это придумалось само). Предположим, что такая инволюция на R^n нашлась. Тогда отфакторизуем по ней, получим некоторое пространство X. Вычислим гомотопические группы пространства X.

Из свойств накрытий следует, что \pi_1(X)=Z_2, а при i>1 \pi_i(X)=0, другими словами, X — пространство типа K(Z_2,1). Нам уже известно одно пространство типа K(Z_2,1) — это RP^{\infty}. Кроме того, любые два пространства типа K(Z_2,1) должны быть гомотопически эквивалентны — а значит, у них у всех одинаковые гомологии.

Но у RP^{\infty} есть гомологии в сколь угодно высоких размерностях — а пространство X является n-мерным топологическим некомпактным многообразием, поэтому выше размерности n-1 у него гомологий нет. Получаем противоречие.

К задаче 10. Комментарий sowa@lj: Наверное, да, но никакой ссылки не помню. Этим в 60-е годы увлекались. Бессага, Пелчинский. В случае гильбертова пространства я уверен больше. Собственно, результаты такого сорта и закрыли предмет — в бесконечномерном случае геометрия/топология многообразий (без дополнительной структуры) малоинтересна — все определяется гомотопическим типом.

В качестве бонуса, несколько развлекательных математических штук:

  • Проблемы Смейла. Аналог знаменитых проблем Гильберта, только в 21-м веке.
  • Пусть p_n(x)/q_n(x) — n-я подходящая дробь числа x. Существует число c, такое что для почти всех x из (0,1) величина q_n(x)^{1/n} стремится к c (Хинчин); при этом c = exp(PI^2/(12ln 2)) (Леви).
  • Про повторные логарифмы:

ЗПЛ — это так называемый закон повторного логарифм. Не знаю, почему решил про него написать. Просто так, ещё один пример того, что мне нравится. Итак: пусть мы бросаем монетку. Обозначим через X_k случайную величину, равную 1, если на k-м бросании выпал орел, и 0, если выпала решка. Число орлов, выпавших за n подбрасываний монетки, равно S_n = X_1+X_2+..+X_n. Закон больших чисел говорит, что S_n/n \to 1/2 по вероятности, то есть для любого \varepsilon>0 вероятность того, что |S_n/n-1/2|>\varepsilon, стремится к нулю при n\to\infty. Из этого, правда, не ясно, должна ли разность S_n/n-1/2 оставаться малой для каждой конкретной последовательности подбрасываний. Оказывается, да: поскольку ряд \sum_n \mathsf{P}(|S_n/n-1/2|>\varepsilon) сходится для каждого \varepsilon>0, то из леммы Бореля-Кантелли следует, что с вероятностью 1 отношение S_n/n стремится к 1/2. По-научному: S_n/n\to 1/2 почти наверное, это «усиленный закон больших чисел». Иначе говоря, S_n=n/2+o(n). Оказывается, остаток o(n) имеет порядок \sqrt{n}. Точнее, имеет место центральная предельная теорема: для любого t

\mathsf{P}(|(S_n-n/2)/\sqrt{n/4}| < t) \to F(t) при n\to\infty,

где F(t) есть функция распределения нормальной величины с нулевым мат. ожиданием и единичной дисперсией. По-научному: S^*_n=(S_n-n/2)/\sqrt{n/4} сходится к N(0,1) по распределению. Но если рассмотреть фиксированную последователность подбрасываний, то S^*_n может оказаться достаточно большим. Насколько большим? Ответ даёт закон повторного логарифма: с вероятностью 1 имеем

\varlimsup S^*_n/\sqrt{2\log\log n} = 1,
\varliminf S^*_n/\sqrt{2\log\log n} = -1.

То есть для любого a>1 мы, начиная с некоторого n, находимся в области -\sqrt{2a \log\log n} < S^*_n < \sqrt{2a \log\log n}, но для любого b<1 мы бесконечное число раз выходим из области -\sqrt{2b \log\log n} < S^*_n < \sqrt{2b \log\log n}, причем как вверх, так и вниз. Так и колеблемся от \sqrt{2\log\log n} до -\sqrt{2\log\log n} и обратно. Интересно, а что можно сказать про граничное значение, \sqrt{2\log\log n}? Достигаем ли мы его? Оказывается, да: с вероятностью 1

\varlimsup (S^*_n-\sqrt{2\log\log n})*(\sqrt{2\log\log n} / \log\log\log n) = 3/2,

т.е S^*_n будет немножко превышать это число!
В заключение нельзя не добавить, что ЗПЛ верен для произвольной последовательности независимых одинаково распределенных случайных величин X_1,…,X_n,.. с конечной дисперсией.

Стандартный

Пример для Паши

haar-plot-colored

Это тепловой график функции f(x,y), ортогональной всем произведениям вида h_{k,i}(x)h_{k,j}(y), где h_{k,i} — нормированная функция Хаара (равная единице на [(i-1)2^{-k},(i-1/2)2^{-k}), минус единице на ((i-1/2)2^{-k},i2^{-k}], и нулю в остальных точках).

Пример такой функции строится довольно легко: любая сумма вида g(x)+h(y) подойдёт; можно также взять разрывную функцию, равную единице над «диагональю» x=y, и минус единице под диагональю. А вот нетривиальный непрерывный пример построить было сложнее. Например, если в какой-то точке f достаточно гладкая и \frac{\partial^2 f}{\partial x\partial y}\ne 0, то такая функция уже не подойдёт.

(Совместная работа с Е.С.Белкиной. Изначально вопрос возник в дипломной работе Паши Глебова.)

Стандартный

Гамма-2-норма: второе доказательство

Продолжение; начало здесь.

Мы приведём доказательство, основанное на технике полуопределённого программирования (Semidefinite programming, SDP), следуя статье T.Lee, A.Shraibman, R.Spalek, «A Direct Product Theorem for Discrepancy», 2008.

Введём некоторые обозначения. Начнём с того, что работать придётся с симметричными матрицами, а наша матрица M размера m\times n может даже не быть квадратной! Применим следующий приём для симметризации:
\widehat M := \begin{pmatrix} 0_m & M \\ M^t & 0_n \end{pmatrix}.
Здесь 0_n и 0_m — нулевые матрицы соответствующего размера. Ясно, что \widehat M симметрична и имеет размер (n+m)\times(n+m). Нам также пригодится матрица F:= \widehat 1_{m,n} — симметризация матрицы, состоящей из одних единиц. Через I обозначаем единичную матрицу (тождественный оператор).

Пусть A — квадратная матрица. Пишем A\ge 0, если матрица A — неотрицательно определённая, то есть симметричная и x^tAx\ge 0 для любого вектора x. Запись A\ge B эквивалентна A-B\ge 0. Для матриц вводится стандартное скалярное произведение: \langle A,B\rangle = \sum A_{i,j}B_{i,j} = \mathrm{tr}\,(AB^t).


Следующая простая лемма лежит в основе SDP:

Лемма. Пусть A=A^t. Тогда
\displaystyle \inf_{X\ge 0}\langle A,X\rangle = \begin{cases} 0,&\quad A\ge 0,\\ -\infty,&\quad A\not\ge0. \end{cases}

Докажем это утверждение. Если A\not\ge 0 и x^tAx<0 для некоторого вектора x, то взяв X=cxx^t и устремив c\to+\infty, мы получим минус бесконечность.

Обратно, если A\ge0 и X\ge 0, то \langle A,X\rangle\ge 0 хотя бы потому, что \langle A,X\rangle=\mathbf{1}^t(A\circ X)\mathbf{1}, а матрица A\circ X\ge 0 по теореме Шура. Следовательно, минимум достигается при X=0.

Читать далее

Стандартный

Гамма-2-норма: первое доказательство

Продолжение; начало здесь.

Первое доказательство приведём по книге G.Pisier, «Similarity Problems and Completely Bounded Maps», 2001. Оно достаточно длинное, но зато познавательное.

Под нормой \|M\| матрицы будем понимать спектральную норму. Для j-й координаты вектора используем обозначение v(j).

Пусть (x_j)_1^n и (y_i)_1^m — конечные последовательности векторов в линейном пространстве V. Скажем, что (y_i)\preccurlyeq (x_j), если для любого линейного функционала \xi\colon V\to\mathbb R имеем \sum |\xi(y_i)|^2 \le \sum |\xi(x_j)|^2.

Утверждение 1. Следующие свойства эквивалентны:
(i)  (y_i)_1^m \preccurlyeq (x_j)_1^n;
(ii)  существует матрица A=(a_{i,j}) размера m\times n и нормы \|A\|\le 1, такая что y_i = \sum\limits_{j=1}^n a_{i,j}x_j для всех i=1,\ldots,m.

Импликация (ii)=>(i) проверяется совсем просто: для любого \xi имеем \xi(y) = A\xi(x), где \xi(y)=(\xi(y_1),\ldots,\xi(y_m))^t, \xi(x)=(\xi(x_1),\ldots,\xi(x_n))^t. Следовательно, длина вектора \xi(y) не превосходит длины \xi(x).

Чтобы вывести (i)=>(ii), нужно построить оператор A. Обозначим через E\subset\mathbb R^n подпространство векторов вида \xi(x), \xi\in V^*. Определим на E оператор A по правилу A\xi(x)=\xi(y). Определение корректно, поскольку \xi(x)=0 влечёт \xi(y)=0. При этом A линеен и не увеличивает норму. Продолжим оператор A на всё \mathbb R^n, не увеличивая норму (сначала проектируем ортогонально на E). По построению, A\xi(x)=\xi(y), то есть \xi(y_i - \sum a_{i,j}x_j)=0 для всех \xi; откуда y_i=\sum a_{i,j}x_j.

Отметим, что добавлением нулей сравнение всегда можно свести к последовательностям одной длины.

Упражнение 1. При сравнении (y_i)\preccurlyeq(x_j) наборов векторов банахова пространства X достаточно проверить неравенство \sum |\xi(y_i)|^2 \le \sum |\xi(x_j)|^2 для \xi\in X^*.

Понятие сравнения последовательностей векторов нужно нам для эквивалентного описания \gamma_2-нормы.

Теорема 1 [Pisier, Theorem 3.4]. Пусть u\colon X\to Y — оператор между банаховыми пространствами, c>0. Тогда следующие утверждения равносильны:
(i) \gamma_2(u)\le c ;
(ii) для любых конечных последовательностей (y_i), (x_j) векторов из X, соотношение (y_i)\preccurlyeq(x_j) влечёт неравенство
\sum_i \|u(y_i)\|^2 \le c^2\sum_j \|x_j\|^2.\qquad(*)

Читать далее

Стандартный

Гамма-2-норма и мультипликаторы Шура: введение

Через |x|, если не указано иное, обозначаем евклидову длину вектора x.

Пусть M — вещественная матрица размера m\times n. Через \gamma_2(M) обозначим точную нижнюю грань c>0, таких что M представляется в виде M=AB, причём для любой строки a_i матрицы A и любого столбца b^j матрицы B имеем |a_i|\cdot|b^j|\le c.

Упражнение 1. \gamma_2(M)\le c тогда и только тогда, когда найдутся вектора x_1,\ldots,x_m и y_1,\ldots,y_n в некотором конечномерном евклидовом пространстве, такие что M_{i,j}=\langle x_i,y_j\rangle для всех i,j, и \max_i |x_i| \cdot \max_j |y_j| \le c.

Матрица имеет малый ранг, когда её элементы представимы в виде скалярного произведения маломерных векторов: \mathrm{rk}\;M\le r\Leftrightarrow M_{i,j}=\langle x_i,y_j\rangle,\;x_i,y_j\in\mathbb R^r; в случае же малой \gamma_2-нормы элементы представимы в виде скалярного произведения коротких векторов. Это говорит о тесной связи ранга и \gamma_2-нормы.

Точная нижняя грань в определении \gamma_2 достигается. Действительно, можно считать, что размерность пространства, в котором лежат x_i,y_j, не превосходит m+n.

Упражнение 2. Величина \gamma_2 задаёт норму в пространстве матриц \mathrm{Mat}_{m\times n}(\mathbb R).

Данное определение есть частный случай \gamma_2-нормы в пространстве операторов между банаховыми пространствами X и Y. А именно, \gamma_2(u) для оператора u\colon X\to Y есть точная нижняя грань c>0, таких что u представляется в виде u=AB, где B\colon X\to H, A\colon H\to Y, H — некоторое гильбертово пространство, \|A\|\cdot\|B\|\le c.

Через \Gamma_2(X,Y) обозначается банахово пространство операторов X\to Y с конечной \gamma_2-нормой.

Упражнение 3. Проверить, что \gamma_2(M) матрицы равна \gamma_2-норме M как оператора \ell_1^n\to\ell_\infty^m. Указание: матричная норма \|\cdot\|_{1\to2} равна максимальной длине столбца матрицы, а норма \|\cdot\|_{2\to\infty} равна максимальной длине строки матрицы.

Из теоремы Джона вытекает следующее неравенство для оператора u\colon X\to Y конечного ранга: \gamma(u)\le \sqrt{\mathrm{rk}\;u}\cdot \|u\|_{X\to Y}.

Действительно, пусть E=\mathrm{Im}\;u, \dim E=r:=\mathrm{rk}\;u. Тогда, по теореме Джона, существуют взаимно обратные операторы f\colon (E,\|\cdot\|_Y)\to \ell_2^r и g\colon\ell_2^r\to(E,\|\cdot\|_Y) такие что \|f\|\cdot\|g\|\le \sqrt{r}. Тогда u=g(fu), \|fu\|\cdot \|g\|\le \|u\|\cdot\|f\|\cdot\|g\|\le \sqrt{r}\|u\|, что и требовалось.

Следствие. \gamma_2(M) \le \sqrt{\mathrm{rk}\;M}\max\limits_{i,j}|M_{i,j}|.

Для доказательства достаточно применить Упражнение 3 и вспомнить, чему равна \|\cdot\|_{1\to\infty} норма матрицы.

Представление M_{i,j}=\langle x_i,y_j\rangle, x_i,y_j\in H, наводит на мысли о неравенстве Гротендика. Вспомним его формулировку:

\max\limits_{x_i,y_j\in U(H)} \sum_{i,j} M_{i,j}\langle x_i,y_j\rangle \le K_G \max\limits_{\varepsilon_i,\delta_j=\pm 1}\sum_{i,j}M_{i,j}\varepsilon_i\delta_j

(U(H) — единичный шар в гильбертовом пространстве H).

Величина в левой части неравенства есть максимум \sum_{i,j} M_{i,j}A_{i,j} по всем матрицам \gamma_2(A)\le 1. Следовательно, этот максимум есть ни что иное как сопряжённая норма \gamma_2^*(M). Неравенство Гротендика позволяет заменить эту норму на более простую.

Упражнение 4. Максимум в правой части неравенства Гротендика равен \|M\|_{\infty\to 1}. Следовательно, \|M\|_{\infty\to 1}\le \gamma_2^*(M) \le K_G\|M\|_{\infty\to 1}.

Фиксируем матрицу M. Оператор в пространстве матриц, действующий по формуле A\mapsto A\circ M, где \circ — произведение Шура (т.е. (A\circ M)_{i,j}=A_{i,j}M_{i,j}), называется мультипликатором Шура; обозначим его S_M. Спектральная норма в пространстве матриц (т.е. норма матриц как операторов \ell_2^n\to\ell_2^m) индуцирует норму в пространстве операторов \mathrm{Mat}_{m\times n}\to\mathrm{Mat}_{m\times n}, поэтому имеет смысл говорить о норме оператора S_M.

Теорема. Норма мультипликатора Шура равна \gamma_2-норме матрицы: \|S_M\|:=\max\limits_{\|A\|\le 1}\|A\circ M\| = \gamma_2(M).

Различным доказательствам этой теоремы будут посвящены следующие несколько записей:
Доказательство по книге Pisier.
Доказательство через SDP.

Стандартный

Доклад про поперечники

Немного поговорил про теорию приближений на примере задачи вычисления колмогоровских поперечников d_n(W^r_p,L_q):
http://www.mathnet.ru/present12816

Из замеченных ляпов: не написал явно, что \mathrm{dim}(\mathcal T_n)=2n+1; на 55-й мин, где определяю \mu(n,N), не указал, что берется |W|=N.

Bonus: обзор по теме, с набросками доказательств и библиографией (черновик): mysurvey.pdf

Стандартный

Фейнман возвращается

Фейнман описывает, как он вернулся в теоретическую физику после работы над атомной бомбой во время войны.

«Когда настало время заняться исследованиями, я не мог приступить к работе. Я немного устал. У меня не было к этому интереса. Я не мог заниматься исследованиями! Это продолжалось, как мне казалось, несколько лет, но когда я возвращаюсь к тому времени и подсчитываю срок, оказывается, что он не мог быть таким длинным. Может быть, сейчас я бы и не подумал, что это было так долго. Я просто не мог заставить себя думать ни над одной задачей: помню, как я написал одно или два предложения о какой-то проблеме, касающейся гамма-лучей, но дальше продвинуться не мог. Я был убежден, что из-за войны и всего прочего (смерти моей жены) я просто «выдохся».

Затем пришла другая мысль. Физика стала внушать мне легкое отвращение, но ведь раньше-то я наслаждался, занимаясь ею. Почему? Обычно я играл в нее. Я делал то, что мне нравилось делать в данный момент, независимо от того, насколько это было важно для развития ядерной физики. Единственное, что имело значение, — так это то, насколько интересной и занимательной была моя игра. Будучи старшеклассником, я однажды обратил внимание, что струя воды, вытекающая из крана, становится уже, и спросил себя, можно ли выяснить, что определяет форму кривой. Оказалось, что это довольно легко сделать. Меня никто не заставлял, и это было абсолютно неважно для будущего науки — кто-то уже все сделал. Но мне было все равно: я изобретал разные штуки и играл с ними для собственного развлечения. Так пришел этот новый настрой. Теперь, когда я «выгорел» и никогда не свершу ничего важного, я получил отличное место в университете, преподаю студентам и это доставляет мне удовольствие так же, как чтение «Тысячи и одной ночи», и я буду играть в физику, когда захочу, не заботясь о какой бы то ни было важности.

— Послушай, Ханс! Знаешь, я заметил кое-что интересное. Вот тарелка вращается таким образом… а отношение два к одному получается по причине… И я показал ему, как складываются ускорения.
Он говорит:
— Фейнман, это очень интересно, но почему это важно, почему ты этим занимаешься?
— Ха, — отвечаю я. — Это абсолютно неважно. Я занимаюсь этим просто для развлечения.
Его реакция меня не обескуражила; я уже решил для себя, что буду получать удовольствие от физики и делать, что захочу. И я продолжал разрабатывать уравнения покачиваний. Затем я подумал о
том, как орбиты электронов начинают двигаться в общей теории относительности. Затем уравнение Дирака в электродинамике. И уже потом — квантовая электродинамика. И еще этого не осознав (понимание пришло через очень короткое время), я «играл» — в действительности работал — с той самой старой задачей, которую я так любил, работу над которой прекратил, когда уехал в Лос-Аламос. Задачей вроде тех, которые были в моей диссертации, — все эти старомодные, прелестные вещи. Дело шло как по маслу, играть было легко. Это было вроде как откупорить бутылку. Одно вытекало из другого без всяких усилий. Я почти пытался этому сопротивляться! Никакой важности в том, что я делал, не было, но в конце концов получилось наоборот. Диаграммы и все остальное, за что я получил Нобелевскую премию, вышли из этой пустячной возни с покачивающейся тарелкой.»

Стандартный