Общая теория символьных вычислений с суммами и произведениям

[EminentVictorians]

У меня есть один давно незакрытый гештальт по поводу оперирования со значками $\sum\limits_{}^{}$ и $\prod\limits_{}^{}$, а тут как раз выдался подходящий момент и я решил таки разобраться со всем этим. В общем, дело в том, что я не очень умею пользоваться этими значками и, как я думаю, немало теряю из-за этого. Разумеется, я способен использовать что-то в духе $\sum\limits_{k=1}^{n}\lambda a_k = \lambda \sum\limits_{k=1}^{n} a_k$ и подобные простые примеры, но мне этого мало. Вот буквально вчера я что-то доказывал, связанное с определителями, и я более менее мог писать выражения вида

$$\operatorname{det}A = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)}a_{1 \sigma{(1)}} \cdot ... \cdot a_{n \sigma{(n)}}=$$

$$= \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)}a_{\sigma{(1)}1} \cdot ... \cdot a_{\sigma{(n)}n}=$$

$$ = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)}a_{1 (\sigma \circ \tau)(1)} \cdot ... \cdot a_{n (\sigma \circ \tau)(n)}= ... \quad \quad \quad \quad \quad [\tau \quad \text{фиксировано}]$$

Как я для себя обосновывал равенство, например, первой и третьей строчки. Я понимаю, что перестановки образуют группу $S_n$, в группе любое уравнение $ax = b$ или $xa = b$ разрешимо и при том единственным образом, поэтому для любого $c \in G$ $cG = G$ (где $cG = \{cg| g \in G\}$). Я знаю, что это так себе объяснение , можете не говорить)) Хоть и формально корректное.

Но мне хочется оперировать суммами автоматически, не думая. Почему-то проблеме оперирования с суммами/произведениями уделяется довольно мало времени, несмотря на то, что эта тема довольно глубокая. Единственное место из мне известных, где что-то говорят о суммах - это вторая глава в "Конкретной математике". Но это слишком слабый уровень.

Мне хочется почитать общую теорию. Вот в том примере выше, например, использовался факт из теории групп. Да, можно его не использовать, а воспользоваться тем, что любая перестановка - это биекция, а значит все в порядке. Это еще один вариант обоснования. Но хочется пойти еще дальше (и думать еще меньше). Хочется использовать, например, машинерию из логики. Да, в "Конкретной математике" рассказывают про скобку Айверсона, но блин... это все такой незначительный уровень... Нужна теория для сумм со сложными логическими предикатами, чтобы там во всю использовались булевы функции, полиномы Жигалкина, конечные поля и так далее. Чтобы можно было суммировать по произвольной области индексации, чтобы можно было не думать, является ли функция смены индексации биекцией или нет (я думаю, это можно было бы достичь какой-нибудь нотацией, навешивающей на аргумент какой-нибудь алгебраический инвариант). Чтобы можно было комбинировать какими-нибудь нетривиальными способами области идексаций: минимум по линии теоретико-множественных операций (а так-то хочется, например, использовать алгебраическую или иную структуру на множестве индексов и иметь нотацию, которая бы как-нибудь хитро все это дело миксовала, факторизовала и т.д). И чтобы это можно было делать автоматически, не думая.

Для всего этого нужен хороший корпус разработанных теорем и нотаций. Кажется, что это все не шибко уж сложные вещи и должно уже быть сделано. Хотелось бы узнать, встречал ли кто-нибудь такую "общую теорию сумм/произведений" и где об этом можно подробно и обстоятельно почитать (желательно на высоком уровне абстракции и с использованием аппаратов логики, алгебры и т.д.)

[svv]

EminentVictorians в сообщении #1586938 писал(а):

$$\sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)}a_{1 (\sigma \circ \tau)(1)} \cdot ... \cdot a_{n (\sigma \circ \tau)(n)}= ... \quad \quad \quad \quad \quad [\tau \quad \text{фиксировано}]$$

Тут должно быть $\operatorname{sign}(\sigma \circ \tau)$, иначе в случае нечётной перестановки $\tau$ все слагаемые будут с противоположными знаками.
Рассмотрите, например, случай $n=2$ и $\tau=\begin{pmatrix} 1 & 2\\ 2 & 1\end{pmatrix}$.

[мат-ламер]

EminentVictorians . На ваш вопрос я ответить не могу. Но он для меня актуален и я к нему присоединяюсь. Я просто зашёл в тему, чтобы добавить в неё немного конкретики. Хочу рассмотреть следующий пример. Пусть нам надо оказать векторное тождество: $a\times (b\times c)= b(a,c)-c(a,b)$ . Здесь слева у меня двойное векторное произведение, а справа два скалярных, умноженные на вектора. Обычно это равенство доказывается выбором подходящей системы координат, в котором вычисления упрощаются. Но мы не будем искать лёгких путей. Предлагаю попробовать доказать это в стандартном базисе $R^3$, в котором векторное произведение можно записать как $a\times b = \varepsilon^{ijk}a_ib_je_k$ . Здесь у меня $\varepsilon^{ijk}$ - символ Леви-Чевита -то же, что в стартовом посту означает $sign$, то есть он равен $+1$ или $-1$ в зависимости от чётности перестановки; $e_k$ - базисные векторы в $R^3$ ; $a_i$ и $b_j$ - координаты векторов $a$ и $b$ . По повторяющимся индексам у меня подразумевается суммирование.

[EminentVictorians]

svv в сообщении #1586942 писал(а):

Тут должно быть $\operatorname{sign}(\sigma \circ \tau)$

Да, конечно. Кстати, посмотрел в бумаги, у меня даже нету ошибки в этом месте. А все потому, что я использовал хоть и свою, сделанную на коленке, но нотацию.

А именно:
Будем различать перестановки и подстановки. Перестановка - это функция из начального отрезка натурального ряда в себя, а подстановка - это просто упорядоченный набор из первых $n$ натуральных чисел. Т.е.

$$A = \begin{pmatrix} 1 & 2 & 2\\ 3 & 1 & 2 \\ \end{pmatrix}$$

это перестановка (функция, переводящая 1 в 3 и т.д. ... )
а $(3 1 2)$ - это подстановка (просто упорядоченный набор).
Разумеется, между ними есть биекция (ставим в соответствие перестановке ее нижнюю строку в стандартной записи).
Есть тривиальная теорема, что если нам даны 2 подстановки друг над другом вида Т.е.

$$X = \begin{pmatrix} \sigma(1) & ... & \sigma(n) \\ \tau(1) & ... & \tau(n)\\ \end{pmatrix}$$

(где $\tau$ и $\sigma$ - подстановки, соответсвующие перестановкам $\tau$ и $\sigma$, а потому и одноименные с ними), то $X = \sigma^{-1} \circ \tau $ (как перестановка) (биекция везде понимается в "понятном" смысле: $f \circ g = g(f())$ ).

Здесь у нас первые индексы не перемешаны, поэтому все еще проще:

$$\operatorname{det}A = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)}a_{1 \sigma{(1)}} \cdot ... \cdot a_{n \sigma{(n)}}=$$

$$ = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma \circ \tau)}a_{1 (\sigma \circ \tau)(1)} \cdot ... \cdot a_{n (\sigma \circ \tau)(n)}=$$

$$ = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\sigma)} \cdot \operatorname{sign (\tau)} a_{1 (\sigma \circ \tau)(1)} \cdot ... \cdot a_{n (\sigma \circ \tau)(n)}=$$

А если бы были перемешаны, было бы так:

$$\operatorname{det}A = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\tau^{-1} \circ \sigma)}a_{\tau(1) \sigma{(1)}} \cdot ... \cdot a_{\tau(n) \sigma{(n)}}=$$

$$ = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\tau ^{-1}) } \cdot \operatorname{sign (\sigma })}a_{\tau(1) \sigma{(1)}} \cdot ... \cdot a_{\tau(n) \sigma{(n)}}=$$

$$ = \sum\limits_{\sigma \in S_n}^{}\operatorname{sign (\tau)} \cdot \operatorname{sign (\sigma)} a_{\tau(1) \sigma{(1)}} \cdot ... \cdot a_{\tau(n) \sigma{(n)}}=$$

