Ttdfjt

To find islands of 1 and 0 in matrix

Desktop app status bar: Notification vs error message

Exploiting the delay when a festival ticket is scanned

Why is の所 used after ドア in this sentence?

How could Nomadic scholars effectively memorize libraries worth of information

Why is it considered acid rain with pH <5.6?

How did the SysRq key get onto modern keyboards if it's rarely used?

What container to use to store developer concentrate?

Compound Word Neologism

Do 3/8 (37.5%) of Quadratics Have No x-Intercepts?

Japanese reading of an integer

How do you pronounce "Hain"?

Nested keyval proper parsing

Must a song using the A minor scale begin or end with an Am chord? If not, how can I tell what the scale is?

Why did Windows 95 crash the whole system but newer Windows only crashed programs?

Can you place a support header in the ceiling?

If Trump gets impeached, how long would Pence be president?

Why didn’t Christianity spread southwards from Ethiopia in the Middle Ages?

(3 of 11: Akari) What is Pyramid Cult's Favorite Car?

8086 stack segment and avoiding overflow in interrupts

What is the most efficient way to write 'for' loops in Matlab?

What do you call a flexible diving platform?

Where can I find a clear explanation (brief derivation) of N(d1) and N(d2)?

Is it error of law to judge on less relevant case law when there is much more relevant one?

When can a polynomial be written as a polynomial function of another polynomial?

Polynomial decomposition testWhen is a polynomial a composition of a polynomial with some (unspecified) non-linear polynomial?Matching of polynomial coefficientsDetermining a polynomial from its crossings with another polynomialIs this an automorphism of a polynomial ring?Identical multivariate polynomial definitionRational symmetric polynomial in the roots of an integer polynomial is rationalA polynomial with real coefficients expressible as sum of squares of two polynomials will have not all roots as real.Sum of squared coefficients of polynomialQuestion about polynomial multiplicationFormulas for the coefficients of the expansion of one monic polynomial in terms of anotherDoes the assumption $0^0=1$ ever lead to a contradiction or conflict with another useful assumption?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

6

5

$begingroup$

Given two polynomials $p(x)$ and $g(x)$, how do I ascertain whether or not $p(x)$ is expressible as

$$p(x)= sum_i=0^n a_i (g(x))^i,$$

where $a_i_i=1^n$ are constant coefficients.

Example: Let $p(x)= x^6-3x^4+4x^2-1$ and $g(x)= x^2-1$, then $$p(x)= (g(x))^3+g(x)+1.$$

algebra-precalculus polynomials

share|cite|improve this question

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

$endgroup$

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  You can be sure $p(x)$ is not a polynomial in $g(x)$ if $deg p$ is not divisible by $deg g$.
  $endgroup$
  – Bernard
  Jul 18 at 14:18
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For general polynomial decomposition algorithms $ p(x) = f(g(x)),$ see my comment here.
  $endgroup$
  – Bill Dubuque
  Jul 19 at 2:20
  

  
  
  
  

add a comment | 

6

5

$begingroup$

Given two polynomials $p(x)$ and $g(x)$, how do I ascertain whether or not $p(x)$ is expressible as

$$p(x)= sum_i=0^n a_i (g(x))^i,$$

where $a_i_i=1^n$ are constant coefficients.

Example: Let $p(x)= x^6-3x^4+4x^2-1$ and $g(x)= x^2-1$, then $$p(x)= (g(x))^3+g(x)+1.$$

algebra-precalculus polynomials

share|cite|improve this question

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

$endgroup$

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  You can be sure $p(x)$ is not a polynomial in $g(x)$ if $deg p$ is not divisible by $deg g$.
  $endgroup$
  – Bernard
  Jul 18 at 14:18
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For general polynomial decomposition algorithms $ p(x) = f(g(x)),$ see my comment here.
  $endgroup$
  – Bill Dubuque
  Jul 19 at 2:20
  

  
  
  
  

add a comment | 

$begingroup$

Given two polynomials $p(x)$ and $g(x)$, how do I ascertain whether or not $p(x)$ is expressible as

$$p(x)= sum_i=0^n a_i (g(x))^i,$$

where $a_i_i=1^n$ are constant coefficients.

Example: Let $p(x)= x^6-3x^4+4x^2-1$ and $g(x)= x^2-1$, then $$p(x)= (g(x))^3+g(x)+1.$$

algebra-precalculus polynomials

share|cite|improve this question

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

$endgroup$

share|cite|improve this question

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

share|cite|improve this question

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

edited Jul 18 at 14:20

Mars Plastic

2,83255 silver badges3131 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

asked Jul 18 at 14:13

aditya guptaaditya gupta

4133 bronze badges

1 Answer
1

active

oldest

votes

16

$begingroup$

I'm not sure how to put it in a simple condition, but there's a procedure that allows to check whether $p(x)=w(g(x))$ for $w$ being a polynomial function.

Let's perform a repeated polynomial division of $p$ over $g$, that is let $q_n(x)$ and $r_n(x)$, $ninmathbb N$ be polynomials such that $deg r_n < deg g$, $q_n neq 0$ and
$$ p(x) = q_0(x) g(x) + r_0(x) \ q_0(x) = q_1(x) g(x) + r_1(x) \ q_1(x) = q_2(x) g(x) + r_2(x) \ q_2(x) = q_3(x) g(x) + r_3(x) \ dots $$
Such division will always end in a finite number of steps. If all $r_n$ are constants, that is $deg r_n = 0$, $r_n(x) = r_n$, then $$ p(x) = sum_n r_n big(g(x)big)^n $$
If at any point we get $r_n(x)$ that is not constant, then $p(x)$ cannot be expressed as a polynomial of $g(x)$.

