Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Categories:

Симметричные функции.

Из серии «математические игры».

Disclamer: Эти рассказы не претендуют на уровень исследований. Это просто рассказы о том, как я заметил когда-то давно закономерность и "поиграл" с ней.

Когда не было калькуляторов, все пользовались для умножения логарифмическими линейками. Исходный принцип этого метода крайне прост: чтобы посчитать произведение чисел a и b, можно посчитать их логарифмы — ln(a) и ln(b), сложить и узнать, логарифмом какого числа является результат.
    ab = exp(ln(a) + ln(b))
или наоборот:
    a + b = ln( exp(a) + exp(b) )

Когда я узнал об этом замечательном факте, мне сразу пришла в голову мысль: а не может ли быть так, что любые "достаточно благоразумные" симметричные функции можно выразить через сумму или произведение? Пусть s(x,y) = s(y,x), тогда существуют такие функции перехода f и g, что
    s(x,y) = f( g(x) + g(y) )
или соотв.
    s(x,y) = f( g(x) · g(y) )

А может, чего доброго, это работает не только для сложения-умножения, я для любой симметричной функции вообще? Т.е. между двумя любыми симметричными функциями n аргументов существуют переходные функции. Пусть у нас есть две n-аргументных симметричных ф-ции. Первую будем обозначать a * b * ··· * d, вторую обозначим a × b × ··· × d. (Это не имеет сейчас никакой связи с умножением, просто обозначения.) Если эти функции удовлетворяют определённым условиям "благоразумности", которые мы найдём позже, то существуют функции f и g, такие, что:
    a * b * ··· * d = g( f(a) × f(b) × ··· × f(d) )

Вначале посмотрим, как обстоят дела с натуральными числами.
Попытаемся представить произвольную симметричную функцию n аргументов через сумму.

Если функция симметрична, значит ей не нужно знать, в каком порядке шли её аргументы. Ей нужно только знать, какие числа среди них содержались и в каком количестве.
s(1,2,2) можно посчитать, зная только что среди аргументов была одна единица и две двойки. Объект, хранящий информацию о содерщащихся в нём объектах и их количестве называется мультимножеством. Будем обозначать мультимножество, получаемое из последовательности (1,2,2) символом [1,2,2]. Пока что мы вывели следующее правило: функция s(x,y,z) тогда и только тогда симметрична, когда существует функция S: S[x,y,z] = s(x,y,z).

Любой человек, хоть раз програмировавший, знает, что еденицами и нулями (точнее, их последовательностями) можно закодировать почти всё, что угодно. :-) Уж конечные мультимножества — точно. Вот мы и попробуем. Пусть функция k кодирует мультимножества натуральными числами, а K их декодирует. Вот бы здорово было, если бы k[a] + k[b] + k[c] = k[a, b, c]! Тогда решение было бы у нас в кармане.
    s(x,y,z) = S[x,y,z] = S°K°k[x,y,z] = S°K(k[x] + k[y] + k[z])

Вот мы и выразили симметричную функцию через сумму!
Осталось только найти нужную функцию K, но это как раз очень просто. Для n-аргументной функции будем кодировать k[x] как (n+1)^x. Если рассматривать запись этого числа в (n+1)-ичной системе счисления, это будет единица на x-той позиции. Складывая k[x] и k[y] получаем единицу в x-той и единицу в y-позиции, либо двойку в x-той позиции, если числа равны. Таким образом, из полученной суммы всегда можно восстановить информацию, какие числа в нашем мультимножестве содержатся и в каком количестве. Ичность системы счисления — (n+1) — гарантирует, что не случится перескока в высший разряд. У нашей функции же всего n-аргументов. Даже если все они будут одинаковыми, мы получим всего лишь цифру n в соответствующем разряде.

Для выражения через умножение можно кодировать простыми числами. k[x] = p_x (x-тое простое число). При умножение степени разны простых чисел не интерферируют, а одинаковых — складываются. Так что, мы сможем добыть из произведения информацию обо всех числах, которые в него входили.

Обратим внимание, что наш чудный метод работает не только для натуральных чисел, но вообще для всех счётных множеств, содержащих таковые. Чтобы показать это, нужно просто добавить в k дополнительный этап кодирования, преобразующий x в натуральное число. В часности, наш результат верен для рациональных чисел. Если наша функция отображает из рациональных чисел в действительные, это всё-равно работает! Действительно, мы нигде не говорили о том, куда функция отображает, нас интересовало только то, откуда. Этот факт может помочь нам при изучении непрерывных симметричных функций, ведь каждая непрерывная функция однозначно задаётся своим ограничением на рациональные числа.

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

А раз базис Гимеля имеет ту же мощность, что и сами действительные числа, значит существует биекция между ними. Вот и будем кодировать каждое действительное число соответствующим ему вектором в базисе. При суммировании компоненты разных базисных векторов не интерферируют, а одинаковых — складываются. При раскодировании будем просто смотреть на соответствующую компоненту: если там единичка, значит данное действительное число один раз было среди аргументов. Если двоечка — два раза, etc.

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

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

