2014 dxdy logo

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

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




 
 Задача из теории чисел (асимптотическое поведение...)
Сообщение28.11.2006, 01:22 
Аватара пользователя
Помогитье пожалуйста с решением такой задачи.
Пусть
$ f(n) = \Sigma_{d | n}\mu(d)2^{n/d}$
$ r(n) = \Sigma_{d | n}\frac{f(d)}{d}$
где $\mu(d)$ - функция Мебиуса.
Необходимо найти $\lim_{n \rightarrow \infty}(\frac{r(n)}{2^n})$
На компьютере я нашел, что отношение $\frac{r(n)}{2^n}$ очень быстро стремится к нулю. Но как это доказать строго я не знаю.

 
 
 
 
Сообщение28.11.2006, 04:04 
Аватара пользователя
Замечу, что задача имеет вероятностный смысл, поскольку $\frac{f(n)}n$ - количество нормированных(со старшим коэффициентом 1) неприводимых многочленов степени $n$ над полем $\mathbb{F}_2$ из 2 элементов. Поэтому $r(n)$ - количество нормированных многочленов степени $n$, являющихся степенью неприводимого, в то время как $2^n$ - количество всех нормированных многочленов степени $n$.
По поводу док-ва.
Из определения $f(n)$ легко вывести, что $f(n)>0$. Формула обращения Мёбиуса дает $2^n=\sum\limits_{d|n}f(d)$, откуда $f(n)\leqslant2^n$.

Edit: На самом деле из определения $f(n)$ видно, что $f(n)=2^n+O(2^{\frac n2})$ и этого достаточно для дальнейшего.

Поэтому
$$r(n)\leqslant\sum_{d|n}\frac{2^d}d=\underline{\underline{\mathrm{O}}}(\frac{2^n}n).$$
На самом деле $r(n)\sim \frac{2^n}n$, если я нигде не наврал.

 
 
 
 
Сообщение28.11.2006, 18:29 
Аватара пользователя
Спасибо ! :D

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


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