Monic Binary Polynomials

There are only $8$ possible cubic monic binary polynomials: $x^3$ , $x^3 + 1$ , $x^3 + x$ , $x^3 + x + 1$ , $x^3 + x^2$ , $x^3 + x^2 + 1$ , $x^3 + x^2 + x$ , and $x^3 + x^2 + x + 1$ . For ease of writing, let $x = 10$ , then the $8$ polynomials are $1000$ , $1001$ , $1010$ , $1011$ , $1100$ , $1101$ , $1110$ , and $1111$ . (Note that these are also the first $8$ binary numbers with a $1$ in front of each one.)

Multiplying any two of the decimal representations above gives the coefficients of the product polynomial. If all the coefficients are all $0$ or $1$ , then the product is also a sextic monic binary polynomial. The following chart shows all the possibilities, and the numbers colored in green represent sextic monic binary polynomials:

The unique sextic monic binary polynomials, in bold above, are represented by $1000000$ , $1001000$ , $1010000$ , $1011000$ , $1100000$ , $1101000$ , $1110000$ , $1111000$ , $1011010$ , $1101100$ , and $1111110$ , which are $x^6$ , $x^6 + x^3$ , $x^6 + x^4$ , $x^6 + x^4 + x^3$ , $x^6 + x^5$ , $x^6 + x^5 + x^3$ , $x^6 + x^5 + x^4$ , $x^6 + x^5 + x^4 + x^3$ , $x^6 + x^4 + x^3 + x$ , $x^6 + x^5 + x^3 + x^2$ , $x^6 + x^5 + x^4 + x^3 + x^2 + x$ , for a total of $\boxed{11}$ unique sextic monic binary polynomials.

I tried doing it without a brute-force enumeration. Here we go:

The two cubic polynomials we multiply cannot have any "collisions" between terms when we expand the product. So the total number of monomials in the two factors must multiply to a number $\le 7,$ the maximum number of terms in the product. Hence one of the cubic divisors is either a monomial or a binomial.

The easiest case is when one divisor is a monomial: there are exactly eight sextic monic binary polynomials divisible by $x^3.$

For the binomial case, there are three divisors to check, $x^3+1, x^3+x,$ and $x^3+x^2.$

For $x^3+1,$ any cubic polynomial with zero constant term will do for the other factor, so there are three new cases: $(x^3+1)(x^3+x), (x^3+1)(x^3+x^2),$ and $(x^3+1)(x^3+x^2+x).$ (The fourth one, $(x^3+1)(x^3),$ has already been counted.)

For $x^3+x,$ the other factor cannot have an $x$ term, and it can't have both an $x^2$ and a constant term. We've already counted $x^3$ and $x^3+1,$ so the only other possible other factor is $x^3+x^2.$ Ah, but $(x^3+x)(x^3+x^2)$ is divisible by $x^3,$ so it has already been counted.

For $x^3+x^2,$ the other factor cannot have an $x^2$ term, and it can't have both an $x$ and a constant term. We've already counted $x^3,$ $x^3+1,$ and $x^3+x$ above, and those are the only other factors possible.

So the total number of unique products is $8+3=\fbox{11}.$

$m=\text{Table}\left[x^i,\{i,3,0,-1\}\right] \Longrightarrow \left\{x^3,x^2,x,1\right\}$

$l=\text{Table}[\text{IntegerDigits}[i,2,4].m,\{i,8,15\}] \Longrightarrow \\ \left\{x^3,x^3+1,x^3+x,x^3+x+1,x^3+x^2,x^3+x^2+1,x^3+x^2+x,x^3+x^2+x+1\right\}$

$\text{zeroOne}=\text{\$\#\$1}=0\lor \text{\$\#\$1}=1\&;$

$\text{Select}[\text{CoefficientList}[\text{Union}[\text{Expand}[\text{Flatten}[\text{Table}[l[[i]] l[[j]], \\ \ \ \{i,8\},\{j,8\}],1]]],x],\text{AllTrue}[\text{\$\#\$1},\text{zeroOne}]\&] \Longrightarrow \\ \left( \begin{array}{ccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right)$

The number of rows in that matrix is 11.

The coefficients in the rows of the matrix above are in $x^0$ to $x^6$ order.