Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  Qiaochu Yuan Dec 2 '11 at 18:00
    
@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. –  David Harris Dec 2 '11 at 18:11
    
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. –  Marc van Leeuwen Dec 3 '11 at 14:01

2 Answers 2

up vote 8 down vote accepted

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

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

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.

share|improve this answer
    
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... –  Igor Rivin Dec 2 '11 at 21:02
    
@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. –  Jacques Carette Dec 2 '11 at 21:40
    
@Jacques: yes, you are right. I was thinking of polynomials represented as black boxes or straight line programs, or?! –  Igor Rivin Dec 3 '11 at 10:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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