Revisions - MathOverflow

Return to Answer

Clarified explanation in response to a comment

view source

edited Sep 26 2010 at 14:58

Peter Shor
4,465●22●46

the nonempty vertices. Since sections are equivalent under permutations of the coordinates, we should consider these to be 8 identical elements (so the only thing that matters is how many elements are on a vertex). There are four cases.

fixed minor mistake

view source

edited Sep 26 2010 at 14:51

Peter Shor
4,465●22●46

{$5,6$}, the vertex $\bar{a}\bar{b}\bar{c}$ would contain {$8$}, $4,8$}, and the

added some editorial commentary

view source

edited Sep 26 2010 at 1:58

Peter Shor
4,465●22●46

Here's the answer. The main claims (Claims 1-4) I am fairly sure I got right, but I could easily have missed a case (or counted an extra case) in the later enumeration. If anybody finds a mistake, please comment. Let me remark that I find Claims 1-4 much more interesting than the subsequent enumeration based on them.

hypercube -> cube

view source

edited Sep 25 2010 at 1:38

Peter Shor
4,465●22●46

minor correction

view source

edited Sep 24 2010 at 21:43

Peter Shor
4,465●22●46

fixed minor typos and defined "unexpected"

view source

edited Sep 24 2010 at 21:26

Peter Shor
4,465●22●46

added 3186 characters in body

view source

edited Sep 24 2010 at 21:01

Peter Shor
4,465●22●46

Here's the first half of the answer. I probably won't have time to finish this today, but I will get back to it some time this weekend. The main claims (Claims 1-4) I am fairly sure I got right, but I could easily have missed a case (or counted an extra case) in the later enumeration. If anybody finds a mistake, please comment.

I'll get back We'll deal with the situation in the Claims 1,2,3 separately.

Case of Claim 3with the situation in Claim 3. First, we can assume that there are noempty vertices of the cube other than the two opposite ones (if this happens,we are in the Claim 1 situation, and we take care of it there).

We now can choose another centroid $d$ in the linear span of $a,b,c,e$so that $a \cup b \cup c \cup d$ covers every coordinate exactly twice.By the criterion that there are six non-empty vertices, none of thesix intersections $a \cap b$, $a \cap c$, etc. can be empty. We need toput the eight elements into these six intersections. This correspondsto putting 8 elements on the edges of a simplex so that every edgecorresponds to at least one element. There are 3 ways to do this (twoextra on one edge, one extra on each of two opposite edges, and oneextra on each of two adjacent edges). Claim 3 thus gives 3 morenon-equivalent sections. Notice that if we had analysed Claim 3 by justlooking at the symmetries of the cube (as we did for the cases withoutunexpected centroids), we would have obtained four non-equivalent sections.

Case of Claim 2What I'd like to claim here is that this is really the situation in Claim 1disguised. Maybe the best way to do this is by example. If we have$a=${$1,2,7,8$}, $b=${$3,4,7,8$}, $c=${$5,6,7,8$}, then the centroid {$7,8$}is in our hyperplane, and the hyperplane is thus generated by $a'=${$1,2$}, $b'=${$3,4$},$c'=${$5,6$}, which is covered by Claim 1.

Case of Claim 1Here, there are three possibilities. In the first one, there are fourcentroids $a$, $b$, $c$, $d$, with pairwise empty intersections so that$a \cup b \cup c \cup d =${$1,2,\ldots,8$}. The number of ways of doing thisis the number of partitions of 8 into four non-empty parts, which is 5:{$(5,1,1,1), (4,2,1,1), (3,3,1,1),(3,2,2,1),(2,2,2,2)$}.

In the second possibility, we have three pairwise disjointcentroids $a$, $b$, $c$, with $a \cup b \cup c = e$,and also another centroid $d$ so thatboth $d\cap x$ and $\bar{d} \cap x$ are non-empty for $x=a,b,c$.The cardinalities of $a,b,c$ could be {$4,2,2$} or {$3,3,2$}. In eithercase, we get two non-equivalent sections, giving 4 total non-equivalentsections.

For the third possibility, we have three pairwise disjointcentroids $a$, $b$, $c$, andwe have a fourth and fifth centroid $f$ and $g$ so that $f \cup g = a \cup b$. In this case, the cardinality of $c$ can range from 1 to 4.I'll just list the vectors for these possibilities. The coordinates considered are those not in $c$.

$c=4$

$(1,1,0,0),(0,1,1,0),(0,0,1,1),(1,0,0,1)$

$c=3$

$(1,1,1,0,0),(0,0,1,1,0),(0,0,0,1,1),(1,1,0,0,1)$

$c=2$

$(1,1,1,0,0,0),(0,0,1,1,1,0),(0,0,0,1,1,1),(1,1,0,0,0,1)$

$(1,1,1,1,0,0),(0,0,1,1,1,0),(0,0,0,0,1,1),(1,1,0,0,0,1)$

$(1,1,1,1,0,0),(0,1,1,1,1,0),(0,0,0,0,1,1),(1,0,0,0,0,1)$

$c=1$

$(1,1,1,1,1,0,0),(0,1,1,1,1,1,0),(0,0,0,0,0,1,1),(1,0,0,0,0,0,1)$

$(1,1,1,1,1,0,0),(0,0,1,1,1,1,0),(0,0,0,0,0,1,1),(1,1,0,0,0,0,1)$

