Очевидность

Аватар пользователя
Ian
Сообщений: 685
Зарегистрирован: 18 янв 2016, 19:42

Очевидность

Сообщение Ian » 06 сен 2020, 18:16

Пусть [math] -n-е простое число, p(1)=2 и т.д.
Доказать, что не существует действительных чисел [math], чтобы
[math] сразу для всех n?
Учебная задачка по алгебре

zykov
Сообщений: 1004
Зарегистрирован: 06 янв 2016, 17:41

Очевидность

Сообщение zykov » 07 сен 2020, 06:54

Не знаю, какое доказательство в рамках алгебры они имели ввиду. Может что-то про делимость.
Но оно и так из асимптотики очевидно.
Как известно, $p(n)$ имеет асимптотику $n \log n$.
А последовательность заданная линейной рекурсией будет либо ограниченной, либо расти экспоненциально.
Там зависит от максимального по модулю собственного значения матрицы.
Если модуль меньше $1$, то всё к нулю стремится. Если равен $1$, то будет как-то скакать, но будет ограниченной.
Если больше $1$, то будет расти, так что супремум можно снизу какой-то экспонентой ограничить.

Аватар пользователя
Ian
Сообщений: 685
Зарегистрирован: 18 янв 2016, 19:42

Очевидность

Сообщение Ian » 07 сен 2020, 08:53

zykov писал(а):Не знаю, какое доказательство в рамках алгебры они имели ввиду. Может что-то про делимость.

Действительно, для всякого р последовательность имеет ровно одно число, делящееся на р, но это ни к какому противоречию не приводит
Задачник Шишкова А.Б.(МИРЭА,2013), задача 7.1(л)
Кем-то доказано, что скорость вычисления n-го простого числа не ниже экспоненциальной от n. А скорость вычисления очередного члена ЛРП линейная.

peregoudov
Сообщений: 523
Зарегистрирован: 29 дек 2015, 13:17

Очевидность

Сообщение peregoudov » 07 сен 2020, 11:55

zykov писал(а):Source of the post А последовательность заданная линейной рекурсией будет либо ограниченной, либо расти экспоненциально.
Там зависит от максимального по модулю собственного значения матрицы.
Мне кажется, все так просто лишь для невырожденных собственных значений. А в случае вырожденных возможности побогаче. К тому же вместе с собственными векторами могут понадобится и присоединенные. Я когда-то разбирался с системой линейных дифференциальных уравнений первого порядка с постоянными коэффициентами, только быстро не найду эту бумажку.

zykov
Сообщений: 1004
Зарегистрирован: 06 янв 2016, 17:41

Очевидность

Сообщение zykov » 08 сен 2020, 09:33

Да, там есть некоторые отличия. Но асимптотики $n \log n$ всё равно не будет.
Вот возьмем одну Жорданову клетку размера $n$. Она имеет вид $J = \lambda E + N$.
Матрица $N$ имеет единицы на второй диагонали сверху, в других местах нули. Это нильпотентная матрица - $N^n = 0$.
Т.к. матрицы $E$ и $N$ коммутируют, то $J^m$ выражается в виде бинома Ньютона. При этом степени $N$ от $n$ и выше зануляются. Т.е. будут только первые $n$ слагаемых (от $0$ до $n-1$). Сами биномиальные коэффициенты растут полиномиально.
Если модуль $\lambda$ больше единицы, то всё равно асимптотика супремума не менее экспоненциальной.
Если модуль $\lambda$ меньше единицы, то экспоненциальное убывание всё равно забъет полином.
Если модуль $\lambda$ равен единице, то может быть полиномиальный рост за счёт биномиальных коэффициентов. Но $n \log n$ быть не может. Оно либо ограничивается линейно сверху, либо квадратично снизу.

zykov
Сообщений: 1004
Зарегистрирован: 06 янв 2016, 17:41

Очевидность

Сообщение zykov » 08 сен 2020, 09:41

zykov писал(а):Source of the post Вот возьмем одну Жорданову клетку размера $n$. Она имеет вид $J = \lambda E + N$.

Да, любая матрица представляется в Жордановой форме (соответствующим выбором базиса), т.е. представляется в виде $M = D + N$, где $D$ диагональна, $N$ нильпотентна, $D$ и $N$ коммутируют. Т.е. $M^m$ представляется в виде обрезанного бинома Ньютона с фиксированным (независящим от $m$) количеством слагаемых.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 6 гостей