Semilinearity conjecture for nonnegative FDG games

At least 4 years old · documented by

Let dd be a positive integer and let D⊂Zd{\cal D}\subset\mathbb{Z}^{d} be a finite difference set satisfying

∑i=1dai>0\sum_{i=1}^d a_i>0

for every (a1,…,ad)∈D(a_1,\dots,a_d)\in{\cal D}. The positions are vectors x∈Ndx\in\mathbb{N}^{d}, and a move from xx to yy is allowed when x−y∈Dx-y\in{\cal D}. Such a game is called an FDG game. Nonnegative FDG semilinearity conjecture. For any FDG game such that ai≥0a_i\geq0 for each (a1,…,ad)∈D(a_1,\dots,a_d)\in{\cal D}, the set of P-positions is semilinear. This is proposed as a stronger version of the Exact Slow kk-Nim conjecture because \scNimn,=k1{\sc Nim}^1_{n,=k} has difference vectors with nonnegative coordinates. The contrast with general FDG games, where nonsemilinearity and computational hardness can occur, highlights the role of the nonnegativity assumption.

References

Primary source

Nikolay Chikin, Vladimir Gurvich, Konstantin Knop, Mike Paterson and Michael Vyalyi, “More about Exact Slow k-Nim”, arXiv:2102.03528 (2021).

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.