Короче говоря, нам нужно найти такую систему кодирования, которая бы «проводила всю нужную информацию» не только через оператор сложения, но через любую симметричную функцию. Каким условиям должна удовлетворять эта функция? Давайте рассмотрим несколько примеров.

Пусть наша функция — константа. Вполне симметрично. Разумеется, никакой информации об аргументах из результата не добудешь. Значит, одно условие уже есть. Множество значений должно совпадать по мощности с областью определения. (Будем называть такие множества множествами максимальной мощности.)

Возьмём функцию max, находящую максимум n своих аргументов. Из результата этой бяки можно выковырять информацию лишь об одном аргументе. Бяка. Нам так не пойдёт.

Попробуем сформулировать, чего нам нужно. Мы можем как угодно симметрично трансформировать аргументы. Т.е. можем позаботиться о том, чтобы каждый из аргументов лежал в неком подмножестве X области определения, совпадающем с ней по мощности. (Большего мы сделать, вроде бы, не можем) Позаботившись об этом, мы хотим, чтобы из функции можно было выковырять информацию о каждом аргументе, вне зависимости от других. Итак, нам нужно, чтобы:
    Существовало такое множество X максимальной мощности, чтобы s была на множестве X^n инъективна в первом аргументе. Из инъективности в первом аргументе следует инъективность в каждом. Кроме того, раз s инъективна на множестве максимальной мощности, значит множество её значений тоже имеет максимальную мощность.
(Для суммы множество X — все натуральные/действительные числа. Для произведения — все натуральные/действительные числа больше нуля.)

Теперь нам нужно выделить среди множества X множество максимальной мощности Y, разные числа из которого в нашей функции не интерферируют.
(Для суммы это были числа вида (n+1)^x / базис Гимеля, для произведения — простые числа / экспоненты базиса Гимеля)

Начнём, как всегда, с натуральных чисел. Построим это множество Y одновременно с кодирующей функцией f и декодирующей функцией g так, чтобы
    g°s(f(x), f(y), ..., f(z)) = x + y + ··· + z

1. Вначале занумеруем множество X_0 = X при помощи функции f: NN -> X. Обозначим обратную ей функцию через F.
2. Зададим g°s(x, y, .., z) = 0 для всех (x, y, .., z) таких, что F(x) + F(y) + ··· + F(z) = 0
3. Теперь найдём множество всех таких (x, y, ... z), для которых
    s(x, y, ... z) = s{(x, y, .., z) | F(x) + F(y) + ··· + F(z) = 0}, но F(x) + F(y) + ··· + F(z) =/= 0.
4. Вычтем это множество из X_0 и поправим нумерацию. Получившееся множество X_1, разумеется, осталось счётным множеством, иначе инъективность в первом аргументе была бы не выполнена.

Мы добились того, что единственными элементами, для которых g°s(x, y, ... z) = 0 являются такие, для которых F(x) + F(y) + ··· + F(z) = 0.

Повторим все действия, начиная с шага 1, заменяя 0 на 1, 2, 3, ... и получая таким образом множества X_1, X_2, ... Их бесконечное пересечение назовём Y. Учитывая, что элемент f(0) совпадает во всех множествах X_n, f(1) во всех, начиная c X_1 и так далее, очевидно, что Y счётно и пронумерованно функцией f, выполняющей вышестоящее соотношение:
    g°s(x, y, ... z) = a <=> F(x) + F(y) + ··· + F(z) = a
или
    g°s(f(x), f(y), ..., f(z)) = x + y + ··· + z

Ура! Мы выразили сумму через нашу почти произвольную симметричную функцию s.
Теперь мы можем выразить через неё любую симметричную функцию w, скомбинировав две выведенные формулы:
    w(x, y, z) = W[x,y,z] = W°K°k[x,y,z] = W°K(k[x] + k[y] + k[z])
    = W°K°g°s(f°k[x], f°k[y], f°k[z])

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

А вот куда более интересная штука. Если s — симметричная непрерывно-дифференцируемая функция на RR^n, то мы можем выразить её через сумму, причём функции перехода будут тоже непрерывно-дифференцируемы. Идея доказательства:
    Функцию с непрерывной и всюду ненулевой производной всегда можно трансформировать в такую, у которой производная всегда будет единицой. (Натуральная параметризация.) Кажется, во многомерном случае, этого тоже можно добиться. Т.е. найти такие трансформационные функции, что D(f°s°g) = id. Функции перехода тоже получатся непрерывно-дифференцируемые.

Раз f°s°g непрерывно-дифференцируема, значит интеграл её дифференциала по некоторому пути будет равен разности на конечных значениях. Другими словами, значение f°s°g в точке p = (x, y, z) можно посчитать как сумму f°s°g(0) и интеграла Ds по некоторой кривой, соединяющей 0 и p. Самая лучшая кривая — путь по ребрам координатного паралеллипипеда p. Раз у нас D(f°s°g) = id, это будет просто сумма координат. Остаётся только показать, что существует k, такая что g(x,y,z) = k(x) + k(y) + k(z). Этого, кажется, несложно достичь по построению.
Subscribe

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments