Parity problem for pattern-avoidance sequences

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 nNn\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.

Sources & referencesView supporting material

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.