ВТФ и дискретная геометрия

[AN]

Есть новый результат - способ решения многочленов без всяких радикалов, только векторы и операторы. Всё просто и красиво. Вкратце так:
1. Многочлену (напоминаю - кори натуральны и различны) степени n сопоставляется гиперплоскость размерности n.
2. Каждому корню соответствует вектор, лежащий в этой гиперплоскости.
3. Каждый из векторов может быть получен из единственного исходного действием некоторой степени оператора специального вида.
4. Зная это, можно построить оператор последовательное действие которого на вектор нормали исходной гиперплоскости приводит на некотором шаге к обращению в нуль его первого компонента.
5. Всё. Дальше нужно просто считать шаги.
Позже напишу формулы.

[shwedka]

AN писал(а):

Позже напишу формулы.

Не доживу.....

[AN]

Когда уже получилось - внятно оформлять как-то неинтересно : ) А может просто нужно немного времени для того, чтобы это устоялось и приняло ясную форму.
Хотя, там всё очень просто, многое я писал раньше. Я каждый раз удивляюсь - как можно столько времени в упор смотреть на простые вещи и не видеть.
Если чесно, я не был уверен, что это кому-нибудь интересно, а теперь напишу обязательно : )

[G^a]

Добречко!

AN писал(а):

Если чесно, я не был уверен, что это кому-нибудь интересно, а теперь напишу обязательно : )

Мы, очень ждём!

На самом деле, если у Вас всё правильно, и корректно, то из того, что Вы озыучили, вытекают интересные прикладные аспекты.

[AN]

Здравствуйте. Сначала я напомню то, о чём уже писал. Буду сразу подробно показывать на примере квадратного уравнения, так мне самому проще.
Пусть имеется квадратное уравнение корни которого натуральны и различны:

$$(x-x_a)(x-x_b)=0;\ a,b\in N,\ a\ne b$$

. Раскрыв скобки и переобозначив коэффициенты получим знакомое со школы

$$x^2-cx+d=0$$

.
Далее обратимся к хорошо известному в комбинаторике тождеству (его можно найти, например, в книге Ричарда Стенли "Перечислительная комбинаторика" на странице 60):

$$x^n=\sum\limits_{k=0}^n k!S(n,k)\binom{x}{k}$$

, где

$$S(n,k)$$

- число Стирлинга второго рода,

$$\binom{x}{k}$$

- биномиальный коэффициент. Обозначим (смысл этого обозначения станет ясен позже):

$$G_1(x,k)=\binom{x}{k},\ G_2(y,k)=k!S(y,k)$$

, тогда тождество примет вид

$$x^y=\sum\limits_{k=0}^n G_1(x,k)G_2(y,k)$$

. Отсюда видно, что фиксируя

$$x$$

,

$$y$$

или обе переменные вместе мы получим показательную функцию, степенную функцию или натуральное число в натуральной степени. Также видно, что тождество можно рассматривать как скалярное произведение.
Для входящих в тождество биномиальных коэффициентов и чисел Стирлинга справедливы рекурентные формулы:

$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k;\ S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

. Как оказалось (в литературе я этого не нашёл) числа

$$G_2$$

также могут быть получены по рекурентной формуле:

$$G_2(n,k)=(k-1)G_2(n-1,k-1)+kG_2(n-1,k)$$

.
Далее я покажу как применить указанное тождество к решению квадратного уравнения.

Добавлено спустя 2 часа 34 минуты 5 секунд:

Сейчас я приведу квадратное уравнение к уравнению плоскости.
Выпишем таблицы (их начала) чисел $G_1$ и $G_2$.
Для $G_1$:

$$\begin{array}{cccccc} &\multicolumn{1}{|c}{1}&2&3&4&5\\ \hline 1&\multicolumn{1}{|c}{1}&0&0&0&0\\ 2&\multicolumn{1}{|c}{1}&1&0&0&0\\ 3&\multicolumn{1}{|c}{1}&2&1&0&0\\ 4&\multicolumn{1}{|c}{1}&3&3&1&0\\ 5&\multicolumn{1}{|c}{1}&4&6&4&1 \end{array}$$

Для $G_2$:

$$\begin{array}{cccccc} &\multicolumn{1}{|c}{1}&2&3&4&5\\ \hline 0&\multicolumn{1}{|c}{1}&0&0&0&0\\ 1&\multicolumn{1}{|c}{1}&1&0&0&0\\ 2&\multicolumn{1}{|c}{1}&3&2&0&0\\ 3&\multicolumn{1}{|c}{1}&7&12&6&0\\ 4&\multicolumn{1}{|c}{1}&15&50&60&24 \end{array}$$

Индекс $n$ нумерует строки, индекс $k$ - столбцы. Обратите внимание на нумерацию строк - в первом треугольнике она начинается с 1, а во втором с 0, это упрощает формулы.
(Подскажите, пожалуйста, как в ТЕХ-е нарисовать в верхнем левом углу таблицы косую черту и проставить индексы?)
Теперь можно написать

$$x^n=(\vec{g_{1x}},\vec{g_{2n}})$$

где $x$ - номер строки первого треугольника, $n$ - номер строки второго треугольника, а первый индекс указывает номер множества к которому принадлежит вектор (позже я укажу способ построения этих множеств).
Поскольку мы ограничиваемся квадратным уравнением, я, для простоты, буду писать формулы именно для этого конкретного случая.
Итак, пользуясь приведёнными выше треугольниками, мы можем записать:

$$x^2=1x_{i1}+3x_{i2}+2x_{i3};\ x^1=1x_{i1}+1x_{i2}+0x_{i3};\ x^0=1x_{i1}+0x_{i2}+0x_{i3}$$

. Подставим это в исхлдное уравнение, учитывая при этом, что

$$x_{i1}\equiv1$$

. Получим

$$1(1+3x_{i2}+2x_{i3})-c\ (1+1x_{i2}+0x_{i3})+d\ (1+0x_{i2}+0x_{i3})=0$$

, и после приведения подобных будем иметь

$$(1-c+d)1+(3-c)x_{i2}+2x_{i3}=0$$

. Обозначим

$$n_1=1-c+d;\ n_2=3-c;\ n_3=2$$

. Полагая

$$\vec{n}=\{n_1,n_2,n_3\},\ \vec{x_i}=\{1,x_{i2},x_{i3}\}$$

запишем

$$(\vec{n},\vec{x_i})=0$$

, что и является уравнением плоскости с вектором нормали $\vec{n}$.

[AN]

Вектор

$$\vec{x_i}$$

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

$$\hat{N_1}$$

, который действуя на вектор принадлежащий множеству даёт следующий в этом множестве вектор? Это можно сделать. Это будет следующая (нижняя треугольная ленточная) матрица

$$N_1=\left( \begin{array}{cccccc} 1&0&0&0&0&\ \\ 1&1&0&0&0&\ \\ 0&1&1&0&0&\ldots\\ 0&0&1&1&0&\ \\ 0&0&0&1&1&\ \\ \ &\ &\vdots&\ &\ &\ddots \end{array}\right)$$

В каждом конкретном случае будет получаться начало строки равное по длине размерности матрицы, но размерность можно задать сколь угодно большой. Для второго треугольника существует подобный оператор, но об этом позже.

Добавлено спустя 1 час 25 минут 32 секунды:

Поскольку это справедливо для любых двух соседних строк, ясно, что люббая строка треугольника Паскаля может быть получена из его первой строки (которая является первым ортом

$$\vec{e_1}=\{1,\ 0,\ 0,\ 0\ .\ .\ .\}$$

) действием некоторой степени оператора

$$\hat{N_1}$$

.
Каждому корню исходного уравнения соответствует вектор - строка треугольника Паскаля с номером, равным значению корня. В данном случае таких векторов два.
Как изменится вектор нормали плоскости, если подействовать оператором

$$\hat{N_1}$$

на оба вектора одновременно?

$$\hat{N_1}\vec{x_i}=\left(\begin{array}{ccc} 1&0&0\\1&1&0\\0&1&1 \end{array}\right) \left(\begin{array}{lll} 1\\x_{i2}\\x_{i3} \end{array}\right)= \left(\begin{array}{lll}1\\1+x_{i2}\\x_{i2}+x_{i3}\end{array}\right)$$

Обозначим

$$y_{i2}=1+x_{i2};\ y_{i3}=x_{i2}+x_{i3}$$

