No. of Polynomials of Degree 5 Divisible By x2-x+1

[juantheron]

Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

 

[chisigma]

For the reasons explained in the successive post of C.B. this post is canceled and the solution must be found... sorry!(Speechless)...

Kind regards

$\chi$ $\sigma$

 

[CaptainBlack]

If 'polynomials with distinct coefficients' means 'different polynomials' the solution is easy: the requested number is equal to the number of polynomials of degree 3 that can be constructed with a set of 8 coefficients, i.e. $\displaystyle n= 8^{4}= 4096$...

Kind regards

$\chi$ $\sigma$

Except there are cubics with coefficients selected from those 8 such that the quintic has duplicate coefficients (and others with one or more coefficients not from the 8).

CB

 

[Opalg]

Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

Start by dividing the fifth degree polynomial $ax^5+bx^4+cx^3+dx^2+ex+f$ by $x^2-x+1$: $$ax^5+bx^4+cx^3+dx^2+ex+f = (x^2-x+1)\bigl(ax^3 + (a+b)x^2 + (b+c)x + (d+c-a)\bigr) + (d+e-b-a)x + (a+f-c-d).$$ The conditions for the remainder to be zero are $$\boxed{\begin{array}{c}a+b = d+e, \\ a+f = c+d. \end{array}}$$ So you are looking for the number of sextuplets $(a,b,c,d,e,f)$ consisting of six distinct elements from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that satisfy the boxed conditions.

I do not see any straightforward method to count that number. In fact, the easiest way might be to generate a computer listing of all such sextuplets.

 

[chisigma]

Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

Let's write the 5 degree polynomial as $\displaystyle P(x)= a_{5}\ x^{5} + a_{4}\ x^{4} + a_{3}\ x^{3} + a_{2}\ x^{2} + a_{1}\ x + a_{0}$. If $\displaystyle x^{2} - x +1$ divides P(x), then $\displaystyle e^{i\ \frac{\pi}{3}}$ as well as $\displaystyle e^{- i\ \frac{\pi}{3}}$ is a root of P(x), so that we can write...

$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Observing (1) we note that all the triplets $\displaystyle a_{0},a_{1},a_{2}$ combined with the conditions $\displaystyle a_{3}=a_{0}, a_{4}=a_{1}, a_{5}=a_{2}$ satisfies (1) so that the requested number of polynomials is $\displaystyle 8^{3}= 512$...

Kind regards

$\chi$ $\sigma$

 

[chisigma]

Let's write the 5 degree polynomial as $\displaystyle P(x)= a_{5}\ x^{5} + a_{4}\ x^{4} + a_{3}\ x^{3} + a_{2}\ x^{2} + a_{1}\ x + a_{0}$. If $\displaystyle x^{2} - x +1$ divides P(x), then $\displaystyle e^{i\ \frac{\pi}{3}}$ as well as $\displaystyle e^{- i\ \frac{\pi}{3}}$ is a root of P(x), so that we can write...

$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Observing (1) we note that all the triplets $\displaystyle a_{0},a_{1},a_{2}$ combined with the conditions $\displaystyle a_{3}=a_{0}, a_{4}=a_{1}, a_{5}=a_{2}$ satisfies (1) so that the requested number of polynomials is $\displaystyle 8^{3}= 512$...

Observing more carefully (1) we discover that the condition $\displaystyle a_{2}-a_{5}= a_{1}-a_{4}=a_{0}-a_{3}=0$ is not the only solving way because the basic equality $\displaystyle e^{i\ \frac{2}{3}\ \pi} - e^{i\ \frac{1}{3}\ \pi} + 1=0$ implies that $\displaystyle a_{2}-a_{5}= a_{4}-a_{1}=a_{0}-a_{3}= \pm 1$ is also a solving way and that means that the requested number of polynomials is $\displaystyle 8^{3} +2\ \cdot 7^{3}= 1198$...

Kind regards

$\chi$ $\sigma$

 

[Opalg]

$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

