по следам перестановочного неравенства

[Утундрий]

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

[mihiv]

Maxal
Вы не могли бы привести пример подстановок, на которых достигается минимум при $n=7$?

[VAL]

mihiv писал(а):

Maxal
Вы не могли бы привести пример подстановок, на которых достигается минимум при $n=7$?

Хоть я и не Maxal, но пример вот:
$(1 2 3 4 5 6 7)$
$(5 4 6 3 2 7 1)$
$(7 5 2 3 4 1 6)$

Добавлено спустя 14 минут 29 секунд:

Re: по следам перестановочного неравенства

maxal писал(а):

Пусть $S_n$ - это множество всех перестановок чисел $\{1,2,\dots,n\}$.
Найдите значение

$$\min_{\pi,\sigma,\tau\in S_n} \sum_{j=1}^n \pi(j)\cdot \sigma(j)\cdot\tau(j)$$

как функцию от $n$.

Очевидная оценка снизу задается формулой $ceil(n \cdot n!^{\frac3n})$
Интересно, что для всех проверенных $n$ (до 7) оценка получается точной.

[Руст]

VAL писал(а):

Очевидная оценка снизу задается формулой $ceil(n \cdot n!^{\frac3n})$
Интересно, что для всех проверенных $n$ (до 7) оценка получается точной.

Эта оценка, среднего арифметического члеов произведений по сравнению с их средним геометрическим действительно интересна. Но при больших n не будет точной. Интересно найти действительную константу а, для которого $S_{min}(n)=an^4(1+o(1))$. Нижняя оценка (от VAL) $a=e^{-3}$, у меня получилось верхняя $a=\frac{19}{324}$.

[Руст]

Вот как достигается $a=\frac{1}{18}$.
Объединим в тройки $(1,n-1,n),(2,n-3,n-2),...$, которые будут встречаться трижды. Когда $n=3k+1$ останется тройка (k+1,k+1,k+1), когда $n=3k+2$ останутся тройки (k+1,k+2,k+1) дважды. Соответственно определим $\pi(i)=n-2i+1,\pi(n-2i+1)=n-2i+2,\pi(n-2i+2)=i,i\le [n/3]$, когда $n=3k+1$ определим $\pi(k+1)=k+1$, когда $n=3k+2$ $\pi(k+1)=k+2,\pi(k+2)=k+1$, другая перестановка $\sigma(i)=\pi^2(i),\tau(i)=i$.
При этом, в случае $n=3k$ получаем

$$S=3\sum_{i=1}^k(n+1-2i)(n+2-2i)i=\frac{k(k+1)}{2}[3n(n+2)-(4n+6)(2k+1)+6k(k+1)]=\frac{n^2(n+3)^2}{18}$$

,
в случпе $n=3k+1$ $S=\frac{k(k+1)}{2}[9k^2+19k+8]+(k+1)^3$,
в случае $n=3k+2$ $S=\frac{k(k+1)}{2}[9k^2+24k+22]+2(k+1)^2(k+2)$.

[Утундрий]

Люблю я такие темы. Полезно иной раз ощутить себя полным нулем. Это стимулирует )

P.S. Посоветуйте что нибудь почитать такого, чтобы после прочтения оного можно было понять хотя бы часть написанного Рустом )

[Sonic86]

Есть такой алгоритм локальной оптимизации. Для
$S = \sum\limits_{j=1}^n \pi _j \sigma _j \tau _j$ и $S' = \sum\limits_{j=1}^n \pi '_j \sigma '_j \tau '_j$, где $(\forall j) \pi _j = \pi '_j, \sigma _j = \sigma '_j, \tau _j = \tau '_j$, кроме двух индексов $i,k$, для которых $\sigma '_i = \sigma _k, \sigma '_k = \sigma _i$.
Тогда $S' <S$ равносильно $sign(\pi _i \pi _k - \tau _i \tau _k) = - sign (\sigma _i - \sigma _k)$. Используя это свойство, можно брать некоторую $(\pi , \sigma , \tau)$ с ее $S$ и строить $(\pi ', \sigma ', \tau ')$ $S': S' <S$ и заходить в локальные максимумы. И запрограммировать легко.
Логичный вопрос: много ли локальных минимумов для $S_n$ и различаются ли значения в них?
Даже уже для $n=4$ есть несколько локальных минимумов и с разными значениями.

[Руст]

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

[Sonic86]

