The rational-strategy conjecture for lattice games
A lattice game is a game played on a set of lattice points in a polyhedron, with a finite compatible rule set determining its winning and losing positions. For a lattice game, let denote the set of P-positions, and let its generating function be the corresponding formal power series. A rational strategy is a rational generating function for the set of P-positions.
Rational-strategy conjecture. Every lattice game possesses a rational strategy; equivalently, the generating function for its P-positions is a ratio of polynomials with integer coefficients.
A rational strategy gives algorithms for recognizing P-positions and N-positions and for computing a legal move to a P-position from any N-position; the paper notes that examples and heuristic arguments motivate the conjecture, but does not establish it in general.
Equivalent formulations
Let a lattice game have winning positions and let
be their generating function. A rational strategy is such a generating function expressible as a ratio of polynomials with integer coefficients. The rational strategy conjecture. Every lattice game has a rational strategy. This conjecture asks for a compact algebraic encoding of winning positions and strategies; the source gives no evidence of a resolution.
source: Ezra Miller, “Theory and applications of lattice point methods for binomial ideals”, arXiv:1009.2823 (2010).
References
- Alan Guo and Ezra Miller, “Lattice point methods for combinatorial games”, arXiv:0908.3473 (2009).
Progress summary
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.