Даже здесь, в таком простом примере, использовался факт из теории групп: $\operatorname{sign (\tau \circ \sigma)} = \operatorname{sign (\tau)} \cdot \operatorname{sign (\sigma)}$ (т.к. оператор знака перестановки является гомоморфизмом из $S_n$ в $\mathbb Z^{*}$ (группу обратимых элементов кольца $\mathbb Z$.)


Так что я даже в некотором смысле не сильно и расстроился, когда ошибся в стартовом посте. Это же только подтверждает мою мысль: хорошая, богатая нотация необходима. А без нее придется много думать и иногда будут вот такие вот ошибки, которые чисто по невнимательности.

[мат-ламер]

мат-ламер в сообщении #1586952 писал(а):

Хочу рассмотреть следующий пример.

К сожалению, ничего хорошего в духе предложенном топик-стартером не придумал. Как вообще доказывать предложенное равенство, понятно. Но все способы немного специфичны или тупы.

мат-ламер в сообщении #1586952 писал(а):

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

У Беклемишева так доказывается.

мат-ламер в сообщении #1586952 писал(а):

Предлагаю попробовать доказать это в стандартном базисе $R^3$

В пособии Степанова тупо расписывается каждый член слева и справа равенства. В пособии Александрова предлагается использовать специфическое тождество: произведение двух символов Леви-Чевита выражается через четыре символа Кронекера.

[EminentVictorians]

мат-ламер, спасибо. Есть еще один похожий сюжет: доказать "в лоб" формулу для определителя произведения $\operatorname{det}AB = \operatorname{det}A \operatorname{det}B$. Я бы может быть даже пописал бы какие-нибудь выкладки, будь у меня энтузиазм, но я хочу именно развитую теорию. Я сторонник идеи, что теория должна быть насыщенной, а практика должна делаться легко. Не люблю решать задачи сложно, когда эта сложность определяется не сложностью концепции, а бедностью инструментария.

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

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

[mihaild]

EminentVictorians в сообщении #1587018 писал(а):

Даже на уровне абелевых групп можно было бы формулировать теоремы типа "сумма инварианта относительно биективных операторов смены индексации" или что-то в таком духе.

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

EminentVictorians в сообщении #1587018 писал(а):

доказать "в лоб" формулу для определителя произведения $\det AB = \det A \det B$.

Исходя из какого определения определителя?

(det)

Как подсказывает форма набора сообщений, det - стандартный оператор, его не надо в operatorname заворачивать.

[EminentVictorians]

mihaild в сообщении #1587019 писал(а):

Ну если сильно хочется, то можно считать что сумма - это интеграл по считающей мере

Мне нравится эта идея. Но это обобщение немного в другую сторону. Я имею в виду примерно вот что. Допусти есть две суммы: одна по множеству $X$, другая по множеству $Y$. Мы хотим найти сумму по множеству $Z$, как-нибудь образованному от множеств $X$ и $Y$. Ладно, если это просто пересечение там или объединение. А если мы, например, образуем множество $Z$ с помощью какой-нибудь сложной формулы с большим числом разных теоретико-множественных операций. Пусть нам повезло и есть какое-нибудь одно объемлющее множество. Мы же знаем, что булеан образует алгебру над $\mathbb Z / 2\mathbb Z$ относительно симметрической разности и пересечения (и понятно какого умножения на скаляры). Было бы здорово, если бы были теоремы, связывающие суммирование вот с этой алгеброй. И можно было бы считать какие-нибудь нетривиальные суммы, используя то свойства сумм, то делая вычисления в этой алгебре, переходить из одного "мира" в другой и по итогу приходить к чему надо. Но это просто пример, а не конечная цель. Так-то хочется гораздо более богатую теорию, чем то, что я написал только что.

Я понимаю, что сумбурно объясняю, но по-другому пока не могу. Нужна "общая теория символического суммирования", лучше пока не могу сказать.

mihaild в сообщении #1587019 писал(а):

Исходя из какого определения определителя?

По формуле Лейбница (сумма по всем перестановкам...).

[мат-ламер]

EminentVictorians в сообщении #1587018 писал(а):

Есть еще один похожий сюжет: доказать "в лоб" формулу для определителя произведения $\operatorname{det}AB = \operatorname{det}A \operatorname{det}B$. Я бы может быть даже пописал бы какие-нибудь выкладки, будь у меня энтузиазм, но я хочу именно развитую теорию.

А есть ли оно, доказательство в лоб? У меня впечатление, что доказательства этого факта интересные, специальные, но не скажешь, что они проделаны на автомате "в лоб". Правда, я знаком конечно не со всеми. Посмотрите Винберга (или Кострикина). Там доказательство основано на некоторой весьма специальной лемме. Помню, что у нас на лекциях доказательство строилось тоже весьма специфическим способом - через построение некоторой матрицы удвоенного размера. Сейчас посмотрел Гантмахера. Там доказывается через формулу Бине-Коши. Тоже не скажешь, что доказательство идёт в лоб на автомате.

[Padawan]

EminentVictorians в сообщении #1587018 писал(а):

Есть еще один похожий сюжет: доказать "в лоб" формулу для определителя произведения $\operatorname{det}AB = \operatorname{det}A \operatorname{det}B$.

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

[Padawan]

$C=AB$, $c_{ij}=\sum\limits_{k=1}^n a_{ik}b_{kj}$, $\det A=\sum\limits_{\tau\in S_n}\operatorname {sgn}\tau a_{1\tau(1)}a_{2\tau(2)}\ldots a_{n\tau(n)}$, $\det B=\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma b_{1\sigma(1)}b_{2\sigma(2)}\ldots b_{n\sigma(n)}$.

$$ \det C=\sum\limits_{\sigma\in S_n} \operatorname {sgn}\sigma c_{1\sigma(1)}c_{2\sigma(2)}\ldots c_{n\sigma(n)}= $$

$$ =\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma \big(a_{11}b_{1\sigma(1)}+a_{12}b_{2\sigma(1)}+\ldots+a_{1n}b_{n\sigma(1)}\big)\big(a_{21}b_{1\sigma(2)}+a_{22}b_{2\sigma(2)}+\ldots+a_{2n}b_{n\sigma(2)}\big)\ldots $$

$$ \ldots\big(a_{n1}b_{1\sigma(n)}+a_{n2}b_{2\sigma(n)}+\ldots+a_{nn}b_{n\sigma(n)}\big)= $$

$$ =\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma\sum\limits_{k_1,k_2,\ldots,k_n=1}^n a_{1k_1}b_{k_1\sigma(1)}a_{2k_2}b_{k_2\sigma(2)}\ldots a_{nk_n}b_{k_n\sigma(n)}= $$

$$ =\sum\limits_{k_1,k_2,\ldots,k_n=1}^na_{1k_1}a_{2k_2}\ldots a_{nk_n}\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma b_{k_1\sigma(1)}b_{k_2\sigma(2)}\ldots b_{k_n\sigma(n)}= $$

Последняя сумма $\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma b_{k_1\sigma(1)}b_{k_2\sigma(2)}\ldots b_{k_n\sigma(n)}$ равна нулю, если среди индексов $k_1,k_2,\ldots, k_n$ есть повторяющиеся, так как это определитель, у которого две строки равны. Поэтому мы пожем продолжить так:

$$ \ldots =\sum\limits_{\tau\in S_n}a_{1\tau(1)}a_{2\tau(2)}\ldots a_{n\tau(n)}\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma b_{\tau(1)\sigma(1)}b_{\tau(2)\sigma(2)}\ldots b_{\tau(n)\sigma(n)}= $$

$$ =\sum\limits_{\tau\in S_n}a_{1\tau(1)}a_{2\tau(2)}\ldots a_{n\tau(n)}\sum\limits_{\sigma\in S_n}\operatorname {sgn}\sigma b_{1\sigma\tau^{-1}(1))}b_{2\sigma\tau^{-1}(2)}\ldots b_{n\sigma\tau^{-1}(n)}= $$

$$ =\sum\limits_{\tau\in S_n}\operatorname {sgn}\tau a_{1\tau(1)}a_{2\tau(2)}\ldots a_{n\tau(n)}\sum\limits_{\sigma\in S_n}\operatorname {sgn}(\sigma\tau^{-1}) b_{1\sigma\tau^{-1}(1))}b_{2\sigma\tau^{-1}(2)}\ldots b_{n\sigma\tau^{-1}(n)}=\det A\det B $$

-- Пн мар 27, 2023 22:30:28 --

EminentVictorians в сообщении #1587018 писал(а):

Хотя сложно считать всю эту теорию тривиальной.

По-моему все тривиально. Ну, вот, например, я использовал правило

$$ \prod\limits_{p=1}^n\sum_{k_p=1}^n a_{pk_p}=\sum_{k_1,\ldots,k_p=1}^n \prod_{p=1}^n a_{pk_p}, $$

которое по-человечески означает раскрытие скобок по правилу "каждое слагаемое на каждое слагаемое"

[EminentVictorians]

Padawan в сообщении #1587049 писал(а):

По-моему все тривиально. Ну, вот, например, я использовал правило

$$ \prod\limits_{p=1}^n\sum_{k_p=1}^n a_{pk_p}=\sum_{k_1,\ldots,k_p=1}^n \prod_{p=1}^n a_{pk_p}, $$

