← All problems

The rational-strategy conjecture for lattice games

16 years old · documented by

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 P\mathcal{P} 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
  1. Let a lattice game have winning positions WW and let

    fW(t)=∑w∈Wtwf_W(\mathbf{t})=\sum_{w\in W}\mathbf{t}^w

    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
  1. Alan Guo and Ezra Miller, “Lattice point methods for combinatorial games”, arXiv:0908.3473 (2009).

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.