Skip to main content
1 of 6
Seva
  • 23k
  • 2
  • 59
  • 141

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

$\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 exceeds $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 will things be if the field $\F$ gets replaced with a ring, like $\Z/6\Z$?

What is the largest possible size of a submodule $L<(\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$?

Seva
  • 23k
  • 2
  • 59
  • 141