Лучше такой алгоритм (модификация предыдущего).
Если надо минимизировать сумму $\sum\limits_{j=1}^n \tau_1(j)...\tau_m(j)$, где $\tau_i \in S_n$, то пишите матрицу $(\tau_i(j))$ из этих перестановок, далее цикл: выбираете $i$ и вычисляете еще строку $p(j)=\frac{\prod\limits_{i=1}^m \tau_i(j)}{\tau_i(j)}$, после чего числа $\tau_i(j), j=1..n$ сортируете в порядке, противоположном порядку $p(j)$. И так последовательно для всех строк (возможно несколько раз). Цикл прекращается, когда для всех $i$ $\tau_i$ уже не изменяются.
Для пространства величиной порядка $n!^m$ алгоритм довольно быстро загоняет сумму в локальный минимум. Опять же легко программируется. Причем очень много локальных минимумов, которые одновременно являются и глобальными. В то же время, чем меньше делителей имеет $n$, тем, скорее всего, больше шагов до локального минимума и меньше глобальных минимумов. Точнее не могу сказать.
Для $m=3$ (наш случай) у меня получилось $S(n)=1; 6; 18; 44; 89; 162; 271$. Проверьте, пожалуйста.

[maxal]

Sonic86
см. A070735

С практической точки зрения представляет интерес вычисление этой функции для $n>15$.

[Руст]

Можно посчитать наилучшую асимптотику. Пусть наименьшее k пробегает снизу шагом 1, средний шагает сверху с шагом h(k), а наибольшее шагает подряд сверху минуя только значения, где был средний. Тогда для h(k) должно выполняться
(1)

$$\sum_{i=1}^k h(k) \ge 2k.$$

Соответственно
(2)

$$\tau(i)=i,\sigma(k)=n+1-\sum_{i=1}^k h(k), \pi(k)= max (a), a<\pi(k-1),a\not =\sigma (j).$$

После выбора значений $\sigma(k),\pi (k)$, выбираем $\pi(k+1)$ согласно (2), а $\sigma(k+1)$ выбираем из условия (2) и так, чтобы число $\sigma(k+1)$ ближайшее целое к

$$\frac{1}{(k+1)\pi(k+1)}(\frac{n!}{\prod_{i=1}^k i\sigma(i)\pi(i)})^{\frac{3}{n-k}}.$$

Тогда получится асимптотический наименьшая сумма, которую можно ещё уменьшить только разбивая тройки, но главный коэффициент a перед $n^4$ не изменится.
Этот коэффициент вычисляется следующем образом. Вначале вычислим b из
$\frac{1-2b}{b}=e^{3-9b},b<1/3$. Получается $b=0,0945..$. Тогда наилучшее а находится из

$$a=(1-3b)b(1-2b)^2+3\int_0^b x(1-2x)^2dx=0.0548<1./18.$$

[Dandan]

Sonic86 писал(а):

Для $m=3$ (наш случай) у меня получилось $S(n)=1; 6; 18; 44; 89; 162; 271$. Проверьте, пожалуйста.

Абсолютный минимум (и сами перестановки) можно посчитать простым алгоритмом перебора со сложностью $n!\cdot n \rm{log} n$ - перебираем $\pi$, умножаем на (1,2,\ldots,n), сортируем, умножаем на (n,n-1,\ldots,1). Вплоть до $n=11$ считается довольно быстро. Думаю, если оптимизировать, то вполне можно и для $n=16$ посчитать ... на кластере ))

Добавлено спустя 7 минут 16 секунд:

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

[Sonic86]

Dandan! Может на компе и быстрее, но $n!$ перебирать в принципе не вариант.
Я пока в Excele смог найти (но за точность не ручаюсь):
$S(n) = 1; 6; 18; 44; 89; 162; 271; 428; 643; 931; 1304; 1781$ - первые 12 чисел. По ссылке у maxal там их 15, но я решил себя проверить. Вот у меня даже для $n=12$ требуется сделать только 10 сортировок, а не 10! и вообще я делал 5-6 испытаний на каждое $n$. Придется все же студию поставить и прогу написать - много времени уходит.

Добавлено спустя 3 минуты 59 секунд:

Ага! Ну вот: 2 ошибки.
maxal! Что Вы имели ввиду под "практической значимостью"?!

[Руст]

Реализовал вышеуказанный алгоритм с наименьшем а. Даже без дополнительной оптимизации результаты почти оптимальные. В особенности в случае $n=3k$. Здесь единственное отличие при $n=12$ по указанному алгоритму $S=1782$ а в таблице $S=1781$.
Для ориентировки этот алгоритм дает $n=18,S=7842,n=21,S=13938$.

[maxal]

Sonic86 в сообщении #189792 писал(а):

Что Вы имели ввиду под "практической значимостью"?!

Практическая значимость - пополнить A070735 новыми значениями.