Квантовая механика и конец арифметики

Когда я учился в университете, квантовую механику нам поначалу преподавал Ч. Как сейчас помню эти занятия где-то в начале апреля. Начал Ч. с обстоятельного (и несколько затянутого на мой вкус) объяснения того, что квантовая механика подразумевает в некотором смысле новую, неклассическую, логику. Гораздо позже я узнал, что и арифметика в квантовом мире претерпевает значительные, я бы даже сказал, фатальные изменения. Рассмотрим атом водорода в основном состоянии. В атомных единицах гамильтониан записывается как\begin{equation}H=\frac{\mathbf{p}^2}{2}-\frac{1}r=-\frac1{2r}\partial_r^2r+\frac{\mathbf{l}^2}{2r^2}-\frac{1}r\end{equation}Волновая функция, соответственно,\begin{equation}\langle\mathbf{r}|0\rangle=\exp(-r)/\sqrt{\pi}\end{equation}Энергия основного состояния, как известно, $E_0=-1/2$.
Теперь вычисляем матричный элемент $\langle 0|r^{-1}\partial_r^2|0\rangle$ двумя разными способами. Прямым дифференцированием получаем:\begin{equation}\langle 0|r^{-1}\partial_r^2|0\rangle\stackrel{\scriptsize 1}{=}4\pi\int dr\, r^2\, \frac{\exp(-r)}{\sqrt{\pi}}r^{-1}\frac{\exp(-r)}{\sqrt{\pi}}=1\end{equation}Немного алгебры дает\begin{multline}\langle 0|r^{-1}\partial_r^2|0\rangle\stackrel{\scriptsize 2}{=}\langle 0|-2(H-\frac{\mathbf{l}^2}{2r^2}+r^{-1})r^{-1}|0\rangle\stackrel{\scriptsize 3}{=}\langle 0|-2(H+r^{-1})r^{-1}|0\rangle\stackrel{\scriptsize 4}{=}\\\langle 0|-2(E_0+r^{-1})r^{-1}|0\rangle\stackrel{\scriptsize 5}{=}\langle 0|r^{-1}|0\rangle-2\langle 0|r^{-2}|0\rangle\stackrel{\scriptsize 6}{=}1-4=-3\end{multline}Итак, мы получаем $1=-3$, или, перенося в одну часть,\begin{equation}4=0,\end{equation}откуда следует, что все числа равны нулю. А это и есть конец арифметики.

Как физики берут интегралы

Всех нас учили в университете брать интегралы. И конечно, на первом курсе объясняли нам что такое собственные и несобственные интегралы. Но где-то курсе на третьем научили нас плохому: брать интегралы как физики. Типичный пример, например, такой интеграл:\begin{equation}I=\int_0^\infty \exp(ipx)\, dx\end{equation} Как физик берет этот интеграл? Регуляризует спадающей экспонентой, берет интеграл, а затем снимает регуляризацию (Извиняюсь за банальные формулы): \begin{equation}I\stackrel{?}{=}\lim_{\epsilon\to 0}\int_0^\infty \exp(ipx-\epsilon x)\, dx=i/p\end{equation} Ну все же брали так, правда? Однако, не нужно лишних иллюзий относительно обоснованности подобного подхода. Дело в том, что можно предъявить регуляризации, которые будут давать другой результат. Вот например \begin{equation}I\stackrel{?}{=}\lim_{\epsilon\to 0}\int_0^\infty (1+\frac{\epsilon}{p} \sin px)\exp(ipx-\epsilon x)\, dx=3i/2p\end{equation} В этом месте физики любят обсудить вопрос: а как же правильно, по-первому или по-второму? Физическая интуиция подсказывает, что первый способ более правильный, чем второй. "Что это ты за синус воткнул, специально, подлец, подбирал" - скажет вдумчивый читатель. Однако, никаких рациональных причин в пользу выбора первого способа регуляризации предъявить не удается, по той причине, что вопрос смысла не имеет.
Что я хочу сказать, это еще одну банальность: если вы изначально имели плохо определенный интеграл, то далее, по-разному его доопределяя, можно получить все что хочешь. Пост этот написан как размышление на тему Гришиной мечты. Рассмотрим по этому поводу такой интеграл \begin{equation}\int_{0}^{1}dx\,\int_{0}^{1-x}dy\,x^{-1-\epsilon }y^{-1+\epsilon }\end{equation} Ну что проще его посчитать так:\begin{equation}\int_{0}^{1}dx\,\int_{0}^{1-x}dy\,x^{-1-\epsilon }y^{-1+\epsilon }=\epsilon ^{-1}\int_{0}^{1}dx\,\,x^{-1-\epsilon }\left( 1-x\right) ^{\epsilon }=\epsilon ^{-1}\Gamma \left[ -\epsilon ,1+\epsilon \right] =\Gamma \left[ -\epsilon ,\epsilon \right]?\end{equation} Но ведь этот интеграл не был определен ни при каких $\epsilon$. Так что наша прескрипция - всего лишь прескрипция. Физики верят, что этот ответ --- "правильный", но рассмотрим такую, казалось бы, совсем непатологическую регуляризацию: \begin{equation}\int_{0}^{1}dx\,\int_{0}^{1-x}dy\,x^{-1-\epsilon }y^{-1+\epsilon }=\lim_{\delta\to +0}\int_{0}^{1}dx\,\int_{0}^{1-x}dy\,x^{-1-\epsilon }y^{-1+\epsilon }\left( xy\right) ^{\delta }\left( x+y\right) ^{2\alpha \delta }\end{equation} Здесь $\alpha>0$ --- фиксированное число (например, $\alpha=2$). Ну этот интеграл сходится на промежутке $-\delta<\epsilon<\delta$, а для остальных $\epsilon$ определяется аналитическим продолжением:\begin{equation}\int_{0}^{1}dx\,\int_{0}^{1-x}dy\,x^{-1-\epsilon }y^{-1+\epsilon }\left( xy\right) ^{\delta }\left( x+y\right) ^{2\alpha \delta }=\frac{\Gamma \left[ \delta -\epsilon ,\delta +\epsilon \right] }{\left( 1+\alpha \right) \Gamma \left[ 1+2\delta \right] }\to\frac{\Gamma \left[ -\epsilon ,\epsilon \right]}{\left( 1+\alpha \right)}\end{equation} Ответ-то другой получился. И что же тут скажешь?
Скажу напоследок, что и сам я такой, беру интегралы как бог на душу положит. Но надеюсь всегда, а если это просто - то и проверяю, что начинал я с хорошо определенной величины, что регуляризовывал я ее только для удобства и что, если и ошибся, никто никогда мою ошибку не найдет.

