Parity problem for pattern-avoidance sequences

About 11 years old · traced to

For a finite set of permutation patterns F\mathcal{F}, let Cn(F)C_n(\mathcal{F}) denote the number of permutations in SnS_n avoiding all patterns in F\mathcal{F}. Parity problem. The problem of deciding whether

Cn(F)≡0(mod2)C_n(\mathcal{F})\equiv 0\pmod 2

for every n∈Nn\in\mathbb N is undecidable. The authors present this as an open problem extending their undecidability theorem and expect their methods may eventually prove it, although substantially more work is required.

References

Primary source

Scott Garrabrant and Igor Pak, “Pattern avoidance is not P-recursive”, arXiv:1505.06508 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.