2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Максимальный порядок элемента группы подстановок
Сообщение05.08.2010, 16:15 
Аватара пользователя
Задача следующая:
Доказать, что порядок любого элемента группы S_n не превосходит e^{n/e}\approx 1.44^n

Двигаюсь в следующем направлении: если подстановка \sigma разлагается в произведение независимых циклов длин p_1,p_2,...,p_n, то ord(\sigma)=LCM\{p_1,p_2,...,p_n\} (LCM - наименьшее общее кратное). Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально. Далее, как известно, число таких целых чисел k, что 0<k\le n, (k,n)=1 - это функция Эйлера \varphi(n) и она вычисляется так: \varphi(n)=n\displaystyle\prod_{p}(1-\frac{1}{p}), где p - все простые делители n. В таком случае \displaystyle\prod_{p}(1-\frac{1}{p})<\displaystyle\lim_{n\to \infty}(1-\frac{1}{n})^n=\frac{1}{e}. Т.о. наибольшее возможное число циклов, на которые разлагается подстановка, равно n/e; Если мы перемножим наибольшую возможную длину цикла n/e число раз (возведем в степень n/e), то мы получим наибольший возможный порядок подстановки \sigma.

Вот тут я застрял - судя по условию задачи, наибольшая возможная длина цикла равна e (а такого не может быть), не могу дотумкать, что здесь не так?
Заранее благодарен за любые идеи!

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение05.08.2010, 17:00 
Аватара пользователя
А, функция Ландау, да-да. Короче так. Ваши рассуждения о взаимно простых циклах остроумны и красивы (и даже дают это чёртово n/e), но не имеют отношения к делу. Проще надо, гораздо проще. Наибольшая длина цикла, очевидно, равна n; но такой цикл получится всего один. А если попробовать два, три...

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 12:50 
Аватара пользователя
JMH в сообщении #342727 писал(а):
Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально.

Это ещё почему?

Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text{НОК}(2,31) = 62$. С другой стороны, $33 = 9 + 24$ и $\text{НОК}(9,24) = 72 > 62$. Однако в первом случае берётся разложение $n$ на взаимно-простые слагаемые, а во втором --- нет.

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 20:35 
Аватара пользователя
Профессор Снэйп в сообщении #342897 писал(а):
Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text{НОК}(2,31) = 62$. С другой стороны, $33 = 9 + 24$ и $\text{НОК}(9,24) = 72 > 62$. Однако в первом случае берётся разложение $n$ на взаимно-простые слагаемые, а во втором --- нет.

Вы правы и это еще один гвоздь в крышку гроба моей попытки решения :-) Я все пытаюсь сообразить в чем состоит суть подсказки ИСН: ясно что нужно искать максимальное НОК разбиения множества n, но в голову приходит только самая грубая оценка $n!\approx n*ln (n)$; как получить $e^{n/e}$ догадаться не получается :-(

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 21:30 
Аватара пользователя
JMH в сообщении #342993 писал(а):
все пытаюсь сообразить в чем состоит суть подсказки ИСН...

Да он очень простую вещь предлагает:

$$
\begin{array}{c}
\text{Максимальный порядок} = \\ \max\limits_{k \in \mathbb{N}} \max \{ \text{НОК}(x_1,\ldots, x_k) : x_1, \ldots, x_k \in \mathbb{N},\, x_1 + \ldots + x_k = n \} \leqslant \\
\max\limits_{k \in \mathbb{N}} \max \{ x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb{N},\, x_1 + \ldots + x_k = n \} \leqslant \\
\max\limits_{k \in \mathbb{N}} \max \{ x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb{R},\, x_1, \ldots, x_k > 0,\, x_1 + \ldots + x_k = n \} = \\
\max\limits_{k \in \mathbb{N}} \left( \frac{n}{k} \right)^k \leqslant \max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}}
\end{array}
$$
Спрашивайте, если что-то вдруг непонятно :-)

-- Сб авг 07, 2010 00:39:49 --

Кстати, понятно, что
$$
\lim\limits_{n \to \infty} \frac{\text{Максимальный порядок}}{e^{n/e}} = 1
$$
Так что оценка в пределе точна.

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 21:49 
Профессор Снэйп в сообщении #343008 писал(а):
Кстати, понятно, что
$$
\lim\limits_{n \to \infty} \frac{\text{Максимальный порядок}}{e^{n/e}} = 1
$$
Так что оценка в пределе точна.


А это почему можно спросить?

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 21:59 
Аватара пользователя
Будьте добры, вот этот момент поясните пожалуйста: $\max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}$

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение06.08.2010, 23:26 
Аватара пользователя
JMH в сообщении #343013 писал(а):
Будьте добры, вот этот момент поясните пожалуйста

Дифференцируете по $k$, приравниваете производную к нулю, находите максимум...

mihailm в сообщении #343011 писал(а):
А это почему можно спросить?

Возможно, я поспешил с этим пределом :-(

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение07.08.2010, 04:00 
Аватара пользователя
Профессор Снэйп в сообщении #343028 писал(а):
JMH в сообщении #343013 писал(а):
Будьте добры, вот этот момент поясните пожалуйста: $\max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}$

Дифференцируете по $k$, приравниваете производную к нулю, находите максимум...

Не получается: $\left[\left(\frac{n}{x}\right)^x\right]'=-\frac{n}{x^2}\left(\frac{n}{x}\right)^x ln \frac{n}{x}$
Приравниваем к нулю и потенциируем: $x=ne^{-\frac{n}{x^2}\left(\frac{n}{x}\right)^x}$
и что дальше? $e^{\frac{n}{e}$ не видать, может вечер пятницы виноват?

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение07.08.2010, 04:33 
Аватара пользователя
JMH в сообщении #343058 писал(а):
Не получается: $\left[\left(\frac{n}{x}\right)^x\right]'=-\frac{n}{x^2}\left(\frac{n}{x}\right)^x ln \frac{n}{x}$
Приравниваем к нулю и потенциируем: $x=ne^{-\frac{n}{x^2}\left(\frac{n}{x}\right)^x}$
и что дальше? $e^{\frac{n}{e}$ не видать, может вечер пятницы виноват?

???

$$
\frac{d}{dx} \left( \frac{n}{x} \right)^x = \frac{d}{dx} e^{x \ln \frac{n}{x}} = e^{x \ln \frac{n}{x}} \left(\ln \frac{n}{x} + x \cdot \frac{x}{n} \cdot \frac{-n}{x^2} \right)
$$
Приравниваем к нулю содержимое скобки, получаем $\ln (n/x) = 1$, $n/x = e$ и $x = n/e$.

А у Вас производная неправильно вычислена :-)

 
 
 
 Re: Максимальный порядок элемента группы подстановок
Сообщение07.08.2010, 05:01 
Аватара пользователя
М-да. Спасибо Вам большое! А у меня, видать, совсем мозги заржавели...

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group