Основной инстинкт

Подсмотрено в CERN Courier за чашкой утреннего кофе. Видео с сайта Science Friday. Сайт, похоже, любопытный.

P.S. Связь в конторе стала пристойной, что не может не радовать.

Обман студентов

Хороший преподаватель должен обманывать студентов (Некоторые, правда, обманывают, не отдавая себе в этом отчет, что имеет свои плюсы и минусы). Приведу два примера.

Все студенты, специализирующиеся в физике элементарных частиц, атомной физике и т.п., изучают релятивистские поправки $\sim v^2/c^2$ к гамильтониану, то, что называется гамильтонианом Брейта. Этот гамильтониан выводится следующим образом. Сначала вычисляется амплитуда $M_{fi}$ рассеяния двух частиц и раскладывается по параметру $v/c$. Затем эта амплитуда сравнивается с борновской амплитудой $-V_{fi}$ в нерелятивистской квантовой механике для некоторого потенциала $V$. Получается $$V_{fi}=\frac{-M_{fi}}{\sqrt{2\varepsilon'_2}\sqrt{2\varepsilon'_1}\sqrt{2\varepsilon_2}\sqrt{2\varepsilon_1}},$$ где $\varepsilon_{1,2}$ и $\varepsilon'_{1,2}$ — энергии начальных и конечных частиц. Вспоминая, что $V_{fi}$ —просто преобразование Фурье от потенциала, делаем обратное преобразование и дело в шляпе. Получили потенциал взаимодействия вместе с первой поправкой по релятивизму. Ну, еще, конечно, кинетические члены $-p_{1,2}^2/8m^3$ нужно добавить. Ну и где же здесь обман?

Чтобы сделать обратное преобразование Фурье, нам нужно, чтобы передача $\mathbf{q}$ была независимой переменной. Посчитаем число свободных параметров. $$4\times4(\text{4-импульсы начальных и конечных частиц})-4(\text{закон сохранения})-4(\text{связь} p_i^2=m_i^2)=8$$ Получили, что амплитуда на массовой поверхности имеет восемь независимых параметров. А сколько же нам надо? Девять, по три на каждый вектор $\mathbf{p}_1$, $\mathbf{p}_2$, $\mathbf{q}$. Значит, между этими векторами есть одна связь. И действительно, выражая $q_0$ двумя разными способами, получаем связь $$С=\frac{2\mathbf{qp}_{1}-\mathbf{q}^{2}}{2m_{1}}-\frac{2\mathbf{qp}_{2}+\mathbf{q}^{2}}{2m_{2}}=0$$ А как же мы тогда делали преобразование Фурье...? Добавим к $V_{fi}$, например, $0=\frac{C^2}{\mathbf{q}^4}$ и получим другой потенциал.

На практике, при вычислении в кулоновской калибровке, вопроса не возникает, потому что $q_0$ в ответе не появляется, и не надо думать на что его заменять. В ковариантной калибровке уже появляется $q_0^2$ и правильная прескрипция состоит в том, чтобы заменить $$q_0^2\to \frac{2\mathbf{qp}_{1}-\mathbf{q}^{2}}{2m_{1}}\times\frac{2\mathbf{qp}_{2}+\mathbf{q}^{2}}{2m_{2}}.$$ Объяснение ограничивается словами: "этот рецепт обеспечивает зануление $q_0^2$ в пределе, когда одна из частиц становится бесконечно тяжелой". Ясно, что, по сути, это обман и более правильное рассмотрение должно быть основано, например, на уравнении Бете-Солпитера. Мне лично вообще не понятно, можно ли проблему связанных состояний сформулировать строго (пост отчасти навеян прочтением недавней статьи Ефимова в архиве. В статье, на мой взгляд, содержится, как минимум, логический прокол, но мысль понятна). Но студентам это объяснение не осилить, по-крайней мере, за разумное для всего курса время. Поэтому, проще всего здесь их обмануть. Я, собственно, в свою бытность студентом и не знал что меня обманули, а понял это только когда сам с этим стал разбираться.

Второй пример касается перенормировки электромагнитного тока в КЭД. Открываем, например, Ченга&Ли и читаем (изложение вольное):

