## Nontrivial algorithm to check for polynomial symmetry?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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!

-

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 2011 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 2011 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 2011 at 14:01

## 2 Answers

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

-

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

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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 2011 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 2011 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 2011 at 10:34
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9225401282310486, "perplexity_flag": "middle"}