GCD divisibility conjecture for drop functions of the Novelli–Pak–Stoyanovskii algorithm

At least 12 years old · documented by

Let n∈Nn\in{\mathbb N}, let λ\lambda be a partition of nn, and let U∈SYT⁡(λ)U\in\operatorname{SYT}(\lambda) be such that the corresponding Novelli–Pak–Stoyanovskii algorithm is uniformly distributed. Let dU(a,x)d_U(a,x) denote the associated drop function for 1≤a≤n1\leq a\leq n and x∈λx\in\lambda. GCD divisibility conjecture. One has

n!lcm⁡{1,…,n}⋅gcd⁡{dU(a,x):  1≤a≤n,x∈λ}∈N.\frac{n!}{\operatorname{lcm}\{1,\dots,n\}\cdot\operatorname{gcd}\{d_U(a,x):\;1\leq a\leq n,x\in\lambda\}}\in{\mathbb N}.

The conjecture was motivated by computer experiments for row-wise Novelli–Pak–Stoyanovskii algorithms on small partitions, and generalizes the equality established in the paper for the one-row shape. Its status is not resolved in the supplied text.

References

Primary source

Christoph Neumann and Robin Sulzgruber, “A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm”, arXiv:1306.5134 (2016).

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.