Рассмотрим трехточечную функцию Грина $$G_{\mu}(p,q)=\int dx\,dy\, e^{-iqx-ipy}\langle\mathrm{T}J_{\mu}(x)\phi(y)\phi^{\dagger}(0)\rangle$$ и пропагатор $$\Delta(p)=\int dx\,e^{-ipx}\langle\mathrm{T}\phi(x)\phi^{\dagger}(0)\rangle$$ (Здесь под знаком T-упорядочивания стоят гейзенберговские операторы). Тождество Уорда — связь между этими функциями: $$-iq^{\mu}G_{\mu}(p,q)=\Delta(p+q)-\Delta(p)$$. Перенормированные функции определяются соотношениями \begin{eqnarray}G^{R}_{\mu}(p,q)&=&Z_{\phi}^{-1}Z_J^{-1}G_{\mu}(p,q)\nonumber\\\Delta^{R}(p)&=&Z_{\phi}^{-1}\Delta(p)\end{eqnarray} Подставляя в тождество Уорда, получаем $$-iq^{\mu}Z_JG^{R}_{\mu}(p,q)=\Delta^R(p+q)-\Delta^R(p)$$. Поскольку правая часть не зависит [в размерностной регуляризации] от точки вычитания, величина $Z_J$ в левой части также не должна зависеть от точки вычитания. Другими словами, сохраняющийся ток не перенормируется.

Этот пассаж сделан для теории $\phi^4$, и в этой теории вывод правилен. Но в КЭД, за исключением тривиального случая, нужно включить взаимодействие с э/м полем $A$. Вопрос: что окажется неправильным в вышеприведенном пассаже?

Неправильной оказывается молчаливо подразумевающаяся мультипликативная перенормируемость оператора $J_\mu$. На самом деле, этот оператор в результате взаимодействия смешивается с оператором $\partial^{\nu}F_{\nu\mu}$.

Уже в одной петле мы можем это понять. Как обычно, пишем $$\langle\mathrm{T}J_{\mu}(x)\psi(y)\bar\psi(0)\rangle=\langle\mathrm{T}J_{I\mu}(x)\psi_I(y)\bar\psi_I(0)\cdot\exp\left[-ie\int dx (A_I\cdot J_I)\right]\rangle$$ Здесь индекс $I$ относится к операторам в представлении взаимодействия. Если просто заменяем экспоненту на единицу, получаем борновский м.э. Дальше мы должны разложить экспоненту до второго члена, вычислить матричный элемент в размерностной регуляризации и взять из него $1/\epsilon$ члены. Если оператор перенормируется мультипликативно, то при них должна собраться борновская структура (с коэффициентом). Спаривание операторов приводит к следующим диаграммам:

Расходящаяся часть (РЧ,члены $1/\epsilon$ в размерностной регуляризации) есть во всех четырех. РЧ первых трех диаграмм пропорциональны борновскому результату ($\propto \gamma_{\mu}$, если ампутировать внешние концы). Более того, РЧ первой диаграммы можно отнести к $Z_{\psi}$, а РЧ второй сокращается с РЧ третьей, что можно проверить прямым вычислением. Все было бы хорошо, если бы не последняя, четвертая диаграмма. РЧ этой диаграммы имеет другую структуру ($\propto \gamma^{\nu}(q_{\nu}q_{\mu}-q^2 g_{\nu\mu})$), что совпадает с борновской структурой для оператора $\partial^{\nu}F_{\nu\mu}$ в таком же матричном элементе $$\int dx\,dy\, e^{-iqx-ipy}\langle\mathrm{T}(\partial^{\nu}F_{\nu\mu})(x)\psi(y)\bar\psi(0)\rangle\,.$$ Это и показывает смешивание операторов $J$ и $\partial F$. Кто хочет бОльших красот и строгости, смотреть статью Collins,Manohar&Wise. Опять-таки, стоит ли это обсуждать со студентами? Или пусть они лучше запомнят, что сохраняющийся ток не перенормируется? Это утверждение, хотя, как любое категорическое, и не правильное, но все-же физически важное. Так же, как и мое утверждение про обман студентов.

P.S. Мне, кстати, обман обычно не удается, и я начинаю бормотать "правильное объяснение", пытаясь уложиться в одну фразу, что понимания не прибавляет.

Принцип суперпозиции

Недавно (мм..., пока писал пост стало уже не так недавно), придя утром на работу, зацепился за одного коллегу темой о квантовой механике. Точнее, он за меня зацепился. Пока говорили, я вспомнил, что эту тему мы уже один раз обсуждали. Речь шла о процессе измерения и физическом смысле волновой функции. Как известно, последний состоит в том, что квадрат оной пропорционален вероятности обнаружить частицу в данном состоянии (в координатном представлении - в данной точке, в импульсном - с данным импульсом, и т.д.). Таким образом, этот физический смысл завязан за процесс измерения. С другой стороны, в квантовой механике вся динамика задается уравнением Шредингера, а значит процесс измерения должно также описать в рамках этой динамики. Но вот это описание, как раз, не так просто придумать. Точнее, вроде довольно очевидно, что это невозможно. На следующий день попробовал обсудить вопрос со старшим коллегой Ч., но кроме надрывания глоток во время сугубо научной дискуссии, лишь изредка переходящей на личности, никакого положительного опыта не получил.

