Recognition of Lattice Point Configurations as Convex Ovals

Definitions and mathematical statement

Let $\Lambda\subset{\mathbb{R}}^2$ be a planar lattice, conventionally $\Lambda=B{\mathbb{Z}}^2$ for an invertible real $2\times2$ matrix $B$. Let $S\subset{\mathbb{R}}^2$ be a closed bounded convex region containing $0$. Using the usual positive-scale convention, put \[ S(r,P)=P+rS=\{P+rs:s\in S\},\qquad r>0,\quad P\in{\mathbb{R}}^2, \] and $J(r,P)=\Lambda\cap S(r,P)$. A finite configuration $J\subset\Lambda$ is an $S$-oval in the sense of the supplied question if \[ \exists r>0\ \exists P\in{\mathbb{R}}^2:\qquad J=\Lambda\cap(P+rS). \] Equivalently, all points of $J$ must lie in $P+rS$ and every point of $\Lambda\setminus J$ must lie outside it. Because $S$ is closed, lattice points on its translated scaled boundary are included. Finding a region merely containing $J$, while allowing additional lattice points, is not the stated recognition problem. Only scaling and translation are included; rotations or arbitrary affine changes of $S$ are not introduced.

Determine how efficiently this existence question can be decided for a given finite lattice configuration. The source asks how readily a possible $S$-oval can be identified, rather than providing a numerical time bound. An algorithmic statement requires a representation or oracle for $S$, a representation of $\Lambda$ and the input points, and a computational cost model. It also matters whether $S$ and $\Lambda$ are fixed or part of the input. No smoothness, strict convexity or curvature hypotheses are added to the general source question. Whether zero scales, empty configurations or lower-dimensional regions are allowed needs confirmation.

The supplied literature assessment checked 2026-08-21 labels the problem partially solved. It attributes important smooth convex cases and sharp configuration counts under geometric conditions to Huxley and Zunic; the relevant hypotheses and algorithms are not reproduced in the record. Configuration counting is not silently substituted for the requested recognition problem.

Short English statement

Given finitely many lattice points, decide whether they are exactly the lattice points in some positive dilate and translate of the prescribed convex region. Analyze recognition efficiency once the region representation and computational model are specified.

Sources

• Local UnsolvedMath registry, permanent ID 30000937, source code catalogue entry; supplied complete record. Its corrected-verified note says the complete statement was preserved while notation was delimited.
• Analytic Number Theory (2008), Oberwolfach Reports, DOI 10.4171/owr/2008/14, pp. 669--746: https://doi.org/10.4171/owr/2008/14.
• Huxley and Zunic, configurations II: https://doi.org/10.1112/plms/pdt011.