share|cite|improve this answer

edited Jul 18 at 14:38

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is there a reference?
  $endgroup$
  – Paracosmiste
  Jul 18 at 23:02
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @Paracosmiste This is known as the $g$-adic expansion of $,p,$ in the general case when the coefficients $r_i$ have degree $< deg g.,$ It is easily seen to be unique.. It is analogous to radix expansions of integers and generalizes Taylor series expansions. If is often used to compute partial fraction expansions.
  $endgroup$
  – Bill Dubuque
  Jul 19 at 2:09
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3296843%2fwhen-can-a-polynomial-be-written-as-a-polynomial-function-of-another-polynomial%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

16

$begingroup$

I'm not sure how to put it in a simple condition, but there's a procedure that allows to check whether $p(x)=w(g(x))$ for $w$ being a polynomial function.

Let's perform a repeated polynomial division of $p$ over $g$, that is let $q_n(x)$ and $r_n(x)$, $ninmathbb N$ be polynomials such that $deg r_n < deg g$, $q_n neq 0$ and
$$ p(x) = q_0(x) g(x) + r_0(x) \ q_0(x) = q_1(x) g(x) + r_1(x) \ q_1(x) = q_2(x) g(x) + r_2(x) \ q_2(x) = q_3(x) g(x) + r_3(x) \ dots $$
Such division will always end in a finite number of steps. If all $r_n$ are constants, that is $deg r_n = 0$, $r_n(x) = r_n$, then $$ p(x) = sum_n r_n big(g(x)big)^n $$
If at any point we get $r_n(x)$ that is not constant, then $p(x)$ cannot be expressed as a polynomial of $g(x)$.

share|cite|improve this answer

edited Jul 18 at 14:38

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is there a reference?
  $endgroup$
  – Paracosmiste
  Jul 18 at 23:02
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @Paracosmiste This is known as the $g$-adic expansion of $,p,$ in the general case when the coefficients $r_i$ have degree $< deg g.,$ It is easily seen to be unique.. It is analogous to radix expansions of integers and generalizes Taylor series expansions. If is often used to compute partial fraction expansions.
  $endgroup$
  – Bill Dubuque
  Jul 19 at 2:09
  

  
  
  
  

add a comment | 

16

$begingroup$

I'm not sure how to put it in a simple condition, but there's a procedure that allows to check whether $p(x)=w(g(x))$ for $w$ being a polynomial function.

Let's perform a repeated polynomial division of $p$ over $g$, that is let $q_n(x)$ and $r_n(x)$, $ninmathbb N$ be polynomials such that $deg r_n < deg g$, $q_n neq 0$ and
$$ p(x) = q_0(x) g(x) + r_0(x) \ q_0(x) = q_1(x) g(x) + r_1(x) \ q_1(x) = q_2(x) g(x) + r_2(x) \ q_2(x) = q_3(x) g(x) + r_3(x) \ dots $$
Such division will always end in a finite number of steps. If all $r_n$ are constants, that is $deg r_n = 0$, $r_n(x) = r_n$, then $$ p(x) = sum_n r_n big(g(x)big)^n $$
If at any point we get $r_n(x)$ that is not constant, then $p(x)$ cannot be expressed as a polynomial of $g(x)$.

share|cite|improve this answer

edited Jul 18 at 14:38

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is there a reference?
  $endgroup$
  – Paracosmiste
  Jul 18 at 23:02
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @Paracosmiste This is known as the $g$-adic expansion of $,p,$ in the general case when the coefficients $r_i$ have degree $< deg g.,$ It is easily seen to be unique.. It is analogous to radix expansions of integers and generalizes Taylor series expansions. If is often used to compute partial fraction expansions.
  $endgroup$
  – Bill Dubuque
  Jul 19 at 2:09
  

  
  
  
  

add a comment | 

$begingroup$

I'm not sure how to put it in a simple condition, but there's a procedure that allows to check whether $p(x)=w(g(x))$ for $w$ being a polynomial function.

Let's perform a repeated polynomial division of $p$ over $g$, that is let $q_n(x)$ and $r_n(x)$, $ninmathbb N$ be polynomials such that $deg r_n < deg g$, $q_n neq 0$ and
$$ p(x) = q_0(x) g(x) + r_0(x) \ q_0(x) = q_1(x) g(x) + r_1(x) \ q_1(x) = q_2(x) g(x) + r_2(x) \ q_2(x) = q_3(x) g(x) + r_3(x) \ dots $$
Such division will always end in a finite number of steps. If all $r_n$ are constants, that is $deg r_n = 0$, $r_n(x) = r_n$, then $$ p(x) = sum_n r_n big(g(x)big)^n $$
If at any point we get $r_n(x)$ that is not constant, then $p(x)$ cannot be expressed as a polynomial of $g(x)$.

share|cite|improve this answer

edited Jul 18 at 14:38

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

$endgroup$

share|cite|improve this answer

edited Jul 18 at 14:38

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges

answered Jul 18 at 14:33

Adam LatosińskiAdam Latosiński

6,91477 silver badges2020 bronze badges