Попробую объяснить проблему. Оставим в стороне все нюансы, связанные с релятивистской теорией поля, а будем считать, что все важные для нас моменты можно изучить на квантовой механике. В квантовой механике у нас есть уравнение Шредингера, которое прекрасно описывает динамику системы. Ну решили мы это уравнение, остается вопрос: как сравнить наше решение с экспериментом? Ответ-то мы знаем: волновая функция позволяет вычислить вероятность того или иного исхода измерения. Но этот ответ является, конечно, практически очень полезным и успешным, но все-же ни откуда не следующим рецептом, который позволяет связать наш вымышленный мир, в котором существует волновая функция, и реальный мир с его измерениями. Привыкнуть к этому рецепту очень даже можно, нет вопросов. Можно даже волновую функцию в каком-то смысле измерять: возьми набор идентичных систем и измеряй разные проекции (точнее, квадраты их модулей) в.ф., а потом по этим измерениям определяй в.ф. Но ведь прибор --- это тоже часть нашего мира, а значит, тоже подчиняется, по нашим предположениям, законам квантовой механики. Пусть прибор — некоторая сложная квантовомеханическая система. Процесс измерения состоит во включении некоторого взаимодействия прибора с наблюдаемым объектом. Последний для простоты выберем, например, прибитой гвоздями частицей со спином 1/2, а прибор хотим сконструировать так, чтобы он измерял проекцию спина на ось z. Хотим, конечно, чтобы прибор был идеальным, т.е., при состоянии частицы |↑⟩ он всегда показывал ⬆, а при |↓⟩ — ⬇. Что значит "показывал"? Это значит, что у прибора есть, например, два набора попарно ортогональных состояний ⬆={|⬆₁⟩,|⬆₂⟩,...} и ⬇={|⬇₁⟩,|⬇₂⟩,...} и в результате взаимодействия с |↑⟩ прибор переходит в состояние, являющееся линейной комбинацией состояний из первого набора, а в результате взаимодействия с |↓⟩ — в состояние, являющееся линейной комбинацией состояний из второго набора. Вообще говоря, нас устроит и если система прибор+объект после измерения будет находиться в запутанном состоянии типа α|⬆₁⟩|↑⟩+β|⬆₂⟩|↓⟩ для начального состояния |↑⟩ объекта и в состоянии типа α|⬇₁⟩|↑⟩+β|⬇₂⟩|↓⟩ для начального состояния |↓⟩ объекта. Но это дальнейших рассуждений не портит.

Возьмем теперь объект в состоянии |→⟩=(|↑⟩+|↓⟩)/√2. Что должен показывать наш прибор после измерения?  Мы хотим, чтобы он с равной вероятностью показывал ⬆ и ⬇. Когда мы говорим о вероятности, мы имеем в виду возможность различных исходов измерения в зависимости от начального состояния прибора и способа включения его взаимодействия с наблюдаемым объектом. При этом, в каждом конкретном измерении прибор показывает либо ⬆, либо ⬇, но не линейную комбинацию, на то он и классический. Так вот, принцип суперпозиции говорит нам, что такого прибора не может быть. Линейность уравнения Шредингера говорит нам, что наш прибор будет находиться как раз в смешанном состоянии, которое включает в себя и состояния из набора ⬆ и состояния из набора ⬇. Невозможность описать процесс измерения в рамках квантовой механики означает что квантовая механика не полна. А почему тогда этим вопросом никто не занимается? Или занимается?

 

В очереди

В очередной раз стоя в очереди на автобус, придумал задачу:

Ты стоишь в очереди на автобус. Перед тобой $n$ человек. Автобус приходит каждые десять минут. За это время к каждому человеку в очереди (включая тебя самого) с вероятностью $\frac{1}{2}$ подходит знакомый и встает впереди. Чему равна вероятность того, что ты в конце концов уедешь, если в автобус входит $k$ человек?

Я пока даже для $n=k=1$ не решил, но проверил с помощью pslq, что $P(n=1,k=1)$ не является алгебраическим числом.

Жажда творчества

Когда нет возможности делать хоть что-нибудь новое на работе (по причине навалившейся рутины), приходится отводить душу на всякой ерунде. Вчера просмотрел забавный ролик на Youtube (в моей живой ленте есть) и не смог удержаться от того чтобы написать демонстрашку. Если вы еще не посмотрели ролик, попробуйте ответить на следующий вопрос. На рисунке изображена тележка(зеленая) на двух колесах (синих). Сверху лежит катушка от ниток (красная), которая внутренним диаметром касается колес. Еще выше изображена линейка, которую мы собираемся тянуть, скажем, вправо. Вопрос такой: куда поедет тележка?

---

---

PS Да, чуть не забыл, если хочется проверить свою догадку, кликните на линейку.
PPS В хроме линейка проскальзывает.

Задача

Недавно прочитал в википедии забавную статью и написал скрипт в духе "Petals around the rose".

---

1

---

Ну, вопрос, понятно, как это работает.
PS Только нецелые числа вводить не надо, а то зациклится.

В борьбе за аудиторию

Вчера убил вечер, пытаясь заставить блоггер показывать математические формулы во всех браузерах. Ну, по-крайней мере, в Firefox, Opera и Chrome.
Гришино решение, конечно, впечатляет. Везде выглядит нормально, даже на смартфоне (он его, правда, по-другому называет). Но если заглянуть в код, то видно, что эта красота нерукотворная создана посредством шинкования пространства с помощью клеток таблицы. Это означает, что обратный процесс перевода в человеческий формат едва ли возможен. А теперь допустим появится через полгодика идеальный способ воспроизводить формулы в вебе. Тогда эта красота останется не у дел, не исправить ее, не использовать повторно будет невозможно. Так что такой подход, по-моему, даже хуже замены формул картинками. А полная масштабируемость, ну кому она особенно нужна? Картинки ведь тоже можно немного растянуть если очень хочется.
Так что я решил остаться на MathML. Фактически, это означает, что формулы у меня в блоге нормально выглядели только в FF. Вчера я нашел в и-нете проект под названием MathJax и он мне показался ничего. Синтаксис копирует MathML, заменяя родные <mrow...></mrow> таги на что-то типа <span class='mrow'...></span> и т.д.
Одна проблема, все работает, когда он установлен на том же сервере, что и страничка, на которой он используется. Дело оказалось в излишней подозрительности современных браузеров. При попытке на лету добыть нужные шрифты с http://www.mathjax.org они применяют same-origin security policy и не грузят шрифты. Утверждалось, что это исключительно проблемы FF, но вскрытие показало, что и современная Opera тоже не лучше. В Chrome, впрочем, все работает. Нужно просто вставить

