# Dickson/determinant type polynomial (updated)

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation}

consisting of all products of all non-zero linear forms $a_1x_1+\ldots +a_kx_k$, at most $\ell$ of whose coefficients are non-zero.

Now let \begin{equation} \alpha_j = \sum_{i=0}^{\ell-1}\binom{j-1}{i}, \end{equation}

and

\begin{equation} D_{k,\ell}= \det \begin{pmatrix} x_1^{\alpha_1} & \cdots & x_k^{\alpha_1} \\ \vdots & \vdots & \vdots \\ x_1^{\alpha_k} & \cdots & x_k^{\alpha_k} \end{pmatrix} = \sum_{\sigma \in S_k} x_{\sigma(1)}^{\alpha_1} x_{\sigma(2)}^{\alpha_2}\cdots x_{\sigma(k)}^{\alpha_k}, \end{equation}

where $S_k$ is the symmetric group.

(Note that $\alpha_{1}=1$, and we assume as usual that $\binom{a}{b}=0$ if $a<b$.)

Question: It is a classical fact that $D_{k,\ell}=P_{k,\ell}$ when $\ell =2, k$. Is it true that, for arbitrary $2\leq \ell \leq k$, $D_{k,\ell}$ is $P_{k,\ell}$ plus (possibly) some additional terms?

• I made a small edit to reflect the fact that $a_1 x_1 + \cdots + a_k x_k$ is a linear form, not a monomial. Further, by $\mathbb{Z}_2$ do you mean the $2$-adic integers or the field $\mathbb{F}_2$? – Stanley Yao Xiao Aug 23 '15 at 15:03
• The $a_i$ are all supposed to be in $\left\{0,1\right\}$, right? – darij grinberg Aug 23 '15 at 15:09
• @darijgrinberg: yes, exactly – Fred Aug 23 '15 at 15:16
• If $\ell=1$, then the determinant is $0$ (at least for $k \geq 2$) since all of the $\alpha_j$ are $1$. But $P_{k,\ell} = x_1 x_2 \cdots x_k$. Where am I going wrong? – darij grinberg Aug 23 '15 at 15:19
• @darijgrinberg: Sorry, I forgot the $\ell\geq 2$ -- now corrected. – Fred Aug 23 '15 at 16:56

## 2 Answers

Is this true? Sage disagrees:

P.<a,b,c,d> = PolynomialRing(GF(2))
xs = P.gens()
M = Matrix(P, [[xs[i] ** (1 + binomial(j, 1) + binomial(j,2)) for j in range(4)] for i in range(4)])
M.determinant().factor()


returns

d * c * (c + d) * b * (b + d) * (b + c) * a * (a + d) * (a + c) * (a + b) * (a^3*b + a^2*b^2 + a*b^3 + a^3*c + b^3*c + a^2*c^2 + b^2*c^2 + a*c^3 + b*c^3 + a^3*d + b^3*d + a*b*c*d + c^3*d + a^2*d^2 + b^2*d^2 + c^2*d^2 + a*d^3 + b*d^3 + c*d^3)


This has all the right factors with $1$ or $2$ addends (which is no surprise), but the remaining degree-$4$ factor does not factor further as you want it to. For comparison, the product of the factors with $3$ addends should be

P.prod([P.sum(xs)-r for r in xs])


which is

a^3*b + a*b^3 + a^3*c + b^3*c + a*c^3 + b*c^3 + a^3*d + b^3*d + a*b*c*d + c^3*d + a*d^3 + b*d^3 + c*d^3


Generally, I think you can learn something about these polynomials from: I. G. Macdonald, Schur functions: Theme and variations, Séminaire Lotharingien de Combinatoire 1992, volume 28, page B28a (specifically, the 7th variation, which does not assume much familiarity with the preceding ones). But do not expect explicit formulas beyond the $\ell = 2$ and $\ell = k$ cases.

• @darjinberg: I've updated the question – Fred Aug 24 '15 at 21:14

For a given $\sigma\in S_{k}$, the coefficient of $x_{\sigma(1)}^{\alpha_1} x_{\sigma(2)}^{\alpha_2}\cdots x_{\sigma(k)}^{\alpha_k}$ in $P_{k,l}$ is 1. So $D_{k,l}$ is $P_{k,l}$ plus (possibly) some additional terms.

• Not sure I get your argument. – darij grinberg Aug 25 '15 at 15:02
• I mean you can uniquely construct $x_{\sigma(1)}^{\alpha_1} x_{\sigma(2)}^{\alpha_2}\cdots x_{\sigma(k)}^{\alpha_k}$, in $P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)$ – Moh514 Aug 25 '15 at 16:54
• I still don't get it. – darij grinberg Aug 25 '15 at 17:17