Fix two positive integers $k$ and $N$. Let $a = (a_{1},a_{2},\dots,a_{N})$ be a weak composition of $k$ into $N$ parts. In other words, $a$ is an $N$ dimensional vector of nonnegative integers such that $\sum_{\ell=1}^N a_{\ell} = k$.
For any weak composition $a$, define $$P_{a}(\{X_{i,\ell}\}) = \prod_{i=1}^k\sum_{\ell=1}^N a_{\ell}X_{i,\ell},$$ which is a polynomial with integer coefficients over the set of formal variables $\{X_{i,\ell}\}_{i \in [k],\ell \in [N]}$.
There are $\binom{N+k-1}{k}$ different polynomials $P_a(\{X_{i,\ell}\})$, one for every possible weak composition $a$.
Let $d \leq k$ be some fixed positive integer. Consider all distinct products of exactly $d$ of these polynomials, allowing for repetition.
More precisely, for any size $d$ multiset $\{a^{(1)},a^{(2)},\dots,a^{(d)}\}$ where each $a^{(j)}$ is a weak composition, the corresponding product is $$Q_{a^{(1)},a^{(2)},\dots,a^{(d)}}(\{X_{i,\ell}\}) = P_{a^{(1)}}(\{X_{i,\ell}\})P_{a^{(2)}}(\{X_{i,\ell}\})\cdots P_{a^{(d)}}(\{X_{i,\ell}\}).$$
Note that there are $$\binom{\binom{N+k-1}{k}+d-1}{d}$$ possible polynomials $Q_{a^{(1)},a^{(2)},\dots,a^{(d)}}(\{X_{i,\ell}\})$, corresponding to all possible size $d$ multisets over the $\binom{N+k-1}{k}$ weak compositions.
My question is: When $d \leq k$, are all the $Q_{a^{(1)},a^{(2)},\dots,a^{(d)}}(\{X_{i,\ell}\})$ polynomials linearly independent?
There are no other restrictions on $N,d,k$ except that they are all positive integers.
Any help would be greatly appreciated!
Some notes:
The motivation is to justify Assumption 1 in https://eprint.iacr.org/2017/946.pdf, a paper which attempts to build secure cryptographic multilinear maps. In that paper, the $X_{i,\ell}$'s actually correspond to matrices (with dimensions chosen so that the above products still evaluate to a scalar). A proof of the above would show that there are no degree $d\leq k$ polynomials that "annihilate" the $P_a$ polynomials over the $\{X_{i,\ell}\}$ formal variables.
If we attempt to count the number of possible monomials that can have distinct coefficients, I believe we get $\binom{\binom{N+d-1}{d}+k-1}{k}$. This should give an upper bound on the number of linearly independent $Q$ polynomials. When $d > k$, the number of polynomials exceeds this value, which is why I think $d \leq k$ is required.
I believe the $d=1$ case is implied by this result: http://epubs.siam.org/doi/pdf/10.1137/S0895479800369141 (they show that when $X_{i,\ell}$ is replaced by $X_{\ell}$, that the resulting $Q$ polynomials are linearly independent).
Edit: I've checked all small cases in Mathematica that my computer can handle and this claim seems to hold true. For example, when $k=3,N=3,d=3$ this produces 220 linearly independent polynomials, and when $k=4,N=3,d=3$ it produces 680 linearly independent polynomials.