Skip to main content
added 62 characters in body
Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

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

A better upper bound of $5^n$ can be obtained via Haemer's upper bound for the Shannon capacity, 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}$.

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

Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

A better upper bound of $5^n$ can be obtained via Haemer's upper bound for the Shannon capacity, 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}$.