и векторно умножим полученные векторы

$$\left|\begin{array}{ccc} \vec{i}&\vec{j}&\vec{k}\\ 1&y_{a2}&y_{a3}\\ 1&y_{b2}&y_{b3} \end{array}\right| =(y_{a2}y_{b3}-y_{a3}y_{b2})\vec{i}-(y_{b3}-y_{a3})\vec{j}+(y_{b2}-y_{a2})\vec{k}$$

Подставив вместо

$$y_{ik}$$

соответствующие выражения найдём, что новый вектор нормали $\vec{n_1}$ может быть получен следующим образом

$$\left(\begin{array}{rrr} 1&-1&1\\0&1&-1\\0&0&1 \end{array}\right) \left(\begin{array}{lll} n_1\\n_2\\n_3 \end{array}\right)=\vec{n_1}$$

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

А если подействовать на вектор нормали оператором обратным указанному? Поскольку любым двум векторам множества однозначно соответствует вектор нормали, то очевидно, что и любому вектору нормали однозначно соответствует пара векторов множества. Подействовав на вектор нормали обратным оператором мы получим вектор, которому будет отвечать пара векторов каждый из которых окажется на шаг ближе к первому орту.
Из уравнения векторного произведения видно, что если на месте одного из сомножителей окажется первый орт, первый компонент результата обратится в ноль. Таким образом, последовательное действие обратного оператора на вектор нормали первый раз даст $0$ в первом компоненте на шаге $x_a-1$ и второй раз на шаге $x_b-1$. Матрица обратного оператора такова

$$\left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right)$$

Всё. Пожалуйста, проверьте : )

[AN]

Если не получится сделать этого сегодня, то в ближайшие дни покажу на простейшем примере.

[AN]

Вот обещанный пример.
Пусть имеется уравнение

$$(x-x_a)(x-x_b)=0$$

где

$$x_a=3;\ x_b=7$$

. Тогда

$$(x-3)(x-7)=0;\ 1\ x^2-10\ x+21=0$$

. Чтобы получить вектор нормали плоскости из вектора коэффициентов

$$\vec{a}=\{1,\ -10,\ 21\}$$

нужно подействовать на него матрицей, содержащей в столбцах строки второго треугольника (см. выше)

$$\vec{n}=\left(\begin{array}{ccc} 1&1&1\\3&1&0\\2&0&0 \end{array}\right) \left(\begin{array}{rrr} 1\\-10\\21 \end{array}\right)= \left(\begin{array}{rrr}12\\-7\\2\end{array}\right)$$

Всё. Далее остаётся последовательно действовать на вектор нормали последним оператором из предпоследнего поста (почти каламбур : ) и считать шаги

$$k$$

. Сделаем это:

$$k=1:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} 12\\-7\\2 \end{array}\right)= \left(\begin{array}{rrr}5\\-5\\2\end{array}\right)$$

$$k=2:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} 5\\-5\\2 \end{array}\right)= \left(\begin{array}{rrr}0\\-3\\2\end{array}\right)$$

- ноль в первом компоненте - раз

$$k=3:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} 0\\-3\\2 \end{array}\right)= \left(\begin{array}{rrr}-3\\-1\\2\end{array}\right)$$

$$k=4:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} -3\\-1\\2 \end{array}\right)= \left(\begin{array}{rrr}-4\\1\\2\end{array}\right)$$

$$k=5:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} -4\\1\\2 \end{array}\right)= \left(\begin{array}{rrr}-3\\3\\2\end{array}\right)$$

$$k=6:\ \left(\begin{array}{ccc} 1&1&0\\0&1&1\\0&0&1 \end{array}\right) \left(\begin{array}{rrr} -3\\3\\2 \end{array}\right)= \left(\begin{array}{rrr}0\\5\\2\end{array}\right)$$

- ноль в первом компоненте - два
Учитывая, что

$$x_i=k+1$$

получим

$$x_a=3;\ x_b=7$$

. Готово : )

[dmd]

AN писал(а):

1. Многочлену (напоминаю - кори натуральны и различны) степени n сопоставляется гиперплоскость размерности n.

В случае квадратного уравнения если его корни натуральны, то дискриминант есть квадрат натурального числа, т.е. вычисление радикала беспроблемно. Распишите, пожалуйста, пример для кубического уравнения, допустим

