Timeline for Spreading $n$ points in $\{0,1\}^n$ as far as possible
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27 at 7:57 | comment | added | Claude Chaunier | @AaronMeyerowitz, as we've found out in this question revival mathoverflow.net/q/477355/127616, there are more options than Hadamard codes, with some distances among members of the set going higher than $\frac{n+1}{2}$, while the minimum distance stays around it of course. | |
| Dec 19, 2020 at 15:05 | comment | added | BD107 | Is this (incredible) answer entirely new to you, or is there a reference? Thanks. | |
| Jan 1, 2019 at 4:10 | history | edited | kodlu | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jan 1, 2019 at 4:09 | comment | added | kodlu | you are right I started letting $m=n$ and changed later. thanks | |
| Jan 1, 2019 at 3:24 | comment | added | Andreas Blass | As far as I can see, the $m^2$ in the rightmost part of the long displayed formula should be $mn$, since each $|u_i|^2$ is $n$, not $m$. Apparently this was just a typo, since the final upper bound on $d$ looks correct. | |
| Dec 31, 2018 at 23:27 | history | edited | kodlu | CC BY-SA 4.0 |
added 83 characters in body
|
| Dec 31, 2018 at 8:41 | comment | added | Aaron Meyerowitz | So $d \leq \frac{n^2}{2(n-1)}=\frac{n+1}2+\frac1{2n-2}$ and, being an integer, for $n \gt 2 $ even, $d=\frac{n}2$ can't be beat. To achieve that (getting a Haddamard code) requires $n$ to be a multiple of $4.$ That may well be sufficient, but is open. For odd $n$ one can't beat $\frac{n+1}2.$ In fact one can , for $n=4m-1$, acheive that with $n+1$ vectors, provided that there is a Haddamard code for $4m:$ puncture it by removing a coordinate where all the words agree. Example: for $n=4,d=2$ use $0000,0011,0101,0110$ for $n=3,d=2$ use $000,011,101,110.$ | |
| Dec 31, 2018 at 8:12 | comment | added | Dominic van der Zypen | Very nice answer, and it's great that you prove the bound is $1/2$! | |
| Dec 31, 2018 at 8:11 | vote | accept | Dominic van der Zypen | ||
| Dec 31, 2018 at 3:42 | history | edited | kodlu | CC BY-SA 4.0 |
added 640 characters in body
|
| Dec 31, 2018 at 0:45 | history | answered | kodlu | CC BY-SA 4.0 |