которое по-человечески означает раскрытие скобок по правилу "каждое слагаемое на каждое слагаемое"

Просто меня напрягает, что всегда в таких случаях я сначала пишу строчку вида $(a_{11} + ... + a_{1n}) \cdot ... \cdot (a_{n1} + ... + a_{nn})$ и потом подгоняю обозначения с $\prod\limits_{}$ и $\sum_{}$ под нее. А хочется работать сразу на уровне нотации с $\prod\limits_{}$ и $\sum_{}$. Чтобы вообще не представлять, что скрывается за преобразованиями, а тупо механически их делать.

Допустим я даже запомню эту формулу. Но ведь она, скажем так, "рафинированная". В реальности могут быть разные пределы суммирования, не "однобуквенные" индексы (а какие-нибудь сложные индексирующие функции). И я буду тупо сначала раскладывать такую формулу в формулу с многоточиями, потом держать в уме всю эту кучу явных преобразований, подстановок и т.д., а потом переводить обратно в запись с $\prod\limits_{}$ и $\sum_{}$. По-моему, это мазохизм.

Я тут подумал, а нельзя ли спуститься на 1-2 уровня вниз и превратиться в симулятор компилятора, который будет мыслить в категориях: "здесь сделаем подстановку, здесь переименуем букву" и т.д? Чтобы было максимально "формально-синтаксически". Да, строчки станут длиннее, ну и ладно. Зато появится вот этот "механический" стиль, который мне нужен. Я хочу не мучаться с нотацией, а пользоваться ее преимуществами (пусть и в ущерб компактности записей). Явно ведь я не первый, у кого такое желание возникло.

[Padawan]

EminentVictorians в сообщении #1587087 писал(а):

И я буду тупо сначала раскладывать такую формулу в формулу с многоточиями, потом держать в уме всю эту кучу явных преобразований, подстановок и т.д., а потом переводить обратно в запись с $\prod\limits_{}$ и $\sum_{}$.

Я так и делал. Потом уже можно переписать все со значками суммы и произведения без многоточия. Будет короче, но не читаемо, на мой взгляд. Хотя... Перепишие, то, что я написал, полностью без многоточия.

[EminentVictorians]

Padawan в сообщении #1587093 писал(а):

Я так и делал.

Вот мой тэйк как раз в том, что это плохо. Не знаю, согласитесь Вы со мной или нет, но я вот так считаю.

[Padawan]

EminentVictorians
Перепешите мои выкладки без многоточий, не поленитесь. Хочу посмотреть, насколько они останутся читаемыми. Возможно, не всё так плохо и я зря испугался. Просто действительно нет навыка оперирования. Ещё можно нотацию Эйнштейна вспомнить, и, возможно, распространить её и на произведения.

-- Вт мар 28, 2023 00:56:41 --

Padawan в сообщении #1587049 писал(а):

Ну, вот, например, я использовал правило

$$ \prod\limits_{p=1}^n\sum_{k_p=1}^n a_{pk_p}=\sum_{k_1,\ldots,k_n=1}^n \prod_{p=1}^n a_{pk_p}, $$

Это правило можно так переписать:

$$ \prod_{p=1}^n\sum_{k=1}^na_{pk}=\sum\limits_{\tau\in M_n}\prod_{p=1}^n a_{p\tau(p) }, $$

где $M_n$ -- множество всех отображений из $\{1, \ldots, n\}$ в $\{1, \ldots, n\}$.