<script src="http://www.mathjax.org/MathJax/MathJax.js">
    MathJax.Hub.Config({
    delayStartupUntil: "onload",
    jax: ["input/MathML", "input/TeX", "output/HTML-CSS"],
    extensions: ["tex2jax.js"],
    tex2jax: {
      inlineMath: [['$','$'], ['\\(','\\)']], 
      processEscapes: 1
    }
  });
</script>

куда-нибудь в голову страницы.
В результате я сделал так, чтобы в FF работал прежний скрипт LaTeXMathML.js, а в остальных браузерах MathJax. Но, как я уже сказал, в Опере рецепт не работал. Помогло просто тупое скачивание шрифтов с сайта MathJax и установка .otf версий в систему. Теперь, наверное, и в FF работал бы MathJax, но ведь не все захотят шрифты устанавливать.

PS. Забыл какую-нибудь тестовую формулу вставить. Вот

\[ \int_{-\infty}^{\infty} dx\int_{-\infty}^{\infty} dy \frac{x^2-y^2}{(1+x^2+y^2)^2}=? \]

Подписали несовершеннолетних

Если набрать в гугле "signed minors", ничего хорошего не получишь, по-крайней мере, на первой странице. Например, вторая сверху ссылка называется "Minor Signed an Agreement to Pay Debts". Вот тебе и релевантность результатов поиска. Английская википедия более продвинута, поскольку четвертый пункт называется cofactors и действительно имеет отношение к теме. Но все-таки, кофактор это частный случай signed minor-а, так сказать, next-to-adult, пользуясь принятой терминологией. Закончил филологические изыскания в гугловском переводчике, который, ничтоже сумняшеся, выдал тему. Красиво, точно, но, как говорится в известном мультике, для своих я просто Нюша, а точнее, минор со знаком (криво все-таки звучит).

Мне, конечно, кажется, что все про миноры со знаком должны знать, но на всякий случай объясню. Как учат нас старшие товарищи, объяснять как раз и нужно то, что, в общем-то, объяснять не нужно. А то, что действительно нужно объяснять, нужно старательно заметать под ковер дабы не вызвать в слушателях ненужных сомнений. Вот и я обнаружил и доказал недавно два красивых тождества и ну очень хотел впихнуть их в свой вклад в труды конференции, но когда дело до этого дошло, понял, что погрязну в объяснениях. Ограничился тем, что привел в статье частный случай одного из них и написал поясняющую все и сразу  фразу, оканчивающуюся на "presented elsewhere". Но зато успел отправить сегодня (в дедлайн).

Да, про миноры со знаком. Если есть у нас матрица
\[\left[\begin{array}{ccc}r_1^1&\ldots&r_N^{1}\\\vdots&\ddots&\vdots\\r_1^N&\ldots&r_N^N\end{array}\right]\]
будем называть ее $\left(\begin{array}{c}i_1,\ldots,i_m\\j_1,\ldots,j_m\end{array}\right)$-минором (обозначение только что придумал) детерминант матрицы, которая получается из исходной вычеркиванием столбцов под номерами  $i_1,\ldots,i_m$ и строк под номерами $j_1,\ldots,j_m$. Видим, что минор симметричен по верхним и по нижним индексам. А минор со знаком — антисимметричен. Потому что от просто минора отличается таким множителем
\[(-1)^{i_1+\ldots+i_m+j_1+\ldots+j_m}\sigma(i_1,\ldots, i_m)\sigma(j_1,\ldots, j_m)\]
Здесь $\sigma(i_1,\ldots, i_m)=\pm 1$ обозначает четность перестановки, которую нужно сделать чтобы упорядочить по возрастанию ряд чисел $i_1,\ldots, i_m$. Обозначать этот страх будем так
\[R_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}=(-1)^{i_1+\ldots+i_m+j_1+\ldots+j_m}\sigma(i_1,\ldots, i_m)\sigma(j_1,\ldots, j_m)\left(\begin{array}{c}i_1,\ldots,i_m\\j_1,\ldots,j_m\end{array}\right)\]
Например, детерминант всей матрицы будет равен
\[R=\left(\begin{array}{с}\, \\\, \end{array}\right)=\left|\begin{array}{ccc}r_1^1&\ldots&r_N^{1}\\\vdots&\ddots&\vdots\\r_1^N&\ldots&r_N^N\end{array}\right|\]
Если наша матрица состоит из независимых переменных, то мы можем любой минор со знаком получить простым дифференцированием $R$:
\[R_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}=\frac{\partial}{\partial r_{i_1}^{j_1}}\ldots \frac{\partial}{\partial r_{i_m}^{j_m}} R\]

Теперь вернемся к теореме Карла Якоби (см. предыдущий пост)

