2014 dxdy logo

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

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




 
 Ширина ЧУМ делителей числа n
Сообщение17.03.2009, 22:03 
Аватара пользователя
Найти верхнюю и нижнюю границу ширины $d$ частично упорядоченного множества $<D(n),|>$ делителей числа $n$ (ширина ЧУМ --- длина максимальной антицепи в графе ЧУМ).
Пример: $d(36)=3$.

Мои выкладки. Пусть разложение числа $n$ на простые числа имеет вид $n=p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m}$. Тогда
$d(n)=$
\begin{cases}
$\min\{k_1,k_2,\ldots,k_m\}+1, \,&m>1\\$
$1,\,&m=1$
\end{cases}
Что делать дальше для проведения оценки?

 
 
 
 
Сообщение17.03.2009, 22:38 
Аватара пользователя
А нужно именно получить оценку как функцию от $n$?
Эта величина сильно скачет туда-сюда, можно попробовать через какие-нибудь теоретико-числовые функции.
Скажем, можно использовать, что для ЧУМ произведение ширины и высоты не больше мощности, а высоту решетки делителей можно оценить сверху двоичным логарифмом.

 
 
 
 
Сообщение17.03.2009, 22:52 
$d(n)\geq C_m^{[m/2]}$
$d(n_1n_2)\geq d(n_1)d(n_2), gcd(n_1,n_2)=1$

Сверху можно ограничивать используя теорему Дилуорса. Например
$d(n)\leq 2^md(n/(p_1p_2...p_m))$
$d(n_1n_2)\leq min(a(n_1)d(n_2),a(n_2)d(n_1)), gcd(n_1,n_2)=1, a(n) - $ кол-во всех делителей.

 
 
 
 
Сообщение18.03.2009, 20:00 
Аватара пользователя
Dandan в сообщении #196077 писал(а):
$d(n_1n_2)\geq d(n_1)d(n_2), gcd(n_1,n_2)=1$

Что такое 'gcd"?

 
 
 
 
Сообщение18.03.2009, 20:11 
Аватара пользователя
AndreyXYZ в сообщении #196401 писал(а):
Что такое 'gcd"?

НОД. Greatest common divisor.

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


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