The number of non-homogeneous lattice points in subsets of R^n

NEW

Problem: Reconstructed statement: for $n,m\ge1$, let $\phi(n,m)$ be the minimum size of a finite set $S\subset \mathbb Z^n$ meeting every coset $a+L$ of every index-$m$ sublattice $L\le \mathbb Z^n$; equivalently, every determinant-$m$ subgrid of the standard grid. Barnes--Mather’s Conjecture 1 asserts

$$\phi(n,m)=n(m-1)+1.$$

This matches their grid terminology $AZ^n+c$ and the standard finite blocking-set reduction.

Result: The conjecture is false. In fact $\phi(3,4)\le 8<10=3(4-1)+1$.

Work in $G=(\mathbb Z/4\mathbb Z)^3$. Let

$$B=\{(0,0,2),(0,0,3),(0,1,2),(2,1,1), (1,2,2),(3,0,3),(1,1,0),(1,3,3)\}.$$

We show that $B$ meets every coset of every index-$4$ subgroup of $G$.

Each index-$4$ quotient of $G$ is either $C_4$ or $C_2^2$. If the quotient is $C_2^2$, its kernel contains $2G$. Since $B$ contains exactly one point in each parity class modulo $2$, it meets every coset.

For a cyclic quotient, the cosets are fibres of a primitive linear form

$$\ell(x,y,z)=ax+by+cz\pmod 4,$$

with at least one of $a,b,c$ odd. Write $a,b,c=\alpha+2\beta$, where $\alpha\in\mathbb F_2^3\setminus\{0\}$, $\beta\in\mathbb F_2^3$. The set $B$ can be written as

$$B=\{p+2f(p):p\in\mathbb F_2^3\},$$

where

$$f(x,y,z)=(xz+yz,\ x+xz+xy,\ 1+yz+xy).$$

A direct substitution gives

$$\ell(p+2f(p))\equiv t+2\bigl(\beta\cdot p+h_\alpha(p)\bigr)\pmod4, \quad t=\alpha\cdot p,$$

with

$$h_\alpha(p)=\sum_{i<j}\alpha_i\alpha_jp_ip_j+\alpha\cdot f(p).$$

For the seven nonzero $\alpha$, the weights of $h_\alpha$ on the two planes $\alpha\cdot p=0,1$ are

$$\begin{array}{c|ccccccc} \alpha&001&010&011&100&101&110&111\\ \hline t=0&3&1&3&1&3&1&3\\ t=1&3&1&3&1&3&3&3 \end{array}$$

all odd. Adding the affine function $\beta\cdot p$ cannot make the restriction constant on a four-point affine plane, since affine functions there have even weight. Hence for each $t=0,1$, both possible second bits occur, so $\ell(B)=\mathbb Z/4\mathbb Z$. Thus $B$ meets every cyclic index-$4$ coset as well.

Lift $B$ to the same eight representatives in $\mathbb Z^3$. If $L\le\mathbb Z^3$ has index $4$, then $4\mathbb Z^3\subseteq L$, so reduction mod $4$ gives an index-$4$ subgroup of $G$. Since $B$ meets every coset modulo $4$, the lifted set meets every coset of $L$. Therefore $\phi(3,4)\le8$, contradicting the conjectured value $10$.

Citation: No known published citation is used for this counterexample. Context: E. S. Barnes and Michael Mather, “The number of non-homogeneous lattice points in subsets of $R^n$,” Math. Proc. Cambridge Philos. Soc. 82 (1977), 265–268, doi:10.1017/S0305004100053883.