1
$\begingroup$

Conjecture: If $A$ is a nonempty, finite set with size $|A|=n$, and $$P_A(x)=\prod_{a\in A}(x-a),$$ then $P_A(x)$ can be expanded as $$P_A(x)=\sum_{k=0}^{n}(-1)^{n-k}x^k\sum_{{U\subseteq A}\atop{|U|=n-k}}\prod_{u\in U}u.\tag{1}$$

I have conjectured this based on algebraic evidence. That is, I expanded out the cases $n=1,...,4$ both manually and through $(1)$, and in each case the conjecture held. The problem is, I'm having difficulty proving this result. I'm fairly certain that a proof would involve induction, but I'm not very good at that, and have so far failed.

I was initially interested in this formula because I recognized that $(1)$ would imply that $$k\ne0,n\iff \sum_{{U\subseteq S_n}\atop{|U|=k}}\prod_{u\in U}u=0\tag{2}$$ for $$S_n=\left\{\exp\frac{2\pi ik}{n}:k=0,1,...,n-1\right\}.$$ It may seem un-intuitive at first, but $(2)$ is true because $$P_{S_n}(x)=x^n-1,$$ (as $S_n$ is the set of roots of $x^n-1$) so each term of the expansion must vanish except for the cases $k=0,n$.

After seeing this, I was naturally curious about a proof of $(1)$. Could I have some help or hints? Thanks.

$\endgroup$
  • 1
    $\begingroup$ The relation between product of linear factors and the polynomial written as a sum of powers goes by the name of Vieta's formulas $\endgroup$ – Winther Jun 24 at 0:09
2
$\begingroup$

Yes, you have discovered the elementary symmetric polynomials and their relationship with the coefficients of a given polynomial (see Section 3, Properties, at the link above).

$\endgroup$
  • $\begingroup$ Thank you for that nice link, do you have a proof to go along with it? $\endgroup$ – clathratus Jun 24 at 0:09
  • 1
    $\begingroup$ Just search the web or check university-level algebra books—it's a fundamental and well-known enough fact that you'll find proofs everywhere. (There are two references at that link, for that matter.) $\endgroup$ – Greg Martin Jun 24 at 0:11
  • $\begingroup$ With all due respect, if it's so fundamental and well-known, then you shouldn't have any trouble typing it up right now, should you? Again, I do not mean to be rude, but I feel that when someone asks an (at least decent) question on MSE, they deserve a complete, thorough answer. I asked for a proof, not a link to a Wikipedia page which just restates my conjecture in a slightly different way. $\endgroup$ – clathratus Jun 24 at 0:20
  • $\begingroup$ You may not mean to be rude, but not being willing to search on your own and expecting Greg Martin to lay it all out for you is rather rude. $\endgroup$ – The Count Jun 24 at 1:17
  • 1
    $\begingroup$ Fundamental and well known does not necessarily mean easy to write up. $\endgroup$ – Robert Shore Jun 24 at 1:44

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.