$(1,1,1,1,0,0,0),(0,0,1,1,1,1,0),(0,0,0,0,1,1,1),(1,1,0,0,0,0,1)$

$(1,1,1,1,0,0,0),(0,1,1,1,1,0,0),(0,0,0,0,1,1,1),(1,0,0,0,0,1,1)$

This gives 9 more non-equivalent sections, making 49 altogether.

[made Community Wiki]

view source

answered Sep 24 2010 at 19:38

Peter Shor
4,465●22●46

Here's the first half of the answer. I probably won't have time to finish this today, but I will get back to it some time this weekend. Claims 1-4 I am fairly sure I got right, but I could easily have missed a case (or counted an extra case) in the later enumeration. If anybody finds a mistake, please comment.

We'll divide the question into cases.

The first case we deal with is when we have three centroids $a$, $b$, and $c$, which don't generate any other unexpected centroids. We'll represent our centroids as subsets of {$1,2,\ldots,8$}. If we have the centroid {$1,2,3$}$=\langle 1,1,1,0,0,0,0,0\rangle $, then we automatically have the centroid {$4,5,6,7,8$} corresponding to the complement of the set. So the first case consists of hyperplanes which pass through $a,b,c,\bar{a},\bar{b},\bar{c}$, but no other centroids.

Now, let's represent this case by putting the numbers {$1,2,\ldots,8$} on the vertices of a hypercube. The hypercube will have three faces corresponding to $a,b,c$ and the three opposite faces will correspond to $\bar{a},\bar{b},\bar{c}$. For example, if the sets were $a=${$1,2,3$}, $b=${ $1,5,6$} and $c=${$2,5,6,7$}, then the vertex $\bar{a}bc$ would contain {$5,6$}, the vertex $\bar{a}\bar{b}\bar{c}$ would contain {$8$}, and the vertex $\bar{a}b\bar{c}$ would be empty. It's not too hard to see that whether there is an unexpected centroid only depends on the positions of the empty vertices. It's also clear that rotations and reflections of this cube give equivalent sections.

Claim 1: If two adjacent vertices are empty, there is an unexpected centroid.

Proof: The two adjacent vertices form an edge. We might as well rotate the cube so that the empty edge is the $ab$ edge. Then we have $a \cap b = \emptyset$. This means that $a \cup b$ is an unexpected centroid (here we have to use the fact $a \neq \bar{b}$). Example: if $a =${$1,2$}, $b = ${$3,4,5$}, then $a \cup b =${$1,2,3,4,5$} is in the linear span of $a$ and $b$.

Claim 2: If two opposite vertices of the cube are empty, then there is an unexpected centroid.

Proof: We can rotate the cube so the empty vertices correspond to $\bar{a}\bar{b}\bar{c}$ and $abc$. Then, for example, if $a=(1,1,1,0,0,0,0,0)$, $b=(0,0,1,1,1,1,0,0)$ and $c=(1,0,0,0,0,1,1,1)$, we can take $a+b+c-e$ where $e$ is the all-ones vector, and get $(1,0,1,0,0,1,0,0)$.

Claim 3: If the odd- or even-parity vertices of the cube are empty, then there is an unexpected centroid.

Proof: Rotate the cube so that $\bar{a}\bar{b}\bar{c}$ is empty. Now, every coordinate is in exactly 1 or 3 of $a,b,c$. Thus, $\frac{1}{2}(a+b+c-e)$ is an unexpected centroid. Example $a=(1,1,1,0,0,0,1,1)$, $b=(0,0,0,1,1,0,1,1)$ and $c=(0,0,0,0,0,1,1,1)$, and $\frac{1}{2}(a+b+c-e) = (0,0,0,0,0,0,1,1)$

Claim 4: If none of the situations in Claims 1,2,3 hold, then there is no unexpected centroid.

Proof: We can rotate the cube so that the empty vertices are a subset of $\bar{a}bc$, $a\bar{b}c$ and $ab\bar{c}$. For there to be an unexpected centroid, you must be able to find $\alpha a + \beta b + \gamma c$ so that the coordinates of this vector take on two values. One of these coordinates is 0 (since $\bar{a}\bar{b}\bar{c}$ is not empty), meaning we can assume wlog that $\alpha, \beta, \gamma$ are either 1 or 0. But for $\alpha + \beta + \gamma$ to also be either 1 or 0, we need two of $\alpha, \beta, \gamma$ to be 0, which means that we don't get an unexpected centroid.

So now, we need to enumerate the number of ways of putting 8 elements onto the vertices of a unit cube so that at least one element is on each of the nonempty vertices. There are four cases.

Case A: no empty vertices. There is just 1 way of doing this: putting one element on each vertex.

Case B: one empty vertex. There are 3 ways of doing this. Exactly one vertex will have two elements on it, and it can be either Hamming distance one, two, or three from the empty vertex.

Case C: two empty vertices. In this case, these two vertices must have Hamming distance 2. The two extra elements can either be on the same vertex (3 ways) or two different vertices (7 ways).

Case D: three empty vertices. In this case, any pair of these three vertices must have Hamming distance 2, so there's only one way of arranging them. The three extra elements can either be all on the same vertex (3 ways), divided two on one vertex and one on another (7 ways), or on three different vertices (4 ways).

This gives 28 essentially different sections with no unexpected centroids.

We now must count the cases with unexpected centroids corresponding to Claims 1-3. I'll get back to this.