MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a permutation $\sigma$ such that for all $x_1,\ldots,x_n$ we have $g(x_1,\ldots,x_n)=h(x_{\sigma(1)},\ldots,x_{\sigma(n)})$.

For function $f(x_1,\ldots,x_n)$ and $1\le i\le n$, define $$f_i(x_1,\ldots,x_n)=f(x_1,\ldots,x_{i-1},-x_i,x_{i+1},\ldots,x_n)$$ (just the $i$-th argument is negated).

Now, you are given the multiset $\mathcal D(f)$ which contains the equivalence classes of $f_i$ for $1\le i\le n$. (I'm calling it a multiset because I don't want you to remove duplicates; $\mathcal D(f)$ has exactly $n$ elements.) Can you determine the equivalence class of $f$?

My question: Has this problem been formulated before? If so, references please!

To show that the question is hard in general, even for polynomials, I'll note that it includes Stanley's unsolved switching reconstruction conjecture for graphs. For a graph $G$ with $n$ vertices and edge set $E$, define $$f(x_1,\ldots,x_n) = \prod_{i<j;~ ij\in E} (1+x_ix_y) \prod_{i<j;~ij\notin E}(1-x_ix_j).$$ Now $f_i$ corresponds to switching $G$ at vertex $i$. It is unknown whether $G$ can be reconstructed from $\mathcal D(f)$ for $n\gt 4$. In the case of $n=4$, there is a counterexample: consider a 4-cycle and the graph with no edges.

The choice of complex numbers was arbitrary; you can consider any domain and range for which the question is meaningful.

Some facts can be determined by the methods used for other reconstruction problems. For example, if $n$ is odd then the equivalence class of $f$ can be reconstructed from $\mathcal D(f)$: it is the only equivalence class occurring an odd number of times in the multiset union of the multisets $\mathcal D(f_i)$. Beáta Faller and I will publish some results on symmetries of non-reconstructible functions. But what is known already?

share|cite|improve this question
It looks like there was supposed to be a link to the Stanley conjecture, but there isn't...? – Allen Knutson Apr 21 '14 at 5:59
Thanks, it is hopefully fixed now. – Brendan McKay Apr 21 '14 at 6:22

Your Answer


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

Browse other questions tagged or ask your own question.