$$(x-3)(x-4)(x-5)=0$$

, у которого дискриминант отрицателен и корни вычисляются через мнимости.

AN писал(а):

Далее обратимся к хорошо известному в комбинаторике тождеству (его можно найти, например, в книге Ричарда Стенли "Перечислительная комбинаторика" на странице 60):

$$x^n=\sum\limits_{k=0}^n k!S(n,k)\binom{x}{k}$$

, где

$$S(n,k)$$

- число Стирлинга второго рода,

$$\binom{x}{k}$$

- биномиальный коэффициент. Обозначим (смысл этого обозначения станет ясен позже):

$$G_1(x,k)=\binom{x}{k},\ G_2(y,k)=k!S(y,k)$$

, тогда тождество примет вид

$$x^y=\sum\limits_{k=0}^n G_1(x,k)G_2(y,k)$$

.

Если Вы перешли от где

$$n$$

к

$$y$$

, то сумма должна быть тоже до

$$y$$

.

AN писал(а):

Для входящих в тождество биномиальных коэффициентов и чисел Стирлинга справедливы рекурентные формулы:

$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k;\ S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

. Как оказалось (в литературе я этого не нашёл) числа

$$G_2$$

также могут быть получены по рекурентной формуле:

$$G_2(n,k)=(k-1)G_2(n-1,k-1)+kG_2(n-1,k)$$

.

Не очень понятно, откуда взялся коэффициент

$$(k-1)$$

перед

$$G_2$$

[Андрей Назаренко]

Должен начать с извинений. Я - AN. Я несколько раз забывал пароль и просил новый и еще забывал где-нибудь его записать, поэтому для входа каждый раз смотрел в почте его последнюю версию. Сегодня что-то случилось с нашим университетским сервером, и я не смог его опять списать. Поэтому для того чтобы ответить, я завёл ящик на mail.ru, а здесь зарегистрировался снова. ICQ остался тот же. Как только наладят сервер - зайду под старым ником и поправлю профиль, всё равно собирался менять почту. Прошу администрацию форума зачесть явку с повинной.
Теперь по существу вопроса. Ваш пример, dmd, расписывал с интересом и волнением - очень хотелось, чтобы работало и в этом случае. Работает : ) Алгоритм абсолютно(!) аналогичен. Смотрите:
Имеем

$$(x-3)(x-4)(x-5)=0$$

или иначе

$$x^3-12\ x^2+47\ x-60=0$$

. Тогда вектор коэффициентов

$$\vec{a}=\{1,\ -12,\ 47,\ -60\}$$

. Получим вектор нормали плоскости

$$\vec{n}=\left(\begin{array}{llll} 1&1&1&1\\7&3&1&0\\12&2&0&0\\6&0&0&0 \end{array}\right) \left(\begin{array}{rrrr} 1\\-12\\47\\-60 \end{array}\right)= \left(\begin{array}{rrrr}-24\\18\\-12\\6 \end{array}\right)$$

или (после вынесения

$$6$$

)

$$\vec{n}=\left(\begin{array}{rrrr}-4\\3\\-2\\1 \end{array}\right)$$

.
Далее будем действовать совершенно так же, как в случае с квадратным уравнением:

$$k=1: \ \left(\begin{array}{cccc} 1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&0&1 \end{array}\right) \left(\begin{array}{rrrr} -4\\3\\-2\\1 \end{array}\right)=\left(\begin{array}{rrrr} -1\\1\\-1\\1\end{array}\right)$$

$$k=2: \ \left(\begin{array}{cccc} 1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&0&1 \end{array}\right) \left(\begin{array}{rrrr} -1\\1\\-1\\1 \end{array}\right)=\left(\begin{array}{rrrr} 0\\0\\0\\1 \end{array}\right)$$

- ноль в первом компоненте - раз

$$k=3: \ \left(\begin{array}{cccc} 1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&0&1 \end{array}\right) \left(\begin{array}{rrrr} 0\\0\\0\\1 \end{array}\right)= \left(\begin{array}{rrrr} 0\\0\\1\\1 \end{array}\right)$$

- ноль в первом компоненте - два

