1
$\begingroup$

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!

$\endgroup$

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.