"If the determinant of a block $= R$, the determinant of any minor of the $m$th degree of the adjugate block is the product of $R^{m-1}$ and the coefficient which, in $R$, multiplies the determinant of the corresponding minor."

(C.Jacobi)

В терминах наших миноров со знаком эту теорему можно записать так
\[m! R_{j_1}^{[i_1}\ldots R_{j_m}^{i_m]}=R^{m-1}R_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}\]
Я этого сразу не понял, но ведь мне никто и не подсказал. Так что эквивалентность выписанной формулы теореме Якоби должна быть понятна. Вообще-то, это уравнение говорит чуть больше, чем теорема Якоби, но это "чуть больше" — тривиальное утверждение, что если есть повторяющиеся верхние или нижние индексы, то ноль с обеих сторон и довольно простое утверждение о том, что знак правильный.
Кстати, тождество Доджсона Desnanot-Jacobi — это частный случай теоремы при $m=2$. Кстати, эквивалентное этому тождество и тоже очень красивое можно записать так
\[C_{m}^k R_{j_1\ldots j_k}^{[i_1\ldots i_k}\,R_{j_{k+1}\ldots j_m}^{i_{k+1}\ldots i_m]}=R\,R_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}\]

Теперь собственно к найденным мной (приоритет!) тождествам. Я их умею доказывать, используя теорему Якоби, но кто же эту скуку в состоянии будет прочитать. А между тем, сами тождества — красоты неописуемой (в смысле, легче предъявить тождества, чем описать их красоту). Рассмотрим такой оператор
\[D_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}=\left|\begin{array}{ccc}\frac{\partial}{\partial r_{i_1}^{j_1}}&\ldots&\frac{\partial}{\partial r_{i_m}^{j_1}}\\\vdots&\ddots&\vdots\\\frac{\partial}{\partial r_{i_1}^{j_m}}&\ldots&\frac{\partial}{\partial r_{i_m}^{j_m}}\end{array}\right|\]
Первое тождество такое
\begin{equation}D_{j_1,\ldots,j_m}^{i_1,\ldots,i_m} (R)^{\alpha}=\alpha (\alpha+1)\ldots (\alpha+m-1)R_{j_1,\ldots,j_m}^{i_1,\ldots,i_m} (R)^{\alpha-1}\end{equation}

А теперь рассмотрим симметричную матрицу
\[\left[\begin{array}{ccc}s_{1,1}&\ldots&s_{1,N}\\\vdots&\ddots&\vdots\\s_{1,N}&\ldots&s_{N,N}\end{array}\right]\]
Мне-то в статье как раз такая нужна была.  Соответственно, миноры будем буквой $S$ обозначать. Вопрос: можно ли похожую формулу написать для этого случая? Оказывается, можно. Используем теперь такой оператор
\[\tilde{D}_{j_1,\ldots,j_m}^{i_1,\ldots,i_m}=\left|\begin{array}{ccc}2^{\delta_{i_1,j_1}-1}\frac{\partial}{\partial s_{i_1,j_1}}&\ldots&2^{\delta_{i_m,j_1}-1}\frac{\partial}{\partial s_{i_m,j_1}}\\\vdots&\ddots&\vdots\\2^{\delta_{i_1,j_m}-1}\frac{\partial}{\partial s_{i_1,j_m}}&\ldots&2^{\delta_{i_m,j_m}-1}\frac{\partial}{\partial s _{i_m,j_m}}\end{array}\right|\]
Так вот, второе тождество выглядит так
\begin{equation}\tilde{D}_{j_1,\ldots,j_m}^{i_1,\ldots,i_m} (S)^{\alpha}=\alpha (\alpha+1/2)\ldots (\alpha+(m-1)/2)S_{j_1,\ldots,j_m}^{i_1,\ldots,i_m} (S)^{\alpha-1}\end{equation}

Вот такая производная по минору.

Матрицы и уравнения

Как известно, Льюис Кэрролл не только написал книги про Алису, но и был математиком. Занимался он в основном линейными уравнениями, матрицами и детерминантами. Я о его математических достижениях узнал совсем недавно. Точнее, я прочитал его статью о методе вычисления детерминантов.
Вот что он придумал. Пусть, например, нам нужно вычислить детерминант матрицы

\[\left[\begin{array}{ccccc}4&4&2&1&2\\4&4&5&2&2\\4&2&5&3&1\\2&5&3&1&2\\1&2&0&4&5\end{array}\right]\]

Делаем так: сначала вычисляем детерминанты блоков $2\times 2$ и строим из них матрицу размерности на один меньше:

\[\left[\begin{array}{cccc}0&12&-1&-2\\-8&10&5&-4\\16&-19&-4&5\\-1&-6&12&-3\end{array}\right]\]

Далее делаем то же самое, но теперь каждый детерминант $2\times 2$ делим на соответствующий элемент внутренности первой матрицы. Внутренность матрицы — это матрица, получающаяся из исходной вычеркиванием первой и последней строки и первого и последнего столбца. Получаем

\[\left[\begin{array}{ccc}24&14&7\\-4&11&3\\-23&-84&-48\end{array}\right]\]

Повторяя процесс, получаем

\[\left[\begin{array}{ccc}\begin{array}{cc} 32 & -7 \\-31 & 69\end{array}\end{array}\right]\]

\[\left[181\right]\]

Получившееся число и есть детерминант исходной матрицы.

Если сравнить число операций

\[N(\mbox{Доджсон})=3(n-1)^2+4(n-2)^2+\ldots=\frac{1}{3} (n-1) \left(4 n^2-5 n+3\right)\]

