1
$\begingroup$

Hi.

As is known, a polynomial $P \in K[x_1, \dots, x_n]$ is symmetric when permuting its variables always yields the same polynomial. This immediately yields an algorithm $O(n!)$ to check for symmetry of a polynomial.

Are there known algorithms faster than $O(n!)$ (perhaps using other bounds, like the degree) to decide if a polynomial of $n$ variables is symmetric?

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ The algorithm is $O(n!)$ if you can check whether two polynomials are identical in one step, but in general this is not trivial to do for large polynomials. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 2, 2011 at 18:00
  • $\begingroup$ @Qiaochu -- if you allow a one-sided error, then you can check if polynomials are equal by evaluating them at random points. This gives a lot more flexibility and speed than expanding the polynomials and checking them term-by-term. $\endgroup$
    – David Harris
    Commented Dec 2, 2011 at 18:11
  • $\begingroup$ Surely you cannot estimate the running time of the algorithm independently of the size of the polynomial. Also the way it is represented is important. (As extreme cases, if it is given as a polynomial in the elementary symmetric polynomials, the check is trivial; if it is given as a black-box polynomial function, the check is impossible.) Very often the size of an expanded symmetric polynomial will dwarf the number $n!$. Please be more specific. $\endgroup$
    – Marc van Leeuwen
    Commented Dec 3, 2011 at 14:01

2 Answers 2

Reset to default
8
$\begingroup$

One needs only check $n$ transpositions, since if each of the transpositions $(12),(23), \dots$ preserves a polynomial, then every permutation preserves that polynomial.

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ Even less, $S_n$ is generated by two elements, $(12\cdots n)$ and $(12)$. $\endgroup$
    – Ryan Budney
    Commented Dec 2, 2011 at 17:52
  • $\begingroup$ That's a huge speedup, thanks both of you :) $\endgroup$
    – Federico Lebrón
    Commented Dec 2, 2011 at 18:01
5
$\begingroup$

Will Sawin's answer necessitates $n-1$ passes over the polynomial $P$, checking for equality. Ryan's comment to Will's answer brings that down to $2$ passes, but with (somewhat) expensive operations to be done.

You can do it in a single pass with only cheap operations, assuming your polynomial $P$ is given in expanded form in the monomial basis. First, you know that, if it is symmetric, it can be rewritten as a polynomial in the symmetric polynomials. So, march through all the coefficients of $P$, figuring out the 'signature' of each monomial (i.e. set of degrees) you encounter; then make sure that the coefficient for each signature is constant, and that you encounter enough such monomials for each degree. This a linear pass on $P$, and storage $O(m)$ where $m$ is the number of different symmetric polynomials which actually occur in $P$.

Of course, if your polynomial is not presented in expanded form in the monomial basis, the above will not work.

Improve this answer
$\endgroup$
3
  • $\begingroup$ And if it IS presented in expanded form, it is going to be gigantic. The question is of most interest if the polynomial is sparse... $\endgroup$
    – Igor Rivin
    Commented Dec 2, 2011 at 21:02
  • $\begingroup$ @Igor: my 'algorithm' will work especially well in the sparse case. Of course, if it is sparse in a non-monomial basis, or is represented in some other way (say via a straight line program), that would indeed be a problem. But we need the OP to clarify that. $\endgroup$
    – Jacques Carette
    Commented Dec 2, 2011 at 21:40
  • $\begingroup$ @Jacques: yes, you are right. I was thinking of polynomials represented as black boxes or straight line programs, or?! $\endgroup$
    – Igor Rivin
    Commented Dec 3, 2011 at 10:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .