I'm taking the product of a specific set of polynomials of idempotent variables and want to find a shortcut for counting groups of homogeneous coefficients without performing all the calculations.

The polynomials in question are laid out in this question Properties of this algebra with idempotent expressions

An example: $(x_1+x_2-x_1x_2)(x_3+x_4-2x_3x_4)$ expands out to give:

$x_1x_3+x_1x_4-2x_1x_3x_4 + x_2x_3+x_2x_4-2x_2x_3x_4 - x_1x_2x_3 - x_1x_2x_4 + 2x_1x_2x_3x_4$

If I then group the terms by homogeneity I get:

$(x_1x_3 + x_1 x_4 + x_2x_3 + x_2 x_4) + (-x_1x_2x_3-x_1x_2x_4-2x_1x_3x_4-2x_2x_3x_4) + (2x_1x_2x_3x_4)$

I am interested in the sums of these coefficients. So for $2$ variables, the sum is $4$, for $3$ variables the sum is $-6$ and for 4 variables the sum is $2$.

So in summary I want a way to go from $(x_1+x_2-x_1x_2)(x_3+x_4-2x_3x_4) \mapsto \pmatrix{0 \\ 0 \\ 4 \\ -6 \\ 2}$

I know that the product of the sum of the coefficients in the factors is equal to the sum of the coefficients in the product: e.g. $(2x+3)(3x+4) = 6x + 17x + 12$

$(2+3)(3+4) = 6+17+12$

but I can't see how I can use this, or if it is even possible. I've also considered that multi-nomial coefficients may come into it, but again couldn't see how.

Another example to highlight the idempotency.

$(x_1+x_2-x_1x_2)(x_2-x_2x_3)$ becomes

$x_1x_2 + x_2 -x_1x_2 -x_1x_2x_3 - x_2x_3 +x_1x_2x_3$

Which simplifies to $x_2 - x_2x_3$ yielding $\pmatrix{ 0 \\ 1 \\ -1\\ 0}$


First, setting all variables to $0$ gives you the constant term.

Now proceed inductively: assume that you know the first $k$ terms (i.e. up to the homogeneous part of degree $k-1$) and call $P_k$ the polynomial truncated to the first $k$ terms. $P_k$ is a polynomial in one variable, where the coefficients are your sums. Set all variables to be equal to $\varepsilon$, divide the whole thing by $\varepsilon^k$, subtract $\frac{P_k(\varepsilon)}{\varepsilon^k}$, and have $\varepsilon$ tend to $0$. The limit is the next sum.

In your example: $(x_1+x_2-x_1x_2)(x_3+x_4-2x_3x_4)$ assume that you know that there are no parts of degree $0$ or $1$, and that the sum of degree $2$ is $4$. Then $$\lim_{\varepsilon\to 0}\left(\frac{(2\varepsilon-\varepsilon^2)(2\varepsilon-2\varepsilon^2)}{\varepsilon^3}-\frac{4\varepsilon^2}{\varepsilon^3}\right)=-6$$ is your next term.

  • $\begingroup$ would this run in polynomial time? $\endgroup$ Dec 3 '19 at 13:41
  • $\begingroup$ @BenCrossley I don't know how you evaluate the complexity of computing a limit, but my guess is that it's not that bad. $\endgroup$ Dec 3 '19 at 13:42
  • $\begingroup$ I'm still trying to wrap my head around how this works. If I can make sense of it I will upvote and accept. $\endgroup$ Dec 3 '19 at 13:44
  • 1
    $\begingroup$ @BenCrossley Look at what your polynomial becomes when you replace every variable by $\varepsilon$: $4\varepsilon^2-6\varepsilon^3+2\varepsilon^4$. That's essentially your list of coefficients. To get the $\varepsilon^3$ part, delete the previous ones, divide by $\varepsilon^3$, and have $\varepsilon$ tend to $0$. $\endgroup$ Dec 3 '19 at 13:49
  • 1
    $\begingroup$ @BenCrossley Oh! Right, I missed that part. But it would be more clear if your worked example featured this. Right now it's just one word buried at the beginning of the introduction. $\endgroup$ Dec 3 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.