Semilinearity conjecture for nonnegative FDG games

From papers

Let dd be a positive integer and let DZd{\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 xNdx\in\mathbb{N}^{d}, and a move from xx to yy is allowed when xyDx-y\in{\cal D}. Such a game is called an FDG game. Nonnegative FDG semilinearity conjecture. For any FDG game such that ai0a_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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.