$$k=4: \ \left(\begin{array}{cccc} 1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&0&1 \end{array}\right) \left(\begin{array}{rrrr} 0\\0\\1\\1 \end{array}\right)= \left(\begin{array}{rrr} 0\\1\\2\\1 \end{array}\right)$$

- ноль в первом компоненте - три
Обратите внимание на то, что на следующем шаге все компоненты результирующего вектора станут положительными, а значит нулей больше не будет. Таким образом, не будет больше и корней - их оказалось ровно три.
С учётом того, что

$$x_i=k+1$$

получим

$$x_1=3;\ x_2=4;\ x_3=5$$

. Как видите, тут обходится не только без радикалов, но и без мнимостей : ) Не знаю, насколько это может быть полезно, но согласитесь - красиво.

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

Вы, dmd, совершенно правы -

$$n$$

действительно следовало заменить на

$$y$$

. А еще лучше - вообще ничего не писать над суммой. Если длины строк не совпадают, то суммировать достаточно до меньшего из двух индексов

$$k=min\{k_1,\ k_2\}$$

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

$$G_2$$

. Это самый сложный момент во всём доселе сказанном. Дело в том, что тождество Ворпицкого (так оно называется в "Конкретной математике" Кнута) я обнаружил в литературе много позже того как нашёл числа

$$G_2$$

, а потом и рекурентную формулу для них. Найденную мной формулу для

$$x^n$$

по моей просьбе доказал читавший нам в то время матанализ профессор Смолич, за что огромное ему спасибо. Я, само собой, это доказательство быстро потерял, но надежда на результат раскопок бумаг не равна нулю. Без сомнений, переход от чисел Стирлинга второго рода (которые, кстати, появляются в явном виде при переходе от дискретного случая к непрерывному) к числам

$$G_2$$

требует строгого доказательства, но пока я прошу сосредоточиться на методе решения многочленов в предположении, что с числами всё в порядке. Вообще, это не единственное их применение. Можно построить числа

$$G_3$$

,

$$G_4$$

и вообще

$$G_n$$

. Есть один интригующий пример который наталкивает на мысль о возможной векторной факторизации (разложении в скалярное произведение) простых чисел по этой схеме. Но это уже совсем другая история : ) Если интересно - обязательно расскажу, но давайте немного разберёмся с этим.

[AN]

На пробу взял уравнение 6-й степени с простыми корнями (3, 5, 7, 11, 17, 19) - работает. Считал в Maple 9.5.

[dmd]

AN писал(а):

На пробу взял уравнение 6-й степени с простыми корнями (3, 5, 7, 11, 17, 19) - работает. Считал в Maple 9.5.

Сколько получилось шагов?

Будет ли работать этот метод для случая действительных коэффициентов и корней многочлена? Или хотя бы произвольных целых коэффициентов?

[AN]

Шагов получилось, соответственно, 2, 4, 6, 10, 16 и 18. Для чистоты эксперимента их считала жена : )
Я говорил, что можно перейти к непрерывному случаю, это позволяет надеяться, что метод будет работать в случае положительных действительных корней, но это требует проверки. Также нужно проверять отрицательные и кратные корни.
Пока результат таков - произвольное уравнение с одной переменной 5-й степени и выше нельзя решить в радикалах, а уравнение любой степени с натуральными различными корнями, по всей видимости, можно решить вообще без радикалов.

[Brukvalub]

AN писал(а):

... уравнение любой степени с натуральными различными корнями, по всей видимости, можно решить вообще без радикалов.

Это очевидно и без всяких ухищрений: с помощью несложных априорных оценок нетрудно выделить отрезок, заведомо содержащий все корни, после чего перебрать все натуральные числа на этом отрезке, причем так находятся даже кратные натуральные корни.

[AN]

Разумеется, решать такие уравнения можно разными способами, в том числе простым перебором. Полезность либо бесполезность данного конкретного метода определяется лишь тем, можно ли на его основе построить алгоритм отыскания корней более эффективный чем уже существующие. А так же тем, можно ли идею лежащую в основе метода применить к другим задачам (об одной я уже упоминал).
Здесь я хотел лишь выяснить - не встречал ли кто-нибудь подобного подхода. Основная мысль - приведение степенной либо показательной функции (поскольку они в данном сучае совершенно равноправны) к уравнению гиперплоскости.