If you take the real part of (1) then you find that $\frac12((a_{2}-a_{5}) +\frac12(a_{1}-a_{4}) + (a_{0}-a_{3}) = 0$. If you take the imaginary part of (1) then you get $a_{2}-a_{5} = a_{1}-a_{4}$. Those equations are equivalent to the boxed equations in my previous comment. These are the only conclusions that you can deduce from (1), and chisigma's following claim is incorrect:

Observing more carefully (1) we discover that the condition $\displaystyle a_{2}-a_{5}= a_{1}-a_{4}=a_{0}-a_{3}=0$ is not the only solving way because the basic equality $\displaystyle e^{i\ \frac{2}{3}\ \pi} - e^{i\ \frac{1}{3}\ \pi} + 1=0$ implies that $\displaystyle a_{2}-a_{5}= a_{4}-a_{1}=a_{0}-a_{3}= \pm 1$ is also a solving way and that means that the requested number of polynomials is $\displaystyle 8^{3} +2\ \cdot 7^{3}= 1198$...

The original problem was:

Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

I understood the phrase in red to mean that, in each such polynomial, the six integers $a_0,a_1,a_2,a_3,a_4,a_5$ should be distinct elements of the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$. That condition makes the problem very much harder to solve.

 

[CaptainBlack]

If you take the real part of (1) then you find that $\frac12((a_{2}-a_{5}) +\frac12(a_{1}-a_{4}) + (a_{0}-a_{3}) = 0$. If you take the imaginary part of (1) then you get $a_{2}-a_{5} = a_{1}-a_{4}$. Those equations are equivalent to the boxed equations in my previous comment. These are the only conclusions that you can deduce from (1), and chisigma's following claim is incorrect:


The original problem was:

I understood the phrase in red to mean that, in each such polynomial, the six integers $a_0,a_1,a_2,a_3,a_4,a_5$ should be distinct elements of the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$. That condition makes the problem very much harder to solve.

When I get the chance I will cut some code to directly count the number of polynomials with the required property (but being Saturday that will be after household duties which will be in about 9 hours time)

CB

 

[chisigma]

I apologize with the members of MHB for having treated the problem till now in poor way and I'll try to repair...

In order to avoid confusion we search first all the polynomials of 5-th degree that are divisible by $\displaystyle x^{2} - x +1$ and have coefficients in $\displaystyle \{1,2,3,4,5,6,7,8\}$. To do that let's start from the coefficient relation about that it seems not to be disagreement among us...

$\displaystyle (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\\pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Because $\displaystyle e^{i\ \frac{\pi}{3}}$ is a root of $\displaystyle x^{2} - x +1$, the equation (1) will be satisfied for...

$\displaystyle a_{2}-a_{5} = a_{4}-a_{1}= a_{0}-a_{3}= 0, \pm 1, \pm 2,...,\pm 7$ (2)

'Taking it easy' in little time You 'discover' [unless some more errors of me.(Wasntme)..] that the whole number of polynomial divisible by $x^{2} - x +1$ is...

$\displaystyle n= 8^{3} + 2\ \sum_{k=1}^{7} (8-k)^{3}= 2080$ (3)

Now to proceed we have to clarify what means 'with distinct coefficients' in the original post...

Kind regards

$\chi$ $\sigma$

 

[Opalg]

On the assumption that the coefficients $a_0,\, ..., a_5$ must all be different, chisigma's equation (2) is a good way to formulate the key condition, namely

$ a_{2}-a_{5} = a_{4}-a_{1}= a_{0}-a_{3}= k$, where $k\in \{0, \pm 1, \pm 2,...,\pm 7\}.$​

Clearly there are no solutions for $k=0$ (because then some of the coefficients would have to be equal). When $k=1$, the possible values for each of the pairs $(a_2,a_5),\,(a_4,a_1),\,(a_0,a_3)$ are $(2,1),\,(3,2),\,(4,3),\,(5,4),\,(6,5),\,(7,6),\,(8,7).$ I counted 10 possible ways to select three of those pairs comprising six different numbers. For each such triple there are 3!=6 ways to assign them to the three pairs $(a_2,a_5),\,(a_4,a_1),\,(a_0,a_3)$, giving a total of 60 solutions to (2) with $k=1.$ There are also 60 solutions for $k=-1$. So 120 solutions for $k=\pm1.$

Similar computations give 72 solutions for $k=\pm2$, 48 solutions for $k=\pm3$ and also for $k=\pm4$, 12 solutions for $k=\pm5$ (and none for $k=\pm6$ or $\pm7$). That gives a grand total of $\boxed{300}$ solutions for the problem. (I'll be interested to see if the Captain's computer tally agrees with that!)

 

[CaptainBlack]

As promised, a direct count give an answer of 300.

>function CountDiv()
$
$  global I;
$
$  count=0;
$  OKs=0;
$  r1=0.5*(1+sqrt(3)*I);
$  r2=0.5*(1-sqrt(3)*I);
$  arry1=1:8;
$
$  for idx1=1 to 7
$    for idx2=idx1+1 to 8
$      aa=nonzeros(arry1!=idx1);
$      arry2=arry1(aa);
$      aa=nonzeros(arry2!=idx2);
$      arry2=arry2(aa);
$
$      for jdx=1 to fak(6)-1
$        count=count+1;
$        c1=polyval(arry2,r1);
$        if c1~=0
$           c2=polyval(arry2,r2);
$           if c2~=0
$              OKs=OKs+1;
$           endif
$        endif
$        arry2=next(arry2);
$      end
$    end
$  end
$  
$  return {count, OKs}
$  endfunction

>{C,O}=CountDiv;[C,O]
        20132           300

CB