Let $\left( Y_x \right)_{x=0}^\infty $ be a sequence of finite subsets of $\mathbb{Z}$, and let $G : \mathbb{N}_0 \to \mathbb{N}_0$ be a greedy permutation, defined by

$$ G(x) = \operatorname{mex} \left( \left\{ G(x') | x' < x \right\} \cup Y_x \right) ,$$ where $\operatorname{mex}$ is the minimum excluded operator. Such permutations appear as Sprague-Grundy functions in the study of certain combinatorial games like Nim and Wythoff's Game.

Dress, Flammenkamp and Pink showed that if $\left( Y_x \right)$ is additively periodic, then $G$ also becomes additively periodic. That is, if there exists $p \in \mathbb{N}_1$ such that $Y_{x+p} = Y_x + p$ for all $x \in \mathbb{N}_0$, then there exists $\overline{p} \in \mathbb{N}_1$ such that $G(x+ \overline{p} ) = G(x) + \overline{p}$ for all sufficiently large $x$. A simple proof of this is given by Landman.

Question: What is the best bound for $\overline{p}$ in terms of $p$, if we know $\overline{M} = \max_{x \in \mathbb{N}_0} (Y_x - x)$ and $\underline{M} = \min_{x \in \mathbb{N}_0} (Y_x - x)$ ?

The proof by Landman gives $\overline{p} \leq 2^{\overline{M} + \underline{M} + 2 } p$, and the original proof gives $\overline{p} \leq \binom{| \underline{M}| + \overline{M} + 2}{ \min \left( | \underline{M} - 1 |, \overline{M} + 1 \right) } p$. I believe I can show that $\overline{p} \leq K_{\underline{M},\overline{M} } \: p$, where

$$ K_{\underline{M} , \overline{M} } \to \exp \left( \sqrt{ \operatorname{Li}^{-1} \left( |\underline{M} | + \overline{M} \right) } \right) \quad \mathrm{as} \quad \underline{M} \to -\infty , \overline{M} \to \infty .$$ Here, $\operatorname{Li}$ is the logarithmic integral.

Is this a known result, and do improved bounds exist?

(Disclaimer: I am an amateur matematician, and I have no opportunities to ask other matematicians in person, which is why I'm asking here.)

Thanks in advance!


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.