с числом операций при разложении по строке

\[N(\mbox{По строке})=e \Gamma (n+1,1)-2,\]

(эту формулу можно получить, решая рекуру) видим, что для больших матриц получаем значительный выигрыш. Но если мы будем просто методом Гаусса приводить матрицу к треугольному виду, получим

\[N(\mbox{Гаусс})=\frac{1}{6} (n-1) \left(4 n^2+n+6\right)\]

т.е., немного лучше, чем метод Доджсона. Есть еще особенные случаи, когда один из внутренних элементов матрицы оказывается равным нулю. В этом случае получается неопределенность и нужно начинать почти сначала. Так что с практической точки зрения метод Доджсона так себе. Вообще-то, я статью стал читать по другому поводу, а именно, по поводу так называемого тождества Доджсона, которое на поверку оказалось элементарным следствием теоремы Якоби, приведенной опять в  вышеупомянутой статье:

" If the determinant of a block $= R$, the determinant of any minor of the $m$th degree of the adjugate block is the product of $R^{m-1}$ and the coefficient which, in $R$, multiplies the determinant of the corresponding minor."

(Jacobi)

Про эту теорему и про красоты с ней связанные я еще, может быть, напишу. Ну а пост этот написан чтобы проверить работу скрипта LaTeXMathML.js, а точнее, его модификации, которая позволяет делать матрицы и выключные уравнения, используя нормальный синтаксис LaTeXа. И еще, этот скрипт работает и для Оперы.

---

PS Только что выяснил, что описанный метод вычисления детерминантов можно найти в английской википедии в соответствующей статье. Там тождество Доджсона называется Desnanot-Jacobi identity, и это, по-моему, правильно.

Интерференция и SVG

Вчера Ваня напомнил про один вопрос из квантовой механики, с которым я когда-то разобрался.
Все знают, как борновская амплитуда рассеяния на нескольких одинаковых центрах выражается через амплитуду рассеяния на одном. А именно, появляется множитель
\[F(\vec{q})=\sum_{k=0}^{N} e^{i\vec{q}\vec{r}_k}.\]
Если центры образуют периодическую структуру, этот множитель приводит к тому, что в интерференционных максимумах сечение увеличивается в $N^2$ раз.
Допустим теперь, что мы случайно бросаем рассеивающие центры в большой ящик и после этого они остаются неподвижными. Каким будет сечение? Я в свою бытность студентом 3-его курса, пока не обдумал вопрос самостоятельно, считал, что дифференциальное сечение будет примерно равно
\[\frac{d\sigma_N}{d\Omega}\approx N\frac{d\sigma_1}{d\Omega},\]
а отклонения будут расти медленнее чем $N$ (как $\sqrt{N}$). Ниже скрипт, который поможет "экспериментально" изучить вопрос. Как можно заметить, отношение сечения на $N$ центрах к умноженному на $N$ сечению на одном и не думает стремиться к единице при $N\to\infty$. Действительно ли это так, или это артефакт моделирования?

---

$\displaystyle{\frac{d\sigma_N/d\Omega}{N d\sigma_1/d\Omega}=\left|F(q)\right|^2/N=}$?

$\lambda=\frac{2\pi}{q}=$ — расстояние между красными линиями.

---

Вообще-то, этот пост еще служит проверкой возможности включения svg в блог. Скажу честно, делается через ж... использование javascript. Правда, если хочешь интерактивности, javascript все-равно нужен. Кто будет смотреть в код, обратите внимание на функцию createSVG. Вроде, мелочь, а времени много экономит.

Измерения и информация

Заголовок получился многозначительным, но речь пойдет не о принципах квантовой механики, а о задачах на взвешивание и измерение.

Все, наверное, решали задачу про 12 монет:

Как за три взвешивания на обычных чашечных весах найти одну фальшивую (легче или тяжелее настоящей) монету из двенадцати?

Задача не тривиальная, но все же, немного подумав, решить можно. Сразу возникает вопрос: а нельзя ли увеличить общее количество монет? Оказывается, что можно до 13. А если есть эталонная, то и до 14. А из скольки монет можно найти фальшивую за четыре взвешивания, за пять?

Сформулируем задачу для любителей обобщений:

Из какого максимального количества монет и каким образом можно найти одну фальшивую за $n$ взвешиваний?

Задачу эту я узнал, на школе Ландау в Черноголовке в далеком 1997 году. На этой школе еще были интересные лекции про криптографию, например, нам рассказали как работает алгоритм шифрования с открытым ключом RSA . Но сейчас не об этом. Со мной был один товарищ, который предложил рекурсивный подход: сначала сгруппировать монеты в кучки, найти среди кучек фальшивую, а затем среди монет этой кучки найти фальшивую. Например, для $n=6$ взвешиваний можно взять аж $13\cdot 14=182$ монеты и сначала применить достижения первой задачи к 13 столбикам по 14 монет, а затем их же к монетам "фальшивого столбика". Хорошая идея, но я решал задачу совсем по-другому и у меня для $6$ взвешиваний получалось $364$ монеты. С тех пор я уже не раз порывался написать какую-нибудь популярную заметку об этой и других подобных задачах, но руки так и не дошли. Я также несколько раз задавал эту задачу коллегам/товарищам, но почему-то у них она не пошла.

Недавно я вспомнил эту историю потому что решал на сайте Diofant.ru другую задачу. Для тех, кому не хочется идти по ссылке, приведу условие:

