Разложить полиномы

12

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

Детали

  • Целочисленный многочлен является многочленом только с целыми числами в качестве коэффициентов.
  • Принимая во внимание два полинома pи композиции определяется .q(p∘q)(x):=p(q(x))
  • Разложение интегрального полинома pявляется конечной упорядоченной последовательностью целочисленных многочленов , q1,q2,...,qnгде deg qi > 1для всех 1 ≤ i ≤ nи p(x) = q1(q2(...qn(x)...)), и все qiдалее не разложимые. Разложение не обязательно уникально.
  • Вы можете использовать, например, списки коэффициентов или встроенные полиномиальные типы в качестве входных и выходных данных.
  • Обратите внимание, что многие встроенные функции для этой задачи фактически разлагают полиномы по заданному полю и не обязательно являются целыми числами, в то время как для этой задачи требуются разложенные целочисленные полиномы. (Некоторые целочисленные полиномы могут допускать разложение на целочисленные полиномы, а также разложение, содержащее рациональные полиномы.)

Примеры

x^2 + 1
[x^2 + 1] (all polynomials of degree 2 or less are not decomposable)
x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6 x - 1
[x^3 - 2, x^2 - 2x + 1]
x^4 - 8x^3 + 18x^2 - 8x + 2 
[x^2 + 1, x^2 - 4x + 1]
x^6 + x^2 + 1
[x^3 + x + 1, x^2]
x^6
[x^2, x^3]
x^8 + 4x^6 + 6x^4 + 4x^2 + 4 = (x^2 + 1)^4 + 3
[x^2 + 3, x^2, x^2 + 1]
x^6 + 6x^4 + x^3 + 9x^2 + 3x - 5
[x^2 + x - 5, x^3 + 3*x], [x^2 + 5*x + 1, x^3 + 3*x - 2]

Используйте Maxima для генерации примеров: попробуйте онлайн!

Некоторые алгоритмы разложения можно найти здесь и здесь .

code-golf math number abstract-algebra polynomials flawr
источник

Ответы:

4

Пари / ГП , 84 байта

f(p)=[if(q'',[f(q),r],p)|r<-x*divisors(p\x),r''&&p==subst(q=substpol(p,r,x),x,r)][1]

На основе алгоритма, описанного здесь .

Попробуйте онлайн!

alephalpha
источник
1
Вы проверяете (или отфильтровываете), действительно ли вы получаете разложение на целые полиномы? (Я спрашиваю, потому что алгоритмы в связанном документе описывают факторизацию по некоторой области, и я не знаю Pari / GP.)
flawr
1
@flawr Я использую второй алгоритм в статье, который всегда возвращает интегральные полиномы, когда входные данные являются интегральными. Фактически, divisorsфункция в Pari / GP всегда возвращает примитивные полиномы, когда она принимает целочисленный полином. Можно доказать, что если p=q∘r, где pи rявляются интегральными и rпримитивными r(0)=0, то qтакже должны быть интегральными. Здесь p, q, rсоответствуют f, g, hв работе.
алефальфа
2

Wolfram Language (Mathematica) , 29 байт

Decompose[#/.x->x+a,x]/.a->0&

Попробуйте онлайн!

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

Необходимо усложнить полином с помощью фиктивной переменной (а), поскольку встроенный не будет пытаться разложить моном.

Я заметил, что ответ часто имеет гораздо большие коэффициенты, чем в исходной композиции, но они действительно всегда целые числа.

Келли Лоудер
источник
Где вы нашли информацию, Decompose[]которая всегда будет возвращать целочисленные полиномы (если они снабжены целочисленными полиномами)? При обсуждении в чате недавно мы ничего не могли найти по этому поводу.
flawr
1
Делай Options@Decomposeи это тебе скажет {Modulus->0}. Теперь посмотрите на модуль и вы увидите, что «Настройка модуля> 0 определяет полное кольцо [DoubleStruckCapitalZ] целых чисел».
Келли Лоудер
Ах, это хорошо, спасибо за разработку!
flawr