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


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.

• If $V$ has an element $v$ in $\{0,-1\}^n$ then in has one in $\{0,1\}^n$, as $5v\in\{0,1\}^n$. So you already have a sharp bound, and I don't see how your construction of a supposedly bigger set can work, save for the case your submodule is not an additive group. – Dima Pasechnik Mar 1 '17 at 13:49
• @DimaPasechnik: It is certainly true that $V\cap\{0,1\}^n=\{0\}$ is equivalent to $V\cap\{0,-1\}^n=\{0\}$, but I do not understand what conclusion you derive from it; could you explain? (Please, notice BTW that $\{0,\pm1\}^n$ does not split into the union of $\{0,1\}^n$ and $\{0,-1\}^n$!) – Seva Mar 1 '17 at 14:34
• I am puzzled by Will's construction, where certain non-symmetry has crept in. Indeed, you are right that $\{0,\pm 1\}$ does not split into 2 parts, and I withdraw the claim that you have a sharp bound, sorry about this. – Dima Pasechnik Mar 1 '17 at 15:52

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}$.
• It would be good to explain why $M$ is the $n$-fold tensor product, and of which matrix $A$. Then indeed one could think of $A$ as some kind of graph, and talk about its Shannon capacity, which is indeed related to taking tensor products of copies of $A$... Or perhaps I completely miss the point :-) – Dima Pasechnik Feb 28 '17 at 11:29
• $M$ is an $n$-fold tensor power of the $6\times 6$-matrix $M$ corresponding to $n=1$ (which has 0 sum in every row, thus rank at most 5, actually exactly 5). – Fedor Petrov Feb 28 '17 at 11:32
• @Seva Croot-You-Pach method works due to the fact that we have many trivial arithmetic progressions, and here we have many trivial differences equal to 0 (and therefore belonging to $\{0,1\}^n$). These trivial solutions without non-trivial solutions force the rank of corresponding tensor be quite large, on the other hand it is small. – Fedor Petrov Feb 28 '17 at 11:34
• @DimaPasechnik Yes, the problem for which $5^n$ is the sharp upper bound is the Shannon capacity of some directed graph (the 6-cycle). Maybe since Shannon capacity is defined only for graphs, it should be called directed Shannon capacity? – Will Sawin Feb 28 '17 at 16:30
• @Seva Specifically the proof is supposed to be analogous to Lemma 1 of your paper, with the polynomial function $P(x-y)$ replaced with $M_{x,y}$. – Will Sawin Feb 28 '17 at 16:41