Когда полином равен нулю?

[DLL]

Рассмотрим полином $F = A_1 x^{\alpha_1} y^{\beta_1} + A_2 x^{\alpha_2} y^{\beta_2}.$
Он равен нулю в случае когда либо:
1) $A_1 = A_2 = 0$
либо
2) $\alpha_1 = \alpha_2, \beta_1 = \beta_2, A_1 = -A_2$.

Возьмем теперь произвольный случай: $F = A_1 x^{\alpha_1} y^{\beta_1} + A_2 x^{\alpha_2} y^{\beta_2} + ... + A_n x^{\alpha_n} y^{\beta_n}.$
Интересно как теперь найти все возможные условия равенства нулю.
Полагаю, можно свести это дело к какому-нибудь известному алгоритму. Есть идеи?

[sergei1961]

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

[Munin]

Рассмотрите все возможные разбиения множества $\{1,\ldots,n\}$ на подмножества. В каждом подмножестве показатели должны быть равны друг другу, а сумма коэффициентов - нулю. Ваши случаи соответствуют разбиениям:
1) $\{1\},\{2\};$
2) $\{1,2\}.$

-- 22.02.2017 22:14:43 --

sergei1961
Очевидно, спрашивается, когда выражение равно нулю не как значение функции в точке, а как функция.

[Anton_Peplov]

Дабы избегать таких недоразумений, можно пользоваться оборотом "тождественно равен нулю".

[arseniiv]

Или «равен нулевому [многочлену]».

Кстати, не понимаю, зачем разбиения — нужно просто привести его к виду

DLL в сообщении #1194686 писал(а):

$F = A_1 x^{\alpha_1} y^{\beta_1} + A_2 x^{\alpha_2} y^{\beta_2} + ... + A_n x^{\alpha_n} y^{\beta_n}.$

в котором, однако, не более одного слагаемого для каждого набора степеней переменных. Тогда равенство нулю — это просто одновременное равенство нулю всех $A_i$. Это и для компьютерных вычислений практичнее, if any.

[Munin]

arseniiv в сообщении #1194697 писал(а):

Или «равен нулевому [многочлену]».

Ну, если альфы и беты, не дай бог, нецелые, то является ли это многочленом? (Вопрос риторический.)

[gris]

arseniiv, привести подобные, как в 7 классе?

[sergei1961]

arseniiv - согласен с Вами. Если спрашивается про тождественно, то по определению. Для немногочленов-непонятно. Для рациональных степеней можно свести дело к многочленам заменами, иначе это похоже безнадёжно, или как?

[DLL]

arseniiv в сообщении #1194697 писал(а):

Или «равен нулевому [многочлену]».

Кстати, не понимаю, зачем разбиения — нужно просто привести его к виду

DLL в сообщении #1194686 писал(а):

$F = A_1 x^{\alpha_1} y^{\beta_1} + A_2 x^{\alpha_2} y^{\beta_2} + ... + A_n x^{\alpha_n} y^{\beta_n}.$

в котором, однако, не более одного слагаемого для каждого набора степеней переменных. Тогда равенство нулю — это просто одновременное равенство нулю всех $A_i$. Это и для компьютерных вычислений практичнее, if any.

ОК, но на самом деле задача чуть сложнее.
Некоторые альфы и беты заданы как числа.
А некоторые как неизвестные, но максимум в виде линейной комбинации.
Например: $3m - 5n$

[DLL]

Ну то есть речь скажем идет:
$F = A_1 x^{4m-5n} y^{n+2} + A_2 x^{m+n} y^{2n - 1}$.
P.S: альфы и беты зависят от неизвестных линейно!

[arseniiv]

Munin в сообщении #1194721 писал(а):

Ну, если альфы и беты, не дай бог, нецелые, то является ли это многочленом? (Вопрос риторический.)

Вообще, конечно, вопрос темы допускает такое расширение с ровно аналогичным же решением, но я в формулировках оставался в рамках того, что написал ТС.

gris в сообщении #1194725 писал(а):

arseniiv, привести подобные, как в 7 классе?

Да, именно.

