14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Mar 1 '17 at 13:49
  • $\begingroup$ @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$!) $\endgroup$ – Seva Mar 1 '17 at 14:34
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Mar 1 '17 at 15:52
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 :-) $\endgroup$ – Dima Pasechnik Feb 28 '17 at 11:29
  • 1
    $\begingroup$ $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). $\endgroup$ – Fedor Petrov Feb 28 '17 at 11:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Fedor Petrov Feb 28 '17 at 11:34
  • 1
    $\begingroup$ @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? $\endgroup$ – Will Sawin Feb 28 '17 at 16:30
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Will Sawin Feb 28 '17 at 16:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.