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

NEW

Problem: Reconstructed Barnes–Mather Conjecture 2: for $n,m\ge1$, let $B(n,m)$ be the minimum size of a subset $S\subset(\mathbb Z/m\mathbb Z)^n$ meeting every coset of every index-$m$ subgroup. Equivalently, $S$ blocks every determinant-$m$ finite subgrid/hyperplane. The conjecture asserts

$$B(n,m)=n(m-1)+1 .$$

This matches the paper’s grid terminology and the finite blocking-set formulation underlying the prime-$m$ Jamison/Brouwer–Schrijver result.

Result: The conjecture is false. For $(n,m)=(3,4)$, the conjectured value is $3(4-1)+1=10$, but $B(3,4)\le8$.

Let $G=(\mathbb Z/4\mathbb Z)^3$, and set

$$S=\{(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 $S$ meets every coset of every index-$4$ subgroup of $G$.

If $H\le G$ has quotient $G/H\cong C_2^2$, then $2G\subset H$. The set $S$ contains exactly one representative of each parity class modulo $2$, hence it meets every coset of $H$.

If $G/H\cong C_4$, then $H=\ker \ell$ for a primitive linear form

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

with at least one of $a,b,c$ odd. Write $a,b,c=\alpha+2\beta$, with $\alpha\in\mathbb F_2^3\setminus\{0\}$, $\beta\in\mathbb F_2^3$. The set $S$ is

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

where

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

A direct calculation gives

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

where

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

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

$$\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}$$

Thus $h_\alpha$ has odd weight on each plane. Adding the affine function $\beta\cdot p$ cannot make its restriction constant, since affine Boolean functions on a four-point affine plane have even weight. Therefore, on each plane $\alpha\cdot p=t$, both second-bit values occur. Hence $\ell(S)=\mathbb Z/4\mathbb Z$.

So $S$ meets every fibre of every primitive $\ell$, and therefore every coset of every cyclic-index-$4$ subgroup. Combining the two quotient types, $S$ blocks all index-$4$ cosets. Hence

$$B(3,4)\le |S|=8<10,$$

contradicting Barnes–Mather’s formula.

Citation: No published citation is used for this counterexample. Original conjecture 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.