sergei1961 в сообщении #1194742 писал(а):

иначе это похоже безнадёжно, или как?

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

DLL в сообщении #1194746 писал(а):

А некоторые как неизвестные, но максимум в виде линейной комбинации.
Например: $3m - 5n$

Но общее решение этим не отменяется. Просто возникнет много условных конструкций, ну так и что?

Пример:

$$ax^\alpha + a'x^{\alpha'} = (\alpha=\alpha') \mathbin? (a + a')x^\alpha : (ax^\alpha + a'x^{\alpha'}),$$

где справа выражение в «каноническом» виде (что вообще уместно представлять как списки, множества или что-то в этом духе, если мы о вычислениях), а слева не обязательно. Или можно скобками Айверсона записать, тут уж зависит от того, чем будет удобнее манипулировать.

DLL в сообщении #1194786 писал(а):

P.S: альфы и беты зависят от неизвестных линейно!

Значит, в худшем случае придётся решать лишь линейные системы.

[arseniiv]

Да, разбиения всё-таки полезны оказываются, если писать реализацию. Например, для выражения

x^a[1] A[1] + x^a[2] A[2] + x^a[3] A[3] + x^a[4] A[4]

можно получить

(a[1] == a[2] == a[3] == a[4] && A[1] + A[2] + A[3] + A[4] == 0) || 
(a[1] == a[2] && a[3] == a[4] && A[1] + A[2] == A[3] + A[4] == 0) || 
(a[1] == a[4] && a[2] == a[3] && A[1] + A[4] == A[2] + A[3] == 0) || 
(a[1] == a[3] && a[2] == a[4] && A[1] + A[3] == A[2] + A[4] == 0) || 
(a[2] == a[3] == a[4] && A[1] == A[2] + A[3] + A[4] == 0) || 
(a[1] == a[3] == a[4] && A[1] + A[3] + A[4] == A[2] == 0) || 
(a[1] == a[2] == a[3] && A[1] + A[2] + A[3] == A[4] == 0) || 
(a[1] == a[2] == a[4] && A[1] + A[2] + A[4] == A[3] == 0) || 
(a[3] == a[4] && A[1] == A[2] == A[3] + A[4] == 0) || 
(a[2] == a[3] && A[1] == A[2] + A[3] == A[4] == 0) || 
(a[2] == a[4] && A[1] == A[2] + A[4] == A[3] == 0) || 
(a[1] == a[2] && A[1] + A[2] == A[3] == A[4] == 0) || 
(a[1] == a[3] && A[1] + A[3] == A[2] == A[4] == 0) || 
(a[1] == a[4] && A[1] + A[4] == A[2] == A[3] == 0) || 
A[1] == A[2] == A[3] == A[4] == 0

Это, конечно, без учёта того, что a[i] могут быть линейными комбинациями других переменных, в случае чего равенства могут давать несовместные системы, и для таких равенств можно будет выкидывать соответствующий член дизъюнкции.

[DLL]

Это в каком пакете получено?

[arseniiv]

Немного кода на Mathematica 8. Но я схитрил, и на входе на самом деле вот такое:

{{A[1], a[1]}, {A[2], a[2]}, {A[3], a[3]}, {A[4], a[4]}}

А код работы с этим такой:

Needs["Combinatorica`"]; (* SetPartitions *)
Clear[zeroCondition, partitionEqMap, partitionEqMap2]
partitionEqMap[f_, p_List] := And @@ Map[Equal @@ # &, Map[f, p, {2}]]
partitionEqMap2[f_, p_List] := Equal @@ Append[Map[Plus @@ (f /@ #) &, p], 0]
zeroCondition[expr_] := Block[
    {len = Length[expr], pns},
    pns = SetPartitions[len];
    Or @@ Map[And[
        partitionEqMap[expr[[#, 2]] &, #],
        partitionEqMap2[expr[[#, 1]] &, #]] &, pns]]

Документация не прилагается.

[Munin]

arseniiv в сообщении #1194792 писал(а):

Вообще, конечно, вопрос темы допускает такое расширение

Кто сказал, что это расширение?