Timeline for Submodules of $({\mathbb Z}/6{\mathbb Z})^n$ intersecting $\{0,1\}^n$ trivially
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 23, 2017 at 19:15 | history | edited | Will Sawin | CC BY-SA 3.0 |
added 62 characters in body
|
| Jun 23, 2017 at 16:08 | comment | added | Eric Naslund | @WillSawin: Shannon capacity is the term used for undirected graphs (and hypergraphs). For a directed graph (or hypergraph), it's called the Sperner Capacity. Also, for sets avoiding differences in {0,1}^n, I think this argument appears somewhere in paper of Alon, but I can't seem to find it at the moment. | |
| Mar 1, 2017 at 20:12 | comment | added | Will Sawin | @DimaPasechnik Yeah, that's why I said the bound satisfying this weaker condition (not including being a group) is sharp. | |
| Mar 1, 2017 at 13:54 | comment | added | Dima Pasechnik | As in the comment I added to the question, it's not clear why this non-symmetry is meaningful: if $V$ is a group then it has no non-0 $\{0,1\}^n$ elements iff it has no non-0 $\{0,-1\}^n$ ones. So your bound is sharp for non-group case only. | |
| Feb 28, 2017 at 16:41 | comment | added | Will Sawin | @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}$. | |
| Feb 28, 2017 at 16:30 | comment | added | Will Sawin | @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? | |
| Feb 28, 2017 at 11:34 | comment | added | Fedor Petrov | @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. | |
| Feb 28, 2017 at 11:32 | comment | added | Fedor Petrov | $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). | |
| Feb 28, 2017 at 11:29 | comment | added | Dima Pasechnik | 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 :-) | |
| Feb 28, 2017 at 10:46 | comment | added | Dima Pasechnik | IMHO Will says that the problem at hand is related to finding an upper bound on an additive code of length $n$ in the alphabet {0,1,...,5}. Shannon capacity happens to be related, but not directly, and I don't see how. | |
| Feb 28, 2017 at 10:08 | comment | added | Seva | Thanks, very interesting (though I can recognize neither Shannon capacity nor Croot-myself-Pach in your nice and self-contained three-line argument). | |
| Feb 28, 2017 at 0:01 | history | answered | Will Sawin | CC BY-SA 3.0 |