Среди нескольких компьютерных чипов есть два поддельных, которые обладают повышенной радиоактивностью, а в остальном не отличаются от настоящих. В имеющийся прибор можно засунуть любое количество чипов и узнать, есть ли среди них радиоактивный (но нельзя понять, сколько именно — один или два). Каково максимальное число чипов, среди которых можно гарантировать обнаружение обоих поддельных за 7 проверок?

Опять же, в условии можно заменить 7 на $n$. А можно и два радиоактивных (при чем тут радиоактивность?) заменить на $m$.

Итак, те, кто все-же хотят решить задачу про монеты самостоятельно, должны воздержаться от чтения текста под чертой. А те кто будут читать — пусть не обвиняют меня в том, что я испортил им удовольствие.

---

Подсказка Подумайте о том, какое количество информации можно получить за одно взвешивание. Сколько неизвестной информации останется после этого в худшем случае? В этой задаче информацию лучше считать в трибитах (точнее, в тритах).

Скрипт:
Вот еще одна подсказка — рабочий скрипт:

Введите число взвешиваний

 

0		0

 

---

Ответ Максимальное число монет при отсутствии эталонной равно
\[N=\frac{3^n-1}2\]
Максимальное число монет при наличии эталонной равно
\[N=\frac{3^n+1}2\]

Первое взвешивание: $(3^{n-1}-1)/2$ на каждой чашке. Если есть эталонная, то $(3^{n-1}+1)/2$ на одной чашке и $(3^{n-1}-1)/2$ плюс эталонная — на другой. После $k$-ого взвешивания может быть три ситуации:

1. Фальшивая монета находится среди $(3^{n-k}+1)/2$ монет.
2. Фальшивая монета содержится в одной из двух стопок, причем легче она или тяжелее определятся тем, в какой именно стопке она находится. В стопках находится $(3^{n-k}+1)/2$ и $(3^{n-k}-1)/2$ монет (если нужно, можно добавить эталонную).

В зависимости от случая, делаем следующее:

1. В первом случае кладем из стопки под подозрением $(3^{n-k-1}+1)/2$ на одну чашу и $(3^{n-k-1}-1)/2$ плюс эталонная — на вторую. После взвешивания получаем случай 1 или случай 2.
2. Во втором случае на каждую чашу кладем из большей стопки по $(3^{n-k-1}+1)/2$ монет, а из меньшей — по $(3^{n-k-1}-1)/2$. После взвешивания получаем случай 2.

Очевидно, после $k=n$ взвешиваний оба случая однозначно определяют фальшивую.

Ускорение сходимости

Недавно пришлось разобраться в вопросе об ускорении сходимости последовательностей. До этого я был в полной уверенности, что знаю достаточно об этом, а чего не знаю — и не надо никогда. Но оказалось, что бывает надо. Расскажу про один простой метод, описанный в статье Дэвида Бродхерста (Broadhurst). Статья, конечно, не про метод.

Рассмотрим в качестве подопытной свинки $\zeta$-функцию Римана:
\[\zeta(n)=\sum_{k=1}^{\infty}\frac 1{k^n}\]

Просуммировав $N$ членов суммы, получим примерно $P\approx (n-1)\log_{10}N$ десятичных знаков. Можно, конечно, "пришить хвост", т.е., аппроксимировать остаток суммы интегралом, но это не может изменить того факта, что сходимость — логарифмическая $P\propto \log N$. Меняется только коэффициент пропорциональности. Справедливости ради заметим, что для многих практических целей достаточно, чтобы этот коэффициент был достаточно большим. Но что, если нам все-же хочется уметь вычислять такие суммы с высокой точностью?

Замечательный метод ускорения сходимости для таких последовательностей описан в вышеупомянутой статье. Я сначала не особенно сильно на него надеялся. Интуитивно мне казалось, что если мы вычислили $N$ первых членов суммы, то лучшее, что мы с ними можем сделать — просто сложить. Фокус в том, что мы не просто знаем эти члены, но еще и знаем кое-что об остатке $r_k$. А именно, функция $k^{n-1}r_k$ раскладывается в ряд вблизи точки $k=\infty$. Это позволяет построить некоторую взвешенную сумму первых $N$ членов так, что $P\propto N$!

В качестве иллюстрации прилагаю маленький скрипт, написанный по мотивам вышеупомянутой статьи, который вычисляет $\zeta(n)$. Внимательный взгляд найдет пару отличий от описанного в статье. Поскольку написан он на javascript, то точность в какой-то момент теряется (точнее, не растет), но это проблемы вычислений с фиксированной точностью. Вбейте в форму ниже $N$ и $n$ и нажмите кнопку.

---

N= членов суммы для ζ() дают
при тупом суммировании, и
после ускорения.

---

Если кому-то стало интересно, предлагаю выяснить как выглядит вектор весов и определить коэффициент пропорциональности между P и N (экспериментально). Результат может удивить. Еще один вопрос — какой должна быть рабочая точность? Для удобства ниже — упрощенный (без учета потери точности) код скрипта
 function Zeta(N,n) {
  var terms= [0];
  //accumulating from above
  for(var i=N;i>0;i--) {
  terms.push(terms[terms.length-1]+1/Math.pow(i,n));
  };
  //acceleration starts
  for(var m=0;m<N;m++) {
  for(var k=0;k<(N-m);k++) {
  terms[k]=((N-k)*terms[k]-(N-k-m-n+1)*terms[k+1])/(m+n-1)
  };
  };
  //direct sum
  document.getElementById('direct').value=terms[N];
  //accelerated
  document.getElementById('accelerated').value=terms[N]-terms[0];
 }