Submodules of $({\mathbb Z}/6{\mathbb Z})^n$ intersecting $\{0,1\}^n$ trivially

Question

$\newcommand{\F}{{\mathbb F}}$ $\newcommand{\Z}{{\mathbb Z}}$

Suppose that $\F$ is a finite field of prime order $p:=|\F|$, and let $n$ be a positive integer. I consider the regime where $\F$ is fixed and $n$ grows. Assuming for simplicity that $n$ is divisible by $p-1$, the linear subspace $V<\F^n$ determined by the equations $$ x_1+\dotsb+x_{p-1}=x_p+\dotsb+x_{2p-2}=\dotsb=x_{n-p+2}+\dotsb+x_n=0 $$ has dimension $\dim V=\big(1-\frac1{p-1}\big)n$ and does not contain any zero-one vector with the obvious exception of the vector $(0,\dotsc,0)$. On the other hand, any subspace $V\le\F^n$ of dimension $d>\big(1-\frac1{p-1}\big)n$ must contain such a vector. To see this, one can choose $n-d$ homogenous linear forms $L_1,\dotsc,L_{n-d}$ such that $V$ is determined by the equations
$$ L_j(x_1,\dotsc,x_n)=0,\ j=1,\dotsc,n-d $$ and apply the Chevalley-Warning theorem to the polynomials $L_j(x_1^{p-1},\dotsc,x_n^{p-1})$. The sum of the degrees of these polynomials is $(n-d)(p-1)$, which is strictly smaller than $n$ (the number of variables) if $d>\big(1-\frac1{p-1}\big)n$; in this case the polynomials are guaranteed to have a non-zero common root $(x_1,\dotsc,x_n)\in\F^n$, and then the zero-one vector $(x_1^{p-1},\dotsc,x_n^{p-1})$ lies in $V$.

How different is the situation where the field $\F$ gets replaced with a ring, like $\Z/6\Z$?

What is the largest possible size of a submodule $V<(\Z/6\Z)^n$ that does not contains any zero-one vector, save for the vector $(0,\dotsc,0)$?

The construction above shows that one can have $|V|=6^{(4/5)n}$ while $V\cap\{0,1\}^n=\{0\}$; is this best possible?

A very basic upper bound can be obtained by observing that if $V\cap\{0,1\}^n=\{0\}$ and $e_1,\dotsc,e_n$ form the "standard basis'' of $(\Z/6\Z)^n$, then $V,e_1+V,e_1+e_2+V,\dotsc,e_1+\dotsb+e_n+V$ are pairwise disjoint; hence $|V|\le 6^n/(n+1)$.

A version of the problem with a non-orthodox notion of size:

How large must an integer $d$ be to ensure that if $V_2\le\F_2^n$ and $V_3\le\F_3^n$ are linear subspaces with $\dim V_2+\dim V_3\ge d$, then there is a non-zero integer vector $x\in\{0,1\}^n$ satisfying $x\!\pmod 2\in V_2$ and $x\!\pmod 3\in V_3$?

$\ $

---

Curiously, it is easy to determine precisely the largest possible size of a submodule $V<(\Z/6\Z)^n$ such that $V$ has a trivial intersection with the set $\{0,\pm 1\}^n$. Namely, for any such submodule $V$, every element of $(\Z/6\Z)^n$ has at most one representation as a sum of an element from $V$ and an element from $\{0,1\}^n$. Consequently, $|V|\cdot|\{0,1\}^n|\le|(\Z/6\Z)^n|$; that is, $|V|\le 3^n$. On the other hand, $V:=\{0,2,4\}^n$ intersects $\{0,\pm1\}^n$ trivially, showing that the bound $|V|\le 3^n$ is sharp.

Also, it is easily seen that if $V<(\Z/6\Z)^n$ has a trivial intersection with $\{0,3\}^n$, then $|V|\le 3^n$. As a slightly more difficult exercise, if $V<(\Z/6\Z)^n$ has a trivial intersection with $\{0,2\}^n$ (equivalently, has a trivial intersection with $\{0,4\}^n$), then $|V|\le(2\sqrt 3)^n$. Thus, only the problem where $V\cap\{0,1\}^n=\{0\}$ remains open.

Answer 1

A better upper bound of $5^n$ can be obtained via Haemer's upper bound for the Shannon capacity, applied to the Sperner capacity of a suitable directed graph, along the lines of Croot-Lev-Pach. As $6^{4/5} = 4.193$, this closes a significant chunk of the gap between the upper bound and the lower bound, though by no means all of it.

The method is to observe that, for such a $V$, $$\left\{x,y \in V \mid x-y \in \{0,1\}^n \right\} = \left\{x,y \in V \mid x=y\right\}$$ so the matrix $M$ whose entry $M_{x,y}$ is $0$ if $(x-y) \not\in \{0,1\}^n$ and is $(-1)^{ \sum_i (x_i - y_i)}$ otherwise is equal to the identity matrix when restricted to $V \times V$. Thus the cardinality of $V$ is at most the rank of $M$. Because $M$ is the $n$-fold tensor product of a rank $5$ matrix, its rank is $5^n$, so $|V| \leq 5^n$.

All the exponential loss in this argument comes from the first step where we drop the condition that $V$ is a subspace and remember only that $\{x,y \in V \mid x-y \in \{0,1\}^n\} = \{x,y \in V \mid x=y\}$. The upper bound of $5^n$ on $V$ satisfying this weaker condition is sharp up to a subexponential factor, as can be demonstrated by the set of vectors in $\{0,1,2,3,4\}^n$ that sum to $2n$, which satisfies that condition and has size $\sim 5^n / \sqrt{n}$.